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

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

Minor improvements to the optimizers and AST manipulation.

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