Context Navigation

source: src/GenPoly/Box.cc @ c10ee66

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 c10ee66 was c10ee66, checked in by Rob Schluntz <rschlunt@…>, 7 years ago
fix nested generic member expressions, fix generic union member expression, silence some generated code warnings
Property mode set to `100644`
File size: 86.6 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
[615a096]	12	// Last Modified On : Fri Mar 17 09:06:37 2017
	13	// Update Count : 339
[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
[5802a4f]	58	#include "InitTweak/InitTweak.h"
	59
[51b7345]	60	#include <ext/functional> // temporary
	61
	62	namespace GenPoly {
[01aeade]	63	namespace {
	64	const std::list<Label> noLabels;
	65
[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
[01aeade]	105	Expression addRetParam( ApplicationExpr appExpr, FunctionType function, 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
[d9fa60a]	112	Expression addDynRetParam( ApplicationExpr appExpr, FunctionType function, 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 >
	138	DeclClass handleDecl( DeclClass decl, Type *type );
[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
	345	Expression *ifCond = makeOp( "?&?", lhs, makeOp( "?-?", rhs, new ConstantExpr( Constant( new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt ), "1" ) ) ) );
	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)
[9d7b3ea]	388	addExpr( layoutDecl->get_statements(), makeOp( "?=?", derefVar( sizeParam ), new ConstantExpr( Constant( sizeAlignType->clone(), "0" ) ) ) );
	389	addExpr( layoutDecl->get_statements(), makeOp( "?=?", derefVar( alignParam ), new ConstantExpr( Constant( sizeAlignType->clone(), "1" ) ) ) );
	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
	445	addExpr( layoutDecl->get_statements(), makeOp( "?=?", derefVar( sizeParam ), new ConstantExpr( Constant( sizeAlignType->clone(), "1" ) ) ) );
	446	addExpr( layoutDecl->get_statements(), makeOp( "?=?", derefVar( alignParam ), new ConstantExpr( Constant( sizeAlignType->clone(), "1" ) ) ) );
	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 ?
	508	doBeginScope();
[4b8f918]	509	scopeTyVars.beginScope();
[9799ec8]	510
[01aeade]	511	DeclarationWithType *oldRetval = retval;
[e56cfdb0]	512
	513	// process polymorphic return value
[cce9429]	514	retval = nullptr;
	515	if ( isDynRet( functionDecl->get_functionType() ) && functionDecl->get_linkage() != LinkageSpec::C ) {
[01aeade]	516	retval = functionDecl->get_functionType()->get_returnVals().front();
[ae63a18]	517
[01aeade]	518	// give names to unnamed return values
	519	if ( retval->get_name() == "" ) {
	520	retval->set_name( "_retparm" );
	521	retval->set_linkage( LinkageSpec::C );
	522	} // if
	523	} // if
[ae63a18]	524
[e56cfdb0]	525	FunctionType *functionType = functionDecl->get_functionType();
[01aeade]	526	makeTyVarMap( functionDecl->get_functionType(), scopeTyVars );
[e56cfdb0]	527
	528	std::list< DeclarationWithType *> &paramList = functionType->get_parameters();
	529	std::list< FunctionType *> functions;
[8c49c0e]	530	for ( Type::ForallList::iterator tyVar = functionType->get_forall().begin(); tyVar != functionType->get_forall().end(); ++tyVar ) {
[e56cfdb0]	531	for ( std::list< DeclarationWithType >::iterator assert = (tyVar)->get_assertions().begin(); assert != (*tyVar)->get_assertions().end(); ++assert ) {
	532	findFunction( (*assert)->get_type(), functions, scopeTyVars, needsAdapter );
	533	} // for
	534	} // for
	535	for ( std::list< DeclarationWithType *>::iterator arg = paramList.begin(); arg != paramList.end(); ++arg ) {
	536	findFunction( (*arg)->get_type(), functions, scopeTyVars, needsAdapter );
	537	} // for
[b4cd03b7]	538
[e56cfdb0]	539	for ( std::list< FunctionType *>::iterator funType = functions.begin(); funType != functions.end(); ++funType ) {
[bdf1954]	540	std::string mangleName = mangleAdapterName( *funType, scopeTyVars );
[e56cfdb0]	541	if ( adapters.find( mangleName ) == adapters.end() ) {
	542	std::string adapterName = makeAdapterName( mangleName );
[68fe077a]	543	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]	544	} // if
	545	} // for
	546
[01aeade]	547	functionDecl->set_statements( functionDecl->get_statements()->acceptMutator( *this ) );
[ae63a18]	548
[6f49cdf]	549	scopeTyVars.endScope();
[01aeade]	550	retval = oldRetval;
[e56cfdb0]	551	doEndScope();
[01aeade]	552	} // if
	553	return functionDecl;
	554	}
[6c3744e]	555
[01aeade]	556	TypeDecl Pass1::mutate( TypeDecl typeDecl ) {
[2c57025]	557	addToTyVarMap( typeDecl, scopeTyVars );
[01aeade]	558	return Mutator::mutate( typeDecl );
	559	}
[6c3744e]	560
[01aeade]	561	Expression Pass1::mutate( CommaExpr commaExpr ) {
[cce9429]	562	// Attempting to find application expressions that were mutated by the copy constructor passes
	563	// to use an explicit return variable, so that the variable can be reused as a parameter to the
	564	// call rather than creating a new temp variable. Previously this step was an optimization, but
	565	// with the introduction of tuples and UniqueExprs, it is necessary to ensure that they use the same variable.
	566	// Essentially, looking for pattern: (x=f(...), x)
	567	// To compound the issue, the right side can be *x, etc. because of lvalue-returning functions
	568	if ( UntypedExpr * assign = dynamic_cast< UntypedExpr * >( commaExpr->get_arg1() ) ) {
	569	if ( InitTweak::isAssignment( InitTweak::getFunctionName( assign ) ) ) {
	570	assert( assign->get_args().size() == 2 );
	571	if ( ApplicationExpr * appExpr = dynamic_cast< ApplicationExpr * > ( assign->get_args().back() ) ) {
	572	// first argument is assignable, so it must be an lvalue, so it should be legal to take its address.
	573	retVals[appExpr] = assign->get_args().front();
	574	}
	575	}
	576	}
	577
[01aeade]	578	commaExpr->set_arg1( maybeMutate( commaExpr->get_arg1(), *this ) );
	579	commaExpr->set_arg2( maybeMutate( commaExpr->get_arg2(), *this ) );
	580	return commaExpr;
	581	}
[6c3744e]	582
[01aeade]	583	Expression Pass1::mutate( ConditionalExpr condExpr ) {
	584	condExpr->set_arg1( maybeMutate( condExpr->get_arg1(), *this ) );
	585	condExpr->set_arg2( maybeMutate( condExpr->get_arg2(), *this ) );
	586	condExpr->set_arg3( maybeMutate( condExpr->get_arg3(), *this ) );
	587	return condExpr;
[6c3744e]	588
[01aeade]	589	}
[6c3744e]	590
[5c52b06]	591	void Pass1::passArgTypeVars( ApplicationExpr appExpr, Type parmType, Type argBaseType, std::list< Expression >::iterator &arg, const TyVarMap &exprTyVars, std::set< std::string > &seenTypes ) {
[4b8f918]	592	Type *polyType = isPolyType( parmType, exprTyVars );
	593	if ( polyType && ! dynamic_cast< TypeInstType* >( polyType ) ) {
	594	std::string typeName = mangleType( polyType );
[adc6781]	595	if ( seenTypes.count( typeName ) ) return;
[5c52b06]	596
	597	arg = appExpr->get_args().insert( arg, new SizeofExpr( argBaseType->clone() ) );
	598	arg++;
	599	arg = appExpr->get_args().insert( arg, new AlignofExpr( argBaseType->clone() ) );
	600	arg++;
[4b8f918]	601	if ( dynamic_cast< StructInstType* >( polyType ) ) {
[5c52b06]	602	if ( StructInstType argBaseStructType = dynamic_cast< StructInstType >( argBaseType ) ) {
[89173242]	603	// zero-length arrays are forbidden by C, so don't pass offset for empty struct
	604	if ( ! argBaseStructType->get_baseStruct()->get_members().empty() ) {
[d75038c]	605	arg = appExpr->get_args().insert( arg, new OffsetPackExpr( argBaseStructType->clone() ) );
[89173242]	606	arg++;
	607	}
[5c52b06]	608	} else {
	609	throw SemanticError( "Cannot pass non-struct type for generic struct" );
	610	}
	611	}
	612
[adc6781]	613	seenTypes.insert( typeName );
[5c52b06]	614	}
	615	}
	616
[d9fa60a]	617	void Pass1::passTypeVars( ApplicationExpr appExpr, Type polyRetType, std::list< Expression *>::iterator &arg, const TyVarMap &exprTyVars ) {
[7754cde]	618	// pass size/align for type variables
[01aeade]	619	for ( TyVarMap::const_iterator tyParm = exprTyVars.begin(); tyParm != exprTyVars.end(); ++tyParm ) {
	620	ResolvExpr::EqvClass eqvClass;
	621	assert( env );
[2c57025]	622	if ( tyParm->second.isComplete ) {
[01aeade]	623	Type *concrete = env->lookup( tyParm->first );
	624	if ( concrete ) {
	625	arg = appExpr->get_args().insert( arg, new SizeofExpr( concrete->clone() ) );
	626	arg++;
[db0b3ce]	627	arg = appExpr->get_args().insert( arg, new AlignofExpr( concrete->clone() ) );
	628	arg++;
[01aeade]	629	} else {
[ea5daeb]	630	// xxx - should this be an assertion?
[cce9429]	631	std::string x = env ? toString( *env ) : "missing env";
	632	throw SemanticError( x + "\n" + "unbound type variable: " + tyParm->first + " in application ", appExpr );
[01aeade]	633	} // if
	634	} // if
	635	} // for
[7754cde]	636
	637	// add size/align for generic types to parameter list
[906e24d]	638	if ( ! appExpr->get_function()->has_result() ) return;
	639	FunctionType *funcType = getFunctionType( appExpr->get_function()->get_result() );
[7754cde]	640	assert( funcType );
[ae63a18]	641
[7754cde]	642	std::list< DeclarationWithType* >::const_iterator fnParm = funcType->get_parameters().begin();
	643	std::list< Expression* >::const_iterator fnArg = arg;
[ea5daeb]	644	std::set< std::string > seenTypes; ///< names for generic types we've seen
[7754cde]	645
[5c52b06]	646	// a polymorphic return type may need to be added to the argument list
	647	if ( polyRetType ) {
	648	Type *concRetType = replaceWithConcrete( appExpr, polyRetType );
	649	passArgTypeVars( appExpr, polyRetType, concRetType, arg, exprTyVars, seenTypes );
[5802a4f]	650	++fnArg; // skip the return parameter in the argument list
[5c52b06]	651	}
[70a06f6]	652
[5c52b06]	653	// add type information args for presently unseen types in parameter list
	654	for ( ; fnParm != funcType->get_parameters().end() && fnArg != appExpr->get_args().end(); ++fnParm, ++fnArg ) {
[5802a4f]	655	if ( ! (*fnArg)->get_result() ) continue;
	656	Type * argType = (*fnArg)->get_result();
	657	passArgTypeVars( appExpr, (*fnParm)->get_type(), argType, arg, exprTyVars, seenTypes );
[7754cde]	658	}
[01aeade]	659	}
[6c3744e]	660
[01aeade]	661	ObjectDecl Pass1::makeTemporary( Type type ) {
[68fe077a]	662	ObjectDecl *newObj = new ObjectDecl( tempNamer.newName(), Type::StorageClasses(), LinkageSpec::C, 0, type, 0 );
[01aeade]	663	stmtsToAdd.push_back( new DeclStmt( noLabels, newObj ) );
	664	return newObj;
	665	}
[6c3744e]	666
[01aeade]	667	Expression Pass1::addRetParam( ApplicationExpr appExpr, FunctionType function, Type retType, std::list< Expression *>::iterator &arg ) {
[cf16f94]	668	// Create temporary to hold return value of polymorphic function and produce that temporary as a result
[cce9429]	669	// using a comma expression.
[d9fa60a]	670	assert( retType );
[cce9429]	671
	672	Expression * paramExpr = nullptr;
	673	// try to use existing return value parameter if it exists, otherwise create a new temporary
	674	if ( retVals.count( appExpr ) ) {
	675	paramExpr = retVals[appExpr]->clone();
	676	} else {
	677	ObjectDecl *newObj = makeTemporary( retType->clone() );
	678	paramExpr = new VariableExpr( newObj );
	679	}
	680	Expression * retExpr = paramExpr->clone();
[5c52b06]	681
	682	// If the type of the temporary is not polymorphic, box temporary by taking its address;
	683	// otherwise the temporary is already boxed and can be used directly.
[cce9429]	684	if ( ! isPolyType( paramExpr->get_result(), scopeTyVars, env ) ) {
[cf16f94]	685	paramExpr = new AddressExpr( paramExpr );
[01aeade]	686	} // if
[cf16f94]	687	arg = appExpr->get_args().insert( arg, paramExpr ); // add argument to function call
	688	arg++;
	689	// Build a comma expression to call the function and emulate a normal return.
[cce9429]	690	CommaExpr *commaExpr = new CommaExpr( appExpr, retExpr );
[cf16f94]	691	commaExpr->set_env( appExpr->get_env() );
	692	appExpr->set_env( 0 );
	693	return commaExpr;
[01aeade]	694	}
[6c3744e]	695
[48ca586]	696	void Pass1::replaceParametersWithConcrete( ApplicationExpr appExpr, std::list< Expression >& params ) {
	697	for ( std::list< Expression* >::iterator param = params.begin(); param != params.end(); ++param ) {
	698	TypeExpr paramType = dynamic_cast< TypeExpr >( *param );
[8bf784a]	699	assertf(paramType, "Aggregate parameters should be type expressions");
[48ca586]	700	paramType->set_type( replaceWithConcrete( appExpr, paramType->get_type(), false ) );
	701	}
	702	}
[b4cd03b7]	703
[48ca586]	704	Type Pass1::replaceWithConcrete( ApplicationExpr appExpr, Type *type, bool doClone ) {
	705	if ( TypeInstType typeInst = dynamic_cast< TypeInstType >( type ) ) {
	706	Type *concrete = env->lookup( typeInst->get_name() );
	707	if ( concrete == 0 ) {
[cce9429]	708	// xxx - should this be an assertion?
	709	std::string x = env ? toString( *env ) : "missing env";
	710	throw SemanticError( x + "\n" + "Unbound type variable " + typeInst->get_name() + " in ", appExpr );
[48ca586]	711	} // if
	712	return concrete;
	713	} else if ( StructInstType structType = dynamic_cast< StructInstType >( type ) ) {
	714	if ( doClone ) {
	715	structType = structType->clone();
	716	}
	717	replaceParametersWithConcrete( appExpr, structType->get_parameters() );
	718	return structType;
	719	} else if ( UnionInstType unionType = dynamic_cast< UnionInstType >( type ) ) {
	720	if ( doClone ) {
	721	unionType = unionType->clone();
	722	}
	723	replaceParametersWithConcrete( appExpr, unionType->get_parameters() );
	724	return unionType;
	725	}
	726	return type;
	727	}
	728
[d9fa60a]	729	Expression Pass1::addDynRetParam( ApplicationExpr appExpr, FunctionType function, Type dynType, std::list< Expression *>::iterator &arg ) {
[01aeade]	730	assert( env );
[3bb195cb]	731	Type *concrete = replaceWithConcrete( appExpr, dynType );
[70a06f6]	732	// add out-parameter for return value
[01aeade]	733	return addRetParam( appExpr, function, concrete, arg );
	734	}
[6c3744e]	735
[01aeade]	736	Expression Pass1::applyAdapter( ApplicationExpr appExpr, FunctionType function, std::list< Expression >::iterator &arg, const TyVarMap &tyVars ) {
	737	Expression *ret = appExpr;
[3bb195cb]	738	// if ( ! function->get_returnVals().empty() && isPolyType( function->get_returnVals().front()->get_type(), tyVars ) ) {
	739	if ( isDynRet( function, tyVars ) ) {
[01aeade]	740	ret = addRetParam( appExpr, function, function->get_returnVals().front()->get_type(), arg );
	741	} // if
[bdf1954]	742	std::string mangleName = mangleAdapterName( function, tyVars );
[01aeade]	743	std::string adapterName = makeAdapterName( mangleName );
[b1a6d6b]	744
[b4cd03b7]	745	// cast adaptee to void (*)(), since it may have any type inside a polymorphic function
	746	Type * adapteeType = new PointerType( Type::Qualifiers(), new FunctionType( Type::Qualifiers(), true ) );
	747	appExpr->get_args().push_front( new CastExpr( appExpr->get_function(), adapteeType ) );
[906e24d]	748	appExpr->set_function( new NameExpr( adapterName ) ); // xxx - result is never set on NameExpr
[ae63a18]	749
[01aeade]	750	return ret;
	751	}
[6c3744e]	752
[01aeade]	753	void Pass1::boxParam( Type param, Expression &arg, const TyVarMap &exprTyVars ) {
[906e24d]	754	assert( arg->has_result() );
[1cced28]	755	if ( isPolyType( param, exprTyVars ) ) {
[906e24d]	756	if ( isPolyType( arg->get_result() ) ) {
[9407ed8]	757	// if the argument's type is polymorphic, we don't need to box again!
[01aeade]	758	return;
[615a096]	759	} else if ( arg->get_result()->get_lvalue() ) {
[b3ab8f0]	760	// 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]	761	// xxx - need to test that this code is still reachable
[b3ab8f0]	762	if ( CommaExpr commaArg = dynamic_cast< CommaExpr >( arg ) ) {
[bc1ab61]	763	commaArg->set_arg2( new AddressExpr( commaArg->get_arg2() ) );
[b3ab8f0]	764	} else {
	765	arg = new AddressExpr( arg );
	766	}
[c10ee66]	767	if ( ! ResolvExpr::typesCompatible( param, arg->get_result(), SymTab::Indexer() ) ) {
	768	// silence warnings by casting boxed parameters when the actual type does not match up with the formal type.
	769	arg = new CastExpr( arg, param->clone() );
	770	}
[01aeade]	771	} else {
[bd85400]	772	// use type computed in unification to declare boxed variables
	773	Type * newType = param->clone();
	774	if ( env ) env->apply( newType );
[68fe077a]	775	ObjectDecl *newObj = new ObjectDecl( tempNamer.newName(), Type::StorageClasses(), LinkageSpec::C, 0, newType, 0 );
[f6d7e0f]	776	newObj->get_type()->get_qualifiers() = Type::Qualifiers(); // TODO: is this right???
[01aeade]	777	stmtsToAdd.push_back( new DeclStmt( noLabels, newObj ) );
	778	UntypedExpr *assign = new UntypedExpr( new NameExpr( "?=?" ) );
	779	assign->get_args().push_back( new VariableExpr( newObj ) );
	780	assign->get_args().push_back( arg );
	781	stmtsToAdd.push_back( new ExprStmt( noLabels, assign ) );
	782	arg = new AddressExpr( new VariableExpr( newObj ) );
	783	} // if
	784	} // if
	785	}
[6c3744e]	786
[b4cd03b7]	787	/// cast parameters to polymorphic functions so that types are replaced with
	788	/// void * if they are type parameters in the formal type.
	789	/// this gets rid of warnings from gcc.
[01aeade]	790	void addCast( Expression &actual, Type formal, const TyVarMap &tyVars ) {
[ea5daeb]	791	if ( getFunctionType( formal ) ) {
	792	Type * newType = formal->clone();
[b4cd03b7]	793	newType = ScrubTyVars::scrub( newType, tyVars );
[01aeade]	794	actual = new CastExpr( actual, newType );
	795	} // if
	796	}
[6c3744e]	797
[01aeade]	798	void Pass1::boxParams( ApplicationExpr appExpr, FunctionType function, std::list< Expression *>::iterator &arg, const TyVarMap &exprTyVars ) {
	799	for ( std::list< DeclarationWithType *>::const_iterator param = function->get_parameters().begin(); param != function->get_parameters().end(); ++param, ++arg ) {
[6c3a988f]	800	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]	801	addCast( arg, (param)->get_type(), exprTyVars );
	802	boxParam( (param)->get_type(), arg, exprTyVars );
	803	} // for
	804	}
[6c3744e]	805
[01aeade]	806	void Pass1::addInferredParams( ApplicationExpr appExpr, FunctionType functionType, std::list< Expression *>::iterator &arg, const TyVarMap &tyVars ) {
	807	std::list< Expression *>::iterator cur = arg;
[8c49c0e]	808	for ( Type::ForallList::iterator tyVar = functionType->get_forall().begin(); tyVar != functionType->get_forall().end(); ++tyVar ) {
[01aeade]	809	for ( std::list< DeclarationWithType >::iterator assert = (tyVar)->get_assertions().begin(); assert != (*tyVar)->get_assertions().end(); ++assert ) {
	810	InferredParams::const_iterator inferParam = appExpr->get_inferParams().find( (*assert)->get_uniqueId() );
[5802a4f]	811	if ( inferParam == appExpr->get_inferParams().end() ) {
	812	std::cerr << "looking for assertion: " << (*assert) << std::endl << appExpr << std::endl;
	813	}
	814	assertf( inferParam != appExpr->get_inferParams().end(), "NOTE: Explicit casts of polymorphic functions to compatible monomorphic functions are currently unsupported" );
[01aeade]	815	Expression *newExpr = inferParam->second.expr->clone();
	816	addCast( newExpr, (*assert)->get_type(), tyVars );
	817	boxParam( (*assert)->get_type(), newExpr, tyVars );
	818	appExpr->get_args().insert( cur, newExpr );
	819	} // for
	820	} // for
	821	}
[6c3744e]	822
[01aeade]	823	void makeRetParm( FunctionType *funcType ) {
	824	DeclarationWithType *retParm = funcType->get_returnVals().front();
[6c3744e]	825
[01aeade]	826	// make a new parameter that is a pointer to the type of the old return value
	827	retParm->set_type( new PointerType( Type::Qualifiers(), retParm->get_type() ) );
	828	funcType->get_parameters().push_front( retParm );
[6c3744e]	829
[01aeade]	830	// we don't need the return value any more
	831	funcType->get_returnVals().clear();
	832	}
[6c3744e]	833
[01aeade]	834	FunctionType makeAdapterType( FunctionType adaptee, const TyVarMap &tyVars ) {
	835	// actually make the adapter type
	836	FunctionType *adapter = adaptee->clone();
[3bb195cb]	837	// if ( ! adapter->get_returnVals().empty() && isPolyType( adapter->get_returnVals().front()->get_type(), tyVars ) ) {
	838	if ( isDynRet( adapter, tyVars ) ) {
[01aeade]	839	makeRetParm( adapter );
	840	} // if
[68fe077a]	841	adapter->get_parameters().push_front( new ObjectDecl( "", Type::StorageClasses(), LinkageSpec::C, 0, new PointerType( Type::Qualifiers(), new FunctionType( Type::Qualifiers(), true ) ), 0 ) );
[01aeade]	842	return adapter;
	843	}
[6c3744e]	844
[01aeade]	845	Expression makeAdapterArg( DeclarationWithType param, DeclarationWithType arg, DeclarationWithType realParam, const TyVarMap &tyVars ) {
	846	assert( param );
	847	assert( arg );
[ffad73a]	848	if ( isPolyType( realParam->get_type(), tyVars ) ) {
[30aeb27]	849	if ( ! isPolyType( arg->get_type() ) ) {
[e56cfdb0]	850	UntypedExpr deref = new UntypedExpr( new NameExpr( "?" ) );
	851	deref->get_args().push_back( new CastExpr( new VariableExpr( param ), new PointerType( Type::Qualifiers(), arg->get_type()->clone() ) ) );
[906e24d]	852	deref->set_result( arg->get_type()->clone() );
[e56cfdb0]	853	return deref;
	854	} // if
[01aeade]	855	} // if
	856	return new VariableExpr( param );
	857	}
[6c3744e]	858
[01aeade]	859	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 ) {
	860	UniqueName paramNamer( "_p" );
	861	for ( ; param != paramEnd; ++param, ++arg, ++realParam ) {
	862	if ( (*param)->get_name() == "" ) {
	863	(*param)->set_name( paramNamer.newName() );
	864	(*param)->set_linkage( LinkageSpec::C );
	865	} // if
	866	adapteeApp->get_args().push_back( makeAdapterArg( param, arg, *realParam, tyVars ) );
	867	} // for
	868	}
[6c3744e]	869
[01aeade]	870	FunctionDecl Pass1::makeAdapter( FunctionType adaptee, FunctionType *realType, const std::string &mangleName, const TyVarMap &tyVars ) {
	871	FunctionType *adapterType = makeAdapterType( adaptee, tyVars );
	872	adapterType = ScrubTyVars::scrub( adapterType, tyVars );
	873	DeclarationWithType *adapteeDecl = adapterType->get_parameters().front();
	874	adapteeDecl->set_name( "_adaptee" );
	875	ApplicationExpr *adapteeApp = new ApplicationExpr( new CastExpr( new VariableExpr( adapteeDecl ), new PointerType( Type::Qualifiers(), realType ) ) );
	876	Statement *bodyStmt;
[ae63a18]	877
[8c49c0e]	878	Type::ForallList::iterator tyArg = realType->get_forall().begin();
	879	Type::ForallList::iterator tyParam = adapterType->get_forall().begin();
	880	Type::ForallList::iterator realTyParam = adaptee->get_forall().begin();
[01aeade]	881	for ( ; tyParam != adapterType->get_forall().end(); ++tyArg, ++tyParam, ++realTyParam ) {
	882	assert( tyArg != realType->get_forall().end() );
	883	std::list< DeclarationWithType >::iterator assertArg = (tyArg)->get_assertions().begin();
	884	std::list< DeclarationWithType >::iterator assertParam = (tyParam)->get_assertions().begin();
	885	std::list< DeclarationWithType >::iterator realAssertParam = (realTyParam)->get_assertions().begin();
	886	for ( ; assertParam != (*tyParam)->get_assertions().end(); ++assertArg, ++assertParam, ++realAssertParam ) {
	887	assert( assertArg != (*tyArg)->get_assertions().end() );
	888	adapteeApp->get_args().push_back( makeAdapterArg( assertParam, assertArg, *realAssertParam, tyVars ) );
	889	} // for
	890	} // for
[ae63a18]	891
[01aeade]	892	std::list< DeclarationWithType *>::iterator arg = realType->get_parameters().begin();
	893	std::list< DeclarationWithType *>::iterator param = adapterType->get_parameters().begin();
	894	std::list< DeclarationWithType *>::iterator realParam = adaptee->get_parameters().begin();
[cc3528f]	895	param++; // skip adaptee parameter in the adapter type
[01aeade]	896	if ( realType->get_returnVals().empty() ) {
[cc3528f]	897	// void return
[01aeade]	898	addAdapterParams( adapteeApp, arg, param, adapterType->get_parameters().end(), realParam, tyVars );
	899	bodyStmt = new ExprStmt( noLabels, adapteeApp );
[3bb195cb]	900	// } else if ( isPolyType( adaptee->get_returnVals().front()->get_type(), tyVars ) ) {
	901	} else if ( isDynType( adaptee->get_returnVals().front()->get_type(), tyVars ) ) {
[cc3528f]	902	// return type T
[01aeade]	903	if ( (*param)->get_name() == "" ) {
	904	(*param)->set_name( "_ret" );
	905	(*param)->set_linkage( LinkageSpec::C );
	906	} // if
	907	UntypedExpr *assign = new UntypedExpr( new NameExpr( "?=?" ) );
[c10ee66]	908	UntypedExpr deref = UntypedExpr::createDeref( new CastExpr( new VariableExpr( param++ ), new PointerType( Type::Qualifiers(), realType->get_returnVals().front()->get_type()->clone() ) ) );
[01aeade]	909	assign->get_args().push_back( deref );
	910	addAdapterParams( adapteeApp, arg, param, adapterType->get_parameters().end(), realParam, tyVars );
	911	assign->get_args().push_back( adapteeApp );
	912	bodyStmt = new ExprStmt( noLabels, assign );
	913	} else {
	914	// adapter for a function that returns a monomorphic value
	915	addAdapterParams( adapteeApp, arg, param, adapterType->get_parameters().end(), realParam, tyVars );
	916	bodyStmt = new ReturnStmt( noLabels, adapteeApp );
	917	} // if
	918	CompoundStmt *adapterBody = new CompoundStmt( noLabels );
	919	adapterBody->get_kids().push_back( bodyStmt );
	920	std::string adapterName = makeAdapterName( mangleName );
[68fe077a]	921	return new FunctionDecl( adapterName, Type::StorageClasses(), LinkageSpec::C, adapterType, adapterBody );
[01aeade]	922	}
[6c3744e]	923
[c29d9ce]	924	void Pass1::passAdapters( ApplicationExpr * appExpr, FunctionType * functionType, const TyVarMap & exprTyVars ) {
[e497c1d]	925	// collect a list of function types passed as parameters or implicit parameters (assertions)
[01aeade]	926	std::list< DeclarationWithType *> &paramList = functionType->get_parameters();
	927	std::list< FunctionType *> functions;
[8c49c0e]	928	for ( Type::ForallList::iterator tyVar = functionType->get_forall().begin(); tyVar != functionType->get_forall().end(); ++tyVar ) {
[01aeade]	929	for ( std::list< DeclarationWithType >::iterator assert = (tyVar)->get_assertions().begin(); assert != (*tyVar)->get_assertions().end(); ++assert ) {
	930	findFunction( (*assert)->get_type(), functions, exprTyVars, needsAdapter );
	931	} // for
	932	} // for
	933	for ( std::list< DeclarationWithType *>::iterator arg = paramList.begin(); arg != paramList.end(); ++arg ) {
	934	findFunction( (*arg)->get_type(), functions, exprTyVars, needsAdapter );
	935	} // for
[e497c1d]	936
[e56cfdb0]	937	// parameter function types for which an appropriate adapter has been generated. we cannot use the types
	938	// after applying substitutions, since two different parameter types may be unified to the same type
[01aeade]	939	std::set< std::string > adaptersDone;
[e497c1d]	940
[01aeade]	941	for ( std::list< FunctionType *>::iterator funType = functions.begin(); funType != functions.end(); ++funType ) {
[c29d9ce]	942	FunctionType originalFunction = (funType)->clone();
[01aeade]	943	FunctionType realFunction = (funType)->clone();
	944	std::string mangleName = SymTab::Mangler::mangle( realFunction );
[e497c1d]	945
[e56cfdb0]	946	// only attempt to create an adapter or pass one as a parameter if we haven't already done so for this
	947	// pre-substitution parameter function type.
[01aeade]	948	if ( adaptersDone.find( mangleName ) == adaptersDone.end() ) {
[e497c1d]	949	adaptersDone.insert( adaptersDone.begin(), mangleName );
[ae63a18]	950
[e56cfdb0]	951	// apply substitution to type variables to figure out what the adapter's type should look like
[e497c1d]	952	assert( env );
	953	env->apply( realFunction );
[ae63a18]	954	mangleName = SymTab::Mangler::mangle( realFunction );
[bdf1954]	955	mangleName += makePolyMonoSuffix( originalFunction, exprTyVars );
[e497c1d]	956
[6635c74]	957	typedef ScopedMap< std::string, DeclarationWithType* >::iterator AdapterIter;
	958	AdapterIter adapter = adapters.find( mangleName );
[e56cfdb0]	959	if ( adapter == adapters.end() ) {
	960	// adapter has not been created yet in the current scope, so define it
	961	FunctionDecl newAdapter = makeAdapter( funType, realFunction, mangleName, exprTyVars );
[6635c74]	962	std::pair< AdapterIter, bool > answer = adapters.insert( std::pair< std::string, DeclarationWithType *>( mangleName, newAdapter ) );
	963	adapter = answer.first;
[e56cfdb0]	964	stmtsToAdd.push_back( new DeclStmt( noLabels, newAdapter ) );
[c29d9ce]	965	} // if
[e56cfdb0]	966	assert( adapter != adapters.end() );
	967
	968	// add the appropriate adapter as a parameter
	969	appExpr->get_args().push_front( new VariableExpr( adapter->second ) );
[01aeade]	970	} // if
	971	} // for
[e56cfdb0]	972	} // passAdapters
[6c3744e]	973
[78dd0da]	974	Expression makeIncrDecrExpr( ApplicationExpr appExpr, Type *polyType, bool isIncr ) {
[01aeade]	975	NameExpr *opExpr;
	976	if ( isIncr ) {
	977	opExpr = new NameExpr( "?+=?" );
	978	} else {
	979	opExpr = new NameExpr( "?-=?" );
[6c3744e]	980	} // if
[01aeade]	981	UntypedExpr *addAssign = new UntypedExpr( opExpr );
	982	if ( AddressExpr address = dynamic_cast< AddressExpr >( appExpr->get_args().front() ) ) {
	983	addAssign->get_args().push_back( address->get_arg() );
	984	} else {
	985	addAssign->get_args().push_back( appExpr->get_args().front() );
[6c3744e]	986	} // if
[adc6781]	987	addAssign->get_args().push_back( new NameExpr( sizeofName( mangleType( polyType ) ) ) );
[906e24d]	988	addAssign->set_result( appExpr->get_result()->clone() );
[01aeade]	989	if ( appExpr->get_env() ) {
	990	addAssign->set_env( appExpr->get_env() );
[6c3744e]	991	appExpr->set_env( 0 );
	992	} // if
[01aeade]	993	appExpr->get_args().clear();
	994	delete appExpr;
	995	return addAssign;
	996	}
	997
	998	Expression Pass1::handleIntrinsics( ApplicationExpr appExpr ) {
	999	if ( VariableExpr varExpr = dynamic_cast< VariableExpr >( appExpr->get_function() ) ) {
	1000	if ( varExpr->get_var()->get_linkage() == LinkageSpec::Intrinsic ) {
	1001	if ( varExpr->get_var()->get_name() == "?[?]" ) {
[906e24d]	1002	assert( appExpr->has_result() );
[01aeade]	1003	assert( appExpr->get_args().size() == 2 );
[906e24d]	1004	Type *baseType1 = isPolyPtr( appExpr->get_args().front()->get_result(), scopeTyVars, env );
	1005	Type *baseType2 = isPolyPtr( appExpr->get_args().back()->get_result(), scopeTyVars, env );
[ae63a18]	1006	assert( ! baseType1 \|\| ! baseType2 ); // the arguments cannot both be polymorphic pointers
[01aeade]	1007	UntypedExpr *ret = 0;
[ae63a18]	1008	if ( baseType1 \|\| baseType2 ) { // one of the arguments is a polymorphic pointer
[01aeade]	1009	ret = new UntypedExpr( new NameExpr( "?+?" ) );
	1010	} // if
[ffad73a]	1011	if ( baseType1 ) {
[01aeade]	1012	UntypedExpr multiply = new UntypedExpr( new NameExpr( "??" ) );
	1013	multiply->get_args().push_back( appExpr->get_args().back() );
[adc6781]	1014	multiply->get_args().push_back( new SizeofExpr( baseType1->clone() ) );
[01aeade]	1015	ret->get_args().push_back( appExpr->get_args().front() );
	1016	ret->get_args().push_back( multiply );
[ffad73a]	1017	} else if ( baseType2 ) {
[01aeade]	1018	UntypedExpr multiply = new UntypedExpr( new NameExpr( "??" ) );
	1019	multiply->get_args().push_back( appExpr->get_args().front() );
[adc6781]	1020	multiply->get_args().push_back( new SizeofExpr( baseType2->clone() ) );
[01aeade]	1021	ret->get_args().push_back( multiply );
	1022	ret->get_args().push_back( appExpr->get_args().back() );
	1023	} // if
[ffad73a]	1024	if ( baseType1 \|\| baseType2 ) {
[906e24d]	1025	ret->set_result( appExpr->get_result()->clone() );
[01aeade]	1026	if ( appExpr->get_env() ) {
	1027	ret->set_env( appExpr->get_env() );
	1028	appExpr->set_env( 0 );
	1029	} // if
	1030	appExpr->get_args().clear();
	1031	delete appExpr;
	1032	return ret;
	1033	} // if
	1034	} else if ( varExpr->get_var()->get_name() == "*?" ) {
[906e24d]	1035	assert( appExpr->has_result() );
[01aeade]	1036	assert( ! appExpr->get_args().empty() );
[906e24d]	1037	if ( isPolyType( appExpr->get_result(), scopeTyVars, env ) ) {
[01aeade]	1038	Expression *ret = appExpr->get_args().front();
[906e24d]	1039	delete ret->get_result();
	1040	ret->set_result( appExpr->get_result()->clone() );
[01aeade]	1041	if ( appExpr->get_env() ) {
	1042	ret->set_env( appExpr->get_env() );
	1043	appExpr->set_env( 0 );
	1044	} // if
	1045	appExpr->get_args().clear();
	1046	delete appExpr;
	1047	return ret;
	1048	} // if
	1049	} else if ( varExpr->get_var()->get_name() == "?++" \|\| varExpr->get_var()->get_name() == "?--" ) {
[906e24d]	1050	assert( appExpr->has_result() );
[01aeade]	1051	assert( appExpr->get_args().size() == 1 );
[906e24d]	1052	if ( Type *baseType = isPolyPtr( appExpr->get_result(), scopeTyVars, env ) ) {
	1053	Type *tempType = appExpr->get_result()->clone();
[01aeade]	1054	if ( env ) {
	1055	env->apply( tempType );
	1056	} // if
	1057	ObjectDecl *newObj = makeTemporary( tempType );
	1058	VariableExpr *tempExpr = new VariableExpr( newObj );
	1059	UntypedExpr *assignExpr = new UntypedExpr( new NameExpr( "?=?" ) );
	1060	assignExpr->get_args().push_back( tempExpr->clone() );
	1061	if ( AddressExpr address = dynamic_cast< AddressExpr >( appExpr->get_args().front() ) ) {
	1062	assignExpr->get_args().push_back( address->get_arg()->clone() );
	1063	} else {
	1064	assignExpr->get_args().push_back( appExpr->get_args().front()->clone() );
	1065	} // if
[ffad73a]	1066	CommaExpr *firstComma = new CommaExpr( assignExpr, makeIncrDecrExpr( appExpr, baseType, varExpr->get_var()->get_name() == "?++" ) );
[01aeade]	1067	return new CommaExpr( firstComma, tempExpr );
	1068	} // if
	1069	} else if ( varExpr->get_var()->get_name() == "++?" \|\| varExpr->get_var()->get_name() == "--?" ) {
[906e24d]	1070	assert( appExpr->has_result() );
[01aeade]	1071	assert( appExpr->get_args().size() == 1 );
[906e24d]	1072	if ( Type *baseType = isPolyPtr( appExpr->get_result(), scopeTyVars, env ) ) {
[ffad73a]	1073	return makeIncrDecrExpr( appExpr, baseType, varExpr->get_var()->get_name() == "++?" );
[01aeade]	1074	} // if
	1075	} else if ( varExpr->get_var()->get_name() == "?+?" \|\| varExpr->get_var()->get_name() == "?-?" ) {
[906e24d]	1076	assert( appExpr->has_result() );
[01aeade]	1077	assert( appExpr->get_args().size() == 2 );
[906e24d]	1078	Type *baseType1 = isPolyPtr( appExpr->get_args().front()->get_result(), scopeTyVars, env );
	1079	Type *baseType2 = isPolyPtr( appExpr->get_args().back()->get_result(), scopeTyVars, env );
[ffad73a]	1080	if ( baseType1 && baseType2 ) {
[01aeade]	1081	UntypedExpr *divide = new UntypedExpr( new NameExpr( "?/?" ) );
	1082	divide->get_args().push_back( appExpr );
[adc6781]	1083	divide->get_args().push_back( new SizeofExpr( baseType1->clone() ) );
[906e24d]	1084	divide->set_result( appExpr->get_result()->clone() );
[01aeade]	1085	if ( appExpr->get_env() ) {
	1086	divide->set_env( appExpr->get_env() );
	1087	appExpr->set_env( 0 );
	1088	} // if
	1089	return divide;
[ffad73a]	1090	} else if ( baseType1 ) {
[01aeade]	1091	UntypedExpr multiply = new UntypedExpr( new NameExpr( "??" ) );
	1092	multiply->get_args().push_back( appExpr->get_args().back() );
[adc6781]	1093	multiply->get_args().push_back( new SizeofExpr( baseType1->clone() ) );
[01aeade]	1094	appExpr->get_args().back() = multiply;
[ffad73a]	1095	} else if ( baseType2 ) {
[01aeade]	1096	UntypedExpr multiply = new UntypedExpr( new NameExpr( "??" ) );
	1097	multiply->get_args().push_back( appExpr->get_args().front() );
[adc6781]	1098	multiply->get_args().push_back( new SizeofExpr( baseType2->clone() ) );
[01aeade]	1099	appExpr->get_args().front() = multiply;
	1100	} // if
	1101	} else if ( varExpr->get_var()->get_name() == "?+=?" \|\| varExpr->get_var()->get_name() == "?-=?" ) {
[906e24d]	1102	assert( appExpr->has_result() );
[01aeade]	1103	assert( appExpr->get_args().size() == 2 );
[906e24d]	1104	Type *baseType = isPolyPtr( appExpr->get_result(), scopeTyVars, env );
[ffad73a]	1105	if ( baseType ) {
[01aeade]	1106	UntypedExpr multiply = new UntypedExpr( new NameExpr( "??" ) );
	1107	multiply->get_args().push_back( appExpr->get_args().back() );
[adc6781]	1108	multiply->get_args().push_back( new SizeofExpr( baseType->clone() ) );
[01aeade]	1109	appExpr->get_args().back() = multiply;
	1110	} // if
	1111	} // if
	1112	return appExpr;
	1113	} // if
[6c3744e]	1114	} // if
[01aeade]	1115	return 0;
	1116	}
[6c3744e]	1117
[01aeade]	1118	Expression Pass1::mutate( ApplicationExpr appExpr ) {
[e56cfdb0]	1119	// std::cerr << "mutate appExpr: ";
	1120	// for ( TyVarMap::iterator i = scopeTyVars.begin(); i != scopeTyVars.end(); ++i ) {
	1121	// std::cerr << i->first << " ";
	1122	// }
	1123	// std::cerr << "\n";
[01aeade]	1124	appExpr->get_function()->acceptMutator( *this );
	1125	mutateAll( appExpr->get_args(), *this );
[ae63a18]	1126
[906e24d]	1127	assert( appExpr->get_function()->has_result() );
	1128	PointerType pointer = safe_dynamic_cast< PointerType >( appExpr->get_function()->get_result() );
	1129	FunctionType function = safe_dynamic_cast< FunctionType >( pointer->get_base() );
[ae63a18]	1130
[01aeade]	1131	if ( Expression *newExpr = handleIntrinsics( appExpr ) ) {
	1132	return newExpr;
	1133	} // if
[ae63a18]	1134
[01aeade]	1135	Expression *ret = appExpr;
[ae63a18]	1136
[01aeade]	1137	std::list< Expression *>::iterator arg = appExpr->get_args().begin();
	1138	std::list< Expression *>::iterator paramBegin = appExpr->get_args().begin();
[ae63a18]	1139
[2c57025]	1140	TyVarMap exprTyVars( TypeDecl::Data{} );
[5802a4f]	1141	makeTyVarMap( function, exprTyVars ); // xxx - should this take into account the variables already bound in scopeTyVars (i.e. remove them from exprTyVars?)
[3bb195cb]	1142	ReferenceToType *dynRetType = isDynRet( function, exprTyVars );
[5c52b06]	1143
[b940dc71]	1144	// 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
	1145	// passTypeVars needs to know the program-text return type (i.e. the distinction between _conc_T30 and T3(int))
	1146	// concRetType may not be a good name in one or both of these places. A more appropriate name change is welcome.
[3bb195cb]	1147	if ( dynRetType ) {
[b940dc71]	1148	Type *concRetType = appExpr->get_result()->isVoid() ? nullptr : appExpr->get_result();
[33a7b6d]	1149	ret = addDynRetParam( appExpr, function, concRetType, arg ); // xxx - used to use dynRetType instead of concRetType
[5802a4f]	1150	} else if ( needsAdapter( function, scopeTyVars ) && ! needsAdapter( function, exprTyVars) ) { // xxx - exprTyVars is used above...?
	1151	// 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.
	1152
[e56cfdb0]	1153	// std::cerr << "needs adapter: ";
[2e3a379]	1154	// printTyVarMap( std::cerr, scopeTyVars );
	1155	// std::cerr << *env << std::endl;
[01aeade]	1156	// change the application so it calls the adapter rather than the passed function
	1157	ret = applyAdapter( appExpr, function, arg, scopeTyVars );
	1158	} // if
	1159	arg = appExpr->get_args().begin();
[ae63a18]	1160
[b940dc71]	1161	Type *concRetType = replaceWithConcrete( appExpr, dynRetType );
[5802a4f]	1162	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]	1163	addInferredParams( appExpr, function, arg, exprTyVars );
[51b7345]	1164
[01aeade]	1165	arg = paramBegin;
[ae63a18]	1166
[01aeade]	1167	boxParams( appExpr, function, arg, exprTyVars );
	1168	passAdapters( appExpr, function, exprTyVars );
[6c3744e]	1169
[01aeade]	1170	return ret;
	1171	}
[6c3744e]	1172
[01aeade]	1173	Expression Pass1::mutate( UntypedExpr expr ) {
[906e24d]	1174	if ( expr->has_result() && isPolyType( expr->get_result(), scopeTyVars, env ) ) {
[01aeade]	1175	if ( NameExpr name = dynamic_cast< NameExpr >( expr->get_function() ) ) {
	1176	if ( name->get_name() == "*?" ) {
	1177	Expression *ret = expr->get_args().front();
	1178	expr->get_args().clear();
	1179	delete expr;
	1180	return ret->acceptMutator( *this );
	1181	} // if
	1182	} // if
	1183	} // if
	1184	return PolyMutator::mutate( expr );
	1185	}
[6c3744e]	1186
[01aeade]	1187	Expression Pass1::mutate( AddressExpr addrExpr ) {
[906e24d]	1188	assert( addrExpr->get_arg()->has_result() && ! addrExpr->get_arg()->get_result()->isVoid() );
[cf16f94]	1189
	1190	bool needs = false;
	1191	if ( UntypedExpr expr = dynamic_cast< UntypedExpr >( addrExpr->get_arg() ) ) {
[906e24d]	1192	if ( expr->has_result() && isPolyType( expr->get_result(), scopeTyVars, env ) ) {
[cf16f94]	1193	if ( NameExpr name = dynamic_cast< NameExpr >( expr->get_function() ) ) {
	1194	if ( name->get_name() == "*?" ) {
	1195	if ( ApplicationExpr * appExpr = dynamic_cast< ApplicationExpr * >( expr->get_args().front() ) ) {
[906e24d]	1196	assert( appExpr->get_function()->has_result() );
	1197	PointerType pointer = safe_dynamic_cast< PointerType >( appExpr->get_function()->get_result() );
	1198	FunctionType function = safe_dynamic_cast< FunctionType >( pointer->get_base() );
[cf16f94]	1199	needs = needsAdapter( function, scopeTyVars );
	1200	} // if
	1201	} // if
	1202	} // if
	1203	} // if
	1204	} // if
[fea7ca7]	1205	// isPolyType check needs to happen before mutating addrExpr arg, so pull it forward
	1206	// out of the if condition.
[906e24d]	1207	bool polytype = isPolyType( addrExpr->get_arg()->get_result(), scopeTyVars, env );
[01aeade]	1208	addrExpr->set_arg( mutateExpression( addrExpr->get_arg() ) );
[fea7ca7]	1209	if ( polytype \|\| needs ) {
[01aeade]	1210	Expression *ret = addrExpr->get_arg();
[906e24d]	1211	delete ret->get_result();
	1212	ret->set_result( addrExpr->get_result()->clone() );
[01aeade]	1213	addrExpr->set_arg( 0 );
	1214	delete addrExpr;
	1215	return ret;
	1216	} else {
	1217	return addrExpr;
	1218	} // if
	1219	}
[6c3744e]	1220
[5802a4f]	1221	Statement * Pass1::mutate( ReturnStmt *returnStmt ) {
[cf16f94]	1222	if ( retval && returnStmt->get_expr() ) {
[906e24d]	1223	assert( returnStmt->get_expr()->has_result() && ! returnStmt->get_expr()->get_result()->isVoid() );
[5802a4f]	1224	delete returnStmt->get_expr();
[cf16f94]	1225	returnStmt->set_expr( 0 );
[01aeade]	1226	} else {
[cf16f94]	1227	returnStmt->set_expr( mutateExpression( returnStmt->get_expr() ) );
[01aeade]	1228	} // if
[cf16f94]	1229	return returnStmt;
[01aeade]	1230	}
[6c3744e]	1231
[01aeade]	1232	Type * Pass1::mutate( PointerType *pointerType ) {
[6f49cdf]	1233	scopeTyVars.beginScope();
[01aeade]	1234	makeTyVarMap( pointerType, scopeTyVars );
[ae63a18]	1235
[01aeade]	1236	Type *ret = Mutator::mutate( pointerType );
[ae63a18]	1237
[6f49cdf]	1238	scopeTyVars.endScope();
[01aeade]	1239	return ret;
	1240	}
[6c3744e]	1241
[01aeade]	1242	Type * Pass1::mutate( FunctionType *functionType ) {
[6f49cdf]	1243	scopeTyVars.beginScope();
[01aeade]	1244	makeTyVarMap( functionType, scopeTyVars );
[ae63a18]	1245
[01aeade]	1246	Type *ret = Mutator::mutate( functionType );
[ae63a18]	1247
[6f49cdf]	1248	scopeTyVars.endScope();
[01aeade]	1249	return ret;
	1250	}
[51b7345]	1251
[01aeade]	1252	void Pass1::doBeginScope() {
[6635c74]	1253	adapters.beginScope();
[01aeade]	1254	}
[b1a6d6b]	1255
[01aeade]	1256	void Pass1::doEndScope() {
[6635c74]	1257	adapters.endScope();
[01aeade]	1258	}
[51b7345]	1259
	1260	////////////////////////////////////////// Pass2 ////////////////////////////////////////////////////
	1261
[01aeade]	1262	void Pass2::addAdapters( FunctionType *functionType ) {
	1263	std::list< DeclarationWithType *> &paramList = functionType->get_parameters();
	1264	std::list< FunctionType *> functions;
	1265	for ( std::list< DeclarationWithType *>::iterator arg = paramList.begin(); arg != paramList.end(); ++arg ) {
	1266	Type orig = (arg)->get_type();
	1267	findAndReplaceFunction( orig, functions, scopeTyVars, needsAdapter );
	1268	(*arg)->set_type( orig );
	1269	}
	1270	std::set< std::string > adaptersDone;
	1271	for ( std::list< FunctionType *>::iterator funType = functions.begin(); funType != functions.end(); ++funType ) {
[bdf1954]	1272	std::string mangleName = mangleAdapterName( *funType, scopeTyVars );
[01aeade]	1273	if ( adaptersDone.find( mangleName ) == adaptersDone.end() ) {
	1274	std::string adapterName = makeAdapterName( mangleName );
[68fe077a]	1275	paramList.push_front( new ObjectDecl( adapterName, Type::StorageClasses(), LinkageSpec::C, 0, new PointerType( Type::Qualifiers(), makeAdapterType( *funType, scopeTyVars ) ), 0 ) );
[01aeade]	1276	adaptersDone.insert( adaptersDone.begin(), mangleName );
	1277	}
	1278	}
[5f6c42c]	1279	// deleteAll( functions );
[01aeade]	1280	}
[6c3744e]	1281
[01aeade]	1282	template< typename DeclClass >
	1283	DeclClass * Pass2::handleDecl( DeclClass decl, Type type ) {
[dd0c97b]	1284	DeclClass ret = static_cast< DeclClass >( Parent::mutate( decl ) );
[6c3744e]	1285
[01aeade]	1286	return ret;
	1287	}
[6c3744e]	1288
[cce9429]	1289	/// determines if `pref` is a prefix of `str`
	1290	bool isPrefix( const std::string & str, const std::string & pref ) {
	1291	if ( pref.size() > str.size() ) return false;
	1292	auto its = std::mismatch( pref.begin(), pref.end(), str.begin() );
	1293	return its.first == pref.end();
	1294	}
	1295
[01aeade]	1296	DeclarationWithType * Pass2::mutate( FunctionDecl *functionDecl ) {
[cce9429]	1297	functionDecl = safe_dynamic_cast< FunctionDecl * > ( handleDecl( functionDecl, functionDecl->get_functionType() ) );
	1298	FunctionType * ftype = functionDecl->get_functionType();
	1299	if ( ! ftype->get_returnVals().empty() && functionDecl->get_statements() ) {
[f5392c1]	1300	if ( functionDecl->get_name() != "?=?" && ! isPrefix( functionDecl->get_name(), "_thunk" ) && ! isPrefix( functionDecl->get_name(), "_adapter" ) ) { // xxx - remove check for ?=? once reference types are in; remove check for prefix once thunks properly use ctor/dtors
[cce9429]	1301	assert( ftype->get_returnVals().size() == 1 );
	1302	DeclarationWithType * retval = ftype->get_returnVals().front();
	1303	if ( retval->get_name() == "" ) {
	1304	retval->set_name( "_retval" );
	1305	}
	1306	functionDecl->get_statements()->get_kids().push_front( new DeclStmt( noLabels, retval ) );
	1307	DeclarationWithType * newRet = retval->clone(); // for ownership purposes
	1308	ftype->get_returnVals().front() = newRet;
	1309	}
	1310	}
[064cb18]	1311	// errors should have been caught by this point, remove initializers from parameters to allow correct codegen of default arguments
	1312	for ( Declaration * param : functionDecl->get_functionType()->get_parameters() ) {
	1313	if ( ObjectDecl * obj = dynamic_cast< ObjectDecl * >( param ) ) {
	1314	delete obj->get_init();
	1315	obj->set_init( nullptr );
	1316	}
	1317	}
[cce9429]	1318	return functionDecl;
[01aeade]	1319	}
[6c3744e]	1320
[01aeade]	1321	ObjectDecl * Pass2::mutate( ObjectDecl *objectDecl ) {
	1322	return handleDecl( objectDecl, objectDecl->get_type() );
	1323	}
[6c3744e]	1324
[dd0c97b]	1325	template< typename AggDecl >
	1326	AggDecl * Pass2::handleAggDecl( AggDecl * aggDecl ) {
	1327	// prevent tyVars from leaking into containing scope
	1328	scopeTyVars.beginScope();
	1329	Parent::mutate( aggDecl );
	1330	scopeTyVars.endScope();
	1331	return aggDecl;
	1332	}
	1333
	1334	StructDecl * Pass2::mutate( StructDecl *aggDecl ) {
	1335	return handleAggDecl( aggDecl );
	1336	}
	1337
	1338	UnionDecl * Pass2::mutate( UnionDecl *aggDecl ) {
	1339	return handleAggDecl( aggDecl );
	1340	}
	1341
[01aeade]	1342	TypeDecl * Pass2::mutate( TypeDecl *typeDecl ) {
[2c57025]	1343	addToTyVarMap( typeDecl, scopeTyVars );
[01aeade]	1344	if ( typeDecl->get_base() ) {
	1345	return handleDecl( typeDecl, typeDecl->get_base() );
	1346	} else {
[dd0c97b]	1347	return Parent::mutate( typeDecl );
[01aeade]	1348	}
	1349	}
[6c3744e]	1350
[01aeade]	1351	TypedefDecl * Pass2::mutate( TypedefDecl *typedefDecl ) {
	1352	return handleDecl( typedefDecl, typedefDecl->get_base() );
	1353	}
[6c3744e]	1354
[01aeade]	1355	Type * Pass2::mutate( PointerType *pointerType ) {
[6f49cdf]	1356	scopeTyVars.beginScope();
[01aeade]	1357	makeTyVarMap( pointerType, scopeTyVars );
[ae63a18]	1358
[dd0c97b]	1359	Type *ret = Parent::mutate( pointerType );
[ae63a18]	1360
[6f49cdf]	1361	scopeTyVars.endScope();
[01aeade]	1362	return ret;
	1363	}
[6c3744e]	1364
[01aeade]	1365	Type Pass2::mutate( FunctionType funcType ) {
[6f49cdf]	1366	scopeTyVars.beginScope();
[01aeade]	1367	makeTyVarMap( funcType, scopeTyVars );
[7754cde]	1368
	1369	// move polymorphic return type to parameter list
[3bb195cb]	1370	if ( isDynRet( funcType ) ) {
[d9fa60a]	1371	ObjectDecl ret = safe_dynamic_cast< ObjectDecl >( funcType->get_returnVals().front() );
[01aeade]	1372	ret->set_type( new PointerType( Type::Qualifiers(), ret->get_type() ) );
	1373	funcType->get_parameters().push_front( ret );
	1374	funcType->get_returnVals().pop_front();
[d9fa60a]	1375	ret->set_init( nullptr ); // xxx - memory leak?
[01aeade]	1376	}
[7754cde]	1377
	1378	// add size/align and assertions for type parameters to parameter list
[01aeade]	1379	std::list< DeclarationWithType *>::iterator last = funcType->get_parameters().begin();
	1380	std::list< DeclarationWithType *> inferredParams;
[68fe077a]	1381	ObjectDecl newObj( "", Type::StorageClasses(), LinkageSpec::C, 0, new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt ), 0 );
	1382	ObjectDecl newPtr( "", Type::StorageClasses(), LinkageSpec::C, 0,
[05d47278]	1383	new PointerType( Type::Qualifiers(), new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt ) ), 0 );
[8c49c0e]	1384	for ( Type::ForallList::const_iterator tyParm = funcType->get_forall().begin(); tyParm != funcType->get_forall().end(); ++tyParm ) {
[db0b3ce]	1385	ObjectDecl sizeParm, alignParm;
	1386	// add all size and alignment parameters to parameter list
[2c57025]	1387	if ( (*tyParm)->isComplete() ) {
[78dd0da]	1388	TypeInstType parmType( Type::Qualifiers(), (tyParm)->get_name(), tyParm );
[adc6781]	1389	std::string parmName = mangleType( &parmType );
[ae63a18]	1390
[78dd0da]	1391	sizeParm = newObj.clone();
[adc6781]	1392	sizeParm->set_name( sizeofName( parmName ) );
[db0b3ce]	1393	last = funcType->get_parameters().insert( last, sizeParm );
	1394	++last;
[78dd0da]	1395
	1396	alignParm = newObj.clone();
[adc6781]	1397	alignParm->set_name( alignofName( parmName ) );
[db0b3ce]	1398	last = funcType->get_parameters().insert( last, alignParm );
[01aeade]	1399	++last;
	1400	}
[e56cfdb0]	1401	// move all assertions into parameter list
[01aeade]	1402	for ( std::list< DeclarationWithType >::iterator assert = (tyParm)->get_assertions().begin(); assert != (*tyParm)->get_assertions().end(); ++assert ) {
[f8b961b]	1403	// assert = (assert)->acceptMutator( *this );
[01aeade]	1404	inferredParams.push_back( *assert );
	1405	}
	1406	(*tyParm)->get_assertions().clear();
	1407	}
[7754cde]	1408
[5c52b06]	1409	// add size/align for generic parameter types to parameter list
[b18b0b5]	1410	std::set< std::string > seenTypes; // sizeofName for generic types we've seen
[7754cde]	1411	for ( std::list< DeclarationWithType* >::const_iterator fnParm = last; fnParm != funcType->get_parameters().end(); ++fnParm ) {
[4b8f918]	1412	Type polyType = isPolyType( (fnParm)->get_type(), scopeTyVars );
	1413	if ( polyType && ! dynamic_cast< TypeInstType* >( polyType ) ) {
	1414	std::string typeName = mangleType( polyType );
[adc6781]	1415	if ( seenTypes.count( typeName ) ) continue;
[ae63a18]	1416
[05d47278]	1417	ObjectDecl sizeParm, alignParm, *offsetParm;
[7754cde]	1418	sizeParm = newObj.clone();
[adc6781]	1419	sizeParm->set_name( sizeofName( typeName ) );
[7754cde]	1420	last = funcType->get_parameters().insert( last, sizeParm );
	1421	++last;
	1422
	1423	alignParm = newObj.clone();
[adc6781]	1424	alignParm->set_name( alignofName( typeName ) );
[7754cde]	1425	last = funcType->get_parameters().insert( last, alignParm );
	1426	++last;
	1427
[4b8f918]	1428	if ( StructInstType polyBaseStruct = dynamic_cast< StructInstType >( polyType ) ) {
[89173242]	1429	// NOTE zero-length arrays are illegal in C, so empty structs have no offset array
	1430	if ( ! polyBaseStruct->get_baseStruct()->get_members().empty() ) {
	1431	offsetParm = newPtr.clone();
[adc6781]	1432	offsetParm->set_name( offsetofName( typeName ) );
[89173242]	1433	last = funcType->get_parameters().insert( last, offsetParm );
	1434	++last;
	1435	}
[05d47278]	1436	}
	1437
[adc6781]	1438	seenTypes.insert( typeName );
[7754cde]	1439	}
	1440	}
	1441
	1442	// splice assertion parameters into parameter list
[01aeade]	1443	funcType->get_parameters().splice( last, inferredParams );
	1444	addAdapters( funcType );
	1445	mutateAll( funcType->get_returnVals(), *this );
	1446	mutateAll( funcType->get_parameters(), *this );
[ae63a18]	1447
[6f49cdf]	1448	scopeTyVars.endScope();
[01aeade]	1449	return funcType;
	1450	}
[51b7345]	1451
[4b8f918]	1452	////////////////////////////////////////// PolyGenericCalculator ////////////////////////////////////////////////////
[51b7345]	1453
[a0ad7dc]	1454	PolyGenericCalculator::PolyGenericCalculator()
	1455	: Parent(), knownLayouts(), knownOffsets(), bufNamer( "_buf" ) {}
	1456
[aa19ccf]	1457	void PolyGenericCalculator::beginTypeScope( Type *ty ) {
	1458	scopeTyVars.beginScope();
	1459	makeTyVarMap( ty, scopeTyVars );
	1460	}
	1461
	1462	void PolyGenericCalculator::endTypeScope() {
	1463	scopeTyVars.endScope();
	1464	}
[51b7345]	1465
[01aeade]	1466	template< typename DeclClass >
[8a34677]	1467	DeclClass * PolyGenericCalculator::handleDecl( DeclClass decl, Type type ) {
[aa19ccf]	1468	beginTypeScope( type );
[1ba88a0]	1469	// knownLayouts.beginScope();
	1470	// knownOffsets.beginScope();
[ae63a18]	1471
[1ba88a0]	1472	DeclClass ret = static_cast< DeclClass >( Parent::mutate( decl ) );
[6c3744e]	1473
[1ba88a0]	1474	// knownOffsets.endScope();
	1475	// knownLayouts.endScope();
[aa19ccf]	1476	endTypeScope();
[01aeade]	1477	return ret;
	1478	}
[6c3744e]	1479
[8a34677]	1480	ObjectDecl * PolyGenericCalculator::mutate( ObjectDecl *objectDecl ) {
[01aeade]	1481	return handleDecl( objectDecl, objectDecl->get_type() );
	1482	}
[6c3744e]	1483
[8a34677]	1484	DeclarationWithType * PolyGenericCalculator::mutate( FunctionDecl *functionDecl ) {
[1ba88a0]	1485	knownLayouts.beginScope();
	1486	knownOffsets.beginScope();
	1487
	1488	DeclarationWithType * decl = handleDecl( functionDecl, functionDecl->get_functionType() );
	1489	knownOffsets.endScope();
	1490	knownLayouts.endScope();
	1491	return decl;
[01aeade]	1492	}
[6c3744e]	1493
[8a34677]	1494	TypedefDecl * PolyGenericCalculator::mutate( TypedefDecl *typedefDecl ) {
[01aeade]	1495	return handleDecl( typedefDecl, typedefDecl->get_base() );
	1496	}
[6c3744e]	1497
[8a34677]	1498	TypeDecl * PolyGenericCalculator::mutate( TypeDecl *typeDecl ) {
[2c57025]	1499	addToTyVarMap( typeDecl, scopeTyVars );
[1ba88a0]	1500	return Parent::mutate( typeDecl );
[01aeade]	1501	}
[51b7345]	1502
[8a34677]	1503	Type * PolyGenericCalculator::mutate( PointerType *pointerType ) {
[aa19ccf]	1504	beginTypeScope( pointerType );
[ae63a18]	1505
[1ba88a0]	1506	Type *ret = Parent::mutate( pointerType );
[ae63a18]	1507
[aa19ccf]	1508	endTypeScope();
[01aeade]	1509	return ret;
	1510	}
[6c3744e]	1511
[8a34677]	1512	Type * PolyGenericCalculator::mutate( FunctionType *funcType ) {
[aa19ccf]	1513	beginTypeScope( funcType );
[ae63a18]	1514
[8a34677]	1515	// make sure that any type information passed into the function is accounted for
	1516	for ( std::list< DeclarationWithType* >::const_iterator fnParm = funcType->get_parameters().begin(); fnParm != funcType->get_parameters().end(); ++fnParm ) {
	1517	// condition here duplicates that in Pass2::mutate( FunctionType* )
[4b8f918]	1518	Type polyType = isPolyType( (fnParm)->get_type(), scopeTyVars );
	1519	if ( polyType && ! dynamic_cast< TypeInstType* >( polyType ) ) {
	1520	knownLayouts.insert( mangleType( polyType ) );
[8a34677]	1521	}
	1522	}
[70a06f6]	1523
[1ba88a0]	1524	Type *ret = Parent::mutate( funcType );
[ae63a18]	1525
[aa19ccf]	1526	endTypeScope();
[01aeade]	1527	return ret;
[6c3744e]	1528	}
[51b7345]	1529
[8a34677]	1530	Statement PolyGenericCalculator::mutate( DeclStmt declStmt ) {
[01aeade]	1531	if ( ObjectDecl objectDecl = dynamic_cast< ObjectDecl >( declStmt->get_decl() ) ) {
[8a34677]	1532	if ( findGeneric( objectDecl->get_type() ) ) {
[a0ad7dc]	1533	// change initialization of a polymorphic value object to allocate via a VLA
	1534	// (alloca was previously used, but can't be safely used in loops)
[ffad73a]	1535	Type *declType = objectDecl->get_type();
[a0ad7dc]	1536	std::string bufName = bufNamer.newName();
[c10ee66]	1537	ObjectDecl *newBuf = new ObjectDecl( bufName, Type::StorageClasses(), LinkageSpec::C, 0,
	1538	new ArrayType( Type::Qualifiers(), new BasicType( Type::Qualifiers(), BasicType::Kind::Char), new NameExpr( sizeofName( mangleType(declType) ) ),
[a0ad7dc]	1539	true, false, std::list<Attribute>{ new Attribute( std::string{"aligned"}, std::list<Expression>{ new ConstantExpr( Constant::from_int(8) ) } ) } ), 0 );
	1540	stmtsToAdd.push_back( new DeclStmt( noLabels, newBuf ) );
[e01559c]	1541
	1542	delete objectDecl->get_init();
	1543
[a0ad7dc]	1544	objectDecl->set_init( new SingleInit( new NameExpr( bufName ) ) );
[01aeade]	1545	}
	1546	}
[1ba88a0]	1547	return Parent::mutate( declStmt );
[01aeade]	1548	}
[05d47278]	1549
[2a4b088]	1550	/// Finds the member in the base list that matches the given declaration; returns its index, or -1 if not present
	1551	long findMember( DeclarationWithType memberDecl, std::list< Declaration > &baseDecls ) {
	1552	long i = 0;
	1553	for(std::list< Declaration* >::const_iterator decl = baseDecls.begin(); decl != baseDecls.end(); ++decl, ++i ) {
	1554	if ( memberDecl->get_name() != (*decl)->get_name() ) continue;
	1555
	1556	if ( DeclarationWithType declWithType = dynamic_cast< DeclarationWithType >( *decl ) ) {
[bed4d37c]	1557	if ( memberDecl->get_mangleName().empty() \|\| declWithType->get_mangleName().empty()
	1558	\|\| memberDecl->get_mangleName() == declWithType->get_mangleName() ) return i;
[2a4b088]	1559	else continue;
	1560	} else return i;
	1561	}
	1562	return -1;
	1563	}
	1564
	1565	/// Returns an index expression into the offset array for a type
	1566	Expression makeOffsetIndex( Type objectType, long i ) {
	1567	std::stringstream offset_namer;
	1568	offset_namer << i;
	1569	ConstantExpr *fieldIndex = new ConstantExpr( Constant( new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt ), offset_namer.str() ) );
	1570	UntypedExpr *fieldOffset = new UntypedExpr( new NameExpr( "?[?]" ) );
[adc6781]	1571	fieldOffset->get_args().push_back( new NameExpr( offsetofName( mangleType( objectType ) ) ) );
[2a4b088]	1572	fieldOffset->get_args().push_back( fieldIndex );
	1573	return fieldOffset;
	1574	}
	1575
[8a34677]	1576	Expression PolyGenericCalculator::mutate( MemberExpr memberExpr ) {
[05d47278]	1577	// mutate, exiting early if no longer MemberExpr
[1ba88a0]	1578	Expression *expr = Parent::mutate( memberExpr );
[05d47278]	1579	memberExpr = dynamic_cast< MemberExpr* >( expr );
	1580	if ( ! memberExpr ) return expr;
	1581
	1582	// only mutate member expressions for polymorphic types
[8488c715]	1583	int tyDepth;
[c10ee66]	1584	Type *objectType = hasPolyBase( memberExpr->get_aggregate()->get_result(), scopeTyVars, &tyDepth );
[05d47278]	1585	if ( ! objectType ) return memberExpr;
[8a34677]	1586	findGeneric( objectType ); // ensure layout for this type is available
[05d47278]	1587
[ea5daeb]	1588	// replace member expression with dynamically-computed layout expression
[4318107]	1589	Expression *newMemberExpr = 0;
[05d47278]	1590	if ( StructInstType structType = dynamic_cast< StructInstType >( objectType ) ) {
[2a4b088]	1591	// look up offset index
	1592	long i = findMember( memberExpr->get_member(), structType->get_baseStruct()->get_members() );
	1593	if ( i == -1 ) return memberExpr;
[05d47278]	1594
[2a4b088]	1595	// replace member expression with pointer to base plus offset
	1596	UntypedExpr *fieldLoc = new UntypedExpr( new NameExpr( "?+?" ) );
[5802a4f]	1597	Expression * aggr = memberExpr->get_aggregate()->clone();
	1598	delete aggr->get_env(); // xxx - there's a problem with keeping the env for some reason, so for now just get rid of it
	1599	aggr->set_env( nullptr );
	1600	fieldLoc->get_args().push_back( aggr );
[2a4b088]	1601	fieldLoc->get_args().push_back( makeOffsetIndex( objectType, i ) );
[c10ee66]	1602	fieldLoc->set_result( memberExpr->get_result()->clone() );
[4318107]	1603	newMemberExpr = fieldLoc;
[98735ef]	1604	} else if ( dynamic_cast< UnionInstType* >( objectType ) ) {
[c10ee66]	1605	// union members are all at offset zero, so just use the aggregate expr
	1606	Expression * aggr = memberExpr->get_aggregate()->clone();
	1607	delete aggr->get_env(); // xxx - there's a problem with keeping the env for some reason, so for now just get rid of it
	1608	aggr->set_env( nullptr );
	1609	newMemberExpr = aggr;
	1610	newMemberExpr->set_result( memberExpr->get_result()->clone() );
[2a4b088]	1611	} else return memberExpr;
[4318107]	1612	assert( newMemberExpr );
	1613
[4067aa8]	1614	Type *memberType = memberExpr->get_member()->get_type();
	1615	if ( ! isPolyType( memberType, scopeTyVars ) ) {
	1616	// 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
	1617	CastExpr *ptrCastExpr = new CastExpr( newMemberExpr, new PointerType( Type::Qualifiers(), memberType->clone() ) );
[c10ee66]	1618	UntypedExpr *derefExpr = UntypedExpr::createDeref( ptrCastExpr );
[4318107]	1619	newMemberExpr = derefExpr;
	1620	}
	1621
	1622	delete memberExpr;
	1623	return newMemberExpr;
[2a4b088]	1624	}
[05d47278]	1625
[8a34677]	1626	ObjectDecl PolyGenericCalculator::makeVar( const std::string &name, Type type, Initializer *init ) {
[68fe077a]	1627	ObjectDecl *newObj = new ObjectDecl( name, Type::StorageClasses(), LinkageSpec::C, 0, type, init );
[8a34677]	1628	stmtsToAdd.push_back( new DeclStmt( noLabels, newObj ) );
	1629	return newObj;
	1630	}
	1631
	1632	void PolyGenericCalculator::addOtypeParamsToLayoutCall( UntypedExpr layoutCall, const std::list< Type > &otypeParams ) {
	1633	for ( std::list< Type* >::const_iterator param = otypeParams.begin(); param != otypeParams.end(); ++param ) {
	1634	if ( findGeneric( *param ) ) {
	1635	// push size/align vars for a generic parameter back
[adc6781]	1636	std::string paramName = mangleType( *param );
	1637	layoutCall->get_args().push_back( new NameExpr( sizeofName( paramName ) ) );
	1638	layoutCall->get_args().push_back( new NameExpr( alignofName( paramName ) ) );
[8a34677]	1639	} else {
	1640	layoutCall->get_args().push_back( new SizeofExpr( (*param)->clone() ) );
	1641	layoutCall->get_args().push_back( new AlignofExpr( (*param)->clone() ) );
	1642	}
	1643	}
	1644	}
	1645
	1646	/// returns true if any of the otype parameters have a dynamic layout and puts all otype parameters in the output list
	1647	bool findGenericParams( std::list< TypeDecl* > &baseParams, std::list< Expression* > &typeParams, std::list< Type* > &out ) {
	1648	bool hasDynamicLayout = false;
	1649
	1650	std::list< TypeDecl* >::const_iterator baseParam = baseParams.begin();
	1651	std::list< Expression* >::const_iterator typeParam = typeParams.begin();
	1652	for ( ; baseParam != baseParams.end() && typeParam != typeParams.end(); ++baseParam, ++typeParam ) {
	1653	// skip non-otype parameters
[2c57025]	1654	if ( ! (*baseParam)->isComplete() ) continue;
[8a34677]	1655	TypeExpr typeExpr = dynamic_cast< TypeExpr >( *typeParam );
	1656	assert( typeExpr && "all otype parameters should be type expressions" );
	1657
	1658	Type *type = typeExpr->get_type();
	1659	out.push_back( type );
	1660	if ( isPolyType( type ) ) hasDynamicLayout = true;
	1661	}
	1662	assert( baseParam == baseParams.end() && typeParam == typeParams.end() );
	1663
	1664	return hasDynamicLayout;
	1665	}
	1666
	1667	bool PolyGenericCalculator::findGeneric( Type *ty ) {
[c2ad3c9]	1668	ty = replaceTypeInst( ty, env );
[9799ec8]	1669
[8a34677]	1670	if ( TypeInstType typeInst = dynamic_cast< TypeInstType >( ty ) ) {
	1671	if ( scopeTyVars.find( typeInst->get_name() ) != scopeTyVars.end() ) {
	1672	// NOTE assumes here that getting put in the scopeTyVars included having the layout variables set
	1673	return true;
	1674	}
	1675	return false;
	1676	} else if ( StructInstType structTy = dynamic_cast< StructInstType >( ty ) ) {
	1677	// check if this type already has a layout generated for it
[adc6781]	1678	std::string typeName = mangleType( ty );
	1679	if ( knownLayouts.find( typeName ) != knownLayouts.end() ) return true;
[8a34677]	1680
	1681	// check if any of the type parameters have dynamic layout; if none do, this type is (or will be) monomorphized
	1682	std::list< Type* > otypeParams;
	1683	if ( ! findGenericParams( *structTy->get_baseParameters(), structTy->get_parameters(), otypeParams ) ) return false;
	1684
	1685	// insert local variables for layout and generate call to layout function
[adc6781]	1686	knownLayouts.insert( typeName ); // done early so as not to interfere with the later addition of parameters to the layout call
[8a34677]	1687	Type *layoutType = new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt );
	1688
	1689	int n_members = structTy->get_baseStruct()->get_members().size();
	1690	if ( n_members == 0 ) {
	1691	// all empty structs have the same layout - size 1, align 1
[cc3528f]	1692	makeVar( sizeofName( typeName ), layoutType, new SingleInit( new ConstantExpr( Constant::from_ulong( (unsigned long)1 ) ) ) );
	1693	makeVar( alignofName( typeName ), layoutType->clone(), new SingleInit( new ConstantExpr( Constant::from_ulong( (unsigned long)1 ) ) ) );
[8a34677]	1694	// NOTE zero-length arrays are forbidden in C, so empty structs have no offsetof array
	1695	} else {
[adc6781]	1696	ObjectDecl *sizeVar = makeVar( sizeofName( typeName ), layoutType );
	1697	ObjectDecl *alignVar = makeVar( alignofName( typeName ), layoutType->clone() );
[cb4c607]	1698	ObjectDecl *offsetVar = makeVar( offsetofName( typeName ), new ArrayType( Type::Qualifiers(), layoutType->clone(), new ConstantExpr( Constant::from_int( n_members ) ), false, false ) );
[8a34677]	1699
	1700	// generate call to layout function
[adc6781]	1701	UntypedExpr *layoutCall = new UntypedExpr( new NameExpr( layoutofName( structTy->get_baseStruct() ) ) );
[8a34677]	1702	layoutCall->get_args().push_back( new AddressExpr( new VariableExpr( sizeVar ) ) );
	1703	layoutCall->get_args().push_back( new AddressExpr( new VariableExpr( alignVar ) ) );
	1704	layoutCall->get_args().push_back( new VariableExpr( offsetVar ) );
	1705	addOtypeParamsToLayoutCall( layoutCall, otypeParams );
	1706
	1707	stmtsToAdd.push_back( new ExprStmt( noLabels, layoutCall ) );
	1708	}
	1709
	1710	return true;
	1711	} else if ( UnionInstType unionTy = dynamic_cast< UnionInstType >( ty ) ) {
	1712	// check if this type already has a layout generated for it
[adc6781]	1713	std::string typeName = mangleType( ty );
	1714	if ( knownLayouts.find( typeName ) != knownLayouts.end() ) return true;
[8a34677]	1715
	1716	// check if any of the type parameters have dynamic layout; if none do, this type is (or will be) monomorphized
	1717	std::list< Type* > otypeParams;
	1718	if ( ! findGenericParams( *unionTy->get_baseParameters(), unionTy->get_parameters(), otypeParams ) ) return false;
	1719
	1720	// insert local variables for layout and generate call to layout function
[adc6781]	1721	knownLayouts.insert( typeName ); // done early so as not to interfere with the later addition of parameters to the layout call
[8a34677]	1722	Type *layoutType = new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt );
	1723
[adc6781]	1724	ObjectDecl *sizeVar = makeVar( sizeofName( typeName ), layoutType );
	1725	ObjectDecl *alignVar = makeVar( alignofName( typeName ), layoutType->clone() );
[8a34677]	1726
	1727	// generate call to layout function
[adc6781]	1728	UntypedExpr *layoutCall = new UntypedExpr( new NameExpr( layoutofName( unionTy->get_baseUnion() ) ) );
[8a34677]	1729	layoutCall->get_args().push_back( new AddressExpr( new VariableExpr( sizeVar ) ) );
	1730	layoutCall->get_args().push_back( new AddressExpr( new VariableExpr( alignVar ) ) );
	1731	addOtypeParamsToLayoutCall( layoutCall, otypeParams );
	1732
	1733	stmtsToAdd.push_back( new ExprStmt( noLabels, layoutCall ) );
	1734
	1735	return true;
	1736	}
	1737
	1738	return false;
	1739	}
	1740
	1741	Expression PolyGenericCalculator::mutate( SizeofExpr sizeofExpr ) {
	1742	Type *ty = sizeofExpr->get_type();
	1743	if ( findGeneric( ty ) ) {
[adc6781]	1744	Expression *ret = new NameExpr( sizeofName( mangleType( ty ) ) );
[8a34677]	1745	delete sizeofExpr;
	1746	return ret;
	1747	}
	1748	return sizeofExpr;
	1749	}
	1750
	1751	Expression PolyGenericCalculator::mutate( AlignofExpr alignofExpr ) {
	1752	Type *ty = alignofExpr->get_type();
	1753	if ( findGeneric( ty ) ) {
[adc6781]	1754	Expression *ret = new NameExpr( alignofName( mangleType( ty ) ) );
[8a34677]	1755	delete alignofExpr;
	1756	return ret;
	1757	}
	1758	return alignofExpr;
	1759	}
	1760
	1761	Expression PolyGenericCalculator::mutate( OffsetofExpr offsetofExpr ) {
[2a4b088]	1762	// mutate, exiting early if no longer OffsetofExpr
[1ba88a0]	1763	Expression *expr = Parent::mutate( offsetofExpr );
[2a4b088]	1764	offsetofExpr = dynamic_cast< OffsetofExpr* >( expr );
	1765	if ( ! offsetofExpr ) return expr;
	1766
	1767	// only mutate expressions for polymorphic structs/unions
[8a34677]	1768	Type *ty = offsetofExpr->get_type();
	1769	if ( ! findGeneric( ty ) ) return offsetofExpr;
[2a4b088]	1770
	1771	if ( StructInstType structType = dynamic_cast< StructInstType >( ty ) ) {
	1772	// replace offsetof expression by index into offset array
	1773	long i = findMember( offsetofExpr->get_member(), structType->get_baseStruct()->get_members() );
	1774	if ( i == -1 ) return offsetofExpr;
	1775
	1776	Expression *offsetInd = makeOffsetIndex( ty, i );
	1777	delete offsetofExpr;
	1778	return offsetInd;
[5c52b06]	1779	} else if ( dynamic_cast< UnionInstType* >( ty ) ) {
[2a4b088]	1780	// all union members are at offset zero
	1781	delete offsetofExpr;
[ca35c51]	1782	return new ConstantExpr( Constant( new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt ), "0" ) );
[2a4b088]	1783	} else return offsetofExpr;
[05d47278]	1784	}
	1785
[8a34677]	1786	Expression PolyGenericCalculator::mutate( OffsetPackExpr offsetPackExpr ) {
	1787	StructInstType *ty = offsetPackExpr->get_type();
	1788
	1789	Expression *ret = 0;
	1790	if ( findGeneric( ty ) ) {
	1791	// pull offset back from generated type information
[adc6781]	1792	ret = new NameExpr( offsetofName( mangleType( ty ) ) );
[8a34677]	1793	} else {
[adc6781]	1794	std::string offsetName = offsetofName( mangleType( ty ) );
[8a34677]	1795	if ( knownOffsets.find( offsetName ) != knownOffsets.end() ) {
	1796	// use the already-generated offsets for this type
	1797	ret = new NameExpr( offsetName );
	1798	} else {
	1799	knownOffsets.insert( offsetName );
	1800
	1801	std::list< Declaration* > &baseMembers = ty->get_baseStruct()->get_members();
	1802	Type *offsetType = new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt );
	1803
	1804	// build initializer list for offset array
	1805	std::list< Initializer* > inits;
	1806	for ( std::list< Declaration* >::const_iterator member = baseMembers.begin(); member != baseMembers.end(); ++member ) {
	1807	DeclarationWithType *memberDecl;
	1808	if ( DeclarationWithType origMember = dynamic_cast< DeclarationWithType >( *member ) ) {
	1809	memberDecl = origMember->clone();
	1810	} else {
[68fe077a]	1811	memberDecl = new ObjectDecl( (*member)->get_name(), Type::StorageClasses(), LinkageSpec::Cforall, 0, offsetType->clone(), 0 );
[8a34677]	1812	}
	1813	inits.push_back( new SingleInit( new OffsetofExpr( ty->clone(), memberDecl ) ) );
	1814	}
	1815
	1816	// build the offset array and replace the pack with a reference to it
[cb4c607]	1817	ObjectDecl *offsetArray = makeVar( offsetName, new ArrayType( Type::Qualifiers(), offsetType, new ConstantExpr( Constant::from_ulong( baseMembers.size() ) ), false, false ),
[8a34677]	1818	new ListInit( inits ) );
	1819	ret = new VariableExpr( offsetArray );
	1820	}
	1821	}
	1822
	1823	delete offsetPackExpr;
	1824	return ret;
	1825	}
	1826
	1827	void PolyGenericCalculator::doBeginScope() {
	1828	knownLayouts.beginScope();
	1829	knownOffsets.beginScope();
	1830	}
	1831
	1832	void PolyGenericCalculator::doEndScope() {
	1833	knownLayouts.endScope();
[adc6781]	1834	knownOffsets.endScope();
[8a34677]	1835	}
	1836
[05d47278]	1837	////////////////////////////////////////// Pass3 ////////////////////////////////////////////////////
	1838
	1839	template< typename DeclClass >
	1840	DeclClass * Pass3::handleDecl( DeclClass decl, Type type ) {
[6f49cdf]	1841	scopeTyVars.beginScope();
[05d47278]	1842	makeTyVarMap( type, scopeTyVars );
	1843
	1844	DeclClass ret = static_cast< DeclClass >( Mutator::mutate( decl ) );
[5a3ac84]	1845	// ScrubTyVars::scrub( decl, scopeTyVars );
	1846	ScrubTyVars::scrubAll( decl );
[05d47278]	1847
[6f49cdf]	1848	scopeTyVars.endScope();
[05d47278]	1849	return ret;
	1850	}
	1851
	1852	ObjectDecl * Pass3::mutate( ObjectDecl *objectDecl ) {
	1853	return handleDecl( objectDecl, objectDecl->get_type() );
	1854	}
	1855
	1856	DeclarationWithType * Pass3::mutate( FunctionDecl *functionDecl ) {
	1857	return handleDecl( functionDecl, functionDecl->get_functionType() );
	1858	}
	1859
	1860	TypedefDecl * Pass3::mutate( TypedefDecl *typedefDecl ) {
	1861	return handleDecl( typedefDecl, typedefDecl->get_base() );
	1862	}
	1863
	1864	TypeDecl * Pass3::mutate( TypeDecl *typeDecl ) {
	1865	// Initializer *init = 0;
	1866	// std::list< Expression *> designators;
[2c57025]	1867	// addToTyVarMap( typeDecl, scopeTyVars );
[05d47278]	1868	// if ( typeDecl->get_base() ) {
	1869	// init = new SimpleInit( new SizeofExpr( handleDecl( typeDecl, typeDecl->get_base() ) ), designators );
	1870	// }
	1871	// return new ObjectDecl( typeDecl->get_name(), Declaration::Extern, LinkageSpec::C, 0, new BasicType( Type::Qualifiers(), BasicType::UnsignedInt ), init );
	1872
[2c57025]	1873	addToTyVarMap( typeDecl, scopeTyVars );
[05d47278]	1874	return Mutator::mutate( typeDecl );
	1875	}
	1876
	1877	Type * Pass3::mutate( PointerType *pointerType ) {
[6f49cdf]	1878	scopeTyVars.beginScope();
[05d47278]	1879	makeTyVarMap( pointerType, scopeTyVars );
	1880
	1881	Type *ret = Mutator::mutate( pointerType );
	1882
[6f49cdf]	1883	scopeTyVars.endScope();
[05d47278]	1884	return ret;
	1885	}
	1886
	1887	Type * Pass3::mutate( FunctionType *functionType ) {
[6f49cdf]	1888	scopeTyVars.beginScope();
[05d47278]	1889	makeTyVarMap( functionType, scopeTyVars );
	1890
	1891	Type *ret = Mutator::mutate( functionType );
	1892
[6f49cdf]	1893	scopeTyVars.endScope();
[05d47278]	1894	return ret;
	1895	}
[01aeade]	1896	} // anonymous namespace
[51b7345]	1897	} // namespace GenPoly
[01aeade]	1898
[51587aa]	1899	// Local Variables: //
	1900	// tab-width: 4 //
	1901	// mode: c++ //
	1902	// compile-command: "make install" //
	1903	// End: //

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

Download in other formats: