source: icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.cpp @ 4611

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

Temporary check-in

File size: 48.1 KB
Line 
1#include "pablo_automultiplexing.hpp"
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 AutoMultiplexing::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    AutoMultiplexing 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 AutoMultiplexing::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 AutoMultiplexing::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 * AutoMultiplexing::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            bdd = input[0];
350            break;
351        case PabloAST::ClassTypeId::And:
352            bdd = And(input[0], input[1]);
353            break;
354        case PabloAST::ClassTypeId::Next:
355        case PabloAST::ClassTypeId::Or:
356            bdd = Or(input[0], input[1]);
357            break;
358        case PabloAST::ClassTypeId::Xor:
359            bdd = Xor(input[0], input[1]);
360            break;
361        case PabloAST::ClassTypeId::Not:
362            bdd = Not(input[0]);
363            break;
364        case PabloAST::ClassTypeId::Sel:
365            bdd = Ite(input[0], input[1], input[2]);
366            break;
367        case PabloAST::ClassTypeId::ScanThru:
368            // It may be possible use "Not(input[1])" for ScanThrus if we rule out the possibility
369            // of a contradition being erroneously calculated later. An example of this
370            // would be ¬(ScanThru(c,m) √ m)
371        case PabloAST::ClassTypeId::MatchStar:
372            if (LLVM_UNLIKELY(isZero(input[0]) || isZero(input[1]))) {
373                bdd = Zero();
374                break;
375            }
376        case PabloAST::ClassTypeId::Call:
377            bdd = NewVar();
378            break;
379        case PabloAST::ClassTypeId::Advance:
380            bdd = characterize(cast<Advance>(stmt), input[0]);
381            break;
382        default:
383            throw std::runtime_error("Unexpected statement type " + stmt->getName()->to_string());
384    }
385
386    assert ("Failed to generate a BDD." && (bdd));
387
388    if (LLVM_UNLIKELY(noSatisfyingAssignment(bdd))) {
389        Cudd_RecursiveDeref(mManager, bdd);
390        bdd = Zero();
391    }
392
393    return bdd;
394
395}
396
397/** ------------------------------------------------------------------------------------------------------------- *
398 * @brief characterize
399 ** ------------------------------------------------------------------------------------------------------------- */
400inline DdNode * AutoMultiplexing::characterize(Advance * adv, DdNode * input) {
401    DdNode * Ik, * Ck, * Nk;
402    if (LLVM_UNLIKELY(isZero(input))) {
403        Ik = Ck = Nk = Zero();
404    }
405    else {
406
407        Ik = input;
408        Ck = NewVar();
409        Nk = Not(Ck);
410
411        assert (mAdvanceMap.count(adv));
412
413        const auto k = mAdvanceMap[adv];
414
415        std::vector<bool> unconstrained(k , false);
416
417        // Can we use a transposed copy of the subset graph to determine an ordering of variables?
418        for (unsigned i = 0; i != k; ++i) {
419            // Have we already proven that these are unconstrained by the subset relationships?
420            if (unconstrained[i]) continue;
421            Advance * tmp = std::get<0>(mAdvance[i]);
422            // If these advances are "shifting" their values by the same amount and aren't transitively dependant ...
423            if ((adv->getOperand(1) == tmp->getOperand(1)) && (notTransitivelyDependant(i, k))) {
424                DdNode * Ii = std::get<1>(mAdvance[i]);
425                DdNode * Ni = std::get<2>(mAdvance[i]);
426                // TODO: test both Cudd_And and Cudd_bddIntersect to see which is faster
427                DdNode * const IiIk = Intersect(Ik, Ii);
428                // Is there any satisfying truth assignment? If not, these streams are mutually exclusive.
429                if (noSatisfyingAssignment(IiIk)) {
430                    assert (mCharacterizationMap.count(tmp));
431                    DdNode *& Ci = mCharacterizationMap[tmp];
432                    // Mark the i-th and k-th Advances as being mutually exclusive
433                    Ck = And(Ck, Ni);
434                    Ci = And(Ci, Nk);
435                    // If Ai ∩ Ak = ∅ and Aj ⊂ Ai, Aj ∩ Ak = ∅.
436                    graph_traits<SubsetGraph>::in_edge_iterator ei, ei_end;
437                    for (std::tie(ei, ei_end) = in_edges(i, mSubsetGraph); ei != ei_end; ++ei) {
438                        const auto j = source(*ei, mSubsetGraph);
439                        if (notTransitivelyDependant(k, j)) {
440                            Advance * adv = std::get<0>(mAdvance[j]);
441                            assert (mCharacterizationMap.count(adv));
442                            DdNode *& Cj = mCharacterizationMap[adv];
443                            DdNode * Nj = std::get<2>(mAdvance[j]);
444                            // Mark the i-th and j-th Advances as being mutually exclusive
445                            Ck = And(Ck, Nj);
446                            Cj = And(Cj, Nk);
447                            unconstrained[j] = true;
448                        }
449                    }
450                    unconstrained[i] = true;
451                }
452                else if (Ik == IiIk) {
453                    // If Ik = Ii ∩ Ik then Ik ⊂ Ii. Record this in the subset graph with the arc (k,i).
454                    // These edges will be moved into the multiplex set graph if Ai and Ak happen to be
455                    // in the same mutually exclusive set.
456                    add_edge(k, i, mSubsetGraph);
457                    // If Ak ⊂ Ai and Ai ⊂ Aj, Ak ⊂ Aj.
458                    graph_traits<SubsetGraph>::out_edge_iterator ei, ei_end;
459                    for (std::tie(ei, ei_end) = out_edges(i, mSubsetGraph); ei != ei_end; ++ei) {
460                        const auto j = target(*ei, mSubsetGraph);
461                        add_edge(k, j, mSubsetGraph);
462                        unconstrained[j] = true;
463                    }
464                    unconstrained[i] = true;
465                }
466                else if (Ii == IiIk) {
467                    // If Ii = Ii ∩ Ik then Ii ⊂ Ik. Record this in the subset graph with the arc (i,k).
468                    add_edge(i, k, mSubsetGraph);
469                    // If Ai ⊂ Ak and Aj ⊂ Ai, Aj ⊂ Ak.
470                    graph_traits<SubsetGraph>::in_edge_iterator ei, ei_end;
471                    for (std::tie(ei, ei_end) = in_edges(i, mSubsetGraph); ei != ei_end; ++ei) {
472                        const auto j = source(*ei, mSubsetGraph);
473                        add_edge(j, k, mSubsetGraph);
474                        unconstrained[j] = true;
475                    }
476                    unconstrained[i] = true;
477                }
478                Cudd_RecursiveDeref(mManager, IiIk);
479            }
480        }
481
482        for (unsigned i = 0; i != k; ++i) {
483            const Advance * const tmp = std::get<0>(mAdvance[i]);
484            // Even if these Advances are mutually exclusive, they must be in the same scope or they cannot be safely multiplexed.
485            if (!unconstrained[i] || (adv->getParent() != tmp->getParent())) {
486                // We want the constraint graph to be acyclic; since the dependencies are already in topological order,
487                // adding an arc from a lesser to greater numbered vertex won't induce a cycle.
488                add_edge(i, k, mConstraintGraph);
489            }
490        }
491    }
492
493    mAdvance.emplace_back(adv, Ik, Nk);
494
495    return Ck;
496}
497
498/** ------------------------------------------------------------------------------------------------------------- *
499 * @brief reevaluate
500 ** ------------------------------------------------------------------------------------------------------------- */
501void AutoMultiplexing::reevaluate(Next * next, DdNode * value) {
502
503    Assign * const initial = cast<Assign>(next->getOperand(0));
504
505    if (LLVM_UNLIKELY(mCharacterizationMap[initial] == value)) {
506        return;
507    }
508    mCharacterizationMap[initial] = value;
509
510
511    std::queue<PabloAST *> Q;
512    flat_set<PabloBlock *> within_scope;
513
514    for (PabloBlock * block = next->getParent(); ;) {
515        within_scope.insert(block);
516        for (PabloAST * user : block->users()) {
517            if (within_scope.insert(cast<PabloBlock>(user)).second) {
518                Q.push(user);
519            }
520        }
521        if (Q.empty()) {
522            break;
523        }
524        block = cast<PabloBlock>(Q.front());
525        Q.pop();
526    }
527
528    std::unordered_set<PabloAST *> visited;
529
530    for (Statement * current = initial; ; ) {
531        for (PabloAST * user : current->users()) {
532            if (Statement * stmt = dyn_cast<Statement>(user)) {
533                if (visited.insert(user).second && within_scope.count(stmt->getParent())) {
534                    DdNode * bdd = characterize(stmt, false);
535                    if (bdd && mCharacterizationMap[user] != bdd) {
536                        mCharacterizationMap[user] = bdd;
537                        Q.push(stmt);
538                    }
539                }
540            }
541        }
542        if (Q.empty()) {
543            break;
544        }
545        current = cast<Statement>(Q.front());
546        Q.pop();
547    }
548
549}
550
551/** ------------------------------------------------------------------------------------------------------------- *
552 * @brief minimize
553 * @param entry the entry block of the program
554 *
555 * Scan through the program using the precomputed BDDs and replace any statements with equivalent BDDs with the
556 * earlier one (assuming its in scope) and replace any contradictions with Zero.
557 ** ------------------------------------------------------------------------------------------------------------- */
558inline void AutoMultiplexing::minimize(PabloBlock & entry) {
559    SubsitutionMap baseMap;
560    baseMap.insert(Zero(), entry.createZeroes());
561    baseMap.insert(One(), entry.createOnes());
562    minimize(entry, baseMap);
563}
564
565/** ------------------------------------------------------------------------------------------------------------- *
566 * @brief minimize
567 ** ------------------------------------------------------------------------------------------------------------- */
568void AutoMultiplexing::minimize(PabloBlock & block, SubsitutionMap & parent) {
569    SubsitutionMap subsitutionMap(&parent);
570    for (Statement * stmt : block) {
571        if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
572            // Set the next statement to be the first statement of the inner scope and push the
573            // next statement of the current statement into the scope stack.
574            minimize(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(), subsitutionMap);
575            continue;
576        }
577
578        if (isa<Assign>(stmt) || isa<Next>(stmt)) {
579            continue;
580        }
581
582        DdNode * bdd = mCharacterizationMap[stmt];
583        PabloAST * replacement = subsitutionMap.test(bdd, stmt);
584        if (LLVM_UNLIKELY(replacement != nullptr)) {
585            if (LLVM_UNLIKELY(isa<Advance>(stmt))) {
586                assert (mAdvanceMap.count(stmt));
587                const auto k = mAdvanceMap[stmt];
588                const auto m = num_vertices(mConstraintGraph);
589                for (unsigned i = 0; i != m; ++i) {
590                    add_edge(k, m, mConstraintGraph);
591                }
592            }
593            Cudd_RecursiveDeref(mManager, bdd);
594            stmt->replaceWith(replacement);
595        }
596    }
597}
598
599/** ------------------------------------------------------------------------------------------------------------- *
600 * @brief notTransitivelyDependant
601 ** ------------------------------------------------------------------------------------------------------------- */
602inline bool AutoMultiplexing::notTransitivelyDependant(const ConstraintVertex i, const ConstraintVertex j) const {
603    assert (i < num_vertices(mConstraintGraph) && j < num_vertices(mConstraintGraph));
604    return (mConstraintGraph.get_edge(i, j) == 0);
605}
606
607/** ------------------------------------------------------------------------------------------------------------- *
608 * @brief CUDD wrappers
609 ** ------------------------------------------------------------------------------------------------------------- */
610
611inline DdNode * AutoMultiplexing::Zero() const {
612    return Cudd_ReadLogicZero(mManager);
613}
614
615inline DdNode * AutoMultiplexing::One() const {
616    return Cudd_ReadOne(mManager);
617}
618
619inline DdNode * AutoMultiplexing::NewVar() {
620    return Cudd_bddIthVar(mManager, mVariables++);
621}
622
623inline bool AutoMultiplexing::isZero(DdNode * const x) const {
624    return x == Zero();
625}
626
627inline DdNode * AutoMultiplexing::And(DdNode * const x, DdNode * const y) {
628    DdNode * r = Cudd_bddAnd(mManager, x, y);
629    Cudd_Ref(r);
630    return r;
631}
632
633inline DdNode * AutoMultiplexing::Intersect(DdNode * const x, DdNode * const y) {
634    DdNode * r = Cudd_bddIntersect(mManager, x, y); Cudd_Ref(r);
635    return r;
636}
637
638inline DdNode * AutoMultiplexing::Or(DdNode * const x, DdNode * const y) {
639    DdNode * r = Cudd_bddOr(mManager, x, y);
640    Cudd_Ref(r);
641    return r;
642}
643
644inline DdNode * AutoMultiplexing::Xor(DdNode * const x, DdNode * const y) {
645    DdNode * r = Cudd_bddXor(mManager, x, y);
646    Cudd_Ref(r);
647    return r;
648}
649
650inline DdNode * AutoMultiplexing::Not(DdNode * const x) const {
651    return Cudd_Not(x);
652}
653
654inline DdNode * AutoMultiplexing::Ite(DdNode * const x, DdNode * const y, DdNode * const z) {
655    DdNode * r = Cudd_bddIte(mManager, x, y, z);
656    Cudd_Ref(r);
657    return r;
658}
659
660inline bool AutoMultiplexing::noSatisfyingAssignment(DdNode * const x) {
661    return Cudd_bddLeq(mManager, x, Zero());
662}
663
664inline void AutoMultiplexing::shutdown() {
665    Cudd_Quit(mManager);
666}
667
668/** ------------------------------------------------------------------------------------------------------------- *
669 * @brief generateMultiplexSets
670 * @param RNG random number generator
671 ** ------------------------------------------------------------------------------------------------------------- */
672bool AutoMultiplexing::generateMultiplexSets(RNG & rng, unsigned k) {
673
674    using vertex_t = ConstraintGraph::vertex_descriptor;
675    using degree_t = graph_traits<ConstraintGraph>::degree_size_type;
676
677    // What if we generated a "constraint free" graph instead? By taking each connected component of it
678    // and computing the complement of it (with the same lesser to greater index ordering), we should
679    // have the same problem here but decomposed into subgraphs.
680
681    IndependentSet M, N;
682    auto remainingVerticies = num_vertices(mConstraintGraph);
683    std::vector<degree_t> D(remainingVerticies);
684    M.reserve(15);
685    N.reserve(15);
686
687    mMultiplexSetGraph = MultiplexSetGraph(remainingVerticies);
688
689    while (k) {
690
691        // Push all source nodes into the new independent set N
692        for (auto v : make_iterator_range(vertices(mConstraintGraph))) {
693            const auto d = in_degree(v, mConstraintGraph);
694            D[v] = d;
695            if (d == 0) {
696                N.push_back(v);
697            }
698        }
699
700        for (;;) {
701
702            addMultiplexSet(N, M);
703
704            if (remainingVerticies == 0) {
705                break;
706            }
707
708            assert (N.size() > 0);
709
710            // Move all of our "newly" uncovered vertices in S into the "known" set M. By always choosing
711            // at least one element from N, this will prevent us from adding the same multiplexing set again.
712            M.insert(M.end(), N.begin(), N.end()); N.clear();
713
714            do {
715                // Randomly choose a vertex in S and discard it.
716                assert (!M.empty());
717                const auto i = M.begin() + IntDistribution(0, M.size() - 1)(rng);
718                const vertex_t u = *i;
719                M.erase(i);
720                --remainingVerticies;
721                for (auto e : make_iterator_range(out_edges(u, mConstraintGraph))) {
722                    const vertex_t v = target(e, mConstraintGraph);
723                    if ((--D[v]) == 0) {
724                        N.push_back(v);
725                    }
726                }
727            }
728            while (N.empty() && remainingVerticies != 0);
729        }
730
731        if (--k == 0) {
732            break;
733        }
734
735        N.clear();
736        M.clear();
737    }
738
739    return num_vertices(mMultiplexSetGraph) > num_vertices(mConstraintGraph);
740}
741
742/** ------------------------------------------------------------------------------------------------------------- *
743 * @brief addMultiplexSet
744 * @param N an independent set
745 * @param M an independent set
746 ** ------------------------------------------------------------------------------------------------------------- */
747inline void AutoMultiplexing::addMultiplexSet(const IndependentSet & N, const IndependentSet & M) {
748
749    // At this stage, the multiplex set graph is a directed bipartite graph that is used to show relationships
750    // between the "set vertex" and its members. We obtain these from "generateMultiplexSets".
751
752    if ((N.size() + M.size()) >= 3) {
753        const auto u = add_vertex(mMultiplexSetGraph);
754        for (const auto x : N) {
755            add_edge(u, x, mMultiplexSetGraph);
756        }
757        for (const auto y : M) {
758            add_edge(u, y, mMultiplexSetGraph);
759        }
760    }
761}
762
763/** ------------------------------------------------------------------------------------------------------------- *
764 * @brief is_power_of_2
765 * @param n an integer
766 ** ------------------------------------------------------------------------------------------------------------- */
767static inline bool is_power_of_2(const size_t n) {
768    return ((n & (n - 1)) == 0) ;
769}
770
771/** ------------------------------------------------------------------------------------------------------------- *
772 * @brief log2_plus_one
773 ** ------------------------------------------------------------------------------------------------------------- */
774static inline size_t log2_plus_one(const size_t n) {
775    return std::log2<size_t>(n) + 1; // use a faster builtin function for this?
776}
777
778/** ------------------------------------------------------------------------------------------------------------- *
779 * @brief selectMultiplexSets
780 * @param RNG random number generator
781 *
782 * This algorithm is simply computes a greedy set cover. We want an exact max-weight set cover but can generate new
783 * sets by taking a subset of any existing set. With a few modifications, the greedy approach seems to work well
784 * enough but more analysis is needed.
785 ** ------------------------------------------------------------------------------------------------------------- */
786void AutoMultiplexing::selectMultiplexSets(RNG &) {
787
788
789    using OutEdgeIterator = graph_traits<MultiplexSetGraph>::out_edge_iterator;
790    using InEdgeIterator = graph_traits<MultiplexSetGraph>::in_edge_iterator;
791    using degree_t = MultiplexSetGraph::degree_size_type;
792    using vertex_t = MultiplexSetGraph::vertex_descriptor;
793
794    const size_t m = num_vertices(mConstraintGraph);
795    const size_t n = num_vertices(mMultiplexSetGraph) - m;
796
797    std::vector<degree_t> remaining(n, 0);
798    std::vector<vertex_t> chosen_set(m, 0);
799
800    for (unsigned i = 0; i != n; ++i) {
801        remaining[i] = out_degree(i + m, mMultiplexSetGraph);
802    }
803
804    for (;;) {
805
806        // Choose the set with the greatest number of vertices not already included in some other set.
807        vertex_t k = 0;
808        degree_t w = 0;
809        for (vertex_t i = 0; i != n; ++i) {
810            const degree_t r = remaining[i];
811            if (w < r) {
812                k = i;
813                w = r;
814            }
815        }
816
817        // Multiplexing requires at least 3 elements; if the best set contains fewer than 3, abort.
818        if (w < 3) {
819            break;
820        }
821
822        OutEdgeIterator ei, ei_end;
823        for (std::tie(ei, ei_end) = out_edges(k + m, mMultiplexSetGraph); ei != ei_end; ++ei) {
824            const vertex_t j = target(*ei, mMultiplexSetGraph);
825            if (chosen_set[j] == 0) {
826                chosen_set[j] = (k + m);
827                InEdgeIterator ej, ej_end;
828                for (std::tie(ej, ej_end) = in_edges(j, mMultiplexSetGraph); ej != ej_end; ++ej) {
829                    remaining[source(*ej, mMultiplexSetGraph) - m]--;
830                }
831            }
832        }
833
834        assert (remaining[k] == 0);
835
836        // If this contains 2^n elements for any n, discard the member that is most likely to be added
837        // to some future set.
838        if (is_power_of_2(w)) {
839            vertex_t j = 0;
840            degree_t w = 0;
841            for (vertex_t i = 0; i != m; ++i) {
842                if (chosen_set[i] == (k + m)) {
843                    InEdgeIterator ej, ej_end;
844                    degree_t r = 1;
845                    for (std::tie(ej, ej_end) = in_edges(i, mMultiplexSetGraph); ej != ej_end; ++ej) {
846                        // strongly prefer adding weight to unvisited sets that have more remaining vertices
847                        r += std::pow(remaining[source(*ej, mMultiplexSetGraph) - m], 2);
848                    }
849                    if (w < r) {
850                        j = i;
851                        w = r;
852                    }
853                }
854            }
855            assert (w > 0);
856            chosen_set[j] = 0;
857            InEdgeIterator ej, ej_end;
858            for (std::tie(ej, ej_end) = in_edges(j, mMultiplexSetGraph); ej != ej_end; ++ej) {
859                remaining[source(*ej, mMultiplexSetGraph) - m]++;
860            }
861        }
862    }
863
864    for (unsigned i = 0; i != m; ++i) {
865        InEdgeIterator ei, ei_end;
866        std::tie(ei, ei_end) = in_edges(i, mMultiplexSetGraph);
867        for (auto next = ei; ei != ei_end; ei = next) {
868            ++next;
869            if (source(*ei, mMultiplexSetGraph) != chosen_set[i]) {
870                remove_edge(*ei, mMultiplexSetGraph);
871            }
872        }
873    }
874
875    #ifndef NDEBUG
876    for (unsigned i = 0; i != m; ++i) {
877        assert (in_degree(i, mMultiplexSetGraph) <= 1);
878    }
879    for (unsigned i = m; i != (m + n); ++i) {
880        assert (out_degree(i, mMultiplexSetGraph) == 0 || out_degree(i, mMultiplexSetGraph) >= 3);
881    }
882    #endif
883}
884
885/** ------------------------------------------------------------------------------------------------------------- *
886 * @brief choose
887 ** ------------------------------------------------------------------------------------------------------------- */
888
889inline Statement * choose(PabloAST * x, PabloAST * y, Statement * z) {
890    return isa<Statement>(x) ? cast<Statement>(x) : (isa<Statement>(y) ? cast<Statement>(y) : z);
891}
892
893/** ------------------------------------------------------------------------------------------------------------- *
894 * @brief applySubsetConstraints
895 ** ------------------------------------------------------------------------------------------------------------- */
896void AutoMultiplexing::applySubsetConstraints() {
897
898    // When entering thus function, the multiplex set graph M is a bipartite DAG with edges denoting the set
899    // relationships of our independent sets.
900    const unsigned m = num_vertices(mConstraintGraph);
901    const unsigned n = num_vertices(mMultiplexSetGraph);
902
903    // Add in any edges from our subset constraints to M that are within the same set.
904    bool hasSubsetConstraint = false;
905
906    graph_traits<SubsetGraph>::edge_iterator ei, ei_end;
907    for (std::tie(ei, ei_end) = edges(mSubsetGraph); ei != ei_end; ++ei) {
908        const auto u = source(*ei, mSubsetGraph);
909        const auto v = target(*ei, mSubsetGraph);
910        graph_traits<MultiplexSetGraph>::in_edge_iterator ej, ej_end;
911        // If both the source and target of ei are adjacent to the same vertex, that vertex must be the
912        // "set vertex". Add the edge between the vertices.
913        for (std::tie(ej, ej_end) = in_edges(u, mMultiplexSetGraph); ej != ej_end; ++ej) {
914            auto w = target(*ej, mMultiplexSetGraph);
915            // Only check (v, w) if w is a "set vertex".
916            if (w >= (n - m) && edge(v, w, mMultiplexSetGraph).second) {
917                add_edge(u, v, mMultiplexSetGraph);
918                hasSubsetConstraint = true;
919            }
920        }
921    }
922
923    if (LLVM_UNLIKELY(hasSubsetConstraint)) {
924        // At this point, M is still a DAG but no longer bipartite. We're going to scan through the set vertices
925        // in M, and use a DFS to scan through M and eliminate any subset relationships in the AST.
926        // That way, "multiplexSelectedIndependentSets" only needs to consider muxing and demuxing of the streams.
927
928        std::vector<MultiplexSetGraph::vertex_descriptor> V;
929        std::stack<MultiplexSetGraph::vertex_descriptor> S;
930        std::queue<PabloAST *> Q;
931        BitVector D(n - m, 0);
932
933        for (auto i = m; i != n; ++i) {
934            graph_traits<MultiplexSetGraph>::out_edge_iterator ei, ei_end;
935            // For each member of a "set vertex" ...
936            std::tie(ei, ei_end) = out_edges(i, mMultiplexSetGraph);
937            for (; ei != ei_end; ++ei) {
938                const auto s = source(*ei, mMultiplexSetGraph);
939                if (out_degree(s, mMultiplexSetGraph) != 0) {
940                    // First scan through the subgraph of vertices in M dominated by s and build up the set T,
941                    // consisting of all sinks w.r.t. vertex s.
942                    auto u = s;
943                    for (;;) {
944                        graph_traits<MultiplexSetGraph>::out_edge_iterator ej, ej_end;
945                        for (std::tie(ej, ej_end) = out_edges(u, mMultiplexSetGraph); ej != ej_end; ++ej) {
946                            auto v = target(*ej, mMultiplexSetGraph);
947                            if (D.test(v)) {
948                                continue;
949                            }
950                            D.set(v);
951                            if (out_degree(v, mMultiplexSetGraph) == 0) {
952                                V.push_back(v);
953                            }
954                            else {
955                                S.push(v);
956                            }
957                        }
958                        if (S.empty()) {
959                            break;
960                        }
961                        u = S.top();
962                        S.pop();
963                    }
964                    D.clear();
965                    // Now in order for these advances to be mutually exclusive, the input to A_s must be masked
966                    // with the complement of each advance indicated by V.
967
968                    Advance * adv = std::get<0>(mAdvance[s]);
969                    PabloBlock * pb = adv->getParent();
970
971                    for (auto i : V) {
972                        Q.push(std::get<0>(mAdvance[i])->getOperand(0));
973                    }                   
974                    while (Q.size() > 1) {
975                        PabloAST * a1 = Q.front(); Q.pop();
976                        PabloAST * a2 = Q.front(); Q.pop();
977                        pb->setInsertPoint(cast<Statement>(a2));
978                        Q.push(pb->createOr(a1, a2));
979                    }
980                    assert (Q.size() == 1);
981
982                    PabloAST * const mask = pb->createNot(Q.front()); Q.pop();
983                    adv->setOperand(0, pb->createAnd(adv->getOperand(0), mask, "subset_in"));
984
985                    // Similar to the above, we're going to OR together the result of each advance,
986                    // including s. This will restore the advanced variable back to its original state.
987
988                    // Gather the original users to this advance. We'll be manipulating it shortly.
989                    Statement::Users U(adv->users());
990
991                    // Add s to V and sort the list; it'll be closer to being in topological order.
992                    V.push_back(s);
993                    std::sort(V.begin(), V.end());
994                    for (auto i : V) {
995                        Q.push(std::get<0>(mAdvance[i]));
996                    }
997                    while (Q.size() > 1) {
998                        PabloAST * a1 = Q.front(); Q.pop();
999                        PabloAST * a2 = Q.front(); Q.pop();
1000                        pb->setInsertPoint(choose(a2, a1, adv));
1001                        Q.push(pb->createOr(a1, a2));
1002                    }
1003                    assert (Q.size() == 1);
1004
1005                    PabloAST * const input = Q.front(); Q.pop();
1006                    for (PabloAST * use : U) {
1007                        if (LLVM_LIKELY(isa<Statement>(use))) {
1008                            cast<Statement>(use)->replaceUsesOfWith(adv, input);
1009                        }
1010                    }
1011
1012                    pb->setInsertPoint(pb->back());
1013
1014                    V.clear();
1015
1016                }
1017            }
1018        }
1019    }
1020}
1021
1022/** ------------------------------------------------------------------------------------------------------------- *
1023 * @brief multiplexSelectedIndependentSets
1024 ** ------------------------------------------------------------------------------------------------------------- */
1025void AutoMultiplexing::multiplexSelectedIndependentSets() const {
1026
1027    const unsigned f = num_vertices(mConstraintGraph);
1028    const unsigned l = num_vertices(mMultiplexSetGraph);
1029
1030    // Preallocate the structures based on the size of the largest multiplex set
1031    size_t max_n = 3;
1032    for (unsigned s = f; s != l; ++s) {
1033        max_n = std::max<unsigned>(max_n, out_degree(s, mMultiplexSetGraph));
1034    }
1035    const size_t max_m = log2_plus_one(max_n);
1036
1037    std::vector<MultiplexSetGraph::vertex_descriptor> I(max_n);
1038    std::vector<Advance *> V(max_n);
1039    std::vector<PabloAST *> muxed(max_m);
1040    circular_buffer<PabloAST *> Q(max_n);
1041
1042    // When entering thus function, the multiplex set graph M is a DAG with edges denoting the set
1043    // relationships of our independent sets.
1044
1045    for (unsigned s = f; s != l; ++s) {
1046        const size_t n = out_degree(s, mMultiplexSetGraph);
1047        if (n) {
1048
1049            const size_t m = log2_plus_one(n);
1050
1051            graph_traits<MultiplexSetGraph>::out_edge_iterator ei, ei_end;
1052            std::tie(ei, ei_end) = out_edges(s, mMultiplexSetGraph);
1053            for (unsigned i = 0; i != n; ++ei, ++i) {
1054                I[i] = target(*ei, mMultiplexSetGraph);
1055                assert (I[i] < mAdvance.size());
1056            }
1057            std::sort(I.begin(), I.begin() + n);
1058
1059            for (unsigned i = 0; i != n; ++i) {
1060                V[i] = std::get<0>(mAdvance[I[i]]);
1061            }
1062
1063            PabloBlock * const block = V[0]->getParent();
1064            assert (block);
1065
1066            // Sanity test to make sure every advance is in the same scope.
1067            #ifndef NDEBUG
1068            for (unsigned i = 1; i != n; ++i) {
1069                assert (I[i - 1] < I[i]);
1070                assert (V[i - 1] != V[i]);
1071                assert (V[i]->getParent() == block);
1072            }
1073            #endif
1074
1075            PabloBuilder pb(*block);
1076
1077            /// Perform n-to-m Multiplexing
1078            for (size_t j = 0; j != m; ++j) {
1079
1080                assert (Q.empty());
1081
1082                std::ostringstream prefix;
1083                prefix << "mux" << n << "to" << m;
1084                for (size_t i = 1; i <= n; ++i) {
1085                    if ((i & (static_cast<size_t>(1) << j)) != 0) {
1086                        assert (!Q.full());
1087                        PabloAST * tmp = V[i - 1]->getOperand(0); assert (tmp);
1088                        prefix << '_' << V[i - 1]->getName()->to_string();
1089                        Q.push_back(tmp);
1090                    }
1091                }
1092
1093                assert (Q.size() >= 1);
1094
1095                Advance * const adv = V[j];
1096                // TODO: figure out a way to determine whether we're creating a duplicate value below.
1097                // The expression map findOrCall ought to work conceptually but the functors method
1098                // doesn't really work anymore with the current API.
1099                while (Q.size() > 1) {
1100                    PabloAST * a1 = Q.front(); Q.pop_front(); assert (a1);
1101                    PabloAST * a2 = Q.front(); Q.pop_front(); assert (a2);
1102                    assert (!Q.full());
1103                    pb.setInsertPoint(choose(a2, a1, adv));
1104                    Q.push_back(pb.createOr(a1, a2));
1105                }
1106                assert (Q.size() == 1);
1107
1108                PabloAST * mux = Q.front(); Q.pop_front(); assert (mux);
1109                muxed[j] = pb.createAdvance(mux, adv->getOperand(1), prefix.str());
1110            }
1111
1112
1113            /// Perform m-to-n Demultiplexing
1114            // Now construct the demuxed values and replaces all the users of the original advances with them.
1115            for (size_t i = 1; i <= n; ++i) {
1116
1117                Advance * const adv = V[i - 1];
1118
1119                pb.setInsertPoint(adv);
1120                assert (Q.empty());
1121                for (size_t j = 0; j != m; ++j) {
1122                    if ((i & (static_cast<size_t>(1) << j)) == 0) {
1123                        Q.push_back(muxed[j]);
1124                    }
1125                }
1126
1127                assert (Q.size() <= m);
1128                PabloAST * neg = nullptr;
1129                if (LLVM_LIKELY(Q.size() > 0)) {
1130                    while (Q.size() > 1) {
1131                        PabloAST * a1 = Q.front(); Q.pop_front(); assert (a1);
1132                        PabloAST * a2 = Q.front(); Q.pop_front(); assert (a2);
1133                        assert (!Q.full());
1134                        Q.push_back(pb.createOr(a1, a2));
1135                    }
1136                    assert (Q.size() == 1);
1137                    neg = pb.createNot(Q.front()); Q.pop_front(); assert (neg);
1138                }
1139
1140                assert (Q.empty());
1141                for (unsigned j = 0; j != m; ++j) {
1142                    if ((i & (static_cast<unsigned>(1) << j)) != 0) {
1143                        assert (!Q.full());
1144                        Q.push_back(muxed[j]);
1145                    }
1146                }
1147
1148                assert (Q.size() <= m);
1149                assert (Q.size() >= 1);
1150
1151                while (Q.size() > 1) {
1152                    PabloAST * a1 = Q.front(); Q.pop_front(); assert (a1);
1153                    PabloAST * a2 = Q.front(); Q.pop_front(); assert (a2);
1154                    assert (!Q.full());
1155                    Q.push_back(pb.createAnd(a1, a2));
1156                }
1157
1158                assert (Q.size() == 1);
1159
1160                PabloAST * demux = Q.front(); Q.pop_front(); assert (demux);
1161                if (LLVM_LIKELY(neg != nullptr)) {
1162                    demux = pb.createAnd(demux, neg);
1163                }
1164                V[i - 1]->replaceWith(demux, true, true);
1165            }
1166        }
1167    }
1168}
1169
1170/** ------------------------------------------------------------------------------------------------------------- *
1171 * @brief topologicalSort
1172 *
1173 * After transforming the IR, we need to run this in order to always have a valid program. Each multiplex set
1174 * contains vertices corresponding to an Advance in the IR. While we know each Advance within a set is independent
1175 * w.r.t. the transitive closure of their dependencies in the IR, the position of each Advance's dependencies and
1176 * users within the IR isn't taken into consideration. Thus while there must be a valid ordering for the program,
1177 * it's not necessarily the original ordering.
1178 ** ------------------------------------------------------------------------------------------------------------- */
1179void AutoMultiplexing::topologicalSort(PabloBlock & entry) const {
1180    // Note: not a real topological sort. I expect the original order to be very close to the resulting one.
1181    std::unordered_set<const PabloAST *> encountered;
1182    std::stack<Statement *> scope;
1183    for (Statement * stmt = entry.front(); ; ) { restart:
1184        while ( stmt ) {
1185            for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
1186                PabloAST * const op = stmt->getOperand(i);
1187                if (LLVM_LIKELY(isa<Statement>(op))) {
1188                    if (LLVM_UNLIKELY(encountered.count(op) == 0)) {
1189                        if (LLVM_UNLIKELY(isa<While>(stmt) && isa<Next>(op))) {
1190                            if (encountered.count(cast<Next>(op)->getInitial()) != 0) {
1191                                continue;
1192                            }
1193                        }
1194                        Statement * const next = stmt->getNextNode();
1195                        stmt->insertAfter(cast<Statement>(op));
1196                        stmt = next;
1197                        goto restart;
1198                    }
1199                }
1200            }
1201            if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
1202                // Set the next statement to be the first statement of the inner scope and push the
1203                // next statement of the current statement into the scope stack.
1204                const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
1205                scope.push(stmt->getNextNode());
1206                stmt = nested.front();
1207                continue;
1208            }
1209            encountered.insert(stmt);
1210            stmt = stmt->getNextNode();
1211        }
1212        if (scope.empty()) {
1213            break;
1214        }
1215        stmt = scope.top();
1216        scope.pop();
1217    }
1218}
1219
1220} // end of namespace pablo
1221
Note: See TracBrowser for help on using the repository browser.