Changeset 4761


Ignore:
Timestamp:
Sep 5, 2015, 1:16:12 AM (3 years ago)
Author:
nmedfort
Message:

More work on reassociation pass.

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

Legend:

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

    r4736 r4761  
    3030        }
    3131    }
    32     else {
     32    else if (LLVM_LIKELY(statement != mInsertionPoint)) {
    3333        statement->insertAfter(mInsertionPoint);
    3434        mLast = (mLast == mInsertionPoint) ? statement : mLast;
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/booleanreassociationpass.cpp

    r4760 r4761  
    2424using Map = BooleanReassociationPass::Map;
    2525using EdgeQueue = std::queue<std::pair<Vertex, Vertex>>;
     26using TypeId = PabloAST::ClassTypeId;
    2627
    2728/** ------------------------------------------------------------------------------------------------------------- *
     
    5657}
    5758
    58 
    59 /** ------------------------------------------------------------------------------------------------------------- *
    60  * @brief scan
     59/** ------------------------------------------------------------------------------------------------------------- *
     60 * @brief processScopes
    6161 ** ------------------------------------------------------------------------------------------------------------- */
    6262inline void BooleanReassociationPass::processScopes(PabloFunction & function) {
     
    6969
    7070/** ------------------------------------------------------------------------------------------------------------- *
    71  * @brief scan
     71 * @brief processScopes
    7272 ** ------------------------------------------------------------------------------------------------------------- */
    7373void BooleanReassociationPass::processScopes(PabloBlock & block, std::vector<Statement *> && terminals) {
     
    183183 ** ------------------------------------------------------------------------------------------------------------- */
    184184static PabloAST * createTree(PabloBlock & block, const PabloAST::ClassTypeId typeId, circular_buffer<PabloAST *> & Q) {
     185    assert (!Q.empty());
    185186    while (Q.size() > 1) {
    186187        PabloAST * e1 = Q.front(); Q.pop_front();
     
    327328 * @brief processScope
    328329 ** ------------------------------------------------------------------------------------------------------------- */
    329 void BooleanReassociationPass::processScope(PabloBlock & block, std::vector<Statement *> && terminals) {
    330 
     330inline void BooleanReassociationPass::processScope(PabloBlock & block, std::vector<Statement *> && terminals) {
    331331    Graph G;
    332 
    333332    summarizeAST(block, terminals, G);
    334     printGraph(block, G, "G");
    335     if (redistributeAST(block, G)) {
    336         printGraph(block, G, "H");
    337     }
     333
     334    printGraph(block, G, "G0");
     335
     336    redistributeAST(block, G);
     337
     338    printGraph(block, G, "G1");
     339
     340    circular_buffer<Vertex> Q(num_vertices(G));
     341    topological_sort(G, std::front_inserter(Q));
     342
     343    circular_buffer<PabloAST *> nodes;
     344    block.setInsertPoint(nullptr);
     345
     346    while (!Q.empty()) {
     347        const Vertex u = Q.front();
     348        Q.pop_front();
     349        PabloAST * expr = G[u];
     350        if (LLVM_LIKELY(inCurrentBlock(expr, block))) {
     351            switch (expr->getClassTypeId()) {
     352                case TypeId::And:
     353                case TypeId::Or:
     354                case TypeId::Xor:
     355                    if (LLVM_UNLIKELY(in_degree(u, G) < 2)) {
     356                        std::string tmp;
     357                        raw_string_ostream str(tmp);
     358                        PabloPrinter::print(cast<Statement>(expr), "Unexpected error: ", str);
     359                        str << " only had " << in_degree(u, G) << " nodes!";
     360                        throw std::runtime_error(str.str());
     361                    }
     362                    nodes.set_capacity(in_degree(u, G));
     363                    for (auto e : make_iterator_range(in_edges(u, G))) {
     364                        nodes.push_back(G[source(e, G)]);
     365                    }
     366                    expr = createTree(block, expr->getClassTypeId(), nodes);
     367                default:
     368                    block.insert(cast<Statement>(expr));
     369            }
     370        }
     371    }
     372
     373
    338374}
    339375
     
    687723        Bi.swap(Bk);
    688724    }
    689 
    690725    return VertexSets(C.begin(), C.end());
    691726}
     
    759794
    760795/** ------------------------------------------------------------------------------------------------------------- *
    761  * @brief sinkIndependentBicliques
     796 * @brief sinkIndependentMaximalBicliques
    762797 ** ------------------------------------------------------------------------------------------------------------- */
    763798template <class Graph>
    764 static VertexSets sinkIndependentBicliques(Graph && G) {
     799static VertexSets sinkIndependentMaximalBicliques(Graph && G) {
    765800    VertexSets B = maximalIndependentSet(std::move(enumerateBicliques(G)));
    766801    VertexSets A;
     
    810845template <class Graph>
    811846static VertexSets safeDistributionSets(Graph & G) {
    812     VertexSets sinks(std::move(sinkIndependentBicliques(makeTransposedGraphFacade(G))));
     847    VertexSets sinks = sinkIndependentMaximalBicliques(makeTransposedGraphFacade(G));
    813848    // Scan through G and replicate any source that has more than one sink until G is broken
    814849    // into weakly connected components in which each has exactly one sink.
     
    852887        }
    853888    }
    854     return std::move(sinkIndependentBicliques(makeGraphFacade(G)));
     889    return std::move(sinkIndependentMaximalBicliques(makeGraphFacade(G)));
    855890}
    856891
     
    858893 * @brief segmentInto3LevelGraph
    859894 *
    860  * Ensure that every source-to-sink path in G has a distance of exactly 2.
     895 * Ensure that every source-to-sink path in G has an edge-distance of exactly 2. The safeDistributionSets algorithm
     896 * expects that G exibits this property but if an input to a distributable function is also the output of another
     897 * distributable function, this complicates the analysis process. Thus method resolves that by replicating the
     898 * appropriate vertices into input-only and output-only vertices.
    861899 ** ------------------------------------------------------------------------------------------------------------- */
    862900template <class Graph>
    863901Graph & segmentInto3LevelGraph(Graph & G) {
    864 
    865     std::vector<Vertex> ordering;
    866     ordering.reserve(num_vertices(G));
    867 
    868     topological_sort(G, std::back_inserter(ordering));
    869 
    870     std::vector<unsigned> distance(num_vertices(G));
    871     // Compute the distance to furthest sink for each node
    872     for (Vertex u : ordering) {
    873         unsigned d = 0;
    874         for (auto e : make_iterator_range(out_edges(u, G))) {
    875             d = std::max<unsigned>(d, distance[target(e, G)] + 1);
    876         }
    877         distance[u] = d;
    878     }
    879 
    880 
    881 
    882 
     902    std::vector<unsigned> distance(num_vertices(G), 0);
     903    std::queue<Vertex> Q;
     904    for (const Vertex u : make_iterator_range(vertices(G))) {
     905        if (in_degree(u, G) == 0) {
     906            distance[u] = 1;
     907            for (const auto e : make_iterator_range(out_edges(u, G))) {
     908                Q.push(target(e, G));
     909            }
     910        }
     911    }
     912    for (;;) {
     913        const Vertex u = Q.front(); Q.pop();
     914        unsigned dist = 0;
     915        bool ready = true;
     916        for (const auto e : make_iterator_range(in_edges(u, G))) {
     917            const Vertex v = source(e, G);
     918            if (LLVM_UNLIKELY(distance[v] == 0)) {
     919                ready = false;
     920                break;
     921            }
     922            dist = std::max(dist, distance[v]);
     923        }
     924        assert (dist <= 4);
     925        if (ready) {
     926            if (LLVM_UNLIKELY(dist == 4)) {
     927                for (const auto e : make_iterator_range(in_edges(u, G))) {
     928                    const Vertex v = source(e, G);
     929                    if (distance[v] == 3) {
     930                        const Vertex w = add_vertex(G[v], G);
     931                        for (const auto e : make_iterator_range(out_edges(v, G))) {
     932                            add_edge(w, target(e, G), G);
     933                        }
     934                        clear_out_edges(v, G);
     935                        assert (w == distance.size());
     936                        distance.push_back(0);
     937                        Q.push(w);
     938                    }
     939                }
     940            } else { // update the distance and add in the adjacent vertices to Q
     941                distance[u] = dist + 1;
     942                for (const auto e : make_iterator_range(out_edges(u, G))) {
     943                    Q.push(target(e, G));
     944                }
     945            }
     946        }
     947        if (Q.empty()) {
     948            break;
     949        }
     950    }
    883951    return G;
    884952}
     
    890958 ** ------------------------------------------------------------------------------------------------------------- */
    891959bool BooleanReassociationPass::redistributeAST(PabloBlock & block, Graph & G) const {
    892     using TypeId = PabloAST::ClassTypeId;
    893 
    894960    bool anyChanges = false;
    895 
    896961    for (;;) {
    897962
     
    9631028        }
    9641029
    965         const VertexSets distributionSets = safeDistributionSets(segmentInto3LevelGraph(H));
     1030        printGraph(block, H, G, "H0");
     1031
     1032        segmentInto3LevelGraph(H);
     1033
     1034        printGraph(block, H, G, "H1");
     1035
     1036        const VertexSets distributionSets = safeDistributionSets(H);
     1037
     1038        printGraph(block, H, G, "H2");
    9661039
    9671040        // If no sources remain, no bicliques were found that would have a meaningful impact on the AST.
     
    10181091        anyChanges = true;
    10191092    }
    1020 
    10211093    return anyChanges;
    10221094}
Note: See TracChangeset for help on using the changeset viewer.