Changeset 58fe85a for src/AST/TypeEnvironment.hpp
- Timestamp:
- Jan 7, 2021, 3:27:00 PM (5 years ago)
- Branches:
- ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast-unique-expr, pthread-emulation, qualifiedEnum
- Children:
- 2b4daf2, 64aeca0
- Parents:
- 3c64c668 (diff), eef8dfb (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the(diff)
links above to see all the changes relative to each parent. - File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
src/AST/TypeEnvironment.hpp
r3c64c668 r58fe85a 37 37 /// Adding this comparison operator significantly improves assertion satisfaction run time for 38 38 /// some cases. The current satisfaction algorithm's speed partially depends on the order of 39 /// assertions. Assertions which have fewer possible matches should appear before assertions 40 /// which have more possible matches. This seems to imply that this could be further improved 41 /// by providing an indexer as an additional argument and ordering based on the number of 39 /// assertions. Assertions which have fewer possible matches should appear before assertions 40 /// which have more possible matches. This seems to imply that this could be further improved 41 /// by providing an indexer as an additional argument and ordering based on the number of 42 42 /// matches of the same kind (object, function) for the names of the declarations. 43 43 /// 44 /// I've seen a TU go from 54 minutes to 1 minute 34 seconds with the addition of this 44 /// I've seen a TU go from 54 minutes to 1 minute 34 seconds with the addition of this 45 45 /// comparator. 46 46 /// 47 /// Note: since this compares pointers for position, minor changes in the source file that 48 /// affect memory layout can alter compilation time in unpredictable ways. For example, the 49 /// placement of a line directive can reorder type pointers with respect to each other so that 50 /// assertions are seen in different orders, causing a potentially different number of 51 /// unification calls when resolving assertions. I've seen a TU go from 36 seconds to 27 52 /// seconds by reordering line directives alone, so it would be nice to fix this comparison so 53 /// that assertions compare more consistently. I've tried to modify this to compare on mangle 54 /// name instead of type as the second comparator, but this causes some assertions to never be 47 /// Note: since this compares pointers for position, minor changes in the source file that 48 /// affect memory layout can alter compilation time in unpredictable ways. For example, the 49 /// placement of a line directive can reorder type pointers with respect to each other so that 50 /// assertions are seen in different orders, causing a potentially different number of 51 /// unification calls when resolving assertions. I've seen a TU go from 36 seconds to 27 52 /// seconds by reordering line directives alone, so it would be nice to fix this comparison so 53 /// that assertions compare more consistently. I've tried to modify this to compare on mangle 54 /// name instead of type as the second comparator, but this causes some assertions to never be 55 55 /// recorded. More investigation is needed. 56 56 struct AssertCompare { 57 bool operator()( const DeclWithType * d1, const DeclWithType* d2 ) const {58 int cmp = d1-> name.compare( d2->name );59 return cmp < 0 || ( cmp == 0 && d1-> get_type() < d2->get_type());57 bool operator()( const VariableExpr * d1, const VariableExpr * d2 ) const { 58 int cmp = d1->var->name.compare( d2->var->name ); 59 return cmp < 0 || ( cmp == 0 && d1->result < d2->result ); 60 60 } 61 61 }; … … 70 70 71 71 /// Set of assertions pending satisfaction 72 using AssertionSet = std::map< readonly<DeclWithType>, AssertionSetValue, AssertCompare >;72 using AssertionSet = std::map< const VariableExpr *, AssertionSetValue, AssertCompare >; 73 73 74 74 /// Set of open variables 75 using OpenVarSet = std::unordered_map< std::string, TypeDecl::Data >;75 using OpenVarSet = std::unordered_map< TypeInstType::TypeEnvKey, TypeDecl::Data >; 76 76 77 77 /// Merges one set of open vars into another … … 86 86 void print( std::ostream &, const OpenVarSet &, Indenter indent = {} ); 87 87 88 /// Represents an equivalence class of bound type variables, optionally with the concrete type 88 /// Represents an equivalence class of bound type variables, optionally with the concrete type 89 89 /// they bind to. 90 90 struct EqvClass { 91 std:: set< std::string> vars;91 std::unordered_set< TypeInstType::TypeEnvKey > vars; 92 92 ptr<Type> bound; 93 93 bool allowWidening; … … 95 95 96 96 EqvClass() : vars(), bound(), allowWidening( true ), data() {} 97 97 98 98 /// Copy-with-bound constructor 99 EqvClass( const EqvClass & o, const Type * b ) 99 EqvClass( const EqvClass & o, const Type * b ) 100 100 : vars( o.vars ), bound( b ), allowWidening( o.allowWidening ), data( o.data ) {} 101 101 102 102 /// Singleton class constructor from TypeDecl 103 EqvClass( const Type Decl * decl)104 : vars{ decl->name }, bound(), allowWidening( true ), data( decl) {}103 EqvClass( const TypeInstType * inst ) 104 : vars{ *inst }, bound(), allowWidening( true ), data( inst->base ) {} 105 105 106 106 /// Singleton class constructor from substitution 107 EqvClass( const std::string& v, const Type * b )107 EqvClass( const TypeInstType::TypeEnvKey & v, const Type * b ) 108 108 : vars{ v }, bound( b ), allowWidening( false ), data( TypeDecl::Dtype, false ) {} 109 109 110 110 /// Single-var constructor (strips qualifiers from bound type) 111 EqvClass( const std::string& v, const Type * b, bool w, const TypeDecl::Data & d )111 EqvClass( const TypeInstType::TypeEnvKey & v, const Type * b, bool w, const TypeDecl::Data & d ) 112 112 : vars{ v }, bound( b ), allowWidening( w ), data( d ) { 113 113 reset_qualifiers( bound ); … … 115 115 116 116 /// Double-var constructor 117 EqvClass( const std::string & v, const std::string& u, bool w, const TypeDecl::Data & d )117 EqvClass( const TypeInstType::TypeEnvKey & v, const TypeInstType::TypeEnvKey & u, bool w, const TypeDecl::Data & d ) 118 118 : vars{ v, u }, bound(), allowWidening( w ), data( d ) {} 119 119 … … 131 131 public: 132 132 /// Finds the equivalence class containing a variable; nullptr for none such 133 const EqvClass * lookup( const std::string& var ) const;133 const EqvClass * lookup( const TypeInstType::TypeEnvKey & var ) const; 134 134 135 135 /// Add a new equivalence class for each type variable 136 void add( const ParameterizedType::ForallList & tyDecls );136 void add( const FunctionType::ForallList & tyDecls ); 137 137 138 138 /// Add a new equivalence class for each branch of the substitution, checking for conflicts … … 142 142 void writeToSubstitution( TypeSubstitution & sub ) const; 143 143 144 template< typename node_t , enum Node::ref_type ref_t>145 int apply( ptr_base< node_t, ref_t >& type ) const {144 template< typename node_t > 145 auto apply( node_t && type ) const { 146 146 TypeSubstitution sub; 147 147 writeToSubstitution( sub ); 148 return sub.apply( type);149 } 150 151 template< typename node_t , enum Node::ref_type ref_t>152 int applyFree( ptr_base< node_t, ref_t >& type ) const {148 return sub.apply( std::forward<node_t>(type) ); 149 } 150 151 template< typename node_t > 152 auto applyFree( node_t && type ) const { 153 153 TypeSubstitution sub; 154 154 writeToSubstitution( sub ); 155 return sub.applyFree( type);155 return sub.applyFree( std::forward<node_t>(type) ); 156 156 } 157 157 … … 172 172 void addActual( const TypeEnvironment & actualEnv, OpenVarSet & openVars ); 173 173 174 /// Binds the type class represented by `typeInst` to the type `bindTo`; will add the class if 174 /// Binds the type class represented by `typeInst` to the type `bindTo`; will add the class if 175 175 /// needed. Returns false on failure. 176 bool bindVar( 177 const TypeInstType * typeInst, const Type * bindTo, const TypeDecl::Data & data, 178 AssertionSet & need, AssertionSet & have, const OpenVarSet & openVars, 176 bool bindVar( 177 const TypeInstType * typeInst, const Type * bindTo, const TypeDecl::Data & data, 178 AssertionSet & need, AssertionSet & have, const OpenVarSet & openVars, 179 179 ResolvExpr::WidenMode widen, const SymbolTable & symtab ); 180 181 /// Binds the type classes represented by `var1` and `var2` together; will add one or both 180 181 /// Binds the type classes represented by `var1` and `var2` together; will add one or both 182 182 /// classes if needed. Returns false on failure. 183 bool bindVarToVar( 184 const TypeInstType * var1, const TypeInstType * var2, TypeDecl::Data && data, 185 AssertionSet & need, AssertionSet & have, const OpenVarSet & openVars, 183 bool bindVarToVar( 184 const TypeInstType * var1, const TypeInstType * var2, TypeDecl::Data && data, 185 AssertionSet & need, AssertionSet & have, const OpenVarSet & openVars, 186 186 ResolvExpr::WidenMode widen, const SymbolTable & symtab ); 187 187 … … 198 198 199 199 /// Unifies the type bound of `to` with the type bound of `from`, returning false if fails 200 bool mergeBound( 200 bool mergeBound( 201 201 EqvClass & to, const EqvClass & from, OpenVarSet & openVars, const SymbolTable & symtab ); 202 202 203 203 /// Merges two type classes from local environment, returning false if fails 204 bool mergeClasses( 205 ClassList::iterator to, ClassList::iterator from, OpenVarSet & openVars, 204 bool mergeClasses( 205 ClassList::iterator to, ClassList::iterator from, OpenVarSet & openVars, 206 206 const SymbolTable & symtab ); 207 207 208 208 /// Private lookup API; returns array index of string, or env.size() for not found 209 ClassList::iterator internal_lookup( const std::string& );209 ClassList::iterator internal_lookup( const TypeInstType::TypeEnvKey & ); 210 210 }; 211 211
Note:
See TracChangeset
for help on using the changeset viewer.