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

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

More minimization work.

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