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

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

Bug fixes for reassociation pass.

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