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

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

Added optional CMake command -DDISABLE_PREGENERATED_UCD_FUNCTIONS.

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