source: src/GenPoly/Box.cc @ 3a5131e

aaron-thesisarm-ehcleanup-dtorsdeferred_resndemanglerenumforall-pointer-decayjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprnew-envno_listpersistent-indexerpthread-emulationqualifiedEnumresolv-newwith_gc
Last change on this file since 3a5131e was 3a5131e, checked in by Peter A. Buhr <pabuhr@…>, 6 years ago

handle KR function declarations

  • Property mode set to 100644
File size: 86.4 KB
Line 
1//
2// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo
3//
4// The contents of this file are covered under the licence agreement in the
5// file "LICENCE" distributed with Cforall.
6//
7// Box.cc --
8//
9// Author           : Richard C. Bilson
10// Created On       : Mon May 18 07:44:20 2015
11// Last Modified By : Peter A. Buhr
12// Last Modified On : Thu Feb 16 14:57:16 2017
13// Update Count     : 297
14//
15
16#include <algorithm>
17#include <iterator>
18#include <list>
19#include <map>
20#include <set>
21#include <stack>
22#include <string>
23#include <utility>
24#include <vector>
25#include <cassert>
26
27#include "Box.h"
28#include "DeclMutator.h"
29#include "PolyMutator.h"
30#include "FindFunction.h"
31#include "ScopedSet.h"
32#include "ScrubTyVars.h"
33
34#include "Parser/ParseNode.h"
35
36#include "SynTree/Constant.h"
37#include "SynTree/Declaration.h"
38#include "SynTree/Expression.h"
39#include "SynTree/Initializer.h"
40#include "SynTree/Mutator.h"
41#include "SynTree/Statement.h"
42#include "SynTree/Type.h"
43#include "SynTree/TypeSubstitution.h"
44
45#include "ResolvExpr/TypeEnvironment.h"
46#include "ResolvExpr/TypeMap.h"
47#include "ResolvExpr/typeops.h"
48
49#include "SymTab/Indexer.h"
50#include "SymTab/Mangler.h"
51
52#include "Common/ScopedMap.h"
53#include "Common/SemanticError.h"
54#include "Common/UniqueName.h"
55#include "Common/utility.h"
56
57#include "InitTweak/InitTweak.h"
58
59#include <ext/functional> // temporary
60
61namespace GenPoly {
62        namespace {
63                const std::list<Label> noLabels;
64
65                FunctionType *makeAdapterType( FunctionType *adaptee, const TyVarMap &tyVars );
66
67                /// Adds layout-generation functions to polymorphic types
68                class LayoutFunctionBuilder final : public DeclMutator {
69                        unsigned int functionNesting;  // current level of nested functions
70                public:
71                        LayoutFunctionBuilder() : functionNesting( 0 ) {}
72
73                        using DeclMutator::mutate;
74                        virtual DeclarationWithType *mutate( FunctionDecl *functionDecl ) override;
75                        virtual Declaration *mutate( StructDecl *structDecl ) override;
76                        virtual Declaration *mutate( UnionDecl *unionDecl ) override;
77                };
78
79                /// Replaces polymorphic return types with out-parameters, replaces calls to polymorphic functions with adapter calls as needed, and adds appropriate type variables to the function call
80                class Pass1 final : public PolyMutator {
81                  public:
82                        Pass1();
83
84                        using PolyMutator::mutate;
85                        virtual Expression *mutate( ApplicationExpr *appExpr ) override;
86                        virtual Expression *mutate( AddressExpr *addrExpr ) override;
87                        virtual Expression *mutate( UntypedExpr *expr ) override;
88                        virtual DeclarationWithType* mutate( FunctionDecl *functionDecl ) override;
89                        virtual TypeDecl *mutate( TypeDecl *typeDecl ) override;
90                        virtual Expression *mutate( CommaExpr *commaExpr ) override;
91                        virtual Expression *mutate( ConditionalExpr *condExpr ) override;
92                        virtual Statement * mutate( ReturnStmt *returnStmt ) override;
93                        virtual Type *mutate( PointerType *pointerType ) override;
94                        virtual Type * mutate( FunctionType *functionType ) override;
95
96                        virtual void doBeginScope() override;
97                        virtual void doEndScope() override;
98                  private:
99                        /// Pass the extra type parameters from polymorphic generic arguments or return types into a function application
100                        void passArgTypeVars( ApplicationExpr *appExpr, Type *parmType, Type *argBaseType, std::list< Expression *>::iterator &arg, const TyVarMap &exprTyVars, std::set< std::string > &seenTypes );
101                        /// passes extra type parameters into a polymorphic function application
102                        void passTypeVars( ApplicationExpr *appExpr, Type *polyRetType, std::list< Expression *>::iterator &arg, const TyVarMap &exprTyVars );
103                        /// wraps a function application with a new temporary for the out-parameter return value
104                        Expression *addRetParam( ApplicationExpr *appExpr, FunctionType *function, Type *retType, std::list< Expression *>::iterator &arg );
105                        /// Replaces all the type parameters of a generic type with their concrete equivalents under the current environment
106                        void replaceParametersWithConcrete( ApplicationExpr *appExpr, std::list< Expression* >& params );
107                        /// Replaces a polymorphic type with its concrete equivalant under the current environment (returns itself if concrete).
108                        /// If `doClone` is set to false, will not clone interior types
109                        Type *replaceWithConcrete( ApplicationExpr *appExpr, Type *type, bool doClone = true );
110                        /// wraps a function application returning a polymorphic type with a new temporary for the out-parameter return value
111                        Expression *addDynRetParam( ApplicationExpr *appExpr, FunctionType *function, Type *polyType, std::list< Expression *>::iterator &arg );
112                        Expression *applyAdapter( ApplicationExpr *appExpr, FunctionType *function, std::list< Expression *>::iterator &arg, const TyVarMap &exprTyVars );
113                        void boxParam( Type *formal, Expression *&arg, const TyVarMap &exprTyVars );
114                        void boxParams( ApplicationExpr *appExpr, FunctionType *function, std::list< Expression *>::iterator &arg, const TyVarMap &exprTyVars );
115                        void addInferredParams( ApplicationExpr *appExpr, FunctionType *functionType, std::list< Expression *>::iterator &arg, const TyVarMap &tyVars );
116                        /// Stores assignment operators from assertion list in local map of assignment operations
117                        void passAdapters( ApplicationExpr *appExpr, FunctionType *functionType, const TyVarMap &exprTyVars );
118                        FunctionDecl *makeAdapter( FunctionType *adaptee, FunctionType *realType, const std::string &mangleName, const TyVarMap &tyVars );
119                        /// Replaces intrinsic operator functions with their arithmetic desugaring
120                        Expression *handleIntrinsics( ApplicationExpr *appExpr );
121                        /// Inserts a new temporary variable into the current scope with an auto-generated name
122                        ObjectDecl *makeTemporary( Type *type );
123
124                        ScopedMap< std::string, DeclarationWithType* > adapters;     ///< Set of adapter functions in the current scope
125
126                        std::map< ApplicationExpr *, Expression * > retVals;
127
128                        DeclarationWithType *retval;
129                        UniqueName tempNamer;
130                };
131
132                /// * Moves polymorphic returns in function types to pointer-type parameters
133                /// * adds type size and assertion parameters to parameter lists
134                class Pass2 final : public PolyMutator {
135                  public:
136                        template< typename DeclClass >
137                        DeclClass *handleDecl( DeclClass *decl, Type *type );
138                        template< typename AggDecl >
139                        AggDecl * handleAggDecl( AggDecl * aggDecl );
140
141                        typedef PolyMutator Parent;
142                        using Parent::mutate;
143                        virtual DeclarationWithType *mutate( FunctionDecl *functionDecl ) override;
144                        virtual ObjectDecl *mutate( ObjectDecl *objectDecl ) override;
145                        virtual StructDecl *mutate( StructDecl *structDecl ) override;
146                        virtual UnionDecl *mutate( UnionDecl *unionDecl ) override;
147                        virtual TypeDecl *mutate( TypeDecl *typeDecl ) override;
148                        virtual TypedefDecl *mutate( TypedefDecl *typedefDecl ) override;
149                        virtual Type *mutate( PointerType *pointerType ) override;
150                        virtual Type *mutate( FunctionType *funcType ) override;
151
152                  private:
153                        void addAdapters( FunctionType *functionType );
154
155                        std::map< UniqueId, std::string > adapterName;
156                };
157
158                /// Replaces member and size/align/offsetof expressions on polymorphic generic types with calculated expressions.
159                /// * Replaces member expressions for polymorphic types with calculated add-field-offset-and-dereference
160                /// * Calculates polymorphic offsetof expressions from offset array
161                /// * Inserts dynamic calculation of polymorphic type layouts where needed
162                class PolyGenericCalculator final : public PolyMutator {
163                public:
164                        typedef PolyMutator Parent;
165                        using Parent::mutate;
166
167                        template< typename DeclClass >
168                        DeclClass *handleDecl( DeclClass *decl, Type *type );
169                        virtual DeclarationWithType *mutate( FunctionDecl *functionDecl ) override;
170                        virtual ObjectDecl *mutate( ObjectDecl *objectDecl ) override;
171                        virtual TypedefDecl *mutate( TypedefDecl *objectDecl ) override;
172                        virtual TypeDecl *mutate( TypeDecl *objectDecl ) override;
173                        virtual Statement *mutate( DeclStmt *declStmt ) override;
174                        virtual Type *mutate( PointerType *pointerType ) override;
175                        virtual Type *mutate( FunctionType *funcType ) override;
176                        virtual Expression *mutate( MemberExpr *memberExpr ) override;
177                        virtual Expression *mutate( SizeofExpr *sizeofExpr ) override;
178                        virtual Expression *mutate( AlignofExpr *alignofExpr ) override;
179                        virtual Expression *mutate( OffsetofExpr *offsetofExpr ) override;
180                        virtual Expression *mutate( OffsetPackExpr *offsetPackExpr ) override;
181
182                        virtual void doBeginScope() override;
183                        virtual void doEndScope() override;
184
185                private:
186                        /// Makes a new variable in the current scope with the given name, type & optional initializer
187                        ObjectDecl *makeVar( const std::string &name, Type *type, Initializer *init = 0 );
188                        /// returns true if the type has a dynamic layout; such a layout will be stored in appropriately-named local variables when the function returns
189                        bool findGeneric( Type *ty );
190                        /// adds type parameters to the layout call; will generate the appropriate parameters if needed
191                        void addOtypeParamsToLayoutCall( UntypedExpr *layoutCall, const std::list< Type* > &otypeParams );
192
193                        /// Enters a new scope for type-variables, adding the type variables from ty
194                        void beginTypeScope( Type *ty );
195                        /// Exits the type-variable scope
196                        void endTypeScope();
197
198                        ScopedSet< std::string > knownLayouts;          ///< Set of generic type layouts known in the current scope, indexed by sizeofName
199                        ScopedSet< std::string > knownOffsets;          ///< Set of non-generic types for which the offset array exists in the current scope, indexed by offsetofName
200                };
201
202                /// Replaces initialization of polymorphic values with alloca, declaration of dtype/ftype with appropriate void expression, and sizeof expressions of polymorphic types with the proper variable
203                class Pass3 final : public PolyMutator {
204                  public:
205                        template< typename DeclClass >
206                        DeclClass *handleDecl( DeclClass *decl, Type *type );
207
208                        using PolyMutator::mutate;
209                        virtual DeclarationWithType *mutate( FunctionDecl *functionDecl ) override;
210                        virtual ObjectDecl *mutate( ObjectDecl *objectDecl ) override;
211                        virtual TypedefDecl *mutate( TypedefDecl *objectDecl ) override;
212                        virtual TypeDecl *mutate( TypeDecl *objectDecl ) override;
213                        virtual Type *mutate( PointerType *pointerType ) override;
214                        virtual Type *mutate( FunctionType *funcType ) override;
215                  private:
216                };
217
218        } // anonymous namespace
219
220        /// version of mutateAll with special handling for translation unit so you can check the end of the prelude when debugging
221        template< typename MutatorType >
222        inline void mutateTranslationUnit( std::list< Declaration* > &translationUnit, MutatorType &mutator ) {
223                bool seenIntrinsic = false;
224                SemanticError errors;
225                for ( typename std::list< Declaration* >::iterator i = translationUnit.begin(); i != translationUnit.end(); ++i ) {
226                        try {
227                                if ( *i ) {
228                                        if ( (*i)->get_linkage() == LinkageSpec::Intrinsic ) {
229                                                seenIntrinsic = true;
230                                        } else if ( seenIntrinsic ) {
231                                                seenIntrinsic = false; // break on this line when debugging for end of prelude
232                                        }
233
234                                        *i = dynamic_cast< Declaration* >( (*i)->acceptMutator( mutator ) );
235                                        assert( *i );
236                                } // if
237                        } catch( SemanticError &e ) {
238                                e.set_location( (*i)->location );
239                                errors.append( e );
240                        } // try
241                } // for
242                if ( ! errors.isEmpty() ) {
243                        throw errors;
244                } // if
245        }
246
247        void box( std::list< Declaration *>& translationUnit ) {
248                LayoutFunctionBuilder layoutBuilder;
249                Pass1 pass1;
250                Pass2 pass2;
251                PolyGenericCalculator polyCalculator;
252                Pass3 pass3;
253
254                layoutBuilder.mutateDeclarationList( translationUnit );
255                mutateTranslationUnit/*All*/( translationUnit, pass1 );
256                mutateTranslationUnit/*All*/( translationUnit, pass2 );
257                mutateTranslationUnit/*All*/( translationUnit, polyCalculator );
258                mutateTranslationUnit/*All*/( translationUnit, pass3 );
259        }
260
261        ////////////////////////////////// LayoutFunctionBuilder ////////////////////////////////////////////
262
263        DeclarationWithType *LayoutFunctionBuilder::mutate( FunctionDecl *functionDecl ) {
264                functionDecl->set_functionType( maybeMutate( functionDecl->get_functionType(), *this ) );
265                ++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                        // errors should have been caught by this point, remove initializers from parameters to allow correct codegen of default arguments
1310                        for ( Declaration * param : functionDecl->get_functionType()->get_parameters() ) {
1311                                if ( ObjectDecl * obj = dynamic_cast< ObjectDecl * >( param ) ) {
1312                                        delete obj->get_init();
1313                                        obj->set_init( nullptr );
1314                                }
1315                        }
1316                        return functionDecl;
1317                }
1318
1319                ObjectDecl * Pass2::mutate( ObjectDecl *objectDecl ) {
1320                        return handleDecl( objectDecl, objectDecl->get_type() );
1321                }
1322
1323                template< typename AggDecl >
1324                AggDecl * Pass2::handleAggDecl( AggDecl * aggDecl ) {
1325                        // prevent tyVars from leaking into containing scope
1326                        scopeTyVars.beginScope();
1327                        Parent::mutate( aggDecl );
1328                        scopeTyVars.endScope();
1329                        return aggDecl;
1330                }
1331
1332                StructDecl * Pass2::mutate( StructDecl *aggDecl ) {
1333                        return handleAggDecl( aggDecl );
1334                }
1335
1336                UnionDecl * Pass2::mutate( UnionDecl *aggDecl ) {
1337                        return handleAggDecl( aggDecl );
1338                }
1339
1340                TypeDecl * Pass2::mutate( TypeDecl *typeDecl ) {
1341                        addToTyVarMap( typeDecl, scopeTyVars );
1342                        if ( typeDecl->get_base() ) {
1343                                return handleDecl( typeDecl, typeDecl->get_base() );
1344                        } else {
1345                                return Parent::mutate( typeDecl );
1346                        }
1347                }
1348
1349                TypedefDecl * Pass2::mutate( TypedefDecl *typedefDecl ) {
1350                        return handleDecl( typedefDecl, typedefDecl->get_base() );
1351                }
1352
1353                Type * Pass2::mutate( PointerType *pointerType ) {
1354                        scopeTyVars.beginScope();
1355                        makeTyVarMap( pointerType, scopeTyVars );
1356
1357                        Type *ret = Parent::mutate( pointerType );
1358
1359                        scopeTyVars.endScope();
1360                        return ret;
1361                }
1362
1363                Type *Pass2::mutate( FunctionType *funcType ) {
1364                        scopeTyVars.beginScope();
1365                        makeTyVarMap( funcType, scopeTyVars );
1366
1367                        // move polymorphic return type to parameter list
1368                        if ( isDynRet( funcType ) ) {
1369                                ObjectDecl *ret = safe_dynamic_cast< ObjectDecl* >( funcType->get_returnVals().front() );
1370                                ret->set_type( new PointerType( Type::Qualifiers(), ret->get_type() ) );
1371                                funcType->get_parameters().push_front( ret );
1372                                funcType->get_returnVals().pop_front();
1373                                ret->set_init( nullptr ); // xxx - memory leak?
1374                        }
1375
1376                        // add size/align and assertions for type parameters to parameter list
1377                        std::list< DeclarationWithType *>::iterator last = funcType->get_parameters().begin();
1378                        std::list< DeclarationWithType *> inferredParams;
1379                        ObjectDecl newObj( "", DeclarationNode::NoStorageClass, LinkageSpec::C, 0, new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt ), 0 );
1380                        ObjectDecl newPtr( "", DeclarationNode::NoStorageClass, LinkageSpec::C, 0,
1381                                           new PointerType( Type::Qualifiers(), new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt ) ), 0 );
1382                        for ( Type::ForallList::const_iterator tyParm = funcType->get_forall().begin(); tyParm != funcType->get_forall().end(); ++tyParm ) {
1383                                ObjectDecl *sizeParm, *alignParm;
1384                                // add all size and alignment parameters to parameter list
1385                                if ( (*tyParm)->isComplete() ) {
1386                                        TypeInstType parmType( Type::Qualifiers(), (*tyParm)->get_name(), *tyParm );
1387                                        std::string parmName = mangleType( &parmType );
1388
1389                                        sizeParm = newObj.clone();
1390                                        sizeParm->set_name( sizeofName( parmName ) );
1391                                        last = funcType->get_parameters().insert( last, sizeParm );
1392                                        ++last;
1393
1394                                        alignParm = newObj.clone();
1395                                        alignParm->set_name( alignofName( parmName ) );
1396                                        last = funcType->get_parameters().insert( last, alignParm );
1397                                        ++last;
1398                                }
1399                                // move all assertions into parameter list
1400                                for ( std::list< DeclarationWithType *>::iterator assert = (*tyParm)->get_assertions().begin(); assert != (*tyParm)->get_assertions().end(); ++assert ) {
1401//      *assert = (*assert)->acceptMutator( *this );
1402                                        inferredParams.push_back( *assert );
1403                                }
1404                                (*tyParm)->get_assertions().clear();
1405                        }
1406
1407                        // add size/align for generic parameter types to parameter list
1408                        std::set< std::string > seenTypes; // sizeofName for generic types we've seen
1409                        for ( std::list< DeclarationWithType* >::const_iterator fnParm = last; fnParm != funcType->get_parameters().end(); ++fnParm ) {
1410                                Type *polyType = isPolyType( (*fnParm)->get_type(), scopeTyVars );
1411                                if ( polyType && ! dynamic_cast< TypeInstType* >( polyType ) ) {
1412                                        std::string typeName = mangleType( polyType );
1413                                        if ( seenTypes.count( typeName ) ) continue;
1414
1415                                        ObjectDecl *sizeParm, *alignParm, *offsetParm;
1416                                        sizeParm = newObj.clone();
1417                                        sizeParm->set_name( sizeofName( typeName ) );
1418                                        last = funcType->get_parameters().insert( last, sizeParm );
1419                                        ++last;
1420
1421                                        alignParm = newObj.clone();
1422                                        alignParm->set_name( alignofName( typeName ) );
1423                                        last = funcType->get_parameters().insert( last, alignParm );
1424                                        ++last;
1425
1426                                        if ( StructInstType *polyBaseStruct = dynamic_cast< StructInstType* >( polyType ) ) {
1427                                                // NOTE zero-length arrays are illegal in C, so empty structs have no offset array
1428                                                if ( ! polyBaseStruct->get_baseStruct()->get_members().empty() ) {
1429                                                        offsetParm = newPtr.clone();
1430                                                        offsetParm->set_name( offsetofName( typeName ) );
1431                                                        last = funcType->get_parameters().insert( last, offsetParm );
1432                                                        ++last;
1433                                                }
1434                                        }
1435
1436                                        seenTypes.insert( typeName );
1437                                }
1438                        }
1439
1440                        // splice assertion parameters into parameter list
1441                        funcType->get_parameters().splice( last, inferredParams );
1442                        addAdapters( funcType );
1443                        mutateAll( funcType->get_returnVals(), *this );
1444                        mutateAll( funcType->get_parameters(), *this );
1445
1446                        scopeTyVars.endScope();
1447                        return funcType;
1448                }
1449
1450////////////////////////////////////////// PolyGenericCalculator ////////////////////////////////////////////////////
1451
1452                void PolyGenericCalculator::beginTypeScope( Type *ty ) {
1453                        scopeTyVars.beginScope();
1454                        makeTyVarMap( ty, scopeTyVars );
1455                }
1456
1457                void PolyGenericCalculator::endTypeScope() {
1458                        scopeTyVars.endScope();
1459                }
1460
1461                template< typename DeclClass >
1462                DeclClass * PolyGenericCalculator::handleDecl( DeclClass *decl, Type *type ) {
1463                        beginTypeScope( type );
1464                        // knownLayouts.beginScope();
1465                        // knownOffsets.beginScope();
1466
1467                        DeclClass *ret = static_cast< DeclClass *>( Parent::mutate( decl ) );
1468
1469                        // knownOffsets.endScope();
1470                        // knownLayouts.endScope();
1471                        endTypeScope();
1472                        return ret;
1473                }
1474
1475                ObjectDecl * PolyGenericCalculator::mutate( ObjectDecl *objectDecl ) {
1476                        return handleDecl( objectDecl, objectDecl->get_type() );
1477                }
1478
1479                DeclarationWithType * PolyGenericCalculator::mutate( FunctionDecl *functionDecl ) {
1480                        knownLayouts.beginScope();
1481                        knownOffsets.beginScope();
1482
1483                        DeclarationWithType * decl = handleDecl( functionDecl, functionDecl->get_functionType() );
1484                        knownOffsets.endScope();
1485                        knownLayouts.endScope();
1486                        return decl;
1487                }
1488
1489                TypedefDecl * PolyGenericCalculator::mutate( TypedefDecl *typedefDecl ) {
1490                        return handleDecl( typedefDecl, typedefDecl->get_base() );
1491                }
1492
1493                TypeDecl * PolyGenericCalculator::mutate( TypeDecl *typeDecl ) {
1494                        addToTyVarMap( typeDecl, scopeTyVars );
1495                        return Parent::mutate( typeDecl );
1496                }
1497
1498                Type * PolyGenericCalculator::mutate( PointerType *pointerType ) {
1499                        beginTypeScope( pointerType );
1500
1501                        Type *ret = Parent::mutate( pointerType );
1502
1503                        endTypeScope();
1504                        return ret;
1505                }
1506
1507                Type * PolyGenericCalculator::mutate( FunctionType *funcType ) {
1508                        beginTypeScope( funcType );
1509
1510                        // make sure that any type information passed into the function is accounted for
1511                        for ( std::list< DeclarationWithType* >::const_iterator fnParm = funcType->get_parameters().begin(); fnParm != funcType->get_parameters().end(); ++fnParm ) {
1512                                // condition here duplicates that in Pass2::mutate( FunctionType* )
1513                                Type *polyType = isPolyType( (*fnParm)->get_type(), scopeTyVars );
1514                                if ( polyType && ! dynamic_cast< TypeInstType* >( polyType ) ) {
1515                                        knownLayouts.insert( mangleType( polyType ) );
1516                                }
1517                        }
1518
1519                        Type *ret = Parent::mutate( funcType );
1520
1521                        endTypeScope();
1522                        return ret;
1523                }
1524
1525                Statement *PolyGenericCalculator::mutate( DeclStmt *declStmt ) {
1526                        if ( ObjectDecl *objectDecl = dynamic_cast< ObjectDecl *>( declStmt->get_decl() ) ) {
1527                                if ( findGeneric( objectDecl->get_type() ) ) {
1528                                        // change initialization of a polymorphic value object
1529                                        // to allocate storage with alloca
1530                                        Type *declType = objectDecl->get_type();
1531                                        UntypedExpr *alloc = new UntypedExpr( new NameExpr( "__builtin_alloca" ) );
1532                                        alloc->get_args().push_back( new NameExpr( sizeofName( mangleType( declType ) ) ) );
1533
1534                                        delete objectDecl->get_init();
1535
1536                                        std::list<Expression*> designators;
1537                                        objectDecl->set_init( new SingleInit( alloc, designators, false ) ); // not constructed
1538                                }
1539                        }
1540                        return Parent::mutate( declStmt );
1541                }
1542
1543                /// Finds the member in the base list that matches the given declaration; returns its index, or -1 if not present
1544                long findMember( DeclarationWithType *memberDecl, std::list< Declaration* > &baseDecls ) {
1545                        long i = 0;
1546                        for(std::list< Declaration* >::const_iterator decl = baseDecls.begin(); decl != baseDecls.end(); ++decl, ++i ) {
1547                                if ( memberDecl->get_name() != (*decl)->get_name() ) continue;
1548
1549                                if ( DeclarationWithType *declWithType = dynamic_cast< DeclarationWithType* >( *decl ) ) {
1550                                        if ( memberDecl->get_mangleName().empty() || declWithType->get_mangleName().empty()
1551                                             || memberDecl->get_mangleName() == declWithType->get_mangleName() ) return i;
1552                                        else continue;
1553                                } else return i;
1554                        }
1555                        return -1;
1556                }
1557
1558                /// Returns an index expression into the offset array for a type
1559                Expression *makeOffsetIndex( Type *objectType, long i ) {
1560                        std::stringstream offset_namer;
1561                        offset_namer << i;
1562                        ConstantExpr *fieldIndex = new ConstantExpr( Constant( new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt ), offset_namer.str() ) );
1563                        UntypedExpr *fieldOffset = new UntypedExpr( new NameExpr( "?[?]" ) );
1564                        fieldOffset->get_args().push_back( new NameExpr( offsetofName( mangleType( objectType ) ) ) );
1565                        fieldOffset->get_args().push_back( fieldIndex );
1566                        return fieldOffset;
1567                }
1568
1569                /// Returns an expression dereferenced n times
1570                Expression *makeDerefdVar( Expression *derefdVar, long n ) {
1571                        for ( int i = 1; i < n; ++i ) {
1572                                UntypedExpr *derefExpr = new UntypedExpr( new NameExpr( "*?" ) );
1573                                derefExpr->get_args().push_back( derefdVar );
1574                                // xxx - should set results on derefExpr
1575                                derefdVar = derefExpr;
1576                        }
1577                        return derefdVar;
1578                }
1579
1580                Expression *PolyGenericCalculator::mutate( MemberExpr *memberExpr ) {
1581                        // mutate, exiting early if no longer MemberExpr
1582                        Expression *expr = Parent::mutate( memberExpr );
1583                        memberExpr = dynamic_cast< MemberExpr* >( expr );
1584                        if ( ! memberExpr ) return expr;
1585
1586                        // get declaration for base struct, exiting early if not found
1587                        int varDepth;
1588                        VariableExpr *varExpr = getBaseVar( memberExpr->get_aggregate(), &varDepth );
1589                        if ( ! varExpr ) return memberExpr;
1590                        ObjectDecl *objectDecl = dynamic_cast< ObjectDecl* >( varExpr->get_var() );
1591                        if ( ! objectDecl ) return memberExpr;
1592
1593                        // only mutate member expressions for polymorphic types
1594                        int tyDepth;
1595                        Type *objectType = hasPolyBase( objectDecl->get_type(), scopeTyVars, &tyDepth );
1596                        if ( ! objectType ) return memberExpr;
1597                        findGeneric( objectType ); // ensure layout for this type is available
1598
1599                        // replace member expression with dynamically-computed layout expression
1600                        Expression *newMemberExpr = 0;
1601                        if ( StructInstType *structType = dynamic_cast< StructInstType* >( objectType ) ) {
1602                                // look up offset index
1603                                long i = findMember( memberExpr->get_member(), structType->get_baseStruct()->get_members() );
1604                                if ( i == -1 ) return memberExpr;
1605
1606                                // replace member expression with pointer to base plus offset
1607                                UntypedExpr *fieldLoc = new UntypedExpr( new NameExpr( "?+?" ) );
1608                                Expression * aggr = memberExpr->get_aggregate()->clone();
1609                                delete aggr->get_env(); // xxx - there's a problem with keeping the env for some reason, so for now just get rid of it
1610                                aggr->set_env( nullptr );
1611                                fieldLoc->get_args().push_back( aggr );
1612                                fieldLoc->get_args().push_back( makeOffsetIndex( objectType, i ) );
1613                                newMemberExpr = fieldLoc;
1614                        } else if ( dynamic_cast< UnionInstType* >( objectType ) ) {
1615                                // union members are all at offset zero, so build appropriately-dereferenced variable
1616                                newMemberExpr = makeDerefdVar( varExpr->clone(), varDepth );
1617                        } else return memberExpr;
1618                        assert( newMemberExpr );
1619
1620                        Type *memberType = memberExpr->get_member()->get_type();
1621                        if ( ! isPolyType( memberType, scopeTyVars ) ) {
1622                                // 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
1623                                CastExpr *ptrCastExpr = new CastExpr( newMemberExpr, new PointerType( Type::Qualifiers(), memberType->clone() ) );
1624                                UntypedExpr *derefExpr = new UntypedExpr( new NameExpr( "*?" ) );
1625                                derefExpr->get_args().push_back( ptrCastExpr );
1626                                newMemberExpr = derefExpr;
1627                        }
1628
1629                        delete memberExpr;
1630                        return newMemberExpr;
1631                }
1632
1633                ObjectDecl *PolyGenericCalculator::makeVar( const std::string &name, Type *type, Initializer *init ) {
1634                        ObjectDecl *newObj = new ObjectDecl( name, DeclarationNode::NoStorageClass, LinkageSpec::C, 0, type, init );
1635                        stmtsToAdd.push_back( new DeclStmt( noLabels, newObj ) );
1636                        return newObj;
1637                }
1638
1639                void PolyGenericCalculator::addOtypeParamsToLayoutCall( UntypedExpr *layoutCall, const std::list< Type* > &otypeParams ) {
1640                        for ( std::list< Type* >::const_iterator param = otypeParams.begin(); param != otypeParams.end(); ++param ) {
1641                                if ( findGeneric( *param ) ) {
1642                                        // push size/align vars for a generic parameter back
1643                                        std::string paramName = mangleType( *param );
1644                                        layoutCall->get_args().push_back( new NameExpr( sizeofName( paramName ) ) );
1645                                        layoutCall->get_args().push_back( new NameExpr( alignofName( paramName ) ) );
1646                                } else {
1647                                        layoutCall->get_args().push_back( new SizeofExpr( (*param)->clone() ) );
1648                                        layoutCall->get_args().push_back( new AlignofExpr( (*param)->clone() ) );
1649                                }
1650                        }
1651                }
1652
1653                /// returns true if any of the otype parameters have a dynamic layout and puts all otype parameters in the output list
1654                bool findGenericParams( std::list< TypeDecl* > &baseParams, std::list< Expression* > &typeParams, std::list< Type* > &out ) {
1655                        bool hasDynamicLayout = false;
1656
1657                        std::list< TypeDecl* >::const_iterator baseParam = baseParams.begin();
1658                        std::list< Expression* >::const_iterator typeParam = typeParams.begin();
1659                        for ( ; baseParam != baseParams.end() && typeParam != typeParams.end(); ++baseParam, ++typeParam ) {
1660                                // skip non-otype parameters
1661                                if ( ! (*baseParam)->isComplete() ) continue;
1662                                TypeExpr *typeExpr = dynamic_cast< TypeExpr* >( *typeParam );
1663                                assert( typeExpr && "all otype parameters should be type expressions" );
1664
1665                                Type *type = typeExpr->get_type();
1666                                out.push_back( type );
1667                                if ( isPolyType( type ) ) hasDynamicLayout = true;
1668                        }
1669                        assert( baseParam == baseParams.end() && typeParam == typeParams.end() );
1670
1671                        return hasDynamicLayout;
1672                }
1673
1674                bool PolyGenericCalculator::findGeneric( Type *ty ) {
1675                        ty = replaceTypeInst( ty, env );
1676
1677                        if ( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( ty ) ) {
1678                                if ( scopeTyVars.find( typeInst->get_name() ) != scopeTyVars.end() ) {
1679                                        // NOTE assumes here that getting put in the scopeTyVars included having the layout variables set
1680                                        return true;
1681                                }
1682                                return false;
1683                        } else if ( StructInstType *structTy = dynamic_cast< StructInstType* >( ty ) ) {
1684                                // check if this type already has a layout generated for it
1685                                std::string typeName = mangleType( ty );
1686                                if ( knownLayouts.find( typeName ) != knownLayouts.end() ) return true;
1687
1688                                // check if any of the type parameters have dynamic layout; if none do, this type is (or will be) monomorphized
1689                                std::list< Type* > otypeParams;
1690                                if ( ! findGenericParams( *structTy->get_baseParameters(), structTy->get_parameters(), otypeParams ) ) return false;
1691
1692                                // insert local variables for layout and generate call to layout function
1693                                knownLayouts.insert( typeName );  // done early so as not to interfere with the later addition of parameters to the layout call
1694                                Type *layoutType = new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt );
1695
1696                                int n_members = structTy->get_baseStruct()->get_members().size();
1697                                if ( n_members == 0 ) {
1698                                        // all empty structs have the same layout - size 1, align 1
1699                                        makeVar( sizeofName( typeName ), layoutType, new SingleInit( new ConstantExpr( Constant::from_ulong( (unsigned long)1 ) ) ) );
1700                                        makeVar( alignofName( typeName ), layoutType->clone(), new SingleInit( new ConstantExpr( Constant::from_ulong( (unsigned long)1 ) ) ) );
1701                                        // NOTE zero-length arrays are forbidden in C, so empty structs have no offsetof array
1702                                } else {
1703                                        ObjectDecl *sizeVar = makeVar( sizeofName( typeName ), layoutType );
1704                                        ObjectDecl *alignVar = makeVar( alignofName( typeName ), layoutType->clone() );
1705                                        ObjectDecl *offsetVar = makeVar( offsetofName( typeName ), new ArrayType( Type::Qualifiers(), layoutType->clone(), new ConstantExpr( Constant::from_int( n_members ) ), false, false ) );
1706
1707                                        // generate call to layout function
1708                                        UntypedExpr *layoutCall = new UntypedExpr( new NameExpr( layoutofName( structTy->get_baseStruct() ) ) );
1709                                        layoutCall->get_args().push_back( new AddressExpr( new VariableExpr( sizeVar ) ) );
1710                                        layoutCall->get_args().push_back( new AddressExpr( new VariableExpr( alignVar ) ) );
1711                                        layoutCall->get_args().push_back( new VariableExpr( offsetVar ) );
1712                                        addOtypeParamsToLayoutCall( layoutCall, otypeParams );
1713
1714                                        stmtsToAdd.push_back( new ExprStmt( noLabels, layoutCall ) );
1715                                }
1716
1717                                return true;
1718                        } else if ( UnionInstType *unionTy = dynamic_cast< UnionInstType* >( ty ) ) {
1719                                // check if this type already has a layout generated for it
1720                                std::string typeName = mangleType( ty );
1721                                if ( knownLayouts.find( typeName ) != knownLayouts.end() ) return true;
1722
1723                                // check if any of the type parameters have dynamic layout; if none do, this type is (or will be) monomorphized
1724                                std::list< Type* > otypeParams;
1725                                if ( ! findGenericParams( *unionTy->get_baseParameters(), unionTy->get_parameters(), otypeParams ) ) return false;
1726
1727                                // insert local variables for layout and generate call to layout function
1728                                knownLayouts.insert( typeName );  // done early so as not to interfere with the later addition of parameters to the layout call
1729                                Type *layoutType = new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt );
1730
1731                                ObjectDecl *sizeVar = makeVar( sizeofName( typeName ), layoutType );
1732                                ObjectDecl *alignVar = makeVar( alignofName( typeName ), layoutType->clone() );
1733
1734                                // generate call to layout function
1735                                UntypedExpr *layoutCall = new UntypedExpr( new NameExpr( layoutofName( unionTy->get_baseUnion() ) ) );
1736                                layoutCall->get_args().push_back( new AddressExpr( new VariableExpr( sizeVar ) ) );
1737                                layoutCall->get_args().push_back( new AddressExpr( new VariableExpr( alignVar ) ) );
1738                                addOtypeParamsToLayoutCall( layoutCall, otypeParams );
1739
1740                                stmtsToAdd.push_back( new ExprStmt( noLabels, layoutCall ) );
1741
1742                                return true;
1743                        }
1744
1745                        return false;
1746                }
1747
1748                Expression *PolyGenericCalculator::mutate( SizeofExpr *sizeofExpr ) {
1749                        Type *ty = sizeofExpr->get_type();
1750                        if ( findGeneric( ty ) ) {
1751                                Expression *ret = new NameExpr( sizeofName( mangleType( ty ) ) );
1752                                delete sizeofExpr;
1753                                return ret;
1754                        }
1755                        return sizeofExpr;
1756                }
1757
1758                Expression *PolyGenericCalculator::mutate( AlignofExpr *alignofExpr ) {
1759                        Type *ty = alignofExpr->get_type();
1760                        if ( findGeneric( ty ) ) {
1761                                Expression *ret = new NameExpr( alignofName( mangleType( ty ) ) );
1762                                delete alignofExpr;
1763                                return ret;
1764                        }
1765                        return alignofExpr;
1766                }
1767
1768                Expression *PolyGenericCalculator::mutate( OffsetofExpr *offsetofExpr ) {
1769                        // mutate, exiting early if no longer OffsetofExpr
1770                        Expression *expr = Parent::mutate( offsetofExpr );
1771                        offsetofExpr = dynamic_cast< OffsetofExpr* >( expr );
1772                        if ( ! offsetofExpr ) return expr;
1773
1774                        // only mutate expressions for polymorphic structs/unions
1775                        Type *ty = offsetofExpr->get_type();
1776                        if ( ! findGeneric( ty ) ) return offsetofExpr;
1777
1778                        if ( StructInstType *structType = dynamic_cast< StructInstType* >( ty ) ) {
1779                                // replace offsetof expression by index into offset array
1780                                long i = findMember( offsetofExpr->get_member(), structType->get_baseStruct()->get_members() );
1781                                if ( i == -1 ) return offsetofExpr;
1782
1783                                Expression *offsetInd = makeOffsetIndex( ty, i );
1784                                delete offsetofExpr;
1785                                return offsetInd;
1786                        } else if ( dynamic_cast< UnionInstType* >( ty ) ) {
1787                                // all union members are at offset zero
1788                                delete offsetofExpr;
1789                                return new ConstantExpr( Constant( new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt ), "0" ) );
1790                        } else return offsetofExpr;
1791                }
1792
1793                Expression *PolyGenericCalculator::mutate( OffsetPackExpr *offsetPackExpr ) {
1794                        StructInstType *ty = offsetPackExpr->get_type();
1795
1796                        Expression *ret = 0;
1797                        if ( findGeneric( ty ) ) {
1798                                // pull offset back from generated type information
1799                                ret = new NameExpr( offsetofName( mangleType( ty ) ) );
1800                        } else {
1801                                std::string offsetName = offsetofName( mangleType( ty ) );
1802                                if ( knownOffsets.find( offsetName ) != knownOffsets.end() ) {
1803                                        // use the already-generated offsets for this type
1804                                        ret = new NameExpr( offsetName );
1805                                } else {
1806                                        knownOffsets.insert( offsetName );
1807
1808                                        std::list< Declaration* > &baseMembers = ty->get_baseStruct()->get_members();
1809                                        Type *offsetType = new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt );
1810
1811                                        // build initializer list for offset array
1812                                        std::list< Initializer* > inits;
1813                                        for ( std::list< Declaration* >::const_iterator member = baseMembers.begin(); member != baseMembers.end(); ++member ) {
1814                                                DeclarationWithType *memberDecl;
1815                                                if ( DeclarationWithType *origMember = dynamic_cast< DeclarationWithType* >( *member ) ) {
1816                                                        memberDecl = origMember->clone();
1817                                                } else {
1818                                                        memberDecl = new ObjectDecl( (*member)->get_name(), DeclarationNode::NoStorageClass, LinkageSpec::Cforall, 0, offsetType->clone(), 0 );
1819                                                }
1820                                                inits.push_back( new SingleInit( new OffsetofExpr( ty->clone(), memberDecl ) ) );
1821                                        }
1822
1823                                        // build the offset array and replace the pack with a reference to it
1824                                        ObjectDecl *offsetArray = makeVar( offsetName, new ArrayType( Type::Qualifiers(), offsetType, new ConstantExpr( Constant::from_ulong( baseMembers.size() ) ), false, false ),
1825                                                        new ListInit( inits ) );
1826                                        ret = new VariableExpr( offsetArray );
1827                                }
1828                        }
1829
1830                        delete offsetPackExpr;
1831                        return ret;
1832                }
1833
1834                void PolyGenericCalculator::doBeginScope() {
1835                        knownLayouts.beginScope();
1836                        knownOffsets.beginScope();
1837                }
1838
1839                void PolyGenericCalculator::doEndScope() {
1840                        knownLayouts.endScope();
1841                        knownOffsets.endScope();
1842                }
1843
1844////////////////////////////////////////// Pass3 ////////////////////////////////////////////////////
1845
1846                template< typename DeclClass >
1847                DeclClass * Pass3::handleDecl( DeclClass *decl, Type *type ) {
1848                        scopeTyVars.beginScope();
1849                        makeTyVarMap( type, scopeTyVars );
1850
1851                        DeclClass *ret = static_cast< DeclClass *>( Mutator::mutate( decl ) );
1852                        ScrubTyVars::scrub( decl, scopeTyVars );
1853
1854                        scopeTyVars.endScope();
1855                        return ret;
1856                }
1857
1858                ObjectDecl * Pass3::mutate( ObjectDecl *objectDecl ) {
1859                        return handleDecl( objectDecl, objectDecl->get_type() );
1860                }
1861
1862                DeclarationWithType * Pass3::mutate( FunctionDecl *functionDecl ) {
1863                        return handleDecl( functionDecl, functionDecl->get_functionType() );
1864                }
1865
1866                TypedefDecl * Pass3::mutate( TypedefDecl *typedefDecl ) {
1867                        return handleDecl( typedefDecl, typedefDecl->get_base() );
1868                }
1869
1870                TypeDecl * Pass3::mutate( TypeDecl *typeDecl ) {
1871//   Initializer *init = 0;
1872//   std::list< Expression *> designators;
1873//   addToTyVarMap( typeDecl, scopeTyVars );
1874//   if ( typeDecl->get_base() ) {
1875//     init = new SimpleInit( new SizeofExpr( handleDecl( typeDecl, typeDecl->get_base() ) ), designators );
1876//   }
1877//   return new ObjectDecl( typeDecl->get_name(), Declaration::Extern, LinkageSpec::C, 0, new BasicType( Type::Qualifiers(), BasicType::UnsignedInt ), init );
1878
1879                        addToTyVarMap( typeDecl, scopeTyVars );
1880                        return Mutator::mutate( typeDecl );
1881                }
1882
1883                Type * Pass3::mutate( PointerType *pointerType ) {
1884                        scopeTyVars.beginScope();
1885                        makeTyVarMap( pointerType, scopeTyVars );
1886
1887                        Type *ret = Mutator::mutate( pointerType );
1888
1889                        scopeTyVars.endScope();
1890                        return ret;
1891                }
1892
1893                Type * Pass3::mutate( FunctionType *functionType ) {
1894                        scopeTyVars.beginScope();
1895                        makeTyVarMap( functionType, scopeTyVars );
1896
1897                        Type *ret = Mutator::mutate( functionType );
1898
1899                        scopeTyVars.endScope();
1900                        return ret;
1901                }
1902        } // anonymous namespace
1903} // namespace GenPoly
1904
1905// Local Variables: //
1906// tab-width: 4 //
1907// mode: c++ //
1908// compile-command: "make install" //
1909// End: //
Note: See TracBrowser for help on using the repository browser.