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

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

More bug-fixing work on reassociation pass.

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