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

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

Multiplexing work: minor bug fix and inconsequential changes.

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