Ignore:
Timestamp:
Jul 23, 2015, 4:47:59 PM (4 years ago)
Author:
nmedfort
Message:

Temporary check in.

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

Legend:

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

    r4686 r4692  
    102102
    103103    std::random_device rd;
    104     const auto seed = rd();
     104    const auto seed = rd(); // 83234827342;
    105105    RNG rng(seed);
    106106
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_bddminimization.cpp

    r4656 r4692  
    5151                " (" << (((double)num_edges(G)) / ((double)(num_vertices(G) * (num_vertices(G) - 1) / 2))) << ')')
    5252
    53 unsigned __count_advances(const PabloBlock & entry) {
    54 
    55     std::stack<const Statement *> scope;
    56     unsigned advances = 0;
    57 
    58     // Scan through and collect all the advances, calls, scanthrus and matchstars ...
    59     for (const Statement * stmt = entry.front(); ; ) {
    60         while ( stmt ) {
    61             if (isa<Advance>(stmt)) {
    62                 ++advances;
    63             }
    64             else if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
    65                 // Set the next statement to be the first statement of the inner scope and push the
    66                 // next statement of the current statement into the scope stack.
    67                 const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
    68                 scope.push(stmt->getNextNode());
    69                 stmt = nested.front();
    70                 assert (stmt);
    71                 continue;
    72             }
    73             stmt = stmt->getNextNode();
    74         }
    75         if (scope.empty()) {
    76             break;
    77         }
    78         stmt = scope.top();
    79         scope.pop();
    80     }
    81     return advances;
    82 }
    83 
    84 #define LOG_NUMBER_OF_ADVANCES(entry) LOG("|Advances|=" << __count_advances(entry))
    8553
    8654#else
     
    9462namespace pablo {
    9563
    96 bool BDDMinimizationPass::optimize(const std::vector<Var *> & input, PabloBlock & entry) {
    97 
    98     std::random_device rd;
    99     const auto seed = rd();
    100     RNG rng(seed);
    101 
    102     LOG("Seed:                    " << seed);
     64bool BDDMinimizationPass::optimize(PabloFunction & function) {
    10365
    10466    BDDMinimizationPass am;
    10567    RECORD_TIMESTAMP(start_initialize);
    106     am.initialize(input, entry);
     68    am.initialize(function);
    10769    RECORD_TIMESTAMP(end_initialize);
    10870
    10971    LOG("Initialize:              " << (end_initialize - start_initialize));
    110 
    111     LOG_NUMBER_OF_ADVANCES(entry);
    11272
    11373    RECORD_TIMESTAMP(start_characterize);
     
    11878
    11979    RECORD_TIMESTAMP(start_minimization);
    120     am.minimize(entry);
     80    am.eliminateLogicallyEquivalentStatements(entry);
     81    RECORD_TIMESTAMP(end_minimization);
     82    LOG("Minimize:                " << (end_minimization - start_minimization));
     83
     84    RECORD_TIMESTAMP(start_minimization);
     85    am.simplify(entry);
    12186    RECORD_TIMESTAMP(end_minimization);
    12287    LOG("Minimize:                " << (end_minimization - start_minimization));
     
    12792    LOG("Shutdown:                " << (end_shutdown - start_shutdown));
    12893
    129     RECORD_TIMESTAMP(start_create_multiplex_graph);
    130     const bool multiplex = am.generateMultiplexSets(rng, 1);
    131     RECORD_TIMESTAMP(end_create_multiplex_graph);
    132     LOG("GenerateMultiplexSets:   " << (end_create_multiplex_graph - start_create_multiplex_graph));
    133 
    134     if (multiplex) {
    135 
    136         RECORD_TIMESTAMP(start_select_multiplex_sets);
    137         am.selectMultiplexSets(rng);
    138         RECORD_TIMESTAMP(end_select_multiplex_sets);
    139         LOG("SelectMultiplexSets:     " << (end_select_multiplex_sets - start_select_multiplex_sets));
    140 
    141         RECORD_TIMESTAMP(start_subset_constraints);
    142         am.applySubsetConstraints();
    143         RECORD_TIMESTAMP(end_subset_constraints);
    144         LOG("ApplySubsetConstraints:  " << (end_subset_constraints - start_subset_constraints));
    145 
    146         RECORD_TIMESTAMP(start_select_independent_sets);
    147         am.multiplexSelectedIndependentSets();
    148         RECORD_TIMESTAMP(end_select_independent_sets);
    149         LOG("MultiplexSelectedSets:   " << (end_select_independent_sets - start_select_independent_sets));
    150 
    151         RECORD_TIMESTAMP(start_topological_sort);
    152         am.topologicalSort(entry);
    153         RECORD_TIMESTAMP(end_topological_sort);
    154         LOG("TopologicalSort:         " << (end_topological_sort - start_topological_sort));
    155     }
    156 
    157     LOG_NUMBER_OF_ADVANCES(entry);
     94
    15895
    15996    return multiplex;
     
    168105 * the proper variable ordering.
    169106 ** ------------------------------------------------------------------------------------------------------------- */
    170 void BDDMinimizationPass::initialize(const std::vector<Var *> & vars, PabloBlock & entry) {
    171 
    172     flat_map<const PabloAST *, unsigned> map;
     107void BDDMinimizationPass::initialize(PabloFunction &function) {
     108
    173109    std::stack<Statement *> scope;
    174     unsigned complexStatements = 0; // number of statements that cannot always be categorized without generating a new variable
    175 
    176     // Scan through and collect all the advances, calls, scanthrus and matchstars ...
    177     unsigned n = 0, m = 0;
    178     for (Statement * stmt = entry.front(); ; ) {
     110    unsigned variableCount = 0; // number of statements that cannot always be categorized without generating a new variable
     111
     112    for (Statement * stmt = function.getEntryBlock().front(); ; ) {
    179113        while ( stmt ) {
    180             ++n;
     114
    181115            if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
    182116                // Set the next statement to be the first statement of the inner scope and push the
     
    189123            }
    190124
    191             assert ("Run the Simplifer pass prior to this!" && (stmt->getNumUses() != 0 || (isa<Assign>(stmt) ? !cast<Assign>(stmt)->superfluous() : false)));
    192 
    193125            switch (stmt->getClassTypeId()) {
    194126                case PabloAST::ClassTypeId::Advance:
    195                     mAdvanceMap.emplace(stmt, m);
    196                     map.emplace(stmt, m++);
    197127                case PabloAST::ClassTypeId::Call:
    198128                case PabloAST::ClassTypeId::ScanThru:
    199129                case PabloAST::ClassTypeId::MatchStar:
    200                     complexStatements++;
     130                    variableCount++;
    201131                    break;
    202132                default:
     
    212142    }
    213143
    214     // Create the transitive closure matrix of graph. From this we'll construct
    215     // two graphs restricted to the relationships between advances. The first will
    216     // be a path graph, which is used to bypass testing for mutual exclusivity of
    217     // advances that cannot be multiplexed. The second is a transitive reduction
    218     // of that graph, which forms the basis of our constraint graph when deciding
    219     // which advances ought to be multiplexed.
    220 
    221     matrix<bool> G(n, m); // Let G be a matrix with n rows of m (Advance) elements
    222     G.clear();
    223     for (unsigned i = 0; i != m; ++i) {
    224         G(i, i) = true;
    225     }
    226 
    227     n = m;
    228     m = 0;
    229 
    230     const Statement * stmt = entry.front();
    231     for (;;) {
    232         while ( stmt ) {
    233 
    234             unsigned u;
    235             if (isa<Advance>(stmt)) {
    236                 assert (mAdvanceMap.count(stmt) && mAdvanceMap[stmt] == m);
    237                 u = m++;
    238             }
    239             else {
    240                 u = n++;
    241                 map.emplace(stmt, u);
    242             }
    243 
    244             for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
    245                 const PabloAST * const op = stmt->getOperand(i);
    246                 if (LLVM_LIKELY(isa<Statement>(op))) {
    247                     const unsigned v = map[op];
    248                     for (unsigned w = 0; w != m; ++w) {
    249                         G(u, w) |= G(v, w);
    250                     }
    251                 }
    252             }
    253             if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
    254                 // Set the next statement to be the first statement of the inner scope
    255                 // and push the next statement of the current statement into the stack.
    256                 const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
    257                 scope.push(stmt->getNextNode());
    258                 stmt = nested.front();
    259                 assert (stmt);
    260                 continue;
    261             }
    262             stmt = stmt->getNextNode();
    263         }
    264         if (scope.empty()) {
    265             break;
    266         }
    267         stmt = scope.top();
    268         scope.pop();
    269     }
    270 
    271     // Record the path / base constraint graph after removing any reflexive-loops.
    272     // Since G is a use-def graph and we want our constraint graph to be a def-use graph,
    273     // reverse the edges as we're writing them to obtain the transposed graph.
    274     mConstraintGraph = ConstraintGraph(m);
    275     mSubsetGraph = SubsetGraph(m);
    276 
    277     for (unsigned i = 0; i != m; ++i) {
    278         G(i, i) = false;
    279         for (unsigned j = 0; j != m; ++j) {
    280             if (G(i, j)) {
    281                 add_edge(j, i, mConstraintGraph);
    282             }
    283         }
    284     }
    285 
    286144    // Initialize the BDD engine ...
    287     mManager = Cudd_Init((complexStatements + vars.size()), 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0);
     145    mManager = Cudd_Init((variableCount + function.getNumOfParameters()), 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0);
    288146    Cudd_AutodynDisable(mManager);
    289147
    290148    // Map the predefined 0/1 entries
    291     mCharacterizationMap[entry.createZeroes()] = Zero();
    292     mCharacterizationMap[entry.createOnes()] = One();
     149    mCharacterizationMap[function.getEntryBlock().createZeroes()] = Zero();
     150    mCharacterizationMap[function.getEntryBlock().createOnes()] = One();
    293151
    294152    // Order the variables so the input Vars are pushed to the end; they ought to
    295153    // be the most complex to resolve.
    296     unsigned i = complexStatements;
    297     for (const Var * var : vars) {
    298         mCharacterizationMap[var] = Cudd_bddIthVar(mManager, i++);
     154    for (auto i = 0; i != function.getNumOfParameters(); ++i) {
     155        mCharacterizationMap[function.getParameter(i)] = Cudd_bddIthVar(mManager, variableCount++);
    299156    }
    300157}
     
    306163 * Scan through the program and iteratively compute the BDDs for each statement.
    307164 ** ------------------------------------------------------------------------------------------------------------- */
    308 void BDDMinimizationPass::characterize(PabloBlock & block) {
     165void BDDMinimizationPass::characterize(const PabloBlock & block) {
    309166    for (Statement * stmt : block) {
    310167        if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
     
    314171            continue;
    315172        }
    316         mCharacterizationMap[stmt] = characterize(stmt, true);
     173        mCharacterizationMap[stmt] =  characterize(stmt);
    317174    }
    318175}
     
    321178 * @brief characterize
    322179 ** ------------------------------------------------------------------------------------------------------------- */
    323 DdNode * BDDMinimizationPass::characterize(Statement * const stmt, const bool throwUncharacterizedOperandError) {
     180inline DdNode * BDDMinimizationPass::characterize(const Statement * const stmt) {
    324181
    325182    DdNode * bdd = nullptr;
     
    331188            continue;
    332189        }
    333         auto f = mCharacterizationMap.find(op);
    334         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;
    343         }
    344         input[i] = f->second;
     190        input[i] = mCharacterizationMap[op];
    345191    }
    346192
     
    353199        case PabloAST::ClassTypeId::Next:
    354200        case PabloAST::ClassTypeId::Or:
    355             return Or(input[0], input[1]);
     201            bdd = Or(input[0], input[1]);
     202            break;
    356203        case PabloAST::ClassTypeId::Xor:
    357             return Xor(input[0], input[1]);
     204            bdd = Xor(input[0], input[1]);
     205            break;
    358206        case PabloAST::ClassTypeId::Not:
    359             return Not(input[0]);
     207            bdd = Not(input[0]);
     208            break;
    360209        case PabloAST::ClassTypeId::Sel:
    361210            bdd = Ite(input[0], input[1], input[2]);
    362211            break;
    363212        case PabloAST::ClassTypeId::ScanThru:
    364             // It may be possible use "Not(input[1])" for ScanThrus if we rule out the possibility
    365             // of a contradition being erroneously calculated later. An example of this
    366             // would be ¬(ScanThru(c,m) √ m)
    367213        case PabloAST::ClassTypeId::MatchStar:
    368             if (LLVM_UNLIKELY(isZero(input[0]) || isZero(input[1]))) {
    369                 return Zero();
    370             }
    371214        case PabloAST::ClassTypeId::Call:
     215        case PabloAST::ClassTypeId::Advance:
    372216            return NewVar();
    373         case PabloAST::ClassTypeId::Advance:
    374             return characterize(cast<Advance>(stmt), input[0]);
    375217        default:
    376218            throw std::runtime_error("Unexpected statement type " + stmt->getName()->to_string());
     
    387229
    388230/** ------------------------------------------------------------------------------------------------------------- *
    389  * @brief characterize
    390  ** ------------------------------------------------------------------------------------------------------------- */
    391 inline DdNode * BDDMinimizationPass::characterize(Advance * adv, DdNode * input) {
    392     DdNode * Ik, * Ck, * Nk;
    393     if (LLVM_UNLIKELY(isZero(input))) {
    394         Ik = Ck = Nk = Zero();
    395     }
    396     else {
    397 
    398         Ik = input;
    399         Ck = NewVar();
    400         Nk = Not(Ck);
    401 
    402         assert (mAdvanceMap.count(adv));
    403 
    404         const auto k = mAdvanceMap[adv];
    405 
    406         std::vector<bool> unconstrained(k , false);
    407 
    408         // Can we use a transposed copy of the subset graph to determine an ordering of variables?
    409         for (unsigned i = 0; i != k; ++i) {
    410             // Have we already proven that these are unconstrained by the subset relationships?
    411             if (unconstrained[i]) continue;
    412             Advance * tmp = std::get<0>(mAdvance[i]);
    413             // If these advances are "shifting" their values by the same amount and aren't transitively dependant ...
    414             if ((adv->getOperand(1) == tmp->getOperand(1)) && (notTransitivelyDependant(i, k))) {
    415                 DdNode * Ii = std::get<1>(mAdvance[i]);
    416                 DdNode * Ni = std::get<2>(mAdvance[i]);
    417                 // TODO: test both Cudd_And and Cudd_bddIntersect to see which is faster
    418                 DdNode * const IiIk = Intersect(Ik, Ii);
    419                 // Is there any satisfying truth assignment? If not, these streams are mutually exclusive.
    420                 if (noSatisfyingAssignment(IiIk)) {
    421                     assert (mCharacterizationMap.count(tmp));
    422                     DdNode *& Ci = mCharacterizationMap[tmp];
    423                     // Mark the i-th and k-th Advances as being mutually exclusive
    424                     Ck = And(Ck, Ni);
    425                     Ci = And(Ci, Nk);
    426                     // If Ai ∩ Ak = âˆ
    427  and Aj ⊂ Ai, Aj ∩ Ak = âˆ
    428 .
    429                     graph_traits<SubsetGraph>::in_edge_iterator ei, ei_end;
    430                     for (std::tie(ei, ei_end) = in_edges(i, mSubsetGraph); ei != ei_end; ++ei) {
    431                         const auto j = source(*ei, mSubsetGraph);
    432                         if (notTransitivelyDependant(k, j)) {
    433                             Advance * adv = std::get<0>(mAdvance[j]);
    434                             assert (mCharacterizationMap.count(adv));
    435                             DdNode *& Cj = mCharacterizationMap[adv];
    436                             DdNode * Nj = std::get<2>(mAdvance[j]);
    437                             // Mark the i-th and j-th Advances as being mutually exclusive
    438                             Ck = And(Ck, Nj);
    439                             Cj = And(Cj, Nk);
    440                             unconstrained[j] = true;
    441                         }
    442                     }
    443                     unconstrained[i] = true;
    444                 }
    445                 else if (Ik == IiIk) {
    446                     // If Ik = Ii ∩ Ik then Ik ⊂ Ii. Record this in the subset graph with the arc (k,i).
    447                     // These edges will be moved into the multiplex set graph if Ai and Ak happen to be
    448                     // in the same mutually exclusive set.
    449                     add_edge(k, i, mSubsetGraph);
    450                     // If Ak ⊂ Ai and Ai ⊂ Aj, Ak ⊂ Aj.
    451                     graph_traits<SubsetGraph>::out_edge_iterator ei, ei_end;
    452                     for (std::tie(ei, ei_end) = out_edges(i, mSubsetGraph); ei != ei_end; ++ei) {
    453                         const auto j = target(*ei, mSubsetGraph);
    454                         add_edge(k, j, mSubsetGraph);
    455                         unconstrained[j] = true;
    456                     }
    457                     unconstrained[i] = true;
    458                 }
    459                 else if (Ii == IiIk) {
    460                     // If Ii = Ii ∩ Ik then Ii ⊂ Ik. Record this in the subset graph with the arc (i,k).
    461                     add_edge(i, k, mSubsetGraph);
    462                     // If Ai ⊂ Ak and Aj ⊂ Ai, Aj ⊂ Ak.
    463                     graph_traits<SubsetGraph>::in_edge_iterator ei, ei_end;
    464                     for (std::tie(ei, ei_end) = in_edges(i, mSubsetGraph); ei != ei_end; ++ei) {
    465                         const auto j = source(*ei, mSubsetGraph);
    466                         add_edge(j, k, mSubsetGraph);
    467                         unconstrained[j] = true;
    468                     }
    469                     unconstrained[i] = true;
    470                 }
    471                 Cudd_RecursiveDeref(mManager, IiIk);
    472             }
    473         }
    474 
    475         for (unsigned i = 0; i != k; ++i) {
    476             const Advance * const tmp = std::get<0>(mAdvance[i]);
    477             // Even if these Advances are mutually exclusive, they must be in the same scope or they cannot be safely multiplexed.
    478             if (!unconstrained[i] || (adv->getParent() != tmp->getParent())) {
    479                 // We want the constraint graph to be acyclic; since the dependencies are already in topological order,
    480                 // adding an arc from a lesser to greater numbered vertex won't induce a cycle.
    481                 add_edge(i, k, mConstraintGraph);
    482             }
    483         }
    484     }
    485 
    486     mAdvance.emplace_back(adv, Ik, Nk);
    487 
    488     return Ck;
    489 }
    490 
    491 /** ------------------------------------------------------------------------------------------------------------- *
    492  * @brief reevaluate
    493  ** ------------------------------------------------------------------------------------------------------------- */
    494 void BDDMinimizationPass::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
     231 * @brief eliminateLogicallyEquivalentStatements
    546232 * @param entry the entry block of the program
    547233 *
     
    549235 * earlier one (assuming its in scope) and replace any contradictions with Zero.
    550236 ** ------------------------------------------------------------------------------------------------------------- */
    551 inline void BDDMinimizationPass::minimize(PabloBlock & entry) {
     237inline void BDDMinimizationPass::eliminateLogicallyEquivalentStatements(PabloBlock & entry) {
    552238    SubsitutionMap baseMap;
    553239    baseMap.insert(Zero(), entry.createZeroes());
    554240    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 BDDMinimizationPass::minimize(PabloBlock & block, SubsitutionMap & parent) {
     241    eliminateLogicallyEquivalentStatements(entry, baseMap);
     242}
     243
     244/** ------------------------------------------------------------------------------------------------------------- *
     245 * @brief eliminateLogicallyEquivalentStatements
     246 ** ------------------------------------------------------------------------------------------------------------- */
     247void BDDMinimizationPass::eliminateLogicallyEquivalentStatements(PabloBlock & block, SubsitutionMap & parent) {
    582248    SubsitutionMap subsitutionMap(&parent);
    583     for (Statement * stmt : block) {
     249    Statement * stmt = block.front();
     250    while (stmt) {
    584251        if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
    585252            // Set the next statement to be the first statement of the inner scope and push the
    586253            // next statement of the current statement into the scope stack.
    587             minimize(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(), subsitutionMap);
     254            eliminateLogicallyEquivalentStatements(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(), subsitutionMap);
    588255            continue;
    589256        }
    590257
    591         if (LLVM_UNLIKELY(prohibited(stmt))) {
     258        if (LLVM_UNLIKELY(isa<Assign>(stmt) || isa<Next>(stmt))) {
    592259            continue;
    593260        }
    594261
    595262        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             }
     263        PabloAST * replacement = subsitutionMap[bdd];
     264        if (replacement) {
    606265            Cudd_RecursiveDeref(mManager, bdd);
    607             stmt->replaceWith(replacement);
    608         }
    609     }
    610 }
    611 
    612 /** ------------------------------------------------------------------------------------------------------------- *
    613  * @brief notTransitivelyDependant
    614  ** ------------------------------------------------------------------------------------------------------------- */
    615 inline bool BDDMinimizationPass::notTransitivelyDependant(const ConstraintVertex i, const ConstraintVertex j) const {
    616     assert (i < num_vertices(mConstraintGraph) && j < num_vertices(mConstraintGraph));
    617     return (mConstraintGraph.get_edge(i, j) == 0);
     266            stmt = stmt->replaceWith(replacement, false, true);
     267        }
     268        else {
     269            stmt = stmt->getNextNode();
     270        }
     271    }
     272}
     273
     274/** ------------------------------------------------------------------------------------------------------------- *
     275 * @brief simplify
     276 ** ------------------------------------------------------------------------------------------------------------- */
     277PabloAST * BDDMinimizationPass::simplify(DdNode * bdd) const {
     278
     279    CUDD_VALUE_TYPE value;
     280    int * cube = nullptr;
     281
     282    DdGen * gen = Cudd_FirstCube(mManager, bdd, &cube, &value);
     283    while (!Cudd_IsGenEmpty(gen)) {
     284        // cube[0 ... n - 1] = { 0 : false, 1: true, 2: don't care }
     285
     286
     287
     288
     289        Cudd_NextCube(gen, &cube, &value);
     290    }
     291    Cudd_GenFree(gen);
     292
    618293}
    619294
     
    679354}
    680355
    681 /** ------------------------------------------------------------------------------------------------------------- *
    682  * @brief generateMultiplexSets
    683  * @param RNG random number generator
    684  ** ------------------------------------------------------------------------------------------------------------- */
    685 bool BDDMinimizationPass::generateMultiplexSets(RNG & rng, unsigned k) {
    686 
    687     using vertex_t = ConstraintGraph::vertex_descriptor;
    688     using degree_t = graph_traits<ConstraintGraph>::degree_size_type;
    689 
    690     // What if we generated a "constraint free" graph instead? By taking each connected component of it
    691     // and computing the complement of it (with the same lesser to greater index ordering), we should
    692     // have the same problem here but decomposed into subgraphs.
    693 
    694     IndependentSet M, N;
    695     auto remainingVerticies = num_vertices(mConstraintGraph);
    696     std::vector<degree_t> D(remainingVerticies);
    697     M.reserve(15);
    698     N.reserve(15);
    699 
    700     mMultiplexSetGraph = MultiplexSetGraph(remainingVerticies);
    701 
    702     while (k) {
    703 
    704         // Push all source nodes into the new independent set N
    705         for (auto v : make_iterator_range(vertices(mConstraintGraph))) {
    706             const auto d = in_degree(v, mConstraintGraph);
    707             D[v] = d;
    708             if (d == 0) {
    709                 N.push_back(v);
    710             }
    711         }
    712 
    713         for (;;) {
    714 
    715             addMultiplexSet(N, M);
    716 
    717             if (remainingVerticies == 0) {
    718                 break;
    719             }
    720 
    721             assert (N.size() > 0);
    722 
    723             // Move all of our "newly" uncovered vertices in S into the "known" set M. By always choosing
    724             // at least one element from N, this will prevent us from adding the same multiplexing set again.
    725             M.insert(M.end(), N.begin(), N.end()); N.clear();
    726 
    727             do {
    728                 // Randomly choose a vertex in S and discard it.
    729                 assert (!M.empty());
    730                 const auto i = M.begin() + IntDistribution(0, M.size() - 1)(rng);
    731                 const vertex_t u = *i;
    732                 M.erase(i);
    733                 --remainingVerticies;
    734                 for (auto e : make_iterator_range(out_edges(u, mConstraintGraph))) {
    735                     const vertex_t v = target(e, mConstraintGraph);
    736                     if ((--D[v]) == 0) {
    737                         N.push_back(v);
    738                     }
    739                 }
    740             }
    741             while (N.empty() && remainingVerticies != 0);
    742         }
    743 
    744         if (--k == 0) {
    745             break;
    746         }
    747 
    748         N.clear();
    749         M.clear();
    750     }
    751 
    752     return num_vertices(mMultiplexSetGraph) > num_vertices(mConstraintGraph);
    753 }
    754 
    755 /** ------------------------------------------------------------------------------------------------------------- *
    756  * @brief addMultiplexSet
    757  * @param N an independent set
    758  * @param M an independent set
    759  ** ------------------------------------------------------------------------------------------------------------- */
    760 inline void BDDMinimizationPass::addMultiplexSet(const IndependentSet & N, const IndependentSet & M) {
    761 
    762     // At this stage, the multiplex set graph is a directed bipartite graph that is used to show relationships
    763     // between the "set vertex" and its members. We obtain these from "generateMultiplexSets".
    764 
    765     if ((N.size() + M.size()) >= 3) {
    766         const auto u = add_vertex(mMultiplexSetGraph);
    767         for (const auto x : N) {
    768             add_edge(u, x, mMultiplexSetGraph);
    769         }
    770         for (const auto y : M) {
    771             add_edge(u, y, mMultiplexSetGraph);
    772         }
    773     }
    774 }
    775 
    776 /** ------------------------------------------------------------------------------------------------------------- *
    777  * @brief is_power_of_2
    778  * @param n an integer
    779  ** ------------------------------------------------------------------------------------------------------------- */
    780 static inline bool is_power_of_2(const size_t n) {
    781     return ((n & (n - 1)) == 0) ;
    782 }
    783 
    784 /** ------------------------------------------------------------------------------------------------------------- *
    785  * @brief log2_plus_one
    786  ** ------------------------------------------------------------------------------------------------------------- */
    787 static inline size_t log2_plus_one(const size_t n) {
    788     return std::log2<size_t>(n) + 1; // use a faster builtin function for this?
    789 }
    790 
    791 /** ------------------------------------------------------------------------------------------------------------- *
    792  * @brief selectMultiplexSets
    793  * @param RNG random number generator
    794  *
    795  * This algorithm is simply computes a greedy set cover. We want an exact max-weight set cover but can generate new
    796  * sets by taking a subset of any existing set. With a few modifications, the greedy approach seems to work well
    797  * enough but more analysis is needed.
    798  ** ------------------------------------------------------------------------------------------------------------- */
    799 void BDDMinimizationPass::selectMultiplexSets(RNG &) {
    800 
    801 
    802     using OutEdgeIterator = graph_traits<MultiplexSetGraph>::out_edge_iterator;
    803     using InEdgeIterator = graph_traits<MultiplexSetGraph>::in_edge_iterator;
    804     using degree_t = MultiplexSetGraph::degree_size_type;
    805     using vertex_t = MultiplexSetGraph::vertex_descriptor;
    806 
    807     const size_t m = num_vertices(mConstraintGraph);
    808     const size_t n = num_vertices(mMultiplexSetGraph) - m;
    809 
    810     std::vector<degree_t> remaining(n, 0);
    811     std::vector<vertex_t> chosen_set(m, 0);
    812 
    813     for (unsigned i = 0; i != n; ++i) {
    814         remaining[i] = out_degree(i + m, mMultiplexSetGraph);
    815     }
    816 
    817     for (;;) {
    818 
    819         // Choose the set with the greatest number of vertices not already included in some other set.
    820         vertex_t k = 0;
    821         degree_t w = 0;
    822         for (vertex_t i = 0; i != n; ++i) {
    823             const degree_t r = remaining[i];
    824             if (w < r) {
    825                 k = i;
    826                 w = r;
    827             }
    828         }
    829 
    830         // Multiplexing requires at least 3 elements; if the best set contains fewer than 3, abort.
    831         if (w < 3) {
    832             break;
    833         }
    834 
    835         OutEdgeIterator ei, ei_end;
    836         for (std::tie(ei, ei_end) = out_edges(k + m, mMultiplexSetGraph); ei != ei_end; ++ei) {
    837             const vertex_t j = target(*ei, mMultiplexSetGraph);
    838             if (chosen_set[j] == 0) {
    839                 chosen_set[j] = (k + m);
    840                 InEdgeIterator ej, ej_end;
    841                 for (std::tie(ej, ej_end) = in_edges(j, mMultiplexSetGraph); ej != ej_end; ++ej) {
    842                     remaining[source(*ej, mMultiplexSetGraph) - m]--;
    843                 }
    844             }
    845         }
    846 
    847         assert (remaining[k] == 0);
    848 
    849         // If this contains 2^n elements for any n, discard the member that is most likely to be added
    850         // to some future set.
    851         if (is_power_of_2(w)) {
    852             vertex_t j = 0;
    853             degree_t w = 0;
    854             for (vertex_t i = 0; i != m; ++i) {
    855                 if (chosen_set[i] == (k + m)) {
    856                     InEdgeIterator ej, ej_end;
    857                     degree_t r = 1;
    858                     for (std::tie(ej, ej_end) = in_edges(i, mMultiplexSetGraph); ej != ej_end; ++ej) {
    859                         // strongly prefer adding weight to unvisited sets that have more remaining vertices
    860                         r += std::pow(remaining[source(*ej, mMultiplexSetGraph) - m], 2);
    861                     }
    862                     if (w < r) {
    863                         j = i;
    864                         w = r;
    865                     }
    866                 }
    867             }
    868             assert (w > 0);
    869             chosen_set[j] = 0;
    870             InEdgeIterator ej, ej_end;
    871             for (std::tie(ej, ej_end) = in_edges(j, mMultiplexSetGraph); ej != ej_end; ++ej) {
    872                 remaining[source(*ej, mMultiplexSetGraph) - m]++;
    873             }
    874         }
    875     }
    876 
    877     for (unsigned i = 0; i != m; ++i) {
    878         InEdgeIterator ei, ei_end;
    879         std::tie(ei, ei_end) = in_edges(i, mMultiplexSetGraph);
    880         for (auto next = ei; ei != ei_end; ei = next) {
    881             ++next;
    882             if (source(*ei, mMultiplexSetGraph) != chosen_set[i]) {
    883                 remove_edge(*ei, mMultiplexSetGraph);
    884             }
    885         }
    886     }
    887 
    888     #ifndef NDEBUG
    889     for (unsigned i = 0; i != m; ++i) {
    890         assert (in_degree(i, mMultiplexSetGraph) <= 1);
    891     }
    892     for (unsigned i = m; i != (m + n); ++i) {
    893         assert (out_degree(i, mMultiplexSetGraph) == 0 || out_degree(i, mMultiplexSetGraph) >= 3);
    894     }
    895     #endif
    896 }
    897 
    898 /** ------------------------------------------------------------------------------------------------------------- *
    899  * @brief choose
    900  ** ------------------------------------------------------------------------------------------------------------- */
    901 
    902 inline Statement * choose(PabloAST * x, PabloAST * y, Statement * z) {
    903     return isa<Statement>(x) ? cast<Statement>(x) : (isa<Statement>(y) ? cast<Statement>(y) : z);
    904 }
    905 
    906 /** ------------------------------------------------------------------------------------------------------------- *
    907  * @brief applySubsetConstraints
    908  ** ------------------------------------------------------------------------------------------------------------- */
    909 void BDDMinimizationPass::applySubsetConstraints() {
    910 
    911     // When entering thus function, the multiplex set graph M is a bipartite DAG with edges denoting the set
    912     // relationships of our independent sets.
    913     const unsigned m = num_vertices(mConstraintGraph);
    914     const unsigned n = num_vertices(mMultiplexSetGraph);
    915 
    916     // Add in any edges from our subset constraints to M that are within the same set.
    917     bool hasSubsetConstraint = false;
    918 
    919     graph_traits<SubsetGraph>::edge_iterator ei, ei_end;
    920     for (std::tie(ei, ei_end) = edges(mSubsetGraph); ei != ei_end; ++ei) {
    921         const auto u = source(*ei, mSubsetGraph);
    922         const auto v = target(*ei, mSubsetGraph);
    923         graph_traits<MultiplexSetGraph>::in_edge_iterator ej, ej_end;
    924         // If both the source and target of ei are adjacent to the same vertex, that vertex must be the
    925         // "set vertex". Add the edge between the vertices.
    926         for (std::tie(ej, ej_end) = in_edges(u, mMultiplexSetGraph); ej != ej_end; ++ej) {
    927             auto w = target(*ej, mMultiplexSetGraph);
    928             // Only check (v, w) if w is a "set vertex".
    929             if (w >= (n - m) && edge(v, w, mMultiplexSetGraph).second) {
    930                 add_edge(u, v, mMultiplexSetGraph);
    931                 hasSubsetConstraint = true;
    932             }
    933         }
    934     }
    935 
    936     if (LLVM_UNLIKELY(hasSubsetConstraint)) {
    937         // At this point, M is still a DAG but no longer bipartite. We're going to scan through the set vertices
    938         // in M, and use a DFS to scan through M and eliminate any subset relationships in the AST.
    939         // That way, "multiplexSelectedIndependentSets" only needs to consider muxing and demuxing of the streams.
    940 
    941         std::vector<MultiplexSetGraph::vertex_descriptor> V;
    942         std::stack<MultiplexSetGraph::vertex_descriptor> S;
    943         std::queue<PabloAST *> Q;
    944         BitVector D(n - m, 0);
    945 
    946         for (auto i = m; i != n; ++i) {
    947             graph_traits<MultiplexSetGraph>::out_edge_iterator ei, ei_end;
    948             // For each member of a "set vertex" ...
    949             std::tie(ei, ei_end) = out_edges(i, mMultiplexSetGraph);
    950             for (; ei != ei_end; ++ei) {
    951                 const auto s = source(*ei, mMultiplexSetGraph);
    952                 if (out_degree(s, mMultiplexSetGraph) != 0) {
    953                     // First scan through the subgraph of vertices in M dominated by s and build up the set T,
    954                     // consisting of all sinks w.r.t. vertex s.
    955                     auto u = s;
    956                     for (;;) {
    957                         graph_traits<MultiplexSetGraph>::out_edge_iterator ej, ej_end;
    958                         for (std::tie(ej, ej_end) = out_edges(u, mMultiplexSetGraph); ej != ej_end; ++ej) {
    959                             auto v = target(*ej, mMultiplexSetGraph);
    960                             if (D.test(v)) {
    961                                 continue;
    962                             }
    963                             D.set(v);
    964                             if (out_degree(v, mMultiplexSetGraph) == 0) {
    965                                 V.push_back(v);
    966                             }
    967                             else {
    968                                 S.push(v);
    969                             }
    970                         }
    971                         if (S.empty()) {
    972                             break;
    973                         }
    974                         u = S.top();
    975                         S.pop();
    976                     }
    977                     D.clear();
    978                     // Now in order for these advances to be mutually exclusive, the input to A_s must be masked
    979                     // with the complement of each advance indicated by V.
    980 
    981                     Advance * adv = std::get<0>(mAdvance[s]);
    982                     PabloBlock * pb = adv->getParent();
    983 
    984                     for (auto i : V) {
    985                         Q.push(std::get<0>(mAdvance[i])->getOperand(0));
    986                     }
    987                     while (Q.size() > 1) {
    988                         PabloAST * a1 = Q.front(); Q.pop();
    989                         PabloAST * a2 = Q.front(); Q.pop();
    990                         pb->setInsertPoint(cast<Statement>(a2));
    991                         Q.push(pb->createOr(a1, a2));
    992                     }
    993                     assert (Q.size() == 1);
    994 
    995                     PabloAST * const mask = pb->createNot(Q.front()); Q.pop();
    996                     adv->setOperand(0, pb->createAnd(adv->getOperand(0), mask, "subset_in"));
    997 
    998                     // Similar to the above, we're going to OR together the result of each advance,
    999                     // including s. This will restore the advanced variable back to its original state.
    1000 
    1001                     // Gather the original users to this advance. We'll be manipulating it shortly.
    1002                     Statement::Vector U(adv->users());
    1003 
    1004                     // Add s to V and sort the list; it'll be closer to being in topological order.
    1005                     V.push_back(s);
    1006                     std::sort(V.begin(), V.end());
    1007                     for (auto i : V) {
    1008                         Q.push(std::get<0>(mAdvance[i]));
    1009                     }
    1010                     while (Q.size() > 1) {
    1011                         PabloAST * a1 = Q.front(); Q.pop();
    1012                         PabloAST * a2 = Q.front(); Q.pop();
    1013                         pb->setInsertPoint(choose(a2, a1, adv));
    1014                         Q.push(pb->createOr(a1, a2));
    1015                     }
    1016                     assert (Q.size() == 1);
    1017 
    1018                     PabloAST * const input = Q.front(); Q.pop();
    1019                     for (PabloAST * use : U) {
    1020                         if (LLVM_LIKELY(isa<Statement>(use))) {
    1021                             cast<Statement>(use)->replaceUsesOfWith(adv, input);
    1022                         }
    1023                     }
    1024 
    1025                     pb->setInsertPoint(pb->back());
    1026 
    1027                     V.clear();
    1028 
    1029                 }
    1030             }
    1031         }
    1032     }
    1033 }
    1034 
    1035 /** ------------------------------------------------------------------------------------------------------------- *
    1036  * @brief multiplexSelectedIndependentSets
    1037  ** ------------------------------------------------------------------------------------------------------------- */
    1038 void BDDMinimizationPass::multiplexSelectedIndependentSets() const {
    1039 
    1040     const unsigned f = num_vertices(mConstraintGraph);
    1041     const unsigned l = num_vertices(mMultiplexSetGraph);
    1042 
    1043     // Preallocate the structures based on the size of the largest multiplex set
    1044     size_t max_n = 3;
    1045     for (unsigned s = f; s != l; ++s) {
    1046         max_n = std::max<unsigned>(max_n, out_degree(s, mMultiplexSetGraph));
    1047     }
    1048     const size_t max_m = log2_plus_one(max_n);
    1049 
    1050     std::vector<MultiplexSetGraph::vertex_descriptor> I(max_n);
    1051     std::vector<Advance *> V(max_n);
    1052     std::vector<PabloAST *> muxed(max_m);
    1053     circular_buffer<PabloAST *> Q(max_n);
    1054 
    1055     // When entering thus function, the multiplex set graph M is a DAG with edges denoting the set
    1056     // relationships of our independent sets.
    1057 
    1058     for (unsigned s = f; s != l; ++s) {
    1059         const size_t n = out_degree(s, mMultiplexSetGraph);
    1060         if (n) {
    1061 
    1062             const size_t m = log2_plus_one(n);
    1063 
    1064             graph_traits<MultiplexSetGraph>::out_edge_iterator ei, ei_end;
    1065             std::tie(ei, ei_end) = out_edges(s, mMultiplexSetGraph);
    1066             for (unsigned i = 0; i != n; ++ei, ++i) {
    1067                 I[i] = target(*ei, mMultiplexSetGraph);
    1068                 assert (I[i] < mAdvance.size());
    1069             }
    1070             std::sort(I.begin(), I.begin() + n);
    1071 
    1072             for (unsigned i = 0; i != n; ++i) {
    1073                 V[i] = std::get<0>(mAdvance[I[i]]);
    1074             }
    1075 
    1076             PabloBlock * const block = V[0]->getParent();
    1077             assert (block);
    1078 
    1079             // Sanity test to make sure every advance is in the same scope.
    1080             #ifndef NDEBUG
    1081             for (unsigned i = 1; i != n; ++i) {
    1082                 assert (I[i - 1] < I[i]);
    1083                 assert (V[i - 1] != V[i]);
    1084                 assert (V[i]->getParent() == block);
    1085             }
    1086             #endif
    1087 
    1088             PabloBuilder pb(*block);
    1089 
    1090             /// Perform n-to-m Multiplexing
    1091             for (size_t j = 0; j != m; ++j) {
    1092 
    1093                 assert (Q.empty());
    1094 
    1095                 std::ostringstream prefix;
    1096                 prefix << "mux" << n << "to" << m << '_';
    1097                 for (size_t i = 1; i <= n; ++i) {
    1098                     if ((i & (static_cast<size_t>(1) << j)) != 0) {
    1099                         assert (!Q.full());
    1100                         PabloAST * tmp = V[i - 1]->getOperand(0); assert (tmp);
    1101                         // prefix << '_' << V[i - 1]->getName()->to_string();
    1102                         Q.push_back(tmp);
    1103                     }
    1104                 }
    1105 
    1106                 assert (Q.size() >= 1);
    1107 
    1108                 Advance * const adv = V[j];
    1109                 // TODO: figure out a way to determine whether we're creating a duplicate value below.
    1110                 // The expression map findOrCall ought to work conceptually but the functors method
    1111                 // doesn't really work anymore with the current API.
    1112                 while (Q.size() > 1) {
    1113                     PabloAST * a1 = Q.front(); Q.pop_front(); assert (a1);
    1114                     PabloAST * a2 = Q.front(); Q.pop_front(); assert (a2);
    1115                     assert (!Q.full());
    1116                     pb.setInsertPoint(choose(a2, a1, adv));
    1117                     Q.push_back(pb.createOr(a1, a2));
    1118                 }
    1119                 assert (Q.size() == 1);
    1120 
    1121                 PabloAST * mux = Q.front(); Q.pop_front(); assert (mux);
    1122                 muxed[j] = pb.createAdvance(mux, adv->getOperand(1), prefix.str());
    1123             }
    1124 
    1125 
    1126             /// Perform m-to-n Demultiplexing
    1127             // Now construct the demuxed values and replaces all the users of the original advances with them.
    1128             for (size_t i = 1; i <= n; ++i) {
    1129 
    1130                 Advance * const adv = V[i - 1];
    1131 
    1132                 pb.setInsertPoint(adv);
    1133                 assert (Q.empty());
    1134                 for (size_t j = 0; j != m; ++j) {
    1135                     if ((i & (static_cast<size_t>(1) << j)) == 0) {
    1136                         Q.push_back(muxed[j]);
    1137                     }
    1138                 }
    1139 
    1140                 assert (Q.size() <= m);
    1141                 PabloAST * neg = nullptr;
    1142                 if (LLVM_LIKELY(Q.size() > 0)) {
    1143                     while (Q.size() > 1) {
    1144                         PabloAST * a1 = Q.front(); Q.pop_front(); assert (a1);
    1145                         PabloAST * a2 = Q.front(); Q.pop_front(); assert (a2);
    1146                         assert (!Q.full());
    1147                         Q.push_back(pb.createOr(a1, a2));
    1148                     }
    1149                     assert (Q.size() == 1);
    1150                     neg = pb.createNot(Q.front()); Q.pop_front(); assert (neg);
    1151                 }
    1152 
    1153                 assert (Q.empty());
    1154                 for (unsigned j = 0; j != m; ++j) {
    1155                     if ((i & (static_cast<unsigned>(1) << j)) != 0) {
    1156                         assert (!Q.full());
    1157                         Q.push_back(muxed[j]);
    1158                     }
    1159                 }
    1160 
    1161                 assert (Q.size() <= m);
    1162                 assert (Q.size() >= 1);
    1163 
    1164                 while (Q.size() > 1) {
    1165                     PabloAST * a1 = Q.front(); Q.pop_front(); assert (a1);
    1166                     PabloAST * a2 = Q.front(); Q.pop_front(); assert (a2);
    1167                     assert (!Q.full());
    1168                     Q.push_back(pb.createAnd(a1, a2));
    1169                 }
    1170 
    1171                 assert (Q.size() == 1);
    1172 
    1173                 PabloAST * demux = Q.front(); Q.pop_front(); assert (demux);
    1174                 if (LLVM_LIKELY(neg != nullptr)) {
    1175                     demux = pb.createAnd(demux, neg);
    1176                 }
    1177                 V[i - 1]->replaceWith(demux, true, true);
    1178             }
    1179         }
    1180     }
    1181 }
    1182 
    1183 /** ------------------------------------------------------------------------------------------------------------- *
    1184  * @brief topologicalSort
    1185  *
    1186  * After transforming the IR, we need to run this in order to always have a valid program. Each multiplex set
    1187  * contains vertices corresponding to an Advance in the IR. While we know each Advance within a set is independent
    1188  * w.r.t. the transitive closure of their dependencies in the IR, the position of each Advance's dependencies and
    1189  * users within the IR isn't taken into consideration. Thus while there must be a valid ordering for the program,
    1190  * it's not necessarily the original ordering.
    1191  ** ------------------------------------------------------------------------------------------------------------- */
    1192 void BDDMinimizationPass::topologicalSort(PabloBlock & entry) const {
    1193     // Note: not a real topological sort. I expect the original order to be very close to the resulting one.
    1194     std::unordered_set<const PabloAST *> encountered;
    1195     std::stack<Statement *> scope;
    1196     for (Statement * stmt = entry.front(); ; ) { restart:
    1197         while ( stmt ) {
    1198             for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
    1199                 PabloAST * const op = stmt->getOperand(i);
    1200                 if (LLVM_LIKELY(isa<Statement>(op))) {
    1201                     if (LLVM_UNLIKELY(encountered.count(op) == 0)) {
    1202                         if (LLVM_UNLIKELY(isa<While>(stmt) && isa<Next>(op))) {
    1203                             if (encountered.count(cast<Next>(op)->getInitial()) != 0) {
    1204                                 continue;
    1205                             }
    1206                         }
    1207                         Statement * const next = stmt->getNextNode();
    1208                         stmt->insertAfter(cast<Statement>(op));
    1209                         stmt = next;
    1210                         goto restart;
    1211                     }
    1212                 }
    1213             }
    1214             if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
    1215                 // Set the next statement to be the first statement of the inner scope and push the
    1216                 // next statement of the current statement into the scope stack.
    1217                 const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
    1218                 scope.push(stmt->getNextNode());
    1219                 stmt = nested.front();
    1220                 continue;
    1221             }
    1222             encountered.insert(stmt);
    1223             stmt = stmt->getNextNode();
    1224         }
    1225         if (scope.empty()) {
    1226             break;
    1227         }
    1228         stmt = scope.top();
    1229         scope.pop();
    1230     }
    1231 }
     356
    1232357
    1233358} // end of namespace pablo
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_bddminimization.h

    r4629 r4692  
    2323
    2424    using CharacterizationMap = llvm::DenseMap<const PabloAST *, DdNode *>;
    25     using ConstraintGraph = boost::adjacency_matrix<boost::directedS>;
    26     using ConstraintVertex = ConstraintGraph::vertex_descriptor;
    27     using RNG = std::mt19937;
    28     using IntDistribution = std::uniform_int_distribution<RNG::result_type>;
    29     using MultiplexSetGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS>;
    30     using IndependentSetGraph = boost::adjacency_matrix<boost::undirectedS, std::pair<int, int>>;
    31     using SubsetGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS>;
    32     // the Advance pointer, input BDD and the BDD variable of the i-th Advance
    33     using AdvanceMap = boost::container::flat_map<const Statement *, unsigned>;
    34     using AdvanceVector = std::vector<std::tuple<Advance *, DdNode *, DdNode *>>;
    35     using IndependentSet = std::vector<ConstraintVertex>;
    3625
    3726    struct SubsitutionMap {
    3827        SubsitutionMap(SubsitutionMap * parent = nullptr) : mParent(parent) {}
    39         PabloAST * test(const DdNode * node, PabloAST * stmt) {
    40             PabloAST * replacement = find(node);
    41             if (LLVM_LIKELY(replacement == nullptr)) {
    42                 mMap.insert(std::make_pair(node, stmt));
    43             }
    44             return replacement;
    45         }
    46         PabloAST * find(const DdNode * node) const {
     28
     29        PabloAST * operator [](const DdNode * node) const {
    4730            auto f = mMap.find(node);
    48             if (LLVM_LIKELY(f == mMap.end())) {
    49                 PabloAST * replacement = nullptr;
    50                 if (mParent == nullptr) {
    51                     replacement = mParent->find(node);
    52                 }
    53                 return replacement;
     31            if (f == mMap.end()) {
     32                return mParent ? mParent->find(node) : nullptr;
    5433            }
    5534            return f->second;
    5635        }
     36
    5737        void insert(const DdNode * node, PabloAST * stmt) {
    5838            mMap.insert(std::make_pair(node, stmt));
     
    6444
    6545public:
    66     static bool optimize(const std::vector<Var *> & input, PabloBlock & entry);
     46    static bool optimize(PabloFunction & function);
    6747protected:
    68     void initialize(const std::vector<Var *> & vars, PabloBlock & entry);
    69     void characterize(PabloBlock & block);
    70     DdNode * characterize(Statement * const stmt, const bool throwUncharacterizedOperandError);
    71     DdNode * characterize(Advance * adv, DdNode * input);
    72     void reevaluate(Next * next, DdNode * value);
    73     void minimize(PabloBlock & entry);
    74     void minimize(PabloBlock & block, SubsitutionMap & parent);
     48    void initialize(PabloFunction & function);
     49    void characterize(const PabloBlock &block);
     50    DdNode * characterize(const Statement * const stmt);
     51    void eliminateLogicallyEquivalentStatements(PabloBlock & entry);
     52    void eliminateLogicallyEquivalentStatements(PabloBlock & block, SubsitutionMap & parent);
     53    void simplify(PabloBlock & entry);
     54    PabloAST * simplify(DdNode * bdd);
    7555
    76     bool notTransitivelyDependant(const ConstraintVertex i, const ConstraintVertex j) const;
    77     bool generateMultiplexSets(RNG & rng, unsigned k = 1);
    78     void addMultiplexSet(const IndependentSet & N, const IndependentSet & M);
    79     void selectMultiplexSets(RNG &);
    80     void applySubsetConstraints();
    81     void multiplexSelectedIndependentSets() const;
    82     void topologicalSort(PabloBlock & entry) const;
    83     inline AutoMultiplexing()
    84     : mVariables(0)
    85     , mConstraintGraph(0)
    86     {
    87     }
    8856private:
    8957    DdNode * Zero() const;
     
    10371    unsigned                mVariables;
    10472    CharacterizationMap     mCharacterizationMap;
    105     ConstraintGraph         mConstraintGraph;
    106     SubsetGraph             mSubsetGraph;
    107     AdvanceMap              mAdvanceMap;
    108     AdvanceVector           mAdvance;
    109     MultiplexSetGraph       mMultiplexSetGraph;
    11073};
    11174
Note: See TracChangeset for help on using the changeset viewer.