source: src/GenPoly/Box.cc @ 2ae171d8

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

Minor clean up

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