source: src/GenPoly/Box.cc @ 68f9c43

new-envwith_gc
Last change on this file since 68f9c43 was 68f9c43, checked in by Aaron Moss <a3moss@…>, 5 years ago

First pass at delete removal

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