Changeset b408364


Ignore:
Timestamp:
Jun 18, 2019, 5:51:23 PM (2 years ago)
Author:
Aaron Moss <a3moss@…>
Branches:
arm-eh, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr
Children:
898ae07
Parents:
c8e4d2f8
Message:

Correct over-aggressive assertion pruning

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/ResolvExpr/ResolveAssertions.cc

    rc8e4d2f8 rb408364  
    186186        using InferCache = std::unordered_map< UniqueId, InferredParams >;
    187187
     188        /// Lexicographically-ordered vector of costs
     189        using CostVec = std::vector< Cost >;
     190
     191        int compare( const CostVec & a, const CostVec & b ) {
     192                unsigned i = 0;
     193                do {
     194                        // lex-compare where shorter one is less
     195                        if ( i == a.size() ) {
     196                                return i == b.size() ? 0 : -1;
     197                        }
     198                        if ( i == b.size() /* && i < a.size() */ ) return 1;
     199                       
     200                        int c = a[i].compare( b[i] );
     201                        if ( c != 0 ) return c;
     202                } while ( ++i );
     203                assert(!"unreachable");
     204        }
     205
     206        bool operator< ( const CostVec & a, const CostVec & b ) { return compare( a, b ) < 0; }
     207
    188208        /// Flag for state iteration
    189209        enum IterateFlag { IterateState };
     
    196216                DeferList deferred;        ///< Deferred matches
    197217                InferCache inferred;       ///< Cache of already-inferred parameters
     218                CostVec costs;             ///< Costs of recursive assertion satisfaction for disambiguation
    198219                SymTab::Indexer& indexer;  ///< Name lookup (depends on previous assertions)
    199220
    200221                /// Initial resolution state for an alternative
    201222                ResnState( Alternative& a, SymTab::Indexer& indexer )
    202                 : alt(a), need(), newNeed(), deferred(), inferred(), indexer(indexer) {
     223                : alt(a), need(), newNeed(), deferred(), inferred(), costs{ Cost::zero }, indexer(indexer) {
    203224                        need.swap( a.need );
    204225                }
     
    207228                ResnState( ResnState&& o, IterateFlag )
    208229                : alt(std::move(o.alt)), need(o.newNeed.begin(), o.newNeed.end()), newNeed(), deferred(),
    209                   inferred(std::move(o.inferred)), indexer(o.indexer) {}
     230                  inferred(std::move(o.inferred)), costs(o.costs), indexer(o.indexer) {
     231                        costs.emplace_back( Cost::zero );
     232                }
    210233        };
    211234
     
    336359        };
    337360
    338         void finalizeAssertions( Alternative& alt, InferCache& inferred, AltList& out ) {
    339                 PassVisitor<InferMatcher> matcher{ inferred };
    340                 alt.expr = alt.expr->acceptMutator( matcher );
    341                 out.emplace_back( alt );
     361        /// Map of alternative return types to recursive assertion satisfaction costs
     362        using PruneMap = std::unordered_map<std::string, CostVec>;
     363
     364        /// Gets the pruning key for an alternative
     365        std::string pruneKey( const Alternative & alt ) {
     366                Type* resType = alt.expr->result->clone();
     367                alt.env.apply( resType );
     368                std::string resKey = SymTab::Mangler::mangleType( resType );
     369                delete resType;
     370                return std::move( resKey );
     371        }
     372       
     373        /// Replace resnSlots with inferParams and add alternative to output list, if meets pruning
     374        /// threshold.
     375        void finalizeAssertions( ResnState& resn, PruneMap & pruneThresholds, AltList& out ) {
     376                // prune if cheaper alternative for same key has already been generated
     377                std::string resKey = pruneKey( resn.alt );
     378                auto it = pruneThresholds.find( resKey );
     379                if ( it != pruneThresholds.end() ) {
     380                        if ( it->second < resn.costs ) return;
     381                } else {
     382                        pruneThresholds.emplace_hint( it, resKey, resn.costs );
     383                }
     384
     385                // replace resolution slots with inferred params, add to output
     386                PassVisitor<InferMatcher> matcher{ resn.inferred };
     387                resn.alt.expr = resn.alt.expr->acceptMutator( matcher );
     388                out.emplace_back( resn.alt );
    342389        }
    343390
     
    359406                ResnList resns{ ResnState{ alt, root_indexer } };
    360407                ResnList new_resns{};
     408               
     409                // Pruning thresholds by result type of the output alternatives.
     410                // Alternatives *should* be generated in sorted order, so no need to retroactively prune
     411                PruneMap thresholds;
    361412
    362413                // resolve assertions in breadth-first-order up to a limited number of levels deep
     
    364415                        // scan over all mutually-compatible resolutions
    365416                        for ( auto& resn : resns ) {
     417                                // stop this branch if already found a better option
     418                                auto it = thresholds.find( pruneKey( resn.alt ) );
     419                                if ( it != thresholds.end() && it->second < resn.costs ) goto nextResn;
     420
    366421                                // make initial pass at matching assertions
    367422                                for ( auto& assn : resn.need ) {
     
    383438                                        // either add successful match or push back next state
    384439                                        if ( resn.newNeed.empty() ) {
    385                                                 finalizeAssertions( resn.alt, resn.inferred, out );
     440                                                finalizeAssertions( resn, thresholds, out );
    386441                                        } else {
    387442                                                new_resns.emplace_back( std::move(resn), IterateState );
     
    420475                                                goto nextResn;
    421476                                        }
    422                                         // sort by cost
     477                                        // sort by cost for overall pruning
    423478                                        CandidateCost coster{ resn.indexer };
    424479                                        std::sort( compatible.begin(), compatible.end(), coster );
    425480
    426                                         // keep map of detected options
    427                                         std::unordered_map<std::string, Cost> found;
    428481                                        for ( auto& compat : compatible ) {
    429                                                 // filter by environment-adjusted result type, keep only cheapest option
    430                                                 Type* resType = alt.expr->result->clone();
    431                                                 compat.env.apply( resType );
    432                                                 // skip if cheaper alternative already processed with same result type
    433                                                 Cost resCost = coster.get( compat );
    434                                                 auto it = found.emplace( SymTab::Mangler::mangleType( resType ), resCost );
    435                                                 delete resType;
    436                                                 if ( it.second == false && it.first->second < resCost ) continue;
    437 
    438                                                 // proceed with resolution step
    439482                                                ResnState new_resn = resn;
    440483
     
    452495                                                new_resn.alt.openVars = std::move(compat.openVars);
    453496
     497                                                // mark cost of this path
     498                                                new_resn.costs.back() += compat.cost;
     499
    454500                                                // either add sucessful match or push back next state
    455501                                                if ( new_resn.newNeed.empty() ) {
    456                                                         finalizeAssertions( new_resn.alt, new_resn.inferred, out );
     502                                                        finalizeAssertions( new_resn, thresholds, out );
    457503                                                } else {
    458504                                                        new_resns.emplace_back( std::move(new_resn), IterateState );
Note: See TracChangeset for help on using the changeset viewer.