Changeset 7583c02


Ignore:
Timestamp:
Dec 31, 2020, 4:17:19 PM (9 months ago)
Author:
Fangren Yu <f37yu@…>
Branches:
arm-eh, jacob/cs343-translation, master, new-ast-unique-expr
Children:
09da82d
Parents:
abc2a643
Message:

partially improve #226: resolver environment size reduced to O(n)

generated code still has exponential size. should cache resolved implicits
and reuse thunks to reduce generated code size.
assertion fails cannot exit early and may have a minor performance
reduction.

Location:
src/ResolvExpr
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • src/ResolvExpr/RenameVars.cc

    rabc2a643 r7583c02  
    186186}
    187187
    188 const ast::Type * renameTyVars( const ast::Type * t, RenameMode mode ) {
     188const ast::Type * renameTyVars( const ast::Type * t, RenameMode mode, bool reset ) {
    189189        // ast::Type *tc = ast::deepCopy(t);
    190190        ast::Pass<RenameVars_new> renamer;
    191191        renamer.core.mode = mode;
    192         if (mode == GEN_USAGE) {
     192        if (mode == GEN_USAGE && reset) {
    193193                renaming.nextUsage();
    194194        }
     
    198198void resetTyVarRenaming() {
    199199        renaming.reset();
     200        renaming.nextUsage();
    200201}
    201202
  • src/ResolvExpr/RenameVars.h

    rabc2a643 r7583c02  
    3535                GEN_EXPR_ID // for type in decl
    3636        };
    37         const ast::Type * renameTyVars( const ast::Type *, RenameMode mode = GEN_USAGE );
     37        const ast::Type * renameTyVars( const ast::Type *, RenameMode mode = GEN_USAGE, bool reset = true );
     38       
    3839
    3940        /// resets internal state of renamer to avoid overflow
  • src/ResolvExpr/Resolver.cc

    rabc2a643 r7583c02  
    11511151                        const ast::Expr * untyped, const ast::SymbolTable & symtab
    11521152                ) {
    1153                         resetTyVarRenaming();
    11541153                        ast::TypeEnvironment env;
    11551154                        ast::ptr< ast::Expr > newExpr = resolveInVoidContext( untyped, symtab, env );
  • src/ResolvExpr/SatisfyAssertions.cpp

    rabc2a643 r7583c02  
    202202                        ast::ptr< ast::Type > toType = assn.first->result;
    203203                        ast::ptr< ast::Type > adjType =
    204                                 renameTyVars( adjustExprType( candidate->get_type(), newEnv, sat.symtab ) );
     204                                renameTyVars( adjustExprType( candidate->get_type(), newEnv, sat.symtab ), GEN_USAGE, false );
    205205
    206206                        // only keep candidates which unify
     
    417417                        if ( it != thresholds.end() && it->second < sat.costs ) goto nextSat;
    418418
    419                         // make initial pass at matching assertions
    420                         for ( auto & assn : sat.need ) {
    421                                 // fail early if any assertion is not satisfiable
    422                                 if ( ! satisfyAssertion( assn, sat ) ) {
     419                        // should a limit be imposed? worst case here is O(n^2) but very unlikely to happen.
     420                        for (unsigned resetCount = 0; ; ++resetCount) {
     421                                ast::AssertionList next;
     422                                resetTyVarRenaming();
     423                                // make initial pass at matching assertions
     424                                for ( auto & assn : sat.need ) {
     425                                        // fail early if any assertion is not satisfiable
     426                                        if ( ! satisfyAssertion( assn, sat ) ) {
     427                                                next.emplace_back(assn);
     428                                                // goto nextSat;
     429                                        }
     430                                }
     431                                // success
     432                                if (next.empty()) break;
     433                                // fail if nothing resolves
     434                                else if (next.size() == sat.need.size()) {
    423435                                        Indenter tabs{ 3 };
    424436                                        std::ostringstream ss;
     
    426438                                        print( ss, *sat.cand, ++tabs );
    427439                                        ss << (tabs-1) << "Could not satisfy assertion:\n";
    428                                         ast::print( ss, assn.first, tabs );
     440                                        ast::print( ss, next[0].first, tabs );
    429441
    430442                                        errors.emplace_back( ss.str() );
    431443                                        goto nextSat;
    432444                                }
     445                                sat.need = std::move(next);
    433446                        }
    434447
Note: See TracChangeset for help on using the changeset viewer.