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

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

Work on coalescing algorithm + minor changes.

File size: 51.6 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
17/// TODO: Investigate why ./icgrep -c -multiplexing-window-size=13,14...,20 "^\p{l}$" causes segfault in BuDDy.
18
19using namespace llvm;
20using namespace boost;
21using namespace boost::container;
22using namespace boost::numeric::ublas;
23
24#define PRINT_DEBUG_OUTPUT
25
26#if !defined(NDEBUG) && !defined(PRINT_DEBUG_OUTPUT)
27#define PRINT_DEBUG_OUTPUT
28#endif
29
30#ifdef PRINT_DEBUG_OUTPUT
31
32#include <iostream>
33
34using namespace pablo;
35typedef uint64_t timestamp_t;
36
37static inline timestamp_t read_cycle_counter() {
38#ifdef __GNUC__
39timestamp_t ts;
40#ifdef __x86_64__
41  unsigned int eax, edx;
42  asm volatile("rdtsc" : "=a" (eax), "=d" (edx));
43  ts = ((timestamp_t) eax) | (((timestamp_t) edx) << 32);
44#else
45  asm volatile("rdtsc\n" : "=A" (ts));
46#endif
47  return(ts);
48#endif
49#ifdef _MSC_VER
50  return __rdtsc();
51#endif
52}
53
54#define LOG(x) std::cerr << x << std::endl;
55#define RECORD_TIMESTAMP(Name) const timestamp_t Name = read_cycle_counter()
56#define LOG_GRAPH(Name, G) \
57    LOG(Name << " |V|=" << num_vertices(G) << ", |E|="  << num_edges(G) << \
58                " (" << (((double)num_edges(G)) / ((double)(num_vertices(G) * (num_vertices(G) - 1) / 2))) << ')')
59
60unsigned __count_advances(const PabloBlock * const entry) {
61
62    std::stack<const Statement *> scope;
63    unsigned advances = 0;
64
65    // Scan through and collect all the advances, calls, scanthrus and matchstars ...
66    for (const Statement * stmt = entry->front(); ; ) {
67        while ( stmt ) {
68            if (isa<Advance>(stmt)) {
69                ++advances;
70            }
71            else if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
72                // Set the next statement to be the first statement of the inner scope and push the
73                // next statement of the current statement into the scope stack.
74                const PabloBlock * const nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
75                scope.push(stmt->getNextNode());
76                stmt = nested->front();
77                assert (stmt);
78                continue;
79            }
80            stmt = stmt->getNextNode();
81        }
82        if (scope.empty()) {
83            break;
84        }
85        stmt = scope.top();
86        scope.pop();
87    }
88    return advances;
89}
90
91#define LOG_NUMBER_OF_ADVANCES(entry) LOG("|Advances|=" << __count_advances(entry))
92
93#else
94#define LOG(x)
95#define RECORD_TIMESTAMP(Name)
96#define LOG_GRAPH(Name, G)
97#define LOG_NUMBER_OF_ADVANCES(entry)
98#endif
99
100
101namespace pablo {
102
103using TypeId = PabloAST::ClassTypeId;
104
105bool MultiplexingPass::optimize(PabloFunction & function, const unsigned limit, const unsigned maxSelections, const unsigned windowSize, const bool independent) {
106
107//    std::random_device rd;
108//    const auto seed = rd();
109    const auto seed = 83234827342;
110
111    LOG("Seed:                    " << seed);
112
113    MultiplexingPass mp(seed, limit, maxSelections, windowSize);
114    RECORD_TIMESTAMP(start_initialize);
115    const unsigned advances = mp.initialize(function, independent);
116    RECORD_TIMESTAMP(end_initialize);
117
118    LOG("Initialize:              " << (end_initialize - start_initialize));
119
120    LOG_NUMBER_OF_ADVANCES(function.getEntryBlock());
121
122    if (advances == 0) {
123        return false;
124    }
125
126    RECORD_TIMESTAMP(start_characterize);
127    mp.characterize(function.getEntryBlock());
128    RECORD_TIMESTAMP(end_characterize);
129
130    LOG("Characterize:             " << (end_characterize - start_characterize));
131
132    LOG("Nodes in BDD:             " << bdd_getnodenum() << " of " << bdd_getallocnum());
133
134    RECORD_TIMESTAMP(start_shutdown);
135    bdd_done();
136    RECORD_TIMESTAMP(end_shutdown);
137    LOG("Shutdown:                 " << (end_shutdown - start_shutdown));
138
139    RECORD_TIMESTAMP(start_create_multiplex_graph);
140    const bool multiplex = mp.generateCandidateSets();
141    RECORD_TIMESTAMP(end_create_multiplex_graph);
142    LOG("GenerateCandidateSets:    " << (end_create_multiplex_graph - start_create_multiplex_graph));
143
144    if (multiplex) {
145
146        RECORD_TIMESTAMP(start_usage_weighting);
147        mp.generateUsageWeightingGraph();
148        RECORD_TIMESTAMP(end_usage_weighting);
149        LOG("GenerateUsageWeighting:   " << (end_usage_weighting - start_usage_weighting));
150
151        RECORD_TIMESTAMP(start_select_multiplex_sets);
152        mp.selectMultiplexSets();
153        RECORD_TIMESTAMP(end_select_multiplex_sets);
154        LOG("SelectMultiplexSets:      " << (end_select_multiplex_sets - start_select_multiplex_sets));
155
156        RECORD_TIMESTAMP(start_subset_constraints);
157        mp.eliminateSubsetConstraints();
158        RECORD_TIMESTAMP(end_subset_constraints);
159        LOG("ApplySubsetConstraints:   " << (end_subset_constraints - start_subset_constraints));
160
161        RECORD_TIMESTAMP(start_select_independent_sets);
162        mp.multiplexSelectedSets(function);
163        RECORD_TIMESTAMP(end_select_independent_sets);
164        LOG("SelectedIndependentSets:  " << (end_select_independent_sets - start_select_independent_sets));
165
166        RECORD_TIMESTAMP(start_topological_sort);
167        MultiplexingPass::topologicalSort(function);
168        RECORD_TIMESTAMP(end_topological_sort);
169        LOG("TopologicalSort:          " << (end_topological_sort - start_topological_sort));
170
171        #ifndef NDEBUG
172        PabloVerifier::verify(function, "post-multiplexing");
173        #endif
174    }
175
176    LOG_NUMBER_OF_ADVANCES(function.getEntryBlock());
177
178    return multiplex;
179}
180
181/** ------------------------------------------------------------------------------------------------------------- *
182 * @brief initialize
183 * @param function the function to optimize
184 * @returns true if there are fewer than three advances in this function
185 *
186 * Scan through the program to identify any advances and calls then initialize the BDD engine with
187 * the proper variable ordering.
188 ** ------------------------------------------------------------------------------------------------------------- */
189unsigned MultiplexingPass::initialize(PabloFunction & function, const bool independent) {
190
191    std::stack<Statement *> scope;
192    unsigned variableCount = 0; // number of statements that cannot always be categorized without generating a new variable
193
194    // Scan through and collect all the advances, calls, scanthrus and matchstars ...
195    unsigned statements = 0, advances = 0;
196    for (Statement * stmt = function.getEntryBlock()->front(); ; ) {
197        while ( stmt ) {
198            ++statements;
199            if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
200                scope.push(stmt->getNextNode());
201                const PabloBlock * const nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();               
202                stmt = nested->front();
203                assert (stmt);
204                continue;
205            }
206            switch (stmt->getClassTypeId()) {
207                case TypeId::Advance:
208                    ++advances;
209                case TypeId::ScanThru:
210                case TypeId::Call:
211                case TypeId::MatchStar:
212                    ++variableCount;
213                    break;
214                default:
215                    break;
216            }
217            stmt = stmt->getNextNode();
218        }
219        if (scope.empty()) {
220            break;
221        }
222        stmt = scope.top();
223        scope.pop();
224    }
225
226    // If there are fewer than three Advances in this program, just abort. We cannot reduce it.
227    if (advances < 3) {
228        return 0;
229    }
230
231    initializeBaseConstraintGraph(function.getEntryBlock(), statements, advances);
232
233    mSubsetGraph = SubsetGraph(advances);
234
235    initializeAdvanceDepth(function.getEntryBlock(), advances);
236
237    // Initialize the BDD engine ...
238    bdd_init(10000000, 100000);
239    bdd_setvarnum(variableCount + function.getNumOfParameters());
240    bdd_setcacheratio(64);
241    bdd_setmaxincrease(10000000);
242    bdd_autoreorder(BDD_REORDER_SIFT);
243
244    // Map the constants and input variables
245    mCharacterization[PabloBlock::createZeroes()] = bdd_zero();
246    mCharacterization[PabloBlock::createOnes()] = bdd_one();
247    mVariables = function.getNumOfParameters();
248
249    // TODO: record information in the function to indicate which pairs of input variables are independent
250    if (independent) {
251        for (unsigned i = 0; i != mVariables; ++i) {
252            BDD Vi = bdd_ithvar(i);
253            BDD Ni = bdd_zero();
254            for (unsigned j = 0; j != i; ++j) {
255                Ni = bdd_addref(bdd_or(Ni, bdd_ithvar(j)));
256            }
257            for (unsigned j = i + 1; j != mVariables; ++j) {
258                Ni = bdd_addref(bdd_or(Ni, bdd_ithvar(j)));
259            }
260            Ni = bdd_addref(bdd_not(Ni));
261            mCharacterization[function.getParameter(i)] = bdd_addref(bdd_imp(Vi, Ni));
262        }
263    } else {
264        for (unsigned i = 0; i != mVariables; ++i) {
265            mCharacterization[function.getParameter(i)] = bdd_ithvar(i);
266        }
267    }
268
269    return advances;
270}
271
272/** ------------------------------------------------------------------------------------------------------------- *
273 * @brief initializeBaseConstraintGraph
274 ** ------------------------------------------------------------------------------------------------------------- */
275inline void MultiplexingPass::initializeBaseConstraintGraph(PabloBlock * const block, const unsigned statements, const unsigned advances) {
276
277    std::stack<Statement *> scope;
278    flat_map<const PabloAST *, unsigned> M;
279    M.reserve(statements);
280    matrix<bool> G(statements, advances, false);
281    for (unsigned i = 0; i != advances; ++i) {
282        G(i, i) = true;
283    }
284
285    unsigned n = advances;
286    unsigned k = 0;
287    for (const Statement * stmt = block->front();;) {
288        while ( stmt ) {
289            unsigned u = 0;
290            if (LLVM_UNLIKELY(isa<Advance>(stmt))) {
291                u = k++;
292            } else {
293                u = n++;
294            }
295            M.emplace(stmt, u);
296            for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
297                const PabloAST * const op = stmt->getOperand(i);
298                if (LLVM_LIKELY(isa<Statement>(op))) {
299                    const unsigned v = M[op];
300                    for (unsigned w = 0; w != k; ++w) {
301                        G(u, w) |= G(v, w);
302                    }
303                }
304            }
305            if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
306                scope.push(stmt->getNextNode());
307                const PabloBlock * const nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
308                stmt = nested->front();
309                assert (stmt);
310                continue;
311            }
312            stmt = stmt->getNextNode();
313        }
314        if (scope.empty()) {
315            break;
316        }
317        stmt = scope.top();
318        scope.pop();
319    }
320
321    assert (k == advances);
322
323    // Initialize the base constraint graph by effectively transposing G and removing reflective loops
324    mConstraintGraph = ConstraintGraph(advances);
325    for (unsigned i = 0; i != advances; ++i) {
326        for (unsigned j = 0; j < i; ++j) {
327            if (G(i, j)) {
328                add_edge(j, i, mConstraintGraph);
329            }
330        }
331        for (unsigned j = i + 1; j < advances; ++j) {
332            if (G(i, j)) {
333                add_edge(j, i, mConstraintGraph);
334            }
335        }
336    }
337
338}
339
340/** ------------------------------------------------------------------------------------------------------------- *
341 * @brief initializeAdvanceDepth
342 ** ------------------------------------------------------------------------------------------------------------- */
343inline void MultiplexingPass::initializeAdvanceDepth(PabloBlock * const entryBlock, const unsigned advances) {
344
345    std::stack<Statement *> scope;
346    unsigned k = 0;
347    int maxDepth = 0;
348    const PabloBlock * advanceScope[advances];
349    mAdvance.resize(advances, nullptr);
350    mAdvanceDepth.resize(advances, 0);
351    mAdvanceNegatedVariable.reserve(advances);
352    for (Statement * stmt = entryBlock->front(); ; ) {
353        while ( stmt ) {
354            if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
355                scope.push(stmt->getNextNode());
356                const PabloBlock * const nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
357                stmt = nested->front();
358                assert (stmt);
359                continue;
360            } else if (LLVM_UNLIKELY(isa<Advance>(stmt))) {
361                int depth = 0;
362                mAdvance[k] = cast<Advance>(stmt);
363                advanceScope[k] = cast<Advance>(stmt)->getParent();
364                for (unsigned i = 0; i != k; ++i) {
365                    if (edge(i, k, mConstraintGraph).second || (advanceScope[i] != advanceScope[k])) {
366                        depth = std::max<int>(depth, mAdvanceDepth[i]);
367                    }
368                }
369                mAdvanceDepth[k++] = ++depth;
370                maxDepth = std::max(maxDepth, depth);
371            }
372            stmt = stmt->getNextNode();
373        }
374        if (scope.empty()) {
375            break;
376        }
377        stmt = scope.top();
378        scope.pop();
379    }
380    assert (k == advances);
381
382    LOG("Window Size / Max Depth: " << mWindowSize << " of " << maxDepth);
383}
384
385/** ------------------------------------------------------------------------------------------------------------- *
386 * @brief characterize
387 * @param vars the input vars for this program
388 *
389 * Scan through the program and iteratively compute the BDDs for each statement.
390 ** ------------------------------------------------------------------------------------------------------------- */
391void MultiplexingPass::characterize(PabloBlock * const block) {
392    for (Statement * stmt : *block) {
393        if (LLVM_UNLIKELY(isa<If>(stmt))) {
394            characterize(cast<If>(stmt)->getBody());
395        } else if (LLVM_UNLIKELY(isa<While>(stmt))) {
396            characterize(cast<While>(stmt)->getBody());
397            for (const Next * var : cast<While>(stmt)->getVariants()) {
398                BDD & assign = get(var->getInitial());
399                assign = bdd_addref(bdd_or(assign, get(var)));
400            }
401        } else {
402            mCharacterization.insert(std::make_pair(stmt, characterize(stmt)));
403        }
404    }
405}
406
407/** ------------------------------------------------------------------------------------------------------------- *
408 * @brief throwUnexpectedStatementTypeError
409 ** ------------------------------------------------------------------------------------------------------------- */
410static void throwUnexpectedStatementTypeError(const Statement * const stmt) {
411    std::string tmp;
412    raw_string_ostream err(tmp);
413    err << "Unexpected statement type ";
414    PabloPrinter::print(stmt, err);
415    throw std::runtime_error(err.str());
416}
417
418/** ------------------------------------------------------------------------------------------------------------- *
419 * @brief characterize
420 ** ------------------------------------------------------------------------------------------------------------- */
421inline BDD MultiplexingPass::characterize(Statement * const stmt) {
422    assert (stmt->getNumOperands() > 0);
423    BDD bdd = get(stmt->getOperand(0));
424    switch (stmt->getClassTypeId()) {
425        case TypeId::Assign:
426        case TypeId::Next:
427            break;
428        case TypeId::And:
429            for (unsigned i = 1; i != stmt->getNumOperands(); ++i) {
430                bdd = bdd_and(bdd, get(stmt->getOperand(i)));
431            }
432            break;
433        case TypeId::Or:
434            for (unsigned i = 1; i != stmt->getNumOperands(); ++i) {
435                bdd = bdd_or(bdd, get(stmt->getOperand(i)));
436            }
437            break;
438        case TypeId::Xor:
439            for (unsigned i = 1; i != stmt->getNumOperands(); ++i) {
440                bdd = bdd_xor(bdd, get(stmt->getOperand(i)));
441            }
442            break;
443        case TypeId::Not:
444            bdd = bdd_not(bdd);
445            break;
446        case TypeId::Sel:
447            bdd = bdd_ite(bdd, get(stmt->getOperand(1)), get(stmt->getOperand(2)));
448            break;
449        case TypeId::ScanThru:
450            // ScanThru(c, m) := (c + m) ∧ ¬m. Thus we can conservatively represent this statement using the BDD
451            // for ¬m --- provided no derivative of this statement is negated in any fashion.
452        case TypeId::MatchStar:
453        case TypeId::Call:
454            return bdd_ithvar(mVariables++);
455        case TypeId::Advance:
456            return characterize(cast<Advance>(stmt), bdd);
457        default:
458            throwUnexpectedStatementTypeError(stmt);
459    }
460    return bdd_addref(bdd);
461}
462
463/** ------------------------------------------------------------------------------------------------------------- *
464 * @brief characterize
465 ** ------------------------------------------------------------------------------------------------------------- */
466inline BDD MultiplexingPass::characterize(Advance * const adv, const BDD Ik) {
467    const auto k = mAdvanceNegatedVariable.size();
468    assert (mAdvance[k] == adv);
469    std::vector<bool> unconstrained(k , false);
470    for (unsigned i = 0; i != k; ++i) {
471
472        // Are we interested in testing these streams to see whether they are mutually exclusive?
473        if (exceedsWindowSize(i, k)) continue;
474
475        // Have we already proven that they are unconstrained by their subset relationship?
476        if (unconstrained[i]) continue;
477
478        // If these Advances are mutually exclusive, in the same scope, transitively independent, and shift their
479        // values by the same amount, we can safely multiplex them. Otherwise mark the constraint in the graph.
480        const Advance * const ithAdv = mAdvance[i];
481        if ((mTestConstrainedAdvances || independent(i, k)) && (ithAdv->getOperand(1) == adv->getOperand(1))) {
482            const BDD Ii = get(ithAdv->getOperand(0));
483            const BDD IiIk = bdd_addref(bdd_and(Ii, Ik));
484            // Is there any satisfying truth assignment? If not, these streams are mutually exclusive.
485            if (bdd_satone(IiIk) == bdd_zero()) {
486                // If Ai ∩ Ak = ∅ and Aj ⊂ Ai, Aj ∩ Ak = ∅.
487                for (auto e : make_iterator_range(in_edges(i, mSubsetGraph))) {
488                    unconstrained[source(e, mSubsetGraph)] = true;
489                }
490                unconstrained[i] = true;
491            } else if (Ii == IiIk) {
492                // If Ii = Ii ∩ Ik then Ii ⊂ Ik. Record this in the subset graph with the arc (i, k).
493                // Note: the AST will be modified to make these mutually exclusive if Ai and Ak end up in
494                // the same multiplexing set.
495                add_edge(i, k, mSubsetGraph);
496                // If Ai ⊂ Ak and Aj ⊂ Ai, Aj ⊂ Ak.
497                for (auto e : make_iterator_range(in_edges(i, mSubsetGraph))) {
498                    const auto j = source(e, mSubsetGraph);
499                    add_edge(j, k, mSubsetGraph);
500                    unconstrained[j] = true;
501                }
502                unconstrained[i] = true;
503            } else if (Ik == IiIk) {
504                // If Ik = Ii ∩ Ik then Ik ⊂ Ii. Record this in the subset graph with the arc (k, i).
505                add_edge(k, i, mSubsetGraph);
506                // If Ak ⊂ Ai and Ai ⊂ Aj, Ak ⊂ Aj.
507                for (auto e : make_iterator_range(out_edges(i, mSubsetGraph))) {
508                    const auto j = target(e, mSubsetGraph);
509                    add_edge(k, j, mSubsetGraph);
510                    unconstrained[j] = true;
511                }
512                unconstrained[i] = true;
513            }
514            bdd_delref(IiIk);
515        }
516    }
517
518    BDD Ak = bdd_ithvar(mVariables++);
519    const BDD Nk = bdd_addref(bdd_not(Ak));
520    for (unsigned i = 0; i != k; ++i) {
521        if (unconstrained[i]) {
522            // Note: this algorithm deems two streams are mutually exclusive if and only if the conjuntion of their BDDs results
523            // in a contradiction. To generate a contradiction when comparing Advances, the BDD of each Advance is represented by
524            // the conjunction of variable representing that Advance and the negation of all variables for the Advances in which
525            // the inputs are deemed to be mutually exclusive. For example, if the input of the i-th Advance is mutually exclusive
526            // with the input of the j-th and k-th Advance, the BDD of the i-th Advance is Ai ∧ ¬Aj ∧ ¬Ak.
527            const Advance * const ithAdv = mAdvance[i];
528            const BDD Ni = mAdvanceNegatedVariable[i];
529            BDD & Ai = get(ithAdv);
530            Ai = bdd_addref(bdd_and(Ai, Nk));
531            Ak = bdd_addref(bdd_and(Ak, Ni));
532            if (independent(i, k) && (adv->getParent() == ithAdv->getParent())) {
533                continue;
534            }
535        }
536        add_edge(i, k, mConstraintGraph);
537    }
538    // To minimize the number of BDD computations, store the negated variable instead of negating it each time.
539    mAdvanceNegatedVariable.emplace_back(Nk);
540    return Ak;
541}
542
543/** ------------------------------------------------------------------------------------------------------------- *
544 * @brief independent
545 ** ------------------------------------------------------------------------------------------------------------- */
546inline bool MultiplexingPass::independent(const ConstraintVertex i, const ConstraintVertex j) const {
547    assert (i < num_vertices(mConstraintGraph) && j < num_vertices(mConstraintGraph));
548    return (mConstraintGraph.get_edge(i, j) == 0);
549}
550
551/** ------------------------------------------------------------------------------------------------------------- *
552 * @brief exceedsWindowSize
553 ** ------------------------------------------------------------------------------------------------------------- */
554inline bool MultiplexingPass::exceedsWindowSize(const ConstraintVertex i, const ConstraintVertex j) const {
555    assert (i < mAdvanceDepth.size() && j < mAdvanceDepth.size());
556    return (std::abs<int>(mAdvanceDepth[i] - mAdvanceDepth[j]) > mWindowSize);
557}
558
559/** ------------------------------------------------------------------------------------------------------------- *
560 * @brief is_power_of_2
561 * @param n an integer
562 ** ------------------------------------------------------------------------------------------------------------- */
563static inline bool is_power_of_2(const size_t n) {
564    return ((n & (n - 1)) == 0);
565}
566
567/** ------------------------------------------------------------------------------------------------------------- *
568 * @brief generateUsageWeightingGraph
569 *
570 * Prior to generating our candidate sets, scan through the constraint graph and generate a clique in the usage
571 * weighting graph each set of constraint-free Advance nodes that have the same users. We may be able optimize
572 * the demultiplexing calculations using range expressions.
573 *
574 * Note: it'd be preferable to contract vertices in the constraint graph prior to scanning through it but that
575 * leaves us with a more difficult problem. Namely, Advance nodes may belong to more than one clique but it'd be
576 * useless to compute a value twice; furthermore, we want to avoid generating a multiplexing set whose size is 2^n
577 * for any n ∈ â„€* but don't want to needlessly limit the size of any clique. Look into this further later.
578 ** ------------------------------------------------------------------------------------------------------------- */
579void MultiplexingPass::generateUsageWeightingGraph() {
580    const auto n = num_vertices(mConstraintGraph); assert (n > 2);
581    // Let G be the complement of the constraint graph ∪ the subset graph restricted to only the edges corresponding
582    // to pairs of Advances with the same users.
583    CliqueGraph G(n);
584    for (unsigned i = 0; i != (n - 1); ++i) {
585        const Advance * const advI = mAdvance[i];
586        for (unsigned j = i + 1; j != n; ++j) {
587            const Advance * const advJ = mAdvance[j];
588            if (LLVM_UNLIKELY(advI->getNumUses() == advJ->getNumUses()) && independent(i, j)) {
589                if (LLVM_UNLIKELY(std::equal(advI->user_begin(), advI->user_end(), advJ->user_begin()))) {
590                    // INVESTIGATE: we should be able to ignore subset relations if these are going to become a
591                    // range expression. Look into making a proof for it once the range expression calculation
592                    // is finished.
593                    if (!(edge(i, j, mSubsetGraph).second || edge(j, i, mSubsetGraph).second)) {
594                        add_edge(i, j, G);
595                    }
596                }
597            }
598        }
599    }
600    if (num_edges(G) > 0) {
601        const CliqueSets S = findMaximalCliques(G);
602        for (unsigned i = 0; i != n; ++i) {
603            clear_vertex(i, G);
604        }
605        for (const std::vector<CliqueGraph::vertex_descriptor> & C : S) {
606            const unsigned m = C.size(); assert (m > 1);
607            for (unsigned i = 1; i != m; ++i) {
608                for (unsigned j = 0; j != i; ++j) {
609                    add_edge(C[j], C[i], G);
610                }
611            }
612        }
613    }
614    mUsageGraph = G;
615}
616
617/** ------------------------------------------------------------------------------------------------------------- *
618 * @brief generateMultiplexSets
619 ** ------------------------------------------------------------------------------------------------------------- */
620bool MultiplexingPass::generateCandidateSets() {
621
622    // What if we generated a "constraint free" graph instead? By taking each connected component of it
623    // and computing the complement of it (with the same lesser to greater index ordering), we should
624    // have the same problem here but decomposed into subgraphs.
625
626    VertexVector S;
627    std::vector<ConstraintGraph::degree_size_type> D(num_vertices(mConstraintGraph));
628    S.reserve(15);
629
630    mMultiplexSetGraph = MultiplexSetGraph(num_vertices(mConstraintGraph));
631
632    // Push all source nodes into the (initial) independent set S
633    for (auto v : make_iterator_range(vertices(mConstraintGraph))) {
634        const auto d = in_degree(v, mConstraintGraph);
635        D[v] = d;
636        if (d == 0) {
637            S.push_back(v);
638        }
639    }
640
641    assert (S.size() > 0);
642
643    auto remainingVerticies = num_vertices(mConstraintGraph) - S.size();
644
645    do {
646
647        addCandidateSet(S);
648
649        bool noNewElements = true;
650        do {
651            assert (S.size() > 0);
652            // Randomly choose a vertex in S and discard it.
653            const auto i = S.begin() + IntDistribution(0, S.size() - 1)(mRNG);
654            assert (i != S.end());
655            const ConstraintVertex u = *i;
656            S.erase(i);
657
658            for (auto e : make_iterator_range(out_edges(u, mConstraintGraph))) {
659                const ConstraintVertex v = target(e, mConstraintGraph);
660                if ((--D[v]) == 0) {
661                    S.push_back(v);
662                    --remainingVerticies;
663                    noNewElements = false;
664                }
665            }
666        }
667        while (noNewElements && remainingVerticies);
668    }
669    while (remainingVerticies);
670
671    return num_vertices(mMultiplexSetGraph) > num_vertices(mConstraintGraph);
672}
673
674/** ------------------------------------------------------------------------------------------------------------- *
675 * @brief choose
676 *
677 * Compute n choose k
678 ** ------------------------------------------------------------------------------------------------------------- */
679__attribute__ ((const)) inline unsigned long choose(const unsigned n, const unsigned k) {
680    if (n < k)
681        return 0;
682    if (n == k || k == 0)
683        return 1;
684    unsigned long delta = k;
685    unsigned long max = n - k;
686    if (delta < max) {
687        std::swap(delta, max);
688    }
689    unsigned long result = delta + 1;
690    for (unsigned i = 2; i <= max; ++i) {
691        result = (result * (delta + i)) / i;
692    }
693    return result;
694}
695
696/** ------------------------------------------------------------------------------------------------------------- *
697 * @brief select
698 *
699 * James McCaffrey's algorithm for "Generating the mth Lexicographical Element of a Mathematical Combination"
700 ** ------------------------------------------------------------------------------------------------------------- */
701void select(const unsigned n, const unsigned k, const unsigned m, unsigned * element) {
702    unsigned long a = n;
703    unsigned long b = k;
704    unsigned long x = (choose(n, k) - 1) - m;
705    for (unsigned i = 0; i != k; ++i) {
706        unsigned long y = 0;
707        while ((y = choose(--a, b)) > x);
708        x = x - y;
709        b = b - 1;
710        element[i] = (n - 1) - a;
711    }
712}
713
714/** ------------------------------------------------------------------------------------------------------------- *
715 * @brief addCandidateSet
716 * @param S an independent set
717 ** ------------------------------------------------------------------------------------------------------------- */
718inline void MultiplexingPass::addCandidateSet(const VertexVector & S) {
719    if (S.size() >= 3) {
720        if (S.size() <= mMultiplexingSetSizeLimit) {
721            const auto u = add_vertex(mMultiplexSetGraph);
722            for (const auto v : S) {
723                add_edge(u, v, mMultiplexSetGraph);
724            }
725        } else {
726            const auto max = choose(S.size(), mMultiplexingSetSizeLimit);
727            unsigned element[mMultiplexingSetSizeLimit];
728            if (LLVM_UNLIKELY(max <= mMaxMultiplexingSetSelections)) {
729                for (unsigned i = 0; i != max; ++i) {
730                    select(S.size(), mMultiplexingSetSizeLimit, i, element);
731                    const auto u = add_vertex(mMultiplexSetGraph);
732                    for (unsigned j = 0; j != mMultiplexingSetSizeLimit; ++j) {
733                        add_edge(u, S[element[j]], mMultiplexSetGraph);
734                    }
735                }
736            } else { // take m random samples
737                for (unsigned i = 0; i != mMaxMultiplexingSetSelections; ++i) {
738                    select(S.size(), mMultiplexingSetSizeLimit, mRNG() % max, element);
739                    const auto u = add_vertex(mMultiplexSetGraph);
740                    for (unsigned j = 0; j != mMultiplexingSetSizeLimit; ++j) {
741                        add_edge(u, S[element[j]], mMultiplexSetGraph);
742                    }
743                }
744            }
745        }
746    }
747}
748
749/** ------------------------------------------------------------------------------------------------------------- *
750 * @brief log2_plus_one
751 ** ------------------------------------------------------------------------------------------------------------- */
752static inline size_t log2_plus_one(const size_t n) {
753    return std::log2<size_t>(n) + 1;
754}
755
756/** ------------------------------------------------------------------------------------------------------------- *
757 * @brief selectMultiplexSets
758 *
759 * This algorithm is simply computes a greedy set cover. We want an exact max-weight set cover but can generate new
760 * sets by taking a subset of any existing set. With a few modifications, the greedy approach seems to work well
761 * enough but can be shown to produce a suboptimal solution if there are three candidate sets labelled A, B and C,
762 * in which A ∩ B = ∅, |A| ≀ |B| < |C|, and C ⊂ (A ∪ B).
763 ** ------------------------------------------------------------------------------------------------------------- */
764void MultiplexingPass::selectMultiplexSets() {
765
766    using SetIterator = graph_traits<MultiplexSetGraph>::in_edge_iterator;
767    using ElementIterator = graph_traits<MultiplexSetGraph>::out_edge_iterator;
768    using degree_t = MultiplexSetGraph::degree_size_type;
769    using vertex_t = MultiplexSetGraph::vertex_descriptor;
770
771    const size_t m = num_vertices(mConstraintGraph);
772    const size_t n = num_vertices(mMultiplexSetGraph) - m;
773
774    degree_t remaining[n];
775    vertex_t chosen_set[m];
776
777    for (unsigned i = 0; i != n; ++i) {
778        remaining[i] = out_degree(i + m, mMultiplexSetGraph);
779    }
780    for (unsigned i = 0; i != m; ++i) {
781        chosen_set[i] = 0;
782    }
783
784    for (;;) {
785
786        // Choose the set with the greatest number of vertices not already included in some other set.
787        vertex_t k = 0;
788        degree_t w = 0;
789        for (vertex_t i = 0; i != n; ++i) {
790            degree_t r = remaining[i];
791            if (r > 2) { // if this set has at least 3 elements.
792                r *= r;
793                ElementIterator begin, end;
794                std::tie(begin, end) = out_edges(i + m, mMultiplexSetGraph);
795                for (auto ei = begin; ei != end; ++ei) {
796                    for (auto ej = ei; ++ej != end; ) {
797                        if (edge(target(*ei, mMultiplexSetGraph), target(*ej, mMultiplexSetGraph), mUsageGraph).second) {
798                            ++r;
799                        }
800                    }
801                }
802                if (w < r) {
803                    k = i;
804                    w = r;
805                }
806            }
807        }
808
809        // Multiplexing requires 3 or more elements; if no set contains at least 3, abort.
810        if (w == 0) {
811            break;
812        }
813
814        for (const auto ei : make_iterator_range(out_edges(k + m, mMultiplexSetGraph))) {
815            const vertex_t j = target(ei, mMultiplexSetGraph);
816            if (chosen_set[j] == 0) {
817                chosen_set[j] = (k + m);
818                for (const auto ej : make_iterator_range(in_edges(j, mMultiplexSetGraph))) {
819                    remaining[source(ej, mMultiplexSetGraph) - m]--;
820                }
821            }
822        }
823
824        assert (remaining[k] == 0);
825
826        // If this contains 2^n elements for any n, discard the member that is most likely to be added
827        // to some future set.
828        if (LLVM_UNLIKELY(is_power_of_2(w))) {
829            vertex_t j = 0;
830            degree_t w = 0;
831            for (vertex_t i = 0; i != m; ++i) {
832                if (chosen_set[i] == (k + m)) {
833                    degree_t r = 1;
834                    for (const auto ej : make_iterator_range(in_edges(i, mMultiplexSetGraph))) {
835                        // strongly prefer adding weight to unvisited sets that have more remaining vertices
836                        r += std::pow(remaining[source(ej, mMultiplexSetGraph) - m], 2);
837                    }
838                    if (w < r) {
839                        j = i;
840                        w = r;
841                    }
842                }
843            }
844            assert (w > 0);
845            chosen_set[j] = 0;
846            for (const auto ej : make_iterator_range(in_edges(j, mMultiplexSetGraph))) {
847                remaining[source(ej, mMultiplexSetGraph) - m]++;
848            }
849        }
850    }
851
852    for (unsigned i = 0; i != m; ++i) {
853        SetIterator ei, ei_end;
854        std::tie(ei, ei_end) = in_edges(i, mMultiplexSetGraph);
855        for (auto next = ei; ei != ei_end; ei = next) {
856            ++next;
857            if (source(*ei, mMultiplexSetGraph) != chosen_set[i]) {
858                remove_edge(*ei, mMultiplexSetGraph);
859            }
860        }
861    }
862
863    #ifndef NDEBUG
864    for (unsigned i = 0; i != m; ++i) {
865        assert (in_degree(i, mMultiplexSetGraph) <= 1);
866    }
867    for (unsigned i = m; i != (m + n); ++i) {
868        assert (out_degree(i, mMultiplexSetGraph) == 0 || out_degree(i, mMultiplexSetGraph) >= 3);
869    }
870    #endif
871}
872
873/** ------------------------------------------------------------------------------------------------------------- *
874 * @brief eliminateSubsetConstraints
875 ** ------------------------------------------------------------------------------------------------------------- */
876void MultiplexingPass::eliminateSubsetConstraints() {
877    // If Ai ⊂ Aj then the subset graph will contain the arc (i, j). Remove all arcs corresponding to vertices
878    // that are not elements of the same multiplexing set.
879    SubsetEdgeIterator ei, ei_end, ei_next;
880    std::tie(ei, ei_end) = edges(mSubsetGraph);
881    for (ei_next = ei; ei != ei_end; ei = ei_next) {
882        ++ei_next;
883        const auto u = source(*ei, mSubsetGraph);
884        const auto v = target(*ei, mSubsetGraph);
885        if (in_degree(u, mMultiplexSetGraph) != 0 && in_degree(v, mMultiplexSetGraph) != 0) {
886            assert (in_degree(u, mMultiplexSetGraph) == 1);
887            const auto su = source(*(in_edges(u, mMultiplexSetGraph).first), mMultiplexSetGraph);
888            assert (in_degree(v, mMultiplexSetGraph) == 1);
889            const auto sv = source(*(in_edges(v, mMultiplexSetGraph).first), mMultiplexSetGraph);
890            if (su == sv) {
891                continue;
892            }
893        }
894        remove_edge(*ei, mSubsetGraph);
895    }
896
897    if (num_edges(mSubsetGraph) != 0) {
898
899        // At least one subset constraint exists; perform a transitive reduction on the graph to ensure that
900        // we perform the minimum number of AST modifications for the selected multiplexing sets.
901
902        doTransitiveReductionOfSubsetGraph();
903
904        // Afterwards modify the AST to ensure that multiplexing algorithm can ignore any subset constraints
905        for (auto e : make_iterator_range(edges(mSubsetGraph))) {
906            Advance * const adv1 = mAdvance[source(e, mSubsetGraph)];
907            Advance * const adv2 = mAdvance[target(e, mSubsetGraph)];
908            assert (adv1->getParent() == adv2->getParent());
909            PabloBlock * const pb = adv1->getParent();
910            pb->setInsertPoint(adv2->getPrevNode());
911            adv2->setOperand(0, pb->createAnd(adv2->getOperand(0), pb->createNot(adv1->getOperand(0)), "subset"));
912            pb->setInsertPoint(adv2);
913            adv2->replaceAllUsesWith(pb->createOr(adv1, adv2, "merge"));
914        }
915
916    }
917}
918
919/** ------------------------------------------------------------------------------------------------------------- *
920 * @brief multiplexSelectedSets
921 ** ------------------------------------------------------------------------------------------------------------- */
922void MultiplexingPass::multiplexSelectedSets(PabloFunction &) {
923    const auto first_set = num_vertices(mConstraintGraph);
924    const auto last_set = num_vertices(mMultiplexSetGraph);
925    for (auto idx = first_set; idx != last_set; ++idx) {
926        const size_t n = out_degree(idx, mMultiplexSetGraph);
927        if (n) {
928            const size_t m = log2_plus_one(n);
929            Advance * input[n];
930            Advance * muxed[m];
931            // The multiplex set graph is a DAG with edges denoting the set relationships of our independent sets.
932            unsigned i = 0;
933            for (const auto u : orderMultiplexSet(idx)) {
934                input[i++] = mAdvance[u];
935            }
936            Advance * const adv = input[0];
937            PabloBlock * const block = adv->getParent(); assert (block);
938            block->setInsertPoint(nullptr);
939            /// Perform n-to-m Multiplexing
940            for (size_t j = 0; j != m; ++j) {
941                std::ostringstream prefix;
942                prefix << "mux" << n << "to" << m << '.' << (j + 1);
943                Or * muxing = block->createOr(n);
944                for (size_t i = 0; i != n; ++i) {
945                    if (((i + 1) & (1UL << j)) != 0) {
946                        assert (input[i]->getParent() == block);
947                        muxing->addOperand(input[i]->getOperand(0));
948                    }
949                }
950                muxed[j] = cast<Advance>(block->createAdvance(muxing, adv->getOperand(1), prefix.str()));
951            }
952            /// Perform m-to-n Demultiplexing
953            for (size_t i = 0; i != n; ++i) {
954                // Construct the demuxed values and replaces all the users of the original advances with them.               
955                PabloAST * demuxing[m];
956                for (size_t j = 0; j != m; ++j) {
957                    demuxing[j] = muxed[j];
958                    if (((i + 1) & (1UL << j)) == 0) {
959                        demuxing[j] = block->createNot(muxed[j]);
960                    }
961                }
962                And * demuxed = block->createAnd(m);
963                for (size_t j = 0; j != m; ++j) {
964                    demuxed->addOperand(demuxing[j]);
965                }
966                input[i]->replaceWith(demuxed, true, true);
967            }
968        }
969    }
970}
971
972/** ------------------------------------------------------------------------------------------------------------- *
973 * @brief orderMultiplexSet
974 ** ------------------------------------------------------------------------------------------------------------- */
975inline MultiplexingPass::MultiplexVector MultiplexingPass::orderMultiplexSet(const MultiplexSetGraph::vertex_descriptor u) {
976    MultiplexVector set;
977    set.reserve(out_degree(u, mMultiplexSetGraph));
978    for (const auto e : make_iterator_range(out_edges(u, mMultiplexSetGraph))) {
979        set.push_back(target(e, mMultiplexSetGraph));
980    }
981    std::sort(set.begin(), set.end());
982    MultiplexVector clique;
983    MultiplexVector result;
984    result.reserve(out_degree(u, mMultiplexSetGraph));
985    while (set.size() > 0) {
986        const auto v = *set.begin();
987        clique.push_back(v);
988        set.erase(set.begin());
989        for (const auto w : make_iterator_range(adjacent_vertices(v, mUsageGraph))) {
990            auto f = std::lower_bound(set.begin(), set.end(), w);
991            // Is w in our multiplexing set?
992            if (f == set.end() || *f != w) {
993                continue;
994            }
995            // Is our subgraph still a clique after adding w to it?
996            bool valid = true;
997            for (const auto y : clique) {
998                if (!edge(w, y, mUsageGraph).second) {
999                    valid = false;
1000                    break;
1001                }
1002            }
1003            if (valid) {
1004                clique.push_back(w);
1005                set.erase(f);
1006            }
1007        }
1008        result.insert(result.end(), clique.begin(), clique.end());
1009        clique.clear();
1010    }
1011    return result;
1012}
1013
1014/** ------------------------------------------------------------------------------------------------------------- *
1015 * @brief OrderingVerifier
1016 ** ------------------------------------------------------------------------------------------------------------- */
1017struct OrderingVerifier {
1018    OrderingVerifier() : mParent(nullptr) {}
1019    OrderingVerifier(const OrderingVerifier & parent) : mParent(&parent) {}
1020    bool count(const PabloAST * expr) const {
1021        if (mSet.count(expr)) {
1022            return true;
1023        } else if (mParent) {
1024            return mParent->count(expr);
1025        }
1026        return false;
1027    }
1028    void insert(const PabloAST * expr) {
1029        mSet.insert(expr);
1030    }
1031private:
1032    const OrderingVerifier * const mParent;
1033    std::unordered_set<const PabloAST *> mSet;
1034};
1035
1036/** ------------------------------------------------------------------------------------------------------------- *
1037 * @brief topologicalSort
1038 ** ------------------------------------------------------------------------------------------------------------- */
1039void MultiplexingPass::topologicalSort(PabloFunction & function) {
1040    OrderingVerifier set;
1041    set.insert(PabloBlock::createZeroes());
1042    set.insert(PabloBlock::createOnes());
1043    for (unsigned i = 0; i != function.getNumOfParameters(); ++i) {
1044        set.insert(function.getParameter(i));
1045    }
1046    topologicalSort(function.getEntryBlock(), set);
1047}
1048
1049/** ------------------------------------------------------------------------------------------------------------- *
1050 * @brief topologicalSort
1051 ** ------------------------------------------------------------------------------------------------------------- */
1052void MultiplexingPass::topologicalSort(PabloBlock * block, OrderingVerifier & parent) {
1053    OrderingVerifier encountered(parent);
1054    for (Statement * stmt = block->front(); stmt; ) {
1055        if (LLVM_UNLIKELY(isa<If>(stmt))) {
1056            topologicalSort(cast<If>(stmt)->getBody(), encountered);
1057            for (Assign * def : cast<If>(stmt)->getDefined()) {
1058                encountered.insert(def);
1059            }
1060        } else if (LLVM_UNLIKELY(isa<While>(stmt))) {
1061            topologicalSort(cast<While>(stmt)->getBody(), encountered);
1062            for (Next * var : cast<While>(stmt)->getVariants()) {
1063                encountered.insert(var);
1064            }
1065        }
1066        bool unmodified = true;
1067        for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
1068            PabloAST * const op = stmt->getOperand(i);
1069            if (LLVM_UNLIKELY(encountered.count(op) == 0 && isa<Statement>(op))) {
1070                Statement * const next = stmt->getNextNode();
1071                Statement * pos = cast<Statement>(op);
1072                if (cast<Statement>(op)->getParent() != block) {
1073                    // If we haven't already encountered the Assign or Next node, it must come from a If or
1074                    // While node that we haven't processed yet. Scan ahead and try to locate it.
1075                    pos = nullptr;
1076                    if (isa<Assign>(pos)) {
1077                        for (pos = cast<Statement>(op); pos; pos = pos->getNextNode()) {
1078                            if (LLVM_UNLIKELY(isa<If>(pos))) {
1079                                const auto & defs = cast<If>(pos)->getDefined();
1080                                if (LLVM_LIKELY(std::find(defs.begin(), defs.end(), op) != defs.end())) {
1081                                    break;
1082                                }
1083                            }
1084                        }
1085                    } else if (isa<Next>(pos)) {
1086                        for (pos = cast<Statement>(op); pos; pos = pos->getNextNode()) {
1087                            if (LLVM_UNLIKELY(isa<While>(pos))) {
1088                                const auto & vars = cast<While>(pos)->getVariants();
1089                                if (LLVM_LIKELY(std::find(vars.begin(), vars.end(), op) != vars.end())) {
1090                                    break;
1091                                }
1092                            }
1093                        }
1094                    }
1095                    if (LLVM_UNLIKELY(pos == nullptr)) {
1096                        throw std::runtime_error("Unexpected error: MultiplexingPass failed to topologically sort the function!");
1097                    }
1098                }
1099                stmt->insertAfter(pos);
1100                stmt = next;
1101                unmodified = false;
1102                break;
1103            }
1104        }
1105        if (unmodified) {
1106            encountered.insert(stmt);
1107            stmt = stmt->getNextNode();
1108        }
1109    }
1110}
1111
1112/** ------------------------------------------------------------------------------------------------------------- *
1113 * @brief doTransitiveReductionOfSubsetGraph
1114 ** ------------------------------------------------------------------------------------------------------------- */
1115void MultiplexingPass::doTransitiveReductionOfSubsetGraph() {
1116    std::vector<SubsetGraph::vertex_descriptor> Q;
1117    for (auto u : make_iterator_range(vertices(mSubsetGraph))) {
1118        if (in_degree(u, mSubsetGraph) == 0 && out_degree(u, mSubsetGraph) != 0) {
1119            Q.push_back(u);
1120        }
1121    }
1122    flat_set<SubsetGraph::vertex_descriptor> targets;
1123    flat_set<SubsetGraph::vertex_descriptor> visited;
1124    do {
1125        const auto u = Q.back(); Q.pop_back();
1126        for (auto ei : make_iterator_range(out_edges(u, mSubsetGraph))) {
1127            for (auto ej : make_iterator_range(out_edges(target(ei, mSubsetGraph), mSubsetGraph))) {
1128                targets.insert(target(ej, mSubsetGraph));
1129            }
1130        }
1131        for (auto v : targets) {
1132            remove_edge(u, v, mSubsetGraph);
1133        }
1134        for (auto e : make_iterator_range(out_edges(u, mSubsetGraph))) {
1135            const auto v = target(e, mSubsetGraph);
1136            if (visited.insert(v).second) {
1137                Q.push_back(v);
1138            }
1139        }
1140    } while (Q.size() > 0);
1141}
1142
1143
1144/** ------------------------------------------------------------------------------------------------------------- *
1145 * @brief findMaximalCliques
1146 *
1147 * Adaptation of the Bron-Kerbosch algorithm.
1148 ** ------------------------------------------------------------------------------------------------------------- */
1149inline MultiplexingPass::CliqueSets MultiplexingPass::findMaximalCliques(const CliqueGraph & G) {
1150    CliqueSets S;
1151    const auto n = num_vertices(G);
1152    std::vector<CliqueGraph::vertex_descriptor> ordering;
1153    ordering.reserve(n);
1154    for (auto u : make_iterator_range(vertices(G))) {
1155        if (degree(u, G)) {
1156            ordering.push_back(u);
1157        }
1158    }
1159    CliqueSet R;
1160    CliqueSet P(ordering.begin(), ordering.end());   
1161    CliqueSet X;
1162    X.reserve(ordering.size());
1163    // compute a degeneracy ordering of G
1164    std::sort(ordering.begin(), ordering.end(), [&G](const CliqueGraph::vertex_descriptor i, const CliqueGraph::vertex_descriptor j){ return degree(i, G) < degree(j, G); });
1165    for (auto v : ordering) {
1166        R.insert(v);
1167        CliqueSet PN, XN;
1168        for (const auto u : make_iterator_range(adjacent_vertices(v, G))) {
1169            if (P.count(u)) PN.insert(u);
1170            if (X.count(u)) XN.insert(u);
1171        }
1172        findMaximalCliques(G, R, std::move(PN), std::move(XN), S); // ({v}, P ∩ N(v), X ∩ N(v))
1173        R.clear();
1174        P.erase(v);
1175        X.insert(v);
1176    }
1177    return S;
1178}
1179
1180/** ------------------------------------------------------------------------------------------------------------- *
1181 * @brief findMaximalCliques
1182 ** ------------------------------------------------------------------------------------------------------------- */
1183void MultiplexingPass::findMaximalCliques(const CliqueGraph & G, CliqueSet & R, CliqueSet && P, CliqueSet && X, CliqueSets & S) {
1184    if (LLVM_UNLIKELY(P.empty() && X.empty())) { // Report R as a maximal clique
1185        S.emplace(R.begin(), R.end());
1186    } else {
1187        // choose the pivot vertex u in P ∪ X as the vertex with the highest number of neighbors in P (Tomita et al. 2006.)
1188        CliqueSet N;
1189        CliqueGraph::degree_size_type size = 0;
1190        for (const CliqueGraph::vertex_descriptor u : P) {
1191            if (degree(u, G) >= size) {
1192                CliqueGraph::degree_size_type neighbours = 0;
1193                for (const CliqueGraph::vertex_descriptor v : make_iterator_range(adjacent_vertices(u, G))) {
1194                    neighbours += P.count(v);
1195                }
1196                if (size <= neighbours) {
1197                    if (size < neighbours) {
1198                        size = neighbours;
1199                        N.clear();
1200                    }
1201                    N.insert(u);
1202                }
1203            }
1204        }
1205        for (const CliqueGraph::vertex_descriptor u : X) {
1206            if (degree(u, G) >= size) {
1207                CliqueGraph::degree_size_type neighbours = 0;
1208                for (const CliqueGraph::vertex_descriptor v : make_iterator_range(adjacent_vertices(u, G))) {
1209                    neighbours += P.count(v);
1210                }
1211                if (size <= neighbours) {
1212                    if (size < neighbours) {
1213                        size = neighbours;
1214                        N.clear();
1215                    }
1216                    N.insert(u);
1217                }
1218            }
1219        }
1220        const CliqueGraph::vertex_descriptor u = *(N.nth(IntDistribution(0, N.size() - 1)(mRNG)));
1221        // for each vertex v in P \ N(u):
1222        for (auto v = P.begin(); v != P.end(); v = P.erase(v)) {
1223            if (edge(u, *v, G).second) continue;
1224            const bool added = R.insert(*v).second;
1225            CliqueSet PN, XN;
1226            for (const CliqueGraph::vertex_descriptor u : make_iterator_range(adjacent_vertices(*v, G))) {
1227                if (P.count(u)) PN.insert(u);
1228                if (X.count(u)) XN.insert(u);
1229            }
1230            findMaximalCliques(G, R, std::move(PN), std::move(XN), S); // (R ∪ {v}, P ∩ N(v), X ∩ N(v))
1231            if (LLVM_LIKELY(added)) R.erase(*v);
1232            X.insert(*v);
1233        }
1234    }
1235}
1236
1237/** ------------------------------------------------------------------------------------------------------------- *
1238 * @brief get
1239 ** ------------------------------------------------------------------------------------------------------------- */
1240inline BDD & MultiplexingPass::get(const PabloAST * const expr) {
1241    assert (expr);
1242    auto f = mCharacterization.find(expr);
1243    assert (f != mCharacterization.end());
1244    return f->second;
1245}
1246
1247} // end of namespace pablo
Note: See TracBrowser for help on using the repository browser.