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

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

More multiplexing work. Reduced MWIS approximation cost.

File size: 49.6 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    const auto seed = rd(); // 573650087;
60    RNG rng(seed);
61    const bool multiplex = am.generateMultiplexSets(rng);
62    const timestamp_t end_create_multiplex_graph = read_cycle_counter();
63    timestamp_t end_mwis = end_create_multiplex_graph,
64            end_subset_constraints = end_create_multiplex_graph,
65            end_select_independent_sets = end_create_multiplex_graph,
66            end_topological_sort = end_create_multiplex_graph;
67
68    if (multiplex) {
69        am.approxMaxWeightIndependentSet(rng);
70        end_mwis = read_cycle_counter();
71        am.applySubsetConstraints();
72        end_subset_constraints = read_cycle_counter();
73        am.multiplexSelectedIndependentSets();
74        end_select_independent_sets = read_cycle_counter();
75        am.topologicalSort(entry);
76        end_topological_sort = read_cycle_counter();
77        modified = true;
78    }
79
80//    std::cerr << "Initialize:              " << (end_initialize - start) << "   (seed=" << seed << ')' << std::endl;
81//    std::cerr << "Characterize:            " << (end_characterize - end_initialize) << std::endl;
82//    std::cerr << "Shutdown:                " << (end_shutdown - end_characterize) << std::endl;
83//    std::cerr << "GenerateMultiplexSets:   " << (end_create_multiplex_graph - end_shutdown) << std::endl;
84//    std::cerr << "MaxWeightIndependentSet: " << (end_mwis - end_create_multiplex_graph) << std::endl;
85//    std::cerr << "ApplySubsetConstraints:  " << (end_subset_constraints - end_mwis) << std::endl;
86//    std::cerr << "MultiplexSelectedSets:   " << (end_select_independent_sets - end_subset_constraints) << std::endl;
87//    std::cerr << "TopologicalSort:         " << (end_topological_sort - end_select_independent_sets) << std::endl;
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 & M) {
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    // Note: this computes (∑i=1 to |N| C(|N|,i)) * [1 + (∑i=1 to |M| C(|M|,i))] = (2^|N| - 1) * (2^|M|) combinations.
633
634    ChosenSet S;
635    for (int i = 0; i < N.size(); ++i) {
636        S.insert(N[i]);
637        addMultiplexSet(N, i + 1, M, 0, S);
638        S.erase(S.find(N[i]));
639    }
640}
641
642/** ------------------------------------------------------------------------------------------------------------- *
643 * @brief addMultiplexSet
644 * @param N an independent set
645 * @param S an independent set
646 ** ------------------------------------------------------------------------------------------------------------- */
647void AutoMultiplexing::addMultiplexSet(const IndependentSet & N, const int i,
648                                       const IndependentSet & M, const int j,
649                                       ChosenSet & S) {
650
651    // TODO: Instead of building a graph, construct a trie of all members.
652
653    // Add S to the multiplex set if |S| >= 3 and not equal to 2^n for any n.
654    if (S.size() >= 3 && !is_power_of_2(S.size())) {
655        const auto v = add_vertex(mMultiplexSetGraph);
656        for (auto u : S) {
657            add_edge(v, u, mMultiplexSetGraph);
658        }
659    }
660
661    for (int ii = i; ii < N.size(); ++ii) {
662        S.insert(N[ii]);
663        addMultiplexSet(N, ii + 1, M, j, S);
664        S.erase(S.find(N[ii]));
665    }
666
667    for (int jj = j; jj < M.size(); ++jj) {
668        S.insert(M[jj]);
669        addMultiplexSet(N, i + 1, M, jj + 1, S);
670        S.erase(S.find(M[jj]));
671    }
672
673}
674
675static inline ssize_t sqr(const ssize_t n) {
676    return n * n;
677}
678
679/** ------------------------------------------------------------------------------------------------------------- *
680 * @brief approxMaxWeightIndependentSet
681 * @param RNG random number generator
682 ** ------------------------------------------------------------------------------------------------------------- */
683void AutoMultiplexing::approxMaxWeightIndependentSet(RNG & rng) {
684
685    // Compute our independent set graph from our multiplex set graph; effectively it's the graph resulting
686    // from contracting one advance node edge with an adjacent vertex
687
688    const unsigned m = num_vertices(mConstraintGraph);
689    const unsigned n = num_vertices(mMultiplexSetGraph) - m;
690
691    const auto start = read_cycle_counter();
692
693    IndependentSetGraph G(n);
694
695    MultiplexSetGraph::vertex_descriptor i = m;
696    graph_traits<IndependentSetGraph>::vertex_iterator vi, vi_end;
697    for (std::tie(vi, vi_end) = vertices(G); vi != vi_end; ++vi, ++i) {
698        G[*vi] = std::make_pair(out_degree(i, mMultiplexSetGraph), 0);
699    }
700
701    // Let M be mMultiplexSetGraph. Each vertex in G corresponds to a set vertex in M.
702    // If an advance vertex in M (i.e., one of the first m vertices of M) is adjacent
703    // to two or more set vertices, add an edge between the corresponding vertices in G.
704    // I.e., make all vertices in G adjacent if their corresponding sets intersect.
705
706    for (i = 0; i != m; ++i) {
707        if (in_degree(i, mMultiplexSetGraph) > 1) {
708            graph_traits<MultiplexSetGraph>::in_edge_iterator ei_begin, ei_end;
709            std::tie(ei_begin, ei_end) = in_edges(i, mMultiplexSetGraph);
710            for (auto ei = ei_begin; ei != ei_end; ++ei) {
711                for (auto ej = ei_begin; ej != ei; ++ej) {
712                    // Note: ei and ej are incoming edges. The source is the set vertex,
713                    add_edge(source(*ei, mMultiplexSetGraph) - m, source(*ej, mMultiplexSetGraph) - m, G);
714                }
715            }
716        }
717    }
718
719    boost::container::flat_set<IndependentSetGraph::vertex_descriptor> indices;
720    indices.reserve(n);
721    #ifdef USE_WEIGHTED_SELECTION
722    for (std::tie(vi, vi_end) = vertices(G); vi != vi_end; ++vi, ++i) {
723        int neighbourhoodWeight = 0;
724        int neighbours = 1;
725        graph_traits<IndependentSetGraph>::adjacency_iterator ai, ai_end;
726        for (std::tie(ai, ai_end) = adjacent_vertices(*vi, G); ai != ai_end; ++ai) {
727            ++neighbours;
728            neighbourhoodWeight += std::get<0>(G[*ai]);
729        }
730        std::get<1>(G[*vi]) = (std::get<0>(G[*vi]) * neighbours) - neighbourhoodWeight;
731        indices.insert(*vi);
732    }
733    #endif
734
735    const auto built_graph = read_cycle_counter();
736
737    // std::cerr << "G=(" << num_vertices(G) << ',' << num_edges(G) << ") built in " << (built_graph - start) << std::endl;
738
739    // Using WMIN from "A note on greedy algorithms for the maximum weighted independent set problem"
740    // (Note: look into minimum independent dominating set algorithms. It fits better with the ceil log2 + subset cost model.)
741
742    while (!indices.empty()) {
743
744        // Select a vertex vi whose weight as greater than the average weight of its neighbours ...
745        #ifdef USE_WEIGHTED_SELECTION
746        int totalWeight = 0;
747        for (auto vi = indices.begin(); vi != indices.end(); ++vi) {
748            totalWeight += sqr(std::get<1>(G[*vi]));
749        }
750
751        IndependentSetGraph::vertex_descriptor v = 0;
752        ssize_t remainingWeight = RNGDistribution(0, totalWeight - 1)(rng);
753        for (auto vi = indices.begin(); vi != indices.end(); ++vi) {
754            remainingWeight -= sqr(std::max<int>(std::get<1>(G[*vi]), 0));
755            if (remainingWeight < 0) {
756                v = *vi;
757                break;
758            }
759        }
760        assert (remainingWeight < 0);
761
762        #else
763        auto i = RNGDistribution(1, indices.size())(rng);
764        for (std::tie(vi, vi_end) = vertices(G); --i != 0; ++vi);
765        assert (vi != vi_end);
766        #endif       
767
768        // Note: by clearing the adjacent set vertices from the multiplex set graph, this will effectively
769        // choose the set refered to by vi as one of our chosen independent sets.
770        graph_traits<IndependentSetGraph>::adjacency_iterator ai, ai_end, aj, aj_end;
771        for (std::tie(ai, ai_end) = adjacent_vertices(v, G); ai != ai_end; ) {
772            const auto u = *ai++;
773            assert (indices.count(u));
774            indices.erase(indices.find(u));
775            clear_out_edges(u + m, mMultiplexSetGraph);
776            #ifdef USE_WEIGHTED_SELECTION
777            const auto Wj = std::get<0>(G[u]);
778            for (std::tie(aj, aj_end) = adjacent_vertices(u, G); aj != aj_end; ) {
779
780                // Let Vi be vertex i, Wi = weight of Vi, Di = degree of Vi, Ni = sum of the weights of vertices
781                // adjacent to Vi, and Ai be the weight difference of Vi w.r.t. its neighbours. Initially,
782
783                //     Ai = (Wi * (Di + 1)) - Ni
784
785                // Suppose Vj is removed from G and is adjacent to Vi. Then,
786
787                //    Ai' = (Wi * (Di + 1 - 1)) - (Ni - Wj) = (Ai - Wi + Wj)
788
789                const auto w = *aj++;
790                const auto Wi = std::get<0>(G[w]);
791                auto & Ai = std::get<1>(G[w]);
792                Ai = Ai - Wi + Wj;
793                remove_edge(u, w, G);
794            }
795            #else
796            clear_vertex(u, G);
797            #endif
798            remove_edge(v, u, G);
799        }
800        indices.erase(indices.find(v));
801    }
802
803//    for (unsigned i = m; i != (m + n); ++i) {
804//        if (out_degree(i, mMultiplexSetGraph) > 0) {
805//            std::cerr << out_degree(i, mMultiplexSetGraph) << std::endl;
806//        }
807//    }
808
809    #ifndef NDEBUG
810    for (unsigned i = 0; i != m; ++i) {
811        assert (in_degree(i, mMultiplexSetGraph) <= 1);
812    }
813    for (unsigned i = m; i != (m + n); ++i) {
814        assert (out_degree(i, mMultiplexSetGraph) == 0 || out_degree(i, mMultiplexSetGraph) >= 3);
815    }
816    #endif
817}
818
819/** ------------------------------------------------------------------------------------------------------------- *
820 * @brief choose
821 ** ------------------------------------------------------------------------------------------------------------- */
822
823inline Statement * choose(PabloAST * x, PabloAST * y, Statement * z) {
824    return isa<Statement>(x) ? cast<Statement>(x) : (isa<Statement>(y) ? cast<Statement>(y) : z);
825}
826
827/** ------------------------------------------------------------------------------------------------------------- *
828 * @brief applySubsetConstraints
829 ** ------------------------------------------------------------------------------------------------------------- */
830void AutoMultiplexing::applySubsetConstraints() {
831
832    // When entering thus function, the multiplex set graph M is a bipartite DAG with edges denoting the set
833    // relationships of our independent sets.
834    const unsigned m = num_vertices(mConstraintGraph);
835    const unsigned n = num_vertices(mMultiplexSetGraph);
836
837    // Add in any edges from our subset constraints to M that are within the same set.
838    bool hasSubsetConstraint = false;
839
840    graph_traits<SubsetGraph>::edge_iterator ei, ei_end;
841    for (std::tie(ei, ei_end) = edges(mSubsetGraph); ei != ei_end; ++ei) {
842        const auto u = source(*ei, mSubsetGraph);
843        const auto v = target(*ei, mSubsetGraph);
844        graph_traits<MultiplexSetGraph>::in_edge_iterator ej, ej_end;
845        // If both the source and target of ei are adjacent to the same vertex, that vertex must be the
846        // "set vertex". Add the edge between the vertices.
847        for (std::tie(ej, ej_end) = in_edges(u, mMultiplexSetGraph); ej != ej_end; ++ej) {
848            auto w = target(*ej, mMultiplexSetGraph);
849            // Only check (v, w) if w is a "set vertex".
850            if (w >= (n - m) && edge(v, w, mMultiplexSetGraph).second) {
851                add_edge(u, v, mMultiplexSetGraph);
852                hasSubsetConstraint = true;
853            }
854        }
855    }
856
857    if (LLVM_UNLIKELY(hasSubsetConstraint)) {
858        // At this point, M is still a DAG but no longer bipartite. We're going to scan through the set vertices
859        // in M, and use a DFS to scan through M and eliminate any subset relationships in the AST.
860        // That way, "multiplexSelectedIndependentSets" only needs to consider muxing and demuxing of the streams.
861
862        std::vector<MultiplexSetGraph::vertex_descriptor> V;
863        std::stack<MultiplexSetGraph::vertex_descriptor> S;
864        std::queue<PabloAST *> Q;
865        BitVector D(n - m, 0);
866
867        for (auto i = m; i != n; ++i) {
868            graph_traits<MultiplexSetGraph>::out_edge_iterator ei, ei_end;
869            // For each member of a "set vertex" ...
870            std::tie(ei, ei_end) = out_edges(i, mMultiplexSetGraph);
871            for (; ei != ei_end; ++ei) {
872                const auto s = source(*ei, mMultiplexSetGraph);
873                if (out_degree(s, mMultiplexSetGraph) != 0) {
874                    // First scan through the subgraph of vertices in M dominated by s and build up the set T,
875                    // consisting of all sinks w.r.t. vertex s.
876                    auto u = s;
877                    for (;;) {
878                        graph_traits<MultiplexSetGraph>::out_edge_iterator ej, ej_end;
879                        for (std::tie(ej, ej_end) = out_edges(u, mMultiplexSetGraph); ej != ej_end; ++ej) {
880                            auto v = target(*ej, mMultiplexSetGraph);
881                            if (D.test(v)) {
882                                continue;
883                            }
884                            D.set(v);
885                            if (out_degree(v, mMultiplexSetGraph) == 0) {
886                                V.push_back(v);
887                            }
888                            else {
889                                S.push(v);
890                            }
891                        }
892                        if (S.empty()) {
893                            break;
894                        }
895                        u = S.top();
896                        S.pop();
897                    }
898                    D.clear();
899                    // Now in order for these advances to be mutually exclusive, the input to A_s must be masked
900                    // with the complement of each advance indicated by V.
901
902                    Advance * adv = mAdvance[s];
903                    PabloBlock * pb = adv->getParent();
904
905                    for (auto i : V) {
906                        Q.push(mAdvance[i]->getOperand(0));
907                    }                   
908                    while (Q.size() > 1) {
909                        PabloAST * a1 = Q.front(); Q.pop();
910                        PabloAST * a2 = Q.front(); Q.pop();
911                        pb->setInsertPoint(cast<Statement>(a2));
912                        Q.push(pb->createOr(a1, a2));
913                    }
914                    assert (Q.size() == 1);
915
916                    PabloAST * const mask = pb->createNot(Q.front()); Q.pop();
917                    adv->setOperand(0, pb->createAnd(adv->getOperand(0), mask, "subset_in"));
918
919                    // Similar to the above, we're going to OR together the result of each advance,
920                    // including s. This will restore the advanced variable back to its original state.
921
922                    // Gather the original users to this advance. We'll be manipulating it shortly.
923                    Statement::Users U(adv->users());
924
925                    // Add s to V and sort the list; it'll be closer to being in topological order.
926                    V.push_back(s);
927                    std::sort(V.begin(), V.end());
928                    for (auto i : V) {
929                        Q.push(mAdvance[i]);
930                    }
931                    while (Q.size() > 1) {
932                        PabloAST * a1 = Q.front(); Q.pop();
933                        PabloAST * a2 = Q.front(); Q.pop();
934                        pb->setInsertPoint(choose(a2, a1, adv));
935                        Q.push(pb->createOr(a1, a2));
936                    }
937                    assert (Q.size() == 1);
938
939                    PabloAST * const input = Q.front(); Q.pop();
940                    for (PabloAST * use : U) {
941                        if (LLVM_LIKELY(isa<Statement>(use))) {
942                            cast<Statement>(use)->replaceUsesOfWith(adv, input);
943                        }
944                    }
945
946                    pb->setInsertPoint(pb->back());
947
948                    V.clear();
949
950                }
951            }
952        }
953    }
954}
955
956/** ------------------------------------------------------------------------------------------------------------- *
957 * @brief log2_plus_one
958 ** ------------------------------------------------------------------------------------------------------------- */
959static inline size_t log2_plus_one(const size_t n) {
960    return std::log2<size_t>(n) + 1; // use a faster builtin function for this?
961}
962
963/** ------------------------------------------------------------------------------------------------------------- *
964 * @brief multiplexSelectedIndependentSets
965 ** ------------------------------------------------------------------------------------------------------------- */
966void AutoMultiplexing::multiplexSelectedIndependentSets() const {
967
968    const unsigned f = num_vertices(mConstraintGraph);
969    const unsigned l = num_vertices(mMultiplexSetGraph);
970
971    // Preallocate the structures based on the size of the largest multiplex set
972    size_t max_n = 3;
973    for (unsigned s = f; s != l; ++s) {
974        max_n = std::max<unsigned>(max_n, out_degree(s, mMultiplexSetGraph));
975    }
976    const size_t max_m = log2_plus_one(max_n);
977
978    std::vector<MultiplexSetGraph::vertex_descriptor> I(max_n);
979    std::vector<Advance *> V(max_n);
980    std::vector<PabloAST *> muxed(max_m);
981    circular_buffer<PabloAST *> Q(max_n);
982
983    // When entering thus function, the multiplex set graph M is a DAG with edges denoting the set
984    // relationships of our independent sets.
985
986    for (unsigned s = f; s != l; ++s) {
987        const size_t n = out_degree(s, mMultiplexSetGraph);
988        if (n) {
989
990            const size_t m = log2_plus_one(n);
991
992            graph_traits<MultiplexSetGraph>::out_edge_iterator ei, ei_end;
993            std::tie(ei, ei_end) = out_edges(s, mMultiplexSetGraph);
994            for (unsigned i = 0; i != n; ++ei, ++i) {
995                I[i] = target(*ei, mMultiplexSetGraph);
996                assert (I[i] < mAdvance.size());
997            }
998            std::sort(I.begin(), I.begin() + n);
999
1000            for (unsigned i = 0; i != n; ++i) {
1001                V[i] = mAdvance[I[i]];
1002            }
1003
1004            PabloBlock * const pb = V[0]->getParent();
1005            assert (pb);
1006
1007            // Sanity test to make sure every advance is in the same scope.
1008            #ifndef NDEBUG
1009            for (unsigned i = 1; i != n; ++i) {
1010                assert (I[i - 1] < I[i]);
1011                assert (V[i - 1] != V[i]);
1012                assert (V[i]->getParent() == pb);
1013            }
1014            #endif
1015
1016            /// Perform n-to-m Multiplexing
1017            for (size_t j = 0; j != m; ++j) {
1018
1019                assert (Q.empty());
1020
1021                std::ostringstream prefix;
1022
1023                prefix << "mux" << n << "to" << m;
1024                for (size_t i = 1; i <= n; ++i) {
1025                    if ((i & (static_cast<size_t>(1) << j)) != 0) {
1026                        assert (!Q.full());
1027                        PabloAST * tmp = V[i - 1]->getOperand(0); assert (tmp);
1028                        prefix << '_' << V[i - 1]->getName()->to_string();
1029                        Q.push_back(tmp);
1030                    }
1031                }
1032
1033                assert (Q.size() >= 1);
1034
1035                Advance * const adv = V[j];
1036                // TODO: figure out a way to determine whether we're creating a duplicate value below.
1037                // The expression map findOrCall ought to work conceptually but the functors method
1038                // doesn't really work anymore with the current API.
1039                while (Q.size() > 1) {
1040                    PabloAST * a1 = Q.front(); Q.pop_front(); assert (a1);
1041                    PabloAST * a2 = Q.front(); Q.pop_front(); assert (a2);
1042                    assert (!Q.full());
1043                    pb->setInsertPoint(choose(a2, a1, adv));
1044                    Q.push_back(pb->createOr(a1, a2));
1045                }
1046                assert (Q.size() == 1);
1047
1048                PabloAST * mux = Q.front(); Q.pop_front(); assert (mux);
1049                muxed[j] = pb->createAdvance(mux, adv->getOperand(1), prefix.str());
1050            }
1051
1052
1053            /// Perform m-to-n Demultiplexing
1054            // Now construct the demuxed values and replaces all the users of the original advances with them.
1055            for (size_t i = 1; i <= n; ++i) {
1056
1057                Advance * const adv = V[i - 1];
1058
1059                pb->setInsertPoint(adv);
1060
1061                assert (Q.empty());
1062                for (size_t j = 0; j != m; ++j) {
1063                    if ((i & (static_cast<size_t>(1) << j)) == 0) {
1064                        Q.push_back(muxed[j]);
1065                    }
1066                }
1067
1068                assert (Q.size() <= m);
1069                PabloAST * neg = nullptr;
1070                if (LLVM_LIKELY(Q.size() > 0)) {
1071                    while (Q.size() > 1) {
1072                        PabloAST * a1 = Q.front(); Q.pop_front(); assert (a1);
1073                        PabloAST * a2 = Q.front(); Q.pop_front(); assert (a2);
1074                        assert (!Q.full());
1075                        Q.push_back(pb->createOr(a1, a2));
1076                    }
1077                    assert (Q.size() == 1);
1078                    neg = pb->createNot(Q.front()); Q.pop_front(); assert (neg);
1079                }
1080
1081                assert (Q.empty());
1082                for (unsigned j = 0; j != m; ++j) {
1083                    if ((i & (static_cast<unsigned>(1) << j)) != 0) {
1084                        assert (!Q.full());
1085                        Q.push_back(muxed[j]);
1086                    }
1087                }
1088
1089                assert (Q.size() <= m);
1090                assert (Q.size() >= 1);
1091
1092                while (Q.size() > 1) {
1093                    PabloAST * a1 = Q.front(); Q.pop_front(); assert (a1);
1094                    PabloAST * a2 = Q.front(); Q.pop_front(); assert (a2);
1095                    assert (!Q.full());
1096                    Q.push_back(pb->createAnd(a1, a2));
1097                }
1098
1099                assert (Q.size() == 1);
1100
1101                PabloAST * demux = Q.front(); Q.pop_front(); assert (demux);
1102                if (LLVM_LIKELY(neg != nullptr)) {
1103                    demux = pb->createAnd(demux, neg);
1104                }
1105                V[i - 1]->replaceWith(demux, true, true);
1106            }
1107        }
1108    }
1109}
1110
1111/** ------------------------------------------------------------------------------------------------------------- *
1112 * @brief topologicalSort
1113 *
1114 * After transforming the IR, we need to run this in order to always have a valid program. Each multiplex set
1115 * contains vertices corresponding to an Advance in the IR. While we know each Advance within a set is independent
1116 * w.r.t. the transitive closure of their dependencies in the IR, the position of each Advance's dependencies and
1117 * users within the IR isn't taken into consideration. Thus while there must be a valid ordering for the program,
1118 * it's not necessarily the original ordering.
1119 ** ------------------------------------------------------------------------------------------------------------- */
1120void AutoMultiplexing::topologicalSort(PabloBlock & entry) const {
1121    // Note: not a real topological sort. I expect the original order to be very close to the resulting one.
1122    std::unordered_set<const PabloAST *> encountered;
1123    std::stack<Statement *> scope;
1124    for (Statement * stmt = entry.front(); ; ) { restart:
1125        while ( stmt ) {
1126            for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
1127                PabloAST * const op = stmt->getOperand(i);
1128                if (LLVM_LIKELY(isa<Statement>(op))) {
1129                    if (LLVM_UNLIKELY(encountered.count(op) == 0)) {
1130                        if (LLVM_UNLIKELY(isa<While>(stmt) && isa<Next>(op))) {
1131                            if (encountered.count(cast<Next>(op)->getInitial()) != 0) {
1132                                continue;
1133                            }
1134                        }
1135                        Statement * const next = stmt->getNextNode();
1136                        stmt->insertAfter(cast<Statement>(op));
1137                        stmt = next;
1138                        goto restart;
1139                    }
1140                }
1141            }
1142            if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
1143                // Set the next statement to be the first statement of the inner scope and push the
1144                // next statement of the current statement into the scope stack.
1145                const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
1146                scope.push(stmt->getNextNode());
1147                stmt = nested.front();
1148                continue;
1149            }
1150            encountered.insert(stmt);
1151            stmt = stmt->getNextNode();
1152        }
1153        if (scope.empty()) {
1154            break;
1155        }
1156        stmt = scope.top();
1157        scope.pop();
1158    }
1159}
1160
1161} // end of namespace pablo
1162
Note: See TracBrowser for help on using the repository browser.