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

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

Temporary check in for demuxing simplification.

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