Context Navigation

source: src/GenPoly/Box.cc @ cccc534

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 cccc534 was cccc534, checked in by Rob Schluntz <rschlunt@…>, 7 years ago
Minor cleanup in Box and GenPoly?
Property mode set to `100644`
File size: 89.3 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 ( isDynType( adaptee->get_returnVals().front()->get_type(), tyVars ) ) {
[cc3528f]	899	// return type T
[01aeade]	900	if ( (*param)->get_name() == "" ) {
	901	(*param)->set_name( "_ret" );
	902	(*param)->set_linkage( LinkageSpec::C );
	903	} // if
	904	UntypedExpr *assign = new UntypedExpr( new NameExpr( "?=?" ) );
[c10ee66]	905	UntypedExpr deref = UntypedExpr::createDeref( new CastExpr( new VariableExpr( param++ ), new PointerType( Type::Qualifiers(), realType->get_returnVals().front()->get_type()->clone() ) ) );
[01aeade]	906	assign->get_args().push_back( deref );
	907	addAdapterParams( adapteeApp, arg, param, adapterType->get_parameters().end(), realParam, tyVars );
	908	assign->get_args().push_back( adapteeApp );
	909	bodyStmt = new ExprStmt( noLabels, assign );
	910	} else {
	911	// adapter for a function that returns a monomorphic value
	912	addAdapterParams( adapteeApp, arg, param, adapterType->get_parameters().end(), realParam, tyVars );
	913	bodyStmt = new ReturnStmt( noLabels, adapteeApp );
	914	} // if
	915	CompoundStmt *adapterBody = new CompoundStmt( noLabels );
	916	adapterBody->get_kids().push_back( bodyStmt );
	917	std::string adapterName = makeAdapterName( mangleName );
[68fe077a]	918	return new FunctionDecl( adapterName, Type::StorageClasses(), LinkageSpec::C, adapterType, adapterBody );
[01aeade]	919	}
[6c3744e]	920
[c29d9ce]	921	void Pass1::passAdapters( ApplicationExpr * appExpr, FunctionType * functionType, const TyVarMap & exprTyVars ) {
[e497c1d]	922	// collect a list of function types passed as parameters or implicit parameters (assertions)
[01aeade]	923	std::list< DeclarationWithType *> &paramList = functionType->get_parameters();
	924	std::list< FunctionType *> functions;
[8c49c0e]	925	for ( Type::ForallList::iterator tyVar = functionType->get_forall().begin(); tyVar != functionType->get_forall().end(); ++tyVar ) {
[01aeade]	926	for ( std::list< DeclarationWithType >::iterator assert = (tyVar)->get_assertions().begin(); assert != (*tyVar)->get_assertions().end(); ++assert ) {
	927	findFunction( (*assert)->get_type(), functions, exprTyVars, needsAdapter );
	928	} // for
	929	} // for
	930	for ( std::list< DeclarationWithType *>::iterator arg = paramList.begin(); arg != paramList.end(); ++arg ) {
	931	findFunction( (*arg)->get_type(), functions, exprTyVars, needsAdapter );
	932	} // for
[e497c1d]	933
[e56cfdb0]	934	// parameter function types for which an appropriate adapter has been generated. we cannot use the types
	935	// after applying substitutions, since two different parameter types may be unified to the same type
[01aeade]	936	std::set< std::string > adaptersDone;
[e497c1d]	937
[01aeade]	938	for ( std::list< FunctionType *>::iterator funType = functions.begin(); funType != functions.end(); ++funType ) {
[c29d9ce]	939	FunctionType originalFunction = (funType)->clone();
[01aeade]	940	FunctionType realFunction = (funType)->clone();
	941	std::string mangleName = SymTab::Mangler::mangle( realFunction );
[e497c1d]	942
[e56cfdb0]	943	// only attempt to create an adapter or pass one as a parameter if we haven't already done so for this
	944	// pre-substitution parameter function type.
[01aeade]	945	if ( adaptersDone.find( mangleName ) == adaptersDone.end() ) {
[e497c1d]	946	adaptersDone.insert( adaptersDone.begin(), mangleName );
[ae63a18]	947
[e56cfdb0]	948	// apply substitution to type variables to figure out what the adapter's type should look like
[e497c1d]	949	assert( env );
	950	env->apply( realFunction );
[ae63a18]	951	mangleName = SymTab::Mangler::mangle( realFunction );
[bdf1954]	952	mangleName += makePolyMonoSuffix( originalFunction, exprTyVars );
[e497c1d]	953
[6635c74]	954	typedef ScopedMap< std::string, DeclarationWithType* >::iterator AdapterIter;
	955	AdapterIter adapter = adapters.find( mangleName );
[e56cfdb0]	956	if ( adapter == adapters.end() ) {
	957	// adapter has not been created yet in the current scope, so define it
	958	FunctionDecl newAdapter = makeAdapter( funType, realFunction, mangleName, exprTyVars );
[6635c74]	959	std::pair< AdapterIter, bool > answer = adapters.insert( std::pair< std::string, DeclarationWithType *>( mangleName, newAdapter ) );
	960	adapter = answer.first;
[e56cfdb0]	961	stmtsToAdd.push_back( new DeclStmt( noLabels, newAdapter ) );
[c29d9ce]	962	} // if
[e56cfdb0]	963	assert( adapter != adapters.end() );
	964
	965	// add the appropriate adapter as a parameter
	966	appExpr->get_args().push_front( new VariableExpr( adapter->second ) );
[01aeade]	967	} // if
	968	} // for
[e56cfdb0]	969	} // passAdapters
[6c3744e]	970
[78dd0da]	971	Expression makeIncrDecrExpr( ApplicationExpr appExpr, Type *polyType, bool isIncr ) {
[01aeade]	972	NameExpr *opExpr;
	973	if ( isIncr ) {
	974	opExpr = new NameExpr( "?+=?" );
	975	} else {
	976	opExpr = new NameExpr( "?-=?" );
[6c3744e]	977	} // if
[01aeade]	978	UntypedExpr *addAssign = new UntypedExpr( opExpr );
	979	if ( AddressExpr address = dynamic_cast< AddressExpr >( appExpr->get_args().front() ) ) {
	980	addAssign->get_args().push_back( address->get_arg() );
	981	} else {
	982	addAssign->get_args().push_back( appExpr->get_args().front() );
[6c3744e]	983	} // if
[adc6781]	984	addAssign->get_args().push_back( new NameExpr( sizeofName( mangleType( polyType ) ) ) );
[906e24d]	985	addAssign->set_result( appExpr->get_result()->clone() );
[01aeade]	986	if ( appExpr->get_env() ) {
	987	addAssign->set_env( appExpr->get_env() );
[6c3744e]	988	appExpr->set_env( 0 );
	989	} // if
[01aeade]	990	appExpr->get_args().clear();
	991	delete appExpr;
	992	return addAssign;
	993	}
	994
	995	Expression Pass1::handleIntrinsics( ApplicationExpr appExpr ) {
	996	if ( VariableExpr varExpr = dynamic_cast< VariableExpr >( appExpr->get_function() ) ) {
	997	if ( varExpr->get_var()->get_linkage() == LinkageSpec::Intrinsic ) {
	998	if ( varExpr->get_var()->get_name() == "?[?]" ) {
[906e24d]	999	assert( appExpr->has_result() );
[01aeade]	1000	assert( appExpr->get_args().size() == 2 );
[906e24d]	1001	Type *baseType1 = isPolyPtr( appExpr->get_args().front()->get_result(), scopeTyVars, env );
	1002	Type *baseType2 = isPolyPtr( appExpr->get_args().back()->get_result(), scopeTyVars, env );
[ae63a18]	1003	assert( ! baseType1 \|\| ! baseType2 ); // the arguments cannot both be polymorphic pointers
[01aeade]	1004	UntypedExpr *ret = 0;
[ae63a18]	1005	if ( baseType1 \|\| baseType2 ) { // one of the arguments is a polymorphic pointer
[01aeade]	1006	ret = new UntypedExpr( new NameExpr( "?+?" ) );
	1007	} // if
[ffad73a]	1008	if ( baseType1 ) {
[01aeade]	1009	UntypedExpr multiply = new UntypedExpr( new NameExpr( "??" ) );
	1010	multiply->get_args().push_back( appExpr->get_args().back() );
[adc6781]	1011	multiply->get_args().push_back( new SizeofExpr( baseType1->clone() ) );
[01aeade]	1012	ret->get_args().push_back( appExpr->get_args().front() );
	1013	ret->get_args().push_back( multiply );
[ffad73a]	1014	} else if ( baseType2 ) {
[01aeade]	1015	UntypedExpr multiply = new UntypedExpr( new NameExpr( "??" ) );
	1016	multiply->get_args().push_back( appExpr->get_args().front() );
[adc6781]	1017	multiply->get_args().push_back( new SizeofExpr( baseType2->clone() ) );
[01aeade]	1018	ret->get_args().push_back( multiply );
	1019	ret->get_args().push_back( appExpr->get_args().back() );
	1020	} // if
[ffad73a]	1021	if ( baseType1 \|\| baseType2 ) {
[83794e1]	1022	delete ret->get_result();
	1023	ret->set_result( appExpr->get_result()->clone() );
[01aeade]	1024	if ( appExpr->get_env() ) {
	1025	ret->set_env( appExpr->get_env() );
	1026	appExpr->set_env( 0 );
	1027	} // if
	1028	appExpr->get_args().clear();
	1029	delete appExpr;
	1030	return ret;
	1031	} // if
	1032	} else if ( varExpr->get_var()->get_name() == "*?" ) {
[906e24d]	1033	assert( appExpr->has_result() );
[01aeade]	1034	assert( ! appExpr->get_args().empty() );
[83794e1]	1035	if ( isPolyType( appExpr->get_result(), scopeTyVars, env ) ) {
[0a81c3f]	1036	// remove dereference from polymorphic types since they are boxed.
[01aeade]	1037	Expression *ret = appExpr->get_args().front();
[83794e1]	1038	// fix expr type to remove pointer
[906e24d]	1039	delete ret->get_result();
[83794e1]	1040	ret->set_result( appExpr->get_result()->clone() );
[01aeade]	1041	if ( appExpr->get_env() ) {
	1042	ret->set_env( appExpr->get_env() );
	1043	appExpr->set_env( 0 );
	1044	} // if
	1045	appExpr->get_args().clear();
	1046	delete appExpr;
	1047	return ret;
	1048	} // if
	1049	} else if ( varExpr->get_var()->get_name() == "?++" \|\| varExpr->get_var()->get_name() == "?--" ) {
[906e24d]	1050	assert( appExpr->has_result() );
[01aeade]	1051	assert( appExpr->get_args().size() == 1 );
[906e24d]	1052	if ( Type *baseType = isPolyPtr( appExpr->get_result(), scopeTyVars, env ) ) {
	1053	Type *tempType = appExpr->get_result()->clone();
[01aeade]	1054	if ( env ) {
	1055	env->apply( tempType );
	1056	} // if
	1057	ObjectDecl *newObj = makeTemporary( tempType );
	1058	VariableExpr *tempExpr = new VariableExpr( newObj );
	1059	UntypedExpr *assignExpr = new UntypedExpr( new NameExpr( "?=?" ) );
	1060	assignExpr->get_args().push_back( tempExpr->clone() );
	1061	if ( AddressExpr address = dynamic_cast< AddressExpr >( appExpr->get_args().front() ) ) {
	1062	assignExpr->get_args().push_back( address->get_arg()->clone() );
	1063	} else {
	1064	assignExpr->get_args().push_back( appExpr->get_args().front()->clone() );
	1065	} // if
[ffad73a]	1066	CommaExpr *firstComma = new CommaExpr( assignExpr, makeIncrDecrExpr( appExpr, baseType, varExpr->get_var()->get_name() == "?++" ) );
[01aeade]	1067	return new CommaExpr( firstComma, tempExpr );
	1068	} // if
	1069	} else if ( varExpr->get_var()->get_name() == "++?" \|\| varExpr->get_var()->get_name() == "--?" ) {
[906e24d]	1070	assert( appExpr->has_result() );
[01aeade]	1071	assert( appExpr->get_args().size() == 1 );
[906e24d]	1072	if ( Type *baseType = isPolyPtr( appExpr->get_result(), scopeTyVars, env ) ) {
[ffad73a]	1073	return makeIncrDecrExpr( appExpr, baseType, varExpr->get_var()->get_name() == "++?" );
[01aeade]	1074	} // if
	1075	} else if ( varExpr->get_var()->get_name() == "?+?" \|\| varExpr->get_var()->get_name() == "?-?" ) {
[906e24d]	1076	assert( appExpr->has_result() );
[01aeade]	1077	assert( appExpr->get_args().size() == 2 );
[906e24d]	1078	Type *baseType1 = isPolyPtr( appExpr->get_args().front()->get_result(), scopeTyVars, env );
	1079	Type *baseType2 = isPolyPtr( appExpr->get_args().back()->get_result(), scopeTyVars, env );
[ffad73a]	1080	if ( baseType1 && baseType2 ) {
[01aeade]	1081	UntypedExpr *divide = new UntypedExpr( new NameExpr( "?/?" ) );
	1082	divide->get_args().push_back( appExpr );
[adc6781]	1083	divide->get_args().push_back( new SizeofExpr( baseType1->clone() ) );
[906e24d]	1084	divide->set_result( appExpr->get_result()->clone() );
[01aeade]	1085	if ( appExpr->get_env() ) {
	1086	divide->set_env( appExpr->get_env() );
	1087	appExpr->set_env( 0 );
	1088	} // if
	1089	return divide;
[ffad73a]	1090	} else if ( baseType1 ) {
[01aeade]	1091	UntypedExpr multiply = new UntypedExpr( new NameExpr( "??" ) );
	1092	multiply->get_args().push_back( appExpr->get_args().back() );
[adc6781]	1093	multiply->get_args().push_back( new SizeofExpr( baseType1->clone() ) );
[01aeade]	1094	appExpr->get_args().back() = multiply;
[ffad73a]	1095	} else if ( baseType2 ) {
[01aeade]	1096	UntypedExpr multiply = new UntypedExpr( new NameExpr( "??" ) );
	1097	multiply->get_args().push_back( appExpr->get_args().front() );
[adc6781]	1098	multiply->get_args().push_back( new SizeofExpr( baseType2->clone() ) );
[01aeade]	1099	appExpr->get_args().front() = multiply;
	1100	} // if
	1101	} else if ( varExpr->get_var()->get_name() == "?+=?" \|\| varExpr->get_var()->get_name() == "?-=?" ) {
[906e24d]	1102	assert( appExpr->has_result() );
[01aeade]	1103	assert( appExpr->get_args().size() == 2 );
[906e24d]	1104	Type *baseType = isPolyPtr( appExpr->get_result(), scopeTyVars, env );
[ffad73a]	1105	if ( baseType ) {
[01aeade]	1106	UntypedExpr multiply = new UntypedExpr( new NameExpr( "??" ) );
	1107	multiply->get_args().push_back( appExpr->get_args().back() );
[adc6781]	1108	multiply->get_args().push_back( new SizeofExpr( baseType->clone() ) );
[01aeade]	1109	appExpr->get_args().back() = multiply;
	1110	} // if
	1111	} // if
	1112	return appExpr;
	1113	} // if
[6c3744e]	1114	} // if
[01aeade]	1115	return 0;
	1116	}
[6c3744e]	1117
[01aeade]	1118	Expression Pass1::mutate( ApplicationExpr appExpr ) {
[2a7b3ca]	1119	// std::cerr << "mutate appExpr: " << InitTweak::getFunctionName( appExpr ) << std::endl;
[e56cfdb0]	1120	// for ( TyVarMap::iterator i = scopeTyVars.begin(); i != scopeTyVars.end(); ++i ) {
	1121	// std::cerr << i->first << " ";
	1122	// }
	1123	// std::cerr << "\n";
[01aeade]	1124	appExpr->get_function()->acceptMutator( *this );
	1125	mutateAll( appExpr->get_args(), *this );
[ae63a18]	1126
[906e24d]	1127	assert( appExpr->get_function()->has_result() );
[83794e1]	1128	FunctionType * function = getFunctionType( appExpr->get_function()->get_result() );
	1129	assertf( function, "ApplicationExpr has non-function type: %s", toString( appExpr->get_function()->get_result() ).c_str() );
[ae63a18]	1130
[01aeade]	1131	if ( Expression *newExpr = handleIntrinsics( appExpr ) ) {
	1132	return newExpr;
	1133	} // if
[ae63a18]	1134
[01aeade]	1135	Expression *ret = appExpr;
[ae63a18]	1136
[01aeade]	1137	std::list< Expression *>::iterator arg = appExpr->get_args().begin();
	1138	std::list< Expression *>::iterator paramBegin = appExpr->get_args().begin();
[ae63a18]	1139
[2c57025]	1140	TyVarMap exprTyVars( TypeDecl::Data{} );
[5802a4f]	1141	makeTyVarMap( function, exprTyVars ); // xxx - should this take into account the variables already bound in scopeTyVars (i.e. remove them from exprTyVars?)
[3bb195cb]	1142	ReferenceToType *dynRetType = isDynRet( function, exprTyVars );
[5c52b06]	1143
[2a7b3ca]	1144	// std::cerr << function << std::endl;
	1145	// std::cerr << "scopeTyVars: ";
	1146	// printTyVarMap( std::cerr, scopeTyVars );
	1147	// std::cerr << "exprTyVars: ";
	1148	// printTyVarMap( std::cerr, exprTyVars );
	1149	// std::cerr << "env: " << *env << std::endl;
	1150	// std::cerr << needsAdapter( function, scopeTyVars ) << ! needsAdapter( function, exprTyVars) << std::endl;
	1151
[b940dc71]	1152	// 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
	1153	// passTypeVars needs to know the program-text return type (i.e. the distinction between _conc_T30 and T3(int))
	1154	// concRetType may not be a good name in one or both of these places. A more appropriate name change is welcome.
[3bb195cb]	1155	if ( dynRetType ) {
[2a7b3ca]	1156	// std::cerr << "dynRetType: " << dynRetType << std::endl;
[b940dc71]	1157	Type *concRetType = appExpr->get_result()->isVoid() ? nullptr : appExpr->get_result();
[d7dc824]	1158	ret = addDynRetParam( appExpr, concRetType, arg ); // xxx - used to use dynRetType instead of concRetType
[5802a4f]	1159	} else if ( needsAdapter( function, scopeTyVars ) && ! needsAdapter( function, exprTyVars) ) { // xxx - exprTyVars is used above...?
	1160	// 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.
	1161
[e56cfdb0]	1162	// std::cerr << "needs adapter: ";
[2e3a379]	1163	// printTyVarMap( std::cerr, scopeTyVars );
	1164	// std::cerr << *env << std::endl;
[01aeade]	1165	// change the application so it calls the adapter rather than the passed function
	1166	ret = applyAdapter( appExpr, function, arg, scopeTyVars );
	1167	} // if
	1168	arg = appExpr->get_args().begin();
[ae63a18]	1169
[b940dc71]	1170	Type *concRetType = replaceWithConcrete( appExpr, dynRetType );
[5802a4f]	1171	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]	1172	addInferredParams( appExpr, function, arg, exprTyVars );
[51b7345]	1173
[01aeade]	1174	arg = paramBegin;
[ae63a18]	1175
[01aeade]	1176	boxParams( appExpr, function, arg, exprTyVars );
	1177	passAdapters( appExpr, function, exprTyVars );
[6c3744e]	1178
[01aeade]	1179	return ret;
	1180	}
[6c3744e]	1181
[01aeade]	1182	Expression Pass1::mutate( UntypedExpr expr ) {
[906e24d]	1183	if ( expr->has_result() && isPolyType( expr->get_result(), scopeTyVars, env ) ) {
[01aeade]	1184	if ( NameExpr name = dynamic_cast< NameExpr >( expr->get_function() ) ) {
	1185	if ( name->get_name() == "*?" ) {
	1186	Expression *ret = expr->get_args().front();
	1187	expr->get_args().clear();
	1188	delete expr;
	1189	return ret->acceptMutator( *this );
	1190	} // if
	1191	} // if
	1192	} // if
	1193	return PolyMutator::mutate( expr );
	1194	}
[6c3744e]	1195
[01aeade]	1196	Expression Pass1::mutate( AddressExpr addrExpr ) {
[906e24d]	1197	assert( addrExpr->get_arg()->has_result() && ! addrExpr->get_arg()->get_result()->isVoid() );
[cf16f94]	1198
	1199	bool needs = false;
	1200	if ( UntypedExpr expr = dynamic_cast< UntypedExpr >( addrExpr->get_arg() ) ) {
[906e24d]	1201	if ( expr->has_result() && isPolyType( expr->get_result(), scopeTyVars, env ) ) {
[cf16f94]	1202	if ( NameExpr name = dynamic_cast< NameExpr >( expr->get_function() ) ) {
	1203	if ( name->get_name() == "*?" ) {
	1204	if ( ApplicationExpr * appExpr = dynamic_cast< ApplicationExpr * >( expr->get_args().front() ) ) {
[906e24d]	1205	assert( appExpr->get_function()->has_result() );
[83794e1]	1206	FunctionType *function = getFunctionType( appExpr->get_function()->get_result() );
	1207	assert( function );
[cf16f94]	1208	needs = needsAdapter( function, scopeTyVars );
	1209	} // if
	1210	} // if
	1211	} // if
	1212	} // if
	1213	} // if
[fea7ca7]	1214	// isPolyType check needs to happen before mutating addrExpr arg, so pull it forward
	1215	// out of the if condition.
[01aeade]	1216	addrExpr->set_arg( mutateExpression( addrExpr->get_arg() ) );
[d335627]	1217	// ... but must happen after mutate, since argument might change (e.g. intrinsic *?, ?[?]) - re-evaluate above comment
	1218	bool polytype = isPolyType( addrExpr->get_arg()->get_result(), scopeTyVars, env );
[fea7ca7]	1219	if ( polytype \|\| needs ) {
[01aeade]	1220	Expression *ret = addrExpr->get_arg();
[906e24d]	1221	delete ret->get_result();
	1222	ret->set_result( addrExpr->get_result()->clone() );
[01aeade]	1223	addrExpr->set_arg( 0 );
	1224	delete addrExpr;
	1225	return ret;
	1226	} else {
	1227	return addrExpr;
	1228	} // if
	1229	}
[6c3744e]	1230
[5802a4f]	1231	Statement * Pass1::mutate( ReturnStmt *returnStmt ) {
[cf16f94]	1232	if ( retval && returnStmt->get_expr() ) {
[906e24d]	1233	assert( returnStmt->get_expr()->has_result() && ! returnStmt->get_expr()->get_result()->isVoid() );
[5802a4f]	1234	delete returnStmt->get_expr();
[cf16f94]	1235	returnStmt->set_expr( 0 );
[01aeade]	1236	} else {
[cf16f94]	1237	returnStmt->set_expr( mutateExpression( returnStmt->get_expr() ) );
[01aeade]	1238	} // if
[cf16f94]	1239	return returnStmt;
[01aeade]	1240	}
[6c3744e]	1241
[01aeade]	1242	Type * Pass1::mutate( PointerType *pointerType ) {
[6f49cdf]	1243	scopeTyVars.beginScope();
[01aeade]	1244	makeTyVarMap( pointerType, scopeTyVars );
[ae63a18]	1245
[01aeade]	1246	Type *ret = Mutator::mutate( pointerType );
[ae63a18]	1247
[6f49cdf]	1248	scopeTyVars.endScope();
[01aeade]	1249	return ret;
	1250	}
[6c3744e]	1251
[01aeade]	1252	Type * Pass1::mutate( FunctionType *functionType ) {
[6f49cdf]	1253	scopeTyVars.beginScope();
[01aeade]	1254	makeTyVarMap( functionType, scopeTyVars );
[ae63a18]	1255
[01aeade]	1256	Type *ret = Mutator::mutate( functionType );
[ae63a18]	1257
[6f49cdf]	1258	scopeTyVars.endScope();
[01aeade]	1259	return ret;
	1260	}
[51b7345]	1261
[01aeade]	1262	void Pass1::doBeginScope() {
[6635c74]	1263	adapters.beginScope();
[01aeade]	1264	}
[b1a6d6b]	1265
[01aeade]	1266	void Pass1::doEndScope() {
[6635c74]	1267	adapters.endScope();
[01aeade]	1268	}
[51b7345]	1269
	1270	////////////////////////////////////////// Pass2 ////////////////////////////////////////////////////
	1271
[01aeade]	1272	void Pass2::addAdapters( FunctionType *functionType ) {
	1273	std::list< DeclarationWithType *> &paramList = functionType->get_parameters();
	1274	std::list< FunctionType *> functions;
	1275	for ( std::list< DeclarationWithType *>::iterator arg = paramList.begin(); arg != paramList.end(); ++arg ) {
	1276	Type orig = (arg)->get_type();
	1277	findAndReplaceFunction( orig, functions, scopeTyVars, needsAdapter );
	1278	(*arg)->set_type( orig );
	1279	}
	1280	std::set< std::string > adaptersDone;
	1281	for ( std::list< FunctionType *>::iterator funType = functions.begin(); funType != functions.end(); ++funType ) {
[bdf1954]	1282	std::string mangleName = mangleAdapterName( *funType, scopeTyVars );
[01aeade]	1283	if ( adaptersDone.find( mangleName ) == adaptersDone.end() ) {
	1284	std::string adapterName = makeAdapterName( mangleName );
[83794e1]	1285	// adapter may not be used in body, pass along with unused attribute.
	1286	paramList.push_front( new ObjectDecl( adapterName, Type::StorageClasses(), LinkageSpec::C, 0, new PointerType( Type::Qualifiers(), makeAdapterType( *funType, scopeTyVars ) ), 0, { new Attribute( "unused" ) } ) );
[01aeade]	1287	adaptersDone.insert( adaptersDone.begin(), mangleName );
	1288	}
	1289	}
[5f6c42c]	1290	// deleteAll( functions );
[01aeade]	1291	}
[6c3744e]	1292
[01aeade]	1293	template< typename DeclClass >
[7e003011]	1294	DeclClass * Pass2::handleDecl( DeclClass *decl ) {
[dd0c97b]	1295	DeclClass ret = static_cast< DeclClass >( Parent::mutate( decl ) );
[6c3744e]	1296
[01aeade]	1297	return ret;
	1298	}
[6c3744e]	1299
[cce9429]	1300	/// determines if `pref` is a prefix of `str`
	1301	bool isPrefix( const std::string & str, const std::string & pref ) {
	1302	if ( pref.size() > str.size() ) return false;
	1303	auto its = std::mismatch( pref.begin(), pref.end(), str.begin() );
	1304	return its.first == pref.end();
	1305	}
	1306
[01aeade]	1307	DeclarationWithType * Pass2::mutate( FunctionDecl *functionDecl ) {
[7e003011]	1308	functionDecl = safe_dynamic_cast< FunctionDecl * > ( handleDecl( functionDecl ) );
[cce9429]	1309	FunctionType * ftype = functionDecl->get_functionType();
	1310	if ( ! ftype->get_returnVals().empty() && functionDecl->get_statements() ) {
[a28bc02]	1311	if ( ! isPrefix( functionDecl->get_name(), "_thunk" ) && ! isPrefix( functionDecl->get_name(), "_adapter" ) ) { // xxx - remove check for prefix once thunks properly use ctor/dtors
[cce9429]	1312	assert( ftype->get_returnVals().size() == 1 );
	1313	DeclarationWithType * retval = ftype->get_returnVals().front();
	1314	if ( retval->get_name() == "" ) {
	1315	retval->set_name( "_retval" );
	1316	}
	1317	functionDecl->get_statements()->get_kids().push_front( new DeclStmt( noLabels, retval ) );
	1318	DeclarationWithType * newRet = retval->clone(); // for ownership purposes
	1319	ftype->get_returnVals().front() = newRet;
	1320	}
	1321	}
[064cb18]	1322	// errors should have been caught by this point, remove initializers from parameters to allow correct codegen of default arguments
	1323	for ( Declaration * param : functionDecl->get_functionType()->get_parameters() ) {
	1324	if ( ObjectDecl * obj = dynamic_cast< ObjectDecl * >( param ) ) {
	1325	delete obj->get_init();
	1326	obj->set_init( nullptr );
	1327	}
	1328	}
[cce9429]	1329	return functionDecl;
[01aeade]	1330	}
[6c3744e]	1331
[01aeade]	1332	ObjectDecl * Pass2::mutate( ObjectDecl *objectDecl ) {
[7e003011]	1333	return handleDecl( objectDecl );
[01aeade]	1334	}
[6c3744e]	1335
[dd0c97b]	1336	template< typename AggDecl >
	1337	AggDecl * Pass2::handleAggDecl( AggDecl * aggDecl ) {
	1338	// prevent tyVars from leaking into containing scope
	1339	scopeTyVars.beginScope();
	1340	Parent::mutate( aggDecl );
	1341	scopeTyVars.endScope();
	1342	return aggDecl;
	1343	}
	1344
	1345	StructDecl * Pass2::mutate( StructDecl *aggDecl ) {
	1346	return handleAggDecl( aggDecl );
	1347	}
	1348
	1349	UnionDecl * Pass2::mutate( UnionDecl *aggDecl ) {
	1350	return handleAggDecl( aggDecl );
	1351	}
	1352
[01aeade]	1353	TypeDecl * Pass2::mutate( TypeDecl *typeDecl ) {
[2c57025]	1354	addToTyVarMap( typeDecl, scopeTyVars );
[01aeade]	1355	if ( typeDecl->get_base() ) {
[7e003011]	1356	return handleDecl( typeDecl );
[01aeade]	1357	} else {
[dd0c97b]	1358	return Parent::mutate( typeDecl );
[01aeade]	1359	}
	1360	}
[6c3744e]	1361
[01aeade]	1362	TypedefDecl * Pass2::mutate( TypedefDecl *typedefDecl ) {
[7e003011]	1363	return handleDecl( typedefDecl );
[01aeade]	1364	}
[6c3744e]	1365
[01aeade]	1366	Type * Pass2::mutate( PointerType *pointerType ) {
[6f49cdf]	1367	scopeTyVars.beginScope();
[01aeade]	1368	makeTyVarMap( pointerType, scopeTyVars );
[ae63a18]	1369
[dd0c97b]	1370	Type *ret = Parent::mutate( pointerType );
[ae63a18]	1371
[6f49cdf]	1372	scopeTyVars.endScope();
[01aeade]	1373	return ret;
	1374	}
[6c3744e]	1375
[01aeade]	1376	Type Pass2::mutate( FunctionType funcType ) {
[6f49cdf]	1377	scopeTyVars.beginScope();
[01aeade]	1378	makeTyVarMap( funcType, scopeTyVars );
[7754cde]	1379
	1380	// move polymorphic return type to parameter list
[3bb195cb]	1381	if ( isDynRet( funcType ) ) {
[d9fa60a]	1382	ObjectDecl ret = safe_dynamic_cast< ObjectDecl >( funcType->get_returnVals().front() );
[01aeade]	1383	ret->set_type( new PointerType( Type::Qualifiers(), ret->get_type() ) );
	1384	funcType->get_parameters().push_front( ret );
	1385	funcType->get_returnVals().pop_front();
[d9fa60a]	1386	ret->set_init( nullptr ); // xxx - memory leak?
[01aeade]	1387	}
[7754cde]	1388
	1389	// add size/align and assertions for type parameters to parameter list
[01aeade]	1390	std::list< DeclarationWithType *>::iterator last = funcType->get_parameters().begin();
	1391	std::list< DeclarationWithType *> inferredParams;
[83794e1]	1392	// size/align/offset parameters may not be used in body, pass along with unused attribute.
	1393	ObjectDecl newObj( "", Type::StorageClasses(), LinkageSpec::C, 0, new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt ), 0,
	1394	{ new Attribute( "unused" ) } );
[68fe077a]	1395	ObjectDecl newPtr( "", Type::StorageClasses(), LinkageSpec::C, 0,
[05d47278]	1396	new PointerType( Type::Qualifiers(), new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt ) ), 0 );
[8c49c0e]	1397	for ( Type::ForallList::const_iterator tyParm = funcType->get_forall().begin(); tyParm != funcType->get_forall().end(); ++tyParm ) {
[db0b3ce]	1398	ObjectDecl sizeParm, alignParm;
	1399	// add all size and alignment parameters to parameter list
[2c57025]	1400	if ( (*tyParm)->isComplete() ) {
[78dd0da]	1401	TypeInstType parmType( Type::Qualifiers(), (tyParm)->get_name(), tyParm );
[adc6781]	1402	std::string parmName = mangleType( &parmType );
[ae63a18]	1403
[78dd0da]	1404	sizeParm = newObj.clone();
[adc6781]	1405	sizeParm->set_name( sizeofName( parmName ) );
[db0b3ce]	1406	last = funcType->get_parameters().insert( last, sizeParm );
	1407	++last;
[78dd0da]	1408
	1409	alignParm = newObj.clone();
[adc6781]	1410	alignParm->set_name( alignofName( parmName ) );
[db0b3ce]	1411	last = funcType->get_parameters().insert( last, alignParm );
[01aeade]	1412	++last;
	1413	}
[e56cfdb0]	1414	// move all assertions into parameter list
[01aeade]	1415	for ( std::list< DeclarationWithType >::iterator assert = (tyParm)->get_assertions().begin(); assert != (*tyParm)->get_assertions().end(); ++assert ) {
[f8b961b]	1416	// assert = (assert)->acceptMutator( *this );
[83794e1]	1417	// assertion parameters may not be used in body, pass along with unused attribute.
	1418	(*assert)->get_attributes().push_back( new Attribute( "unused" ) );
[01aeade]	1419	inferredParams.push_back( *assert );
	1420	}
	1421	(*tyParm)->get_assertions().clear();
	1422	}
[7754cde]	1423
[5c52b06]	1424	// add size/align for generic parameter types to parameter list
[b18b0b5]	1425	std::set< std::string > seenTypes; // sizeofName for generic types we've seen
[7754cde]	1426	for ( std::list< DeclarationWithType* >::const_iterator fnParm = last; fnParm != funcType->get_parameters().end(); ++fnParm ) {
[4b8f918]	1427	Type polyType = isPolyType( (fnParm)->get_type(), scopeTyVars );
	1428	if ( polyType && ! dynamic_cast< TypeInstType* >( polyType ) ) {
	1429	std::string typeName = mangleType( polyType );
[adc6781]	1430	if ( seenTypes.count( typeName ) ) continue;
[ae63a18]	1431
[05d47278]	1432	ObjectDecl sizeParm, alignParm, *offsetParm;
[7754cde]	1433	sizeParm = newObj.clone();
[adc6781]	1434	sizeParm->set_name( sizeofName( typeName ) );
[7754cde]	1435	last = funcType->get_parameters().insert( last, sizeParm );
	1436	++last;
	1437
	1438	alignParm = newObj.clone();
[adc6781]	1439	alignParm->set_name( alignofName( typeName ) );
[7754cde]	1440	last = funcType->get_parameters().insert( last, alignParm );
	1441	++last;
	1442
[4b8f918]	1443	if ( StructInstType polyBaseStruct = dynamic_cast< StructInstType >( polyType ) ) {
[89173242]	1444	// NOTE zero-length arrays are illegal in C, so empty structs have no offset array
	1445	if ( ! polyBaseStruct->get_baseStruct()->get_members().empty() ) {
	1446	offsetParm = newPtr.clone();
[adc6781]	1447	offsetParm->set_name( offsetofName( typeName ) );
[89173242]	1448	last = funcType->get_parameters().insert( last, offsetParm );
	1449	++last;
	1450	}
[05d47278]	1451	}
	1452
[adc6781]	1453	seenTypes.insert( typeName );
[7754cde]	1454	}
	1455	}
	1456
	1457	// splice assertion parameters into parameter list
[01aeade]	1458	funcType->get_parameters().splice( last, inferredParams );
	1459	addAdapters( funcType );
	1460	mutateAll( funcType->get_returnVals(), *this );
	1461	mutateAll( funcType->get_parameters(), *this );
[ae63a18]	1462
[6f49cdf]	1463	scopeTyVars.endScope();
[01aeade]	1464	return funcType;
	1465	}
[51b7345]	1466
[4b8f918]	1467	////////////////////////////////////////// PolyGenericCalculator ////////////////////////////////////////////////////
[51b7345]	1468
[a0ad7dc]	1469	PolyGenericCalculator::PolyGenericCalculator()
	1470	: Parent(), knownLayouts(), knownOffsets(), bufNamer( "_buf" ) {}
	1471
[aa19ccf]	1472	void PolyGenericCalculator::beginTypeScope( Type *ty ) {
	1473	scopeTyVars.beginScope();
	1474	makeTyVarMap( ty, scopeTyVars );
	1475	}
	1476
	1477	void PolyGenericCalculator::endTypeScope() {
	1478	scopeTyVars.endScope();
	1479	}
[51b7345]	1480
[01aeade]	1481	template< typename DeclClass >
[8a34677]	1482	DeclClass * PolyGenericCalculator::handleDecl( DeclClass decl, Type type ) {
[aa19ccf]	1483	beginTypeScope( type );
[1ba88a0]	1484	// knownLayouts.beginScope();
	1485	// knownOffsets.beginScope();
[ae63a18]	1486
[1ba88a0]	1487	DeclClass ret = static_cast< DeclClass >( Parent::mutate( decl ) );
[6c3744e]	1488
[1ba88a0]	1489	// knownOffsets.endScope();
	1490	// knownLayouts.endScope();
[aa19ccf]	1491	endTypeScope();
[01aeade]	1492	return ret;
	1493	}
[6c3744e]	1494
[8a34677]	1495	ObjectDecl * PolyGenericCalculator::mutate( ObjectDecl *objectDecl ) {
[01aeade]	1496	return handleDecl( objectDecl, objectDecl->get_type() );
	1497	}
[6c3744e]	1498
[8a34677]	1499	DeclarationWithType * PolyGenericCalculator::mutate( FunctionDecl *functionDecl ) {
[1ba88a0]	1500	knownLayouts.beginScope();
	1501	knownOffsets.beginScope();
	1502
	1503	DeclarationWithType * decl = handleDecl( functionDecl, functionDecl->get_functionType() );
	1504	knownOffsets.endScope();
	1505	knownLayouts.endScope();
	1506	return decl;
[01aeade]	1507	}
[6c3744e]	1508
[8a34677]	1509	TypedefDecl * PolyGenericCalculator::mutate( TypedefDecl *typedefDecl ) {
[01aeade]	1510	return handleDecl( typedefDecl, typedefDecl->get_base() );
	1511	}
[6c3744e]	1512
[8a34677]	1513	TypeDecl * PolyGenericCalculator::mutate( TypeDecl *typeDecl ) {
[2c57025]	1514	addToTyVarMap( typeDecl, scopeTyVars );
[1ba88a0]	1515	return Parent::mutate( typeDecl );
[01aeade]	1516	}
[51b7345]	1517
[8a34677]	1518	Type * PolyGenericCalculator::mutate( PointerType *pointerType ) {
[aa19ccf]	1519	beginTypeScope( pointerType );
[ae63a18]	1520
[1ba88a0]	1521	Type *ret = Parent::mutate( pointerType );
[ae63a18]	1522
[aa19ccf]	1523	endTypeScope();
[01aeade]	1524	return ret;
	1525	}
[6c3744e]	1526
[8a34677]	1527	Type * PolyGenericCalculator::mutate( FunctionType *funcType ) {
[aa19ccf]	1528	beginTypeScope( funcType );
[ae63a18]	1529
[8a34677]	1530	// make sure that any type information passed into the function is accounted for
	1531	for ( std::list< DeclarationWithType* >::const_iterator fnParm = funcType->get_parameters().begin(); fnParm != funcType->get_parameters().end(); ++fnParm ) {
	1532	// condition here duplicates that in Pass2::mutate( FunctionType* )
[4b8f918]	1533	Type polyType = isPolyType( (fnParm)->get_type(), scopeTyVars );
	1534	if ( polyType && ! dynamic_cast< TypeInstType* >( polyType ) ) {
	1535	knownLayouts.insert( mangleType( polyType ) );
[8a34677]	1536	}
	1537	}
[70a06f6]	1538
[1ba88a0]	1539	Type *ret = Parent::mutate( funcType );
[ae63a18]	1540
[aa19ccf]	1541	endTypeScope();
[01aeade]	1542	return ret;
[6c3744e]	1543	}
[51b7345]	1544
[8a34677]	1545	Statement PolyGenericCalculator::mutate( DeclStmt declStmt ) {
[01aeade]	1546	if ( ObjectDecl objectDecl = dynamic_cast< ObjectDecl >( declStmt->get_decl() ) ) {
[8a34677]	1547	if ( findGeneric( objectDecl->get_type() ) ) {
[a0ad7dc]	1548	// change initialization of a polymorphic value object to allocate via a VLA
	1549	// (alloca was previously used, but can't be safely used in loops)
[ffad73a]	1550	Type *declType = objectDecl->get_type();
[cccc534]	1551	ObjectDecl *newBuf = new ObjectDecl( bufNamer.newName(), Type::StorageClasses(), LinkageSpec::C, 0,
[c10ee66]	1552	new ArrayType( Type::Qualifiers(), new BasicType( Type::Qualifiers(), BasicType::Kind::Char), new NameExpr( sizeofName( mangleType(declType) ) ),
[cccc534]	1553	true, false, std::list<Attribute>{ new Attribute( "aligned", std::list<Expression>{ new ConstantExpr( Constant::from_int(8) ) } ) } ), 0 );
[a0ad7dc]	1554	stmtsToAdd.push_back( new DeclStmt( noLabels, newBuf ) );
[e01559c]	1555
	1556	delete objectDecl->get_init();
[cccc534]	1557	objectDecl->set_init( new SingleInit( new VariableExpr( newBuf ) ) );
[01aeade]	1558	}
	1559	}
[1ba88a0]	1560	return Parent::mutate( declStmt );
[01aeade]	1561	}
[05d47278]	1562
[2a4b088]	1563	/// Finds the member in the base list that matches the given declaration; returns its index, or -1 if not present
	1564	long findMember( DeclarationWithType memberDecl, std::list< Declaration > &baseDecls ) {
	1565	long i = 0;
	1566	for(std::list< Declaration* >::const_iterator decl = baseDecls.begin(); decl != baseDecls.end(); ++decl, ++i ) {
	1567	if ( memberDecl->get_name() != (*decl)->get_name() ) continue;
	1568
	1569	if ( DeclarationWithType declWithType = dynamic_cast< DeclarationWithType >( *decl ) ) {
[bed4d37c]	1570	if ( memberDecl->get_mangleName().empty() \|\| declWithType->get_mangleName().empty()
	1571	\|\| memberDecl->get_mangleName() == declWithType->get_mangleName() ) return i;
[2a4b088]	1572	else continue;
	1573	} else return i;
	1574	}
	1575	return -1;
	1576	}
	1577
	1578	/// Returns an index expression into the offset array for a type
	1579	Expression makeOffsetIndex( Type objectType, long i ) {
[d56e5bc]	1580	ConstantExpr *fieldIndex = new ConstantExpr( Constant::from_ulong( i ) );
[2a4b088]	1581	UntypedExpr *fieldOffset = new UntypedExpr( new NameExpr( "?[?]" ) );
[adc6781]	1582	fieldOffset->get_args().push_back( new NameExpr( offsetofName( mangleType( objectType ) ) ) );
[2a4b088]	1583	fieldOffset->get_args().push_back( fieldIndex );
	1584	return fieldOffset;
	1585	}
	1586
[8a34677]	1587	Expression PolyGenericCalculator::mutate( MemberExpr memberExpr ) {
[05d47278]	1588	// mutate, exiting early if no longer MemberExpr
[1ba88a0]	1589	Expression *expr = Parent::mutate( memberExpr );
[05d47278]	1590	memberExpr = dynamic_cast< MemberExpr* >( expr );
	1591	if ( ! memberExpr ) return expr;
	1592
	1593	// only mutate member expressions for polymorphic types
[8488c715]	1594	int tyDepth;
[c10ee66]	1595	Type *objectType = hasPolyBase( memberExpr->get_aggregate()->get_result(), scopeTyVars, &tyDepth );
[05d47278]	1596	if ( ! objectType ) return memberExpr;
[8a34677]	1597	findGeneric( objectType ); // ensure layout for this type is available
[05d47278]	1598
[ea5daeb]	1599	// replace member expression with dynamically-computed layout expression
[4318107]	1600	Expression *newMemberExpr = 0;
[05d47278]	1601	if ( StructInstType structType = dynamic_cast< StructInstType >( objectType ) ) {
[2a4b088]	1602	// look up offset index
	1603	long i = findMember( memberExpr->get_member(), structType->get_baseStruct()->get_members() );
	1604	if ( i == -1 ) return memberExpr;
[05d47278]	1605
[2a4b088]	1606	// replace member expression with pointer to base plus offset
	1607	UntypedExpr *fieldLoc = new UntypedExpr( new NameExpr( "?+?" ) );
[5802a4f]	1608	Expression * aggr = memberExpr->get_aggregate()->clone();
	1609	delete aggr->get_env(); // xxx - there's a problem with keeping the env for some reason, so for now just get rid of it
	1610	aggr->set_env( nullptr );
	1611	fieldLoc->get_args().push_back( aggr );
[2a4b088]	1612	fieldLoc->get_args().push_back( makeOffsetIndex( objectType, i ) );
[c10ee66]	1613	fieldLoc->set_result( memberExpr->get_result()->clone() );
[4318107]	1614	newMemberExpr = fieldLoc;
[98735ef]	1615	} else if ( dynamic_cast< UnionInstType* >( objectType ) ) {
[c10ee66]	1616	// union members are all at offset zero, so just use the aggregate expr
	1617	Expression * aggr = memberExpr->get_aggregate()->clone();
	1618	delete aggr->get_env(); // xxx - there's a problem with keeping the env for some reason, so for now just get rid of it
	1619	aggr->set_env( nullptr );
	1620	newMemberExpr = aggr;
	1621	newMemberExpr->set_result( memberExpr->get_result()->clone() );
[2a4b088]	1622	} else return memberExpr;
[4318107]	1623	assert( newMemberExpr );
	1624
[4067aa8]	1625	Type *memberType = memberExpr->get_member()->get_type();
	1626	if ( ! isPolyType( memberType, scopeTyVars ) ) {
	1627	// 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
	1628	CastExpr *ptrCastExpr = new CastExpr( newMemberExpr, new PointerType( Type::Qualifiers(), memberType->clone() ) );
[c10ee66]	1629	UntypedExpr *derefExpr = UntypedExpr::createDeref( ptrCastExpr );
[4318107]	1630	newMemberExpr = derefExpr;
	1631	}
	1632
	1633	delete memberExpr;
	1634	return newMemberExpr;
[2a4b088]	1635	}
[05d47278]	1636
[8a34677]	1637	ObjectDecl PolyGenericCalculator::makeVar( const std::string &name, Type type, Initializer *init ) {
[68fe077a]	1638	ObjectDecl *newObj = new ObjectDecl( name, Type::StorageClasses(), LinkageSpec::C, 0, type, init );
[8a34677]	1639	stmtsToAdd.push_back( new DeclStmt( noLabels, newObj ) );
	1640	return newObj;
	1641	}
	1642
	1643	void PolyGenericCalculator::addOtypeParamsToLayoutCall( UntypedExpr layoutCall, const std::list< Type > &otypeParams ) {
	1644	for ( std::list< Type* >::const_iterator param = otypeParams.begin(); param != otypeParams.end(); ++param ) {
	1645	if ( findGeneric( *param ) ) {
	1646	// push size/align vars for a generic parameter back
[adc6781]	1647	std::string paramName = mangleType( *param );
	1648	layoutCall->get_args().push_back( new NameExpr( sizeofName( paramName ) ) );
	1649	layoutCall->get_args().push_back( new NameExpr( alignofName( paramName ) ) );
[8a34677]	1650	} else {
	1651	layoutCall->get_args().push_back( new SizeofExpr( (*param)->clone() ) );
	1652	layoutCall->get_args().push_back( new AlignofExpr( (*param)->clone() ) );
	1653	}
	1654	}
	1655	}
	1656
	1657	/// returns true if any of the otype parameters have a dynamic layout and puts all otype parameters in the output list
	1658	bool findGenericParams( std::list< TypeDecl* > &baseParams, std::list< Expression* > &typeParams, std::list< Type* > &out ) {
	1659	bool hasDynamicLayout = false;
	1660
	1661	std::list< TypeDecl* >::const_iterator baseParam = baseParams.begin();
	1662	std::list< Expression* >::const_iterator typeParam = typeParams.begin();
	1663	for ( ; baseParam != baseParams.end() && typeParam != typeParams.end(); ++baseParam, ++typeParam ) {
	1664	// skip non-otype parameters
[2c57025]	1665	if ( ! (*baseParam)->isComplete() ) continue;
[8a34677]	1666	TypeExpr typeExpr = dynamic_cast< TypeExpr >( *typeParam );
	1667	assert( typeExpr && "all otype parameters should be type expressions" );
	1668
	1669	Type *type = typeExpr->get_type();
	1670	out.push_back( type );
	1671	if ( isPolyType( type ) ) hasDynamicLayout = true;
	1672	}
	1673	assert( baseParam == baseParams.end() && typeParam == typeParams.end() );
	1674
	1675	return hasDynamicLayout;
	1676	}
	1677
	1678	bool PolyGenericCalculator::findGeneric( Type *ty ) {
[c2ad3c9]	1679	ty = replaceTypeInst( ty, env );
[9799ec8]	1680
[8a34677]	1681	if ( TypeInstType typeInst = dynamic_cast< TypeInstType >( ty ) ) {
	1682	if ( scopeTyVars.find( typeInst->get_name() ) != scopeTyVars.end() ) {
	1683	// NOTE assumes here that getting put in the scopeTyVars included having the layout variables set
	1684	return true;
	1685	}
	1686	return false;
	1687	} else if ( StructInstType structTy = dynamic_cast< StructInstType >( ty ) ) {
	1688	// check if this type already has a layout generated for it
[adc6781]	1689	std::string typeName = mangleType( ty );
	1690	if ( knownLayouts.find( typeName ) != knownLayouts.end() ) return true;
[8a34677]	1691
	1692	// check if any of the type parameters have dynamic layout; if none do, this type is (or will be) monomorphized
	1693	std::list< Type* > otypeParams;
	1694	if ( ! findGenericParams( *structTy->get_baseParameters(), structTy->get_parameters(), otypeParams ) ) return false;
	1695
	1696	// insert local variables for layout and generate call to layout function
[adc6781]	1697	knownLayouts.insert( typeName ); // done early so as not to interfere with the later addition of parameters to the layout call
[8a34677]	1698	Type *layoutType = new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt );
	1699
	1700	int n_members = structTy->get_baseStruct()->get_members().size();
	1701	if ( n_members == 0 ) {
	1702	// all empty structs have the same layout - size 1, align 1
[cc3528f]	1703	makeVar( sizeofName( typeName ), layoutType, new SingleInit( new ConstantExpr( Constant::from_ulong( (unsigned long)1 ) ) ) );
	1704	makeVar( alignofName( typeName ), layoutType->clone(), new SingleInit( new ConstantExpr( Constant::from_ulong( (unsigned long)1 ) ) ) );
[8a34677]	1705	// NOTE zero-length arrays are forbidden in C, so empty structs have no offsetof array
	1706	} else {
[adc6781]	1707	ObjectDecl *sizeVar = makeVar( sizeofName( typeName ), layoutType );
	1708	ObjectDecl *alignVar = makeVar( alignofName( typeName ), layoutType->clone() );
[cb4c607]	1709	ObjectDecl *offsetVar = makeVar( offsetofName( typeName ), new ArrayType( Type::Qualifiers(), layoutType->clone(), new ConstantExpr( Constant::from_int( n_members ) ), false, false ) );
[8a34677]	1710
	1711	// generate call to layout function
[adc6781]	1712	UntypedExpr *layoutCall = new UntypedExpr( new NameExpr( layoutofName( structTy->get_baseStruct() ) ) );
[8a34677]	1713	layoutCall->get_args().push_back( new AddressExpr( new VariableExpr( sizeVar ) ) );
	1714	layoutCall->get_args().push_back( new AddressExpr( new VariableExpr( alignVar ) ) );
	1715	layoutCall->get_args().push_back( new VariableExpr( offsetVar ) );
	1716	addOtypeParamsToLayoutCall( layoutCall, otypeParams );
	1717
	1718	stmtsToAdd.push_back( new ExprStmt( noLabels, layoutCall ) );
	1719	}
	1720
	1721	return true;
	1722	} else if ( UnionInstType unionTy = dynamic_cast< UnionInstType >( ty ) ) {
	1723	// check if this type already has a layout generated for it
[adc6781]	1724	std::string typeName = mangleType( ty );
	1725	if ( knownLayouts.find( typeName ) != knownLayouts.end() ) return true;
[8a34677]	1726
	1727	// check if any of the type parameters have dynamic layout; if none do, this type is (or will be) monomorphized
	1728	std::list< Type* > otypeParams;
	1729	if ( ! findGenericParams( *unionTy->get_baseParameters(), unionTy->get_parameters(), otypeParams ) ) return false;
	1730
	1731	// insert local variables for layout and generate call to layout function
[adc6781]	1732	knownLayouts.insert( typeName ); // done early so as not to interfere with the later addition of parameters to the layout call
[8a34677]	1733	Type *layoutType = new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt );
	1734
[adc6781]	1735	ObjectDecl *sizeVar = makeVar( sizeofName( typeName ), layoutType );
	1736	ObjectDecl *alignVar = makeVar( alignofName( typeName ), layoutType->clone() );
[8a34677]	1737
	1738	// generate call to layout function
[adc6781]	1739	UntypedExpr *layoutCall = new UntypedExpr( new NameExpr( layoutofName( unionTy->get_baseUnion() ) ) );
[8a34677]	1740	layoutCall->get_args().push_back( new AddressExpr( new VariableExpr( sizeVar ) ) );
	1741	layoutCall->get_args().push_back( new AddressExpr( new VariableExpr( alignVar ) ) );
	1742	addOtypeParamsToLayoutCall( layoutCall, otypeParams );
	1743
	1744	stmtsToAdd.push_back( new ExprStmt( noLabels, layoutCall ) );
	1745
	1746	return true;
	1747	}
	1748
	1749	return false;
	1750	}
	1751
	1752	Expression PolyGenericCalculator::mutate( SizeofExpr sizeofExpr ) {
[2edd80ae]	1753	Type *ty = sizeofExpr->get_isType() ? sizeofExpr->get_type() : sizeofExpr->get_expr()->get_result();
[8a34677]	1754	if ( findGeneric( ty ) ) {
[adc6781]	1755	Expression *ret = new NameExpr( sizeofName( mangleType( ty ) ) );
[8a34677]	1756	delete sizeofExpr;
	1757	return ret;
	1758	}
	1759	return sizeofExpr;
	1760	}
	1761
	1762	Expression PolyGenericCalculator::mutate( AlignofExpr alignofExpr ) {
[2edd80ae]	1763	Type *ty = alignofExpr->get_isType() ? alignofExpr->get_type() : alignofExpr->get_expr()->get_result();
[8a34677]	1764	if ( findGeneric( ty ) ) {
[adc6781]	1765	Expression *ret = new NameExpr( alignofName( mangleType( ty ) ) );
[8a34677]	1766	delete alignofExpr;
	1767	return ret;
	1768	}
	1769	return alignofExpr;
	1770	}
	1771
	1772	Expression PolyGenericCalculator::mutate( OffsetofExpr offsetofExpr ) {
[2a4b088]	1773	// mutate, exiting early if no longer OffsetofExpr
[1ba88a0]	1774	Expression *expr = Parent::mutate( offsetofExpr );
[2a4b088]	1775	offsetofExpr = dynamic_cast< OffsetofExpr* >( expr );
	1776	if ( ! offsetofExpr ) return expr;
	1777
	1778	// only mutate expressions for polymorphic structs/unions
[8a34677]	1779	Type *ty = offsetofExpr->get_type();
	1780	if ( ! findGeneric( ty ) ) return offsetofExpr;
[2a4b088]	1781
	1782	if ( StructInstType structType = dynamic_cast< StructInstType >( ty ) ) {
	1783	// replace offsetof expression by index into offset array
	1784	long i = findMember( offsetofExpr->get_member(), structType->get_baseStruct()->get_members() );
	1785	if ( i == -1 ) return offsetofExpr;
	1786
	1787	Expression *offsetInd = makeOffsetIndex( ty, i );
	1788	delete offsetofExpr;
	1789	return offsetInd;
[5c52b06]	1790	} else if ( dynamic_cast< UnionInstType* >( ty ) ) {
[2a4b088]	1791	// all union members are at offset zero
	1792	delete offsetofExpr;
[d56e5bc]	1793	return new ConstantExpr( Constant::from_ulong( 0 ) );
[2a4b088]	1794	} else return offsetofExpr;
[05d47278]	1795	}
	1796
[8a34677]	1797	Expression PolyGenericCalculator::mutate( OffsetPackExpr offsetPackExpr ) {
	1798	StructInstType *ty = offsetPackExpr->get_type();
	1799
	1800	Expression *ret = 0;
	1801	if ( findGeneric( ty ) ) {
	1802	// pull offset back from generated type information
[adc6781]	1803	ret = new NameExpr( offsetofName( mangleType( ty ) ) );
[8a34677]	1804	} else {
[adc6781]	1805	std::string offsetName = offsetofName( mangleType( ty ) );
[8a34677]	1806	if ( knownOffsets.find( offsetName ) != knownOffsets.end() ) {
	1807	// use the already-generated offsets for this type
	1808	ret = new NameExpr( offsetName );
	1809	} else {
	1810	knownOffsets.insert( offsetName );
	1811
	1812	std::list< Declaration* > &baseMembers = ty->get_baseStruct()->get_members();
	1813	Type *offsetType = new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt );
	1814
	1815	// build initializer list for offset array
	1816	std::list< Initializer* > inits;
	1817	for ( std::list< Declaration* >::const_iterator member = baseMembers.begin(); member != baseMembers.end(); ++member ) {
[2164637]	1818	if ( DeclarationWithType memberDecl = dynamic_cast< DeclarationWithType >( *member ) ) {
	1819	inits.push_back( new SingleInit( new OffsetofExpr( ty->clone(), memberDecl ) ) );
[8a34677]	1820	} else {
[2164637]	1821	assertf( false, "Requesting offset of Non-DWT member: %s", toString( *member ).c_str() );
[8a34677]	1822	}
	1823	}
	1824
	1825	// build the offset array and replace the pack with a reference to it
[cb4c607]	1826	ObjectDecl *offsetArray = makeVar( offsetName, new ArrayType( Type::Qualifiers(), offsetType, new ConstantExpr( Constant::from_ulong( baseMembers.size() ) ), false, false ),
[8a34677]	1827	new ListInit( inits ) );
	1828	ret = new VariableExpr( offsetArray );
	1829	}
	1830	}
	1831
	1832	delete offsetPackExpr;
	1833	return ret;
	1834	}
	1835
	1836	void PolyGenericCalculator::doBeginScope() {
	1837	knownLayouts.beginScope();
	1838	knownOffsets.beginScope();
	1839	}
	1840
	1841	void PolyGenericCalculator::doEndScope() {
	1842	knownLayouts.endScope();
[adc6781]	1843	knownOffsets.endScope();
[8a34677]	1844	}
	1845
[05d47278]	1846	////////////////////////////////////////// Pass3 ////////////////////////////////////////////////////
	1847
	1848	template< typename DeclClass >
	1849	DeclClass * Pass3::handleDecl( DeclClass decl, Type type ) {
[6f49cdf]	1850	scopeTyVars.beginScope();
[05d47278]	1851	makeTyVarMap( type, scopeTyVars );
	1852
	1853	DeclClass ret = static_cast< DeclClass >( Mutator::mutate( decl ) );
[5a3ac84]	1854	// ScrubTyVars::scrub( decl, scopeTyVars );
	1855	ScrubTyVars::scrubAll( decl );
[05d47278]	1856
[6f49cdf]	1857	scopeTyVars.endScope();
[05d47278]	1858	return ret;
	1859	}
	1860
	1861	ObjectDecl * Pass3::mutate( ObjectDecl *objectDecl ) {
	1862	return handleDecl( objectDecl, objectDecl->get_type() );
	1863	}
	1864
	1865	DeclarationWithType * Pass3::mutate( FunctionDecl *functionDecl ) {
	1866	return handleDecl( functionDecl, functionDecl->get_functionType() );
	1867	}
	1868
	1869	TypedefDecl * Pass3::mutate( TypedefDecl *typedefDecl ) {
	1870	return handleDecl( typedefDecl, typedefDecl->get_base() );
	1871	}
	1872
[fea3faa]	1873	/// Strips the members from a generic aggregate
	1874	void stripGenericMembers(AggregateDecl* decl) {
	1875	if ( ! decl->get_parameters().empty() ) decl->get_members().clear();
	1876	}
	1877
	1878	Declaration Pass3::mutate( StructDecl structDecl ) {
	1879	stripGenericMembers( structDecl );
	1880	return structDecl;
	1881	}
[acd7c5dd]	1882
[fea3faa]	1883	Declaration Pass3::mutate( UnionDecl unionDecl ) {
	1884	stripGenericMembers( unionDecl );
	1885	return unionDecl;
	1886	}
	1887
[05d47278]	1888	TypeDecl * Pass3::mutate( TypeDecl *typeDecl ) {
	1889	// Initializer *init = 0;
	1890	// std::list< Expression *> designators;
[2c57025]	1891	// addToTyVarMap( typeDecl, scopeTyVars );
[05d47278]	1892	// if ( typeDecl->get_base() ) {
	1893	// init = new SimpleInit( new SizeofExpr( handleDecl( typeDecl, typeDecl->get_base() ) ), designators );
	1894	// }
	1895	// return new ObjectDecl( typeDecl->get_name(), Declaration::Extern, LinkageSpec::C, 0, new BasicType( Type::Qualifiers(), BasicType::UnsignedInt ), init );
	1896
[2c57025]	1897	addToTyVarMap( typeDecl, scopeTyVars );
[05d47278]	1898	return Mutator::mutate( typeDecl );
	1899	}
	1900
	1901	Type * Pass3::mutate( PointerType *pointerType ) {
[6f49cdf]	1902	scopeTyVars.beginScope();
[05d47278]	1903	makeTyVarMap( pointerType, scopeTyVars );
	1904
	1905	Type *ret = Mutator::mutate( pointerType );
	1906
[6f49cdf]	1907	scopeTyVars.endScope();
[05d47278]	1908	return ret;
	1909	}
	1910
	1911	Type * Pass3::mutate( FunctionType *functionType ) {
[6f49cdf]	1912	scopeTyVars.beginScope();
[05d47278]	1913	makeTyVarMap( functionType, scopeTyVars );
	1914
	1915	Type *ret = Mutator::mutate( functionType );
	1916
[6f49cdf]	1917	scopeTyVars.endScope();
[05d47278]	1918	return ret;
	1919	}
[01aeade]	1920	} // anonymous namespace
[51b7345]	1921	} // namespace GenPoly
[01aeade]	1922
[51587aa]	1923	// Local Variables: //
	1924	// tab-width: 4 //
	1925	// mode: c++ //
	1926	// compile-command: "make install" //
	1927	// End: //

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

Download in other formats: