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

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

Temporary check in

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