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

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

More multiplexing work.

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