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

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

More multiplexing work.

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