source: src/GenPoly/Box.cc @ 2a7b3ca

aaron-thesisarm-ehcleanup-dtorsdeferred_resndemanglerjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprnew-envno_listpersistent-indexerresolv-newwith_gc
Last change on this file since 2a7b3ca was 2a7b3ca, checked in by Rob Schluntz <rschlunt@…>, 4 years ago

convert InstantiateGeneric? to PassVisitor?, add missing mutate and accept calls to PassVisitor?, add missing ValueGuardPtrs? to PassVisitor::handleStatementList

  • 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 : Wed Jun 21 15:49:59 2017
13// Update Count     : 346
14//
15
16#include <algorithm>
17#include <iterator>
18#include <list>
19#include <map>
20#include <set>
21#include <stack>
22#include <string>
23#include <utility>
24#include <vector>
25#include <cassert>
26
27#include "Box.h"
28#include "DeclMutator.h"
29#include "PolyMutator.h"
30#include "FindFunction.h"
31#include "ScopedSet.h"
32#include "ScrubTyVars.h"
33
34#include "Parser/ParseNode.h"
35
36#include "SynTree/Attribute.h"
37#include "SynTree/Constant.h"
38#include "SynTree/Declaration.h"
39#include "SynTree/Expression.h"
40#include "SynTree/Initializer.h"
41#include "SynTree/Mutator.h"
42#include "SynTree/Statement.h"
43#include "SynTree/Type.h"
44#include "SynTree/TypeSubstitution.h"
45
46#include "ResolvExpr/TypeEnvironment.h"
47#include "ResolvExpr/TypeMap.h"
48#include "ResolvExpr/typeops.h"
49
50#include "SymTab/Indexer.h"
51#include "SymTab/Mangler.h"
52
53#include "Common/ScopedMap.h"
54#include "Common/SemanticError.h"
55#include "Common/UniqueName.h"
56#include "Common/utility.h"
57
58#include "InitTweak/InitTweak.h"
59
60#include <ext/functional> // temporary
61
62namespace GenPoly {
63        namespace {
64                FunctionType *makeAdapterType( FunctionType *adaptee, const TyVarMap &tyVars );
65
66                /// Adds layout-generation functions to polymorphic types
67                class LayoutFunctionBuilder final : public DeclMutator {
68                        unsigned int functionNesting;  // current level of nested functions
69                public:
70                        LayoutFunctionBuilder() : functionNesting( 0 ) {}
71
72                        using DeclMutator::mutate;
73                        virtual DeclarationWithType *mutate( FunctionDecl *functionDecl ) override;
74                        virtual Declaration *mutate( StructDecl *structDecl ) override;
75                        virtual Declaration *mutate( UnionDecl *unionDecl ) override;
76                };
77
78                /// Replaces polymorphic return types with out-parameters, replaces calls to polymorphic functions with adapter calls as needed, and adds appropriate type variables to the function call
79                class Pass1 final : public PolyMutator {
80                  public:
81                        Pass1();
82
83                        using PolyMutator::mutate;
84                        virtual Expression *mutate( ApplicationExpr *appExpr ) override;
85                        virtual Expression *mutate( AddressExpr *addrExpr ) override;
86                        virtual Expression *mutate( UntypedExpr *expr ) override;
87                        virtual DeclarationWithType* mutate( FunctionDecl *functionDecl ) override;
88                        virtual TypeDecl *mutate( TypeDecl *typeDecl ) override;
89                        virtual Expression *mutate( CommaExpr *commaExpr ) override;
90                        virtual Expression *mutate( ConditionalExpr *condExpr ) override;
91                        virtual Statement * mutate( ReturnStmt *returnStmt ) override;
92                        virtual Type *mutate( PointerType *pointerType ) override;
93                        virtual Type * mutate( FunctionType *functionType ) override;
94
95                        virtual void doBeginScope() override;
96                        virtual void doEndScope() override;
97                  private:
98                        /// Pass the extra type parameters from polymorphic generic arguments or return types into a function application
99                        void passArgTypeVars( ApplicationExpr *appExpr, Type *parmType, Type *argBaseType, std::list< Expression *>::iterator &arg, const TyVarMap &exprTyVars, std::set< std::string > &seenTypes );
100                        /// passes extra type parameters into a polymorphic function application
101                        void passTypeVars( ApplicationExpr *appExpr, Type *polyRetType, std::list< Expression *>::iterator &arg, const TyVarMap &exprTyVars );
102                        /// wraps a function application with a new temporary for the out-parameter return value
103                        Expression *addRetParam( ApplicationExpr *appExpr, Type *retType, std::list< Expression *>::iterator &arg );
104                        /// Replaces all the type parameters of a generic type with their concrete equivalents under the current environment
105                        void replaceParametersWithConcrete( ApplicationExpr *appExpr, std::list< Expression* >& params );
106                        /// Replaces a polymorphic type with its concrete equivalant under the current environment (returns itself if concrete).
107                        /// If `doClone` is set to false, will not clone interior types
108                        Type *replaceWithConcrete( ApplicationExpr *appExpr, Type *type, bool doClone = true );
109                        /// wraps a function application returning a polymorphic type with a new temporary for the out-parameter return value
110                        Expression *addDynRetParam( ApplicationExpr *appExpr, Type *polyType, std::list< Expression *>::iterator &arg );
111                        Expression *applyAdapter( ApplicationExpr *appExpr, FunctionType *function, std::list< Expression *>::iterator &arg, const TyVarMap &exprTyVars );
112                        void boxParam( Type *formal, Expression *&arg, const TyVarMap &exprTyVars );
113                        void boxParams( ApplicationExpr *appExpr, FunctionType *function, std::list< Expression *>::iterator &arg, const TyVarMap &exprTyVars );
114                        void addInferredParams( ApplicationExpr *appExpr, FunctionType *functionType, std::list< Expression *>::iterator &arg, const TyVarMap &tyVars );
115                        /// Stores assignment operators from assertion list in local map of assignment operations
116                        void passAdapters( ApplicationExpr *appExpr, FunctionType *functionType, const TyVarMap &exprTyVars );
117                        FunctionDecl *makeAdapter( FunctionType *adaptee, FunctionType *realType, const std::string &mangleName, const TyVarMap &tyVars );
118                        /// Replaces intrinsic operator functions with their arithmetic desugaring
119                        Expression *handleIntrinsics( ApplicationExpr *appExpr );
120                        /// Inserts a new temporary variable into the current scope with an auto-generated name
121                        ObjectDecl *makeTemporary( Type *type );
122
123                        ScopedMap< std::string, DeclarationWithType* > adapters;     ///< Set of adapter functions in the current scope
124
125                        std::map< ApplicationExpr *, Expression * > retVals;
126
127                        DeclarationWithType *retval;
128                        UniqueName tempNamer;
129                };
130
131                /// * Moves polymorphic returns in function types to pointer-type parameters
132                /// * adds type size and assertion parameters to parameter lists
133                class Pass2 final : public PolyMutator {
134                  public:
135                        template< typename DeclClass >
136                        DeclClass *handleDecl( DeclClass *decl );
137                        template< typename AggDecl >
138                        AggDecl * handleAggDecl( AggDecl * aggDecl );
139
140                        typedef PolyMutator Parent;
141                        using Parent::mutate;
142                        virtual DeclarationWithType *mutate( FunctionDecl *functionDecl ) override;
143                        virtual ObjectDecl *mutate( ObjectDecl *objectDecl ) override;
144                        virtual StructDecl *mutate( StructDecl *structDecl ) override;
145                        virtual UnionDecl *mutate( UnionDecl *unionDecl ) override;
146                        virtual TypeDecl *mutate( TypeDecl *typeDecl ) override;
147                        virtual TypedefDecl *mutate( TypedefDecl *typedefDecl ) override;
148                        virtual Type *mutate( PointerType *pointerType ) override;
149                        virtual Type *mutate( FunctionType *funcType ) override;
150
151                  private:
152                        void addAdapters( FunctionType *functionType );
153
154                        std::map< UniqueId, std::string > adapterName;
155                };
156
157                /// Replaces member and size/align/offsetof expressions on polymorphic generic types with calculated expressions.
158                /// * Replaces member expressions for polymorphic types with calculated add-field-offset-and-dereference
159                /// * Calculates polymorphic offsetof expressions from offset array
160                /// * Inserts dynamic calculation of polymorphic type layouts where needed
161                class PolyGenericCalculator final : public PolyMutator {
162                public:
163                        typedef PolyMutator Parent;
164                        using Parent::mutate;
165
166                        PolyGenericCalculator();
167
168                        template< typename DeclClass >
169                        DeclClass *handleDecl( DeclClass *decl, Type *type );
170                        virtual DeclarationWithType *mutate( FunctionDecl *functionDecl ) override;
171                        virtual ObjectDecl *mutate( ObjectDecl *objectDecl ) override;
172                        virtual TypedefDecl *mutate( TypedefDecl *objectDecl ) override;
173                        virtual TypeDecl *mutate( TypeDecl *objectDecl ) override;
174                        virtual Statement *mutate( DeclStmt *declStmt ) override;
175                        virtual Type *mutate( PointerType *pointerType ) override;
176                        virtual Type *mutate( FunctionType *funcType ) override;
177                        virtual Expression *mutate( MemberExpr *memberExpr ) override;
178                        virtual Expression *mutate( SizeofExpr *sizeofExpr ) override;
179                        virtual Expression *mutate( AlignofExpr *alignofExpr ) override;
180                        virtual Expression *mutate( OffsetofExpr *offsetofExpr ) override;
181                        virtual Expression *mutate( OffsetPackExpr *offsetPackExpr ) override;
182
183                        virtual void doBeginScope() override;
184                        virtual void doEndScope() override;
185
186                private:
187                        /// Makes a new variable in the current scope with the given name, type & optional initializer
188                        ObjectDecl *makeVar( const std::string &name, Type *type, Initializer *init = 0 );
189                        /// returns true if the type has a dynamic layout; such a layout will be stored in appropriately-named local variables when the function returns
190                        bool findGeneric( Type *ty );
191                        /// adds type parameters to the layout call; will generate the appropriate parameters if needed
192                        void addOtypeParamsToLayoutCall( UntypedExpr *layoutCall, const std::list< Type* > &otypeParams );
193
194                        /// Enters a new scope for type-variables, adding the type variables from ty
195                        void beginTypeScope( Type *ty );
196                        /// Exits the type-variable scope
197                        void endTypeScope();
198
199                        ScopedSet< std::string > knownLayouts;          ///< Set of generic type layouts known in the current scope, indexed by sizeofName
200                        ScopedSet< std::string > knownOffsets;          ///< Set of non-generic types for which the offset array exists in the current scope, indexed by offsetofName
201                        UniqueName bufNamer;                           ///< Namer for VLA buffers
202                };
203
204                /// Replaces initialization of polymorphic values with alloca, declaration of dtype/ftype with appropriate void expression, and sizeof expressions of polymorphic types with the proper variable
205                class Pass3 final : public PolyMutator {
206                  public:
207                        template< typename DeclClass >
208                        DeclClass *handleDecl( DeclClass *decl, Type *type );
209
210                        using PolyMutator::mutate;
211                        virtual DeclarationWithType *mutate( FunctionDecl *functionDecl ) override;
212                        virtual ObjectDecl *mutate( ObjectDecl *objectDecl ) override;
213                        virtual TypedefDecl *mutate( TypedefDecl *objectDecl ) override;
214                        virtual TypeDecl *mutate( TypeDecl *objectDecl ) override;
215                        virtual Type *mutate( PointerType *pointerType ) override;
216                        virtual Type *mutate( FunctionType *funcType ) override;
217                  private:
218                };
219
220        } // anonymous namespace
221
222        /// version of mutateAll with special handling for translation unit so you can check the end of the prelude when debugging
223        template< typename MutatorType >
224        inline void mutateTranslationUnit( std::list< Declaration* > &translationUnit, MutatorType &mutator ) {
225                bool seenIntrinsic = false;
226                SemanticError errors;
227                for ( typename std::list< Declaration* >::iterator i = translationUnit.begin(); i != translationUnit.end(); ++i ) {
228                        try {
229                                if ( *i ) {
230                                        if ( (*i)->get_linkage() == LinkageSpec::Intrinsic ) {
231                                                seenIntrinsic = true;
232                                        } else if ( seenIntrinsic ) {
233                                                seenIntrinsic = false; // break on this line when debugging for end of prelude
234                                        }
235
236                                        *i = dynamic_cast< Declaration* >( (*i)->acceptMutator( mutator ) );
237                                        assert( *i );
238                                } // if
239                        } catch( SemanticError &e ) {
240                                e.set_location( (*i)->location );
241                                errors.append( e );
242                        } // try
243                } // for
244                if ( ! errors.isEmpty() ) {
245                        throw errors;
246                } // if
247        }
248
249        void box( std::list< Declaration *>& translationUnit ) {
250                LayoutFunctionBuilder layoutBuilder;
251                Pass1 pass1;
252                Pass2 pass2;
253                PolyGenericCalculator polyCalculator;
254                Pass3 pass3;
255
256                layoutBuilder.mutateDeclarationList( translationUnit );
257                mutateTranslationUnit/*All*/( translationUnit, pass1 );
258                mutateTranslationUnit/*All*/( translationUnit, pass2 );
259                mutateTranslationUnit/*All*/( translationUnit, polyCalculator );
260                mutateTranslationUnit/*All*/( translationUnit, pass3 );
261        }
262
263        ////////////////////////////////// LayoutFunctionBuilder ////////////////////////////////////////////
264
265        DeclarationWithType *LayoutFunctionBuilder::mutate( FunctionDecl *functionDecl ) {
266                functionDecl->set_functionType( maybeMutate( functionDecl->get_functionType(), *this ) );
267                ++functionNesting;
268                functionDecl->set_statements( maybeMutate( functionDecl->get_statements(), *this ) );
269                --functionNesting;
270                return functionDecl;
271        }
272
273        /// Get a list of type declarations that will affect a layout function
274        std::list< TypeDecl* > takeOtypeOnly( std::list< TypeDecl* > &decls ) {
275                std::list< TypeDecl * > otypeDecls;
276
277                for ( std::list< TypeDecl* >::const_iterator decl = decls.begin(); decl != decls.end(); ++decl ) {
278                        if ( (*decl)->isComplete() ) {
279                                otypeDecls.push_back( *decl );
280                        }
281                }
282
283                return otypeDecls;
284        }
285
286        /// Adds parameters for otype layout to a function type
287        void addOtypeParams( FunctionType *layoutFnType, std::list< TypeDecl* > &otypeParams ) {
288                BasicType sizeAlignType( Type::Qualifiers(), BasicType::LongUnsignedInt );
289
290                for ( std::list< TypeDecl* >::const_iterator param = otypeParams.begin(); param != otypeParams.end(); ++param ) {
291                        TypeInstType paramType( Type::Qualifiers(), (*param)->get_name(), *param );
292                        std::string paramName = mangleType( &paramType );
293                        layoutFnType->get_parameters().push_back( new ObjectDecl( sizeofName( paramName ), Type::StorageClasses(), LinkageSpec::Cforall, 0, sizeAlignType.clone(), 0 ) );
294                        layoutFnType->get_parameters().push_back( new ObjectDecl( alignofName( paramName ), Type::StorageClasses(), LinkageSpec::Cforall, 0, sizeAlignType.clone(), 0 ) );
295                }
296        }
297
298        /// Builds a layout function declaration
299        FunctionDecl *buildLayoutFunctionDecl( AggregateDecl *typeDecl, unsigned int functionNesting, FunctionType *layoutFnType ) {
300                // Routines at global scope marked "static" to prevent multiple definitions is separate translation units
301                // because each unit generates copies of the default routines for each aggregate.
302                FunctionDecl *layoutDecl = new FunctionDecl( layoutofName( typeDecl ),
303                                                                                                         functionNesting > 0 ? Type::StorageClasses() : Type::StorageClasses( Type::Static ),
304                                                                                                         LinkageSpec::AutoGen, layoutFnType, new CompoundStmt( noLabels ),
305                                                                                                         std::list< Attribute * >(), Type::FuncSpecifiers( Type::Inline ) );
306                layoutDecl->fixUniqueId();
307                return layoutDecl;
308        }
309
310        /// Makes a unary operation
311        Expression *makeOp( const std::string &name, Expression *arg ) {
312                UntypedExpr *expr = new UntypedExpr( new NameExpr( name ) );
313                expr->get_args().push_back( arg );
314                return expr;
315        }
316
317        /// Makes a binary operation
318        Expression *makeOp( const std::string &name, Expression *lhs, Expression *rhs ) {
319                UntypedExpr *expr = new UntypedExpr( new NameExpr( name ) );
320                expr->get_args().push_back( lhs );
321                expr->get_args().push_back( rhs );
322                return expr;
323        }
324
325        /// Returns the dereference of a local pointer variable
326        Expression *derefVar( ObjectDecl *var ) {
327                return makeOp( "*?", new VariableExpr( var ) );
328        }
329
330        /// makes an if-statement with a single-expression if-block and no then block
331        Statement *makeCond( Expression *cond, Expression *ifPart ) {
332                return new IfStmt( noLabels, cond, new ExprStmt( noLabels, ifPart ), 0 );
333        }
334
335        /// makes a statement that assigns rhs to lhs if lhs < rhs
336        Statement *makeAssignMax( Expression *lhs, Expression *rhs ) {
337                return makeCond( makeOp( "?<?", lhs, rhs ), makeOp( "?=?", lhs->clone(), rhs->clone() ) );
338        }
339
340        /// makes a statement that aligns lhs to rhs (rhs should be an integer power of two)
341        Statement *makeAlignTo( Expression *lhs, Expression *rhs ) {
342                // check that the lhs is zeroed out to the level of rhs
343                Expression *ifCond = makeOp( "?&?", lhs, makeOp( "?-?", rhs, new ConstantExpr( Constant::from_ulong( 1 ) ) ) );
344                // if not aligned, increment to alignment
345                Expression *ifExpr = makeOp( "?+=?", lhs->clone(), makeOp( "?-?", rhs->clone(), ifCond->clone() ) );
346                return makeCond( ifCond, ifExpr );
347        }
348
349        /// adds an expression to a compound statement
350        void addExpr( CompoundStmt *stmts, Expression *expr ) {
351                stmts->get_kids().push_back( new ExprStmt( noLabels, expr ) );
352        }
353
354        /// adds a statement to a compound statement
355        void addStmt( CompoundStmt *stmts, Statement *stmt ) {
356                stmts->get_kids().push_back( stmt );
357        }
358
359        Declaration *LayoutFunctionBuilder::mutate( StructDecl *structDecl ) {
360                // do not generate layout function for "empty" tag structs
361                if ( structDecl->get_members().empty() ) return structDecl;
362
363                // get parameters that can change layout, exiting early if none
364                std::list< TypeDecl* > otypeParams = takeOtypeOnly( structDecl->get_parameters() );
365                if ( otypeParams.empty() ) return structDecl;
366
367                // build layout function signature
368                FunctionType *layoutFnType = new FunctionType( Type::Qualifiers(), false );
369                BasicType *sizeAlignType = new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt );
370                PointerType *sizeAlignOutType = new PointerType( Type::Qualifiers(), sizeAlignType );
371
372                ObjectDecl *sizeParam = new ObjectDecl( sizeofName( structDecl->get_name() ), Type::StorageClasses(), LinkageSpec::Cforall, 0, sizeAlignOutType, 0 );
373                layoutFnType->get_parameters().push_back( sizeParam );
374                ObjectDecl *alignParam = new ObjectDecl( alignofName( structDecl->get_name() ), Type::StorageClasses(), LinkageSpec::Cforall, 0, sizeAlignOutType->clone(), 0 );
375                layoutFnType->get_parameters().push_back( alignParam );
376                ObjectDecl *offsetParam = new ObjectDecl( offsetofName( structDecl->get_name() ), Type::StorageClasses(), LinkageSpec::Cforall, 0, sizeAlignOutType->clone(), 0 );
377                layoutFnType->get_parameters().push_back( offsetParam );
378                addOtypeParams( layoutFnType, otypeParams );
379
380                // build function decl
381                FunctionDecl *layoutDecl = buildLayoutFunctionDecl( structDecl, functionNesting, layoutFnType );
382
383                // calculate struct layout in function body
384
385                // initialize size and alignment to 0 and 1 (will have at least one member to re-edit size)
386                addExpr( layoutDecl->get_statements(), makeOp( "?=?", derefVar( sizeParam ), new ConstantExpr( Constant::from_ulong( 0 ) ) ) );
387                addExpr( layoutDecl->get_statements(), makeOp( "?=?", derefVar( alignParam ), new ConstantExpr( Constant::from_ulong( 1 ) ) ) );
388                unsigned long n_members = 0;
389                bool firstMember = true;
390                for ( std::list< Declaration* >::const_iterator member = structDecl->get_members().begin(); member != structDecl->get_members().end(); ++member ) {
391                        DeclarationWithType *dwt = dynamic_cast< DeclarationWithType * >( *member );
392                        assert( dwt );
393                        Type *memberType = dwt->get_type();
394
395                        if ( firstMember ) {
396                                firstMember = false;
397                        } else {
398                                // make sure all members after the first (automatically aligned at 0) are properly padded for alignment
399                                addStmt( layoutDecl->get_statements(), makeAlignTo( derefVar( sizeParam ), new AlignofExpr( memberType->clone() ) ) );
400                        }
401
402                        // place current size in the current offset index
403                        addExpr( layoutDecl->get_statements(), makeOp( "?=?", makeOp( "?[?]", new VariableExpr( offsetParam ), new ConstantExpr( Constant::from_ulong( n_members ) ) ),
404                                                                              derefVar( sizeParam ) ) );
405                        ++n_members;
406
407                        // add member size to current size
408                        addExpr( layoutDecl->get_statements(), makeOp( "?+=?", derefVar( sizeParam ), new SizeofExpr( memberType->clone() ) ) );
409
410                        // take max of member alignment and global alignment
411                        addStmt( layoutDecl->get_statements(), makeAssignMax( derefVar( alignParam ), new AlignofExpr( memberType->clone() ) ) );
412                }
413                // make sure the type is end-padded to a multiple of its alignment
414                addStmt( layoutDecl->get_statements(), makeAlignTo( derefVar( sizeParam ), derefVar( alignParam ) ) );
415
416                addDeclarationAfter( layoutDecl );
417                return structDecl;
418        }
419
420        Declaration *LayoutFunctionBuilder::mutate( UnionDecl *unionDecl ) {
421                // do not generate layout function for "empty" tag unions
422                if ( unionDecl->get_members().empty() ) return unionDecl;
423
424                // get parameters that can change layout, exiting early if none
425                std::list< TypeDecl* > otypeParams = takeOtypeOnly( unionDecl->get_parameters() );
426                if ( otypeParams.empty() ) return unionDecl;
427
428                // build layout function signature
429                FunctionType *layoutFnType = new FunctionType( Type::Qualifiers(), false );
430                BasicType *sizeAlignType = new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt );
431                PointerType *sizeAlignOutType = new PointerType( Type::Qualifiers(), sizeAlignType );
432
433                ObjectDecl *sizeParam = new ObjectDecl( sizeofName( unionDecl->get_name() ), Type::StorageClasses(), LinkageSpec::Cforall, 0, sizeAlignOutType, 0 );
434                layoutFnType->get_parameters().push_back( sizeParam );
435                ObjectDecl *alignParam = new ObjectDecl( alignofName( unionDecl->get_name() ), Type::StorageClasses(), LinkageSpec::Cforall, 0, sizeAlignOutType->clone(), 0 );
436                layoutFnType->get_parameters().push_back( alignParam );
437                addOtypeParams( layoutFnType, otypeParams );
438
439                // build function decl
440                FunctionDecl *layoutDecl = buildLayoutFunctionDecl( unionDecl, functionNesting, layoutFnType );
441
442                // calculate union layout in function body
443                addExpr( layoutDecl->get_statements(), makeOp( "?=?", derefVar( sizeParam ), new ConstantExpr( Constant::from_ulong( 1 ) ) ) );
444                addExpr( layoutDecl->get_statements(), makeOp( "?=?", derefVar( alignParam ), new ConstantExpr( Constant::from_ulong( 1 ) ) ) );
445                for ( std::list< Declaration* >::const_iterator member = unionDecl->get_members().begin(); member != unionDecl->get_members().end(); ++member ) {
446                        DeclarationWithType *dwt = dynamic_cast< DeclarationWithType * >( *member );
447                        assert( dwt );
448                        Type *memberType = dwt->get_type();
449
450                        // take max member size and global size
451                        addStmt( layoutDecl->get_statements(), makeAssignMax( derefVar( sizeParam ), new SizeofExpr( memberType->clone() ) ) );
452
453                        // take max of member alignment and global alignment
454                        addStmt( layoutDecl->get_statements(), makeAssignMax( derefVar( alignParam ), new AlignofExpr( memberType->clone() ) ) );
455                }
456                // make sure the type is end-padded to a multiple of its alignment
457                addStmt( layoutDecl->get_statements(), makeAlignTo( derefVar( sizeParam ), derefVar( alignParam ) ) );
458
459                addDeclarationAfter( layoutDecl );
460                return unionDecl;
461        }
462
463        ////////////////////////////////////////// Pass1 ////////////////////////////////////////////////////
464
465        namespace {
466                std::string makePolyMonoSuffix( FunctionType * function, const TyVarMap &tyVars ) {
467                        std::stringstream name;
468
469                        // NOTE: this function previously used isPolyObj, which failed to produce
470                        // the correct thing in some situations. It's not clear to me why this wasn't working.
471
472                        // if the return type or a parameter type involved polymorphic types, then the adapter will need
473                        // to take those polymorphic types as pointers. Therefore, there can be two different functions
474                        // with the same mangled name, so we need to further mangle the names.
475                        for ( std::list< DeclarationWithType *>::iterator retval = function->get_returnVals().begin(); retval != function->get_returnVals().end(); ++retval ) {
476                                if ( isPolyType( (*retval)->get_type(), tyVars ) ) {
477                                        name << "P";
478                                } else {
479                                        name << "M";
480                                }
481                        }
482                        name << "_";
483                        std::list< DeclarationWithType *> &paramList = function->get_parameters();
484                        for ( std::list< DeclarationWithType *>::iterator arg = paramList.begin(); arg != paramList.end(); ++arg ) {
485                                if ( isPolyType( (*arg)->get_type(), tyVars ) ) {
486                                        name << "P";
487                                } else {
488                                        name << "M";
489                                }
490                        } // for
491                        return name.str();
492                }
493
494                std::string mangleAdapterName( FunctionType * function, const TyVarMap &tyVars ) {
495                        return SymTab::Mangler::mangle( function ) + makePolyMonoSuffix( function, tyVars );
496                }
497
498                std::string makeAdapterName( const std::string &mangleName ) {
499                        return "_adapter" + mangleName;
500                }
501
502                Pass1::Pass1() : tempNamer( "_temp" ) {}
503
504                DeclarationWithType *Pass1::mutate( FunctionDecl *functionDecl ) {
505                        if ( functionDecl->get_statements() ) {         // empty routine body ?
506                                // std::cerr << "mutating function: " << functionDecl->get_mangleName() << std::endl;
507                                doBeginScope();
508                                scopeTyVars.beginScope();
509
510                                DeclarationWithType *oldRetval = retval;
511
512                                // process polymorphic return value
513                                retval = nullptr;
514                                if ( isDynRet( functionDecl->get_functionType() ) && functionDecl->get_linkage() != LinkageSpec::C ) {
515                                        retval = functionDecl->get_functionType()->get_returnVals().front();
516
517                                        // give names to unnamed return values
518                                        if ( retval->get_name() == "" ) {
519                                                retval->set_name( "_retparm" );
520                                                retval->set_linkage( LinkageSpec::C );
521                                        } // if
522                                } // if
523
524                                FunctionType *functionType = functionDecl->get_functionType();
525                                makeTyVarMap( functionDecl->get_functionType(), scopeTyVars );
526
527                                std::list< DeclarationWithType *> &paramList = functionType->get_parameters();
528                                std::list< FunctionType *> functions;
529                                for ( Type::ForallList::iterator tyVar = functionType->get_forall().begin(); tyVar != functionType->get_forall().end(); ++tyVar ) {
530                                        for ( std::list< DeclarationWithType *>::iterator assert = (*tyVar)->get_assertions().begin(); assert != (*tyVar)->get_assertions().end(); ++assert ) {
531                                                findFunction( (*assert)->get_type(), functions, scopeTyVars, needsAdapter );
532                                        } // for
533                                } // for
534                                for ( std::list< DeclarationWithType *>::iterator arg = paramList.begin(); arg != paramList.end(); ++arg ) {
535                                        findFunction( (*arg)->get_type(), functions, scopeTyVars, needsAdapter );
536                                } // for
537
538                                for ( std::list< FunctionType *>::iterator funType = functions.begin(); funType != functions.end(); ++funType ) {
539                                        std::string mangleName = mangleAdapterName( *funType, scopeTyVars );
540                                        if ( adapters.find( mangleName ) == adapters.end() ) {
541                                                std::string adapterName = makeAdapterName( mangleName );
542                                                adapters.insert( std::pair< std::string, DeclarationWithType *>( mangleName, new ObjectDecl( adapterName, Type::StorageClasses(), LinkageSpec::C, nullptr, new PointerType( Type::Qualifiers(), makeAdapterType( *funType, scopeTyVars ) ), nullptr ) ) );
543                                        } // if
544                                } // for
545
546                                functionDecl->set_statements( functionDecl->get_statements()->acceptMutator( *this ) );
547
548                                scopeTyVars.endScope();
549                                retval = oldRetval;
550                                doEndScope();
551                                // std::cerr << "end function: " << functionDecl->get_mangleName() << std::endl;
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, 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, 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, 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->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: " << InitTweak::getFunctionName( appExpr ) << std::endl;
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                        // std::cerr << function << std::endl;
1146                        // std::cerr << "scopeTyVars: ";
1147                        // printTyVarMap( std::cerr, scopeTyVars );
1148                        // std::cerr << "exprTyVars: ";
1149                        // printTyVarMap( std::cerr, exprTyVars );
1150                        // std::cerr << "env: " << *env << std::endl;
1151                        // std::cerr << needsAdapter( function, scopeTyVars ) << ! needsAdapter( function, exprTyVars) << std::endl;
1152
1153                        // 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
1154                        // passTypeVars needs to know the program-text return type (i.e. the distinction between _conc_T30 and T3(int))
1155                        // concRetType may not be a good name in one or both of these places. A more appropriate name change is welcome.
1156                        if ( dynRetType ) {
1157                                // std::cerr << "dynRetType: " << dynRetType << std::endl;
1158                                Type *concRetType = appExpr->get_result()->isVoid() ? nullptr : appExpr->get_result();
1159                                ret = addDynRetParam( appExpr, concRetType, arg ); // xxx - used to use dynRetType instead of concRetType
1160                        } else if ( needsAdapter( function, scopeTyVars ) && ! needsAdapter( function, exprTyVars) ) { // xxx - exprTyVars is used above...?
1161                                // 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.
1162
1163                                // std::cerr << "needs adapter: ";
1164                                // printTyVarMap( std::cerr, scopeTyVars );
1165                                // std::cerr << *env << std::endl;
1166                                // change the application so it calls the adapter rather than the passed function
1167                                ret = applyAdapter( appExpr, function, arg, scopeTyVars );
1168                        } // if
1169                        arg = appExpr->get_args().begin();
1170
1171                        Type *concRetType = replaceWithConcrete( appExpr, dynRetType );
1172                        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)
1173                        addInferredParams( appExpr, function, arg, exprTyVars );
1174
1175                        arg = paramBegin;
1176
1177                        boxParams( appExpr, function, arg, exprTyVars );
1178                        passAdapters( appExpr, function, exprTyVars );
1179
1180                        return ret;
1181                }
1182
1183                Expression *Pass1::mutate( UntypedExpr *expr ) {
1184                        if ( expr->has_result() && isPolyType( expr->get_result(), scopeTyVars, env ) ) {
1185                                if ( NameExpr *name = dynamic_cast< NameExpr *>( expr->get_function() ) ) {
1186                                        if ( name->get_name() == "*?" ) {
1187                                                Expression *ret = expr->get_args().front();
1188                                                expr->get_args().clear();
1189                                                delete expr;
1190                                                return ret->acceptMutator( *this );
1191                                        } // if
1192                                } // if
1193                        } // if
1194                        return PolyMutator::mutate( expr );
1195                }
1196
1197                Expression *Pass1::mutate( AddressExpr *addrExpr ) {
1198                        assert( addrExpr->get_arg()->has_result() && ! addrExpr->get_arg()->get_result()->isVoid() );
1199
1200                        bool needs = false;
1201                        if ( UntypedExpr *expr = dynamic_cast< UntypedExpr *>( addrExpr->get_arg() ) ) {
1202                                if ( expr->has_result() && isPolyType( expr->get_result(), scopeTyVars, env ) ) {
1203                                        if ( NameExpr *name = dynamic_cast< NameExpr *>( expr->get_function() ) ) {
1204                                                if ( name->get_name() == "*?" ) {
1205                                                        if ( ApplicationExpr * appExpr = dynamic_cast< ApplicationExpr * >( expr->get_args().front() ) ) {
1206                                                                assert( appExpr->get_function()->has_result() );
1207                                                                PointerType *pointer = safe_dynamic_cast< PointerType *>( appExpr->get_function()->get_result() );
1208                                                                FunctionType *function = safe_dynamic_cast< FunctionType *>( pointer->get_base() );
1209                                                                needs = needsAdapter( function, scopeTyVars );
1210                                                        } // if
1211                                                } // if
1212                                        } // if
1213                                } // if
1214                        } // if
1215                        // isPolyType check needs to happen before mutating addrExpr arg, so pull it forward
1216                        // out of the if condition.
1217                        bool polytype = isPolyType( addrExpr->get_arg()->get_result(), scopeTyVars, env );
1218                        addrExpr->set_arg( mutateExpression( addrExpr->get_arg() ) );
1219                        if ( polytype || needs ) {
1220                                Expression *ret = addrExpr->get_arg();
1221                                delete ret->get_result();
1222                                ret->set_result( addrExpr->get_result()->clone() );
1223                                addrExpr->set_arg( 0 );
1224                                delete addrExpr;
1225                                return ret;
1226                        } else {
1227                                return addrExpr;
1228                        } // if
1229                }
1230
1231                Statement * Pass1::mutate( ReturnStmt *returnStmt ) {
1232                        if ( retval && returnStmt->get_expr() ) {
1233                                assert( returnStmt->get_expr()->has_result() && ! returnStmt->get_expr()->get_result()->isVoid() );
1234                                delete returnStmt->get_expr();
1235                                returnStmt->set_expr( 0 );
1236                        } else {
1237                                returnStmt->set_expr( mutateExpression( returnStmt->get_expr() ) );
1238                        } // if
1239                        return returnStmt;
1240                }
1241
1242                Type * Pass1::mutate( PointerType *pointerType ) {
1243                        scopeTyVars.beginScope();
1244                        makeTyVarMap( pointerType, scopeTyVars );
1245
1246                        Type *ret = Mutator::mutate( pointerType );
1247
1248                        scopeTyVars.endScope();
1249                        return ret;
1250                }
1251
1252                Type * Pass1::mutate( FunctionType *functionType ) {
1253                        scopeTyVars.beginScope();
1254                        makeTyVarMap( functionType, scopeTyVars );
1255
1256                        Type *ret = Mutator::mutate( functionType );
1257
1258                        scopeTyVars.endScope();
1259                        return ret;
1260                }
1261
1262                void Pass1::doBeginScope() {
1263                        adapters.beginScope();
1264                }
1265
1266                void Pass1::doEndScope() {
1267                        adapters.endScope();
1268                }
1269
1270////////////////////////////////////////// Pass2 ////////////////////////////////////////////////////
1271
1272                void Pass2::addAdapters( FunctionType *functionType ) {
1273                        std::list< DeclarationWithType *> &paramList = functionType->get_parameters();
1274                        std::list< FunctionType *> functions;
1275                        for ( std::list< DeclarationWithType *>::iterator arg = paramList.begin(); arg != paramList.end(); ++arg ) {
1276                                Type *orig = (*arg)->get_type();
1277                                findAndReplaceFunction( orig, functions, scopeTyVars, needsAdapter );
1278                                (*arg)->set_type( orig );
1279                        }
1280                        std::set< std::string > adaptersDone;
1281                        for ( std::list< FunctionType *>::iterator funType = functions.begin(); funType != functions.end(); ++funType ) {
1282                                std::string mangleName = mangleAdapterName( *funType, scopeTyVars );
1283                                if ( adaptersDone.find( mangleName ) == adaptersDone.end() ) {
1284                                        std::string adapterName = makeAdapterName( mangleName );
1285                                        paramList.push_front( new ObjectDecl( adapterName, Type::StorageClasses(), LinkageSpec::C, 0, new PointerType( Type::Qualifiers(), makeAdapterType( *funType, scopeTyVars ) ), 0 ) );
1286                                        adaptersDone.insert( adaptersDone.begin(), mangleName );
1287                                }
1288                        }
1289//  deleteAll( functions );
1290                }
1291
1292                template< typename DeclClass >
1293                DeclClass * Pass2::handleDecl( DeclClass *decl ) {
1294                        DeclClass *ret = static_cast< DeclClass *>( Parent::mutate( decl ) );
1295
1296                        return ret;
1297                }
1298
1299                /// determines if `pref` is a prefix of `str`
1300                bool isPrefix( const std::string & str, const std::string & pref ) {
1301                        if ( pref.size() > str.size() ) return false;
1302                        auto its = std::mismatch( pref.begin(), pref.end(), str.begin() );
1303                        return its.first == pref.end();
1304                }
1305
1306                DeclarationWithType * Pass2::mutate( FunctionDecl *functionDecl ) {
1307                        functionDecl = safe_dynamic_cast< FunctionDecl * > ( handleDecl( functionDecl ) );
1308                        FunctionType * ftype = functionDecl->get_functionType();
1309                        if ( ! ftype->get_returnVals().empty() && functionDecl->get_statements() ) {
1310                                if ( ! isPrefix( functionDecl->get_name(), "_thunk" ) && ! isPrefix( functionDecl->get_name(), "_adapter" ) ) { // xxx - remove check for prefix once thunks properly use ctor/dtors
1311                                        assert( ftype->get_returnVals().size() == 1 );
1312                                        DeclarationWithType * retval = ftype->get_returnVals().front();
1313                                        if ( retval->get_name() == "" ) {
1314                                                retval->set_name( "_retval" );
1315                                        }
1316                                        functionDecl->get_statements()->get_kids().push_front( new DeclStmt( noLabels, retval ) );
1317                                        DeclarationWithType * newRet = retval->clone(); // for ownership purposes
1318                                        ftype->get_returnVals().front() = newRet;
1319                                }
1320                        }
1321                        // errors should have been caught by this point, remove initializers from parameters to allow correct codegen of default arguments
1322                        for ( Declaration * param : functionDecl->get_functionType()->get_parameters() ) {
1323                                if ( ObjectDecl * obj = dynamic_cast< ObjectDecl * >( param ) ) {
1324                                        delete obj->get_init();
1325                                        obj->set_init( nullptr );
1326                                }
1327                        }
1328                        return functionDecl;
1329                }
1330
1331                ObjectDecl * Pass2::mutate( ObjectDecl *objectDecl ) {
1332                        return handleDecl( objectDecl );
1333                }
1334
1335                template< typename AggDecl >
1336                AggDecl * Pass2::handleAggDecl( AggDecl * aggDecl ) {
1337                        // prevent tyVars from leaking into containing scope
1338                        scopeTyVars.beginScope();
1339                        Parent::mutate( aggDecl );
1340                        scopeTyVars.endScope();
1341                        return aggDecl;
1342                }
1343
1344                StructDecl * Pass2::mutate( StructDecl *aggDecl ) {
1345                        return handleAggDecl( aggDecl );
1346                }
1347
1348                UnionDecl * Pass2::mutate( UnionDecl *aggDecl ) {
1349                        return handleAggDecl( aggDecl );
1350                }
1351
1352                TypeDecl * Pass2::mutate( TypeDecl *typeDecl ) {
1353                        addToTyVarMap( typeDecl, scopeTyVars );
1354                        if ( typeDecl->get_base() ) {
1355                                return handleDecl( typeDecl );
1356                        } else {
1357                                return Parent::mutate( typeDecl );
1358                        }
1359                }
1360
1361                TypedefDecl * Pass2::mutate( TypedefDecl *typedefDecl ) {
1362                        return handleDecl( typedefDecl );
1363                }
1364
1365                Type * Pass2::mutate( PointerType *pointerType ) {
1366                        scopeTyVars.beginScope();
1367                        makeTyVarMap( pointerType, scopeTyVars );
1368
1369                        Type *ret = Parent::mutate( pointerType );
1370
1371                        scopeTyVars.endScope();
1372                        return ret;
1373                }
1374
1375                Type *Pass2::mutate( FunctionType *funcType ) {
1376                        scopeTyVars.beginScope();
1377                        makeTyVarMap( funcType, scopeTyVars );
1378
1379                        // move polymorphic return type to parameter list
1380                        if ( isDynRet( funcType ) ) {
1381                                ObjectDecl *ret = safe_dynamic_cast< ObjectDecl* >( funcType->get_returnVals().front() );
1382                                ret->set_type( new PointerType( Type::Qualifiers(), ret->get_type() ) );
1383                                funcType->get_parameters().push_front( ret );
1384                                funcType->get_returnVals().pop_front();
1385                                ret->set_init( nullptr ); // xxx - memory leak?
1386                        }
1387
1388                        // add size/align and assertions for type parameters to parameter list
1389                        std::list< DeclarationWithType *>::iterator last = funcType->get_parameters().begin();
1390                        std::list< DeclarationWithType *> inferredParams;
1391                        ObjectDecl newObj( "", Type::StorageClasses(), LinkageSpec::C, 0, new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt ), 0 );
1392                        ObjectDecl newPtr( "", Type::StorageClasses(), LinkageSpec::C, 0,
1393                                           new PointerType( Type::Qualifiers(), new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt ) ), 0 );
1394                        for ( Type::ForallList::const_iterator tyParm = funcType->get_forall().begin(); tyParm != funcType->get_forall().end(); ++tyParm ) {
1395                                ObjectDecl *sizeParm, *alignParm;
1396                                // add all size and alignment parameters to parameter list
1397                                if ( (*tyParm)->isComplete() ) {
1398                                        TypeInstType parmType( Type::Qualifiers(), (*tyParm)->get_name(), *tyParm );
1399                                        std::string parmName = mangleType( &parmType );
1400
1401                                        sizeParm = newObj.clone();
1402                                        sizeParm->set_name( sizeofName( parmName ) );
1403                                        last = funcType->get_parameters().insert( last, sizeParm );
1404                                        ++last;
1405
1406                                        alignParm = newObj.clone();
1407                                        alignParm->set_name( alignofName( parmName ) );
1408                                        last = funcType->get_parameters().insert( last, alignParm );
1409                                        ++last;
1410                                }
1411                                // move all assertions into parameter list
1412                                for ( std::list< DeclarationWithType *>::iterator assert = (*tyParm)->get_assertions().begin(); assert != (*tyParm)->get_assertions().end(); ++assert ) {
1413//      *assert = (*assert)->acceptMutator( *this );
1414                                        inferredParams.push_back( *assert );
1415                                }
1416                                (*tyParm)->get_assertions().clear();
1417                        }
1418
1419                        // add size/align for generic parameter types to parameter list
1420                        std::set< std::string > seenTypes; // sizeofName for generic types we've seen
1421                        for ( std::list< DeclarationWithType* >::const_iterator fnParm = last; fnParm != funcType->get_parameters().end(); ++fnParm ) {
1422                                Type *polyType = isPolyType( (*fnParm)->get_type(), scopeTyVars );
1423                                if ( polyType && ! dynamic_cast< TypeInstType* >( polyType ) ) {
1424                                        std::string typeName = mangleType( polyType );
1425                                        if ( seenTypes.count( typeName ) ) continue;
1426
1427                                        ObjectDecl *sizeParm, *alignParm, *offsetParm;
1428                                        sizeParm = newObj.clone();
1429                                        sizeParm->set_name( sizeofName( typeName ) );
1430                                        last = funcType->get_parameters().insert( last, sizeParm );
1431                                        ++last;
1432
1433                                        alignParm = newObj.clone();
1434                                        alignParm->set_name( alignofName( typeName ) );
1435                                        last = funcType->get_parameters().insert( last, alignParm );
1436                                        ++last;
1437
1438                                        if ( StructInstType *polyBaseStruct = dynamic_cast< StructInstType* >( polyType ) ) {
1439                                                // NOTE zero-length arrays are illegal in C, so empty structs have no offset array
1440                                                if ( ! polyBaseStruct->get_baseStruct()->get_members().empty() ) {
1441                                                        offsetParm = newPtr.clone();
1442                                                        offsetParm->set_name( offsetofName( typeName ) );
1443                                                        last = funcType->get_parameters().insert( last, offsetParm );
1444                                                        ++last;
1445                                                }
1446                                        }
1447
1448                                        seenTypes.insert( typeName );
1449                                }
1450                        }
1451
1452                        // splice assertion parameters into parameter list
1453                        funcType->get_parameters().splice( last, inferredParams );
1454                        addAdapters( funcType );
1455                        mutateAll( funcType->get_returnVals(), *this );
1456                        mutateAll( funcType->get_parameters(), *this );
1457
1458                        scopeTyVars.endScope();
1459                        return funcType;
1460                }
1461
1462////////////////////////////////////////// PolyGenericCalculator ////////////////////////////////////////////////////
1463
1464                PolyGenericCalculator::PolyGenericCalculator()
1465                        : Parent(), knownLayouts(), knownOffsets(), bufNamer( "_buf" ) {}
1466
1467                void PolyGenericCalculator::beginTypeScope( Type *ty ) {
1468                        scopeTyVars.beginScope();
1469                        makeTyVarMap( ty, scopeTyVars );
1470                }
1471
1472                void PolyGenericCalculator::endTypeScope() {
1473                        scopeTyVars.endScope();
1474                }
1475
1476                template< typename DeclClass >
1477                DeclClass * PolyGenericCalculator::handleDecl( DeclClass *decl, Type *type ) {
1478                        beginTypeScope( type );
1479                        // knownLayouts.beginScope();
1480                        // knownOffsets.beginScope();
1481
1482                        DeclClass *ret = static_cast< DeclClass *>( Parent::mutate( decl ) );
1483
1484                        // knownOffsets.endScope();
1485                        // knownLayouts.endScope();
1486                        endTypeScope();
1487                        return ret;
1488                }
1489
1490                ObjectDecl * PolyGenericCalculator::mutate( ObjectDecl *objectDecl ) {
1491                        return handleDecl( objectDecl, objectDecl->get_type() );
1492                }
1493
1494                DeclarationWithType * PolyGenericCalculator::mutate( FunctionDecl *functionDecl ) {
1495                        knownLayouts.beginScope();
1496                        knownOffsets.beginScope();
1497
1498                        DeclarationWithType * decl = handleDecl( functionDecl, functionDecl->get_functionType() );
1499                        knownOffsets.endScope();
1500                        knownLayouts.endScope();
1501                        return decl;
1502                }
1503
1504                TypedefDecl * PolyGenericCalculator::mutate( TypedefDecl *typedefDecl ) {
1505                        return handleDecl( typedefDecl, typedefDecl->get_base() );
1506                }
1507
1508                TypeDecl * PolyGenericCalculator::mutate( TypeDecl *typeDecl ) {
1509                        addToTyVarMap( typeDecl, scopeTyVars );
1510                        return Parent::mutate( typeDecl );
1511                }
1512
1513                Type * PolyGenericCalculator::mutate( PointerType *pointerType ) {
1514                        beginTypeScope( pointerType );
1515
1516                        Type *ret = Parent::mutate( pointerType );
1517
1518                        endTypeScope();
1519                        return ret;
1520                }
1521
1522                Type * PolyGenericCalculator::mutate( FunctionType *funcType ) {
1523                        beginTypeScope( funcType );
1524
1525                        // make sure that any type information passed into the function is accounted for
1526                        for ( std::list< DeclarationWithType* >::const_iterator fnParm = funcType->get_parameters().begin(); fnParm != funcType->get_parameters().end(); ++fnParm ) {
1527                                // condition here duplicates that in Pass2::mutate( FunctionType* )
1528                                Type *polyType = isPolyType( (*fnParm)->get_type(), scopeTyVars );
1529                                if ( polyType && ! dynamic_cast< TypeInstType* >( polyType ) ) {
1530                                        knownLayouts.insert( mangleType( polyType ) );
1531                                }
1532                        }
1533
1534                        Type *ret = Parent::mutate( funcType );
1535
1536                        endTypeScope();
1537                        return ret;
1538                }
1539
1540                Statement *PolyGenericCalculator::mutate( DeclStmt *declStmt ) {
1541                        if ( ObjectDecl *objectDecl = dynamic_cast< ObjectDecl *>( declStmt->get_decl() ) ) {
1542                                if ( findGeneric( objectDecl->get_type() ) ) {
1543                                        // change initialization of a polymorphic value object to allocate via a VLA
1544                                        // (alloca was previously used, but can't be safely used in loops)
1545                                        Type *declType = objectDecl->get_type();
1546                                        std::string bufName = bufNamer.newName();
1547                                        ObjectDecl *newBuf = new ObjectDecl( bufName, Type::StorageClasses(), LinkageSpec::C, 0,
1548                                                new ArrayType( Type::Qualifiers(), new BasicType( Type::Qualifiers(), BasicType::Kind::Char), new NameExpr( sizeofName( mangleType(declType) ) ),
1549                                                true, false, std::list<Attribute*>{ new Attribute( std::string{"aligned"}, std::list<Expression*>{ new ConstantExpr( Constant::from_int(8) ) } ) } ), 0 );
1550                                        stmtsToAdd.push_back( new DeclStmt( noLabels, newBuf ) );
1551
1552                                        delete objectDecl->get_init();
1553
1554                                        objectDecl->set_init( new SingleInit( new NameExpr( bufName ) ) );
1555                                }
1556                        }
1557                        return Parent::mutate( declStmt );
1558                }
1559
1560                /// Finds the member in the base list that matches the given declaration; returns its index, or -1 if not present
1561                long findMember( DeclarationWithType *memberDecl, std::list< Declaration* > &baseDecls ) {
1562                        long i = 0;
1563                        for(std::list< Declaration* >::const_iterator decl = baseDecls.begin(); decl != baseDecls.end(); ++decl, ++i ) {
1564                                if ( memberDecl->get_name() != (*decl)->get_name() ) continue;
1565
1566                                if ( DeclarationWithType *declWithType = dynamic_cast< DeclarationWithType* >( *decl ) ) {
1567                                        if ( memberDecl->get_mangleName().empty() || declWithType->get_mangleName().empty()
1568                                             || memberDecl->get_mangleName() == declWithType->get_mangleName() ) return i;
1569                                        else continue;
1570                                } else return i;
1571                        }
1572                        return -1;
1573                }
1574
1575                /// Returns an index expression into the offset array for a type
1576                Expression *makeOffsetIndex( Type *objectType, long i ) {
1577                        ConstantExpr *fieldIndex = new ConstantExpr( Constant::from_ulong( i ) );
1578                        UntypedExpr *fieldOffset = new UntypedExpr( new NameExpr( "?[?]" ) );
1579                        fieldOffset->get_args().push_back( new NameExpr( offsetofName( mangleType( objectType ) ) ) );
1580                        fieldOffset->get_args().push_back( fieldIndex );
1581                        return fieldOffset;
1582                }
1583
1584                Expression *PolyGenericCalculator::mutate( MemberExpr *memberExpr ) {
1585                        // mutate, exiting early if no longer MemberExpr
1586                        Expression *expr = Parent::mutate( memberExpr );
1587                        memberExpr = dynamic_cast< MemberExpr* >( expr );
1588                        if ( ! memberExpr ) return expr;
1589
1590                        // only mutate member expressions for polymorphic types
1591                        int tyDepth;
1592                        Type *objectType = hasPolyBase( memberExpr->get_aggregate()->get_result(), scopeTyVars, &tyDepth );
1593                        if ( ! objectType ) return memberExpr;
1594                        findGeneric( objectType ); // ensure layout for this type is available
1595
1596                        // replace member expression with dynamically-computed layout expression
1597                        Expression *newMemberExpr = 0;
1598                        if ( StructInstType *structType = dynamic_cast< StructInstType* >( objectType ) ) {
1599                                // look up offset index
1600                                long i = findMember( memberExpr->get_member(), structType->get_baseStruct()->get_members() );
1601                                if ( i == -1 ) return memberExpr;
1602
1603                                // replace member expression with pointer to base plus offset
1604                                UntypedExpr *fieldLoc = new UntypedExpr( new NameExpr( "?+?" ) );
1605                                Expression * aggr = memberExpr->get_aggregate()->clone();
1606                                delete aggr->get_env(); // xxx - there's a problem with keeping the env for some reason, so for now just get rid of it
1607                                aggr->set_env( nullptr );
1608                                fieldLoc->get_args().push_back( aggr );
1609                                fieldLoc->get_args().push_back( makeOffsetIndex( objectType, i ) );
1610                                fieldLoc->set_result( memberExpr->get_result()->clone() );
1611                                newMemberExpr = fieldLoc;
1612                        } else if ( dynamic_cast< UnionInstType* >( objectType ) ) {
1613                                // union members are all at offset zero, so just use the aggregate expr
1614                                Expression * aggr = memberExpr->get_aggregate()->clone();
1615                                delete aggr->get_env(); // xxx - there's a problem with keeping the env for some reason, so for now just get rid of it
1616                                aggr->set_env( nullptr );
1617                                newMemberExpr = aggr;
1618                                newMemberExpr->set_result( memberExpr->get_result()->clone() );
1619                        } else return memberExpr;
1620                        assert( newMemberExpr );
1621
1622                        Type *memberType = memberExpr->get_member()->get_type();
1623                        if ( ! isPolyType( memberType, scopeTyVars ) ) {
1624                                // 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
1625                                CastExpr *ptrCastExpr = new CastExpr( newMemberExpr, new PointerType( Type::Qualifiers(), memberType->clone() ) );
1626                                UntypedExpr *derefExpr = UntypedExpr::createDeref( ptrCastExpr );
1627                                newMemberExpr = derefExpr;
1628                        }
1629
1630                        delete memberExpr;
1631                        return newMemberExpr;
1632                }
1633
1634                ObjectDecl *PolyGenericCalculator::makeVar( const std::string &name, Type *type, Initializer *init ) {
1635                        ObjectDecl *newObj = new ObjectDecl( name, Type::StorageClasses(), LinkageSpec::C, 0, type, init );
1636                        stmtsToAdd.push_back( new DeclStmt( noLabels, newObj ) );
1637                        return newObj;
1638                }
1639
1640                void PolyGenericCalculator::addOtypeParamsToLayoutCall( UntypedExpr *layoutCall, const std::list< Type* > &otypeParams ) {
1641                        for ( std::list< Type* >::const_iterator param = otypeParams.begin(); param != otypeParams.end(); ++param ) {
1642                                if ( findGeneric( *param ) ) {
1643                                        // push size/align vars for a generic parameter back
1644                                        std::string paramName = mangleType( *param );
1645                                        layoutCall->get_args().push_back( new NameExpr( sizeofName( paramName ) ) );
1646                                        layoutCall->get_args().push_back( new NameExpr( alignofName( paramName ) ) );
1647                                } else {
1648                                        layoutCall->get_args().push_back( new SizeofExpr( (*param)->clone() ) );
1649                                        layoutCall->get_args().push_back( new AlignofExpr( (*param)->clone() ) );
1650                                }
1651                        }
1652                }
1653
1654                /// returns true if any of the otype parameters have a dynamic layout and puts all otype parameters in the output list
1655                bool findGenericParams( std::list< TypeDecl* > &baseParams, std::list< Expression* > &typeParams, std::list< Type* > &out ) {
1656                        bool hasDynamicLayout = false;
1657
1658                        std::list< TypeDecl* >::const_iterator baseParam = baseParams.begin();
1659                        std::list< Expression* >::const_iterator typeParam = typeParams.begin();
1660                        for ( ; baseParam != baseParams.end() && typeParam != typeParams.end(); ++baseParam, ++typeParam ) {
1661                                // skip non-otype parameters
1662                                if ( ! (*baseParam)->isComplete() ) continue;
1663                                TypeExpr *typeExpr = dynamic_cast< TypeExpr* >( *typeParam );
1664                                assert( typeExpr && "all otype parameters should be type expressions" );
1665
1666                                Type *type = typeExpr->get_type();
1667                                out.push_back( type );
1668                                if ( isPolyType( type ) ) hasDynamicLayout = true;
1669                        }
1670                        assert( baseParam == baseParams.end() && typeParam == typeParams.end() );
1671
1672                        return hasDynamicLayout;
1673                }
1674
1675                bool PolyGenericCalculator::findGeneric( Type *ty ) {
1676                        ty = replaceTypeInst( ty, env );
1677
1678                        if ( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( ty ) ) {
1679                                if ( scopeTyVars.find( typeInst->get_name() ) != scopeTyVars.end() ) {
1680                                        // NOTE assumes here that getting put in the scopeTyVars included having the layout variables set
1681                                        return true;
1682                                }
1683                                return false;
1684                        } else if ( StructInstType *structTy = dynamic_cast< StructInstType* >( ty ) ) {
1685                                // check if this type already has a layout generated for it
1686                                std::string typeName = mangleType( ty );
1687                                if ( knownLayouts.find( typeName ) != knownLayouts.end() ) return true;
1688
1689                                // check if any of the type parameters have dynamic layout; if none do, this type is (or will be) monomorphized
1690                                std::list< Type* > otypeParams;
1691                                if ( ! findGenericParams( *structTy->get_baseParameters(), structTy->get_parameters(), otypeParams ) ) return false;
1692
1693                                // insert local variables for layout and generate call to layout function
1694                                knownLayouts.insert( typeName );  // done early so as not to interfere with the later addition of parameters to the layout call
1695                                Type *layoutType = new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt );
1696
1697                                int n_members = structTy->get_baseStruct()->get_members().size();
1698                                if ( n_members == 0 ) {
1699                                        // all empty structs have the same layout - size 1, align 1
1700                                        makeVar( sizeofName( typeName ), layoutType, new SingleInit( new ConstantExpr( Constant::from_ulong( (unsigned long)1 ) ) ) );
1701                                        makeVar( alignofName( typeName ), layoutType->clone(), new SingleInit( new ConstantExpr( Constant::from_ulong( (unsigned long)1 ) ) ) );
1702                                        // NOTE zero-length arrays are forbidden in C, so empty structs have no offsetof array
1703                                } else {
1704                                        ObjectDecl *sizeVar = makeVar( sizeofName( typeName ), layoutType );
1705                                        ObjectDecl *alignVar = makeVar( alignofName( typeName ), layoutType->clone() );
1706                                        ObjectDecl *offsetVar = makeVar( offsetofName( typeName ), new ArrayType( Type::Qualifiers(), layoutType->clone(), new ConstantExpr( Constant::from_int( n_members ) ), false, false ) );
1707
1708                                        // generate call to layout function
1709                                        UntypedExpr *layoutCall = new UntypedExpr( new NameExpr( layoutofName( structTy->get_baseStruct() ) ) );
1710                                        layoutCall->get_args().push_back( new AddressExpr( new VariableExpr( sizeVar ) ) );
1711                                        layoutCall->get_args().push_back( new AddressExpr( new VariableExpr( alignVar ) ) );
1712                                        layoutCall->get_args().push_back( new VariableExpr( offsetVar ) );
1713                                        addOtypeParamsToLayoutCall( layoutCall, otypeParams );
1714
1715                                        stmtsToAdd.push_back( new ExprStmt( noLabels, layoutCall ) );
1716                                }
1717
1718                                return true;
1719                        } else if ( UnionInstType *unionTy = dynamic_cast< UnionInstType* >( ty ) ) {
1720                                // check if this type already has a layout generated for it
1721                                std::string typeName = mangleType( ty );
1722                                if ( knownLayouts.find( typeName ) != knownLayouts.end() ) return true;
1723
1724                                // check if any of the type parameters have dynamic layout; if none do, this type is (or will be) monomorphized
1725                                std::list< Type* > otypeParams;
1726                                if ( ! findGenericParams( *unionTy->get_baseParameters(), unionTy->get_parameters(), otypeParams ) ) return false;
1727
1728                                // insert local variables for layout and generate call to layout function
1729                                knownLayouts.insert( typeName );  // done early so as not to interfere with the later addition of parameters to the layout call
1730                                Type *layoutType = new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt );
1731
1732                                ObjectDecl *sizeVar = makeVar( sizeofName( typeName ), layoutType );
1733                                ObjectDecl *alignVar = makeVar( alignofName( typeName ), layoutType->clone() );
1734
1735                                // generate call to layout function
1736                                UntypedExpr *layoutCall = new UntypedExpr( new NameExpr( layoutofName( unionTy->get_baseUnion() ) ) );
1737                                layoutCall->get_args().push_back( new AddressExpr( new VariableExpr( sizeVar ) ) );
1738                                layoutCall->get_args().push_back( new AddressExpr( new VariableExpr( alignVar ) ) );
1739                                addOtypeParamsToLayoutCall( layoutCall, otypeParams );
1740
1741                                stmtsToAdd.push_back( new ExprStmt( noLabels, layoutCall ) );
1742
1743                                return true;
1744                        }
1745
1746                        return false;
1747                }
1748
1749                Expression *PolyGenericCalculator::mutate( SizeofExpr *sizeofExpr ) {
1750                        Type *ty = sizeofExpr->get_type();
1751                        if ( findGeneric( ty ) ) {
1752                                Expression *ret = new NameExpr( sizeofName( mangleType( ty ) ) );
1753                                delete sizeofExpr;
1754                                return ret;
1755                        }
1756                        return sizeofExpr;
1757                }
1758
1759                Expression *PolyGenericCalculator::mutate( AlignofExpr *alignofExpr ) {
1760                        Type *ty = alignofExpr->get_type();
1761                        if ( findGeneric( ty ) ) {
1762                                Expression *ret = new NameExpr( alignofName( mangleType( ty ) ) );
1763                                delete alignofExpr;
1764                                return ret;
1765                        }
1766                        return alignofExpr;
1767                }
1768
1769                Expression *PolyGenericCalculator::mutate( OffsetofExpr *offsetofExpr ) {
1770                        // mutate, exiting early if no longer OffsetofExpr
1771                        Expression *expr = Parent::mutate( offsetofExpr );
1772                        offsetofExpr = dynamic_cast< OffsetofExpr* >( expr );
1773                        if ( ! offsetofExpr ) return expr;
1774
1775                        // only mutate expressions for polymorphic structs/unions
1776                        Type *ty = offsetofExpr->get_type();
1777                        if ( ! findGeneric( ty ) ) return offsetofExpr;
1778
1779                        if ( StructInstType *structType = dynamic_cast< StructInstType* >( ty ) ) {
1780                                // replace offsetof expression by index into offset array
1781                                long i = findMember( offsetofExpr->get_member(), structType->get_baseStruct()->get_members() );
1782                                if ( i == -1 ) return offsetofExpr;
1783
1784                                Expression *offsetInd = makeOffsetIndex( ty, i );
1785                                delete offsetofExpr;
1786                                return offsetInd;
1787                        } else if ( dynamic_cast< UnionInstType* >( ty ) ) {
1788                                // all union members are at offset zero
1789                                delete offsetofExpr;
1790                                return new ConstantExpr( Constant::from_ulong( 0 ) );
1791                        } else return offsetofExpr;
1792                }
1793
1794                Expression *PolyGenericCalculator::mutate( OffsetPackExpr *offsetPackExpr ) {
1795                        StructInstType *ty = offsetPackExpr->get_type();
1796
1797                        Expression *ret = 0;
1798                        if ( findGeneric( ty ) ) {
1799                                // pull offset back from generated type information
1800                                ret = new NameExpr( offsetofName( mangleType( ty ) ) );
1801                        } else {
1802                                std::string offsetName = offsetofName( mangleType( ty ) );
1803                                if ( knownOffsets.find( offsetName ) != knownOffsets.end() ) {
1804                                        // use the already-generated offsets for this type
1805                                        ret = new NameExpr( offsetName );
1806                                } else {
1807                                        knownOffsets.insert( offsetName );
1808
1809                                        std::list< Declaration* > &baseMembers = ty->get_baseStruct()->get_members();
1810                                        Type *offsetType = new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt );
1811
1812                                        // build initializer list for offset array
1813                                        std::list< Initializer* > inits;
1814                                        for ( std::list< Declaration* >::const_iterator member = baseMembers.begin(); member != baseMembers.end(); ++member ) {
1815                                                if ( DeclarationWithType *memberDecl = dynamic_cast< DeclarationWithType* >( *member ) ) {
1816                                                        inits.push_back( new SingleInit( new OffsetofExpr( ty->clone(), memberDecl ) ) );
1817                                                } else {
1818                                                        assertf( false, "Requesting offset of Non-DWT member: %s", toString( *member ).c_str() );
1819                                                }
1820                                        }
1821
1822                                        // build the offset array and replace the pack with a reference to it
1823                                        ObjectDecl *offsetArray = makeVar( offsetName, new ArrayType( Type::Qualifiers(), offsetType, new ConstantExpr( Constant::from_ulong( baseMembers.size() ) ), false, false ),
1824                                                        new ListInit( inits ) );
1825                                        ret = new VariableExpr( offsetArray );
1826                                }
1827                        }
1828
1829                        delete offsetPackExpr;
1830                        return ret;
1831                }
1832
1833                void PolyGenericCalculator::doBeginScope() {
1834                        knownLayouts.beginScope();
1835                        knownOffsets.beginScope();
1836                }
1837
1838                void PolyGenericCalculator::doEndScope() {
1839                        knownLayouts.endScope();
1840                        knownOffsets.endScope();
1841                }
1842
1843////////////////////////////////////////// Pass3 ////////////////////////////////////////////////////
1844
1845                template< typename DeclClass >
1846                DeclClass * Pass3::handleDecl( DeclClass *decl, Type *type ) {
1847                        scopeTyVars.beginScope();
1848                        makeTyVarMap( type, scopeTyVars );
1849
1850                        DeclClass *ret = static_cast< DeclClass *>( Mutator::mutate( decl ) );
1851                        // ScrubTyVars::scrub( decl, scopeTyVars );
1852                        ScrubTyVars::scrubAll( decl );
1853
1854                        scopeTyVars.endScope();
1855                        return ret;
1856                }
1857
1858                ObjectDecl * Pass3::mutate( ObjectDecl *objectDecl ) {
1859                        return handleDecl( objectDecl, objectDecl->get_type() );
1860                }
1861
1862                DeclarationWithType * Pass3::mutate( FunctionDecl *functionDecl ) {
1863                        return handleDecl( functionDecl, functionDecl->get_functionType() );
1864                }
1865
1866                TypedefDecl * Pass3::mutate( TypedefDecl *typedefDecl ) {
1867                        return handleDecl( typedefDecl, typedefDecl->get_base() );
1868                }
1869
1870                TypeDecl * Pass3::mutate( TypeDecl *typeDecl ) {
1871//   Initializer *init = 0;
1872//   std::list< Expression *> designators;
1873//   addToTyVarMap( typeDecl, scopeTyVars );
1874//   if ( typeDecl->get_base() ) {
1875//     init = new SimpleInit( new SizeofExpr( handleDecl( typeDecl, typeDecl->get_base() ) ), designators );
1876//   }
1877//   return new ObjectDecl( typeDecl->get_name(), Declaration::Extern, LinkageSpec::C, 0, new BasicType( Type::Qualifiers(), BasicType::UnsignedInt ), init );
1878
1879                        addToTyVarMap( typeDecl, scopeTyVars );
1880                        return Mutator::mutate( typeDecl );
1881                }
1882
1883                Type * Pass3::mutate( PointerType *pointerType ) {
1884                        scopeTyVars.beginScope();
1885                        makeTyVarMap( pointerType, scopeTyVars );
1886
1887                        Type *ret = Mutator::mutate( pointerType );
1888
1889                        scopeTyVars.endScope();
1890                        return ret;
1891                }
1892
1893                Type * Pass3::mutate( FunctionType *functionType ) {
1894                        scopeTyVars.beginScope();
1895                        makeTyVarMap( functionType, scopeTyVars );
1896
1897                        Type *ret = Mutator::mutate( functionType );
1898
1899                        scopeTyVars.endScope();
1900                        return ret;
1901                }
1902        } // anonymous namespace
1903} // namespace GenPoly
1904
1905// Local Variables: //
1906// tab-width: 4 //
1907// mode: c++ //
1908// compile-command: "make install" //
1909// End: //
Note: See TracBrowser for help on using the repository browser.