source: src/GenPoly/Box.cc @ d55d7a6

aaron-thesisarm-ehcleanup-dtorsdeferred_resndemanglerjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprnew-envno_listpersistent-indexerresolv-newwith_gc
Last change on this file since d55d7a6 was d55d7a6, checked in by Thierry Delisle <tdelisle@…>, 4 years ago

Massive change to errors to enable warnings

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