Changeset 4590 for icGREP/icgrep-devel


Ignore:
Timestamp:
Jun 3, 2015, 12:06:07 PM (4 years ago)
Author:
nmedfort
Message:

More multiplexing work; close to passing make check.

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

Legend:

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

    r4588 r4590  
    6363                                      cl::cat(cPabloOptimizationsOptions));
    6464#ifdef ENABLE_MULTIPLEXING
    65 static 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."),
     65static cl::opt<bool> PabloMutualExclusionPass("mutual-exclusion", cl::init(true),
     66                                      cl::desc("Multiplex Advances whose inputs are mutual exclusive and replaces any contradictory stream with Zero."),
    6767                                      cl::cat(cPabloOptimizationsOptions));
    6868#endif
     
    168168        CodeSinking::optimize(main);
    169169    }
     170
    170171    #ifdef ENABLE_MULTIPLEXING
    171172    if (PabloMutualExclusionPass) {
     173        if (PrintCompiledREcode) {
     174            //Print to the terminal the AST that was generated by the pararallel bit-stream compiler.
     175            llvm::raw_os_ostream cerr(std::cerr);
     176            cerr << "Pre-Multiplexing Pablo AST:\n";
     177            PabloPrinter::print(main.statements(), cerr);
     178        }
    172179        AutoMultiplexing::optimize(basisBits, main);
    173180    }
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.cpp

    r4588 r4590  
    226226                scope.push(stmt->getNextNode());
    227227                stmt = nested.front();
    228                 assert (stmt);
    229228                continue;
    230229            }
    231230
    232231            DdNode * bdd = nullptr;
    233 
    234232            // Map our operands to the computed BDDs
    235233            std::array<DdNode *, 3> input;
     
    247245
    248246            bool testContradiction = true;
    249             bool updateCharacterization = true;
     247            bool updateVariable = true;
    250248
    251249            switch (stmt->getClassTypeId()) {
     
    283281                case PabloAST::ClassTypeId::Call:
    284282                    testContradiction = false;
    285                     updateCharacterization = false;
     283                    updateVariable = false;
    286284                    break;
    287285                case PabloAST::ClassTypeId::Advance:
    288 
    289286                    assert (stmt == mAdvance[advances.size()]);
    290 
    291287                    if (LLVM_UNLIKELY(isZero(input[0]))) {
    292288                        bdd = Cudd_ReadZero(mManager);
     
    315311
    316312
    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?
     313                            // Only test pairs if they are in the same scope or one has a user in the a scope that is reachable by
     314                            // the other?
    319315
    320316                            bool constrained = true;
     
    322318                            // If these advances are "shifting" their values by the same amount and aren't transitively dependant ...
    323319                            if ((stmt->getOperand(1) == adv->getOperand(1)) && (!edge(k, i, mPathGraph).second)) {
    324 
    325 
    326                                 // Test this with Cudd_bddIntersect / Cudd_bddLeq
     320                                // Test this with Cudd_And, Cudd_bddIntersect (and maybe Cudd_bddLeq?) to see which is faster ...
    327321                                DdNode * const tmp = Cudd_bddIntersect(mManager, Ik, Ii);
    328322                                Cudd_Ref(tmp);
    329323                                // Is there any satisfying truth assignment? If not, these streams are mutually exclusive.
    330324                                if (noSatisfyingAssignment(tmp)) {
    331                                     std::cerr << stmt->getName()->to_string() << " ∩ " << adv->getName()->to_string() << " = âˆ
    332 "  << std::endl;
    333 
    334325                                    assert (mCharacterizationMap.count(adv));
    335326
     
    341332                                }
    342333                                else if (Ik == tmp) {
    343                                     std::cerr << stmt->getName()->to_string() << " ⊂ " << adv->getName()->to_string()  << std::endl;
    344334                                    // If Ik = Ii ∩ Ik then Ik (the input to the k-th advance) is a *subset* of Ii (the input of the
    345335                                    // i-th advance). Record this in the subset graph with the arc (k,i). These edges will be moved into the
     
    349339                                }
    350340                                else if (Ii == tmp) {
    351                                     std::cerr << stmt->getName()->to_string() << " ⊃ " << adv->getName()->to_string()  << std::endl;
    352341                                    mSubsetGraph.emplace_back(i, k);
    353342                                    constrained = false;
     
    364353
    365354                        }
    366 
    367                         // Append this advance to the list of known advances in this "basic block"; add on the input's BDD to
    368                         // eliminate the need for looking it up again.
     355                        // Append this advance to the list of known advances. Both its input BDD and the Advance variable are stored in
     356                        // the list to eliminate the need for searching for it.
    369357                        advances.emplace_back(Ik, Vk);
    370358                        testContradiction = false;
    371359                    }
    372 
    373 
    374360                    break;
    375361                default:
    376362                    throw std::runtime_error("Unexpected statement " + stmt->getName()->to_string());
    377363            }
     364            assert ("Failed to generate a BDD." && (bdd || !(testContradiction || updateVariable)));
    378365            if (LLVM_UNLIKELY(testContradiction && noSatisfyingAssignment(bdd))) {
     366                // std::cerr << stmt->getName()->to_string() << " = âˆ
     367"  << std::endl;
    379368                Cudd_RecursiveDeref(mManager, bdd);               
    380369                stmt = stmt->replaceWith(entry.createZeroes());
    381                 continue;
    382             }
    383             else if (LLVM_LIKELY(updateCharacterization)){
     370            }
     371            else if (LLVM_LIKELY(updateVariable)) {
    384372                mCharacterizationMap[stmt] = bdd;
    385373            }
     
    919907 ** ------------------------------------------------------------------------------------------------------------- */
    920908void AutoMultiplexing::topologicalSort(PabloBlock & entry) const {
    921 
    922909    // Note: not a real topological sort. I expect the original order to be very close to the resulting one.
    923 
    924     std::unordered_set<PabloAST *> encountered;
     910    std::unordered_set<const PabloAST *> encountered;
    925911    std::stack<Statement *> scope;
    926912    for (Statement * stmt = entry.front(); ; ) {
    927 
    928         while ( stmt ) {
    929 
    930             bool moved = false;
    931 
     913restart:while ( stmt ) {
    932914            for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
    933915                PabloAST * const op = stmt->getOperand(i);
    934916                if (LLVM_LIKELY(isa<Statement>(op))) {
    935917                    if (LLVM_UNLIKELY(encountered.count(op) == 0)) {
    936                         Statement * next = stmt->getNextNode();
     918                        if (LLVM_UNLIKELY(isa<While>(stmt) && isa<Next>(op))) {
     919                            if (encountered.count(cast<Next>(op)->getInitial()) != 0) {
     920                                continue;
     921                            }
     922                        }
     923                        Statement * const next = stmt->getNextNode();
    937924                        stmt->insertAfter(cast<Statement>(op));
    938925                        stmt = next;
    939                         moved = true;
    940                         break;
    941                     }
    942                 }
    943             }
    944 
    945             if (moved) {
    946                 continue;
    947             }
    948 
    949             encountered.insert(stmt);
    950 
     926                        goto restart;
     927                    }
     928                }
     929            }
    951930            if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
    952931                // Set the next statement to be the first statement of the inner scope and push the
     
    955934                scope.push(stmt->getNextNode());
    956935                stmt = nested.front();
    957                 assert (stmt);
    958936                continue;
    959937            }
    960 
     938            encountered.insert(stmt);
    961939            stmt = stmt->getNextNode();
    962940        }
    963 
    964941        if (scope.empty()) {
    965942            break;
     
    968945        scope.pop();
    969946    }
    970 
    971947}
    972948
Note: See TracChangeset for help on using the changeset viewer.