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

Last change on this file since 4738 was 4738, checked in by nmedfort, 4 years ago

More work on the boolean reassociation pass.

File size: 44.6 KB
Line 
1#include "pablo_automultiplexing.hpp"
2#include <include/simd-lib/builtins.hpp>
3#include <pablo/builder.hpp>
4#include <pablo/function.h>
5#include <pablo/printer_pablos.h>
6#include <boost/container/flat_set.hpp>
7#include <boost/numeric/ublas/matrix.hpp>
8#include <boost/circular_buffer.hpp>
9#include <boost/graph/topological_sort.hpp>
10#include <boost/range/iterator_range.hpp>
11#include <llvm/ADT/BitVector.h>
12#include <cudd.h>
13#include <cuddInt.h>
14#include <util.h>
15#include <stack>
16#include <queue>
17#include <unordered_set>
18#include <pablo/optimizers/pablo_simplifier.hpp>
19#include <pablo/optimizers/booleanreassociationpass.h>
20#include <pablo/optimizers/pablo_bddminimization.h>
21
22using namespace llvm;
23using namespace boost;
24using namespace boost::container;
25using namespace boost::numeric::ublas;
26
27#define PRINT_DEBUG_OUTPUT
28
29#if !defined(NDEBUG) && !defined(PRINT_DEBUG_OUTPUT)
30#define PRINT_DEBUG_OUTPUT
31#endif
32
33#ifdef PRINT_DEBUG_OUTPUT
34
35#include <iostream>
36
37using namespace pablo;
38typedef uint64_t timestamp_t;
39
40static inline timestamp_t read_cycle_counter() {
41#ifdef __GNUC__
42timestamp_t ts;
43#ifdef __x86_64__
44  unsigned int eax, edx;
45  asm volatile("rdtsc" : "=a" (eax), "=d" (edx));
46  ts = ((timestamp_t) eax) | (((timestamp_t) edx) << 32);
47#else
48  asm volatile("rdtsc\n" : "=A" (ts));
49#endif
50  return(ts);
51#endif
52#ifdef _MSC_VER
53  return __rdtsc();
54#endif
55}
56
57#define LOG(x) std::cerr << x << std::endl;
58#define RECORD_TIMESTAMP(Name) const timestamp_t Name = read_cycle_counter()
59#define LOG_GRAPH(Name, G) \
60    LOG(Name << " |V|=" << num_vertices(G) << ", |E|="  << num_edges(G) << \
61                " (" << (((double)num_edges(G)) / ((double)(num_vertices(G) * (num_vertices(G) - 1) / 2))) << ')')
62
63unsigned __count_advances(const PabloBlock & entry) {
64
65    std::stack<const Statement *> scope;
66    unsigned advances = 0;
67
68    // Scan through and collect all the advances, calls, scanthrus and matchstars ...
69    for (const Statement * stmt = entry.front(); ; ) {
70        while ( stmt ) {
71            if (isa<Advance>(stmt)) {
72                ++advances;
73            }
74            else if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
75                // Set the next statement to be the first statement of the inner scope and push the
76                // next statement of the current statement into the scope stack.
77                const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
78                scope.push(stmt->getNextNode());
79                stmt = nested.front();
80                assert (stmt);
81                continue;
82            }
83            stmt = stmt->getNextNode();
84        }
85        if (scope.empty()) {
86            break;
87        }
88        stmt = scope.top();
89        scope.pop();
90    }
91    return advances;
92}
93
94#define LOG_NUMBER_OF_ADVANCES(entry) LOG("|Advances|=" << __count_advances(entry))
95
96#else
97#define LOG(x)
98#define RECORD_TIMESTAMP(Name)
99#define LOG_GRAPH(Name, G)
100#define LOG_NUMBER_OF_ADVANCES(entry)
101#endif
102
103
104namespace pablo {
105
106bool AutoMultiplexing::optimize(PabloFunction & function) {
107
108    BDDMinimizationPass::optimize(function);
109
110    // std::random_device rd;
111    const auto seed = 83234827342;
112    RNG rng(seed);
113
114    LOG("Seed:                    " << seed);
115
116    AutoMultiplexing am;
117    RECORD_TIMESTAMP(start_initialize);
118    const bool abort = am.initialize(function);
119    RECORD_TIMESTAMP(end_initialize);
120
121    LOG("Initialize:              " << (end_initialize - start_initialize));
122
123    LOG_NUMBER_OF_ADVANCES(function.getEntryBlock());
124
125    if (abort) {
126        return false;
127    }
128
129    RECORD_TIMESTAMP(start_characterize);
130    am.characterize(function.getEntryBlock());
131    RECORD_TIMESTAMP(end_characterize);
132
133    LOG("Characterize:            " << (end_characterize - start_characterize));
134
135    RECORD_TIMESTAMP(start_create_multiplex_graph);
136    const bool multiplex = am.generateCandidateSets(rng);
137    RECORD_TIMESTAMP(end_create_multiplex_graph);
138    LOG("GenerateCandidateSets:   " << (end_create_multiplex_graph - start_create_multiplex_graph));
139
140    RECORD_TIMESTAMP(start_shutdown);
141    am.Shutdown();
142    RECORD_TIMESTAMP(end_shutdown);
143    LOG("Shutdown:                " << (end_shutdown - start_shutdown));
144
145    if (multiplex) {
146
147        RECORD_TIMESTAMP(start_select_multiplex_sets);
148        am.selectMultiplexSets(rng);
149        RECORD_TIMESTAMP(end_select_multiplex_sets);
150        LOG("SelectMultiplexSets:     " << (end_select_multiplex_sets - start_select_multiplex_sets));
151
152        RECORD_TIMESTAMP(start_subset_constraints);
153        am.applySubsetConstraints();
154        RECORD_TIMESTAMP(end_subset_constraints);
155        LOG("ApplySubsetConstraints:  " << (end_subset_constraints - start_subset_constraints));
156
157        RECORD_TIMESTAMP(start_select_independent_sets);
158        am.multiplexSelectedIndependentSets();
159        RECORD_TIMESTAMP(end_select_independent_sets);
160        LOG("SelectedIndependentSets: " << (end_select_independent_sets - start_select_independent_sets));
161
162        BooleanReassociationPass::optimize(function);
163
164        RECORD_TIMESTAMP(start_topological_sort);
165        am.topologicalSort(function.getEntryBlock());
166        RECORD_TIMESTAMP(end_topological_sort);
167        LOG("TopologicalSort (1):     " << (end_topological_sort - start_topological_sort));
168
169        BDDMinimizationPass::optimize(function, false);
170    }
171
172    LOG_NUMBER_OF_ADVANCES(function.getEntryBlock());
173    return multiplex;
174}
175
176/** ------------------------------------------------------------------------------------------------------------- *
177 * @brief initialize
178 * @param function the function to optimize
179 * @returns true if there are fewer than three advances in this function
180 *
181 * Scan through the program to identify any advances and calls then initialize the BDD engine with
182 * the proper variable ordering.
183 ** ------------------------------------------------------------------------------------------------------------- */
184bool AutoMultiplexing::initialize(PabloFunction & function) {
185
186    flat_map<const PabloAST *, unsigned> map;   
187    std::stack<Statement *> scope;
188    unsigned variableCount = 0; // number of statements that cannot always be categorized without generating a new variable
189
190    // Scan through and collect all the advances, calls, scanthrus and matchstars ...
191    unsigned n = 0, m = 0;
192    for (Statement * stmt = function.getEntryBlock().front(); ; ) {
193        while ( stmt ) {
194            ++n;
195            if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
196                // Set the next statement to be the first statement of the inner scope and push the
197                // next statement of the current statement into the scope stack.
198                const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
199                scope.push(stmt->getNextNode());
200                stmt = nested.front();
201                assert (stmt);
202                continue;
203            }
204
205            assert ("Run the Simplifer pass prior to this!" && (stmt->getNumUses() > 0));
206
207            switch (stmt->getClassTypeId()) {
208                case PabloAST::ClassTypeId::Advance:
209                    mAdvanceMap.emplace(stmt, m);
210                    map.emplace(stmt, m++);
211                case PabloAST::ClassTypeId::Call:
212                case PabloAST::ClassTypeId::ScanThru:
213                case PabloAST::ClassTypeId::MatchStar:
214                    variableCount++;
215                    break;
216                default:
217                    break;
218            }
219            stmt = stmt->getNextNode();
220        }
221        if (scope.empty()) {
222            break;
223        }
224        stmt = scope.top();
225        scope.pop();
226    }
227
228    // If there are fewer than three Advances in this program, just abort. We cannot reduce it.
229    if (m < 3) {
230        return true;
231    }
232
233    // Create the transitive closure matrix of graph. From this we'll construct
234    // two graphs restricted to the relationships between advances. The first will
235    // be a path graph, which is used to bypass testing for mutual exclusivity of
236    // advances that cannot be multiplexed. The second is a transitive reduction
237    // of that graph, which forms the basis of our constraint graph when deciding
238    // which advances ought to be multiplexed.
239
240    matrix<bool> G(n, m); // Let G be a matrix with n rows of m (Advance) elements
241    G.clear();
242    for (unsigned i = 0; i != m; ++i) {
243        G(i, i) = true;
244    }
245
246    n = m;
247    m = 0;
248
249    const Statement * stmt = function.getEntryBlock().front();
250    for (;;) {
251        while ( stmt ) {
252
253            unsigned u;
254            if (isa<Advance>(stmt)) {
255                assert (mAdvanceMap.count(stmt) && mAdvanceMap[stmt] == m);
256                u = m++;
257            }
258            else {
259                u = n++;
260                map.emplace(stmt, u);
261            }
262
263            for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
264                const PabloAST * const op = stmt->getOperand(i);
265                if (LLVM_LIKELY(isa<Statement>(op))) {
266                    const unsigned v = map[op];
267                    for (unsigned w = 0; w != m; ++w) {
268                        G(u, w) |= G(v, w);
269                    }
270                }
271            }
272            if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
273                // Set the next statement to be the first statement of the inner scope
274                // and push the next statement of the current statement into the stack.
275                const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
276                scope.push(stmt->getNextNode());
277                stmt = nested.front();
278                assert (stmt);
279                continue;
280            }
281            stmt = stmt->getNextNode();
282        }
283        if (scope.empty()) {
284            break;
285        }
286        stmt = scope.top();
287        scope.pop();
288    }
289
290    // Record the path / base constraint graph after removing any reflexive-loops.
291    // Since G is a use-def graph and we want our constraint graph to be a def-use graph,
292    // reverse the edges as we're writing them to obtain the transposed graph.
293    mConstraintGraph = ConstraintGraph(m);
294    mSubsetGraph = SubsetGraph(m);
295
296    for (unsigned i = 0; i != m; ++i) {
297        G(i, i) = false;
298        for (unsigned j = 0; j != m; ++j) {
299            if (G(i, j)) {
300                add_edge(j, i, mConstraintGraph);
301            }
302        }       
303    }
304
305    // Initialize the BDD engine ...
306    mManager = Cudd_Init((variableCount + function.getNumOfParameters()), 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0);
307    Cudd_AutodynDisable(mManager);
308
309    // Map the predefined 0/1 entries
310    mCharacterizationMap[function.getEntryBlock().createZeroes()] = Zero();
311    mCharacterizationMap[function.getEntryBlock().createOnes()] = One();
312
313    // Order the variables so the input Vars are pushed to the end; they ought to
314    // be the most complex to resolve.
315    for (auto i = 0; i != function.getNumOfParameters(); ++i) {
316        mCharacterizationMap[function.getParameter(i)] = Cudd_bddIthVar(mManager, variableCount++);
317    }
318
319    return false;
320}
321
322/** ------------------------------------------------------------------------------------------------------------- *
323 * @brief characterize
324 * @param vars the input vars for this program
325 *
326 * Scan through the program and iteratively compute the BDDs for each statement.
327 ** ------------------------------------------------------------------------------------------------------------- */
328void AutoMultiplexing::characterize(PabloBlock &block) {
329    for (Statement * stmt : block) {
330        if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
331            const auto start = mRecentCharacterizations.size();
332            characterize(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
333            assert (mRecentCharacterizations.size() >= start);
334            if (isa<If>(stmt)) {
335                const auto & defined = cast<const If>(stmt)->getDefined();
336                for (auto pair = mRecentCharacterizations.begin() + start; pair != mRecentCharacterizations.end(); ++pair) {
337                    const PabloAST * expr = nullptr;
338                    DdNode * bdd = nullptr;
339                    std::tie(expr, bdd) = *pair;
340                    if (LLVM_UNLIKELY(isa<Assign>(expr))) {
341                        if (LLVM_LIKELY(std::find(defined.begin(), defined.end(), expr) != defined.end())) {
342                            continue;
343                        }
344                    }
345                    mCharacterizationMap.erase(mCharacterizationMap.find(expr));
346                    if (LLVM_UNLIKELY(Cudd_IsConstant(bdd))) {
347                        continue;
348                    }
349                    Deref(bdd);
350                }
351            }
352            else { // if isa<While>(stmt)
353                const auto & variants = cast<const While>(stmt)->getVariants();
354                for (auto pair = mRecentCharacterizations.begin() + start; pair != mRecentCharacterizations.end(); ++pair) {
355                    const PabloAST * expr = nullptr;
356                    DdNode * bdd = nullptr;
357                    std::tie(expr, bdd) = *pair;
358                    if (LLVM_UNLIKELY(isa<Next>(expr))) {
359                        if (LLVM_LIKELY(std::find(variants.begin(), variants.end(), expr) != variants.end())) {
360                            DdNode *& next = mCharacterizationMap[expr];
361                            next = Or(next, bdd);
362                            Ref(next);
363                            continue;
364                        }
365                    }
366                    mCharacterizationMap.erase(mCharacterizationMap.find(expr));
367                    if (LLVM_UNLIKELY(Cudd_IsConstant(bdd))) {
368                        continue;
369                    }
370                    Deref(bdd);
371                }
372            }
373            mRecentCharacterizations.erase(mRecentCharacterizations.begin() + start, mRecentCharacterizations.end());
374            continue;
375        }
376
377        DdNode * var = characterize(stmt);
378        mCharacterizationMap[stmt] = var;       
379    }
380}
381
382/** ------------------------------------------------------------------------------------------------------------- *
383 * @brief characterize
384 ** ------------------------------------------------------------------------------------------------------------- */
385inline DdNode * AutoMultiplexing::characterize(Statement * const stmt) {
386
387    DdNode * bdd = nullptr;
388    // Map our operands to the computed BDDs
389    std::array<DdNode *, 3> input;
390    unsigned count = 0;
391    for (; count != stmt->getNumOperands(); ++count) {
392        PabloAST * const op = stmt->getOperand(count);
393        if (LLVM_UNLIKELY(isa<Integer>(op) || isa<String>(op))) {
394            continue;
395        }
396        auto f = mCharacterizationMap.find(op);
397        if (LLVM_UNLIKELY(f == mCharacterizationMap.end())) {
398            std::string tmp;
399            llvm::raw_string_ostream msg(tmp);
400            msg << "Uncharacterized operand " << std::to_string(count);
401            PabloPrinter::print(stmt, " of ", msg);
402            throw std::runtime_error(msg.str());
403        }
404        input[count] = f->second;
405    }
406
407    switch (stmt->getClassTypeId()) {
408        case PabloAST::ClassTypeId::Assign:
409        case PabloAST::ClassTypeId::Next:
410            bdd = input[0];
411            break;
412        case PabloAST::ClassTypeId::And:
413            bdd = And(input[0], input[1]);
414            break;       
415        case PabloAST::ClassTypeId::Or:
416            bdd = Or(input[0], input[1]);
417            break;
418        case PabloAST::ClassTypeId::Xor:
419            bdd = Xor(input[0], input[1]);
420            break;
421        case PabloAST::ClassTypeId::Not:
422            bdd = Not(input[0]);
423            break;
424        case PabloAST::ClassTypeId::Sel:
425            bdd = Ite(input[0], input[1], input[2]);
426            break;
427        case PabloAST::ClassTypeId::ScanThru:
428            // It may be possible use "Not(input[1])" for ScanThrus if we rule out the possibility
429            // of a contradition being erroneously calculated later. An example of this
430            // would be ¬(ScanThru(c,m) √ m)
431        case PabloAST::ClassTypeId::MatchStar:
432        case PabloAST::ClassTypeId::Call:
433            bdd = NewVar();
434            mRecentCharacterizations.emplace_back(stmt, bdd);
435            return bdd;
436        case PabloAST::ClassTypeId::Advance:
437            // This returns so that it doesn't mistakeningly replace the Advance with 0 or add it
438            // to the list of recent characterizations.
439            return characterize(cast<Advance>(stmt), input[0]);
440        default:
441            throw std::runtime_error("Unexpected statement type " + stmt->getName()->to_string());
442    }
443    Ref(bdd);
444    mRecentCharacterizations.emplace_back(stmt, bdd);
445    return bdd;
446}
447
448/** ------------------------------------------------------------------------------------------------------------- *
449 * @brief characterize
450 ** ------------------------------------------------------------------------------------------------------------- */
451inline DdNode * AutoMultiplexing::characterize(Advance *adv, DdNode * input) {
452    DdNode * Ik, * Ck, * Nk;
453    if (LLVM_UNLIKELY(isZero(input))) {
454        Ik = Ck = Nk = Zero();
455    }
456    else {
457
458        Ik = input;
459        Ref(input);
460        Ck = NewVar();
461        Nk = Not(Ck);
462
463        assert (mAdvanceMap.count(adv));
464
465        const auto k = mAdvanceMap[adv];
466
467        std::vector<bool> unconstrained(k , false);
468
469        // Can we use a transposed copy of the subset graph to determine an ordering of variables?
470        for (unsigned i = 0; i != k; ++i) {
471            // Have we already proven that these are unconstrained by the subset relationships?
472            if (unconstrained[i]) continue;
473            Advance * tmp = std::get<0>(mAdvance[i]);
474            // If these advances are "shifting" their values by the same amount and aren't transitively dependant ...
475            if ((adv->getOperand(1) == tmp->getOperand(1)) && (notTransitivelyDependant(i, k))) {
476                DdNode * Ii = std::get<1>(mAdvance[i]);
477                DdNode * const IiIk = And(Ik, Ii);
478                Ref(IiIk);
479                // Is there any satisfying truth assignment? If not, these streams are mutually exclusive.
480                if (NoSatisfyingAssignment(IiIk)) {
481                    assert (mCharacterizationMap.count(tmp));
482                    DdNode *& Ci = mCharacterizationMap[tmp];
483                    // Mark the i-th and k-th Advances as being mutually exclusive
484                    DdNode * Ni = std::get<2>(mAdvance[i]);
485                    Ck = And(Ck, Ni); Ref(Ck);
486                    Ci = And(Ci, Nk); Ref(Ci);
487                    // If Ai ∩ Ak = ∅ and Aj ⊂ Ai, Aj ∩ Ak = ∅.
488                    graph_traits<SubsetGraph>::in_edge_iterator ei, ei_end;
489                    for (std::tie(ei, ei_end) = in_edges(i, mSubsetGraph); ei != ei_end; ++ei) {
490                        const auto j = source(*ei, mSubsetGraph);
491                        if (notTransitivelyDependant(k, j)) {
492                            Advance * adv = std::get<0>(mAdvance[j]);
493                            assert (mCharacterizationMap.count(adv));
494                            DdNode *& Cj = mCharacterizationMap[adv];
495                            DdNode * Nj = std::get<2>(mAdvance[j]);
496                            // Mark the i-th and j-th Advances as being mutually exclusive
497                            Ck = And(Ck, Nj); Ref(Ck);
498                            Cj = And(Cj, Nk); Ref(Cj);
499                            unconstrained[j] = true;
500                        }
501                    }
502                    unconstrained[i] = true;
503                }
504                else if (Ik == IiIk) {
505                    // If Ik = Ii ∩ Ik then Ik ⊂ Ii. Record this in the subset graph with the arc (k,i).
506                    // These edges will be moved into the multiplex set graph if Ai and Ak happen to be
507                    // in the same mutually exclusive set.
508                    add_edge(k, i, mSubsetGraph);
509                    // If Ak ⊂ Ai and Ai ⊂ Aj, Ak ⊂ Aj.
510                    graph_traits<SubsetGraph>::out_edge_iterator ei, ei_end;
511                    for (std::tie(ei, ei_end) = out_edges(i, mSubsetGraph); ei != ei_end; ++ei) {
512                        const auto j = target(*ei, mSubsetGraph);
513                        add_edge(k, j, mSubsetGraph);
514                        unconstrained[j] = true;
515                    }
516                    unconstrained[i] = true;
517                }
518                else if (Ii == IiIk) {
519                    // If Ii = Ii ∩ Ik then Ii ⊂ Ik. Record this in the subset graph with the arc (i,k).
520                    add_edge(i, k, mSubsetGraph);
521                    // If Ai ⊂ Ak and Aj ⊂ Ai, Aj ⊂ Ak.
522                    graph_traits<SubsetGraph>::in_edge_iterator ei, ei_end;
523                    for (std::tie(ei, ei_end) = in_edges(i, mSubsetGraph); ei != ei_end; ++ei) {
524                        const auto j = source(*ei, mSubsetGraph);
525                        add_edge(j, k, mSubsetGraph);
526                        unconstrained[j] = true;
527                    }
528                    unconstrained[i] = true;
529                }
530                Deref(IiIk);
531            }
532        }
533
534        for (unsigned i = 0; i != k; ++i) {
535            const Advance * const tmp = std::get<0>(mAdvance[i]);
536            // Even if these Advances are mutually exclusive, they must be in the same scope or they cannot be safely multiplexed.
537            if (!unconstrained[i] || (adv->getParent() != tmp->getParent())) {
538                // We want the constraint graph to be acyclic; since the dependencies are already in topological order,
539                // adding an arc from a lesser to greater numbered vertex won't induce a cycle.
540                add_edge(i, k, mConstraintGraph);
541            }
542        }
543    }
544
545    mAdvance.emplace_back(adv, Ik, Nk);
546    return Ck;
547}
548
549/** ------------------------------------------------------------------------------------------------------------- *
550 * @brief notTransitivelyDependant
551 ** ------------------------------------------------------------------------------------------------------------- */
552inline bool AutoMultiplexing::notTransitivelyDependant(const ConstraintVertex i, const ConstraintVertex j) const {
553    assert (i < num_vertices(mConstraintGraph) && j < num_vertices(mConstraintGraph));
554    return (mConstraintGraph.get_edge(i, j) == 0);
555}
556
557/** ------------------------------------------------------------------------------------------------------------- *
558 * @brief CUDD wrappers
559 ** ------------------------------------------------------------------------------------------------------------- */
560
561inline DdNode * AutoMultiplexing::Zero() const {
562    return Cudd_ReadLogicZero(mManager);
563}
564
565inline DdNode * AutoMultiplexing::One() const {
566    return Cudd_ReadOne(mManager);
567}
568
569inline DdNode * AutoMultiplexing::NewVar() {
570    DdNode * var = Cudd_bddIthVar(mManager, mVariables++);
571    return var;
572}
573
574inline bool AutoMultiplexing::isZero(DdNode * const x) const {
575    return x == Zero();
576}
577
578inline DdNode * AutoMultiplexing::And(DdNode * const x, DdNode * const y) {
579    return Cudd_bddAnd(mManager, x, y);
580}
581
582inline DdNode * AutoMultiplexing::Or(DdNode * const x, DdNode * const y) {
583    return Cudd_bddOr(mManager, x, y);
584}
585
586inline DdNode * AutoMultiplexing::Xor(DdNode * const x, DdNode * const y) {
587    return Cudd_bddXor(mManager, x, y);
588}
589
590inline DdNode * AutoMultiplexing::Not(DdNode * const x) const {
591    return Cudd_Not(x);
592}
593
594inline DdNode * AutoMultiplexing::Ite(DdNode * const x, DdNode * const y, DdNode * const z) {
595    return Cudd_bddIte(mManager, x, y, z);
596}
597
598inline bool AutoMultiplexing::NoSatisfyingAssignment(DdNode * const x) {
599    return Cudd_bddLeq(mManager, x, Zero());
600}
601
602inline void AutoMultiplexing::Ref(DdNode * const x) {
603    assert (x);
604    Cudd_Ref(x);
605}
606
607inline void AutoMultiplexing::Deref(DdNode * const x) {
608    assert (x);
609    Cudd_RecursiveDeref(mManager, x);
610}
611
612inline void AutoMultiplexing::Shutdown() {
613//    #ifdef PRINT_DEBUG_OUTPUT
614//    Cudd_PrintInfo(mManager, stderr);
615//    #endif
616    Cudd_Quit(mManager);
617}
618
619/** ------------------------------------------------------------------------------------------------------------- *
620 * @brief generateMultiplexSets
621 * @param RNG random number generator
622 ** ------------------------------------------------------------------------------------------------------------- */
623bool AutoMultiplexing::generateCandidateSets(RNG & rng) {
624
625    using degree_t = graph_traits<ConstraintGraph>::degree_size_type;
626
627    // What if we generated a "constraint free" graph instead? By taking each connected component of it
628    // and computing the complement of it (with the same lesser to greater index ordering), we should
629    // have the same problem here but decomposed into subgraphs.
630
631    VertexVector S;
632    std::vector<degree_t> D(num_vertices(mConstraintGraph));
633    S.reserve(15);
634
635    mMultiplexSetGraph = MultiplexSetGraph(num_vertices(mConstraintGraph));
636
637    // Push all source nodes into the new independent set N
638    for (auto v : make_iterator_range(vertices(mConstraintGraph))) {
639        const auto d = in_degree(v, mConstraintGraph);
640        D[v] = d;
641        if (d == 0) {
642            S.push_back(v);
643        }
644    }
645
646    assert (S.size() > 0);
647
648    auto remainingVerticies = num_vertices(mConstraintGraph) - S.size();
649
650    do {
651
652        addCandidateSet(S);
653
654        bool noNewElements = true;
655        do {
656            assert (S.size() > 0);
657            // Randomly choose a vertex in S and discard it.
658            const auto i = S.begin() + IntDistribution(0, S.size() - 1)(rng);
659            assert (i != S.end());
660            const ConstraintVertex u = *i;           
661            S.erase(i);           
662
663            for (auto e : make_iterator_range(out_edges(u, mConstraintGraph))) {
664                const ConstraintVertex v = target(e, mConstraintGraph);
665                if ((--D[v]) == 0) {
666                    S.push_back(v);
667                    --remainingVerticies;
668                    noNewElements = false;
669                }
670            }
671        }
672        while (noNewElements && remainingVerticies);
673    }
674    while (remainingVerticies);
675
676    return num_vertices(mMultiplexSetGraph) > num_vertices(mConstraintGraph);
677}
678
679/** ------------------------------------------------------------------------------------------------------------- *
680 * @brief addCandidateSet
681 * @param S an independent set
682 * @param T the trie in which to encode this new set into
683 * @param roots the roots (source nodes) for each tree in T
684 ** ------------------------------------------------------------------------------------------------------------- */
685inline void AutoMultiplexing::addCandidateSet(const VertexVector & S) {
686    if (S.size() >= 3) {
687        const auto u = add_vertex(mMultiplexSetGraph);
688        for (const auto v : S) {
689            add_edge(u, v, mMultiplexSetGraph);
690        }
691    }
692}
693
694/** ------------------------------------------------------------------------------------------------------------- *
695 * @brief is_power_of_2
696 * @param n an integer
697 ** ------------------------------------------------------------------------------------------------------------- */
698static inline bool is_power_of_2(const size_t n) {
699    return ((n & (n - 1)) == 0) ;
700}
701
702/** ------------------------------------------------------------------------------------------------------------- *
703 * @brief log2_plus_one
704 ** ------------------------------------------------------------------------------------------------------------- */
705static inline size_t log2_plus_one(const size_t n) {
706    return std::log2<size_t>(n) + 1; // use a faster builtin function for this?
707}
708
709/** ------------------------------------------------------------------------------------------------------------- *
710 * @brief selectMultiplexSets
711 * @param RNG random number generator
712 *
713 * This algorithm is simply computes a greedy set cover. We want an exact max-weight set cover but can generate new
714 * sets by taking a subset of any existing set. With a few modifications, the greedy approach seems to work well
715 * enough but can be trivially shown to produce a suboptimal solution if there are three (or more) sets in which
716 * two, labelled A and B, are disjoint and the third larger set, C, that consists of elements of A and B.
717 ** ------------------------------------------------------------------------------------------------------------- */
718void AutoMultiplexing::selectMultiplexSets(RNG &) {
719
720
721    using OutEdgeIterator = graph_traits<MultiplexSetGraph>::out_edge_iterator;
722    using InEdgeIterator = graph_traits<MultiplexSetGraph>::in_edge_iterator;
723    using degree_t = MultiplexSetGraph::degree_size_type;
724    using vertex_t = MultiplexSetGraph::vertex_descriptor;
725
726    const size_t m = num_vertices(mConstraintGraph);
727    const size_t n = num_vertices(mMultiplexSetGraph) - m;
728
729    std::vector<degree_t> remaining(n, 0);
730    std::vector<vertex_t> chosen_set(m, 0);
731
732    for (unsigned i = 0; i != n; ++i) {
733        remaining[i] = out_degree(i + m, mMultiplexSetGraph);
734    }
735
736    for (;;) {
737
738        // Choose the set with the greatest number of vertices not already included in some other set.
739        vertex_t k = 0;
740        degree_t w = 0;
741        for (vertex_t i = 0; i != n; ++i) {
742            const degree_t r = remaining[i];
743            if (w < r) {
744                k = i;
745                w = r;
746            }
747        }
748
749        // Multiplexing requires at least 3 elements; if the best set contains fewer than 3, abort.
750        if (w < 3) {
751            break;
752        }
753
754        for (const auto ei : make_iterator_range(out_edges(k + m, mMultiplexSetGraph))) {
755            const vertex_t j = target(ei, mMultiplexSetGraph);
756            if (chosen_set[j] == 0) {
757                chosen_set[j] = (k + m);
758                for (const auto ej : make_iterator_range(in_edges(j, mMultiplexSetGraph))) {
759                    remaining[source(ej, mMultiplexSetGraph) - m]--;
760                }
761            }
762        }
763
764        assert (remaining[k] == 0);
765
766        // If this contains 2^n elements for any n, discard the member that is most likely to be added
767        // to some future set.
768        if (is_power_of_2(w)) {
769            vertex_t j = 0;
770            degree_t w = 0;
771            for (vertex_t i = 0; i != m; ++i) {
772                if (chosen_set[i] == (k + m)) {
773                    degree_t r = 1;
774                    for (const auto ej : make_iterator_range(in_edges(i, mMultiplexSetGraph))) {
775                        // strongly prefer adding weight to unvisited sets that have more remaining vertices
776                        r += std::pow(remaining[source(ej, mMultiplexSetGraph) - m], 2);
777                    }
778                    if (w < r) {
779                        j = i;
780                        w = r;
781                    }
782                }
783            }
784            assert (w > 0);
785            chosen_set[j] = 0;
786            for (const auto ej : make_iterator_range(in_edges(j, mMultiplexSetGraph))) {
787                remaining[source(ej, mMultiplexSetGraph) - m]++;
788            }
789        }
790    }
791
792    for (unsigned i = 0; i != m; ++i) {
793        InEdgeIterator ei, ei_end;
794        std::tie(ei, ei_end) = in_edges(i, mMultiplexSetGraph);
795        for (auto next = ei; ei != ei_end; ei = next) {
796            ++next;
797            if (source(*ei, mMultiplexSetGraph) != chosen_set[i]) {
798                remove_edge(*ei, mMultiplexSetGraph);
799            }
800        }
801    }
802
803    #ifndef NDEBUG
804    for (unsigned i = 0; i != m; ++i) {
805        assert (in_degree(i, mMultiplexSetGraph) <= 1);
806    }
807    for (unsigned i = m; i != (m + n); ++i) {
808        assert (out_degree(i, mMultiplexSetGraph) == 0 || out_degree(i, mMultiplexSetGraph) >= 3);
809    }
810    #endif
811}
812
813/** ------------------------------------------------------------------------------------------------------------- *
814 * @brief applySubsetConstraints
815 ** ------------------------------------------------------------------------------------------------------------- */
816void AutoMultiplexing::applySubsetConstraints() {
817
818    // When entering thus function, the multiplex set graph M is a bipartite DAG with edges denoting the set
819    // relationships of our independent sets.
820    const unsigned m = num_vertices(mConstraintGraph);
821    const unsigned n = num_vertices(mMultiplexSetGraph);
822
823    // Add in any edges from our subset constraints to M that are within the same set.
824    bool hasSubsetConstraint = false;
825
826    graph_traits<SubsetGraph>::edge_iterator ei, ei_end;
827    for (std::tie(ei, ei_end) = edges(mSubsetGraph); ei != ei_end; ++ei) {
828        const auto u = source(*ei, mSubsetGraph);
829        const auto v = target(*ei, mSubsetGraph);
830        graph_traits<MultiplexSetGraph>::in_edge_iterator ej, ej_end;
831        // If both the source and target of ei are adjacent to the same vertex, that vertex must be the
832        // "set vertex". Add the edge between the vertices.
833        for (std::tie(ej, ej_end) = in_edges(u, mMultiplexSetGraph); ej != ej_end; ++ej) {
834            auto w = target(*ej, mMultiplexSetGraph);
835            // Only check (v, w) if w is a "set vertex".
836            if (w >= (n - m) && edge(v, w, mMultiplexSetGraph).second) {
837                add_edge(u, v, mMultiplexSetGraph);
838                hasSubsetConstraint = true;
839            }
840        }
841    }
842
843    if (LLVM_UNLIKELY(hasSubsetConstraint)) {
844        // At this point, M is still a DAG but no longer bipartite. We're going to scan through the set vertices
845        // in M, and use a DFS to scan through M and eliminate any subset relationships in the AST.
846        // That way, "multiplexSelectedIndependentSets" only needs to consider muxing and demuxing of the streams.
847
848        std::vector<MultiplexSetGraph::vertex_descriptor> V;
849        std::stack<MultiplexSetGraph::vertex_descriptor> S;
850        std::queue<PabloAST *> Q;
851        BitVector D(n - m, 0);
852
853        for (auto i = m; i != n; ++i) {
854            graph_traits<MultiplexSetGraph>::out_edge_iterator ei, ei_end;
855            // For each member of a "set vertex" ...
856            for (auto e : make_iterator_range(out_edges(i, mMultiplexSetGraph))) {
857                const auto s = source(e, mMultiplexSetGraph);
858                if (out_degree(s, mMultiplexSetGraph) != 0) {
859                    // First scan through the subgraph of vertices in M dominated by s and build up the set T,
860                    // consisting of all sinks w.r.t. vertex s.
861                    auto u = s;
862                    for (;;) {
863                        graph_traits<MultiplexSetGraph>::out_edge_iterator ej, ej_end;
864                        for (std::tie(ej, ej_end) = out_edges(u, mMultiplexSetGraph); ej != ej_end; ++ej) {
865                            auto v = target(*ej, mMultiplexSetGraph);
866                            if (D.test(v)) {
867                                continue;
868                            }
869                            D.set(v);
870                            if (out_degree(v, mMultiplexSetGraph) == 0) {
871                                V.push_back(v);
872                            }
873                            else {
874                                S.push(v);
875                            }
876                        }
877                        if (S.empty()) {
878                            break;
879                        }
880                        u = S.top();
881                        S.pop();
882                    }
883                    D.clear();
884                    // Now in order for these advances to be mutually exclusive, the input to A_s must be masked
885                    // with the complement of each advance indicated by V.
886
887                    Advance * adv = std::get<0>(mAdvance[s]);
888                    PabloBlock * pb = adv->getParent();
889
890                    for (auto i : V) {
891                        Q.push(std::get<0>(mAdvance[i])->getOperand(0));
892                    }                   
893                    pb->setInsertPoint(adv);
894                    while (Q.size() > 1) {
895                        PabloAST * a1 = Q.front(); Q.pop();
896                        PabloAST * a2 = Q.front(); Q.pop();                       
897                        Q.push(pb->createOr(a1, a2, "subset"));
898                    }
899                    assert (Q.size() == 1);
900
901                    PabloAST * const mask = pb->createNot(Q.front()); Q.pop();
902                    adv->setOperand(0, pb->createAnd(adv->getOperand(0), mask, "subset"));
903
904                    // Similar to the above, we're going to OR together the result of each advance,
905                    // including s. This will restore the advanced variable back to its original state.
906
907                    // Gather the original users to this advance. We'll be manipulating it shortly.
908                    std::vector<PabloAST *> U(adv->users().begin(), adv->users().end());
909
910                    // Add s to V and sort the list; it'll be closer to being in topological order.
911                    V.push_back(s);
912                    std::sort(V.begin(), V.end());
913                    for (auto i : V) {
914                        Q.push(std::get<0>(mAdvance[i]));
915                    }
916                    pb->setInsertPoint(adv);
917                    while (Q.size() > 1) {
918                        PabloAST * a1 = Q.front(); Q.pop();
919                        PabloAST * a2 = Q.front(); Q.pop();                       
920                        Q.push(pb->createOr(a1, a2, "subset"));
921                    }
922                    assert (Q.size() == 1);
923
924                    PabloAST * const input = Q.front(); Q.pop();
925                    for (PabloAST * use : U) {
926                        if (LLVM_LIKELY(isa<Statement>(use))) {
927                            cast<Statement>(use)->replaceUsesOfWith(adv, input);
928                        }
929                    }
930
931                    pb->setInsertPoint(pb->back());
932
933                    V.clear();
934
935                }
936            }
937        }
938    }
939}
940
941/** ------------------------------------------------------------------------------------------------------------- *
942 * @brief multiplexSelectedIndependentSets
943 ** ------------------------------------------------------------------------------------------------------------- */
944void AutoMultiplexing::multiplexSelectedIndependentSets() {
945
946    const unsigned first_set = num_vertices(mConstraintGraph);
947    const unsigned last_set = num_vertices(mMultiplexSetGraph);
948
949    // Preallocate the structures based on the size of the largest multiplex set
950    size_t max_n = 3;
951    for (unsigned idx = first_set; idx != last_set; ++idx) {
952        max_n = std::max<unsigned>(max_n, out_degree(idx, mMultiplexSetGraph));
953    }
954
955    circular_buffer<PabloAST *> Q(max_n);
956
957    // When entering thus function, the multiplex set graph M is a DAG with edges denoting the set
958    // relationships of our independent sets.
959
960    for (unsigned idx = first_set; idx != last_set; ++idx) {
961        const size_t n = out_degree(idx, mMultiplexSetGraph);
962        if (n) {
963            const size_t m = log2_plus_one(n);           
964            Advance * input[n];
965            Advance * muxed[m];           
966
967            unsigned i = 0;
968            for (const auto e : make_iterator_range(out_edges(idx, mMultiplexSetGraph))) {
969                input[i] = std::get<0>(mAdvance[target(e, mMultiplexSetGraph)]);
970                assert (input[i]);
971                ++i;
972            }
973            assert (i == n);
974
975            PabloBlock * const block = input[0]->getParent();
976            block->setInsertPoint(block->back());
977            PabloBuilder builder(*block);
978            Advance * const adv = input[0];
979
980            /// Perform n-to-m Multiplexing
981            for (size_t j = 0; j != m; ++j) {
982
983                std::ostringstream prefix;
984                prefix << "mux" << n << "to" << m << '.' << (j + 1);
985                for (size_t i = 0; i != n; ++i) {
986                    if (((i + 1) & (1ULL << j)) != 0) {
987                        Q.push_back(input[i]->getOperand(0));
988                    }
989                }
990
991                while (Q.size() > 1) {
992                    PabloAST * a1 = Q.front(); Q.pop_front(); assert (a1);
993                    PabloAST * a2 = Q.front(); Q.pop_front(); assert (a2);
994                    assert (!Q.full());                                       
995                    Q.push_back(builder.createOr(a2, a1, "muxing"));
996                }
997
998                PabloAST * mux = Q.front(); Q.pop_front(); assert (mux);
999                // The only way this did not return an Advance statement would be if either the mux or shift amount
1000                // is zero. Since these cases would have been eliminated earlier, we are safe to cast here.               
1001                muxed[j] = cast<Advance>(builder.createAdvance(mux, adv->getOperand(1), prefix.str()));
1002            }
1003
1004            /// Perform m-to-n Demultiplexing                       
1005            for (size_t i = 0; i != n; ++i) {
1006
1007                // Construct the demuxed values and replaces all the users of the original advances with them.
1008                for (size_t j = 0; j != m; ++j) {
1009                    if (((i + 1) & (1ULL << j)) == 0) {
1010                        Q.push_back(muxed[j]);
1011                    }
1012                }
1013
1014                if (LLVM_LIKELY(Q.size() > 0)) {
1015                    while (Q.size() > 1) {
1016                        PabloAST * a1 = Q.front(); Q.pop_front(); assert (a1);
1017                        PabloAST * a2 = Q.front(); Q.pop_front(); assert (a2);
1018                        assert (!Q.full());
1019                        Q.push_back(builder.createOr(a2, a1, "demuxing"));
1020                    }
1021                    assert (Q.size() == 1);
1022                    PabloAST * neg = Q.front(); Q.pop_front();
1023                    Q.push_back(builder.createNot(neg, "demuxing")); assert (neg);
1024                }
1025
1026                for (unsigned j = 0; j != m; ++j) {
1027                    if (((i + 1) & (1ULL << j)) != 0) {
1028                        assert (!Q.full());
1029                        Q.push_back(muxed[j]);
1030                    }
1031                }
1032
1033                while (Q.size() > 1) {
1034                    PabloAST * a1 = Q.front(); Q.pop_front(); assert (a1);
1035                    PabloAST * a2 = Q.front(); Q.pop_front(); assert (a2);
1036                    assert (!Q.full());
1037                    Q.push_back(builder.createAnd(a1, a2, "demuxing"));
1038                }
1039
1040                PabloAST * demuxed = Q.front(); Q.pop_front(); assert (demuxed);
1041                input[i]->replaceWith(demuxed, true, true);
1042            }
1043        }       
1044    }
1045}
1046
1047/** ------------------------------------------------------------------------------------------------------------- *
1048 * @brief topologicalSort
1049 *
1050 * After transforming the IR, we need to run this in order to always have a valid program. Each multiplex set
1051 * contains vertices corresponding to an Advance in the IR. While we know each Advance within a set is independent
1052 * w.r.t. the transitive closure of their dependencies in the IR, the position of each Advance's dependencies and
1053 * users within the IR isn't taken into consideration. Thus while there must be a valid ordering for the program,
1054 * it's not necessarily the original ordering.
1055 ** ------------------------------------------------------------------------------------------------------------- */
1056void AutoMultiplexing::topologicalSort(PabloBlock & entry) const {
1057    // Note: not a real topological sort. I expect the original graph to be close to the resulting one. Thus cost
1058    // of constructing a graph in which to perform the sort takes longer than potentially moving an instruction
1059    // multiple times.
1060    std::unordered_set<const PabloAST *> encountered;
1061    std::stack<Statement *> scope;
1062
1063    raw_os_ostream out(std::cerr);
1064
1065    for (Statement * stmt = entry.front(); ; ) { restart:
1066        while ( stmt ) {
1067            for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
1068                PabloAST * const op = stmt->getOperand(i);
1069                if (LLVM_LIKELY(isa<Statement>(op))) {
1070                    if (LLVM_UNLIKELY(encountered.count(op) == 0)) {
1071                        if (LLVM_UNLIKELY(isa<While>(stmt) && isa<Next>(op))) {
1072                            if (encountered.count(cast<Next>(op)->getInitial()) != 0) {
1073                                continue;
1074                            }
1075                        }
1076                        Statement * const next = stmt->getNextNode();
1077                        stmt->insertAfter(cast<Statement>(op));
1078                        stmt = next;
1079                        goto restart;
1080                    }
1081                }
1082            }
1083            if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
1084                // Set the next statement to be the first statement of the inner scope and push the
1085                // next statement of the current statement into the scope stack.
1086                const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
1087                scope.push(stmt->getNextNode());
1088                stmt = nested.front();
1089                continue;
1090            }
1091
1092            encountered.insert(stmt);
1093            stmt = stmt->getNextNode();
1094        }
1095        if (scope.empty()) {
1096            break;
1097        }
1098        stmt = scope.top();
1099        scope.pop();
1100    }
1101}
1102
1103} // end of namespace pablo
1104
Note: See TracBrowser for help on using the repository browser.