source: src/GenPoly/Box.cc @ 6016c87

aaron-thesisarm-ehcleanup-dtorsdeferred_resndemanglerjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprnew-envno_listpersistent-indexerresolv-newwith_gc
Last change on this file since 6016c87 was 7b2c0a99, checked in by Peter A. Buhr <pabuhr@…>, 4 years ago

fix unbound type-variable error

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