Changeset 4765


Ignore:
Timestamp:
Sep 9, 2015, 4:22:53 PM (4 years ago)
Author:
nmedfort
Message:

Work on distribution law.

Location:
icGREP/icgrep-devel/icgrep/pablo/optimizers
Files:
2 edited

Legend:

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

    r4764 r4765  
    2525using EdgeQueue = std::queue<std::pair<Vertex, Vertex>>;
    2626using TypeId = PabloAST::ClassTypeId;
     27using DistributionGraph = adjacency_list<hash_setS, vecS, bidirectionalS, Vertex>;
     28using DistributionMap = flat_map<Graph::vertex_descriptor, DistributionGraph::vertex_descriptor>;
     29using VertexSet = std::vector<Vertex>;
     30using VertexSets = std::vector<VertexSet>;
     31using Biclique = std::pair<VertexSet, VertexSet>;
     32using BicliqueSet = std::vector<Biclique>;
     33using DistributionSet = std::tuple<std::vector<Vertex>, std::vector<Vertex>, std::vector<Vertex>>;
     34using DistributionSets = std::vector<DistributionSet>;
     35
     36template <class Graph>
     37static VertexSet incomingVertexSet(const Vertex u, const Graph & G) {
     38    VertexSet V;
     39    V.reserve(G.in_degree(u));
     40    for (auto e : make_iterator_range(G.in_edges(u))) {
     41        V.push_back(G.source(e));
     42    }
     43    std::sort(V.begin(), V.end());
     44    return std::move(V);
     45}
     46
     47template <class Graph>
     48static VertexSet outgoingVertexSet(const Vertex u, const Graph & G) {
     49    VertexSet V;
     50    V.reserve(G.out_degree(u));
     51    for (auto e : make_iterator_range(G.out_edges(u))) {
     52        V.push_back(G.target(e));
     53    }
     54    std::sort(V.begin(), V.end());
     55    return std::move(V);
     56}
    2757
    2858/** ------------------------------------------------------------------------------------------------------------- *
     
    3161bool BooleanReassociationPass::optimize(PabloFunction & function) {
    3262    BooleanReassociationPass brp;
    33 
    34     raw_os_ostream out(std::cerr);
    35 
    36     out << "BEFORE:\n";
    37     PabloPrinter::print(function.getEntryBlock().statements(), out);
    38     out << "----------------------------------------------------------\n";
    39     out.flush();
    40 
    4163    brp.resolveScopes(function);
    4264    brp.processScopes(function);
    4365    Simplifier::optimize(function);
    44 
    45     out << "AFTER:\n";
    46     PabloPrinter::print(function.getEntryBlock().statements(), out);
    47 
    4866    return true;
    4967}
     
    7492 ** ------------------------------------------------------------------------------------------------------------- */
    7593inline void BooleanReassociationPass::processScopes(PabloFunction & function) {
    76     std::vector<Statement *> terminals;
    77     for (unsigned i = 0; i != function.getNumOfResults(); ++i) {
    78         terminals.push_back(function.getResult(i));
    79     }
    80     processScopes(function.getEntryBlock(), std::move(terminals));
     94    processScopes(function.getEntryBlock());
    8195}
    8296
     
    8498 * @brief processScopes
    8599 ** ------------------------------------------------------------------------------------------------------------- */
    86 void BooleanReassociationPass::processScopes(PabloBlock & block, std::vector<Statement *> && terminals) {
    87     processScope(block, std::move(terminals));
     100void BooleanReassociationPass::processScopes(PabloBlock & block) {
    88101    for (Statement * stmt : block) {
    89102        if (isa<If>(stmt)) {
    90             const auto & defs = cast<const If>(stmt)->getDefined();
    91             std::vector<Statement *> terminals(defs.begin(), defs.end());
    92             processScopes(cast<If>(stmt)->getBody(), std::move(terminals));
     103            processScopes(cast<If>(stmt)->getBody());
    93104        } else if (isa<While>(stmt)) {
    94             const auto & vars = cast<const While>(stmt)->getVariants();
    95             std::vector<Statement *> terminals(vars.begin(), vars.end());
    96             processScopes(cast<While>(stmt)->getBody(), std::move(terminals));
    97         }
    98     }
     105            processScopes(cast<While>(stmt)->getBody());
     106        }
     107    }
     108    processScope(block);
    99109}
    100110
     
    149159    while (Q.size() > 1) {
    150160        PabloAST * e1 = Q.front(); Q.pop_front();
     161        // assert (isa<Statement>(e1) ? cast<Statement>(e1)->getParent() != nullptr : true);
    151162        PabloAST * e2 = Q.front(); Q.pop_front();
     163        // assert (isa<Statement>(e2) ? cast<Statement>(e2)->getParent() != nullptr : true);
    152164        PabloAST * expr = nullptr;
    153165        // Note: this switch ought to compile to an array of function pointers to the appropriate method.
     
    175187    out << "digraph " << name << " {\n";
    176188    for (auto u : make_iterator_range(vertices(G))) {
    177 //        if (in_degree(u, G) == 0 && out_degree(u, G) == 0) {
    178 //            continue;
    179 //        }
     189        if (in_degree(u, G) == 0 && out_degree(u, G) == 0) {
     190            continue;
     191        }
    180192        out << "v" << u << " [label=\"";
    181193        PabloAST * expr = G[u];
     
    294306 * @brief processScope
    295307 ** ------------------------------------------------------------------------------------------------------------- */
    296 inline void BooleanReassociationPass::processScope(PabloBlock & block, std::vector<Statement *> && terminals) {
     308inline void BooleanReassociationPass::processScope(PabloBlock & block) {
    297309    Graph G;
    298310
     
    305317
    306318    circular_buffer<PabloAST *> nodes;
    307     block.setInsertPoint(block.back());
     319    block.setInsertPoint(nullptr);
    308320
    309321    while (!Q.empty()) {
    310         const Vertex u = Q.front(); Q.pop_front();
     322        const Vertex u = Q.front();
     323        Q.pop_front();
    311324        PabloAST * expr = G[u];
    312325        if (LLVM_LIKELY(inCurrentBlock(expr, block))) {
     
    322335                        nodes.push_back(G[source(e, G)]);
    323336                    }
    324                     assert (nodes.size() == in_degree(u, G));
    325                     PabloAST * replacement = createTree(block, expr->getClassTypeId(), nodes);
    326 
    327                     cast<Statement>(expr)->replaceWith(replacement, true, false);
    328                     expr = replacement;
    329                     G[u] = replacement;
     337                    G[u] = createTree(block, expr->getClassTypeId(), nodes);
     338                    cast<Statement>(expr)->replaceWith(G[u], true, true);
     339                    if (LLVM_UNLIKELY(isa<Var>(G[u]))) {
     340                        continue;
     341                    }
     342                    expr = G[u];
    330343                }
    331344            }
     
    333346        }
    334347    }
     348
    335349}
    336350
     
    426440}
    427441
    428 using VertexSet = std::vector<Vertex>;
    429 using VertexSets = std::vector<VertexSet>;
    430 
    431 template <class Graph>
    432 static VertexSet incomingVertexSet(const Vertex u, const Graph & G) {
    433     VertexSet V;
    434     V.reserve(G.in_degree(u));
    435     for (auto e : make_iterator_range(G.in_edges(u))) {
    436         V.push_back(G.source(e));
    437     }
    438     std::sort(V.begin(), V.end());
    439     return std::move(V);
    440 }
    441 
    442 template <class Graph>
    443 static VertexSet outgoingVertexSet(const Vertex u, const Graph & G) {
    444     VertexSet V;
    445     V.reserve(G.out_degree(u));
    446     for (auto e : make_iterator_range(G.out_edges(u))) {
    447         V.push_back(G.target(e));
    448     }
    449     std::sort(V.begin(), V.end());
    450     return std::move(V);
    451 }
    452 
    453442/** ------------------------------------------------------------------------------------------------------------- *
    454443 * @brief enumerateBicliques
     
    459448  ** ------------------------------------------------------------------------------------------------------------- */
    460449template <class Graph>
    461 static VertexSets enumerateBicliques(const Graph & G) {
     450static BicliqueSet enumerateBicliques(const Graph & G, const VertexSet & A) {
    462451    using IntersectionSets = std::set<VertexSet>;
    463452
    464453    IntersectionSets B1;
    465     for (auto u : make_iterator_range(G.vertices())) {
    466         if (G.in_degree(u) == 0) {
    467             B1.insert(std::move(outgoingVertexSet(u, G)));
    468         }
    469     }
    470 
    471     IntersectionSets C(B1.begin(), B1.end());
     454    for (auto u : A) {
     455        B1.insert(std::move(incomingVertexSet(u, G)));
     456    }
     457
     458    IntersectionSets B(B1.begin(), B1.end());
    472459
    473460    IntersectionSets Bi;
     461
    474462    VertexSet clique;
    475463    for (auto i = B1.begin(); i != B1.end(); ++i) {
     
    477465            std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(clique));
    478466            if (clique.size() > 0) {
    479                 if (C.count(clique) == 0) {
     467                if (B.count(clique) == 0) {
    480468                    Bi.insert(clique);
    481469                }
     
    489477            break;
    490478        }
    491         C.insert(Bi.begin(), Bi.end());
     479        B.insert(Bi.begin(), Bi.end());
    492480        IntersectionSets Bk;
    493481        for (auto i = B1.begin(); i != B1.end(); ++i) {
     
    495483                std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(clique));
    496484                if (clique.size() > 0) {
    497                     if (C.count(clique) == 0) {
     485                    if (B.count(clique) == 0) {
    498486                        Bk.insert(clique);
    499487                    }
     
    504492        Bi.swap(Bk);
    505493    }
    506     return VertexSets(C.begin(), C.end());
    507 }
    508 
    509 /** ------------------------------------------------------------------------------------------------------------- *
    510  * @brief intersects
    511  ** ------------------------------------------------------------------------------------------------------------- */
    512 template <class Type>
    513 inline bool intersects(const Type & A, const Type & B) {
    514     auto first1 = A.begin(), last1 = A.end();
    515     auto first2 = B.begin(), last2 = B.end();
    516     while (first1 != last1 && first2 != last2) {
    517         if (*first1 < *first2) {
    518             ++first1;
    519         } else if (*first2 < *first1) {
    520             ++first2;
     494
     495    BicliqueSet cliques;
     496    cliques.reserve(B.size());
     497    for (auto Bi = B.begin(); Bi != B.end(); ++Bi) {
     498        // Compute our A set
     499        auto bi = Bi->begin();
     500        VertexSet Ai = outgoingVertexSet(*bi, G);
     501        while (++bi != Bi->end()) {
     502            VertexSet Aj = outgoingVertexSet(*bi, G);
     503            VertexSet Ak;
     504            std::set_intersection(Ai.begin(), Ai.end(), Aj.begin(), Aj.end(), std::back_inserter(Ak));
     505            Ai.swap(Ak);
     506        }
     507        cliques.emplace_back(std::move(Ai), std::move(*Bi));
     508    }
     509
     510    return std::move(cliques);
     511}
     512
     513/** ------------------------------------------------------------------------------------------------------------- *
     514 * @brief safeDistributionSets
     515 ** ------------------------------------------------------------------------------------------------------------- */
     516static DistributionSets safeDistributionSets(DistributionGraph & H, const Graph & G) {
     517
     518    VertexSet terminals;
     519    for (const Vertex u : make_iterator_range(vertices(H))) {
     520        if (out_degree(u, H) == 0) {
     521            terminals.push_back(u);
     522        }
     523    }
     524
     525    BicliqueSet lowerSet = enumerateBicliques(makeGraphFacade(H), terminals);
     526    // An intermediary vertex could have more than one outgoing edge but if any edge
     527    // is not directed to a vertex in our biclique, we'll need to compute that specific
     528    // value anyway. Remove them from the clique set and if there are not enough vertices
     529    // in the biclique to make distribution profitable, eliminate the clique.
     530    for (auto ci = lowerSet.begin(); ci != lowerSet.end(); ) {
     531        VertexSet & A = std::get<0>(*ci);
     532        VertexSet & B = std::get<1>(*ci);
     533        const auto cardinalityA = A.size();
     534        for (auto bi = B.begin(); bi != B.end(); ) {
     535            if (out_degree(H[*bi], G) == cardinalityA) {
     536                ++bi;
     537            } else {
     538                bi = B.erase(bi);
     539            }
     540        }
     541
     542        if (B.size() > 1) {
     543            ++ci;
    521544        } else {
    522             return true;
    523         }
    524     }
    525     return false;
    526 }
    527 
    528 /** ------------------------------------------------------------------------------------------------------------- *
    529  * @brief maximalIndependentSet
    530  ** ------------------------------------------------------------------------------------------------------------- */
    531 static VertexSets && maximalIndependentSet(VertexSets && V) {
    532     using IndependentSetGraph = adjacency_list<hash_setS, vecS, undirectedS, unsigned>;
    533     const auto l = V.size();
    534     IndependentSetGraph I(l);
    535     // Initialize our weights
    536     for (unsigned i = 0; i != l; ++i) {
    537         I[i] = V[i].size();
    538     }
    539     // Determine our constraints
    540     for (unsigned i = 0; i != l; ++i) {
    541         for (unsigned j = i + 1; j != l; ++j) {
    542             if (intersects(V[i], V[j])) {
    543                 add_edge(i, j, I);
    544             }
    545         }
    546     }
    547     // Use the greedy algorithm to choose our independent set (TODO: try the similar randomized approach)
    548     VertexSet selected;
    549     std::vector<bool> ignored(l, false);
    550     for (;;) {
    551         unsigned w = 0;
    552         Vertex u = 0;
    553         for (unsigned i = 0; i != l; ++i) {
    554             if (!ignored[i] && I[i] > w) {
    555                 w = I[i];
    556                 u = i;
    557             }
    558         }
    559         if (w == 0) break;
    560         selected.push_back(u);
    561         ignored[u] = true;
    562         for (auto v : make_iterator_range(adjacent_vertices(u, I))) {
    563             ignored[v] = true;
    564         }
    565     }
    566     // Sort the selected list and then remove the unselected sets from V
    567     std::sort(selected.begin(), selected.end(), std::greater<Vertex>());
    568     auto end = V.end();
    569     for (const unsigned offset : selected) {
    570         end = V.erase(V.begin() + offset + 1, end) - 1;
    571     }
    572     V.erase(V.begin(), end);
    573     return std::move(V);
    574 }
    575 
    576 /** ------------------------------------------------------------------------------------------------------------- *
    577  * @brief sinkIndependentMaximalBicliques
    578  ** ------------------------------------------------------------------------------------------------------------- */
    579 template <class Graph>
    580 static VertexSets sinkIndependentMaximalBicliques(Graph && G) {
    581     VertexSets B = maximalIndependentSet(std::move(enumerateBicliques(G)));
    582     VertexSets A;
    583     A.reserve(B.size());
    584     for (const VertexSet & Bi : B) {
    585         // Compute our A set
    586         auto bi = Bi.begin();
    587         VertexSet Ai = incomingVertexSet(*bi, G);
    588         while (++bi != Bi.end()) {
    589             VertexSet Ai = incomingVertexSet(*bi, G);
    590             VertexSet Ak;
    591             std::set_intersection(Ai.begin(), Ai.end(), Ai.begin(), Ai.end(), std::back_inserter(Ak));
    592             Ai.swap(Ak);
    593         }
    594         A.emplace_back(std::move(Ai));
    595     }
    596     std::vector<Vertex> sources;
    597     std::vector<Vertex> intermediary;
    598     for (auto u : make_iterator_range(G.vertices())) {
    599         if (G.in_degree(u) == 0) {
    600             sources.push_back(u);
    601         } else if (G.out_degree(u) != 0) {
    602             intermediary.push_back(u);
    603         }
    604     }
    605     for (auto u : sources) {
    606         G.clear_out_edges(u);
    607     }
    608     for (unsigned i = 0; i != B.size(); ++i) {
    609         for (auto u : A[i]) {
    610             for (auto v : B[i]) {
    611                 G.add_edge(u, v);
    612             }
    613         }
    614     }
    615     for (auto u : intermediary) {
    616         if (G.in_degree(u) == 0) {
    617             G.clear_out_edges(u);
    618         }
    619     }
    620     return std::move(A);
    621 }
    622 
    623 /** ------------------------------------------------------------------------------------------------------------- *
    624  * @brief safeDistributionSets
    625  ** ------------------------------------------------------------------------------------------------------------- */
    626 template <class Graph>
    627 static VertexSets safeDistributionSets(Graph & G) {
    628     VertexSets sinks = sinkIndependentMaximalBicliques(makeTransposedGraphFacade(G));
    629     // Scan through G and replicate any source that has more than one sink until G is broken
    630     // into weakly connected components in which each has exactly one sink.
    631     if (sinks.size() > 1) {
    632         std::vector<unsigned> component(num_vertices(G), 0);
    633         unsigned components = 0;
    634         for (const VertexSet & S : sinks) {
    635             ++components;
    636             for (auto e : make_iterator_range(in_edges(S.front(), G))) {
    637                 component[source(e, G)] = components;
    638             }
    639         }
    640         for (const Vertex u : make_iterator_range(vertices(G))) {
    641             if (LLVM_UNLIKELY(in_degree(u, G) == 0)) {
    642                 flat_set<unsigned> membership;
    643                 for (auto e : make_iterator_range(out_edges(u, G))) {
    644                     membership.insert(component[target(e, G)]);
    645                 }
    646                 if (LLVM_UNLIKELY(membership.size() > 1)) {
    647                     VertexSet adjacent;
    648                     adjacent.reserve(out_degree(u, G));
    649                     for (auto e : make_iterator_range(out_edges(u, G))) {
    650                         adjacent.push_back(target(e, G));
    651                     }
    652                     clear_out_edges(u, G);
    653                     auto mi = membership.begin();
    654                     for (Vertex w = u; ;) {
    655                         const unsigned m = *mi;
    656                         for (auto v : adjacent) {
    657                             if (component[v] == m) {
    658                                 add_edge(w, v, G);
     545            ci = lowerSet.erase(ci);
     546        }
     547    }
     548
     549    // Each distribution tuple consists of the sources, intermediary, and sink nodes.
     550    DistributionSets T;
     551    for (const Biclique & lower : lowerSet) {
     552        BicliqueSet upperSet = enumerateBicliques(makeGraphFacade(H), std::get<1>(lower));
     553        for (Biclique upper : upperSet) {
     554            T.emplace_back(std::get<1>(upper), std::get<0>(upper), std::get<0>(lower));
     555        }
     556    }
     557
     558    return std::move(T);
     559}
     560
     561/** ------------------------------------------------------------------------------------------------------------- *
     562 * @brief generateDistributionGraph
     563 ** ------------------------------------------------------------------------------------------------------------- */
     564void generateDistributionGraph(PabloBlock & block, Graph & G, DistributionGraph & H) {
     565    DistributionMap M;
     566    for (const Vertex u : make_iterator_range(vertices(G))) {
     567        const TypeId outerTypeId = G[u]->getClassTypeId();
     568        if (outerTypeId == TypeId::And || outerTypeId == TypeId::Or) {
     569            if (inCurrentBlock(cast<Statement>(G[u]), block)) {
     570                const TypeId innerTypeId = (outerTypeId == TypeId::And) ? TypeId::Or : TypeId::And;
     571                flat_set<Vertex> distributable;
     572                for (auto e : make_iterator_range(in_edges(u, G))) {
     573                    const Vertex v = source(e, G);
     574                    if (LLVM_UNLIKELY(G[v]->getClassTypeId() == innerTypeId && inCurrentBlock(cast<Statement>(G[v]), block))) {
     575                        bool safe = true;
     576                        for (const auto e : make_iterator_range(out_edges(v, G))) {
     577                            if (G[target(e, G)]->getClassTypeId() != outerTypeId) {
     578                                safe = false;
     579                                break;
    659580                            }
    660581                        }
    661                         if (++mi == membership.end()) {
    662                             break;
     582                        if (safe) {
     583                            distributable.insert(v);
    663584                        }
    664                         w = add_vertex(G[u], G);
    665585                    }
    666586                }
    667             }
    668         }
    669     }
    670     return std::move(sinkIndependentMaximalBicliques(makeGraphFacade(G)));
    671 }
    672 
    673 /** ------------------------------------------------------------------------------------------------------------- *
    674  * @brief segmentInto3LevelGraph
    675  *
    676  * Ensure that every source-to-sink path in G has an edge-distance of exactly 2. The safeDistributionSets algorithm
    677  * expects that G exibits this property but if an input to a distributable function is also the output of another
    678  * distributable function, this complicates the analysis process. Thus method resolves that by replicating the
    679  * appropriate vertices into input-only and output-only vertices.
    680  ** ------------------------------------------------------------------------------------------------------------- */
    681 template <class Graph>
    682 Graph & segmentInto3LevelGraph(Graph & G) {
    683     std::vector<unsigned> distance(num_vertices(G), 0);
    684     std::queue<Vertex> Q;
    685     for (const Vertex u : make_iterator_range(vertices(G))) {
    686         if (in_degree(u, G) == 0) {
    687             distance[u] = 1;
    688             for (const auto e : make_iterator_range(out_edges(u, G))) {
    689                 Q.push(target(e, G));
    690             }
    691         }
    692     }
    693     for (;;) {
    694         const Vertex u = Q.front(); Q.pop();
    695         unsigned dist = 0;
    696         bool ready = true;
    697         for (const auto e : make_iterator_range(in_edges(u, G))) {
    698             const Vertex v = source(e, G);
    699             if (LLVM_UNLIKELY(distance[v] == 0)) {
    700                 ready = false;
    701                 break;
    702             }
    703             dist = std::max(dist, distance[v]);
    704         }
    705         assert (dist <= 4);
    706         if (ready) {
    707             if (LLVM_UNLIKELY(dist == 4)) {
    708                 for (const auto e : make_iterator_range(in_edges(u, G))) {
    709                     const Vertex v = source(e, G);
    710                     if (distance[v] == 3) {
    711                         const Vertex w = add_vertex(G[v], G);
    712                         for (const auto e : make_iterator_range(out_edges(v, G))) {
    713                             add_edge(w, target(e, G), G);
    714                         }
    715                         clear_out_edges(v, G);
    716                         assert (w == distance.size());
    717                         distance.push_back(0);
    718                         Q.push(w);
    719                     }
    720                 }
    721             } else { // update the distance and add in the adjacent vertices to Q
    722                 distance[u] = dist + 1;
    723                 for (const auto e : make_iterator_range(out_edges(u, G))) {
    724                     Q.push(target(e, G));
    725                 }
    726             }
    727         }
    728         if (Q.empty()) {
    729             break;
    730         }
    731     }
    732     return G;
    733 }
    734 
    735 /** ------------------------------------------------------------------------------------------------------------- *
    736  * @brief redistributeAST
    737  *
    738  * Apply the distribution law to reduce computations whenever possible.
    739  ** ------------------------------------------------------------------------------------------------------------- */
    740 bool BooleanReassociationPass::redistributeAST(PabloBlock & block, Graph & G) const {
    741     bool anyChanges = false;
    742     for (;;) {
    743 
    744         adjacency_list<hash_setS, vecS, bidirectionalS, Vertex> H;
    745         flat_map<Vertex, Vertex> M;
    746 
    747         for (const Vertex u : make_iterator_range(vertices(G))) {
    748             const TypeId outerTypeId = G[u]->getClassTypeId();
    749             if (outerTypeId == TypeId::And || outerTypeId == TypeId::Or) {
    750                 if (inCurrentBlock(cast<Statement>(G[u]), block)) {
    751                     const TypeId innerTypeId = (outerTypeId == TypeId::And) ? TypeId::Or : TypeId::And;
    752                     flat_set<Vertex> distributable;
    753                     for (auto e : make_iterator_range(in_edges(u, G))) {
    754                         const Vertex v = source(e, G);
    755                         if (LLVM_UNLIKELY(G[v]->getClassTypeId() == innerTypeId) && LLVM_LIKELY(inCurrentBlock(cast<Statement>(G[v]), block))) {
    756                             bool safe = true;
    757                             for (const auto e : make_iterator_range(out_edges(v, G))) {
    758                                 if (G[target(e, G)]->getClassTypeId() != outerTypeId) {
    759                                     safe = false;
    760                                     break;
    761                                 }
    762                             }
    763                             if (safe) {
    764                                 distributable.insert(v);
     587                if (LLVM_LIKELY(distributable.size() > 1)) {
     588                    // We're only interested in computing a subgraph of G in which every source has an out-degree
     589                    // greater than 1. Otherwise we'd only end up permuting the AND/OR sequence with no logical
     590                    // benefit. (Note: this does not consider register pressure / liveness.)
     591                    flat_map<Vertex, bool> observedMoreThanOnce;
     592                    bool anyOpportunities = false;
     593                    for (const Vertex v : distributable) {
     594                        for (auto e : make_iterator_range(in_edges(v, G))) {
     595                            const Vertex w = source(e, G);
     596                            auto ob = observedMoreThanOnce.find(w);
     597                            if (ob == observedMoreThanOnce.end()) {
     598                                observedMoreThanOnce.emplace(w, false);
     599                            } else {
     600                                ob->second = true;
     601                                anyOpportunities = true;
    765602                            }
    766603                        }
    767604                    }
    768                     if (LLVM_LIKELY(distributable.size() > 1)) {
    769                         // We're only interested in computing a subgraph of G in which every source has an out-degree
    770                         // greater than 1. Otherwise we'd only end up permuting the AND/OR sequence with no logical
    771                         // benefit. (Note: this does not consider register pressure / liveness.)
    772                         flat_map<Vertex, unsigned> observed;
    773                         bool anyOpportunities = false;
    774                         for (const Vertex v : distributable) {
    775                             for (auto e : make_iterator_range(in_edges(v, G))) {
    776                                 const Vertex w = source(e, G);
    777                                 const auto f = observed.find(w);
    778                                 if (f == observed.end()) {
    779                                     observed.emplace(w, 0);
    780                                 } else {
    781                                     f->second += 1;
    782                                     anyOpportunities = true;
    783                                 }
    784                             }
    785                         }
    786                         if (anyOpportunities) {
    787                             for (auto ob : observed) {
    788                                 if (std::get<1>(ob)) {
    789                                     const Vertex w = std::get<0>(ob);
    790                                     for (auto e : make_iterator_range(out_edges(w, G))) {
    791                                         const Vertex v = target(e, G);
    792                                         if (distributable.count(v)) {
    793                                             const Vertex y = getVertex(v, H, M);
    794                                             add_edge(y, getVertex(u, H, M), H);
    795                                             add_edge(getVertex(w, H, M), y, H);
    796                                         }
     605                    if (anyOpportunities) {
     606                        for (const auto ob : observedMoreThanOnce) {
     607                            if (ob.second) {
     608                                const Vertex w = ob.first;
     609                                for (auto e : make_iterator_range(out_edges(w, G))) {
     610                                    const Vertex v = target(e, G);
     611                                    if (distributable.count(v)) {
     612                                        const Vertex y = getVertex(v, H, M);
     613                                        add_edge(y, getVertex(u, H, M), H);
     614                                        add_edge(getVertex(w, H, M), y, H);
    797615                                    }
    798616                                }
     
    803621            }
    804622        }
     623    }
     624}
     625
     626/** ------------------------------------------------------------------------------------------------------------- *
     627 * @brief redistributeAST
     628 *
     629 * Apply the distribution law to reduce computations whenever possible.
     630 ** ------------------------------------------------------------------------------------------------------------- */
     631bool BooleanReassociationPass::redistributeAST(PabloBlock & block, Graph & G) const {
     632    bool anyChanges = false;
     633    for (;;) {
     634
     635        DistributionGraph H;
     636
     637        generateDistributionGraph(block, G, H);
    805638
    806639        // If we found no potential opportunities then we cannot apply the distribution law to any part of G.
     
    809642        }
    810643
    811         printGraph(block, H, G, "H1");
    812 
    813         const VertexSets distributionSets = safeDistributionSets(segmentInto3LevelGraph(H));
    814 
    815         printGraph(block, H, G, "H2");
    816 
    817         // If no sources remain, no bicliques were found that would have a meaningful impact on the AST.
    818         if (LLVM_UNLIKELY(distributionSets.size() == 0)) {
     644        DistributionSets distributionSets = safeDistributionSets(H, G);
     645
     646        if (LLVM_UNLIKELY(distributionSets.empty())) {
    819647            break;
    820648        }
    821649
    822         for (const VertexSet & sources : distributionSets) {
    823             assert (sources.size() > 0);
    824             const VertexSet intermediary = outgoingVertexSet(sources.front(), makeGraphFacade(H));
    825             assert (intermediary.size() > 0);
    826             const VertexSet sinks = outgoingVertexSet(intermediary.front(), makeGraphFacade(H));
    827             assert (sinks.size() > 0);
    828 
    829             // Now begin transforming the AST
    830             const TypeId typeId = G[H[sinks.front()]]->getClassTypeId();
    831             assert (typeId == TypeId::And || typeId == TypeId::Or);
    832 
    833             circular_buffer<PabloAST *> Q(std::max(sources.size(), intermediary.size() + 1));
    834             for (const Vertex u : intermediary) {
    835                 Q.push_back(G[H[u]]);
    836             }
    837             PabloAST * merged = createTree(block, typeId, Q);
    838             for (const Vertex s : sources) {
    839                 Q.push_back(G[H[s]]);
    840             }
    841             Q.push_back(merged);
    842             PabloAST * masked = createTree(block, typeId == TypeId::Or ? TypeId::And : TypeId::Or, Q);
    843 
    844             // Eliminate the edges from our original graph
    845             for (const Vertex u : intermediary) {
    846                 for (const Vertex s : sources) {
    847                     remove_edge(H[s], H[u], G);
    848                 }
    849                 for (const Vertex t : sinks) {
    850                     remove_edge(H[u], H[t], G);
    851                 }
    852             }
    853 
    854             // Finally update G to match the desired changes
    855             const Vertex x = add_vertex(merged, G);
    856             const Vertex y = add_vertex(masked, G);
    857             for (const Vertex u : intermediary) {
    858                 add_edge(H[u], x, G);
    859             }
    860             add_edge(x, y, G);
    861             for (const Vertex s : sources) {
    862                 add_edge(H[s], y, G);
    863             }
    864             for (const Vertex t : sinks) {
    865                 add_edge(y, H[t], G);
    866             }
    867             for (const Vertex u : intermediary) {
    868                 if (LLVM_UNLIKELY(in_degree(H[u], G) == 0)) {
    869                     clear_out_edges(H[u], G);
    870                 }
    871             }
    872         }
    873         anyChanges = true;
    874     }
     650
     651        break;
     652
     653
     654
     655//        for (const Vertex s : make_iterator_range(vertices(H))) {
     656
     657//            if (in_degree(s, H) == 0) {
     658
     659//                assert (sources.size() > 0);
     660//                const VertexSet intermediary = outgoingVertexSet(sources.front(), makeGraphFacade(H));
     661//                assert (intermediary.size() > 0);
     662//                const VertexSet sinks = outgoingVertexSet(intermediary.front(), makeGraphFacade(H));
     663//                assert (sinks.size() > 0);
     664
     665//                // Now begin transforming the AST
     666//                circular_buffer<PabloAST *> Q(std::max(sources.size(), intermediary.size() + 1));
     667//                for (const Vertex u : intermediary) {
     668//                    Q.push_back(G[H[u]]);
     669//                }
     670//                const TypeId typeId = G[H[sinks.front()]]->getClassTypeId();
     671//                assert (typeId == TypeId::And || typeId == TypeId::Or);
     672//                PabloAST * merged = createTree(block, typeId, Q);
     673//                for (const Vertex s : sources) {
     674//                    Q.push_back(G[H[s]]);
     675//                }
     676//                Q.push_back(merged);
     677//                PabloAST * masked = createTree(block, (typeId == TypeId::Or) ? TypeId::And : TypeId::Or, Q);
     678
     679//                // Eliminate the edges from our original graph G
     680//                for (const Vertex u : intermediary) {
     681//                    const auto uu = H[u];
     682//                    for (const Vertex s : sources) {
     683//                        assert(edge(H[s], uu, G).second);
     684//                        remove_edge(H[s], uu, G);
     685//                    }
     686//                    for (const Vertex t : sinks) {
     687//                        assert(edge(uu, H[t], G).second);
     688//                        remove_edge(uu, H[t], G);
     689//                    }
     690//                }
     691
     692//                // Finally update G to match the desired changes
     693//                const Vertex x = add_vertex(merged, G);
     694//                const Vertex y = add_vertex(masked, G);
     695//                for (const Vertex u : intermediary) {
     696//                    add_edge(H[u], x, G);
     697//                }
     698//                add_edge(x, y, G);
     699//                for (const Vertex s : sources) {
     700//                    add_edge(H[s], y, G);
     701//                }
     702//                for (const Vertex t : sinks) {
     703//                    add_edge(y, H[t], G);
     704//                }
     705
     706//            }
     707
     708//        }
     709//        anyChanges = true;
     710
     711    }
     712
    875713    return anyChanges;
    876714}
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/booleanreassociationpass.h

    r4764 r4765  
    2020    void resolveScopes(PabloBlock &block);
    2121    void processScopes(PabloFunction & function);
    22     void processScopes(PabloBlock & block, std::vector<Statement *> && terminals);
    23     void processScope(PabloBlock & block, std::vector<Statement *> && terminals);
     22    void processScopes(PabloBlock & block);
     23    void processScope(PabloBlock & block);
    2424    void summarizeAST(PabloBlock & block, Graph & G) const;
    2525    void resolveUsages(const Vertex u, PabloAST * expr, PabloBlock & block, Graph & G, Map & M) const;
Note: See TracChangeset for help on using the changeset viewer.