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

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

Added ability to limit the size of candidate multiplexing sets and choose a sample of the possible combinations.

File size: 49.5 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>
[4808]19#include <pablo/optimizers/booleanreassociationpass.h>
[4775]20#include <pablo/analysis/pabloverifier.hpp>
[4287]21
22using namespace llvm;
[4569]23using namespace boost;
24using namespace boost::container;
25using namespace boost::numeric::ublas;
[4287]26
[4809]27// #define PRINT_DEBUG_OUTPUT
[4596]28
[4638]29#if !defined(NDEBUG) && !defined(PRINT_DEBUG_OUTPUT)
30#define PRINT_DEBUG_OUTPUT
31#endif
32
33#ifdef PRINT_DEBUG_OUTPUT
34
[4601]35#include <iostream>
[4242]36
[4601]37using namespace pablo;
[4596]38typedef uint64_t timestamp_t;
39
40static inline timestamp_t read_cycle_counter() {
41#ifdef __GNUC__
42timestamp_t ts;
43#ifdef __x86_64__
44  unsigned int eax, edx;
45  asm volatile("rdtsc" : "=a" (eax), "=d" (edx));
46  ts = ((timestamp_t) eax) | (((timestamp_t) edx) << 32);
47#else
48  asm volatile("rdtsc\n" : "=A" (ts));
49#endif
50  return(ts);
51#endif
52#ifdef _MSC_VER
53  return __rdtsc();
54#endif
55}
56
[4600]57#define LOG(x) std::cerr << x << std::endl;
[4601]58#define RECORD_TIMESTAMP(Name) const timestamp_t Name = read_cycle_counter()
59#define LOG_GRAPH(Name, G) \
60    LOG(Name << " |V|=" << num_vertices(G) << ", |E|="  << num_edges(G) << \
61                " (" << (((double)num_edges(G)) / ((double)(num_vertices(G) * (num_vertices(G) - 1) / 2))) << ')')
62
63unsigned __count_advances(const PabloBlock & entry) {
64
65    std::stack<const Statement *> scope;
66    unsigned advances = 0;
67
68    // Scan through and collect all the advances, calls, scanthrus and matchstars ...
69    for (const Statement * stmt = entry.front(); ; ) {
70        while ( stmt ) {
71            if (isa<Advance>(stmt)) {
72                ++advances;
73            }
74            else if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
75                // Set the next statement to be the first statement of the inner scope and push the
76                // next statement of the current statement into the scope stack.
77                const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
78                scope.push(stmt->getNextNode());
79                stmt = nested.front();
80                assert (stmt);
81                continue;
82            }
83            stmt = stmt->getNextNode();
84        }
85        if (scope.empty()) {
86            break;
87        }
88        stmt = scope.top();
89        scope.pop();
90    }
91    return advances;
92}
93
94#define LOG_NUMBER_OF_ADVANCES(entry) LOG("|Advances|=" << __count_advances(entry))
95
[4600]96#else
97#define LOG(x)
[4601]98#define RECORD_TIMESTAMP(Name)
99#define LOG_GRAPH(Name, G)
100#define LOG_NUMBER_OF_ADVANCES(entry)
[4600]101#endif
[4596]102
[4600]103
[4601]104namespace pablo {
105
[4772]106using TypeId = PabloAST::ClassTypeId;
107
[4822]108bool AutoMultiplexing::optimize(PabloFunction & function, const unsigned limit, const unsigned maxSelections) {
[4600]109
[4797]110//    std::random_device rd;
111//    const auto seed = rd();
[4695]112    const auto seed = 83234827342;
[4600]113    RNG rng(seed);
114
115    LOG("Seed:                    " << seed);
116
[4822]117    AutoMultiplexing am(limit, maxSelections);
[4601]118    RECORD_TIMESTAMP(start_initialize);
[4686]119    const bool abort = am.initialize(function);
[4601]120    RECORD_TIMESTAMP(end_initialize);
[4600]121
122    LOG("Initialize:              " << (end_initialize - start_initialize));
123
[4657]124    LOG_NUMBER_OF_ADVANCES(function.getEntryBlock());
[4601]125
[4686]126    if (abort) {
[4665]127        return false;
128    }
129
[4601]130    RECORD_TIMESTAMP(start_characterize);
[4657]131    am.characterize(function.getEntryBlock());
[4601]132    RECORD_TIMESTAMP(end_characterize);
[4600]133
134    LOG("Characterize:            " << (end_characterize - start_characterize));
135
[4601]136    RECORD_TIMESTAMP(start_create_multiplex_graph);
[4650]137    const bool multiplex = am.generateCandidateSets(rng);
[4601]138    RECORD_TIMESTAMP(end_create_multiplex_graph);
[4722]139    LOG("GenerateCandidateSets:   " << (end_create_multiplex_graph - start_create_multiplex_graph));
[4596]140
[4711]141    RECORD_TIMESTAMP(start_shutdown);
142    am.Shutdown();
143    RECORD_TIMESTAMP(end_shutdown);
144    LOG("Shutdown:                " << (end_shutdown - start_shutdown));
145
[4596]146    if (multiplex) {
[4600]147
[4610]148        RECORD_TIMESTAMP(start_select_multiplex_sets);
[4608]149        am.selectMultiplexSets(rng);
[4610]150        RECORD_TIMESTAMP(end_select_multiplex_sets);
151        LOG("SelectMultiplexSets:     " << (end_select_multiplex_sets - start_select_multiplex_sets));
[4600]152
[4601]153        RECORD_TIMESTAMP(start_subset_constraints);
[4578]154        am.applySubsetConstraints();
[4601]155        RECORD_TIMESTAMP(end_subset_constraints);
[4600]156        LOG("ApplySubsetConstraints:  " << (end_subset_constraints - start_subset_constraints));
157
[4601]158        RECORD_TIMESTAMP(start_select_independent_sets);
[4775]159        am.multiplexSelectedIndependentSets(function);
[4601]160        RECORD_TIMESTAMP(end_select_independent_sets);
[4722]161        LOG("SelectedIndependentSets: " << (end_select_independent_sets - start_select_independent_sets));
[4775]162
[4797]163        #ifndef NDEBUG
164        PabloVerifier::verify(function, "post-multiplexing");
165        #endif
166
[4775]167        Simplifier::optimize(function);
[4578]168    }
[4596]169
[4659]170    LOG_NUMBER_OF_ADVANCES(function.getEntryBlock());
[4601]171    return multiplex;
[4242]172}
173
[4569]174/** ------------------------------------------------------------------------------------------------------------- *
175 * @brief initialize
[4665]176 * @param function the function to optimize
177 * @returns true if there are fewer than three advances in this function
[4569]178 *
179 * Scan through the program to identify any advances and calls then initialize the BDD engine with
180 * the proper variable ordering.
181 ** ------------------------------------------------------------------------------------------------------------- */
[4665]182bool AutoMultiplexing::initialize(PabloFunction & function) {
[4242]183
[4600]184    flat_map<const PabloAST *, unsigned> map;   
[4611]185    std::stack<Statement *> scope;
[4680]186    unsigned variableCount = 0; // number of statements that cannot always be categorized without generating a new variable
[4521]187
[4569]188    // Scan through and collect all the advances, calls, scanthrus and matchstars ...
[4583]189    unsigned n = 0, m = 0;
[4657]190    for (Statement * stmt = function.getEntryBlock().front(); ; ) {
[4570]191        while ( stmt ) {
[4569]192            ++n;
193            if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
[4536]194                // Set the next statement to be the first statement of the inner scope and push the
195                // next statement of the current statement into the scope stack.
[4569]196                const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
[4775]197                mResolvedScopes.emplace(&nested, stmt);
[4536]198                scope.push(stmt->getNextNode());
[4569]199                stmt = nested.front();
200                assert (stmt);
201                continue;
[4536]202            }
[4583]203
[4659]204            assert ("Run the Simplifer pass prior to this!" && (stmt->getNumUses() > 0));
[4586]205
[4569]206            switch (stmt->getClassTypeId()) {
[4772]207                case TypeId::Advance:
[4611]208                    mAdvanceMap.emplace(stmt, m);
[4579]209                    map.emplace(stmt, m++);
[4772]210                case TypeId::Call:
211                case TypeId::ScanThru:
212                case TypeId::MatchStar:
[4680]213                    variableCount++;
[4569]214                    break;
215                default:
216                    break;
[4521]217            }
[4570]218            stmt = stmt->getNextNode();
[4569]219        }
220        if (scope.empty()) {
221            break;
222        }
223        stmt = scope.top();
224        scope.pop();
225    }
[4521]226
[4665]227    // If there are fewer than three Advances in this program, just abort. We cannot reduce it.
[4686]228    if (m < 3) {
[4665]229        return true;
230    }
231
[4570]232    // Create the transitive closure matrix of graph. From this we'll construct
233    // two graphs restricted to the relationships between advances. The first will
234    // be a path graph, which is used to bypass testing for mutual exclusivity of
235    // advances that cannot be multiplexed. The second is a transitive reduction
236    // of that graph, which forms the basis of our constraint graph when deciding
237    // which advances ought to be multiplexed.
238
[4579]239    matrix<bool> G(n, m); // Let G be a matrix with n rows of m (Advance) elements
[4569]240    G.clear();
241    for (unsigned i = 0; i != m; ++i) {
242        G(i, i) = true;
243    }
[4521]244
[4583]245    n = m;
[4582]246    m = 0;
[4583]247
[4657]248    const Statement * stmt = function.getEntryBlock().front();
[4582]249    for (;;) {
[4570]250        while ( stmt ) {
[4583]251
[4570]252            unsigned u;
[4579]253            if (isa<Advance>(stmt)) {
[4611]254                assert (mAdvanceMap.count(stmt) && mAdvanceMap[stmt] == m);
[4583]255                u = m++;
[4570]256            }
257            else {
[4583]258                u = n++;
[4570]259                map.emplace(stmt, u);
260            }
[4583]261
[4569]262            for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
[4582]263                const PabloAST * const op = stmt->getOperand(i);
[4583]264                if (LLVM_LIKELY(isa<Statement>(op))) {
265                    const unsigned v = map[op];
266                    for (unsigned w = 0; w != m; ++w) {
267                        G(u, w) |= G(v, w);
268                    }
[4570]269                }
[4536]270            }
[4569]271            if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
[4579]272                // Set the next statement to be the first statement of the inner scope
273                // and push the next statement of the current statement into the stack.
[4569]274                const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
275                scope.push(stmt->getNextNode());
276                stmt = nested.front();
277                assert (stmt);
278                continue;
279            }
[4570]280            stmt = stmt->getNextNode();
[4521]281        }
[4536]282        if (scope.empty()) {
283            break;
284        }
285        stmt = scope.top();
286        scope.pop();
287    }
[4521]288
[4601]289    // Record the path / base constraint graph after removing any reflexive-loops.
290    // Since G is a use-def graph and we want our constraint graph to be a def-use graph,
291    // reverse the edges as we're writing them to obtain the transposed graph.
292    mConstraintGraph = ConstraintGraph(m);
293    mSubsetGraph = SubsetGraph(m);
294
[4583]295    for (unsigned i = 0; i != m; ++i) {
296        G(i, i) = false;
297        for (unsigned j = 0; j != m; ++j) {
[4569]298            if (G(i, j)) {
[4601]299                add_edge(j, i, mConstraintGraph);
[4569]300            }
[4583]301        }       
[4569]302    }
[4521]303
[4579]304    // Initialize the BDD engine ...
[4680]305    mManager = Cudd_Init((variableCount + function.getNumOfParameters()), 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0);
[4594]306    Cudd_AutodynDisable(mManager);
[4583]307
308    // Map the predefined 0/1 entries
[4788]309    mCharacterizationMap[PabloBlock::createZeroes()] = Zero();
310    mCharacterizationMap[PabloBlock::createOnes()] = One();
[4583]311
[4579]312    // Order the variables so the input Vars are pushed to the end; they ought to
[4570]313    // be the most complex to resolve.
[4680]314    for (auto i = 0; i != function.getNumOfParameters(); ++i) {
315        mCharacterizationMap[function.getParameter(i)] = Cudd_bddIthVar(mManager, variableCount++);
[4569]316    }
[4665]317
318    return false;
[4569]319}
[4521]320
[4569]321/** ------------------------------------------------------------------------------------------------------------- *
322 * @brief characterize
323 * @param vars the input vars for this program
324 *
325 * Scan through the program and iteratively compute the BDDs for each statement.
326 ** ------------------------------------------------------------------------------------------------------------- */
[4646]327void AutoMultiplexing::characterize(PabloBlock &block) {
[4611]328    for (Statement * stmt : block) {
329        if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
[4646]330            const auto start = mRecentCharacterizations.size();
[4611]331            characterize(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
[4646]332            assert (mRecentCharacterizations.size() >= start);
333            if (isa<If>(stmt)) {
334                const auto & defined = cast<const If>(stmt)->getDefined();
335                for (auto pair = mRecentCharacterizations.begin() + start; pair != mRecentCharacterizations.end(); ++pair) {
336                    const PabloAST * expr = nullptr;
337                    DdNode * bdd = nullptr;
338                    std::tie(expr, bdd) = *pair;
339                    if (LLVM_UNLIKELY(isa<Assign>(expr))) {
340                        if (LLVM_LIKELY(std::find(defined.begin(), defined.end(), expr) != defined.end())) {
341                            continue;
342                        }
343                    }
344                    mCharacterizationMap.erase(mCharacterizationMap.find(expr));
345                    if (LLVM_UNLIKELY(Cudd_IsConstant(bdd))) {
346                        continue;
347                    }
348                    Deref(bdd);
349                }
350            }
351            else { // if isa<While>(stmt)
352                const auto & variants = cast<const While>(stmt)->getVariants();
353                for (auto pair = mRecentCharacterizations.begin() + start; pair != mRecentCharacterizations.end(); ++pair) {
354                    const PabloAST * expr = nullptr;
355                    DdNode * bdd = nullptr;
356                    std::tie(expr, bdd) = *pair;
357                    if (LLVM_UNLIKELY(isa<Next>(expr))) {
358                        if (LLVM_LIKELY(std::find(variants.begin(), variants.end(), expr) != variants.end())) {
359                            DdNode *& next = mCharacterizationMap[expr];
360                            next = Or(next, bdd);
361                            Ref(next);
362                            continue;
363                        }
364                    }
365                    mCharacterizationMap.erase(mCharacterizationMap.find(expr));
366                    if (LLVM_UNLIKELY(Cudd_IsConstant(bdd))) {
367                        continue;
368                    }
369                    Deref(bdd);
370                }
371            }
372            mRecentCharacterizations.erase(mRecentCharacterizations.begin() + start, mRecentCharacterizations.end());
[4611]373            continue;
374        }
[4646]375
376        DdNode * var = characterize(stmt);
[4722]377        mCharacterizationMap[stmt] = var;       
[4611]378    }
379}
[4521]380
[4611]381/** ------------------------------------------------------------------------------------------------------------- *
382 * @brief characterize
383 ** ------------------------------------------------------------------------------------------------------------- */
[4629]384inline DdNode * AutoMultiplexing::characterize(Statement * const stmt) {
[4521]385
[4611]386    DdNode * bdd = nullptr;
387    // Map our operands to the computed BDDs
388    std::array<DdNode *, 3> input;
[4751]389    for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
390        PabloAST * const op = stmt->getOperand(i);
[4611]391        if (LLVM_UNLIKELY(isa<Integer>(op) || isa<String>(op))) {
392            continue;
393        }
394        auto f = mCharacterizationMap.find(op);
395        if (LLVM_UNLIKELY(f == mCharacterizationMap.end())) {
[4629]396            std::string tmp;
397            llvm::raw_string_ostream msg(tmp);
[4751]398            msg << "AutoMultiplexing: Uncharacterized operand " << std::to_string(i);
[4629]399            PabloPrinter::print(stmt, " of ", msg);
400            throw std::runtime_error(msg.str());
[4611]401        }
[4751]402        input[i] = f->second;
[4611]403    }
[4594]404
[4611]405    switch (stmt->getClassTypeId()) {
[4772]406        case TypeId::Assign:
407        case TypeId::Next:
[4646]408            bdd = input[0];
409            break;
[4772]410        case TypeId::And:
[4611]411            bdd = And(input[0], input[1]);
[4646]412            break;       
[4772]413        case TypeId::Or:
[4646]414            bdd = Or(input[0], input[1]);
[4611]415            break;
[4772]416        case TypeId::Xor:
[4646]417            bdd = Xor(input[0], input[1]);
418            break;
[4772]419        case TypeId::Not:
[4646]420            bdd = Not(input[0]);
421            break;
[4772]422        case TypeId::Sel:
[4611]423            bdd = Ite(input[0], input[1], input[2]);
424            break;
[4772]425        case TypeId::ScanThru:
[4611]426            // It may be possible use "Not(input[1])" for ScanThrus if we rule out the possibility
427            // of a contradition being erroneously calculated later. An example of this
428            // would be ¬(ScanThru(c,m) √ m)
[4772]429        case TypeId::MatchStar:
430        case TypeId::Call:
[4646]431            bdd = NewVar();
432            mRecentCharacterizations.emplace_back(stmt, bdd);
433            return bdd;
[4772]434        case TypeId::Advance:
[4646]435            // This returns so that it doesn't mistakeningly replace the Advance with 0 or add it
436            // to the list of recent characterizations.
[4612]437            return characterize(cast<Advance>(stmt), input[0]);
[4611]438        default:
439            throw std::runtime_error("Unexpected statement type " + stmt->getName()->to_string());
440    }
[4646]441    Ref(bdd);
442    mRecentCharacterizations.emplace_back(stmt, bdd);
[4611]443    return bdd;
444}
445
446/** ------------------------------------------------------------------------------------------------------------- *
447 * @brief characterize
448 ** ------------------------------------------------------------------------------------------------------------- */
[4646]449inline DdNode * AutoMultiplexing::characterize(Advance *adv, DdNode * input) {
[4611]450    DdNode * Ik, * Ck, * Nk;
451    if (LLVM_UNLIKELY(isZero(input))) {
452        Ik = Ck = Nk = Zero();
453    }
454    else {
455
456        Ik = input;
[4646]457        Ref(input);
[4611]458        Ck = NewVar();
459        Nk = Not(Ck);
460
461        assert (mAdvanceMap.count(adv));
462
463        const auto k = mAdvanceMap[adv];
464
465        std::vector<bool> unconstrained(k , false);
466
467        // Can we use a transposed copy of the subset graph to determine an ordering of variables?
468        for (unsigned i = 0; i != k; ++i) {
469            // Have we already proven that these are unconstrained by the subset relationships?
470            if (unconstrained[i]) continue;
471            Advance * tmp = std::get<0>(mAdvance[i]);
472            // If these advances are "shifting" their values by the same amount and aren't transitively dependant ...
473            if ((adv->getOperand(1) == tmp->getOperand(1)) && (notTransitivelyDependant(i, k))) {
474                DdNode * Ii = std::get<1>(mAdvance[i]);
[4638]475                DdNode * const IiIk = And(Ik, Ii);
[4646]476                Ref(IiIk);
[4611]477                // Is there any satisfying truth assignment? If not, these streams are mutually exclusive.
[4639]478                if (NoSatisfyingAssignment(IiIk)) {
[4611]479                    assert (mCharacterizationMap.count(tmp));
480                    DdNode *& Ci = mCharacterizationMap[tmp];
481                    // Mark the i-th and k-th Advances as being mutually exclusive
[4646]482                    DdNode * Ni = std::get<2>(mAdvance[i]);
483                    Ck = And(Ck, Ni); Ref(Ck);
484                    Ci = And(Ci, Nk); Ref(Ci);
[4611]485                    // If Ai ∩ Ak = ∅ and Aj ⊂ Ai, Aj ∩ Ak = ∅.
486                    graph_traits<SubsetGraph>::in_edge_iterator ei, ei_end;
487                    for (std::tie(ei, ei_end) = in_edges(i, mSubsetGraph); ei != ei_end; ++ei) {
488                        const auto j = source(*ei, mSubsetGraph);
489                        if (notTransitivelyDependant(k, j)) {
490                            Advance * adv = std::get<0>(mAdvance[j]);
491                            assert (mCharacterizationMap.count(adv));
492                            DdNode *& Cj = mCharacterizationMap[adv];
493                            DdNode * Nj = std::get<2>(mAdvance[j]);
494                            // Mark the i-th and j-th Advances as being mutually exclusive
[4646]495                            Ck = And(Ck, Nj); Ref(Ck);
496                            Cj = And(Cj, Nk); Ref(Cj);
[4611]497                            unconstrained[j] = true;
498                        }
499                    }
500                    unconstrained[i] = true;
[4569]501                }
[4611]502                else if (Ik == IiIk) {
503                    // If Ik = Ii ∩ Ik then Ik ⊂ Ii. Record this in the subset graph with the arc (k,i).
504                    // These edges will be moved into the multiplex set graph if Ai and Ak happen to be
505                    // in the same mutually exclusive set.
506                    add_edge(k, i, mSubsetGraph);
507                    // If Ak ⊂ Ai and Ai ⊂ Aj, Ak ⊂ Aj.
508                    graph_traits<SubsetGraph>::out_edge_iterator ei, ei_end;
509                    for (std::tie(ei, ei_end) = out_edges(i, mSubsetGraph); ei != ei_end; ++ei) {
510                        const auto j = target(*ei, mSubsetGraph);
511                        add_edge(k, j, mSubsetGraph);
512                        unconstrained[j] = true;
513                    }
514                    unconstrained[i] = true;
[4569]515                }
[4611]516                else if (Ii == IiIk) {
517                    // If Ii = Ii ∩ Ik then Ii ⊂ Ik. Record this in the subset graph with the arc (i,k).
518                    add_edge(i, k, mSubsetGraph);
519                    // If Ai ⊂ Ak and Aj ⊂ Ai, Aj ⊂ Ak.
520                    graph_traits<SubsetGraph>::in_edge_iterator ei, ei_end;
521                    for (std::tie(ei, ei_end) = in_edges(i, mSubsetGraph); ei != ei_end; ++ei) {
522                        const auto j = source(*ei, mSubsetGraph);
523                        add_edge(j, k, mSubsetGraph);
524                        unconstrained[j] = true;
525                    }
526                    unconstrained[i] = true;
527                }
[4646]528                Deref(IiIk);
[4569]529            }
[4611]530        }
[4242]531
[4611]532        for (unsigned i = 0; i != k; ++i) {
533            const Advance * const tmp = std::get<0>(mAdvance[i]);
534            // Even if these Advances are mutually exclusive, they must be in the same scope or they cannot be safely multiplexed.
535            if (!unconstrained[i] || (adv->getParent() != tmp->getParent())) {
536                // We want the constraint graph to be acyclic; since the dependencies are already in topological order,
537                // adding an arc from a lesser to greater numbered vertex won't induce a cycle.
538                add_edge(i, k, mConstraintGraph);
539            }
540        }
541    }
[4583]542
[4611]543    mAdvance.emplace_back(adv, Ik, Nk);
544    return Ck;
545}
[4601]546
[4611]547/** ------------------------------------------------------------------------------------------------------------- *
[4594]548 * @brief notTransitivelyDependant
549 ** ------------------------------------------------------------------------------------------------------------- */
[4610]550inline bool AutoMultiplexing::notTransitivelyDependant(const ConstraintVertex i, const ConstraintVertex j) const {
[4611]551    assert (i < num_vertices(mConstraintGraph) && j < num_vertices(mConstraintGraph));
[4601]552    return (mConstraintGraph.get_edge(i, j) == 0);
[4594]553}
554
555/** ------------------------------------------------------------------------------------------------------------- *
[4583]556 * @brief CUDD wrappers
557 ** ------------------------------------------------------------------------------------------------------------- */
558
[4592]559inline DdNode * AutoMultiplexing::Zero() const {
[4594]560    return Cudd_ReadLogicZero(mManager);
[4592]561}
562
563inline DdNode * AutoMultiplexing::One() const {
[4594]564    return Cudd_ReadOne(mManager);
[4592]565}
566
[4610]567inline DdNode * AutoMultiplexing::NewVar() {
[4646]568    DdNode * var = Cudd_bddIthVar(mManager, mVariables++);
569    return var;
[4610]570}
571
[4594]572inline bool AutoMultiplexing::isZero(DdNode * const x) const {
573    return x == Zero();
[4583]574}
575
[4594]576inline DdNode * AutoMultiplexing::And(DdNode * const x, DdNode * const y) {
[4648]577    return Cudd_bddAnd(mManager, x, y);
[4583]578}
579
[4594]580inline DdNode * AutoMultiplexing::Or(DdNode * const x, DdNode * const y) {
[4648]581    return Cudd_bddOr(mManager, x, y);
[4583]582}
583
[4594]584inline DdNode * AutoMultiplexing::Xor(DdNode * const x, DdNode * const y) {
[4648]585    return Cudd_bddXor(mManager, x, y);
[4583]586}
587
[4594]588inline DdNode * AutoMultiplexing::Not(DdNode * const x) const {
[4648]589    return Cudd_Not(x);
[4583]590}
591
[4594]592inline DdNode * AutoMultiplexing::Ite(DdNode * const x, DdNode * const y, DdNode * const z) {
[4648]593    return Cudd_bddIte(mManager, x, y, z);
[4583]594}
595
[4639]596inline bool AutoMultiplexing::NoSatisfyingAssignment(DdNode * const x) {
[4594]597    return Cudd_bddLeq(mManager, x, Zero());
[4583]598}
599
[4646]600inline void AutoMultiplexing::Ref(DdNode * const x) {
601    assert (x);
602    Cudd_Ref(x);
603}
604
605inline void AutoMultiplexing::Deref(DdNode * const x) {
606    assert (x);
607    Cudd_RecursiveDeref(mManager, x);
608}
609
[4639]610inline void AutoMultiplexing::Shutdown() {
[4650]611//    #ifdef PRINT_DEBUG_OUTPUT
612//    Cudd_PrintInfo(mManager, stderr);
613//    #endif
[4583]614    Cudd_Quit(mManager);
615}
616
617/** ------------------------------------------------------------------------------------------------------------- *
[4570]618 * @brief generateMultiplexSets
619 * @param RNG random number generator
[4569]620 ** ------------------------------------------------------------------------------------------------------------- */
[4650]621bool AutoMultiplexing::generateCandidateSets(RNG & rng) {
[4287]622
[4610]623    using degree_t = graph_traits<ConstraintGraph>::degree_size_type;
[4287]624
[4601]625    // What if we generated a "constraint free" graph instead? By taking each connected component of it
626    // and computing the complement of it (with the same lesser to greater index ordering), we should
627    // have the same problem here but decomposed into subgraphs.
628
[4650]629    VertexVector S;
[4648]630    std::vector<degree_t> D(num_vertices(mConstraintGraph));
[4650]631    S.reserve(15);
[4570]632
[4650]633    mMultiplexSetGraph = MultiplexSetGraph(num_vertices(mConstraintGraph));
[4610]634
[4650]635    // Push all source nodes into the new independent set N
636    for (auto v : make_iterator_range(vertices(mConstraintGraph))) {
637        const auto d = in_degree(v, mConstraintGraph);
638        D[v] = d;
639        if (d == 0) {
640            S.push_back(v);
[4569]641        }
[4650]642    }
[4287]643
[4736]644    assert (S.size() > 0);
645
[4650]646    auto remainingVerticies = num_vertices(mConstraintGraph) - S.size();
[4648]647
[4650]648    do {
[4648]649
[4822]650        addCandidateSet(S, rng);
[4583]651
[4650]652        bool noNewElements = true;
653        do {
[4736]654            assert (S.size() > 0);
[4650]655            // Randomly choose a vertex in S and discard it.
656            const auto i = S.begin() + IntDistribution(0, S.size() - 1)(rng);
[4736]657            assert (i != S.end());
658            const ConstraintVertex u = *i;           
659            S.erase(i);           
[4598]660
[4650]661            for (auto e : make_iterator_range(out_edges(u, mConstraintGraph))) {
662                const ConstraintVertex v = target(e, mConstraintGraph);
663                if ((--D[v]) == 0) {
664                    S.push_back(v);
[4736]665                    --remainingVerticies;
[4650]666                    noNewElements = false;
[4598]667                }
[4569]668            }
669        }
[4650]670        while (noNewElements && remainingVerticies);
[4648]671    }
[4650]672    while (remainingVerticies);
[4608]673
[4650]674    return num_vertices(mMultiplexSetGraph) > num_vertices(mConstraintGraph);
[4569]675}
[4287]676
[4570]677/** ------------------------------------------------------------------------------------------------------------- *
[4822]678 * @brief choose
679 ** ------------------------------------------------------------------------------------------------------------- */
680inline unsigned long choose(const unsigned n, const unsigned k) {
681    if (n < k)
682        return 0;
683    if (n == k || k == 0)
684        return 1;
685    unsigned long delta = k;
686    unsigned long max = n - k;
687    if (delta < max) {
688        std::swap(delta, max);
689    }
690    unsigned long result = delta + 1;
691    for (unsigned i = 2; i <= max; ++i) {
692        result = (result * (delta + i)) / i;
693    }
694    return result;
695}
696
697/** ------------------------------------------------------------------------------------------------------------- *
698 * @brief select
699 *
700 * James McCaffrey's algorithm for "Generating the mth Lexicographical Element of a Mathematical Combination"
701 ** ------------------------------------------------------------------------------------------------------------- */
702void select(const unsigned n, const unsigned k, const unsigned m, unsigned * element) {
703    unsigned long a = n;
704    unsigned long b = k;
705    unsigned long x = (choose(n, k) - 1) - m;
706    for (unsigned i = 0; i != k; ++i) {
707        while (choose(--a, b) > x);
708        x = x - choose(a, b);
709        b = b - 1;
710        element[i] = (n - 1) - a;
711    }
712}
713
714/** ------------------------------------------------------------------------------------------------------------- *
[4648]715 * @brief addCandidateSet
[4650]716 * @param S an independent set
[4570]717 ** ------------------------------------------------------------------------------------------------------------- */
[4822]718inline void AutoMultiplexing::addCandidateSet(const VertexVector & S, RNG & rng) {
[4650]719    if (S.size() >= 3) {
[4822]720        if (S.size() <= mLimit) {
721            const auto u = add_vertex(mMultiplexSetGraph);
722            for (const auto v : S) {
723                add_edge(u, v, mMultiplexSetGraph);
724            }
725        } else {
726            const auto max = choose(S.size(), mLimit);
727            unsigned element[mLimit];
728            if (LLVM_UNLIKELY(max <= mMaxSelections)) {
729                for (unsigned i = 0; i != max; ++i) {
730                    select(S.size(), mLimit, i, element);
731                    const auto u = add_vertex(mMultiplexSetGraph);
732                    for (unsigned j = 0; j != mLimit; ++j) {
733                        add_edge(u, S[element[j]], mMultiplexSetGraph);
734                    }
735                }
736            } else { // take m random samples
737                for (unsigned i = 0; i != mMaxSelections; ++i) {
738                    select(S.size(), mLimit, rng() % max, element);
739                    const auto u = add_vertex(mMultiplexSetGraph);
740                    for (unsigned j = 0; j != mLimit; ++j) {
741                        add_edge(u, S[element[j]], mMultiplexSetGraph);
742                    }
743                }
744            }
[4608]745        }
[4648]746    }
[4598]747}
[4586]748
[4598]749/** ------------------------------------------------------------------------------------------------------------- *
[4608]750 * @brief is_power_of_2
751 * @param n an integer
[4598]752 ** ------------------------------------------------------------------------------------------------------------- */
[4608]753static inline bool is_power_of_2(const size_t n) {
754    return ((n & (n - 1)) == 0) ;
[4570]755}
[4287]756
[4600]757/** ------------------------------------------------------------------------------------------------------------- *
[4608]758 * @brief log2_plus_one
[4600]759 ** ------------------------------------------------------------------------------------------------------------- */
[4608]760static inline size_t log2_plus_one(const size_t n) {
761    return std::log2<size_t>(n) + 1; // use a faster builtin function for this?
[4599]762}
763
[4571]764/** ------------------------------------------------------------------------------------------------------------- *
[4610]765 * @brief selectMultiplexSets
[4586]766 * @param RNG random number generator
[4610]767 *
768 * This algorithm is simply computes a greedy set cover. We want an exact max-weight set cover but can generate new
769 * sets by taking a subset of any existing set. With a few modifications, the greedy approach seems to work well
[4650]770 * enough but can be trivially shown to produce a suboptimal solution if there are three (or more) sets in which
771 * two, labelled A and B, are disjoint and the third larger set, C, that consists of elements of A and B.
[4571]772 ** ------------------------------------------------------------------------------------------------------------- */
[4608]773void AutoMultiplexing::selectMultiplexSets(RNG &) {
[4570]774
[4608]775    using InEdgeIterator = graph_traits<MultiplexSetGraph>::in_edge_iterator;
776    using degree_t = MultiplexSetGraph::degree_size_type;
777    using vertex_t = MultiplexSetGraph::vertex_descriptor;
[4287]778
[4608]779    const size_t m = num_vertices(mConstraintGraph);
780    const size_t n = num_vertices(mMultiplexSetGraph) - m;
[4571]781
[4608]782    std::vector<degree_t> remaining(n, 0);
783    std::vector<vertex_t> chosen_set(m, 0);
[4571]784
[4608]785    for (unsigned i = 0; i != n; ++i) {
786        remaining[i] = out_degree(i + m, mMultiplexSetGraph);
[4585]787    }
[4582]788
[4608]789    for (;;) {
[4583]790
[4610]791        // Choose the set with the greatest number of vertices not already included in some other set.
[4608]792        vertex_t k = 0;
793        degree_t w = 0;
794        for (vertex_t i = 0; i != n; ++i) {
795            const degree_t r = remaining[i];
796            if (w < r) {
797                k = i;
798                w = r;
[4583]799            }
800        }
801
[4610]802        // Multiplexing requires at least 3 elements; if the best set contains fewer than 3, abort.
[4608]803        if (w < 3) {
804            break;
[4599]805        }
[4586]806
[4725]807        for (const auto ei : make_iterator_range(out_edges(k + m, mMultiplexSetGraph))) {
808            const vertex_t j = target(ei, mMultiplexSetGraph);
[4608]809            if (chosen_set[j] == 0) {
810                chosen_set[j] = (k + m);
[4725]811                for (const auto ej : make_iterator_range(in_edges(j, mMultiplexSetGraph))) {
812                    remaining[source(ej, mMultiplexSetGraph) - m]--;
[4608]813                }
814            }
[4596]815        }
[4586]816
[4610]817        assert (remaining[k] == 0);
818
819        // If this contains 2^n elements for any n, discard the member that is most likely to be added
820        // to some future set.
821        if (is_power_of_2(w)) {
[4608]822            vertex_t j = 0;
823            degree_t w = 0;
824            for (vertex_t i = 0; i != m; ++i) {
825                if (chosen_set[i] == (k + m)) {
826                    degree_t r = 1;
[4725]827                    for (const auto ej : make_iterator_range(in_edges(i, mMultiplexSetGraph))) {
[4610]828                        // strongly prefer adding weight to unvisited sets that have more remaining vertices
[4725]829                        r += std::pow(remaining[source(ej, mMultiplexSetGraph) - m], 2);
[4608]830                    }
831                    if (w < r) {
832                        j = i;
833                        w = r;
834                    }
835                }
[4596]836            }
[4608]837            assert (w > 0);
838            chosen_set[j] = 0;
[4725]839            for (const auto ej : make_iterator_range(in_edges(j, mMultiplexSetGraph))) {
840                remaining[source(ej, mMultiplexSetGraph) - m]++;
[4608]841            }
[4596]842        }
[4608]843    }
[4599]844
[4608]845    for (unsigned i = 0; i != m; ++i) {
846        InEdgeIterator ei, ei_end;
847        std::tie(ei, ei_end) = in_edges(i, mMultiplexSetGraph);
848        for (auto next = ei; ei != ei_end; ei = next) {
849            ++next;
850            if (source(*ei, mMultiplexSetGraph) != chosen_set[i]) {
851                remove_edge(*ei, mMultiplexSetGraph);
[4599]852            }
[4596]853        }
854    }
[4586]855
856    #ifndef NDEBUG
857    for (unsigned i = 0; i != m; ++i) {
858        assert (in_degree(i, mMultiplexSetGraph) <= 1);
859    }
860    for (unsigned i = m; i != (m + n); ++i) {
861        assert (out_degree(i, mMultiplexSetGraph) == 0 || out_degree(i, mMultiplexSetGraph) >= 3);
862    }
863    #endif
[4569]864}
[4287]865
[4571]866/** ------------------------------------------------------------------------------------------------------------- *
867 * @brief applySubsetConstraints
868 ** ------------------------------------------------------------------------------------------------------------- */
869void AutoMultiplexing::applySubsetConstraints() {
[4287]870
[4579]871    // When entering thus function, the multiplex set graph M is a bipartite DAG with edges denoting the set
[4577]872    // relationships of our independent sets.
873    const unsigned m = num_vertices(mConstraintGraph);
[4579]874    const unsigned n = num_vertices(mMultiplexSetGraph);
[4571]875
[4577]876    // Add in any edges from our subset constraints to M that are within the same set.
877    bool hasSubsetConstraint = false;
[4594]878
[4747]879    for (auto ei : make_iterator_range(edges(mSubsetGraph))) {
880        const auto u = source(ei, mSubsetGraph);
881        const auto v = target(ei, mSubsetGraph);
[4577]882        // If both the source and target of ei are adjacent to the same vertex, that vertex must be the
883        // "set vertex". Add the edge between the vertices.
[4747]884        for (auto ej : make_iterator_range(in_edges(u, mMultiplexSetGraph))) {
885            auto w = target(ej, mMultiplexSetGraph);
[4577]886            // Only check (v, w) if w is a "set vertex".
[4582]887            if (w >= (n - m) && edge(v, w, mMultiplexSetGraph).second) {
[4579]888                add_edge(u, v, mMultiplexSetGraph);
[4577]889                hasSubsetConstraint = true;
[4571]890            }
891        }
892    }
893
[4577]894    if (LLVM_UNLIKELY(hasSubsetConstraint)) {
895        // At this point, M is still a DAG but no longer bipartite. We're going to scan through the set vertices
896        // in M, and use a DFS to scan through M and eliminate any subset relationships in the AST.
897        // That way, "multiplexSelectedIndependentSets" only needs to consider muxing and demuxing of the streams.
898
[4579]899        std::vector<MultiplexSetGraph::vertex_descriptor> V;
900        std::stack<MultiplexSetGraph::vertex_descriptor> S;
[4577]901        std::queue<PabloAST *> Q;
902        BitVector D(n - m, 0);
903
904        for (auto i = m; i != n; ++i) {
905            // For each member of a "set vertex" ...
[4736]906            for (auto e : make_iterator_range(out_edges(i, mMultiplexSetGraph))) {
907                const auto s = source(e, mMultiplexSetGraph);
[4579]908                if (out_degree(s, mMultiplexSetGraph) != 0) {
[4577]909                    // First scan through the subgraph of vertices in M dominated by s and build up the set T,
910                    // consisting of all sinks w.r.t. vertex s.
911                    auto u = s;
912                    for (;;) {
[4579]913                        graph_traits<MultiplexSetGraph>::out_edge_iterator ej, ej_end;
914                        for (std::tie(ej, ej_end) = out_edges(u, mMultiplexSetGraph); ej != ej_end; ++ej) {
915                            auto v = target(*ej, mMultiplexSetGraph);
[4577]916                            if (D.test(v)) {
917                                continue;
918                            }
919                            D.set(v);
[4579]920                            if (out_degree(v, mMultiplexSetGraph) == 0) {
[4582]921                                V.push_back(v);
[4577]922                            }
923                            else {
924                                S.push(v);
925                            }
926                        }
927                        if (S.empty()) {
928                            break;
929                        }
930                        u = S.top();
931                        S.pop();
932                    }
933                    D.clear();
934                    // Now in order for these advances to be mutually exclusive, the input to A_s must be masked
935                    // with the complement of each advance indicated by V.
936
[4611]937                    Advance * adv = std::get<0>(mAdvance[s]);
[4577]938                    PabloBlock * pb = adv->getParent();
939
940                    for (auto i : V) {
[4611]941                        Q.push(std::get<0>(mAdvance[i])->getOperand(0));
[4579]942                    }                   
[4638]943                    pb->setInsertPoint(adv);
[4577]944                    while (Q.size() > 1) {
945                        PabloAST * a1 = Q.front(); Q.pop();
[4638]946                        PabloAST * a2 = Q.front(); Q.pop();                       
947                        Q.push(pb->createOr(a1, a2, "subset"));
[4577]948                    }
949                    assert (Q.size() == 1);
950
951                    PabloAST * const mask = pb->createNot(Q.front()); Q.pop();
[4638]952                    adv->setOperand(0, pb->createAnd(adv->getOperand(0), mask, "subset"));
[4577]953
954                    // Similar to the above, we're going to OR together the result of each advance,
955                    // including s. This will restore the advanced variable back to its original state.
956
957                    // Gather the original users to this advance. We'll be manipulating it shortly.
[4646]958                    std::vector<PabloAST *> U(adv->users().begin(), adv->users().end());
[4577]959
960                    // Add s to V and sort the list; it'll be closer to being in topological order.
961                    V.push_back(s);
962                    std::sort(V.begin(), V.end());
963                    for (auto i : V) {
[4611]964                        Q.push(std::get<0>(mAdvance[i]));
[4577]965                    }
[4638]966                    pb->setInsertPoint(adv);
[4577]967                    while (Q.size() > 1) {
968                        PabloAST * a1 = Q.front(); Q.pop();
[4638]969                        PabloAST * a2 = Q.front(); Q.pop();                       
970                        Q.push(pb->createOr(a1, a2, "subset"));
[4577]971                    }
972                    assert (Q.size() == 1);
[4579]973
[4577]974                    PabloAST * const input = Q.front(); Q.pop();
975                    for (PabloAST * use : U) {
976                        if (LLVM_LIKELY(isa<Statement>(use))) {
977                            cast<Statement>(use)->replaceUsesOfWith(adv, input);
978                        }
979                    }
980
981                    pb->setInsertPoint(pb->back());
982
983                    V.clear();
984
985                }
986            }
987        }
988    }
[4287]989}
[4571]990
[4592]991/** ------------------------------------------------------------------------------------------------------------- *
[4571]992 * @brief multiplexSelectedIndependentSets
993 ** ------------------------------------------------------------------------------------------------------------- */
[4775]994void AutoMultiplexing::multiplexSelectedIndependentSets(PabloFunction & function) {
[4571]995
[4736]996    const unsigned first_set = num_vertices(mConstraintGraph);
997    const unsigned last_set = num_vertices(mMultiplexSetGraph);
[4587]998
999    // Preallocate the structures based on the size of the largest multiplex set
1000    size_t max_n = 3;
[4736]1001    for (unsigned idx = first_set; idx != last_set; ++idx) {
1002        max_n = std::max<unsigned>(max_n, out_degree(idx, mMultiplexSetGraph));
[4587]1003    }
1004
1005    circular_buffer<PabloAST *> Q(max_n);
[4775]1006    flat_set<PabloBlock *> modified;
[4587]1007
[4579]1008    // When entering thus function, the multiplex set graph M is a DAG with edges denoting the set
[4578]1009    // relationships of our independent sets.
[4571]1010
[4736]1011    for (unsigned idx = first_set; idx != last_set; ++idx) {
1012        const size_t n = out_degree(idx, mMultiplexSetGraph);
[4578]1013        if (n) {
[4728]1014            const size_t m = log2_plus_one(n);           
[4711]1015            Advance * input[n];
[4736]1016            Advance * muxed[m];           
[4578]1017
[4725]1018            unsigned i = 0;
[4736]1019            for (const auto e : make_iterator_range(out_edges(idx, mMultiplexSetGraph))) {
[4725]1020                input[i] = std::get<0>(mAdvance[target(e, mMultiplexSetGraph)]);
1021                assert (input[i]);
1022                ++i;
[4578]1023            }
[4725]1024            assert (i == n);
[4578]1025
[4775]1026            Advance * const adv = input[0];
1027            assert (adv);
1028            PabloBlock * const block = adv->getParent();
1029            assert (block);           
1030            PabloBuilder builder(*block);
[4638]1031            block->setInsertPoint(block->back());
[4585]1032
[4578]1033            /// Perform n-to-m Multiplexing
[4587]1034            for (size_t j = 0; j != m; ++j) {
[4586]1035
[4592]1036                std::ostringstream prefix;
[4736]1037                prefix << "mux" << n << "to" << m << '.' << (j + 1);
1038                for (size_t i = 0; i != n; ++i) {
1039                    if (((i + 1) & (1ULL << j)) != 0) {
[4775]1040                        assert (input[i]->getParent() == block);
[4736]1041                        Q.push_back(input[i]->getOperand(0));
[4578]1042                    }
1043                }
[4587]1044
1045                while (Q.size() > 1) {
1046                    PabloAST * a1 = Q.front(); Q.pop_front(); assert (a1);
1047                    PabloAST * a2 = Q.front(); Q.pop_front(); assert (a2);
[4638]1048                    assert (!Q.full());                                       
1049                    Q.push_back(builder.createOr(a2, a1, "muxing"));
[4578]1050                }
[4585]1051
[4587]1052                PabloAST * mux = Q.front(); Q.pop_front(); assert (mux);
[4711]1053                // The only way this did not return an Advance statement would be if either the mux or shift amount
[4722]1054                // is zero. Since these cases would have been eliminated earlier, we are safe to cast here.               
[4728]1055                muxed[j] = cast<Advance>(builder.createAdvance(mux, adv->getOperand(1), prefix.str()));
[4578]1056            }
1057
[4736]1058            /// Perform m-to-n Demultiplexing                       
1059            for (size_t i = 0; i != n; ++i) {
[4578]1060
[4702]1061                // Construct the demuxed values and replaces all the users of the original advances with them.
[4587]1062                for (size_t j = 0; j != m; ++j) {
[4736]1063                    if (((i + 1) & (1ULL << j)) == 0) {
[4587]1064                        Q.push_back(muxed[j]);
1065                    }
1066                }
[4585]1067
[4587]1068                if (LLVM_LIKELY(Q.size() > 0)) {
1069                    while (Q.size() > 1) {
1070                        PabloAST * a1 = Q.front(); Q.pop_front(); assert (a1);
1071                        PabloAST * a2 = Q.front(); Q.pop_front(); assert (a2);
1072                        assert (!Q.full());
[4638]1073                        Q.push_back(builder.createOr(a2, a1, "demuxing"));
[4587]1074                    }
1075                    assert (Q.size() == 1);
[4638]1076                    PabloAST * neg = Q.front(); Q.pop_front();
1077                    Q.push_back(builder.createNot(neg, "demuxing")); assert (neg);
[4587]1078                }
1079
[4578]1080                for (unsigned j = 0; j != m; ++j) {
[4736]1081                    if (((i + 1) & (1ULL << j)) != 0) {
[4587]1082                        assert (!Q.full());
1083                        Q.push_back(muxed[j]);
[4578]1084                    }
1085                }
[4585]1086
[4592]1087                while (Q.size() > 1) {
[4587]1088                    PabloAST * a1 = Q.front(); Q.pop_front(); assert (a1);
1089                    PabloAST * a2 = Q.front(); Q.pop_front(); assert (a2);
1090                    assert (!Q.full());
[4638]1091                    Q.push_back(builder.createAnd(a1, a2, "demuxing"));
[4578]1092                }
[4585]1093
[4641]1094                PabloAST * demuxed = Q.front(); Q.pop_front(); assert (demuxed);
[4736]1095                input[i]->replaceWith(demuxed, true, true);
[4638]1096            }
[4775]1097            modified.insert(block);
1098        }
[4578]1099    }
[4775]1100
1101    for (PabloBlock * block : modified) {
1102        topologicalSort(function, *block);
1103    }
[4571]1104}
1105
[4775]1106///** ------------------------------------------------------------------------------------------------------------- *
1107// * @brief printGraph
1108// ** ------------------------------------------------------------------------------------------------------------- */
1109//template <class Graph>
1110//static void printGraph(const PabloBlock & block, const Graph & G, const std::string name) {
1111//    raw_os_ostream out(std::cerr);
1112
1113//    out << "digraph " << name << " {\n";
1114//    for (auto u : make_iterator_range(vertices(G))) {
1115//        if (in_degree(u, G) == 0 && out_degree(u, G) == 0) {
1116//            continue;
1117//        }
1118//        out << "v" << u << " [label=\"" << u << ": ";
1119//        PabloAST * const expr = G[u];
1120//        if (isa<Statement>(expr)) {
1121//            if (LLVM_UNLIKELY(isa<If>(expr))) {
1122//                out << "If ";
1123//                PabloPrinter::print(cast<If>(expr)->getOperand(0), out);
1124//                out << ":";
1125//            } else if (LLVM_UNLIKELY(isa<While>(expr))) {
1126//                out << "While ";
1127//                PabloPrinter::print(cast<While>(expr)->getOperand(0), out);
1128//                out << ":";
1129//            } else {
1130//                PabloPrinter::print(cast<Statement>(expr), "", out);
1131//            }
1132//        } else {
1133//            PabloPrinter::print(expr, out);
1134//        }
1135//        out << "\"";
1136//        if (!isa<Statement>(expr) || cast<Statement>(expr)->getParent() != &block) {
1137//            out << " style=dashed";
1138//        }
1139//        out << "];\n";
1140//    }
1141//    for (auto e : make_iterator_range(edges(G))) {
1142//        const auto s = source(e, G);
1143//        const auto t = target(e, G);
1144//        out << "v" << s << " -> v" << t << ";\n";
1145//    }
1146
1147//    if (num_vertices(G) > 0) {
1148
1149//        out << "{ rank=same;";
1150//        for (auto u : make_iterator_range(vertices(G))) {
1151//            if (in_degree(u, G) == 0 && out_degree(u, G) != 0) {
1152//                out << " v" << u;
1153//            }
1154//        }
1155//        out << "}\n";
1156
1157//        out << "{ rank=same;";
1158//        for (auto u : make_iterator_range(vertices(G))) {
1159//            if (out_degree(u, G) == 0 && in_degree(u, G) != 0) {
1160//                out << " v" << u;
1161//            }
1162//        }
1163//        out << "}\n";
1164
1165//    }
1166
1167//    out << "}\n\n";
1168//    out.flush();
1169//}
1170
1171/** ------------------------------------------------------------------------------------------------------------- *
1172 * @brief topologicalSort
1173 ** ------------------------------------------------------------------------------------------------------------- */
1174void AutoMultiplexing::topologicalSort(PabloFunction &, PabloBlock & block) const {
1175
1176    TopologicalGraph G;
1177    TopologicalMap M;
1178    // Compute the base def-use graph ...
1179    for (Statement * stmt : block) {       
1180        const TopologicalVertex u = getVertex(stmt, G, M);
1181        if (isa<If>(stmt)) {
1182            for (Assign * def : cast<const If>(stmt)->getDefined()) {
1183                resolveUsages(u, def, block, G, M, stmt);
1184            }
1185        } else if (isa<While>(stmt)) {
1186            for (Next * var : cast<const While>(stmt)->getVariants()) {
1187                resolveUsages(u, var, block, G, M, stmt);
1188            }
1189        } else {
1190            resolveUsages(u, stmt, block, G, M, nullptr);
1191        }
1192    }
1193
1194    circular_buffer<TopologicalVertex> Q(num_vertices(G));
1195    topological_sort(G, std::back_inserter(Q));
1196
1197    block.setInsertPoint(nullptr);
1198    while (!Q.empty()) {
1199        Statement * stmt = G[Q.back()];
1200        Q.pop_back();
1201        if (stmt->getParent() == &block) {
1202            block.insert(stmt);
1203        }
1204    }
1205
1206}
1207
1208/** ------------------------------------------------------------------------------------------------------------- *
1209 * @brief resolveUsages
1210 ** ------------------------------------------------------------------------------------------------------------- */
1211void AutoMultiplexing::resolveUsages(const TopologicalVertex u, Statement * expr, PabloBlock & block, TopologicalGraph & G, TopologicalMap & M, Statement * ignoreIfThis) const {
1212    for (PabloAST * user : expr->users()) {
1213        if (LLVM_LIKELY(user != ignoreIfThis && isa<Statement>(user))) {
1214            PabloBlock * parent = cast<Statement>(user)->getParent();
1215            assert (parent);
1216            if (LLVM_LIKELY(parent == &block)) {
1217                add_edge(u, getVertex(cast<Statement>(user), G, M), G);
1218            } else {
1219                for (;;) {
1220                    if (LLVM_UNLIKELY(parent == nullptr)) {
1221                        assert (isa<Assign>(expr) || isa<Next>(expr));
1222                        break;
1223                    } else if (parent->getParent() == &block) {
1224                        const auto f = mResolvedScopes.find(parent);
1225                        if (LLVM_UNLIKELY(f == mResolvedScopes.end())) {
1226                            throw std::runtime_error("Failed to resolve scope block!");
1227                        }
1228                        Statement * const branch = f->second;
1229                        if (LLVM_UNLIKELY(branch != ignoreIfThis)) {
1230                            add_edge(u, getVertex(branch, G, M), G);
1231                        }
1232                        break;
1233                    }
1234                    parent = parent->getParent();
1235                }
1236            }
1237        }
1238    }
1239}
1240
1241/** ------------------------------------------------------------------------------------------------------------- *
1242 * @brief getVertex
1243 ** ------------------------------------------------------------------------------------------------------------- */
1244AutoMultiplexing::TopologicalVertex AutoMultiplexing::getVertex(Statement * expr, TopologicalGraph & G, TopologicalMap & M) {
1245    const auto f = M.find(expr);
1246    if (f != M.end()) {
1247        return f->second;
1248    }
1249    const auto u = add_vertex(expr, G);
1250    M.emplace(expr, u);
1251    return u;
1252}
1253
[4582]1254} // end of namespace pablo
1255
Note: See TracBrowser for help on using the repository browser.