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

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

Added the ability to compute all unique combinations of potential multiplexing sets.

File size: 48.9 KB
Line 
1#include "pablo_automultiplexing.hpp"
2#include <pablo/codegenstate.h>
3#include <llvm/ADT/BitVector.h>
4#include <stack>
5#include <queue>
6#include <unordered_set>
7#include <boost/container/flat_set.hpp>
8#include <unordered_map>
9#include <boost/numeric/ublas/matrix.hpp>
10#include <boost/circular_buffer.hpp>
11#include <include/simd-lib/builtins.hpp>
12#include <pablo/expression_map.hpp>
13#include <pablo/printer_pablos.h>
14#include <iostream>
15#include <cudd.h>
16#include <util.h>
17
18using namespace llvm;
19using namespace boost;
20using namespace boost::container;
21using namespace boost::numeric::ublas;
22
23#define USE_WEIGHTED_SELECTION
24
25namespace pablo {
26
27typedef uint64_t timestamp_t;
28
29static inline timestamp_t read_cycle_counter() {
30#ifdef __GNUC__
31timestamp_t ts;
32#ifdef __x86_64__
33  unsigned int eax, edx;
34  asm volatile("rdtsc" : "=a" (eax), "=d" (edx));
35  ts = ((timestamp_t) eax) | (((timestamp_t) edx) << 32);
36#else
37  asm volatile("rdtsc\n" : "=A" (ts));
38#endif
39  return(ts);
40#endif
41#ifdef _MSC_VER
42  return __rdtsc();
43#endif
44}
45
46
47bool AutoMultiplexing::optimize(const std::vector<Var *> & input, PabloBlock & entry) {
48    bool modified = false;
49    AutoMultiplexing am;
50    const timestamp_t start = read_cycle_counter();
51    am.initialize(input, entry);
52    const timestamp_t end_initialize = read_cycle_counter();
53    am.characterize(entry);
54    const timestamp_t end_characterize = read_cycle_counter();
55    am.shutdown();
56    const timestamp_t end_shutdown = read_cycle_counter();
57    am.createMultiplexSetGraph();
58    std::random_device rd;
59    RNG rng(rd());
60    const bool multiplex = am.generateMultiplexSets(rng);
61    const timestamp_t end_create_multiplex_graph = read_cycle_counter();
62    timestamp_t end_mwis = end_create_multiplex_graph,
63            end_subset_constraints = end_create_multiplex_graph,
64            end_select_independent_sets = end_create_multiplex_graph,
65            end_topological_sort = end_create_multiplex_graph;
66
67    if (multiplex) {
68        am.approxMaxWeightIndependentSet(rng);
69        end_mwis = read_cycle_counter();
70        am.applySubsetConstraints();
71        end_subset_constraints = read_cycle_counter();
72        am.multiplexSelectedIndependentSets();
73        end_select_independent_sets = read_cycle_counter();
74        am.topologicalSort(entry);
75        end_topological_sort = read_cycle_counter();
76        modified = true;
77    }
78
79    std::cerr << "Initialize:              " << (end_initialize - start) << std::endl;
80    std::cerr << "Characterize:            " << (end_characterize - end_initialize) << std::endl;
81    std::cerr << "Shutdown:                " << (end_shutdown - end_characterize) << std::endl;
82    std::cerr << "GenerateMultiplexSets:   " << (end_create_multiplex_graph - end_shutdown) << std::endl;
83    std::cerr << "MaxWeightIndependentSet: " << (end_mwis - end_create_multiplex_graph) << std::endl;
84    std::cerr << "ApplySubsetConstraints:  " << (end_subset_constraints - end_mwis) << std::endl;
85    std::cerr << "MultiplexSelectedSets:   " << (end_select_independent_sets - end_subset_constraints) << std::endl;
86    std::cerr << "TopologicalSort:         " << (end_topological_sort - end_select_independent_sets) << std::endl;
87
88
89    return modified;
90}
91
92/** ------------------------------------------------------------------------------------------------------------- *
93 * @brief initialize
94 * @param vars the input vars for this program
95 * @param entry the entry block
96 *
97 * Scan through the program to identify any advances and calls then initialize the BDD engine with
98 * the proper variable ordering.
99 ** ------------------------------------------------------------------------------------------------------------- */
100void AutoMultiplexing::initialize(const std::vector<Var *> & vars, const PabloBlock & entry) {
101
102    flat_map<const PabloAST *, unsigned> map;
103    std::vector<const Statement *> complexStatements;
104    std::stack<const Statement *> scope;
105
106    // Scan through and collect all the advances, calls, scanthrus and matchstars ...
107    unsigned n = 0, m = 0;
108    for (const Statement * stmt = entry.front(); ; ) {
109        while ( stmt ) {
110            ++n;
111            if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
112                // Set the next statement to be the first statement of the inner scope and push the
113                // next statement of the current statement into the scope stack.
114                const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
115                scope.push(stmt->getNextNode());
116                stmt = nested.front();
117                assert (stmt);
118                continue;
119            }
120
121            assert ("Run the Simplifer pass prior to this!" && (stmt->getNumUses() != 0 || (isa<Assign>(stmt) ? !cast<Assign>(stmt)->superfluous() : false)));
122
123            switch (stmt->getClassTypeId()) {
124                case PabloAST::ClassTypeId::Advance:                   
125                    mAdvance.push_back(const_cast<Advance*>(cast<Advance>(stmt)));
126                    map.emplace(stmt, m++);
127                case PabloAST::ClassTypeId::Call:
128                case PabloAST::ClassTypeId::ScanThru:
129                case PabloAST::ClassTypeId::MatchStar:
130                    complexStatements.push_back(stmt);
131                    break;
132                default:
133                    break;
134            }
135            stmt = stmt->getNextNode();
136        }
137        if (scope.empty()) {
138            break;
139        }
140        stmt = scope.top();
141        scope.pop();
142    }
143
144    // Create the transitive closure matrix of graph. From this we'll construct
145    // two graphs restricted to the relationships between advances. The first will
146    // be a path graph, which is used to bypass testing for mutual exclusivity of
147    // advances that cannot be multiplexed. The second is a transitive reduction
148    // of that graph, which forms the basis of our constraint graph when deciding
149    // which advances ought to be multiplexed.
150
151    matrix<bool> G(n, m); // Let G be a matrix with n rows of m (Advance) elements
152    G.clear();
153    for (unsigned i = 0; i != m; ++i) {
154        G(i, i) = true;
155    }
156
157    n = m;
158    m = 0;
159
160    const Statement * stmt = entry.front();
161    for (;;) {
162        while ( stmt ) {
163
164            unsigned u;
165            if (isa<Advance>(stmt)) {
166                assert (mAdvance[m] == stmt);
167                u = m++;
168            }
169            else {
170                u = n++;
171                map.emplace(stmt, u);
172            }
173
174            for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
175                const PabloAST * const op = stmt->getOperand(i);
176                if (LLVM_LIKELY(isa<Statement>(op))) {
177                    const unsigned v = map[op];
178                    for (unsigned w = 0; w != m; ++w) {
179                        G(u, w) |= G(v, w);
180                    }
181                }
182            }
183            if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
184                // Set the next statement to be the first statement of the inner scope
185                // and push the next statement of the current statement into the stack.
186                const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
187                scope.push(stmt->getNextNode());
188                stmt = nested.front();
189                assert (stmt);
190                continue;
191            }
192            stmt = stmt->getNextNode();
193        }
194        if (scope.empty()) {
195            break;
196        }
197        stmt = scope.top();
198        scope.pop();
199    }
200
201    // Record our transitive closure in the path graph and remove any reflexive-loops
202    mPathGraph = PathGraph(m);
203    for (unsigned i = 0; i != m; ++i) {
204        G(i, i) = false;
205        for (unsigned j = 0; j != m; ++j) {
206            if (G(i, j)) {
207                add_edge(i, j, mPathGraph);
208            }
209        }       
210    }
211
212    // Now take the transitive reduction of G
213    for (unsigned j = 0; j != m; ++j) {
214        for (unsigned i = 0; i != m; ++i) {
215            if (G(i, j)) {
216                // Eliminate any unecessary arcs not covered by a longer path
217                for (unsigned k = 0; k != m; ++k) {
218                    G(i, k) = G(j, k) ? false : G(i, k);
219                }
220            }
221        }
222    }
223
224    // And now transcribe it into our base constraint graph. Since G is a use-def
225    // graph and we want our constraint graph to be a def-use graph, reverse the
226    // edges as we're writing them to obtain the transposed graph.
227    mConstraintGraph = ConstraintGraph(m);
228    mSubsetGraph = SubsetGraph(m);
229    for (unsigned j = 0; j != m; ++j) {
230        for (unsigned i = 0; i != m; ++i) {
231            if (G(i, j)) {
232                add_edge(j, i, mConstraintGraph);
233            }
234        }
235    }
236
237    // Initialize the BDD engine ...
238    mManager = Cudd_Init((complexStatements.size() + vars.size()), 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0);
239    Cudd_AutodynDisable(mManager);
240
241    // Map the predefined 0/1 entries
242    mCharacterizationMap.emplace(entry.createZeroes(), Zero());
243    mCharacterizationMap.emplace(entry.createOnes(), One());
244
245    // Order the variables so the input Vars are pushed to the end; they ought to
246    // be the most complex to resolve.
247    unsigned i = 0;
248    for (const Statement * stmt : complexStatements) {
249        mCharacterizationMap.emplace(stmt, Cudd_bddIthVar(mManager, i++));
250    }
251    for (const Var * var : vars) {
252        mCharacterizationMap.emplace(var, Cudd_bddIthVar(mManager, i++));
253    }
254}
255
256/** ------------------------------------------------------------------------------------------------------------- *
257 * @brief characterize
258 * @param vars the input vars for this program
259 *
260 * Scan through the program and iteratively compute the BDDs for each statement.
261 ** ------------------------------------------------------------------------------------------------------------- */
262void AutoMultiplexing::characterize(PabloBlock & entry) {
263
264    std::vector<std::pair<DdNode *, DdNode *>> advances; // the input BDD and the BDD variable of the i-th Advance
265    std::stack<Statement *> scope;
266    std::vector<bool> unconstrained(mAdvance.size());
267    advances.reserve(mAdvance.size());
268
269    // TODO: What if we did some minterm analysis in here? We'd need to be careful to keep the Advances properly indexed.
270
271    unsigned comparisons = 0;
272    unsigned avoided = 0;
273
274    // Scan through and collect all the advances, calls, scanthrus and matchstars ...
275    for (Statement * stmt = entry.front(); ; ) {
276        while ( stmt ) {
277
278            if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
279                // Set the next statement to be the first statement of the inner scope and push the
280                // next statement of the current statement into the scope stack.
281                const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
282                scope.push(stmt->getNextNode());
283                stmt = nested.front();
284                continue;
285            }
286
287            DdNode * bdd = nullptr;
288            // Map our operands to the computed BDDs
289            std::array<DdNode *, 3> input;
290            for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
291                PabloAST * const op = stmt->getOperand(i);
292                if (LLVM_UNLIKELY(isa<Integer>(op) || isa<String>(op))) {
293                    continue;
294                }
295                auto f = mCharacterizationMap.find(op);
296                if (LLVM_UNLIKELY(f == mCharacterizationMap.end())) {
297                    throw std::runtime_error("Uncharacterized operand " + std::to_string(i) + " of " + stmt->getName()->to_string());
298                }
299                input[i] = f->second;
300            }
301
302            bool testContradiction = true;
303            bool updateVariable = true;
304
305            switch (stmt->getClassTypeId()) {
306                case PabloAST::ClassTypeId::Assign:
307                    bdd = input[0];
308                    break;
309                case PabloAST::ClassTypeId::And:
310                    bdd = And(input[0], input[1]);
311                    break;
312                case PabloAST::ClassTypeId::Next:
313                    // The next instruction is almost identical to an OR; however, a Next cannot be
314                    // an operand of a Statement. Instead it updates the Initial operand's value.
315                    testContradiction = false;
316                case PabloAST::ClassTypeId::Or:           
317                    bdd = Or(input[0], input[1]);
318                    break;
319                case PabloAST::ClassTypeId::Xor:
320                    bdd = Xor(input[0], input[1]);
321                    break;
322                case PabloAST::ClassTypeId::Not:
323                    bdd = Not(input[0]);
324                    break;
325                case PabloAST::ClassTypeId::Sel:
326                    bdd = Ite(input[0], input[1], input[2]);
327                    break;
328                case PabloAST::ClassTypeId::ScanThru:
329                    // It may be possible use "Not(input[1])" for ScanThrus if we rule out the possibility
330                    // of a contradition being erroneously calculated later. An example of this
331                    // would be ¬(ScanThru(c,m) √ m)
332                case PabloAST::ClassTypeId::MatchStar:
333                    if (LLVM_UNLIKELY(isZero(input[0]) || isZero(input[1]))) {
334                        bdd = Zero();
335                        break;
336                    }
337                case PabloAST::ClassTypeId::Call:
338                    testContradiction = false;
339                    updateVariable = false;
340                    break;
341                case PabloAST::ClassTypeId::Advance:
342                    assert (stmt == mAdvance[advances.size()]);
343                    if (LLVM_UNLIKELY(isZero(input[0]))) {
344                        bdd = input[0];
345                        advances.emplace_back(bdd, bdd);
346                    }
347                    else {
348
349                        // When we built the path graph, we constructed it in the same order; hense the row/column of
350                        // the path graph is equivalent to the index.
351
352                        assert (mCharacterizationMap.count(stmt));
353                        DdNode * const Ik = input[0];
354                        DdNode * Ck = mCharacterizationMap[stmt];
355                        DdNode * const Nk = Not(Ck);
356
357                        const unsigned k = advances.size();
358
359                        std::fill(unconstrained.begin(), unconstrained.end(), false);
360
361                        // Instead of processing these sequentially, look at the existing subset relationships incase we can infer
362                        // more things sooner?
363                        for (unsigned i = 0; i != k; ++i) {
364
365                            Advance * adv = mAdvance[i];
366
367                            // Only test pairs if they are in the same scope or one has a user in the a scope that is reachable by
368                            // the other?
369
370                            bool constrained = !unconstrained[i];
371
372                            // If these advances are "shifting" their values by the same amount and aren't transitively dependant ...
373                            if (constrained && (stmt->getOperand(1) == adv->getOperand(1)) && (notTransitivelyDependant(k, i))) {
374                                ++comparisons;
375                                DdNode * Ii = std::get<0>(advances[i]);
376                                DdNode * Ni = std::get<1>(advances[i]);
377                                // TODO: test both Cudd_And and Cudd_bddIntersect to see which is faster
378                                DdNode * const IiIk = Intersect(Ik, Ii);
379                                // Is there any satisfying truth assignment? If not, these streams are mutually exclusive.
380                                if (noSatisfyingAssignment(IiIk)) {
381                                    assert (mCharacterizationMap.count(adv));
382                                    DdNode *& Ci = mCharacterizationMap[adv];
383                                    // Mark the i-th and k-th Advances as being mutually exclusive
384                                    Ck = And(Ck, Ni);
385                                    Ci = And(Ci, Nk);
386                                    // If Ai ∩ Ak = ∅ and Aj ⊂ Ai, Aj ∩ Ak = ∅.
387                                    graph_traits<SubsetGraph>::in_edge_iterator ei, ei_end;
388                                    for (std::tie(ei, ei_end) = in_edges(i, mSubsetGraph); ei != ei_end; ++ei) {
389                                        const auto j = source(*ei, mSubsetGraph);
390                                        if (j > i && notTransitivelyDependant(k, j)) {
391                                            Advance * adv = mAdvance[j];
392                                            assert (mCharacterizationMap.count(adv));
393                                            DdNode *& Cj = mCharacterizationMap[adv];
394                                            DdNode * Nj = std::get<1>(advances[j]);
395                                            // Mark the i-th and j-th Advances as being mutually exclusive
396                                            Ck = And(Ck, Nj);
397                                            Cj = And(Cj, Nk);
398                                            unconstrained[j] = true;
399                                            ++avoided;
400                                        }
401                                    }
402                                    constrained = false;
403                                }
404                                else if (Ik == IiIk) {
405                                    // If Ik = Ii ∩ Ik then Ik ⊂ Ii. Record this in the subset graph with the arc (k,i).
406                                    // These edges will be moved into the multiplex set graph if Ai and Ak happen to be
407                                    // in the same mutually exclusive set.
408                                    add_edge(k, i, mSubsetGraph);
409                                    // If Ak ⊂ Ai and Ai ⊂ Aj, Ak ⊂ Aj.
410                                    graph_traits<SubsetGraph>::out_edge_iterator ei, ei_end;
411                                    for (std::tie(ei, ei_end) = out_edges(i, mSubsetGraph); ei != ei_end; ++ei) {
412                                        const auto j = target(*ei, mSubsetGraph);
413                                        if (j > i) {
414                                            add_edge(k, j, mSubsetGraph);
415                                            unconstrained[j] = true;
416                                            ++avoided;
417                                        }
418                                    }
419                                    constrained = false;
420                                }
421                                else if (Ii == IiIk) {
422                                    // If Ii = Ii ∩ Ik then Ii ⊂ Ik. Record this in the subset graph with the arc (i,k).
423                                    add_edge(i, k, mSubsetGraph);
424                                    // If Ai ⊂ Ak and Aj ⊂ Ai, Aj ⊂ Ak.
425                                    graph_traits<SubsetGraph>::in_edge_iterator ei, ei_end;
426                                    for (std::tie(ei, ei_end) = in_edges(i, mSubsetGraph); ei != ei_end; ++ei) {
427                                        const auto j = source(*ei, mSubsetGraph);
428                                        if (j > i) {
429                                            add_edge(j, k, mSubsetGraph);
430                                            unconstrained[j] = true;
431                                            ++avoided;
432                                        }
433                                    }
434                                    constrained = false;
435                                }
436                                Cudd_RecursiveDeref(mManager, IiIk);
437                            }
438
439                            // Even if these Advances are mutually exclusive, they must be in the same scope or they cannot be safely multiplexed.
440                            if (constrained || (stmt->getParent() != adv->getParent())) {
441                                // We want the constraint graph to be acyclic; since the dependencies are already in topological order,
442                                // adding an arc from a lesser to greater numbered vertex won't induce a cycle.
443                                add_edge(i, k, mConstraintGraph);
444                            }
445
446                        }
447                        // Append this advance to the list of known advances. Both its input BDD and the Advance variable are stored in
448                        // the list to eliminate the need for searching for it.
449                        advances.emplace_back(Ik, Nk);
450                        testContradiction = false;
451                        bdd = Ck;
452                    }
453                    break;
454                default:
455                    throw std::runtime_error("Unexpected statement type " + stmt->getName()->to_string());
456            }
457            assert ("Failed to generate a BDD." && (bdd || !(testContradiction || updateVariable)));
458            if (LLVM_LIKELY(updateVariable)) {
459                mCharacterizationMap[stmt] = bdd;
460            }
461            if (LLVM_UNLIKELY(testContradiction && noSatisfyingAssignment(bdd))) {               
462                if (!isa<Assign>(stmt)) {
463                    Cudd_RecursiveDeref(mManager, bdd);
464                    stmt = stmt->replaceWith(entry.createZeroes());
465                    continue;
466                }
467            }
468            stmt = stmt->getNextNode();
469        }
470
471        if (scope.empty()) {
472            break;
473        }
474        stmt = scope.top();
475        scope.pop();
476    }
477
478    std::cerr << "comparisons: " << comparisons << ", avoided: " << avoided << std::endl;
479}
480
481/** ------------------------------------------------------------------------------------------------------------- *
482 * @brief notTransitivelyDependant
483 ** ------------------------------------------------------------------------------------------------------------- */
484inline bool AutoMultiplexing::notTransitivelyDependant(const PathGraph::vertex_descriptor i, const PathGraph::vertex_descriptor j) const {
485    return (mPathGraph.get_edge(i, j) == 0);
486}
487
488/** ------------------------------------------------------------------------------------------------------------- *
489 * @brief CUDD wrappers
490 ** ------------------------------------------------------------------------------------------------------------- */
491
492inline DdNode * AutoMultiplexing::Zero() const {
493    return Cudd_ReadLogicZero(mManager);
494}
495
496inline DdNode * AutoMultiplexing::One() const {
497    return Cudd_ReadOne(mManager);
498}
499
500inline bool AutoMultiplexing::isZero(DdNode * const x) const {
501    return x == Zero();
502}
503
504inline DdNode * AutoMultiplexing::And(DdNode * const x, DdNode * const y) {
505    DdNode * r = Cudd_bddAnd(mManager, x, y);
506    Cudd_Ref(r);
507    return r;
508}
509
510inline DdNode * AutoMultiplexing::Intersect(DdNode * const x, DdNode * const y) {
511    DdNode * r = Cudd_bddIntersect(mManager, x, y); Cudd_Ref(r);
512    return r;
513}
514
515inline DdNode * AutoMultiplexing::Or(DdNode * const x, DdNode * const y) {
516    DdNode * r = Cudd_bddOr(mManager, x, y);
517    Cudd_Ref(r);
518    return r;
519}
520
521inline DdNode * AutoMultiplexing::Xor(DdNode * const x, DdNode * const y) {
522    DdNode * r = Cudd_bddXor(mManager, x, y);
523    Cudd_Ref(r);
524    return r;
525}
526
527inline DdNode * AutoMultiplexing::Not(DdNode * const x) const {
528    return Cudd_Not(x);
529}
530
531inline DdNode * AutoMultiplexing::Ite(DdNode * const x, DdNode * const y, DdNode * const z) {
532    DdNode * r = Cudd_bddIte(mManager, x, y, z);
533    Cudd_Ref(r);
534    return r;
535}
536
537inline bool AutoMultiplexing::noSatisfyingAssignment(DdNode * const x) {
538    return Cudd_bddLeq(mManager, x, Zero());
539}
540
541inline void AutoMultiplexing::shutdown() {
542    Cudd_Quit(mManager);
543}
544
545/** ------------------------------------------------------------------------------------------------------------- *
546 * @brief createMultiplexSetGraph
547 ** ------------------------------------------------------------------------------------------------------------- */
548void AutoMultiplexing::createMultiplexSetGraph() {
549    mMultiplexSetGraph = MultiplexSetGraph(num_vertices(mConstraintGraph));
550}
551
552/** ------------------------------------------------------------------------------------------------------------- *
553 * @brief generateMultiplexSets
554 * @param RNG random number generator
555 ** ------------------------------------------------------------------------------------------------------------- */
556bool AutoMultiplexing::generateMultiplexSets(RNG & rng) {
557
558    using Vertex = ConstraintGraph::vertex_descriptor;
559    using VertexIterator = graph_traits<ConstraintGraph>::vertex_iterator;
560    using EdgeIterator = graph_traits<ConstraintGraph>::out_edge_iterator;
561    using DegreeType = graph_traits<ConstraintGraph>::degree_size_type;
562
563    IndependentSet S, N;
564    auto remainingVerticies = num_vertices(mConstraintGraph);
565    std::vector<DegreeType> D(remainingVerticies);
566    S.reserve(15);
567    N.reserve(15);
568
569    // Push all source nodes into the new independent set N
570    VertexIterator vi, vi_end;
571    for (std::tie(vi, vi_end) = vertices(mConstraintGraph); vi != vi_end; ++vi) {
572        const auto d = in_degree(*vi, mConstraintGraph);
573        D[*vi] = d;
574        if (d == 0) {
575            N.push_back(*vi);
576        }
577    }
578
579    while ( remainingVerticies >= 3 ) {
580
581
582        // If we have at least 3 vertices in our two sets, try adding them to our
583        // multiplexing set.
584        if ((N.size() + S.size()) >= 3) {
585            addMultiplexSet(N, S);
586        }       
587
588        // Move all of our "newly" uncovered vertices into the "known" set. By always
589        // choosing at least one element from N, this will prevent us from adding the
590        // same multiplexing set again.
591        S.insert(S.end(), N.begin(), N.end()); N.clear();
592
593        do {
594            // Randomly choose a vertex in S and discard it.
595            assert (!S.empty());
596            const auto i = S.begin() + RNGDistribution(0, S.size() - 1)(rng);
597            const Vertex u = *i;
598            S.erase(i);
599            --remainingVerticies;
600            EdgeIterator ei, ei_end;
601            for (std::tie(ei, ei_end) = out_edges(u, mConstraintGraph); ei != ei_end; ++ei) {
602                const Vertex v = target(*ei, mConstraintGraph);
603                if ((--D[v]) == 0) {
604                    N.push_back(v);
605                }
606            }
607        }
608        while (N.empty() && remainingVerticies >= 3);
609    }
610
611    return num_vertices(mMultiplexSetGraph) > num_vertices(mConstraintGraph);
612}
613
614/** ------------------------------------------------------------------------------------------------------------- *
615 * @brief is_power_of_2
616 * @param n an integer
617 ** ------------------------------------------------------------------------------------------------------------- */
618static inline bool is_power_of_2(const size_t n) {
619    return ((n & (n - 1)) == 0) ;
620}
621
622/** ------------------------------------------------------------------------------------------------------------- *
623 * @brief addMultiplexSet
624 * @param N an independent set
625 * @param S an independent set
626 ** ------------------------------------------------------------------------------------------------------------- */
627inline void AutoMultiplexing::addMultiplexSet(const IndependentSet & N, const IndependentSet & S) {
628
629    // At this stage, the multiplex set graph is a directed bipartite graph that is used to show relationships
630    // between the "set vertex" and its members. We obtain these from "generateMultiplexSets".
631
632    // TODO: Instead of building a graph, construct a trie of all members of all combinations of S that are of size
633    // >= 3 and not 2^n for any n.
634
635    // This will give us <= (∑i=1 to |N| C(|N|,i)) * [1 + (∑i=1 to |M| C(|M|,i))] combinations. It seems to improve
636    // the potential result but make the MaxWeightIndependentSet far more costly. Look into a method without explicit
637    // vertex deletion.
638
639    for (int i = 0; i < N.size(); ++i) {
640        mCurrentCombination.push_back(N[i]);
641        addMultiplexSet(N, i + 1, S, 0);
642        assert (mCurrentCombination.back() == N[i]);
643        mCurrentCombination.pop_back();
644    }
645}
646
647/** ------------------------------------------------------------------------------------------------------------- *
648 * @brief addMultiplexSet
649 * @param N an independent set
650 * @param S an independent set
651 ** ------------------------------------------------------------------------------------------------------------- */
652void AutoMultiplexing::addMultiplexSet(const IndependentSet & N, const int i,
653                                       const IndependentSet & S, const int j) {
654
655    // At this stage, the multiplex set graph is a directed bipartite graph that is used to show relationships
656    // between the "set vertex" and its members. We obtain these from "generateMultiplexSets".
657
658    // TODO: Instead of building a graph, construct a trie of all members of all combinations of S that are of size
659    // >= 3 and not 2^n for any n.
660
661    if (mCurrentCombination.size() >= 3 && !is_power_of_2(mCurrentCombination.size())) {
662        const auto v = add_vertex(mMultiplexSetGraph);
663        for (auto u : mCurrentCombination) {
664            add_edge(v, u, mMultiplexSetGraph);
665        }
666    }
667
668    for (int ii = i; ii < N.size(); ++ii) {
669        mCurrentCombination.push_back(N[ii]);
670        addMultiplexSet(N, ii + 1, S, j);
671        assert (mCurrentCombination.back() == N[ii]);
672        mCurrentCombination.pop_back();
673    }
674
675    for (int jj = j; jj < S.size(); ++jj) {
676        mCurrentCombination.push_back(S[jj]);
677        addMultiplexSet(N, i + 1, S, jj + 1);
678        assert (mCurrentCombination.back() == S[jj]);
679        mCurrentCombination.pop_back();
680    }
681
682}
683
684/** ------------------------------------------------------------------------------------------------------------- *
685 * @brief approxMaxWeightIndependentSet
686 * @param RNG random number generator
687 ** ------------------------------------------------------------------------------------------------------------- */
688void AutoMultiplexing::approxMaxWeightIndependentSet(RNG & rng) {
689
690    // Compute our independent set graph from our multiplex set graph; effectively it's the graph resulting
691    // from contracting one advance node edge with an adjacent vertex
692
693    const unsigned m = num_vertices(mConstraintGraph);
694    const unsigned n = num_vertices(mMultiplexSetGraph) - m;
695
696    IndependentSetGraph G(n);
697
698    std::unordered_map<MultiplexSetGraph::vertex_descriptor, IndependentSetGraph::vertex_descriptor> M;
699    MultiplexSetGraph::vertex_descriptor i = m;
700    graph_traits<IndependentSetGraph>::vertex_iterator vi, vi_end;
701    for (std::tie(vi, vi_end) = vertices(G); vi != vi_end; ++vi, ++i) {
702        M.emplace(i, *vi);
703        G[*vi] = std::make_tuple(out_degree(i, mMultiplexSetGraph), 0, i);
704    }
705
706    // Let M be mMultiplexSetGraph. Each vertex in G corresponds to a set vertex in M.
707    // If an advance vertex in M (i.e., one of the first m vertices of M) is adjacent
708    // to two or more set vertices, add an edge between the corresponding vertices in G.
709    // I.e., make all vertices in G adjacent if their corresponding sets intersect.
710
711    for (i = 0; i != m; ++i) {
712        if (in_degree(i, mMultiplexSetGraph) > 1) {
713            graph_traits<MultiplexSetGraph>::in_edge_iterator ei_begin, ei_end;
714            std::tie(ei_begin, ei_end) = in_edges(i, mMultiplexSetGraph);
715            for (auto ei = ei_begin; ei != ei_end; ++ei) {
716                for (auto ej = ei_begin; ej != ei; ++ej) {
717                    // Note: ei and ej are incoming edges. The source is the set vertex,
718                    add_edge(M[source(*ei, mMultiplexSetGraph)], M[source(*ej, mMultiplexSetGraph)], G);
719                }
720            }
721        }
722    }
723
724    // Using WMIN from "A note on greedy algorithms for the maximum weighted independent set problem"
725    // (Note: look into minimum independent dominating set algorithms. It fits better with the ceil log2 + subset cost model.)
726
727    std::vector<IndependentSetGraph::vertex_descriptor> A;
728
729    while (num_vertices(G) > 0) {
730
731        // Select a vertex vi whose weight as greater than the average weight of its neighbours ...
732        #ifdef USE_WEIGHTED_SELECTION
733        int Tw = 0;
734        for (std::tie(vi, vi_end) = vertices(G); vi != vi_end; ++vi) {
735            int Vw = std::get<0>(G[*vi]) * (degree(*vi, G) + 1);
736            int Nw = 0;
737            graph_traits<IndependentSetGraph>::adjacency_iterator ai, ai_end;
738            std::tie(ai, ai_end) = adjacent_vertices(*vi, G);
739            for (; ai != ai_end; ++ai) {
740                Nw += std::get<0>(G[*ai]);
741            }
742            Vw = std::max<int>(Vw - Nw, 0);
743            Vw *= Vw;
744            std::get<1>(G[*vi]) = Vw;
745            Tw += Vw;
746        }
747
748        int w = RNGDistribution(0, Tw - 1)(rng);
749        for (std::tie(vi, vi_end) = vertices(G); vi != vi_end; ++vi) {
750            w -= std::get<1>(G[*vi]);
751            if (w < 0) {
752                break;
753            }
754        }
755        #else
756        auto i = RNGDistribution(1, num_vertices(G))(rng);
757        for (std::tie(vi, vi_end) = vertices(G); --i != 0; ++vi);
758        #endif
759        assert (vi != vi_end);
760
761        // Then add it to our set and remove it and its neighbourhood from G
762        A.reserve(degree(*vi, G) + 1);
763        // Note: by clearing the adjacent set vertices from the multiplex set graph, this will effectively
764        // choose the set refered to by vi as one of our chosen independent sets.
765        graph_traits<IndependentSetGraph>::adjacency_iterator ai, ai_end;
766        A.push_back(*vi);
767        for (std::tie(ai, ai_end) = adjacent_vertices(*vi, G); ai != ai_end; ++ai) {
768            clear_out_edges(std::get<2>(G[*ai]), mMultiplexSetGraph);
769            A.push_back(*ai);
770        }
771        for (auto u : A) {
772            clear_vertex(u, G);
773            remove_vertex(u, G);
774        }
775        A.clear();
776    }
777
778    for (unsigned i = m; i != (m + n); ++i) {
779        if (out_degree(i, mMultiplexSetGraph) > 0) {
780            std::cerr << out_degree(i, mMultiplexSetGraph) << std::endl;
781        }
782    }
783
784    #ifndef NDEBUG
785    for (unsigned i = 0; i != m; ++i) {
786        assert (in_degree(i, mMultiplexSetGraph) <= 1);
787    }
788    for (unsigned i = m; i != (m + n); ++i) {
789        assert (out_degree(i, mMultiplexSetGraph) == 0 || out_degree(i, mMultiplexSetGraph) >= 3);
790    }
791    #endif
792}
793
794/** ------------------------------------------------------------------------------------------------------------- *
795 * @brief choose
796 ** ------------------------------------------------------------------------------------------------------------- */
797
798inline Statement * choose(PabloAST * x, PabloAST * y, Statement * z) {
799    return isa<Statement>(x) ? cast<Statement>(x) : (isa<Statement>(y) ? cast<Statement>(y) : z);
800}
801
802/** ------------------------------------------------------------------------------------------------------------- *
803 * @brief applySubsetConstraints
804 ** ------------------------------------------------------------------------------------------------------------- */
805void AutoMultiplexing::applySubsetConstraints() {
806
807    // When entering thus function, the multiplex set graph M is a bipartite DAG with edges denoting the set
808    // relationships of our independent sets.
809    const unsigned m = num_vertices(mConstraintGraph);
810    const unsigned n = num_vertices(mMultiplexSetGraph);
811
812    // Add in any edges from our subset constraints to M that are within the same set.
813    bool hasSubsetConstraint = false;
814
815    graph_traits<SubsetGraph>::edge_iterator ei, ei_end;
816    for (std::tie(ei, ei_end) = edges(mSubsetGraph); ei != ei_end; ++ei) {
817        const auto u = source(*ei, mSubsetGraph);
818        const auto v = target(*ei, mSubsetGraph);
819        graph_traits<MultiplexSetGraph>::in_edge_iterator ej, ej_end;
820        // If both the source and target of ei are adjacent to the same vertex, that vertex must be the
821        // "set vertex". Add the edge between the vertices.
822        for (std::tie(ej, ej_end) = in_edges(u, mMultiplexSetGraph); ej != ej_end; ++ej) {
823            auto w = target(*ej, mMultiplexSetGraph);
824            // Only check (v, w) if w is a "set vertex".
825            if (w >= (n - m) && edge(v, w, mMultiplexSetGraph).second) {
826                add_edge(u, v, mMultiplexSetGraph);
827                hasSubsetConstraint = true;
828            }
829        }
830    }
831
832    if (LLVM_UNLIKELY(hasSubsetConstraint)) {
833        // At this point, M is still a DAG but no longer bipartite. We're going to scan through the set vertices
834        // in M, and use a DFS to scan through M and eliminate any subset relationships in the AST.
835        // That way, "multiplexSelectedIndependentSets" only needs to consider muxing and demuxing of the streams.
836
837        std::vector<MultiplexSetGraph::vertex_descriptor> V;
838        std::stack<MultiplexSetGraph::vertex_descriptor> S;
839        std::queue<PabloAST *> Q;
840        BitVector D(n - m, 0);
841
842        for (auto i = m; i != n; ++i) {
843            graph_traits<MultiplexSetGraph>::out_edge_iterator ei, ei_end;
844            // For each member of a "set vertex" ...
845            std::tie(ei, ei_end) = out_edges(i, mMultiplexSetGraph);
846            for (; ei != ei_end; ++ei) {
847                const auto s = source(*ei, mMultiplexSetGraph);
848                if (out_degree(s, mMultiplexSetGraph) != 0) {
849                    // First scan through the subgraph of vertices in M dominated by s and build up the set T,
850                    // consisting of all sinks w.r.t. vertex s.
851                    auto u = s;
852                    for (;;) {
853                        graph_traits<MultiplexSetGraph>::out_edge_iterator ej, ej_end;
854                        for (std::tie(ej, ej_end) = out_edges(u, mMultiplexSetGraph); ej != ej_end; ++ej) {
855                            auto v = target(*ej, mMultiplexSetGraph);
856                            if (D.test(v)) {
857                                continue;
858                            }
859                            D.set(v);
860                            if (out_degree(v, mMultiplexSetGraph) == 0) {
861                                V.push_back(v);
862                            }
863                            else {
864                                S.push(v);
865                            }
866                        }
867                        if (S.empty()) {
868                            break;
869                        }
870                        u = S.top();
871                        S.pop();
872                    }
873                    D.clear();
874                    // Now in order for these advances to be mutually exclusive, the input to A_s must be masked
875                    // with the complement of each advance indicated by V.
876
877                    Advance * adv = mAdvance[s];
878                    PabloBlock * pb = adv->getParent();
879
880                    for (auto i : V) {
881                        Q.push(mAdvance[i]->getOperand(0));
882                    }                   
883                    while (Q.size() > 1) {
884                        PabloAST * a1 = Q.front(); Q.pop();
885                        PabloAST * a2 = Q.front(); Q.pop();
886                        pb->setInsertPoint(cast<Statement>(a2));
887                        Q.push(pb->createOr(a1, a2));
888                    }
889                    assert (Q.size() == 1);
890
891                    PabloAST * const mask = pb->createNot(Q.front()); Q.pop();
892                    adv->setOperand(0, pb->createAnd(adv->getOperand(0), mask, "subset_in"));
893
894                    // Similar to the above, we're going to OR together the result of each advance,
895                    // including s. This will restore the advanced variable back to its original state.
896
897                    // Gather the original users to this advance. We'll be manipulating it shortly.
898                    Statement::Users U(adv->users());
899
900                    // Add s to V and sort the list; it'll be closer to being in topological order.
901                    V.push_back(s);
902                    std::sort(V.begin(), V.end());
903                    for (auto i : V) {
904                        Q.push(mAdvance[i]);
905                    }
906                    while (Q.size() > 1) {
907                        PabloAST * a1 = Q.front(); Q.pop();
908                        PabloAST * a2 = Q.front(); Q.pop();
909                        pb->setInsertPoint(choose(a2, a1, adv));
910                        Q.push(pb->createOr(a1, a2));
911                    }
912                    assert (Q.size() == 1);
913
914                    PabloAST * const input = Q.front(); Q.pop();
915                    for (PabloAST * use : U) {
916                        if (LLVM_LIKELY(isa<Statement>(use))) {
917                            cast<Statement>(use)->replaceUsesOfWith(adv, input);
918                        }
919                    }
920
921                    pb->setInsertPoint(pb->back());
922
923                    V.clear();
924
925                }
926            }
927        }
928    }
929}
930
931/** ------------------------------------------------------------------------------------------------------------- *
932 * @brief log2_plus_one
933 ** ------------------------------------------------------------------------------------------------------------- */
934static inline size_t log2_plus_one(const size_t n) {
935    return std::log2<size_t>(n) + 1; // use a faster builtin function for this?
936}
937
938/** ------------------------------------------------------------------------------------------------------------- *
939 * @brief multiplexSelectedIndependentSets
940 ** ------------------------------------------------------------------------------------------------------------- */
941void AutoMultiplexing::multiplexSelectedIndependentSets() const {
942
943    const unsigned f = num_vertices(mConstraintGraph);
944    const unsigned l = num_vertices(mMultiplexSetGraph);
945
946    // Preallocate the structures based on the size of the largest multiplex set
947    size_t max_n = 3;
948    for (unsigned s = f; s != l; ++s) {
949        max_n = std::max<unsigned>(max_n, out_degree(s, mMultiplexSetGraph));
950    }
951    const size_t max_m = log2_plus_one(max_n);
952
953    std::vector<MultiplexSetGraph::vertex_descriptor> I(max_n);
954    std::vector<Advance *> V(max_n);
955    std::vector<PabloAST *> muxed(max_m);
956    circular_buffer<PabloAST *> Q(max_n);
957
958    // When entering thus function, the multiplex set graph M is a DAG with edges denoting the set
959    // relationships of our independent sets.
960
961    for (unsigned s = f; s != l; ++s) {
962        const size_t n = out_degree(s, mMultiplexSetGraph);
963        if (n) {
964
965            const size_t m = log2_plus_one(n);
966
967            graph_traits<MultiplexSetGraph>::out_edge_iterator ei, ei_end;
968            std::tie(ei, ei_end) = out_edges(s, mMultiplexSetGraph);
969            for (unsigned i = 0; i != n; ++ei, ++i) {
970                I[i] = target(*ei, mMultiplexSetGraph);
971                assert (I[i] < mAdvance.size());
972            }
973            std::sort(I.begin(), I.begin() + n);
974
975            for (unsigned i = 0; i != n; ++i) {
976                V[i] = mAdvance[I[i]];
977            }
978
979            PabloBlock * const pb = V[0]->getParent();
980            assert (pb);
981
982            // Sanity test to make sure every advance is in the same scope.
983            #ifndef NDEBUG
984            for (unsigned i = 1; i != n; ++i) {
985                assert (I[i - 1] < I[i]);
986                assert (V[i - 1] != V[i]);
987                assert (V[i]->getParent() == pb);
988            }
989            #endif
990
991            /// Perform n-to-m Multiplexing
992            for (size_t j = 0; j != m; ++j) {
993
994                assert (Q.empty());
995
996                std::ostringstream prefix;
997
998                prefix << "mux" << n << "to" << m;
999                for (size_t i = 1; i <= n; ++i) {
1000                    if ((i & (static_cast<size_t>(1) << j)) != 0) {
1001                        assert (!Q.full());
1002                        PabloAST * tmp = V[i - 1]->getOperand(0); assert (tmp);
1003                        prefix << '_' << V[i - 1]->getName()->to_string();
1004                        Q.push_back(tmp);
1005                    }
1006                }
1007
1008                assert (Q.size() >= 1);
1009
1010                Advance * const adv = V[j];
1011                // TODO: figure out a way to determine whether we're creating a duplicate value below.
1012                // The expression map findOrCall ought to work conceptually but the functors method
1013                // doesn't really work anymore with the current API.
1014                while (Q.size() > 1) {
1015                    PabloAST * a1 = Q.front(); Q.pop_front(); assert (a1);
1016                    PabloAST * a2 = Q.front(); Q.pop_front(); assert (a2);
1017                    assert (!Q.full());
1018                    pb->setInsertPoint(choose(a2, a1, adv));
1019                    Q.push_back(pb->createOr(a1, a2));
1020                }
1021                assert (Q.size() == 1);
1022
1023                PabloAST * mux = Q.front(); Q.pop_front(); assert (mux);
1024                muxed[j] = pb->createAdvance(mux, adv->getOperand(1), prefix.str());
1025            }
1026
1027
1028            /// Perform m-to-n Demultiplexing
1029            // Now construct the demuxed values and replaces all the users of the original advances with them.
1030            for (size_t i = 1; i <= n; ++i) {
1031
1032                Advance * const adv = V[i - 1];
1033
1034                pb->setInsertPoint(adv);
1035
1036                assert (Q.empty());
1037                for (size_t j = 0; j != m; ++j) {
1038                    if ((i & (static_cast<size_t>(1) << j)) == 0) {
1039                        Q.push_back(muxed[j]);
1040                    }
1041                }
1042
1043                assert (Q.size() <= m);
1044                PabloAST * neg = nullptr;
1045                if (LLVM_LIKELY(Q.size() > 0)) {
1046                    while (Q.size() > 1) {
1047                        PabloAST * a1 = Q.front(); Q.pop_front(); assert (a1);
1048                        PabloAST * a2 = Q.front(); Q.pop_front(); assert (a2);
1049                        assert (!Q.full());
1050                        Q.push_back(pb->createOr(a1, a2));
1051                    }
1052                    assert (Q.size() == 1);
1053                    neg = pb->createNot(Q.front()); Q.pop_front(); assert (neg);
1054                }
1055
1056                assert (Q.empty());
1057                for (unsigned j = 0; j != m; ++j) {
1058                    if ((i & (static_cast<unsigned>(1) << j)) != 0) {
1059                        assert (!Q.full());
1060                        Q.push_back(muxed[j]);
1061                    }
1062                }
1063
1064                assert (Q.size() <= m);
1065                assert (Q.size() >= 1);
1066
1067                while (Q.size() > 1) {
1068                    PabloAST * a1 = Q.front(); Q.pop_front(); assert (a1);
1069                    PabloAST * a2 = Q.front(); Q.pop_front(); assert (a2);
1070                    assert (!Q.full());
1071                    Q.push_back(pb->createAnd(a1, a2));
1072                }
1073
1074                assert (Q.size() == 1);
1075
1076                PabloAST * demux = Q.front(); Q.pop_front(); assert (demux);
1077                if (LLVM_LIKELY(neg != nullptr)) {
1078                    demux = pb->createAnd(demux, neg);
1079                }
1080                V[i - 1]->replaceWith(demux, true, true);
1081            }
1082        }
1083    }
1084}
1085
1086/** ------------------------------------------------------------------------------------------------------------- *
1087 * @brief topologicalSort
1088 *
1089 * After transforming the IR, we need to run this in order to always have a valid program. Each multiplex set
1090 * contains vertices corresponding to an Advance in the IR. While we know each Advance within a set is independent
1091 * w.r.t. the transitive closure of their dependencies in the IR, the position of each Advance's dependencies and
1092 * users within the IR isn't taken into consideration. Thus while there must be a valid ordering for the program,
1093 * it's not necessarily the original ordering.
1094 ** ------------------------------------------------------------------------------------------------------------- */
1095void AutoMultiplexing::topologicalSort(PabloBlock & entry) const {
1096    // Note: not a real topological sort. I expect the original order to be very close to the resulting one.
1097    std::unordered_set<const PabloAST *> encountered;
1098    std::stack<Statement *> scope;
1099    for (Statement * stmt = entry.front(); ; ) { restart:
1100        while ( stmt ) {
1101            for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
1102                PabloAST * const op = stmt->getOperand(i);
1103                if (LLVM_LIKELY(isa<Statement>(op))) {
1104                    if (LLVM_UNLIKELY(encountered.count(op) == 0)) {
1105                        if (LLVM_UNLIKELY(isa<While>(stmt) && isa<Next>(op))) {
1106                            if (encountered.count(cast<Next>(op)->getInitial()) != 0) {
1107                                continue;
1108                            }
1109                        }
1110                        Statement * const next = stmt->getNextNode();
1111                        stmt->insertAfter(cast<Statement>(op));
1112                        stmt = next;
1113                        goto restart;
1114                    }
1115                }
1116            }
1117            if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
1118                // Set the next statement to be the first statement of the inner scope and push the
1119                // next statement of the current statement into the scope stack.
1120                const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
1121                scope.push(stmt->getNextNode());
1122                stmt = nested.front();
1123                continue;
1124            }
1125            encountered.insert(stmt);
1126            stmt = stmt->getNextNode();
1127        }
1128        if (scope.empty()) {
1129            break;
1130        }
1131        stmt = scope.top();
1132        scope.pop();
1133    }
1134}
1135
1136} // end of namespace pablo
1137
Note: See TracBrowser for help on using the repository browser.