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

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

Fixed Multiplexing for new While structure/logic + Potential bug fix for PabloBuilder::Create.

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