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

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

More multiplexing changes.

File size: 40.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            bool updateCharacterization = true;
250
251            switch (stmt->getClassTypeId()) {
252                case PabloAST::ClassTypeId::Assign:
253                    bdd = input[0];
254                    break;
255                case PabloAST::ClassTypeId::And:
256                    bdd = And(input[0], input[1]);
257                    break;
258                case PabloAST::ClassTypeId::Next:
259                    // The next instruction is almost identical to an OR; however, a Next cannot be
260                    // an operand of a Statement. Instead it updates the Initial operand's value.
261                    testContradiction = false;
262                case PabloAST::ClassTypeId::Or:
263                    bdd = Or(input[0], input[1]);
264                    break;
265                case PabloAST::ClassTypeId::Xor:
266                    bdd = Xor(input[0], input[1]);
267                    break;
268                case PabloAST::ClassTypeId::Not:
269                    bdd = Not(input[0]);
270                    break;
271                case PabloAST::ClassTypeId::Sel:
272                    bdd = Ite(input[0], input[1], input[2]);
273                    break;
274                case PabloAST::ClassTypeId::ScanThru:
275                    // It may be possible use "mEngine.applyNot(input[1])" for ScanThrus if we rule out the
276                    // possibility of a contradition being erroneously calculated later. An example of this
277                    // would be ¬(ScanThru(c,m) √ m) but are there others that would be harder to predict?
278                case PabloAST::ClassTypeId::MatchStar:
279                    if (LLVM_UNLIKELY(isZero(input[0]) || isZero(input[1]))) {
280                        bdd = Cudd_ReadZero(mManager);
281                        break;
282                    }
283                case PabloAST::ClassTypeId::Call:
284                    testContradiction = false;
285                    updateCharacterization = false;
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                            // We could probably avoid some tests by infering that if X ⊂ Y and Y ⊂ Z then X ⊂ Z too. Will need a
313                            // more complex graph structure for storing subset edges. Similarly if X ∩ Y = ∅ and Z ⊂ X, Z ∩ Y = ∅
314
315                            // Only test pairs if they are in the same scope or one has a user in the same scope that is reachable
316                            // by the other?
317
318                            bool constrained = true;
319
320                            // If these advances are "shifting" their values by the same amount and aren't transitively dependant ...
321                            if ((stmt->getOperand(1) == adv->getOperand(1)) && (!edge(k, i, mPathGraph).second)) {
322
323
324                                // Test this with Cudd_bddIntersect / Cudd_bddLeq
325                                DdNode * const tmp = Cudd_bddIntersect(mManager, Ik, Ii);
326                                Cudd_Ref(tmp);
327                                // Is there any satisfying truth assignment? If not, these streams are mutually exclusive.
328                                if (noSatisfyingAssignment(tmp)) {
329                                    std::cerr << stmt->getName()->to_string() << " ∩ " << adv->getName()->to_string() << " = ∅"  << std::endl;
330
331                                    assert (mCharacterizationMap.count(adv));
332
333                                    DdNode *& other = mCharacterizationMap[adv];
334                                    // mark the i-th and k-th Advances as being mutually exclusive
335                                    bdd = And(bdd, Not(Vi));
336                                    other = And(other, Not(Vk));
337                                    constrained = false;
338                                }
339                                else if (Ik == tmp) {
340                                    std::cerr << stmt->getName()->to_string() << " ⊂ " << adv->getName()->to_string()  << std::endl;
341                                    // If Ik = Ii ∩ Ik then Ik (the input to the k-th advance) is a *subset* of Ii (the input of the
342                                    // i-th advance). Record this in the subset graph with the arc (k,i). These edges will be moved into the
343                                    // multiplex set graph if Advance_i and Advance_k happen to be in the same mutually exclusive set.
344                                    mSubsetGraph.emplace_back(k, i);
345                                    constrained = false;
346                                }
347                                else if (Ii == tmp) {
348                                    std::cerr << stmt->getName()->to_string() << " ⊃ " << adv->getName()->to_string()  << std::endl;
349                                    mSubsetGraph.emplace_back(i, k);
350                                    constrained = false;
351                                }
352                                Cudd_RecursiveDeref(mManager, tmp);
353                            }
354
355                            // Even if these Advances are mutually exclusive, they must be in the same scope or they cannot be safely multiplexed.
356                            if (constrained || (stmt->getParent() != adv->getParent())) {
357                                // We want the constraint graph to be acyclic; since the dependencies are already in topological order,
358                                // adding an arc from a lesser to greater numbered vertex won't induce a cycle.
359                                add_edge(i, k, mConstraintGraph);
360                            }
361
362                        }
363
364                        // Append this advance to the list of known advances in this "basic block"; add on the input's BDD to
365                        // eliminate the need for looking it up again.
366                        advances.emplace_back(Ik, Vk);
367                        testContradiction = false;
368                    }
369
370
371                    break;
372                default:
373                    throw std::runtime_error("Unexpected statement " + stmt->getName()->to_string());
374            }
375            if (LLVM_UNLIKELY(testContradiction && noSatisfyingAssignment(bdd))) {
376                Cudd_RecursiveDeref(mManager, bdd);               
377                stmt = stmt->replaceWith(entry.createZeroes());
378                continue;
379            }
380            else if (LLVM_LIKELY(updateCharacterization)){
381                mCharacterizationMap[stmt] = bdd;
382            }
383            stmt = stmt->getNextNode();
384        }
385
386        if (scope.empty()) {
387            break;
388        }
389        stmt = scope.top();
390        scope.pop();
391    }
392}
393
394/** ------------------------------------------------------------------------------------------------------------- *
395 * @brief CUDD wrappers
396 ** ------------------------------------------------------------------------------------------------------------- */
397
398inline bool AutoMultiplexing::isZero(DdNode * x) const {
399    return x == Cudd_ReadZero(mManager);
400}
401
402inline DdNode * AutoMultiplexing::And(DdNode * x, DdNode * y) {
403    DdNode * r = Cudd_bddAnd(mManager, x, y);
404    Cudd_Ref(r);
405    return r;
406}
407
408inline DdNode * AutoMultiplexing::Or(DdNode * x, DdNode * y) {
409    DdNode * r = Cudd_bddOr(mManager, x, y);
410    Cudd_Ref(r);
411    return r;
412}
413
414inline DdNode * AutoMultiplexing::Xor(DdNode * x, DdNode * y) {
415    DdNode * r = Cudd_bddXor(mManager, x, y);
416    Cudd_Ref(r);
417    return r;
418}
419
420inline DdNode * AutoMultiplexing::Not(DdNode * x) {
421    return Cudd_Not(x);
422}
423
424inline DdNode * AutoMultiplexing::Ite(DdNode * x, DdNode * y, DdNode * z) {
425    DdNode * r = Cudd_bddIte(mManager, x, y, z);
426    Cudd_Ref(r);
427    return r;
428}
429
430inline bool AutoMultiplexing::noSatisfyingAssignment(DdNode * x) {
431    // TODO: since we're only interested in knowing whether there is no such cube,
432    // write an optimized function for that if one does not exist.
433    int* cube;
434    CUDD_VALUE_TYPE dummy;
435    auto gen = Cudd_FirstCube(mManager, x, &cube, &dummy);
436    bool r = Cudd_IsGenEmpty(gen);
437    Cudd_GenFree(gen);
438    return r;
439}
440
441inline void AutoMultiplexing::shutdown() {
442    Cudd_Quit(mManager);
443}
444
445/** ------------------------------------------------------------------------------------------------------------- *
446 * @brief createMappingGraph
447 ** ------------------------------------------------------------------------------------------------------------- */
448void AutoMultiplexing::createMultiplexSetGraph() {
449    mMultiplexSetGraph = MultiplexSetGraph(num_vertices(mConstraintGraph));
450}
451
452/** ------------------------------------------------------------------------------------------------------------- *
453 * @brief generateMultiplexSets
454 * @param RNG random number generator
455 ** ------------------------------------------------------------------------------------------------------------- */
456bool AutoMultiplexing::generateMultiplexSets(RNG & rng) {
457
458    using Vertex = ConstraintGraph::vertex_descriptor;
459    using VertexIterator = graph_traits<ConstraintGraph>::vertex_iterator;
460    using EdgeIterator = graph_traits<ConstraintGraph>::out_edge_iterator;
461    using DegreeType = graph_traits<ConstraintGraph>::degree_size_type;
462
463    // push all source nodes into the active independent set S
464    IndependentSet S;
465    unsigned remainingVerticies = num_vertices(mConstraintGraph);
466    std::vector<DegreeType> D(remainingVerticies);
467
468    VertexIterator vi, vi_end;
469    for (std::tie(vi, vi_end) = vertices(mConstraintGraph); vi != vi_end; ++vi) {
470        auto d = in_degree(*vi, mConstraintGraph);
471        D[*vi] = d;
472        if (d == 0) {
473            S.push_back(*vi);
474        }
475    }
476
477    assert (!S.empty());
478
479    for ( ; remainingVerticies >= 3; --remainingVerticies) {
480        if (S.size() >= 3) {
481            addMultiplexSet(S);
482        }       
483        // Randomly choose a vertex in S and discard it.
484        assert (!S.empty());
485        const auto i = S.begin() + RNGDistribution(0, S.size() - 1)(rng);
486        const Vertex u = *i;
487        S.erase(i);
488        EdgeIterator ei, ei_end;
489        for (std::tie(ei, ei_end) = out_edges(u, mConstraintGraph); ei != ei_end; ++ei) {
490            const Vertex v = target(*ei, mConstraintGraph);
491            if ((--D[v]) == 0) {
492                S.push_back(v);
493            }
494        }
495    }
496
497    return num_vertices(mMultiplexSetGraph) > num_vertices(mConstraintGraph);
498}
499
500/** ------------------------------------------------------------------------------------------------------------- *
501 * @brief addMultiplexSet
502 * @param S an independent set
503 ** ------------------------------------------------------------------------------------------------------------- */
504inline void AutoMultiplexing::addMultiplexSet(const IndependentSet & S) {
505
506    // At this stage, the multiplex set graph is a directed bipartite graph that is used to show relationships
507    // between the "set vertex" and its members. We obtain these from "generateMultiplexSets".
508
509    // Question: should we enumerate the power set of S?
510
511    const auto v = add_vertex(mMultiplexSetGraph);
512    for (auto u : S) {
513        add_edge(v, u, mMultiplexSetGraph);
514    }
515
516}
517
518/** ------------------------------------------------------------------------------------------------------------- *
519 * @brief approxMaxWeightIndependentSet
520 * @param RNG random number generator
521 ** ------------------------------------------------------------------------------------------------------------- */
522void AutoMultiplexing::approxMaxWeightIndependentSet(RNG & rng) {
523
524    // Compute our independent set graph from our multiplex set graph; effectively it's the graph resulting
525    // from contracting one advance node edge with an adjacent vertex
526
527    const unsigned m = num_vertices(mConstraintGraph);
528    const unsigned n = num_vertices(mMultiplexSetGraph) - m;
529
530    IndependentSetGraph G(n);
531
532    std::unordered_map<MultiplexSetGraph::vertex_descriptor, IndependentSetGraph::vertex_descriptor> M;
533    MultiplexSetGraph::vertex_descriptor i = m;
534    graph_traits<IndependentSetGraph>::vertex_iterator vi, vi_end;
535    for (std::tie(vi, vi_end) = vertices(G); vi != vi_end; ++vi, ++i) {
536        M.emplace(i, *vi);
537        G[*vi] = std::make_pair(out_degree(i, mMultiplexSetGraph), i);
538    }
539
540    // Let M be mMultiplexSetGraph. Each vertex in G corresponds to a set vertex in M.
541    // If an advance vertex in M (i.e., one of the first m vertices of M) is adjacent
542    // to two or more set vertices, add an edge between the corresponding vertices in G.
543    // I.e., make all vertices in G adjacent if their corresponding sets intersect.
544
545    for (i = 0; i != m; ++i) {
546        if (in_degree(i, mMultiplexSetGraph) > 1) {
547            graph_traits<MultiplexSetGraph>::in_edge_iterator ei_begin, ei_end;
548            std::tie(ei_begin, ei_end) = in_edges(i, mMultiplexSetGraph);
549            for (auto ei = ei_begin; ei != ei_end; ++ei) {
550                for (auto ej = ei_begin; ej != ei; ++ej) {
551                    // Note: ei and ej are incoming edges. The source is the set vertex,
552                    add_edge(M[source(*ei, mMultiplexSetGraph)], M[source(*ej, mMultiplexSetGraph)], G);
553                }
554            }
555        }
556    }
557
558    // Using WMIN from "A note on greedy algorithms for the maximum weighted independent set problem"
559    // (Note: look into minimum independent dominating set algorithms. It fits better with the ceil log2 + subset cost model.)
560
561    std::vector<IndependentSetGraph::vertex_descriptor> A;
562
563    while (num_vertices(G) > 0) {
564
565        // Select a vertex vi whose weight as greater than the average weight of its neighbours ...
566
567        auto i = RNGDistribution(0, num_vertices(G) - 1)(rng);
568        for (std::tie(vi, vi_end) = vertices(G); i && vi != vi_end; ++vi, --i);
569
570        const unsigned Vw = G[*vi].first * (degree(*vi, G) + 1);
571
572        unsigned Nw = 0;
573        graph_traits<IndependentSetGraph>::adjacency_iterator ai, ai_end;
574        std::tie(ai, ai_end) = adjacent_vertices(*vi, G);
575        for (; ai != ai_end; ++ai) {
576            Nw += G[*ai].first;
577        }
578
579        // Then add it to our set and remove it and its neighbourhood from G
580
581        if (Nw <= Vw) {
582            A.reserve(degree(*vi, G) + 1);
583            // Note: by clearing the adjacent set vertices from the multiplex set graph, this will effectively
584            // choose the set refered to by vi as one of our chosen independent sets.
585            graph_traits<IndependentSetGraph>::adjacency_iterator ai, ai_end;
586            A.push_back(*vi);
587            for (std::tie(ai, ai_end) = adjacent_vertices(*vi, G); ai != ai_end; ++ai) {
588                clear_out_edges(G[*ai].second, mMultiplexSetGraph);
589                A.push_back(*ai);
590            }
591            for (auto u : A) {
592                clear_vertex(u, G);
593                remove_vertex(u, G);
594            }
595            A.clear();
596        }
597
598
599    }
600
601    #ifndef NDEBUG
602    for (unsigned i = 0; i != m; ++i) {
603        assert (in_degree(i, mMultiplexSetGraph) <= 1);
604    }
605    for (unsigned i = m; i != (m + n); ++i) {
606        assert (out_degree(i, mMultiplexSetGraph) == 0 || out_degree(i, mMultiplexSetGraph) >= 3);
607    }
608    #endif
609}
610
611/** ------------------------------------------------------------------------------------------------------------- *
612 * @brief choose
613 ** ------------------------------------------------------------------------------------------------------------- */
614
615inline Statement * choose(PabloAST * x, PabloAST * y, Statement * z) {
616    return isa<Statement>(x) ? cast<Statement>(x) : (isa<Statement>(y) ? cast<Statement>(y) : z);
617}
618
619/** ------------------------------------------------------------------------------------------------------------- *
620 * @brief applySubsetConstraints
621 ** ------------------------------------------------------------------------------------------------------------- */
622void AutoMultiplexing::applySubsetConstraints() {
623
624    // When entering thus function, the multiplex set graph M is a bipartite DAG with edges denoting the set
625    // relationships of our independent sets.
626    const unsigned m = num_vertices(mConstraintGraph);
627    const unsigned n = num_vertices(mMultiplexSetGraph);
628
629    // Add in any edges from our subset constraints to M that are within the same set.
630    bool hasSubsetConstraint = false;
631    for (const auto & ei : mSubsetGraph) {
632        const auto u = ei.first;
633        const auto v = ei.second;
634        graph_traits<MultiplexSetGraph>::in_edge_iterator ej, ej_end;
635        // If both the source and target of ei are adjacent to the same vertex, that vertex must be the
636        // "set vertex". Add the edge between the vertices.
637        for (std::tie(ej, ej_end) = in_edges(u, mMultiplexSetGraph); ej != ej_end; ++ej) {
638            auto w = target(*ej, mMultiplexSetGraph);
639            // Only check (v, w) if w is a "set vertex".
640            if (w >= (n - m) && edge(v, w, mMultiplexSetGraph).second) {
641                add_edge(u, v, mMultiplexSetGraph);
642                hasSubsetConstraint = true;
643            }
644        }
645    }
646
647    if (LLVM_UNLIKELY(hasSubsetConstraint)) {
648        // At this point, M is still a DAG but no longer bipartite. We're going to scan through the set vertices
649        // in M, and use a DFS to scan through M and eliminate any subset relationships in the AST.
650        // That way, "multiplexSelectedIndependentSets" only needs to consider muxing and demuxing of the streams.
651
652        std::vector<MultiplexSetGraph::vertex_descriptor> V;
653        std::stack<MultiplexSetGraph::vertex_descriptor> S;
654        std::queue<PabloAST *> Q;
655        BitVector D(n - m, 0);
656
657        for (auto i = m; i != n; ++i) {
658            graph_traits<MultiplexSetGraph>::out_edge_iterator ei, ei_end;
659            // For each member of a "set vertex" ...
660            std::tie(ei, ei_end) = out_edges(i, mMultiplexSetGraph);
661            for (; ei != ei_end; ++ei) {
662                const auto s = source(*ei, mMultiplexSetGraph);
663                if (out_degree(s, mMultiplexSetGraph) != 0) {
664                    // First scan through the subgraph of vertices in M dominated by s and build up the set T,
665                    // consisting of all sinks w.r.t. vertex s.
666                    auto u = s;
667                    for (;;) {
668                        graph_traits<MultiplexSetGraph>::out_edge_iterator ej, ej_end;
669                        for (std::tie(ej, ej_end) = out_edges(u, mMultiplexSetGraph); ej != ej_end; ++ej) {
670                            auto v = target(*ej, mMultiplexSetGraph);
671                            if (D.test(v)) {
672                                continue;
673                            }
674                            D.set(v);
675                            if (out_degree(v, mMultiplexSetGraph) == 0) {
676                                V.push_back(v);
677                            }
678                            else {
679                                S.push(v);
680                            }
681                        }
682                        if (S.empty()) {
683                            break;
684                        }
685                        u = S.top();
686                        S.pop();
687                    }
688                    D.clear();
689                    // Now in order for these advances to be mutually exclusive, the input to A_s must be masked
690                    // with the complement of each advance indicated by V.
691
692                    Advance * adv = mAdvance[s];
693                    PabloBlock * pb = adv->getParent();
694
695                    for (auto i : V) {
696                        Q.push(mAdvance[i]->getOperand(0));
697                    }                   
698                    while (Q.size() > 1) {
699                        PabloAST * a1 = Q.front(); Q.pop();
700                        PabloAST * a2 = Q.front(); Q.pop();
701                        pb->setInsertPoint(cast<Statement>(a2));
702                        Q.push(pb->createOr(a1, a2));
703                    }
704                    assert (Q.size() == 1);
705
706                    PabloAST * const mask = pb->createNot(Q.front()); Q.pop();
707                    adv->setOperand(0, pb->createAnd(adv->getOperand(0), mask, "subset_in"));
708
709                    // Similar to the above, we're going to OR together the result of each advance,
710                    // including s. This will restore the advanced variable back to its original state.
711
712                    // Gather the original users to this advance. We'll be manipulating it shortly.
713                    Statement::Users U(adv->users());
714
715                    // Add s to V and sort the list; it'll be closer to being in topological order.
716                    V.push_back(s);
717                    std::sort(V.begin(), V.end());
718                    for (auto i : V) {
719                        Q.push(mAdvance[i]);
720                    }
721                    while (Q.size() > 1) {
722                        PabloAST * a1 = Q.front(); Q.pop();
723                        PabloAST * a2 = Q.front(); Q.pop();
724                        pb->setInsertPoint(choose(a2, a1, adv));
725                        Q.push(pb->createOr(a1, a2));
726                    }
727                    assert (Q.size() == 1);
728
729                    PabloAST * const input = Q.front(); Q.pop();
730                    for (PabloAST * use : U) {
731                        if (LLVM_LIKELY(isa<Statement>(use))) {
732                            cast<Statement>(use)->replaceUsesOfWith(adv, input);
733                        }
734                    }
735
736                    pb->setInsertPoint(pb->back());
737
738                    V.clear();
739
740                }
741            }
742        }
743    }
744}
745
746
747static inline size_t smallest_multiplexed_set(const size_t x) {
748    return std::log2<size_t>(x) + 1; // use a faster builtin function for this?
749}
750
751
752/** ------------------------------------------------------------------------------------------------------------- *
753 * @brief multiplexSelectedIndependentSets
754 ** ------------------------------------------------------------------------------------------------------------- */
755void AutoMultiplexing::multiplexSelectedIndependentSets() const {
756
757    const unsigned f = num_vertices(mConstraintGraph);
758    const unsigned l = num_vertices(mMultiplexSetGraph);
759
760    // Preallocate the structures based on the size of the largest multiplex set
761    size_t max_n = 3;
762    for (unsigned s = f; s != l; ++s) {
763        max_n = std::max<unsigned>(max_n, out_degree(s, mMultiplexSetGraph));
764    }
765    const size_t max_m = smallest_multiplexed_set(max_n);
766
767    std::vector<MultiplexSetGraph::vertex_descriptor> I(max_n);
768    std::vector<Advance *> V(max_n);
769    std::vector<PabloAST *> muxed(max_m);
770    circular_buffer<PabloAST *> Q(max_n);
771
772    // When entering thus function, the multiplex set graph M is a DAG with edges denoting the set
773    // relationships of our independent sets.
774
775    for (unsigned s = f; s != l; ++s) {
776        const size_t n = out_degree(s, mMultiplexSetGraph);
777        if (n) {
778
779            const size_t m = smallest_multiplexed_set(n);
780
781            graph_traits<MultiplexSetGraph>::out_edge_iterator ei, ei_end;
782            std::tie(ei, ei_end) = out_edges(s, mMultiplexSetGraph);
783            for (unsigned i = 0; i != n; ++ei, ++i) {
784                I[i] = target(*ei, mMultiplexSetGraph);
785                assert (I[i] < mAdvance.size());
786            }
787            std::sort(I.begin(), I.begin() + n);
788
789            for (unsigned i = 0; i != n; ++i) {
790                V[i] = mAdvance[I[i]];
791            }
792
793            PabloBlock * const pb = V[0]->getParent();
794            assert (pb);
795
796            // Sanity test to make sure every advance is in the same scope.
797            #ifndef NDEBUG
798            for (unsigned i = 1; i != n; ++i) {
799                assert (I[i - 1] < I[i]);
800                assert (V[i - 1] != V[i]);
801                assert (V[i]->getParent() == pb);
802            }
803            #endif
804
805            /// Perform n-to-m Multiplexing
806            for (size_t j = 0; j != m; ++j) {
807
808                assert (Q.empty());
809
810                std::stringstream name;
811                name << "mux";
812                for (size_t i = 1; i <= n; ++i) {
813                    if ((i & (static_cast<size_t>(1) << j)) != 0) {
814                        assert (!Q.full());
815                        PabloAST * tmp = V[i - 1]->getOperand(0); assert (tmp);
816                        Q.push_back(tmp);
817                        name << "_" << V[i - 1]->getName()->to_string();
818                    }
819                }
820
821                assert (Q.size() >= 1);
822
823                Advance * const adv = V[j];
824                // TODO: figure out a way to determine whether we're creating a duplicate value below.
825                // The expression map findOrCall ought to work conceptually but the functors method
826                // doesn't really work anymore with the current API.
827                while (Q.size() > 1) {
828                    PabloAST * a1 = Q.front(); Q.pop_front(); assert (a1);
829                    PabloAST * a2 = Q.front(); Q.pop_front(); assert (a2);
830                    assert (!Q.full());
831                    pb->setInsertPoint(choose(a2, a1, adv));
832                    PabloAST * tmp = pb->createOr(a1, a2); assert (tmp);
833                    Q.push_back(tmp);
834                }
835                assert (Q.size() == 1);
836
837                PabloAST * mux = Q.front(); Q.pop_front(); assert (mux);
838                muxed[j] = pb->createAdvance(mux, adv->getOperand(1), name.str());
839            }
840
841
842            /// Perform m-to-n Demultiplexing
843            // Now construct the demuxed values and replaces all the users of the original advances with them.
844            for (size_t i = 1; i <= n; ++i) {
845
846                Advance * const adv = V[i - 1];
847
848                assert (Q.empty());
849                for (size_t j = 0; j != m; ++j) {
850                    if ((i & (static_cast<size_t>(1) << j)) == 0) {
851                        Q.push_back(muxed[j]);
852                    }
853                }
854
855                assert (Q.size() <= m);
856                PabloAST * neg = nullptr;
857                if (LLVM_LIKELY(Q.size() > 0)) {
858                    while (Q.size() > 1) {
859                        PabloAST * a1 = Q.front(); Q.pop_front(); assert (a1);
860                        PabloAST * a2 = Q.front(); Q.pop_front(); assert (a2);
861                        pb->setInsertPoint(choose(a2, a1, adv));
862                        assert (!Q.full());
863                        PabloAST * tmp = pb->createOr(a1, a2); assert (tmp);
864                        Q.push_back(tmp);
865                    }
866                    assert (Q.size() == 1);
867                    neg = pb->createNot(Q.front()); Q.pop_front(); assert (neg);
868                }
869
870                assert (Q.empty());
871                for (unsigned j = 0; j != m; ++j) {
872                    if ((i & (static_cast<unsigned>(1) << j)) != 0) {
873                        assert (!Q.full());
874                        Q.push_back(muxed[j]);
875                    }
876                }
877
878                assert (Q.size() <= m);
879                assert (Q.size() >= 1);
880
881                while (Q.size() > (1 + ((neg == nullptr) ? 1 : 0))) {
882                    PabloAST * a1 = Q.front(); Q.pop_front(); assert (a1);
883                    PabloAST * a2 = Q.front(); Q.pop_front(); assert (a2);
884
885                    assert (!Q.full());
886                    PabloAST * tmp = pb->createAnd(a1, a2); assert (tmp);
887                    Q.push_back(tmp);
888                }
889
890                assert (Q.size() >= 0 && Q.size() <= 2);
891
892                PabloAST * a1 = Q.front(); Q.pop_front(); assert (a1);
893                PabloAST * a2 = neg;
894                if (LLVM_UNLIKELY(neg == nullptr)) {
895                    a2 = Q.front(); Q.pop_front(); assert (a2);
896                }
897                assert (Q.empty());
898
899                pb->setInsertPoint(choose(a2, a1, adv));
900                PabloAST * demux = pb->createAnd(a1, a2, "demux_" + V[i - 1]->getName()->to_string());
901
902                V[i - 1]->replaceWith(demux, false);
903            }
904        }
905    }
906}
907
908/** ------------------------------------------------------------------------------------------------------------- *
909 * @brief topologicalSort
910 *
911 * After transforming the IR, we need to run this in order to always have a valid program. Each multiplex set
912 * contains vertices corresponding to an Advance in the IR. While we know each Advance within a set is independent
913 * w.r.t. the transitive closure of their dependencies in the IR, the position of each Advance's dependencies and
914 * users within the IR isn't taken into consideration. Thus while there must be a valid ordering for the program,
915 * it's not necessarily the original ordering.
916 ** ------------------------------------------------------------------------------------------------------------- */
917void AutoMultiplexing::topologicalSort(PabloBlock & entry) const {
918
919    // Note: not a real topological sort. I expect the original order to be very close to the resulting one.
920
921    std::unordered_set<PabloAST *> encountered;
922    std::stack<Statement *> scope;
923    for (Statement * stmt = entry.front(); ; ) {
924
925        while ( stmt ) {
926
927            bool moved = false;
928
929            for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
930                PabloAST * const op = stmt->getOperand(i);
931                if (LLVM_LIKELY(isa<Statement>(op))) {
932                    if (LLVM_UNLIKELY(encountered.count(op) == 0)) {
933                        Statement * next = stmt->getNextNode();
934                        stmt->insertAfter(cast<Statement>(op));
935                        stmt = next;
936                        moved = true;
937                        break;
938                    }
939                }
940            }
941
942            if (moved) {
943                continue;
944            }
945
946            encountered.insert(stmt);
947
948            if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
949                // Set the next statement to be the first statement of the inner scope and push the
950                // next statement of the current statement into the scope stack.
951                const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
952                scope.push(stmt->getNextNode());
953                stmt = nested.front();
954                assert (stmt);
955                continue;
956            }
957
958            stmt = stmt->getNextNode();
959        }
960
961        if (scope.empty()) {
962            break;
963        }
964        stmt = scope.top();
965        scope.pop();
966    }
967
968}
969
970} // end of namespace pablo
971
Note: See TracBrowser for help on using the repository browser.