source: src/GenPoly/Box.cc @ 138e29e

aaron-thesisarm-ehcleanup-dtorsdeferred_resndemanglerenumforall-pointer-decayjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprnew-envno_listpersistent-indexerpthread-emulationqualifiedEnumresolv-newwith_gc
Last change on this file since 138e29e was 138e29e, checked in by Thierry Delisle <tdelisle@…>, 6 years ago

Implemented filename and linenumber errors in most cases, only missing constructor errors apparently

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