source: src/GenPoly/Box.cc @ 201182a

ADTaaron-thesisarm-ehast-experimentalcleanup-dtorsdeferred_resndemanglerenumforall-pointer-decayjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprnew-envno_listpersistent-indexerpthread-emulationqualifiedEnumresolv-newwith_gc
Last change on this file since 201182a was 201182a, checked in by Rob Schluntz <rschlunt@…>, 7 years ago

Convert Box Pass1 to PassVisitor?

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