source: src/ResolvExpr/SpecCost.cc @ 7d01cf44

ADTarm-ehast-experimentalenumforall-pointer-decayjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprpthread-emulationqualifiedEnum
Last change on this file since 7d01cf44 was 5aa4656, checked in by Andrew Beach <ajbeach@…>, 5 years ago

Filled in SpecCost? and PolyCost? for the new ast.

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