source: src/GenPoly/GenPoly.cc@ 4e13e2a

ADT arm-eh ast-experimental enum forall-pointer-decay jacob/cs343-translation new-ast new-ast-unique-expr pthread-emulation qualifiedEnum
Last change on this file since 4e13e2a was 8d70648, checked in by Aaron Moss <a3moss@…>, 6 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
34using namespace std;
35
36namespace 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.