Context Navigation

source: src/GenPoly/GenPoly.cc @ 5715d43

ADTarm-ehast-experimentalenumforall-pointer-decayjacob/cs343-translationnew-astnew-ast-unique-exprpthread-emulationqualifiedEnum

Last change on this file since 5715d43 was 8d70648, checked in by Aaron Moss <a3moss@…>, 5 years ago
Merge branch 'master' of plg.uwaterloo.ca:software/cfa/cfa-cc
Property mode set to `100644`
File size: 19.6 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	// GenPoly.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 : Wed Jun 29 21:45:53 2016
13	// Update Count : 14
14	//
15
16	#include "GenPoly.h"
17
18	#include <cassert> // for assertf, assert
19	#include <iostream> // for operator<<, ostream, basic_os...
20	#include <iterator> // for back_insert_iterator, back_in...
21	#include <list> // for list, _List_iterator, list<>:...
22	#include <typeindex> // for type_index
23	#include <utility> // for pair
24	#include <vector> // for vector
25
26	#include "AST/Type.hpp"
27	#include "GenPoly/ErasableScopedMap.h" // for ErasableScopedMap<>::const_it...
28	#include "ResolvExpr/typeops.h" // for flatten
29	#include "SynTree/Constant.h" // for Constant
30	#include "SynTree/Expression.h" // for Expression, TypeExpr, Constan...
31	#include "SynTree/Type.h" // for Type, StructInstType, UnionIn...
32	#include "SynTree/TypeSubstitution.h" // for TypeSubstitution
33
34	using namespace std;
35
36	namespace GenPoly {
37	namespace {
38	/// Checks a parameter list for polymorphic parameters; will substitute according to env if present
39	bool hasPolyParams( std::list< Expression* >& params, const TypeSubstitution *env ) {
40	for ( std::list< Expression* >::iterator param = params.begin(); param != params.end(); ++param ) {
41	TypeExpr paramType = dynamic_cast< TypeExpr >( *param );
42	assertf(paramType, "Aggregate parameters should be type expressions");
43	if ( isPolyType( paramType->get_type(), env ) ) return true;
44	}
45	return false;
46	}
47
48	/// Checks a parameter list for polymorphic parameters from tyVars; will substitute according to env if present
49	bool hasPolyParams( std::list< Expression* >& params, const TyVarMap &tyVars, const TypeSubstitution *env ) {
50	for ( std::list< Expression* >::iterator param = params.begin(); param != params.end(); ++param ) {
51	TypeExpr paramType = dynamic_cast< TypeExpr >( *param );
52	assertf(paramType, "Aggregate parameters should be type expressions");
53	if ( isPolyType( paramType->get_type(), tyVars, env ) ) return true;
54	}
55	return false;
56	}
57
58	/// Checks a parameter list for dynamic-layout parameters from tyVars; will substitute according to env if present
59	bool hasDynParams( std::list< Expression* >& params, const TyVarMap &tyVars, const TypeSubstitution *env ) {
60	for ( std::list< Expression* >::iterator param = params.begin(); param != params.end(); ++param ) {
61	TypeExpr paramType = dynamic_cast< TypeExpr >( *param );
62	assertf(paramType, "Aggregate parameters should be type expressions");
63	if ( isDynType( paramType->get_type(), tyVars, env ) ) return true;
64	}
65	return false;
66	}
67
68	/// Checks a parameter list for inclusion of polymorphic parameters; will substitute according to env if present
69	bool includesPolyParams( std::list< Expression* >& params, const TypeSubstitution *env ) {
70	for ( std::list< Expression* >::iterator param = params.begin(); param != params.end(); ++param ) {
71	TypeExpr paramType = dynamic_cast< TypeExpr >( *param );
72	assertf(paramType, "Aggregate parameters should be type expressions");
73	if ( includesPolyType( paramType->get_type(), env ) ) return true;
74	}
75	return false;
76	}
77
78	/// Checks a parameter list for inclusion of polymorphic parameters from tyVars; will substitute according to env if present
79	bool includesPolyParams( std::list< Expression* >& params, const TyVarMap &tyVars, const TypeSubstitution *env ) {
80	for ( std::list< Expression* >::iterator param = params.begin(); param != params.end(); ++param ) {
81	TypeExpr paramType = dynamic_cast< TypeExpr >( *param );
82	assertf(paramType, "Aggregate parameters should be type expressions");
83	if ( includesPolyType( paramType->get_type(), tyVars, env ) ) return true;
84	}
85	return false;
86	}
87	}
88
89	Type* replaceTypeInst( Type* type, const TypeSubstitution* env ) {
90	if ( ! env ) return type;
91	if ( TypeInstType typeInst = dynamic_cast< TypeInstType >( type ) ) {
92	Type *newType = env->lookup( typeInst->get_name() );
93	if ( newType ) return newType;
94	}
95	return type;
96	}
97
98	Type isPolyType( Type type, const TypeSubstitution *env ) {
99	type = replaceTypeInst( type, env );
100
101	if ( dynamic_cast< TypeInstType * >( type ) ) {
102	return type;
103	} else if ( ArrayType * arrayType = dynamic_cast< ArrayType * >( type ) ) {
104	return isPolyType( arrayType->base, env );
105	} else if ( StructInstType structType = dynamic_cast< StructInstType >( type ) ) {
106	if ( hasPolyParams( structType->get_parameters(), env ) ) return type;
107	} else if ( UnionInstType unionType = dynamic_cast< UnionInstType >( type ) ) {
108	if ( hasPolyParams( unionType->get_parameters(), env ) ) return type;
109	}
110	return 0;
111	}
112
113	Type isPolyType( Type type, const TyVarMap &tyVars, const TypeSubstitution *env ) {
114	type = replaceTypeInst( type, env );
115
116	if ( TypeInstType typeInst = dynamic_cast< TypeInstType >( type ) ) {
117	if ( tyVars.find( typeInst->get_name() ) != tyVars.end() ) {
118	return type;
119	}
120	} else if ( ArrayType * arrayType = dynamic_cast< ArrayType * >( type ) ) {
121	return isPolyType( arrayType->base, tyVars, env );
122	} else if ( StructInstType structType = dynamic_cast< StructInstType >( type ) ) {
123	if ( hasPolyParams( structType->get_parameters(), tyVars, env ) ) return type;
124	} else if ( UnionInstType unionType = dynamic_cast< UnionInstType >( type ) ) {
125	if ( hasPolyParams( unionType->get_parameters(), tyVars, env ) ) return type;
126	}
127	return 0;
128	}
129
130	ReferenceToType isDynType( Type type, const TyVarMap &tyVars, const TypeSubstitution *env ) {
131	type = replaceTypeInst( type, env );
132
133	if ( TypeInstType typeInst = dynamic_cast< TypeInstType >( type ) ) {
134	auto var = tyVars.find( typeInst->get_name() );
135	if ( var != tyVars.end() && var->second.isComplete ) {
136	return typeInst;
137	}
138	} else if ( StructInstType structType = dynamic_cast< StructInstType >( type ) ) {
139	if ( hasDynParams( structType->get_parameters(), tyVars, env ) ) return structType;
140	} else if ( UnionInstType unionType = dynamic_cast< UnionInstType >( type ) ) {
141	if ( hasDynParams( unionType->get_parameters(), tyVars, env ) ) return unionType;
142	}
143	return 0;
144	}
145
146	ReferenceToType isDynRet( FunctionType function, const TyVarMap &forallTypes ) {
147	if ( function->get_returnVals().empty() ) return 0;
148
149	return (ReferenceToType*)isDynType( function->get_returnVals().front()->get_type(), forallTypes );
150	}
151
152	ReferenceToType isDynRet( FunctionType function ) {
153	if ( function->get_returnVals().empty() ) return 0;
154
155	TyVarMap forallTypes( TypeDecl::Data{} );
156	makeTyVarMap( function, forallTypes );
157	return (ReferenceToType*)isDynType( function->get_returnVals().front()->get_type(), forallTypes );
158	}
159
160	bool needsAdapter( FunctionType *adaptee, const TyVarMap &tyVars ) {
161	// if ( ! adaptee->get_returnVals().empty() && isPolyType( adaptee->get_returnVals().front()->get_type(), tyVars ) ) {
162	// return true;
163	// } // if
164	if ( isDynRet( adaptee, tyVars ) ) return true;
165
166	for ( std::list< DeclarationWithType* >::const_iterator innerArg = adaptee->get_parameters().begin(); innerArg != adaptee->get_parameters().end(); ++innerArg ) {
167	// if ( isPolyType( (*innerArg)->get_type(), tyVars ) ) {
168	if ( isDynType( (*innerArg)->get_type(), tyVars ) ) {
169	return true;
170	} // if
171	} // for
172	return false;
173	}
174
175	Type isPolyPtr( Type type, const TypeSubstitution *env ) {
176	type = replaceTypeInst( type, env );
177
178	if ( PointerType ptr = dynamic_cast< PointerType >( type ) ) {
179	return isPolyType( ptr->get_base(), env );
180	}
181	return 0;
182	}
183
184	Type isPolyPtr( Type type, const TyVarMap &tyVars, const TypeSubstitution *env ) {
185	type = replaceTypeInst( type, env );
186
187	if ( PointerType ptr = dynamic_cast< PointerType >( type ) ) {
188	return isPolyType( ptr->get_base(), tyVars, env );
189	}
190	return 0;
191	}
192
193	Type * hasPolyBase( Type type, int levels, const TypeSubstitution *env ) {
194	int dummy;
195	if ( ! levels ) { levels = &dummy; }
196	*levels = 0;
197
198	while ( true ) {
199	type = replaceTypeInst( type, env );
200
201	if ( PointerType ptr = dynamic_cast< PointerType >( type ) ) {
202	type = ptr->get_base();
203	++(*levels);
204	} else break;
205	}
206
207	return isPolyType( type, env );
208	}
209
210	Type * hasPolyBase( Type type, const TyVarMap &tyVars, int levels, const TypeSubstitution *env ) {
211	int dummy;
212	if ( ! levels ) { levels = &dummy; }
213	*levels = 0;
214
215	while ( true ) {
216	type = replaceTypeInst( type, env );
217
218	if ( PointerType ptr = dynamic_cast< PointerType >( type ) ) {
219	type = ptr->get_base();
220	++(*levels);
221	} else break;
222	}
223
224	return isPolyType( type, tyVars, env );
225	}
226
227	bool includesPolyType( Type type, const TypeSubstitution env ) {
228	type = replaceTypeInst( type, env );
229
230	if ( dynamic_cast< TypeInstType * >( type ) ) {
231	return true;
232	} else if ( PointerType pointerType = dynamic_cast< PointerType >( type ) ) {
233	if ( includesPolyType( pointerType->get_base(), env ) ) return true;
234	} else if ( StructInstType structType = dynamic_cast< StructInstType >( type ) ) {
235	if ( includesPolyParams( structType->get_parameters(), env ) ) return true;
236	} else if ( UnionInstType unionType = dynamic_cast< UnionInstType >( type ) ) {
237	if ( includesPolyParams( unionType->get_parameters(), env ) ) return true;
238	}
239	return false;
240	}
241
242	bool includesPolyType( Type type, const TyVarMap &tyVars, const TypeSubstitution env ) {
243	type = replaceTypeInst( type, env );
244
245	if ( TypeInstType typeInstType = dynamic_cast< TypeInstType >( type ) ) {
246	if ( tyVars.find( typeInstType->get_name() ) != tyVars.end() ) {
247	return true;
248	}
249	} else if ( PointerType pointerType = dynamic_cast< PointerType >( type ) ) {
250	if ( includesPolyType( pointerType->get_base(), tyVars, env ) ) return true;
251	} else if ( StructInstType structType = dynamic_cast< StructInstType >( type ) ) {
252	if ( includesPolyParams( structType->get_parameters(), tyVars, env ) ) return true;
253	} else if ( UnionInstType unionType = dynamic_cast< UnionInstType >( type ) ) {
254	if ( includesPolyParams( unionType->get_parameters(), tyVars, env ) ) return true;
255	}
256	return false;
257	}
258
259	FunctionType * getFunctionType( Type *ty ) {
260	PointerType *ptrType;
261	if ( ( ptrType = dynamic_cast< PointerType* >( ty ) ) ) {
262	return dynamic_cast< FunctionType* >( ptrType->get_base() ); // pointer if FunctionType, NULL otherwise
263	} else {
264	return dynamic_cast< FunctionType* >( ty ); // pointer if FunctionType, NULL otherwise
265	}
266	}
267
268	const ast::FunctionType * getFunctionType( const ast::Type * ty ) {
269	if ( auto pty = dynamic_cast< const ast::PointerType * >( ty ) ) {
270	return pty->base.as< ast::FunctionType >();
271	} else {
272	return dynamic_cast< const ast::FunctionType * >( ty );
273	}
274	}
275
276	VariableExpr * getBaseVar( Expression expr, int levels ) {
277	int dummy;
278	if ( ! levels ) { levels = &dummy; }
279	*levels = 0;
280
281	while ( true ) {
282	if ( VariableExpr varExpr = dynamic_cast< VariableExpr >( expr ) ) {
283	return varExpr;
284	} else if ( MemberExpr memberExpr = dynamic_cast< MemberExpr >( expr ) ) {
285	expr = memberExpr->get_aggregate();
286	} else if ( AddressExpr addressExpr = dynamic_cast< AddressExpr >( expr ) ) {
287	expr = addressExpr->get_arg();
288	} else if ( UntypedExpr untypedExpr = dynamic_cast< UntypedExpr >( expr ) ) {
289	// look for compiler-inserted dereference operator
290	NameExpr fn = dynamic_cast< NameExpr >( untypedExpr->get_function() );
291	if ( ! fn \|\| fn->get_name() != std::string("*?") ) return 0;
292	expr = *untypedExpr->begin_args();
293	} else if ( CommaExpr commaExpr = dynamic_cast< CommaExpr >( expr ) ) {
294	// copy constructors insert comma exprs, look at second argument which contains the variable
295	expr = commaExpr->get_arg2();
296	continue;
297	} else if ( ConditionalExpr * condExpr = dynamic_cast< ConditionalExpr * >( expr ) ) {
298	int lvl1;
299	int lvl2;
300	VariableExpr * var1 = getBaseVar( condExpr->get_arg2(), &lvl1 );
301	VariableExpr * var2 = getBaseVar( condExpr->get_arg3(), &lvl2 );
302	if ( lvl1 == lvl2 && var1 && var2 && var1->get_var() == var2->get_var() ) {
303	*levels = lvl1;
304	return var1;
305	}
306	break;
307	} else break;
308
309	++(*levels);
310	}
311
312	return 0;
313	}
314
315	namespace {
316	/// Checks if is a pointer to D
317	template<typename D, typename B>
318	bool is( const B* p ) { return type_index{typeid(D)} == type_index{typeid(*p)}; }
319
320	/// Converts to a pointer to D without checking for safety
321	template<typename D, typename B>
322	inline D* as( B* p ) { return reinterpret_cast<D*>(p); }
323
324	/// Flattens a declaration list
325	template<typename Output>
326	void flattenList( list< DeclarationWithType* > src, Output out ) {
327	for ( DeclarationWithType* decl : src ) {
328	ResolvExpr::flatten( decl->get_type(), out );
329	}
330	}
331
332	/// Flattens a list of types
333	template<typename Output>
334	void flattenList( list< Type* > src, Output out ) {
335	for ( Type* ty : src ) {
336	ResolvExpr::flatten( ty, out );
337	}
338	}
339
340	/// Checks if two lists of parameters are equal up to polymorphic substitution.
341	bool paramListsPolyCompatible( const list< Expression* >& aparams, const list< Expression* >& bparams ) {
342	if ( aparams.size() != bparams.size() ) return false;
343
344	for ( list< Expression* >::const_iterator at = aparams.begin(), bt = bparams.begin();
345	at != aparams.end(); ++at, ++bt ) {
346	TypeExpr aparam = dynamic_cast< TypeExpr >(*at);
347	assertf(aparam, "Aggregate parameters should be type expressions");
348	TypeExpr bparam = dynamic_cast< TypeExpr >(*bt);
349	assertf(bparam, "Aggregate parameters should be type expressions");
350
351	// xxx - might need to let VoidType be a wildcard here too; could have some voids
352	// stuffed in for dtype-statics.
353	// if ( is<VoidType>( aparam->get_type() ) \|\| is<VoidType>( bparam->get_type() ) ) continue;
354	if ( ! typesPolyCompatible( aparam->get_type(), bparam->get_type() ) ) return false;
355	}
356
357	return true;
358	}
359	}
360
361	bool typesPolyCompatible( Type a, Type b ) {
362	type_index aid{ typeid(*a) };
363	// polymorphic types always match
364	if ( aid == type_index{typeid(TypeInstType)} ) return true;
365
366	type_index bid{ typeid(*b) };
367	// polymorphic types always match
368	if ( bid == type_index{typeid(TypeInstType)} ) return true;
369
370	// can't match otherwise if different types
371	if ( aid != bid ) return false;
372
373	// recurse through type structure (conditions borrowed from Unify.cc)
374	if ( aid == type_index{typeid(BasicType)} ) {
375	return as<BasicType>(a)->get_kind() == as<BasicType>(b)->get_kind();
376	} else if ( aid == type_index{typeid(PointerType)} ) {
377	PointerType ap = as<PointerType>(a), bp = as<PointerType>(b);
378
379	// void pointers should match any other pointer type
380	return is<VoidType>( ap->get_base() ) \|\| is<VoidType>( bp->get_base() )
381	\|\| typesPolyCompatible( ap->get_base(), bp->get_base() );
382	} else if ( aid == type_index{typeid(ReferenceType)} ) {
383	ReferenceType ap = as<ReferenceType>(a), bp = as<ReferenceType>(b);
384	return is<VoidType>( ap->get_base() ) \|\| is<VoidType>( bp->get_base() )
385	\|\| typesPolyCompatible( ap->get_base(), bp->get_base() );
386	} else if ( aid == type_index{typeid(ArrayType)} ) {
387	ArrayType aa = as<ArrayType>(a), ba = as<ArrayType>(b);
388
389	if ( aa->get_isVarLen() ) {
390	if ( ! ba->get_isVarLen() ) return false;
391	} else {
392	if ( ba->get_isVarLen() ) return false;
393
394	ConstantExpr ad = dynamic_cast<ConstantExpr>( aa->get_dimension() );
395	ConstantExpr bd = dynamic_cast<ConstantExpr>( ba->get_dimension() );
396	if ( ad && bd
397	&& ad->get_constant()->get_value() != bd->get_constant()->get_value() )
398	return false;
399	}
400
401	return typesPolyCompatible( aa->get_base(), ba->get_base() );
402	} else if ( aid == type_index{typeid(FunctionType)} ) {
403	FunctionType af = as<FunctionType>(a), bf = as<FunctionType>(b);
404
405	vector<Type*> aparams, bparams;
406	flattenList( af->get_parameters(), back_inserter( aparams ) );
407	flattenList( bf->get_parameters(), back_inserter( bparams ) );
408	if ( aparams.size() != bparams.size() ) return false;
409
410	vector<Type*> areturns, breturns;
411	flattenList( af->get_returnVals(), back_inserter( areturns ) );
412	flattenList( bf->get_returnVals(), back_inserter( breturns ) );
413	if ( areturns.size() != breturns.size() ) return false;
414
415	for ( unsigned i = 0; i < aparams.size(); ++i ) {
416	if ( ! typesPolyCompatible( aparams[i], bparams[i] ) ) return false;
417	}
418	for ( unsigned i = 0; i < areturns.size(); ++i ) {
419	if ( ! typesPolyCompatible( areturns[i], breturns[i] ) ) return false;
420	}
421	return true;
422	} else if ( aid == type_index{typeid(StructInstType)} ) {
423	StructInstType aa = as<StructInstType>(a), ba = as<StructInstType>(b);
424
425	if ( aa->get_name() != ba->get_name() ) return false;
426	return paramListsPolyCompatible( aa->get_parameters(), ba->get_parameters() );
427	} else if ( aid == type_index{typeid(UnionInstType)} ) {
428	UnionInstType aa = as<UnionInstType>(a), ba = as<UnionInstType>(b);
429
430	if ( aa->get_name() != ba->get_name() ) return false;
431	return paramListsPolyCompatible( aa->get_parameters(), ba->get_parameters() );
432	} else if ( aid == type_index{typeid(EnumInstType)} ) {
433	return as<EnumInstType>(a)->get_name() == as<EnumInstType>(b)->get_name();
434	} else if ( aid == type_index{typeid(TraitInstType)} ) {
435	return as<TraitInstType>(a)->get_name() == as<TraitInstType>(b)->get_name();
436	} else if ( aid == type_index{typeid(TupleType)} ) {
437	TupleType at = as<TupleType>(a), bt = as<TupleType>(b);
438
439	vector<Type*> atypes, btypes;
440	flattenList( at->get_types(), back_inserter( atypes ) );
441	flattenList( bt->get_types(), back_inserter( btypes ) );
442	if ( atypes.size() != btypes.size() ) return false;
443
444	for ( unsigned i = 0; i < atypes.size(); ++i ) {
445	if ( ! typesPolyCompatible( atypes[i], btypes[i] ) ) return false;
446	}
447	return true;
448	} else return true; // VoidType, VarArgsType, ZeroType & OneType just need the same type
449	}
450
451	bool needsBoxing( Type * param, Type * arg, const TyVarMap &exprTyVars, const TypeSubstitution * env ) {
452	// is parameter is not polymorphic, don't need to box
453	if ( ! isPolyType( param, exprTyVars ) ) return false;
454	Type * newType = arg->clone();
455	if ( env ) env->apply( newType );
456	std::unique_ptr<Type> manager( newType );
457	// if the argument's type is polymorphic, we don't need to box again!
458	return ! isPolyType( newType );
459	}
460
461	bool needsBoxing( Type * param, Type * arg, ApplicationExpr * appExpr, const TypeSubstitution * env ) {
462	FunctionType * function = getFunctionType( appExpr->function->result );
463	assertf( function, "ApplicationExpr has non-function type: %s", toString( appExpr->function->result ).c_str() );
464	TyVarMap exprTyVars( TypeDecl::Data{} );
465	makeTyVarMap( function, exprTyVars );
466	return needsBoxing( param, arg, exprTyVars, env );
467	}
468
469	void addToTyVarMap( TypeDecl * tyVar, TyVarMap &tyVarMap ) {
470	tyVarMap.insert( tyVar->name, TypeDecl::Data{ tyVar } );
471	}
472
473	void makeTyVarMap( Type *type, TyVarMap &tyVarMap ) {
474	for ( Type::ForallList::const_iterator tyVar = type->get_forall().begin(); tyVar != type->get_forall().end(); ++tyVar ) {
475	assert( *tyVar );
476	addToTyVarMap( *tyVar, tyVarMap );
477	}
478	if ( PointerType pointer = dynamic_cast< PointerType >( type ) ) {
479	makeTyVarMap( pointer->get_base(), tyVarMap );
480	}
481	}
482
483	void printTyVarMap( std::ostream &os, const TyVarMap &tyVarMap ) {
484	for ( TyVarMap::const_iterator i = tyVarMap.begin(); i != tyVarMap.end(); ++i ) {
485	os << i->first << " (" << i->second << ") ";
486	} // for
487	os << std::endl;
488	}
489
490	} // namespace GenPoly
491
492	// Local Variables: //
493	// tab-width: 4 //
494	// mode: c++ //
495	// compile-command: "make install" //
496	// End: //

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

Download in other formats: