source: src/GenPoly/Box.cc @ 982832e

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

Merge branch 'master' of plg.uwaterloo.ca:software/cfa/cfa-cc

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