source: icGREP/icgrep-devel/icgrep/pablo/optimizers/booleanreassociationpass.cpp @ 4868

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

Work on bug fixes for multiplexing pass.

File size: 40.5 KB
Line 
1#include "booleanreassociationpass.h"
2#include <boost/container/flat_set.hpp>
3#include <boost/container/flat_map.hpp>
4#include <boost/circular_buffer.hpp>
5#include <boost/graph/adjacency_list.hpp>
6#include <boost/graph/filtered_graph.hpp>
7#include <boost/graph/topological_sort.hpp>
8#include <pablo/optimizers/pablo_simplifier.hpp>
9#include <pablo/analysis/pabloverifier.hpp>
10#include <algorithm>
11#include <numeric> // std::iota
12
13#ifndef NDEBUG
14#include <queue>
15#include <pablo/printer_pablos.h>
16#include <iostream>
17#include <llvm/Support/raw_os_ostream.h>
18#include <boost/graph/strong_components.hpp>
19#endif
20
21
22using namespace boost;
23using namespace boost::container;
24
25namespace pablo {
26
27using TypeId = PabloAST::ClassTypeId;
28using Graph = BooleanReassociationPass::Graph;
29using Vertex = Graph::vertex_descriptor;
30using VertexData = BooleanReassociationPass::VertexData;
31using Map = BooleanReassociationPass::Map;
32using DistributionGraph = adjacency_list<hash_setS, vecS, bidirectionalS, Vertex>;
33using DistributionMap = flat_map<Graph::vertex_descriptor, DistributionGraph::vertex_descriptor>;
34using VertexSet = std::vector<Vertex>;
35using VertexSets = std::vector<VertexSet>;
36using Biclique = std::pair<VertexSet, VertexSet>;
37using BicliqueSet = std::vector<Biclique>;
38using DistributionSet = std::tuple<VertexSet, VertexSet, VertexSet>;
39using DistributionSets = std::vector<DistributionSet>;
40
41/** ------------------------------------------------------------------------------------------------------------- *
42 * @brief helper functions
43 ** ------------------------------------------------------------------------------------------------------------- */
44template<typename Iterator>
45inline Graph::edge_descriptor first(const std::pair<Iterator, Iterator> & range) {
46    assert (range.first != range.second);
47    return *range.first;
48}
49
50#ifndef NDEBUG
51static bool no_path(const Vertex u, const Vertex v, const Graph & G) {
52    if (u == v) return false;
53    flat_set<Vertex> V;
54    std::queue<Vertex> Q;
55    Q.push(u);
56    for (;;) {
57        Vertex w = Q.front();
58        if (w == v) {
59            return false;
60        }
61        Q.pop();
62        for (auto e : make_iterator_range(out_edges(w, G))) {
63            Vertex x = target(e, G);
64            if (V.count(x)) continue;
65            Q.push(x);
66            V.insert(x);
67        }
68        if (Q.empty()) {
69            break;
70        }
71    }
72    return true;
73}
74#endif
75
76inline void add_edge(PabloAST * expr, const Vertex u, const Vertex v, Graph & G) {
77    assert (no_path(v, u, G));
78    // Make sure each edge is unique
79    for (auto e : make_iterator_range(out_edges(u, G))) {
80        if (LLVM_UNLIKELY(target(e, G) == v && (G[e] == nullptr || G[e] == expr))) {
81            G[e] = expr;
82            return;
83        }
84    }
85    G[std::get<0>(add_edge(u, v, G))] = expr;
86}
87
88static inline bool inCurrentBlock(const Statement * stmt, const PabloBlock & block) {
89    return stmt->getParent() == &block;
90}
91
92static inline bool inCurrentBlock(const PabloAST * expr, const PabloBlock & block) {
93    return expr ? isa<Statement>(expr) && inCurrentBlock(cast<Statement>(expr), block) : true;
94}
95
96inline TypeId & getType(VertexData & data) {
97    return std::get<0>(data);
98}
99
100inline TypeId getType(const VertexData & data) {
101    return std::get<0>(data);
102}
103
104inline PabloAST *& getValue(VertexData & data) {
105    return std::get<1>(data);
106}
107
108inline PabloAST * getValue(const VertexData & data) {
109    return std::get<1>(data);
110}
111
112inline bool isAssociative(const VertexData & data) {
113    switch (getType(data)) {
114        case TypeId::And:
115        case TypeId::Or:
116        case TypeId::Xor:
117            return true;
118        default:
119            return false;
120    }
121}
122
123inline bool isDistributive(const VertexData & data) {
124    switch (getType(data)) {
125        case TypeId::And:
126        case TypeId::Or:
127            return true;
128        default:
129            return false;
130    }
131}
132
133inline bool isMutable(const VertexData & data) {
134    return getType(data) != TypeId::Var;
135}
136
137inline bool isNonEscaping(const VertexData & data) {
138    return getType(data) != TypeId::Assign && getType(data) != TypeId::Next;
139}
140
141inline bool isSameType(const VertexData & data1, const VertexData & data2) {
142    return getType(data1) == getType(data2);
143}
144
145/** ------------------------------------------------------------------------------------------------------------- *
146 * @brief intersects
147 ** ------------------------------------------------------------------------------------------------------------- */
148template <class Type>
149inline bool intersects(const Type & A, const Type & B) {
150    auto first1 = A.begin(), last1 = A.end();
151    auto first2 = B.begin(), last2 = B.end();
152    while (first1 != last1 && first2 != last2) {
153        if (*first1 < *first2) {
154            ++first1;
155        } else if (*first2 < *first1) {
156            ++first2;
157        } else {
158            return true;
159        }
160    }
161    return false;
162}
163
164/** ------------------------------------------------------------------------------------------------------------- *
165 * @brief optimize
166 ** ------------------------------------------------------------------------------------------------------------- */
167bool BooleanReassociationPass::optimize(PabloFunction & function) {
168    BooleanReassociationPass brp;
169    brp.resolveScopes(function);
170    brp.processScopes(function);   
171    #ifndef NDEBUG
172    PabloVerifier::verify(function, "post-reassociation");
173    #endif
174    Simplifier::optimize(function);
175    return true;
176}
177
178/** ------------------------------------------------------------------------------------------------------------- *
179 * @brief resolveScopes
180 ** ------------------------------------------------------------------------------------------------------------- */
181inline void BooleanReassociationPass::resolveScopes(PabloFunction &function) {
182    mResolvedScopes.emplace(&function.getEntryBlock(), nullptr);
183    resolveScopes(function.getEntryBlock());
184}
185
186/** ------------------------------------------------------------------------------------------------------------- *
187 * @brief resolveScopes
188 ** ------------------------------------------------------------------------------------------------------------- */
189void BooleanReassociationPass::resolveScopes(PabloBlock & block) {
190    for (Statement * stmt : block) {
191        if (isa<If>(stmt) || isa<While>(stmt)) {
192            PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
193            mResolvedScopes.emplace(&nested, stmt);
194            resolveScopes(nested);
195        }
196    }
197}
198
199/** ------------------------------------------------------------------------------------------------------------- *
200 * @brief processScopes
201 ** ------------------------------------------------------------------------------------------------------------- */
202inline void BooleanReassociationPass::processScopes(PabloFunction & function) {
203    processScopes(function, function.getEntryBlock());
204}
205
206/** ------------------------------------------------------------------------------------------------------------- *
207 * @brief processScopes
208 ** ------------------------------------------------------------------------------------------------------------- */
209void BooleanReassociationPass::processScopes(PabloFunction & function, PabloBlock & block) {
210    for (Statement * stmt : block) {
211        if (isa<If>(stmt)) {
212            processScopes(function, cast<If>(stmt)->getBody());
213        } else if (isa<While>(stmt)) {
214            processScopes(function, cast<While>(stmt)->getBody());
215        }
216    }
217    processScope(function, block);
218}
219
220/** ------------------------------------------------------------------------------------------------------------- *
221 * @brief getVertex
222 ** ------------------------------------------------------------------------------------------------------------- */
223template<typename ValueType, typename GraphType, typename MapType>
224static inline Vertex getVertex(const ValueType value, GraphType & G, MapType & M) {
225    const auto f = M.find(value);
226    if (f != M.end()) {
227        return f->second;
228    }
229    const auto u = add_vertex(value, G);
230    M.insert(std::make_pair(value, u));
231    return u;
232}
233
234/** ------------------------------------------------------------------------------------------------------------- *
235 * @brief writeTree
236 ** ------------------------------------------------------------------------------------------------------------- */
237inline PabloAST * writeTree(PabloBlock & block, const TypeId typeId, circular_buffer<PabloAST *> & Q) {
238    while (Q.size() > 1) {
239        PabloAST * e1 = Q.front(); Q.pop_front();
240        PabloAST * e2 = Q.front(); Q.pop_front();
241        PabloAST * expr = nullptr;
242        switch (typeId) {
243            case TypeId::And:
244                expr = block.createAnd(e1, e2); break;
245            case TypeId::Or:
246                expr = block.createOr(e1, e2); break;
247            case TypeId::Xor:
248                expr = block.createXor(e1, e2); break;
249            default: break;
250        }
251        Q.push_back(expr);
252    }   
253    return Q.front();
254}
255
256/** ------------------------------------------------------------------------------------------------------------- *
257 * @brief isReachableAtEntryPoint
258 ** ------------------------------------------------------------------------------------------------------------- */
259bool isReachableAtEntryPoint(const PabloAST * const expr, const PabloBlock & block) {
260    // if expr is not a statement, it's always reachable
261    if (isa<Statement>(expr)) {
262        const PabloBlock * parent = cast<Statement>(expr)->getParent();
263        // if expr is in the current block, it's not reachable at the entry point of this block
264        if (parent == &block) {
265            return false;
266        }
267        const PabloBlock * current = block.getParent();
268        // If expr is an Assign or Next node, it must escape its block (presuming the Simplifier has eliminated any
269        // unnecessary Assign or Next nodes.) We'll want to test whether the parent of its block is an ancestor of
270        // the current block.
271        if (isa<Assign>(expr) || isa<Next>(expr)) {
272            parent = parent->getParent();
273        }
274        // If we can find expr in a preceeding block, it's reachable
275        for (;;) {
276            if (parent == current) {
277                return true;
278            }
279            if (current == nullptr) {
280                break;
281            }
282            current = current->getParent();
283        }
284        // otherwise it must be in a nested block and therefore unreachable
285        return false;
286    }
287    return true;
288}
289
290/** ------------------------------------------------------------------------------------------------------------- *
291 * @brief createTree
292 ** ------------------------------------------------------------------------------------------------------------- */
293PabloAST * BooleanReassociationPass::createTree(PabloBlock & block, const Vertex u, Graph & G) {
294
295    flat_set<PabloAST *> internalVars;
296
297    flat_set<PabloAST *> externalVars;
298
299    assert (in_degree(u, G) > 0);
300
301    for (const auto e : make_iterator_range(in_edges(u, G))) {
302        PabloAST * const expr = getValue(G[source(e, G)]);
303        assert ("G contains a null input variable!" && (expr != nullptr));
304        if (isReachableAtEntryPoint(expr, block)) {
305            externalVars.insert(expr);
306        } else {
307            internalVars.insert(expr);
308        }
309    }
310
311    circular_buffer<PabloAST *> Q(in_degree(u, G));
312    for (auto expr : externalVars) {
313        Q.push_back(expr);
314    }
315
316    const TypeId typeId = getType(G[u]);
317    Statement * stmt = block.front();
318    if (Q.size() > 1) {
319        block.setInsertPoint(nullptr);
320        writeTree(block, typeId, Q);
321        assert (Q.size() == 1);
322    }
323
324    for (unsigned distance = 0; stmt; ++distance, stmt = stmt->getNextNode()) {
325
326        if (distance > 3 && Q.size() > 1) { // write out the current Q
327            writeTree(block, typeId, Q);
328            assert (Q.size() == 1);
329        }
330
331        bool found = false;
332        if (isa<If>(stmt)) {
333            for (Assign * def : cast<If>(stmt)->getDefined()) {
334                if (internalVars.erase(def) != 0) {
335                    assert (!Q.full());
336                    Q.push_back(def);
337                    found = true;
338                }
339            }
340        } else if (isa<While>(stmt)) {
341            for (Next * var : cast<While>(stmt)->getVariants()) {
342                if (internalVars.erase(var) != 0) {
343                    assert (!Q.full());
344                    Q.push_back(var);
345                    found = true;
346                }
347            }
348        } else if (internalVars.erase(stmt) != 0) {
349            Q.push_back(stmt);
350            found = true;
351        }
352
353        if (found) {
354            block.setInsertPoint(stmt);
355            distance = 0;
356        }
357    }
358
359    assert (internalVars.empty());
360
361    block.setInsertPoint(block.back());
362
363    writeTree(block, typeId, Q);
364    assert (Q.size() == 1);
365    PabloAST * const result = Q.front();
366    assert (result);
367    getValue(G[u]) = result;
368
369    return result;
370}
371
372/** ------------------------------------------------------------------------------------------------------------- *
373 * @brief processScope
374 ** ------------------------------------------------------------------------------------------------------------- */
375inline void BooleanReassociationPass::processScope(PabloFunction &, PabloBlock & block) {
376    Graph G;
377    Map M;
378    summarizeAST(block, G, M);
379    redistributeAST(block, G, M);
380    rewriteAST(block, G);
381}
382
383/** ------------------------------------------------------------------------------------------------------------- *
384 * @brief rewriteAST
385 ** ------------------------------------------------------------------------------------------------------------- */
386void BooleanReassociationPass::rewriteAST(PabloBlock & block, Graph & G) {
387
388    using ReadyPair = std::pair<unsigned, Vertex>;
389    using ReadySet = std::vector<ReadyPair>;
390
391    // Determine the bottom-up ordering of G
392    std::vector<unsigned> ordering(num_vertices(G));
393    circular_buffer<Vertex> Q(num_vertices(G));
394    for (const Vertex u : make_iterator_range(vertices(G))) {
395        if (out_degree(u, G) == 0 && in_degree(u, G) != 0) {
396            ordering[u] = 1;
397            Q.push_back(u);
398        }
399    }
400
401    while (!Q.empty()) {
402        const Vertex u = Q.front();
403        Q.pop_front();
404        assert (ordering[u] > 0);
405        for (const auto ei : make_iterator_range(in_edges(u, G))) {
406            const Vertex v = source(ei, G);
407            if (ordering[v] == 0) {
408                unsigned weight = 0;
409                bool ready = true;
410                for (const auto ej : make_iterator_range(out_edges(v, G))) {
411                    const Vertex w = target(ej, G);
412                    const unsigned t = ordering[w];
413                    if (t == 0) {
414                        ready = false;
415                        break;
416                    }
417                    weight = std::max(weight, t);
418                }
419                if (ready) {
420                    assert (weight < std::numeric_limits<unsigned>::max());
421                    assert (weight > 0);
422                    ordering[v] = (weight + 1);
423                    Q.push_back(v);
424                }
425            }
426        }
427    }
428
429    // Compute the initial ready set
430    ReadySet readySet;
431    for (const Vertex u : make_iterator_range(vertices(G))) {
432        if (in_degree(u, G) == 0 && out_degree(u, G) != 0) {
433
434            readySet.emplace_back(ordering[u], u);
435        }
436    }
437
438    struct {
439        bool operator()(const ReadyPair a, const ReadyPair b) {
440            return std::get<0>(a) > std::get<0>(b);
441        }
442    } readyComparator;
443
444    std::sort(readySet.begin(), readySet.end(), readyComparator);
445
446    // Store the original AST then clear the block
447    std::vector<Statement *> originalAST(block.begin(), block.end());
448    block.clear();
449    flat_set<Vertex> tested;
450
451    // Rewrite the AST using the bottom-up ordering
452    while (!readySet.empty()) {
453
454        // Scan through the ready set to determine which one 'kills' the greatest number of inputs
455        // NOTE: the readySet is kept in sorted "distance to sink" order; thus those closest to a
456        // sink will be evaluated first.
457        unsigned best = 0;
458        auto chosen = readySet.begin();
459        for (auto ri = readySet.begin(); ri != readySet.end(); ++ri) {
460            const Vertex u = std::get<1>(*ri);
461            unsigned kills = 0;
462            for (auto ei : make_iterator_range(in_edges(u, G))) {
463                const auto v = source(ei, G);
464                unsigned remaining = 0;
465                for (auto ej : make_iterator_range(out_edges(v, G))) {
466                    const auto w = target(ej, G);
467                    PabloAST * expr = getValue(G[w]);
468                    if (expr == nullptr || (isa<Statement>(expr) && cast<Statement>(expr)->getParent() == nullptr)) {
469                        if (++remaining > 1) {
470                            break;
471                        }
472                    }
473                }
474                if (remaining < 2) {
475                    ++kills;
476                }
477            }
478            if (kills > best) {
479                chosen = ri;
480                best = kills;
481            }
482        }
483        Vertex u; unsigned weight;
484        std::tie(weight, u) = *chosen;
485        readySet.erase(chosen);               
486        PabloAST * expr = getValue(G[u]);
487
488        assert (weight > 0);
489
490        if (LLVM_LIKELY(isMutable(G[u]))) {
491            if (isAssociative(G[u])) {
492                expr = createTree(block, u, G);
493            }
494            assert (expr);
495            for (auto e : make_iterator_range(out_edges(u, G))) {
496                if (G[e] && G[e] != expr) {
497                    if (PabloAST * user = getValue(G[target(e, G)])) {
498                        cast<Statement>(user)->replaceUsesOfWith(G[e], expr);
499                    }
500                }
501            }
502            // Make sure that optimization doesn't reduce this to an already written statement
503            if (LLVM_LIKELY(isa<Statement>(expr) && cast<Statement>(expr)->getParent() == nullptr)) {
504                block.insert(cast<Statement>(expr));
505            }
506        }
507
508        // mark this instruction as written
509        ordering[u] = 0;
510        // Now check whether any new instructions are ready
511        for (auto ei : make_iterator_range(out_edges(u, G))) {
512            bool ready = true;
513            const auto v = target(ei, G);
514            // since G may be a multigraph, we need to check whether we've already tested v
515            if (tested.insert(v).second) {
516                for (auto ej : make_iterator_range(in_edges(v, G))) {
517                    if (ordering[source(ej, G)]) {
518                        ready = false;
519                        break;
520                    }
521                }
522                if (ready) {
523
524                    auto entry = std::make_pair(ordering[v], v);
525                    auto position = std::lower_bound(readySet.begin(), readySet.end(), entry, readyComparator);
526                    readySet.insert(position, entry);
527                    assert (std::is_sorted(readySet.cbegin(), readySet.cend(), readyComparator));
528                }
529            }
530        }
531        tested.clear();
532    }
533
534    for (Statement * stmt : originalAST) {
535        if (stmt->getParent() == nullptr) {
536            stmt->eraseFromParent();
537        }
538    }
539}
540
541/** ------------------------------------------------------------------------------------------------------------- *
542 * @brief summarizeAST
543 *
544 * This function scans through a scope block and computes a DAG G in which any sequences of AND, OR or XOR functions
545 * are "flattened" (i.e., allowed to have any number of inputs.)
546 ** ------------------------------------------------------------------------------------------------------------- */
547void BooleanReassociationPass::summarizeAST(PabloBlock & block, Graph & G, Map & M) const {
548    // Compute the base def-use graph ...
549    for (Statement * stmt : block) {
550        const Vertex u = getSummaryVertex(stmt, G, M, block);
551        for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
552            PabloAST * const op = stmt->getOperand(i);
553            if (LLVM_UNLIKELY(isa<Integer>(op) || isa<String>(op))) {
554                continue;
555            }
556            const Vertex v = getSummaryVertex(op, G, M, block);
557            add_edge(op, v, u, G);
558            // If this operand is a Not operation that is not in this PabloBlock,
559            // pull its input operand in. It may lead to future optimizations.
560            if (LLVM_UNLIKELY(isa<Not>(op) && !inCurrentBlock(cast<Not>(op), block))) {
561                PabloAST * const negatedValue = cast<Not>(op)->getExpr();
562                add_edge(negatedValue, getSummaryVertex(negatedValue, G, M, block), v, G);
563            }
564        }
565        if (isa<If>(stmt)) {
566            for (Assign * def : cast<const If>(stmt)->getDefined()) {
567                const Vertex v = getSummaryVertex(def, G, M, block);
568                add_edge(def, u, v, G);
569                resolveNestedUsages(v, def, block, G, M, stmt);
570            }
571        } else if (isa<While>(stmt)) {
572            // To keep G a DAG, we need to do a bit of surgery on loop variants because
573            // the next variables it produces can be used within the condition. Instead,
574            // we make the loop dependent on the original value of each Next node and
575            // the Next node dependent on the loop.
576            for (Next * var : cast<const While>(stmt)->getVariants()) {
577                const Vertex v = getSummaryVertex(var, G, M, block);
578                assert (in_degree(v, G) == 1);
579                add_edge(nullptr, source(first(in_edges(v, G)), G), u, G);
580                remove_edge(v, u, G);
581                add_edge(var, u, v, G);
582                resolveNestedUsages(v, var, block, G, M, stmt);
583            }
584        } else {
585            resolveNestedUsages(u, stmt, block, G, M);
586        }
587    }
588    std::vector<Vertex> mapping(num_vertices(G));
589    summarizeGraph(block, G, mapping, M);
590}
591
592/** ------------------------------------------------------------------------------------------------------------- *
593 * @brief resolveNestedUsages
594 ** ------------------------------------------------------------------------------------------------------------- */
595void BooleanReassociationPass::resolveNestedUsages(const Vertex u, PabloAST * expr, PabloBlock & block, Graph & G, Map & M, const Statement * const ignoreIfThis) const {
596    for (PabloAST * user : expr->users()) {
597        assert (user);
598        if (LLVM_LIKELY(user != expr && isa<Statement>(user))) {
599            PabloBlock * parent = cast<Statement>(user)->getParent();
600            assert (parent);
601            if (LLVM_UNLIKELY(parent != &block)) {
602                for (;;) {
603                    if (LLVM_UNLIKELY(parent == nullptr)) {
604                        assert (isa<Assign>(expr) || isa<Next>(expr));
605                        break;
606                    } else if (parent->getParent() == &block) {
607                        const auto f = mResolvedScopes.find(parent);
608                        if (LLVM_UNLIKELY(f == mResolvedScopes.end())) {
609                            throw std::runtime_error("Failed to resolve scope block!");
610                        }
611                        Statement * const branch = f->second;
612                        if (LLVM_UNLIKELY(branch == ignoreIfThis)) {
613                            break;
614                        }
615                        // Add in a Var denoting the user of this expression so that it can be updated if expr changes.
616                        const Vertex v = getSummaryVertex(user, G, M, block);
617                        add_edge(expr, u, v, G);
618
619                        const Vertex w = getSummaryVertex(branch, G, M, block);
620                        add_edge(nullptr, v, w, G);
621                        break;
622                    }
623                    parent = parent->getParent();
624                }
625            }
626        }
627    }
628}
629
630/** ------------------------------------------------------------------------------------------------------------- *
631 * @brief summarizeGraph
632 ** ------------------------------------------------------------------------------------------------------------- */
633inline void BooleanReassociationPass::summarizeGraph(const PabloBlock &, Graph & G, std::vector<Vertex> & mapping, Map &) {
634    std::vector<Vertex> reverse_topological_ordering;
635    reverse_topological_ordering.reserve(num_vertices(G));
636
637    topological_sort(G, std::back_inserter(reverse_topological_ordering));
638    assert(mapping.size() >= num_vertices(G));
639    for (const Vertex u : reverse_topological_ordering) {       
640        if (in_degree(u, G) == 0 && out_degree(u, G) == 0) {
641            continue;
642        } else if (LLVM_LIKELY(out_degree(u, G) > 0)) {
643            if (isAssociative(G[u])) {
644                if (LLVM_UNLIKELY(in_degree(u, G) == 1)) {
645                    // We have a redundant node here that'll simply end up being a duplicate
646                    // of the input value. Remove it and add any of its outgoing edges to its
647                    // input node.
648                    const auto ei = first(in_edges(u, G));
649                    const Vertex v = source(ei, G);
650                    for (auto ej : make_iterator_range(out_edges(u, G))) {
651                        const Vertex w = target(ej, G);
652                        add_edge(G[ei], v, w, G);
653                        if (mapping[w] == mapping[u]) {
654                            mapping[w] = v;
655                        }
656                    }
657                    mapping[u] = v;
658                    clear_vertex(u, G);                   
659                    getType(G[u]) = TypeId::Var;
660                    getValue(G[u]) = nullptr;
661                    continue;
662                } else if (LLVM_UNLIKELY(out_degree(u, G) == 1)) {
663                    // Otherwise if we have a single user, we have a similar case as above but
664                    // we can only merge this vertex into the outgoing instruction if they are
665                    // of the same type.
666                    const auto ei = first(out_edges(u, G));
667                    const Vertex v = target(ei, G);
668                    if (LLVM_UNLIKELY(isSameType(G[v], G[u]))) {
669                        for (auto ej : make_iterator_range(in_edges(u, G))) {
670                            add_edge(G[ei], source(ej, G), v, G);
671                        }
672                        mapping[u] = v;
673                        clear_vertex(u, G);
674                        getType(G[u]) = TypeId::Var;
675                        getValue(G[u]) = nullptr;
676                        continue;
677                    }
678                }
679            }
680        } else if (isNonEscaping(G[u])) {
681            clear_in_edges(u, G);
682            getType(G[u]) = TypeId::Var;
683            getValue(G[u]) = nullptr;
684            continue;
685        }
686    }   
687}
688
689/** ------------------------------------------------------------------------------------------------------------- *
690 * @brief enumerateBicliques
691 *
692 * Adaptation of the MICA algorithm as described in "Consensus algorithms for the generation of all maximal
693 * bicliques" by Alexe et. al. (2003). Note: this implementation considers all verticies in set A to be in
694 * bipartition A and their adjacencies to be in B.
695  ** ------------------------------------------------------------------------------------------------------------- */
696template <class Graph>
697static BicliqueSet enumerateBicliques(const Graph & G, const VertexSet & A) {
698    using IntersectionSets = std::set<VertexSet>;
699
700    IntersectionSets B1;
701    for (auto u : A) {
702        if (in_degree(u, G) > 0) {
703            VertexSet incomingAdjacencies;
704            incomingAdjacencies.reserve(in_degree(u, G));
705            for (auto e : make_iterator_range(in_edges(u, G))) {
706                incomingAdjacencies.push_back(source(e, G));
707            }
708            std::sort(incomingAdjacencies.begin(), incomingAdjacencies.end());
709            B1.insert(std::move(incomingAdjacencies));
710        }
711    }
712
713    IntersectionSets B(B1);
714
715    IntersectionSets Bi;
716
717    VertexSet clique;
718    for (auto i = B1.begin(); i != B1.end(); ++i) {
719        for (auto j = i; ++j != B1.end(); ) {
720            std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(clique));
721            if (clique.size() > 0) {
722                if (B.count(clique) == 0) {
723                    Bi.insert(clique);
724                }
725                clique.clear();
726            }
727        }
728    }
729
730    for (;;) {
731        if (Bi.empty()) {
732            break;
733        }
734        B.insert(Bi.begin(), Bi.end());
735        IntersectionSets Bk;
736        for (auto i = B1.begin(); i != B1.end(); ++i) {
737            for (auto j = Bi.begin(); j != Bi.end(); ++j) {
738                std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(clique));
739                if (clique.size() > 0) {
740                    if (B.count(clique) == 0) {
741                        Bk.insert(clique);
742                    }
743                    clique.clear();
744                }
745            }
746        }
747        Bi.swap(Bk);
748    }
749
750    BicliqueSet cliques;
751    cliques.reserve(B.size());
752    for (auto Bi = B.begin(); Bi != B.end(); ++Bi) {
753        VertexSet Ai(A);
754        for (const Vertex u : *Bi) {                                   
755            VertexSet Aj;
756            Aj.reserve(out_degree(u, G));
757            for (auto e : make_iterator_range(out_edges(u, G))) {
758                Aj.push_back(target(e, G));
759            }
760            std::sort(Aj.begin(), Aj.end());
761            VertexSet Ak;
762            Ak.reserve(std::min(Ai.size(), Aj.size()));
763            std::set_intersection(Ai.begin(), Ai.end(), Aj.begin(), Aj.end(), std::back_inserter(Ak));
764            Ai.swap(Ak);
765        }
766        assert (Ai.size() > 0); // cannot happen if this algorithm is working correctly
767        cliques.emplace_back(std::move(Ai), std::move(*Bi));
768    }
769    return std::move(cliques);
770}
771
772/** ------------------------------------------------------------------------------------------------------------- *
773 * @brief independentCliqueSets
774 ** ------------------------------------------------------------------------------------------------------------- */
775template <unsigned side>
776inline static BicliqueSet && independentCliqueSets(BicliqueSet && cliques, const unsigned minimum) {
777    using IndependentSetGraph = adjacency_list<hash_setS, vecS, undirectedS, unsigned>;
778
779    const auto l = cliques.size();
780    IndependentSetGraph I(l);
781
782    // Initialize our weights
783    for (unsigned i = 0; i != l; ++i) {
784        I[i] = std::pow(std::get<side>(cliques[i]).size(), 2);
785    }
786
787    // Determine our constraints
788    for (unsigned i = 0; i != l; ++i) {
789        for (unsigned j = i + 1; j != l; ++j) {
790            if (intersects(std::get<side>(cliques[i]), std::get<side>(cliques[j]))) {
791                add_edge(i, j, I);
792            }
793        }
794    }
795
796    // Use the greedy algorithm to choose our independent set
797    VertexSet selected;
798    for (;;) {
799        unsigned w = 0;
800        Vertex u = 0;
801        for (unsigned i = 0; i != l; ++i) {
802            if (I[i] > w) {
803                w = I[i];
804                u = i;
805            }
806        }
807        if (w < minimum) break;
808        selected.push_back(u);
809        I[u] = 0;
810        for (auto v : make_iterator_range(adjacent_vertices(u, I))) {
811            I[v] = 0;
812        }
813    }
814
815    // Sort the selected list and then remove the unselected cliques
816    std::sort(selected.begin(), selected.end(), std::greater<Vertex>());
817    auto end = cliques.end();
818    for (const unsigned offset : selected) {
819        end = cliques.erase(cliques.begin() + offset + 1, end) - 1;
820    }
821    cliques.erase(cliques.begin(), end);
822
823    return std::move(cliques);
824}
825
826/** ------------------------------------------------------------------------------------------------------------- *
827 * @brief removeUnhelpfulBicliques
828 *
829 * An intermediary vertex could have more than one outgoing edge but if any that are not directed to vertices in
830 * the lower biclique, we'll need to compute that specific value anyway. Remove them from the clique set and if
831 * there are not enough vertices in the biclique to make distribution profitable, eliminate the clique.
832 ** ------------------------------------------------------------------------------------------------------------- */
833static BicliqueSet && removeUnhelpfulBicliques(BicliqueSet && cliques, const Graph & G, DistributionGraph & H) {
834    for (auto ci = cliques.begin(); ci != cliques.end(); ) {
835        const auto cardinalityA = std::get<0>(*ci).size();
836        VertexSet & B = std::get<1>(*ci);
837        for (auto bi = B.begin(); bi != B.end(); ) {
838            if (out_degree(H[*bi], G) == cardinalityA) {
839                ++bi;
840            } else {
841                bi = B.erase(bi);
842            }
843        }
844        if (B.size() > 1) {
845            ++ci;
846        } else {
847            ci = cliques.erase(ci);
848        }
849    }
850    return std::move(cliques);
851}
852
853/** ------------------------------------------------------------------------------------------------------------- *
854 * @brief safeDistributionSets
855 ** ------------------------------------------------------------------------------------------------------------- */
856static DistributionSets safeDistributionSets(const Graph & G, DistributionGraph & H) {
857
858    VertexSet sinks;
859    for (const Vertex u : make_iterator_range(vertices(H))) {
860        if (out_degree(u, H) == 0 && in_degree(u, G) != 0) {
861            sinks.push_back(u);
862        }
863    }
864    std::sort(sinks.begin(), sinks.end());
865
866    DistributionSets T;
867    BicliqueSet lowerSet = independentCliqueSets<1>(removeUnhelpfulBicliques(enumerateBicliques(H, sinks), G, H), 1);
868    for (Biclique & lower : lowerSet) {
869        BicliqueSet upperSet = independentCliqueSets<0>(enumerateBicliques(H, std::get<1>(lower)), 2);
870        for (Biclique & upper : upperSet) {
871            T.emplace_back(std::move(std::get<1>(upper)), std::move(std::get<0>(upper)), std::get<0>(lower));
872        }
873    }
874    return std::move(T);
875}
876
877/** ------------------------------------------------------------------------------------------------------------- *
878 * @brief generateDistributionGraph
879 ** ------------------------------------------------------------------------------------------------------------- */
880void generateDistributionGraph(const Graph & G, DistributionGraph & H) {
881    DistributionMap M;
882    for (const Vertex u : make_iterator_range(vertices(G))) {
883        if (in_degree(u, G) == 0 && out_degree(u, G) == 0) {
884            continue;
885        } else if (isDistributive(G[u])) {
886            const TypeId outerTypeId = getType(G[u]);
887            const TypeId innerTypeId = (outerTypeId == TypeId::And) ? TypeId::Or : TypeId::And;
888            flat_set<Vertex> distributable;
889            for (auto e : make_iterator_range(in_edges(u, G))) {
890                const Vertex v = source(e, G);
891                if (LLVM_UNLIKELY(getType(G[v]) == innerTypeId)) {
892                    bool safe = true;
893                    for (const auto e : make_iterator_range(out_edges(v, G))) {
894                        if (getType(G[target(e, G)]) != outerTypeId) {
895                            safe = false;
896                            break;
897                        }
898                    }
899                    if (safe) {
900                        distributable.insert(v);
901                    }
902                }
903            }
904            if (LLVM_LIKELY(distributable.size() > 1)) {
905                // We're only interested in computing a subgraph of G in which every source has an out-degree
906                // greater than 1. Otherwise we'd only end up permuting the AND/OR sequence with no logical
907                // benefit. (Note: this does not consider register pressure / liveness.)
908                flat_map<Vertex, bool> observedMoreThanOnce;
909                bool anyOpportunities = false;
910                for (const Vertex v : distributable) {
911                    for (auto e : make_iterator_range(in_edges(v, G))) {
912                        const Vertex w = source(e, G);
913                        auto ob = observedMoreThanOnce.find(w);
914                        if (ob == observedMoreThanOnce.end()) {
915                            observedMoreThanOnce.emplace(w, false);
916                        } else {
917                            ob->second = true;
918                            anyOpportunities = true;
919                        }
920                    }
921                }
922                if (anyOpportunities) {
923                    for (const auto ob : observedMoreThanOnce) {
924                        if (std::get<1>(ob)) {
925                            const Vertex w = std::get<0>(ob);
926                            for (auto e : make_iterator_range(out_edges(w, G))) {
927                                const Vertex v = target(e, G);
928                                if (distributable.count(v)) {
929                                    const Vertex y = getVertex(v, H, M);
930                                    add_edge(y, getVertex(u, H, M), H);
931                                    add_edge(getVertex(w, H, M), y, H);
932                                }
933                            }
934                        }
935                    }
936                }
937            }
938        }
939    }
940}
941
942/** ------------------------------------------------------------------------------------------------------------- *
943 * @brief redistributeAST
944 *
945 * Apply the distribution law to reduce computations whenever possible.
946 ** ------------------------------------------------------------------------------------------------------------- */
947void BooleanReassociationPass::redistributeAST(const PabloBlock & block, Graph & G, Map & M) const {
948
949    std::vector<Vertex> mapping(num_vertices(G) + 16);
950    std::iota(mapping.begin(), mapping.end(), 0); // 0,1,.....n
951
952    for (;;) {
953
954        DistributionGraph H;
955
956        generateDistributionGraph(G, H);
957
958        // If we found no potential opportunities then we cannot apply the distribution law to any part of G.
959        if (num_vertices(H) == 0) {
960            break;
961        }
962
963        const DistributionSets distributionSets = safeDistributionSets(G, H);
964
965        if (LLVM_UNLIKELY(distributionSets.empty())) {
966            break;
967        }
968
969        for (const DistributionSet & set : distributionSets) {
970
971            // Each distribution tuple consists of the sources, intermediary, and sink nodes.
972            const VertexSet & sources = std::get<0>(set);
973            const VertexSet & intermediary = std::get<1>(set);
974            const VertexSet & sinks = std::get<2>(set);
975
976            const TypeId outerTypeId = getType(G[mapping[H[sinks.front()]]]);
977            assert (outerTypeId == TypeId::And || outerTypeId == TypeId::Or);
978            const TypeId innerTypeId = (outerTypeId == TypeId::Or) ? TypeId::And : TypeId::Or;
979
980            // Update G to match the desired change
981            const Vertex x = addSummaryVertex(outerTypeId, G);
982            const Vertex y = addSummaryVertex(innerTypeId, G);
983            mapping.resize(num_vertices(G));
984            mapping[x] = x;
985            mapping[y] = y;
986
987            for (const Vertex i : intermediary) {
988                const auto u = mapping[H[i]];
989                assert (getType(G[u]) == innerTypeId);
990                for (const Vertex t : sinks) {
991                    assert (getType(G[mapping[H[t]]]) == outerTypeId);
992                    remove_edge(u, mapping[H[t]], G);
993                }
994                add_edge(nullptr, u, x, G);
995            }           
996
997            for (const Vertex s : sources) {
998                const auto u = mapping[H[s]];
999                for (const Vertex i : intermediary) {
1000                    remove_edge(u, mapping[H[i]], G);
1001                }
1002                add_edge(nullptr, u, y, G);
1003            }
1004            add_edge(nullptr, x, y, G);
1005
1006            for (const Vertex t : sinks) {
1007                const auto v = mapping[H[t]];
1008                add_edge(getValue(G[v]), y, v, G);
1009            }
1010
1011            summarizeGraph(block, G, mapping, M);
1012        }
1013    }
1014}
1015
1016/** ------------------------------------------------------------------------------------------------------------- *
1017 * @brief addSummaryVertex
1018 ** ------------------------------------------------------------------------------------------------------------- */
1019inline Vertex BooleanReassociationPass::addSummaryVertex(const TypeId typeId, Graph & G) {
1020    return add_vertex(std::make_pair(typeId, nullptr), G);
1021}
1022
1023/** ------------------------------------------------------------------------------------------------------------- *
1024 * @brief getVertex
1025 ** ------------------------------------------------------------------------------------------------------------- */
1026Vertex BooleanReassociationPass::getSummaryVertex(PabloAST * expr, Graph & G, Map & M, const PabloBlock & block) {
1027    const auto f = M.find(expr);
1028    if (f != M.end()) {
1029        return f->second;
1030    }
1031    // To simplify future analysis, every statement not in the current block will be recorded as a Var.
1032    const TypeId typeId = inCurrentBlock(expr, block) ? expr->getClassTypeId() : TypeId::Var;
1033    const auto u = add_vertex(std::make_pair(typeId, expr), G);
1034    M.insert(std::make_pair(expr, u));
1035    return u;
1036}
1037
1038}
Note: See TracBrowser for help on using the repository browser.