source: icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_bddminimization.cpp @ 4687

Last change on this file since 4687 was 4656, checked in by nmedfort, 4 years ago

Temporary check-in.

File size: 48.8 KB
Line 
1#include "pablo_bddminimization.h"
2#include <pablo/codegenstate.h>
3#include <llvm/ADT/BitVector.h>
4#include <stack>
5#include <queue>
6#include <unordered_set>
7#include <boost/container/flat_set.hpp>
8#include <boost/numeric/ublas/matrix.hpp>
9#include <boost/circular_buffer.hpp>
10#include <include/simd-lib/builtins.hpp>
11#include <pablo/builder.hpp>
12#include <boost/range/iterator_range.hpp>
13#include <pablo/printer_pablos.h>
14#include <cudd.h>
15#include <util.h>
16
17using namespace llvm;
18using namespace boost;
19using namespace boost::container;
20using namespace boost::numeric::ublas;
21
22// #define PRINT_DEBUG_OUTPUT
23
24#if !defined(NDEBUG) || defined(PRINT_DEBUG_OUTPUT)
25#include <iostream>
26
27using namespace pablo;
28typedef uint64_t timestamp_t;
29
30static inline timestamp_t read_cycle_counter() {
31#ifdef __GNUC__
32timestamp_t ts;
33#ifdef __x86_64__
34  unsigned int eax, edx;
35  asm volatile("rdtsc" : "=a" (eax), "=d" (edx));
36  ts = ((timestamp_t) eax) | (((timestamp_t) edx) << 32);
37#else
38  asm volatile("rdtsc\n" : "=A" (ts));
39#endif
40  return(ts);
41#endif
42#ifdef _MSC_VER
43  return __rdtsc();
44#endif
45}
46
47#define LOG(x) std::cerr << x << std::endl;
48#define RECORD_TIMESTAMP(Name) const timestamp_t Name = read_cycle_counter()
49#define LOG_GRAPH(Name, G) \
50    LOG(Name << " |V|=" << num_vertices(G) << ", |E|="  << num_edges(G) << \
51                " (" << (((double)num_edges(G)) / ((double)(num_vertices(G) * (num_vertices(G) - 1) / 2))) << ')')
52
53unsigned __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))
85
86#else
87#define LOG(x)
88#define RECORD_TIMESTAMP(Name)
89#define LOG_GRAPH(Name, G)
90#define LOG_NUMBER_OF_ADVANCES(entry)
91#endif
92
93
94namespace pablo {
95
96bool 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);
103
104    BDDMinimizationPass am;
105    RECORD_TIMESTAMP(start_initialize);
106    am.initialize(input, entry);
107    RECORD_TIMESTAMP(end_initialize);
108
109    LOG("Initialize:              " << (end_initialize - start_initialize));
110
111    LOG_NUMBER_OF_ADVANCES(entry);
112
113    RECORD_TIMESTAMP(start_characterize);
114    am.characterize(entry);
115    RECORD_TIMESTAMP(end_characterize);
116
117    LOG("Characterize:            " << (end_characterize - start_characterize));
118
119    RECORD_TIMESTAMP(start_minimization);
120    am.minimize(entry);
121    RECORD_TIMESTAMP(end_minimization);
122    LOG("Minimize:                " << (end_minimization - start_minimization));
123
124    RECORD_TIMESTAMP(start_shutdown);
125    am.shutdown();
126    RECORD_TIMESTAMP(end_shutdown);
127    LOG("Shutdown:                " << (end_shutdown - start_shutdown));
128
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);
158
159    return multiplex;
160}
161
162/** ------------------------------------------------------------------------------------------------------------- *
163 * @brief initialize
164 * @param vars the input vars for this program
165 * @param entry the entry block
166 *
167 * Scan through the program to identify any advances and calls then initialize the BDD engine with
168 * the proper variable ordering.
169 ** ------------------------------------------------------------------------------------------------------------- */
170void BDDMinimizationPass::initialize(const std::vector<Var *> & vars, PabloBlock & entry) {
171
172    flat_map<const PabloAST *, unsigned> map;
173    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(); ; ) {
179        while ( stmt ) {
180            ++n;
181            if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
182                // Set the next statement to be the first statement of the inner scope and push the
183                // next statement of the current statement into the scope stack.
184                const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
185                scope.push(stmt->getNextNode());
186                stmt = nested.front();
187                assert (stmt);
188                continue;
189            }
190
191            assert ("Run the Simplifer pass prior to this!" && (stmt->getNumUses() != 0 || (isa<Assign>(stmt) ? !cast<Assign>(stmt)->superfluous() : false)));
192
193            switch (stmt->getClassTypeId()) {
194                case PabloAST::ClassTypeId::Advance:
195                    mAdvanceMap.emplace(stmt, m);
196                    map.emplace(stmt, m++);
197                case PabloAST::ClassTypeId::Call:
198                case PabloAST::ClassTypeId::ScanThru:
199                case PabloAST::ClassTypeId::MatchStar:
200                    complexStatements++;
201                    break;
202                default:
203                    break;
204            }
205            stmt = stmt->getNextNode();
206        }
207        if (scope.empty()) {
208            break;
209        }
210        stmt = scope.top();
211        scope.pop();
212    }
213
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
286    // Initialize the BDD engine ...
287    mManager = Cudd_Init((complexStatements + vars.size()), 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0);
288    Cudd_AutodynDisable(mManager);
289
290    // Map the predefined 0/1 entries
291    mCharacterizationMap[entry.createZeroes()] = Zero();
292    mCharacterizationMap[entry.createOnes()] = One();
293
294    // Order the variables so the input Vars are pushed to the end; they ought to
295    // be the most complex to resolve.
296    unsigned i = complexStatements;
297    for (const Var * var : vars) {
298        mCharacterizationMap[var] = Cudd_bddIthVar(mManager, i++);
299    }
300}
301
302/** ------------------------------------------------------------------------------------------------------------- *
303 * @brief characterize
304 * @param vars the input vars for this program
305 *
306 * Scan through the program and iteratively compute the BDDs for each statement.
307 ** ------------------------------------------------------------------------------------------------------------- */
308void BDDMinimizationPass::characterize(PabloBlock & block) {
309    for (Statement * stmt : block) {
310        if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
311            // Set the next statement to be the first statement of the inner scope and push the
312            // next statement of the current statement into the scope stack.
313            characterize(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
314            continue;
315        }
316        mCharacterizationMap[stmt] = characterize(stmt, true);
317    }
318}
319
320/** ------------------------------------------------------------------------------------------------------------- *
321 * @brief characterize
322 ** ------------------------------------------------------------------------------------------------------------- */
323DdNode * BDDMinimizationPass::characterize(Statement * const stmt, const bool throwUncharacterizedOperandError) {
324
325    DdNode * bdd = nullptr;
326    // Map our operands to the computed BDDs
327    std::array<DdNode *, 3> input;
328    for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
329        PabloAST * const op = stmt->getOperand(i);
330        if (LLVM_UNLIKELY(isa<Integer>(op) || isa<String>(op))) {
331            continue;
332        }
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;
345    }
346
347    switch (stmt->getClassTypeId()) {
348        case PabloAST::ClassTypeId::Assign:
349            return input[0];
350        case PabloAST::ClassTypeId::And:
351            bdd = And(input[0], input[1]);
352            break;
353        case PabloAST::ClassTypeId::Next:
354        case PabloAST::ClassTypeId::Or:
355            return Or(input[0], input[1]);
356        case PabloAST::ClassTypeId::Xor:
357            return Xor(input[0], input[1]);
358        case PabloAST::ClassTypeId::Not:
359            return Not(input[0]);
360        case PabloAST::ClassTypeId::Sel:
361            bdd = Ite(input[0], input[1], input[2]);
362            break;
363        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)
367        case PabloAST::ClassTypeId::MatchStar:
368            if (LLVM_UNLIKELY(isZero(input[0]) || isZero(input[1]))) {
369                return Zero();
370            }
371        case PabloAST::ClassTypeId::Call:
372            return NewVar();
373        case PabloAST::ClassTypeId::Advance:
374            return characterize(cast<Advance>(stmt), input[0]);
375        default:
376            throw std::runtime_error("Unexpected statement type " + stmt->getName()->to_string());
377    }
378
379    if (LLVM_UNLIKELY(noSatisfyingAssignment(bdd))) {
380        Cudd_RecursiveDeref(mManager, bdd);
381        bdd = Zero();
382    }
383
384    return bdd;
385
386}
387
388/** ------------------------------------------------------------------------------------------------------------- *
389 * @brief characterize
390 ** ------------------------------------------------------------------------------------------------------------- */
391inline 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 = ∅ and Aj ⊂ Ai, Aj ∩ Ak = ∅.
427                    graph_traits<SubsetGraph>::in_edge_iterator ei, ei_end;
428                    for (std::tie(ei, ei_end) = in_edges(i, mSubsetGraph); ei != ei_end; ++ei) {
429                        const auto j = source(*ei, mSubsetGraph);
430                        if (notTransitivelyDependant(k, j)) {
431                            Advance * adv = std::get<0>(mAdvance[j]);
432                            assert (mCharacterizationMap.count(adv));
433                            DdNode *& Cj = mCharacterizationMap[adv];
434                            DdNode * Nj = std::get<2>(mAdvance[j]);
435                            // Mark the i-th and j-th Advances as being mutually exclusive
436                            Ck = And(Ck, Nj);
437                            Cj = And(Cj, Nk);
438                            unconstrained[j] = true;
439                        }
440                    }
441                    unconstrained[i] = true;
442                }
443                else if (Ik == IiIk) {
444                    // If Ik = Ii ∩ Ik then Ik ⊂ Ii. Record this in the subset graph with the arc (k,i).
445                    // These edges will be moved into the multiplex set graph if Ai and Ak happen to be
446                    // in the same mutually exclusive set.
447                    add_edge(k, i, mSubsetGraph);
448                    // If Ak ⊂ Ai and Ai ⊂ Aj, Ak ⊂ Aj.
449                    graph_traits<SubsetGraph>::out_edge_iterator ei, ei_end;
450                    for (std::tie(ei, ei_end) = out_edges(i, mSubsetGraph); ei != ei_end; ++ei) {
451                        const auto j = target(*ei, mSubsetGraph);
452                        add_edge(k, j, mSubsetGraph);
453                        unconstrained[j] = true;
454                    }
455                    unconstrained[i] = true;
456                }
457                else if (Ii == IiIk) {
458                    // If Ii = Ii ∩ Ik then Ii ⊂ Ik. Record this in the subset graph with the arc (i,k).
459                    add_edge(i, k, mSubsetGraph);
460                    // If Ai ⊂ Ak and Aj ⊂ Ai, Aj ⊂ Ak.
461                    graph_traits<SubsetGraph>::in_edge_iterator ei, ei_end;
462                    for (std::tie(ei, ei_end) = in_edges(i, mSubsetGraph); ei != ei_end; ++ei) {
463                        const auto j = source(*ei, mSubsetGraph);
464                        add_edge(j, k, mSubsetGraph);
465                        unconstrained[j] = true;
466                    }
467                    unconstrained[i] = true;
468                }
469                Cudd_RecursiveDeref(mManager, IiIk);
470            }
471        }
472
473        for (unsigned i = 0; i != k; ++i) {
474            const Advance * const tmp = std::get<0>(mAdvance[i]);
475            // Even if these Advances are mutually exclusive, they must be in the same scope or they cannot be safely multiplexed.
476            if (!unconstrained[i] || (adv->getParent() != tmp->getParent())) {
477                // We want the constraint graph to be acyclic; since the dependencies are already in topological order,
478                // adding an arc from a lesser to greater numbered vertex won't induce a cycle.
479                add_edge(i, k, mConstraintGraph);
480            }
481        }
482    }
483
484    mAdvance.emplace_back(adv, Ik, Nk);
485
486    return Ck;
487}
488
489/** ------------------------------------------------------------------------------------------------------------- *
490 * @brief reevaluate
491 ** ------------------------------------------------------------------------------------------------------------- */
492void BDDMinimizationPass::reevaluate(Next * next, DdNode * value) {
493
494    Assign * const initial = cast<Assign>(next->getOperand(0));
495
496    if (LLVM_UNLIKELY(mCharacterizationMap[initial] == value)) {
497        return;
498    }
499    mCharacterizationMap[initial] = value;
500
501
502    std::queue<PabloAST *> Q;
503    flat_set<PabloBlock *> within_scope;
504
505    for (PabloBlock * block = next->getParent(); ;) {
506        within_scope.insert(block);
507        for (PabloAST * user : block->users()) {
508            if (within_scope.insert(cast<PabloBlock>(user)).second) {
509                Q.push(user);
510            }
511        }
512        if (Q.empty()) {
513            break;
514        }
515        block = cast<PabloBlock>(Q.front());
516        Q.pop();
517    }
518
519    std::unordered_set<PabloAST *> visited;
520
521    for (Statement * current = initial; ; ) {
522        for (PabloAST * user : current->users()) {
523            if (Statement * stmt = dyn_cast<Statement>(user)) {
524                if (visited.insert(user).second && within_scope.count(stmt->getParent())) {
525                    DdNode * bdd = characterize(stmt, false);
526                    if (bdd && mCharacterizationMap[user] != bdd) {
527                        mCharacterizationMap[user] = bdd;
528                        Q.push(stmt);
529                    }
530                }
531            }
532        }
533        if (Q.empty()) {
534            break;
535        }
536        current = cast<Statement>(Q.front());
537        Q.pop();
538    }
539
540}
541
542/** ------------------------------------------------------------------------------------------------------------- *
543 * @brief minimize
544 * @param entry the entry block of the program
545 *
546 * Scan through the program using the precomputed BDDs and replace any statements with equivalent BDDs with the
547 * earlier one (assuming its in scope) and replace any contradictions with Zero.
548 ** ------------------------------------------------------------------------------------------------------------- */
549inline void BDDMinimizationPass::minimize(PabloBlock & entry) {
550    SubsitutionMap baseMap;
551    baseMap.insert(Zero(), entry.createZeroes());
552    baseMap.insert(One(), entry.createOnes());
553    minimize(entry, baseMap);
554}
555
556/** ------------------------------------------------------------------------------------------------------------- *
557 * @brief prohibited
558 *
559 * If this statement is an Assign or Next node or any of its operands is a non-superfluous Assign or Next node,
560 * then we're prohibited from minimizing this statement.
561 ** ------------------------------------------------------------------------------------------------------------- */
562inline bool prohibited(const Statement * const stmt) {
563    if (isa<Assign>(stmt) || isa<Next>(stmt)) {
564        return true;
565    }
566    for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
567        const PabloAST * const  op = stmt->getOperand(i);
568        const Assign * const assign = dyn_cast<Assign>(op);
569        if (LLVM_UNLIKELY((assign && !assign->superfluous()) || isa<Next>(op))) {
570            return true;
571        }
572    }
573    return false;
574}
575
576/** ------------------------------------------------------------------------------------------------------------- *
577 * @brief minimize
578 ** ------------------------------------------------------------------------------------------------------------- */
579void BDDMinimizationPass::minimize(PabloBlock & block, SubsitutionMap & parent) {
580    SubsitutionMap subsitutionMap(&parent);
581    for (Statement * stmt : block) {
582        if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
583            // Set the next statement to be the first statement of the inner scope and push the
584            // next statement of the current statement into the scope stack.
585            minimize(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(), subsitutionMap);
586            continue;
587        }
588
589        if (LLVM_UNLIKELY(prohibited(stmt))) {
590            continue;
591        }
592
593        DdNode * bdd = mCharacterizationMap[stmt];
594        PabloAST * replacement = subsitutionMap.test(bdd, stmt);
595        if (LLVM_UNLIKELY(replacement != nullptr)) {
596            if (LLVM_UNLIKELY(isa<Advance>(stmt))) {
597                assert (mAdvanceMap.count(stmt));
598                const auto k = mAdvanceMap[stmt];
599                const auto m = num_vertices(mConstraintGraph);
600                for (unsigned i = 0; i != m; ++i) {
601                    add_edge(k, m, mConstraintGraph);
602                }
603            }
604            Cudd_RecursiveDeref(mManager, bdd);
605            stmt->replaceWith(replacement);
606        }
607    }
608}
609
610/** ------------------------------------------------------------------------------------------------------------- *
611 * @brief notTransitivelyDependant
612 ** ------------------------------------------------------------------------------------------------------------- */
613inline bool BDDMinimizationPass::notTransitivelyDependant(const ConstraintVertex i, const ConstraintVertex j) const {
614    assert (i < num_vertices(mConstraintGraph) && j < num_vertices(mConstraintGraph));
615    return (mConstraintGraph.get_edge(i, j) == 0);
616}
617
618/** ------------------------------------------------------------------------------------------------------------- *
619 * @brief CUDD wrappers
620 ** ------------------------------------------------------------------------------------------------------------- */
621
622inline DdNode * BDDMinimizationPass::Zero() const {
623    return Cudd_ReadLogicZero(mManager);
624}
625
626inline DdNode * BDDMinimizationPass::One() const {
627    return Cudd_ReadOne(mManager);
628}
629
630inline DdNode * BDDMinimizationPass::NewVar() {
631    return Cudd_bddIthVar(mManager, mVariables++);
632}
633
634inline bool BDDMinimizationPass::isZero(DdNode * const x) const {
635    return x == Zero();
636}
637
638inline DdNode * BDDMinimizationPass::And(DdNode * const x, DdNode * const y) {
639    DdNode * r = Cudd_bddAnd(mManager, x, y);
640    Cudd_Ref(r);
641    return r;
642}
643
644inline DdNode * BDDMinimizationPass::Intersect(DdNode * const x, DdNode * const y) {
645    DdNode * r = Cudd_bddIntersect(mManager, x, y); Cudd_Ref(r);
646    return r;
647}
648
649inline DdNode * BDDMinimizationPass::Or(DdNode * const x, DdNode * const y) {
650    DdNode * r = Cudd_bddOr(mManager, x, y);
651    Cudd_Ref(r);
652    return r;
653}
654
655inline DdNode * BDDMinimizationPass::Xor(DdNode * const x, DdNode * const y) {
656    DdNode * r = Cudd_bddXor(mManager, x, y);
657    Cudd_Ref(r);
658    return r;
659}
660
661inline DdNode * BDDMinimizationPass::Not(DdNode * const x) const {
662    return Cudd_Not(x);
663}
664
665inline DdNode * BDDMinimizationPass::Ite(DdNode * const x, DdNode * const y, DdNode * const z) {
666    DdNode * r = Cudd_bddIte(mManager, x, y, z);
667    Cudd_Ref(r);
668    return r;
669}
670
671inline bool BDDMinimizationPass::noSatisfyingAssignment(DdNode * const x) {
672    return Cudd_bddLeq(mManager, x, Zero());
673}
674
675inline void BDDMinimizationPass::shutdown() {
676    Cudd_Quit(mManager);
677}
678
679/** ------------------------------------------------------------------------------------------------------------- *
680 * @brief generateMultiplexSets
681 * @param RNG random number generator
682 ** ------------------------------------------------------------------------------------------------------------- */
683bool BDDMinimizationPass::generateMultiplexSets(RNG & rng, unsigned k) {
684
685    using vertex_t = ConstraintGraph::vertex_descriptor;
686    using degree_t = graph_traits<ConstraintGraph>::degree_size_type;
687
688    // What if we generated a "constraint free" graph instead? By taking each connected component of it
689    // and computing the complement of it (with the same lesser to greater index ordering), we should
690    // have the same problem here but decomposed into subgraphs.
691
692    IndependentSet M, N;
693    auto remainingVerticies = num_vertices(mConstraintGraph);
694    std::vector<degree_t> D(remainingVerticies);
695    M.reserve(15);
696    N.reserve(15);
697
698    mMultiplexSetGraph = MultiplexSetGraph(remainingVerticies);
699
700    while (k) {
701
702        // Push all source nodes into the new independent set N
703        for (auto v : make_iterator_range(vertices(mConstraintGraph))) {
704            const auto d = in_degree(v, mConstraintGraph);
705            D[v] = d;
706            if (d == 0) {
707                N.push_back(v);
708            }
709        }
710
711        for (;;) {
712
713            addMultiplexSet(N, M);
714
715            if (remainingVerticies == 0) {
716                break;
717            }
718
719            assert (N.size() > 0);
720
721            // Move all of our "newly" uncovered vertices in S into the "known" set M. By always choosing
722            // at least one element from N, this will prevent us from adding the same multiplexing set again.
723            M.insert(M.end(), N.begin(), N.end()); N.clear();
724
725            do {
726                // Randomly choose a vertex in S and discard it.
727                assert (!M.empty());
728                const auto i = M.begin() + IntDistribution(0, M.size() - 1)(rng);
729                const vertex_t u = *i;
730                M.erase(i);
731                --remainingVerticies;
732                for (auto e : make_iterator_range(out_edges(u, mConstraintGraph))) {
733                    const vertex_t v = target(e, mConstraintGraph);
734                    if ((--D[v]) == 0) {
735                        N.push_back(v);
736                    }
737                }
738            }
739            while (N.empty() && remainingVerticies != 0);
740        }
741
742        if (--k == 0) {
743            break;
744        }
745
746        N.clear();
747        M.clear();
748    }
749
750    return num_vertices(mMultiplexSetGraph) > num_vertices(mConstraintGraph);
751}
752
753/** ------------------------------------------------------------------------------------------------------------- *
754 * @brief addMultiplexSet
755 * @param N an independent set
756 * @param M an independent set
757 ** ------------------------------------------------------------------------------------------------------------- */
758inline void BDDMinimizationPass::addMultiplexSet(const IndependentSet & N, const IndependentSet & M) {
759
760    // At this stage, the multiplex set graph is a directed bipartite graph that is used to show relationships
761    // between the "set vertex" and its members. We obtain these from "generateMultiplexSets".
762
763    if ((N.size() + M.size()) >= 3) {
764        const auto u = add_vertex(mMultiplexSetGraph);
765        for (const auto x : N) {
766            add_edge(u, x, mMultiplexSetGraph);
767        }
768        for (const auto y : M) {
769            add_edge(u, y, mMultiplexSetGraph);
770        }
771    }
772}
773
774/** ------------------------------------------------------------------------------------------------------------- *
775 * @brief is_power_of_2
776 * @param n an integer
777 ** ------------------------------------------------------------------------------------------------------------- */
778static inline bool is_power_of_2(const size_t n) {
779    return ((n & (n - 1)) == 0) ;
780}
781
782/** ------------------------------------------------------------------------------------------------------------- *
783 * @brief log2_plus_one
784 ** ------------------------------------------------------------------------------------------------------------- */
785static inline size_t log2_plus_one(const size_t n) {
786    return std::log2<size_t>(n) + 1; // use a faster builtin function for this?
787}
788
789/** ------------------------------------------------------------------------------------------------------------- *
790 * @brief selectMultiplexSets
791 * @param RNG random number generator
792 *
793 * This algorithm is simply computes a greedy set cover. We want an exact max-weight set cover but can generate new
794 * sets by taking a subset of any existing set. With a few modifications, the greedy approach seems to work well
795 * enough but more analysis is needed.
796 ** ------------------------------------------------------------------------------------------------------------- */
797void BDDMinimizationPass::selectMultiplexSets(RNG &) {
798
799
800    using OutEdgeIterator = graph_traits<MultiplexSetGraph>::out_edge_iterator;
801    using InEdgeIterator = graph_traits<MultiplexSetGraph>::in_edge_iterator;
802    using degree_t = MultiplexSetGraph::degree_size_type;
803    using vertex_t = MultiplexSetGraph::vertex_descriptor;
804
805    const size_t m = num_vertices(mConstraintGraph);
806    const size_t n = num_vertices(mMultiplexSetGraph) - m;
807
808    std::vector<degree_t> remaining(n, 0);
809    std::vector<vertex_t> chosen_set(m, 0);
810
811    for (unsigned i = 0; i != n; ++i) {
812        remaining[i] = out_degree(i + m, mMultiplexSetGraph);
813    }
814
815    for (;;) {
816
817        // Choose the set with the greatest number of vertices not already included in some other set.
818        vertex_t k = 0;
819        degree_t w = 0;
820        for (vertex_t i = 0; i != n; ++i) {
821            const degree_t r = remaining[i];
822            if (w < r) {
823                k = i;
824                w = r;
825            }
826        }
827
828        // Multiplexing requires at least 3 elements; if the best set contains fewer than 3, abort.
829        if (w < 3) {
830            break;
831        }
832
833        OutEdgeIterator ei, ei_end;
834        for (std::tie(ei, ei_end) = out_edges(k + m, mMultiplexSetGraph); ei != ei_end; ++ei) {
835            const vertex_t j = target(*ei, mMultiplexSetGraph);
836            if (chosen_set[j] == 0) {
837                chosen_set[j] = (k + m);
838                InEdgeIterator ej, ej_end;
839                for (std::tie(ej, ej_end) = in_edges(j, mMultiplexSetGraph); ej != ej_end; ++ej) {
840                    remaining[source(*ej, mMultiplexSetGraph) - m]--;
841                }
842            }
843        }
844
845        assert (remaining[k] == 0);
846
847        // If this contains 2^n elements for any n, discard the member that is most likely to be added
848        // to some future set.
849        if (is_power_of_2(w)) {
850            vertex_t j = 0;
851            degree_t w = 0;
852            for (vertex_t i = 0; i != m; ++i) {
853                if (chosen_set[i] == (k + m)) {
854                    InEdgeIterator ej, ej_end;
855                    degree_t r = 1;
856                    for (std::tie(ej, ej_end) = in_edges(i, mMultiplexSetGraph); ej != ej_end; ++ej) {
857                        // strongly prefer adding weight to unvisited sets that have more remaining vertices
858                        r += std::pow(remaining[source(*ej, mMultiplexSetGraph) - m], 2);
859                    }
860                    if (w < r) {
861                        j = i;
862                        w = r;
863                    }
864                }
865            }
866            assert (w > 0);
867            chosen_set[j] = 0;
868            InEdgeIterator ej, ej_end;
869            for (std::tie(ej, ej_end) = in_edges(j, mMultiplexSetGraph); ej != ej_end; ++ej) {
870                remaining[source(*ej, mMultiplexSetGraph) - m]++;
871            }
872        }
873    }
874
875    for (unsigned i = 0; i != m; ++i) {
876        InEdgeIterator ei, ei_end;
877        std::tie(ei, ei_end) = in_edges(i, mMultiplexSetGraph);
878        for (auto next = ei; ei != ei_end; ei = next) {
879            ++next;
880            if (source(*ei, mMultiplexSetGraph) != chosen_set[i]) {
881                remove_edge(*ei, mMultiplexSetGraph);
882            }
883        }
884    }
885
886    #ifndef NDEBUG
887    for (unsigned i = 0; i != m; ++i) {
888        assert (in_degree(i, mMultiplexSetGraph) <= 1);
889    }
890    for (unsigned i = m; i != (m + n); ++i) {
891        assert (out_degree(i, mMultiplexSetGraph) == 0 || out_degree(i, mMultiplexSetGraph) >= 3);
892    }
893    #endif
894}
895
896/** ------------------------------------------------------------------------------------------------------------- *
897 * @brief choose
898 ** ------------------------------------------------------------------------------------------------------------- */
899
900inline Statement * choose(PabloAST * x, PabloAST * y, Statement * z) {
901    return isa<Statement>(x) ? cast<Statement>(x) : (isa<Statement>(y) ? cast<Statement>(y) : z);
902}
903
904/** ------------------------------------------------------------------------------------------------------------- *
905 * @brief applySubsetConstraints
906 ** ------------------------------------------------------------------------------------------------------------- */
907void BDDMinimizationPass::applySubsetConstraints() {
908
909    // When entering thus function, the multiplex set graph M is a bipartite DAG with edges denoting the set
910    // relationships of our independent sets.
911    const unsigned m = num_vertices(mConstraintGraph);
912    const unsigned n = num_vertices(mMultiplexSetGraph);
913
914    // Add in any edges from our subset constraints to M that are within the same set.
915    bool hasSubsetConstraint = false;
916
917    graph_traits<SubsetGraph>::edge_iterator ei, ei_end;
918    for (std::tie(ei, ei_end) = edges(mSubsetGraph); ei != ei_end; ++ei) {
919        const auto u = source(*ei, mSubsetGraph);
920        const auto v = target(*ei, mSubsetGraph);
921        graph_traits<MultiplexSetGraph>::in_edge_iterator ej, ej_end;
922        // If both the source and target of ei are adjacent to the same vertex, that vertex must be the
923        // "set vertex". Add the edge between the vertices.
924        for (std::tie(ej, ej_end) = in_edges(u, mMultiplexSetGraph); ej != ej_end; ++ej) {
925            auto w = target(*ej, mMultiplexSetGraph);
926            // Only check (v, w) if w is a "set vertex".
927            if (w >= (n - m) && edge(v, w, mMultiplexSetGraph).second) {
928                add_edge(u, v, mMultiplexSetGraph);
929                hasSubsetConstraint = true;
930            }
931        }
932    }
933
934    if (LLVM_UNLIKELY(hasSubsetConstraint)) {
935        // At this point, M is still a DAG but no longer bipartite. We're going to scan through the set vertices
936        // in M, and use a DFS to scan through M and eliminate any subset relationships in the AST.
937        // That way, "multiplexSelectedIndependentSets" only needs to consider muxing and demuxing of the streams.
938
939        std::vector<MultiplexSetGraph::vertex_descriptor> V;
940        std::stack<MultiplexSetGraph::vertex_descriptor> S;
941        std::queue<PabloAST *> Q;
942        BitVector D(n - m, 0);
943
944        for (auto i = m; i != n; ++i) {
945            graph_traits<MultiplexSetGraph>::out_edge_iterator ei, ei_end;
946            // For each member of a "set vertex" ...
947            std::tie(ei, ei_end) = out_edges(i, mMultiplexSetGraph);
948            for (; ei != ei_end; ++ei) {
949                const auto s = source(*ei, mMultiplexSetGraph);
950                if (out_degree(s, mMultiplexSetGraph) != 0) {
951                    // First scan through the subgraph of vertices in M dominated by s and build up the set T,
952                    // consisting of all sinks w.r.t. vertex s.
953                    auto u = s;
954                    for (;;) {
955                        graph_traits<MultiplexSetGraph>::out_edge_iterator ej, ej_end;
956                        for (std::tie(ej, ej_end) = out_edges(u, mMultiplexSetGraph); ej != ej_end; ++ej) {
957                            auto v = target(*ej, mMultiplexSetGraph);
958                            if (D.test(v)) {
959                                continue;
960                            }
961                            D.set(v);
962                            if (out_degree(v, mMultiplexSetGraph) == 0) {
963                                V.push_back(v);
964                            }
965                            else {
966                                S.push(v);
967                            }
968                        }
969                        if (S.empty()) {
970                            break;
971                        }
972                        u = S.top();
973                        S.pop();
974                    }
975                    D.clear();
976                    // Now in order for these advances to be mutually exclusive, the input to A_s must be masked
977                    // with the complement of each advance indicated by V.
978
979                    Advance * adv = std::get<0>(mAdvance[s]);
980                    PabloBlock * pb = adv->getParent();
981
982                    for (auto i : V) {
983                        Q.push(std::get<0>(mAdvance[i])->getOperand(0));
984                    }
985                    while (Q.size() > 1) {
986                        PabloAST * a1 = Q.front(); Q.pop();
987                        PabloAST * a2 = Q.front(); Q.pop();
988                        pb->setInsertPoint(cast<Statement>(a2));
989                        Q.push(pb->createOr(a1, a2));
990                    }
991                    assert (Q.size() == 1);
992
993                    PabloAST * const mask = pb->createNot(Q.front()); Q.pop();
994                    adv->setOperand(0, pb->createAnd(adv->getOperand(0), mask, "subset_in"));
995
996                    // Similar to the above, we're going to OR together the result of each advance,
997                    // including s. This will restore the advanced variable back to its original state.
998
999                    // Gather the original users to this advance. We'll be manipulating it shortly.
1000                    Statement::Vector U(adv->users());
1001
1002                    // Add s to V and sort the list; it'll be closer to being in topological order.
1003                    V.push_back(s);
1004                    std::sort(V.begin(), V.end());
1005                    for (auto i : V) {
1006                        Q.push(std::get<0>(mAdvance[i]));
1007                    }
1008                    while (Q.size() > 1) {
1009                        PabloAST * a1 = Q.front(); Q.pop();
1010                        PabloAST * a2 = Q.front(); Q.pop();
1011                        pb->setInsertPoint(choose(a2, a1, adv));
1012                        Q.push(pb->createOr(a1, a2));
1013                    }
1014                    assert (Q.size() == 1);
1015
1016                    PabloAST * const input = Q.front(); Q.pop();
1017                    for (PabloAST * use : U) {
1018                        if (LLVM_LIKELY(isa<Statement>(use))) {
1019                            cast<Statement>(use)->replaceUsesOfWith(adv, input);
1020                        }
1021                    }
1022
1023                    pb->setInsertPoint(pb->back());
1024
1025                    V.clear();
1026
1027                }
1028            }
1029        }
1030    }
1031}
1032
1033/** ------------------------------------------------------------------------------------------------------------- *
1034 * @brief multiplexSelectedIndependentSets
1035 ** ------------------------------------------------------------------------------------------------------------- */
1036void BDDMinimizationPass::multiplexSelectedIndependentSets() const {
1037
1038    const unsigned f = num_vertices(mConstraintGraph);
1039    const unsigned l = num_vertices(mMultiplexSetGraph);
1040
1041    // Preallocate the structures based on the size of the largest multiplex set
1042    size_t max_n = 3;
1043    for (unsigned s = f; s != l; ++s) {
1044        max_n = std::max<unsigned>(max_n, out_degree(s, mMultiplexSetGraph));
1045    }
1046    const size_t max_m = log2_plus_one(max_n);
1047
1048    std::vector<MultiplexSetGraph::vertex_descriptor> I(max_n);
1049    std::vector<Advance *> V(max_n);
1050    std::vector<PabloAST *> muxed(max_m);
1051    circular_buffer<PabloAST *> Q(max_n);
1052
1053    // When entering thus function, the multiplex set graph M is a DAG with edges denoting the set
1054    // relationships of our independent sets.
1055
1056    for (unsigned s = f; s != l; ++s) {
1057        const size_t n = out_degree(s, mMultiplexSetGraph);
1058        if (n) {
1059
1060            const size_t m = log2_plus_one(n);
1061
1062            graph_traits<MultiplexSetGraph>::out_edge_iterator ei, ei_end;
1063            std::tie(ei, ei_end) = out_edges(s, mMultiplexSetGraph);
1064            for (unsigned i = 0; i != n; ++ei, ++i) {
1065                I[i] = target(*ei, mMultiplexSetGraph);
1066                assert (I[i] < mAdvance.size());
1067            }
1068            std::sort(I.begin(), I.begin() + n);
1069
1070            for (unsigned i = 0; i != n; ++i) {
1071                V[i] = std::get<0>(mAdvance[I[i]]);
1072            }
1073
1074            PabloBlock * const block = V[0]->getParent();
1075            assert (block);
1076
1077            // Sanity test to make sure every advance is in the same scope.
1078            #ifndef NDEBUG
1079            for (unsigned i = 1; i != n; ++i) {
1080                assert (I[i - 1] < I[i]);
1081                assert (V[i - 1] != V[i]);
1082                assert (V[i]->getParent() == block);
1083            }
1084            #endif
1085
1086            PabloBuilder pb(*block);
1087
1088            /// Perform n-to-m Multiplexing
1089            for (size_t j = 0; j != m; ++j) {
1090
1091                assert (Q.empty());
1092
1093                std::ostringstream prefix;
1094                prefix << "mux" << n << "to" << m << '_';
1095                for (size_t i = 1; i <= n; ++i) {
1096                    if ((i & (static_cast<size_t>(1) << j)) != 0) {
1097                        assert (!Q.full());
1098                        PabloAST * tmp = V[i - 1]->getOperand(0); assert (tmp);
1099                        // prefix << '_' << V[i - 1]->getName()->to_string();
1100                        Q.push_back(tmp);
1101                    }
1102                }
1103
1104                assert (Q.size() >= 1);
1105
1106                Advance * const adv = V[j];
1107                // TODO: figure out a way to determine whether we're creating a duplicate value below.
1108                // The expression map findOrCall ought to work conceptually but the functors method
1109                // doesn't really work anymore with the current API.
1110                while (Q.size() > 1) {
1111                    PabloAST * a1 = Q.front(); Q.pop_front(); assert (a1);
1112                    PabloAST * a2 = Q.front(); Q.pop_front(); assert (a2);
1113                    assert (!Q.full());
1114                    pb.setInsertPoint(choose(a2, a1, adv));
1115                    Q.push_back(pb.createOr(a1, a2));
1116                }
1117                assert (Q.size() == 1);
1118
1119                PabloAST * mux = Q.front(); Q.pop_front(); assert (mux);
1120                muxed[j] = pb.createAdvance(mux, adv->getOperand(1), prefix.str());
1121            }
1122
1123
1124            /// Perform m-to-n Demultiplexing
1125            // Now construct the demuxed values and replaces all the users of the original advances with them.
1126            for (size_t i = 1; i <= n; ++i) {
1127
1128                Advance * const adv = V[i - 1];
1129
1130                pb.setInsertPoint(adv);
1131                assert (Q.empty());
1132                for (size_t j = 0; j != m; ++j) {
1133                    if ((i & (static_cast<size_t>(1) << j)) == 0) {
1134                        Q.push_back(muxed[j]);
1135                    }
1136                }
1137
1138                assert (Q.size() <= m);
1139                PabloAST * neg = nullptr;
1140                if (LLVM_LIKELY(Q.size() > 0)) {
1141                    while (Q.size() > 1) {
1142                        PabloAST * a1 = Q.front(); Q.pop_front(); assert (a1);
1143                        PabloAST * a2 = Q.front(); Q.pop_front(); assert (a2);
1144                        assert (!Q.full());
1145                        Q.push_back(pb.createOr(a1, a2));
1146                    }
1147                    assert (Q.size() == 1);
1148                    neg = pb.createNot(Q.front()); Q.pop_front(); assert (neg);
1149                }
1150
1151                assert (Q.empty());
1152                for (unsigned j = 0; j != m; ++j) {
1153                    if ((i & (static_cast<unsigned>(1) << j)) != 0) {
1154                        assert (!Q.full());
1155                        Q.push_back(muxed[j]);
1156                    }
1157                }
1158
1159                assert (Q.size() <= m);
1160                assert (Q.size() >= 1);
1161
1162                while (Q.size() > 1) {
1163                    PabloAST * a1 = Q.front(); Q.pop_front(); assert (a1);
1164                    PabloAST * a2 = Q.front(); Q.pop_front(); assert (a2);
1165                    assert (!Q.full());
1166                    Q.push_back(pb.createAnd(a1, a2));
1167                }
1168
1169                assert (Q.size() == 1);
1170
1171                PabloAST * demux = Q.front(); Q.pop_front(); assert (demux);
1172                if (LLVM_LIKELY(neg != nullptr)) {
1173                    demux = pb.createAnd(demux, neg);
1174                }
1175                V[i - 1]->replaceWith(demux, true, true);
1176            }
1177        }
1178    }
1179}
1180
1181/** ------------------------------------------------------------------------------------------------------------- *
1182 * @brief topologicalSort
1183 *
1184 * After transforming the IR, we need to run this in order to always have a valid program. Each multiplex set
1185 * contains vertices corresponding to an Advance in the IR. While we know each Advance within a set is independent
1186 * w.r.t. the transitive closure of their dependencies in the IR, the position of each Advance's dependencies and
1187 * users within the IR isn't taken into consideration. Thus while there must be a valid ordering for the program,
1188 * it's not necessarily the original ordering.
1189 ** ------------------------------------------------------------------------------------------------------------- */
1190void BDDMinimizationPass::topologicalSort(PabloBlock & entry) const {
1191    // Note: not a real topological sort. I expect the original order to be very close to the resulting one.
1192    std::unordered_set<const PabloAST *> encountered;
1193    std::stack<Statement *> scope;
1194    for (Statement * stmt = entry.front(); ; ) { restart:
1195        while ( stmt ) {
1196            for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
1197                PabloAST * const op = stmt->getOperand(i);
1198                if (LLVM_LIKELY(isa<Statement>(op))) {
1199                    if (LLVM_UNLIKELY(encountered.count(op) == 0)) {
1200                        if (LLVM_UNLIKELY(isa<While>(stmt) && isa<Next>(op))) {
1201                            if (encountered.count(cast<Next>(op)->getInitial()) != 0) {
1202                                continue;
1203                            }
1204                        }
1205                        Statement * const next = stmt->getNextNode();
1206                        stmt->insertAfter(cast<Statement>(op));
1207                        stmt = next;
1208                        goto restart;
1209                    }
1210                }
1211            }
1212            if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
1213                // Set the next statement to be the first statement of the inner scope and push the
1214                // next statement of the current statement into the scope stack.
1215                const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
1216                scope.push(stmt->getNextNode());
1217                stmt = nested.front();
1218                continue;
1219            }
1220            encountered.insert(stmt);
1221            stmt = stmt->getNextNode();
1222        }
1223        if (scope.empty()) {
1224            break;
1225        }
1226        stmt = scope.top();
1227        scope.pop();
1228    }
1229}
1230
1231} // end of namespace pablo
1232
Note: See TracBrowser for help on using the repository browser.