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

Last change on this file since 4942 was 4942, checked in by lindanl, 3 years ago

Remove simd-lib. Print register implemented in LLVM IR.

File size: 64.0 KB
Line 
1#include "pablo_automultiplexing.hpp"
2#include <pablo/builder.hpp>
3#include <pablo/function.h>
4#include <pablo/printer_pablos.h>
5#include <boost/container/flat_set.hpp>
6#include <boost/numeric/ublas/matrix.hpp>
7#include <boost/circular_buffer.hpp>
8#include <boost/graph/topological_sort.hpp>
9#include <boost/range/iterator_range.hpp>
10#include <pablo/analysis/pabloverifier.hpp>
11#include <pablo/optimizers/pablo_simplifier.hpp>
12#include <pablo/builder.hpp>
13#include <stack>
14#include <queue>
15#include <unordered_set>
16#include <bdd.h>
17#include <functional>
18
19#include <llvm/Support/CommandLine.h>
20
21using namespace llvm;
22using namespace boost;
23using namespace boost::container;
24using namespace boost::numeric::ublas;
25
26/// Interesting test cases:
27/// ./icgrep -c -multiplexing '[\p{Lm}\p{Meetei_Mayek}]' -disable-if-hierarchy-strategy
28
29/// ./icgrep -c -multiplexing '\p{Imperial_Aramaic}(?<!\p{Sm})' -disable-if-hierarchy-strategy
30
31
32static cl::OptionCategory MultiplexingOptions("Multiplexing Optimization Options", "These options control the Pablo Multiplexing optimization pass.");
33
34#ifdef NDEBUG
35#define INITIAL_SEED_VALUE (std::random_device()())
36#else
37#define INITIAL_SEED_VALUE (83234827342)
38#endif
39
40static cl::opt<std::mt19937::result_type> Seed("multiplexing-seed", cl::init(INITIAL_SEED_VALUE),
41                                        cl::desc("randomization seed used when performing any non-deterministic operations."),
42                                        cl::cat(MultiplexingOptions));
43
44#undef INITIAL_SEED_VALUE
45
46static cl::opt<unsigned> SetLimit("multiplexing-set-limit", cl::init(std::numeric_limits<unsigned>::max()),
47                                        cl::desc("maximum size of any candidate set."),
48                                        cl::cat(MultiplexingOptions));
49
50static cl::opt<unsigned> SelectionLimit("multiplexing-selection-limit", cl::init(100),
51                                        cl::desc("maximum number of selections from any partial candidate set."),
52                                        cl::cat(MultiplexingOptions));
53
54static cl::opt<unsigned> WindowSize("multiplexing-window-size", cl::init(1),
55                                        cl::desc("maximum depth difference for computing mutual exclusion of Advance nodes."),
56                                        cl::cat(MultiplexingOptions));
57
58static cl::opt<unsigned> Samples("multiplexing-samples", cl::init(1),
59                                 cl::desc("number of times the Advance constraint graph is sampled to find multiplexing opportunities."),
60                                 cl::cat(MultiplexingOptions));
61
62
63enum SelectionStrategy {Greedy, WorkingSet};
64
65static cl::opt<SelectionStrategy> Strategy(cl::desc("Choose set selection strategy:"),
66                                             cl::values(
67                                             clEnumVal(Greedy, "choose the largest multiplexing sets possible (w.r.t. the multiplexing-set-limit)."),
68                                             clEnumVal(WorkingSet, "choose multiplexing sets that share common input values."),
69                                             clEnumValEnd),
70                                           cl::init(Greedy),
71                                           cl::cat(MultiplexingOptions));
72
73// #define PRINT_DEBUG_OUTPUT
74
75#if !defined(NDEBUG) && !defined(PRINT_DEBUG_OUTPUT)
76#define PRINT_DEBUG_OUTPUT
77#endif
78
79#ifdef PRINT_DEBUG_OUTPUT
80
81#include <iostream>
82
83using namespace pablo;
84typedef uint64_t timestamp_t;
85
86static inline timestamp_t read_cycle_counter() {
87#ifdef __GNUC__
88timestamp_t ts;
89#ifdef __x86_64__
90  unsigned int eax, edx;
91  asm volatile("rdtsc" : "=a" (eax), "=d" (edx));
92  ts = ((timestamp_t) eax) | (((timestamp_t) edx) << 32);
93#else
94  asm volatile("rdtsc\n" : "=A" (ts));
95#endif
96  return(ts);
97#endif
98#ifdef _MSC_VER
99  return __rdtsc();
100#endif
101}
102
103#define LOG(x) std::cerr << x << std::endl;
104#define RECORD_TIMESTAMP(Name) const timestamp_t Name = read_cycle_counter()
105#define LOG_GRAPH(Name, G) \
106    LOG(Name << " |V|=" << num_vertices(G) << ", |E|="  << num_edges(G) << \
107                " (" << (((double)num_edges(G)) / ((double)(num_vertices(G) * (num_vertices(G) - 1) / 2))) << ')')
108
109unsigned __count_advances(const PabloBlock * const entry) {
110
111    std::stack<const Statement *> scope;
112    unsigned advances = 0;
113
114    // Scan through and collect all the advances, calls, scanthrus and matchstars ...
115    for (const Statement * stmt = entry->front(); ; ) {
116        while ( stmt ) {
117            if (isa<Advance>(stmt)) {
118                ++advances;
119            }
120            else if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
121                // Set the next statement to be the first statement of the inner scope and push the
122                // next statement of the current statement into the scope stack.
123                const PabloBlock * const nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
124                scope.push(stmt->getNextNode());
125                stmt = nested->front();
126                assert (stmt);
127                continue;
128            }
129            stmt = stmt->getNextNode();
130        }
131        if (scope.empty()) {
132            break;
133        }
134        stmt = scope.top();
135        scope.pop();
136    }
137    return advances;
138}
139
140#define LOG_NUMBER_OF_ADVANCES(entry) LOG("|Advances|=" << __count_advances(entry))
141
142#else
143#define LOG(x)
144#define RECORD_TIMESTAMP(Name)
145#define LOG_GRAPH(Name, G)
146#define LOG_NUMBER_OF_ADVANCES(entry)
147#endif
148
149
150namespace pablo {
151
152#ifdef PRINT_TIMING_INFORMATION
153MultiplexingPass::seed_t MultiplexingPass::SEED = 0;
154unsigned MultiplexingPass::NODES_ALLOCATED = 0;
155unsigned MultiplexingPass::NODES_USED = 0;
156#endif
157
158using TypeId = PabloAST::ClassTypeId;
159
160template<typename Graph>
161static Graph construct(PabloBlock * const block);
162
163template<typename Graph, typename Map>
164static Graph construct(PabloBlock * const block, Map & M);
165
166bool MultiplexingPass::optimize(PabloFunction & function, const bool independent) {
167
168    LOG("Seed:                    " << Seed);
169
170    #ifdef PRINT_TIMING_INFORMATION
171    MultiplexingPass::SEED = Seed;
172    MultiplexingPass::NODES_ALLOCATED = 0;
173    MultiplexingPass::NODES_USED = 0;
174    #endif
175
176    MultiplexingPass mp(Seed);
177    RECORD_TIMESTAMP(start_initialize);
178    const unsigned advances = mp.initialize(function, independent);
179    RECORD_TIMESTAMP(end_initialize);
180
181    LOG("Initialize:              " << (end_initialize - start_initialize));
182
183    LOG_NUMBER_OF_ADVANCES(function.getEntryBlock());
184
185    if (advances == 0) {
186        return false;
187    }
188
189    RECORD_TIMESTAMP(start_characterize);
190    mp.characterize(function.getEntryBlock());
191    RECORD_TIMESTAMP(end_characterize);
192
193    LOG("Characterize:             " << (end_characterize - start_characterize));
194
195    LOG("Nodes in BDD:             " << bdd_getnodenum() << " of " << bdd_getallocnum());
196
197    #ifdef PRINT_TIMING_INFORMATION
198    MultiplexingPass::NODES_ALLOCATED = bdd_getallocnum();
199    MultiplexingPass::NODES_USED = bdd_getnodenum();
200    #endif
201
202    RECORD_TIMESTAMP(start_shutdown);
203    bdd_done();
204    RECORD_TIMESTAMP(end_shutdown);
205    LOG("Shutdown:                 " << (end_shutdown - start_shutdown));
206
207    RECORD_TIMESTAMP(start_create_multiplex_graph);
208    const bool multiplex = mp.generateCandidateSets();
209    RECORD_TIMESTAMP(end_create_multiplex_graph);
210    LOG("GenerateCandidateSets:    " << (end_create_multiplex_graph - start_create_multiplex_graph));
211
212    if (multiplex) {
213
214        RECORD_TIMESTAMP(start_usage_weighting);
215        mp.generateUsageWeightingGraph();
216        RECORD_TIMESTAMP(end_usage_weighting);
217        LOG("GenerateUsageWeighting:   " << (end_usage_weighting - start_usage_weighting));
218
219        RECORD_TIMESTAMP(start_select_multiplex_sets);
220        if (Strategy == SelectionStrategy::Greedy) {
221            mp.selectMultiplexSetsGreedy();
222        } else if (Strategy == SelectionStrategy::WorkingSet) {
223            mp.selectMultiplexSetsWorkingSet();
224        }
225        RECORD_TIMESTAMP(end_select_multiplex_sets);
226        LOG("SelectMultiplexSets:      " << (end_select_multiplex_sets - start_select_multiplex_sets));
227
228        RECORD_TIMESTAMP(start_subset_constraints);
229        mp.eliminateSubsetConstraints();
230        RECORD_TIMESTAMP(end_subset_constraints);
231        LOG("ApplySubsetConstraints:   " << (end_subset_constraints - start_subset_constraints));
232
233        RECORD_TIMESTAMP(start_select_independent_sets);
234        mp.multiplexSelectedSets(function);
235        RECORD_TIMESTAMP(end_select_independent_sets);
236        LOG("MultiplexSelectedSets:    " << (end_select_independent_sets - start_select_independent_sets));
237
238        #ifndef NDEBUG
239        PabloVerifier::verify(function, "post-multiplexing");
240        #endif
241
242        Simplifier::optimize(function);
243    }
244
245    LOG_NUMBER_OF_ADVANCES(function.getEntryBlock());
246
247    return multiplex;
248}
249
250/** ------------------------------------------------------------------------------------------------------------- *
251 * @brief initialize
252 * @param function the function to optimize
253 * @returns true if there are fewer than three advances in this function
254 *
255 * Scan through the program to identify any advances and calls then initialize the BDD engine with
256 * the proper variable ordering.
257 ** ------------------------------------------------------------------------------------------------------------- */
258unsigned MultiplexingPass::initialize(PabloFunction & function, const bool independent) {
259
260    std::stack<Statement *> scope;
261    unsigned variableCount = 0; // number of statements that cannot always be categorized without generating a new variable
262
263    // Scan through and collect all the advances, calls, scanthrus and matchstars ...
264    unsigned statements = 0, advances = 0;
265    for (Statement * stmt = function.getEntryBlock()->front(); ; ) {
266        while ( stmt ) {
267            ++statements;
268            if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
269                scope.push(stmt->getNextNode());
270                const PabloBlock * const nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();               
271                stmt = nested->front();
272                assert (stmt);
273                continue;
274            }
275            switch (stmt->getClassTypeId()) {
276                case TypeId::Advance:
277                    ++advances;
278                case TypeId::ScanThru:
279                case TypeId::Call:
280                case TypeId::MatchStar:
281                    ++variableCount;
282                    break;
283                default:
284                    break;
285            }
286            stmt = stmt->getNextNode();
287        }
288        if (scope.empty()) {
289            break;
290        }
291        stmt = scope.top();
292        scope.pop();
293    }
294
295    // If there are fewer than three Advances in this program, just abort. We cannot reduce it.
296    if (advances < 3) {
297        return 0;
298    }
299
300    initializeBaseConstraintGraph(function.getEntryBlock(), statements, advances);
301
302    mSubsetGraph = SubsetGraph(advances);
303
304    initializeAdvanceDepth(function.getEntryBlock(), advances);
305
306    // Initialize the BDD engine ...
307    bdd_init(10000000, 100000);
308    bdd_setvarnum(variableCount + function.getNumOfParameters());
309    bdd_setcacheratio(64);
310    bdd_setmaxincrease(10000000);
311    bdd_autoreorder(BDD_REORDER_SIFT); // BDD_REORDER_SIFT
312
313    // Map the constants and input variables
314    mCharacterization[PabloBlock::createZeroes()] = bdd_zero();
315    mCharacterization[PabloBlock::createOnes()] = bdd_one();
316    mVariables = function.getNumOfParameters();
317
318    // TODO: record information in the function to indicate which pairs of input variables are independent
319    if (independent) {
320        for (unsigned i = 0; i != mVariables; ++i) {
321            BDD Vi = bdd_ithvar(i);
322            BDD Ni = bdd_zero();
323            for (unsigned j = 0; j != i; ++j) {
324                Ni = bdd_addref(bdd_or(Ni, bdd_ithvar(j)));
325            }
326            for (unsigned j = i + 1; j != mVariables; ++j) {
327                Ni = bdd_addref(bdd_or(Ni, bdd_ithvar(j)));
328            }
329            Ni = bdd_addref(bdd_not(Ni));
330            mCharacterization[function.getParameter(i)] = bdd_addref(bdd_imp(Vi, Ni));
331        }
332    } else {
333        for (unsigned i = 0; i != mVariables; ++i) {
334            mCharacterization[function.getParameter(i)] = bdd_ithvar(i);
335        }
336    }
337
338    return advances;
339}
340
341/** ------------------------------------------------------------------------------------------------------------- *
342 * @brief initializeBaseConstraintGraph
343 ** ------------------------------------------------------------------------------------------------------------- */
344inline void MultiplexingPass::initializeBaseConstraintGraph(PabloBlock * const block, const unsigned statements, const unsigned advances) {
345
346    std::stack<Statement *> scope;
347    flat_map<const PabloAST *, unsigned> M;
348    M.reserve(statements);
349    matrix<bool> G(statements, advances, false);
350    for (unsigned i = 0; i != advances; ++i) {
351        G(i, i) = true;
352    }
353
354    unsigned n = advances;
355    unsigned k = 0;
356    for (const Statement * stmt = block->front();;) {
357        while ( stmt ) {
358            unsigned u = 0;
359            if (LLVM_UNLIKELY(isa<Advance>(stmt))) {
360                u = k++;
361            } else {
362                u = n++;
363            }
364            M.emplace(stmt, u);
365            for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
366                const PabloAST * const op = stmt->getOperand(i);
367                if (LLVM_LIKELY(isa<Statement>(op))) {
368                    const unsigned v = M[op];
369                    for (unsigned w = 0; w != k; ++w) {
370                        G(u, w) |= G(v, w);
371                    }
372                }
373            }
374            if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
375                scope.push(stmt->getNextNode());
376                const PabloBlock * const nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
377                stmt = nested->front();
378                assert (stmt);
379                continue;
380            }
381            stmt = stmt->getNextNode();
382        }
383        if (scope.empty()) {
384            break;
385        }
386        stmt = scope.top();
387        scope.pop();
388    }
389
390    assert (k == advances);
391
392    // Initialize the base constraint graph by effectively transposing G and removing reflective loops
393    mConstraintGraph = ConstraintGraph(advances);
394    for (unsigned i = 0; i != advances; ++i) {
395        for (unsigned j = 0; j < i; ++j) {
396            if (G(i, j)) {
397                add_edge(j, i, mConstraintGraph);
398            }
399        }
400        for (unsigned j = i + 1; j < advances; ++j) {
401            if (G(i, j)) {
402                add_edge(j, i, mConstraintGraph);
403            }
404        }
405    }
406
407}
408
409/** ------------------------------------------------------------------------------------------------------------- *
410 * @brief initializeAdvanceDepth
411 ** ------------------------------------------------------------------------------------------------------------- */
412inline void MultiplexingPass::initializeAdvanceDepth(PabloBlock * const entryBlock, const unsigned advances) {
413
414    std::stack<Statement *> scope;
415    unsigned k = 0;
416    int maxDepth = 0;
417    const PabloBlock * advanceScope[advances];
418    mAdvance.resize(advances, nullptr);
419    mAdvanceRank.resize(advances, 0);
420    mAdvanceNegatedVariable.reserve(advances);
421    for (Statement * stmt = entryBlock->front(); ; ) {
422        while ( stmt ) {
423            if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
424                scope.push(stmt->getNextNode());
425                const PabloBlock * const nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
426                stmt = nested->front();
427                assert (stmt);
428                continue;
429            } else if (LLVM_UNLIKELY(isa<Advance>(stmt))) {
430                int depth = 0;
431                mAdvance[k] = cast<Advance>(stmt);
432                advanceScope[k] = cast<Advance>(stmt)->getParent();
433                for (unsigned i = 0; i != k; ++i) {
434                    if (edge(i, k, mConstraintGraph).second || (advanceScope[i] != advanceScope[k])) {
435                        depth = std::max<int>(depth, mAdvanceRank[i]);
436                    }
437                }
438                mAdvanceRank[k++] = ++depth;
439                maxDepth = std::max(maxDepth, depth);
440            }
441            stmt = stmt->getNextNode();
442        }
443        if (scope.empty()) {
444            break;
445        }
446        stmt = scope.top();
447        scope.pop();
448    }
449    assert (k == advances);
450
451    LOG("Window Size / Max Depth: " << WindowSize << " of " << maxDepth);
452}
453
454/** ------------------------------------------------------------------------------------------------------------- *
455 * @brief characterize
456 * @param vars the input vars for this program
457 *
458 * Scan through the program and iteratively compute the BDDs for each statement.
459 ** ------------------------------------------------------------------------------------------------------------- */
460void MultiplexingPass::characterize(PabloBlock * const block) {
461    for (Statement * stmt : *block) {
462        if (LLVM_UNLIKELY(isa<If>(stmt))) {
463            characterize(cast<If>(stmt)->getBody());
464            for (const Assign * def : cast<If>(stmt)->getDefined()) {
465                if (LLVM_LIKELY(escapes(def))) {
466                    bdd_addref(get(def));
467                }
468            }
469        } else if (LLVM_UNLIKELY(isa<While>(stmt))) {
470            characterize(cast<While>(stmt)->getBody());
471            for (const Next * var : cast<While>(stmt)->getVariants()) {
472                if (LLVM_LIKELY(escapes(var))) {
473                    BDD & initial = get(var->getInitial());
474                    BDD & escaped = get(var);
475                    initial = bdd_addref(bdd_or(initial, escaped));
476                    escaped = initial;
477                }
478            }
479        } else {
480            mCharacterization.insert(std::make_pair(stmt, characterize(stmt)));
481        }
482    }
483}
484
485/** ------------------------------------------------------------------------------------------------------------- *
486 * @brief throwUnexpectedStatementTypeError
487 ** ------------------------------------------------------------------------------------------------------------- */
488static void throwUnexpectedStatementTypeError(const Statement * const stmt) {
489    std::string tmp;
490    raw_string_ostream err(tmp);
491    err << "Unexpected statement type ";
492    PabloPrinter::print(stmt, err);
493    throw std::runtime_error(err.str());
494}
495
496/** ------------------------------------------------------------------------------------------------------------- *
497 * @brief characterize
498 ** ------------------------------------------------------------------------------------------------------------- */
499inline BDD MultiplexingPass::characterize(Statement * const stmt) {
500    assert (stmt->getNumOperands() > 0);
501    BDD bdd = get(stmt->getOperand(0));
502    switch (stmt->getClassTypeId()) {
503        case TypeId::Assign:
504        case TypeId::Next:
505            break;
506        case TypeId::And:
507            for (unsigned i = 1; i != stmt->getNumOperands(); ++i) {
508                bdd = bdd_and(bdd, get(stmt->getOperand(i)));
509            }
510            break;
511        case TypeId::Or:
512            for (unsigned i = 1; i != stmt->getNumOperands(); ++i) {
513                bdd = bdd_or(bdd, get(stmt->getOperand(i)));
514            }
515            break;
516        case TypeId::Xor:
517            for (unsigned i = 1; i != stmt->getNumOperands(); ++i) {
518                bdd = bdd_xor(bdd, get(stmt->getOperand(i)));
519            }
520            break;
521        case TypeId::Not:
522            bdd = bdd_not(bdd);
523            break;
524        case TypeId::Sel:
525            bdd = bdd_ite(bdd, get(stmt->getOperand(1)), get(stmt->getOperand(2)));
526            break;
527        case TypeId::ScanThru:
528            // ScanThru(c, m) := (c + m) ∧ ¬m. Thus we can conservatively represent this statement using the BDD
529            // for ¬m --- provided no derivative of this statement is negated in any fashion.
530        case TypeId::MatchStar:
531        case TypeId::Call:
532            return bdd_ithvar(mVariables++);
533        case TypeId::Advance:
534            return characterize(cast<Advance>(stmt), bdd);
535        default:
536            throwUnexpectedStatementTypeError(stmt);
537    }
538    return bdd_addref(bdd);
539}
540
541/** ------------------------------------------------------------------------------------------------------------- *
542 * @brief characterize
543 ** ------------------------------------------------------------------------------------------------------------- */
544inline BDD MultiplexingPass::characterize(Advance * const adv, const BDD Ik) {
545    const auto k = mAdvanceNegatedVariable.size();
546    assert (mAdvance[k] == adv);
547    std::vector<bool> unconstrained(k , false);
548    for (unsigned i = 0; i != k; ++i) {
549
550        // Are we interested in testing these streams to see whether they are mutually exclusive?
551        if (exceedsWindowSize(i, k)) continue;
552
553        // Have we already proven that they are unconstrained by their subset relationship?
554        if (unconstrained[i]) continue;
555
556        // If these Advances are mutually exclusive, in the same scope, transitively independent, and shift their
557        // values by the same amount, we can safely multiplex them. Otherwise mark the constraint in the graph.
558        const Advance * const ithAdv = mAdvance[i];
559        if ((mTestConstrainedAdvances || independent(i, k)) && (ithAdv->getOperand(1) == adv->getOperand(1))) {
560            const BDD Ii = get(ithAdv->getOperand(0));
561            const BDD IiIk = bdd_addref(bdd_and(Ii, Ik));
562            // Is there any satisfying truth assignment? If not, these streams are mutually exclusive.
563            if (bdd_satone(IiIk) == bdd_zero()) {
564                // If Ai ∩ Ak = ∅ and Aj ⊂ Ai, Aj ∩ Ak = ∅.
565                for (auto e : make_iterator_range(in_edges(i, mSubsetGraph))) {
566                    const auto j = source(e, mSubsetGraph);
567                    if (mSubsetImplicationsAdhereToWindowingSizeConstraint && exceedsWindowSize(j, k)) {
568                        continue;
569                    }
570                    unconstrained[j] = true;
571                }
572                unconstrained[i] = true;
573            } else if (Ii == IiIk) {
574                // If Ii = Ii ∩ Ik then Ii ⊂ Ik. Record this in the subset graph with the arc (i, k).
575                // Note: the AST will be modified to make these mutually exclusive if Ai and Ak end up in
576                // the same multiplexing set.
577                add_edge(i, k, mSubsetGraph);
578                // If Ai ⊂ Ak and Aj ⊂ Ai, Aj ⊂ Ak.
579                for (auto e : make_iterator_range(in_edges(i, mSubsetGraph))) {
580                    const auto j = source(e, mSubsetGraph);
581                    add_edge(j, k, mSubsetGraph);
582                    if (mSubsetImplicationsAdhereToWindowingSizeConstraint && exceedsWindowSize(j, k)) {
583                        continue;
584                    }
585                    unconstrained[j] = true;
586                }
587                unconstrained[i] = true;
588            } else if (Ik == IiIk) {
589                // If Ik = Ii ∩ Ik then Ik ⊂ Ii. Record this in the subset graph with the arc (k, i).
590                add_edge(k, i, mSubsetGraph);
591                // If Ak ⊂ Ai and Ai ⊂ Aj, Ak ⊂ Aj.
592                for (auto e : make_iterator_range(out_edges(i, mSubsetGraph))) {
593                    const auto j = target(e, mSubsetGraph);
594                    add_edge(k, j, mSubsetGraph);
595                    if (mSubsetImplicationsAdhereToWindowingSizeConstraint && exceedsWindowSize(j, k)) {
596                        continue;
597                    }
598                    unconstrained[j] = true;
599                }
600                unconstrained[i] = true;
601            }
602            bdd_delref(IiIk);
603        }
604    }
605
606    BDD Ak = bdd_ithvar(mVariables++);
607    const BDD Nk = bdd_addref(bdd_not(Ak));
608    for (unsigned i = 0; i != k; ++i) {
609        if (unconstrained[i]) {
610            // This algorithm deems two streams mutually exclusive if and only if the conjuntion of their BDDs is a contradiction.
611            // To generate a contradiction when comparing Advances, the BDD of each Advance is represented by the conjunction of
612            // variables representing the k-th Advance and the negation of all variables for the Advances whose inputs are mutually
613            // exclusive with the k-th input.
614
615            // For example, if the input of the i-th Advance is mutually exclusive with the input of the j-th and k-th Advance, the
616            // BDD of the i-th Advance is Ai ∧ ¬Aj ∧ ¬Ak. Similarly, the j- and k-th Advance is Aj ∧ ¬Ai and Ak ∧ ¬Ai, respectively
617            // (assuming that the j-th and k-th Advance are not mutually exclusive.)
618
619            const BDD Ni = mAdvanceNegatedVariable[i];
620            BDD & Ai = get(mAdvance[i]);
621            Ai = bdd_addref(bdd_and(Ai, Nk));
622            Ak = bdd_addref(bdd_and(Ak, Ni));
623            if (independent(i, k) && (adv->getParent() == mAdvance[i]->getParent())) {
624                continue;
625            }
626        }
627        add_edge(i, k, mConstraintGraph);
628    }
629    // To minimize the number of BDD computations, we store the negated variable instead of negating it each time.
630    mAdvanceNegatedVariable.emplace_back(Nk);
631    return Ak;
632}
633
634/** ------------------------------------------------------------------------------------------------------------- *
635 * @brief independent
636 ** ------------------------------------------------------------------------------------------------------------- */
637inline bool MultiplexingPass::independent(const ConstraintVertex i, const ConstraintVertex j) const {
638    assert (i < num_vertices(mConstraintGraph) && j < num_vertices(mConstraintGraph));
639    return (mConstraintGraph.get_edge(i, j) == 0);
640}
641
642/** ------------------------------------------------------------------------------------------------------------- *
643 * @brief exceedsWindowSize
644 ** ------------------------------------------------------------------------------------------------------------- */
645inline bool MultiplexingPass::exceedsWindowSize(const ConstraintVertex i, const ConstraintVertex j) const {
646    assert (i < mAdvanceRank.size() && j < mAdvanceRank.size());
647    return (std::abs<int>(mAdvanceRank[i] - mAdvanceRank[j]) > WindowSize);
648}
649
650/** ------------------------------------------------------------------------------------------------------------- *
651 * @brief is_power_of_2
652 * @param n an integer
653 ** ------------------------------------------------------------------------------------------------------------- */
654static inline bool is_power_of_2(const size_t n) {
655    return ((n & (n - 1)) == 0);
656}
657
658/** ------------------------------------------------------------------------------------------------------------- *
659 * @brief generateUsageWeightingGraph
660 *
661 * Prior to generating our candidate sets, scan through the constraint graph and generate a clique in the usage
662 * weighting graph each set of constraint-free Advance nodes that have the same users. We may be able optimize
663 * the demultiplexing calculations using range expressions.
664 *
665 * Note: it'd be preferable to contract vertices in the constraint graph prior to scanning through it but that
666 * leaves us with a more difficult problem. Namely, Advance nodes may belong to more than one clique but it'd be
667 * useless to compute a value twice; furthermore, we want to avoid generating a multiplexing set whose size is 2^n
668 * for any n ∈ â„€* but don't want to needlessly limit the size of any clique. Look into this further later.
669 ** ------------------------------------------------------------------------------------------------------------- */
670void MultiplexingPass::generateUsageWeightingGraph() {
671    const auto n = num_vertices(mConstraintGraph); assert (n > 2);
672    // Let G be the complement of the constraint graph ∪ the subset graph restricted to only the edges corresponding
673    // to pairs of Advances with the same users.
674    CliqueGraph G(n);
675    for (unsigned i = 0; i != (n - 1); ++i) {
676        const Advance * const advI = mAdvance[i];
677        for (unsigned j = i + 1; j != n; ++j) {
678            const Advance * const advJ = mAdvance[j];
679            if (LLVM_UNLIKELY(advI->getNumUses() == advJ->getNumUses()) && independent(i, j)) {
680                if (LLVM_UNLIKELY(std::equal(advI->user_begin(), advI->user_end(), advJ->user_begin()))) {
681                    // INVESTIGATE: we should be able to ignore subset relations if these are going to become a
682                    // range expression. Look into making a proof for it once the range expression calculation
683                    // is finished.
684                    if (!(edge(i, j, mSubsetGraph).second || edge(j, i, mSubsetGraph).second)) {
685                        add_edge(i, j, G);
686                    }
687                }
688            }
689        }
690    }
691    if (num_edges(G) > 0) {
692        const CliqueSets S = findMaximalCliques(G);
693        for (unsigned i = 0; i != n; ++i) {
694            clear_vertex(i, G);
695        }
696        for (const std::vector<CliqueGraph::vertex_descriptor> & C : S) {
697            const unsigned m = C.size(); assert (m > 1);
698            for (unsigned i = 1; i != m; ++i) {
699                for (unsigned j = 0; j != i; ++j) {
700                    add_edge(C[j], C[i], G);
701                }
702            }
703        }
704    }
705    mUsageGraph = G;
706}
707
708/** ------------------------------------------------------------------------------------------------------------- *
709 * @brief generateCandidateSets
710 ** ------------------------------------------------------------------------------------------------------------- */
711bool MultiplexingPass::generateCandidateSets() {
712
713    Constraints S;
714
715    ConstraintGraph::degree_size_type D[num_vertices(mConstraintGraph)];
716
717    mCandidateGraph = CandidateGraph(num_vertices(mConstraintGraph));
718
719    for (unsigned iteration = 0; iteration < Samples; ++iteration) {
720
721        // Push all source nodes into the (initial) independent set S
722        for (const auto v : make_iterator_range(vertices(mConstraintGraph))) {
723            const auto d = in_degree(v, mConstraintGraph);
724            D[v] = d;
725            if (d == 0) {
726                S.push_back(v);
727            }
728        }
729
730        auto remaining = num_vertices(mConstraintGraph) - S.size();
731
732        for (;;) {
733            assert (S.size() > 0);
734            addCandidateSet(S);
735            if (LLVM_UNLIKELY(remaining == 0)) {
736                break;
737            }
738            for (;;) {
739                assert (S.size() > 0);
740                // Randomly choose a vertex in S and discard it.
741                const auto i = S.begin() + IntDistribution(0, S.size() - 1)(mRNG);
742                assert (i != S.end());
743                const auto u = *i;
744                S.erase(i);
745                bool checkCandidate = false;
746                for (auto e : make_iterator_range(out_edges(u, mConstraintGraph))) {
747                    const auto v = target(e, mConstraintGraph);
748                    assert ("Constraint set degree subtraction error!" && (D[v] != 0));
749                    if ((--D[v]) == 0) {
750                        assert ("Error v is already in S!" && std::count(S.begin(), S.end(), v) == 0);
751                        S.push_back(v);
752                        assert (remaining != 0);
753                        --remaining;
754                        if (LLVM_LIKELY(S.size() >= 3)) {
755                            checkCandidate = true;
756                        }
757                    }
758                }
759                if (checkCandidate || LLVM_UNLIKELY(remaining == 0)) {
760                    break;
761                }
762            }
763        }
764
765        S.clear();
766    }
767
768    return num_vertices(mCandidateGraph) > num_vertices(mConstraintGraph);
769}
770
771/** ------------------------------------------------------------------------------------------------------------- *
772 * @brief choose
773 *
774 * Compute n choose k
775 ** ------------------------------------------------------------------------------------------------------------- */
776__attribute__ ((const)) inline unsigned long choose(const unsigned n, const unsigned k) {
777    if (n < k)
778        return 0;
779    if (n == k || k == 0)
780        return 1;
781    unsigned long delta = k;
782    unsigned long max = n - k;
783    if (delta < max) {
784        std::swap(delta, max);
785    }
786    unsigned long result = delta + 1;
787    for (unsigned i = 2; i <= max; ++i) {
788        result = (result * (delta + i)) / i;
789    }
790    return result;
791}
792
793/** ------------------------------------------------------------------------------------------------------------- *
794 * @brief select
795 *
796 * James McCaffrey's algorithm for "Generating the mth Lexicographical Element of a Mathematical Combination"
797 ** ------------------------------------------------------------------------------------------------------------- */
798void MultiplexingPass::selectCandidateSet(const unsigned n, const unsigned k, const unsigned m, const Constraints & S, ConstraintVertex * const element) {
799    unsigned long a = n;
800    unsigned long b = k;
801    unsigned long x = (choose(n, k) - 1) - m;
802    for (unsigned i = 0; i != k; ++i) {
803        unsigned long y = 0;
804        while ((y = choose(--a, b)) > x);
805        x = x - y;
806        b = b - 1;
807        element[i] = S[(n - 1) - a];
808    }
809}
810
811/** ------------------------------------------------------------------------------------------------------------- *
812 * @brief updateCandidateSet
813 ** ------------------------------------------------------------------------------------------------------------- */
814void MultiplexingPass::updateCandidateSet(ConstraintVertex * const begin, ConstraintVertex * const end) {
815
816    using Vertex = CandidateGraph::vertex_descriptor;
817
818    const auto n = num_vertices(mConstraintGraph);
819    const auto m = num_vertices(mCandidateGraph);
820    const auto d = end - begin;
821
822    std::sort(begin, end);
823
824    Vertex u = 0;
825
826    for (Vertex i = n; i != m; ++i) {
827
828        if (LLVM_UNLIKELY(degree(i, mCandidateGraph) == 0)) {
829            u = i;
830            continue;
831        }
832
833        const auto adj = adjacent_vertices(i, mCandidateGraph);
834        if (degree(i, mCandidateGraph) < d) {
835            // set_i can only be a subset of the new set
836            if (LLVM_UNLIKELY(std::includes(begin, end, adj.first, adj.second))) {
837                clear_vertex(i, mCandidateGraph);
838                u = i;
839            }
840        } else if (LLVM_UNLIKELY(std::includes(adj.first, adj.second, begin, end))) {
841            // the new set is a subset of set_i; discard it.
842            return;
843        }
844
845    }
846
847    if (LLVM_LIKELY(u == 0)) { // n must be at least 3 so u is 0 if and only if we're not reusing a set vertex.
848        u = add_vertex(mCandidateGraph);
849    }
850
851    for (ConstraintVertex * i = begin; i != end; ++i) {
852        add_edge(u, *i, mCandidateGraph);
853    }
854
855}
856
857/** ------------------------------------------------------------------------------------------------------------- *
858 * @brief addCandidateSet
859 * @param S an independent set
860 ** ------------------------------------------------------------------------------------------------------------- */
861inline void MultiplexingPass::addCandidateSet(const Constraints & S) {
862    if (S.size() >= 3) {
863        const unsigned setLimit = SetLimit;
864        if (S.size() <= setLimit) {
865            ConstraintVertex E[S.size()];
866            std::copy(S.cbegin(), S.cend(), E);
867            updateCandidateSet(E, E + S.size());
868        } else {
869            assert (setLimit > 0);
870            ConstraintVertex E[setLimit];
871            const auto max = choose(S.size(), setLimit);
872            if (LLVM_UNLIKELY(max <= SelectionLimit)) {
873                for (unsigned i = 0; i != max; ++i) {
874                    selectCandidateSet(S.size(), setLimit, i, S, E);
875                    updateCandidateSet(E, E + setLimit);
876                }
877            } else { // take m random samples
878                for (unsigned i = 0; i != SelectionLimit; ++i) {
879                    selectCandidateSet(S.size(), setLimit, mRNG() % max, S, E);
880                    updateCandidateSet(E, E + setLimit);
881                }
882            }
883        }
884    }
885}
886
887/** ------------------------------------------------------------------------------------------------------------- *
888 * @brief log2_plus_one
889 ** ------------------------------------------------------------------------------------------------------------- */
890static inline size_t log2_plus_one(const size_t n) {
891    return std::log2<size_t>(n) + 1;
892}
893
894/** ------------------------------------------------------------------------------------------------------------- *
895 * @brief selectMultiplexSetsGreedy
896 *
897 * This algorithm is simply computes a greedy set cover. We want an exact max-weight set cover but can generate new
898 * sets by taking a subset of any existing set. With a few modifications, the greedy approach seems to work well
899 * enough but can be shown to produce a suboptimal solution if there are three candidate sets labelled A, B and C,
900 * in which A ∩ B = ∅, |A| ≀ |B| < |C|, and C ⊂ (A ∪ B).
901 ** ------------------------------------------------------------------------------------------------------------- */
902void MultiplexingPass::selectMultiplexSetsGreedy() {
903
904    using AdjIterator = graph_traits<CandidateGraph>::adjacency_iterator;
905    using degree_t = CandidateGraph::degree_size_type;
906    using vertex_t = CandidateGraph::vertex_descriptor;
907
908    const size_t m = num_vertices(mConstraintGraph);
909    const size_t n = num_vertices(mCandidateGraph) - m;
910
911    degree_t remaining[n];
912    vertex_t chosen_set[m];
913
914    for (unsigned i = 0; i != n; ++i) {
915        remaining[i] = degree(i + m, mCandidateGraph);
916    }
917    for (unsigned i = 0; i != m; ++i) {
918        chosen_set[i] = 0;
919    }
920
921    for (;;) {
922
923        // Choose the set with the greatest number of vertices not already included in some other set.
924        vertex_t k = 0;
925        degree_t w = 0;
926        for (vertex_t i = 0; i != n; ++i) {
927            degree_t r = remaining[i];
928            if (r > 2) { // if this set has at least 3 elements.
929                r *= r;
930                AdjIterator begin, end;
931                std::tie(begin, end) = adjacent_vertices(i + m, mCandidateGraph);
932                for (auto ei = begin; ei != end; ++ei) {
933                    for (auto ej = ei; ++ej != end; ) {
934                        if (edge(*ei, *ej, mUsageGraph).second) {
935                            ++r;
936                        }
937                    }
938                }
939                if (w < r) {
940                    k = i;
941                    w = r;
942                }
943            }
944        }
945
946        // Multiplexing requires 3 or more elements; if no set contains at least 3, abort.
947        if (w == 0) {
948            break;
949        }
950
951        for (const auto u : make_iterator_range(adjacent_vertices(k + m, mCandidateGraph))) {
952            if (chosen_set[u] == 0) {
953                chosen_set[u] = (k + m);
954                for (const auto v : make_iterator_range(adjacent_vertices(u, mCandidateGraph))) {
955                    assert (v >= m);
956                    remaining[v - m]--;
957                }
958            }
959        }
960
961        assert (remaining[k] == 0);
962
963        // If this contains 2^n elements for any n, discard the member that is most likely to be added
964        // to some future set.
965        if (LLVM_UNLIKELY(is_power_of_2(w))) {
966            vertex_t j = 0;
967            degree_t w = 0;
968            for (vertex_t i = 0; i != m; ++i) {
969                if (chosen_set[i] == (k + m)) {
970                    degree_t r = 1;
971                    for (const auto u : make_iterator_range(adjacent_vertices(i, mCandidateGraph))) {
972                        // strongly prefer adding weight to unvisited sets that have more remaining vertices
973                        r += std::pow(remaining[u - m], 2);
974                    }
975                    if (w < r) {
976                        j = i;
977                        w = r;
978                    }
979                }
980            }
981            assert (w > 0);
982            chosen_set[j] = 0;
983            for (const auto u : make_iterator_range(adjacent_vertices(j, mCandidateGraph))) {
984                assert (u >= m);
985                remaining[u - m]++;
986            }
987        }
988
989        // If Samples > 1 then our candidate sets were generated by more than one traversal through the constraint graph.
990        // Sets generated by differing traversals may generate a cycle in the AST if multiplex even when they are not
991        // multiplexed together. For example,
992
993        // Assume we're multiplexing set {A,B,C} and {D,E,F} and that no constraint exists between any nodes in
994        // either set. If A is dependent on D and E is dependent on B, multiplexing both sets would result in a cycle
995        // in the AST. To fix this, we'd have to remove A, D, B or E.
996
997        // This cannot occur with only one traversal (or between sets generated by the same traversal) because of the
998        // DAG traversal strategy used in "generateCandidateSets".
999
1000
1001    }
1002
1003    for (unsigned i = 0; i != m; ++i) {
1004        AdjIterator ei, ei_end;
1005        std::tie(ei, ei_end) = adjacent_vertices(i, mCandidateGraph);
1006        for (auto next = ei; ei != ei_end; ei = next) {
1007            ++next;
1008            if (*ei != chosen_set[i]) {
1009                remove_edge(i, *ei, mCandidateGraph);
1010            }
1011        }
1012    }
1013
1014    #ifndef NDEBUG
1015    for (unsigned i = 0; i != m; ++i) {
1016        assert (degree(i, mCandidateGraph) <= 1);
1017    }
1018    for (unsigned i = m; i != (m + n); ++i) {
1019        assert (degree(i, mCandidateGraph) == 0 || degree(i, mCandidateGraph) >= 3);
1020    }
1021    #endif
1022}
1023
1024/** ------------------------------------------------------------------------------------------------------------- *
1025 * @brief selectMultiplexSetsWorkingSet
1026 ** ------------------------------------------------------------------------------------------------------------- */
1027void MultiplexingPass::selectMultiplexSetsWorkingSet() {
1028
1029    // The inputs to each Advance must be different; otherwise the SimplificationPass would consider all but
1030    // one of the Advances redundant. However, if the input is short lived, we can ignore it in favour of its
1031    // operands, which *may* be shared amongst more than one of the Advances (or may be short lived themselves,
1032    // in which we can consider their operands instead.) Ideally, if we can keep the set of live values small,
1033    // we may be able to reduce register pressure.
1034
1035//    using Graph = adjacency_list<hash_setS, vecS, bidirectionalS, Statement *, unsigned>;
1036//    using Map = flat_map<const Statement *, typename Graph::vertex_descriptor>;
1037
1038//    const size_t m = num_vertices(mConstraintGraph);
1039//    const size_t n = num_vertices(mMultiplexSetGraph) - m;
1040
1041//    for (unsigned i = 0; i != n; ++i) {
1042
1043//        Map M;
1044//        Graph G = construct<Graph>(block, M);
1045
1046
1047
1048
1049
1050
1051
1052//    }
1053
1054
1055
1056
1057
1058
1059}
1060
1061/** ------------------------------------------------------------------------------------------------------------- *
1062 * @brief eliminateSubsetConstraints
1063 ** ------------------------------------------------------------------------------------------------------------- */
1064void MultiplexingPass::eliminateSubsetConstraints() {
1065    using SubsetEdgeIterator = graph_traits<SubsetGraph>::edge_iterator;
1066    // If Ai ⊂ Aj then the subset graph will contain the arc (i, j). Remove all arcs corresponding to vertices
1067    // that are not elements of the same multiplexing set.
1068    SubsetEdgeIterator ei, ei_end, ei_next;
1069    std::tie(ei, ei_end) = edges(mSubsetGraph);
1070    for (ei_next = ei; ei != ei_end; ei = ei_next) {
1071        ++ei_next;
1072        const auto u = source(*ei, mSubsetGraph);
1073        const auto v = target(*ei, mSubsetGraph);
1074        if (degree(u, mCandidateGraph) != 0 && degree(v, mCandidateGraph) != 0) {
1075            assert (degree(u, mCandidateGraph) == 1);
1076            assert (degree(v, mCandidateGraph) == 1);
1077            const auto su = *(adjacent_vertices(u, mCandidateGraph).first);
1078            const auto sv = *(adjacent_vertices(v, mCandidateGraph).first);
1079            if (su == sv) {
1080                continue;
1081            }
1082        }
1083        remove_edge(*ei, mSubsetGraph);
1084    }
1085
1086    if (num_edges(mSubsetGraph) != 0) {
1087
1088        // At least one subset constraint exists; perform a transitive reduction on the graph to ensure that
1089        // we perform the minimum number of AST modifications for the selected multiplexing sets.
1090
1091        doTransitiveReductionOfSubsetGraph();
1092
1093        // Afterwards modify the AST to ensure that multiplexing algorithm can ignore any subset constraints
1094        for (auto e : make_iterator_range(edges(mSubsetGraph))) {
1095            Advance * const adv1 = mAdvance[source(e, mSubsetGraph)];
1096            Advance * const adv2 = mAdvance[target(e, mSubsetGraph)];
1097            assert (adv1->getParent() == adv2->getParent());
1098            PabloBlock * const pb = adv1->getParent();
1099            pb->setInsertPoint(adv2->getPrevNode());
1100            adv2->setOperand(0, pb->createAnd(adv2->getOperand(0), pb->createNot(adv1->getOperand(0)), "subset"));
1101            pb->setInsertPoint(adv2);
1102            adv2->replaceAllUsesWith(pb->createOr(adv1, adv2, "merge"));
1103        }
1104
1105    }
1106}
1107
1108/** ------------------------------------------------------------------------------------------------------------- *
1109 * @brief multiplexSelectedSets
1110 ** ------------------------------------------------------------------------------------------------------------- */
1111void MultiplexingPass::multiplexSelectedSets(PabloFunction & function) {
1112    flat_set<PabloBlock *> modified;
1113    const auto first_set = num_vertices(mConstraintGraph);
1114    const auto last_set = num_vertices(mCandidateGraph);
1115    for (auto idx = first_set; idx != last_set; ++idx) {
1116        const size_t n = degree(idx, mCandidateGraph);
1117        assert (n == 0 || n > 2);
1118        if (n) {
1119            const size_t m = log2_plus_one(n);
1120            Advance * input[n];
1121            PabloAST * muxed[m];
1122            PabloAST * muxed_n[m];
1123            // The multiplex set graph is a DAG with edges denoting the set relationships of our independent sets.
1124            unsigned i = 0;
1125            for (const auto u : orderMultiplexSet(idx)) {
1126                input[i++] = mAdvance[u];
1127            }
1128            Advance * const adv = input[0];
1129            PabloBlock * const block = adv->getParent(); assert (block);
1130            modified.insert(block);
1131
1132            circular_buffer<PabloAST *> Q(n);
1133
1134            PabloBuilder builder(block);
1135            block->setInsertPoint(nullptr);
1136            /// Perform n-to-m Multiplexing           
1137            for (size_t j = 0; j != m; ++j) {               
1138                std::ostringstream prefix;
1139                prefix << "mux" << n << "to" << m << '.' << (j);
1140                assert (Q.empty());
1141                for (size_t i = 0; i != n; ++i) {
1142                    if (((i + 1) & (1UL << j)) != 0) {
1143                        Q.push_back(input[i]->getOperand(0));
1144                    }
1145                }
1146                while (Q.size() > 1) {
1147                    PabloAST * a = Q.front(); Q.pop_front();
1148                    PabloAST * b = Q.front(); Q.pop_front();
1149                    Q.push_back(builder.createOr(a, b));
1150                }
1151                PabloAST * const muxing =  Q.front(); Q.clear();
1152                muxed[j] = builder.createAdvance(muxing, adv->getOperand(1), prefix.str());
1153                muxed_n[j] = builder.createNot(muxed[j]);
1154            }
1155            /// Perform m-to-n Demultiplexing
1156            block->setInsertPoint(block->back());
1157            for (size_t i = 0; i != n; ++i) {
1158                // Construct the demuxed values and replaces all the users of the original advances with them.
1159                assert (Q.empty());
1160                for (size_t j = 0; j != m; ++j) {
1161                    Q.push_back((((i + 1) & (1UL << j)) != 0) ? muxed[j] : muxed_n[j]);
1162                }
1163                while (Q.size() > 1) {
1164                    PabloAST * const a = Q.front(); Q.pop_front();
1165                    PabloAST * const b = Q.front(); Q.pop_front();
1166                    Q.push_back(builder.createAnd(a, b));
1167                }
1168                PabloAST * const demuxed =  Q.front(); Q.clear();
1169                input[i]->replaceWith(demuxed, true, true);
1170            }
1171        }
1172    }
1173    for (PabloBlock * block : modified) {
1174        rewriteAST(block);
1175    }
1176}
1177
1178/** ------------------------------------------------------------------------------------------------------------- *
1179 * @brief orderMultiplexSet
1180 ** ------------------------------------------------------------------------------------------------------------- */
1181inline MultiplexingPass::Candidates MultiplexingPass::orderMultiplexSet(const CandidateGraph::vertex_descriptor u) {
1182    Candidates set;
1183    set.reserve(degree(u, mCandidateGraph));
1184    for (const auto e : make_iterator_range(adjacent_vertices(u, mCandidateGraph))) {
1185        set.push_back(e);
1186    }
1187    std::sort(set.begin(), set.end());
1188    Candidates clique;
1189    Candidates result;
1190    result.reserve(degree(u, mCandidateGraph));
1191    while (set.size() > 0) {
1192        const auto v = *set.begin();
1193        clique.push_back(v);
1194        set.erase(set.begin());
1195        for (const auto w : make_iterator_range(adjacent_vertices(v, mUsageGraph))) {
1196            auto f = std::lower_bound(set.begin(), set.end(), w);
1197            // Is w in our multiplexing set?
1198            if (f == set.end() || *f != w) {
1199                continue;
1200            }
1201            // Is our subgraph still a clique after adding w to it?
1202            bool valid = true;
1203            for (const auto y : clique) {
1204                if (!edge(w, y, mUsageGraph).second) {
1205                    valid = false;
1206                    break;
1207                }
1208            }
1209            if (valid) {
1210                clique.push_back(w);
1211                set.erase(f);
1212            }
1213        }
1214        result.insert(result.end(), clique.begin(), clique.end());
1215        clique.clear();
1216    }
1217    return result;
1218}
1219
1220
1221
1222
1223/** ------------------------------------------------------------------------------------------------------------- *
1224 * @brief rewriteAST
1225 *
1226 * Multiplexing ignores def-use ordering when muxing and demuxing the Advances; this will likely lead to an illegal
1227 * ordering but, by virtue of the multiplexing algorithm, some ordering of the IR must be legal. However, an
1228 * arbritary topological ordering will likely lead to poor performance due to excessive register spills; this
1229 * algorithm attempts to mitigate this by using a simple bottom-up ordering scheme.
1230 ** ------------------------------------------------------------------------------------------------------------- */
1231void MultiplexingPass::rewriteAST(PabloBlock * const block) {
1232
1233    using Graph = adjacency_list<hash_setS, vecS, bidirectionalS, Statement *>;
1234    using Vertex = Graph::vertex_descriptor;
1235    using ReadySet = std::vector<Vertex>;
1236    using TypeId = PabloAST::ClassTypeId;
1237
1238    Graph G = construct<Graph>(block);
1239
1240
1241    std::vector<unsigned> rank(num_vertices(G), 0);
1242
1243    {
1244        circular_buffer<Vertex> Q(num_vertices(G));
1245        // Compute the rank of each statement
1246        for (const Vertex u : make_iterator_range(vertices(G))) {
1247            if (out_degree(u, G) == 0 && rank[u] == 0) {
1248                Q.push_back(u);
1249            }
1250        }
1251
1252        while (Q.size() > 0) {
1253
1254            const Vertex u = Q.front();
1255            Q.pop_front();
1256
1257            assert (rank[u] == 0);
1258
1259            unsigned work = 0;
1260            switch (G[u]->getClassTypeId()) {
1261                case TypeId::And:
1262                case TypeId::Or:
1263                case TypeId::Xor:
1264                    work = 2;
1265                    break;
1266//                case TypeId::Not:
1267                case TypeId::Assign:
1268                case TypeId::Next:
1269                    work = 1;
1270                    break;
1271                case TypeId::Sel:
1272                    work = 6;
1273                    break;
1274                case TypeId::Advance:
1275                case TypeId::ScanThru:
1276                    work = 33;
1277                    break;
1278                case TypeId::MatchStar:
1279                    work = 51;
1280                    break;
1281                case TypeId::If:
1282                case TypeId::While:
1283                case TypeId::Call:
1284                    work = 10000; // <-- try to push If, While and Call nodes as high as possible
1285                    break;
1286                default: break;
1287            }
1288
1289            unsigned r = 0;
1290            for (const auto e : make_iterator_range(out_edges(u, G))) {
1291                r = std::max(r, rank[target(e, G)]);
1292            }
1293
1294            rank[u] = work + r;
1295
1296            for (const auto ei : make_iterator_range(in_edges(u, G))) {
1297                const auto v = source(ei, G);
1298                assert (rank[v] == 0);
1299                bool ready = true;
1300                for (const auto ej : make_iterator_range(out_edges(v, G))) {
1301                    if (rank[target(ej, G)] == 0) {
1302                        ready = false;
1303                        break;
1304                    }
1305                }
1306                if (ready) {
1307                    Q.push_back(v);
1308                }
1309            }
1310
1311        }
1312    }
1313
1314    // Compute the initial ready set
1315    ReadySet readySet;
1316    for (const Vertex u : make_iterator_range(vertices(G))) {
1317        if (in_degree(u, G) == 0) {
1318            readySet.emplace_back(u);
1319        }
1320    }
1321
1322    auto by_nonincreasing_rank = [&rank](const Vertex u, const Vertex v) -> bool {
1323        return rank[u] > rank[v];
1324    };
1325
1326    std::sort(readySet.begin(), readySet.end(), by_nonincreasing_rank);
1327
1328    block->setInsertPoint(nullptr);
1329    // Rewrite the AST using the bottom-up ordering
1330    while (readySet.size() > 0) {
1331        // Scan through the ready set to determine which one 'kills' the greatest number of inputs
1332        double best = 0.0;
1333        auto rk = readySet.begin();
1334        for (auto ri = readySet.begin(); ri != readySet.end(); ++ri) {
1335            double p = 0.0;
1336            assert (rank[*ri] != 0);
1337            for (auto ei : make_iterator_range(in_edges(*ri, G))) {
1338                const auto v = source(ei, G);
1339                unsigned unscheduled = 0;
1340                for (auto ej : make_iterator_range(out_edges(v, G))) {
1341                    if (rank[target(ej, G)] != 0) { // if this edge leads to an unscheduled statement
1342                        ++unscheduled;
1343                    }
1344                }
1345                assert (unscheduled > 0);
1346                assert (unscheduled <= out_degree(v, G));
1347                const double uses = out_degree(v, G);
1348                p += std::pow((uses - (double)(unscheduled - 1)) / uses, 2);
1349            }
1350            if (p > best) {
1351                rk = ri;
1352                best = p;
1353            }
1354        }
1355        const auto u = *rk;
1356        readySet.erase(rk);
1357        // Write the statement back to the AST ...
1358        block->insert(G[u]);
1359        // ... and mark it as written
1360        rank[u] = 0;
1361        // Now check whether any new statements are ready
1362        for (auto ei : make_iterator_range(out_edges(u, G))) {
1363            bool ready = true;
1364            const auto v = target(ei, G);
1365            for (auto ej : make_iterator_range(in_edges(v, G))) {
1366                if (rank[source(ej, G)] != 0) {
1367                    ready = false;
1368                    break;
1369                }
1370            }
1371            if (ready) {
1372                assert (rank[v] != 0);
1373                readySet.insert(std::lower_bound(readySet.begin(), readySet.end(), v, by_nonincreasing_rank), v);
1374                assert (std::is_sorted(readySet.cbegin(), readySet.cend(), by_nonincreasing_rank));
1375            }
1376        }
1377    }
1378
1379}
1380
1381/** ------------------------------------------------------------------------------------------------------------- *
1382 * @brief doTransitiveReductionOfSubsetGraph
1383 ** ------------------------------------------------------------------------------------------------------------- */
1384void MultiplexingPass::doTransitiveReductionOfSubsetGraph() {
1385    std::vector<SubsetGraph::vertex_descriptor> Q;
1386    for (auto u : make_iterator_range(vertices(mSubsetGraph))) {
1387        if (in_degree(u, mSubsetGraph) == 0 && out_degree(u, mSubsetGraph) != 0) {
1388            Q.push_back(u);
1389        }
1390    }
1391    flat_set<SubsetGraph::vertex_descriptor> targets;
1392    flat_set<SubsetGraph::vertex_descriptor> visited;
1393    do {
1394        const auto u = Q.back(); Q.pop_back();
1395        for (auto ei : make_iterator_range(out_edges(u, mSubsetGraph))) {
1396            for (auto ej : make_iterator_range(out_edges(target(ei, mSubsetGraph), mSubsetGraph))) {
1397                targets.insert(target(ej, mSubsetGraph));
1398            }
1399        }
1400        for (auto v : targets) {
1401            remove_edge(u, v, mSubsetGraph);
1402        }
1403        for (auto e : make_iterator_range(out_edges(u, mSubsetGraph))) {
1404            const auto v = target(e, mSubsetGraph);
1405            if (visited.insert(v).second) {
1406                Q.push_back(v);
1407            }
1408        }
1409    } while (Q.size() > 0);
1410}
1411
1412
1413/** ------------------------------------------------------------------------------------------------------------- *
1414 * @brief findMaximalCliques
1415 *
1416 * Adaptation of the Bron-Kerbosch algorithm.
1417 ** ------------------------------------------------------------------------------------------------------------- */
1418inline MultiplexingPass::CliqueSets MultiplexingPass::findMaximalCliques(const CliqueGraph & G) {
1419    CliqueSets S;
1420    const auto n = num_vertices(G);
1421    std::vector<CliqueGraph::vertex_descriptor> ordering;
1422    ordering.reserve(n);
1423    for (auto u : make_iterator_range(vertices(G))) {
1424        if (degree(u, G)) {
1425            ordering.push_back(u);
1426        }
1427    }
1428    CliqueSet R;
1429    CliqueSet P(ordering.begin(), ordering.end());   
1430    CliqueSet X;
1431    X.reserve(ordering.size());
1432    // compute a degeneracy ordering of G
1433    std::sort(ordering.begin(), ordering.end(), [&G](const CliqueGraph::vertex_descriptor i, const CliqueGraph::vertex_descriptor j){ return degree(i, G) < degree(j, G); });
1434    for (auto v : ordering) {
1435        R.insert(v);
1436        CliqueSet PN, XN;
1437        for (const auto u : make_iterator_range(adjacent_vertices(v, G))) {
1438            if (P.count(u)) PN.insert(u);
1439            if (X.count(u)) XN.insert(u);
1440        }
1441        findMaximalCliques(G, R, std::move(PN), std::move(XN), S); // ({v}, P ∩ N(v), X ∩ N(v))
1442        R.clear();
1443        P.erase(v);
1444        X.insert(v);
1445    }
1446    return S;
1447}
1448
1449/** ------------------------------------------------------------------------------------------------------------- *
1450 * @brief findMaximalCliques
1451 ** ------------------------------------------------------------------------------------------------------------- */
1452void MultiplexingPass::findMaximalCliques(const CliqueGraph & G, CliqueSet & R, CliqueSet && P, CliqueSet && X, CliqueSets & S) {
1453    if (LLVM_UNLIKELY(P.empty() && X.empty())) { // Report R as a maximal clique
1454        S.emplace(R.begin(), R.end());
1455    } else {
1456        // choose the pivot vertex u in P ∪ X as the vertex with the highest number of neighbors in P (Tomita et al. 2006.)
1457        CliqueSet N;
1458        CliqueGraph::degree_size_type size = 0;
1459        for (const CliqueGraph::vertex_descriptor u : P) {
1460            if (degree(u, G) >= size) {
1461                CliqueGraph::degree_size_type neighbours = 0;
1462                for (const CliqueGraph::vertex_descriptor v : make_iterator_range(adjacent_vertices(u, G))) {
1463                    neighbours += P.count(v);
1464                }
1465                if (size <= neighbours) {
1466                    if (size < neighbours) {
1467                        size = neighbours;
1468                        N.clear();
1469                    }
1470                    N.insert(u);
1471                }
1472            }
1473        }
1474        for (const CliqueGraph::vertex_descriptor u : X) {
1475            if (degree(u, G) >= size) {
1476                CliqueGraph::degree_size_type neighbours = 0;
1477                for (const CliqueGraph::vertex_descriptor v : make_iterator_range(adjacent_vertices(u, G))) {
1478                    neighbours += P.count(v);
1479                }
1480                if (size <= neighbours) {
1481                    if (size < neighbours) {
1482                        size = neighbours;
1483                        N.clear();
1484                    }
1485                    N.insert(u);
1486                }
1487            }
1488        }
1489        const CliqueGraph::vertex_descriptor u = *(N.nth(IntDistribution(0, N.size() - 1)(mRNG)));
1490        // for each vertex v in P \ N(u):
1491        for (auto v = P.begin(); v != P.end(); v = P.erase(v)) {
1492            if (edge(u, *v, G).second) continue;
1493            const bool added = R.insert(*v).second;
1494            CliqueSet PN, XN;
1495            for (const CliqueGraph::vertex_descriptor u : make_iterator_range(adjacent_vertices(*v, G))) {
1496                if (P.count(u)) PN.insert(u);
1497                if (X.count(u)) XN.insert(u);
1498            }
1499            findMaximalCliques(G, R, std::move(PN), std::move(XN), S); // (R ∪ {v}, P ∩ N(v), X ∩ N(v))
1500            if (LLVM_LIKELY(added)) R.erase(*v);
1501            X.insert(*v);
1502        }
1503    }
1504}
1505
1506/** ------------------------------------------------------------------------------------------------------------- *
1507 * @brief get
1508 ** ------------------------------------------------------------------------------------------------------------- */
1509inline BDD & MultiplexingPass::get(const PabloAST * const expr) {
1510    assert (expr);
1511    auto f = mCharacterization.find(expr);
1512    assert (f != mCharacterization.end());
1513    return f->second;
1514}
1515
1516/** ------------------------------------------------------------------------------------------------------------- *
1517 * @brief computeDAG
1518 ** ------------------------------------------------------------------------------------------------------------- */
1519template<typename Graph, typename Map>
1520Graph construct(PabloBlock * const block, Map & M) {
1521
1522    using Vertex = typename Graph::vertex_descriptor;
1523
1524    const auto size = std::distance(block->begin(), block->end());
1525
1526    Graph G(size);
1527    M.reserve(size);
1528
1529    Vertex u = 0;
1530    for (Statement * stmt : *block ) {
1531        G[u] = stmt;
1532        M.emplace(stmt, u);
1533        if (LLVM_UNLIKELY(isa<If>(stmt))) {
1534            for (Assign * def : cast<If>(stmt)->getDefined()) {
1535                M.emplace(def, u);
1536            }
1537        } else if (LLVM_UNLIKELY(isa<While>(stmt))) {
1538            for (Next * var : cast<While>(stmt)->getVariants()) {
1539                M.emplace(var, u);
1540            }
1541        }
1542        ++u;
1543    }
1544
1545    /// The following is a lamda function that adds any users of "stmt" to the graph after resolving
1546    /// which vertex it maps to w.r.t. the current block.
1547    auto addUsers = [&](const Vertex u, const Statement * const stmt) -> void {
1548        for (const PabloAST * user : stmt->users()) {
1549            if (LLVM_LIKELY(isa<Statement>(user))) {
1550                const Statement * use = cast<Statement>(user);
1551                auto f = M.find(use);
1552                if (LLVM_UNLIKELY(f == M.end())) {
1553                    const PabloBlock * parent = use->getParent();
1554                    for (;;) {
1555                        if (parent == block) {
1556                            break;
1557                        }
1558                        use = parent->getBranch();
1559                        parent = parent->getParent();
1560                        if (parent == nullptr) {
1561                            return;
1562                        }
1563                    }
1564                    f = M.find(use);
1565                    assert (f != M.end());
1566                    M.emplace(use, f->second);
1567                }
1568                const auto v = f->second;
1569                if (LLVM_UNLIKELY(u != v)) {
1570                    add_edge(u, v, G);
1571                }
1572            }
1573        }
1574    };
1575
1576    u = 0;
1577    for (Statement * stmt : *block ) {
1578
1579        for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
1580            PabloAST * const op = stmt->getOperand(i);
1581            if (isa<Statement>(op)) {
1582                auto f = M.find(cast<Statement>(op));
1583                if (f != M.end()) {
1584                    add_edge(f->second, u, G);
1585                }
1586            }
1587        }
1588
1589        if (LLVM_UNLIKELY(isa<If>(stmt))) {
1590            for (Assign * def : cast<If>(stmt)->getDefined()) {
1591                addUsers(u, def);
1592            }
1593        } else if (LLVM_UNLIKELY(isa<While>(stmt))) {
1594            for (Next * var : cast<While>(stmt)->getVariants()) {
1595                addUsers(u, var);
1596            }
1597        } else {
1598            addUsers(u, stmt);
1599        }
1600
1601        ++u;
1602    }
1603
1604    #ifndef NDEBUG
1605    std::vector<typename Graph::vertex_descriptor> nothing;
1606    topological_sort(G, std::back_inserter(nothing));
1607    #endif
1608
1609    return G;
1610}
1611
1612
1613/** ------------------------------------------------------------------------------------------------------------- *
1614 * @brief computeDAG
1615 ** ------------------------------------------------------------------------------------------------------------- */
1616template<typename Graph>
1617Graph construct(PabloBlock * const block) {
1618    using Map = flat_map<const Statement *, typename Graph::vertex_descriptor>;
1619    Map M;
1620    return construct<Graph, Map>(block, M);
1621}
1622
1623} // end of namespace pablo
Note: See TracBrowser for help on using the repository browser.