Changeset 4588


Ignore:
Timestamp:
Jun 3, 2015, 9:48:23 AM (4 years ago)
Author:
nmedfort
Message:

More multiplexing changes.

Location:
icGREP/icgrep-devel/icgrep
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/compiler.cpp

    r4587 r4588  
    6262                                      cl::desc("Moves all instructions into the innermost legal If-scope so that they are only executed when needed."),
    6363                                      cl::cat(cPabloOptimizationsOptions));
     64#ifdef ENABLE_MULTIPLEXING
     65static cl::opt<bool> PabloMutualExclusionPass("mutual-exclusion", cl::init(false),
     66                                      cl::desc("Multiplex Advances whose inputs are mutual exclusive and eliminate any stream that is produces Zero."),
     67                                      cl::cat(cPabloOptimizationsOptions));
     68#endif
    6469
    6570using namespace re;
     
    9095
    9196    if (PrintAllREs || PrintParsedREs) {
    92       std::cerr << "Parser:" << std::endl << Printer_RE::PrintRE(re_ast) << std::endl;
     97        std::cerr << "Parser:" << std::endl << Printer_RE::PrintRE(re_ast) << std::endl;
    9398    }
    9499
     
    96101    re_ast = RE_Nullable::removeNullablePrefix(re_ast);
    97102    if (PrintAllREs || PrintStrippedREs) {
    98       std::cerr << "RemoveNullablePrefix:" << std::endl << Printer_RE::PrintRE(re_ast) << std::endl;
     103        std::cerr << "RemoveNullablePrefix:" << std::endl << Printer_RE::PrintRE(re_ast) << std::endl;
    99104    }
    100105    re_ast = RE_Nullable::removeNullableSuffix(re_ast);
    101106    if (PrintAllREs || PrintStrippedREs) {
    102       std::cerr << "RemoveNullableSuffix:" << std::endl << Printer_RE::PrintRE(re_ast) << std::endl;
     107        std::cerr << "RemoveNullableSuffix:" << std::endl << Printer_RE::PrintRE(re_ast) << std::endl;
    103108    }
    104109   
     
    110115
    111116    if (PrintAllREs || PrintNamedREs) {
    112       std::cerr << "Namer:" << std::endl << Printer_RE::PrintRE(re_ast) << std::endl;
    113       std::cerr << "NameMap:\n" << nameMap.printMap() << std::endl;
     117        std::cerr << "Namer:" << std::endl << Printer_RE::PrintRE(re_ast) << std::endl;
     118        std::cerr << "NameMap:\n" << nameMap.printMap() << std::endl;
    114119    }
    115120
     
    118123        re_ast = UTF8_Encoder::toUTF8(nameMap, re_ast);
    119124        if (PrintAllREs || PrintUTF8REs) {
    120           //Print to the terminal the AST that was generated by the utf8 encoder.
    121           std::cerr << "UTF8-encoder:" << std::endl << Printer_RE::PrintRE(re_ast) << std::endl;
    122           std::cerr << "NameMap:\n" << nameMap.printMap() << std::endl;
     125            //Print to the terminal the AST that was generated by the utf8 encoder.
     126            std::cerr << "UTF8-encoder:" << std::endl << Printer_RE::PrintRE(re_ast) << std::endl;
     127            std::cerr << "NameMap:\n" << nameMap.printMap() << std::endl;
    123128        }
    124129    }
     
    148153    re_compiler.initializeRequiredStreams(cc_compiler);
    149154    re_compiler.finalizeMatchResult(re_compiler.compile(re_ast));
     155
    150156    if (PrintCompiledREcode) {
    151       //Print to the terminal the AST that was generated by the pararallel bit-stream compiler.
    152       llvm::raw_os_ostream cerr(std::cerr);
    153       cerr << "Initial Pablo AST:\n";
    154       PabloPrinter::print(main.statements(), cerr);
     157        //Print to the terminal the AST that was generated by the pararallel bit-stream compiler.
     158        llvm::raw_os_ostream cerr(std::cerr);
     159        cerr << "Initial Pablo AST:\n";
     160        PabloPrinter::print(main.statements(), cerr);
    155161    }
    156162
     
    162168        CodeSinking::optimize(main);
    163169    }
    164 
    165 
    166 
    167170    #ifdef ENABLE_MULTIPLEXING
     171    if (PabloMutualExclusionPass) {
    168172        AutoMultiplexing::optimize(basisBits, main);
     173    }
    169174    #endif
    170175    if (PrintOptimizedREcode) {
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.cpp

    r4587 r4588  
    247247
    248248            bool testContradiction = true;
     249            bool updateCharacterization = true;
    249250
    250251            switch (stmt->getClassTypeId()) {
     
    282283                case PabloAST::ClassTypeId::Call:
    283284                    testContradiction = false;
    284                     assert (mCharacterizationMap.count(stmt));
    285                     bdd = mCharacterizationMap[stmt];
     285                    updateCharacterization = false;
    286286                    break;
    287287                case PabloAST::ClassTypeId::Advance:
     
    310310                            DdNode * Vi = std::get<1>(advances[i]);
    311311
     312                            // We could probably avoid some tests by infering that if X ⊂ Y and Y ⊂ Z then X ⊂ Z too. Will need a
     313                            // more complex graph structure for storing subset edges. Similarly if X ∩ Y = âˆ
     314 and Z ⊂ X, Z ∩ Y = âˆ
     315
     316
     317                            // Only test pairs if they are in the same scope or one has a user in the same scope that is reachable
     318                            // by the other?
     319
    312320                            bool constrained = true;
    313321
     
    315323                            if ((stmt->getOperand(1) == adv->getOperand(1)) && (!edge(k, i, mPathGraph).second)) {
    316324
    317                                 // Test this with Cudd_bddIntersect(mManager, Ik, Ii);
    318                                 DdNode * const tmp = And(Ik, Ii); // do we need to simplify this to identify subsets?
    319 
    320                                 if (Ik == tmp) {
    321                                     // If Ik = C and C = Ii ∩ Ik then Ik (the input to the k-th advance) is a *subset* of Ii (the input of the
     325
     326                                // Test this with Cudd_bddIntersect / Cudd_bddLeq
     327                                DdNode * const tmp = Cudd_bddIntersect(mManager, Ik, Ii);
     328                                Cudd_Ref(tmp);
     329                                // Is there any satisfying truth assignment? If not, these streams are mutually exclusive.
     330                                if (noSatisfyingAssignment(tmp)) {
     331                                    std::cerr << stmt->getName()->to_string() << " ∩ " << adv->getName()->to_string() << " = âˆ
     332"  << std::endl;
     333
     334                                    assert (mCharacterizationMap.count(adv));
     335
     336                                    DdNode *& other = mCharacterizationMap[adv];
     337                                    // mark the i-th and k-th Advances as being mutually exclusive
     338                                    bdd = And(bdd, Not(Vi));
     339                                    other = And(other, Not(Vk));
     340                                    constrained = false;
     341                                }
     342                                else if (Ik == tmp) {
     343                                    std::cerr << stmt->getName()->to_string() << " ⊂ " << adv->getName()->to_string()  << std::endl;
     344                                    // If Ik = Ii ∩ Ik then Ik (the input to the k-th advance) is a *subset* of Ii (the input of the
    322345                                    // i-th advance). Record this in the subset graph with the arc (k,i). These edges will be moved into the
    323346                                    // multiplex set graph if Advance_i and Advance_k happen to be in the same mutually exclusive set.
     
    326349                                }
    327350                                else if (Ii == tmp) {
     351                                    std::cerr << stmt->getName()->to_string() << " ⊃ " << adv->getName()->to_string()  << std::endl;
    328352                                    mSubsetGraph.emplace_back(i, k);
    329353                                    constrained = false;
    330354                                }
    331                                 // Is there any satisfying truth assignment? If not, these streams are mutually exclusive.
    332                                 else if (noSatisfyingAssignment(tmp)) {
    333 
    334                                     assert (mCharacterizationMap.count(adv));
    335 
    336                                     DdNode *& other = mCharacterizationMap[adv];
    337                                     // mark the i-th and k-th Advances as being mutually exclusive
    338                                     bdd = And(bdd, Not(Vi));
    339                                     other = And(other, Not(Vk));
    340                                     constrained = false;
    341                                 }
    342 
    343355                                Cudd_RecursiveDeref(mManager, tmp);
    344356                            }
    345357
    346                             // Advances must be in the same scope or they cannot be safely multiplexed unless one is moved.
     358                            // Even if these Advances are mutually exclusive, they must be in the same scope or they cannot be safely multiplexed.
    347359                            if (constrained || (stmt->getParent() != adv->getParent())) {
    348360                                // We want the constraint graph to be acyclic; since the dependencies are already in topological order,
     
    367379                Cudd_RecursiveDeref(mManager, bdd);               
    368380                stmt = stmt->replaceWith(entry.createZeroes());
    369             }
    370             else {               
     381                continue;
     382            }
     383            else if (LLVM_LIKELY(updateCharacterization)){
    371384                mCharacterizationMap[stmt] = bdd;
    372                 stmt = stmt->getNextNode();
    373             }
     385            }
     386            stmt = stmt->getNextNode();
    374387        }
    375388
     
    799812
    800813                std::stringstream name;
    801 
    802814                name << "mux";
    803 
    804815                for (size_t i = 1; i <= n; ++i) {
    805816                    if ((i & (static_cast<size_t>(1) << j)) != 0) {
     
    880891                }
    881892
    882                 PabloAST * a1 = Q.front(); Q.pop_front(); assert (demux);
     893                assert (Q.size() >= 0 && Q.size() <= 2);
     894
     895                PabloAST * a1 = Q.front(); Q.pop_front(); assert (a1);
    883896                PabloAST * a2 = neg;
    884                 if (LLVM_UNLIKELY(Q.size() == 2)) {
     897                if (LLVM_UNLIKELY(neg == nullptr)) {
    885898                    a2 = Q.front(); Q.pop_front(); assert (a2);
    886899                }
     900                assert (Q.empty());
     901
    887902                pb->setInsertPoint(choose(a2, a1, adv));
    888903                PabloAST * demux = pb->createAnd(a1, a2, "demux_" + V[i - 1]->getName()->to_string());
    889904
    890                 V[i - 1]->replaceWith(demux, false, true);
     905                V[i - 1]->replaceWith(demux, false);
    891906            }
    892907        }
  • icGREP/icgrep-devel/icgrep/slab_allocator.h

    r4586 r4588  
    1919    }
    2020    static inline void Reset() {
    21         #ifndef NDEBUG
    22         mAllocator.PrintStats();
    23         #endif
    2421        mAllocator.Reset();
    2522    }
Note: See TracChangeset for help on using the changeset viewer.