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

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

More multiplexing work. Can only be enabled by adding -DENABLE_MULTIPLEXING=yes to the cmake command. Not quite functional yet but close.

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