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

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

Temporary check in

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