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

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

Work on adding Multiplexing Window Size.

File size: 41.9 KB
Line 
1#include "pablo_automultiplexing.hpp"
2#include <include/simd-lib/builtins.hpp>
3#include <pablo/builder.hpp>
4#include <pablo/function.h>
5#include <pablo/printer_pablos.h>
6#include <boost/container/flat_set.hpp>
7#include <boost/numeric/ublas/matrix.hpp>
8#include <boost/circular_buffer.hpp>
9#include <boost/graph/topological_sort.hpp>
10#include <boost/range/iterator_range.hpp>
11#include <pablo/analysis/pabloverifier.hpp>
12#include <stack>
13#include <queue>
14#include <unordered_set>
15#include <bdd.h>
16
17using namespace llvm;
18using namespace boost;
19using namespace boost::container;
20using namespace boost::numeric::ublas;
21
22#define PRINT_DEBUG_OUTPUT
23
24#if !defined(NDEBUG) && !defined(PRINT_DEBUG_OUTPUT)
25#define PRINT_DEBUG_OUTPUT
26#endif
27
28#ifdef PRINT_DEBUG_OUTPUT
29
30#include <iostream>
31
32using namespace pablo;
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
52#define LOG(x) std::cerr << x << std::endl;
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
58unsigned __count_advances(const PabloBlock * const entry) {
59
60    std::stack<const Statement *> scope;
61    unsigned advances = 0;
62
63    // Scan through and collect all the advances, calls, scanthrus and matchstars ...
64    for (const Statement * stmt = entry->front(); ; ) {
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.
72                const PabloBlock * const nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
73                scope.push(stmt->getNextNode());
74                stmt = nested->front();
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
91#else
92#define LOG(x)
93#define RECORD_TIMESTAMP(Name)
94#define LOG_GRAPH(Name, G)
95#define LOG_NUMBER_OF_ADVANCES(entry)
96#endif
97
98
99namespace pablo {
100
101using TypeId = PabloAST::ClassTypeId;
102
103bool MultiplexingPass::optimize(PabloFunction & function, const unsigned limit, const unsigned maxSelections, const unsigned windowSize, const bool independent) {
104
105//    std::random_device rd;
106//    const auto seed = rd();
107    const auto seed = 83234827342;
108    RNG rng(seed);
109
110    LOG("Seed:                    " << seed);
111
112    MultiplexingPass mp(limit, maxSelections, windowSize);
113    RECORD_TIMESTAMP(start_initialize);
114    const unsigned advances = mp.initialize(function, independent);
115    RECORD_TIMESTAMP(end_initialize);
116
117    LOG("Initialize:              " << (end_initialize - start_initialize));
118
119    LOG_NUMBER_OF_ADVANCES(function.getEntryBlock());
120
121    if (advances == 0) {
122        return false;
123    }
124
125    RECORD_TIMESTAMP(start_characterize);
126    mp.characterize(function.getEntryBlock());
127    RECORD_TIMESTAMP(end_characterize);
128
129    LOG("Characterize:            " << (end_characterize - start_characterize));
130
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
138    RECORD_TIMESTAMP(start_create_multiplex_graph);
139    const bool multiplex = mp.generateCandidateSets(rng);
140    RECORD_TIMESTAMP(end_create_multiplex_graph);
141    LOG("GenerateCandidateSets:   " << (end_create_multiplex_graph - start_create_multiplex_graph));
142
143    if (multiplex) {
144
145        RECORD_TIMESTAMP(start_select_multiplex_sets);
146        mp.selectMultiplexSets(rng);
147        RECORD_TIMESTAMP(end_select_multiplex_sets);
148        LOG("SelectMultiplexSets:     " << (end_select_multiplex_sets - start_select_multiplex_sets));
149
150        RECORD_TIMESTAMP(start_subset_constraints);
151        mp.eliminateSubsetConstraints();
152        RECORD_TIMESTAMP(end_subset_constraints);
153        LOG("ApplySubsetConstraints:  " << (end_subset_constraints - start_subset_constraints));
154
155        RECORD_TIMESTAMP(start_select_independent_sets);
156        mp.multiplexSelectedIndependentSets(function);
157        RECORD_TIMESTAMP(end_select_independent_sets);
158        LOG("SelectedIndependentSets: " << (end_select_independent_sets - start_select_independent_sets));
159
160        MultiplexingPass::topologicalSort(function);
161        #ifndef NDEBUG
162        PabloVerifier::verify(function, "post-multiplexing");
163        #endif
164    }
165
166    LOG_NUMBER_OF_ADVANCES(function.getEntryBlock());
167    return multiplex;
168}
169
170/** ------------------------------------------------------------------------------------------------------------- *
171 * @brief initialize
172 * @param function the function to optimize
173 * @returns true if there are fewer than three advances in this function
174 *
175 * Scan through the program to identify any advances and calls then initialize the BDD engine with
176 * the proper variable ordering.
177 ** ------------------------------------------------------------------------------------------------------------- */
178unsigned MultiplexingPass::initialize(PabloFunction & function, const bool independent) {
179
180    std::stack<Statement *> scope;
181    unsigned variableCount = 0; // number of statements that cannot always be categorized without generating a new variable
182
183    // Scan through and collect all the advances, calls, scanthrus and matchstars ...
184    unsigned statements = 0, advances = 0;
185    for (Statement * stmt = function.getEntryBlock()->front(); ; ) {
186        while ( stmt ) {
187            ++statements;
188            if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
189                scope.push(stmt->getNextNode());
190                const PabloBlock * const nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();               
191                stmt = nested->front();
192                assert (stmt);
193                continue;
194            }
195            switch (stmt->getClassTypeId()) {
196                case TypeId::Advance:
197                    ++advances;
198                case TypeId::ScanThru:
199                case TypeId::Call:
200                case TypeId::MatchStar:
201                    ++variableCount;
202                    break;
203                default:
204                    break;
205            }
206            stmt = stmt->getNextNode();
207        }
208        if (scope.empty()) {
209            break;
210        }
211        stmt = scope.top();
212        scope.pop();
213    }
214
215    // If there are fewer than three Advances in this program, just abort. We cannot reduce it.
216    if (advances < 3) {
217        return 0;
218    }
219
220    initializeBaseConstraintGraph(function.getEntryBlock(), statements, advances);
221
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);
269    matrix<bool> G(statements, advances, false);
270    for (unsigned i = 0; i != advances; ++i) {
271        G(i, i) = true;
272    }
273
274    unsigned n = advances;
275    unsigned k = 0;
276    for (const Statement * stmt = block->front();;) {
277        while ( stmt ) {
278            unsigned u = 0;
279            if (LLVM_UNLIKELY(isa<Advance>(stmt))) {
280                u = k++;
281            } else {
282                u = n++;
283            }
284            M.emplace(stmt, u);
285            for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
286                const PabloAST * const op = stmt->getOperand(i);
287                if (LLVM_LIKELY(isa<Statement>(op))) {
288                    const unsigned v = M[op];
289                    for (unsigned w = 0; w != k; ++w) {
290                        G(u, w) |= G(v, w);
291                    }
292                }
293            }
294            if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
295                scope.push(stmt->getNextNode());
296                const PabloBlock * const nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
297                stmt = nested->front();
298                assert (stmt);
299                continue;
300            }
301            stmt = stmt->getNextNode();
302        }
303        if (scope.empty()) {
304            break;
305        }
306        stmt = scope.top();
307        scope.pop();
308    }
309
310    assert (k == advances);
311
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.
314
315    mConstraintGraph = ConstraintGraph(advances);
316    for (unsigned i = 0; i != advances; ++i) {
317        for (unsigned j = 0; j < i; ++j) {
318            if (G(i, j)) {
319                add_edge(j, i, mConstraintGraph);
320            }
321        }
322        for (unsigned j = i + 1; j < advances; ++j) {
323            if (G(i, j)) {
324                add_edge(j, i, mConstraintGraph);
325            }
326        }
327    }
328
329}
330
331/** ------------------------------------------------------------------------------------------------------------- *
332 * @brief initializeAdvanceDepth
333 ** ------------------------------------------------------------------------------------------------------------- */
334inline void MultiplexingPass::initializeAdvanceDepth(PabloBlock * const block, const unsigned advances) {
335
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);
359            }
360            stmt = stmt->getNextNode();
361        }
362        if (scope.empty()) {
363            break;
364        }
365        stmt = scope.top();
366        scope.pop();
367    }
368    assert (k == advances);
369
370    LOG("Window Size / Max Depth: " << mWindowSize << " of " << maxDepth);
371}
372
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 ** ------------------------------------------------------------------------------------------------------------- */
379void MultiplexingPass::characterize(PabloBlock * const block) {
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            }
394        } else {
395            mCharacterization.insert(std::make_pair(stmt, characterize(stmt)));
396        }
397    }
398}
399
400/** ------------------------------------------------------------------------------------------------------------- *
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/** ------------------------------------------------------------------------------------------------------------- *
412 * @brief characterize
413 ** ------------------------------------------------------------------------------------------------------------- */
414inline BDD MultiplexingPass::characterize(Statement * const stmt) {
415    BDD bdd = get(stmt->getOperand(0));
416    switch (stmt->getClassTypeId()) {
417        case TypeId::Assign:
418        case TypeId::Next:
419            break;
420        case TypeId::And:
421            for (unsigned i = 1; i != stmt->getNumOperands(); ++i) {
422                bdd = bdd_and(bdd, get(stmt->getOperand(i)));
423            }
424            break;
425        case TypeId::Or:
426            for (unsigned i = 1; i != stmt->getNumOperands(); ++i) {
427                bdd = bdd_or(bdd, get(stmt->getOperand(i)));
428            }
429            break;
430        case TypeId::Xor:
431            for (unsigned i = 1; i != stmt->getNumOperands(); ++i) {
432                bdd = bdd_xor(bdd, get(stmt->getOperand(i)));
433            }
434            break;
435        case TypeId::Not:
436            bdd = bdd_not(bdd);
437            break;
438        case TypeId::Sel:
439            bdd = bdd_ite(bdd, get(stmt->getOperand(1)), get(stmt->getOperand(2)));
440            break;
441        case TypeId::ScanThru:
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.
444        case TypeId::MatchStar:
445        case TypeId::Call:
446            return bdd_ithvar(mVariables++);
447        case TypeId::Advance:
448            return characterize(cast<Advance>(stmt), bdd);
449        default:
450            throwUnexpectedStatementTypeError(stmt);
451    }
452    return bdd_addref(bdd);
453}
454
455/** ------------------------------------------------------------------------------------------------------------- *
456 * @brief characterize
457 ** ------------------------------------------------------------------------------------------------------------- */
458inline BDD MultiplexingPass::characterize(Advance * const adv, const BDD Ik) {
459    const auto k = mAdvanceAttributes.size();
460    std::vector<bool> unconstrained(k , false);
461    for (unsigned i = 0; i != k; ++i) {
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?
465        if (unconstrained[i]) continue;
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.
468        const Advance * const ithAdv = std::get<0>(mAdvanceAttributes[i]);
469        if ((mTestConstrainedAdvances || independent(i, k)) && (ithAdv->getOperand(1) == adv->getOperand(1))) {
470            const BDD Ii = get(ithAdv->getOperand(0));
471            const BDD IiIk = bdd_addref(bdd_and(Ii, Ik));
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))) {
476                    unconstrained[source(e, mSubsetGraph)] = true;
477                }
478                unconstrained[i] = true;
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;
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;
499                }
500                unconstrained[i] = true;
501            }
502            bdd_delref(IiIk);
503        }
504    }
505
506    BDD Ck = bdd_ithvar(mVariables++);
507    const BDD Nk = bdd_addref(bdd_not(Ck));
508    for (unsigned i = 0; i != k; ++i) {
509        if (unconstrained[i]) {
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())) {
517                continue;
518            }
519        }
520        add_edge(i, k, mConstraintGraph);
521    }
522    mAdvanceAttributes.emplace_back(adv, Nk);
523    return Ck;
524}
525
526/** ------------------------------------------------------------------------------------------------------------- *
527 * @brief independent
528 ** ------------------------------------------------------------------------------------------------------------- */
529inline bool MultiplexingPass::independent(const ConstraintVertex i, const ConstraintVertex j) const {
530    assert (i < num_vertices(mConstraintGraph) && j < num_vertices(mConstraintGraph));
531    return (mConstraintGraph.get_edge(i, j) == 0);
532}
533
534/** ------------------------------------------------------------------------------------------------------------- *
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/** ------------------------------------------------------------------------------------------------------------- *
543 * @brief generateMultiplexSets
544 * @param RNG random number generator
545 ** ------------------------------------------------------------------------------------------------------------- */
546bool MultiplexingPass::generateCandidateSets(RNG & rng) {
547
548    using degree_t = graph_traits<ConstraintGraph>::degree_size_type;
549
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
554    VertexVector S;
555    std::vector<degree_t> D(num_vertices(mConstraintGraph));
556    S.reserve(15);
557
558    mMultiplexSetGraph = MultiplexSetGraph(num_vertices(mConstraintGraph));
559
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);
566        }
567    }
568
569    assert (S.size() > 0);
570
571    auto remainingVerticies = num_vertices(mConstraintGraph) - S.size();
572
573    do {
574
575        addCandidateSet(S, rng);
576
577        bool noNewElements = true;
578        do {
579            assert (S.size() > 0);
580            // Randomly choose a vertex in S and discard it.
581            const auto i = S.begin() + IntDistribution(0, S.size() - 1)(rng);
582            assert (i != S.end());
583            const ConstraintVertex u = *i;
584            S.erase(i);
585
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);
590                    --remainingVerticies;
591                    noNewElements = false;
592                }
593            }
594        }
595        while (noNewElements && remainingVerticies);
596    }
597    while (remainingVerticies);
598
599    return num_vertices(mMultiplexSetGraph) > num_vertices(mConstraintGraph);
600}
601
602/** ------------------------------------------------------------------------------------------------------------- *
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/** ------------------------------------------------------------------------------------------------------------- *
640 * @brief addCandidateSet
641 * @param S an independent set
642 ** ------------------------------------------------------------------------------------------------------------- */
643inline void MultiplexingPass::addCandidateSet(const VertexVector & S, RNG & rng) {
644    if (S.size() >= 3) {
645        if (S.size() <= mMultiplexingSetSizeLimit) {
646            const auto u = add_vertex(mMultiplexSetGraph);
647            for (const auto v : S) {
648                add_edge(u, v, mMultiplexSetGraph);
649            }
650        } else {
651            const auto max = choose(S.size(), mMultiplexingSetSizeLimit);
652            unsigned element[mMultiplexingSetSizeLimit];
653            if (LLVM_UNLIKELY(max <= mMaxMultiplexingSetSelections)) {
654                for (unsigned i = 0; i != max; ++i) {
655                    select(S.size(), mMultiplexingSetSizeLimit, i, element);
656                    const auto u = add_vertex(mMultiplexSetGraph);
657                    for (unsigned j = 0; j != mMultiplexingSetSizeLimit; ++j) {
658                        add_edge(u, S[element[j]], mMultiplexSetGraph);
659                    }
660                }
661            } else { // take m random samples
662                for (unsigned i = 0; i != mMaxMultiplexingSetSelections; ++i) {
663                    select(S.size(), mMultiplexingSetSizeLimit, rng() % max, element);
664                    const auto u = add_vertex(mMultiplexSetGraph);
665                    for (unsigned j = 0; j != mMultiplexingSetSizeLimit; ++j) {
666                        add_edge(u, S[element[j]], mMultiplexSetGraph);
667                    }
668                }
669            }
670        }
671    }
672}
673
674/** ------------------------------------------------------------------------------------------------------------- *
675 * @brief is_power_of_2
676 * @param n an integer
677 ** ------------------------------------------------------------------------------------------------------------- */
678static inline bool is_power_of_2(const size_t n) {
679    return ((n & (n - 1)) == 0) ;
680}
681
682/** ------------------------------------------------------------------------------------------------------------- *
683 * @brief log2_plus_one
684 ** ------------------------------------------------------------------------------------------------------------- */
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?
687}
688
689/** ------------------------------------------------------------------------------------------------------------- *
690 * @brief selectMultiplexSets
691 * @param RNG random number generator
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
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.
697 ** ------------------------------------------------------------------------------------------------------------- */
698void MultiplexingPass::selectMultiplexSets(RNG &) {
699
700    using InEdgeIterator = graph_traits<MultiplexSetGraph>::in_edge_iterator;
701    using degree_t = MultiplexSetGraph::degree_size_type;
702    using vertex_t = MultiplexSetGraph::vertex_descriptor;
703
704    const size_t m = num_vertices(mConstraintGraph);
705    const size_t n = num_vertices(mMultiplexSetGraph) - m;
706
707    std::vector<degree_t> remaining(n, 0);
708    std::vector<vertex_t> chosen_set(m, 0);
709
710    for (unsigned i = 0; i != n; ++i) {
711        remaining[i] = out_degree(i + m, mMultiplexSetGraph);
712    }
713
714    for (;;) {
715
716        // Choose the set with the greatest number of vertices not already included in some other set.
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;
724            }
725        }
726
727        // Multiplexing requires at least 3 elements; if the best set contains fewer than 3, abort.
728        if (w < 3) {
729            break;
730        }
731
732        for (const auto ei : make_iterator_range(out_edges(k + m, mMultiplexSetGraph))) {
733            const vertex_t j = target(ei, mMultiplexSetGraph);
734            if (chosen_set[j] == 0) {
735                chosen_set[j] = (k + m);
736                for (const auto ej : make_iterator_range(in_edges(j, mMultiplexSetGraph))) {
737                    remaining[source(ej, mMultiplexSetGraph) - m]--;
738                }
739            }
740        }
741
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)) {
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;
752                    for (const auto ej : make_iterator_range(in_edges(i, mMultiplexSetGraph))) {
753                        // strongly prefer adding weight to unvisited sets that have more remaining vertices
754                        r += std::pow(remaining[source(ej, mMultiplexSetGraph) - m], 2);
755                    }
756                    if (w < r) {
757                        j = i;
758                        w = r;
759                    }
760                }
761            }
762            assert (w > 0);
763            chosen_set[j] = 0;
764            for (const auto ej : make_iterator_range(in_edges(j, mMultiplexSetGraph))) {
765                remaining[source(ej, mMultiplexSetGraph) - m]++;
766            }
767        }
768    }
769
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);
777            }
778        }
779    }
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
789}
790
791/** ------------------------------------------------------------------------------------------------------------- *
792 * @brief eliminateSubsetConstraints
793 ** ------------------------------------------------------------------------------------------------------------- */
794void MultiplexingPass::eliminateSubsetConstraints() {
795
796    using SubsetEdgeIterator = graph_traits<SubsetGraph>::edge_iterator;
797
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) {
807            assert (in_degree(u, mMultiplexSetGraph) == 1);
808            const auto su = source(*(in_edges(u, mMultiplexSetGraph).first), mMultiplexSetGraph);
809            assert (in_degree(v, mMultiplexSetGraph) == 1);
810            const auto sv = source(*(in_edges(v, mMultiplexSetGraph).first), mMultiplexSetGraph);
811            if (su == sv) {
812                continue;
813            }
814        }
815        remove_edge(*ei, mSubsetGraph);
816    }
817
818    if (num_edges(mSubsetGraph) != 0) {
819
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.
822
823        doTransitiveReductionOfSubsetGraph();
824
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        }
836
837    }
838}
839
840/** ------------------------------------------------------------------------------------------------------------- *
841 * @brief multiplexSelectedIndependentSets
842 ** ------------------------------------------------------------------------------------------------------------- */
843void MultiplexingPass::multiplexSelectedIndependentSets(PabloFunction &) {
844
845    const unsigned first_set = num_vertices(mConstraintGraph);
846    const unsigned last_set = num_vertices(mMultiplexSetGraph);
847
848    // Preallocate the structures based on the size of the largest multiplex set
849    size_t max_n = 3;
850    for (unsigned idx = first_set; idx != last_set; ++idx) {
851        max_n = std::max<unsigned>(max_n, out_degree(idx, mMultiplexSetGraph));
852    }
853
854    circular_buffer<PabloAST *> Q(max_n);
855
856    // When entering thus function, the multiplex set graph M is a DAG with edges denoting the set
857    // relationships of our independent sets.
858
859    for (unsigned idx = first_set; idx != last_set; ++idx) {
860        const size_t n = out_degree(idx, mMultiplexSetGraph);
861        if (n) {
862            const size_t m = log2_plus_one(n);
863            Advance * input[n];
864            Advance * muxed[m];
865
866            unsigned i = 0;
867            for (const auto e : make_iterator_range(out_edges(idx, mMultiplexSetGraph))) {
868                input[i++] = std::get<0>(mAdvanceAttributes[target(e, mMultiplexSetGraph)]);
869            }
870
871            Advance * const adv = input[0];
872            PabloBlock * const block = adv->getParent(); assert (block);
873            PabloBuilder builder(block);
874            block->setInsertPoint(block->back());
875
876            /// Perform n-to-m Multiplexing
877            for (size_t j = 0; j != m; ++j) {
878
879                std::ostringstream prefix;
880                prefix << "mux" << n << "to" << m << '.' << (j + 1);
881                for (size_t i = 0; i != n; ++i) {
882                    if (((i + 1) & (1UL << j)) != 0) {
883                        assert (input[i]->getParent() == block);
884                        Q.push_back(input[i]->getOperand(0));
885                    }
886                }
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);
891                    assert (!Q.full());
892                    Q.push_back(builder.createOr(a2, a1, "muxing"));
893                }
894
895                PabloAST * mux = Q.front(); Q.pop_front(); assert (mux);
896                // The only way this did not return an Advance statement would be if either the mux or shift amount
897                // is zero. Since these cases would have been eliminated earlier, we are safe to cast here.
898                muxed[j] = cast<Advance>(builder.createAdvance(mux, adv->getOperand(1), prefix.str()));
899            }
900
901            /// Perform m-to-n Demultiplexing
902            for (size_t i = 0; i != n; ++i) {
903
904                // Construct the demuxed values and replaces all the users of the original advances with them.
905                for (size_t j = 0; j != m; ++j) {
906                    if (((i + 1) & (1UL << j)) == 0) {
907                        Q.push_back(muxed[j]);
908                    }
909                }
910
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());
916                        Q.push_back(builder.createOr(a2, a1, "demuxing"));
917                    }
918                    assert (Q.size() == 1);
919                    PabloAST * neg = Q.front(); Q.pop_front(); assert (neg);
920                    Q.push_back(builder.createNot(neg, "demuxing"));
921                }
922
923                for (unsigned j = 0; j != m; ++j) {
924                    if (((i + 1) & (1ULL << j)) != 0) {
925                        assert (!Q.full());
926                        Q.push_back(muxed[j]);
927                    }
928                }
929
930                while (Q.size() > 1) {
931                    PabloAST * a1 = Q.front(); Q.pop_front(); assert (a1);
932                    PabloAST * a2 = Q.front(); Q.pop_front(); assert (a2);
933                    assert (!Q.full());
934                    Q.push_back(builder.createAnd(a1, a2, "demuxing"));
935                }
936
937                PabloAST * demuxed = Q.front(); Q.pop_front(); assert (demuxed);
938                input[i]->replaceWith(demuxed, true, true);
939            }
940        }
941    }
942}
943
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 ** ------------------------------------------------------------------------------------------------------------- */
953void MultiplexingPass::topologicalSort(PabloFunction & function) {
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;
957    for (Statement * stmt = function.getEntryBlock()->front(); ; ) { restart:
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.
978                const PabloBlock * const nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
979                scope.push(stmt->getNextNode());
980                stmt = nested->front();
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/** ------------------------------------------------------------------------------------------------------------- *
995 * @brief doTransitiveReductionOfSubsetGraph
996 ** ------------------------------------------------------------------------------------------------------------- */
997void MultiplexingPass::doTransitiveReductionOfSubsetGraph() {
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
1025/** ------------------------------------------------------------------------------------------------------------- *
1026 * @brief get
1027 ** ------------------------------------------------------------------------------------------------------------- */
1028inline BDD & MultiplexingPass::get(const PabloAST * const expr) {
1029    assert (expr);
1030    auto f = mCharacterization.find(expr);
1031    assert (f != mCharacterization.end());
1032    return f->second;
1033}
1034
1035} // end of namespace pablo
Note: See TracBrowser for help on using the repository browser.