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

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

Progress on multi-target UCD compiler.

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