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

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

Misc changes + potential SIGBUS fix for issue reported by Hongpu.

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