source: src/GenPoly/Box.cc @ acd7c5dd

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

Apply generalized lvalue pass to MemberExpr?

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