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

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

Few extra changes.

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