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

Last change on this file since 5082 was 5082, checked in by cameron, 3 years ago

More cppcheck fixes

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