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

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

Minor changes to multiplexing code.

File size: 49.5 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 <unordered_map>
9#include <boost/numeric/ublas/matrix.hpp>
10#include <boost/circular_buffer.hpp>
11#include <include/simd-lib/builtins.hpp>
12#include <pablo/expression_map.hpp>
13//#include <boost/function.hpp>
14//#include <boost/graph/connected_components.hpp>
15//#include <boost/graph/filtered_graph.hpp>
16#include <boost/range/iterator_range.hpp>
17#include <cudd.h>
18#include <util.h>
19
20using namespace llvm;
21using namespace boost;
22using namespace boost::container;
23using namespace boost::numeric::ublas;
24
25// #define PRINT_DEBUG_OUTPUT
26
27#if !defined(NDEBUG) || defined(PRINT_DEBUG_OUTPUT)
28#include <iostream>
29
30using namespace pablo;
31typedef uint64_t timestamp_t;
32
33static inline timestamp_t read_cycle_counter() {
34#ifdef __GNUC__
35timestamp_t ts;
36#ifdef __x86_64__
37  unsigned int eax, edx;
38  asm volatile("rdtsc" : "=a" (eax), "=d" (edx));
39  ts = ((timestamp_t) eax) | (((timestamp_t) edx) << 32);
40#else
41  asm volatile("rdtsc\n" : "=A" (ts));
42#endif
43  return(ts);
44#endif
45#ifdef _MSC_VER
46  return __rdtsc();
47#endif
48}
49
50#define LOG(x) std::cerr << x << std::endl;
51#define RECORD_TIMESTAMP(Name) const timestamp_t Name = read_cycle_counter()
52#define LOG_GRAPH(Name, G) \
53    LOG(Name << " |V|=" << num_vertices(G) << ", |E|="  << num_edges(G) << \
54                " (" << (((double)num_edges(G)) / ((double)(num_vertices(G) * (num_vertices(G) - 1) / 2))) << ')')
55
56unsigned __count_advances(const PabloBlock & entry) {
57
58    std::stack<const Statement *> scope;
59    unsigned advances = 0;
60
61    // Scan through and collect all the advances, calls, scanthrus and matchstars ...
62    for (const Statement * stmt = entry.front(); ; ) {
63        while ( stmt ) {
64            if (isa<Advance>(stmt)) {
65                ++advances;
66            }
67            else if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
68                // Set the next statement to be the first statement of the inner scope and push the
69                // next statement of the current statement into the scope stack.
70                const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
71                scope.push(stmt->getNextNode());
72                stmt = nested.front();
73                assert (stmt);
74                continue;
75            }
76            stmt = stmt->getNextNode();
77        }
78        if (scope.empty()) {
79            break;
80        }
81        stmt = scope.top();
82        scope.pop();
83    }
84    return advances;
85}
86
87#define LOG_NUMBER_OF_ADVANCES(entry) LOG("|Advances|=" << __count_advances(entry))
88
89#else
90#define LOG(x)
91#define RECORD_TIMESTAMP(Name)
92#define LOG_GRAPH(Name, G)
93#define LOG_NUMBER_OF_ADVANCES(entry)
94#endif
95
96
97namespace pablo {
98
99bool AutoMultiplexing::optimize(const std::vector<Var *> & input, PabloBlock & entry) {
100
101    std::random_device rd;
102    const auto seed = rd();
103    RNG rng(seed);
104
105    LOG("Seed:                    " << seed);
106
107    AutoMultiplexing am;
108    RECORD_TIMESTAMP(start_initialize);
109    am.initialize(input, entry);
110    RECORD_TIMESTAMP(end_initialize);
111
112    LOG("Initialize:              " << (end_initialize - start_initialize));
113
114    LOG_NUMBER_OF_ADVANCES(entry);
115
116    RECORD_TIMESTAMP(start_characterize);
117    am.characterize(entry);
118    RECORD_TIMESTAMP(end_characterize);
119
120    LOG("Characterize:            " << (end_characterize - start_characterize));
121
122    RECORD_TIMESTAMP(start_shutdown);
123    am.shutdown();
124    RECORD_TIMESTAMP(end_shutdown);
125    LOG("Shutdown:                " << (end_shutdown - start_shutdown));
126
127    RECORD_TIMESTAMP(start_create_multiplex_graph);
128    am.createMultiplexSetGraph();
129    const bool multiplex = am.generateMultiplexSets(rng);
130    RECORD_TIMESTAMP(end_create_multiplex_graph);
131    LOG("GenerateMultiplexSets:   " << (end_create_multiplex_graph - start_create_multiplex_graph));
132
133    if (multiplex) {
134
135        RECORD_TIMESTAMP(start_mwis);
136        am.approxMaxWeightIndependentSet(rng);
137        RECORD_TIMESTAMP(end_mwis);
138        LOG("MaxWeightIndependentSet: " << (end_mwis - start_mwis));
139
140        RECORD_TIMESTAMP(start_subset_constraints);
141        am.applySubsetConstraints();
142        RECORD_TIMESTAMP(end_subset_constraints);
143        LOG("ApplySubsetConstraints:  " << (end_subset_constraints - start_subset_constraints));
144
145        RECORD_TIMESTAMP(start_select_independent_sets);
146        am.multiplexSelectedIndependentSets();
147        RECORD_TIMESTAMP(end_select_independent_sets);
148        LOG("MultiplexSelectedSets:   " << (end_select_independent_sets - start_select_independent_sets));
149
150        RECORD_TIMESTAMP(start_topological_sort);
151        am.topologicalSort(entry);
152        RECORD_TIMESTAMP(end_topological_sort);
153        LOG("TopologicalSort:         " << (end_topological_sort - start_topological_sort));
154    }
155
156    LOG_NUMBER_OF_ADVANCES(entry);
157
158    return multiplex;
159}
160
161/** ------------------------------------------------------------------------------------------------------------- *
162 * @brief initialize
163 * @param vars the input vars for this program
164 * @param entry the entry block
165 *
166 * Scan through the program to identify any advances and calls then initialize the BDD engine with
167 * the proper variable ordering.
168 ** ------------------------------------------------------------------------------------------------------------- */
169void AutoMultiplexing::initialize(const std::vector<Var *> & vars, const PabloBlock & entry) {
170
171    flat_map<const PabloAST *, unsigned> map;   
172    std::stack<const Statement *> scope;
173    unsigned complexStatements = 0; // number of statements that cannot always be categorized without generating a new variable
174
175    // Scan through and collect all the advances, calls, scanthrus and matchstars ...
176    unsigned n = 0, m = 0;
177    for (const Statement * stmt = entry.front(); ; ) {
178        while ( stmt ) {
179            ++n;
180            if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
181                // Set the next statement to be the first statement of the inner scope and push the
182                // next statement of the current statement into the scope stack.
183                const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
184                scope.push(stmt->getNextNode());
185                stmt = nested.front();
186                assert (stmt);
187                continue;
188            }
189
190            assert ("Run the Simplifer pass prior to this!" && (stmt->getNumUses() != 0 || (isa<Assign>(stmt) ? !cast<Assign>(stmt)->superfluous() : false)));
191
192            switch (stmt->getClassTypeId()) {
193                case PabloAST::ClassTypeId::Advance:                   
194                    mAdvance.push_back(const_cast<Advance*>(cast<Advance>(stmt)));
195                    map.emplace(stmt, m++);
196                case PabloAST::ClassTypeId::Call:
197                case PabloAST::ClassTypeId::ScanThru:
198                case PabloAST::ClassTypeId::MatchStar:
199                    complexStatements++;
200                    break;
201                default:
202                    break;
203            }
204            stmt = stmt->getNextNode();
205        }
206        if (scope.empty()) {
207            break;
208        }
209        stmt = scope.top();
210        scope.pop();
211    }
212
213    // Create the transitive closure matrix of graph. From this we'll construct
214    // two graphs restricted to the relationships between advances. The first will
215    // be a path graph, which is used to bypass testing for mutual exclusivity of
216    // advances that cannot be multiplexed. The second is a transitive reduction
217    // of that graph, which forms the basis of our constraint graph when deciding
218    // which advances ought to be multiplexed.
219
220    matrix<bool> G(n, m); // Let G be a matrix with n rows of m (Advance) elements
221    G.clear();
222    for (unsigned i = 0; i != m; ++i) {
223        G(i, i) = true;
224    }
225
226    n = m;
227    m = 0;
228
229    const Statement * stmt = entry.front();
230    for (;;) {
231        while ( stmt ) {
232
233            unsigned u;
234            if (isa<Advance>(stmt)) {
235                assert (mAdvance[m] == stmt);
236                u = m++;
237            }
238            else {
239                u = n++;
240                map.emplace(stmt, u);
241            }
242
243            for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
244                const PabloAST * const op = stmt->getOperand(i);
245                if (LLVM_LIKELY(isa<Statement>(op))) {
246                    const unsigned v = map[op];
247                    for (unsigned w = 0; w != m; ++w) {
248                        G(u, w) |= G(v, w);
249                    }
250                }
251            }
252            if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
253                // Set the next statement to be the first statement of the inner scope
254                // and push the next statement of the current statement into the stack.
255                const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
256                scope.push(stmt->getNextNode());
257                stmt = nested.front();
258                assert (stmt);
259                continue;
260            }
261            stmt = stmt->getNextNode();
262        }
263        if (scope.empty()) {
264            break;
265        }
266        stmt = scope.top();
267        scope.pop();
268    }
269
270    // Record the path / base constraint graph after removing any reflexive-loops.
271    // Since G is a use-def graph and we want our constraint graph to be a def-use graph,
272    // reverse the edges as we're writing them to obtain the transposed graph.
273    mConstraintGraph = ConstraintGraph(m);
274    mSubsetGraph = SubsetGraph(m);
275
276    for (unsigned i = 0; i != m; ++i) {
277        G(i, i) = false;
278        for (unsigned j = 0; j != m; ++j) {
279            if (G(i, j)) {
280                add_edge(j, i, mConstraintGraph);
281            }
282        }       
283    }
284
285    // Initialize the BDD engine ...
286    mManager = Cudd_Init((complexStatements + vars.size()), 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0);
287    Cudd_AutodynDisable(mManager);
288
289    // Map the predefined 0/1 entries
290    mCharacterizationMap.emplace(entry.createZeroes(), Zero());
291    mCharacterizationMap.emplace(entry.createOnes(), One());
292
293    // Order the variables so the input Vars are pushed to the end; they ought to
294    // be the most complex to resolve.
295    unsigned i = complexStatements;
296    for (const Var * var : vars) {
297        mCharacterizationMap.emplace(var, Cudd_bddIthVar(mManager, i++));
298    }
299}
300
301/** ------------------------------------------------------------------------------------------------------------- *
302 * @brief characterize
303 * @param vars the input vars for this program
304 *
305 * Scan through the program and iteratively compute the BDDs for each statement.
306 ** ------------------------------------------------------------------------------------------------------------- */
307void AutoMultiplexing::characterize(PabloBlock & entry) {
308
309    std::vector<std::pair<DdNode *, DdNode *>> advances; // the input BDD and the BDD variable of the i-th Advance
310    std::stack<Statement *> scope;
311    std::vector<bool> unconstrained(mAdvance.size());
312    advances.reserve(mAdvance.size());
313
314    // TODO: What if we did some minterm analysis in here? We'd need to be careful to keep the Advances properly indexed.
315
316    // Scan through and collect all the advances, calls, scanthrus and matchstars ...
317    for (Statement * stmt = entry.front(); ; ) {
318        while ( stmt ) {
319
320            if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
321                // Set the next statement to be the first statement of the inner scope and push the
322                // next statement of the current statement into the scope stack.
323                const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
324                scope.push(stmt->getNextNode());
325                stmt = nested.front();
326                continue;
327            }
328
329            DdNode * bdd = nullptr;
330            // Map our operands to the computed BDDs
331            std::array<DdNode *, 3> input;
332            for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
333                PabloAST * const op = stmt->getOperand(i);
334                if (LLVM_UNLIKELY(isa<Integer>(op) || isa<String>(op))) {
335                    continue;
336                }
337                auto f = mCharacterizationMap.find(op);
338                if (LLVM_UNLIKELY(f == mCharacterizationMap.end())) {
339                    throw std::runtime_error("Uncharacterized operand " + std::to_string(i) + " of " + stmt->getName()->to_string());
340                }
341                input[i] = f->second;
342            }
343
344            switch (stmt->getClassTypeId()) {
345                case PabloAST::ClassTypeId::Assign:
346                    bdd = input[0];
347                    break;
348                case PabloAST::ClassTypeId::And:
349                    bdd = And(input[0], input[1]);
350                    break;
351                case PabloAST::ClassTypeId::Next:
352                    // The next instruction is almost identical to an OR; however, a Next cannot be
353                    // an operand of a Statement. Instead it updates the Initial operand's value.
354                case PabloAST::ClassTypeId::Or:           
355                    bdd = Or(input[0], input[1]);
356                    break;
357                case PabloAST::ClassTypeId::Xor:
358                    bdd = Xor(input[0], input[1]);
359                    break;
360                case PabloAST::ClassTypeId::Not:
361                    bdd = Not(input[0]);
362                    break;
363                case PabloAST::ClassTypeId::Sel:
364                    bdd = Ite(input[0], input[1], input[2]);
365                    break;
366                case PabloAST::ClassTypeId::ScanThru:
367                    // It may be possible use "Not(input[1])" for ScanThrus if we rule out the possibility
368                    // of a contradition being erroneously calculated later. An example of this
369                    // would be ¬(ScanThru(c,m) √ m)
370                case PabloAST::ClassTypeId::MatchStar:
371                    if (LLVM_UNLIKELY(isZero(input[0]) || isZero(input[1]))) {
372                        bdd = Zero();
373                        break;
374                    }
375                case PabloAST::ClassTypeId::Call:
376                    bdd = Cudd_bddIthVar(mManager, mVariables++);
377                    break;
378                case PabloAST::ClassTypeId::Advance:
379                    assert (stmt == mAdvance[advances.size()]);
380                    if (LLVM_UNLIKELY(isZero(input[0]))) {
381                        bdd = Zero();
382                        advances.emplace_back(bdd, bdd);
383                    }
384                    else {
385
386                        // When we built the path graph, we constructed it in the same order; hense the row/column of
387                        // the path graph is equivalent to the index.
388
389                        // Only test pairs if they are in the same scope or one has a user in the a scope that is reachable by
390                        // the other?
391
392                        // Can we use a transposed copy of the subset graph to determine an ordering of variables?
393
394                        DdNode * const Ik = input[0];
395                        DdNode * Ck = Cudd_bddIthVar(mManager, mVariables++);
396                        DdNode * const Nk = Not(Ck);
397
398                        const unsigned k = advances.size();
399
400                        std::fill(unconstrained.begin(), unconstrained.begin() + k, false);
401
402                        for (unsigned i = 0; i != k; ++i) {
403                            // Have we already proven that these are unconstrained by the subset relationships?
404                            if (unconstrained[i]) continue;
405                            Advance * adv = mAdvance[i];
406                            // If these advances are "shifting" their values by the same amount and aren't transitively dependant ...
407                            if ((stmt->getOperand(1) == adv->getOperand(1)) && (notTransitivelyDependant(i, k))) {
408                                DdNode * Ii = std::get<0>(advances[i]);
409                                DdNode * Ni = std::get<1>(advances[i]);
410                                // TODO: test both Cudd_And and Cudd_bddIntersect to see which is faster
411                                DdNode * const IiIk = Intersect(Ik, Ii);
412                                // Is there any satisfying truth assignment? If not, these streams are mutually exclusive.
413                                if (noSatisfyingAssignment(IiIk)) {
414                                    assert (mCharacterizationMap.count(adv));
415                                    DdNode *& Ci = mCharacterizationMap[adv];
416                                    // Mark the i-th and k-th Advances as being mutually exclusive
417                                    Ck = And(Ck, Ni);
418                                    Ci = And(Ci, Nk);
419                                    // If Ai ∩ Ak = ∅ and Aj ⊂ Ai, Aj ∩ Ak = ∅.
420                                    graph_traits<SubsetGraph>::in_edge_iterator ei, ei_end;
421                                    for (std::tie(ei, ei_end) = in_edges(i, mSubsetGraph); ei != ei_end; ++ei) {
422                                        const auto j = source(*ei, mSubsetGraph);
423                                        if (notTransitivelyDependant(k, j)) {
424                                            Advance * adv = mAdvance[j];
425                                            assert (mCharacterizationMap.count(adv));
426                                            DdNode *& Cj = mCharacterizationMap[adv];
427                                            DdNode * Nj = std::get<1>(advances[j]);
428                                            // Mark the i-th and j-th Advances as being mutually exclusive
429                                            Ck = And(Ck, Nj);
430                                            Cj = And(Cj, Nk);
431                                            unconstrained[j] = true;
432                                        }
433                                    }
434                                    unconstrained[i] = true;
435                                }
436                                else if (Ik == IiIk) {
437                                    // If Ik = Ii ∩ Ik then Ik ⊂ Ii. Record this in the subset graph with the arc (k,i).
438                                    // These edges will be moved into the multiplex set graph if Ai and Ak happen to be
439                                    // in the same mutually exclusive set.
440                                    add_edge(k, i, mSubsetGraph);
441                                    // If Ak ⊂ Ai and Ai ⊂ Aj, Ak ⊂ Aj.
442                                    graph_traits<SubsetGraph>::out_edge_iterator ei, ei_end;
443                                    for (std::tie(ei, ei_end) = out_edges(i, mSubsetGraph); ei != ei_end; ++ei) {
444                                        const auto j = target(*ei, mSubsetGraph);
445                                        add_edge(k, j, mSubsetGraph);
446                                        unconstrained[j] = true;
447                                    }
448                                    unconstrained[i] = true;
449                                }
450                                else if (Ii == IiIk) {
451                                    // If Ii = Ii ∩ Ik then Ii ⊂ Ik. Record this in the subset graph with the arc (i,k).
452                                    add_edge(i, k, mSubsetGraph);
453                                    // If Ai ⊂ Ak and Aj ⊂ Ai, Aj ⊂ Ak.
454                                    graph_traits<SubsetGraph>::in_edge_iterator ei, ei_end;
455                                    for (std::tie(ei, ei_end) = in_edges(i, mSubsetGraph); ei != ei_end; ++ei) {
456                                        const auto j = source(*ei, mSubsetGraph);
457                                        add_edge(j, k, mSubsetGraph);
458                                        unconstrained[j] = true;
459                                    }
460                                    unconstrained[i] = true;
461                                }
462                                Cudd_RecursiveDeref(mManager, IiIk);
463                            }
464                        }
465
466                        for (unsigned i = 0; i != k; ++i) {
467                            const Advance * const adv = mAdvance[i];
468                            // Even if these Advances are mutually exclusive, they must be in the same scope or they cannot be safely multiplexed.
469                            if (!unconstrained[i] || (stmt->getParent() != adv->getParent())) {
470                                // We want the constraint graph to be acyclic; since the dependencies are already in topological order,
471                                // adding an arc from a lesser to greater numbered vertex won't induce a cycle.
472                                add_edge(i, k, mConstraintGraph);
473                            }
474                        }
475
476                        // Append this advance to the list of known advances. Both its input BDD and the Advance variable are stored in
477                        // the list to eliminate the need for searching for it.
478                        advances.emplace_back(Ik, Nk);
479                        bdd = Ck;
480                    }
481                    break;
482                default:
483                    throw std::runtime_error("Unexpected statement type " + stmt->getName()->to_string());
484            }
485            assert ("Failed to generate a BDD." && (bdd));
486            mCharacterizationMap[stmt] = bdd;
487            if (LLVM_UNLIKELY(noSatisfyingAssignment(bdd))) {
488                if (!isa<Assign>(stmt)) {
489                    Cudd_RecursiveDeref(mManager, bdd);
490                    mCharacterizationMap[stmt] = Zero();
491                    stmt = stmt->replaceWith(entry.createZeroes());
492                    continue;
493                }
494            }
495            stmt = stmt->getNextNode();
496        }
497
498        if (scope.empty()) {
499            break;
500        }
501        stmt = scope.top();
502        scope.pop();
503    }
504}
505
506/** ------------------------------------------------------------------------------------------------------------- *
507 * @brief notTransitivelyDependant
508 ** ------------------------------------------------------------------------------------------------------------- */
509inline bool AutoMultiplexing::notTransitivelyDependant(const PathGraph::vertex_descriptor i, const PathGraph::vertex_descriptor j) const {
510    return (mConstraintGraph.get_edge(i, j) == 0);
511}
512
513/** ------------------------------------------------------------------------------------------------------------- *
514 * @brief CUDD wrappers
515 ** ------------------------------------------------------------------------------------------------------------- */
516
517inline DdNode * AutoMultiplexing::Zero() const {
518    return Cudd_ReadLogicZero(mManager);
519}
520
521inline DdNode * AutoMultiplexing::One() const {
522    return Cudd_ReadOne(mManager);
523}
524
525inline bool AutoMultiplexing::isZero(DdNode * const x) const {
526    return x == Zero();
527}
528
529inline DdNode * AutoMultiplexing::And(DdNode * const x, DdNode * const y) {
530    DdNode * r = Cudd_bddAnd(mManager, x, y);
531    Cudd_Ref(r);
532    return r;
533}
534
535inline DdNode * AutoMultiplexing::Intersect(DdNode * const x, DdNode * const y) {
536    DdNode * r = Cudd_bddIntersect(mManager, x, y); Cudd_Ref(r);
537    return r;
538}
539
540inline DdNode * AutoMultiplexing::Or(DdNode * const x, DdNode * const y) {
541    DdNode * r = Cudd_bddOr(mManager, x, y);
542    Cudd_Ref(r);
543    return r;
544}
545
546inline DdNode * AutoMultiplexing::Xor(DdNode * const x, DdNode * const y) {
547    DdNode * r = Cudd_bddXor(mManager, x, y);
548    Cudd_Ref(r);
549    return r;
550}
551
552inline DdNode * AutoMultiplexing::Not(DdNode * const x) const {
553    return Cudd_Not(x);
554}
555
556inline DdNode * AutoMultiplexing::Ite(DdNode * const x, DdNode * const y, DdNode * const z) {
557    DdNode * r = Cudd_bddIte(mManager, x, y, z);
558    Cudd_Ref(r);
559    return r;
560}
561
562inline bool AutoMultiplexing::noSatisfyingAssignment(DdNode * const x) {
563    return Cudd_bddLeq(mManager, x, Zero());
564}
565
566inline void AutoMultiplexing::shutdown() {
567    Cudd_Quit(mManager);
568}
569
570/** ------------------------------------------------------------------------------------------------------------- *
571 * @brief createMultiplexSetGraph
572 ** ------------------------------------------------------------------------------------------------------------- */
573void AutoMultiplexing::createMultiplexSetGraph() {
574    mMultiplexSetGraph = MultiplexSetGraph(num_vertices(mConstraintGraph));
575}
576
577/** ------------------------------------------------------------------------------------------------------------- *
578 * @brief generateMultiplexSets
579 * @param RNG random number generator
580 ** ------------------------------------------------------------------------------------------------------------- */
581bool AutoMultiplexing::generateMultiplexSets(RNG & rng) {
582
583    using Vertex = ConstraintGraph::vertex_descriptor;
584    using DegreeType = graph_traits<ConstraintGraph>::degree_size_type;
585
586    // What if we generated a "constraint free" graph instead? By taking each connected component of it
587    // and computing the complement of it (with the same lesser to greater index ordering), we should
588    // have the same problem here but decomposed into subgraphs.
589
590    IndependentSet M, N;
591    auto remainingVerticies = num_vertices(mConstraintGraph);
592    std::vector<DegreeType> D(remainingVerticies);
593    M.reserve(15);
594    N.reserve(15);
595
596    // Push all source nodes into the new independent set N
597    for (auto v : make_iterator_range(vertices(mConstraintGraph))) {
598        const auto d = in_degree(v, mConstraintGraph);
599        D[v] = d;
600        if (d == 0) {
601            N.push_back(v);
602        }
603    }
604
605    for (;;) {
606
607        // If we have at least 3 vertices in our two sets, try adding them to our multiplexing set.
608        if ((N.size() + M.size()) >= 3) {
609            addMultiplexSet(N, M);
610        }
611
612        if (remainingVerticies == 0) {
613            break;
614        }
615
616        // Move all of our "newly" uncovered vertices in S into the "known" set M. By always choosing
617        // at least one element from N, this will prevent us from adding the same multiplexing set again.
618        M.insert(M.end(), N.begin(), N.end()); N.clear();
619
620        do {
621            // Randomly choose a vertex in S and discard it.
622            assert (!M.empty());
623            const auto i = M.begin() + RNGDistribution(0, M.size() - 1)(rng);
624            const Vertex u = *i;
625            M.erase(i);
626            --remainingVerticies;
627            for (auto e : make_iterator_range(out_edges(u, mConstraintGraph))) {
628                const Vertex v = target(e, mConstraintGraph);
629                if ((--D[v]) == 0) {
630                    N.push_back(v);
631                }
632            }
633        }
634        while (N.empty() && remainingVerticies != 0);
635    }
636
637    return num_vertices(mMultiplexSetGraph) > num_vertices(mConstraintGraph);
638}
639
640/** ------------------------------------------------------------------------------------------------------------- *
641 * @brief is_power_of_2
642 * @param n an integer
643 ** ------------------------------------------------------------------------------------------------------------- */
644static inline bool is_power_of_2(const size_t n) {
645    return ((n & (n - 1)) == 0) ;
646}
647
648/** ------------------------------------------------------------------------------------------------------------- *
649 * @brief addMultiplexSet
650 * @param N an independent set
651 * @param S an independent set
652 ** ------------------------------------------------------------------------------------------------------------- */
653inline void AutoMultiplexing::addMultiplexSet(const IndependentSet & N, const IndependentSet & M) {
654
655    // At this stage, the multiplex set graph is a directed bipartite graph that is used to show relationships
656    // between the "set vertex" and its members. We obtain these from "generateMultiplexSets".
657
658    // Note: this computes (∑i=1 to |N| C(|N|,i)) * [1 + (∑i=1 to |M| C(|M|,i))] = (2^|N| - 1) * (2^|M|) combinations.
659
660    ChosenSet S;
661    for (int i = 0; i < N.size(); ++i) {
662        S.insert(N[i]);
663        addMultiplexSet(N, i + 1, M, 0, S);
664        S.erase(S.find(N[i]));
665    }
666}
667
668/** ------------------------------------------------------------------------------------------------------------- *
669 * @brief addMultiplexSet
670 * @param N an independent set
671 * @param S an independent set
672 ** ------------------------------------------------------------------------------------------------------------- */
673void AutoMultiplexing::addMultiplexSet(const IndependentSet & N, const int i,
674                                       const IndependentSet & M, const int j,
675                                       ChosenSet & S) {
676
677    // TODO: Instead of building a graph, construct a trie of all members.
678
679    // Add S to the multiplex set if |S| >= 3 and not equal to 2^n for any n.
680    if (S.size() >= 3 && !is_power_of_2(S.size())) {
681        const auto v = add_vertex(mMultiplexSetGraph);
682        for (auto u : S) {
683            add_edge(v, u, mMultiplexSetGraph);
684        }
685    }
686
687    for (int ii = i; ii < N.size(); ++ii) {
688        S.insert(N[ii]);
689        addMultiplexSet(N, ii + 1, M, j, S);
690        S.erase(S.find(N[ii]));
691    }
692
693    for (int jj = j; jj < M.size(); ++jj) {
694        S.insert(M[jj]);
695        addMultiplexSet(N, i + 1, M, jj + 1, S);
696        S.erase(S.find(M[jj]));
697    }
698
699}
700
701/** ------------------------------------------------------------------------------------------------------------- *
702 * @brief cardinalityWeight
703 * @param x the input number
704 *
705 * Returns 0 if x < 0; otherwise x^2.
706 ** ------------------------------------------------------------------------------------------------------------- */
707static inline ssize_t cardinalityWeight(const ssize_t x) {
708    const ssize_t xx = std::max<ssize_t>(x, 0);
709    return xx * xx;
710}
711
712/** ------------------------------------------------------------------------------------------------------------- *
713 * @brief approxMaxWeightIndependentSet
714 * @param RNG random number generator
715 ** ------------------------------------------------------------------------------------------------------------- */
716void AutoMultiplexing::approxMaxWeightIndependentSet(RNG & rng) {
717
718    // Compute our independent set graph from our multiplex set graph; effectively it's the graph resulting
719    // from contracting one advance node edge with an adjacent vertex
720
721    const unsigned m = num_vertices(mConstraintGraph);
722    const unsigned n = num_vertices(mMultiplexSetGraph) - m;
723
724    IndependentSetGraph G(n);
725
726    MultiplexSetGraph::vertex_descriptor i = m;
727    graph_traits<IndependentSetGraph>::vertex_iterator vi, vi_end;
728    for (std::tie(vi, vi_end) = vertices(G); vi != vi_end; ++vi, ++i) {
729        G[*vi] = std::make_pair(out_degree(i, mMultiplexSetGraph), 0);
730    }
731
732    // Let M be mMultiplexSetGraph. Each vertex in G corresponds to a set vertex in M.
733    // If an advance vertex in M (i.e., one of the first m vertices of M) is adjacent
734    // to two or more set vertices, add an edge between the corresponding vertices in G.
735    // I.e., make all vertices in G adjacent if their corresponding sets intersect.
736
737    for (i = 0; i != m; ++i) {
738        if (in_degree(i, mMultiplexSetGraph) > 1) {
739            graph_traits<MultiplexSetGraph>::in_edge_iterator ei_begin, ei_end;
740            std::tie(ei_begin, ei_end) = in_edges(i, mMultiplexSetGraph);
741            for (auto ei = ei_begin; ei != ei_end; ++ei) {
742                for (auto ej = ei_begin; ej != ei; ++ej) {
743                    // Note: ei and ej are incoming edges. The source is the set vertex,
744                    add_edge(source(*ei, mMultiplexSetGraph) - m, source(*ej, mMultiplexSetGraph) - m, G);
745                }
746            }
747        }
748    }
749
750    boost::container::flat_set<IndependentSetGraph::vertex_descriptor> indices;
751    indices.reserve(n);
752
753    for (std::tie(vi, vi_end) = vertices(G); vi != vi_end; ++vi, ++i) {
754        int neighbourhoodWeight = 0;
755        int neighbours = 1;
756        graph_traits<IndependentSetGraph>::adjacency_iterator ai, ai_end;
757        for (std::tie(ai, ai_end) = adjacent_vertices(*vi, G); ai != ai_end; ++ai) {
758            ++neighbours;
759            neighbourhoodWeight += std::get<0>(G[*ai]);
760        }
761        std::get<1>(G[*vi]) = (std::get<0>(G[*vi]) * neighbours) - neighbourhoodWeight;
762        indices.insert(*vi);
763    }
764    // Using WMIN from "A note on greedy algorithms for the maximum weighted independent set problem"
765    // (Note: look into minimum independent dominating set algorithms. It fits better with the ceil log2 + subset cost model.)
766
767    while (!indices.empty()) {
768
769        // Select a vertex vi whose weight as greater than the average weight of its neighbours ...
770        ssize_t totalWeight = 0;
771        for (auto vi = indices.begin(); vi != indices.end(); ++vi) {           
772            const ssize_t prevWeight = totalWeight;
773            totalWeight += cardinalityWeight(std::get<1>(G[*vi]));
774            assert (totalWeight >= prevWeight);
775        }
776
777        IndependentSetGraph::vertex_descriptor v = 0;
778        ssize_t remainingWeight = RNGDistribution(0, totalWeight - 1)(rng);
779        assert (remainingWeight >= 0 && remainingWeight < totalWeight);
780        for (auto vi = indices.begin(); vi != indices.end(); ++vi) {           
781            remainingWeight -= cardinalityWeight(std::get<1>(G[*vi]));
782            if (remainingWeight < 0) {
783                v = *vi;
784                break;
785            }
786        }
787        assert (remainingWeight < 0);
788
789        // Note: by clearing the adjacent set vertices from the multiplex set graph, this will effectively
790        // choose the set refered to by vi as one of our chosen independent sets.
791
792        for (auto u : make_iterator_range(adjacent_vertices(v, G))) {
793            assert (indices.count(u));
794            indices.erase(indices.find(u));
795            clear_out_edges(u + m, mMultiplexSetGraph);
796            const auto Wj = std::get<0>(G[u]);
797            for (auto w : make_iterator_range(adjacent_vertices(u, G))) {
798
799                // Let Vi be vertex i, Wi = weight of Vi, Di = degree of Vi, Ni = sum of the weights of vertices
800                // adjacent to Vi, and Ai be the weight difference of Vi w.r.t. its neighbours. Initially,
801
802                //     Ai = (Wi * (Di + 1)) - Ni
803
804                // Suppose Vj is removed from G and is adjacent to Vi. Then,
805
806                //    Ai' = (Wi * (Di + 1 - 1)) - (Ni - Wj) = (Ai - Wi + Wj)
807
808                const auto Wi = std::get<0>(G[w]);
809                auto & Ai = std::get<1>(G[w]);
810                Ai = Ai - Wi + Wj;
811                remove_edge(u, w, G);
812            }
813            remove_edge(v, u, G);
814        }
815        indices.erase(indices.find(v));
816    }
817
818    #ifndef NDEBUG
819    for (unsigned i = 0; i != m; ++i) {
820        assert (in_degree(i, mMultiplexSetGraph) <= 1);
821    }
822    for (unsigned i = m; i != (m + n); ++i) {
823        assert (out_degree(i, mMultiplexSetGraph) == 0 || out_degree(i, mMultiplexSetGraph) >= 3);
824    }
825    #endif
826}
827
828/** ------------------------------------------------------------------------------------------------------------- *
829 * @brief choose
830 ** ------------------------------------------------------------------------------------------------------------- */
831
832inline Statement * choose(PabloAST * x, PabloAST * y, Statement * z) {
833    return isa<Statement>(x) ? cast<Statement>(x) : (isa<Statement>(y) ? cast<Statement>(y) : z);
834}
835
836/** ------------------------------------------------------------------------------------------------------------- *
837 * @brief applySubsetConstraints
838 ** ------------------------------------------------------------------------------------------------------------- */
839void AutoMultiplexing::applySubsetConstraints() {
840
841    // When entering thus function, the multiplex set graph M is a bipartite DAG with edges denoting the set
842    // relationships of our independent sets.
843    const unsigned m = num_vertices(mConstraintGraph);
844    const unsigned n = num_vertices(mMultiplexSetGraph);
845
846    // Add in any edges from our subset constraints to M that are within the same set.
847    bool hasSubsetConstraint = false;
848
849    graph_traits<SubsetGraph>::edge_iterator ei, ei_end;
850    for (std::tie(ei, ei_end) = edges(mSubsetGraph); ei != ei_end; ++ei) {
851        const auto u = source(*ei, mSubsetGraph);
852        const auto v = target(*ei, mSubsetGraph);
853        graph_traits<MultiplexSetGraph>::in_edge_iterator ej, ej_end;
854        // If both the source and target of ei are adjacent to the same vertex, that vertex must be the
855        // "set vertex". Add the edge between the vertices.
856        for (std::tie(ej, ej_end) = in_edges(u, mMultiplexSetGraph); ej != ej_end; ++ej) {
857            auto w = target(*ej, mMultiplexSetGraph);
858            // Only check (v, w) if w is a "set vertex".
859            if (w >= (n - m) && edge(v, w, mMultiplexSetGraph).second) {
860                add_edge(u, v, mMultiplexSetGraph);
861                hasSubsetConstraint = true;
862            }
863        }
864    }
865
866    if (LLVM_UNLIKELY(hasSubsetConstraint)) {
867        // At this point, M is still a DAG but no longer bipartite. We're going to scan through the set vertices
868        // in M, and use a DFS to scan through M and eliminate any subset relationships in the AST.
869        // That way, "multiplexSelectedIndependentSets" only needs to consider muxing and demuxing of the streams.
870
871        std::vector<MultiplexSetGraph::vertex_descriptor> V;
872        std::stack<MultiplexSetGraph::vertex_descriptor> S;
873        std::queue<PabloAST *> Q;
874        BitVector D(n - m, 0);
875
876        for (auto i = m; i != n; ++i) {
877            graph_traits<MultiplexSetGraph>::out_edge_iterator ei, ei_end;
878            // For each member of a "set vertex" ...
879            std::tie(ei, ei_end) = out_edges(i, mMultiplexSetGraph);
880            for (; ei != ei_end; ++ei) {
881                const auto s = source(*ei, mMultiplexSetGraph);
882                if (out_degree(s, mMultiplexSetGraph) != 0) {
883                    // First scan through the subgraph of vertices in M dominated by s and build up the set T,
884                    // consisting of all sinks w.r.t. vertex s.
885                    auto u = s;
886                    for (;;) {
887                        graph_traits<MultiplexSetGraph>::out_edge_iterator ej, ej_end;
888                        for (std::tie(ej, ej_end) = out_edges(u, mMultiplexSetGraph); ej != ej_end; ++ej) {
889                            auto v = target(*ej, mMultiplexSetGraph);
890                            if (D.test(v)) {
891                                continue;
892                            }
893                            D.set(v);
894                            if (out_degree(v, mMultiplexSetGraph) == 0) {
895                                V.push_back(v);
896                            }
897                            else {
898                                S.push(v);
899                            }
900                        }
901                        if (S.empty()) {
902                            break;
903                        }
904                        u = S.top();
905                        S.pop();
906                    }
907                    D.clear();
908                    // Now in order for these advances to be mutually exclusive, the input to A_s must be masked
909                    // with the complement of each advance indicated by V.
910
911                    Advance * adv = mAdvance[s];
912                    PabloBlock * pb = adv->getParent();
913
914                    for (auto i : V) {
915                        Q.push(mAdvance[i]->getOperand(0));
916                    }                   
917                    while (Q.size() > 1) {
918                        PabloAST * a1 = Q.front(); Q.pop();
919                        PabloAST * a2 = Q.front(); Q.pop();
920                        pb->setInsertPoint(cast<Statement>(a2));
921                        Q.push(pb->createOr(a1, a2));
922                    }
923                    assert (Q.size() == 1);
924
925                    PabloAST * const mask = pb->createNot(Q.front()); Q.pop();
926                    adv->setOperand(0, pb->createAnd(adv->getOperand(0), mask, "subset_in"));
927
928                    // Similar to the above, we're going to OR together the result of each advance,
929                    // including s. This will restore the advanced variable back to its original state.
930
931                    // Gather the original users to this advance. We'll be manipulating it shortly.
932                    Statement::Users U(adv->users());
933
934                    // Add s to V and sort the list; it'll be closer to being in topological order.
935                    V.push_back(s);
936                    std::sort(V.begin(), V.end());
937                    for (auto i : V) {
938                        Q.push(mAdvance[i]);
939                    }
940                    while (Q.size() > 1) {
941                        PabloAST * a1 = Q.front(); Q.pop();
942                        PabloAST * a2 = Q.front(); Q.pop();
943                        pb->setInsertPoint(choose(a2, a1, adv));
944                        Q.push(pb->createOr(a1, a2));
945                    }
946                    assert (Q.size() == 1);
947
948                    PabloAST * const input = Q.front(); Q.pop();
949                    for (PabloAST * use : U) {
950                        if (LLVM_LIKELY(isa<Statement>(use))) {
951                            cast<Statement>(use)->replaceUsesOfWith(adv, input);
952                        }
953                    }
954
955                    pb->setInsertPoint(pb->back());
956
957                    V.clear();
958
959                }
960            }
961        }
962    }
963}
964
965/** ------------------------------------------------------------------------------------------------------------- *
966 * @brief log2_plus_one
967 ** ------------------------------------------------------------------------------------------------------------- */
968static inline size_t log2_plus_one(const size_t n) {
969    return std::log2<size_t>(n) + 1; // use a faster builtin function for this?
970}
971
972/** ------------------------------------------------------------------------------------------------------------- *
973 * @brief multiplexSelectedIndependentSets
974 ** ------------------------------------------------------------------------------------------------------------- */
975void AutoMultiplexing::multiplexSelectedIndependentSets() const {
976
977    const unsigned f = num_vertices(mConstraintGraph);
978    const unsigned l = num_vertices(mMultiplexSetGraph);
979
980    // Preallocate the structures based on the size of the largest multiplex set
981    size_t max_n = 3;
982    for (unsigned s = f; s != l; ++s) {
983        max_n = std::max<unsigned>(max_n, out_degree(s, mMultiplexSetGraph));
984    }
985    const size_t max_m = log2_plus_one(max_n);
986
987    std::vector<MultiplexSetGraph::vertex_descriptor> I(max_n);
988    std::vector<Advance *> V(max_n);
989    std::vector<PabloAST *> muxed(max_m);
990    circular_buffer<PabloAST *> Q(max_n);
991
992    // When entering thus function, the multiplex set graph M is a DAG with edges denoting the set
993    // relationships of our independent sets.
994
995    for (unsigned s = f; s != l; ++s) {
996        const size_t n = out_degree(s, mMultiplexSetGraph);
997        if (n) {
998
999            const size_t m = log2_plus_one(n);
1000
1001            graph_traits<MultiplexSetGraph>::out_edge_iterator ei, ei_end;
1002            std::tie(ei, ei_end) = out_edges(s, mMultiplexSetGraph);
1003            for (unsigned i = 0; i != n; ++ei, ++i) {
1004                I[i] = target(*ei, mMultiplexSetGraph);
1005                assert (I[i] < mAdvance.size());
1006            }
1007            std::sort(I.begin(), I.begin() + n);
1008
1009            for (unsigned i = 0; i != n; ++i) {
1010                V[i] = mAdvance[I[i]];
1011            }
1012
1013            PabloBlock * const pb = V[0]->getParent();
1014            assert (pb);
1015
1016            // Sanity test to make sure every advance is in the same scope.
1017            #ifndef NDEBUG
1018            for (unsigned i = 1; i != n; ++i) {
1019                assert (I[i - 1] < I[i]);
1020                assert (V[i - 1] != V[i]);
1021                assert (V[i]->getParent() == pb);
1022            }
1023            #endif
1024
1025            /// Perform n-to-m Multiplexing
1026            for (size_t j = 0; j != m; ++j) {
1027
1028                assert (Q.empty());
1029
1030                std::ostringstream prefix;
1031
1032                prefix << "mux" << n << "to" << m;
1033                for (size_t i = 1; i <= n; ++i) {
1034                    if ((i & (static_cast<size_t>(1) << j)) != 0) {
1035                        assert (!Q.full());
1036                        PabloAST * tmp = V[i - 1]->getOperand(0); assert (tmp);
1037                        prefix << '_' << V[i - 1]->getName()->to_string();
1038                        Q.push_back(tmp);
1039                    }
1040                }
1041
1042                assert (Q.size() >= 1);
1043
1044                Advance * const adv = V[j];
1045                // TODO: figure out a way to determine whether we're creating a duplicate value below.
1046                // The expression map findOrCall ought to work conceptually but the functors method
1047                // doesn't really work anymore with the current API.
1048                while (Q.size() > 1) {
1049                    PabloAST * a1 = Q.front(); Q.pop_front(); assert (a1);
1050                    PabloAST * a2 = Q.front(); Q.pop_front(); assert (a2);
1051                    assert (!Q.full());
1052                    pb->setInsertPoint(choose(a2, a1, adv));
1053                    Q.push_back(pb->createOr(a1, a2));
1054                }
1055                assert (Q.size() == 1);
1056
1057                PabloAST * mux = Q.front(); Q.pop_front(); assert (mux);
1058                muxed[j] = pb->createAdvance(mux, adv->getOperand(1), prefix.str());
1059            }
1060
1061
1062            /// Perform m-to-n Demultiplexing
1063            // Now construct the demuxed values and replaces all the users of the original advances with them.
1064            for (size_t i = 1; i <= n; ++i) {
1065
1066                Advance * const adv = V[i - 1];
1067
1068                pb->setInsertPoint(adv);
1069
1070                assert (Q.empty());
1071                for (size_t j = 0; j != m; ++j) {
1072                    if ((i & (static_cast<size_t>(1) << j)) == 0) {
1073                        Q.push_back(muxed[j]);
1074                    }
1075                }
1076
1077                assert (Q.size() <= m);
1078                PabloAST * neg = nullptr;
1079                if (LLVM_LIKELY(Q.size() > 0)) {
1080                    while (Q.size() > 1) {
1081                        PabloAST * a1 = Q.front(); Q.pop_front(); assert (a1);
1082                        PabloAST * a2 = Q.front(); Q.pop_front(); assert (a2);
1083                        assert (!Q.full());
1084                        Q.push_back(pb->createOr(a1, a2));
1085                    }
1086                    assert (Q.size() == 1);
1087                    neg = pb->createNot(Q.front()); Q.pop_front(); assert (neg);
1088                }
1089
1090                assert (Q.empty());
1091                for (unsigned j = 0; j != m; ++j) {
1092                    if ((i & (static_cast<unsigned>(1) << j)) != 0) {
1093                        assert (!Q.full());
1094                        Q.push_back(muxed[j]);
1095                    }
1096                }
1097
1098                assert (Q.size() <= m);
1099                assert (Q.size() >= 1);
1100
1101                while (Q.size() > 1) {
1102                    PabloAST * a1 = Q.front(); Q.pop_front(); assert (a1);
1103                    PabloAST * a2 = Q.front(); Q.pop_front(); assert (a2);
1104                    assert (!Q.full());
1105                    Q.push_back(pb->createAnd(a1, a2));
1106                }
1107
1108                assert (Q.size() == 1);
1109
1110                PabloAST * demux = Q.front(); Q.pop_front(); assert (demux);
1111                if (LLVM_LIKELY(neg != nullptr)) {
1112                    demux = pb->createAnd(demux, neg);
1113                }
1114                V[i - 1]->replaceWith(demux, true, true);
1115            }
1116        }
1117    }
1118}
1119
1120/** ------------------------------------------------------------------------------------------------------------- *
1121 * @brief topologicalSort
1122 *
1123 * After transforming the IR, we need to run this in order to always have a valid program. Each multiplex set
1124 * contains vertices corresponding to an Advance in the IR. While we know each Advance within a set is independent
1125 * w.r.t. the transitive closure of their dependencies in the IR, the position of each Advance's dependencies and
1126 * users within the IR isn't taken into consideration. Thus while there must be a valid ordering for the program,
1127 * it's not necessarily the original ordering.
1128 ** ------------------------------------------------------------------------------------------------------------- */
1129void AutoMultiplexing::topologicalSort(PabloBlock & entry) const {
1130    // Note: not a real topological sort. I expect the original order to be very close to the resulting one.
1131    std::unordered_set<const PabloAST *> encountered;
1132    std::stack<Statement *> scope;
1133    for (Statement * stmt = entry.front(); ; ) { restart:
1134        while ( stmt ) {
1135            for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
1136                PabloAST * const op = stmt->getOperand(i);
1137                if (LLVM_LIKELY(isa<Statement>(op))) {
1138                    if (LLVM_UNLIKELY(encountered.count(op) == 0)) {
1139                        if (LLVM_UNLIKELY(isa<While>(stmt) && isa<Next>(op))) {
1140                            if (encountered.count(cast<Next>(op)->getInitial()) != 0) {
1141                                continue;
1142                            }
1143                        }
1144                        Statement * const next = stmt->getNextNode();
1145                        stmt->insertAfter(cast<Statement>(op));
1146                        stmt = next;
1147                        goto restart;
1148                    }
1149                }
1150            }
1151            if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
1152                // Set the next statement to be the first statement of the inner scope and push the
1153                // next statement of the current statement into the scope stack.
1154                const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
1155                scope.push(stmt->getNextNode());
1156                stmt = nested.front();
1157                continue;
1158            }
1159            encountered.insert(stmt);
1160            stmt = stmt->getNextNode();
1161        }
1162        if (scope.empty()) {
1163            break;
1164        }
1165        stmt = scope.top();
1166        scope.pop();
1167    }
1168}
1169
1170} // end of namespace pablo
1171
Note: See TracBrowser for help on using the repository browser.