source: src/GenPoly/GenPoly.cpp

Last change on this file was b6f2e7ab, checked in by Andrew Beach <ajbeach@…>, 3 weeks 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.