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

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

Temporary check-in.

File size: 70.7 KB
Line 
1#include "pablo_automultiplexing.hpp"
2#include <include/simd-lib/builtins.hpp>
3#include <pablo/builder.hpp>
4#include <pablo/function.h>
5#include <pablo/printer_pablos.h>
6#include <boost/container/flat_set.hpp>
7#include <boost/numeric/ublas/matrix.hpp>
8#include <boost/circular_buffer.hpp>
9#include <boost/graph/topological_sort.hpp>
10#include <boost/range/iterator_range.hpp>
11#include <llvm/ADT/BitVector.h>
12#include <cudd.h>
13#include <cuddInt.h>
14#include <util.h>
15#include <stack>
16#include <queue>
17#include <unordered_set>
18
19using namespace llvm;
20using namespace boost;
21using namespace boost::container;
22using namespace boost::numeric::ublas;
23
24// #define PRINT_DEBUG_OUTPUT
25
26#if !defined(NDEBUG) && !defined(PRINT_DEBUG_OUTPUT)
27#define PRINT_DEBUG_OUTPUT
28#endif
29
30#ifdef PRINT_DEBUG_OUTPUT
31
32#include <iostream>
33
34using namespace pablo;
35typedef uint64_t timestamp_t;
36
37static inline timestamp_t read_cycle_counter() {
38#ifdef __GNUC__
39timestamp_t ts;
40#ifdef __x86_64__
41  unsigned int eax, edx;
42  asm volatile("rdtsc" : "=a" (eax), "=d" (edx));
43  ts = ((timestamp_t) eax) | (((timestamp_t) edx) << 32);
44#else
45  asm volatile("rdtsc\n" : "=A" (ts));
46#endif
47  return(ts);
48#endif
49#ifdef _MSC_VER
50  return __rdtsc();
51#endif
52}
53
54#define LOG(x) std::cerr << x << std::endl;
55#define RECORD_TIMESTAMP(Name) const timestamp_t Name = read_cycle_counter()
56#define LOG_GRAPH(Name, G) \
57    LOG(Name << " |V|=" << num_vertices(G) << ", |E|="  << num_edges(G) << \
58                " (" << (((double)num_edges(G)) / ((double)(num_vertices(G) * (num_vertices(G) - 1) / 2))) << ')')
59
60unsigned __count_advances(const PabloBlock & entry) {
61
62    std::stack<const Statement *> scope;
63    unsigned advances = 0;
64
65    // Scan through and collect all the advances, calls, scanthrus and matchstars ...
66    for (const Statement * stmt = entry.front(); ; ) {
67        while ( stmt ) {
68            if (isa<Advance>(stmt)) {
69                ++advances;
70            }
71            else if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
72                // Set the next statement to be the first statement of the inner scope and push the
73                // next statement of the current statement into the scope stack.
74                const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
75                scope.push(stmt->getNextNode());
76                stmt = nested.front();
77                assert (stmt);
78                continue;
79            }
80            stmt = stmt->getNextNode();
81        }
82        if (scope.empty()) {
83            break;
84        }
85        stmt = scope.top();
86        scope.pop();
87    }
88    return advances;
89}
90
91#define LOG_NUMBER_OF_ADVANCES(entry) LOG("|Advances|=" << __count_advances(entry))
92
93#else
94#define LOG(x)
95#define RECORD_TIMESTAMP(Name)
96#define LOG_GRAPH(Name, G)
97#define LOG_NUMBER_OF_ADVANCES(entry)
98#endif
99
100
101namespace pablo {
102
103bool AutoMultiplexing::optimize(PabloFunction & function) {
104
105    // std::random_device rd;
106    const auto seed = 83234827342;
107    RNG rng(seed);
108
109    LOG("Seed:                    " << seed);
110
111    AutoMultiplexing am;
112    RECORD_TIMESTAMP(start_initialize);
113    const bool abort = am.initialize(function);
114    RECORD_TIMESTAMP(end_initialize);
115
116    LOG("Initialize:              " << (end_initialize - start_initialize));
117
118    LOG_NUMBER_OF_ADVANCES(function.getEntryBlock());
119
120    if (abort) {
121        return false;
122    }
123
124    RECORD_TIMESTAMP(start_characterize);
125    am.characterize(function.getEntryBlock());
126    RECORD_TIMESTAMP(end_characterize);
127
128    LOG("Characterize:            " << (end_characterize - start_characterize));
129
130    RECORD_TIMESTAMP(start_create_multiplex_graph);
131    const bool multiplex = am.generateCandidateSets(rng);
132    RECORD_TIMESTAMP(end_create_multiplex_graph);
133    LOG("GenerateMultiplexSets:   " << (end_create_multiplex_graph - start_create_multiplex_graph));
134
135    RECORD_TIMESTAMP(start_shutdown);
136    am.Shutdown();
137    RECORD_TIMESTAMP(end_shutdown);
138    LOG("Shutdown:                " << (end_shutdown - start_shutdown));
139
140    if (multiplex) {
141
142        RECORD_TIMESTAMP(start_select_multiplex_sets);
143        am.selectMultiplexSets(rng);
144        RECORD_TIMESTAMP(end_select_multiplex_sets);
145        LOG("SelectMultiplexSets:     " << (end_select_multiplex_sets - start_select_multiplex_sets));
146
147        RECORD_TIMESTAMP(start_subset_constraints);
148        am.applySubsetConstraints();
149        RECORD_TIMESTAMP(end_subset_constraints);
150        LOG("ApplySubsetConstraints:  " << (end_subset_constraints - start_subset_constraints));
151
152        RECORD_TIMESTAMP(start_select_independent_sets);
153        am.multiplexSelectedIndependentSets();
154        RECORD_TIMESTAMP(end_select_independent_sets);
155        LOG("MultiplexSelectedSets:   " << (end_select_independent_sets - start_select_independent_sets));
156
157        RECORD_TIMESTAMP(start_topological_sort);
158        am.topologicalSort(function.getEntryBlock());
159        RECORD_TIMESTAMP(end_topological_sort);
160        LOG("TopologicalSort:         " << (end_topological_sort - start_topological_sort));
161    }
162
163    LOG_NUMBER_OF_ADVANCES(function.getEntryBlock());
164
165    return multiplex;
166}
167
168/** ------------------------------------------------------------------------------------------------------------- *
169 * @brief initialize
170 * @param function the function to optimize
171 * @returns true if there are fewer than three advances in this function
172 *
173 * Scan through the program to identify any advances and calls then initialize the BDD engine with
174 * the proper variable ordering.
175 ** ------------------------------------------------------------------------------------------------------------- */
176bool AutoMultiplexing::initialize(PabloFunction & function) {
177
178    flat_map<const PabloAST *, unsigned> map;   
179    std::stack<Statement *> scope;
180    unsigned variableCount = 0; // number of statements that cannot always be categorized without generating a new variable
181
182    // Scan through and collect all the advances, calls, scanthrus and matchstars ...
183    unsigned n = 0, m = 0;
184    for (Statement * stmt = function.getEntryBlock().front(); ; ) {
185        while ( stmt ) {
186            ++n;
187            if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
188                // Set the next statement to be the first statement of the inner scope and push the
189                // next statement of the current statement into the scope stack.
190                const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
191                scope.push(stmt->getNextNode());
192                stmt = nested.front();
193                assert (stmt);
194                continue;
195            }
196
197            assert ("Run the Simplifer pass prior to this!" && (stmt->getNumUses() > 0));
198
199            switch (stmt->getClassTypeId()) {
200                case PabloAST::ClassTypeId::Advance:
201                    mAdvanceMap.emplace(stmt, m);
202                    map.emplace(stmt, m++);
203                case PabloAST::ClassTypeId::Call:
204                case PabloAST::ClassTypeId::ScanThru:
205                case PabloAST::ClassTypeId::MatchStar:
206                    variableCount++;
207                    break;
208                default:
209                    break;
210            }
211            stmt = stmt->getNextNode();
212        }
213        if (scope.empty()) {
214            break;
215        }
216        stmt = scope.top();
217        scope.pop();
218    }
219
220    // If there are fewer than three Advances in this program, just abort. We cannot reduce it.
221    if (m < 3) {
222        return true;
223    }
224
225    // Create the transitive closure matrix of graph. From this we'll construct
226    // two graphs restricted to the relationships between advances. The first will
227    // be a path graph, which is used to bypass testing for mutual exclusivity of
228    // advances that cannot be multiplexed. The second is a transitive reduction
229    // of that graph, which forms the basis of our constraint graph when deciding
230    // which advances ought to be multiplexed.
231
232    matrix<bool> G(n, m); // Let G be a matrix with n rows of m (Advance) elements
233    G.clear();
234    for (unsigned i = 0; i != m; ++i) {
235        G(i, i) = true;
236    }
237
238    n = m;
239    m = 0;
240
241    const Statement * stmt = function.getEntryBlock().front();
242    for (;;) {
243        while ( stmt ) {
244
245            unsigned u;
246            if (isa<Advance>(stmt)) {
247                assert (mAdvanceMap.count(stmt) && mAdvanceMap[stmt] == m);
248                u = m++;
249            }
250            else {
251                u = n++;
252                map.emplace(stmt, u);
253            }
254
255            for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
256                const PabloAST * const op = stmt->getOperand(i);
257                if (LLVM_LIKELY(isa<Statement>(op))) {
258                    const unsigned v = map[op];
259                    for (unsigned w = 0; w != m; ++w) {
260                        G(u, w) |= G(v, w);
261                    }
262                }
263            }
264            if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
265                // Set the next statement to be the first statement of the inner scope
266                // and push the next statement of the current statement into the stack.
267                const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
268                scope.push(stmt->getNextNode());
269                stmt = nested.front();
270                assert (stmt);
271                continue;
272            }
273            stmt = stmt->getNextNode();
274        }
275        if (scope.empty()) {
276            break;
277        }
278        stmt = scope.top();
279        scope.pop();
280    }
281
282    // Record the path / base constraint graph after removing any reflexive-loops.
283    // Since G is a use-def graph and we want our constraint graph to be a def-use graph,
284    // reverse the edges as we're writing them to obtain the transposed graph.
285    mConstraintGraph = ConstraintGraph(m);
286    mSubsetGraph = SubsetGraph(m);
287
288    for (unsigned i = 0; i != m; ++i) {
289        G(i, i) = false;
290        for (unsigned j = 0; j != m; ++j) {
291            if (G(i, j)) {
292                add_edge(j, i, mConstraintGraph);
293            }
294        }       
295    }
296
297    // Initialize the BDD engine ...
298    mManager = Cudd_Init((variableCount + function.getNumOfParameters()), 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0);
299    Cudd_AutodynDisable(mManager);
300
301    // Map the predefined 0/1 entries
302    mCharacterizationMap[function.getEntryBlock().createZeroes()] = Zero();
303    mCharacterizationMap[function.getEntryBlock().createOnes()] = One();
304
305    // Order the variables so the input Vars are pushed to the end; they ought to
306    // be the most complex to resolve.
307    for (auto i = 0; i != function.getNumOfParameters(); ++i) {
308        mCharacterizationMap[function.getParameter(i)] = Cudd_bddIthVar(mManager, variableCount++);
309    }
310
311    return false;
312}
313
314/** ------------------------------------------------------------------------------------------------------------- *
315 * @brief characterize
316 * @param vars the input vars for this program
317 *
318 * Scan through the program and iteratively compute the BDDs for each statement.
319 ** ------------------------------------------------------------------------------------------------------------- */
320void AutoMultiplexing::characterize(PabloBlock &block) {
321    for (Statement * stmt : block) {
322        if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
323            const auto start = mRecentCharacterizations.size();
324            characterize(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
325            assert (mRecentCharacterizations.size() >= start);
326            if (isa<If>(stmt)) {
327                const auto & defined = cast<const If>(stmt)->getDefined();
328                for (auto pair = mRecentCharacterizations.begin() + start; pair != mRecentCharacterizations.end(); ++pair) {
329                    const PabloAST * expr = nullptr;
330                    DdNode * bdd = nullptr;
331                    std::tie(expr, bdd) = *pair;
332                    if (LLVM_UNLIKELY(isa<Assign>(expr))) {
333                        if (LLVM_LIKELY(std::find(defined.begin(), defined.end(), expr) != defined.end())) {
334                            continue;
335                        }
336                    }
337                    mCharacterizationMap.erase(mCharacterizationMap.find(expr));
338                    if (LLVM_UNLIKELY(Cudd_IsConstant(bdd))) {
339                        continue;
340                    }
341                    Deref(bdd);
342                }
343            }
344            else { // if isa<While>(stmt)
345                const auto & variants = cast<const While>(stmt)->getVariants();
346                for (auto pair = mRecentCharacterizations.begin() + start; pair != mRecentCharacterizations.end(); ++pair) {
347                    const PabloAST * expr = nullptr;
348                    DdNode * bdd = nullptr;
349                    std::tie(expr, bdd) = *pair;
350                    if (LLVM_UNLIKELY(isa<Next>(expr))) {
351                        if (LLVM_LIKELY(std::find(variants.begin(), variants.end(), expr) != variants.end())) {
352                            DdNode *& next = mCharacterizationMap[expr];
353                            next = Or(next, bdd);
354                            Ref(next);
355                            continue;
356                        }
357                    }
358                    mCharacterizationMap.erase(mCharacterizationMap.find(expr));
359                    if (LLVM_UNLIKELY(Cudd_IsConstant(bdd))) {
360                        continue;
361                    }
362                    Deref(bdd);
363                }
364            }
365            mRecentCharacterizations.erase(mRecentCharacterizations.begin() + start, mRecentCharacterizations.end());
366            continue;
367        }
368
369        DdNode * var = characterize(stmt);
370        mCharacterizationMap[stmt] = var;
371        assert (Cudd_DebugCheck(mManager) == 0);
372    }
373}
374
375/** ------------------------------------------------------------------------------------------------------------- *
376 * @brief characterize
377 ** ------------------------------------------------------------------------------------------------------------- */
378inline DdNode * AutoMultiplexing::characterize(Statement * const stmt) {
379
380    DdNode * bdd = nullptr;
381    // Map our operands to the computed BDDs
382    std::array<DdNode *, 3> input;
383    unsigned count = 0;
384    for (; count != stmt->getNumOperands(); ++count) {
385        PabloAST * const op = stmt->getOperand(count);
386        if (LLVM_UNLIKELY(isa<Integer>(op) || isa<String>(op))) {
387            continue;
388        }
389        auto f = mCharacterizationMap.find(op);
390        if (LLVM_UNLIKELY(f == mCharacterizationMap.end())) {
391            std::string tmp;
392            llvm::raw_string_ostream msg(tmp);
393            msg << "Uncharacterized operand " << std::to_string(count);
394            PabloPrinter::print(stmt, " of ", msg);
395            throw std::runtime_error(msg.str());
396        }
397        input[count] = f->second;
398    }
399
400    switch (stmt->getClassTypeId()) {
401        case PabloAST::ClassTypeId::Assign:
402        case PabloAST::ClassTypeId::Next:
403            bdd = input[0];
404            break;
405        case PabloAST::ClassTypeId::And:
406            bdd = And(input[0], input[1]);
407            break;       
408        case PabloAST::ClassTypeId::Or:
409            bdd = Or(input[0], input[1]);
410            break;
411        case PabloAST::ClassTypeId::Xor:
412            bdd = Xor(input[0], input[1]);
413            break;
414        case PabloAST::ClassTypeId::Not:
415            bdd = Not(input[0]);
416            break;
417        case PabloAST::ClassTypeId::Sel:
418            bdd = Ite(input[0], input[1], input[2]);
419            break;
420        case PabloAST::ClassTypeId::ScanThru:
421            // It may be possible use "Not(input[1])" for ScanThrus if we rule out the possibility
422            // of a contradition being erroneously calculated later. An example of this
423            // would be ¬(ScanThru(c,m) √ m)
424        case PabloAST::ClassTypeId::MatchStar:
425            if (LLVM_UNLIKELY(isZero(input[0]) || isZero(input[1]))) {
426                return Zero();
427            }
428        case PabloAST::ClassTypeId::Call:
429            bdd = NewVar();
430            mRecentCharacterizations.emplace_back(stmt, bdd);
431            return bdd;
432        case PabloAST::ClassTypeId::Advance:
433            // This returns so that it doesn't mistakeningly replace the Advance with 0 or add it
434            // to the list of recent characterizations.
435            return characterize(cast<Advance>(stmt), input[0]);
436        default:
437            throw std::runtime_error("Unexpected statement type " + stmt->getName()->to_string());
438    }
439
440    Ref(bdd);
441    if (LLVM_UNLIKELY(NoSatisfyingAssignment(bdd))) {
442        Deref(bdd);
443        // If there is no satisfing assignment for this bdd, the statement will always produce 0.
444        // We can safely replace this statement with 0 unless it is an Advance, Assign or Next node.
445        // Those must be handled specially or we may end up producing a non-equivalent function.
446        if (LLVM_UNLIKELY(isa<Advance>(stmt) || isa<Assign>(stmt) || isa<Next>(stmt))) {
447            stmt->setOperand(0, stmt->getParent()->createZeroes());
448            bdd = Zero();
449        }
450        else {
451            stmt->replaceWith(stmt->getParent()->createZeroes());
452            return nullptr;
453        }
454    }
455    mRecentCharacterizations.emplace_back(stmt, bdd);
456    return bdd;
457}
458
459/** ------------------------------------------------------------------------------------------------------------- *
460 * @brief characterize
461 ** ------------------------------------------------------------------------------------------------------------- */
462inline DdNode * AutoMultiplexing::characterize(Advance *adv, DdNode * input) {
463    DdNode * Ik, * Ck, * Nk;
464    if (LLVM_UNLIKELY(isZero(input))) {
465        Ik = Ck = Nk = Zero();
466    }
467    else {
468
469        Ik = input;
470        Ref(input);
471        Ck = NewVar();
472        Nk = Not(Ck);
473
474        assert (mAdvanceMap.count(adv));
475
476        const auto k = mAdvanceMap[adv];
477
478        std::vector<bool> unconstrained(k , false);
479
480        // Can we use a transposed copy of the subset graph to determine an ordering of variables?
481        for (unsigned i = 0; i != k; ++i) {
482            // Have we already proven that these are unconstrained by the subset relationships?
483            if (unconstrained[i]) continue;
484            Advance * tmp = std::get<0>(mAdvance[i]);
485            // If these advances are "shifting" their values by the same amount and aren't transitively dependant ...
486            if ((adv->getOperand(1) == tmp->getOperand(1)) && (notTransitivelyDependant(i, k))) {
487                DdNode * Ii = std::get<1>(mAdvance[i]);
488                DdNode * const IiIk = And(Ik, Ii);
489                Ref(IiIk);
490                // Is there any satisfying truth assignment? If not, these streams are mutually exclusive.
491                if (NoSatisfyingAssignment(IiIk)) {
492                    assert (mCharacterizationMap.count(tmp));
493                    DdNode *& Ci = mCharacterizationMap[tmp];
494                    // Mark the i-th and k-th Advances as being mutually exclusive
495                    DdNode * Ni = std::get<2>(mAdvance[i]);
496                    Ck = And(Ck, Ni); Ref(Ck);
497                    Ci = And(Ci, Nk); Ref(Ci);
498                    // If Ai ∩ Ak = ∅ and Aj ⊂ Ai, Aj ∩ Ak = ∅.
499                    graph_traits<SubsetGraph>::in_edge_iterator ei, ei_end;
500                    for (std::tie(ei, ei_end) = in_edges(i, mSubsetGraph); ei != ei_end; ++ei) {
501                        const auto j = source(*ei, mSubsetGraph);
502                        if (notTransitivelyDependant(k, j)) {
503                            Advance * adv = std::get<0>(mAdvance[j]);
504                            assert (mCharacterizationMap.count(adv));
505                            DdNode *& Cj = mCharacterizationMap[adv];
506                            DdNode * Nj = std::get<2>(mAdvance[j]);
507                            // Mark the i-th and j-th Advances as being mutually exclusive
508                            Ck = And(Ck, Nj); Ref(Ck);
509                            Cj = And(Cj, Nk); Ref(Cj);
510                            unconstrained[j] = true;
511                        }
512                    }
513                    unconstrained[i] = true;
514                }
515                else if (Ik == IiIk) {
516                    // If Ik = Ii ∩ Ik then Ik ⊂ Ii. Record this in the subset graph with the arc (k,i).
517                    // These edges will be moved into the multiplex set graph if Ai and Ak happen to be
518                    // in the same mutually exclusive set.
519                    add_edge(k, i, mSubsetGraph);
520                    // If Ak ⊂ Ai and Ai ⊂ Aj, Ak ⊂ Aj.
521                    graph_traits<SubsetGraph>::out_edge_iterator ei, ei_end;
522                    for (std::tie(ei, ei_end) = out_edges(i, mSubsetGraph); ei != ei_end; ++ei) {
523                        const auto j = target(*ei, mSubsetGraph);
524                        add_edge(k, j, mSubsetGraph);
525                        unconstrained[j] = true;
526                    }
527                    unconstrained[i] = true;
528                }
529                else if (Ii == IiIk) {
530                    // If Ii = Ii ∩ Ik then Ii ⊂ Ik. Record this in the subset graph with the arc (i,k).
531                    add_edge(i, k, mSubsetGraph);
532                    // If Ai ⊂ Ak and Aj ⊂ Ai, Aj ⊂ Ak.
533                    graph_traits<SubsetGraph>::in_edge_iterator ei, ei_end;
534                    for (std::tie(ei, ei_end) = in_edges(i, mSubsetGraph); ei != ei_end; ++ei) {
535                        const auto j = source(*ei, mSubsetGraph);
536                        add_edge(j, k, mSubsetGraph);
537                        unconstrained[j] = true;
538                    }
539                    unconstrained[i] = true;
540                }
541                Deref(IiIk);
542            }
543        }
544
545        for (unsigned i = 0; i != k; ++i) {
546            const Advance * const tmp = std::get<0>(mAdvance[i]);
547            // Even if these Advances are mutually exclusive, they must be in the same scope or they cannot be safely multiplexed.
548            if (!unconstrained[i] || (adv->getParent() != tmp->getParent())) {
549                // We want the constraint graph to be acyclic; since the dependencies are already in topological order,
550                // adding an arc from a lesser to greater numbered vertex won't induce a cycle.
551                add_edge(i, k, mConstraintGraph);
552            }
553        }
554    }
555
556    mAdvance.emplace_back(adv, Ik, Nk);
557    return Ck;
558}
559
560/** ------------------------------------------------------------------------------------------------------------- *
561 * @brief notTransitivelyDependant
562 ** ------------------------------------------------------------------------------------------------------------- */
563inline bool AutoMultiplexing::notTransitivelyDependant(const ConstraintVertex i, const ConstraintVertex j) const {
564    assert (i < num_vertices(mConstraintGraph) && j < num_vertices(mConstraintGraph));
565    return (mConstraintGraph.get_edge(i, j) == 0);
566}
567
568/** ------------------------------------------------------------------------------------------------------------- *
569 * @brief CUDD wrappers
570 ** ------------------------------------------------------------------------------------------------------------- */
571
572inline DdNode * AutoMultiplexing::Zero() const {
573    return Cudd_ReadLogicZero(mManager);
574}
575
576inline DdNode * AutoMultiplexing::One() const {
577    return Cudd_ReadOne(mManager);
578}
579
580inline DdNode * AutoMultiplexing::NewVar() {
581    DdNode * var = Cudd_bddIthVar(mManager, mVariables++);
582    return var;
583}
584
585inline bool AutoMultiplexing::isZero(DdNode * const x) const {
586    return x == Zero();
587}
588
589inline DdNode * AutoMultiplexing::And(DdNode * const x, DdNode * const y) {
590    return Cudd_bddAnd(mManager, x, y);
591}
592
593inline DdNode * AutoMultiplexing::Or(DdNode * const x, DdNode * const y) {
594    return Cudd_bddOr(mManager, x, y);
595}
596
597inline DdNode * AutoMultiplexing::Xor(DdNode * const x, DdNode * const y) {
598    return Cudd_bddXor(mManager, x, y);
599}
600
601inline DdNode * AutoMultiplexing::Not(DdNode * const x) const {
602    return Cudd_Not(x);
603}
604
605inline DdNode * AutoMultiplexing::Ite(DdNode * const x, DdNode * const y, DdNode * const z) {
606    return Cudd_bddIte(mManager, x, y, z);
607}
608
609inline bool AutoMultiplexing::NoSatisfyingAssignment(DdNode * const x) {
610    return Cudd_bddLeq(mManager, x, Zero());
611}
612
613inline void AutoMultiplexing::Ref(DdNode * const x) {
614    assert (x);
615    Cudd_Ref(x);
616}
617
618inline void AutoMultiplexing::Deref(DdNode * const x) {
619    assert (x);
620    Cudd_RecursiveDeref(mManager, x);
621}
622
623inline void AutoMultiplexing::Shutdown() {
624//    #ifdef PRINT_DEBUG_OUTPUT
625//    Cudd_PrintInfo(mManager, stderr);
626//    #endif
627    Cudd_Quit(mManager);
628}
629
630/** ------------------------------------------------------------------------------------------------------------- *
631 * @brief generateMultiplexSets
632 * @param RNG random number generator
633 ** ------------------------------------------------------------------------------------------------------------- */
634bool AutoMultiplexing::generateCandidateSets(RNG & rng) {
635
636    using degree_t = graph_traits<ConstraintGraph>::degree_size_type;
637
638    // What if we generated a "constraint free" graph instead? By taking each connected component of it
639    // and computing the complement of it (with the same lesser to greater index ordering), we should
640    // have the same problem here but decomposed into subgraphs.
641
642    VertexVector S;
643    std::vector<degree_t> D(num_vertices(mConstraintGraph));
644    S.reserve(15);
645
646    mMultiplexSetGraph = MultiplexSetGraph(num_vertices(mConstraintGraph));
647
648    // Push all source nodes into the new independent set N
649    for (auto v : make_iterator_range(vertices(mConstraintGraph))) {
650        const auto d = in_degree(v, mConstraintGraph);
651        D[v] = d;
652        if (d == 0) {
653            S.push_back(v);
654        }
655    }
656
657    auto remainingVerticies = num_vertices(mConstraintGraph) - S.size();
658
659    do {
660
661        addCandidateSet(S);
662
663        bool noNewElements = true;
664        do {
665            // Randomly choose a vertex in S and discard it.
666            const auto i = S.begin() + IntDistribution(0, S.size() - 1)(rng);
667            const ConstraintVertex u = *i;
668            S.erase(i);
669            --remainingVerticies;
670
671            for (auto e : make_iterator_range(out_edges(u, mConstraintGraph))) {
672                const ConstraintVertex v = target(e, mConstraintGraph);
673                if ((--D[v]) == 0) {
674                    S.push_back(v);
675                    noNewElements = false;
676                }
677            }
678        }
679        while (noNewElements && remainingVerticies);
680    }
681    while (remainingVerticies);
682
683    return num_vertices(mMultiplexSetGraph) > num_vertices(mConstraintGraph);
684}
685
686/** ------------------------------------------------------------------------------------------------------------- *
687 * @brief addCandidateSet
688 * @param S an independent set
689 * @param T the trie in which to encode this new set into
690 * @param roots the roots (source nodes) for each tree in T
691 ** ------------------------------------------------------------------------------------------------------------- */
692inline void AutoMultiplexing::addCandidateSet(const VertexVector & S) {
693    if (S.size() >= 3) {
694        const auto u = add_vertex(mMultiplexSetGraph);
695        for (const auto v : S) {
696            add_edge(u, v, mMultiplexSetGraph);
697        }
698    }
699}
700
701/** ------------------------------------------------------------------------------------------------------------- *
702 * @brief is_power_of_2
703 * @param n an integer
704 ** ------------------------------------------------------------------------------------------------------------- */
705static inline bool is_power_of_2(const size_t n) {
706    return ((n & (n - 1)) == 0) ;
707}
708
709/** ------------------------------------------------------------------------------------------------------------- *
710 * @brief log2_plus_one
711 ** ------------------------------------------------------------------------------------------------------------- */
712static inline size_t log2_plus_one(const size_t n) {
713    return std::log2<size_t>(n) + 1; // use a faster builtin function for this?
714}
715
716/** ------------------------------------------------------------------------------------------------------------- *
717 * @brief selectMultiplexSets
718 * @param RNG random number generator
719 *
720 * This algorithm is simply computes a greedy set cover. We want an exact max-weight set cover but can generate new
721 * sets by taking a subset of any existing set. With a few modifications, the greedy approach seems to work well
722 * enough but can be trivially shown to produce a suboptimal solution if there are three (or more) sets in which
723 * two, labelled A and B, are disjoint and the third larger set, C, that consists of elements of A and B.
724 ** ------------------------------------------------------------------------------------------------------------- */
725void AutoMultiplexing::selectMultiplexSets(RNG &) {
726
727
728    using OutEdgeIterator = graph_traits<MultiplexSetGraph>::out_edge_iterator;
729    using InEdgeIterator = graph_traits<MultiplexSetGraph>::in_edge_iterator;
730    using degree_t = MultiplexSetGraph::degree_size_type;
731    using vertex_t = MultiplexSetGraph::vertex_descriptor;
732
733    const size_t m = num_vertices(mConstraintGraph);
734    const size_t n = num_vertices(mMultiplexSetGraph) - m;
735
736    std::vector<degree_t> remaining(n, 0);
737    std::vector<vertex_t> chosen_set(m, 0);
738
739    for (unsigned i = 0; i != n; ++i) {
740        remaining[i] = out_degree(i + m, mMultiplexSetGraph);
741    }
742
743    for (;;) {
744
745        // Choose the set with the greatest number of vertices not already included in some other set.
746        vertex_t k = 0;
747        degree_t w = 0;
748        for (vertex_t i = 0; i != n; ++i) {
749            const degree_t r = remaining[i];
750            if (w < r) {
751                k = i;
752                w = r;
753            }
754        }
755
756        // Multiplexing requires at least 3 elements; if the best set contains fewer than 3, abort.
757        if (w < 3) {
758            break;
759        }
760
761        OutEdgeIterator ei, ei_end;
762        for (std::tie(ei, ei_end) = out_edges(k + m, mMultiplexSetGraph); ei != ei_end; ++ei) {
763            const vertex_t j = target(*ei, mMultiplexSetGraph);
764            if (chosen_set[j] == 0) {
765                chosen_set[j] = (k + m);
766                InEdgeIterator ej, ej_end;
767                for (std::tie(ej, ej_end) = in_edges(j, mMultiplexSetGraph); ej != ej_end; ++ej) {
768                    remaining[source(*ej, mMultiplexSetGraph) - m]--;
769                }
770            }
771        }
772
773        assert (remaining[k] == 0);
774
775        // If this contains 2^n elements for any n, discard the member that is most likely to be added
776        // to some future set.
777        if (is_power_of_2(w)) {
778            vertex_t j = 0;
779            degree_t w = 0;
780            for (vertex_t i = 0; i != m; ++i) {
781                if (chosen_set[i] == (k + m)) {
782                    InEdgeIterator ej, ej_end;
783                    degree_t r = 1;
784                    for (std::tie(ej, ej_end) = in_edges(i, mMultiplexSetGraph); ej != ej_end; ++ej) {
785                        // strongly prefer adding weight to unvisited sets that have more remaining vertices
786                        r += std::pow(remaining[source(*ej, mMultiplexSetGraph) - m], 2);
787                    }
788                    if (w < r) {
789                        j = i;
790                        w = r;
791                    }
792                }
793            }
794            assert (w > 0);
795            chosen_set[j] = 0;
796            InEdgeIterator ej, ej_end;
797            for (std::tie(ej, ej_end) = in_edges(j, mMultiplexSetGraph); ej != ej_end; ++ej) {
798                remaining[source(*ej, mMultiplexSetGraph) - m]++;
799            }
800        }
801    }
802
803    for (unsigned i = 0; i != m; ++i) {
804        InEdgeIterator ei, ei_end;
805        std::tie(ei, ei_end) = in_edges(i, mMultiplexSetGraph);
806        for (auto next = ei; ei != ei_end; ei = next) {
807            ++next;
808            if (source(*ei, mMultiplexSetGraph) != chosen_set[i]) {
809                remove_edge(*ei, mMultiplexSetGraph);
810            }
811        }
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 applySubsetConstraints
826 ** ------------------------------------------------------------------------------------------------------------- */
827void AutoMultiplexing::applySubsetConstraints() {
828
829    // When entering thus function, the multiplex set graph M is a bipartite DAG with edges denoting the set
830    // relationships of our independent sets.
831    const unsigned m = num_vertices(mConstraintGraph);
832    const unsigned n = num_vertices(mMultiplexSetGraph);
833
834    // Add in any edges from our subset constraints to M that are within the same set.
835    bool hasSubsetConstraint = false;
836
837    graph_traits<SubsetGraph>::edge_iterator ei, ei_end;
838    for (std::tie(ei, ei_end) = edges(mSubsetGraph); ei != ei_end; ++ei) {
839        const auto u = source(*ei, mSubsetGraph);
840        const auto v = target(*ei, mSubsetGraph);
841        graph_traits<MultiplexSetGraph>::in_edge_iterator ej, ej_end;
842        // If both the source and target of ei are adjacent to the same vertex, that vertex must be the
843        // "set vertex". Add the edge between the vertices.
844        for (std::tie(ej, ej_end) = in_edges(u, mMultiplexSetGraph); ej != ej_end; ++ej) {
845            auto w = target(*ej, mMultiplexSetGraph);
846            // Only check (v, w) if w is a "set vertex".
847            if (w >= (n - m) && edge(v, w, mMultiplexSetGraph).second) {
848                add_edge(u, v, mMultiplexSetGraph);
849                hasSubsetConstraint = true;
850            }
851        }
852    }
853
854    if (LLVM_UNLIKELY(hasSubsetConstraint)) {
855        // At this point, M is still a DAG but no longer bipartite. We're going to scan through the set vertices
856        // in M, and use a DFS to scan through M and eliminate any subset relationships in the AST.
857        // That way, "multiplexSelectedIndependentSets" only needs to consider muxing and demuxing of the streams.
858
859        std::vector<MultiplexSetGraph::vertex_descriptor> V;
860        std::stack<MultiplexSetGraph::vertex_descriptor> S;
861        std::queue<PabloAST *> Q;
862        BitVector D(n - m, 0);
863
864        for (auto i = m; i != n; ++i) {
865            graph_traits<MultiplexSetGraph>::out_edge_iterator ei, ei_end;
866            // For each member of a "set vertex" ...
867            std::tie(ei, ei_end) = out_edges(i, mMultiplexSetGraph);
868            for (; ei != ei_end; ++ei) {
869                const auto s = source(*ei, mMultiplexSetGraph);
870                if (out_degree(s, mMultiplexSetGraph) != 0) {
871                    // First scan through the subgraph of vertices in M dominated by s and build up the set T,
872                    // consisting of all sinks w.r.t. vertex s.
873                    auto u = s;
874                    for (;;) {
875                        graph_traits<MultiplexSetGraph>::out_edge_iterator ej, ej_end;
876                        for (std::tie(ej, ej_end) = out_edges(u, mMultiplexSetGraph); ej != ej_end; ++ej) {
877                            auto v = target(*ej, mMultiplexSetGraph);
878                            if (D.test(v)) {
879                                continue;
880                            }
881                            D.set(v);
882                            if (out_degree(v, mMultiplexSetGraph) == 0) {
883                                V.push_back(v);
884                            }
885                            else {
886                                S.push(v);
887                            }
888                        }
889                        if (S.empty()) {
890                            break;
891                        }
892                        u = S.top();
893                        S.pop();
894                    }
895                    D.clear();
896                    // Now in order for these advances to be mutually exclusive, the input to A_s must be masked
897                    // with the complement of each advance indicated by V.
898
899                    Advance * adv = std::get<0>(mAdvance[s]);
900                    PabloBlock * pb = adv->getParent();
901
902                    for (auto i : V) {
903                        Q.push(std::get<0>(mAdvance[i])->getOperand(0));
904                    }                   
905                    pb->setInsertPoint(adv);
906                    while (Q.size() > 1) {
907                        PabloAST * a1 = Q.front(); Q.pop();
908                        PabloAST * a2 = Q.front(); Q.pop();                       
909                        Q.push(pb->createOr(a1, a2, "subset"));
910                    }
911                    assert (Q.size() == 1);
912
913                    PabloAST * const mask = pb->createNot(Q.front()); Q.pop();
914                    adv->setOperand(0, pb->createAnd(adv->getOperand(0), mask, "subset"));
915
916                    // Similar to the above, we're going to OR together the result of each advance,
917                    // including s. This will restore the advanced variable back to its original state.
918
919                    // Gather the original users to this advance. We'll be manipulating it shortly.
920                    std::vector<PabloAST *> U(adv->users().begin(), adv->users().end());
921
922                    // Add s to V and sort the list; it'll be closer to being in topological order.
923                    V.push_back(s);
924                    std::sort(V.begin(), V.end());
925                    for (auto i : V) {
926                        Q.push(std::get<0>(mAdvance[i]));
927                    }
928                    pb->setInsertPoint(adv);
929                    while (Q.size() > 1) {
930                        PabloAST * a1 = Q.front(); Q.pop();
931                        PabloAST * a2 = Q.front(); Q.pop();                       
932                        Q.push(pb->createOr(a1, a2, "subset"));
933                    }
934                    assert (Q.size() == 1);
935
936                    PabloAST * const input = Q.front(); Q.pop();
937                    for (PabloAST * use : U) {
938                        if (LLVM_LIKELY(isa<Statement>(use))) {
939                            cast<Statement>(use)->replaceUsesOfWith(adv, input);
940                        }
941                    }
942
943                    pb->setInsertPoint(pb->back());
944
945                    V.clear();
946
947                }
948            }
949        }
950    }
951}
952
953/** ------------------------------------------------------------------------------------------------------------- *
954 * @brief multiplexSelectedIndependentSets
955 ** ------------------------------------------------------------------------------------------------------------- */
956void AutoMultiplexing::multiplexSelectedIndependentSets() const {
957
958    const unsigned f = num_vertices(mConstraintGraph);
959    const unsigned l = num_vertices(mMultiplexSetGraph);
960
961    // Preallocate the structures based on the size of the largest multiplex set
962    size_t max_n = 3;
963    for (unsigned s = f; s != l; ++s) {
964        max_n = std::max<unsigned>(max_n, out_degree(s, mMultiplexSetGraph));
965    }
966
967    std::vector<MultiplexSetGraph::vertex_descriptor> I(max_n);
968    circular_buffer<PabloAST *> Q(max_n);
969
970    // When entering thus function, the multiplex set graph M is a DAG with edges denoting the set
971    // relationships of our independent sets.
972
973    for (unsigned s = f; s != l; ++s) {
974        const size_t n = out_degree(s, mMultiplexSetGraph);
975        if (n) {
976            const size_t m = log2_plus_one(n);
977            Advance * input[n];
978            Advance * muxed[m];
979
980            graph_traits<MultiplexSetGraph>::out_edge_iterator ei, ei_end;
981            std::tie(ei, ei_end) = out_edges(s, mMultiplexSetGraph);
982            for (unsigned i = 0; i != n; ++ei, ++i) {
983                I[i] = target(*ei, mMultiplexSetGraph);
984            }
985            std::sort(I.begin(), I.begin() + n);
986
987            for (unsigned i = 0; i != n; ++i) {
988                input[i] = std::get<0>(mAdvance[I[i]]);
989            }
990
991            PabloBlock * const block = input[0]->getParent();
992            block->setInsertPoint(block->back());
993            PabloBuilder builder(*block);
994            Advance * const adv = input[0];
995
996            /// Perform n-to-m Multiplexing
997            for (size_t j = 0; j != m; ++j) {
998
999                std::ostringstream prefix;
1000                prefix << "mux" << n << "to" << m << '_';
1001                for (size_t i = 1; i <= n; ++i) {
1002                    if ((i & (static_cast<size_t>(1) << j)) != 0) {
1003                        Q.push_back(input[i - 1]->getOperand(0));
1004                    }
1005                }
1006
1007                while (Q.size() > 1) {
1008                    PabloAST * a1 = Q.front(); Q.pop_front(); assert (a1);
1009                    PabloAST * a2 = Q.front(); Q.pop_front(); assert (a2);
1010                    assert (!Q.full());                                       
1011                    Q.push_back(builder.createOr(a2, a1, "muxing"));
1012                }
1013
1014                PabloAST * mux = Q.front(); Q.pop_front(); assert (mux);
1015                // The only way this did not return an Advance statement would be if either the mux or shift amount
1016                // is zero. Since these cases would have been eliminated earlier, we are safe to cast here.
1017                muxed[j] = cast<Advance>(builder.createAdvance(mux, adv->getOperand(1), prefix.str()));
1018            }
1019
1020            /// Perform m-to-n Demultiplexing           
1021            for (size_t i = 1; i <= n; ++i) {
1022
1023                // Construct the demuxed values and replaces all the users of the original advances with them.
1024                for (size_t j = 0; j != m; ++j) {
1025                    if ((i & (1ULL << j)) == 0) {
1026                        Q.push_back(muxed[j]);
1027                    }
1028                }
1029
1030                if (LLVM_LIKELY(Q.size() > 0)) {
1031                    while (Q.size() > 1) {
1032                        PabloAST * a1 = Q.front(); Q.pop_front(); assert (a1);
1033                        PabloAST * a2 = Q.front(); Q.pop_front(); assert (a2);
1034                        assert (!Q.full());
1035                        Q.push_back(builder.createOr(a2, a1, "demuxing"));
1036                    }
1037                    assert (Q.size() == 1);
1038                    PabloAST * neg = Q.front(); Q.pop_front();
1039                    Q.push_back(builder.createNot(neg, "demuxing")); assert (neg);
1040                }
1041
1042                for (unsigned j = 0; j != m; ++j) {
1043                    if ((i & (1ULL << j)) != 0) {
1044                        assert (!Q.full());
1045                        Q.push_back(muxed[j]);
1046                    }
1047                }
1048
1049                while (Q.size() > 1) {
1050                    PabloAST * a1 = Q.front(); Q.pop_front(); assert (a1);
1051                    PabloAST * a2 = Q.front(); Q.pop_front(); assert (a2);
1052                    assert (!Q.full());
1053                    Q.push_back(builder.createAnd(a1, a2, "demuxing"));
1054                }
1055
1056                PabloAST * demuxed = Q.front(); Q.pop_front(); assert (demuxed);
1057                input[i - 1]->replaceWith(demuxed, true, true);
1058            }
1059
1060            /// Attempt to simplify the demultiplexed values
1061            // simplifyAST(muxed, m, builder);
1062        }
1063    }
1064}
1065
1066/** ------------------------------------------------------------------------------------------------------------- *
1067 * @brief simplifyAST
1068 ** ------------------------------------------------------------------------------------------------------------- */
1069void AutoMultiplexing::simplifyAST(Advance * const muxed[], const unsigned m, PabloBuilder & builder) const {
1070
1071    // first do a BFS to build a topological ordering of statements we're going to end up visiting
1072    // and determine which of those will be terminals in the BDD
1073    using Graph = adjacency_list<hash_setS, vecS, bidirectionalS, PabloAST *>;
1074    using Vertex = Graph::vertex_descriptor;
1075
1076    Graph G;
1077    std::unordered_map<PabloAST *, unsigned> M;
1078    std::queue<Statement *> Q;
1079
1080    for (unsigned i = 0; i != m; ++i) {
1081
1082        const auto u = add_vertex(muxed[i], G);
1083        M.insert(std::make_pair(muxed[i], u));
1084        for (PabloAST * user : muxed[i]->users()) {
1085            auto f = M.find(user);
1086            Vertex v = 0;
1087            if (f == M.end()) {
1088                v = add_vertex(user, G);
1089                M.insert(std::make_pair(user, v));
1090                switch (user->getClassTypeId()) {
1091                    case PabloAST::ClassTypeId::And:
1092                    case PabloAST::ClassTypeId::Or:
1093                    case PabloAST::ClassTypeId::Not:
1094                    case PabloAST::ClassTypeId::Sel:
1095                        Q.push(cast<Statement>(user));
1096                    default: break;
1097                }
1098            } else { // if (f != M.end()) {
1099                v = f->second;
1100            }
1101            add_edge(u, v, G);
1102        }
1103    }
1104
1105    while (!Q.empty()) {
1106        Statement * const var = Q.front(); Q.pop();
1107        const Vertex u = M[var];
1108        for (unsigned i = 0; i != var->getNumOperands(); ++i) {
1109            PabloAST * operand = var->getOperand(i);
1110            auto f = M.find(operand);
1111            Vertex v = 0;
1112            if (LLVM_UNLIKELY(f == M.end())) {
1113                v = add_vertex(operand, G);
1114                M.insert(std::make_pair(operand, v));
1115            } else { // if (f != M.end()) {
1116                v = f->second;
1117            }
1118            add_edge(v, u, G);
1119        }
1120
1121        for (PabloAST * user : var->users()) {
1122            auto f = M.find(user);
1123            Vertex v = 0;
1124            if (LLVM_LIKELY(f == M.end())) {
1125                v = add_vertex(user, G);
1126                M.insert(std::make_pair(user, v));
1127                switch (user->getClassTypeId()) {
1128                    case PabloAST::ClassTypeId::And:
1129                    case PabloAST::ClassTypeId::Or:
1130                    case PabloAST::ClassTypeId::Not:
1131                    case PabloAST::ClassTypeId::Sel:
1132                        Q.push(cast<Statement>(user));
1133                    default: break;
1134                }
1135            } else { // if (f != M.end()) {
1136                v = f->second;
1137            }
1138            add_edge(u, v, G);
1139        }
1140    }
1141
1142    // count the number of sources (sinks) so we know how many inputs (terminals) will exist in the BDD
1143    std::vector<Vertex> inputs;
1144    flat_set<Vertex> terminals;
1145    for (auto u : make_iterator_range(vertices(G))) {
1146        if (in_degree(u, G) == 0) {
1147            inputs.push_back(u);
1148        }
1149        if (out_degree(u, G) == 0) {
1150            // the inputs to the sinks become the terminals in the BDD
1151            for (auto e : make_iterator_range(in_edges(u, G))) {
1152                terminals.insert(source(e, G));
1153            }
1154        }
1155    }
1156
1157    const auto n = inputs.size();
1158
1159    DdManager * manager = Cudd_Init(n, 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0);
1160    Cudd_AutodynEnable(manager, CUDD_REORDER_LAZY_SIFT);
1161
1162    PabloAST * variables[n];
1163    std::vector<DdNode *> characterization(num_vertices(G), nullptr);
1164    for (unsigned i = 0; i != n; ++i) {
1165        variables[i] = G[inputs[i]];
1166        characterization[inputs[i]] = Cudd_bddIthVar(manager, i);
1167    }
1168
1169    std::vector<Vertex> ordering;
1170    ordering.reserve(num_vertices(G));
1171    topological_sort(G, std::back_inserter(ordering));
1172
1173    for (auto ui = ordering.rbegin(); ui != ordering.rend(); ++ui) {
1174
1175        const Vertex u = *ui;
1176
1177        if (characterization[u]) {
1178            continue;
1179        }
1180
1181        std::array<DdNode *, 3> input;
1182
1183        unsigned i = 0;
1184        for (const auto e : make_iterator_range(in_edges(u, G))) {
1185            input[i++] = characterization[source(e, G)];
1186
1187        }
1188
1189        assert (is<Statement>(G[u]) ? i == cast<Statement>(G[u])->getNumOperands() : i == 0);
1190
1191        DdNode * bdd = nullptr;
1192        bool characterized = true;
1193        switch (G[u]->getClassTypeId()) {
1194            case PabloAST::ClassTypeId::And:
1195                bdd = Cudd_bddAnd(manager, input[0], input[1]);
1196                break;
1197            case PabloAST::ClassTypeId::Or:
1198                bdd = Cudd_bddOr(manager, input[0], input[1]);
1199                break;
1200            case PabloAST::ClassTypeId::Not:
1201                bdd = Cudd_Not(input[0]);
1202                break;
1203            case PabloAST::ClassTypeId::Sel:
1204                bdd = Cudd_bddIte(manager, input[0], input[1], input[2]);
1205                break;
1206            default: characterized = false; break;
1207        }
1208
1209        if (characterized) {
1210            Cudd_Ref(bdd);
1211            characterization[u] = bdd;
1212        }
1213    }
1214
1215    Cudd_AutodynDisable(manager);
1216    Cudd_ReduceHeap(manager, CUDD_REORDER_SIFT, 0);
1217    Cudd_ReduceHeap(manager, CUDD_REORDER_EXACT, 0);
1218
1219    raw_os_ostream out(std::cerr);
1220
1221    for (Vertex t : terminals) {
1222
1223//        out << "*******************************************************************************************\n";
1224//        PabloPrinter::print(*(builder.getPabloBlock()), "", out);
1225//        out << "\n\n";
1226        PabloPrinter::print(cast<Statement>(G[t]), " >> ", out);
1227        out << '\n';
1228        out.flush();
1229
1230        DdNode * const f = characterization[t];
1231        Cudd_Ref(f);
1232        PabloAST * expr;
1233        unsigned count;
1234        std::tie(expr, count) = simplifyAST(manager, f, variables, builder);
1235        if (expr) {
1236
1237            PabloPrinter::print(cast<Statement>(expr), "    replacement: ", out);
1238            out << '\n';
1239            out.flush();
1240
1241            cast<Statement>(G[t])->replaceWith(expr, true, true);
1242        }
1243        Cudd_RecursiveDeref(manager, f);
1244    }
1245
1246//    out << "+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n";
1247//    PabloPrinter::print(*(builder.getPabloBlock()), "", out);
1248//    out << '\n';
1249//    out.flush();
1250
1251    Cudd_Quit(manager);
1252}
1253
1254/** ------------------------------------------------------------------------------------------------------------- *
1255 * @brief simplifyAST
1256 ** ------------------------------------------------------------------------------------------------------------- */
1257std::pair<PabloAST *, unsigned> AutoMultiplexing::simplifyAST(DdManager * manager, DdNode * const f, PabloAST * const variables[], PabloBuilder & builder) const {
1258    DdNode * g = Cudd_FindEssential(manager, f);
1259    if (g && Cudd_SupportSize(manager, g) > 0) {
1260        if (g == f) { // every variable is essential
1261            return makeCoverAST(manager, f, variables, builder);
1262        }
1263        Cudd_Ref(g);
1264        PabloAST * c0;
1265        unsigned count0;
1266        std::tie(c0, count0) = makeCoverAST(manager, g, variables, builder);
1267        if (LLVM_UNLIKELY(c0 == nullptr)) {
1268            Cudd_RecursiveDeref(manager, g);
1269            return std::make_pair(nullptr, 0);
1270        }
1271        DdNode * h = Cudd_Cofactor(manager, f, g);
1272        Cudd_Ref(h);
1273        Cudd_RecursiveDeref(manager, g);
1274        PabloAST * c1;
1275        unsigned count1;
1276        std::tie(c1, count1) = simplifyAST(manager, h, variables, builder);
1277        Cudd_RecursiveDeref(manager, h);
1278        if (LLVM_UNLIKELY(c1 == nullptr)) {
1279            cast<Statement>(c0)->eraseFromParent(true);
1280            return std::make_pair(nullptr, 0);
1281        }
1282        return std::make_pair(builder.createAnd(c0, c1), count0 + count1 + 1);
1283    }
1284
1285    PabloAST * disjunctionAST = nullptr;
1286    unsigned disjunctionCount = 0;
1287    PabloAST * conjunctionAST = nullptr;
1288    unsigned conjunctionCount = 0;
1289
1290    DdNode ** decomp = nullptr;
1291    const auto disjuncts = Cudd_bddGenDisjDecomp(manager, f, &decomp);
1292    if (LLVM_LIKELY(disjuncts == 2)) {
1293        Cudd_Ref(decomp[0]);
1294        Cudd_Ref(decomp[1]);
1295        PabloAST * d0;
1296        unsigned count0;
1297        std::tie(d0, count0) = simplifyAST(manager, decomp[0], variables, builder);
1298        Cudd_RecursiveDeref(manager, decomp[0]);
1299        if (LLVM_UNLIKELY(d0 == nullptr)) {
1300            Cudd_RecursiveDeref(manager, decomp[1]);
1301            return std::make_pair(nullptr, 0);
1302        }
1303        PabloAST * d1;
1304        unsigned count1;
1305        std::tie(d1, count1) = simplifyAST(manager, decomp[1], variables, builder);
1306        Cudd_RecursiveDeref(manager, decomp[1]);
1307        FREE(decomp);
1308        if (LLVM_UNLIKELY(d1 == nullptr)) {
1309            cast<Statement>(d0)->eraseFromParent(true);
1310            return std::make_pair(nullptr, 0);
1311        }
1312        disjunctionAST = builder.createOr(d0, d1);
1313        disjunctionCount = count0 + count1 + 1;
1314    }
1315    FREE(decomp);
1316
1317    const auto conjuncts = Cudd_bddGenConjDecomp(manager, f, &decomp);
1318    if (LLVM_LIKELY(conjuncts == 2)) {
1319        Cudd_Ref(decomp[0]);
1320        Cudd_Ref(decomp[1]);
1321        PabloAST * d0;
1322        unsigned count0;
1323        std::tie(d0, count0) = simplifyAST(manager, decomp[0], variables, builder);
1324        Cudd_RecursiveDeref(manager, decomp[0]);
1325        if (LLVM_UNLIKELY(d0 == nullptr)) {
1326            Cudd_RecursiveDeref(manager, decomp[1]);
1327            return std::make_pair(nullptr, 0);
1328        }
1329        PabloAST * d1;
1330        unsigned count1;
1331        std::tie(d1, count1) = simplifyAST(manager, decomp[1], variables, builder);
1332        Cudd_RecursiveDeref(manager, decomp[1]);
1333        FREE(decomp);
1334        if (LLVM_UNLIKELY(d1 == nullptr)) {
1335            cast<Statement>(d0)->eraseFromParent(true);
1336            return std::make_pair(nullptr, 0);
1337        }
1338        conjunctionAST = builder.createAnd(d0, d1);
1339        conjunctionCount = count0 + count1 + 1;
1340    }
1341    FREE(decomp);
1342
1343    if (disjunctionAST && conjunctionAST) {
1344        if (disjunctionCount > conjunctionCount) {
1345            cast<Statement>(disjunctionAST)->eraseFromParent(true);
1346            return std::make_pair(conjunctionAST, conjunctionCount);
1347        } else {
1348            cast<Statement>(conjunctionAST)->eraseFromParent(true);
1349            return std::make_pair(disjunctionAST, disjunctionCount);
1350        }
1351    } else if (disjunctionAST) {
1352        return std::make_pair(disjunctionAST, disjunctionCount);
1353    } else if (conjunctionAST) {
1354        return std::make_pair(conjunctionAST, conjunctionCount);
1355    }
1356    return makeCoverAST(manager, f, variables, builder);
1357}
1358
1359/** ------------------------------------------------------------------------------------------------------------- *
1360 * @brief makeCoverAST
1361 ** ------------------------------------------------------------------------------------------------------------- */
1362std::pair<PabloAST *, unsigned> AutoMultiplexing::makeCoverAST(DdManager * manager, DdNode * const f, PabloAST * const variables[], PabloBuilder & builder) const {
1363
1364    std::queue<PabloAST *> SQ;
1365
1366    circular_buffer<PabloAST *> CQ(manager->size);
1367    circular_buffer<PabloAST *> DQ(manager->size);
1368
1369    int cube[manager->size];
1370
1371    unsigned count = 0;
1372
1373    DdNode * g = f;
1374
1375    Cudd_Ref(g);
1376
1377    while (g != Cudd_ReadLogicZero(manager)) {
1378        int length;
1379        DdNode * implicant = Cudd_LargestCube(manager, g, &length);
1380        if (LLVM_UNLIKELY(implicant == nullptr)) {
1381            Cudd_RecursiveDeref(manager, g);
1382            return std::make_pair(nullptr, 0);
1383        }
1384        Cudd_Ref(implicant);
1385        DdNode * prime = Cudd_bddMakePrime(manager, implicant, f);
1386        if (LLVM_UNLIKELY(prime == nullptr)) {
1387            Cudd_RecursiveDeref(manager, g);
1388            Cudd_RecursiveDeref(manager, implicant);
1389            return std::make_pair(nullptr, 0);
1390        }
1391        Cudd_Ref(prime);
1392        Cudd_RecursiveDeref(manager, implicant);
1393
1394        DdNode * h = Cudd_bddAnd(manager, g, Cudd_Not(prime));
1395        if (LLVM_UNLIKELY(h == nullptr)) {
1396            Cudd_RecursiveDeref(manager, g);
1397            Cudd_RecursiveDeref(manager, prime);
1398            return std::make_pair(nullptr, 0);
1399        }
1400        Cudd_Ref(h);
1401        Cudd_RecursiveDeref(manager, g);
1402
1403        g = h;
1404        if (LLVM_UNLIKELY(Cudd_BddToCubeArray(manager, prime, cube) == 0)) {
1405            Cudd_RecursiveDeref(manager, g);
1406            Cudd_RecursiveDeref(manager, prime);
1407            return std::make_pair(nullptr, 0);
1408        }
1409        Cudd_RecursiveDeref(manager, prime);
1410
1411        for (auto i = 0; i != manager->size; ++i) {
1412            if (cube[i] == 0) {
1413                DQ.push_back(variables[i]);
1414            } else if (cube[i] == 1) {
1415                CQ.push_back(variables[i]);
1416            }
1417        }
1418        if (!DQ.empty()) {
1419            while (DQ.size() > 1) {
1420                PabloAST * v1 = DQ.front(); DQ.pop_front();
1421                PabloAST * v2 = DQ.front(); DQ.pop_front();
1422                DQ.push_back(builder.createOr(v1, v2));
1423                ++count;
1424            }
1425            CQ.push_back(builder.createNot(DQ.front()));
1426            DQ.clear();
1427        }
1428        while (CQ.size() > 1) {
1429            PabloAST * v1 = CQ.front(); CQ.pop_front();
1430            PabloAST * v2 = CQ.front(); CQ.pop_front();
1431            CQ.push_back(builder.createAnd(v1, v2));
1432            ++count;
1433        }
1434        SQ.push(CQ.front()); CQ.clear();
1435    }
1436    Cudd_RecursiveDeref(manager, g);
1437
1438    while (SQ.size() > 1) {
1439        PabloAST * v1 = SQ.front(); SQ.pop();
1440        PabloAST * v2 = SQ.front(); SQ.pop();
1441        SQ.push(builder.createOr(v1, v2));
1442        ++count;
1443    }
1444
1445    return std::make_pair(SQ.front(), count);
1446}
1447
1448///** ------------------------------------------------------------------------------------------------------------- *
1449// * @brief reduce
1450// ** ------------------------------------------------------------------------------------------------------------- */
1451//inline bool isBinaryOp(const PabloAST * const expr) {
1452//    switch (expr->getClassTypeId()) {
1453//        case PabloAST::ClassTypeId::And:
1454//        case PabloAST::ClassTypeId::Or:
1455//        case PabloAST::ClassTypeId::Not:
1456//        case PabloAST::ClassTypeId::Xor:
1457//        case PabloAST::ClassTypeId::Sel:
1458//            return true;
1459//        default:
1460//            return false;
1461//    }
1462//}
1463
1464///** ------------------------------------------------------------------------------------------------------------- *
1465// * @brief minimizeCoFactor
1466// ** ------------------------------------------------------------------------------------------------------------- */
1467//PabloAST * minimizeCoFactor(DdManager * const manager, DdNode * const f, const std::vector<PabloAST *> & variables, PabloBuilder & builder) {
1468
1469//    std::queue<PabloAST *> SQ;
1470//    std::queue<PabloAST *> CQ;
1471//    std::queue<PabloAST *> DQ;
1472
1473//    int cube[manager->size];
1474
1475//    DdNode * g = f;
1476
1477//    Cudd_Ref(g);
1478
1479//    while (g != Cudd_ReadLogicZero(manager)) {
1480//        int length;
1481//        DdNode * implicant = Cudd_LargestCube(manager, g, &length);
1482//        if (LLVM_UNLIKELY(implicant == nullptr)) {
1483//            Cudd_RecursiveDeref(manager, g);
1484//            std::cerr << "Cudd_LargestCube" << std::endl;
1485//            return nullptr;
1486//        }
1487//        Cudd_Ref(implicant);
1488//        DdNode * prime = Cudd_bddMakePrime(manager, implicant, f);
1489//        if (LLVM_UNLIKELY(prime == nullptr)) {
1490//            Cudd_RecursiveDeref(manager, g);
1491//            Cudd_RecursiveDeref(manager, implicant);
1492//            std::cerr << "Cudd_bddMakePrime" << std::endl;
1493//            return nullptr;
1494//        }
1495//        Cudd_Ref(prime);
1496//        Cudd_RecursiveDeref(manager, implicant);
1497
1498//        DdNode * h = Cudd_bddAnd(manager, g, Cudd_Not(prime));
1499//        if (LLVM_UNLIKELY(h == nullptr)) {
1500//            Cudd_RecursiveDeref(manager, g);
1501//            Cudd_RecursiveDeref(manager, prime);
1502//            std::cerr << "Cudd_bddAnd" << std::endl;
1503//            return nullptr;
1504//        }
1505//        Cudd_Ref(h);
1506//        Cudd_RecursiveDeref(manager, g);
1507
1508//        g = h;
1509//        if (LLVM_UNLIKELY(Cudd_BddToCubeArray(manager, prime, cube) == 0)) {
1510//            Cudd_RecursiveDeref(manager, g);
1511//            Cudd_RecursiveDeref(manager, prime);
1512//            std::cerr << "Cudd_BddToCubeArray" << std::endl;
1513//            return nullptr;
1514//        }
1515//        Cudd_RecursiveDeref(manager, prime);
1516
1517//        for (auto i = 0; i != manager->size; ++i) {
1518//            if (cube[i] == 0) {
1519//                DQ.push(variables[i]);
1520//            } else if (cube[i] == 1) {
1521//                CQ.push(variables[i]);
1522//            }
1523//        }
1524
1525//        if (DQ.size() > 0) {
1526//            while (DQ.size() > 1) {
1527//                PabloAST * v1 = DQ.front(); DQ.pop();
1528//                PabloAST * v2 = DQ.front(); DQ.pop();
1529//                DQ.push(builder.createOr(v1, v2));
1530//            }
1531//            CQ.push(builder.createNot(DQ.front())); DQ.pop();
1532//        }
1533
1534//        while (CQ.size() > 1) {
1535//            PabloAST * v1 = CQ.front(); CQ.pop();
1536//            PabloAST * v2 = CQ.front(); CQ.pop();
1537//            CQ.push(builder.createAnd(v1, v2));
1538//        }
1539
1540//        SQ.push(CQ.front()); CQ.pop();
1541//    }
1542//    Cudd_RecursiveDeref(manager, g);
1543
1544//    while (SQ.size() > 1) {
1545//        PabloAST * v1 = SQ.front(); SQ.pop();
1546//        PabloAST * v2 = SQ.front(); SQ.pop();
1547//        SQ.push(builder.createOr(v1, v2));
1548//    }
1549
1550//    return SQ.front();
1551//}
1552
1553///** ------------------------------------------------------------------------------------------------------------- *
1554// * @brief minimize
1555// ** ------------------------------------------------------------------------------------------------------------- */
1556//PabloAST * minimize(DdManager * const manager, DdNode * const f, const std::vector<PabloAST *> & variables, PabloBuilder & builder) {
1557//     DdNode * g = Cudd_FindEssential(manager, f);
1558//    if (f == g || g == nullptr || Cudd_SupportSize(manager, g) == 0) {
1559////        g = Cudd_SubsetCompress(manager, f, Cudd_SupportSize(manager, f), Cudd_DagSize(f));
1560////        if (f == g || g == nullptr) {
1561//            return minimizeCoFactor(manager, f, variables, builder);
1562////        }
1563//    }
1564//    Cudd_Ref(g);
1565//    PabloAST * essentialAST = minimize(manager, g, variables, builder);
1566//    if (LLVM_UNLIKELY(essentialAST == nullptr)) {
1567//        Cudd_RecursiveDeref(manager, g);
1568//        return nullptr;
1569//    }
1570//    DdNode * h = Cudd_Cofactor(manager, f, g);
1571//    Cudd_Ref(h);
1572//    Cudd_RecursiveDeref(manager, g);
1573//    PabloAST * cofactorAST = minimize(manager, h, variables, builder);
1574//    Cudd_RecursiveDeref(manager, h);
1575//    if (LLVM_UNLIKELY(cofactorAST == nullptr)) {
1576//        if (LLVM_LIKELY(isa<Statement>(essentialAST))) {
1577//            cast<Statement>(essentialAST)->eraseFromParent(true);
1578//        }
1579//        return nullptr;
1580//    }
1581//    return builder.createAnd(essentialAST, cofactorAST);
1582//}
1583
1584///** ------------------------------------------------------------------------------------------------------------- *
1585// * @brief reduce
1586// ** ------------------------------------------------------------------------------------------------------------- */
1587//void AutoMultiplexing::reduce(const std::vector<std::vector<PabloAST *>> & sets) const {
1588
1589//    for (const auto & set : sets) {
1590
1591//        // first do a BFS to build a topological ordering of statements we're going to end up visiting
1592//        // and determine which of those will be terminals in the BDD
1593//        using Graph = adjacency_list<hash_setS, vecS, bidirectionalS, PabloAST *>;
1594//        using Vertex = Graph::vertex_descriptor;
1595
1596//        Graph G;
1597//        std::unordered_map<PabloAST *, unsigned> M;
1598
1599//        std::queue<Statement *> Q;
1600
1601//        for (PabloAST * inst : set) {
1602//            if (LLVM_LIKELY(isa<Advance>(inst))) {
1603//                const auto u = add_vertex(inst, G);
1604//                M.insert(std::make_pair(inst, u));
1605
1606//                for (PabloAST * user : inst->users()) {
1607//                    auto f = M.find(user);
1608//                    Vertex v = 0;
1609//                    if (f == M.end()) {
1610//                        v = add_vertex(user, G);
1611//                        M.insert(std::make_pair(user, v));
1612//                        if (isBinaryOp(user)) {
1613//                            Q.push(cast<Statement>(user));
1614//                        }
1615//                    } else { // if (f != M.end()) {
1616//                        v = f->second;
1617//                    }
1618//                    add_edge(u, v, G);
1619//                }
1620
1621//            }
1622//        }
1623
1624//        while (!Q.empty()) {
1625//            Statement * const var = Q.front(); Q.pop();
1626//            const Vertex u = M[var];
1627
1628//            for (unsigned i = 0; i != var->getNumOperands(); ++i) {
1629//                PabloAST * operand = var->getOperand(i);
1630//                auto f = M.find(operand);
1631//                Vertex v;
1632//                if (LLVM_UNLIKELY(f == M.end())) {
1633//                    v = add_vertex(operand, G);
1634//                    M.insert(std::make_pair(operand, v));
1635//                } else { // if (f != M.end()) {
1636//                    v = f->second;
1637//                }
1638//                add_edge(v, u, G);
1639//            }
1640
1641//            for (PabloAST * user : var->users()) {
1642//                auto f = M.find(user);
1643//                Vertex v = 0;
1644//                if (LLVM_LIKELY(f == M.end())) {
1645//                    v = add_vertex(user, G);
1646//                    M.insert(std::make_pair(user, v));
1647//                    if (isBinaryOp(user)) {
1648//                        Q.push(cast<Statement>(user));
1649//                    }
1650//                } else { // if (f != M.end()) {
1651//                    v = f->second;
1652//                }
1653//                add_edge(u, v, G);
1654//            }
1655//        }
1656
1657//        // count the number of sinks (sources) so we know how many variables (terminals) will exist in the BDD
1658//        std::vector<Vertex> variable;
1659//        flat_set<Vertex> terminal;
1660//        for (auto u : make_iterator_range(vertices(G))) {
1661//            if (in_degree(u, G) == 0) {
1662//                variable.push_back(u);
1663//            }
1664//            if (out_degree(u, G) == 0) {
1665//                // the inputs to the sinks become the terminals in the BDD
1666//                for (auto e : make_iterator_range(in_edges(u, G))) {
1667//                    terminal.insert(source(e, G));
1668//                }
1669//            }
1670//        }
1671
1672//        DdManager * manager = Cudd_Init(variable.size(), 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0);
1673//        Cudd_AutodynEnable(manager, CUDD_REORDER_SIFT);
1674
1675//        std::vector<DdNode *> characterization(num_vertices(G), nullptr);
1676//        unsigned i = 0;
1677//        for (auto u : variable) {
1678//            characterization[u] = Cudd_bddIthVar(manager, i++);
1679//        }
1680
1681//        std::vector<Vertex> ordering;
1682//        ordering.reserve(num_vertices(G));
1683//        topological_sort(G, std::back_inserter(ordering));
1684
1685//        for (auto ui = ordering.rbegin(); ui != ordering.rend(); ++ui) {
1686
1687//            const Vertex u = *ui;
1688
1689//            if (characterization[u]) {
1690//                continue;
1691//            }
1692
1693//            std::array<DdNode *, 3> input;
1694
1695//            unsigned i = 0;
1696//            for (const auto e : make_iterator_range(in_edges(u, G))) {
1697//                input[i++] = characterization[source(e, G)];
1698
1699//            }
1700
1701//            assert (is<Statement>(G[u]) ? i == cast<Statement>(G[u])->getNumOperands() : i == 0);
1702
1703//            DdNode * bdd = nullptr;
1704//            bool characterized = true;
1705//            switch (G[u]->getClassTypeId()) {
1706//                case PabloAST::ClassTypeId::And:
1707//                    bdd = Cudd_bddAnd(manager, input[0], input[1]);
1708//                    break;
1709//                case PabloAST::ClassTypeId::Or:
1710//                    bdd = Cudd_bddOr(manager, input[0], input[1]);
1711//                    break;
1712//                case PabloAST::ClassTypeId::Not:
1713//                    bdd = Cudd_Not(input[0]);
1714//                    break;
1715//                case PabloAST::ClassTypeId::Xor:
1716//                    bdd = Cudd_bddXor(manager, input[0], input[1]);
1717//                    break;
1718//                case PabloAST::ClassTypeId::Sel:
1719//                    bdd = Cudd_bddIte(manager, input[0], input[1], input[2]);
1720//                    break;
1721//                default: characterized = false; break;
1722//            }
1723
1724//            if (characterized) {
1725//                Cudd_Ref(bdd);
1726//                characterization[u] = bdd;
1727//            }
1728//        }
1729
1730//        Cudd_AutodynDisable(manager);
1731//        Cudd_ReduceHeap(manager, CUDD_REORDER_SIFT, 0);
1732
1733//        std::vector<PabloAST *> inputs;
1734//        for (Vertex s : variable) {
1735//            inputs.push_back(G[s]);
1736//        }
1737
1738//        for (Vertex t : terminal) {
1739//            Statement * const stmt = cast<Statement>(G[t]);
1740//            PabloBlock * const block = stmt->getParent();
1741//            block->setInsertPoint(stmt);
1742//            PabloBuilder builder(*block);
1743//            DdNode * const f = characterization[t];
1744//            llvm::raw_os_ostream out(std::cerr);
1745//            PabloPrinter::print(stmt, " > ", out); out << '\n'; out.flush();
1746
1747//            Cudd_Ref(f);
1748//            PabloAST * expr = minimize(manager, f, inputs, builder);
1749//            if (LLVM_LIKELY(expr != nullptr)) {
1750//                stmt->replaceWith(expr);
1751//            } else {
1752//                llvm::raw_os_ostream out(std::cerr);
1753//                PabloPrinter::print(stmt, "Failed to minimize: ", out); out << '\n'; out.flush();
1754//            }
1755//            Cudd_RecursiveDeref(manager, f);
1756//        }
1757//        Cudd_Quit(manager);
1758//    }
1759//}
1760
1761/** ------------------------------------------------------------------------------------------------------------- *
1762 * @brief topologicalSort
1763 *
1764 * After transforming the IR, we need to run this in order to always have a valid program. Each multiplex set
1765 * contains vertices corresponding to an Advance in the IR. While we know each Advance within a set is independent
1766 * w.r.t. the transitive closure of their dependencies in the IR, the position of each Advance's dependencies and
1767 * users within the IR isn't taken into consideration. Thus while there must be a valid ordering for the program,
1768 * it's not necessarily the original ordering.
1769 ** ------------------------------------------------------------------------------------------------------------- */
1770void AutoMultiplexing::topologicalSort(PabloBlock & entry) const {
1771    // Note: not a real topological sort. I expect the original graph to be close to the resulting one. Thus cost
1772    // of constructing a graph in which to perform the sort takes longer than potentially moving an instruction
1773    // multiple times.
1774    std::unordered_set<const PabloAST *> encountered;
1775    std::stack<Statement *> scope;
1776    for (Statement * stmt = entry.front(); ; ) { restart:
1777        while ( stmt ) {
1778            for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
1779                PabloAST * const op = stmt->getOperand(i);
1780                if (LLVM_LIKELY(isa<Statement>(op))) {
1781                    if (LLVM_UNLIKELY(encountered.count(op) == 0)) {
1782                        if (LLVM_UNLIKELY(isa<While>(stmt) && isa<Next>(op))) {
1783                            if (encountered.count(cast<Next>(op)->getInitial()) != 0) {
1784                                continue;
1785                            }
1786                        }
1787                        Statement * const next = stmt->getNextNode();
1788                        stmt->insertAfter(cast<Statement>(op));
1789                        stmt = next;
1790                        goto restart;
1791                    }
1792                }
1793            }
1794            if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
1795                // Set the next statement to be the first statement of the inner scope and push the
1796                // next statement of the current statement into the scope stack.
1797                const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
1798                scope.push(stmt->getNextNode());
1799                stmt = nested.front();
1800                continue;
1801            }
1802            encountered.insert(stmt);
1803            stmt = stmt->getNextNode();
1804        }
1805        if (scope.empty()) {
1806            break;
1807        }
1808        stmt = scope.top();
1809        scope.pop();
1810    }
1811}
1812
1813} // end of namespace pablo
1814
Note: See TracBrowser for help on using the repository browser.