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

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

More work on multiplexing

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