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

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

Misc. changes and start of dependency chain analysis in ucd generator.

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