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

new-envwith_gc
Last change on this file since 2efe4b8 was 2efe4b8, checked in by Aaron Moss <a3moss@…>, 4 years ago

Assorted GC bugfixes

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