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

More multiplexing changes.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • 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        }
Note: See TracChangeset for help on using the changeset viewer.