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

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

Temporary check-in

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