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

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

Partial roll back of Trie structure. Seemed to introduce the potential of generating a cycle in the AST. More analysis is needed here before mixing together multiple Advance DAG traversals.

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