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

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

Temporary check-in.

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