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

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

Bug fix for Multiplexing. Added ability to set the body of a If/While? node after creation.

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