Ignore:
Timestamp:
Nov 14, 2015, 5:38:36 PM (4 years ago)
Author:
nmedfort
Message:

Bug fix for Multiplexing. Added ability to set the body of a If/While? node after creation.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.cpp

    r4868 r4870  
    5656                " (" << (((double)num_edges(G)) / ((double)(num_vertices(G) * (num_vertices(G) - 1) / 2))) << ')')
    5757
    58 unsigned __count_advances(const PabloBlock & entry) {
     58unsigned __count_advances(const PabloBlock * const entry) {
    5959
    6060    std::stack<const Statement *> scope;
     
    6262
    6363    // Scan through and collect all the advances, calls, scanthrus and matchstars ...
    64     for (const Statement * stmt = entry.front(); ; ) {
     64    for (const Statement * stmt = entry->front(); ; ) {
    6565        while ( stmt ) {
    6666            if (isa<Advance>(stmt)) {
     
    7070                // Set the next statement to be the first statement of the inner scope and push the
    7171                // next statement of the current statement into the scope stack.
    72                 const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
     72                const PabloBlock * const nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
    7373                scope.push(stmt->getNextNode());
    74                 stmt = nested.front();
     74                stmt = nested->front();
    7575                assert (stmt);
    7676                continue;
     
    108108    RNG rng(seed);
    109109
     110
     111    raw_os_ostream out(std::cerr);
     112
     113//    out << seed << ',';
     114
    110115    LOG("Seed:                    " << seed);
    111116
    112117    AutoMultiplexing am(limit, maxSelections);
    113118    RECORD_TIMESTAMP(start_initialize);
    114     const unsigned advances = am.initialize(function);
     119    const unsigned advances = am.initialize(function, out);
    115120    RECORD_TIMESTAMP(end_initialize);
    116121
     
    126131    am.characterize(function.getEntryBlock());
    127132    RECORD_TIMESTAMP(end_characterize);
     133
     134    out << bdd_getnodenum() << ',' << bdd_getallocnum() << '\n';
    128135
    129136    LOG("Characterize:            " << (end_characterize - start_characterize));
     
    147154        RECORD_TIMESTAMP(end_select_multiplex_sets);
    148155        LOG("SelectMultiplexSets:     " << (end_select_multiplex_sets - start_select_multiplex_sets));
     156
     157//        raw_os_ostream out(std::cerr);
     158//        PabloPrinter::print(function.getEntryBlock().statements(), out);
     159//        out.flush();
    149160
    150161        RECORD_TIMESTAMP(start_subset_constraints);
     
    173184 * the proper variable ordering.
    174185 ** ------------------------------------------------------------------------------------------------------------- */
    175 unsigned AutoMultiplexing::initialize(PabloFunction & function) {
     186unsigned AutoMultiplexing::initialize(PabloFunction & function, raw_ostream & out) {
    176187
    177188    flat_map<const PabloAST *, unsigned> map;   
     
    181192    // Scan through and collect all the advances, calls, scanthrus and matchstars ...
    182193    unsigned statements = 0, advances = 0;
    183     unsigned maxDepth = 0;
    184     mResolvedScopes.emplace(&function.getEntryBlock(), nullptr);
    185     for (Statement * stmt = function.getEntryBlock().front(); ; ) {
     194    mResolvedScopes.emplace(function.getEntryBlock(), nullptr);
     195    for (Statement * stmt = function.getEntryBlock()->front(); ; ) {
    186196        while ( stmt ) {
    187197            ++statements;
     
    189199                // Set the next statement to be the first statement of the inner scope and push the
    190200                // next statement of the current statement into the scope stack.
    191                 const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
    192                 mResolvedScopes.emplace(&nested, stmt);
     201                const PabloBlock * const nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
     202                mResolvedScopes.emplace(nested, stmt);
    193203                scope.push(stmt->getNextNode());
    194                 stmt = nested.front();
    195                 maxDepth = std::max<unsigned>(maxDepth, scope.size());
     204                stmt = nested->front();
    196205                assert (stmt);
    197206                continue;
     
    220229    }
    221230
     231    out << statements << ',' << variableCount << ',' << advances << ',';
     232
    222233    // If there are fewer than three Advances in this program, just abort. We cannot reduce it.
    223234    if (advances < 3) {
     
    241252    unsigned m = 0;
    242253
    243     for (const Statement * stmt = function.getEntryBlock().front();;) {
     254    for (const Statement * stmt = function.getEntryBlock()->front();;) {
    244255        while ( stmt ) {
    245256
     
    264275                // Set the next statement to be the first statement of the inner scope
    265276                // and push the next statement of the current statement into the stack.
    266                 const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
     277                const PabloBlock * const nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
    267278                scope.push(stmt->getNextNode());
    268                 stmt = nested.front();
     279                stmt = nested->front();
    269280                assert (stmt);
    270281                continue;
     
    321332 * Scan through the program and iteratively compute the BDDs for each statement.
    322333 ** ------------------------------------------------------------------------------------------------------------- */
    323 void AutoMultiplexing::characterize(PabloBlock & block) {
    324     for (Statement * stmt : block) {
    325         if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
    326             characterize(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
     334void AutoMultiplexing::characterize(PabloBlock * const block) {
     335    for (Statement * stmt : *block) {
     336        if (LLVM_UNLIKELY(isa<If>(stmt))) {
     337            characterize(cast<If>(stmt)->getBody());
     338        } else if (LLVM_UNLIKELY(isa<While>(stmt))) {
     339            const auto & variants = cast<While>(stmt)->getVariants();
     340            std::vector<BDD> assignments(variants.size());
     341            for (unsigned i = 0; i != variants.size(); ++i) {
     342                assignments[i] = get(variants[i]->getInitial());
     343            }
     344            characterize(cast<While>(stmt)->getBody());
     345            for (unsigned i = 0; i != variants.size(); ++i) {
     346                BDD & var = get(variants[i]->getInitial());
     347                var = bdd_addref(bdd_or(var, assignments[i]));
     348            }
    327349        } else {
    328350            mCharacterizationMap.insert(std::make_pair(stmt, characterize(stmt)));
     
    343365            continue;
    344366        }
    345         auto f = mCharacterizationMap.find(op);
    346         if (LLVM_UNLIKELY(f == mCharacterizationMap.end())) {
    347             std::string tmp;
    348             llvm::raw_string_ostream msg(tmp);
    349             msg << "AutoMultiplexing: Uncharacterized operand " << std::to_string(i);
    350             PabloPrinter::print(stmt, " of ", msg);
    351             throw std::runtime_error(msg.str());
    352         }
    353         input[i] = f->second;
     367        input[i] = get(op);
    354368    }
    355369
     
    394408inline BDD AutoMultiplexing::characterize(Advance * const adv, const BDD Ik) {
    395409
    396     assert (Ik != bdd_zero());
    397 
    398410    bdd_addref(Ik);
    399411
     
    406418        if (unconstrained[i]) continue;
    407419
     420        // If these advances are "shifting" their values by the same amount ...
    408421        const Advance * const ithAdv = std::get<0>(mAdvanceAttributes[i]);
    409         // If these advances are "shifting" their values by the same amount ...
    410422        if (adv->getOperand(1) == ithAdv->getOperand(1)) {
    411             BDD Ii = std::get<1>(mAdvanceAttributes[i]);
    412             const BDD IiIk = bdd_and(Ik, Ii);
    413             bdd_addref(IiIk);
     423            const BDD Ii = get(ithAdv->getOperand(0));
     424            const BDD IiIk = bdd_addref(bdd_and(Ii, Ik));
    414425            // Is there any satisfying truth assignment? If not, these streams are mutually exclusive.
    415426            if (bdd_satone(IiIk) == bdd_zero()) {
     
    418429.
    419430                for (auto e : make_iterator_range(in_edges(i, mSubsetGraph))) {
    420                      unconstrained[source(e, mSubsetGraph)] = true;
     431                    unconstrained[source(e, mSubsetGraph)] = true;
     432                }
     433                unconstrained[i] = true;
     434            } else if (Ii == IiIk) {
     435                // If Ii = Ii ∩ Ik then Ii ⊂ Ik. Record this in the subset graph with the arc (i, k).
     436                // Note: the AST will be modified to make these mutually exclusive if Ai and Ak end up in
     437                // the same multiplexing set.
     438                add_edge(i, k, mSubsetGraph);
     439                // If Ai ⊂ Ak and Aj ⊂ Ai, Aj ⊂ Ak.
     440                for (auto e : make_iterator_range(in_edges(i, mSubsetGraph))) {
     441                    const auto j = source(e, mSubsetGraph);
     442                    add_edge(j, k, mSubsetGraph);
     443                    unconstrained[j] = true;
    421444                }
    422445                unconstrained[i] = true;
    423446            } else if (Ik == IiIk) {
    424447                // If Ik = Ii ∩ Ik then Ik ⊂ Ii. Record this in the subset graph with the arc (k, i).
    425                 // The AST will be modified to make these mutually exclusive if Ai and Ak end up in
    426                 // the same multiplexing set.
    427448                add_edge(k, i, mSubsetGraph);
    428449                // If Ak ⊂ Ai and Ai ⊂ Aj, Ak ⊂ Aj.
     
    433454                }
    434455                unconstrained[i] = true;
    435             } else if (Ii == IiIk) {
    436                 // If Ii = Ii ∩ Ik then Ii ⊂ Ik. Record this in the subset graph with the arc (i, k).
    437                 add_edge(i, k, mSubsetGraph);
    438                 // If Ai ⊂ Ak and Aj ⊂ Ai, Aj ⊂ Ak.
    439                 for (auto e : make_iterator_range(in_edges(i, mSubsetGraph))) {
    440                     const auto j = source(e, mSubsetGraph);
    441                     add_edge(j, k, mSubsetGraph);
    442                     unconstrained[j] = true;
    443                 }
    444                 unconstrained[i] = true;
    445456            }
    446457            bdd_delref(IiIk);
     
    454465    for (unsigned i = 0; i != k; ++i) {
    455466        const Advance * const ithAdv = std::get<0>(mAdvanceAttributes[i]);
    456         auto f = mCharacterizationMap.find(ithAdv);
    457         assert (f != mCharacterizationMap.end());
    458         BDD & Ci = f->second;
    459         const BDD Vi = std::get<2>(mAdvanceAttributes[i]);
     467        BDD & Ci = get(ithAdv);
     468        const BDD Vi = std::get<1>(mAdvanceAttributes[i]);
    460469        if (unconstrained[i]) {
    461             Ck = bdd_and(Ck, bdd_not(Vi));
    462             bdd_addref(Ck);
    463             Ci = bdd_and(Ci, bdd_not(Vk));
    464             bdd_addref(Ci);
     470            Ck = bdd_addref(bdd_imp(Ck, bdd_addref(bdd_not(Vi))));
     471            Ci = bdd_addref(bdd_imp(Ci, bdd_addref(bdd_not(Vk))));
    465472            // If these Advances are mutually exclusive, in the same scope, and transitively independent,
    466473            // we safely multiplex them.
     
    468475                continue;
    469476            }
    470         } else { // TODO: investigate how to determine when it's safe to avoid computing these
    471             Ck = bdd_imp(Ck, Vi);
    472             bdd_addref(Ck);
    473             Ci = bdd_imp(Ci, Vk);
    474             bdd_addref(Ci);
    475477        }
    476478        add_edge(i, k, mConstraintGraph);
    477479    }
    478480
    479     mAdvanceAttributes.emplace_back(adv, Ik, Vk);
     481    bdd_delref(Ik);
     482
     483    mAdvanceAttributes.emplace_back(adv, Vk);
    480484
    481485    return Ck;
     
    755759        const auto v = target(*ei, mSubsetGraph);
    756760        if (in_degree(u, mMultiplexSetGraph) != 0 && in_degree(v, mMultiplexSetGraph) != 0) {
     761            assert (in_degree(u, mMultiplexSetGraph) == 1);
    757762            const auto su = source(*(in_edges(u, mMultiplexSetGraph).first), mMultiplexSetGraph);
     763            assert (in_degree(v, mMultiplexSetGraph) == 1);
    758764            const auto sv = source(*(in_edges(v, mMultiplexSetGraph).first), mMultiplexSetGraph);
    759765            if (su == sv) {
     
    769775        // we perform the minimum number of AST modifications for the given multiplexing sets.
    770776
    771         transitiveReductionOfSubsetGraph();
     777        doTransitiveReductionOfSubsetGraph();
    772778
    773779        // Afterwards modify the AST to ensure that multiplexing algorithm can ignore any subset constraints
     
    819825            Advance * const adv = input[0];
    820826            PabloBlock * const block = adv->getParent(); assert (block);
    821             PabloBuilder builder(*block);
     827            PabloBuilder builder(block);
    822828            block->setInsertPoint(block->back());
    823829
     
    903909    std::unordered_set<const PabloAST *> encountered;
    904910    std::stack<Statement *> scope;
    905     for (Statement * stmt = function.getEntryBlock().front(); ; ) { restart:
     911    for (Statement * stmt = function.getEntryBlock()->front(); ; ) { restart:
    906912        while ( stmt ) {
    907913            for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
     
    924930                // Set the next statement to be the first statement of the inner scope and push the
    925931                // next statement of the current statement into the scope stack.
    926                 const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
     932                const PabloBlock * const nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
    927933                scope.push(stmt->getNextNode());
    928                 stmt = nested.front();
     934                stmt = nested->front();
    929935                continue;
    930936            }
     
    941947
    942948/** ------------------------------------------------------------------------------------------------------------- *
    943  * @brief transitiveReductionOfSubsetGraph
    944  ** ------------------------------------------------------------------------------------------------------------- */
    945 void AutoMultiplexing::transitiveReductionOfSubsetGraph() {
     949 * @brief doTransitiveReductionOfSubsetGraph
     950 ** ------------------------------------------------------------------------------------------------------------- */
     951void AutoMultiplexing::doTransitiveReductionOfSubsetGraph() {
    946952    std::vector<SubsetGraph::vertex_descriptor> Q;
    947953    for (auto u : make_iterator_range(vertices(mSubsetGraph))) {
     
    971977}
    972978
     979/** ------------------------------------------------------------------------------------------------------------- *
     980 * @brief get
     981 ** ------------------------------------------------------------------------------------------------------------- */
     982inline BDD & AutoMultiplexing::get(const PabloAST * const expr) {
     983    auto f = mCharacterizationMap.find(expr);
     984    assert (f != mCharacterizationMap.end());
     985    return f->second;
     986}
     987
    973988} // end of namespace pablo
Note: See TracChangeset for help on using the changeset viewer.