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

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

More work on n-ary operations. Unresolved bug in DistributionPass?.

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