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

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

Work on lowering + minor bug fixes.

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