source: src/GenPoly/Box.cc @ f5392c1

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

don't generate return value temporaries for adapters

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