Context Navigation

source: src/GenPoly/Box.cc @ 2ae171d8

ADTaaron-thesisarm-ehast-experimentalcleanup-dtorsdeferred_resndemanglerenumforall-pointer-decayjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprnew-envno_listpersistent-indexerpthread-emulationqualifiedEnumresolv-newwith_gc

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

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

Download in other formats: