Context Navigation

source: src/GenPoly/Box.cc @ 08fc48f

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 08fc48f was 08fc48f, checked in by Thierry Delisle <tdelisle@…>, 7 years ago
Big header cleaning pass - commit 1
Property mode set to `100644`
File size: 88.7 KB

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

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

Download in other formats: