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

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

Temporary check-in

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