source: src/GenPoly/Box.cc @ 59310bf

ADTaaron-thesisarm-ehast-experimentalcleanup-dtorsdeferred_resndemanglerenumforall-pointer-decayjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprnew-envno_listpersistent-indexerpthread-emulationqualifiedEnumresolv-newwith_gc
Last change on this file since 59310bf was 2edd80ae, checked in by Aaron Moss <a3moss@…>, 7 years ago

Fixes #29

  • Property mode set to 100644
File size: 87.2 KB
Line 
1//
2// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo
3//
4// The contents of this file are covered under the licence agreement in the
5// file "LICENCE" distributed with Cforall.
6//
7// Box.cc --
8//
9// Author           : Richard C. Bilson
10// Created On       : Mon May 18 07:44:20 2015
11// Last Modified By : Peter A. Buhr
12// Last Modified On : Wed Jun 21 15:49:59 2017
13// Update Count     : 346
14//
15
16#include <algorithm>
17#include <iterator>
18#include <list>
19#include <map>
20#include <set>
21#include <stack>
22#include <string>
23#include <utility>
24#include <vector>
25#include <cassert>
26
27#include "Box.h"
28#include "DeclMutator.h"
29#include "PolyMutator.h"
30#include "FindFunction.h"
31#include "ScopedSet.h"
32#include "ScrubTyVars.h"
33
34#include "Parser/ParseNode.h"
35
36#include "SynTree/Attribute.h"
37#include "SynTree/Constant.h"
38#include "SynTree/Declaration.h"
39#include "SynTree/Expression.h"
40#include "SynTree/Initializer.h"
41#include "SynTree/Mutator.h"
42#include "SynTree/Statement.h"
43#include "SynTree/Type.h"
44#include "SynTree/TypeSubstitution.h"
45
46#include "ResolvExpr/TypeEnvironment.h"
47#include "ResolvExpr/TypeMap.h"
48#include "ResolvExpr/typeops.h"
49
50#include "SymTab/Indexer.h"
51#include "SymTab/Mangler.h"
52
53#include "Common/ScopedMap.h"
54#include "Common/SemanticError.h"
55#include "Common/UniqueName.h"
56#include "Common/utility.h"
57
58#include "InitTweak/InitTweak.h"
59
60#include <ext/functional> // temporary
61
62namespace GenPoly {
63        namespace {
64                FunctionType *makeAdapterType( FunctionType *adaptee, const TyVarMap &tyVars );
65
66                /// Adds layout-generation functions to polymorphic types
67                class LayoutFunctionBuilder final : public DeclMutator {
68                        unsigned int functionNesting;  // current level of nested functions
69                public:
70                        LayoutFunctionBuilder() : functionNesting( 0 ) {}
71
72                        using DeclMutator::mutate;
73                        virtual DeclarationWithType *mutate( FunctionDecl *functionDecl ) override;
74                        virtual Declaration *mutate( StructDecl *structDecl ) override;
75                        virtual Declaration *mutate( UnionDecl *unionDecl ) override;
76                };
77
78                /// Replaces polymorphic return types with out-parameters, replaces calls to polymorphic functions with adapter calls as needed, and adds appropriate type variables to the function call
79                class Pass1 final : public PolyMutator {
80                  public:
81                        Pass1();
82
83                        using PolyMutator::mutate;
84                        virtual Expression *mutate( ApplicationExpr *appExpr ) override;
85                        virtual Expression *mutate( AddressExpr *addrExpr ) override;
86                        virtual Expression *mutate( UntypedExpr *expr ) override;
87                        virtual DeclarationWithType* mutate( FunctionDecl *functionDecl ) override;
88                        virtual TypeDecl *mutate( TypeDecl *typeDecl ) override;
89                        virtual Expression *mutate( CommaExpr *commaExpr ) override;
90                        virtual Expression *mutate( ConditionalExpr *condExpr ) override;
91                        virtual Statement * mutate( ReturnStmt *returnStmt ) override;
92                        virtual Type *mutate( PointerType *pointerType ) override;
93                        virtual Type * mutate( FunctionType *functionType ) override;
94
95                        virtual void doBeginScope() override;
96                        virtual void doEndScope() override;
97                  private:
98                        /// Pass the extra type parameters from polymorphic generic arguments or return types into a function application
99                        void passArgTypeVars( ApplicationExpr *appExpr, Type *parmType, Type *argBaseType, std::list< Expression *>::iterator &arg, const TyVarMap &exprTyVars, std::set< std::string > &seenTypes );
100                        /// passes extra type parameters into a polymorphic function application
101                        void passTypeVars( ApplicationExpr *appExpr, Type *polyRetType, std::list< Expression *>::iterator &arg, const TyVarMap &exprTyVars );
102                        /// wraps a function application with a new temporary for the out-parameter return value
103                        Expression *addRetParam( ApplicationExpr *appExpr, Type *retType, std::list< Expression *>::iterator &arg );
104                        /// Replaces all the type parameters of a generic type with their concrete equivalents under the current environment
105                        void replaceParametersWithConcrete( ApplicationExpr *appExpr, std::list< Expression* >& params );
106                        /// Replaces a polymorphic type with its concrete equivalant under the current environment (returns itself if concrete).
107                        /// If `doClone` is set to false, will not clone interior types
108                        Type *replaceWithConcrete( ApplicationExpr *appExpr, Type *type, bool doClone = true );
109                        /// wraps a function application returning a polymorphic type with a new temporary for the out-parameter return value
110                        Expression *addDynRetParam( ApplicationExpr *appExpr, Type *polyType, std::list< Expression *>::iterator &arg );
111                        Expression *applyAdapter( ApplicationExpr *appExpr, FunctionType *function, std::list< Expression *>::iterator &arg, const TyVarMap &exprTyVars );
112                        void boxParam( Type *formal, Expression *&arg, const TyVarMap &exprTyVars );
113                        void boxParams( ApplicationExpr *appExpr, FunctionType *function, std::list< Expression *>::iterator &arg, const TyVarMap &exprTyVars );
114                        void addInferredParams( ApplicationExpr *appExpr, FunctionType *functionType, std::list< Expression *>::iterator &arg, const TyVarMap &tyVars );
115                        /// Stores assignment operators from assertion list in local map of assignment operations
116                        void passAdapters( ApplicationExpr *appExpr, FunctionType *functionType, const TyVarMap &exprTyVars );
117                        FunctionDecl *makeAdapter( FunctionType *adaptee, FunctionType *realType, const std::string &mangleName, const TyVarMap &tyVars );
118                        /// Replaces intrinsic operator functions with their arithmetic desugaring
119                        Expression *handleIntrinsics( ApplicationExpr *appExpr );
120                        /// Inserts a new temporary variable into the current scope with an auto-generated name
121                        ObjectDecl *makeTemporary( Type *type );
122
123                        ScopedMap< std::string, DeclarationWithType* > adapters;     ///< Set of adapter functions in the current scope
124
125                        std::map< ApplicationExpr *, Expression * > retVals;
126
127                        DeclarationWithType *retval;
128                        UniqueName tempNamer;
129                };
130
131                /// * Moves polymorphic returns in function types to pointer-type parameters
132                /// * adds type size and assertion parameters to parameter lists
133                class Pass2 final : public PolyMutator {
134                  public:
135                        template< typename DeclClass >
136                        DeclClass *handleDecl( DeclClass *decl );
137                        template< typename AggDecl >
138                        AggDecl * handleAggDecl( AggDecl * aggDecl );
139
140                        typedef PolyMutator Parent;
141                        using Parent::mutate;
142                        virtual DeclarationWithType *mutate( FunctionDecl *functionDecl ) override;
143                        virtual ObjectDecl *mutate( ObjectDecl *objectDecl ) override;
144                        virtual StructDecl *mutate( StructDecl *structDecl ) override;
145                        virtual UnionDecl *mutate( UnionDecl *unionDecl ) override;
146                        virtual TypeDecl *mutate( TypeDecl *typeDecl ) override;
147                        virtual TypedefDecl *mutate( TypedefDecl *typedefDecl ) override;
148                        virtual Type *mutate( PointerType *pointerType ) override;
149                        virtual Type *mutate( FunctionType *funcType ) override;
150
151                  private:
152                        void addAdapters( FunctionType *functionType );
153
154                        std::map< UniqueId, std::string > adapterName;
155                };
156
157                /// Replaces member and size/align/offsetof expressions on polymorphic generic types with calculated expressions.
158                /// * Replaces member expressions for polymorphic types with calculated add-field-offset-and-dereference
159                /// * Calculates polymorphic offsetof expressions from offset array
160                /// * Inserts dynamic calculation of polymorphic type layouts where needed
161                class PolyGenericCalculator final : public PolyMutator {
162                public:
163                        typedef PolyMutator Parent;
164                        using Parent::mutate;
165
166                        PolyGenericCalculator();
167
168                        template< typename DeclClass >
169                        DeclClass *handleDecl( DeclClass *decl, Type *type );
170                        virtual DeclarationWithType *mutate( FunctionDecl *functionDecl ) override;
171                        virtual ObjectDecl *mutate( ObjectDecl *objectDecl ) override;
172                        virtual TypedefDecl *mutate( TypedefDecl *objectDecl ) override;
173                        virtual TypeDecl *mutate( TypeDecl *objectDecl ) override;
174                        virtual Statement *mutate( DeclStmt *declStmt ) override;
175                        virtual Type *mutate( PointerType *pointerType ) override;
176                        virtual Type *mutate( FunctionType *funcType ) override;
177                        virtual Expression *mutate( MemberExpr *memberExpr ) override;
178                        virtual Expression *mutate( SizeofExpr *sizeofExpr ) override;
179                        virtual Expression *mutate( AlignofExpr *alignofExpr ) override;
180                        virtual Expression *mutate( OffsetofExpr *offsetofExpr ) override;
181                        virtual Expression *mutate( OffsetPackExpr *offsetPackExpr ) override;
182
183                        virtual void doBeginScope() override;
184                        virtual void doEndScope() override;
185
186                private:
187                        /// Makes a new variable in the current scope with the given name, type & optional initializer
188                        ObjectDecl *makeVar( const std::string &name, Type *type, Initializer *init = 0 );
189                        /// returns true if the type has a dynamic layout; such a layout will be stored in appropriately-named local variables when the function returns
190                        bool findGeneric( Type *ty );
191                        /// adds type parameters to the layout call; will generate the appropriate parameters if needed
192                        void addOtypeParamsToLayoutCall( UntypedExpr *layoutCall, const std::list< Type* > &otypeParams );
193
194                        /// Enters a new scope for type-variables, adding the type variables from ty
195                        void beginTypeScope( Type *ty );
196                        /// Exits the type-variable scope
197                        void endTypeScope();
198
199                        ScopedSet< std::string > knownLayouts;          ///< Set of generic type layouts known in the current scope, indexed by sizeofName
200                        ScopedSet< std::string > knownOffsets;          ///< Set of non-generic types for which the offset array exists in the current scope, indexed by offsetofName
201                        UniqueName bufNamer;                           ///< Namer for VLA buffers
202                };
203
204                /// Replaces initialization of polymorphic values with alloca, declaration of dtype/ftype with appropriate void expression, sizeof expressions of polymorphic types with the proper variable, and strips fields from generic struct declarations.
205                class Pass3 final : public PolyMutator {
206                  public:
207                        template< typename DeclClass >
208                        DeclClass *handleDecl( DeclClass *decl, Type *type );
209
210                        using PolyMutator::mutate;
211                        virtual DeclarationWithType *mutate( FunctionDecl *functionDecl ) override;
212                        virtual Declaration *mutate( StructDecl *structDecl ) override;
213                        virtual Declaration *mutate( UnionDecl *unionDecl ) override;
214                        virtual ObjectDecl *mutate( ObjectDecl *objectDecl ) override;
215                        virtual TypedefDecl *mutate( TypedefDecl *objectDecl ) override;
216                        virtual TypeDecl *mutate( TypeDecl *objectDecl ) override;
217                        virtual Type *mutate( PointerType *pointerType ) override;
218                        virtual Type *mutate( FunctionType *funcType ) override;
219                  private:
220                };
221
222        } // anonymous namespace
223
224        /// version of mutateAll with special handling for translation unit so you can check the end of the prelude when debugging
225        template< typename MutatorType >
226        inline void mutateTranslationUnit( std::list< Declaration* > &translationUnit, MutatorType &mutator ) {
227                bool seenIntrinsic = false;
228                SemanticError errors;
229                for ( typename std::list< Declaration* >::iterator i = translationUnit.begin(); i != translationUnit.end(); ++i ) {
230                        try {
231                                if ( *i ) {
232                                        if ( (*i)->get_linkage() == LinkageSpec::Intrinsic ) {
233                                                seenIntrinsic = true;
234                                        } else if ( seenIntrinsic ) {
235                                                seenIntrinsic = false; // break on this line when debugging for end of prelude
236                                        }
237
238                                        *i = dynamic_cast< Declaration* >( (*i)->acceptMutator( mutator ) );
239                                        assert( *i );
240                                } // if
241                        } catch( SemanticError &e ) {
242                                e.set_location( (*i)->location );
243                                errors.append( e );
244                        } // try
245                } // for
246                if ( ! errors.isEmpty() ) {
247                        throw errors;
248                } // if
249        }
250
251        void box( std::list< Declaration *>& translationUnit ) {
252                LayoutFunctionBuilder layoutBuilder;
253                Pass1 pass1;
254                Pass2 pass2;
255                PolyGenericCalculator polyCalculator;
256                Pass3 pass3;
257
258                layoutBuilder.mutateDeclarationList( translationUnit );
259                mutateTranslationUnit/*All*/( translationUnit, pass1 );
260                mutateTranslationUnit/*All*/( translationUnit, pass2 );
261                mutateTranslationUnit/*All*/( translationUnit, polyCalculator );
262                mutateTranslationUnit/*All*/( translationUnit, pass3 );
263        }
264
265        ////////////////////////////////// LayoutFunctionBuilder ////////////////////////////////////////////
266
267        DeclarationWithType *LayoutFunctionBuilder::mutate( FunctionDecl *functionDecl ) {
268                functionDecl->set_functionType( maybeMutate( functionDecl->get_functionType(), *this ) );
269                ++functionNesting;
270                functionDecl->set_statements( maybeMutate( functionDecl->get_statements(), *this ) );
271                --functionNesting;
272                return functionDecl;
273        }
274
275        /// Get a list of type declarations that will affect a layout function
276        std::list< TypeDecl* > takeOtypeOnly( std::list< TypeDecl* > &decls ) {
277                std::list< TypeDecl * > otypeDecls;
278
279                for ( std::list< TypeDecl* >::const_iterator decl = decls.begin(); decl != decls.end(); ++decl ) {
280                        if ( (*decl)->isComplete() ) {
281                                otypeDecls.push_back( *decl );
282                        }
283                }
284
285                return otypeDecls;
286        }
287
288        /// Adds parameters for otype layout to a function type
289        void addOtypeParams( FunctionType *layoutFnType, std::list< TypeDecl* > &otypeParams ) {
290                BasicType sizeAlignType( Type::Qualifiers(), BasicType::LongUnsignedInt );
291
292                for ( std::list< TypeDecl* >::const_iterator param = otypeParams.begin(); param != otypeParams.end(); ++param ) {
293                        TypeInstType paramType( Type::Qualifiers(), (*param)->get_name(), *param );
294                        std::string paramName = mangleType( &paramType );
295                        layoutFnType->get_parameters().push_back( new ObjectDecl( sizeofName( paramName ), Type::StorageClasses(), LinkageSpec::Cforall, 0, sizeAlignType.clone(), 0 ) );
296                        layoutFnType->get_parameters().push_back( new ObjectDecl( alignofName( paramName ), Type::StorageClasses(), LinkageSpec::Cforall, 0, sizeAlignType.clone(), 0 ) );
297                }
298        }
299
300        /// Builds a layout function declaration
301        FunctionDecl *buildLayoutFunctionDecl( AggregateDecl *typeDecl, unsigned int functionNesting, FunctionType *layoutFnType ) {
302                // Routines at global scope marked "static" to prevent multiple definitions is separate translation units
303                // because each unit generates copies of the default routines for each aggregate.
304                FunctionDecl *layoutDecl = new FunctionDecl( layoutofName( typeDecl ),
305                                                                                                         functionNesting > 0 ? Type::StorageClasses() : Type::StorageClasses( Type::Static ),
306                                                                                                         LinkageSpec::AutoGen, layoutFnType, new CompoundStmt( noLabels ),
307                                                                                                         std::list< Attribute * >(), Type::FuncSpecifiers( Type::Inline ) );
308                layoutDecl->fixUniqueId();
309                return layoutDecl;
310        }
311
312        /// Makes a unary operation
313        Expression *makeOp( const std::string &name, Expression *arg ) {
314                UntypedExpr *expr = new UntypedExpr( new NameExpr( name ) );
315                expr->get_args().push_back( arg );
316                return expr;
317        }
318
319        /// Makes a binary operation
320        Expression *makeOp( const std::string &name, Expression *lhs, Expression *rhs ) {
321                UntypedExpr *expr = new UntypedExpr( new NameExpr( name ) );
322                expr->get_args().push_back( lhs );
323                expr->get_args().push_back( rhs );
324                return expr;
325        }
326
327        /// Returns the dereference of a local pointer variable
328        Expression *derefVar( ObjectDecl *var ) {
329                return makeOp( "*?", new VariableExpr( var ) );
330        }
331
332        /// makes an if-statement with a single-expression if-block and no then block
333        Statement *makeCond( Expression *cond, Expression *ifPart ) {
334                return new IfStmt( noLabels, cond, new ExprStmt( noLabels, ifPart ), 0 );
335        }
336
337        /// makes a statement that assigns rhs to lhs if lhs < rhs
338        Statement *makeAssignMax( Expression *lhs, Expression *rhs ) {
339                return makeCond( makeOp( "?<?", lhs, rhs ), makeOp( "?=?", lhs->clone(), rhs->clone() ) );
340        }
341
342        /// makes a statement that aligns lhs to rhs (rhs should be an integer power of two)
343        Statement *makeAlignTo( Expression *lhs, Expression *rhs ) {
344                // check that the lhs is zeroed out to the level of rhs
345                Expression *ifCond = makeOp( "?&?", lhs, makeOp( "?-?", rhs, new ConstantExpr( Constant::from_ulong( 1 ) ) ) );
346                // if not aligned, increment to alignment
347                Expression *ifExpr = makeOp( "?+=?", lhs->clone(), makeOp( "?-?", rhs->clone(), ifCond->clone() ) );
348                return makeCond( ifCond, ifExpr );
349        }
350
351        /// adds an expression to a compound statement
352        void addExpr( CompoundStmt *stmts, Expression *expr ) {
353                stmts->get_kids().push_back( new ExprStmt( noLabels, expr ) );
354        }
355
356        /// adds a statement to a compound statement
357        void addStmt( CompoundStmt *stmts, Statement *stmt ) {
358                stmts->get_kids().push_back( stmt );
359        }
360
361        Declaration *LayoutFunctionBuilder::mutate( StructDecl *structDecl ) {
362                // do not generate layout function for "empty" tag structs
363                if ( structDecl->get_members().empty() ) return structDecl;
364
365                // get parameters that can change layout, exiting early if none
366                std::list< TypeDecl* > otypeParams = takeOtypeOnly( structDecl->get_parameters() );
367                if ( otypeParams.empty() ) return structDecl;
368
369                // build layout function signature
370                FunctionType *layoutFnType = new FunctionType( Type::Qualifiers(), false );
371                BasicType *sizeAlignType = new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt );
372                PointerType *sizeAlignOutType = new PointerType( Type::Qualifiers(), sizeAlignType );
373
374                ObjectDecl *sizeParam = new ObjectDecl( sizeofName( structDecl->get_name() ), Type::StorageClasses(), LinkageSpec::Cforall, 0, sizeAlignOutType, 0 );
375                layoutFnType->get_parameters().push_back( sizeParam );
376                ObjectDecl *alignParam = new ObjectDecl( alignofName( structDecl->get_name() ), Type::StorageClasses(), LinkageSpec::Cforall, 0, sizeAlignOutType->clone(), 0 );
377                layoutFnType->get_parameters().push_back( alignParam );
378                ObjectDecl *offsetParam = new ObjectDecl( offsetofName( structDecl->get_name() ), Type::StorageClasses(), LinkageSpec::Cforall, 0, sizeAlignOutType->clone(), 0 );
379                layoutFnType->get_parameters().push_back( offsetParam );
380                addOtypeParams( layoutFnType, otypeParams );
381
382                // build function decl
383                FunctionDecl *layoutDecl = buildLayoutFunctionDecl( structDecl, functionNesting, layoutFnType );
384
385                // calculate struct layout in function body
386
387                // initialize size and alignment to 0 and 1 (will have at least one member to re-edit size)
388                addExpr( layoutDecl->get_statements(), makeOp( "?=?", derefVar( sizeParam ), new ConstantExpr( Constant::from_ulong( 0 ) ) ) );
389                addExpr( layoutDecl->get_statements(), makeOp( "?=?", derefVar( alignParam ), new ConstantExpr( Constant::from_ulong( 1 ) ) ) );
390                unsigned long n_members = 0;
391                bool firstMember = true;
392                for ( std::list< Declaration* >::const_iterator member = structDecl->get_members().begin(); member != structDecl->get_members().end(); ++member ) {
393                        DeclarationWithType *dwt = dynamic_cast< DeclarationWithType * >( *member );
394                        assert( dwt );
395                        Type *memberType = dwt->get_type();
396
397                        if ( firstMember ) {
398                                firstMember = false;
399                        } else {
400                                // make sure all members after the first (automatically aligned at 0) are properly padded for alignment
401                                addStmt( layoutDecl->get_statements(), makeAlignTo( derefVar( sizeParam ), new AlignofExpr( memberType->clone() ) ) );
402                        }
403
404                        // place current size in the current offset index
405                        addExpr( layoutDecl->get_statements(), makeOp( "?=?", makeOp( "?[?]", new VariableExpr( offsetParam ), new ConstantExpr( Constant::from_ulong( n_members ) ) ),
406                                                                              derefVar( sizeParam ) ) );
407                        ++n_members;
408
409                        // add member size to current size
410                        addExpr( layoutDecl->get_statements(), makeOp( "?+=?", derefVar( sizeParam ), new SizeofExpr( memberType->clone() ) ) );
411
412                        // take max of member alignment and global alignment
413                        addStmt( layoutDecl->get_statements(), makeAssignMax( derefVar( alignParam ), new AlignofExpr( memberType->clone() ) ) );
414                }
415                // make sure the type is end-padded to a multiple of its alignment
416                addStmt( layoutDecl->get_statements(), makeAlignTo( derefVar( sizeParam ), derefVar( alignParam ) ) );
417
418                addDeclarationAfter( layoutDecl );
419                return structDecl;
420        }
421
422        Declaration *LayoutFunctionBuilder::mutate( UnionDecl *unionDecl ) {
423                // do not generate layout function for "empty" tag unions
424                if ( unionDecl->get_members().empty() ) return unionDecl;
425
426                // get parameters that can change layout, exiting early if none
427                std::list< TypeDecl* > otypeParams = takeOtypeOnly( unionDecl->get_parameters() );
428                if ( otypeParams.empty() ) return unionDecl;
429
430                // build layout function signature
431                FunctionType *layoutFnType = new FunctionType( Type::Qualifiers(), false );
432                BasicType *sizeAlignType = new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt );
433                PointerType *sizeAlignOutType = new PointerType( Type::Qualifiers(), sizeAlignType );
434
435                ObjectDecl *sizeParam = new ObjectDecl( sizeofName( unionDecl->get_name() ), Type::StorageClasses(), LinkageSpec::Cforall, 0, sizeAlignOutType, 0 );
436                layoutFnType->get_parameters().push_back( sizeParam );
437                ObjectDecl *alignParam = new ObjectDecl( alignofName( unionDecl->get_name() ), Type::StorageClasses(), LinkageSpec::Cforall, 0, sizeAlignOutType->clone(), 0 );
438                layoutFnType->get_parameters().push_back( alignParam );
439                addOtypeParams( layoutFnType, otypeParams );
440
441                // build function decl
442                FunctionDecl *layoutDecl = buildLayoutFunctionDecl( unionDecl, functionNesting, layoutFnType );
443
444                // calculate union layout in function body
445                addExpr( layoutDecl->get_statements(), makeOp( "?=?", derefVar( sizeParam ), new ConstantExpr( Constant::from_ulong( 1 ) ) ) );
446                addExpr( layoutDecl->get_statements(), makeOp( "?=?", derefVar( alignParam ), new ConstantExpr( Constant::from_ulong( 1 ) ) ) );
447                for ( std::list< Declaration* >::const_iterator member = unionDecl->get_members().begin(); member != unionDecl->get_members().end(); ++member ) {
448                        DeclarationWithType *dwt = dynamic_cast< DeclarationWithType * >( *member );
449                        assert( dwt );
450                        Type *memberType = dwt->get_type();
451
452                        // take max member size and global size
453                        addStmt( layoutDecl->get_statements(), makeAssignMax( derefVar( sizeParam ), new SizeofExpr( memberType->clone() ) ) );
454
455                        // take max of member alignment and global alignment
456                        addStmt( layoutDecl->get_statements(), makeAssignMax( derefVar( alignParam ), new AlignofExpr( memberType->clone() ) ) );
457                }
458                // make sure the type is end-padded to a multiple of its alignment
459                addStmt( layoutDecl->get_statements(), makeAlignTo( derefVar( sizeParam ), derefVar( alignParam ) ) );
460
461                addDeclarationAfter( layoutDecl );
462                return unionDecl;
463        }
464
465        ////////////////////////////////////////// Pass1 ////////////////////////////////////////////////////
466
467        namespace {
468                std::string makePolyMonoSuffix( FunctionType * function, const TyVarMap &tyVars ) {
469                        std::stringstream name;
470
471                        // NOTE: this function previously used isPolyObj, which failed to produce
472                        // the correct thing in some situations. It's not clear to me why this wasn't working.
473
474                        // if the return type or a parameter type involved polymorphic types, then the adapter will need
475                        // to take those polymorphic types as pointers. Therefore, there can be two different functions
476                        // with the same mangled name, so we need to further mangle the names.
477                        for ( std::list< DeclarationWithType *>::iterator retval = function->get_returnVals().begin(); retval != function->get_returnVals().end(); ++retval ) {
478                                if ( isPolyType( (*retval)->get_type(), tyVars ) ) {
479                                        name << "P";
480                                } else {
481                                        name << "M";
482                                }
483                        }
484                        name << "_";
485                        std::list< DeclarationWithType *> &paramList = function->get_parameters();
486                        for ( std::list< DeclarationWithType *>::iterator arg = paramList.begin(); arg != paramList.end(); ++arg ) {
487                                if ( isPolyType( (*arg)->get_type(), tyVars ) ) {
488                                        name << "P";
489                                } else {
490                                        name << "M";
491                                }
492                        } // for
493                        return name.str();
494                }
495
496                std::string mangleAdapterName( FunctionType * function, const TyVarMap &tyVars ) {
497                        return SymTab::Mangler::mangle( function ) + makePolyMonoSuffix( function, tyVars );
498                }
499
500                std::string makeAdapterName( const std::string &mangleName ) {
501                        return "_adapter" + mangleName;
502                }
503
504                Pass1::Pass1() : tempNamer( "_temp" ) {}
505
506                DeclarationWithType *Pass1::mutate( FunctionDecl *functionDecl ) {
507                        if ( functionDecl->get_statements() ) {         // empty routine body ?
508                                // std::cerr << "mutating function: " << functionDecl->get_mangleName() << std::endl;
509                                doBeginScope();
510                                scopeTyVars.beginScope();
511
512                                DeclarationWithType *oldRetval = retval;
513
514                                // process polymorphic return value
515                                retval = nullptr;
516                                if ( isDynRet( functionDecl->get_functionType() ) && functionDecl->get_linkage() != LinkageSpec::C ) {
517                                        retval = functionDecl->get_functionType()->get_returnVals().front();
518
519                                        // give names to unnamed return values
520                                        if ( retval->get_name() == "" ) {
521                                                retval->set_name( "_retparm" );
522                                                retval->set_linkage( LinkageSpec::C );
523                                        } // if
524                                } // if
525
526                                FunctionType *functionType = functionDecl->get_functionType();
527                                makeTyVarMap( functionDecl->get_functionType(), scopeTyVars );
528
529                                std::list< DeclarationWithType *> &paramList = functionType->get_parameters();
530                                std::list< FunctionType *> functions;
531                                for ( Type::ForallList::iterator tyVar = functionType->get_forall().begin(); tyVar != functionType->get_forall().end(); ++tyVar ) {
532                                        for ( std::list< DeclarationWithType *>::iterator assert = (*tyVar)->get_assertions().begin(); assert != (*tyVar)->get_assertions().end(); ++assert ) {
533                                                findFunction( (*assert)->get_type(), functions, scopeTyVars, needsAdapter );
534                                        } // for
535                                } // for
536                                for ( std::list< DeclarationWithType *>::iterator arg = paramList.begin(); arg != paramList.end(); ++arg ) {
537                                        findFunction( (*arg)->get_type(), functions, scopeTyVars, needsAdapter );
538                                } // for
539
540                                for ( std::list< FunctionType *>::iterator funType = functions.begin(); funType != functions.end(); ++funType ) {
541                                        std::string mangleName = mangleAdapterName( *funType, scopeTyVars );
542                                        if ( adapters.find( mangleName ) == adapters.end() ) {
543                                                std::string adapterName = makeAdapterName( mangleName );
544                                                adapters.insert( std::pair< std::string, DeclarationWithType *>( mangleName, new ObjectDecl( adapterName, Type::StorageClasses(), LinkageSpec::C, nullptr, new PointerType( Type::Qualifiers(), makeAdapterType( *funType, scopeTyVars ) ), nullptr ) ) );
545                                        } // if
546                                } // for
547
548                                functionDecl->set_statements( functionDecl->get_statements()->acceptMutator( *this ) );
549
550                                scopeTyVars.endScope();
551                                retval = oldRetval;
552                                doEndScope();
553                                // std::cerr << "end function: " << functionDecl->get_mangleName() << std::endl;
554                        } // if
555                        return functionDecl;
556                }
557
558                TypeDecl *Pass1::mutate( TypeDecl *typeDecl ) {
559                        addToTyVarMap( typeDecl, scopeTyVars );
560                        return Mutator::mutate( typeDecl );
561                }
562
563                Expression *Pass1::mutate( CommaExpr *commaExpr ) {
564                        // Attempting to find application expressions that were mutated by the copy constructor passes
565                        // to use an explicit return variable, so that the variable can be reused as a parameter to the
566                        // call rather than creating a new temp variable. Previously this step was an optimization, but
567                        // with the introduction of tuples and UniqueExprs, it is necessary to ensure that they use the same variable.
568                        // Essentially, looking for pattern: (x=f(...), x)
569                        // To compound the issue, the right side can be *x, etc. because of lvalue-returning functions
570                        if ( UntypedExpr * assign = dynamic_cast< UntypedExpr * >( commaExpr->get_arg1() ) ) {
571                                if ( InitTweak::isAssignment( InitTweak::getFunctionName( assign ) ) ) {
572                                        assert( assign->get_args().size() == 2 );
573                                        if ( ApplicationExpr * appExpr = dynamic_cast< ApplicationExpr * > ( assign->get_args().back() ) ) {
574                                                // first argument is assignable, so it must be an lvalue, so it should be legal to take its address.
575                                                retVals[appExpr] = assign->get_args().front();
576                                        }
577                                }
578                        }
579
580                        commaExpr->set_arg1( maybeMutate( commaExpr->get_arg1(), *this ) );
581                        commaExpr->set_arg2( maybeMutate( commaExpr->get_arg2(), *this ) );
582                        return commaExpr;
583                }
584
585                Expression *Pass1::mutate( ConditionalExpr *condExpr ) {
586                        condExpr->set_arg1( maybeMutate( condExpr->get_arg1(), *this ) );
587                        condExpr->set_arg2( maybeMutate( condExpr->get_arg2(), *this ) );
588                        condExpr->set_arg3( maybeMutate( condExpr->get_arg3(), *this ) );
589                        return condExpr;
590
591                }
592
593                void Pass1::passArgTypeVars( ApplicationExpr *appExpr, Type *parmType, Type *argBaseType, std::list< Expression *>::iterator &arg, const TyVarMap &exprTyVars, std::set< std::string > &seenTypes ) {
594                        Type *polyType = isPolyType( parmType, exprTyVars );
595                        if ( polyType && ! dynamic_cast< TypeInstType* >( polyType ) ) {
596                                std::string typeName = mangleType( polyType );
597                                if ( seenTypes.count( typeName ) ) return;
598
599                                arg = appExpr->get_args().insert( arg, new SizeofExpr( argBaseType->clone() ) );
600                                arg++;
601                                arg = appExpr->get_args().insert( arg, new AlignofExpr( argBaseType->clone() ) );
602                                arg++;
603                                if ( dynamic_cast< StructInstType* >( polyType ) ) {
604                                        if ( StructInstType *argBaseStructType = dynamic_cast< StructInstType* >( argBaseType ) ) {
605                                                // zero-length arrays are forbidden by C, so don't pass offset for empty struct
606                                                if ( ! argBaseStructType->get_baseStruct()->get_members().empty() ) {
607                                                        arg = appExpr->get_args().insert( arg, new OffsetPackExpr( argBaseStructType->clone() ) );
608                                                        arg++;
609                                                }
610                                        } else {
611                                                throw SemanticError( "Cannot pass non-struct type for generic struct" );
612                                        }
613                                }
614
615                                seenTypes.insert( typeName );
616                        }
617                }
618
619                void Pass1::passTypeVars( ApplicationExpr *appExpr, Type *polyRetType, std::list< Expression *>::iterator &arg, const TyVarMap &exprTyVars ) {
620                        // pass size/align for type variables
621                        for ( TyVarMap::const_iterator tyParm = exprTyVars.begin(); tyParm != exprTyVars.end(); ++tyParm ) {
622                                ResolvExpr::EqvClass eqvClass;
623                                assert( env );
624                                if ( tyParm->second.isComplete ) {
625                                        Type *concrete = env->lookup( tyParm->first );
626                                        if ( concrete ) {
627                                                arg = appExpr->get_args().insert( arg, new SizeofExpr( concrete->clone() ) );
628                                                arg++;
629                                                arg = appExpr->get_args().insert( arg, new AlignofExpr( concrete->clone() ) );
630                                                arg++;
631                                        } else {
632                                                // xxx - should this be an assertion?
633                                                std::string x = env ? toString( *env ) : "missing env";
634                                                throw SemanticError( x + "\n" + "unbound type variable: " + tyParm->first + " in application ", appExpr );
635                                        } // if
636                                } // if
637                        } // for
638
639                        // add size/align for generic types to parameter list
640                        if ( ! appExpr->get_function()->has_result() ) return;
641                        FunctionType *funcType = getFunctionType( appExpr->get_function()->get_result() );
642                        assert( funcType );
643
644                        std::list< DeclarationWithType* >::const_iterator fnParm = funcType->get_parameters().begin();
645                        std::list< Expression* >::const_iterator fnArg = arg;
646                        std::set< std::string > seenTypes; ///< names for generic types we've seen
647
648                        // a polymorphic return type may need to be added to the argument list
649                        if ( polyRetType ) {
650                                Type *concRetType = replaceWithConcrete( appExpr, polyRetType );
651                                passArgTypeVars( appExpr, polyRetType, concRetType, arg, exprTyVars, seenTypes );
652                                ++fnArg; // skip the return parameter in the argument list
653                        }
654
655                        // add type information args for presently unseen types in parameter list
656                        for ( ; fnParm != funcType->get_parameters().end() && fnArg != appExpr->get_args().end(); ++fnParm, ++fnArg ) {
657                                if ( ! (*fnArg)->get_result() ) continue;
658                                Type * argType = (*fnArg)->get_result();
659                                passArgTypeVars( appExpr, (*fnParm)->get_type(), argType, arg, exprTyVars, seenTypes );
660                        }
661                }
662
663                ObjectDecl *Pass1::makeTemporary( Type *type ) {
664                        ObjectDecl *newObj = new ObjectDecl( tempNamer.newName(), Type::StorageClasses(), LinkageSpec::C, 0, type, 0 );
665                        stmtsToAdd.push_back( new DeclStmt( noLabels, newObj ) );
666                        return newObj;
667                }
668
669                Expression *Pass1::addRetParam( ApplicationExpr *appExpr, Type *retType, std::list< Expression *>::iterator &arg ) {
670                        // Create temporary to hold return value of polymorphic function and produce that temporary as a result
671                        // using a comma expression.
672                        assert( retType );
673
674                        Expression * paramExpr = nullptr;
675                        // try to use existing return value parameter if it exists, otherwise create a new temporary
676                        if ( retVals.count( appExpr ) ) {
677                                paramExpr = retVals[appExpr]->clone();
678                        } else {
679                                ObjectDecl *newObj = makeTemporary( retType->clone() );
680                                paramExpr = new VariableExpr( newObj );
681                        }
682                        Expression * retExpr = paramExpr->clone();
683
684                        // If the type of the temporary is not polymorphic, box temporary by taking its address;
685                        // otherwise the temporary is already boxed and can be used directly.
686                        if ( ! isPolyType( paramExpr->get_result(), scopeTyVars, env ) ) {
687                                paramExpr = new AddressExpr( paramExpr );
688                        } // if
689                        arg = appExpr->get_args().insert( arg, paramExpr ); // add argument to function call
690                        arg++;
691                        // Build a comma expression to call the function and emulate a normal return.
692                        CommaExpr *commaExpr = new CommaExpr( appExpr, retExpr );
693                        commaExpr->set_env( appExpr->get_env() );
694                        appExpr->set_env( 0 );
695                        return commaExpr;
696                }
697
698                void Pass1::replaceParametersWithConcrete( ApplicationExpr *appExpr, std::list< Expression* >& params ) {
699                        for ( std::list< Expression* >::iterator param = params.begin(); param != params.end(); ++param ) {
700                                TypeExpr *paramType = dynamic_cast< TypeExpr* >( *param );
701                                assertf(paramType, "Aggregate parameters should be type expressions");
702                                paramType->set_type( replaceWithConcrete( appExpr, paramType->get_type(), false ) );
703                        }
704                }
705
706                Type *Pass1::replaceWithConcrete( ApplicationExpr *appExpr, Type *type, bool doClone ) {
707                        if ( TypeInstType *typeInst = dynamic_cast< TypeInstType * >( type ) ) {
708                                Type *concrete = env->lookup( typeInst->get_name() );
709                                if ( concrete == 0 ) {
710                                        return typeInst;
711                                        // xxx - should this be an assertion?
712//                                      std::string x = env ? toString( *env ) : "missing env";
713//                                      throw SemanticError( x + "\n" + "Unbound type variable " + typeInst->get_name() + " in ", appExpr );
714                                } // if
715                                return concrete;
716                        } else if ( StructInstType *structType = dynamic_cast< StructInstType* >( type ) ) {
717                                if ( doClone ) {
718                                        structType = structType->clone();
719                                }
720                                replaceParametersWithConcrete( appExpr, structType->get_parameters() );
721                                return structType;
722                        } else if ( UnionInstType *unionType = dynamic_cast< UnionInstType* >( type ) ) {
723                                if ( doClone ) {
724                                        unionType = unionType->clone();
725                                }
726                                replaceParametersWithConcrete( appExpr, unionType->get_parameters() );
727                                return unionType;
728                        }
729                        return type;
730                }
731
732                Expression *Pass1::addDynRetParam( ApplicationExpr *appExpr, Type *dynType, std::list< Expression *>::iterator &arg ) {
733                        assert( env );
734                        Type *concrete = replaceWithConcrete( appExpr, dynType );
735                        // add out-parameter for return value
736                        return addRetParam( appExpr, concrete, arg );
737                }
738
739                Expression *Pass1::applyAdapter( ApplicationExpr *appExpr, FunctionType *function, std::list< Expression *>::iterator &arg, const TyVarMap &tyVars ) {
740                        Expression *ret = appExpr;
741//                      if ( ! function->get_returnVals().empty() && isPolyType( function->get_returnVals().front()->get_type(), tyVars ) ) {
742                        if ( isDynRet( function, tyVars ) ) {
743                                ret = addRetParam( appExpr, function->get_returnVals().front()->get_type(), arg );
744                        } // if
745                        std::string mangleName = mangleAdapterName( function, tyVars );
746                        std::string adapterName = makeAdapterName( mangleName );
747
748                        // cast adaptee to void (*)(), since it may have any type inside a polymorphic function
749                        Type * adapteeType = new PointerType( Type::Qualifiers(), new FunctionType( Type::Qualifiers(), true ) );
750                        appExpr->get_args().push_front( new CastExpr( appExpr->get_function(), adapteeType ) );
751                        appExpr->set_function( new NameExpr( adapterName ) ); // xxx - result is never set on NameExpr
752
753                        return ret;
754                }
755
756                void Pass1::boxParam( Type *param, Expression *&arg, const TyVarMap &exprTyVars ) {
757                        assert( arg->has_result() );
758                        if ( isPolyType( param, exprTyVars ) ) {
759                                if ( isPolyType( arg->get_result() ) ) {
760                                        // if the argument's type is polymorphic, we don't need to box again!
761                                        return;
762                                } else if ( arg->get_result()->get_lvalue() ) {
763                                        // VariableExpr and MemberExpr are lvalues; need to check this isn't coming from the second arg of a comma expression though (not an lvalue)
764                                        // xxx - need to test that this code is still reachable
765                                        if ( CommaExpr *commaArg = dynamic_cast< CommaExpr* >( arg ) ) {
766                                                commaArg->set_arg2( new AddressExpr( commaArg->get_arg2() ) );
767                                        } else {
768                                                arg = new AddressExpr( arg );
769                                        }
770                                        if ( ! ResolvExpr::typesCompatible( param, arg->get_result(), SymTab::Indexer() ) ) {
771                                                // silence warnings by casting boxed parameters when the actual type does not match up with the formal type.
772                                                arg = new CastExpr( arg, param->clone() );
773                                        }
774                                } else {
775                                        // use type computed in unification to declare boxed variables
776                                        Type * newType = param->clone();
777                                        if ( env ) env->apply( newType );
778                                        ObjectDecl *newObj = new ObjectDecl( tempNamer.newName(), Type::StorageClasses(), LinkageSpec::C, 0, newType, 0 );
779                                        newObj->get_type()->get_qualifiers() = Type::Qualifiers(); // TODO: is this right???
780                                        stmtsToAdd.push_back( new DeclStmt( noLabels, newObj ) );
781                                        UntypedExpr *assign = new UntypedExpr( new NameExpr( "?=?" ) );
782                                        assign->get_args().push_back( new VariableExpr( newObj ) );
783                                        assign->get_args().push_back( arg );
784                                        stmtsToAdd.push_back( new ExprStmt( noLabels, assign ) );
785                                        arg = new AddressExpr( new VariableExpr( newObj ) );
786                                } // if
787                        } // if
788                }
789
790                /// cast parameters to polymorphic functions so that types are replaced with
791                /// void * if they are type parameters in the formal type.
792                /// this gets rid of warnings from gcc.
793                void addCast( Expression *&actual, Type *formal, const TyVarMap &tyVars ) {
794                        if ( getFunctionType( formal ) ) {
795                                Type * newType = formal->clone();
796                                newType = ScrubTyVars::scrub( newType, tyVars );
797                                actual = new CastExpr( actual, newType );
798                        } // if
799                }
800
801                void Pass1::boxParams( ApplicationExpr *appExpr, FunctionType *function, std::list< Expression *>::iterator &arg, const TyVarMap &exprTyVars ) {
802                        for ( std::list< DeclarationWithType *>::const_iterator param = function->get_parameters().begin(); param != function->get_parameters().end(); ++param, ++arg ) {
803                                assertf( arg != appExpr->get_args().end(), "boxParams: missing argument for param %s to %s in %s", toString( *param ).c_str(), toString( function ).c_str(), toString( appExpr ).c_str() );
804                                addCast( *arg, (*param)->get_type(), exprTyVars );
805                                boxParam( (*param)->get_type(), *arg, exprTyVars );
806                        } // for
807                }
808
809                void Pass1::addInferredParams( ApplicationExpr *appExpr, FunctionType *functionType, std::list< Expression *>::iterator &arg, const TyVarMap &tyVars ) {
810                        std::list< Expression *>::iterator cur = arg;
811                        for ( Type::ForallList::iterator tyVar = functionType->get_forall().begin(); tyVar != functionType->get_forall().end(); ++tyVar ) {
812                                for ( std::list< DeclarationWithType *>::iterator assert = (*tyVar)->get_assertions().begin(); assert != (*tyVar)->get_assertions().end(); ++assert ) {
813                                        InferredParams::const_iterator inferParam = appExpr->get_inferParams().find( (*assert)->get_uniqueId() );
814                                        if ( inferParam == appExpr->get_inferParams().end() ) {
815                                                std::cerr << "looking for assertion: " << (*assert) << std::endl << appExpr << std::endl;
816                                        }
817                                        assertf( inferParam != appExpr->get_inferParams().end(), "NOTE: Explicit casts of polymorphic functions to compatible monomorphic functions are currently unsupported" );
818                                        Expression *newExpr = inferParam->second.expr->clone();
819                                        addCast( newExpr, (*assert)->get_type(), tyVars );
820                                        boxParam( (*assert)->get_type(), newExpr, tyVars );
821                                        appExpr->get_args().insert( cur, newExpr );
822                                } // for
823                        } // for
824                }
825
826                void makeRetParm( FunctionType *funcType ) {
827                        DeclarationWithType *retParm = funcType->get_returnVals().front();
828
829                        // make a new parameter that is a pointer to the type of the old return value
830                        retParm->set_type( new PointerType( Type::Qualifiers(), retParm->get_type() ) );
831                        funcType->get_parameters().push_front( retParm );
832
833                        // we don't need the return value any more
834                        funcType->get_returnVals().clear();
835                }
836
837                FunctionType *makeAdapterType( FunctionType *adaptee, const TyVarMap &tyVars ) {
838                        // actually make the adapter type
839                        FunctionType *adapter = adaptee->clone();
840//                      if ( ! adapter->get_returnVals().empty() && isPolyType( adapter->get_returnVals().front()->get_type(), tyVars ) ) {
841                        if ( isDynRet( adapter, tyVars ) ) {
842                                makeRetParm( adapter );
843                        } // if
844                        adapter->get_parameters().push_front( new ObjectDecl( "", Type::StorageClasses(), LinkageSpec::C, 0, new PointerType( Type::Qualifiers(), new FunctionType( Type::Qualifiers(), true ) ), 0 ) );
845                        return adapter;
846                }
847
848                Expression *makeAdapterArg( DeclarationWithType *param, DeclarationWithType *arg, DeclarationWithType *realParam, const TyVarMap &tyVars ) {
849                        assert( param );
850                        assert( arg );
851                        if ( isPolyType( realParam->get_type(), tyVars ) ) {
852                                if ( ! isPolyType( arg->get_type() ) ) {
853                                        UntypedExpr *deref = new UntypedExpr( new NameExpr( "*?" ) );
854                                        deref->get_args().push_back( new CastExpr( new VariableExpr( param ), new PointerType( Type::Qualifiers(), arg->get_type()->clone() ) ) );
855                                        deref->set_result( arg->get_type()->clone() );
856                                        return deref;
857                                } // if
858                        } // if
859                        return new VariableExpr( param );
860                }
861
862                void addAdapterParams( ApplicationExpr *adapteeApp, std::list< DeclarationWithType *>::iterator arg, std::list< DeclarationWithType *>::iterator param, std::list< DeclarationWithType *>::iterator paramEnd, std::list< DeclarationWithType *>::iterator realParam, const TyVarMap &tyVars ) {
863                        UniqueName paramNamer( "_p" );
864                        for ( ; param != paramEnd; ++param, ++arg, ++realParam ) {
865                                if ( (*param)->get_name() == "" ) {
866                                        (*param)->set_name( paramNamer.newName() );
867                                        (*param)->set_linkage( LinkageSpec::C );
868                                } // if
869                                adapteeApp->get_args().push_back( makeAdapterArg( *param, *arg, *realParam, tyVars ) );
870                        } // for
871                }
872
873                FunctionDecl *Pass1::makeAdapter( FunctionType *adaptee, FunctionType *realType, const std::string &mangleName, const TyVarMap &tyVars ) {
874                        FunctionType *adapterType = makeAdapterType( adaptee, tyVars );
875                        adapterType = ScrubTyVars::scrub( adapterType, tyVars );
876                        DeclarationWithType *adapteeDecl = adapterType->get_parameters().front();
877                        adapteeDecl->set_name( "_adaptee" );
878                        ApplicationExpr *adapteeApp = new ApplicationExpr( new CastExpr( new VariableExpr( adapteeDecl ), new PointerType( Type::Qualifiers(), realType ) ) );
879                        Statement *bodyStmt;
880
881                        Type::ForallList::iterator tyArg = realType->get_forall().begin();
882                        Type::ForallList::iterator tyParam = adapterType->get_forall().begin();
883                        Type::ForallList::iterator realTyParam = adaptee->get_forall().begin();
884                        for ( ; tyParam != adapterType->get_forall().end(); ++tyArg, ++tyParam, ++realTyParam ) {
885                                assert( tyArg != realType->get_forall().end() );
886                                std::list< DeclarationWithType *>::iterator assertArg = (*tyArg)->get_assertions().begin();
887                                std::list< DeclarationWithType *>::iterator assertParam = (*tyParam)->get_assertions().begin();
888                                std::list< DeclarationWithType *>::iterator realAssertParam = (*realTyParam)->get_assertions().begin();
889                                for ( ; assertParam != (*tyParam)->get_assertions().end(); ++assertArg, ++assertParam, ++realAssertParam ) {
890                                        assert( assertArg != (*tyArg)->get_assertions().end() );
891                                        adapteeApp->get_args().push_back( makeAdapterArg( *assertParam, *assertArg, *realAssertParam, tyVars ) );
892                                } // for
893                        } // for
894
895                        std::list< DeclarationWithType *>::iterator arg = realType->get_parameters().begin();
896                        std::list< DeclarationWithType *>::iterator param = adapterType->get_parameters().begin();
897                        std::list< DeclarationWithType *>::iterator realParam = adaptee->get_parameters().begin();
898                        param++;                // skip adaptee parameter in the adapter type
899                        if ( realType->get_returnVals().empty() ) {
900                                // void return
901                                addAdapterParams( adapteeApp, arg, param, adapterType->get_parameters().end(), realParam, tyVars );
902                                bodyStmt = new ExprStmt( noLabels, adapteeApp );
903//                      } else if ( isPolyType( adaptee->get_returnVals().front()->get_type(), tyVars ) ) {
904                        } else if ( isDynType( adaptee->get_returnVals().front()->get_type(), tyVars ) ) {
905                                // return type T
906                                if ( (*param)->get_name() == "" ) {
907                                        (*param)->set_name( "_ret" );
908                                        (*param)->set_linkage( LinkageSpec::C );
909                                } // if
910                                UntypedExpr *assign = new UntypedExpr( new NameExpr( "?=?" ) );
911                                UntypedExpr *deref = UntypedExpr::createDeref( new CastExpr( new VariableExpr( *param++ ), new PointerType( Type::Qualifiers(), realType->get_returnVals().front()->get_type()->clone() ) ) );
912                                assign->get_args().push_back( deref );
913                                addAdapterParams( adapteeApp, arg, param, adapterType->get_parameters().end(), realParam, tyVars );
914                                assign->get_args().push_back( adapteeApp );
915                                bodyStmt = new ExprStmt( noLabels, assign );
916                        } else {
917                                // adapter for a function that returns a monomorphic value
918                                addAdapterParams( adapteeApp, arg, param, adapterType->get_parameters().end(), realParam, tyVars );
919                                bodyStmt = new ReturnStmt( noLabels, adapteeApp );
920                        } // if
921                        CompoundStmt *adapterBody = new CompoundStmt( noLabels );
922                        adapterBody->get_kids().push_back( bodyStmt );
923                        std::string adapterName = makeAdapterName( mangleName );
924                        return new FunctionDecl( adapterName, Type::StorageClasses(), LinkageSpec::C, adapterType, adapterBody );
925                }
926
927                void Pass1::passAdapters( ApplicationExpr * appExpr, FunctionType * functionType, const TyVarMap & exprTyVars ) {
928                        // collect a list of function types passed as parameters or implicit parameters (assertions)
929                        std::list< DeclarationWithType *> &paramList = functionType->get_parameters();
930                        std::list< FunctionType *> functions;
931                        for ( Type::ForallList::iterator tyVar = functionType->get_forall().begin(); tyVar != functionType->get_forall().end(); ++tyVar ) {
932                                for ( std::list< DeclarationWithType *>::iterator assert = (*tyVar)->get_assertions().begin(); assert != (*tyVar)->get_assertions().end(); ++assert ) {
933                                        findFunction( (*assert)->get_type(), functions, exprTyVars, needsAdapter );
934                                } // for
935                        } // for
936                        for ( std::list< DeclarationWithType *>::iterator arg = paramList.begin(); arg != paramList.end(); ++arg ) {
937                                findFunction( (*arg)->get_type(), functions, exprTyVars, needsAdapter );
938                        } // for
939
940                        // parameter function types for which an appropriate adapter has been generated.  we cannot use the types
941                        // after applying substitutions, since two different parameter types may be unified to the same type
942                        std::set< std::string > adaptersDone;
943
944                        for ( std::list< FunctionType *>::iterator funType = functions.begin(); funType != functions.end(); ++funType ) {
945                                FunctionType *originalFunction = (*funType)->clone();
946                                FunctionType *realFunction = (*funType)->clone();
947                                std::string mangleName = SymTab::Mangler::mangle( realFunction );
948
949                                // only attempt to create an adapter or pass one as a parameter if we haven't already done so for this
950                                // pre-substitution parameter function type.
951                                if ( adaptersDone.find( mangleName ) == adaptersDone.end() ) {
952                                        adaptersDone.insert( adaptersDone.begin(), mangleName );
953
954                                        // apply substitution to type variables to figure out what the adapter's type should look like
955                                        assert( env );
956                                        env->apply( realFunction );
957                                        mangleName = SymTab::Mangler::mangle( realFunction );
958                                        mangleName += makePolyMonoSuffix( originalFunction, exprTyVars );
959
960                                        typedef ScopedMap< std::string, DeclarationWithType* >::iterator AdapterIter;
961                                        AdapterIter adapter = adapters.find( mangleName );
962                                        if ( adapter == adapters.end() ) {
963                                                // adapter has not been created yet in the current scope, so define it
964                                                FunctionDecl *newAdapter = makeAdapter( *funType, realFunction, mangleName, exprTyVars );
965                                                std::pair< AdapterIter, bool > answer = adapters.insert( std::pair< std::string, DeclarationWithType *>( mangleName, newAdapter ) );
966                                                adapter = answer.first;
967                                                stmtsToAdd.push_back( new DeclStmt( noLabels, newAdapter ) );
968                                        } // if
969                                        assert( adapter != adapters.end() );
970
971                                        // add the appropriate adapter as a parameter
972                                        appExpr->get_args().push_front( new VariableExpr( adapter->second ) );
973                                } // if
974                        } // for
975                } // passAdapters
976
977                Expression *makeIncrDecrExpr( ApplicationExpr *appExpr, Type *polyType, bool isIncr ) {
978                        NameExpr *opExpr;
979                        if ( isIncr ) {
980                                opExpr = new NameExpr( "?+=?" );
981                        } else {
982                                opExpr = new NameExpr( "?-=?" );
983                        } // if
984                        UntypedExpr *addAssign = new UntypedExpr( opExpr );
985                        if ( AddressExpr *address = dynamic_cast< AddressExpr *>( appExpr->get_args().front() ) ) {
986                                addAssign->get_args().push_back( address->get_arg() );
987                        } else {
988                                addAssign->get_args().push_back( appExpr->get_args().front() );
989                        } // if
990                        addAssign->get_args().push_back( new NameExpr( sizeofName( mangleType( polyType ) ) ) );
991                        addAssign->set_result( appExpr->get_result()->clone() );
992                        if ( appExpr->get_env() ) {
993                                addAssign->set_env( appExpr->get_env() );
994                                appExpr->set_env( 0 );
995                        } // if
996                        appExpr->get_args().clear();
997                        delete appExpr;
998                        return addAssign;
999                }
1000
1001                Expression *Pass1::handleIntrinsics( ApplicationExpr *appExpr ) {
1002                        if ( VariableExpr *varExpr = dynamic_cast< VariableExpr *>( appExpr->get_function() ) ) {
1003                                if ( varExpr->get_var()->get_linkage() == LinkageSpec::Intrinsic ) {
1004                                        if ( varExpr->get_var()->get_name() == "?[?]" ) {
1005                                                assert( appExpr->has_result() );
1006                                                assert( appExpr->get_args().size() == 2 );
1007                                                Type *baseType1 = isPolyPtr( appExpr->get_args().front()->get_result(), scopeTyVars, env );
1008                                                Type *baseType2 = isPolyPtr( appExpr->get_args().back()->get_result(), scopeTyVars, env );
1009                                                assert( ! baseType1 || ! baseType2 ); // the arguments cannot both be polymorphic pointers
1010                                                UntypedExpr *ret = 0;
1011                                                if ( baseType1 || baseType2 ) { // one of the arguments is a polymorphic pointer
1012                                                        ret = new UntypedExpr( new NameExpr( "?+?" ) );
1013                                                } // if
1014                                                if ( baseType1 ) {
1015                                                        UntypedExpr *multiply = new UntypedExpr( new NameExpr( "?*?" ) );
1016                                                        multiply->get_args().push_back( appExpr->get_args().back() );
1017                                                        multiply->get_args().push_back( new SizeofExpr( baseType1->clone() ) );
1018                                                        ret->get_args().push_back( appExpr->get_args().front() );
1019                                                        ret->get_args().push_back( multiply );
1020                                                } else if ( baseType2 ) {
1021                                                        UntypedExpr *multiply = new UntypedExpr( new NameExpr( "?*?" ) );
1022                                                        multiply->get_args().push_back( appExpr->get_args().front() );
1023                                                        multiply->get_args().push_back( new SizeofExpr( baseType2->clone() ) );
1024                                                        ret->get_args().push_back( multiply );
1025                                                        ret->get_args().push_back( appExpr->get_args().back() );
1026                                                } // if
1027                                                if ( baseType1 || baseType2 ) {
1028                                                        ret->set_result( appExpr->get_result()->clone() );
1029                                                        if ( appExpr->get_env() ) {
1030                                                                ret->set_env( appExpr->get_env() );
1031                                                                appExpr->set_env( 0 );
1032                                                        } // if
1033                                                        appExpr->get_args().clear();
1034                                                        delete appExpr;
1035                                                        return ret;
1036                                                } // if
1037                                        } else if ( varExpr->get_var()->get_name() == "*?" ) {
1038                                                assert( appExpr->has_result() );
1039                                                assert( ! appExpr->get_args().empty() );
1040                                                if ( isPolyType( appExpr->get_result(), scopeTyVars, env ) ) {
1041                                                        Expression *ret = appExpr->get_args().front();
1042                                                        delete ret->get_result();
1043                                                        ret->set_result( appExpr->get_result()->clone() );
1044                                                        if ( appExpr->get_env() ) {
1045                                                                ret->set_env( appExpr->get_env() );
1046                                                                appExpr->set_env( 0 );
1047                                                        } // if
1048                                                        appExpr->get_args().clear();
1049                                                        delete appExpr;
1050                                                        return ret;
1051                                                } // if
1052                                        } else if ( varExpr->get_var()->get_name() == "?++" || varExpr->get_var()->get_name() == "?--" ) {
1053                                                assert( appExpr->has_result() );
1054                                                assert( appExpr->get_args().size() == 1 );
1055                                                if ( Type *baseType = isPolyPtr( appExpr->get_result(), scopeTyVars, env ) ) {
1056                                                        Type *tempType = appExpr->get_result()->clone();
1057                                                        if ( env ) {
1058                                                                env->apply( tempType );
1059                                                        } // if
1060                                                        ObjectDecl *newObj = makeTemporary( tempType );
1061                                                        VariableExpr *tempExpr = new VariableExpr( newObj );
1062                                                        UntypedExpr *assignExpr = new UntypedExpr( new NameExpr( "?=?" ) );
1063                                                        assignExpr->get_args().push_back( tempExpr->clone() );
1064                                                        if ( AddressExpr *address = dynamic_cast< AddressExpr *>( appExpr->get_args().front() ) ) {
1065                                                                assignExpr->get_args().push_back( address->get_arg()->clone() );
1066                                                        } else {
1067                                                                assignExpr->get_args().push_back( appExpr->get_args().front()->clone() );
1068                                                        } // if
1069                                                        CommaExpr *firstComma = new CommaExpr( assignExpr, makeIncrDecrExpr( appExpr, baseType, varExpr->get_var()->get_name() == "?++" ) );
1070                                                        return new CommaExpr( firstComma, tempExpr );
1071                                                } // if
1072                                        } else if ( varExpr->get_var()->get_name() == "++?" || varExpr->get_var()->get_name() == "--?" ) {
1073                                                assert( appExpr->has_result() );
1074                                                assert( appExpr->get_args().size() == 1 );
1075                                                if ( Type *baseType = isPolyPtr( appExpr->get_result(), scopeTyVars, env ) ) {
1076                                                        return makeIncrDecrExpr( appExpr, baseType, varExpr->get_var()->get_name() == "++?" );
1077                                                } // if
1078                                        } else if ( varExpr->get_var()->get_name() == "?+?" || varExpr->get_var()->get_name() == "?-?" ) {
1079                                                assert( appExpr->has_result() );
1080                                                assert( appExpr->get_args().size() == 2 );
1081                                                Type *baseType1 = isPolyPtr( appExpr->get_args().front()->get_result(), scopeTyVars, env );
1082                                                Type *baseType2 = isPolyPtr( appExpr->get_args().back()->get_result(), scopeTyVars, env );
1083                                                if ( baseType1 && baseType2 ) {
1084                                                        UntypedExpr *divide = new UntypedExpr( new NameExpr( "?/?" ) );
1085                                                        divide->get_args().push_back( appExpr );
1086                                                        divide->get_args().push_back( new SizeofExpr( baseType1->clone() ) );
1087                                                        divide->set_result( appExpr->get_result()->clone() );
1088                                                        if ( appExpr->get_env() ) {
1089                                                                divide->set_env( appExpr->get_env() );
1090                                                                appExpr->set_env( 0 );
1091                                                        } // if
1092                                                        return divide;
1093                                                } else if ( baseType1 ) {
1094                                                        UntypedExpr *multiply = new UntypedExpr( new NameExpr( "?*?" ) );
1095                                                        multiply->get_args().push_back( appExpr->get_args().back() );
1096                                                        multiply->get_args().push_back( new SizeofExpr( baseType1->clone() ) );
1097                                                        appExpr->get_args().back() = multiply;
1098                                                } else if ( baseType2 ) {
1099                                                        UntypedExpr *multiply = new UntypedExpr( new NameExpr( "?*?" ) );
1100                                                        multiply->get_args().push_back( appExpr->get_args().front() );
1101                                                        multiply->get_args().push_back( new SizeofExpr( baseType2->clone() ) );
1102                                                        appExpr->get_args().front() = multiply;
1103                                                } // if
1104                                        } else if ( varExpr->get_var()->get_name() == "?+=?" || varExpr->get_var()->get_name() == "?-=?" ) {
1105                                                assert( appExpr->has_result() );
1106                                                assert( appExpr->get_args().size() == 2 );
1107                                                Type *baseType = isPolyPtr( appExpr->get_result(), scopeTyVars, env );
1108                                                if ( baseType ) {
1109                                                        UntypedExpr *multiply = new UntypedExpr( new NameExpr( "?*?" ) );
1110                                                        multiply->get_args().push_back( appExpr->get_args().back() );
1111                                                        multiply->get_args().push_back( new SizeofExpr( baseType->clone() ) );
1112                                                        appExpr->get_args().back() = multiply;
1113                                                } // if
1114                                        } // if
1115                                        return appExpr;
1116                                } // if
1117                        } // if
1118                        return 0;
1119                }
1120
1121                Expression *Pass1::mutate( ApplicationExpr *appExpr ) {
1122                        // std::cerr << "mutate appExpr: " << InitTweak::getFunctionName( appExpr ) << std::endl;
1123                        // for ( TyVarMap::iterator i = scopeTyVars.begin(); i != scopeTyVars.end(); ++i ) {
1124                        //      std::cerr << i->first << " ";
1125                        // }
1126                        // std::cerr << "\n";
1127                        appExpr->get_function()->acceptMutator( *this );
1128                        mutateAll( appExpr->get_args(), *this );
1129
1130                        assert( appExpr->get_function()->has_result() );
1131                        PointerType *pointer = safe_dynamic_cast< PointerType *>( appExpr->get_function()->get_result() );
1132                        FunctionType *function = safe_dynamic_cast< FunctionType *>( pointer->get_base() );
1133
1134                        if ( Expression *newExpr = handleIntrinsics( appExpr ) ) {
1135                                return newExpr;
1136                        } // if
1137
1138                        Expression *ret = appExpr;
1139
1140                        std::list< Expression *>::iterator arg = appExpr->get_args().begin();
1141                        std::list< Expression *>::iterator paramBegin = appExpr->get_args().begin();
1142
1143                        TyVarMap exprTyVars( TypeDecl::Data{} );
1144                        makeTyVarMap( function, exprTyVars ); // xxx - should this take into account the variables already bound in scopeTyVars (i.e. remove them from exprTyVars?)
1145                        ReferenceToType *dynRetType = isDynRet( function, exprTyVars );
1146
1147                        // std::cerr << function << std::endl;
1148                        // std::cerr << "scopeTyVars: ";
1149                        // printTyVarMap( std::cerr, scopeTyVars );
1150                        // std::cerr << "exprTyVars: ";
1151                        // printTyVarMap( std::cerr, exprTyVars );
1152                        // std::cerr << "env: " << *env << std::endl;
1153                        // std::cerr << needsAdapter( function, scopeTyVars ) << ! needsAdapter( function, exprTyVars) << std::endl;
1154
1155                        // NOTE: addDynRetParam needs to know the actual (generated) return type so it can make a temp variable, so pass the result type from the appExpr
1156                        // passTypeVars needs to know the program-text return type (i.e. the distinction between _conc_T30 and T3(int))
1157                        // concRetType may not be a good name in one or both of these places. A more appropriate name change is welcome.
1158                        if ( dynRetType ) {
1159                                // std::cerr << "dynRetType: " << dynRetType << std::endl;
1160                                Type *concRetType = appExpr->get_result()->isVoid() ? nullptr : appExpr->get_result();
1161                                ret = addDynRetParam( appExpr, concRetType, arg ); // xxx - used to use dynRetType instead of concRetType
1162                        } else if ( needsAdapter( function, scopeTyVars ) && ! needsAdapter( function, exprTyVars) ) { // xxx - exprTyVars is used above...?
1163                                // xxx - the ! needsAdapter check may be incorrect. It seems there is some situation where an adapter is applied where it shouldn't be, and this fixes it for some cases. More investigation is needed.
1164
1165                                // std::cerr << "needs adapter: ";
1166                                // printTyVarMap( std::cerr, scopeTyVars );
1167                                // std::cerr << *env << std::endl;
1168                                // change the application so it calls the adapter rather than the passed function
1169                                ret = applyAdapter( appExpr, function, arg, scopeTyVars );
1170                        } // if
1171                        arg = appExpr->get_args().begin();
1172
1173                        Type *concRetType = replaceWithConcrete( appExpr, dynRetType );
1174                        passTypeVars( appExpr, concRetType, arg, exprTyVars ); // xxx - used to use dynRetType instead of concRetType; this changed so that the correct type paramaters are passed for return types (it should be the concrete type's parameters, not the formal type's)
1175                        addInferredParams( appExpr, function, arg, exprTyVars );
1176
1177                        arg = paramBegin;
1178
1179                        boxParams( appExpr, function, arg, exprTyVars );
1180                        passAdapters( appExpr, function, exprTyVars );
1181
1182                        return ret;
1183                }
1184
1185                Expression *Pass1::mutate( UntypedExpr *expr ) {
1186                        if ( expr->has_result() && isPolyType( expr->get_result(), scopeTyVars, env ) ) {
1187                                if ( NameExpr *name = dynamic_cast< NameExpr *>( expr->get_function() ) ) {
1188                                        if ( name->get_name() == "*?" ) {
1189                                                Expression *ret = expr->get_args().front();
1190                                                expr->get_args().clear();
1191                                                delete expr;
1192                                                return ret->acceptMutator( *this );
1193                                        } // if
1194                                } // if
1195                        } // if
1196                        return PolyMutator::mutate( expr );
1197                }
1198
1199                Expression *Pass1::mutate( AddressExpr *addrExpr ) {
1200                        assert( addrExpr->get_arg()->has_result() && ! addrExpr->get_arg()->get_result()->isVoid() );
1201
1202                        bool needs = false;
1203                        if ( UntypedExpr *expr = dynamic_cast< UntypedExpr *>( addrExpr->get_arg() ) ) {
1204                                if ( expr->has_result() && isPolyType( expr->get_result(), scopeTyVars, env ) ) {
1205                                        if ( NameExpr *name = dynamic_cast< NameExpr *>( expr->get_function() ) ) {
1206                                                if ( name->get_name() == "*?" ) {
1207                                                        if ( ApplicationExpr * appExpr = dynamic_cast< ApplicationExpr * >( expr->get_args().front() ) ) {
1208                                                                assert( appExpr->get_function()->has_result() );
1209                                                                PointerType *pointer = safe_dynamic_cast< PointerType *>( appExpr->get_function()->get_result() );
1210                                                                FunctionType *function = safe_dynamic_cast< FunctionType *>( pointer->get_base() );
1211                                                                needs = needsAdapter( function, scopeTyVars );
1212                                                        } // if
1213                                                } // if
1214                                        } // if
1215                                } // if
1216                        } // if
1217                        // isPolyType check needs to happen before mutating addrExpr arg, so pull it forward
1218                        // out of the if condition.
1219                        bool polytype = isPolyType( addrExpr->get_arg()->get_result(), scopeTyVars, env );
1220                        addrExpr->set_arg( mutateExpression( addrExpr->get_arg() ) );
1221                        if ( polytype || needs ) {
1222                                Expression *ret = addrExpr->get_arg();
1223                                delete ret->get_result();
1224                                ret->set_result( addrExpr->get_result()->clone() );
1225                                addrExpr->set_arg( 0 );
1226                                delete addrExpr;
1227                                return ret;
1228                        } else {
1229                                return addrExpr;
1230                        } // if
1231                }
1232
1233                Statement * Pass1::mutate( ReturnStmt *returnStmt ) {
1234                        if ( retval && returnStmt->get_expr() ) {
1235                                assert( returnStmt->get_expr()->has_result() && ! returnStmt->get_expr()->get_result()->isVoid() );
1236                                delete returnStmt->get_expr();
1237                                returnStmt->set_expr( 0 );
1238                        } else {
1239                                returnStmt->set_expr( mutateExpression( returnStmt->get_expr() ) );
1240                        } // if
1241                        return returnStmt;
1242                }
1243
1244                Type * Pass1::mutate( PointerType *pointerType ) {
1245                        scopeTyVars.beginScope();
1246                        makeTyVarMap( pointerType, scopeTyVars );
1247
1248                        Type *ret = Mutator::mutate( pointerType );
1249
1250                        scopeTyVars.endScope();
1251                        return ret;
1252                }
1253
1254                Type * Pass1::mutate( FunctionType *functionType ) {
1255                        scopeTyVars.beginScope();
1256                        makeTyVarMap( functionType, scopeTyVars );
1257
1258                        Type *ret = Mutator::mutate( functionType );
1259
1260                        scopeTyVars.endScope();
1261                        return ret;
1262                }
1263
1264                void Pass1::doBeginScope() {
1265                        adapters.beginScope();
1266                }
1267
1268                void Pass1::doEndScope() {
1269                        adapters.endScope();
1270                }
1271
1272////////////////////////////////////////// Pass2 ////////////////////////////////////////////////////
1273
1274                void Pass2::addAdapters( FunctionType *functionType ) {
1275                        std::list< DeclarationWithType *> &paramList = functionType->get_parameters();
1276                        std::list< FunctionType *> functions;
1277                        for ( std::list< DeclarationWithType *>::iterator arg = paramList.begin(); arg != paramList.end(); ++arg ) {
1278                                Type *orig = (*arg)->get_type();
1279                                findAndReplaceFunction( orig, functions, scopeTyVars, needsAdapter );
1280                                (*arg)->set_type( orig );
1281                        }
1282                        std::set< std::string > adaptersDone;
1283                        for ( std::list< FunctionType *>::iterator funType = functions.begin(); funType != functions.end(); ++funType ) {
1284                                std::string mangleName = mangleAdapterName( *funType, scopeTyVars );
1285                                if ( adaptersDone.find( mangleName ) == adaptersDone.end() ) {
1286                                        std::string adapterName = makeAdapterName( mangleName );
1287                                        paramList.push_front( new ObjectDecl( adapterName, Type::StorageClasses(), LinkageSpec::C, 0, new PointerType( Type::Qualifiers(), makeAdapterType( *funType, scopeTyVars ) ), 0 ) );
1288                                        adaptersDone.insert( adaptersDone.begin(), mangleName );
1289                                }
1290                        }
1291//  deleteAll( functions );
1292                }
1293
1294                template< typename DeclClass >
1295                DeclClass * Pass2::handleDecl( DeclClass *decl ) {
1296                        DeclClass *ret = static_cast< DeclClass *>( Parent::mutate( decl ) );
1297
1298                        return ret;
1299                }
1300
1301                /// determines if `pref` is a prefix of `str`
1302                bool isPrefix( const std::string & str, const std::string & pref ) {
1303                        if ( pref.size() > str.size() ) return false;
1304                        auto its = std::mismatch( pref.begin(), pref.end(), str.begin() );
1305                        return its.first == pref.end();
1306                }
1307
1308                DeclarationWithType * Pass2::mutate( FunctionDecl *functionDecl ) {
1309                        functionDecl = safe_dynamic_cast< FunctionDecl * > ( handleDecl( functionDecl ) );
1310                        FunctionType * ftype = functionDecl->get_functionType();
1311                        if ( ! ftype->get_returnVals().empty() && functionDecl->get_statements() ) {
1312                                if ( ! isPrefix( functionDecl->get_name(), "_thunk" ) && ! isPrefix( functionDecl->get_name(), "_adapter" ) ) { // xxx - remove check for prefix once thunks properly use ctor/dtors
1313                                        assert( ftype->get_returnVals().size() == 1 );
1314                                        DeclarationWithType * retval = ftype->get_returnVals().front();
1315                                        if ( retval->get_name() == "" ) {
1316                                                retval->set_name( "_retval" );
1317                                        }
1318                                        functionDecl->get_statements()->get_kids().push_front( new DeclStmt( noLabels, retval ) );
1319                                        DeclarationWithType * newRet = retval->clone(); // for ownership purposes
1320                                        ftype->get_returnVals().front() = newRet;
1321                                }
1322                        }
1323                        // errors should have been caught by this point, remove initializers from parameters to allow correct codegen of default arguments
1324                        for ( Declaration * param : functionDecl->get_functionType()->get_parameters() ) {
1325                                if ( ObjectDecl * obj = dynamic_cast< ObjectDecl * >( param ) ) {
1326                                        delete obj->get_init();
1327                                        obj->set_init( nullptr );
1328                                }
1329                        }
1330                        return functionDecl;
1331                }
1332
1333                ObjectDecl * Pass2::mutate( ObjectDecl *objectDecl ) {
1334                        return handleDecl( objectDecl );
1335                }
1336
1337                template< typename AggDecl >
1338                AggDecl * Pass2::handleAggDecl( AggDecl * aggDecl ) {
1339                        // prevent tyVars from leaking into containing scope
1340                        scopeTyVars.beginScope();
1341                        Parent::mutate( aggDecl );
1342                        scopeTyVars.endScope();
1343                        return aggDecl;
1344                }
1345
1346                StructDecl * Pass2::mutate( StructDecl *aggDecl ) {
1347                        return handleAggDecl( aggDecl );
1348                }
1349
1350                UnionDecl * Pass2::mutate( UnionDecl *aggDecl ) {
1351                        return handleAggDecl( aggDecl );
1352                }
1353
1354                TypeDecl * Pass2::mutate( TypeDecl *typeDecl ) {
1355                        addToTyVarMap( typeDecl, scopeTyVars );
1356                        if ( typeDecl->get_base() ) {
1357                                return handleDecl( typeDecl );
1358                        } else {
1359                                return Parent::mutate( typeDecl );
1360                        }
1361                }
1362
1363                TypedefDecl * Pass2::mutate( TypedefDecl *typedefDecl ) {
1364                        return handleDecl( typedefDecl );
1365                }
1366
1367                Type * Pass2::mutate( PointerType *pointerType ) {
1368                        scopeTyVars.beginScope();
1369                        makeTyVarMap( pointerType, scopeTyVars );
1370
1371                        Type *ret = Parent::mutate( pointerType );
1372
1373                        scopeTyVars.endScope();
1374                        return ret;
1375                }
1376
1377                Type *Pass2::mutate( FunctionType *funcType ) {
1378                        scopeTyVars.beginScope();
1379                        makeTyVarMap( funcType, scopeTyVars );
1380
1381                        // move polymorphic return type to parameter list
1382                        if ( isDynRet( funcType ) ) {
1383                                ObjectDecl *ret = safe_dynamic_cast< ObjectDecl* >( funcType->get_returnVals().front() );
1384                                ret->set_type( new PointerType( Type::Qualifiers(), ret->get_type() ) );
1385                                funcType->get_parameters().push_front( ret );
1386                                funcType->get_returnVals().pop_front();
1387                                ret->set_init( nullptr ); // xxx - memory leak?
1388                        }
1389
1390                        // add size/align and assertions for type parameters to parameter list
1391                        std::list< DeclarationWithType *>::iterator last = funcType->get_parameters().begin();
1392                        std::list< DeclarationWithType *> inferredParams;
1393                        ObjectDecl newObj( "", Type::StorageClasses(), LinkageSpec::C, 0, new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt ), 0 );
1394                        ObjectDecl newPtr( "", Type::StorageClasses(), LinkageSpec::C, 0,
1395                                           new PointerType( Type::Qualifiers(), new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt ) ), 0 );
1396                        for ( Type::ForallList::const_iterator tyParm = funcType->get_forall().begin(); tyParm != funcType->get_forall().end(); ++tyParm ) {
1397                                ObjectDecl *sizeParm, *alignParm;
1398                                // add all size and alignment parameters to parameter list
1399                                if ( (*tyParm)->isComplete() ) {
1400                                        TypeInstType parmType( Type::Qualifiers(), (*tyParm)->get_name(), *tyParm );
1401                                        std::string parmName = mangleType( &parmType );
1402
1403                                        sizeParm = newObj.clone();
1404                                        sizeParm->set_name( sizeofName( parmName ) );
1405                                        last = funcType->get_parameters().insert( last, sizeParm );
1406                                        ++last;
1407
1408                                        alignParm = newObj.clone();
1409                                        alignParm->set_name( alignofName( parmName ) );
1410                                        last = funcType->get_parameters().insert( last, alignParm );
1411                                        ++last;
1412                                }
1413                                // move all assertions into parameter list
1414                                for ( std::list< DeclarationWithType *>::iterator assert = (*tyParm)->get_assertions().begin(); assert != (*tyParm)->get_assertions().end(); ++assert ) {
1415//      *assert = (*assert)->acceptMutator( *this );
1416                                        inferredParams.push_back( *assert );
1417                                }
1418                                (*tyParm)->get_assertions().clear();
1419                        }
1420
1421                        // add size/align for generic parameter types to parameter list
1422                        std::set< std::string > seenTypes; // sizeofName for generic types we've seen
1423                        for ( std::list< DeclarationWithType* >::const_iterator fnParm = last; fnParm != funcType->get_parameters().end(); ++fnParm ) {
1424                                Type *polyType = isPolyType( (*fnParm)->get_type(), scopeTyVars );
1425                                if ( polyType && ! dynamic_cast< TypeInstType* >( polyType ) ) {
1426                                        std::string typeName = mangleType( polyType );
1427                                        if ( seenTypes.count( typeName ) ) continue;
1428
1429                                        ObjectDecl *sizeParm, *alignParm, *offsetParm;
1430                                        sizeParm = newObj.clone();
1431                                        sizeParm->set_name( sizeofName( typeName ) );
1432                                        last = funcType->get_parameters().insert( last, sizeParm );
1433                                        ++last;
1434
1435                                        alignParm = newObj.clone();
1436                                        alignParm->set_name( alignofName( typeName ) );
1437                                        last = funcType->get_parameters().insert( last, alignParm );
1438                                        ++last;
1439
1440                                        if ( StructInstType *polyBaseStruct = dynamic_cast< StructInstType* >( polyType ) ) {
1441                                                // NOTE zero-length arrays are illegal in C, so empty structs have no offset array
1442                                                if ( ! polyBaseStruct->get_baseStruct()->get_members().empty() ) {
1443                                                        offsetParm = newPtr.clone();
1444                                                        offsetParm->set_name( offsetofName( typeName ) );
1445                                                        last = funcType->get_parameters().insert( last, offsetParm );
1446                                                        ++last;
1447                                                }
1448                                        }
1449
1450                                        seenTypes.insert( typeName );
1451                                }
1452                        }
1453
1454                        // splice assertion parameters into parameter list
1455                        funcType->get_parameters().splice( last, inferredParams );
1456                        addAdapters( funcType );
1457                        mutateAll( funcType->get_returnVals(), *this );
1458                        mutateAll( funcType->get_parameters(), *this );
1459
1460                        scopeTyVars.endScope();
1461                        return funcType;
1462                }
1463
1464////////////////////////////////////////// PolyGenericCalculator ////////////////////////////////////////////////////
1465
1466                PolyGenericCalculator::PolyGenericCalculator()
1467                        : Parent(), knownLayouts(), knownOffsets(), bufNamer( "_buf" ) {}
1468
1469                void PolyGenericCalculator::beginTypeScope( Type *ty ) {
1470                        scopeTyVars.beginScope();
1471                        makeTyVarMap( ty, scopeTyVars );
1472                }
1473
1474                void PolyGenericCalculator::endTypeScope() {
1475                        scopeTyVars.endScope();
1476                }
1477
1478                template< typename DeclClass >
1479                DeclClass * PolyGenericCalculator::handleDecl( DeclClass *decl, Type *type ) {
1480                        beginTypeScope( type );
1481                        // knownLayouts.beginScope();
1482                        // knownOffsets.beginScope();
1483
1484                        DeclClass *ret = static_cast< DeclClass *>( Parent::mutate( decl ) );
1485
1486                        // knownOffsets.endScope();
1487                        // knownLayouts.endScope();
1488                        endTypeScope();
1489                        return ret;
1490                }
1491
1492                ObjectDecl * PolyGenericCalculator::mutate( ObjectDecl *objectDecl ) {
1493                        return handleDecl( objectDecl, objectDecl->get_type() );
1494                }
1495
1496                DeclarationWithType * PolyGenericCalculator::mutate( FunctionDecl *functionDecl ) {
1497                        knownLayouts.beginScope();
1498                        knownOffsets.beginScope();
1499
1500                        DeclarationWithType * decl = handleDecl( functionDecl, functionDecl->get_functionType() );
1501                        knownOffsets.endScope();
1502                        knownLayouts.endScope();
1503                        return decl;
1504                }
1505
1506                TypedefDecl * PolyGenericCalculator::mutate( TypedefDecl *typedefDecl ) {
1507                        return handleDecl( typedefDecl, typedefDecl->get_base() );
1508                }
1509
1510                TypeDecl * PolyGenericCalculator::mutate( TypeDecl *typeDecl ) {
1511                        addToTyVarMap( typeDecl, scopeTyVars );
1512                        return Parent::mutate( typeDecl );
1513                }
1514
1515                Type * PolyGenericCalculator::mutate( PointerType *pointerType ) {
1516                        beginTypeScope( pointerType );
1517
1518                        Type *ret = Parent::mutate( pointerType );
1519
1520                        endTypeScope();
1521                        return ret;
1522                }
1523
1524                Type * PolyGenericCalculator::mutate( FunctionType *funcType ) {
1525                        beginTypeScope( funcType );
1526
1527                        // make sure that any type information passed into the function is accounted for
1528                        for ( std::list< DeclarationWithType* >::const_iterator fnParm = funcType->get_parameters().begin(); fnParm != funcType->get_parameters().end(); ++fnParm ) {
1529                                // condition here duplicates that in Pass2::mutate( FunctionType* )
1530                                Type *polyType = isPolyType( (*fnParm)->get_type(), scopeTyVars );
1531                                if ( polyType && ! dynamic_cast< TypeInstType* >( polyType ) ) {
1532                                        knownLayouts.insert( mangleType( polyType ) );
1533                                }
1534                        }
1535
1536                        Type *ret = Parent::mutate( funcType );
1537
1538                        endTypeScope();
1539                        return ret;
1540                }
1541
1542                Statement *PolyGenericCalculator::mutate( DeclStmt *declStmt ) {
1543                        if ( ObjectDecl *objectDecl = dynamic_cast< ObjectDecl *>( declStmt->get_decl() ) ) {
1544                                if ( findGeneric( objectDecl->get_type() ) ) {
1545                                        // change initialization of a polymorphic value object to allocate via a VLA
1546                                        // (alloca was previously used, but can't be safely used in loops)
1547                                        Type *declType = objectDecl->get_type();
1548                                        std::string bufName = bufNamer.newName();
1549                                        ObjectDecl *newBuf = new ObjectDecl( bufName, Type::StorageClasses(), LinkageSpec::C, 0,
1550                                                new ArrayType( Type::Qualifiers(), new BasicType( Type::Qualifiers(), BasicType::Kind::Char), new NameExpr( sizeofName( mangleType(declType) ) ),
1551                                                true, false, std::list<Attribute*>{ new Attribute( std::string{"aligned"}, std::list<Expression*>{ new ConstantExpr( Constant::from_int(8) ) } ) } ), 0 );
1552                                        stmtsToAdd.push_back( new DeclStmt( noLabels, newBuf ) );
1553
1554                                        delete objectDecl->get_init();
1555
1556                                        objectDecl->set_init( new SingleInit( new NameExpr( bufName ) ) );
1557                                }
1558                        }
1559                        return Parent::mutate( declStmt );
1560                }
1561
1562                /// Finds the member in the base list that matches the given declaration; returns its index, or -1 if not present
1563                long findMember( DeclarationWithType *memberDecl, std::list< Declaration* > &baseDecls ) {
1564                        long i = 0;
1565                        for(std::list< Declaration* >::const_iterator decl = baseDecls.begin(); decl != baseDecls.end(); ++decl, ++i ) {
1566                                if ( memberDecl->get_name() != (*decl)->get_name() ) continue;
1567
1568                                if ( DeclarationWithType *declWithType = dynamic_cast< DeclarationWithType* >( *decl ) ) {
1569                                        if ( memberDecl->get_mangleName().empty() || declWithType->get_mangleName().empty()
1570                                             || memberDecl->get_mangleName() == declWithType->get_mangleName() ) return i;
1571                                        else continue;
1572                                } else return i;
1573                        }
1574                        return -1;
1575                }
1576
1577                /// Returns an index expression into the offset array for a type
1578                Expression *makeOffsetIndex( Type *objectType, long i ) {
1579                        ConstantExpr *fieldIndex = new ConstantExpr( Constant::from_ulong( i ) );
1580                        UntypedExpr *fieldOffset = new UntypedExpr( new NameExpr( "?[?]" ) );
1581                        fieldOffset->get_args().push_back( new NameExpr( offsetofName( mangleType( objectType ) ) ) );
1582                        fieldOffset->get_args().push_back( fieldIndex );
1583                        return fieldOffset;
1584                }
1585
1586                Expression *PolyGenericCalculator::mutate( MemberExpr *memberExpr ) {
1587                        // mutate, exiting early if no longer MemberExpr
1588                        Expression *expr = Parent::mutate( memberExpr );
1589                        memberExpr = dynamic_cast< MemberExpr* >( expr );
1590                        if ( ! memberExpr ) return expr;
1591
1592                        // only mutate member expressions for polymorphic types
1593                        int tyDepth;
1594                        Type *objectType = hasPolyBase( memberExpr->get_aggregate()->get_result(), scopeTyVars, &tyDepth );
1595                        if ( ! objectType ) return memberExpr;
1596                        findGeneric( objectType ); // ensure layout for this type is available
1597
1598                        // replace member expression with dynamically-computed layout expression
1599                        Expression *newMemberExpr = 0;
1600                        if ( StructInstType *structType = dynamic_cast< StructInstType* >( objectType ) ) {
1601                                // look up offset index
1602                                long i = findMember( memberExpr->get_member(), structType->get_baseStruct()->get_members() );
1603                                if ( i == -1 ) return memberExpr;
1604
1605                                // replace member expression with pointer to base plus offset
1606                                UntypedExpr *fieldLoc = new UntypedExpr( new NameExpr( "?+?" ) );
1607                                Expression * aggr = memberExpr->get_aggregate()->clone();
1608                                delete aggr->get_env(); // xxx - there's a problem with keeping the env for some reason, so for now just get rid of it
1609                                aggr->set_env( nullptr );
1610                                fieldLoc->get_args().push_back( aggr );
1611                                fieldLoc->get_args().push_back( makeOffsetIndex( objectType, i ) );
1612                                fieldLoc->set_result( memberExpr->get_result()->clone() );
1613                                newMemberExpr = fieldLoc;
1614                        } else if ( dynamic_cast< UnionInstType* >( objectType ) ) {
1615                                // union members are all at offset zero, so just use the aggregate expr
1616                                Expression * aggr = memberExpr->get_aggregate()->clone();
1617                                delete aggr->get_env(); // xxx - there's a problem with keeping the env for some reason, so for now just get rid of it
1618                                aggr->set_env( nullptr );
1619                                newMemberExpr = aggr;
1620                                newMemberExpr->set_result( memberExpr->get_result()->clone() );
1621                        } else return memberExpr;
1622                        assert( newMemberExpr );
1623
1624                        Type *memberType = memberExpr->get_member()->get_type();
1625                        if ( ! isPolyType( memberType, scopeTyVars ) ) {
1626                                // Not all members of a polymorphic type are themselves of polymorphic type; in this case the member expression should be wrapped and dereferenced to form an lvalue
1627                                CastExpr *ptrCastExpr = new CastExpr( newMemberExpr, new PointerType( Type::Qualifiers(), memberType->clone() ) );
1628                                UntypedExpr *derefExpr = UntypedExpr::createDeref( ptrCastExpr );
1629                                newMemberExpr = derefExpr;
1630                        }
1631
1632                        delete memberExpr;
1633                        return newMemberExpr;
1634                }
1635
1636                ObjectDecl *PolyGenericCalculator::makeVar( const std::string &name, Type *type, Initializer *init ) {
1637                        ObjectDecl *newObj = new ObjectDecl( name, Type::StorageClasses(), LinkageSpec::C, 0, type, init );
1638                        stmtsToAdd.push_back( new DeclStmt( noLabels, newObj ) );
1639                        return newObj;
1640                }
1641
1642                void PolyGenericCalculator::addOtypeParamsToLayoutCall( UntypedExpr *layoutCall, const std::list< Type* > &otypeParams ) {
1643                        for ( std::list< Type* >::const_iterator param = otypeParams.begin(); param != otypeParams.end(); ++param ) {
1644                                if ( findGeneric( *param ) ) {
1645                                        // push size/align vars for a generic parameter back
1646                                        std::string paramName = mangleType( *param );
1647                                        layoutCall->get_args().push_back( new NameExpr( sizeofName( paramName ) ) );
1648                                        layoutCall->get_args().push_back( new NameExpr( alignofName( paramName ) ) );
1649                                } else {
1650                                        layoutCall->get_args().push_back( new SizeofExpr( (*param)->clone() ) );
1651                                        layoutCall->get_args().push_back( new AlignofExpr( (*param)->clone() ) );
1652                                }
1653                        }
1654                }
1655
1656                /// returns true if any of the otype parameters have a dynamic layout and puts all otype parameters in the output list
1657                bool findGenericParams( std::list< TypeDecl* > &baseParams, std::list< Expression* > &typeParams, std::list< Type* > &out ) {
1658                        bool hasDynamicLayout = false;
1659
1660                        std::list< TypeDecl* >::const_iterator baseParam = baseParams.begin();
1661                        std::list< Expression* >::const_iterator typeParam = typeParams.begin();
1662                        for ( ; baseParam != baseParams.end() && typeParam != typeParams.end(); ++baseParam, ++typeParam ) {
1663                                // skip non-otype parameters
1664                                if ( ! (*baseParam)->isComplete() ) continue;
1665                                TypeExpr *typeExpr = dynamic_cast< TypeExpr* >( *typeParam );
1666                                assert( typeExpr && "all otype parameters should be type expressions" );
1667
1668                                Type *type = typeExpr->get_type();
1669                                out.push_back( type );
1670                                if ( isPolyType( type ) ) hasDynamicLayout = true;
1671                        }
1672                        assert( baseParam == baseParams.end() && typeParam == typeParams.end() );
1673
1674                        return hasDynamicLayout;
1675                }
1676
1677                bool PolyGenericCalculator::findGeneric( Type *ty ) {
1678                        ty = replaceTypeInst( ty, env );
1679
1680                        if ( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( ty ) ) {
1681                                if ( scopeTyVars.find( typeInst->get_name() ) != scopeTyVars.end() ) {
1682                                        // NOTE assumes here that getting put in the scopeTyVars included having the layout variables set
1683                                        return true;
1684                                }
1685                                return false;
1686                        } else if ( StructInstType *structTy = dynamic_cast< StructInstType* >( ty ) ) {
1687                                // check if this type already has a layout generated for it
1688                                std::string typeName = mangleType( ty );
1689                                if ( knownLayouts.find( typeName ) != knownLayouts.end() ) return true;
1690
1691                                // check if any of the type parameters have dynamic layout; if none do, this type is (or will be) monomorphized
1692                                std::list< Type* > otypeParams;
1693                                if ( ! findGenericParams( *structTy->get_baseParameters(), structTy->get_parameters(), otypeParams ) ) return false;
1694
1695                                // insert local variables for layout and generate call to layout function
1696                                knownLayouts.insert( typeName );  // done early so as not to interfere with the later addition of parameters to the layout call
1697                                Type *layoutType = new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt );
1698
1699                                int n_members = structTy->get_baseStruct()->get_members().size();
1700                                if ( n_members == 0 ) {
1701                                        // all empty structs have the same layout - size 1, align 1
1702                                        makeVar( sizeofName( typeName ), layoutType, new SingleInit( new ConstantExpr( Constant::from_ulong( (unsigned long)1 ) ) ) );
1703                                        makeVar( alignofName( typeName ), layoutType->clone(), new SingleInit( new ConstantExpr( Constant::from_ulong( (unsigned long)1 ) ) ) );
1704                                        // NOTE zero-length arrays are forbidden in C, so empty structs have no offsetof array
1705                                } else {
1706                                        ObjectDecl *sizeVar = makeVar( sizeofName( typeName ), layoutType );
1707                                        ObjectDecl *alignVar = makeVar( alignofName( typeName ), layoutType->clone() );
1708                                        ObjectDecl *offsetVar = makeVar( offsetofName( typeName ), new ArrayType( Type::Qualifiers(), layoutType->clone(), new ConstantExpr( Constant::from_int( n_members ) ), false, false ) );
1709
1710                                        // generate call to layout function
1711                                        UntypedExpr *layoutCall = new UntypedExpr( new NameExpr( layoutofName( structTy->get_baseStruct() ) ) );
1712                                        layoutCall->get_args().push_back( new AddressExpr( new VariableExpr( sizeVar ) ) );
1713                                        layoutCall->get_args().push_back( new AddressExpr( new VariableExpr( alignVar ) ) );
1714                                        layoutCall->get_args().push_back( new VariableExpr( offsetVar ) );
1715                                        addOtypeParamsToLayoutCall( layoutCall, otypeParams );
1716
1717                                        stmtsToAdd.push_back( new ExprStmt( noLabels, layoutCall ) );
1718                                }
1719
1720                                return true;
1721                        } else if ( UnionInstType *unionTy = dynamic_cast< UnionInstType* >( ty ) ) {
1722                                // check if this type already has a layout generated for it
1723                                std::string typeName = mangleType( ty );
1724                                if ( knownLayouts.find( typeName ) != knownLayouts.end() ) return true;
1725
1726                                // check if any of the type parameters have dynamic layout; if none do, this type is (or will be) monomorphized
1727                                std::list< Type* > otypeParams;
1728                                if ( ! findGenericParams( *unionTy->get_baseParameters(), unionTy->get_parameters(), otypeParams ) ) return false;
1729
1730                                // insert local variables for layout and generate call to layout function
1731                                knownLayouts.insert( typeName );  // done early so as not to interfere with the later addition of parameters to the layout call
1732                                Type *layoutType = new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt );
1733
1734                                ObjectDecl *sizeVar = makeVar( sizeofName( typeName ), layoutType );
1735                                ObjectDecl *alignVar = makeVar( alignofName( typeName ), layoutType->clone() );
1736
1737                                // generate call to layout function
1738                                UntypedExpr *layoutCall = new UntypedExpr( new NameExpr( layoutofName( unionTy->get_baseUnion() ) ) );
1739                                layoutCall->get_args().push_back( new AddressExpr( new VariableExpr( sizeVar ) ) );
1740                                layoutCall->get_args().push_back( new AddressExpr( new VariableExpr( alignVar ) ) );
1741                                addOtypeParamsToLayoutCall( layoutCall, otypeParams );
1742
1743                                stmtsToAdd.push_back( new ExprStmt( noLabels, layoutCall ) );
1744
1745                                return true;
1746                        }
1747
1748                        return false;
1749                }
1750
1751                Expression *PolyGenericCalculator::mutate( SizeofExpr *sizeofExpr ) {
1752                        Type *ty = sizeofExpr->get_isType() ? sizeofExpr->get_type() : sizeofExpr->get_expr()->get_result();
1753                        if ( findGeneric( ty ) ) {
1754                                Expression *ret = new NameExpr( sizeofName( mangleType( ty ) ) );
1755                                delete sizeofExpr;
1756                                return ret;
1757                        }
1758                        return sizeofExpr;
1759                }
1760
1761                Expression *PolyGenericCalculator::mutate( AlignofExpr *alignofExpr ) {
1762                        Type *ty = alignofExpr->get_isType() ? alignofExpr->get_type() : alignofExpr->get_expr()->get_result();
1763                        if ( findGeneric( ty ) ) {
1764                                Expression *ret = new NameExpr( alignofName( mangleType( ty ) ) );
1765                                delete alignofExpr;
1766                                return ret;
1767                        }
1768                        return alignofExpr;
1769                }
1770
1771                Expression *PolyGenericCalculator::mutate( OffsetofExpr *offsetofExpr ) {
1772                        // mutate, exiting early if no longer OffsetofExpr
1773                        Expression *expr = Parent::mutate( offsetofExpr );
1774                        offsetofExpr = dynamic_cast< OffsetofExpr* >( expr );
1775                        if ( ! offsetofExpr ) return expr;
1776
1777                        // only mutate expressions for polymorphic structs/unions
1778                        Type *ty = offsetofExpr->get_type();
1779                        if ( ! findGeneric( ty ) ) return offsetofExpr;
1780
1781                        if ( StructInstType *structType = dynamic_cast< StructInstType* >( ty ) ) {
1782                                // replace offsetof expression by index into offset array
1783                                long i = findMember( offsetofExpr->get_member(), structType->get_baseStruct()->get_members() );
1784                                if ( i == -1 ) return offsetofExpr;
1785
1786                                Expression *offsetInd = makeOffsetIndex( ty, i );
1787                                delete offsetofExpr;
1788                                return offsetInd;
1789                        } else if ( dynamic_cast< UnionInstType* >( ty ) ) {
1790                                // all union members are at offset zero
1791                                delete offsetofExpr;
1792                                return new ConstantExpr( Constant::from_ulong( 0 ) );
1793                        } else return offsetofExpr;
1794                }
1795
1796                Expression *PolyGenericCalculator::mutate( OffsetPackExpr *offsetPackExpr ) {
1797                        StructInstType *ty = offsetPackExpr->get_type();
1798
1799                        Expression *ret = 0;
1800                        if ( findGeneric( ty ) ) {
1801                                // pull offset back from generated type information
1802                                ret = new NameExpr( offsetofName( mangleType( ty ) ) );
1803                        } else {
1804                                std::string offsetName = offsetofName( mangleType( ty ) );
1805                                if ( knownOffsets.find( offsetName ) != knownOffsets.end() ) {
1806                                        // use the already-generated offsets for this type
1807                                        ret = new NameExpr( offsetName );
1808                                } else {
1809                                        knownOffsets.insert( offsetName );
1810
1811                                        std::list< Declaration* > &baseMembers = ty->get_baseStruct()->get_members();
1812                                        Type *offsetType = new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt );
1813
1814                                        // build initializer list for offset array
1815                                        std::list< Initializer* > inits;
1816                                        for ( std::list< Declaration* >::const_iterator member = baseMembers.begin(); member != baseMembers.end(); ++member ) {
1817                                                if ( DeclarationWithType *memberDecl = dynamic_cast< DeclarationWithType* >( *member ) ) {
1818                                                        inits.push_back( new SingleInit( new OffsetofExpr( ty->clone(), memberDecl ) ) );
1819                                                } else {
1820                                                        assertf( false, "Requesting offset of Non-DWT member: %s", toString( *member ).c_str() );
1821                                                }
1822                                        }
1823
1824                                        // build the offset array and replace the pack with a reference to it
1825                                        ObjectDecl *offsetArray = makeVar( offsetName, new ArrayType( Type::Qualifiers(), offsetType, new ConstantExpr( Constant::from_ulong( baseMembers.size() ) ), false, false ),
1826                                                        new ListInit( inits ) );
1827                                        ret = new VariableExpr( offsetArray );
1828                                }
1829                        }
1830
1831                        delete offsetPackExpr;
1832                        return ret;
1833                }
1834
1835                void PolyGenericCalculator::doBeginScope() {
1836                        knownLayouts.beginScope();
1837                        knownOffsets.beginScope();
1838                }
1839
1840                void PolyGenericCalculator::doEndScope() {
1841                        knownLayouts.endScope();
1842                        knownOffsets.endScope();
1843                }
1844
1845////////////////////////////////////////// Pass3 ////////////////////////////////////////////////////
1846
1847                template< typename DeclClass >
1848                DeclClass * Pass3::handleDecl( DeclClass *decl, Type *type ) {
1849                        scopeTyVars.beginScope();
1850                        makeTyVarMap( type, scopeTyVars );
1851
1852                        DeclClass *ret = static_cast< DeclClass *>( Mutator::mutate( decl ) );
1853                        // ScrubTyVars::scrub( decl, scopeTyVars );
1854                        ScrubTyVars::scrubAll( decl );
1855
1856                        scopeTyVars.endScope();
1857                        return ret;
1858                }
1859
1860                ObjectDecl * Pass3::mutate( ObjectDecl *objectDecl ) {
1861                        return handleDecl( objectDecl, objectDecl->get_type() );
1862                }
1863
1864                DeclarationWithType * Pass3::mutate( FunctionDecl *functionDecl ) {
1865                        return handleDecl( functionDecl, functionDecl->get_functionType() );
1866                }
1867
1868                TypedefDecl * Pass3::mutate( TypedefDecl *typedefDecl ) {
1869                        return handleDecl( typedefDecl, typedefDecl->get_base() );
1870                }
1871
1872                /// Strips the members from a generic aggregate
1873                void stripGenericMembers(AggregateDecl* decl) {
1874                        if ( ! decl->get_parameters().empty() ) decl->get_members().clear();
1875                }
1876
1877                Declaration *Pass3::mutate( StructDecl *structDecl ) {
1878                        stripGenericMembers( structDecl );
1879                        return structDecl;
1880                }
1881               
1882                Declaration *Pass3::mutate( UnionDecl *unionDecl ) {
1883                        stripGenericMembers( unionDecl );
1884                        return unionDecl;
1885                }
1886
1887                TypeDecl * Pass3::mutate( TypeDecl *typeDecl ) {
1888//   Initializer *init = 0;
1889//   std::list< Expression *> designators;
1890//   addToTyVarMap( typeDecl, scopeTyVars );
1891//   if ( typeDecl->get_base() ) {
1892//     init = new SimpleInit( new SizeofExpr( handleDecl( typeDecl, typeDecl->get_base() ) ), designators );
1893//   }
1894//   return new ObjectDecl( typeDecl->get_name(), Declaration::Extern, LinkageSpec::C, 0, new BasicType( Type::Qualifiers(), BasicType::UnsignedInt ), init );
1895
1896                        addToTyVarMap( typeDecl, scopeTyVars );
1897                        return Mutator::mutate( typeDecl );
1898                }
1899
1900                Type * Pass3::mutate( PointerType *pointerType ) {
1901                        scopeTyVars.beginScope();
1902                        makeTyVarMap( pointerType, scopeTyVars );
1903
1904                        Type *ret = Mutator::mutate( pointerType );
1905
1906                        scopeTyVars.endScope();
1907                        return ret;
1908                }
1909
1910                Type * Pass3::mutate( FunctionType *functionType ) {
1911                        scopeTyVars.beginScope();
1912                        makeTyVarMap( functionType, scopeTyVars );
1913
1914                        Type *ret = Mutator::mutate( functionType );
1915
1916                        scopeTyVars.endScope();
1917                        return ret;
1918                }
1919        } // anonymous namespace
1920} // namespace GenPoly
1921
1922// Local Variables: //
1923// tab-width: 4 //
1924// mode: c++ //
1925// compile-command: "make install" //
1926// End: //
Note: See TracBrowser for help on using the repository browser.