source: src/GenPoly/InstantiateGeneric.cc @ 63db3d7

aaron-thesisarm-ehcleanup-dtorsctordeferred_resndemanglergc_noraiijacob/cs343-translationjenkins-sandboxmemorynew-astnew-ast-unique-exprnew-envno_listpersistent-indexerresolv-newstringwith_gc
Last change on this file since 63db3d7 was 63db3d7, checked in by Aaron Moss <a3moss@…>, 6 years ago

Temporarily roll back dtype-to-void optimization until it works properly

  • Property mode set to 100644
File size: 14.4 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// InstantiateGeneric.cc --
8//
9// Author           : Aaron B. Moss
10// Created On       : Wed Nov 11 14:55:01 2015
11// Last Modified By : Aaron B. Moss
12// Last Modified On : Wed Nov 11 14:55:01 2015
13// Update Count     : 1
14//
15
16#include <list>
17#include <map>
18#include <string>
19#include <utility>
20#include <vector>
21
22#include "InstantiateGeneric.h"
23#include "DeclMutator.h"
24
25#include "ResolvExpr/typeops.h"
26#include "SymTab/Indexer.h"
27#include "SynTree/Declaration.h"
28#include "SynTree/Mutator.h"
29#include "SynTree/Statement.h"
30#include "SynTree/Type.h"
31#include "SynTree/TypeSubstitution.h"
32
33#include "UniqueName.h"
34#include "utility.h"
35
36namespace GenPoly {
37
38        /// Key for a unique concrete type; generic base type paired with type parameter list
39        struct ConcreteType {
40                ConcreteType() : base(NULL), params() {}
41
42                ConcreteType(AggregateDecl *_base, const std::list< Type* >& _params) : base(_base), params() { cloneAll(_params, params); }
43
44                ConcreteType(const ConcreteType& that) : base(that.base), params() { cloneAll(that.params, params); }
45
46                /// Extracts types from a list of TypeExpr*
47                ConcreteType(AggregateDecl *_base, const std::list< TypeExpr* >& _params) : base(_base), params() {
48                        for ( std::list< TypeExpr* >::const_iterator param = _params.begin(); param != _params.end(); ++param ) {
49                                params.push_back( (*param)->get_type()->clone() );
50                        }
51                }
52
53                ConcreteType& operator= (const ConcreteType& that) {
54                        deleteAll( params );
55                        params.clear();
56
57                        base = that.base;
58                        cloneAll( that.params, params );
59
60                        return *this;
61                }
62
63                ~ConcreteType() { deleteAll( params ); }
64
65                bool operator== (const ConcreteType& that) const {
66                        if ( base != that.base ) return false;
67
68                        SymTab::Indexer dummy;
69                        if ( params.size() != that.params.size() ) return false;
70                        for ( std::list< Type* >::const_iterator it = params.begin(), jt = that.params.begin(); it != params.end(); ++it, ++jt ) {
71                                if ( ! ResolvExpr::typesCompatible( *it, *jt, dummy ) ) return false;
72                        }
73                        return true;
74                }
75
76                AggregateDecl *base;        ///< Base generic type
77                std::list< Type* > params;  ///< Instantiation parameters
78        };
79       
80        /// Maps a concrete type to the instantiated struct type, accounting for scope
81        class InstantiationMap {
82                /// Instantiation of a generic type, with key information to find it
83                struct Instantiation {
84                        ConcreteType key;     ///< Instantiation parameters for this type
85                        AggregateDecl *decl;  ///< Declaration of the instantiated generic type
86
87                        Instantiation() : key(), decl(0) {}
88                        Instantiation(const ConcreteType &_key, AggregateDecl *_decl) : key(_key), decl(_decl) {}
89                };
90                /// Map of generic types to instantiations of them
91                typedef std::map< AggregateDecl*, std::vector< Instantiation > > Scope;
92
93                std::vector< Scope > scopes;  ///< list of scopes, from outermost to innermost
94
95        public:
96                /// Starts a new scope
97                void beginScope() {
98                        Scope scope;
99                        scopes.push_back(scope);
100                }
101
102                /// Ends a scope
103                void endScope() {
104                        scopes.pop_back();
105                }
106
107                /// Default constructor initializes with one scope
108                InstantiationMap() { beginScope(); }
109
110        private:
111                /// Gets the declaration for the concrete instantiation of this type, assuming it has already been instantiated in the current scope.
112                /// Returns NULL on none such.
113                AggregateDecl* lookup( AggregateDecl *generic, const std::list< TypeExpr* >& params ) {
114                        ConcreteType key(generic, params);
115                        // scan scopes from innermost out
116                        for ( std::vector< Scope >::const_reverse_iterator scope = scopes.rbegin(); scope != scopes.rend(); ++scope ) {
117                                // skip scope if no instantiations of this generic type
118                                Scope::const_iterator insts = scope->find( generic );
119                                if ( insts == scope->end() ) continue;
120                                // look through instantiations for matches to concrete type
121                                for ( std::vector< Instantiation >::const_iterator inst = insts->second.begin(); inst != insts->second.end(); ++inst ) {
122                                        if ( inst->key == key ) return inst->decl;
123                                }
124                        }
125                        // no matching instantiation found
126                        return NULL;
127                }
128        public:
129                StructDecl* lookup( StructInstType *inst, const std::list< TypeExpr* > &typeSubs ) { return (StructDecl*)lookup( inst->get_baseStruct(), typeSubs ); }
130                UnionDecl* lookup( UnionInstType *inst, const std::list< TypeExpr* > &typeSubs ) { return (UnionDecl*)lookup( inst->get_baseUnion(), typeSubs ); }
131
132        private:
133                /// Adds a declaration for a concrete type to the current scope
134                void insert( AggregateDecl *generic, const std::list< TypeExpr* > &params, AggregateDecl *decl ) {
135                        ConcreteType key(generic, params);
136                        scopes.back()[generic].push_back( Instantiation( key, decl ) );
137                }
138        public:
139                void insert( StructInstType *inst, const std::list< TypeExpr* > &typeSubs, StructDecl *decl ) { insert( inst->get_baseStruct(), typeSubs, decl ); }
140                void insert( UnionInstType *inst, const std::list< TypeExpr* > &typeSubs, UnionDecl *decl ) { insert( inst->get_baseUnion(), typeSubs, decl ); }
141        };
142
143        /// Mutator pass that replaces concrete instantiations of generic types with actual struct declarations, scoped appropriately
144        class Instantiate : public DeclMutator {
145                /// Map of (generic type, parameter list) pairs to concrete type instantiations
146                InstantiationMap instantiations;
147                /// Namer for concrete types
148                UniqueName typeNamer;
149
150        public:
151                Instantiate() : DeclMutator(), instantiations(), typeNamer("_conc_") {}
152
153                virtual Type* mutate( StructInstType *inst );
154                virtual Type* mutate( UnionInstType *inst );
155
156//              virtual Expression* mutate( MemberExpr *memberExpr );
157               
158                virtual void doBeginScope();
159                virtual void doEndScope();
160        };
161       
162        void instantiateGeneric( std::list< Declaration* >& translationUnit ) {
163                Instantiate instantiator;
164                instantiator.mutateDeclarationList( translationUnit );
165        }
166
167        /// Makes substitutions of params into baseParams; returns true if all parameters substituted for a concrete type
168        bool makeSubstitutions( const std::list< TypeDecl* >& baseParams, const std::list< Expression* >& params, std::list< TypeExpr* >& out ) {
169                bool allConcrete = true;  // will finish the substitution list even if they're not all concrete
170
171                // substitute concrete types for given parameters, and incomplete types for placeholders
172                std::list< TypeDecl* >::const_iterator baseParam = baseParams.begin();
173                std::list< Expression* >::const_iterator param = params.begin();
174                for ( ; baseParam != baseParams.end() && param != params.end(); ++baseParam, ++param ) {
175//                      switch ( (*baseParam)->get_kind() ) {
176//                      case TypeDecl::Any: {   // any type is a valid substitution here; complete types can be used to instantiate generics
177                                TypeExpr *paramType = dynamic_cast< TypeExpr* >( *param );
178                                assert(paramType && "Aggregate parameters should be type expressions");
179                                out.push_back( paramType->clone() );
180                                // check that the substituted type isn't a type variable itself
181                                if ( dynamic_cast< TypeInstType* >( paramType->get_type() ) ) {
182                                        allConcrete = false;
183                                }
184//                              break;
185//                      }
186//                      case TypeDecl::Dtype:  // dtype can be consistently replaced with void [only pointers, which become void*]
187//                              out.push_back( new TypeExpr( new VoidType( Type::Qualifiers() ) ) );
188//                              break;
189//                      case TypeDecl::Ftype:  // pointer-to-ftype can be consistently replaced with void (*)(void) [similar to dtype]
190//                              out.push_back( new TypeExpr( new FunctionType( Type::Qualifiers(), false ) ) );
191//                              break;
192//                      }
193                }
194
195                // if any parameters left over, not done
196                if ( baseParam != baseParams.end() ) return false;
197//              // if not enough parameters given, substitute remaining incomplete types for placeholders
198//              for ( ; baseParam != baseParams.end(); ++baseParam ) {
199//                      switch ( (*baseParam)->get_kind() ) {
200//                      case TypeDecl::Any:    // no more substitutions here, fail early
201//                              return false;
202//                      case TypeDecl::Dtype:  // dtype can be consistently replaced with void [only pointers, which become void*]
203//                              out.push_back( new TypeExpr( new VoidType( Type::Qualifiers() ) ) );
204//                              break;
205//                      case TypeDecl::Ftype:  // pointer-to-ftype can be consistently replaced with void (*)(void) [similar to dtype]
206//                              out.push_back( new TypeExpr( new FunctionType( Type::Qualifiers(), false ) ) );
207//                              break;
208//                      }
209//              }
210
211                return allConcrete;
212        }
213
214        /// Substitutes types of members of in according to baseParams => typeSubs, appending the result to out
215        void substituteMembers( const std::list< Declaration* >& in, const std::list< TypeDecl* >& baseParams, const std::list< TypeExpr* >& typeSubs, 
216                                                    std::list< Declaration* >& out ) {
217                // substitute types into new members
218                TypeSubstitution subs( baseParams.begin(), baseParams.end(), typeSubs.begin() );
219                for ( std::list< Declaration* >::const_iterator member = in.begin(); member != in.end(); ++member ) {
220                        Declaration *newMember = (*member)->clone();
221                        subs.apply(newMember);
222                        out.push_back( newMember );
223                }
224        }
225
226        Type* Instantiate::mutate( StructInstType *inst ) {
227                // mutate subtypes
228                Type *mutated = Mutator::mutate( inst );
229                inst = dynamic_cast< StructInstType* >( mutated );
230                if ( ! inst ) return mutated;
231
232                // exit early if no need for further mutation
233                if ( inst->get_parameters().empty() ) return inst;
234                assert( inst->get_baseParameters() && "Base struct has parameters" );
235
236                // check if type can be concretely instantiated; put substitutions into typeSubs
237                std::list< TypeExpr* > typeSubs;
238                if ( ! makeSubstitutions( *inst->get_baseParameters(), inst->get_parameters(), typeSubs ) ) {
239                        deleteAll( typeSubs );
240                        return inst;
241                }
242               
243                // make concrete instantiation of generic type
244                StructDecl *concDecl = instantiations.lookup( inst, typeSubs );
245                if ( ! concDecl ) {
246                        // set concDecl to new type, insert type declaration into statements to add
247                        concDecl = new StructDecl( typeNamer.newName( inst->get_name() ) );
248                        substituteMembers( inst->get_baseStruct()->get_members(), *inst->get_baseParameters(), typeSubs,        concDecl->get_members() );
249                        DeclMutator::addDeclaration( concDecl );
250                        instantiations.insert( inst, typeSubs, concDecl );
251                }
252                StructInstType *newInst = new StructInstType( inst->get_qualifiers(), concDecl->get_name() );
253                newInst->set_baseStruct( concDecl );
254
255                deleteAll( typeSubs );
256                delete inst;
257                return newInst;
258        }
259       
260        Type* Instantiate::mutate( UnionInstType *inst ) {
261                // mutate subtypes
262                Type *mutated = Mutator::mutate( inst );
263                inst = dynamic_cast< UnionInstType* >( mutated );
264                if ( ! inst ) return mutated;
265
266                // exit early if no need for further mutation
267                if ( inst->get_parameters().empty() ) return inst;
268                assert( inst->get_baseParameters() && "Base union has parameters" );
269
270                // check if type can be concretely instantiated; put substitutions into typeSubs
271                std::list< TypeExpr* > typeSubs;
272                if ( ! makeSubstitutions( *inst->get_baseParameters(), inst->get_parameters(), typeSubs ) ) {
273                        deleteAll( typeSubs );
274                        return inst;
275                }
276               
277                // make concrete instantiation of generic type
278                UnionDecl *concDecl = instantiations.lookup( inst, typeSubs );
279                if ( ! concDecl ) {
280                        // set concDecl to new type, insert type declaration into statements to add
281                        concDecl = new UnionDecl( typeNamer.newName( inst->get_name() ) );
282                        substituteMembers( inst->get_baseUnion()->get_members(), *inst->get_baseParameters(), typeSubs, concDecl->get_members() );
283                        DeclMutator::addDeclaration( concDecl );
284                        instantiations.insert( inst, typeSubs, concDecl );
285                }
286                UnionInstType *newInst = new UnionInstType( inst->get_qualifiers(), concDecl->get_name() );
287                newInst->set_baseUnion( concDecl );
288
289                deleteAll( typeSubs );
290                delete inst;
291                return newInst;
292        }
293
294//      /// Gets the base struct or union declaration for a member expression; NULL if not applicable
295//      AggregateDecl* getMemberBaseDecl( MemberExpr *memberExpr ) {
296//              // get variable for member aggregate
297//              VariableExpr *varExpr = dynamic_cast< VariableExpr* >( memberExpr->get_aggregate() );
298//              if ( ! varExpr ) return NULL;
299//
300//              // get object for variable
301//              ObjectDecl *objectDecl = dynamic_cast< ObjectDecl* >( varExpr->get_var() );
302//              if ( ! objectDecl ) return NULL;
303//
304//              // get base declaration from object type
305//              Type *objectType = objectDecl->get_type();
306//              StructInstType *structType = dynamic_cast< StructInstType* >( objectType );
307//              if ( structType ) return structType->get_baseStruct();
308//              UnionInstType *unionType = dynamic_cast< UnionInstType* >( objectType );
309//              if ( unionType ) return unionType->get_baseUnion();
310//
311//              return NULL;
312//      }
313//
314//      /// Finds the declaration with the given name, returning decls.end() if none such
315//      std::list< Declaration* >::const_iterator findDeclNamed( const std::list< Declaration* > &decls, const std::string &name ) {
316//              for( std::list< Declaration* >::const_iterator decl = decls.begin(); decl != decls.end(); ++decl ) {
317//                      if ( (*decl)->get_name() == name ) return decl;
318//              }
319//              return decls.end();
320//      }
321//     
322//      Expression* Instantiate::mutate( MemberExpr *memberExpr ) {
323//              // mutate, exiting early if no longer MemberExpr
324//              Expression *expr = Mutator::mutate( memberExpr );
325//              memberExpr = dynamic_cast< MemberExpr* >( expr );
326//              if ( ! memberExpr ) return expr;
327//
328//              // get declaration of member and base declaration of member, exiting early if not found
329//              AggregateDecl *memberBase = getMemberBaseDecl( memberExpr );
330//              if ( ! memberBase ) return memberExpr;
331//              DeclarationWithType *memberDecl = memberExpr->get_member();
332//              std::list< Declaration* >::const_iterator baseIt = findDeclNamed( memberBase->get_members(), memberDecl->get_name() );
333//              if ( baseIt == memberBase->get_members().end() ) return memberExpr;
334//              DeclarationWithType *baseDecl = dynamic_cast< DeclarationWithType* >( *baseIt );
335//              if ( ! baseDecl ) return memberExpr;
336//
337//              // check if stated type of the member is not the type of the member's declaration; if so, need a cast
338//              // this *SHOULD* be safe, I don't think anything but the void-replacements I put in for dtypes would make it past the typechecker
339//              SymTab::Indexer dummy;
340//              if ( ResolvExpr::typesCompatible( memberDecl->get_type(), baseDecl->get_type(), dummy ) ) return memberExpr;
341//              else return new CastExpr( memberExpr, memberDecl->get_type() );
342//      }
343       
344        void Instantiate::doBeginScope() {
345                DeclMutator::doBeginScope();
346                instantiations.beginScope();
347        }
348
349        void Instantiate::doEndScope() {
350                DeclMutator::doEndScope();
351                instantiations.endScope();
352        }
353       
354}  // namespace GenPoly
355
356// Local Variables: //
357// tab-width: 4 //
358// mode: c++ //
359// compile-command: "make install" //
360// End: //
Note: See TracBrowser for help on using the repository browser.