Context Navigation

source: src/GenPoly/Box.cc @ 3205495

new-envwith_gc

Last change on this file since 3205495 was 9f2012f, checked in by Aaron Moss <a3moss@…>, 7 years ago
Find more stack-alloc'd nodes
Property mode set to `100644`
File size: 87.4 KB

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

Note: See TracBrowser for help on using the repository browser.

Download in other formats: