Ignore:
Timestamp:
Sep 2, 2015, 4:39:39 PM (4 years ago)
Author:
nmedfort
Message:

Work on distribution law.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/booleanreassociationpass.cpp

    r4754 r4756  
    44#include <boost/circular_buffer.hpp>
    55#include <boost/graph/adjacency_list.hpp>
     6#include <boost/graph/filtered_graph.hpp>
    67#include <boost/graph/topological_sort.hpp>
    78#include <pablo/optimizers/pablo_simplifier.hpp>
     9#include <algorithm>
    810#include <queue>
     11#include <set>
    912#include <iostream>
    1013#include <pablo/printer_pablos.h>
     
    1922using Vertex = Graph::vertex_descriptor;
    2023using VertexQueue = circular_buffer<Vertex>;
    21 using Map = std::unordered_map<PabloAST *, Vertex>;
     24using Map = BooleanReassociationPass::Map;
    2225using EdgeQueue = std::queue<std::pair<Vertex, Vertex>>;
    23 
    24 static void redistributeAST(PabloBlock &block, Graph & G);
    2526
    2627/** ------------------------------------------------------------------------------------------------------------- *
     
    167168 * @brief getVertex
    168169 ** ------------------------------------------------------------------------------------------------------------- */
    169 static inline Vertex getVertex(PabloAST * expr, Graph & G, Map & M) {
    170     const auto f = M.find(expr);
     170template<typename ValueType, typename GraphType, typename MapType>
     171static inline Vertex getVertex(ValueType value, GraphType & G, MapType & M) {
     172    const auto f = M.find(value);
    171173    if (f != M.end()) {
    172174        return f->second;
    173175    }
    174     const auto u = add_vertex(expr, G);
    175     M.insert(std::make_pair(expr, u));
     176    const auto u = add_vertex(value, G);
     177    M.insert(std::make_pair(value, u));
    176178    return u;
    177179}
     
    204206 * @brief printGraph
    205207 ** ------------------------------------------------------------------------------------------------------------- */
    206 static void printGraph(PabloBlock & block, const Graph & G) {
     208static void printGraph(PabloBlock & block, const Graph & G, const std::string name) {
    207209    raw_os_ostream out(std::cerr);
    208     out << "digraph G {\n";
     210    out << "digraph " << name << " {\n";
    209211    for (auto u : make_iterator_range(vertices(G))) {
    210212        out << "v" << u << " [label=\"";
     
    235237    }
    236238
    237     out << "{ rank=same;";
    238     for (auto u : make_iterator_range(vertices(G))) {
    239         if (in_degree(u, G) == 0 && out_degree(u, G) != 0) {
    240             out << " v" << u;
    241         }
    242     }
    243     out << "}\n";
    244 
    245     out << "{ rank=same;";
    246     for (auto u : make_iterator_range(vertices(G))) {
    247         if (out_degree(u, G) == 0 && in_degree(u, G) != 0) {
    248             out << " v" << u;
    249         }
    250     }
    251     out << "}\n";
     239    if (num_vertices(G) > 0) {
     240
     241        out << "{ rank=same;";
     242        for (auto u : make_iterator_range(vertices(G))) {
     243            if (in_degree(u, G) == 0 && out_degree(u, G) != 0) {
     244                out << " v" << u;
     245            }
     246        }
     247        out << "}\n";
     248
     249        out << "{ rank=same;";
     250        for (auto u : make_iterator_range(vertices(G))) {
     251            if (out_degree(u, G) == 0 && in_degree(u, G) != 0) {
     252                out << " v" << u;
     253            }
     254        }
     255        out << "}\n";
     256
     257    }
    252258
    253259    out << "}\n\n";
     
    256262
    257263/** ------------------------------------------------------------------------------------------------------------- *
     264 * @brief printGraph
     265 ** ------------------------------------------------------------------------------------------------------------- */
     266template<typename SubgraphType>
     267static void printGraph(PabloBlock & block, const SubgraphType & S, const Graph & G, const std::string name) {
     268    raw_os_ostream out(std::cerr);
     269    out << "digraph " << name << " {\n";
     270    for (auto u : make_iterator_range(vertices(S))) {
     271        out << "v" << u << " [label=\"";
     272        PabloAST * expr = G[S[u]];
     273        if (isa<Statement>(expr)) {
     274            if (LLVM_UNLIKELY(isa<If>(expr))) {
     275                out << "If ";
     276                PabloPrinter::print(cast<If>(expr)->getOperand(0), out);
     277                out << ":";
     278            } else if (LLVM_UNLIKELY(isa<While>(expr))) {
     279                out << "While ";
     280                PabloPrinter::print(cast<While>(expr)->getOperand(0), out);
     281                out << ":";
     282            } else {
     283                PabloPrinter::print(cast<Statement>(expr), "", out);
     284            }
     285        } else {
     286            PabloPrinter::print(expr, out);
     287        }
     288        out << "\"";
     289        if (!inCurrentBlock(expr, block)) {
     290            out << " style=dashed";
     291        }
     292        out << "];\n";
     293    }
     294    for (auto e : make_iterator_range(edges(S))) {
     295        out << "v" << source(e, S) << " -> v" << target(e, S) << ";\n";
     296    }
     297
     298    if (num_vertices(S) > 0) {
     299
     300        out << "{ rank=same;";
     301        for (auto u : make_iterator_range(vertices(S))) {
     302            if (in_degree(u, S) == 0 && out_degree(u, S) != 0) {
     303                out << " v" << u;
     304            }
     305        }
     306        out << "}\n";
     307
     308        out << "{ rank=same;";
     309        for (auto u : make_iterator_range(vertices(S))) {
     310            if (out_degree(u, S) == 0 && in_degree(u, S) != 0) {
     311                out << " v" << u;
     312            }
     313        }
     314        out << "}\n";
     315
     316    }
     317
     318    out << "}\n\n";
     319    out.flush();
     320}
     321
     322/** ------------------------------------------------------------------------------------------------------------- *
    258323 * @brief processScope
    259324 ** ------------------------------------------------------------------------------------------------------------- */
     
    261326
    262327    Graph G;
    263     summarizeAST(block, std::move(terminals), G);
     328
     329    summarizeAST(block, terminals, G);
    264330    redistributeAST(block, G);
    265331
    266 
    267 
    268 
    269     printGraph(block, G);
     332//    for (;;) {
     333//        summarizeAST(block, terminals, G);
     334//        if (redistributeAST(block, G)) {
     335//            G.clear();
     336//        } else {
     337//            break;
     338//        }
     339//    }
     340
     341    printGraph(block, G, "G");
    270342
    271343}
     
    275347 *
    276348 * This function scans through a basic block (starting by its terminals) and computes a DAG in which any sequences
    277  * of AND, OR or XOR functions are "flattened" and allowed to have any number of inputs. This allows us to
     349 * of AND, OR or XOR functions are "flattened" (i.e., allowed to have any number of inputs.) This allows us to
    278350 * reassociate them in the most efficient way possible.
    279351 ** ------------------------------------------------------------------------------------------------------------- */
    280 void BooleanReassociationPass::summarizeAST(PabloBlock & block, std::vector<Statement *> && terminals, Graph & G) {
    281 
    282     Map M;
     352void BooleanReassociationPass::summarizeAST(PabloBlock & block, std::vector<Statement *> terminals, Graph & G) const {
     353
    283354    VertexQueue Q(128);
    284355    EdgeQueue E;
     356    Map M;
    285357
    286358    for (;;) {
     
    542614}
    543615
     616using VertexSet = std::vector<Vertex>;
     617using VertexSets = std::set<VertexSet>;
     618
     619/** ------------------------------------------------------------------------------------------------------------- *
     620 * @brief mica
     621 *
     622 * Adaptation of the MICA algorithm as described in "Consensus algorithms for the generation of all maximal
     623 * bicliques" by Alexe et. al. (2003). Note: this implementation considers all verticies with an in-degree of 0
     624 * to be in bipartition A and their adjacencies to be in bipartition B. Because we do not care about the rank 1
     625 * (star) cliques, this does not record them.
     626 ** ------------------------------------------------------------------------------------------------------------- */
     627static std::vector<VertexSet> mica(const Graph & G) {
     628
     629    VertexSets B1;
     630    for (auto u : make_iterator_range(vertices(G))) {
     631        if (in_degree(u, G) == 0) {
     632            VertexSet B;
     633            B.reserve(out_degree(u, G));
     634            for (auto e : make_iterator_range(out_edges(u, G))) {
     635                B.push_back(target(e, G));
     636            }
     637            std::sort(B.begin(), B.end()); // note: these already ought to be in order
     638            B1.insert(std::move(B));
     639        }
     640    }
     641
     642    VertexSets Bi;
     643
     644    VertexSet clique;
     645    for (auto i = B1.begin(); i != B1.end(); ++i) {
     646        for (auto j = i; ++j != B1.end(); ) {
     647            std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(clique));
     648            if (clique.size() > 0) {
     649                Bi.insert(clique);
     650                clique.clear();
     651            }
     652        }
     653    }
     654
     655    VertexSets C;
     656
     657    for (;;) {
     658        if (Bi.empty()) {
     659            break;
     660        }
     661        C.insert(Bi.begin(), Bi.end());
     662
     663        VertexSets Bk;
     664        for (auto i = B1.begin(); i != B1.end(); ++i) {
     665            for (auto j = Bi.begin(); j != Bi.end(); ++j) {
     666                std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(clique));
     667                if (clique.size() > 0) {
     668                    if (C.count(clique) == 0) {
     669                        Bk.insert(clique);
     670                    }
     671                    clique.clear();
     672                }
     673            }
     674        }
     675        Bi.swap(Bk);
     676    }
     677
     678    return std::vector<VertexSet>(C.begin(), C.end());
     679}
     680
     681/** ------------------------------------------------------------------------------------------------------------- *
     682 * @brief areNonDisjoint
     683 ** ------------------------------------------------------------------------------------------------------------- */
     684template <class Type>
     685inline bool areNonDisjoint(const Type & A, const Type & B) {
     686    auto first1 = A.begin(), last1 = A.end();
     687    auto first2 = B.begin(), last2 = B.end();
     688    while (first1 != last1 && first2 != last2) {
     689        if (*first1 < *first2) {
     690            ++first1;
     691        } else if (*first2 < *first1) {
     692            ++first2;
     693        } else {
     694            return true;
     695        }
     696    }
     697    return false;
     698}
     699
     700/** ------------------------------------------------------------------------------------------------------------- *
     701 * @brief maximalIndependentSet
     702 ** ------------------------------------------------------------------------------------------------------------- */
     703static void maximalIndependentSet(std::vector<VertexSet> & V) {
     704    using IndependentSetGraph = adjacency_list<hash_setS, vecS, undirectedS, unsigned>;
     705    const auto l = V.size();
     706    IndependentSetGraph I(l);
     707    // Initialize our weights
     708    for (unsigned i = 0; i != l; ++i) {
     709        I[i] = std::pow(V[i].size(), 2);
     710    }
     711    // Determine our constraints
     712    for (unsigned i = 0; i != l; ++i) {
     713        for (unsigned j = i + 1; j != l; ++j) {
     714            if (areNonDisjoint(V[i], V[j])) {
     715                add_edge(i, j, I);
     716            }
     717        }
     718    }
     719    // Use the greedy algorithm to choose our independent set (TODO: try the similar randomized approach)
     720    std::vector<Vertex> selected;
     721
     722    std::vector<bool> ignored(l, false);
     723    for (;;) {
     724        unsigned w = 0;
     725        Vertex u = 0;
     726        for (unsigned i = 0; i != l; ++i) {
     727            if (!ignored[i] && I[i] > w) {
     728                w = I[i];
     729                u = i;
     730            }
     731        }
     732        if (w < 2) break;
     733        selected.push_back(u);
     734        ignored[u] = true;
     735        for (auto v : make_iterator_range(adjacent_vertices(u, I))) {
     736            ignored[v] = true;
     737        }
     738    }
     739
     740    // Sort the selected list and then remove the unselected sets from V
     741    std::sort(selected.begin(), selected.end(), std::greater<unsigned>());
     742    auto end = V.end();
     743    for (const unsigned offset : selected) {
     744        end = V.erase(V.begin() + offset + 1, end) - 1;
     745    }
     746    V.erase(V.begin(), end);
     747
     748}
     749
     750
     751/** ------------------------------------------------------------------------------------------------------------- *
     752 * @brief maximalIndependentBicliqueSet
     753 ** ------------------------------------------------------------------------------------------------------------- */
     754static void maximalIndependentBicliqueSet(Graph & G) {
     755    // First enumerate our bicliques in G.
     756    auto R = mica(G);
     757    // Then compute the maximal independent set of the vertices in the B bipartition.
     758    // NOTE: this means vertices in A can point to more than one vertex in B. These
     759    // have to be resolved specially later.
     760    maximalIndependentSet(R);
     761    // Update G to reflect our maximal independent biclique set
     762    std::vector<VertexSet> L;
     763    for (const VertexSet & B : R) {
     764        // Compute our A set
     765        VertexSet A;
     766        auto bi = B.begin();
     767        A.reserve(in_degree(*bi, G));
     768        for (auto e : make_iterator_range(in_edges(*bi, G))) {
     769            A.push_back(source(e, G));
     770        }
     771        std::sort(A.begin(), A.end());
     772        while (++bi != B.end()) {
     773            VertexSet Ai;
     774            Ai.reserve(in_degree(*bi, G));
     775            for (auto e : make_iterator_range(in_edges(*bi, G))) {
     776                Ai.push_back(source(e, G));
     777            }
     778            std::sort(Ai.begin(), Ai.end());
     779            VertexSet Ak;
     780            std::set_intersection(A.begin(), A.end(), Ai.begin(), Ai.end(), std::back_inserter(Ak));
     781            A.swap(Ak);
     782        }
     783        L.emplace_back(std::move(A));
     784    }
     785    for (auto u : make_iterator_range(vertices(G))) {
     786        if (in_degree(u, G) == 0) {
     787            clear_out_edges(u, G);
     788        }
     789    }
     790    for (unsigned i = 0; i != R.size(); ++i) {
     791        for (auto u : L[i]) {
     792            for (auto v : R[i]) {
     793                add_edge(u, v, G);
     794            }
     795        }
     796    }
     797}
     798
    544799/** ------------------------------------------------------------------------------------------------------------- *
    545800 * @brief redistributeAST
     
    547802 * Apply the distribution law to reduce computations whenever possible.
    548803 ** ------------------------------------------------------------------------------------------------------------- */
    549 static void redistributeAST(PabloBlock & block, Graph & G) {
     804bool BooleanReassociationPass::redistributeAST(PabloBlock & block, Graph & G) const {
    550805    using TypeId = PabloAST::ClassTypeId;
    551806
    552     // Process the graph in reverse topological order so that we end up recursively applying the distribution law
    553     // to the entire AST.
    554     std::vector<unsigned> ordering;
    555     ordering.reserve(num_vertices(G));
    556     topological_sort(G, std::back_inserter(ordering));
    557 
    558     for (const Vertex u : ordering) {
     807    Graph B;
     808    Map M;
     809
     810    for (const Vertex u : make_iterator_range(vertices(G))) {
    559811        const TypeId outerTypeId = G[u]->getClassTypeId();
    560812        if (outerTypeId == TypeId::And || outerTypeId == TypeId::Or) {
    561813            if (inCurrentBlock(cast<Statement>(G[u]), block)) {
    562814                const TypeId innerTypeId = (outerTypeId == TypeId::And) ? TypeId::Or : TypeId::And;
    563 
    564                 Graph H;
    565                 Map M;
    566 
    567815                flat_set<Vertex> distributable;
    568 
    569816                for (auto e : make_iterator_range(in_edges(u, G))) {
    570817                    const Vertex v = source(e, G);
    571818                    if (G[v]->getClassTypeId() == innerTypeId && inCurrentBlock(cast<Statement>(G[v]), block)) {
    572819                        bool safe = true;
    573                         // This operation is safe to transform if all of its users are AND or OR instructions.
    574                         if (out_degree(v, G) > 1) {
    575                             for (auto e : make_iterator_range(out_edges(v, G))) {
    576                                 const PabloAST * expr = G[target(e, G)];
    577                                 if (expr->getClassTypeId() != TypeId::And && expr->getClassTypeId() != TypeId::Or) {
    578                                     safe = false;
    579                                     break;
    580                                 }
     820                        for (PabloAST * user : G[v]->users()) {
     821                            if (user->getClassTypeId() != outerTypeId) {
     822                                safe = false;
     823                                break;
    581824                            }
    582825                        }
     
    586829                    }
    587830                }
    588 
    589                 if (distributable.size() > 1) {
    590                     flat_map<Vertex, unsigned> sources;
    591                     bool canRedistribute = false;
     831                if (LLVM_LIKELY(distributable.size() > 1)) {
     832                    // We're only interested in computing a subgraph of G in which every source has an out-degree
     833                    // greater than 1. Otherwise we'd only end up permuting the AND/OR sequence with no logical
     834                    // benefit. (Note: this does not consider register pressure / liveness.)
     835                    flat_map<Vertex, unsigned> observed;
     836                    bool anyOpportunities = false;
    592837                    for (const Vertex v : distributable) {
    593838                        for (auto e : make_iterator_range(in_edges(v, G))) {
    594839                            const Vertex w = source(e, G);
    595                             const auto f = sources.find(w);
    596                             if (f == sources.end()) {
    597                                 sources.emplace(w, 1);
     840                            const auto f = observed.find(w);
     841                            if (f == observed.end()) {
     842                                observed.emplace(w, 0);
    598843                            } else {
    599844                                f->second += 1;
    600                                 canRedistribute = true;
     845                                anyOpportunities = true;
    601846                            }
    602847                        }
    603848                    }
    604                     if (canRedistribute) {
    605                         Vertex w = 0;
    606                         unsigned count = 0;
    607                         const Vertex x = getVertex(G[u], H, M);
    608                         for (auto s : sources) {
    609                             std::tie(w, count) = s;
    610                             if (count > 1) {
    611                                 const Vertex z = getVertex(G[w], H, M);
    612                                 for (auto e : make_iterator_range(out_edges(w, G))) {
    613                                     const Vertex v = target(e, G);
    614                                     if (distributable.count(v)) {
    615                                         const Vertex y = getVertex(G[v], H, M);
    616                                         add_edge(y, x, H);
    617                                         add_edge(z, y, H);
     849                    if (anyOpportunities) {
     850                        for (auto ob : observed) {
     851                            if (std::get<1>(ob)) {
     852                                const Vertex v = std::get<0>(ob);
     853                                for (auto e : make_iterator_range(out_edges(v, G))) {
     854                                    const Vertex w = target(e, G);
     855                                    if (distributable.count(w)) {
     856                                        add_edge(getVertex(G[v], B, M), getVertex(G[w], B, M), B);
    618857                                    }
    619858                                }
     
    622861                    }
    623862                }
    624 
    625                 printGraph(block, H);
    626             }
    627         }
    628     }
    629 
    630 
    631 
    632 
    633 
    634 }
    635 
    636 /** ------------------------------------------------------------------------------------------------------------- *
    637  * @brief applyDistributionLaw
    638  ** ------------------------------------------------------------------------------------------------------------- */
    639 BooleanReassociationPass::BooleanReassociationPass() { }
    640 
    641 
    642 }
     863            }
     864        }
     865    }
     866
     867    // If we found no potential opportunities then we cannot apply the distribution law to any part of G.
     868    if (num_vertices(B) == 0) {
     869        return false;
     870    }
     871
     872    printGraph(block, B, "B0");
     873
     874    // By finding the maximal set of independent bicliques in S,
     875
     876    maximalIndependentBicliqueSet(B);
     877
     878
     879    printGraph(block, B, "B1");
     880
     881
     882
     883    return true;
     884}
     885
     886}
Note: See TracChangeset for help on using the changeset viewer.