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

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

Bug fixes for reassociation pass; passes make check.

File size: 35.3 KB
RevLine 
[4736]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>
[4756]6#include <boost/graph/filtered_graph.hpp>
[4736]7#include <boost/graph/topological_sort.hpp>
[4771]8#include <boost/graph/strong_components.hpp>
[4751]9#include <pablo/optimizers/pablo_simplifier.hpp>
[4766]10#include <pablo/analysis/pabloverifier.hpp>
[4756]11#include <algorithm>
[4747]12#include <queue>
[4756]13#include <set>
[4751]14#include <iostream>
15#include <pablo/printer_pablos.h>
[4760]16#include "graph-facade.hpp"
[4736]17
18using namespace boost;
19using namespace boost::container;
20
21namespace pablo {
22
[4769]23using TypeId = PabloAST::ClassTypeId;
[4754]24using Graph = BooleanReassociationPass::Graph;
[4751]25using Vertex = Graph::vertex_descriptor;
26using VertexQueue = circular_buffer<Vertex>;
[4756]27using Map = BooleanReassociationPass::Map;
[4751]28using EdgeQueue = std::queue<std::pair<Vertex, Vertex>>;
[4765]29using DistributionGraph = adjacency_list<hash_setS, vecS, bidirectionalS, Vertex>;
30using DistributionMap = flat_map<Graph::vertex_descriptor, DistributionGraph::vertex_descriptor>;
31using VertexSet = std::vector<Vertex>;
32using VertexSets = std::vector<VertexSet>;
33using Biclique = std::pair<VertexSet, VertexSet>;
34using BicliqueSet = std::vector<Biclique>;
[4769]35using DistributionSet = std::tuple<VertexSet, VertexSet, VertexSet>;
[4765]36using DistributionSets = std::vector<DistributionSet>;
[4751]37
[4768]38/** ------------------------------------------------------------------------------------------------------------- *
39 * @brief helper functions
40 ** ------------------------------------------------------------------------------------------------------------- */
[4765]41template <class Graph>
42static VertexSet incomingVertexSet(const Vertex u, const Graph & G) {
43    VertexSet V;
44    V.reserve(G.in_degree(u));
45    for (auto e : make_iterator_range(G.in_edges(u))) {
46        V.push_back(G.source(e));
47    }
48    std::sort(V.begin(), V.end());
49    return std::move(V);
50}
51
52template <class Graph>
53static VertexSet outgoingVertexSet(const Vertex u, const Graph & G) {
54    VertexSet V;
55    V.reserve(G.out_degree(u));
56    for (auto e : make_iterator_range(G.out_edges(u))) {
57        V.push_back(G.target(e));
58    }
59    std::sort(V.begin(), V.end());
60    return std::move(V);
61}
62
[4766]63template <class Graph>
64static VertexSet sinks(const Graph & G) {
65    VertexSet V;
66    for (const Vertex u : make_iterator_range(vertices(G))) {
67        if (out_degree(u, G) == 0) {
68            V.push_back(u);
69        }
70    }
71    std::sort(V.begin(), V.end());
72    return std::move(V);
73}
74
[4768]75template<typename Iterator>
76inline Graph::edge_descriptor first(const std::pair<Iterator, Iterator> & range) {
77    assert (range.first != range.second);
78    return *range.first;
79}
80
[4771]81inline bool has_edge(const Vertex u, const Vertex v, const Graph & G) {
82    return edge(u, v, G).second == true;
83}
84
85inline bool no_edge(const Vertex u, const Vertex v, const Graph & G) {
86    return edge(u, v, G).second == false;
87}
88
[4768]89inline void add_edge(PabloAST * expr, const Vertex u, const Vertex v, Graph & G) {
[4771]90    // assert (u != v);
91    // assert (no_edge(v, u, G));
92    // Make sure each edge is unique
93    for (auto e : make_iterator_range(out_edges(u, G))) {
94        if (LLVM_UNLIKELY(target(e, G) == v && (G[e] == nullptr || G[e] == expr))) {
95            G[e] = expr;
96            return;
97        }
98    }
99    G[std::get<0>(add_edge(u, v, G))] = expr;
[4768]100}
101
[4771]102
[4751]103/** ------------------------------------------------------------------------------------------------------------- *
104 * @brief optimize
105 ** ------------------------------------------------------------------------------------------------------------- */
[4736]106bool BooleanReassociationPass::optimize(PabloFunction & function) {
107    BooleanReassociationPass brp;
[4753]108    brp.resolveScopes(function);
109    brp.processScopes(function);
[4763]110    Simplifier::optimize(function);
[4736]111    return true;
112}
113
[4738]114/** ------------------------------------------------------------------------------------------------------------- *
[4753]115 * @brief resolveScopes
116 ** ------------------------------------------------------------------------------------------------------------- */
117inline void BooleanReassociationPass::resolveScopes(PabloFunction &function) {
[4763]118    mResolvedScopes.emplace(&function.getEntryBlock(), nullptr);
[4753]119    resolveScopes(function.getEntryBlock());
120}
121
122/** ------------------------------------------------------------------------------------------------------------- *
123 * @brief resolveScopes
124 ** ------------------------------------------------------------------------------------------------------------- */
125void BooleanReassociationPass::resolveScopes(PabloBlock & block) {
126    for (Statement * stmt : block) {
127        if (isa<If>(stmt) || isa<While>(stmt)) {
128            PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
129            mResolvedScopes.emplace(&nested, stmt);
130            resolveScopes(nested);
131        }
132    }
133}
134
135/** ------------------------------------------------------------------------------------------------------------- *
[4761]136 * @brief processScopes
[4738]137 ** ------------------------------------------------------------------------------------------------------------- */
[4753]138inline void BooleanReassociationPass::processScopes(PabloFunction & function) {
[4766]139    processScopes(function, function.getEntryBlock());
[4736]140}
141
[4738]142/** ------------------------------------------------------------------------------------------------------------- *
[4761]143 * @brief processScopes
[4751]144 ** ------------------------------------------------------------------------------------------------------------- */
[4766]145void BooleanReassociationPass::processScopes(PabloFunction & function, PabloBlock & block) {
[4751]146    for (Statement * stmt : block) {
147        if (isa<If>(stmt)) {
[4766]148            processScopes(function, cast<If>(stmt)->getBody());
[4751]149        } else if (isa<While>(stmt)) {
[4766]150            processScopes(function, cast<While>(stmt)->getBody());
[4751]151        }
152    }
[4766]153    processScope(function, block);
[4751]154}
155
156/** ------------------------------------------------------------------------------------------------------------- *
[4769]157 * @brief inCurrentBlock
158 ** ------------------------------------------------------------------------------------------------------------- */
159static inline bool inCurrentBlock(const Statement * stmt, const PabloBlock & block) {
160    return stmt->getParent() == &block;
161}
162
163static inline bool inCurrentBlock(const PabloAST * expr, const PabloBlock & block) {
164    return expr ? isa<Statement>(expr) && inCurrentBlock(cast<Statement>(expr), block) : true;
165}
166
167/** ------------------------------------------------------------------------------------------------------------- *
[4751]168 * @brief isOptimizable
169 *
170 * And, Or and Xor instructions are all associative, commutative and distributive operations. Thus we can
171 * safely rearrange expressions such as "((((a √ b) √ c) √ d) √ e) √ f" into "((a √ b) √ (c √ d)) √ (e √ f)".
[4741]172 ** ------------------------------------------------------------------------------------------------------------- */
[4769]173inline bool BooleanReassociationPass::isOptimizable(const VertexData & data) {
[4771]174    switch (std::get<0>(data)) {
[4741]175        case PabloAST::ClassTypeId::And:
176        case PabloAST::ClassTypeId::Or:
177        case PabloAST::ClassTypeId::Xor:
178            return true;
179        default:
180            return false;
181    }
182}
183
[4769]184inline bool isNegated(const BooleanReassociationPass::VertexData & data) {
[4771]185    return (std::get<0>(data) == TypeId::Not) && (std::get<1>(data) != nullptr);
[4751]186}
[4741]187
[4769]188inline bool BooleanReassociationPass::isMutable(const VertexData & data, const PabloBlock &) {
[4771]189    return (std::get<0>(data) != TypeId::Var);
[4751]190}
191
[4769]192inline bool BooleanReassociationPass::isNonEscaping(const VertexData & data) {
[4771]193    return std::get<0>(data) != TypeId::Assign && std::get<0>(data) != TypeId::Next;
[4769]194}
195
196inline bool BooleanReassociationPass::isSameType(const VertexData & data1, const VertexData & data2) {
[4771]197    return std::get<0>(data1) == std::get<0>(data2);
[4769]198}
199
[4748]200/** ------------------------------------------------------------------------------------------------------------- *
[4751]201 * @brief getVertex
[4738]202 ** ------------------------------------------------------------------------------------------------------------- */
[4756]203template<typename ValueType, typename GraphType, typename MapType>
[4764]204static inline Vertex getVertex(const ValueType value, GraphType & G, MapType & M) {
[4756]205    const auto f = M.find(value);
[4751]206    if (f != M.end()) {
207        return f->second;
208    }
[4756]209    const auto u = add_vertex(value, G);
210    M.insert(std::make_pair(value, u));
[4751]211    return u;
212}
[4736]213
[4751]214/** ------------------------------------------------------------------------------------------------------------- *
[4768]215 * @brief printGraph
216 ** ------------------------------------------------------------------------------------------------------------- */
217static void printGraph(const PabloBlock & block, const Graph & G, const std::string name) {
218    raw_os_ostream out(std::cerr);
[4771]219
220    std::vector<unsigned> c(num_vertices(G));
221    strong_components(G, make_iterator_property_map(c.begin(), get(vertex_index, G), c[0]));
222
[4768]223    out << "digraph " << name << " {\n";
[4769]224    for (auto u : make_iterator_range(vertices(G))) {
[4768]225        if (in_degree(u, G) == 0 && out_degree(u, G) == 0) {
226            continue;
227        }
[4770]228        out << "v" << u << " [label=\"" << u << ": ";
[4769]229        PabloAST * expr;
230        TypeId typeId;
231        std::tie(typeId, expr) = G[u];
232        bool temporary = false;
233        bool error = false;
234        if (expr == nullptr) {
235            temporary = true;
236            switch (typeId) {
237                case TypeId::And:
238                    out << "And";
239                    break;
240                case TypeId::Or:
241                    out << "Or";
242                    break;
243                case TypeId::Xor:
244                    out << "Xor";
245                    break;
246                default:
247                    out << "???";
248                    error = true;
249                    break;
250            }
[4771]251        } else if (std::get<0>(G[u]) != TypeId::Var) {
[4768]252            if (LLVM_UNLIKELY(isa<If>(expr))) {
253                out << "If ";
254                PabloPrinter::print(cast<If>(expr)->getOperand(0), out);
255                out << ":";
256            } else if (LLVM_UNLIKELY(isa<While>(expr))) {
257                out << "While ";
258                PabloPrinter::print(cast<While>(expr)->getOperand(0), out);
259                out << ":";
260            } else {
261                PabloPrinter::print(cast<Statement>(expr), "", out);
262            }
263        } else {
264            PabloPrinter::print(expr, out);
265        }
266        out << "\"";
[4770]267        if (!BooleanReassociationPass::isMutable(G[u], block)) {
[4768]268            out << " style=dashed";
269        }
[4769]270        if (error) {
271            out << " color=red";
272        } else if (temporary) {
273            out << " color=blue";
274        }
[4768]275        out << "];\n";
276    }
277    for (auto e : make_iterator_range(edges(G))) {
[4771]278        const auto s = source(e, G);
279        const auto t = target(e, G);
280        out << "v" << s << " -> v" << t;
281        bool cyclic = (c[s] == c[t]);
282        if (G[e] || cyclic) {
283            out << " [";
284             if (G[e]) {
285                out << "label=\"";
286                PabloPrinter::print(G[e], out);
287                out << "\" ";
288             }
289             if (cyclic) {
290                out << "color=red ";
291             }
292             out << "]";
[4770]293        }
[4768]294        out << ";\n";
295    }
296
297    if (num_vertices(G) > 0) {
298
299        out << "{ rank=same;";
[4769]300        for (auto u : make_iterator_range(vertices(G))) {
[4771]301            if (in_degree(u, G) == 0 && out_degree(u, G) != 0) {
[4768]302                out << " v" << u;
303            }
304        }
305        out << "}\n";
306
307        out << "{ rank=same;";
[4769]308        for (auto u : make_iterator_range(vertices(G))) {
[4771]309            if (out_degree(u, G) == 0 && in_degree(u, G) != 0) {
[4768]310                out << " v" << u;
311            }
312        }
313        out << "}\n";
314
315    }
316
317    out << "}\n\n";
318    out.flush();
319}
320
321/** ------------------------------------------------------------------------------------------------------------- *
[4769]322 * @brief createTree
[4768]323 ** ------------------------------------------------------------------------------------------------------------- */
[4770]324static PabloAST * createTree(PabloBlock & block, const Vertex u, Graph & G) {
325    flat_set<PabloAST *> sources;
[4769]326    for (const auto e : make_iterator_range(in_edges(u, G))) {
[4771]327        PabloAST * expr = std::get<1>(G[source(e, G)]);
[4770]328        assert ("G contains a null input variable!" && (expr != nullptr));
329        sources.insert(expr);
[4768]330    }
[4770]331    circular_buffer<PabloAST *> Q(sources.begin(), sources.end());
[4771]332    const TypeId typeId = std::get<0>(G[u]);
[4751]333    while (Q.size() > 1) {
334        PabloAST * e1 = Q.front(); Q.pop_front();
335        PabloAST * e2 = Q.front(); Q.pop_front();
336        PabloAST * expr = nullptr;
[4760]337        // Note: this switch ought to compile to an array of function pointers to the appropriate method.
[4751]338        switch (typeId) {
339            case PabloAST::ClassTypeId::And:
340                expr = block.createAnd(e1, e2); break;
341            case PabloAST::ClassTypeId::Or:
342                expr = block.createOr(e1, e2); break;
343            case PabloAST::ClassTypeId::Xor:
344                expr = block.createXor(e1, e2); break;
345            default: break;
346        }
347        Q.push_back(expr);
348    }
[4770]349    PabloAST * const result = Q.front();
350    assert (result);
[4771]351    std::get<1>(G[u]) = result;
[4769]352    return result;
[4751]353}
[4736]354
[4751]355/** ------------------------------------------------------------------------------------------------------------- *
[4754]356 * @brief processScope
357 ** ------------------------------------------------------------------------------------------------------------- */
[4766]358inline void BooleanReassociationPass::processScope(PabloFunction & function, PabloBlock & block) {
[4754]359    Graph G;
[4763]360
[4761]361    circular_buffer<Vertex> Q(num_vertices(G));
[4768]362    topological_sort(G, std::back_inserter(Q));
[4765]363    block.setInsertPoint(nullptr);
[4761]364
365    while (!Q.empty()) {
[4768]366        const Vertex u = Q.back(); Q.pop_back();
[4769]367        if (LLVM_LIKELY(isMutable(G[u], block))) {
368            Statement * stmt = nullptr;
369            if (isOptimizable(G[u])) {
[4770]370                PabloAST * replacement = createTree(block, u, G);
371                if (LLVM_LIKELY(inCurrentBlock(replacement, block))) {
372                    stmt = cast<Statement>(replacement);
373                } else { // optimization reduced this to a Constant, Var or an outer-scope statement
374                    continue;
375                }
[4769]376            } else { // update any potential mappings
[4771]377                stmt = cast<Statement>(std::get<1>(G[u]));
[4769]378            }
379            assert (stmt);
[4770]380            assert (inCurrentBlock(stmt, block));
[4769]381            for (auto e : make_iterator_range(out_edges(u, G))) {
382                if (G[e] && G[e] != stmt) {
[4771]383                    PabloAST * expr = std::get<1>(G[target(e, G)]);
[4769]384                    if (expr) { // processing a yet-to-be created value
385                        cast<Statement>(expr)->replaceUsesOfWith(G[e], stmt);
[4763]386                    }
[4762]387                }
[4761]388            }
[4769]389            block.insert(stmt);
[4761]390        }
[4760]391    }
[4751]392}
393
394/** ------------------------------------------------------------------------------------------------------------- *
[4769]395 * @brief getVertex
396 ** ------------------------------------------------------------------------------------------------------------- */
397static inline Vertex getVertex(PabloAST * expr, Graph & G, Map & M, const PabloBlock & block) {
398    const auto f = M.find(expr);
399    if (f != M.end()) {
400        return f->second;
401    }
402    // To simplify future analysis, every statement not in the current block will be recorded as a Var.
403    const TypeId typeId = inCurrentBlock(expr, block) ? expr->getClassTypeId() : TypeId::Var;
404    const auto u = add_vertex(std::make_pair(typeId, expr), G);
405    M.insert(std::make_pair(expr, u));
406    return u;
407}
408
409/** ------------------------------------------------------------------------------------------------------------- *
[4751]410 * @brief summarizeAST
411 *
[4769]412 * This function scans through a scope blockand computes a DAG G in which any sequences of AND, OR or XOR functions
413 * are "flattened" (i.e., allowed to have any number of inputs.)
[4751]414 ** ------------------------------------------------------------------------------------------------------------- */
[4762]415void BooleanReassociationPass::summarizeAST(PabloBlock & block, Graph & G) const {
[4756]416    Map M;
[4762]417    // Compute the base def-use graph ...
418    for (Statement * stmt : block) {
[4769]419        const Vertex u = getVertex(stmt, G, M, block);
[4762]420        for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
421            PabloAST * const op = stmt->getOperand(i);
422            if (LLVM_UNLIKELY(isa<Integer>(op) || isa<String>(op))) {
423                continue;
424            }
[4769]425            const Vertex v = getVertex(op, G, M, block);
[4771]426            add_edge(op, v, u, G);
[4769]427            // If this operand is a Not operation that is not in this PabloBlock,
428            // pull its input operand in. It may lead to future optimizations.
429            if (LLVM_UNLIKELY(isa<Not>(op) && !inCurrentBlock(cast<Not>(op), block))) {
[4771]430                PabloAST * const negatedValue = cast<Not>(op)->getExpr();
431                add_edge(negatedValue, getVertex(negatedValue, G, M, block), v, G);
[4769]432            }
[4762]433        }
434        if (isa<If>(stmt)) {
435            for (Assign * def : cast<const If>(stmt)->getDefined()) {
[4769]436                const Vertex v = getVertex(def, G, M, block);
[4768]437                add_edge(def, u, v, G);
438                resolveUsages(v, def, block, G, M, stmt);
[4762]439            }
440        } else if (isa<While>(stmt)) {
[4771]441            // To keep G a DAG, we need to do a bit of surgery on loop variants because
442            // the next variables it produces can be used within the condition. Instead,
443            // we make the loop dependent on the original value of each Next node and
444            // the Next node dependent on the loop.
[4762]445            for (Next * var : cast<const While>(stmt)->getVariants()) {
[4769]446                const Vertex v = getVertex(var, G, M, block);
[4771]447                assert (in_degree(v, G) == 1);
448                add_edge(nullptr, source(first(in_edges(v, G)), G), u, G);
449                remove_edge(v, u, G);
[4768]450                add_edge(var, u, v, G);
451                resolveUsages(v, var, block, G, M, stmt);
[4762]452            }
[4763]453        } else {
[4764]454            resolveUsages(u, stmt, block, G, M);
[4736]455        }
[4762]456    }
[4769]457    std::vector<Vertex> mapping(num_vertices(G));
[4771]458    summarizeGraph(block, G, mapping);
[4768]459}
[4736]460
[4768]461/** ------------------------------------------------------------------------------------------------------------- *
462 * @brief resolveUsages
463 ** ------------------------------------------------------------------------------------------------------------- */
464void BooleanReassociationPass::resolveUsages(const Vertex u, PabloAST * expr, PabloBlock & block, Graph & G, Map & M, Statement * ignoreIfThis) const {
[4763]465    for (PabloAST * user : expr->users()) {
466        assert (user);
[4764]467        if (LLVM_LIKELY(user != expr && isa<Statement>(user))) {
[4763]468            PabloBlock * parent = cast<Statement>(user)->getParent();
469            assert (parent);
470            if (LLVM_UNLIKELY(parent != &block)) {
471                for (;;) {
472                    if (LLVM_UNLIKELY(parent == nullptr)) {
473                        assert (isa<Assign>(expr) || isa<Next>(expr));
474                        break;
475                    } else if (parent->getParent() == &block) {
476                        const auto f = mResolvedScopes.find(parent);
477                        if (LLVM_UNLIKELY(f == mResolvedScopes.end())) {
478                            throw std::runtime_error("Failed to resolve scope block!");
479                        }
[4771]480                        Statement * const branch = f->second;
[4769]481                        if (LLVM_UNLIKELY(branch == ignoreIfThis)) {
[4768]482                            break;
483                        }
[4769]484                        // Add in a Var denoting the user of this expression so that it can be updated if expr changes.
[4771]485                        const Vertex v = getVertex(user, G, M, block);                       
[4769]486                        add_edge(expr, u, v, G);
[4771]487
[4769]488                        const Vertex w = getVertex(branch, G, M, block);
489                        add_edge(nullptr, v, w, G);
[4763]490                        break;
491                    }
492                    parent = parent->getParent();
493                }
494            }
495        }
496    }
497}
[4738]498
[4753]499/** ------------------------------------------------------------------------------------------------------------- *
[4769]500 * @brief summarizeGraph
501 ** ------------------------------------------------------------------------------------------------------------- */
[4771]502inline void BooleanReassociationPass::summarizeGraph(const PabloBlock & block, Graph & G, std::vector<Vertex> & mapping) {
[4769]503    std::vector<Vertex> reverse_topological_ordering;
504    reverse_topological_ordering.reserve(num_vertices(G));
[4771]505
[4769]506    topological_sort(G, std::back_inserter(reverse_topological_ordering));
507    assert(mapping.size() >= num_vertices(G));
508    for (const Vertex u : reverse_topological_ordering) {
509        if (LLVM_LIKELY(out_degree(u, G) > 0)) {
510            if (isOptimizable(G[u])) {
511                if (LLVM_UNLIKELY(in_degree(u, G) == 1)) {
512                    // We have a redundant node here that'll simply end up being a duplicate
513                    // of the input value. Remove it and add any of its outgoing edges to its
514                    // input node.
515                    const auto ei = first(in_edges(u, G));
516                    const Vertex v = source(ei, G);
517                    for (auto ej : make_iterator_range(out_edges(u, G))) {
518                        const Vertex w = target(ej, G);
519                        add_edge(G[ei], v, w, G);
520                        if (mapping[w] == mapping[u]) {
521                            mapping[w] = v;
522                        }
523                    }
524                    clear_vertex(u, G);
[4771]525                    std::get<0>(G[u]) = TypeId::Var;
[4769]526                    mapping[u] = v;
527                    continue;
528                } else if (LLVM_UNLIKELY(out_degree(u, G) == 1)) {
529                    // Otherwise if we have a single user, we have a similar case as above but
530                    // we can only merge this vertex into the outgoing instruction if they are
531                    // of the same type.
532                    const auto ei = first(out_edges(u, G));
533                    const Vertex v = target(ei, G);
534                    if (LLVM_UNLIKELY(isSameType(G[v], G[u]))) {
535                        for (auto ej : make_iterator_range(in_edges(u, G))) {
536                            add_edge(G[ei], source(ej, G), v, G);
537                        }
538                        clear_vertex(u, G);
[4771]539                        std::get<0>(G[u]) = TypeId::Var;
[4769]540                        mapping[u] = v;
541                    }
542                }
543            }
544        } else if (isNonEscaping(G[u])) {
545            clear_in_edges(u, G);
[4771]546            std::get<0>(G[u]) = TypeId::Var;
[4769]547        }
[4771]548    }   
[4769]549}
550
551/** ------------------------------------------------------------------------------------------------------------- *
[4760]552 * @brief enumerateBicliques
[4756]553 *
554 * Adaptation of the MICA algorithm as described in "Consensus algorithms for the generation of all maximal
555 * bicliques" by Alexe et. al. (2003). Note: this implementation considers all verticies with an in-degree of 0
[4760]556 * to be in bipartition A and their adjacencies to be in B.
[4758]557  ** ------------------------------------------------------------------------------------------------------------- */
[4760]558template <class Graph>
[4765]559static BicliqueSet enumerateBicliques(const Graph & G, const VertexSet & A) {
[4757]560    using IntersectionSets = std::set<VertexSet>;
[4756]561
[4757]562    IntersectionSets B1;
[4765]563    for (auto u : A) {
564        B1.insert(std::move(incomingVertexSet(u, G)));
[4756]565    }
566
[4766]567    IntersectionSets B(B1);
[4758]568
[4757]569    IntersectionSets Bi;
[4765]570
[4756]571    VertexSet clique;
572    for (auto i = B1.begin(); i != B1.end(); ++i) {
573        for (auto j = i; ++j != B1.end(); ) {
574            std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(clique));
575            if (clique.size() > 0) {
[4765]576                if (B.count(clique) == 0) {
[4758]577                    Bi.insert(clique);
578                }
[4756]579                clique.clear();
580            }
581        }
582    }
583
584    for (;;) {
585        if (Bi.empty()) {
586            break;
587        }
[4765]588        B.insert(Bi.begin(), Bi.end());
[4757]589        IntersectionSets Bk;
[4756]590        for (auto i = B1.begin(); i != B1.end(); ++i) {
591            for (auto j = Bi.begin(); j != Bi.end(); ++j) {
592                std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(clique));
593                if (clique.size() > 0) {
[4765]594                    if (B.count(clique) == 0) {
[4756]595                        Bk.insert(clique);
596                    }
597                    clique.clear();
598                }
599            }
600        }
601        Bi.swap(Bk);
602    }
603
[4765]604    BicliqueSet cliques;
605    cliques.reserve(B.size());
606    for (auto Bi = B.begin(); Bi != B.end(); ++Bi) {
[4766]607        VertexSet Ai(A);
608        for (const Vertex u : *Bi) {
609            VertexSet Aj = outgoingVertexSet(u, G);
[4765]610            VertexSet Ak;
611            std::set_intersection(Ai.begin(), Ai.end(), Aj.begin(), Aj.end(), std::back_inserter(Ak));
612            Ai.swap(Ak);
[4756]613        }
[4765]614        cliques.emplace_back(std::move(Ai), std::move(*Bi));
[4756]615    }
[4765]616    return std::move(cliques);
[4756]617}
618
619/** ------------------------------------------------------------------------------------------------------------- *
[4766]620 * @brief intersects
[4756]621 ** ------------------------------------------------------------------------------------------------------------- */
[4766]622template <class Type>
623inline bool intersects(const Type & A, const Type & B) {
624    auto first1 = A.begin(), last1 = A.end();
625    auto first2 = B.begin(), last2 = B.end();
626    while (first1 != last1 && first2 != last2) {
627        if (*first1 < *first2) {
628            ++first1;
629        } else if (*first2 < *first1) {
630            ++first2;
631        } else {
632            return true;
633        }
634    }
635    return false;
636}
[4765]637
[4766]638/** ------------------------------------------------------------------------------------------------------------- *
639 * @brief independentCliqueSets
640 ** ------------------------------------------------------------------------------------------------------------- */
641template <unsigned side>
[4767]642inline static BicliqueSet && independentCliqueSets(BicliqueSet && cliques, const unsigned minimum) {
[4766]643    using IndependentSetGraph = adjacency_list<hash_setS, vecS, undirectedS, unsigned>;
644
645    const auto l = cliques.size();
646    IndependentSetGraph I(l);
647
648    // Initialize our weights
649    for (unsigned i = 0; i != l; ++i) {
650        I[i] = std::pow(std::get<side>(cliques[i]).size(), 2);
651    }
652
653    // Determine our constraints
654    for (unsigned i = 0; i != l; ++i) {
655        for (unsigned j = i + 1; j != l; ++j) {
656            if (intersects(std::get<side>(cliques[i]), std::get<side>(cliques[j]))) {
657                add_edge(i, j, I);
658            }
[4756]659        }
660    }
[4765]661
[4766]662    // Use the greedy algorithm to choose our independent set
663    VertexSet selected;
664    for (;;) {
665        unsigned w = 0;
666        Vertex u = 0;
667        for (unsigned i = 0; i != l; ++i) {
668            if (I[i] > w) {
669                w = I[i];
670                u = i;
671            }
672        }
[4767]673        if (w < minimum) break;
[4766]674        selected.push_back(u);
675        I[u] = 0;
676        for (auto v : make_iterator_range(adjacent_vertices(u, I))) {
677            I[v] = 0;
678        }
679    }
680
681    // Sort the selected list and then remove the unselected cliques
682    std::sort(selected.begin(), selected.end(), std::greater<Vertex>());
683    auto end = cliques.end();
684    for (const unsigned offset : selected) {
685        end = cliques.erase(cliques.begin() + offset + 1, end) - 1;
686    }
687    cliques.erase(cliques.begin(), end);
688
689    return std::move(cliques);
690}
691
692/** ------------------------------------------------------------------------------------------------------------- *
693 * @brief removeUnhelpfulBicliques
694 *
695 * An intermediary vertex could have more than one outgoing edge but if any edge is not directed to a vertex in our
696 * biclique, we'll need to compute that specific value anyway. Remove them from the clique set and if there are not
697 * enough vertices in the biclique to make distribution profitable, eliminate the clique.
698 ** ------------------------------------------------------------------------------------------------------------- */
699static BicliqueSet && removeUnhelpfulBicliques(BicliqueSet && cliques, const Graph & G, DistributionGraph & H) {
700    for (auto ci = cliques.begin(); ci != cliques.end(); ) {
701        const auto cardinalityA = std::get<0>(*ci).size();
[4765]702        VertexSet & B = std::get<1>(*ci);
703        for (auto bi = B.begin(); bi != B.end(); ) {
704            if (out_degree(H[*bi], G) == cardinalityA) {
705                ++bi;
706            } else {
707                bi = B.erase(bi);
[4756]708            }
709        }
[4765]710        if (B.size() > 1) {
711            ++ci;
712        } else {
[4766]713            ci = cliques.erase(ci);
[4756]714        }
715    }
[4766]716    return std::move(cliques);
717}
[4756]718
[4766]719/** ------------------------------------------------------------------------------------------------------------- *
720 * @brief safeDistributionSets
721 ** ------------------------------------------------------------------------------------------------------------- */
[4769]722static DistributionSets safeDistributionSets(const Graph & G, DistributionGraph & H) {
[4766]723    const auto F = makeGraphFacade(H);
[4765]724    DistributionSets T;
[4767]725    BicliqueSet lowerSet = independentCliqueSets<1>(removeUnhelpfulBicliques(enumerateBicliques(F, sinks(H)), G, H), 1);
[4766]726    for (Biclique & lower : lowerSet) {
[4767]727        BicliqueSet upperSet = independentCliqueSets<0>(enumerateBicliques(F, std::get<1>(lower)), 2);
[4766]728        for (Biclique & upper : upperSet) {
729            T.emplace_back(std::move(std::get<1>(upper)), std::move(std::get<0>(upper)), std::get<0>(lower));
[4756]730        }
731    }
[4765]732    return std::move(T);
[4758]733}
734
735/** ------------------------------------------------------------------------------------------------------------- *
[4765]736 * @brief generateDistributionGraph
[4758]737 ** ------------------------------------------------------------------------------------------------------------- */
[4769]738void generateDistributionGraph(const Graph & G, DistributionGraph & H) {
[4765]739    DistributionMap M;
740    for (const Vertex u : make_iterator_range(vertices(G))) {
[4771]741        const TypeId outerTypeId = std::get<0>(G[u]);
[4769]742        if (outerTypeId == TypeId::And || outerTypeId == TypeId::Or) {
743            const TypeId innerTypeId = (outerTypeId == TypeId::And) ? TypeId::Or : TypeId::And;
744            flat_set<Vertex> distributable;
745            for (auto e : make_iterator_range(in_edges(u, G))) {
746                const Vertex v = source(e, G);
[4771]747                if (LLVM_UNLIKELY(std::get<0>(G[v]) == innerTypeId)) {
[4769]748                    bool safe = true;
749                    for (const auto e : make_iterator_range(out_edges(v, G))) {
[4771]750                        if (std::get<0>(G[target(e, G)]) != outerTypeId) {
[4769]751                            safe = false;
752                            break;
[4758]753                        }
754                    }
[4769]755                    if (safe) {
756                        distributable.insert(v);
757                    }
758                }
759            }
760            if (LLVM_LIKELY(distributable.size() > 1)) {
761                // We're only interested in computing a subgraph of G in which every source has an out-degree
762                // greater than 1. Otherwise we'd only end up permuting the AND/OR sequence with no logical
763                // benefit. (Note: this does not consider register pressure / liveness.)
764                flat_map<Vertex, bool> observedMoreThanOnce;
765                bool anyOpportunities = false;
766                for (const Vertex v : distributable) {
767                    for (auto e : make_iterator_range(in_edges(v, G))) {
768                        const Vertex w = source(e, G);
769                        auto ob = observedMoreThanOnce.find(w);
770                        if (ob == observedMoreThanOnce.end()) {
771                            observedMoreThanOnce.emplace(w, false);
772                        } else {
773                            ob->second = true;
774                            anyOpportunities = true;
[4761]775                        }
[4769]776                    }
777                }
778                if (anyOpportunities) {
779                    for (const auto ob : observedMoreThanOnce) {
[4771]780                        if (std::get<1>(ob)) {
781                            const Vertex w = std::get<0>(ob);
[4769]782                            for (auto e : make_iterator_range(out_edges(w, G))) {
783                                const Vertex v = target(e, G);
784                                if (distributable.count(v)) {
785                                    const Vertex y = getVertex(v, H, M);
786                                    add_edge(y, getVertex(u, H, M), H);
787                                    add_edge(getVertex(w, H, M), y, H);
[4765]788                                }
789                            }
790                        }
791                    }
[4761]792                }
793            }
794        }
795    }
[4760]796}
797
798/** ------------------------------------------------------------------------------------------------------------- *
[4753]799 * @brief redistributeAST
800 *
801 * Apply the distribution law to reduce computations whenever possible.
802 ** ------------------------------------------------------------------------------------------------------------- */
[4769]803void BooleanReassociationPass::redistributeAST(const PabloBlock & block, Graph & G) const {
[4766]804
[4769]805    std::vector<Vertex> mapping(num_vertices(G) + 16);
806    std::iota(mapping.begin(), mapping.end(), 0); // 0,1,.....n
807
[4760]808    for (;;) {
809
[4765]810        DistributionGraph H;
[4760]811
[4769]812        generateDistributionGraph(G, H);
[4754]813
[4760]814        // If we found no potential opportunities then we cannot apply the distribution law to any part of G.
815        if (num_vertices(H) == 0) {
816            break;
817        }
[4754]818
[4769]819        const DistributionSets distributionSets = safeDistributionSets(G, H);
[4761]820
[4765]821        if (LLVM_UNLIKELY(distributionSets.empty())) {
[4760]822            break;
[4759]823        }
[4756]824
[4766]825        for (const DistributionSet & set : distributionSets) {
[4769]826
[4766]827            // Each distribution tuple consists of the sources, intermediary, and sink nodes.
828            const VertexSet & sources = std::get<0>(set);
829            const VertexSet & intermediary = std::get<1>(set);
830            const VertexSet & sinks = std::get<2>(set);
[4759]831
[4771]832            const TypeId outerTypeId = std::get<0>(G[mapping[H[sinks.front()]]]);
[4766]833            assert (outerTypeId == TypeId::And || outerTypeId == TypeId::Or);
834            const TypeId innerTypeId = (outerTypeId == TypeId::Or) ? TypeId::And : TypeId::Or;
[4759]835
[4769]836            // Update G to match the desired changes (TODO: modify this to reuse a discarded vertex instead)
837            const Vertex x = add_vertex(std::make_pair(outerTypeId, nullptr), G);
838            const Vertex y = add_vertex(std::make_pair(innerTypeId, nullptr), G);
839            mapping.resize(num_vertices(G));
840            mapping[x] = x;
841            mapping[y] = y;
842
843            for (const Vertex i : intermediary) {
844                const auto u = mapping[H[i]];
[4771]845                assert (std::get<0>(G[u]) == innerTypeId);
[4766]846                for (const Vertex t : sinks) {
[4771]847                    assert (std::get<0>(G[mapping[H[t]]]) == outerTypeId);
848                    remove_edge(u, mapping[H[t]], G);
[4766]849                }
[4769]850                add_edge(nullptr, u, x, G);
851            }           
[4759]852
[4766]853            for (const Vertex s : sources) {
[4769]854                const auto u = mapping[H[s]];
855                for (const Vertex i : intermediary) {
[4771]856                    remove_edge(u, mapping[H[i]], G);
[4769]857                }
858                add_edge(nullptr, u, y, G);
[4766]859            }
[4769]860
[4768]861            add_edge(nullptr, x, y, G);
[4759]862
[4769]863            for (const Vertex t : sinks) {
864                const auto v = mapping[H[t]];
[4771]865                add_edge(std::get<1>(G[v]), y, v, G);
[4766]866            }
[4767]867
[4771]868            summarizeGraph(block, G, mapping);
[4766]869        }
[4759]870    }
[4736]871}
[4756]872
873}
Note: See TracBrowser for help on using the repository browser.