source: src/GenPoly/Box.cc @ 08fc48f

aaron-thesisarm-ehcleanup-dtorsdeferred_resndemanglerjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprnew-envno_listpersistent-indexerresolv-newwith_gc
Last change on this file since 08fc48f was 08fc48f, checked in by Thierry Delisle <tdelisle@…>, 4 years ago

Big header cleaning pass - commit 1

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