source: src/GenPoly/Box.cc @ dd0c97b

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

prevent generic parameters from polluting the outer scope in Box Pass2

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