Ignore:
Timestamp:
Jan 7, 2021, 3:27:00 PM (5 years ago)
Author:
Thierry Delisle <tdelisle@…>
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.
Message:

Merge branch 'master' into park_unpark

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/AST/TypeEnvironment.hpp

    r3c64c668 r58fe85a  
    3737/// Adding this comparison operator significantly improves assertion satisfaction run time for
    3838/// 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
    4242/// matches of the same kind (object, function) for the names of the declarations.
    4343///
    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
    4545/// comparator.
    4646///
    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
    5555/// recorded. More investigation is needed.
    5656struct 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 );
    6060        }
    6161};
     
    7070
    7171/// Set of assertions pending satisfaction
    72 using AssertionSet = std::map< readonly<DeclWithType>, AssertionSetValue, AssertCompare >;
     72using AssertionSet = std::map< const VariableExpr *, AssertionSetValue, AssertCompare >;
    7373
    7474/// Set of open variables
    75 using OpenVarSet = std::unordered_map< std::string, TypeDecl::Data >;
     75using OpenVarSet = std::unordered_map< TypeInstType::TypeEnvKey, TypeDecl::Data >;
    7676
    7777/// Merges one set of open vars into another
     
    8686void print( std::ostream &, const OpenVarSet &, Indenter indent = {} );
    8787
    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
    8989/// they bind to.
    9090struct EqvClass {
    91         std::set< std::string > vars;
     91        std::unordered_set< TypeInstType::TypeEnvKey > vars;
    9292        ptr<Type> bound;
    9393        bool allowWidening;
     
    9595
    9696        EqvClass() : vars(), bound(), allowWidening( true ), data() {}
    97        
     97
    9898        /// Copy-with-bound constructor
    99         EqvClass( const EqvClass & o, const Type * b ) 
     99        EqvClass( const EqvClass & o, const Type * b )
    100100        : vars( o.vars ), bound( b ), allowWidening( o.allowWidening ), data( o.data ) {}
    101101
    102102        /// Singleton class constructor from TypeDecl
    103         EqvClass( const TypeDecl * decl )
    104         : vars{ decl->name }, bound(), allowWidening( true ), data( decl ) {}
     103        EqvClass( const TypeInstType * inst )
     104        : vars{ *inst }, bound(), allowWidening( true ), data( inst->base ) {}
    105105
    106106        /// Singleton class constructor from substitution
    107         EqvClass( const std::string & v, const Type * b )
     107        EqvClass( const TypeInstType::TypeEnvKey & v, const Type * b )
    108108        : vars{ v }, bound( b ), allowWidening( false ), data( TypeDecl::Dtype, false ) {}
    109109
    110110        /// 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 )
    112112        : vars{ v }, bound( b ), allowWidening( w ), data( d ) {
    113113                reset_qualifiers( bound );
     
    115115
    116116        /// 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 )
    118118        : vars{ v, u }, bound(), allowWidening( w ), data( d ) {}
    119119
     
    131131public:
    132132        /// 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;
    134134
    135135        /// Add a new equivalence class for each type variable
    136         void add( const ParameterizedType::ForallList & tyDecls );
     136        void add( const FunctionType::ForallList & tyDecls );
    137137
    138138        /// Add a new equivalence class for each branch of the substitution, checking for conflicts
     
    142142        void writeToSubstitution( TypeSubstitution & sub ) const;
    143143
    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 {
    146146                TypeSubstitution sub;
    147147                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 {
    153153                TypeSubstitution sub;
    154154                writeToSubstitution( sub );
    155                 return sub.applyFree( type );
     155                return sub.applyFree( std::forward<node_t>(type) );
    156156        }
    157157
     
    172172        void addActual( const TypeEnvironment & actualEnv, OpenVarSet & openVars );
    173173
    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
    175175        /// 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,
    179179                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
    182182        /// 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,
    186186                ResolvExpr::WidenMode widen, const SymbolTable & symtab );
    187187
     
    198198
    199199        /// Unifies the type bound of `to` with the type bound of `from`, returning false if fails
    200         bool mergeBound( 
     200        bool mergeBound(
    201201                EqvClass & to, const EqvClass & from, OpenVarSet & openVars, const SymbolTable & symtab );
    202202
    203203        /// 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,
    206206                const SymbolTable & symtab );
    207207
    208208        /// 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 & );
    210210};
    211211
Note: See TracChangeset for help on using the changeset viewer.