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

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

Work on adding Multiplexing Window Size.

File size: 41.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>
[4868]11#include <pablo/analysis/pabloverifier.hpp>
[4650]12#include <stack>
13#include <queue>
14#include <unordered_set>
[4868]15#include <bdd.h>
[4287]16
17using namespace llvm;
[4569]18using namespace boost;
19using namespace boost::container;
20using namespace boost::numeric::ublas;
[4287]21
[4888]22#define PRINT_DEBUG_OUTPUT
[4596]23
[4638]24#if !defined(NDEBUG) && !defined(PRINT_DEBUG_OUTPUT)
25#define PRINT_DEBUG_OUTPUT
26#endif
27
28#ifdef PRINT_DEBUG_OUTPUT
29
[4601]30#include <iostream>
[4242]31
[4601]32using namespace pablo;
[4596]33typedef uint64_t timestamp_t;
34
35static inline timestamp_t read_cycle_counter() {
36#ifdef __GNUC__
37timestamp_t ts;
38#ifdef __x86_64__
39  unsigned int eax, edx;
40  asm volatile("rdtsc" : "=a" (eax), "=d" (edx));
41  ts = ((timestamp_t) eax) | (((timestamp_t) edx) << 32);
42#else
43  asm volatile("rdtsc\n" : "=A" (ts));
44#endif
45  return(ts);
46#endif
47#ifdef _MSC_VER
48  return __rdtsc();
49#endif
50}
51
[4600]52#define LOG(x) std::cerr << x << std::endl;
[4601]53#define RECORD_TIMESTAMP(Name) const timestamp_t Name = read_cycle_counter()
54#define LOG_GRAPH(Name, G) \
55    LOG(Name << " |V|=" << num_vertices(G) << ", |E|="  << num_edges(G) << \
56                " (" << (((double)num_edges(G)) / ((double)(num_vertices(G) * (num_vertices(G) - 1) / 2))) << ')')
57
[4870]58unsigned __count_advances(const PabloBlock * const entry) {
[4601]59
60    std::stack<const Statement *> scope;
61    unsigned advances = 0;
62
63    // Scan through and collect all the advances, calls, scanthrus and matchstars ...
[4870]64    for (const Statement * stmt = entry->front(); ; ) {
[4601]65        while ( stmt ) {
66            if (isa<Advance>(stmt)) {
67                ++advances;
68            }
69            else if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
70                // Set the next statement to be the first statement of the inner scope and push the
71                // next statement of the current statement into the scope stack.
[4870]72                const PabloBlock * const nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
[4601]73                scope.push(stmt->getNextNode());
[4870]74                stmt = nested->front();
[4601]75                assert (stmt);
76                continue;
77            }
78            stmt = stmt->getNextNode();
79        }
80        if (scope.empty()) {
81            break;
82        }
83        stmt = scope.top();
84        scope.pop();
85    }
86    return advances;
87}
88
89#define LOG_NUMBER_OF_ADVANCES(entry) LOG("|Advances|=" << __count_advances(entry))
90
[4600]91#else
92#define LOG(x)
[4601]93#define RECORD_TIMESTAMP(Name)
94#define LOG_GRAPH(Name, G)
95#define LOG_NUMBER_OF_ADVANCES(entry)
[4600]96#endif
[4596]97
[4600]98
[4601]99namespace pablo {
100
[4772]101using TypeId = PabloAST::ClassTypeId;
102
[4888]103bool MultiplexingPass::optimize(PabloFunction & function, const unsigned limit, const unsigned maxSelections, const unsigned windowSize, const bool independent) {
[4600]104
[4797]105//    std::random_device rd;
106//    const auto seed = rd();
[4695]107    const auto seed = 83234827342;
[4600]108    RNG rng(seed);
109
110    LOG("Seed:                    " << seed);
111
[4888]112    MultiplexingPass mp(limit, maxSelections, windowSize);
[4601]113    RECORD_TIMESTAMP(start_initialize);
[4888]114    const unsigned advances = mp.initialize(function, independent);
[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
[4868]121    if (advances == 0) {
[4665]122        return false;
123    }
124
[4601]125    RECORD_TIMESTAMP(start_characterize);
[4888]126    mp.characterize(function.getEntryBlock());
[4601]127    RECORD_TIMESTAMP(end_characterize);
[4600]128
129    LOG("Characterize:            " << (end_characterize - start_characterize));
130
[4868]131    LOG("Nodes in BDD:            " << bdd_getnodenum() << " of " << bdd_getallocnum());
132
133    RECORD_TIMESTAMP(start_shutdown);
134    bdd_done();
135    RECORD_TIMESTAMP(end_shutdown);
136    LOG("Shutdown:                " << (end_shutdown - start_shutdown));
137
[4601]138    RECORD_TIMESTAMP(start_create_multiplex_graph);
[4888]139    const bool multiplex = mp.generateCandidateSets(rng);
[4601]140    RECORD_TIMESTAMP(end_create_multiplex_graph);
[4722]141    LOG("GenerateCandidateSets:   " << (end_create_multiplex_graph - start_create_multiplex_graph));
[4596]142
143    if (multiplex) {
[4600]144
[4610]145        RECORD_TIMESTAMP(start_select_multiplex_sets);
[4888]146        mp.selectMultiplexSets(rng);
[4610]147        RECORD_TIMESTAMP(end_select_multiplex_sets);
148        LOG("SelectMultiplexSets:     " << (end_select_multiplex_sets - start_select_multiplex_sets));
[4600]149
[4601]150        RECORD_TIMESTAMP(start_subset_constraints);
[4888]151        mp.eliminateSubsetConstraints();
[4601]152        RECORD_TIMESTAMP(end_subset_constraints);
[4600]153        LOG("ApplySubsetConstraints:  " << (end_subset_constraints - start_subset_constraints));
154
[4601]155        RECORD_TIMESTAMP(start_select_independent_sets);
[4888]156        mp.multiplexSelectedIndependentSets(function);
[4601]157        RECORD_TIMESTAMP(end_select_independent_sets);
[4722]158        LOG("SelectedIndependentSets: " << (end_select_independent_sets - start_select_independent_sets));
[4775]159
[4888]160        MultiplexingPass::topologicalSort(function);
[4871]161        #ifndef NDEBUG
162        PabloVerifier::verify(function, "post-multiplexing");
163        #endif
[4578]164    }
[4596]165
[4659]166    LOG_NUMBER_OF_ADVANCES(function.getEntryBlock());
[4601]167    return multiplex;
[4242]168}
169
[4569]170/** ------------------------------------------------------------------------------------------------------------- *
171 * @brief initialize
[4665]172 * @param function the function to optimize
173 * @returns true if there are fewer than three advances in this function
[4569]174 *
175 * Scan through the program to identify any advances and calls then initialize the BDD engine with
176 * the proper variable ordering.
177 ** ------------------------------------------------------------------------------------------------------------- */
[4888]178unsigned MultiplexingPass::initialize(PabloFunction & function, const bool independent) {
[4242]179
[4611]180    std::stack<Statement *> scope;
[4680]181    unsigned variableCount = 0; // number of statements that cannot always be categorized without generating a new variable
[4521]182
[4569]183    // Scan through and collect all the advances, calls, scanthrus and matchstars ...
[4868]184    unsigned statements = 0, advances = 0;
[4870]185    for (Statement * stmt = function.getEntryBlock()->front(); ; ) {
[4570]186        while ( stmt ) {
[4868]187            ++statements;
[4569]188            if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
[4536]189                scope.push(stmt->getNextNode());
[4888]190                const PabloBlock * const nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();               
[4870]191                stmt = nested->front();
[4569]192                assert (stmt);
193                continue;
[4536]194            }
[4569]195            switch (stmt->getClassTypeId()) {
[4772]196                case TypeId::Advance:
[4868]197                    ++advances;
198                case TypeId::ScanThru:
[4772]199                case TypeId::Call:
200                case TypeId::MatchStar:
[4868]201                    ++variableCount;
[4569]202                    break;
203                default:
204                    break;
[4521]205            }
[4570]206            stmt = stmt->getNextNode();
[4569]207        }
208        if (scope.empty()) {
209            break;
210        }
211        stmt = scope.top();
212        scope.pop();
213    }
[4521]214
[4665]215    // If there are fewer than three Advances in this program, just abort. We cannot reduce it.
[4868]216    if (advances < 3) {
217        return 0;
[4665]218    }
219
[4888]220    initializeBaseConstraintGraph(function.getEntryBlock(), statements, advances);
[4570]221
[4888]222    mSubsetGraph = SubsetGraph(advances);
223
224    initializeAdvanceDepth(function.getEntryBlock(), advances);
225
226    // Initialize the BDD engine ...
227    bdd_init(10000000, 100000);
228    bdd_setvarnum(variableCount + function.getNumOfParameters());
229    bdd_setcacheratio(64);
230    bdd_setmaxincrease(10000000);
231    bdd_autoreorder(BDD_REORDER_SIFT);
232
233    // Map the constants and input variables
234    mCharacterization[PabloBlock::createZeroes()] = bdd_zero();
235    mCharacterization[PabloBlock::createOnes()] = bdd_one();
236    mVariables = function.getNumOfParameters();
237
238    // TODO: record information in the function to indicate which pairs of input variables are independent
239    if (independent) {
240        for (unsigned i = 0; i != mVariables; ++i) {
241            BDD Vi = bdd_ithvar(i);
242            BDD Ni = bdd_zero();
243            for (unsigned j = 0; j != i; ++j) {
244                Ni = bdd_addref(bdd_or(Ni, bdd_ithvar(j)));
245            }
246            for (unsigned j = i + 1; j != mVariables; ++j) {
247                Ni = bdd_addref(bdd_or(Ni, bdd_ithvar(j)));
248            }
249            Ni = bdd_addref(bdd_not(Ni));
250            mCharacterization[function.getParameter(i)] = bdd_addref(bdd_imp(Vi, Ni));
251        }
252    } else {
253        for (unsigned i = 0; i != mVariables; ++i) {
254            mCharacterization[function.getParameter(i)] = bdd_ithvar(i);
255        }
256    }
257
258    return advances;
259}
260
261/** ------------------------------------------------------------------------------------------------------------- *
262 * @brief initializeBaseConstraintGraph
263 ** ------------------------------------------------------------------------------------------------------------- */
264inline void MultiplexingPass::initializeBaseConstraintGraph(PabloBlock * const block, const unsigned statements, const unsigned advances) {
265
266    std::stack<Statement *> scope;
267    flat_map<const PabloAST *, unsigned> M;
268    M.reserve(statements);
[4871]269    matrix<bool> G(statements, advances, false);
[4868]270    for (unsigned i = 0; i != advances; ++i) {
[4569]271        G(i, i) = true;
272    }
[4521]273
[4868]274    unsigned n = advances;
[4888]275    unsigned k = 0;
276    for (const Statement * stmt = block->front();;) {
[4570]277        while ( stmt ) {
[4868]278            unsigned u = 0;
[4888]279            if (LLVM_UNLIKELY(isa<Advance>(stmt))) {
280                u = k++;
[4868]281            } else {
[4583]282                u = n++;
[4570]283            }
[4888]284            M.emplace(stmt, u);
[4569]285            for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
[4582]286                const PabloAST * const op = stmt->getOperand(i);
[4583]287                if (LLVM_LIKELY(isa<Statement>(op))) {
[4888]288                    const unsigned v = M[op];
289                    for (unsigned w = 0; w != k; ++w) {
[4583]290                        G(u, w) |= G(v, w);
291                    }
[4570]292                }
[4536]293            }
[4569]294            if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
[4888]295                scope.push(stmt->getNextNode());
[4870]296                const PabloBlock * const nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
297                stmt = nested->front();
[4569]298                assert (stmt);
299                continue;
300            }
[4570]301            stmt = stmt->getNextNode();
[4521]302        }
[4536]303        if (scope.empty()) {
304            break;
305        }
306        stmt = scope.top();
307        scope.pop();
308    }
[4521]309
[4888]310    assert (k == advances);
[4871]311
[4888]312    // Compute the base constraint graph as the union of TRANSPOSE(G) without any reflective loops and the set of edges
313    // marking which advances are in differing scope blocks.
[4871]314
[4868]315    mConstraintGraph = ConstraintGraph(advances);
316    for (unsigned i = 0; i != advances; ++i) {
[4888]317        for (unsigned j = 0; j < i; ++j) {
[4569]318            if (G(i, j)) {
[4601]319                add_edge(j, i, mConstraintGraph);
[4569]320            }
[4871]321        }
[4888]322        for (unsigned j = i + 1; j < advances; ++j) {
323            if (G(i, j)) {
324                add_edge(j, i, mConstraintGraph);
325            }
326        }
[4569]327    }
[4521]328
[4888]329}
[4583]330
[4888]331/** ------------------------------------------------------------------------------------------------------------- *
332 * @brief initializeAdvanceDepth
333 ** ------------------------------------------------------------------------------------------------------------- */
334inline void MultiplexingPass::initializeAdvanceDepth(PabloBlock * const block, const unsigned advances) {
[4583]335
[4888]336    std::stack<Statement *> scope;
337    unsigned k = 0;
338    int maxDepth = 0;
339    const Advance * advance[advances];
340    mAdvanceDepth.resize(advances, 0);
341    for (Statement * stmt = block->front(); ; ) {
342        while ( stmt ) {
343            if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
344                scope.push(stmt->getNextNode());
345                const PabloBlock * const nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
346                stmt = nested->front();
347                assert (stmt);
348                continue;
349            } else if (LLVM_UNLIKELY(isa<Advance>(stmt))) {
350                int depth = 0;
351                advance[k] = cast<Advance>(stmt);
352                for (unsigned i = 0; i != k; ++i) {
353                    if (edge(i, k, mConstraintGraph).second || (advance[i]->getParent() != advance[k]->getParent())) {
354                        depth = std::max<int>(depth, mAdvanceDepth[i]);
355                    }
356                }
357                mAdvanceDepth[k++] = ++depth;
358                maxDepth = std::max(maxDepth, depth);
[4871]359            }
[4888]360            stmt = stmt->getNextNode();
[4871]361        }
[4888]362        if (scope.empty()) {
363            break;
[4871]364        }
[4888]365        stmt = scope.top();
366        scope.pop();
[4569]367    }
[4888]368    assert (k == advances);
[4665]369
[4888]370    LOG("Window Size / Max Depth: " << mWindowSize << " of " << maxDepth);
[4569]371}
[4521]372
[4569]373/** ------------------------------------------------------------------------------------------------------------- *
374 * @brief characterize
375 * @param vars the input vars for this program
376 *
377 * Scan through the program and iteratively compute the BDDs for each statement.
378 ** ------------------------------------------------------------------------------------------------------------- */
[4888]379void MultiplexingPass::characterize(PabloBlock * const block) {
[4870]380    for (Statement * stmt : *block) {
381        if (LLVM_UNLIKELY(isa<If>(stmt))) {
382            characterize(cast<If>(stmt)->getBody());
383        } else if (LLVM_UNLIKELY(isa<While>(stmt))) {
384            const auto & variants = cast<While>(stmt)->getVariants();
385            std::vector<BDD> assignments(variants.size());
386            for (unsigned i = 0; i != variants.size(); ++i) {
387                assignments[i] = get(variants[i]->getInitial());
388            }
389            characterize(cast<While>(stmt)->getBody());
390            for (unsigned i = 0; i != variants.size(); ++i) {
391                BDD & var = get(variants[i]->getInitial());
392                var = bdd_addref(bdd_or(var, assignments[i]));
393            }
[4868]394        } else {
[4871]395            mCharacterization.insert(std::make_pair(stmt, characterize(stmt)));
[4611]396        }
397    }
398}
[4521]399
[4611]400/** ------------------------------------------------------------------------------------------------------------- *
[4880]401 * @brief throwUnexpectedStatementTypeError
402 ** ------------------------------------------------------------------------------------------------------------- */
403static void throwUnexpectedStatementTypeError(const Statement * const stmt) {
404    std::string tmp;
405    raw_string_ostream err(tmp);
406    err << "Unexpected statement type ";
407    PabloPrinter::print(stmt, err);
408    throw std::runtime_error(err.str());
409}
410
411/** ------------------------------------------------------------------------------------------------------------- *
[4611]412 * @brief characterize
413 ** ------------------------------------------------------------------------------------------------------------- */
[4888]414inline BDD MultiplexingPass::characterize(Statement * const stmt) {
[4880]415    BDD bdd = get(stmt->getOperand(0));
[4611]416    switch (stmt->getClassTypeId()) {
[4772]417        case TypeId::Assign:
418        case TypeId::Next:
[4646]419            break;
[4772]420        case TypeId::And:
[4880]421            for (unsigned i = 1; i != stmt->getNumOperands(); ++i) {
422                bdd = bdd_and(bdd, get(stmt->getOperand(i)));
423            }
[4868]424            break;
[4772]425        case TypeId::Or:
[4880]426            for (unsigned i = 1; i != stmt->getNumOperands(); ++i) {
427                bdd = bdd_or(bdd, get(stmt->getOperand(i)));
428            }
[4611]429            break;
[4772]430        case TypeId::Xor:
[4880]431            for (unsigned i = 1; i != stmt->getNumOperands(); ++i) {
432                bdd = bdd_xor(bdd, get(stmt->getOperand(i)));
433            }
[4646]434            break;
[4772]435        case TypeId::Not:
[4880]436            bdd = bdd_not(bdd);
[4646]437            break;
[4772]438        case TypeId::Sel:
[4880]439            bdd = bdd_ite(bdd, get(stmt->getOperand(1)), get(stmt->getOperand(2)));
[4611]440            break;
[4772]441        case TypeId::ScanThru:
[4888]442            // ScanThru(c, m) := (c + m) ∧ ¬m. Thus we can conservatively represent this statement using the BDD
443            // for ¬m --- provided no derivative of this statement is negated in any fashion.
[4772]444        case TypeId::MatchStar:
445        case TypeId::Call:
[4868]446            return bdd_ithvar(mVariables++);
[4772]447        case TypeId::Advance:
[4880]448            return characterize(cast<Advance>(stmt), bdd);
[4611]449        default:
[4880]450            throwUnexpectedStatementTypeError(stmt);
[4611]451    }
[4868]452    return bdd_addref(bdd);
[4611]453}
454
455/** ------------------------------------------------------------------------------------------------------------- *
456 * @brief characterize
457 ** ------------------------------------------------------------------------------------------------------------- */
[4888]458inline BDD MultiplexingPass::characterize(Advance * const adv, const BDD Ik) {
[4868]459    const auto k = mAdvanceAttributes.size();
460    std::vector<bool> unconstrained(k , false);
461    for (unsigned i = 0; i != k; ++i) {
[4888]462        // Are we interested in testing these streams to see whether they are mutually exclusive?
463        if (exceedsWindowSize(i, k)) continue;
464        // Have we already proven that they are unconstrained by their subset relationship?
[4868]465        if (unconstrained[i]) continue;
[4888]466        // If these Advances are mutually exclusive, in the same scope, transitively independent, and shift their
467        // values by the same amount, we can safely multiplex them. Otherwise mark the constraint in the graph.
[4868]468        const Advance * const ithAdv = std::get<0>(mAdvanceAttributes[i]);
[4888]469        if ((mTestConstrainedAdvances || independent(i, k)) && (ithAdv->getOperand(1) == adv->getOperand(1))) {
[4870]470            const BDD Ii = get(ithAdv->getOperand(0));
471            const BDD IiIk = bdd_addref(bdd_and(Ii, Ik));
[4868]472            // Is there any satisfying truth assignment? If not, these streams are mutually exclusive.
473            if (bdd_satone(IiIk) == bdd_zero()) {
474                // If Ai ∩ Ak = ∅ and Aj ⊂ Ai, Aj ∩ Ak = ∅.
475                for (auto e : make_iterator_range(in_edges(i, mSubsetGraph))) {
[4870]476                    unconstrained[source(e, mSubsetGraph)] = true;
[4569]477                }
[4868]478                unconstrained[i] = true;
[4870]479            } else if (Ii == IiIk) {
480                // If Ii = Ii ∩ Ik then Ii ⊂ Ik. Record this in the subset graph with the arc (i, k).
481                // Note: the AST will be modified to make these mutually exclusive if Ai and Ak end up in
482                // the same multiplexing set.
483                add_edge(i, k, mSubsetGraph);
484                // If Ai ⊂ Ak and Aj ⊂ Ai, Aj ⊂ Ak.
485                for (auto e : make_iterator_range(in_edges(i, mSubsetGraph))) {
486                    const auto j = source(e, mSubsetGraph);
487                    add_edge(j, k, mSubsetGraph);
488                    unconstrained[j] = true;
489                }
490                unconstrained[i] = true;
[4868]491            } else if (Ik == IiIk) {
492                // If Ik = Ii ∩ Ik then Ik ⊂ Ii. Record this in the subset graph with the arc (k, i).
493                add_edge(k, i, mSubsetGraph);
494                // If Ak ⊂ Ai and Ai ⊂ Aj, Ak ⊂ Aj.
495                for (auto e : make_iterator_range(out_edges(i, mSubsetGraph))) {
496                    const auto j = target(e, mSubsetGraph);
497                    add_edge(k, j, mSubsetGraph);
498                    unconstrained[j] = true;
[4569]499                }
[4868]500                unconstrained[i] = true;
[4569]501            }
[4868]502            bdd_delref(IiIk);
[4611]503        }
[4868]504    }
[4242]505
[4888]506    BDD Ck = bdd_ithvar(mVariables++);
507    const BDD Nk = bdd_addref(bdd_not(Ck));
[4868]508    for (unsigned i = 0; i != k; ++i) {
509        if (unconstrained[i]) {
[4888]510            const Advance * const ithAdv = std::get<0>(mAdvanceAttributes[i]);
511            const BDD Ni = std::get<1>(mAdvanceAttributes[i]);
512
513            BDD & Ci = get(ithAdv);
514            Ci = bdd_addref(bdd_and(Ci, Nk));
515            Ck = bdd_addref(bdd_and(Ck, Ni));
516            if ((!mTestConstrainedAdvances || independent(i, k)) && (adv->getParent() == ithAdv->getParent())) {
[4868]517                continue;
[4611]518            }
519        }
[4868]520        add_edge(i, k, mConstraintGraph);
[4611]521    }
[4888]522    mAdvanceAttributes.emplace_back(adv, Nk);
[4611]523    return Ck;
524}
[4601]525
[4611]526/** ------------------------------------------------------------------------------------------------------------- *
[4868]527 * @brief independent
[4594]528 ** ------------------------------------------------------------------------------------------------------------- */
[4888]529inline bool MultiplexingPass::independent(const ConstraintVertex i, const ConstraintVertex j) const {
[4611]530    assert (i < num_vertices(mConstraintGraph) && j < num_vertices(mConstraintGraph));
[4601]531    return (mConstraintGraph.get_edge(i, j) == 0);
[4594]532}
533
534/** ------------------------------------------------------------------------------------------------------------- *
[4888]535 * @brief exceedsWindowSize
536 ** ------------------------------------------------------------------------------------------------------------- */
537inline bool MultiplexingPass::exceedsWindowSize(const ConstraintVertex i, const ConstraintVertex j) const {
538    assert (i < mAdvanceDepth.size() && j < mAdvanceDepth.size());
539    return (std::abs<int>(mAdvanceDepth[i] - mAdvanceDepth[j]) > mWindowSize);
540}
541
542/** ------------------------------------------------------------------------------------------------------------- *
[4570]543 * @brief generateMultiplexSets
544 * @param RNG random number generator
[4569]545 ** ------------------------------------------------------------------------------------------------------------- */
[4888]546bool MultiplexingPass::generateCandidateSets(RNG & rng) {
[4287]547
[4610]548    using degree_t = graph_traits<ConstraintGraph>::degree_size_type;
[4287]549
[4601]550    // What if we generated a "constraint free" graph instead? By taking each connected component of it
551    // and computing the complement of it (with the same lesser to greater index ordering), we should
552    // have the same problem here but decomposed into subgraphs.
553
[4650]554    VertexVector S;
[4648]555    std::vector<degree_t> D(num_vertices(mConstraintGraph));
[4650]556    S.reserve(15);
[4570]557
[4650]558    mMultiplexSetGraph = MultiplexSetGraph(num_vertices(mConstraintGraph));
[4610]559
[4650]560    // Push all source nodes into the new independent set N
561    for (auto v : make_iterator_range(vertices(mConstraintGraph))) {
562        const auto d = in_degree(v, mConstraintGraph);
563        D[v] = d;
564        if (d == 0) {
565            S.push_back(v);
[4569]566        }
[4650]567    }
[4287]568
[4736]569    assert (S.size() > 0);
570
[4650]571    auto remainingVerticies = num_vertices(mConstraintGraph) - S.size();
[4648]572
[4650]573    do {
[4648]574
[4822]575        addCandidateSet(S, rng);
[4583]576
[4650]577        bool noNewElements = true;
578        do {
[4736]579            assert (S.size() > 0);
[4650]580            // Randomly choose a vertex in S and discard it.
581            const auto i = S.begin() + IntDistribution(0, S.size() - 1)(rng);
[4736]582            assert (i != S.end());
[4871]583            const ConstraintVertex u = *i;
584            S.erase(i);
[4598]585
[4650]586            for (auto e : make_iterator_range(out_edges(u, mConstraintGraph))) {
587                const ConstraintVertex v = target(e, mConstraintGraph);
588                if ((--D[v]) == 0) {
589                    S.push_back(v);
[4736]590                    --remainingVerticies;
[4650]591                    noNewElements = false;
[4598]592                }
[4569]593            }
594        }
[4650]595        while (noNewElements && remainingVerticies);
[4648]596    }
[4650]597    while (remainingVerticies);
[4608]598
[4650]599    return num_vertices(mMultiplexSetGraph) > num_vertices(mConstraintGraph);
[4569]600}
[4287]601
[4570]602/** ------------------------------------------------------------------------------------------------------------- *
[4822]603 * @brief choose
604 ** ------------------------------------------------------------------------------------------------------------- */
605inline unsigned long choose(const unsigned n, const unsigned k) {
606    if (n < k)
607        return 0;
608    if (n == k || k == 0)
609        return 1;
610    unsigned long delta = k;
611    unsigned long max = n - k;
612    if (delta < max) {
613        std::swap(delta, max);
614    }
615    unsigned long result = delta + 1;
616    for (unsigned i = 2; i <= max; ++i) {
617        result = (result * (delta + i)) / i;
618    }
619    return result;
620}
621
622/** ------------------------------------------------------------------------------------------------------------- *
623 * @brief select
624 *
625 * James McCaffrey's algorithm for "Generating the mth Lexicographical Element of a Mathematical Combination"
626 ** ------------------------------------------------------------------------------------------------------------- */
627void select(const unsigned n, const unsigned k, const unsigned m, unsigned * element) {
628    unsigned long a = n;
629    unsigned long b = k;
630    unsigned long x = (choose(n, k) - 1) - m;
631    for (unsigned i = 0; i != k; ++i) {
632        while (choose(--a, b) > x);
633        x = x - choose(a, b);
634        b = b - 1;
635        element[i] = (n - 1) - a;
636    }
637}
638
639/** ------------------------------------------------------------------------------------------------------------- *
[4648]640 * @brief addCandidateSet
[4650]641 * @param S an independent set
[4570]642 ** ------------------------------------------------------------------------------------------------------------- */
[4888]643inline void MultiplexingPass::addCandidateSet(const VertexVector & S, RNG & rng) {
[4650]644    if (S.size() >= 3) {
[4888]645        if (S.size() <= mMultiplexingSetSizeLimit) {
[4822]646            const auto u = add_vertex(mMultiplexSetGraph);
647            for (const auto v : S) {
648                add_edge(u, v, mMultiplexSetGraph);
649            }
650        } else {
[4888]651            const auto max = choose(S.size(), mMultiplexingSetSizeLimit);
652            unsigned element[mMultiplexingSetSizeLimit];
653            if (LLVM_UNLIKELY(max <= mMaxMultiplexingSetSelections)) {
[4822]654                for (unsigned i = 0; i != max; ++i) {
[4888]655                    select(S.size(), mMultiplexingSetSizeLimit, i, element);
[4822]656                    const auto u = add_vertex(mMultiplexSetGraph);
[4888]657                    for (unsigned j = 0; j != mMultiplexingSetSizeLimit; ++j) {
[4822]658                        add_edge(u, S[element[j]], mMultiplexSetGraph);
659                    }
660                }
661            } else { // take m random samples
[4888]662                for (unsigned i = 0; i != mMaxMultiplexingSetSelections; ++i) {
663                    select(S.size(), mMultiplexingSetSizeLimit, rng() % max, element);
[4822]664                    const auto u = add_vertex(mMultiplexSetGraph);
[4888]665                    for (unsigned j = 0; j != mMultiplexingSetSizeLimit; ++j) {
[4822]666                        add_edge(u, S[element[j]], mMultiplexSetGraph);
667                    }
668                }
669            }
[4608]670        }
[4648]671    }
[4598]672}
[4586]673
[4598]674/** ------------------------------------------------------------------------------------------------------------- *
[4608]675 * @brief is_power_of_2
676 * @param n an integer
[4598]677 ** ------------------------------------------------------------------------------------------------------------- */
[4608]678static inline bool is_power_of_2(const size_t n) {
679    return ((n & (n - 1)) == 0) ;
[4570]680}
[4287]681
[4600]682/** ------------------------------------------------------------------------------------------------------------- *
[4608]683 * @brief log2_plus_one
[4600]684 ** ------------------------------------------------------------------------------------------------------------- */
[4608]685static inline size_t log2_plus_one(const size_t n) {
686    return std::log2<size_t>(n) + 1; // use a faster builtin function for this?
[4599]687}
688
[4571]689/** ------------------------------------------------------------------------------------------------------------- *
[4610]690 * @brief selectMultiplexSets
[4586]691 * @param RNG random number generator
[4610]692 *
693 * This algorithm is simply computes a greedy set cover. We want an exact max-weight set cover but can generate new
694 * sets by taking a subset of any existing set. With a few modifications, the greedy approach seems to work well
[4650]695 * enough but can be trivially shown to produce a suboptimal solution if there are three (or more) sets in which
696 * two, labelled A and B, are disjoint and the third larger set, C, that consists of elements of A and B.
[4571]697 ** ------------------------------------------------------------------------------------------------------------- */
[4888]698void MultiplexingPass::selectMultiplexSets(RNG &) {
[4570]699
[4608]700    using InEdgeIterator = graph_traits<MultiplexSetGraph>::in_edge_iterator;
701    using degree_t = MultiplexSetGraph::degree_size_type;
702    using vertex_t = MultiplexSetGraph::vertex_descriptor;
[4287]703
[4608]704    const size_t m = num_vertices(mConstraintGraph);
705    const size_t n = num_vertices(mMultiplexSetGraph) - m;
[4571]706
[4608]707    std::vector<degree_t> remaining(n, 0);
708    std::vector<vertex_t> chosen_set(m, 0);
[4571]709
[4608]710    for (unsigned i = 0; i != n; ++i) {
711        remaining[i] = out_degree(i + m, mMultiplexSetGraph);
[4585]712    }
[4582]713
[4608]714    for (;;) {
[4583]715
[4610]716        // Choose the set with the greatest number of vertices not already included in some other set.
[4608]717        vertex_t k = 0;
718        degree_t w = 0;
719        for (vertex_t i = 0; i != n; ++i) {
720            const degree_t r = remaining[i];
721            if (w < r) {
722                k = i;
723                w = r;
[4583]724            }
725        }
726
[4610]727        // Multiplexing requires at least 3 elements; if the best set contains fewer than 3, abort.
[4608]728        if (w < 3) {
729            break;
[4599]730        }
[4586]731
[4725]732        for (const auto ei : make_iterator_range(out_edges(k + m, mMultiplexSetGraph))) {
733            const vertex_t j = target(ei, mMultiplexSetGraph);
[4608]734            if (chosen_set[j] == 0) {
735                chosen_set[j] = (k + m);
[4725]736                for (const auto ej : make_iterator_range(in_edges(j, mMultiplexSetGraph))) {
737                    remaining[source(ej, mMultiplexSetGraph) - m]--;
[4608]738                }
739            }
[4596]740        }
[4586]741
[4610]742        assert (remaining[k] == 0);
743
744        // If this contains 2^n elements for any n, discard the member that is most likely to be added
745        // to some future set.
746        if (is_power_of_2(w)) {
[4608]747            vertex_t j = 0;
748            degree_t w = 0;
749            for (vertex_t i = 0; i != m; ++i) {
750                if (chosen_set[i] == (k + m)) {
751                    degree_t r = 1;
[4725]752                    for (const auto ej : make_iterator_range(in_edges(i, mMultiplexSetGraph))) {
[4610]753                        // strongly prefer adding weight to unvisited sets that have more remaining vertices
[4725]754                        r += std::pow(remaining[source(ej, mMultiplexSetGraph) - m], 2);
[4608]755                    }
756                    if (w < r) {
757                        j = i;
758                        w = r;
759                    }
760                }
[4596]761            }
[4608]762            assert (w > 0);
763            chosen_set[j] = 0;
[4725]764            for (const auto ej : make_iterator_range(in_edges(j, mMultiplexSetGraph))) {
765                remaining[source(ej, mMultiplexSetGraph) - m]++;
[4608]766            }
[4596]767        }
[4608]768    }
[4599]769
[4608]770    for (unsigned i = 0; i != m; ++i) {
771        InEdgeIterator ei, ei_end;
772        std::tie(ei, ei_end) = in_edges(i, mMultiplexSetGraph);
773        for (auto next = ei; ei != ei_end; ei = next) {
774            ++next;
775            if (source(*ei, mMultiplexSetGraph) != chosen_set[i]) {
776                remove_edge(*ei, mMultiplexSetGraph);
[4599]777            }
[4596]778        }
779    }
[4586]780
781    #ifndef NDEBUG
782    for (unsigned i = 0; i != m; ++i) {
783        assert (in_degree(i, mMultiplexSetGraph) <= 1);
784    }
785    for (unsigned i = m; i != (m + n); ++i) {
786        assert (out_degree(i, mMultiplexSetGraph) == 0 || out_degree(i, mMultiplexSetGraph) >= 3);
787    }
788    #endif
[4569]789}
[4287]790
[4571]791/** ------------------------------------------------------------------------------------------------------------- *
[4888]792 * @brief eliminateSubsetConstraints
[4571]793 ** ------------------------------------------------------------------------------------------------------------- */
[4888]794void MultiplexingPass::eliminateSubsetConstraints() {
[4287]795
[4868]796    using SubsetEdgeIterator = graph_traits<SubsetGraph>::edge_iterator;
[4571]797
[4868]798    // If Ai ⊂ Aj then the subset graph will contain the arc (i, j). Remove all arcs corresponding to vertices
799    // that are not elements of the same multiplexing set.
800    SubsetEdgeIterator ei, ei_end, ei_next;
801    std::tie(ei, ei_end) = edges(mSubsetGraph);
802    for (ei_next = ei; ei != ei_end; ei = ei_next) {
803        ++ei_next;
804        const auto u = source(*ei, mSubsetGraph);
805        const auto v = target(*ei, mSubsetGraph);
806        if (in_degree(u, mMultiplexSetGraph) != 0 && in_degree(v, mMultiplexSetGraph) != 0) {
[4870]807            assert (in_degree(u, mMultiplexSetGraph) == 1);
[4868]808            const auto su = source(*(in_edges(u, mMultiplexSetGraph).first), mMultiplexSetGraph);
[4870]809            assert (in_degree(v, mMultiplexSetGraph) == 1);
[4868]810            const auto sv = source(*(in_edges(v, mMultiplexSetGraph).first), mMultiplexSetGraph);
811            if (su == sv) {
812                continue;
[4571]813            }
814        }
[4868]815        remove_edge(*ei, mSubsetGraph);
[4571]816    }
817
[4868]818    if (num_edges(mSubsetGraph) != 0) {
[4577]819
[4868]820        // At least one subset constraint exists; perform a transitive reduction on the graph to ensure that
821        // we perform the minimum number of AST modifications for the given multiplexing sets.
[4577]822
[4870]823        doTransitiveReductionOfSubsetGraph();
[4577]824
[4868]825        // Afterwards modify the AST to ensure that multiplexing algorithm can ignore any subset constraints
826        for (auto e : make_iterator_range(edges(mSubsetGraph))) {
827            Advance * adv1 = std::get<0>(mAdvanceAttributes[source(e, mSubsetGraph)]);
828            Advance * adv2 = std::get<0>(mAdvanceAttributes[target(e, mSubsetGraph)]);
829            assert (adv1->getParent() == adv2->getParent());
830            PabloBlock * const pb = adv1->getParent();
831            pb->setInsertPoint(adv2->getPrevNode());
832            adv2->setOperand(0, pb->createAnd(adv2->getOperand(0), pb->createNot(adv1->getOperand(0)), "subset"));
833            pb->setInsertPoint(adv2);
834            adv2->replaceAllUsesWith(pb->createOr(adv1, adv2, "merge"));
835        }
[4577]836
837    }
[4287]838}
[4571]839
[4592]840/** ------------------------------------------------------------------------------------------------------------- *
[4571]841 * @brief multiplexSelectedIndependentSets
842 ** ------------------------------------------------------------------------------------------------------------- */
[4888]843void MultiplexingPass::multiplexSelectedIndependentSets(PabloFunction &) {
[4571]844
[4736]845    const unsigned first_set = num_vertices(mConstraintGraph);
846    const unsigned last_set = num_vertices(mMultiplexSetGraph);
[4587]847
848    // Preallocate the structures based on the size of the largest multiplex set
849    size_t max_n = 3;
[4736]850    for (unsigned idx = first_set; idx != last_set; ++idx) {
851        max_n = std::max<unsigned>(max_n, out_degree(idx, mMultiplexSetGraph));
[4587]852    }
853
854    circular_buffer<PabloAST *> Q(max_n);
855
[4579]856    // When entering thus function, the multiplex set graph M is a DAG with edges denoting the set
[4578]857    // relationships of our independent sets.
[4571]858
[4736]859    for (unsigned idx = first_set; idx != last_set; ++idx) {
860        const size_t n = out_degree(idx, mMultiplexSetGraph);
[4578]861        if (n) {
[4871]862            const size_t m = log2_plus_one(n);
[4711]863            Advance * input[n];
[4871]864            Advance * muxed[m];
[4578]865
[4725]866            unsigned i = 0;
[4736]867            for (const auto e : make_iterator_range(out_edges(idx, mMultiplexSetGraph))) {
[4868]868                input[i++] = std::get<0>(mAdvanceAttributes[target(e, mMultiplexSetGraph)]);
[4578]869            }
870
[4775]871            Advance * const adv = input[0];
[4868]872            PabloBlock * const block = adv->getParent(); assert (block);
[4870]873            PabloBuilder builder(block);
[4638]874            block->setInsertPoint(block->back());
[4585]875
[4578]876            /// Perform n-to-m Multiplexing
[4587]877            for (size_t j = 0; j != m; ++j) {
[4586]878
[4592]879                std::ostringstream prefix;
[4736]880                prefix << "mux" << n << "to" << m << '.' << (j + 1);
881                for (size_t i = 0; i != n; ++i) {
[4868]882                    if (((i + 1) & (1UL << j)) != 0) {
[4775]883                        assert (input[i]->getParent() == block);
[4736]884                        Q.push_back(input[i]->getOperand(0));
[4578]885                    }
886                }
[4587]887
888                while (Q.size() > 1) {
889                    PabloAST * a1 = Q.front(); Q.pop_front(); assert (a1);
890                    PabloAST * a2 = Q.front(); Q.pop_front(); assert (a2);
[4871]891                    assert (!Q.full());
[4638]892                    Q.push_back(builder.createOr(a2, a1, "muxing"));
[4578]893                }
[4585]894
[4587]895                PabloAST * mux = Q.front(); Q.pop_front(); assert (mux);
[4711]896                // The only way this did not return an Advance statement would be if either the mux or shift amount
[4871]897                // is zero. Since these cases would have been eliminated earlier, we are safe to cast here.
[4728]898                muxed[j] = cast<Advance>(builder.createAdvance(mux, adv->getOperand(1), prefix.str()));
[4578]899            }
900
[4871]901            /// Perform m-to-n Demultiplexing
[4736]902            for (size_t i = 0; i != n; ++i) {
[4578]903
[4702]904                // Construct the demuxed values and replaces all the users of the original advances with them.
[4587]905                for (size_t j = 0; j != m; ++j) {
[4868]906                    if (((i + 1) & (1UL << j)) == 0) {
[4587]907                        Q.push_back(muxed[j]);
908                    }
909                }
[4585]910
[4587]911                if (LLVM_LIKELY(Q.size() > 0)) {
912                    while (Q.size() > 1) {
913                        PabloAST * a1 = Q.front(); Q.pop_front(); assert (a1);
914                        PabloAST * a2 = Q.front(); Q.pop_front(); assert (a2);
915                        assert (!Q.full());
[4638]916                        Q.push_back(builder.createOr(a2, a1, "demuxing"));
[4587]917                    }
918                    assert (Q.size() == 1);
[4868]919                    PabloAST * neg = Q.front(); Q.pop_front(); assert (neg);
920                    Q.push_back(builder.createNot(neg, "demuxing"));
[4587]921                }
922
[4578]923                for (unsigned j = 0; j != m; ++j) {
[4736]924                    if (((i + 1) & (1ULL << j)) != 0) {
[4587]925                        assert (!Q.full());
926                        Q.push_back(muxed[j]);
[4578]927                    }
928                }
[4585]929
[4592]930                while (Q.size() > 1) {
[4587]931                    PabloAST * a1 = Q.front(); Q.pop_front(); assert (a1);
932                    PabloAST * a2 = Q.front(); Q.pop_front(); assert (a2);
933                    assert (!Q.full());
[4638]934                    Q.push_back(builder.createAnd(a1, a2, "demuxing"));
[4578]935                }
[4585]936
[4641]937                PabloAST * demuxed = Q.front(); Q.pop_front(); assert (demuxed);
[4736]938                input[i]->replaceWith(demuxed, true, true);
[4638]939            }
[4775]940        }
[4578]941    }
[4571]942}
943
[4868]944/** ------------------------------------------------------------------------------------------------------------- *
945 * @brief topologicalSort
946 *
947 * After transforming the IR, we need to run this in order to always have a valid program. Each multiplex set
948 * contains vertices corresponding to an Advance in the IR. While we know each Advance within a set is independent
949 * w.r.t. the transitive closure of their dependencies in the IR, the position of each Advance's dependencies and
950 * users within the IR isn't taken into consideration. Thus while there must be a valid ordering for the program,
951 * it's not necessarily the original ordering.
952 ** ------------------------------------------------------------------------------------------------------------- */
[4888]953void MultiplexingPass::topologicalSort(PabloFunction & function) {
[4868]954    // Note: not a real topological sort. I expect the original order to be very close to the resulting one.
955    std::unordered_set<const PabloAST *> encountered;
956    std::stack<Statement *> scope;
[4870]957    for (Statement * stmt = function.getEntryBlock()->front(); ; ) { restart:
[4868]958        while ( stmt ) {
959            for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
960                PabloAST * const op = stmt->getOperand(i);
961                if (LLVM_LIKELY(isa<Statement>(op))) {
962                    if (LLVM_UNLIKELY(encountered.count(op) == 0)) {
963                        if (LLVM_UNLIKELY(isa<While>(stmt) && isa<Next>(op))) {
964                            if (encountered.count(cast<Next>(op)->getInitial()) != 0) {
965                                continue;
966                            }
967                        }
968                        Statement * const next = stmt->getNextNode();
969                        stmt->insertAfter(cast<Statement>(op));
970                        stmt = next;
971                        goto restart;
972                    }
973                }
974            }
975            if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
976                // Set the next statement to be the first statement of the inner scope and push the
977                // next statement of the current statement into the scope stack.
[4870]978                const PabloBlock * const nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
[4868]979                scope.push(stmt->getNextNode());
[4870]980                stmt = nested->front();
[4868]981                continue;
982            }
983            encountered.insert(stmt);
984            stmt = stmt->getNextNode();
985        }
986        if (scope.empty()) {
987            break;
988        }
989        stmt = scope.top();
990        scope.pop();
991    }
992}
993
994/** ------------------------------------------------------------------------------------------------------------- *
[4870]995 * @brief doTransitiveReductionOfSubsetGraph
[4868]996 ** ------------------------------------------------------------------------------------------------------------- */
[4888]997void MultiplexingPass::doTransitiveReductionOfSubsetGraph() {
[4868]998    std::vector<SubsetGraph::vertex_descriptor> Q;
999    for (auto u : make_iterator_range(vertices(mSubsetGraph))) {
1000        if (in_degree(u, mSubsetGraph) == 0 && out_degree(u, mSubsetGraph) != 0) {
1001            Q.push_back(u);
1002        }
1003    }
1004    flat_set<SubsetGraph::vertex_descriptor> targets;
1005    flat_set<SubsetGraph::vertex_descriptor> visited;
1006    do {
1007        const auto u = Q.back(); Q.pop_back();
1008        for (auto ei : make_iterator_range(out_edges(u, mSubsetGraph))) {
1009            for (auto ej : make_iterator_range(out_edges(target(ei, mSubsetGraph), mSubsetGraph))) {
1010                targets.insert(target(ej, mSubsetGraph));
1011            }
1012        }
1013        for (auto v : targets) {
1014            remove_edge(u, v, mSubsetGraph);
1015        }
1016        for (auto e : make_iterator_range(out_edges(u, mSubsetGraph))) {
1017            const auto v = target(e, mSubsetGraph);
1018            if (visited.insert(v).second) {
1019                Q.push_back(v);
1020            }
1021        }
1022    } while (Q.size() > 0);
1023}
1024
[4870]1025/** ------------------------------------------------------------------------------------------------------------- *
1026 * @brief get
1027 ** ------------------------------------------------------------------------------------------------------------- */
[4888]1028inline BDD & MultiplexingPass::get(const PabloAST * const expr) {
1029    assert (expr);
[4871]1030    auto f = mCharacterization.find(expr);
1031    assert (f != mCharacterization.end());
[4870]1032    return f->second;
1033}
1034
[4582]1035} // end of namespace pablo
Note: See TracBrowser for help on using the repository browser.