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

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

Work on bug fixes for multiplexing pass.

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