source: src/GenPoly/Box.cc @ 83794e1

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

Add unused attributes to assertion parameters and adapters

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