source: src/GenPoly/Box.cc @ 436c0de

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

Merge branch 'master' of plg.uwaterloo.ca:/u/cforall/software/cfa/cfa-cc

Conflicts:

src/InitTweak/GenInit.cc

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