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

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

Replaced independent set approximation for multiplex set selection with the greedy set cover algorithm.

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