source: src/GenPoly/GenPoly.cpp@ 4b465445

Last change on this file since 4b465445 was b6f2e7ab, checked in by Andrew Beach <ajbeach@…>, 14 months ago

Removed SizeofExpr::expr and AlignofExpr::expr, expressions that would be stored there are wrapped in TypeofType and stored in the type field. Some special cases to hide the typeof in code generation were added. In addition, initializer length is calculated in more cases so that the full type of more arrays is known sooner. Other than that, most of the code changes were just stripping out the conditional code and checks no longer needed. Some tests had to be updated, because the typeof is not hidden in dumps and the resolver replaces known typeof expressions with the type. The extension case caused some concern but it appears that just hides warnings in the expression which no longer exists.
  • Property mode set to 100644
File size: 16.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.cpp -- General GenPoly utilities.
8//
9// Author : Richard C. Bilson
10// Created On : Mon May 18 07:44:20 2015
11// Last Modified By : Andrew Beach
12// Last Modified On : Mon Oct 24 15:19:00 2022
13// Update Count : 17
14//
15
16#include "GenPoly.hpp"
17
18#include <cassert> // for assertf, assert
19#include <iostream> // for operator<<, ostream, basic_...
20#include <iterator> // for back_insert_iterator, back_...
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/Expr.hpp"
27#include "AST/Type.hpp"
28#include "AST/TypeSubstitution.hpp"
29#include "Common/Eval.hpp" // for eval
30#include "GenPoly/ErasableScopedMap.hpp" // for ErasableScopedMap<>::const_...
31#include "ResolvExpr/Typeops.hpp" // for flatten
32
33using namespace std;
34
35namespace GenPoly {
36
37namespace {
38 /// Checks a parameter list for polymorphic parameters; will substitute according to env if present.
39 bool hasPolyParams( const std::vector<ast::ptr<ast::Expr>> & params, const ast::TypeSubstitution * env ) {
40 for ( auto & param : params ) {
41 auto paramType = param.as<ast::TypeExpr>();
42 assertf( paramType, "Aggregate parameters should be type expressions" );
43 if ( isPolyType( paramType->type, env ) ) return true;
44 }
45 return false;
46 }
47
48 /// Checks a parameter list for polymorphic parameters from typeVars; will substitute according to env if present.
49 bool hasPolyParams( const std::vector<ast::ptr<ast::Expr>> & params, const TypeVarMap & typeVars, const ast::TypeSubstitution * env ) {
50 for ( auto & param : params ) {
51 auto paramType = param.as<ast::TypeExpr>();
52 assertf( paramType, "Aggregate parameters should be type expressions" );
53 if ( isPolyType( paramType->type, typeVars, 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(
60 const std::vector<ast::ptr<ast::Expr>> & params,
61 const TypeVarMap & typeVars,
62 const ast::TypeSubstitution * subst ) {
63 for ( ast::ptr<ast::Expr> const & paramExpr : params ) {
64 auto param = paramExpr.as<ast::TypeExpr>();
65 assertf( param, "Aggregate parameters should be type expressions." );
66 if ( isDynType( param->type.get(), typeVars, subst ) ) {
67 return true;
68 }
69 }
70 return false;
71 }
72} // namespace
73
74const ast::Type * replaceTypeInst( const ast::Type * type, const ast::TypeSubstitution * env ) {
75 if ( !env ) return type;
76 if ( auto typeInst = dynamic_cast<const ast::TypeInstType*>( type ) ) {
77 if ( auto newType = env->lookup( typeInst ) ) return newType;
78 }
79 return type;
80}
81
82const ast::Type * isPolyType( const ast::Type * type, const ast::TypeSubstitution * subst ) {
83 type = replaceTypeInst( type, subst );
84
85 if ( dynamic_cast< const ast::TypeInstType * >( type ) ) {
86 // This case is where the two variants of isPolyType differ.
87 return type;
88 } else if ( auto arrayType = dynamic_cast< const ast::ArrayType * >( type ) ) {
89 return isPolyType( arrayType->base, subst );
90 } else if ( auto structType = dynamic_cast< const ast::StructInstType* >( type ) ) {
91 if ( hasPolyParams( structType->params, subst ) ) return type;
92 } else if ( auto unionType = dynamic_cast< const ast::UnionInstType* >( type ) ) {
93 if ( hasPolyParams( unionType->params, subst ) ) return type;
94 }
95 return nullptr;
96}
97
98const ast::Type * isPolyType( const ast::Type * type,
99 const TypeVarMap & typeVars, const ast::TypeSubstitution * subst ) {
100 type = replaceTypeInst( type, subst );
101
102 if ( auto inst = dynamic_cast< const ast::TypeInstType * >( type ) ) {
103 if ( typeVars.contains( *inst ) ) return type;
104 } else if ( auto array = dynamic_cast< const ast::ArrayType * >( type ) ) {
105 return isPolyType( array->base, typeVars, subst );
106 } else if ( auto sue = dynamic_cast< const ast::StructInstType * >( type ) ) {
107 if ( hasPolyParams( sue->params, typeVars, subst ) ) return type;
108 } else if ( auto sue = dynamic_cast< const ast::UnionInstType * >( type ) ) {
109 if ( hasPolyParams( sue->params, typeVars, subst ) ) return type;
110 }
111 return nullptr;
112}
113
114const ast::BaseInstType * isDynType(
115 const ast::Type * type, const TypeVarMap & typeVars,
116 const ast::TypeSubstitution * subst ) {
117 type = replaceTypeInst( type, subst );
118
119 if ( auto inst = dynamic_cast<ast::TypeInstType const *>( type ) ) {
120 auto var = typeVars.find( *inst );
121 if ( var != typeVars.end() && var->second.isComplete ) {
122 return inst;
123 }
124 } else if ( auto inst = dynamic_cast<ast::StructInstType const *>( type ) ) {
125 if ( hasDynParams( inst->params, typeVars, subst ) ) return inst;
126 } else if ( auto inst = dynamic_cast<ast::UnionInstType const *>( type ) ) {
127 if ( hasDynParams( inst->params, typeVars, subst ) ) return inst;
128 }
129 return nullptr;
130}
131
132const ast::BaseInstType *isDynRet(
133 const ast::FunctionType * type, const TypeVarMap & typeVars ) {
134 if ( type->returns.empty() ) return nullptr;
135
136 return isDynType( type->returns.front(), typeVars );
137}
138
139const ast::BaseInstType *isDynRet( const ast::FunctionType * func ) {
140 if ( func->returns.empty() ) return nullptr;
141
142 TypeVarMap forallTypes;
143 makeTypeVarMap( func, forallTypes );
144 return isDynType( func->returns.front(), forallTypes );
145}
146
147bool needsAdapter(
148 ast::FunctionType const * adaptee, const TypeVarMap & typeVars ) {
149 if ( isDynRet( adaptee, typeVars ) ) return true;
150
151 for ( auto param : adaptee->params ) {
152 if ( isDynType( param, typeVars ) ) {
153 return true;
154 }
155 }
156 return false;
157}
158
159const ast::Type * isPolyPtr(
160 const ast::Type * type, const TypeVarMap & typeVars,
161 const ast::TypeSubstitution * typeSubs ) {
162 type = replaceTypeInst( type, typeSubs );
163
164 if ( auto * ptr = dynamic_cast<ast::PointerType const *>( type ) ) {
165 return isPolyType( ptr->base, typeVars, typeSubs );
166 }
167 return nullptr;
168}
169
170ast::Type const * hasPolyBase(
171 ast::Type const * type, const TypeVarMap & typeVars,
172 int * levels, const ast::TypeSubstitution * subst ) {
173 int level_count = 0;
174
175 while ( true ) {
176 type = replaceTypeInst( type, subst );
177
178 if ( auto ptr = dynamic_cast<ast::PointerType const *>( type ) ) {
179 type = ptr->base;
180 ++level_count;
181 } else {
182 break;
183 }
184 }
185
186 if ( nullptr != levels ) { *levels = level_count; }
187 return isPolyType( type, typeVars, subst );
188}
189
190const ast::FunctionType * getFunctionType( const ast::Type * ty ) {
191 if ( auto pty = dynamic_cast< const ast::PointerType * >( ty ) ) {
192 return pty->base.as< ast::FunctionType >();
193 } else {
194 return dynamic_cast< const ast::FunctionType * >( ty );
195 }
196}
197
198namespace {
199 /// Checks if is a pointer to D
200 template<typename D, typename B>
201 bool is( const B* p ) { return type_index{typeid(D)} == type_index{typeid(*p)}; }
202
203 /// Converts to a pointer to D without checking for safety
204 template<typename D, typename B>
205 inline D* as( B* p ) { return reinterpret_cast<D*>(p); }
206
207 template<typename D, typename B>
208 inline D const * as( B const * p ) {
209 return reinterpret_cast<D const *>( p );
210 }
211
212 /// Flattens a list of types.
213 void flattenList( vector<ast::ptr<ast::Type>> const & src,
214 vector<ast::ptr<ast::Type>> & out ) {
215 for ( auto const & type : src ) {
216 ResolvExpr::flatten( type, out );
217 }
218 }
219
220 bool paramListsPolyCompatible(
221 std::vector<ast::ptr<ast::Expr>> const & lparams,
222 std::vector<ast::ptr<ast::Expr>> const & rparams ) {
223 if ( lparams.size() != rparams.size() ) {
224 return false;
225 }
226
227 for ( auto lparam = lparams.begin(), rparam = rparams.begin() ;
228 lparam != lparams.end() ; ++lparam, ++rparam ) {
229 ast::TypeExpr const * lexpr = lparam->as<ast::TypeExpr>();
230 assertf( lexpr, "Aggregate parameters should be type expressions" );
231 ast::TypeExpr const * rexpr = rparam->as<ast::TypeExpr>();
232 assertf( rexpr, "Aggregate parameters should be type expressions" );
233
234 // xxx - might need to let VoidType be a wildcard here too; could have some voids
235 // stuffed in for dtype-statics.
236 // if ( is<VoidType>( lexpr->type() ) || is<VoidType>( bparam->get_type() ) ) continue;
237 if ( !typesPolyCompatible( lexpr->type, rexpr->type ) ) {
238 return false;
239 }
240 }
241
242 return true;
243 }
244} // namespace
245
246// This function, and its helpers following, have logic duplicated from
247// unification. The difference in context is that unification applies where
248// the types "must" match, while this variation applies to arbitrary type
249// pairs, when an optimization could apply if they happen to match. This
250// variation does not bind type variables. The helper functions support
251// the case for matching ArrayType.
252bool typesPolyCompatible( ast::Type const * lhs, ast::Type const * rhs );
253
254static bool exprsPolyCompatibleByStaticValue(
255 const ast::Expr * e1, const ast::Expr * e2 ) {
256 Evaluation r1 = eval(e1);
257 Evaluation r2 = eval(e2);
258
259 if ( !r1.hasKnownValue ) return false;
260 if ( !r2.hasKnownValue ) return false;
261
262 if ( r1.knownValue != r2.knownValue ) return false;
263
264 return true;
265}
266
267static bool exprsPolyCompatible( ast::Expr const * lhs,
268 ast::Expr const * rhs ) {
269 type_index const lid = typeid(*lhs);
270 type_index const rid = typeid(*rhs);
271 if ( lid != rid ) return false;
272
273 if ( exprsPolyCompatibleByStaticValue( lhs, rhs ) ) return true;
274
275 if ( type_index(typeid(ast::CastExpr)) == lid ) {
276 ast::CastExpr const * l = as<ast::CastExpr>(lhs);
277 ast::CastExpr const * r = as<ast::CastExpr>(rhs);
278
279 // inspect casts' target types
280 if ( !typesPolyCompatible(
281 l->result, r->result ) ) return false;
282
283 // inspect casts' inner expressions
284 return exprsPolyCompatible( l->arg, r->arg );
285
286 } else if ( type_index(typeid(ast::VariableExpr)) == lid ) {
287 ast::VariableExpr const * l = as<ast::VariableExpr>(lhs);
288 ast::VariableExpr const * r = as<ast::VariableExpr>(rhs);
289
290 assert(l->var);
291 assert(r->var);
292
293 // conservative: variable exprs match if their declarations are
294 // represented by the same C++ AST object
295 return (l->var == r->var);
296
297 } else if ( type_index(typeid(ast::SizeofExpr)) == lid ) {
298 ast::SizeofExpr const * l = as<ast::SizeofExpr>(lhs);
299 ast::SizeofExpr const * r = as<ast::SizeofExpr>(rhs);
300
301 assert( l->type );
302 assert( r->type );
303
304 // mutual recursion with type poly compatibility
305 return typesPolyCompatible( l->type, r->type );
306
307 } else {
308 // All other forms compare on static value only, done earlier
309 return false;
310 }
311}
312
313bool typesPolyCompatible( ast::Type const * lhs, ast::Type const * rhs ) {
314 type_index const lid = typeid(*lhs);
315
316 // Polymorphic types always match:
317 if ( type_index(typeid(ast::TypeInstType)) == lid ) return true;
318
319 type_index const rid = typeid(*rhs);
320 if ( type_index(typeid(ast::TypeInstType)) == rid ) return true;
321
322 // All other types only match if they are the same type:
323 if ( lid != rid ) return false;
324
325 // So remaining types can be examined case by case.
326 // Recurse through type structure (conditions duplicated from Unify.cpp).
327
328 if ( type_index(typeid(ast::BasicType)) == lid ) {
329 return as<ast::BasicType>(lhs)->kind == as<ast::BasicType>(rhs)->kind;
330 } else if ( type_index(typeid(ast::PointerType)) == lid ) {
331 ast::PointerType const * l = as<ast::PointerType>(lhs);
332 ast::PointerType const * r = as<ast::PointerType>(rhs);
333
334 // void pointers should match any other pointer type.
335 return is<ast::VoidType>( l->base.get() )
336 || is<ast::VoidType>( r->base.get() )
337 || typesPolyCompatible( l->base.get(), r->base.get() );
338 } else if ( type_index(typeid(ast::ReferenceType)) == lid ) {
339 ast::ReferenceType const * l = as<ast::ReferenceType>(lhs);
340 ast::ReferenceType const * r = as<ast::ReferenceType>(rhs);
341
342 // void references should match any other reference type.
343 return is<ast::VoidType>( l->base.get() )
344 || is<ast::VoidType>( r->base.get() )
345 || typesPolyCompatible( l->base.get(), r->base.get() );
346 } else if ( type_index(typeid(ast::ArrayType)) == lid ) {
347 ast::ArrayType const * l = as<ast::ArrayType>(lhs);
348 ast::ArrayType const * r = as<ast::ArrayType>(rhs);
349
350 if ( l->isVarLen != r->isVarLen ) return false;
351 if ( (l->dimension != nullptr) != (r->dimension != nullptr) )
352 return false;
353
354 if ( l->dimension ) {
355 assert( r->dimension );
356 // mutual recursion with expression poly compatibility
357 if ( !exprsPolyCompatible(l->dimension, r->dimension) )
358 return false;
359 }
360
361 return typesPolyCompatible( l->base.get(), r->base.get() );
362 } else if ( type_index(typeid(ast::FunctionType)) == lid ) {
363 ast::FunctionType const * l = as<ast::FunctionType>(lhs);
364 ast::FunctionType const * r = as<ast::FunctionType>(rhs);
365
366 std::vector<ast::ptr<ast::Type>> lparams, rparams;
367 flattenList( l->params, lparams );
368 flattenList( r->params, rparams );
369 if ( lparams.size() != rparams.size() ) return false;
370 for ( unsigned i = 0; i < lparams.size(); ++i ) {
371 if ( !typesPolyCompatible( lparams[i], rparams[i] ) ) return false;
372 }
373
374 std::vector<ast::ptr<ast::Type>> lrets, rrets;
375 flattenList( l->returns, lrets );
376 flattenList( r->returns, rrets );
377 if ( lrets.size() != rrets.size() ) return false;
378 for ( unsigned i = 0; i < lrets.size(); ++i ) {
379 if ( !typesPolyCompatible( lrets[i], rrets[i] ) ) return false;
380 }
381 return true;
382 } else if ( type_index(typeid(ast::StructInstType)) == lid ) {
383 ast::StructInstType const * l = as<ast::StructInstType>(lhs);
384 ast::StructInstType const * r = as<ast::StructInstType>(rhs);
385
386 if ( l->name != r->name ) return false;
387 return paramListsPolyCompatible( l->params, r->params );
388 } else if ( type_index(typeid(ast::UnionInstType)) == lid ) {
389 ast::UnionInstType const * l = as<ast::UnionInstType>(lhs);
390 ast::UnionInstType const * r = as<ast::UnionInstType>(rhs);
391
392 if ( l->name != r->name ) return false;
393 return paramListsPolyCompatible( l->params, r->params );
394 } else if ( type_index(typeid(ast::EnumInstType)) == lid ) {
395 ast::EnumInstType const * l = as<ast::EnumInstType>(lhs);
396 ast::EnumInstType const * r = as<ast::EnumInstType>(rhs);
397
398 return l->name == r->name;
399 } else if ( type_index(typeid(ast::TraitInstType)) == lid ) {
400 ast::TraitInstType const * l = as<ast::TraitInstType>(lhs);
401 ast::TraitInstType const * r = as<ast::TraitInstType>(rhs);
402
403 return l->name == r->name;
404 } else if ( type_index(typeid(ast::TupleType)) == lid ) {
405 ast::TupleType const * l = as<ast::TupleType>(lhs);
406 ast::TupleType const * r = as<ast::TupleType>(rhs);
407
408 std::vector<ast::ptr<ast::Type>> ltypes, rtypes;
409 flattenList( l->types, ( ltypes ) );
410 flattenList( r->types, ( rtypes ) );
411 if ( ltypes.size() != rtypes.size() ) return false;
412
413 for ( unsigned i = 0 ; i < ltypes.size() ; ++i ) {
414 if ( !typesPolyCompatible( ltypes[i], rtypes[i] ) ) return false;
415 }
416 return true;
417 // The remaining types (VoidType, VarArgsType, ZeroType & OneType)
418 // have no variation so will always be equal.
419 } else {
420 return true;
421 }
422}
423
424bool needsBoxing( const ast::Type * param, const ast::Type * arg,
425 const TypeVarMap & typeVars, const ast::TypeSubstitution * subst ) {
426 // Don't need to box if the parameter is not polymorphic.
427 if ( !isPolyType( param, typeVars ) ) return false;
428
429 ast::ptr<ast::Type> newType = arg;
430 if ( subst ) {
431 int count = subst->apply( newType );
432 (void)count;
433 }
434 // Only need to box if the argument is not also polymorphic.
435 return !isPolyType( newType );
436}
437
438bool needsBoxing(
439 const ast::Type * param, const ast::Type * arg,
440 const ast::ApplicationExpr * expr,
441 const ast::TypeSubstitution * subst ) {
442 const ast::FunctionType * function = getFunctionType( expr->func->result );
443 assertf( function, "ApplicationExpr has non-function type: %s", toCString( expr->func->result ) );
444 TypeVarMap exprTyVars;
445 makeTypeVarMap( function, exprTyVars );
446 return needsBoxing( param, arg, exprTyVars, subst );
447}
448
449void addToTypeVarMap( const ast::TypeDecl * decl, TypeVarMap & typeVars ) {
450 typeVars.insert( ast::TypeEnvKey( decl, 0, 0 ), ast::TypeData( decl ) );
451}
452
453void addToTypeVarMap( const ast::TypeInstType * type, TypeVarMap & typeVars ) {
454 typeVars.insert( ast::TypeEnvKey( *type ), ast::TypeData( type->base ) );
455}
456
457void makeTypeVarMap( const ast::Type * type, TypeVarMap & typeVars ) {
458 if ( auto func = dynamic_cast<ast::FunctionType const *>( type ) ) {
459 for ( auto & typeVar : func->forall ) {
460 assert( typeVar );
461 addToTypeVarMap( typeVar, typeVars );
462 }
463 }
464 if ( auto pointer = dynamic_cast<ast::PointerType const *>( type ) ) {
465 makeTypeVarMap( pointer->base, typeVars );
466 }
467}
468
469void makeTypeVarMap( const ast::FunctionDecl * decl, TypeVarMap & typeVars ) {
470 for ( auto & typeDecl : decl->type_params ) {
471 addToTypeVarMap( typeDecl, typeVars );
472 }
473}
474
475} // namespace GenPoly
476
477// Local Variables: //
478// tab-width: 4 //
479// mode: c++ //
480// compile-command: "make install" //
481// End: //
Note: See TracBrowser for help on using the repository browser.