Context Navigation

source: src/GenPoly/Box.cc @ d335627

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

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

Download in other formats: