Ignore:
Timestamp:
Jul 2, 2015, 9:28:21 AM (4 years ago)
Author:
nmedfort
Message:

Couple modifications to the UCD compiler. Splitting Multiplexing from BDD Minimization.

File:
1 edited

Legend:

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

    r4612 r4629  
    117117    LOG("Characterize:            " << (end_characterize - start_characterize));
    118118
    119     RECORD_TIMESTAMP(start_minimization);
    120     am.minimize(entry);
    121     RECORD_TIMESTAMP(end_minimization);
    122     LOG("Minimize:                " << (end_minimization - start_minimization));
    123 
    124119    RECORD_TIMESTAMP(start_shutdown);
    125120    am.shutdown();
     
    314309            continue;
    315310        }
    316         mCharacterizationMap[stmt] = characterize(stmt, true);
     311        mCharacterizationMap[stmt] = characterize(stmt);
    317312    }
    318313}
     
    321316 * @brief characterize
    322317 ** ------------------------------------------------------------------------------------------------------------- */
    323 DdNode * AutoMultiplexing::characterize(Statement * const stmt, const bool throwUncharacterizedOperandError) {
     318inline DdNode * AutoMultiplexing::characterize(Statement * const stmt) {
    324319
    325320    DdNode * bdd = nullptr;
     
    333328        auto f = mCharacterizationMap.find(op);
    334329        if (LLVM_UNLIKELY(f == mCharacterizationMap.end())) {
    335             if (throwUncharacterizedOperandError) {
    336                 std::string tmp;
    337                 llvm::raw_string_ostream msg(tmp);
    338                 msg << "Uncharacterized operand " << std::to_string(i);
    339                 PabloPrinter::print(stmt, " of ", msg);
    340                 throw std::runtime_error(msg.str());
    341             }
    342             return nullptr;
     330            std::string tmp;
     331            llvm::raw_string_ostream msg(tmp);
     332            msg << "Uncharacterized operand " << std::to_string(i);
     333            PabloPrinter::print(stmt, " of ", msg);
     334            throw std::runtime_error(msg.str());
    343335        }
    344336        input[i] = f->second;
     
    377369    }
    378370
    379     if (LLVM_UNLIKELY(noSatisfyingAssignment(bdd))) {
    380         Cudd_RecursiveDeref(mManager, bdd);
    381         bdd = Zero();
    382     }
    383 
    384371    return bdd;
    385 
    386372}
    387373
     
    490476
    491477/** ------------------------------------------------------------------------------------------------------------- *
    492  * @brief reevaluate
    493  ** ------------------------------------------------------------------------------------------------------------- */
    494 void AutoMultiplexing::reevaluate(Next * next, DdNode * value) {
    495 
    496     Assign * const initial = cast<Assign>(next->getOperand(0));
    497 
    498     if (LLVM_UNLIKELY(mCharacterizationMap[initial] == value)) {
    499         return;
    500     }
    501     mCharacterizationMap[initial] = value;
    502 
    503 
    504     std::queue<PabloAST *> Q;
    505     flat_set<PabloBlock *> within_scope;
    506 
    507     for (PabloBlock * block = next->getParent(); ;) {
    508         within_scope.insert(block);
    509         for (PabloAST * user : block->users()) {
    510             if (within_scope.insert(cast<PabloBlock>(user)).second) {
    511                 Q.push(user);
    512             }
    513         }
    514         if (Q.empty()) {
    515             break;
    516         }
    517         block = cast<PabloBlock>(Q.front());
    518         Q.pop();
    519     }
    520 
    521     std::unordered_set<PabloAST *> visited;
    522 
    523     for (Statement * current = initial; ; ) {
    524         for (PabloAST * user : current->users()) {
    525             if (Statement * stmt = dyn_cast<Statement>(user)) {
    526                 if (visited.insert(user).second && within_scope.count(stmt->getParent())) {
    527                     DdNode * bdd = characterize(stmt, false);
    528                     if (bdd && mCharacterizationMap[user] != bdd) {
    529                         mCharacterizationMap[user] = bdd;
    530                         Q.push(stmt);
    531                     }
    532                 }
    533             }
    534         }
    535         if (Q.empty()) {
    536             break;
    537         }
    538         current = cast<Statement>(Q.front());
    539         Q.pop();
    540     }
    541 
    542 }
    543 
    544 /** ------------------------------------------------------------------------------------------------------------- *
    545  * @brief minimize
    546  * @param entry the entry block of the program
    547  *
    548  * Scan through the program using the precomputed BDDs and replace any statements with equivalent BDDs with the
    549  * earlier one (assuming its in scope) and replace any contradictions with Zero.
    550  ** ------------------------------------------------------------------------------------------------------------- */
    551 inline void AutoMultiplexing::minimize(PabloBlock & entry) {
    552     SubsitutionMap baseMap;
    553     baseMap.insert(Zero(), entry.createZeroes());
    554     baseMap.insert(One(), entry.createOnes());
    555     minimize(entry, baseMap);
    556 }
    557 
    558 /** ------------------------------------------------------------------------------------------------------------- *
    559  * @brief prohibited
    560  *
    561  * If this statement is an Assign or Next node or any of its operands is a non-superfluous Assign or Next node,
    562  * then we're prohibited from minimizing this statement.
    563  ** ------------------------------------------------------------------------------------------------------------- */
    564 inline bool prohibited(const Statement * const stmt) {
    565     if (isa<Assign>(stmt) || isa<Next>(stmt)) {
    566         return true;
    567     }
    568     for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
    569         const PabloAST * const  op = stmt->getOperand(i);
    570         const Assign * const assign = dyn_cast<Assign>(op);
    571         if (LLVM_UNLIKELY((assign && !assign->superfluous()) || isa<Next>(op))) {
    572             return true;
    573         }
    574     }
    575     return false;
    576 }
    577 
    578 /** ------------------------------------------------------------------------------------------------------------- *
    579  * @brief minimize
    580  ** ------------------------------------------------------------------------------------------------------------- */
    581 void AutoMultiplexing::minimize(PabloBlock & block, SubsitutionMap & parent) {
    582     SubsitutionMap subsitutionMap(&parent);
    583     for (Statement * stmt : block) {
    584         if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
    585             // Set the next statement to be the first statement of the inner scope and push the
    586             // next statement of the current statement into the scope stack.
    587             minimize(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(), subsitutionMap);
    588             continue;
    589         }
    590 
    591         if (LLVM_UNLIKELY(prohibited(stmt))) {
    592             continue;
    593         }
    594 
    595         DdNode * bdd = mCharacterizationMap[stmt];
    596         PabloAST * replacement = subsitutionMap.test(bdd, stmt);
    597         if (LLVM_UNLIKELY(replacement != nullptr)) {
    598             if (LLVM_UNLIKELY(isa<Advance>(stmt))) {
    599                 assert (mAdvanceMap.count(stmt));
    600                 const auto k = mAdvanceMap[stmt];
    601                 const auto m = num_vertices(mConstraintGraph);
    602                 for (unsigned i = 0; i != m; ++i) {
    603                     add_edge(k, m, mConstraintGraph);
    604                 }
    605             }
    606             Cudd_RecursiveDeref(mManager, bdd);
    607             stmt->replaceWith(replacement);
    608         }
    609     }
    610 }
    611 
    612 /** ------------------------------------------------------------------------------------------------------------- *
    613478 * @brief notTransitivelyDependant
    614479 ** ------------------------------------------------------------------------------------------------------------- */
     
    1094959
    1095960                std::ostringstream prefix;
    1096                 prefix << "mux" << n << "to" << m;
     961                prefix << "mux" << n << "to" << m << '_';
    1097962                for (size_t i = 1; i <= n; ++i) {
    1098963                    if ((i & (static_cast<size_t>(1) << j)) != 0) {
    1099964                        assert (!Q.full());
    1100965                        PabloAST * tmp = V[i - 1]->getOperand(0); assert (tmp);
    1101                         prefix << '_' << V[i - 1]->getName()->to_string();
     966                        // prefix << '_' << V[i - 1]->getName()->to_string();
    1102967                        Q.push_back(tmp);
    1103968                    }
Note: See TracChangeset for help on using the changeset viewer.