source: src/GenPoly/Box.cc @ 5802a4f

ADTaaron-thesisarm-ehast-experimentalcleanup-dtorsdeferred_resndemanglerenumforall-pointer-decayjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprnew-envno_listpersistent-indexerpthread-emulationqualifiedEnumresolv-newwith_gc
Last change on this file since 5802a4f was 5802a4f, checked in by Rob Schluntz <rschlunt@…>, 8 years ago

remove assignment to polymorphic return values in Box

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