source: src/GenPoly/Box.cc @ a0ad7dc

aaron-thesisarm-ehcleanup-dtorsdeferred_resndemanglerjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprnew-envno_listpersistent-indexerresolv-newwith_gc
Last change on this file since a0ad7dc was a0ad7dc, checked in by Aaron Moss <a3moss@…>, 5 years ago

Switch alloca's to VLA's for safe in-loop use

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