source: src/ResolvExpr/SpecCost.cc @ 954c954

arm-ehjacob/cs343-translationnew-ast-unique-expr
Last change on this file since 954c954 was 954c954, checked in by Fangren Yu <f37yu@…>, 13 months ago

Move function argument and return variable declarations from FunctionType? to FunctionDecl?

  • Property mode set to 100644
File size: 7.1 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// SpecCost.cc --
8//
9// Author           : Aaron B. Moss
10// Created On       : Tue Oct 02 15:50:00 2018
11// Last Modified By : Andrew Beach
12// Last Modified On : Wed Jul  3 11:07:00 2019
13// Update Count     : 3
14//
15
16#include <cassert>
17#include <limits>
18#include <list>
19#include <type_traits>
20
21#include "AST/Pass.hpp"
22#include "AST/Type.hpp"
23#include "Common/PassVisitor.h"
24#include "SynTree/Declaration.h"
25#include "SynTree/Expression.h"
26#include "SynTree/Type.h"
27
28namespace ResolvExpr {
29
30        /// Counts specializations in a type
31        class CountSpecs : public WithShortCircuiting, public WithVisitorRef<CountSpecs> {
32                int count = -1;  ///< specialization count (-1 for none)
33
34        public:
35                int get_count() const { return count >= 0 ? count : 0; }
36
37                // mark specialization of base type
38                void postvisit(PointerType*) { if ( count >= 0 ) ++count; }
39
40                // mark specialization of base type
41                void postvisit(ArrayType*) { if ( count >= 0 ) ++count; }
42
43                // mark specialization of base type
44                void postvisit(ReferenceType*) { if ( count >= 0 ) ++count; }
45
46        private:
47                // takes minimum non-negative count over parameter/return list
48                void takeminover( int& mincount, std::list<DeclarationWithType*>& dwts ) {
49                        for ( DeclarationWithType* dwt : dwts ) {
50                                count = -1;
51                                maybeAccept( dwt->get_type(), *visitor );
52                                if ( count != -1 && count < mincount ) mincount = count;
53                        }
54                }
55
56        public:
57                // take minimal specialization value over ->returnVals and ->parameters
58                void previsit(FunctionType* fty) {
59                        int mincount = std::numeric_limits<int>::max();
60                        takeminover( mincount, fty->parameters );
61                        takeminover( mincount, fty->returnVals );
62                        // add another level to mincount if set
63                        count = mincount < std::numeric_limits<int>::max() ? mincount + 1 : -1;
64                        // already visited children
65                        visit_children = false;
66                }
67
68        private:
69                // returns minimum non-negative count + 1 over type parameters (-1 if none such)
70                int minover( std::list<Expression*>& parms ) {
71                        int mincount = std::numeric_limits<int>::max();
72                        for ( Expression* parm : parms ) {
73                                count = -1;
74                                maybeAccept( parm->result, *visitor );
75                                if ( count != -1 && count < mincount ) mincount = count;
76                        }
77                        return mincount < std::numeric_limits<int>::max() ? mincount + 1 : -1;
78                }
79
80        public:
81                // look for polymorphic parameters
82                void previsit(StructInstType* sty) {
83                        count = minover( sty->parameters );
84                        visit_children = false;
85                }
86
87                // look for polymorphic parameters
88                void previsit(UnionInstType* uty) {
89                        count = minover( uty->parameters );
90                        visit_children = false;
91                }
92
93                // note polymorphic type (which may be specialized)
94                // xxx - maybe account for open/closed type variables
95                void postvisit(TypeInstType*) { count = 0; }
96
97                // take minimal specialization over elements
98                // xxx - maybe don't increment, tuple flattening doesn't necessarily specialize
99                void previsit(TupleType* tty) {
100                        int mincount = std::numeric_limits<int>::max();
101                        for ( Type* ty : tty->types ) {
102                                count = -1;
103                                maybeAccept( ty, *visitor );
104                                if ( count != -1 && count < mincount ) mincount = count;
105                        }
106                        count = mincount < std::numeric_limits<int>::max() ? mincount + 1 : -1;
107                        visit_children = false;
108                }
109        };
110
111        /// Returns the (negated) specialization cost for a given type
112        int specCost( Type* ty ) {
113                PassVisitor<CountSpecs> counter;
114                maybeAccept( ty, *counter.pass.visitor );
115                return counter.pass.get_count();
116        }
117
118namespace {
119        /// The specialization counter inner class.
120        class SpecCounter : public ast::WithShortCircuiting, public ast::WithVisitorRef<SpecCounter> {
121                int count = -1;  ///< specialization count (-1 for none)
122
123                // Converts the max value to -1 (none), otherwise increments the value.
124                static int toNoneOrInc( int value ) {
125                        assert( 0 <= value );
126                        return value < std::numeric_limits<int>::max() ? value + 1 : -1;
127                }
128
129                template<typename T> using MapperT =
130                        typename std::add_pointer<ast::Type const *(typename T::value_type const &)>::type;
131
132                #warning Should use a standard maybe_accept
133                void maybe_accept( ast::Type const * type ) {
134                        if ( type ) {
135                                auto node = type->accept( *visitor );
136                                assert( node == nullptr || node == type );
137                        }
138                }
139
140                // Update the minimum to the new lowest non-none value.
141                template<typename T>
142                void updateMinimumPresent( int & minimum, const T & list, MapperT<T> mapper ) {
143                        for ( const auto & node : list ) {
144                                count = -1;
145                                maybe_accept( mapper( node ) );
146                                if ( count != -1 && count < minimum ) minimum = count;
147                        }
148                }
149
150                // Returns minimum non-negative count + 1 over type parameters (-1 if none such).
151                template<typename T>
152                int minimumPresent( const T & list, MapperT<T> mapper ) {
153                        int minCount = std::numeric_limits<int>::max();
154                        updateMinimumPresent( minCount, list, mapper );
155                        return toNoneOrInc( minCount );
156                }
157
158                // The three mappers:
159                static const ast::Type * decl_type( const ast::ptr< ast::DeclWithType > & decl ) {
160                        return decl->get_type();
161                }
162                static const ast::Type * expr_result( const ast::ptr< ast::Expr > & expr ) {
163                        return expr->result;
164                }
165                static const ast::Type * type_deref( const ast::ptr< ast::Type > & type ) {
166                        return type.get();
167                }
168
169        public:
170                int get_count() const { return 0 <= count ? count : 0; }
171
172                // Mark specialization of base type.
173                void postvisit( const ast::PointerType * ) { if ( count >= 0 ) ++count; }
174                void postvisit( const ast::ArrayType * ) { if ( count >= 0 ) ++count; }
175                void postvisit( const ast::ReferenceType * ) { if ( count >= 0 ) ++count; }
176
177                // Use the minimal specialization value over returns and params.
178                void previsit( const ast::FunctionType * fty ) {
179                        int minCount = std::numeric_limits<int>::max();
180                        updateMinimumPresent( minCount, fty->params, type_deref );
181                        updateMinimumPresent( minCount, fty->returns, type_deref );
182                        // Add another level to minCount if set.
183                        count = toNoneOrInc( minCount );
184                        // We have already visited children.
185                        visit_children = false;
186                }
187
188                // Look for polymorphic parameters.
189                void previsit( const ast::StructInstType * sty ) {
190                        count = minimumPresent( sty->params, expr_result );
191                        visit_children = false;
192                }
193
194                // Look for polymorphic parameters.
195                void previsit( const ast::UnionInstType * uty ) {
196                        count = minimumPresent( uty->params, expr_result );
197                        visit_children = false;
198                }
199
200                // Note polymorphic type (which may be specialized).
201                // xxx - maybe account for open/closed type variables
202                void postvisit( const ast::TypeInstType * ) { count = 0; }
203
204                // Use the minimal specialization over elements.
205                // xxx - maybe don't increment, tuple flattening doesn't necessarily specialize
206                void previsit( const ast::TupleType * tty ) {
207                        count = minimumPresent( tty->types, type_deref );
208                        visit_children = false;
209                }
210        };
211
212} // namespace
213
214int specCost( const ast::Type * type ) {
215        if ( nullptr == type ) {
216                return 0;
217        }
218        ast::Pass<SpecCounter> counter;
219        type->accept( counter );
220        return counter.core.get_count();
221}
222
223} // namespace ResolvExpr
224
225// Local Variables: //
226// tab-width: 4 //
227// mode: c++ //
228// compile-command: "make install" //
229// End: //
Note: See TracBrowser for help on using the repository browser.