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

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

More work on multiplexing.

File size: 34.9 KB
Line 
1#include "pablo_automultiplexing.hpp"
2#include <pablo/codegenstate.h>
3#include <llvm/ADT/SmallVector.h>
4#include <llvm/ADT/DenseMap.h>
5#include <llvm/ADT/DenseSet.h>
6#include <llvm/ADT/BitVector.h>
7#include <stack>
8#include <queue>
9#include <unordered_set>
10#include <pablo/analysis/bdd/bdd.hpp>
11#include <boost/container/flat_set.hpp>
12#include <boost/numeric/ublas/matrix.hpp>
13#include <include/simd-lib/builtins.hpp>
14// #include <pablo/expression_map.hpp>
15
16using namespace llvm;
17using namespace bdd;
18using namespace boost;
19using namespace boost::container;
20using namespace boost::numeric::ublas;
21
22namespace pablo {
23
24void AutoMultiplexing::optimize(const std::vector<Var *> & input, PabloBlock & entry) {
25    AutoMultiplexing am;
26    Engine eng = am.initialize(input, entry);
27    am.characterize(eng, entry);
28    am.createMultiplexSetGraph();
29    std::random_device rd;
30    RNG rng(rd());
31    if (am.generateMultiplexSets(rng)) {
32        am.approxMaxWeightIndependentSet(rng);
33        am.applySubsetConstraints();
34        am.multiplexSelectedIndependentSets();
35        am.topologicalSort(entry);
36    }
37}
38
39/** ------------------------------------------------------------------------------------------------------------- *
40 * @brief initialize
41 * @param vars the input vars for this program
42 * @param entry the entry block
43 *
44 * Scan through the program to identify any advances and calls then initialize the BDD engine with
45 * the proper variable ordering.
46 ** ------------------------------------------------------------------------------------------------------------- */
47Engine AutoMultiplexing::initialize(const std::vector<Var *> & vars, const PabloBlock & entry) {
48
49    flat_map<const PabloAST *, unsigned> map;
50    for (const Var * var : vars) {
51        map.emplace(var, 0);
52    }
53
54    std::stack<const Statement *> scope;
55
56    // Scan through and collect all the advances, calls, scanthrus and matchstars ...
57    unsigned n = 0, m = 1, variables = 0;
58    for (const Statement * stmt = entry.front(); ; ) {
59        while ( stmt ) {
60            ++n;
61            if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
62                // Set the next statement to be the first statement of the inner scope and push the
63                // next statement of the current statement into the scope stack.
64                const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
65                scope.push(stmt->getNextNode());
66                stmt = nested.front();
67                assert (stmt);
68                continue;
69            }
70            switch (stmt->getClassTypeId()) {
71                case PabloAST::ClassTypeId::Advance:
72                    mAdvance.push_back(const_cast<Advance*>(cast<Advance>(stmt)));
73                    map.emplace(stmt, m++);
74                case PabloAST::ClassTypeId::Call:
75                case PabloAST::ClassTypeId::ScanThru:
76                case PabloAST::ClassTypeId::MatchStar:
77                    ++variables;
78                    break;
79                default:
80                    break;
81            }
82            stmt = stmt->getNextNode();
83        }
84        if (scope.empty()) {
85            break;
86        }
87        stmt = scope.top();
88        scope.pop();
89    }
90
91    // Create the transitive closure matrix of graph. From this we'll construct
92    // two graphs restricted to the relationships between advances. The first will
93    // be a path graph, which is used to bypass testing for mutual exclusivity of
94    // advances that cannot be multiplexed. The second is a transitive reduction
95    // of that graph, which forms the basis of our constraint graph when deciding
96    // which advances ought to be multiplexed.
97
98    matrix<bool> G(n, m); // Let G be a matrix with n rows of m (Advance) elements
99    G.clear();
100    for (unsigned i = 0; i != m; ++i) {
101        G(i, i) = true;
102    }
103
104    m = 0;
105    n = m;
106    const Statement * stmt = entry.front();
107    for (;;) {
108        while ( stmt ) {
109            unsigned u;
110            if (isa<Advance>(stmt)) {
111                assert (mAdvance[m] == stmt);
112                u = ++m;
113            }
114            else {
115                u = ++n;
116                map.emplace(stmt, u);
117            }
118            for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
119                const PabloAST * const op = stmt->getOperand(i);
120                if (LLVM_UNLIKELY(isa<Integer>(op) || isa<String>(op))) {
121                    continue;
122                }
123                const unsigned v = map[op];
124                for (unsigned w = 0; w != m; ++w) {
125                    G(v, w) |= G(u, w);
126                }
127            }
128            if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
129                // Set the next statement to be the first statement of the inner scope
130                // and push the next statement of the current statement into the stack.
131                const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
132                scope.push(stmt->getNextNode());
133                stmt = nested.front();
134                assert (stmt);
135                continue;
136            }
137            stmt = stmt->getNextNode();
138        }
139        if (scope.empty()) {
140            break;
141        }
142        stmt = scope.top();
143        scope.pop();
144    }
145
146    // Record our transitive closure in the path graph and remove any reflexive-loops
147    mPathGraph = PathGraph(m - 1);
148    for (unsigned i = 1; i != m; ++i) {
149        for (unsigned j = 1; j != m; ++j) {
150            if (G(i, j)) {
151                add_edge(i - 1, j - 1, mPathGraph);
152            }
153        }
154        G(i, i) = false;
155    }
156
157    // Now take the transitive reduction of G
158    for (unsigned j = 1; j != m; ++j) {
159        for (unsigned i = 1; i != m; ++i) {
160            if (G(i, j)) {
161                // Eliminate any unecessary arcs not covered by a longer path
162                for (unsigned k = 0; k != m; ++k) {
163                    G(i, k) = G(j, k) ? false : G(i, k);
164                }
165            }
166        }
167    }
168
169    // And now transcribe it into our base constraint graph
170    mConstraintGraph = ConstraintGraph(m - 1);
171    for (unsigned j = 1; j != m; ++j) {
172        for (unsigned i = 1; i != m; ++i) {
173            if (G(i, j)) {
174                add_edge(i - 1, j - 1, mConstraintGraph);
175            }
176        }
177    }
178
179    // Initialize the BDD engine ...
180    Engine engine(variables + vars.size());
181    mCharacterizationMap.emplace(entry.createZeroes(), BDD::Contradiction());
182    mCharacterizationMap.emplace(entry.createOnes(), BDD::Tautology());
183    // Order the variables so the input Vars are pushed to the end; they ought to
184    // be the most complex to resolve.
185    for (const Var * var : vars) {
186        mCharacterizationMap.emplace(var, engine.var(variables++));
187    }
188    return engine;
189}
190
191/** ------------------------------------------------------------------------------------------------------------- *
192 * @brief characterize
193 * @param engine the BDD engine
194 * @param vars the input vars for this program
195 *
196 * Scan through the program and iteratively compute the BDDs for each statement.
197 ** ------------------------------------------------------------------------------------------------------------- */
198void AutoMultiplexing::characterize(Engine & engine, PabloBlock & entry) {
199
200    std::vector<std::pair<BDD, BDD>> advances; // the input BDD and the BDD variable of the i-th Advance
201    std::stack<Statement *> scope;
202
203    advances.reserve(mAdvance.size());
204
205    unsigned variables = 0;
206
207    // Scan through and collect all the advances, calls, scanthrus and matchstars ...
208    for (Statement * stmt = entry.front(); ; ) {
209        while ( stmt ) {
210
211            if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
212                // Set the next statement to be the first statement of the inner scope and push the
213                // next statement of the current statement into the scope stack.
214                const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
215                scope.push(stmt->getNextNode());
216                stmt = nested.front();
217                assert (stmt);
218                continue;
219            }
220
221            BDD bdd; // defaults to false
222
223            // Map our operands to the computed BDDs
224            std::array<BDD, 3> input;
225            for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
226                PabloAST * const op = stmt->getOperand(i);
227                if (LLVM_UNLIKELY(isa<Integer>(op) || isa<String>(op))) {
228                    continue;
229                }
230                auto f = mCharacterizationMap.find(op);
231                if (LLVM_UNLIKELY(f == mCharacterizationMap.end())) {
232                    throw std::runtime_error("Uncharacterized operand " + std::to_string(i) + " of " + stmt->getName()->to_string());
233                }
234                input[i] = f->second;
235            }
236
237            bool testContradiction = true;
238
239            switch (stmt->getClassTypeId()) {
240                case PabloAST::ClassTypeId::Assign:
241                    bdd = input[0];
242                    break;
243                case PabloAST::ClassTypeId::And:
244                    bdd = engine.applyAnd(input[0], input[1]);
245                    break;
246                case PabloAST::ClassTypeId::Or:
247                case PabloAST::ClassTypeId::Next:
248                    bdd = engine.applyOr(input[0], input[1]);
249                    break;
250                case PabloAST::ClassTypeId::Xor:
251                    bdd = engine.applyXor(input[0], input[1]);
252                    break;
253                case PabloAST::ClassTypeId::Not:
254                    bdd = engine.applyNot(input[0]);
255                    break;
256                case PabloAST::ClassTypeId::Sel:
257                    bdd = engine.applySel(input[0], input[1], input[2]);
258                    break;
259                case PabloAST::ClassTypeId::ScanThru:
260                    // It may be possible use "engine.applyNot(input[1])" for ScanThrus if we rule out the
261                    // possibility of a contradition being erroneously calculated later. An example of this
262                    // would be ¬(ScanThru(c,m) √ m) but are there others that would be harder to predict?
263                case PabloAST::ClassTypeId::MatchStar:
264                    if (LLVM_UNLIKELY(input[0].isFalse() || input[1].isFalse())) {
265                        break;
266                    }
267                case PabloAST::ClassTypeId::Call:
268                    testContradiction = false;
269                    bdd = engine.var(variables++);
270                    break;
271                case PabloAST::ClassTypeId::Advance:
272                    if (LLVM_LIKELY(!input[0].isFalse())) {
273
274                        // When we built the path graph, we constructed it in the same order; hense the row/column of
275                        // the path graph is equivalent to the index.
276
277                        const BDD Vk = bdd = engine.var(variables++);
278                        const BDD Ik = input[0];
279                        const unsigned k = advances.size();
280
281                        assert (stmt == mAdvance[k]);
282
283                        for (unsigned i = 0; i != k; ++i) {
284
285                            Advance * adv = mAdvance[i];
286                            const BDD Ii = std::get<0>(advances[i]);
287                            const BDD Vi = std::get<1>(advances[i]);
288
289                            bool constrained = true;
290
291                            // If these advances are "shifting" their values by the same amount and aren't transitively dependant ...
292                            if ((stmt->getOperand(1) != adv->getOperand(1)) && !edge(k, i, mPathGraph).second) {
293
294                                const BDD C = engine.applyAnd(Ik, Ii); // do we need to simplify this to identify subsets?
295                                // Is there any satisfying truth assignment? If not, these streams are mutually exclusive.
296                                bool mutuallyExclusive = engine.satOne(C).isFalse();
297
298                                if (mutuallyExclusive) {
299                                    auto f = mCharacterizationMap.find(adv);
300                                    assert (f != mCharacterizationMap.end());
301                                    // mark the i-th and k-th Advances as being mutually exclusive
302                                    bdd = engine.applyAnd(bdd, engine.applyNot(Vi));
303                                    f->second = engine.applyAnd(f->second, engine.applyNot(Vk));
304
305                                    // If these advances are not from the same scope, we cannot safely multiplex them even if
306                                    // they're mutually exclusive.
307                                    constrained = (stmt->getParent() != adv->getParent());
308                                }
309
310                                if (constrained) {
311                                    // Test whether one of the inputs to these advances are a subset of the other
312                                    if (LLVM_UNLIKELY(Ik == C)) {
313                                        // If Ik = C and C = Ii ∩ Ik then Ik (the input to the k-th advance) is a *subset* of Ii (the input of the
314                                        // i-th advance). Record this in the subset graph with the arc (k,i). These edges will be moved into the
315                                        // multiplex set graph if Advance_i and Advance_k happen to be mutually exclusive set.
316                                        mSubsetGraph.emplace_back(k, i);
317                                        continue;
318                                    }
319                                    else if (LLVM_UNLIKELY(Ii == C)) {
320                                        mSubsetGraph.emplace_back(i, k);
321                                        continue;
322                                    }
323                                }
324                            }
325
326                            if (constrained) {
327                                // We want the constraint graph to be acyclic; since the dependencies are already in topological order,
328                                // adding an arc from a lesser to greater numbered vertex won't induce a cycle.
329                                add_edge(i, k, mConstraintGraph);
330                            }
331
332                        }
333                    }
334
335                    // Append this advance to the list of known advances in this "basic block"; add on the input's BDD to
336                    // eliminate the need for looking it up again.
337                    advances.emplace_back(input[0], bdd);
338
339                    testContradiction = false;
340
341                    break;
342            }
343            if (LLVM_UNLIKELY(testContradiction && engine.satOne(bdd).isFalse())) {
344                stmt = stmt->replaceWith(entry.createZeroes());
345            }
346            else {
347                mCharacterizationMap.emplace(stmt, bdd);
348                stmt = stmt->getNextNode();
349            }
350        }
351
352        if (scope.empty()) {
353            break;
354        }
355        stmt = scope.top();
356        scope.pop();
357    }
358}
359
360/** ------------------------------------------------------------------------------------------------------------- *
361 * @brief createMappingGraph
362 ** ------------------------------------------------------------------------------------------------------------- */
363void AutoMultiplexing::createMultiplexSetGraph() {
364    mMultiplexSetGraph = MultiplexSetGraph(num_vertices(mConstraintGraph));
365}
366
367/** ------------------------------------------------------------------------------------------------------------- *
368 * @brief generateMultiplexSets
369 * @param RNG random number generator
370 ** ------------------------------------------------------------------------------------------------------------- */
371bool AutoMultiplexing::generateMultiplexSets(RNG & rng) {
372
373    using Vertex = ConstraintGraph::vertex_descriptor;
374    using VertexIterator = graph_traits<ConstraintGraph>::vertex_iterator;
375    using EdgeIterator = graph_traits<ConstraintGraph>::out_edge_iterator;
376    using DegreeType = graph_traits<ConstraintGraph>::degree_size_type;
377
378    // push all source nodes into the active independent set S
379    IndependentSet S;
380    unsigned remainingVerticies = num_vertices(mConstraintGraph);
381    std::vector<DegreeType> D(remainingVerticies);
382
383    bool canMultiplex = false;
384
385    VertexIterator vi, vi_end;
386    for (std::tie(vi, vi_end) = vertices(mConstraintGraph); vi != vi_end; ++vi) {
387        auto d = in_degree(*vi, mConstraintGraph);
388        D[*vi] = d;
389        if (d == 0) {
390            S.push_back(*vi);
391        }
392    }
393
394    for ( ; remainingVerticies >= 3; --remainingVerticies) {
395        if (S.size() >= 3) {
396            addMultiplexSet(S);
397            canMultiplex = true;
398        }       
399        // Randomly choose a vertex in S and discard it.
400        assert (!S.empty());
401        const auto i = S.begin() + RNGDistribution(0, S.size() - 1)(rng);
402        const Vertex u = *i;
403        S.erase(i);
404        EdgeIterator ei, ei_end;
405        for (std::tie(ei, ei_end) = out_edges(u, mConstraintGraph); ei != ei_end; ++ei) {
406            const Vertex v = target(*ei, mConstraintGraph);
407            if ((--D[v]) == 0) {
408                S.push_back(v);
409            }
410        }
411    }
412
413    return canMultiplex;
414}
415
416/** ------------------------------------------------------------------------------------------------------------- *
417 * @brief addMultiplexSet
418 * @param set an independent set
419 ** ------------------------------------------------------------------------------------------------------------- */
420inline void AutoMultiplexing::addMultiplexSet(const IndependentSet & S) {
421
422    // At this stage, the multiplex set graph is a directed bipartite graph that is used to show relationships
423    // between the "set vertex" and its members. We obtain these from "generateMultiplexSets".
424
425    // Question: should we enumerate the power set of S?
426    const auto v = add_vertex(mMultiplexSetGraph);
427    for (auto u : S) {
428        add_edge(v, u, mMultiplexSetGraph);
429    }
430}
431
432/** ------------------------------------------------------------------------------------------------------------- *
433 * @brief approxMaxWeightIndependentSet
434 ** ------------------------------------------------------------------------------------------------------------- */
435void AutoMultiplexing::approxMaxWeightIndependentSet(RNG & rng) {
436
437    // Compute our independent set graph from our multiplex set graph; effectively it's the graph resulting
438    // from contracting one advance node edge with an adjacent vertex
439
440    const unsigned m = num_vertices(mConstraintGraph);
441    const unsigned n = num_vertices(mMultiplexSetGraph);
442
443    IndependentSetGraph G(n);
444
445    // Record the "weight" of this independent set vertex
446    for (IndependentSetGraph::vertex_descriptor i = m; i != n; ++i) {
447        G[i] = out_degree(i, mMultiplexSetGraph);
448    }
449
450    // Make all vertices in G adjacent if they are mutually adjacent to a set vertex in S.
451    for (MultiplexSetGraph::vertex_descriptor i = m; i != n; ++i) {
452        graph_traits<MultiplexSetGraph>::in_edge_iterator ei, ei_end;
453        std::tie(ei, ei_end) = in_edges(i, mMultiplexSetGraph);
454        for (; ei != ei_end; ++ei) {
455            for (auto ej = ei; ej != ei; ++ej) {
456                add_edge(source(*ei, mMultiplexSetGraph), source(*ej, mMultiplexSetGraph), G);
457            }
458        }
459    }
460    // Process the graph using the greedy method of "Approximation Algorithms for the Weighted Independent Set Problem" (2005)
461    // (Note: look into minimum independent dominating set algorithms. It fits better with the log2 + subset relationship cost model.)
462    std::vector<IndependentSetGraph::vertex_descriptor> S;
463    std::vector<bool> removed(n, false);
464    for (;;) {
465        // Let S be the set of verticies of miminal weight
466        graph_traits<IndependentSetGraph>::vertex_iterator vi, vi_end;
467        std::tie(vi, vi_end) = vertices(G);
468        unsigned W = std::numeric_limits<unsigned>::max();
469        for (; vi != vi_end; ++vi) {
470            if (removed[*vi]) {
471                continue;
472            }
473            const unsigned w = G[*vi];
474            if (w <= W) {
475                if (w < W) {
476                    W = w;
477                    S.clear();
478                }
479                S.push_back(*vi);
480            }
481        }
482        if (S.empty()) {
483            break;
484        }
485        // Select u from S
486        const auto u = S[S.size() == 1 ? 0 : RNGDistribution(0, S.size() - 1)(rng)];
487        // Remove u and its adjacencies from G; clear the adjacent set vertices from the multiplex set graph. This will effectively
488        // choose the set refered to by u as one of our chosen independent sets and discard any other sets that contain one
489        // of the vertices in the chosen set.
490        graph_traits<IndependentSetGraph>::adjacency_iterator ai, ai_end;
491        std::tie(ai, ai_end) = adjacent_vertices(u, G);
492        for (; ai != ai_end; ++ai) {
493            removed[*ai] = true;
494            clear_out_edges(m + *ai, mMultiplexSetGraph);
495        }
496        removed[u] = true;
497    }
498}
499
500/** ------------------------------------------------------------------------------------------------------------- *
501 * @brief applySubsetConstraints
502 ** ------------------------------------------------------------------------------------------------------------- */
503void AutoMultiplexing::applySubsetConstraints() {
504
505    // When entering thus function, the multiplex set graph M is a bipartite DAG with edges denoting the set
506    // relationships of our independent sets.
507    const unsigned m = num_vertices(mConstraintGraph);
508    const unsigned n = num_vertices(mMultiplexSetGraph);
509
510    // Add in any edges from our subset constraints to M that are within the same set.
511    bool hasSubsetConstraint = false;
512    for (const auto & ei : mSubsetGraph) {
513        const auto u = ei.first;
514        const auto v = ei.second;
515        graph_traits<MultiplexSetGraph>::in_edge_iterator ej, ej_end;
516        // If both the source and target of ei are adjacent to the same vertex, that vertex must be the
517        // "set vertex". Add the edge between the vertices.
518        for (std::tie(ej, ej_end) = in_edges(u, mMultiplexSetGraph); ej != ej_end; ++ej) {
519            auto w = target(*ej, mMultiplexSetGraph);
520            // Only check (v, w) if w is a "set vertex".
521            if (w >= (n - m) && edge(v, w, mMultiplexSetGraph).second) {
522                add_edge(u, v, mMultiplexSetGraph);
523                hasSubsetConstraint = true;
524            }
525        }
526    }
527
528    if (LLVM_UNLIKELY(hasSubsetConstraint)) {
529        // At this point, M is still a DAG but no longer bipartite. We're going to scan through the set vertices
530        // in M, and use a DFS to scan through M and eliminate any subset relationships in the AST.
531        // That way, "multiplexSelectedIndependentSets" only needs to consider muxing and demuxing of the streams.
532
533        std::vector<MultiplexSetGraph::vertex_descriptor> V;
534        std::stack<MultiplexSetGraph::vertex_descriptor> S;
535        std::queue<PabloAST *> Q;
536        BitVector D(n - m, 0);
537
538        for (auto i = m; i != n; ++i) {
539            graph_traits<MultiplexSetGraph>::out_edge_iterator ei, ei_end;
540            // For each member of a "set vertex" ...
541            std::tie(ei, ei_end) = out_edges(i, mMultiplexSetGraph);
542            for (; ei != ei_end; ++ei) {
543                const auto s = source(*ei, mMultiplexSetGraph);
544                if (out_degree(s, mMultiplexSetGraph) != 0) {
545                    // First scan through the subgraph of vertices in M dominated by s and build up the set T,
546                    // consisting of all sinks w.r.t. vertex s.
547                    auto u = s;
548                    for (;;) {
549                        graph_traits<MultiplexSetGraph>::out_edge_iterator ej, ej_end;
550                        for (std::tie(ej, ej_end) = out_edges(u, mMultiplexSetGraph); ej != ej_end; ++ej) {
551                            auto v = target(*ej, mMultiplexSetGraph);
552                            if (D.test(v)) {
553                                continue;
554                            }
555                            D.set(v);
556                            if (out_degree(v, mMultiplexSetGraph) == 0) {
557                                V.push_back(v);
558                            }
559                            else {
560                                S.push(v);
561                            }
562                        }
563                        if (S.empty()) {
564                            break;
565                        }
566                        u = S.top();
567                        S.pop();
568                    }
569                    D.clear();
570                    // Now in order for these advances to be mutually exclusive, the input to A_s must be masked
571                    // with the complement of each advance indicated by V.
572
573                    Advance * adv = mAdvance[s];
574                    PabloBlock * pb = adv->getParent();
575
576                    #define CHOOSE(A,B,C) (isa<Statement>(A) ? cast<Statement>(A) : (isa<Statement>(B) ? cast<Statement>(B) : C))
577
578                    for (auto i : V) {
579                        Q.push(mAdvance[i]->getOperand(0));
580                    }                   
581                    while (Q.size() > 1) {
582                        PabloAST * a1 = Q.front(); Q.pop();
583                        PabloAST * a2 = Q.front(); Q.pop();
584                        pb->setInsertPoint(CHOOSE(a2, a1, adv));
585                        Q.push(pb->createOr(a1, a2));
586                    }
587                    assert (Q.size() == 1);
588
589                    PabloAST * const mask = pb->createNot(Q.front()); Q.pop();
590                    adv->setOperand(0, pb->createAnd(adv->getOperand(0), mask, "subset_in"));
591
592                    // Similar to the above, we're going to OR together the result of each advance,
593                    // including s. This will restore the advanced variable back to its original state.
594
595                    // Gather the original users to this advance. We'll be manipulating it shortly.
596                    Statement::Users U(adv->users());
597
598                    // Add s to V and sort the list; it'll be closer to being in topological order.
599                    V.push_back(s);
600                    std::sort(V.begin(), V.end());
601                    for (auto i : V) {
602                        Q.push(mAdvance[i]);
603                    }
604                    while (Q.size() > 1) {
605                        PabloAST * a1 = Q.front(); Q.pop();
606                        PabloAST * a2 = Q.front(); Q.pop();
607                        pb->setInsertPoint(CHOOSE(a2, a1, adv));
608                        Q.push(pb->createOr(a1, a2));
609                    }
610                    assert (Q.size() == 1);
611
612                    PabloAST * const input = Q.front(); Q.pop();
613                    for (PabloAST * use : U) {
614                        if (LLVM_LIKELY(isa<Statement>(use))) {
615                            cast<Statement>(use)->replaceUsesOfWith(adv, input);
616                        }
617                    }
618
619                    pb->setInsertPoint(pb->back());
620
621                    V.clear();
622
623                }
624            }
625        }
626    }
627}
628
629//#define FAST_LOG2(x) ((sizeof(unsigned long) * 8 - 1) - ScanReverseIntrinsic((unsigned long)(x)))
630
631//#define FAST_CEIL_LOG2(x) (FAST_LOG_2(x) + ((x & (x - 1) != 0) ? 1 : 0))
632
633/** ------------------------------------------------------------------------------------------------------------- *
634 * @brief multiplexSelectedIndependentSets
635 ** ------------------------------------------------------------------------------------------------------------- */
636void AutoMultiplexing::multiplexSelectedIndependentSets() {
637
638    // When entering thus function, the multiplex set graph M is a DAG with edges denoting the set
639    // relationships of our independent sets.
640
641    unsigned N = 3;
642    for (unsigned s = num_vertices(mConstraintGraph), e = num_vertices(mMultiplexSetGraph); s != e; ++s) {
643        N = std::max<unsigned>(N, out_degree(s, mMultiplexSetGraph));
644    }
645
646    std::vector<MultiplexSetGraph::vertex_descriptor> V(N);
647    std::queue<PabloAST *> T;
648    std::queue<PabloAST *> F;
649    std::vector<SmallVector<PabloAST *, 4>> users(N);
650
651    for (unsigned s = num_vertices(mConstraintGraph), e = num_vertices(mMultiplexSetGraph); s != e; ++s) {
652        const unsigned n = out_degree(s, mMultiplexSetGraph);
653        if (n) {
654
655            const unsigned m = static_cast<unsigned>(std::ceil(std::log2(n))); // use a faster builtin function for this.
656
657            graph_traits<MultiplexSetGraph>::out_edge_iterator ei_begin, ei_end;
658            std::tie(ei_begin, ei_end) = out_edges(s, mMultiplexSetGraph);
659            for (auto ei = ei_begin; ei != ei_end; ++ei) {
660                V[std::distance(ei_begin, ei)] = target(*ei, mMultiplexSetGraph);
661            }
662            std::sort(V.begin(), V.begin() + n);
663
664            PabloBlock * const pb = mAdvance[V[0]]->getParent();
665            // Sanity test to make sure every advance is in the same scope.
666            #ifndef NDEBUG
667            for (auto i = 1; i != n; ++i) {
668                assert (mAdvance[V[i]]->getParent() == pb);
669            }
670            #endif
671
672            /// Perform n-to-m Multiplexing
673            for (unsigned j = 0; j != m; ++j) {
674                for (unsigned i = 0; i != (1 << m); ++i) {
675                    if (((i + 1) & (1 << j)) != 0) {
676                        T.push(mAdvance[V[i]]->getOperand(0));
677                    }
678                }
679                Advance * const adv = mAdvance[V[j]];
680                // TODO: figure out a way to determine whether we're creating a duplicate value below.
681                // The expression map findOrCall ought to work conceptually but the functors method
682                // doesn't really work anymore with the current API.
683                while (T.size() > 1) {
684                    PabloAST * a1 = T.front(); T.pop();
685                    PabloAST * a2 = T.front(); T.pop();
686                    pb->setInsertPoint(CHOOSE(a2, a1, adv));
687                    T.push(pb->createOr(a1, a2));
688                }
689                adv->setOperand(0, T.front()); T.pop();
690            }
691
692            /// Perform m-to-n Demultiplexing
693            // Store the original users of our advances; we'll be modifying these extensively shortly.
694            for (unsigned i = 0; i != n; ++i) {
695                const Advance * const adv = mAdvance[V[i]];
696                users[i].insert(users[i].begin(), adv->user_begin(), adv->user_end()) ;
697            }
698
699            // Now construct the demuxed values and replaces all the users of the original advances with them.
700            for (unsigned i = 0; i != n; ++i) {
701                Advance * adv = mAdvance[V[i]];
702                for (unsigned j = 0; j != m; ++j) {
703                    if (((i + 1) & (1 << j)) != 0) {
704                        T.push(mAdvance[V[j]]);
705                    }
706                    else {
707                        F.push(mAdvance[V[j]]);
708                    }
709                }
710                while (T.size() > 1) {
711                    PabloAST * a1 = T.front(); T.pop();
712                    PabloAST * a2 = T.front(); T.pop();
713                    pb->setInsertPoint(CHOOSE(a2, a1, adv));
714                    T.push(pb->createAnd(a1, a2));
715                }
716                assert (T.size() == 1);
717
718                while (F.size() > 1) {
719                    PabloAST * a1 = T.front(); T.pop();
720                    PabloAST * a2 = T.front(); T.pop();
721                    pb->setInsertPoint(CHOOSE(a2, a1, adv));
722                    F.push(pb->createOr(a1, a2));
723                }
724                assert (F.size() == 1);
725
726                PabloAST * const demux = pb->createAnd(T.front(), pb->createNot(F.front()), "demux"); T.pop(); F.pop();
727                for (PabloAST * use : users[i]) {
728                    cast<Statement>(use)->replaceUsesOfWith(adv, demux);
729                }
730            }
731
732            /// Clean up the unneeded advances ...
733            for (unsigned i = m; i != n; ++i) {
734                mAdvance[V[i]]->eraseFromParent(true);
735            }
736            for (unsigned i = 0; i != n; ++i) {
737                users[i].clear();
738            }
739
740        }
741    }
742}
743
744/** ------------------------------------------------------------------------------------------------------------- *
745 * @brief topologicalSort
746 *
747 * After transforming the IR, we need to run this in order to always have a valid program. Each multiplex set
748 * contains vertices corresponding to an Advance in the IR. While we know each Advance within a set is independent
749 * w.r.t. the transitive closure of their dependencies in the IR, the position of each Advance's dependencies and
750 * users within the IR isn't taken into consideration. Thus while there must be a valid ordering for the program,
751 * it's not necessarily the original ordering.
752 ** ------------------------------------------------------------------------------------------------------------- */
753void AutoMultiplexing::topologicalSort(PabloBlock & entry) const {
754
755    TopologicalSortGraph G;
756    TopologicalSortQueue Q;
757    TopologicalSortMap map;
758
759    std::stack<Statement *> scope;
760
761    Statement * ip = nullptr;
762    Statement * first;
763    Statement * stmt;
764
765    for (first = stmt = entry.front(); ; ) {
766
767        while ( stmt ) {
768            if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
769                // Sort the current "basic block"
770                topologicalSort(G, Q, map, ip, first);
771                // Set the next statement to be the first statement of the inner scope and push the
772                // next statement of the current statement into the scope stack.
773                const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
774                scope.push(stmt);
775                ip = nullptr;
776                first = stmt = nested.front();
777                assert (stmt);
778                continue;
779            }
780
781            const auto u = add_vertex(stmt, G);
782            for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
783                auto f = map.find(stmt->getOperand(i));
784                if (f == map.end()) {
785                    continue;
786                }
787                add_edge(f->second, u, G);
788            }
789            if (in_degree(u, G) == 0) {
790                Q.push(u);
791            }
792            map.emplace(stmt, u);
793            stmt = stmt->getNextNode();
794        }
795
796        topologicalSort(G, Q, map, ip, first);
797        if (scope.empty()) {
798            break;
799        }
800        ip = scope.top();
801        scope.pop();
802        first = stmt = ip->getNextNode();
803    }
804
805}
806
807void AutoMultiplexing::topologicalSort(TopologicalSortGraph & G, TopologicalSortQueue & Q, TopologicalSortMap & M, Statement * ip, Statement * first) const {
808    Statement * stmt = first;
809    while (!Q.empty()) {
810        const auto u = Q.front(); Q.pop();
811        graph_traits<TopologicalSortGraph>::out_edge_iterator ei, ei_end;
812        for (std::tie(ei, ei_end) = out_edges(u, G); ei != ei_end; ++ei) {
813            const auto v = target(*ei, G);
814            if (in_degree(v, G) == 1) {
815                Q.push(v);
816            }
817        }
818        Statement * next = G[u];
819        if (stmt != next) {
820            if (LLVM_UNLIKELY(ip == nullptr)) {
821                next->insertBefore(first);
822            }
823            else {
824                next->insertAfter(ip);
825            }
826        }
827        ip = next;
828    }
829    G.clear();
830    M.clear();
831}
832
833} // end of namespace pablo
834
Note: See TracBrowser for help on using the repository browser.