source: src/GenPoly/InstantiateGeneric.cc @ ea5daeb

aaron-thesisarm-ehcleanup-dtorsctordeferred_resndemanglerenumforall-pointer-decayjacob/cs343-translationjenkins-sandboxmemorynew-astnew-ast-unique-exprnew-envno_listpersistent-indexerpthread-emulationqualifiedEnumresolv-newwith_gc
Last change on this file since ea5daeb was ea5daeb, checked in by Aaron Moss <a3moss@…>, 6 years ago

Move generic instantiation earlier

  • Property mode set to 100644
File size: 11.6 KB
Line 
1//
2// Cforall Version 1.0.0 Copyright (C) 2016 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       : Thu Aug 04 18:33:00 2016
11// Last Modified By : Aaron B. Moss
12// Last Modified On : Thu Aug 04 18:33:00 2016
13// Update Count     : 1
14//
15
16#include <cassert>
17#include <list>
18#include <utility>
19#include <vector>
20
21#include "InstantiateGeneric.h"
22
23#include "DeclMutator.h"
24#include "GenPoly.h"
25#include "ScopedMap.h"
26
27#include "ResolvExpr/typeops.h"
28
29#include "SynTree/Declaration.h"
30#include "SynTree/Expression.h"
31#include "SynTree/Type.h"
32
33#include "Common/UniqueName.h"
34#include "Common/utility.h"
35
36namespace GenPoly {
37
38        /// Abstracts type equality for a list of parameter types
39        struct TypeList {
40                TypeList() : params() {}
41                TypeList( const std::list< Type* > &_params ) : params() { cloneAll(_params, params); }
42                TypeList( std::list< Type* > &&_params ) : params( _params ) {}
43
44                TypeList( const TypeList &that ) : params() { cloneAll(that.params, params); }
45                TypeList( TypeList &&that ) : params( std::move( that.params ) ) {}
46
47                /// Extracts types from a list of TypeExpr*
48                TypeList( const std::list< TypeExpr* >& _params ) : params() {
49                        for ( std::list< TypeExpr* >::const_iterator param = _params.begin(); param != _params.end(); ++param ) {
50                                params.push_back( (*param)->get_type()->clone() );
51                        }
52                }
53
54                TypeList& operator= ( const TypeList &that ) {
55                        deleteAll( params );
56
57                        params.clear();
58                        cloneAll( that.params, params );
59
60                        return *this;
61                }
62
63                TypeList& operator= ( TypeList &&that ) {
64                        deleteAll( params );
65
66                        params = std::move( that.params );
67
68                        return *this;
69                }
70
71                ~TypeList() { deleteAll( params ); }
72
73                bool operator== ( const TypeList& that ) const {
74                        if ( params.size() != that.params.size() ) return false;
75
76                        SymTab::Indexer dummy;
77                        for ( std::list< Type* >::const_iterator it = params.begin(), jt = that.params.begin(); it != params.end(); ++it, ++jt ) {
78                                if ( ! ResolvExpr::typesCompatible( *it, *jt, dummy ) ) return false;
79                        }
80                        return true;
81                }
82
83                std::list< Type* > params;  ///< Instantiation parameters
84        };
85       
86        /// Maps a key and a TypeList to the some value, accounting for scope
87        template< typename Key, typename Value >
88        class InstantiationMap {
89                /// Wraps value for a specific (Key, TypeList) combination
90                typedef std::pair< TypeList, Value* > Instantiation;
91                /// List of TypeLists paired with their appropriate values
92                typedef std::vector< Instantiation > ValueList;
93                /// Underlying map type; maps keys to a linear list of corresponding TypeLists and values
94                typedef ScopedMap< Key*, ValueList > InnerMap;
95
96                InnerMap instantiations;  ///< instantiations
97
98        public:
99                /// Starts a new scope
100                void beginScope() { instantiations.beginScope(); }
101
102                /// Ends a scope
103                void endScope() { instantiations.endScope(); }
104
105                /// Gets the value for the (key, typeList) pair, returns NULL on none such.
106                Value *lookup( Key *key, const std::list< TypeExpr* >& params ) const {
107                        TypeList typeList( params );
108
109                        // scan scopes for matches to the key
110                        for ( typename InnerMap::const_iterator insts = instantiations.find( key ); insts != instantiations.end(); insts = instantiations.findNext( insts, key ) ) {
111                                for ( typename ValueList::const_reverse_iterator inst = insts->second.rbegin(); inst != insts->second.rend(); ++inst ) {
112                                        if ( inst->first == typeList ) return inst->second;
113                                }
114                        }
115                        // no matching instantiations found
116                        return 0;
117                }
118
119                /// Adds a value for a (key, typeList) pair to the current scope
120                void insert( Key *key, const std::list< TypeExpr* > &params, Value *value ) {
121                        instantiations[ key ].push_back( Instantiation( TypeList( params ), value ) );
122                }
123        };
124       
125        /// Mutator pass that replaces concrete instantiations of generic types with actual struct declarations, scoped appropriately
126        class GenericInstantiator : public DeclMutator {
127                /// Map of (generic type, parameter list) pairs to concrete type instantiations
128                InstantiationMap< AggregateDecl, AggregateDecl > instantiations;
129                /// Namer for concrete types
130                UniqueName typeNamer;
131
132        public:
133                GenericInstantiator() : DeclMutator(), instantiations(), typeNamer("_conc_") {}
134
135                virtual Type* mutate( StructInstType *inst );
136                virtual Type* mutate( UnionInstType *inst );
137
138                virtual void doBeginScope();
139                virtual void doEndScope();
140        private:
141                /// Wrap instantiation lookup for structs
142                StructDecl* lookup( StructInstType *inst, const std::list< TypeExpr* > &typeSubs ) { return (StructDecl*)instantiations.lookup( inst->get_baseStruct(), typeSubs ); }
143                /// Wrap instantiation lookup for unions
144                UnionDecl* lookup( UnionInstType *inst, const std::list< TypeExpr* > &typeSubs ) { return (UnionDecl*)instantiations.lookup( inst->get_baseUnion(), typeSubs ); }
145                /// Wrap instantiation insertion for structs
146                void insert( StructInstType *inst, const std::list< TypeExpr* > &typeSubs, StructDecl *decl ) { instantiations.insert( inst->get_baseStruct(), typeSubs, decl ); }
147                /// Wrap instantiation insertion for unions
148                void insert( UnionInstType *inst, const std::list< TypeExpr* > &typeSubs, UnionDecl *decl ) { instantiations.insert( inst->get_baseUnion(), typeSubs, decl ); }
149        };
150
151        void instantiateGeneric( std::list< Declaration* > &translationUnit ) {
152                GenericInstantiator instantiator;
153                instantiator.mutateDeclarationList( translationUnit );
154        }
155
156        //////////////////////////////////////// GenericInstantiator //////////////////////////////////////////////////
157
158        /// Possible options for a given specialization of a generic type
159        enum class genericType {
160                dtypeStatic,  ///< Concrete instantiation based solely on {d,f}type-to-void conversions
161                concrete,     ///< Concrete instantiation requiring at least one parameter type
162                dynamic       ///< No concrete instantiation
163        };
164
165        genericType& operator |= ( genericType& gt, const genericType& ht ) {
166                switch ( gt ) {
167                case genericType::dtypeStatic:
168                        gt = ht;
169                        break;
170                case genericType::concrete:
171                        if ( ht == genericType::dynamic ) { gt = genericType::dynamic; }
172                        break;
173                case genericType::dynamic:
174                        // nothing possible
175                        break;
176                }
177                return gt;
178        }
179
180        /// Makes substitutions of params into baseParams; returns true if all parameters substituted for a concrete type
181        genericType makeSubstitutions( const std::list< TypeDecl* >& baseParams, const std::list< Expression* >& params, std::list< TypeExpr* >& out ) {
182                genericType gt = genericType::dtypeStatic;
183
184                // substitute concrete types for given parameters, and incomplete types for placeholders
185                std::list< TypeDecl* >::const_iterator baseParam = baseParams.begin();
186                std::list< Expression* >::const_iterator param = params.begin();
187                for ( ; baseParam != baseParams.end() && param != params.end(); ++baseParam, ++param ) {
188                        TypeExpr *paramType = dynamic_cast< TypeExpr* >( *param );
189                        assert(paramType && "Aggregate parameters should be type expressions");
190                       
191                        switch ( (*baseParam)->get_kind() ) {
192                        case TypeDecl::Any: {
193                                // substitute parameter for otype; makes the type concrete or dynamic depending on the parameter
194                                out.push_back( paramType->clone() );
195                                gt |= isPolyType( paramType->get_type() ) ? genericType::dynamic : genericType::concrete;
196                                break;
197                        }
198                        case TypeDecl::Dtype:
199                                // can pretend that any dtype is `void`
200                                out.push_back( new TypeExpr( new VoidType( Type::Qualifiers() ) ) );
201                                break;
202                        case TypeDecl::Ftype:
203                                // can pretend that any ftype is `void (*)(void)`
204                                out.push_back( new TypeExpr( new FunctionType( Type::Qualifiers(), false ) ) );
205                                break;
206                        }
207                }
208
209                assert( baseParam == baseParams.end() && param == params.end() && "Type parameters should match type variables" );
210                return gt;
211        }
212
213        /// Substitutes types of members of in according to baseParams => typeSubs, appending the result to out
214        void substituteMembers( const std::list< Declaration* >& in, const std::list< TypeDecl* >& baseParams, const std::list< TypeExpr* >& typeSubs,
215                                                        std::list< Declaration* >& out ) {
216                // substitute types into new members
217                TypeSubstitution subs( baseParams.begin(), baseParams.end(), typeSubs.begin() );
218                for ( std::list< Declaration* >::const_iterator member = in.begin(); member != in.end(); ++member ) {
219                        Declaration *newMember = (*member)->clone();
220                        subs.apply(newMember);
221                        out.push_back( newMember );
222                }
223        }
224
225        Type* GenericInstantiator::mutate( StructInstType *inst ) {
226                // mutate subtypes
227                Type *mutated = Mutator::mutate( inst );
228                inst = dynamic_cast< StructInstType* >( mutated );
229                if ( ! inst ) return mutated;
230
231                // exit early if no need for further mutation
232                if ( inst->get_parameters().empty() ) return inst;
233                assert( inst->get_baseParameters() && "Base struct has parameters" );
234
235                // check if type can be concretely instantiated; put substitutions into typeSubs
236                std::list< TypeExpr* > typeSubs;
237                genericType gt = makeSubstitutions( *inst->get_baseParameters(), inst->get_parameters(), typeSubs );
238                switch ( gt ) {
239                case genericType::dtypeStatic: // TODO strip params off original decl and reuse here
240                case genericType::concrete:
241                {
242                        // make concrete instantiation of generic type
243                        StructDecl *concDecl = lookup( inst, typeSubs );
244                        if ( ! concDecl ) {
245                                // set concDecl to new type, insert type declaration into statements to add
246                                concDecl = new StructDecl( typeNamer.newName( inst->get_name() ) );
247                                substituteMembers( inst->get_baseStruct()->get_members(), *inst->get_baseParameters(), typeSubs,        concDecl->get_members() );
248                                DeclMutator::addDeclaration( concDecl );
249                                insert( inst, typeSubs, concDecl );
250                        }
251                        StructInstType *newInst = new StructInstType( inst->get_qualifiers(), concDecl->get_name() );
252                        newInst->set_baseStruct( concDecl );
253
254                        delete inst;
255                        inst = newInst;
256                        break;
257                }
258
259                case genericType::dynamic:
260                        // do nothing
261                        break;
262                }
263
264                deleteAll( typeSubs );
265                return inst;
266        }
267
268        Type* GenericInstantiator::mutate( UnionInstType *inst ) {
269                // mutate subtypes
270                Type *mutated = Mutator::mutate( inst );
271                inst = dynamic_cast< UnionInstType* >( mutated );
272                if ( ! inst ) return mutated;
273
274                // exit early if no need for further mutation
275                if ( inst->get_parameters().empty() ) return inst;
276                assert( inst->get_baseParameters() && "Base union has parameters" );
277
278                // check if type can be concretely instantiated; put substitutions into typeSubs
279                std::list< TypeExpr* > typeSubs;
280                genericType gt = makeSubstitutions( *inst->get_baseParameters(), inst->get_parameters(), typeSubs );
281                switch ( gt ) {
282                case genericType::dtypeStatic:  // TODO strip params off original decls and reuse here
283                case genericType::concrete:
284                {
285                        // make concrete instantiation of generic type
286                        UnionDecl *concDecl = lookup( inst, typeSubs );
287                        if ( ! concDecl ) {
288                                // set concDecl to new type, insert type declaration into statements to add
289                                concDecl = new UnionDecl( typeNamer.newName( inst->get_name() ) );
290                                substituteMembers( inst->get_baseUnion()->get_members(), *inst->get_baseParameters(), typeSubs, concDecl->get_members() );
291                                DeclMutator::addDeclaration( concDecl );
292                                insert( inst, typeSubs, concDecl );
293                        }
294                        UnionInstType *newInst = new UnionInstType( inst->get_qualifiers(), concDecl->get_name() );
295                        newInst->set_baseUnion( concDecl );
296
297                        delete inst;
298                        inst = newInst;
299                        break;
300                }
301                case genericType::dynamic:
302                        // do nothing
303                        break;
304                }
305
306                deleteAll( typeSubs );
307                return inst;
308        }
309
310        void GenericInstantiator::doBeginScope() {
311                DeclMutator::doBeginScope();
312                instantiations.beginScope();
313        }
314
315        void GenericInstantiator::doEndScope() {
316                DeclMutator::doEndScope();
317                instantiations.endScope();
318        }
319
320} // namespace GenPoly
321
322// Local Variables: //
323// tab-width: 4 //
324// mode: c++ //
325// compile-command: "make install" //
326// End: //
Note: See TracBrowser for help on using the repository browser.