Context Navigation

source: src/GenPoly/Box.cc@ 9d7b3ea

Visit:

ADT aaron-thesis arm-eh ast-experimental cleanup-dtors ctor deferred_resn demangler enum forall-pointer-decay gc_noraii jacob/cs343-translation jenkins-sandbox memory new-ast new-ast-unique-expr new-env no_list persistent-indexer pthread-emulation qualifiedEnum resolv-new string stuck-waitfor-destruct with_gc

Last change on this file since 9d7b3ea was 9d7b3ea, checked in by Aaron Moss <a3moss@…>, 10 years ago
First draft of layout function builders
Property mode set to `100644`
File size: 79.0 KB

Line
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	//
7	// Box.cc --
8	//
9	// Author : Richard C. Bilson
10	// Created On : Mon May 18 07:44:20 2015
11	// Last Modified By : Peter A. Buhr
12	// Last Modified On : Fri Feb 5 16:45:07 2016
13	// Update Count : 286
14	//
15
16	#include <set>
17	#include <stack>
18	#include <string>
19	#include <iterator>
20	#include <algorithm>
21	#include <cassert>
22
23	#include "Box.h"
24	#include "DeclMutator.h"
25	#include "InstantiateGeneric.h"
26	#include "PolyMutator.h"
27	#include "FindFunction.h"
28	#include "ScrubTyVars.h"
29
30	#include "Parser/ParseNode.h"
31
32	#include "SynTree/Constant.h"
33	#include "SynTree/Type.h"
34	#include "SynTree/Expression.h"
35	#include "SynTree/Initializer.h"
36	#include "SynTree/Statement.h"
37	#include "SynTree/Mutator.h"
38
39	#include "ResolvExpr/TypeEnvironment.h"
40	#include "ResolvExpr/TypeMap.h"
41	#include "ResolvExpr/typeops.h"
42
43	#include "SymTab/Mangler.h"
44
45	#include "Common/SemanticError.h"
46	#include "Common/UniqueName.h"
47	#include "Common/utility.h"
48
49	#include <ext/functional> // temporary
50
51	namespace GenPoly {
52	namespace {
53	const std::list<Label> noLabels;
54
55	FunctionType makeAdapterType( FunctionType adaptee, const TyVarMap &tyVars );
56
57	/// Adds layout-generation functions to polymorphic types
58	class LayoutFunctionBuilder : public DeclMutator {
59	unsigned int functionNesting; // current level of nested functions
60	public:
61	LayoutFunctionBuilder() : functionNesting( 0 ) {}
62
63	virtual DeclarationWithType mutate( FunctionDecl functionDecl );
64	virtual Declaration mutate( StructDecl structDecl );
65	virtual Declaration mutate( UnionDecl unionDecl );
66	};
67
68	/// 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
69	class Pass1 : public PolyMutator {
70	public:
71	Pass1();
72	virtual Expression mutate( ApplicationExpr appExpr );
73	virtual Expression mutate( AddressExpr addrExpr );
74	virtual Expression mutate( UntypedExpr expr );
75	virtual DeclarationWithType* mutate( FunctionDecl *functionDecl );
76	virtual TypeDecl mutate( TypeDecl typeDecl );
77	virtual Expression mutate( CommaExpr commaExpr );
78	virtual Expression mutate( ConditionalExpr condExpr );
79	virtual Statement * mutate( ReturnStmt *returnStmt );
80	virtual Type mutate( PointerType pointerType );
81	virtual Type * mutate( FunctionType *functionType );
82
83	virtual void doBeginScope();
84	virtual void doEndScope();
85	private:
86	/// Makes a new temporary array holding the offsets of the fields of `type`, and returns a new variable expression referencing it
87	Expression makeOffsetArray( StructInstType type );
88	/// Pass the extra type parameters from polymorphic generic arguments or return types into a function application
89	void passArgTypeVars( ApplicationExpr appExpr, Type parmType, Type argBaseType, std::list< Expression >::iterator &arg, const TyVarMap &exprTyVars, std::set< std::string > &seenTypes );
90	/// passes extra type parameters into a polymorphic function application
91	void passTypeVars( ApplicationExpr appExpr, ReferenceToType polyRetType, std::list< Expression *>::iterator &arg, const TyVarMap &exprTyVars );
92	/// wraps a function application with a new temporary for the out-parameter return value
93	Expression addRetParam( ApplicationExpr appExpr, FunctionType function, Type retType, std::list< Expression *>::iterator &arg );
94	/// Replaces all the type parameters of a generic type with their concrete equivalents under the current environment
95	void replaceParametersWithConcrete( ApplicationExpr appExpr, std::list< Expression >& params );
96	/// Replaces a polymorphic type with its concrete equivalant under the current environment (returns itself if concrete).
97	/// If `doClone` is set to false, will not clone interior types
98	Type replaceWithConcrete( ApplicationExpr appExpr, Type *type, bool doClone = true );
99	/// wraps a function application returning a polymorphic type with a new temporary for the out-parameter return value
100	Expression addPolyRetParam( ApplicationExpr appExpr, FunctionType function, ReferenceToType polyType, std::list< Expression *>::iterator &arg );
101	Expression applyAdapter( ApplicationExpr appExpr, FunctionType function, std::list< Expression >::iterator &arg, const TyVarMap &exprTyVars );
102	void boxParam( Type formal, Expression &arg, const TyVarMap &exprTyVars );
103	void boxParams( ApplicationExpr appExpr, FunctionType function, std::list< Expression *>::iterator &arg, const TyVarMap &exprTyVars );
104	void addInferredParams( ApplicationExpr appExpr, FunctionType functionType, std::list< Expression *>::iterator &arg, const TyVarMap &tyVars );
105	/// Stores assignment operators from assertion list in local map of assignment operations
106	void findAssignOps( const std::list< TypeDecl *> &forall );
107	void passAdapters( ApplicationExpr appExpr, FunctionType functionType, const TyVarMap &exprTyVars );
108	FunctionDecl makeAdapter( FunctionType adaptee, FunctionType *realType, const std::string &mangleName, const TyVarMap &tyVars );
109	/// Replaces intrinsic operator functions with their arithmetic desugaring
110	Expression handleIntrinsics( ApplicationExpr appExpr );
111	/// Inserts a new temporary variable into the current scope with an auto-generated name
112	ObjectDecl makeTemporary( Type type );
113
114	typedef std::map< std::string, DeclarationWithType *> AdapterMap;
115	std::map< std::string, DeclarationWithType *> assignOps;
116	ResolvExpr::TypeMap< DeclarationWithType > scopedAssignOps;
117	std::stack< AdapterMap > adapters;
118	DeclarationWithType *retval;
119	bool useRetval;
120	UniqueName tempNamer;
121	};
122
123	/// Moves polymorphic returns in function types to pointer-type parameters, adds type size and assertion parameters to parameter lists as well
124	class Pass2 : public PolyMutator {
125	public:
126	template< typename DeclClass >
127	DeclClass handleDecl( DeclClass decl, Type *type );
128	virtual DeclarationWithType mutate( FunctionDecl functionDecl );
129	virtual ObjectDecl mutate( ObjectDecl objectDecl );
130	virtual TypeDecl mutate( TypeDecl typeDecl );
131	virtual TypedefDecl mutate( TypedefDecl typedefDecl );
132	virtual Type mutate( PointerType pointerType );
133	virtual Type mutate( FunctionType funcType );
134	private:
135	void addAdapters( FunctionType *functionType );
136
137	std::map< UniqueId, std::string > adapterName;
138	};
139
140	/// Replaces member expressions for polymorphic types with calculated add-field-offset-and-dereference;
141	/// also fixes offsetof expressions.
142	class MemberExprFixer : public PolyMutator {
143	public:
144	template< typename DeclClass >
145	DeclClass handleDecl( DeclClass decl, Type *type );
146	virtual DeclarationWithType mutate( FunctionDecl functionDecl );
147	virtual ObjectDecl mutate( ObjectDecl objectDecl );
148	virtual TypedefDecl mutate( TypedefDecl objectDecl );
149	virtual TypeDecl mutate( TypeDecl objectDecl );
150	virtual Statement mutate( DeclStmt declStmt );
151	virtual Type mutate( PointerType pointerType );
152	virtual Type mutate( FunctionType funcType );
153	virtual Expression mutate( MemberExpr memberExpr );
154	virtual Expression mutate( OffsetofExpr offsetofExpr );
155	};
156
157	/// Replaces initialization of polymorphic values with alloca, declaration of dtype/ftype with appropriate void expression, and sizeof expressions of polymorphic types with the proper variable
158	class Pass3 : public PolyMutator {
159	public:
160	template< typename DeclClass >
161	DeclClass handleDecl( DeclClass decl, Type *type );
162	virtual DeclarationWithType mutate( FunctionDecl functionDecl );
163	virtual ObjectDecl mutate( ObjectDecl objectDecl );
164	virtual TypedefDecl mutate( TypedefDecl objectDecl );
165	virtual TypeDecl mutate( TypeDecl objectDecl );
166	virtual Type mutate( PointerType pointerType );
167	virtual Type mutate( FunctionType funcType );
168	private:
169	};
170
171	} // anonymous namespace
172
173	/// version of mutateAll with special handling for translation unit so you can check the end of the prelude when debugging
174	template< typename MutatorType >
175	inline void mutateTranslationUnit( std::list< Declaration* > &translationUnit, MutatorType &mutator ) {
176	bool seenIntrinsic = false;
177	SemanticError errors;
178	for ( typename std::list< Declaration* >::iterator i = translationUnit.begin(); i != translationUnit.end(); ++i ) {
179	try {
180	if ( *i ) {
181	if ( (*i)->get_linkage() == LinkageSpec::Intrinsic ) {
182	seenIntrinsic = true;
183	} else if ( seenIntrinsic ) {
184	seenIntrinsic = false; // break on this line when debugging for end of prelude
185	}
186
187	i = dynamic_cast< Declaration >( (*i)->acceptMutator( mutator ) );
188	assert( *i );
189	} // if
190	} catch( SemanticError &e ) {
191	errors.append( e );
192	} // try
193	} // for
194	if ( ! errors.isEmpty() ) {
195	throw errors;
196	} // if
197	}
198
199	void box( std::list< Declaration *>& translationUnit ) {
200	LayoutFunctionBuilder layoutBuilder;
201	Pass1 pass1;
202	Pass2 pass2;
203	MemberExprFixer memberFixer;
204	Pass3 pass3;
205	layoutBuilder.mutateDeclarationList( translationUnit );
206	mutateTranslationUnit/All/( translationUnit, pass1 );
207	mutateTranslationUnit/All/( translationUnit, pass2 );
208	instantiateGeneric( translationUnit );
209	mutateTranslationUnit/All/( translationUnit, memberFixer );
210	mutateTranslationUnit/All/( translationUnit, pass3 );
211	}
212
213	////////////////////////////////// LayoutFunctionBuilder ////////////////////////////////////////////
214
215	DeclarationWithType LayoutFunctionBuilder::mutate( FunctionDecl functionDecl ) {
216	functionDecl->set_functionType( maybeMutate( functionDecl->get_functionType(), *this ) );
217	mutateAll( functionDecl->get_oldDecls(), *this );
218	++functionNesting;
219	functionDecl->set_statements( maybeMutate( functionDecl->get_statements(), *this ) );
220	--functionNesting;
221	return functionDecl;
222	}
223
224	/// Get a list of type declarations that will affect a layout function
225	std::list< TypeDecl* > takeOtypeOnly( std::list< TypeDecl* > &decls ) {
226	std::list< TypeDecl * > otypeDecls;
227
228	for ( std::list< TypeDecl* >::const_iterator decl = decls.begin(); decl != decls.end(); ++decl ) {
229	if ( decl->get_kind() == TypeDecl::Any ) {
230	otypeDecls.push_back( *decl );
231	}
232	}
233
234	return otypeDecls;
235	}
236
237	/// Adds parameters for otype layout to a function type
238	void addOtypeParams( FunctionType layoutFnType, std::list< TypeDecl > &otypeParams ) {
239	BasicType sizeAlignType( Type::Qualifiers(), BasicType::LongUnsignedInt );
240
241	for ( std::list< TypeDecl* >::const_iterator param = otypeParams.begin(); param != otypeParams.end(); ++param ) {
242	layoutFnType->get_parameters().push_back( new ObjectDecl( sizeofName( (*param)->get_base() ), DeclarationNode::NoStorageClass, LinkageSpec::Cforall, 0, sizeAlignType.clone(), 0 ) );
243	}
244	}
245
246	/// Builds a layout function declaration
247	FunctionDecl buildLayoutFunctionDecl( const std::string &typeName, unsigned int functionNesting, FunctionType layoutFnType ) {
248	// Routines at global scope marked "static" to prevent multiple definitions is separate translation units
249	// because each unit generates copies of the default routines for each aggregate.
250	FunctionDecl *layoutDecl = new FunctionDecl(
251	"__layoutof_" + typeName, functionNesting > 0 ? DeclarationNode::NoStorageClass : DeclarationNode::Static, LinkageSpec::AutoGen, layoutFnType, new CompoundStmt( noLabels ), true, false );
252	layoutDecl->fixUniqueId();
253	return layoutDecl;
254	}
255
256	/// Makes a unary operation
257	Expression makeOp( const std::string &name, Expression arg ) {
258	UntypedExpr *expr = new UntypedExpr( new NameExpr( name ) );
259	expr->get_args().push_back( arg );
260	return expr;
261	}
262
263	/// Makes a binary operation
264	Expression makeOp( const std::string &name, Expression lhs, Expression *rhs ) {
265	UntypedExpr *expr = new UntypedExpr( new NameExpr( name ) );
266	expr->get_args().push_back( lhs );
267	expr->get_args().push_back( rhs );
268	return expr;
269	}
270
271	/// Returns the dereference of a local pointer variable
272	Expression derefVar( ObjectDecl var ) {
273	return makeOp( "*?", new VariableExpr( var ) );
274	}
275
276	/// makes an if-statement with a single-expression if-block and no then block
277	Statement makeCond( Expression cond, Expression *ifPart ) {
278	return new IfStmt( noLabels, cond, new ExprStmt( ifPart ), 0 );
279	}
280
281	/// makes a statement that assigns rhs to lhs if lhs < rhs
282	Statement makeAssignMax( Expression lhs, Expression *rhs ) {
283	return makeCond( makeOp( "?<?", lhs, rhs ), makeOp( "?=?", lhs->clone(), rhs->clone() ) );
284	}
285
286	/// makes a statement that aligns lhs to rhs (rhs should be an integer power of two)
287	Statement makeAlignTo( Expression lhs, Expression *rhs ) {
288	// check that the lhs is zeroed out to the level of rhs
289	Expression *ifCond = makeOp( "?&?", lhs, makeOp( "?-?", rhs, new ConstantExpr( Constant( new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt ), "1" ) ) ) );
290	// if not aligned, increment to alignment
291	Expression *ifExpr = makeOp( "?+=?", lhs->clone(), makeOp( "?-?", rhs->clone(), ifCond->clone() ) );
292	return makeCond( ifCond, ifExpr );
293	}
294
295	/// adds an expression to a compound statement
296	void addExpr( CompoundStmt stmts, Expression expr ) {
297	stmts->get_kids().push_back( new ExprStmt( noLabels, expr ) );
298	}
299
300	/// adds a statement to a compound statement
301	void addStmt( CompoundStmt stmts, Statement stmt ) {
302	stmts->get_kids().push_back( stmt );
303	}
304
305	virtual Declaration LayoutFunctionBuilder::mutate( StructDecl structDecl ) {
306	// do not generate layout function for "empty" tag structs
307	if ( structDecl->get_members().empty() ) return structDecl;
308
309	// get parameters that can change layout, exiting early if none
310	std::list< TypeDecl* > otypeParams = takeOtypeOnly( structDecl->get_parameters() );
311	if ( otypeParams.empty() ) return structDecl;
312
313	// build layout function signature
314	FunctionType *layoutFnType = new FunctionType( Type::Qualifiers(), false );
315	BasicType *sizeAlignType = new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt );
316	PointerType *sizeAlignOutType = new PointerType( Type::Qualifiers(), sizeAlignType );
317
318	ObjectDecl *sizeParam = new ObjectDecl( "__sizeof_" + structDecl->get_name(), DeclarationNode::NoStorageClass, LinkageSpec::Cforall, 0, sizeAlignOutType, 0 );
319	layoutFnType->get_parameters().push_back( sizeParam );
320	ObjectDecl *alignParam = new ObjectDecl( "__alignof_" + structDecl->get_name(), DeclarationNode::NoStorageClass, LinkageSpec::Cforall, 0, sizeAlignOutType->clone(), 0 );
321	layoutFnType->get_parameters().push_back( alignParam );
322	ObjectDecl *offsetParam = new ObjectDecl( "__offsetof_" + structDecl->get_name(), DeclarationNode::NoStorageClass, LinkageSpec::Cforall, 0, sizeAlignOutType->clone(), 0 );
323	layoutFnType->get_parameters().push_back( offsetParam );
324	addOtypeParams( layoutFnType, otypeParams );
325
326	// build function decl
327	FunctionDecl *layoutDecl = buildLayoutFunctionDecl( structDecl->get_name(), functionNesting, layoutFnType );
328
329	// calculate struct layout in function body
330
331	// initialize size and alignment to 0 and 1 (will have at least one member to re-edit size
332	addExpr( layoutDecl->get_statements(), makeOp( "?=?", derefVar( sizeParam ), new ConstantExpr( Constant( sizeAlignType->clone(), "0" ) ) ) );
333	addExpr( layoutDecl->get_statements(), makeOp( "?=?", derefVar( alignParam ), new ConstantExpr( Constant( sizeAlignType->clone(), "1" ) ) ) );
334	unsigned long n_members = 0;
335	bool firstMember = true;
336	for ( std::list< Declaration* >::const_iterator member = structDecl->get_members().begin(); member != structDecl->get_members().end(); ++member ) {
337	DeclarationWithType dwt = dynamic_cast< DeclarationWithType >( *member );
338	assert( dwt );
339
340	if ( firstMember ) {
341	firstMember = false;
342	} else {
343	// make sure all members after the first (automatically aligned at 0) are properly padded for alignment
344	addStmt( layoutDecl->get_statements(), makeAlignTo( derefVar( sizeParam ), new AlignofExpr( dwt->get_type() ) ) );
345	}
346
347	// place current size in the current offset index
348	addExpr( layoutDecl->get_statements(), makeOp( "?=?", makeOp( "?[?]", new VariableExpr( offsetParam ), new ConstantExpr( Constant::from( n_members ) ) ),
349	derefVar( sizeParam ) ) );
350	++n_members;
351
352	// add member size to current size
353	addExpr( layoutDecl->get_statements(), makeOp( "?+=?", derefVar( sizeParam ), new SizeofExpr( dwt->get_type() ) ) );
354
355	// take max of member alignment and global alignment
356	addStmt( layoutDecl->get_statements(), makeAssignMax( derefVar( alignParam ), new AlignofExpr( dwt->get_type() ) ) );
357	}
358	// make sure the type is end-padded to a multiple of its alignment
359	addStmt( layoutDecl->get_statements(), makeAlignTo( derefVar( sizeParam ), derefVar( alignParam ) ) );
360
361	addDeclarationAfter( layoutDecl );
362	return structDecl;
363	}
364
365	virtual Declaration LayoutFunctionBuilder::mutate( UnionDecl unionDecl ) {
366	// do not generate layout function for "empty" tag unions
367	if ( unionDecl->get_members().empty() ) return unionDecl;
368
369	// get parameters that can change layout, exiting early if none
370	std::list< TypeDecl* > otypeParams = takeOtypeOnly( unionDecl->get_parameters() );
371	if ( otypeParams.empty() ) return unionDecl;
372
373	// build layout function signature
374	FunctionType *layoutFnType = new FunctionType( Type::Qualifiers(), false );
375	BasicType *sizeAlignType = new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt );
376	PointerType *sizeAlignOutType = new PointerType( Type::Qualifiers(), sizeAlignType );
377
378	ObjectDecl *sizeParam = new ObjectDecl( "__sizeof_" + unionDecl->get_name(), DeclarationNode::NoStorageClass, LinkageSpec::Cforall, 0, sizeAlignOutType, 0 );
379	layoutFnType->get_parameters().push_back( sizeParam );
380	ObjectDecl *alignParam = new ObjectDecl( "__alignof_" + unionDecl->get_name(), DeclarationNode::NoStorageClass, LinkageSpec::Cforall, 0, sizeAlignOutType->clone(), 0 );
381	layoutFnType->get_parameters().push_back( alignParam );
382	addOtypeParams( layoutFnType, otypeParams );
383
384	// build function decl
385	FunctionDecl *layoutDecl = buildLayoutFunctionDecl( unionDecl->get_name(), functionNesting, layoutFnType );
386
387	// calculate union layout in function body
388	addExpr( layoutDecl->get_statements(), makeOp( "?=?", derefVar( sizeParam ), new ConstantExpr( Constant( sizeAlignType->clone(), "1" ) ) ) );
389	addExpr( layoutDecl->get_statements(), makeOp( "?=?", derefVar( alignParam ), new ConstantExpr( Constant( sizeAlignType->clone(), "1" ) ) ) );
390	for ( std::list< Declaration* >::const_iterator member = unionDecl->get_members().begin(); member != unionDecl->get_members().end(); ++member ) {
391	DeclarationWithType dwt = dynamic_cast< DeclarationWithType >( *member );
392	assert( dwt );
393
394	// take max member size and global size
395	addStmt( layoutDecl->get_statements(), makeAssignMax( derefVar( sizeParam ), new SizeofExpr( dwt->get_type() ) ) );
396
397	// take max of member alignment and global alignment
398	addStmt( layoutDecl->get_statements(), makeAssignMax( derefVar( alignParam ), new AlignofExpr( dwt->get_type() ) ) );
399	}
400	// make sure the type is end-padded to a multiple of its alignment
401	addStmt( layoutDecl->get_statements(), makeAlignTo( derefVar( sizeParam ), derefVar( alignParam ) ) );
402
403	addDeclarationAfter( layoutDecl );
404	return unionDecl;
405	}
406
407	////////////////////////////////////////// Pass1 ////////////////////////////////////////////////////
408
409	namespace {
410	std::string makePolyMonoSuffix( FunctionType * function, const TyVarMap &tyVars ) {
411	std::stringstream name;
412
413	// NOTE: this function previously used isPolyObj, which failed to produce
414	// the correct thing in some situations. It's not clear to me why this wasn't working.
415
416	// if the return type or a parameter type involved polymorphic types, then the adapter will need
417	// to take those polymorphic types as pointers. Therefore, there can be two different functions
418	// with the same mangled name, so we need to further mangle the names.
419	for ( std::list< DeclarationWithType *>::iterator retval = function->get_returnVals().begin(); retval != function->get_returnVals().end(); ++retval ) {
420	if ( isPolyType( (*retval)->get_type(), tyVars ) ) {
421	name << "P";
422	} else {
423	name << "M";
424	}
425	}
426	name << "_";
427	std::list< DeclarationWithType *> &paramList = function->get_parameters();
428	for ( std::list< DeclarationWithType *>::iterator arg = paramList.begin(); arg != paramList.end(); ++arg ) {
429	if ( isPolyType( (*arg)->get_type(), tyVars ) ) {
430	name << "P";
431	} else {
432	name << "M";
433	}
434	} // for
435	return name.str();
436	}
437
438	std::string mangleAdapterName( FunctionType * function, const TyVarMap &tyVars ) {
439	return SymTab::Mangler::mangle( function ) + makePolyMonoSuffix( function, tyVars );
440	}
441
442	std::string makeAdapterName( const std::string &mangleName ) {
443	return "_adapter" + mangleName;
444	}
445
446	Pass1::Pass1() : useRetval( false ), tempNamer( "_temp" ) {
447	adapters.push(AdapterMap());
448	}
449
450	/// Returns T if the given declaration is (?=?)(T , T) for some TypeInstType T (return not checked, but maybe should be), NULL otherwise
451	TypeInstType isTypeInstAssignment( DeclarationWithType decl ) {
452	if ( decl->get_name() == "?=?" ) {
453	if ( FunctionType *funType = getFunctionType( decl->get_type() ) ) {
454	if ( funType->get_parameters().size() == 2 ) {
455	if ( PointerType pointer = dynamic_cast< PointerType >( funType->get_parameters().front()->get_type() ) ) {
456	if ( TypeInstType refType = dynamic_cast< TypeInstType >( pointer->get_base() ) ) {
457	if ( TypeInstType refType2 = dynamic_cast< TypeInstType >( funType->get_parameters().back()->get_type() ) ) {
458	if ( refType->get_name() == refType2->get_name() ) {
459	return refType;
460	} // if
461	} // if
462	} // if
463	} // if
464	} // if
465	} // if
466	} // if
467	return 0;
468	}
469
470	/// returns T if the given declaration is: (?=?)(T , T) for some type T (return not checked, but maybe should be), NULL otherwise
471	/// Only picks assignments where neither parameter is cv-qualified
472	Type isAssignment( DeclarationWithType decl ) {
473	if ( decl->get_name() == "?=?" ) {
474	if ( FunctionType *funType = getFunctionType( decl->get_type() ) ) {
475	if ( funType->get_parameters().size() == 2 ) {
476	Type::Qualifiers defaultQualifiers;
477	Type *paramType1 = funType->get_parameters().front()->get_type();
478	if ( paramType1->get_qualifiers() != defaultQualifiers ) return 0;
479	Type *paramType2 = funType->get_parameters().back()->get_type();
480	if ( paramType2->get_qualifiers() != defaultQualifiers ) return 0;
481
482	if ( PointerType pointerType = dynamic_cast< PointerType >( paramType1 ) ) {
483	Type *baseType1 = pointerType->get_base();
484	if ( baseType1->get_qualifiers() != defaultQualifiers ) return 0;
485	SymTab::Indexer dummy;
486	if ( ResolvExpr::typesCompatible( baseType1, paramType2, dummy ) ) {
487	return baseType1;
488	} // if
489	} // if
490	} // if
491	} // if
492	} // if
493	return 0;
494	}
495
496	void Pass1::findAssignOps( const std::list< TypeDecl *> &forall ) {
497	// what if a nested function uses an assignment operator?
498	// assignOps.clear();
499	for ( std::list< TypeDecl *>::const_iterator i = forall.begin(); i != forall.end(); ++i ) {
500	for ( std::list< DeclarationWithType >::const_iterator assert = (i)->get_assertions().begin(); assert != (*i)->get_assertions().end(); ++assert ) {
501	std::string typeName;
502	if ( TypeInstType typeInst = isTypeInstAssignment( assert ) ) {
503	assignOps[ typeInst->get_name() ] = *assert;
504	} // if
505	} // for
506	} // for
507	}
508
509	DeclarationWithType Pass1::mutate( FunctionDecl functionDecl ) {
510	// if this is a polymorphic assignment function, put it in the map for this scope
511	if ( Type *assignedType = isAssignment( functionDecl ) ) {
512	if ( ! dynamic_cast< TypeInstType* >( assignedType ) ) {
513	scopedAssignOps.insert( assignedType, functionDecl );
514	}
515	}
516
517	if ( functionDecl->get_statements() ) { // empty routine body ?
518	doBeginScope();
519	TyVarMap oldtyVars = scopeTyVars;
520	std::map< std::string, DeclarationWithType *> oldassignOps = assignOps;
521	DeclarationWithType *oldRetval = retval;
522	bool oldUseRetval = useRetval;
523
524	// process polymorphic return value
525	retval = 0;
526	if ( isPolyRet( functionDecl->get_functionType() ) && functionDecl->get_linkage() == LinkageSpec::Cforall ) {
527	retval = functionDecl->get_functionType()->get_returnVals().front();
528
529	// give names to unnamed return values
530	if ( retval->get_name() == "" ) {
531	retval->set_name( "_retparm" );
532	retval->set_linkage( LinkageSpec::C );
533	} // if
534	} // if
535
536	FunctionType *functionType = functionDecl->get_functionType();
537	makeTyVarMap( functionDecl->get_functionType(), scopeTyVars );
538	findAssignOps( functionDecl->get_functionType()->get_forall() );
539
540	std::list< DeclarationWithType *> &paramList = functionType->get_parameters();
541	std::list< FunctionType *> functions;
542	for ( std::list< TypeDecl *>::iterator tyVar = functionType->get_forall().begin(); tyVar != functionType->get_forall().end(); ++tyVar ) {
543	for ( std::list< DeclarationWithType >::iterator assert = (tyVar)->get_assertions().begin(); assert != (*tyVar)->get_assertions().end(); ++assert ) {
544	findFunction( (*assert)->get_type(), functions, scopeTyVars, needsAdapter );
545	} // for
546	} // for
547	for ( std::list< DeclarationWithType *>::iterator arg = paramList.begin(); arg != paramList.end(); ++arg ) {
548	findFunction( (*arg)->get_type(), functions, scopeTyVars, needsAdapter );
549	} // for
550
551	AdapterMap & adapters = Pass1::adapters.top();
552	for ( std::list< FunctionType *>::iterator funType = functions.begin(); funType != functions.end(); ++funType ) {
553	std::string mangleName = mangleAdapterName( *funType, scopeTyVars );
554	if ( adapters.find( mangleName ) == adapters.end() ) {
555	std::string adapterName = makeAdapterName( mangleName );
556	adapters.insert( std::pair< std::string, DeclarationWithType >( mangleName, new ObjectDecl( adapterName, DeclarationNode::NoStorageClass, LinkageSpec::C, 0, new PointerType( Type::Qualifiers(), makeAdapterType( funType, scopeTyVars ) ), 0 ) ) );
557	} // if
558	} // for
559
560	functionDecl->set_statements( functionDecl->get_statements()->acceptMutator( *this ) );
561
562	scopeTyVars = oldtyVars;
563	assignOps = oldassignOps;
564	// std::cerr << "end FunctionDecl: ";
565	// for ( TyVarMap::iterator i = scopeTyVars.begin(); i != scopeTyVars.end(); ++i ) {
566	// std::cerr << i->first << " ";
567	// }
568	// std::cerr << "\n";
569	retval = oldRetval;
570	useRetval = oldUseRetval;
571	doEndScope();
572	} // if
573	return functionDecl;
574	}
575
576	TypeDecl Pass1::mutate( TypeDecl typeDecl ) {
577	scopeTyVars[ typeDecl->get_name() ] = typeDecl->get_kind();
578	return Mutator::mutate( typeDecl );
579	}
580
581	Expression Pass1::mutate( CommaExpr commaExpr ) {
582	bool oldUseRetval = useRetval;
583	useRetval = false;
584	commaExpr->set_arg1( maybeMutate( commaExpr->get_arg1(), *this ) );
585	useRetval = oldUseRetval;
586	commaExpr->set_arg2( maybeMutate( commaExpr->get_arg2(), *this ) );
587	return commaExpr;
588	}
589
590	Expression Pass1::mutate( ConditionalExpr condExpr ) {
591	bool oldUseRetval = useRetval;
592	useRetval = false;
593	condExpr->set_arg1( maybeMutate( condExpr->get_arg1(), *this ) );
594	useRetval = oldUseRetval;
595	condExpr->set_arg2( maybeMutate( condExpr->get_arg2(), *this ) );
596	condExpr->set_arg3( maybeMutate( condExpr->get_arg3(), *this ) );
597	return condExpr;
598
599	}
600
601	Expression Pass1::makeOffsetArray( StructInstType ty ) {
602	std::list< Declaration* > &baseMembers = ty->get_baseStruct()->get_members();
603
604	// make a new temporary array
605	Type *offsetType = new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt );
606	std::stringstream lenGen;
607	lenGen << baseMembers.size();
608	ConstantExpr *lenExpr = new ConstantExpr( Constant( offsetType->clone(), lenGen.str() ) );
609	ObjectDecl *arrayTemp = makeTemporary( new ArrayType( Type::Qualifiers(), offsetType, lenExpr, false, false ) );
610
611	// build initializer list for temporary
612	std::list< Initializer* > inits;
613	for ( std::list< Declaration* >::const_iterator member = baseMembers.begin(); member != baseMembers.end(); ++member ) {
614	DeclarationWithType *memberDecl;
615	if ( DeclarationWithType origMember = dynamic_cast< DeclarationWithType >( *member ) ) {
616	memberDecl = origMember->clone();
617	} else {
618	memberDecl = new ObjectDecl( (*member)->get_name(), DeclarationNode::NoStorageClass, LinkageSpec::Cforall, 0, offsetType->clone(), 0 );
619	}
620	inits.push_back( new SingleInit( new OffsetofExpr( ty->clone(), memberDecl ) ) );
621	}
622	arrayTemp->set_init( new ListInit( inits ) );
623
624	// return variable pointing to temporary
625	return new VariableExpr( arrayTemp );
626	}
627
628	void Pass1::passArgTypeVars( ApplicationExpr appExpr, Type parmType, Type argBaseType, std::list< Expression >::iterator &arg, const TyVarMap &exprTyVars, std::set< std::string > &seenTypes ) {
629	Type *polyBase = hasPolyBase( parmType, exprTyVars );
630	if ( polyBase && ! dynamic_cast< TypeInstType* >( polyBase ) ) {
631	std::string sizeName = sizeofName( polyBase );
632	if ( seenTypes.count( sizeName ) ) return;
633
634	arg = appExpr->get_args().insert( arg, new SizeofExpr( argBaseType->clone() ) );
635	arg++;
636	arg = appExpr->get_args().insert( arg, new AlignofExpr( argBaseType->clone() ) );
637	arg++;
638	if ( dynamic_cast< StructInstType* >( polyBase ) ) {
639	if ( StructInstType argBaseStructType = dynamic_cast< StructInstType >( argBaseType ) ) {
640	arg = appExpr->get_args().insert( arg, makeOffsetArray( argBaseStructType ) );
641	arg++;
642	} else {
643	throw SemanticError( "Cannot pass non-struct type for generic struct" );
644	}
645	}
646
647	seenTypes.insert( sizeName );
648	}
649	}
650
651	void Pass1::passTypeVars( ApplicationExpr appExpr, ReferenceToType polyRetType, std::list< Expression *>::iterator &arg, const TyVarMap &exprTyVars ) {
652	// pass size/align for type variables
653	for ( TyVarMap::const_iterator tyParm = exprTyVars.begin(); tyParm != exprTyVars.end(); ++tyParm ) {
654	ResolvExpr::EqvClass eqvClass;
655	assert( env );
656	if ( tyParm->second == TypeDecl::Any ) {
657	Type *concrete = env->lookup( tyParm->first );
658	if ( concrete ) {
659	arg = appExpr->get_args().insert( arg, new SizeofExpr( concrete->clone() ) );
660	arg++;
661	arg = appExpr->get_args().insert( arg, new AlignofExpr( concrete->clone() ) );
662	arg++;
663	} else {
664	throw SemanticError( "unbound type variable in application ", appExpr );
665	} // if
666	} // if
667	} // for
668
669	// add size/align for generic types to parameter list
670	if ( appExpr->get_function()->get_results().empty() ) return;
671	FunctionType *funcType = getFunctionType( appExpr->get_function()->get_results().front() );
672	assert( funcType );
673
674	std::list< DeclarationWithType* >::const_iterator fnParm = funcType->get_parameters().begin();
675	std::list< Expression* >::const_iterator fnArg = arg;
676	std::set< std::string > seenTypes; //< names for generic types we've seen
677
678	// a polymorphic return type may need to be added to the argument list
679	if ( polyRetType ) {
680	Type *concRetType = replaceWithConcrete( appExpr, polyRetType );
681	passArgTypeVars( appExpr, polyRetType, concRetType, arg, exprTyVars, seenTypes );
682	}
683
684	// add type information args for presently unseen types in parameter list
685	for ( ; fnParm != funcType->get_parameters().end() && fnArg != appExpr->get_args().end(); ++fnParm, ++fnArg ) {
686	VariableExpr fnArgBase = getBaseVar( fnArg );
687	if ( ! fnArgBase \|\| fnArgBase->get_results().empty() ) continue;
688	passArgTypeVars( appExpr, (*fnParm)->get_type(), fnArgBase->get_results().front(), arg, exprTyVars, seenTypes );
689	}
690	}
691
692	ObjectDecl Pass1::makeTemporary( Type type ) {
693	ObjectDecl *newObj = new ObjectDecl( tempNamer.newName(), DeclarationNode::NoStorageClass, LinkageSpec::C, 0, type, 0 );
694	stmtsToAdd.push_back( new DeclStmt( noLabels, newObj ) );
695	return newObj;
696	}
697
698	Expression Pass1::addRetParam( ApplicationExpr appExpr, FunctionType function, Type retType, std::list< Expression *>::iterator &arg ) {
699	// *** Code Removal *** After introducing a temporary variable for all return expressions, the following code appears superfluous.
700	// if ( useRetval ) {
701	// assert( retval );
702	// arg = appExpr->get_args().insert( arg, new VariableExpr( retval ) );
703	// arg++;
704	// } else {
705
706	// Create temporary to hold return value of polymorphic function and produce that temporary as a result
707	// using a comma expression. Possibly change comma expression into statement expression "{}" for multiple
708	// return values.
709	ObjectDecl *newObj = makeTemporary( retType->clone() );
710	Expression *paramExpr = new VariableExpr( newObj );
711
712	// If the type of the temporary is not polymorphic, box temporary by taking its address;
713	// otherwise the temporary is already boxed and can be used directly.
714	if ( ! isPolyType( newObj->get_type(), scopeTyVars, env ) ) {
715	paramExpr = new AddressExpr( paramExpr );
716	} // if
717	arg = appExpr->get_args().insert( arg, paramExpr ); // add argument to function call
718	arg++;
719	// Build a comma expression to call the function and emulate a normal return.
720	CommaExpr *commaExpr = new CommaExpr( appExpr, new VariableExpr( newObj ) );
721	commaExpr->set_env( appExpr->get_env() );
722	appExpr->set_env( 0 );
723	return commaExpr;
724	// } // if
725	// return appExpr;
726	}
727
728	void Pass1::replaceParametersWithConcrete( ApplicationExpr appExpr, std::list< Expression >& params ) {
729	for ( std::list< Expression* >::iterator param = params.begin(); param != params.end(); ++param ) {
730	TypeExpr paramType = dynamic_cast< TypeExpr >( *param );
731	assert(paramType && "Aggregate parameters should be type expressions");
732	paramType->set_type( replaceWithConcrete( appExpr, paramType->get_type(), false ) );
733	}
734	}
735
736	Type Pass1::replaceWithConcrete( ApplicationExpr appExpr, Type *type, bool doClone ) {
737	if ( TypeInstType typeInst = dynamic_cast< TypeInstType >( type ) ) {
738	Type *concrete = env->lookup( typeInst->get_name() );
739	if ( concrete == 0 ) {
740	throw SemanticError( "Unbound type variable " + typeInst->get_name() + " in ", appExpr );
741	} // if
742	return concrete;
743	} else if ( StructInstType structType = dynamic_cast< StructInstType >( type ) ) {
744	if ( doClone ) {
745	structType = structType->clone();
746	}
747	replaceParametersWithConcrete( appExpr, structType->get_parameters() );
748	return structType;
749	} else if ( UnionInstType unionType = dynamic_cast< UnionInstType >( type ) ) {
750	if ( doClone ) {
751	unionType = unionType->clone();
752	}
753	replaceParametersWithConcrete( appExpr, unionType->get_parameters() );
754	return unionType;
755	}
756	return type;
757	}
758
759	Expression Pass1::addPolyRetParam( ApplicationExpr appExpr, FunctionType function, ReferenceToType polyType, std::list< Expression *>::iterator &arg ) {
760	assert( env );
761	Type *concrete = replaceWithConcrete( appExpr, polyType );
762	// add out-parameter for return value
763	return addRetParam( appExpr, function, concrete, arg );
764	}
765
766	Expression Pass1::applyAdapter( ApplicationExpr appExpr, FunctionType function, std::list< Expression >::iterator &arg, const TyVarMap &tyVars ) {
767	Expression *ret = appExpr;
768	if ( ! function->get_returnVals().empty() && isPolyType( function->get_returnVals().front()->get_type(), tyVars ) ) {
769	ret = addRetParam( appExpr, function, function->get_returnVals().front()->get_type(), arg );
770	} // if
771	std::string mangleName = mangleAdapterName( function, tyVars );
772	std::string adapterName = makeAdapterName( mangleName );
773
774	// cast adaptee to void (*)(), since it may have any type inside a polymorphic function
775	Type * adapteeType = new PointerType( Type::Qualifiers(), new FunctionType( Type::Qualifiers(), true ) );
776	appExpr->get_args().push_front( new CastExpr( appExpr->get_function(), adapteeType ) );
777	appExpr->set_function( new NameExpr( adapterName ) );
778
779	return ret;
780	}
781
782	void Pass1::boxParam( Type param, Expression &arg, const TyVarMap &exprTyVars ) {
783	assert( ! arg->get_results().empty() );
784	if ( isPolyType( param, exprTyVars ) ) {
785	if ( isPolyType( arg->get_results().front() ) ) {
786	// if the argument's type is polymorphic, we don't need to box again!
787	return;
788	} else if ( arg->get_results().front()->get_isLvalue() ) {
789	// VariableExpr and MemberExpr are lvalues
790	arg = new AddressExpr( arg );
791	} else {
792	// use type computed in unification to declare boxed variables
793	Type * newType = param->clone();
794	if ( env ) env->apply( newType );
795	ObjectDecl *newObj = new ObjectDecl( tempNamer.newName(), DeclarationNode::NoStorageClass, LinkageSpec::C, 0, newType, 0 );
796	newObj->get_type()->get_qualifiers() = Type::Qualifiers(); // TODO: is this right???
797	stmtsToAdd.push_back( new DeclStmt( noLabels, newObj ) );
798	UntypedExpr *assign = new UntypedExpr( new NameExpr( "?=?" ) );
799	assign->get_args().push_back( new VariableExpr( newObj ) );
800	assign->get_args().push_back( arg );
801	stmtsToAdd.push_back( new ExprStmt( noLabels, assign ) );
802	arg = new AddressExpr( new VariableExpr( newObj ) );
803	} // if
804	} // if
805	}
806
807	/// cast parameters to polymorphic functions so that types are replaced with
808	/// void * if they are type parameters in the formal type.
809	/// this gets rid of warnings from gcc.
810	void addCast( Expression &actual, Type formal, const TyVarMap &tyVars ) {
811	Type * newType = formal->clone();
812	if ( getFunctionType( newType ) ) {
813	newType = ScrubTyVars::scrub( newType, tyVars );
814	actual = new CastExpr( actual, newType );
815	} // if
816	}
817
818	void Pass1::boxParams( ApplicationExpr appExpr, FunctionType function, std::list< Expression *>::iterator &arg, const TyVarMap &exprTyVars ) {
819	for ( std::list< DeclarationWithType *>::const_iterator param = function->get_parameters().begin(); param != function->get_parameters().end(); ++param, ++arg ) {
820	assert( arg != appExpr->get_args().end() );
821	addCast( arg, (param)->get_type(), exprTyVars );
822	boxParam( (param)->get_type(), arg, exprTyVars );
823	} // for
824	}
825
826	void Pass1::addInferredParams( ApplicationExpr appExpr, FunctionType functionType, std::list< Expression *>::iterator &arg, const TyVarMap &tyVars ) {
827	std::list< Expression *>::iterator cur = arg;
828	for ( std::list< TypeDecl *>::iterator tyVar = functionType->get_forall().begin(); tyVar != functionType->get_forall().end(); ++tyVar ) {
829	for ( std::list< DeclarationWithType >::iterator assert = (tyVar)->get_assertions().begin(); assert != (*tyVar)->get_assertions().end(); ++assert ) {
830	InferredParams::const_iterator inferParam = appExpr->get_inferParams().find( (*assert)->get_uniqueId() );
831	assert( inferParam != appExpr->get_inferParams().end() && "NOTE: Explicit casts of polymorphic functions to compatible monomorphic functions are currently unsupported" );
832	Expression *newExpr = inferParam->second.expr->clone();
833	addCast( newExpr, (*assert)->get_type(), tyVars );
834	boxParam( (*assert)->get_type(), newExpr, tyVars );
835	appExpr->get_args().insert( cur, newExpr );
836	} // for
837	} // for
838	}
839
840	void makeRetParm( FunctionType *funcType ) {
841	DeclarationWithType *retParm = funcType->get_returnVals().front();
842
843	// make a new parameter that is a pointer to the type of the old return value
844	retParm->set_type( new PointerType( Type::Qualifiers(), retParm->get_type() ) );
845	funcType->get_parameters().push_front( retParm );
846
847	// we don't need the return value any more
848	funcType->get_returnVals().clear();
849	}
850
851	FunctionType makeAdapterType( FunctionType adaptee, const TyVarMap &tyVars ) {
852	// actually make the adapter type
853	FunctionType *adapter = adaptee->clone();
854	if ( ! adapter->get_returnVals().empty() && isPolyType( adapter->get_returnVals().front()->get_type(), tyVars ) ) {
855	makeRetParm( adapter );
856	} // if
857	adapter->get_parameters().push_front( new ObjectDecl( "", DeclarationNode::NoStorageClass, LinkageSpec::C, 0, new PointerType( Type::Qualifiers(), new FunctionType( Type::Qualifiers(), true ) ), 0 ) );
858	return adapter;
859	}
860
861	Expression makeAdapterArg( DeclarationWithType param, DeclarationWithType arg, DeclarationWithType realParam, const TyVarMap &tyVars ) {
862	assert( param );
863	assert( arg );
864	if ( isPolyType( realParam->get_type(), tyVars ) ) {
865	if ( ! isPolyType( arg->get_type() ) ) {
866	UntypedExpr deref = new UntypedExpr( new NameExpr( "?" ) );
867	deref->get_args().push_back( new CastExpr( new VariableExpr( param ), new PointerType( Type::Qualifiers(), arg->get_type()->clone() ) ) );
868	deref->get_results().push_back( arg->get_type()->clone() );
869	return deref;
870	} // if
871	} // if
872	return new VariableExpr( param );
873	}
874
875	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 ) {
876	UniqueName paramNamer( "_p" );
877	for ( ; param != paramEnd; ++param, ++arg, ++realParam ) {
878	if ( (*param)->get_name() == "" ) {
879	(*param)->set_name( paramNamer.newName() );
880	(*param)->set_linkage( LinkageSpec::C );
881	} // if
882	adapteeApp->get_args().push_back( makeAdapterArg( param, arg, *realParam, tyVars ) );
883	} // for
884	}
885
886
887
888	FunctionDecl Pass1::makeAdapter( FunctionType adaptee, FunctionType *realType, const std::string &mangleName, const TyVarMap &tyVars ) {
889	FunctionType *adapterType = makeAdapterType( adaptee, tyVars );
890	adapterType = ScrubTyVars::scrub( adapterType, tyVars );
891	DeclarationWithType *adapteeDecl = adapterType->get_parameters().front();
892	adapteeDecl->set_name( "_adaptee" );
893	ApplicationExpr *adapteeApp = new ApplicationExpr( new CastExpr( new VariableExpr( adapteeDecl ), new PointerType( Type::Qualifiers(), realType ) ) );
894	Statement *bodyStmt;
895
896	std::list< TypeDecl *>::iterator tyArg = realType->get_forall().begin();
897	std::list< TypeDecl *>::iterator tyParam = adapterType->get_forall().begin();
898	std::list< TypeDecl *>::iterator realTyParam = adaptee->get_forall().begin();
899	for ( ; tyParam != adapterType->get_forall().end(); ++tyArg, ++tyParam, ++realTyParam ) {
900	assert( tyArg != realType->get_forall().end() );
901	std::list< DeclarationWithType >::iterator assertArg = (tyArg)->get_assertions().begin();
902	std::list< DeclarationWithType >::iterator assertParam = (tyParam)->get_assertions().begin();
903	std::list< DeclarationWithType >::iterator realAssertParam = (realTyParam)->get_assertions().begin();
904	for ( ; assertParam != (*tyParam)->get_assertions().end(); ++assertArg, ++assertParam, ++realAssertParam ) {
905	assert( assertArg != (*tyArg)->get_assertions().end() );
906	adapteeApp->get_args().push_back( makeAdapterArg( assertParam, assertArg, *realAssertParam, tyVars ) );
907	} // for
908	} // for
909
910	std::list< DeclarationWithType *>::iterator arg = realType->get_parameters().begin();
911	std::list< DeclarationWithType *>::iterator param = adapterType->get_parameters().begin();
912	std::list< DeclarationWithType *>::iterator realParam = adaptee->get_parameters().begin();
913	param++; // skip adaptee parameter
914	if ( realType->get_returnVals().empty() ) {
915	addAdapterParams( adapteeApp, arg, param, adapterType->get_parameters().end(), realParam, tyVars );
916	bodyStmt = new ExprStmt( noLabels, adapteeApp );
917	} else if ( isPolyType( adaptee->get_returnVals().front()->get_type(), tyVars ) ) {
918	if ( (*param)->get_name() == "" ) {
919	(*param)->set_name( "_ret" );
920	(*param)->set_linkage( LinkageSpec::C );
921	} // if
922	UntypedExpr *assign = new UntypedExpr( new NameExpr( "?=?" ) );
923	UntypedExpr deref = new UntypedExpr( new NameExpr( "?" ) );
924	deref->get_args().push_back( new CastExpr( new VariableExpr( *param++ ), new PointerType( Type::Qualifiers(), realType->get_returnVals().front()->get_type()->clone() ) ) );
925	assign->get_args().push_back( deref );
926	addAdapterParams( adapteeApp, arg, param, adapterType->get_parameters().end(), realParam, tyVars );
927	assign->get_args().push_back( adapteeApp );
928	bodyStmt = new ExprStmt( noLabels, assign );
929	} else {
930	// adapter for a function that returns a monomorphic value
931	addAdapterParams( adapteeApp, arg, param, adapterType->get_parameters().end(), realParam, tyVars );
932	bodyStmt = new ReturnStmt( noLabels, adapteeApp );
933	} // if
934	CompoundStmt *adapterBody = new CompoundStmt( noLabels );
935	adapterBody->get_kids().push_back( bodyStmt );
936	std::string adapterName = makeAdapterName( mangleName );
937	return new FunctionDecl( adapterName, DeclarationNode::NoStorageClass, LinkageSpec::C, adapterType, adapterBody, false, false );
938	}
939
940	void Pass1::passAdapters( ApplicationExpr * appExpr, FunctionType * functionType, const TyVarMap & exprTyVars ) {
941	// collect a list of function types passed as parameters or implicit parameters (assertions)
942	std::list< DeclarationWithType *> &paramList = functionType->get_parameters();
943	std::list< FunctionType *> functions;
944	for ( std::list< TypeDecl *>::iterator tyVar = functionType->get_forall().begin(); tyVar != functionType->get_forall().end(); ++tyVar ) {
945	for ( std::list< DeclarationWithType >::iterator assert = (tyVar)->get_assertions().begin(); assert != (*tyVar)->get_assertions().end(); ++assert ) {
946	findFunction( (*assert)->get_type(), functions, exprTyVars, needsAdapter );
947	} // for
948	} // for
949	for ( std::list< DeclarationWithType *>::iterator arg = paramList.begin(); arg != paramList.end(); ++arg ) {
950	findFunction( (*arg)->get_type(), functions, exprTyVars, needsAdapter );
951	} // for
952
953	// parameter function types for which an appropriate adapter has been generated. we cannot use the types
954	// after applying substitutions, since two different parameter types may be unified to the same type
955	std::set< std::string > adaptersDone;
956
957	for ( std::list< FunctionType *>::iterator funType = functions.begin(); funType != functions.end(); ++funType ) {
958	FunctionType originalFunction = (funType)->clone();
959	FunctionType realFunction = (funType)->clone();
960	std::string mangleName = SymTab::Mangler::mangle( realFunction );
961
962	// only attempt to create an adapter or pass one as a parameter if we haven't already done so for this
963	// pre-substitution parameter function type.
964	if ( adaptersDone.find( mangleName ) == adaptersDone.end() ) {
965	adaptersDone.insert( adaptersDone.begin(), mangleName );
966
967	// apply substitution to type variables to figure out what the adapter's type should look like
968	assert( env );
969	env->apply( realFunction );
970	mangleName = SymTab::Mangler::mangle( realFunction );
971	mangleName += makePolyMonoSuffix( originalFunction, exprTyVars );
972
973	AdapterMap & adapters = Pass1::adapters.top();
974	AdapterMap::iterator adapter = adapters.find( mangleName );
975	if ( adapter == adapters.end() ) {
976	// adapter has not been created yet in the current scope, so define it
977	FunctionDecl newAdapter = makeAdapter( funType, realFunction, mangleName, exprTyVars );
978	adapter = adapters.insert( adapters.begin(), std::pair< std::string, DeclarationWithType *>( mangleName, newAdapter ) );
979	stmtsToAdd.push_back( new DeclStmt( noLabels, newAdapter ) );
980	} // if
981	assert( adapter != adapters.end() );
982
983	// add the appropriate adapter as a parameter
984	appExpr->get_args().push_front( new VariableExpr( adapter->second ) );
985	} // if
986	} // for
987	} // passAdapters
988
989	Expression makeIncrDecrExpr( ApplicationExpr appExpr, Type *polyType, bool isIncr ) {
990	NameExpr *opExpr;
991	if ( isIncr ) {
992	opExpr = new NameExpr( "?+=?" );
993	} else {
994	opExpr = new NameExpr( "?-=?" );
995	} // if
996	UntypedExpr *addAssign = new UntypedExpr( opExpr );
997	if ( AddressExpr address = dynamic_cast< AddressExpr >( appExpr->get_args().front() ) ) {
998	addAssign->get_args().push_back( address->get_arg() );
999	} else {
1000	addAssign->get_args().push_back( appExpr->get_args().front() );
1001	} // if
1002	addAssign->get_args().push_back( new NameExpr( sizeofName( polyType ) ) );
1003	addAssign->get_results().front() = appExpr->get_results().front()->clone();
1004	if ( appExpr->get_env() ) {
1005	addAssign->set_env( appExpr->get_env() );
1006	appExpr->set_env( 0 );
1007	} // if
1008	appExpr->get_args().clear();
1009	delete appExpr;
1010	return addAssign;
1011	}
1012
1013	Expression Pass1::handleIntrinsics( ApplicationExpr appExpr ) {
1014	if ( VariableExpr varExpr = dynamic_cast< VariableExpr >( appExpr->get_function() ) ) {
1015	if ( varExpr->get_var()->get_linkage() == LinkageSpec::Intrinsic ) {
1016	if ( varExpr->get_var()->get_name() == "?[?]" ) {
1017	assert( ! appExpr->get_results().empty() );
1018	assert( appExpr->get_args().size() == 2 );
1019	Type *baseType1 = isPolyPtr( appExpr->get_args().front()->get_results().front(), scopeTyVars, env );
1020	Type *baseType2 = isPolyPtr( appExpr->get_args().back()->get_results().front(), scopeTyVars, env );
1021	assert( ! baseType1 \|\| ! baseType2 ); // the arguments cannot both be polymorphic pointers
1022	UntypedExpr *ret = 0;
1023	if ( baseType1 \|\| baseType2 ) { // one of the arguments is a polymorphic pointer
1024	ret = new UntypedExpr( new NameExpr( "?+?" ) );
1025	} // if
1026	if ( baseType1 ) {
1027	UntypedExpr multiply = new UntypedExpr( new NameExpr( "??" ) );
1028	multiply->get_args().push_back( appExpr->get_args().back() );
1029	multiply->get_args().push_back( new NameExpr( sizeofName( baseType1 ) ) );
1030	ret->get_args().push_back( appExpr->get_args().front() );
1031	ret->get_args().push_back( multiply );
1032	} else if ( baseType2 ) {
1033	UntypedExpr multiply = new UntypedExpr( new NameExpr( "??" ) );
1034	multiply->get_args().push_back( appExpr->get_args().front() );
1035	multiply->get_args().push_back( new NameExpr( sizeofName( baseType2 ) ) );
1036	ret->get_args().push_back( multiply );
1037	ret->get_args().push_back( appExpr->get_args().back() );
1038	} // if
1039	if ( baseType1 \|\| baseType2 ) {
1040	ret->get_results().push_front( appExpr->get_results().front()->clone() );
1041	if ( appExpr->get_env() ) {
1042	ret->set_env( appExpr->get_env() );
1043	appExpr->set_env( 0 );
1044	} // if
1045	appExpr->get_args().clear();
1046	delete appExpr;
1047	return ret;
1048	} // if
1049	} else if ( varExpr->get_var()->get_name() == "*?" ) {
1050	assert( ! appExpr->get_results().empty() );
1051	assert( ! appExpr->get_args().empty() );
1052	if ( isPolyType( appExpr->get_results().front(), scopeTyVars, env ) ) {
1053	Expression *ret = appExpr->get_args().front();
1054	delete ret->get_results().front();
1055	ret->get_results().front() = appExpr->get_results().front()->clone();
1056	if ( appExpr->get_env() ) {
1057	ret->set_env( appExpr->get_env() );
1058	appExpr->set_env( 0 );
1059	} // if
1060	appExpr->get_args().clear();
1061	delete appExpr;
1062	return ret;
1063	} // if
1064	} else if ( varExpr->get_var()->get_name() == "?++" \|\| varExpr->get_var()->get_name() == "?--" ) {
1065	assert( ! appExpr->get_results().empty() );
1066	assert( appExpr->get_args().size() == 1 );
1067	if ( Type *baseType = isPolyPtr( appExpr->get_results().front(), scopeTyVars, env ) ) {
1068	Type *tempType = appExpr->get_results().front()->clone();
1069	if ( env ) {
1070	env->apply( tempType );
1071	} // if
1072	ObjectDecl *newObj = makeTemporary( tempType );
1073	VariableExpr *tempExpr = new VariableExpr( newObj );
1074	UntypedExpr *assignExpr = new UntypedExpr( new NameExpr( "?=?" ) );
1075	assignExpr->get_args().push_back( tempExpr->clone() );
1076	if ( AddressExpr address = dynamic_cast< AddressExpr >( appExpr->get_args().front() ) ) {
1077	assignExpr->get_args().push_back( address->get_arg()->clone() );
1078	} else {
1079	assignExpr->get_args().push_back( appExpr->get_args().front()->clone() );
1080	} // if
1081	CommaExpr *firstComma = new CommaExpr( assignExpr, makeIncrDecrExpr( appExpr, baseType, varExpr->get_var()->get_name() == "?++" ) );
1082	return new CommaExpr( firstComma, tempExpr );
1083	} // if
1084	} else if ( varExpr->get_var()->get_name() == "++?" \|\| varExpr->get_var()->get_name() == "--?" ) {
1085	assert( ! appExpr->get_results().empty() );
1086	assert( appExpr->get_args().size() == 1 );
1087	if ( Type *baseType = isPolyPtr( appExpr->get_results().front(), scopeTyVars, env ) ) {
1088	return makeIncrDecrExpr( appExpr, baseType, varExpr->get_var()->get_name() == "++?" );
1089	} // if
1090	} else if ( varExpr->get_var()->get_name() == "?+?" \|\| varExpr->get_var()->get_name() == "?-?" ) {
1091	assert( ! appExpr->get_results().empty() );
1092	assert( appExpr->get_args().size() == 2 );
1093	Type *baseType1 = isPolyPtr( appExpr->get_args().front()->get_results().front(), scopeTyVars, env );
1094	Type *baseType2 = isPolyPtr( appExpr->get_args().back()->get_results().front(), scopeTyVars, env );
1095	if ( baseType1 && baseType2 ) {
1096	UntypedExpr *divide = new UntypedExpr( new NameExpr( "?/?" ) );
1097	divide->get_args().push_back( appExpr );
1098	divide->get_args().push_back( new NameExpr( sizeofName( baseType1 ) ) );
1099	divide->get_results().push_front( appExpr->get_results().front()->clone() );
1100	if ( appExpr->get_env() ) {
1101	divide->set_env( appExpr->get_env() );
1102	appExpr->set_env( 0 );
1103	} // if
1104	return divide;
1105	} else if ( baseType1 ) {
1106	UntypedExpr multiply = new UntypedExpr( new NameExpr( "??" ) );
1107	multiply->get_args().push_back( appExpr->get_args().back() );
1108	multiply->get_args().push_back( new NameExpr( sizeofName( baseType1 ) ) );
1109	appExpr->get_args().back() = multiply;
1110	} else if ( baseType2 ) {
1111	UntypedExpr multiply = new UntypedExpr( new NameExpr( "??" ) );
1112	multiply->get_args().push_back( appExpr->get_args().front() );
1113	multiply->get_args().push_back( new NameExpr( sizeofName( baseType2 ) ) );
1114	appExpr->get_args().front() = multiply;
1115	} // if
1116	} else if ( varExpr->get_var()->get_name() == "?+=?" \|\| varExpr->get_var()->get_name() == "?-=?" ) {
1117	assert( ! appExpr->get_results().empty() );
1118	assert( appExpr->get_args().size() == 2 );
1119	Type *baseType = isPolyPtr( appExpr->get_results().front(), scopeTyVars, env );
1120	if ( baseType ) {
1121	UntypedExpr multiply = new UntypedExpr( new NameExpr( "??" ) );
1122	multiply->get_args().push_back( appExpr->get_args().back() );
1123	multiply->get_args().push_back( new NameExpr( sizeofName( baseType ) ) );
1124	appExpr->get_args().back() = multiply;
1125	} // if
1126	} // if
1127	return appExpr;
1128	} // if
1129	} // if
1130	return 0;
1131	}
1132
1133	Expression Pass1::mutate( ApplicationExpr appExpr ) {
1134	// std::cerr << "mutate appExpr: ";
1135	// for ( TyVarMap::iterator i = scopeTyVars.begin(); i != scopeTyVars.end(); ++i ) {
1136	// std::cerr << i->first << " ";
1137	// }
1138	// std::cerr << "\n";
1139	bool oldUseRetval = useRetval;
1140	useRetval = false;
1141	appExpr->get_function()->acceptMutator( *this );
1142	mutateAll( appExpr->get_args(), *this );
1143	useRetval = oldUseRetval;
1144
1145	assert( ! appExpr->get_function()->get_results().empty() );
1146	PointerType pointer = dynamic_cast< PointerType >( appExpr->get_function()->get_results().front() );
1147	assert( pointer );
1148	FunctionType function = dynamic_cast< FunctionType >( pointer->get_base() );
1149	assert( function );
1150
1151	if ( Expression *newExpr = handleIntrinsics( appExpr ) ) {
1152	return newExpr;
1153	} // if
1154
1155	Expression *ret = appExpr;
1156
1157	std::list< Expression *>::iterator arg = appExpr->get_args().begin();
1158	std::list< Expression *>::iterator paramBegin = appExpr->get_args().begin();
1159
1160	TyVarMap exprTyVars;
1161	makeTyVarMap( function, exprTyVars );
1162	ReferenceToType *polyRetType = isPolyRet( function );
1163
1164	if ( polyRetType ) {
1165	ret = addPolyRetParam( appExpr, function, polyRetType, arg );
1166	} else if ( needsAdapter( function, scopeTyVars ) ) {
1167	// std::cerr << "needs adapter: ";
1168	// for ( TyVarMap::iterator i = scopeTyVars.begin(); i != scopeTyVars.end(); ++i ) {
1169	// std::cerr << i->first << " ";
1170	// }
1171	// std::cerr << "\n";
1172	// change the application so it calls the adapter rather than the passed function
1173	ret = applyAdapter( appExpr, function, arg, scopeTyVars );
1174	} // if
1175	arg = appExpr->get_args().begin();
1176
1177	passTypeVars( appExpr, polyRetType, arg, exprTyVars );
1178	addInferredParams( appExpr, function, arg, exprTyVars );
1179
1180	arg = paramBegin;
1181
1182	boxParams( appExpr, function, arg, exprTyVars );
1183
1184	passAdapters( appExpr, function, exprTyVars );
1185
1186	return ret;
1187	}
1188
1189	Expression Pass1::mutate( UntypedExpr expr ) {
1190	if ( ! expr->get_results().empty() && isPolyType( expr->get_results().front(), scopeTyVars, env ) ) {
1191	if ( NameExpr name = dynamic_cast< NameExpr >( expr->get_function() ) ) {
1192	if ( name->get_name() == "*?" ) {
1193	Expression *ret = expr->get_args().front();
1194	expr->get_args().clear();
1195	delete expr;
1196	return ret->acceptMutator( *this );
1197	} // if
1198	} // if
1199	} // if
1200	return PolyMutator::mutate( expr );
1201	}
1202
1203	Expression Pass1::mutate( AddressExpr addrExpr ) {
1204	assert( ! addrExpr->get_arg()->get_results().empty() );
1205
1206	bool needs = false;
1207	if ( UntypedExpr expr = dynamic_cast< UntypedExpr >( addrExpr->get_arg() ) ) {
1208	if ( ! expr->get_results().empty() && isPolyType( expr->get_results().front(), scopeTyVars, env ) ) {
1209	if ( NameExpr name = dynamic_cast< NameExpr >( expr->get_function() ) ) {
1210	if ( name->get_name() == "*?" ) {
1211	if ( ApplicationExpr * appExpr = dynamic_cast< ApplicationExpr * >( expr->get_args().front() ) ) {
1212	assert( ! appExpr->get_function()->get_results().empty() );
1213	PointerType pointer = dynamic_cast< PointerType >( appExpr->get_function()->get_results().front() );
1214	assert( pointer );
1215	FunctionType function = dynamic_cast< FunctionType >( pointer->get_base() );
1216	assert( function );
1217	needs = needsAdapter( function, scopeTyVars );
1218	} // if
1219	} // if
1220	} // if
1221	} // if
1222	} // if
1223	addrExpr->set_arg( mutateExpression( addrExpr->get_arg() ) );
1224	if ( isPolyType( addrExpr->get_arg()->get_results().front(), scopeTyVars, env ) \|\| needs ) {
1225	Expression *ret = addrExpr->get_arg();
1226	delete ret->get_results().front();
1227	ret->get_results().front() = addrExpr->get_results().front()->clone();
1228	addrExpr->set_arg( 0 );
1229	delete addrExpr;
1230	return ret;
1231	} else {
1232	return addrExpr;
1233	} // if
1234	}
1235
1236	/// Wraps a function declaration in a new pointer-to-function variable expression
1237	VariableExpr wrapFunctionDecl( DeclarationWithType functionDecl ) {
1238	// line below cloned from FixFunction.cc
1239	ObjectDecl *functionObj = new ObjectDecl( functionDecl->get_name(), functionDecl->get_storageClass(), functionDecl->get_linkage(), 0,
1240	new PointerType( Type::Qualifiers(), functionDecl->get_type()->clone() ), 0 );
1241	functionObj->set_mangleName( functionDecl->get_mangleName() );
1242	return new VariableExpr( functionObj );
1243	}
1244
1245	Statement * Pass1::mutate( ReturnStmt *returnStmt ) {
1246	if ( retval && returnStmt->get_expr() ) {
1247	assert( ! returnStmt->get_expr()->get_results().empty() );
1248	// *** Code Removal *** After introducing a temporary variable for all return expressions, the following code appears superfluous.
1249	// if ( returnStmt->get_expr()->get_results().front()->get_isLvalue() ) {
1250	// by this point, a cast expr on a polymorphic return value is redundant
1251	while ( CastExpr castExpr = dynamic_cast< CastExpr >( returnStmt->get_expr() ) ) {
1252	returnStmt->set_expr( castExpr->get_arg() );
1253	returnStmt->get_expr()->set_env( castExpr->get_env() );
1254	castExpr->set_env( 0 );
1255	castExpr->set_arg( 0 );
1256	delete castExpr;
1257	} //while
1258
1259	// find assignment operator for (polymorphic) return type
1260	ApplicationExpr *assignExpr = 0;
1261	if ( TypeInstType typeInst = dynamic_cast< TypeInstType >( retval->get_type() ) ) {
1262	// find assignment operator for type variable
1263	std::map< std::string, DeclarationWithType *>::const_iterator assignIter = assignOps.find( typeInst->get_name() );
1264	if ( assignIter == assignOps.end() ) {
1265	throw SemanticError( "Attempt to return dtype or ftype object in ", returnStmt->get_expr() );
1266	} // if
1267	assignExpr = new ApplicationExpr( new VariableExpr( assignIter->second ) );
1268	} else if ( ReferenceToType refType = dynamic_cast< ReferenceToType >( retval->get_type() ) ) {
1269	// find assignment operator for generic type
1270	DeclarationWithType *functionDecl = scopedAssignOps.find( refType );
1271	if ( ! functionDecl ) {
1272	throw SemanticError( "Attempt to return dtype or ftype generic object in ", returnStmt->get_expr() );
1273	}
1274
1275	// wrap it up in an application expression
1276	assignExpr = new ApplicationExpr( wrapFunctionDecl( functionDecl ) );
1277	assignExpr->set_env( env->clone() );
1278
1279	// find each of its needed secondary assignment operators
1280	std::list< Expression* > &tyParams = refType->get_parameters();
1281	std::list< TypeDecl* > &forallParams = functionDecl->get_type()->get_forall();
1282	std::list< Expression* >::const_iterator tyIt = tyParams.begin();
1283	std::list< TypeDecl* >::const_iterator forallIt = forallParams.begin();
1284	for ( ; tyIt != tyParams.end() && forallIt != forallParams.end(); ++tyIt, ++forallIt ) {
1285	if ( (*forallIt)->get_kind() != TypeDecl::Any ) continue; // skip types with no assign op (ftype/dtype)
1286
1287	std::list< DeclarationWithType* > &asserts = (*forallIt)->get_assertions();
1288	assert( ! asserts.empty() && "Type param needs assignment operator assertion" );
1289	DeclarationWithType *actualDecl = asserts.front();
1290	TypeInstType *actualType = isTypeInstAssignment( actualDecl );
1291	assert( actualType && "First assertion of type with assertions should be assignment operator" );
1292	TypeExpr formalTypeExpr = dynamic_cast< TypeExpr >( *tyIt );
1293	assert( formalTypeExpr && "type parameters must be type expressions" );
1294	Type *formalType = formalTypeExpr->get_type();
1295	assignExpr->get_env()->add( actualType->get_name(), formalType );
1296
1297	DeclarationWithType *assertAssign = 0;
1298	if ( TypeInstType formalTypeInstType = dynamic_cast< TypeInstType >( formalType ) ) {
1299	std::map< std::string, DeclarationWithType *>::const_iterator assertAssignIt = assignOps.find( formalTypeInstType->get_name() );
1300	if ( assertAssignIt == assignOps.end() ) {
1301	throw SemanticError( "No assignment operation found for ", formalTypeInstType );
1302	}
1303	assertAssign = assertAssignIt->second;
1304	} else {
1305	assertAssign = scopedAssignOps.find( formalType );
1306	if ( ! assertAssign ) {
1307	throw SemanticError( "No assignment operation found for ", formalType );
1308	}
1309	}
1310
1311
1312	assignExpr->get_inferParams()[ actualDecl->get_uniqueId() ]
1313	= ParamEntry( assertAssign->get_uniqueId(), assertAssign->get_type()->clone(), actualDecl->get_type()->clone(), wrapFunctionDecl( assertAssign ) );
1314	}
1315	}
1316	assert( assignExpr );
1317
1318	// replace return statement with appropriate assignment to out parameter
1319	Expression *retParm = new NameExpr( retval->get_name() );
1320	retParm->get_results().push_back( new PointerType( Type::Qualifiers(), retval->get_type()->clone() ) );
1321	assignExpr->get_args().push_back( retParm );
1322	assignExpr->get_args().push_back( returnStmt->get_expr() );
1323	stmtsToAdd.push_back( new ExprStmt( noLabels, mutateExpression( assignExpr ) ) );
1324	// } else {
1325	// useRetval = true;
1326	// stmtsToAdd.push_back( new ExprStmt( noLabels, mutateExpression( returnStmt->get_expr() ) ) );
1327	// useRetval = false;
1328	// } // if
1329	returnStmt->set_expr( 0 );
1330	} else {
1331	returnStmt->set_expr( mutateExpression( returnStmt->get_expr() ) );
1332	} // if
1333	return returnStmt;
1334	}
1335
1336	Type * Pass1::mutate( PointerType *pointerType ) {
1337	TyVarMap oldtyVars = scopeTyVars;
1338	makeTyVarMap( pointerType, scopeTyVars );
1339
1340	Type *ret = Mutator::mutate( pointerType );
1341
1342	scopeTyVars = oldtyVars;
1343	return ret;
1344	}
1345
1346	Type * Pass1::mutate( FunctionType *functionType ) {
1347	TyVarMap oldtyVars = scopeTyVars;
1348	makeTyVarMap( functionType, scopeTyVars );
1349
1350	Type *ret = Mutator::mutate( functionType );
1351
1352	scopeTyVars = oldtyVars;
1353	return ret;
1354	}
1355
1356	void Pass1::doBeginScope() {
1357	// push a copy of the current map
1358	adapters.push(adapters.top());
1359	scopedAssignOps.beginScope();
1360	}
1361
1362	void Pass1::doEndScope() {
1363	adapters.pop();
1364	scopedAssignOps.endScope();
1365	}
1366
1367	////////////////////////////////////////// Pass2 ////////////////////////////////////////////////////
1368
1369	void Pass2::addAdapters( FunctionType *functionType ) {
1370	std::list< DeclarationWithType *> &paramList = functionType->get_parameters();
1371	std::list< FunctionType *> functions;
1372	for ( std::list< DeclarationWithType *>::iterator arg = paramList.begin(); arg != paramList.end(); ++arg ) {
1373	Type orig = (arg)->get_type();
1374	findAndReplaceFunction( orig, functions, scopeTyVars, needsAdapter );
1375	(*arg)->set_type( orig );
1376	}
1377	std::set< std::string > adaptersDone;
1378	for ( std::list< FunctionType *>::iterator funType = functions.begin(); funType != functions.end(); ++funType ) {
1379	std::string mangleName = mangleAdapterName( *funType, scopeTyVars );
1380	if ( adaptersDone.find( mangleName ) == adaptersDone.end() ) {
1381	std::string adapterName = makeAdapterName( mangleName );
1382	paramList.push_front( new ObjectDecl( adapterName, DeclarationNode::NoStorageClass, LinkageSpec::C, 0, new PointerType( Type::Qualifiers(), makeAdapterType( *funType, scopeTyVars ) ), 0 ) );
1383	adaptersDone.insert( adaptersDone.begin(), mangleName );
1384	}
1385	}
1386	// deleteAll( functions );
1387	}
1388
1389	template< typename DeclClass >
1390	DeclClass * Pass2::handleDecl( DeclClass decl, Type type ) {
1391	DeclClass ret = static_cast< DeclClass >( Mutator::mutate( decl ) );
1392
1393	return ret;
1394	}
1395
1396	DeclarationWithType * Pass2::mutate( FunctionDecl *functionDecl ) {
1397	return handleDecl( functionDecl, functionDecl->get_functionType() );
1398	}
1399
1400	ObjectDecl * Pass2::mutate( ObjectDecl *objectDecl ) {
1401	return handleDecl( objectDecl, objectDecl->get_type() );
1402	}
1403
1404	TypeDecl * Pass2::mutate( TypeDecl *typeDecl ) {
1405	scopeTyVars[ typeDecl->get_name() ] = typeDecl->get_kind();
1406	if ( typeDecl->get_base() ) {
1407	return handleDecl( typeDecl, typeDecl->get_base() );
1408	} else {
1409	return Mutator::mutate( typeDecl );
1410	}
1411	}
1412
1413	TypedefDecl * Pass2::mutate( TypedefDecl *typedefDecl ) {
1414	return handleDecl( typedefDecl, typedefDecl->get_base() );
1415	}
1416
1417	Type * Pass2::mutate( PointerType *pointerType ) {
1418	TyVarMap oldtyVars = scopeTyVars;
1419	makeTyVarMap( pointerType, scopeTyVars );
1420
1421	Type *ret = Mutator::mutate( pointerType );
1422
1423	scopeTyVars = oldtyVars;
1424	return ret;
1425	}
1426
1427	Type Pass2::mutate( FunctionType funcType ) {
1428	TyVarMap oldtyVars = scopeTyVars;
1429	makeTyVarMap( funcType, scopeTyVars );
1430
1431	// move polymorphic return type to parameter list
1432	if ( isPolyRet( funcType ) ) {
1433	DeclarationWithType *ret = funcType->get_returnVals().front();
1434	ret->set_type( new PointerType( Type::Qualifiers(), ret->get_type() ) );
1435	funcType->get_parameters().push_front( ret );
1436	funcType->get_returnVals().pop_front();
1437	}
1438
1439	// add size/align and assertions for type parameters to parameter list
1440	std::list< DeclarationWithType *>::iterator last = funcType->get_parameters().begin();
1441	std::list< DeclarationWithType *> inferredParams;
1442	ObjectDecl newObj( "", DeclarationNode::NoStorageClass, LinkageSpec::C, 0, new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt ), 0 );
1443	ObjectDecl newPtr( "", DeclarationNode::NoStorageClass, LinkageSpec::C, 0,
1444	new PointerType( Type::Qualifiers(), new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt ) ), 0 );
1445	// ObjectDecl *newFunPtr = new ObjectDecl( "", DeclarationNode::NoStorageClass, LinkageSpec::Cforall, 0, new PointerType( Type::Qualifiers(), new FunctionType( Type::Qualifiers(), true ) ), 0 );
1446	for ( std::list< TypeDecl *>::const_iterator tyParm = funcType->get_forall().begin(); tyParm != funcType->get_forall().end(); ++tyParm ) {
1447	ObjectDecl sizeParm, alignParm;
1448	// add all size and alignment parameters to parameter list
1449	if ( (*tyParm)->get_kind() == TypeDecl::Any ) {
1450	TypeInstType parmType( Type::Qualifiers(), (tyParm)->get_name(), tyParm );
1451
1452	sizeParm = newObj.clone();
1453	sizeParm->set_name( sizeofName( &parmType ) );
1454	last = funcType->get_parameters().insert( last, sizeParm );
1455	++last;
1456
1457	alignParm = newObj.clone();
1458	alignParm->set_name( alignofName( &parmType ) );
1459	last = funcType->get_parameters().insert( last, alignParm );
1460	++last;
1461	}
1462	// move all assertions into parameter list
1463	for ( std::list< DeclarationWithType >::iterator assert = (tyParm)->get_assertions().begin(); assert != (*tyParm)->get_assertions().end(); ++assert ) {
1464	// assert = (assert)->acceptMutator( *this );
1465	inferredParams.push_back( *assert );
1466	}
1467	(*tyParm)->get_assertions().clear();
1468	}
1469
1470	// add size/align for generic parameter types to parameter list
1471	std::set< std::string > seenTypes; // sizeofName for generic types we've seen
1472	for ( std::list< DeclarationWithType* >::const_iterator fnParm = last; fnParm != funcType->get_parameters().end(); ++fnParm ) {
1473	Type polyBase = hasPolyBase( (fnParm)->get_type(), scopeTyVars );
1474	if ( polyBase && ! dynamic_cast< TypeInstType* >( polyBase ) ) {
1475	std::string sizeName = sizeofName( polyBase );
1476	if ( seenTypes.count( sizeName ) ) continue;
1477
1478	ObjectDecl sizeParm, alignParm, *offsetParm;
1479	sizeParm = newObj.clone();
1480	sizeParm->set_name( sizeName );
1481	last = funcType->get_parameters().insert( last, sizeParm );
1482	++last;
1483
1484	alignParm = newObj.clone();
1485	alignParm->set_name( alignofName( polyBase ) );
1486	last = funcType->get_parameters().insert( last, alignParm );
1487	++last;
1488
1489	if ( dynamic_cast< StructInstType* >( polyBase ) ) {
1490	offsetParm = newPtr.clone();
1491	offsetParm->set_name( offsetofName( polyBase ) );
1492	last = funcType->get_parameters().insert( last, offsetParm );
1493	++last;
1494	}
1495
1496	seenTypes.insert( sizeName );
1497	}
1498	}
1499
1500	// splice assertion parameters into parameter list
1501	funcType->get_parameters().splice( last, inferredParams );
1502	addAdapters( funcType );
1503	mutateAll( funcType->get_returnVals(), *this );
1504	mutateAll( funcType->get_parameters(), *this );
1505
1506	scopeTyVars = oldtyVars;
1507	return funcType;
1508	}
1509
1510	////////////////////////////////////////// MemberExprFixer ////////////////////////////////////////////////////
1511
1512	template< typename DeclClass >
1513	DeclClass * MemberExprFixer::handleDecl( DeclClass decl, Type type ) {
1514	TyVarMap oldtyVars = scopeTyVars;
1515	makeTyVarMap( type, scopeTyVars );
1516
1517	DeclClass ret = static_cast< DeclClass >( Mutator::mutate( decl ) );
1518
1519	scopeTyVars = oldtyVars;
1520	return ret;
1521	}
1522
1523	ObjectDecl * MemberExprFixer::mutate( ObjectDecl *objectDecl ) {
1524	return handleDecl( objectDecl, objectDecl->get_type() );
1525	}
1526
1527	DeclarationWithType * MemberExprFixer::mutate( FunctionDecl *functionDecl ) {
1528	return handleDecl( functionDecl, functionDecl->get_functionType() );
1529	}
1530
1531	TypedefDecl * MemberExprFixer::mutate( TypedefDecl *typedefDecl ) {
1532	return handleDecl( typedefDecl, typedefDecl->get_base() );
1533	}
1534
1535	TypeDecl * MemberExprFixer::mutate( TypeDecl *typeDecl ) {
1536	scopeTyVars[ typeDecl->get_name() ] = typeDecl->get_kind();
1537	return Mutator::mutate( typeDecl );
1538	}
1539
1540	Type * MemberExprFixer::mutate( PointerType *pointerType ) {
1541	TyVarMap oldtyVars = scopeTyVars;
1542	makeTyVarMap( pointerType, scopeTyVars );
1543
1544	Type *ret = Mutator::mutate( pointerType );
1545
1546	scopeTyVars = oldtyVars;
1547	return ret;
1548	}
1549
1550	Type * MemberExprFixer::mutate( FunctionType *functionType ) {
1551	TyVarMap oldtyVars = scopeTyVars;
1552	makeTyVarMap( functionType, scopeTyVars );
1553
1554	Type *ret = Mutator::mutate( functionType );
1555
1556	scopeTyVars = oldtyVars;
1557	return ret;
1558	}
1559
1560	Statement MemberExprFixer::mutate( DeclStmt declStmt ) {
1561	if ( ObjectDecl objectDecl = dynamic_cast< ObjectDecl >( declStmt->get_decl() ) ) {
1562	if ( isPolyType( objectDecl->get_type(), scopeTyVars ) ) {
1563	// change initialization of a polymorphic value object
1564	// to allocate storage with alloca
1565	Type *declType = objectDecl->get_type();
1566	UntypedExpr *alloc = new UntypedExpr( new NameExpr( "__builtin_alloca" ) );
1567	alloc->get_args().push_back( new NameExpr( sizeofName( declType ) ) );
1568
1569	delete objectDecl->get_init();
1570
1571	std::list<Expression*> designators;
1572	objectDecl->set_init( new SingleInit( alloc, designators ) );
1573	}
1574	}
1575	return Mutator::mutate( declStmt );
1576	}
1577
1578	/// Finds the member in the base list that matches the given declaration; returns its index, or -1 if not present
1579	long findMember( DeclarationWithType memberDecl, std::list< Declaration > &baseDecls ) {
1580	long i = 0;
1581	for(std::list< Declaration* >::const_iterator decl = baseDecls.begin(); decl != baseDecls.end(); ++decl, ++i ) {
1582	if ( memberDecl->get_name() != (*decl)->get_name() ) continue;
1583
1584	if ( DeclarationWithType declWithType = dynamic_cast< DeclarationWithType >( *decl ) ) {
1585	if ( memberDecl->get_mangleName().empty() \|\| declWithType->get_mangleName().empty()
1586	\|\| memberDecl->get_mangleName() == declWithType->get_mangleName() ) return i;
1587	else continue;
1588	} else return i;
1589	}
1590	return -1;
1591	}
1592
1593	/// Returns an index expression into the offset array for a type
1594	Expression makeOffsetIndex( Type objectType, long i ) {
1595	std::stringstream offset_namer;
1596	offset_namer << i;
1597	ConstantExpr *fieldIndex = new ConstantExpr( Constant( new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt ), offset_namer.str() ) );
1598	UntypedExpr *fieldOffset = new UntypedExpr( new NameExpr( "?[?]" ) );
1599	fieldOffset->get_args().push_back( new NameExpr( offsetofName( objectType ) ) );
1600	fieldOffset->get_args().push_back( fieldIndex );
1601	return fieldOffset;
1602	}
1603
1604	/// Returns an expression dereferenced n times
1605	Expression makeDerefdVar( Expression derefdVar, long n ) {
1606	for ( int i = 1; i < n; ++i ) {
1607	UntypedExpr derefExpr = new UntypedExpr( new NameExpr( "?" ) );
1608	derefExpr->get_args().push_back( derefdVar );
1609	derefdVar = derefExpr;
1610	}
1611	return derefdVar;
1612	}
1613
1614	Expression MemberExprFixer::mutate( MemberExpr memberExpr ) {
1615	// mutate, exiting early if no longer MemberExpr
1616	Expression *expr = Mutator::mutate( memberExpr );
1617	memberExpr = dynamic_cast< MemberExpr* >( expr );
1618	if ( ! memberExpr ) return expr;
1619
1620	// get declaration for base struct, exiting early if not found
1621	int varDepth;
1622	VariableExpr *varExpr = getBaseVar( memberExpr->get_aggregate(), &varDepth );
1623	if ( ! varExpr ) return memberExpr;
1624	ObjectDecl objectDecl = dynamic_cast< ObjectDecl >( varExpr->get_var() );
1625	if ( ! objectDecl ) return memberExpr;
1626
1627	// only mutate member expressions for polymorphic types
1628	int tyDepth;
1629	Type *objectType = hasPolyBase( objectDecl->get_type(), scopeTyVars, &tyDepth );
1630	if ( ! objectType ) return memberExpr;
1631
1632	Expression *newMemberExpr = 0;
1633	if ( StructInstType structType = dynamic_cast< StructInstType >( objectType ) ) {
1634	// look up offset index
1635	long i = findMember( memberExpr->get_member(), structType->get_baseStruct()->get_members() );
1636	if ( i == -1 ) return memberExpr;
1637
1638	// replace member expression with pointer to base plus offset
1639	UntypedExpr *fieldLoc = new UntypedExpr( new NameExpr( "?+?" ) );
1640	fieldLoc->get_args().push_back( makeDerefdVar( varExpr->clone(), varDepth ) );
1641	fieldLoc->get_args().push_back( makeOffsetIndex( objectType, i ) );
1642	newMemberExpr = fieldLoc;
1643	} else if ( dynamic_cast< UnionInstType* >( objectType ) ) {
1644	// union members are all at offset zero, so build appropriately-dereferenced variable
1645	newMemberExpr = makeDerefdVar( varExpr->clone(), varDepth );
1646	} else return memberExpr;
1647	assert( newMemberExpr );
1648
1649	Type *memberType = memberExpr->get_member()->get_type();
1650	if ( ! isPolyType( memberType, scopeTyVars ) ) {
1651	// 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
1652	CastExpr *ptrCastExpr = new CastExpr( newMemberExpr, new PointerType( Type::Qualifiers(), memberType->clone() ) );
1653	UntypedExpr derefExpr = new UntypedExpr( new NameExpr( "?" ) );
1654	derefExpr->get_args().push_back( ptrCastExpr );
1655	newMemberExpr = derefExpr;
1656	}
1657
1658	delete memberExpr;
1659	return newMemberExpr;
1660	}
1661
1662	Expression MemberExprFixer::mutate( OffsetofExpr offsetofExpr ) {
1663	// mutate, exiting early if no longer OffsetofExpr
1664	Expression *expr = Mutator::mutate( offsetofExpr );
1665	offsetofExpr = dynamic_cast< OffsetofExpr* >( expr );
1666	if ( ! offsetofExpr ) return expr;
1667
1668	// only mutate expressions for polymorphic structs/unions
1669	Type *ty = isPolyType( offsetofExpr->get_type(), scopeTyVars );
1670	if ( ! ty ) return offsetofExpr;
1671
1672	if ( StructInstType structType = dynamic_cast< StructInstType >( ty ) ) {
1673	// replace offsetof expression by index into offset array
1674	long i = findMember( offsetofExpr->get_member(), structType->get_baseStruct()->get_members() );
1675	if ( i == -1 ) return offsetofExpr;
1676
1677	Expression *offsetInd = makeOffsetIndex( ty, i );
1678	delete offsetofExpr;
1679	return offsetInd;
1680	} else if ( dynamic_cast< UnionInstType* >( ty ) ) {
1681	// all union members are at offset zero
1682	delete offsetofExpr;
1683	return new ConstantExpr( Constant( new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt ), std::string("0") ) );
1684	} else return offsetofExpr;
1685	}
1686
1687	////////////////////////////////////////// Pass3 ////////////////////////////////////////////////////
1688
1689	template< typename DeclClass >
1690	DeclClass * Pass3::handleDecl( DeclClass decl, Type type ) {
1691	TyVarMap oldtyVars = scopeTyVars;
1692	makeTyVarMap( type, scopeTyVars );
1693
1694	DeclClass ret = static_cast< DeclClass >( Mutator::mutate( decl ) );
1695	ScrubTyVars::scrub( decl, scopeTyVars );
1696
1697	scopeTyVars = oldtyVars;
1698	return ret;
1699	}
1700
1701	ObjectDecl * Pass3::mutate( ObjectDecl *objectDecl ) {
1702	return handleDecl( objectDecl, objectDecl->get_type() );
1703	}
1704
1705	DeclarationWithType * Pass3::mutate( FunctionDecl *functionDecl ) {
1706	return handleDecl( functionDecl, functionDecl->get_functionType() );
1707	}
1708
1709	TypedefDecl * Pass3::mutate( TypedefDecl *typedefDecl ) {
1710	return handleDecl( typedefDecl, typedefDecl->get_base() );
1711	}
1712
1713	TypeDecl * Pass3::mutate( TypeDecl *typeDecl ) {
1714	// Initializer *init = 0;
1715	// std::list< Expression *> designators;
1716	// scopeTyVars[ typeDecl->get_name() ] = typeDecl->get_kind();
1717	// if ( typeDecl->get_base() ) {
1718	// init = new SimpleInit( new SizeofExpr( handleDecl( typeDecl, typeDecl->get_base() ) ), designators );
1719	// }
1720	// return new ObjectDecl( typeDecl->get_name(), Declaration::Extern, LinkageSpec::C, 0, new BasicType( Type::Qualifiers(), BasicType::UnsignedInt ), init );
1721
1722	scopeTyVars[ typeDecl->get_name() ] = typeDecl->get_kind();
1723	return Mutator::mutate( typeDecl );
1724	}
1725
1726	Type * Pass3::mutate( PointerType *pointerType ) {
1727	TyVarMap oldtyVars = scopeTyVars;
1728	makeTyVarMap( pointerType, scopeTyVars );
1729
1730	Type *ret = Mutator::mutate( pointerType );
1731
1732	scopeTyVars = oldtyVars;
1733	return ret;
1734	}
1735
1736	Type * Pass3::mutate( FunctionType *functionType ) {
1737	TyVarMap oldtyVars = scopeTyVars;
1738	makeTyVarMap( functionType, scopeTyVars );
1739
1740	Type *ret = Mutator::mutate( functionType );
1741
1742	scopeTyVars = oldtyVars;
1743	return ret;
1744	}
1745	} // anonymous namespace
1746	} // namespace GenPoly
1747
1748	// Local Variables: //
1749	// tab-width: 4 //
1750	// mode: c++ //
1751	// compile-command: "make install" //
1752	// End: //

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

Download in other formats: