Ignore:
Timestamp:
Sep 11, 2015, 8:55:52 AM (4 years ago)
Author:
nmedfort
Message:

Work on reassociation pass

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

Legend:

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

    r4766 r4767  
    66#include <boost/graph/filtered_graph.hpp>
    77#include <boost/graph/topological_sort.hpp>
     8#include <boost/graph/strong_components.hpp>
    89#include <pablo/optimizers/pablo_simplifier.hpp>
    910#include <pablo/analysis/pabloverifier.hpp>
     
    169170 ** ------------------------------------------------------------------------------------------------------------- */
    170171static PabloAST * createTree(PabloBlock & block, const PabloAST::ClassTypeId typeId, circular_buffer<PabloAST *> & Q) {
    171     assert (!Q.empty());
     172    assert (Q.size() > 0);
    172173    while (Q.size() > 1) {
    173174        PabloAST * e1 = Q.front(); Q.pop_front();
    174         // assert (isa<Statement>(e1) ? cast<Statement>(e1)->getParent() != nullptr : true);
    175175        PabloAST * e2 = Q.front(); Q.pop_front();
    176         // assert (isa<Statement>(e2) ? cast<Statement>(e2)->getParent() != nullptr : true);
    177176        PabloAST * expr = nullptr;
    178177        // Note: this switch ought to compile to an array of function pointers to the appropriate method.
     
    188187        Q.push_back(expr);
    189188    }
    190     PabloAST * r = Q.front();
     189    PabloAST * const expr = Q.front();
    191190    Q.clear();
    192     return r;
    193 }
    194 
    195 /** ------------------------------------------------------------------------------------------------------------- *
    196  * @brief printGraph
    197  ** ------------------------------------------------------------------------------------------------------------- */
    198 static void printGraph(const PabloBlock & block, const Graph & G, const std::string name) {
    199     raw_os_ostream out(std::cerr);
    200     out << "digraph " << name << " {\n";
    201     for (auto u : make_iterator_range(vertices(G))) {
    202         if (in_degree(u, G) == 0 && out_degree(u, G) == 0) {
    203             continue;
    204         }
    205         out << "v" << u << " [label=\"";
    206         PabloAST * expr = G[u];
    207         if (isa<Statement>(expr)) {
    208             if (LLVM_UNLIKELY(isa<If>(expr))) {
    209                 out << "If ";
    210                 PabloPrinter::print(cast<If>(expr)->getOperand(0), out);
    211                 out << ":";
    212             } else if (LLVM_UNLIKELY(isa<While>(expr))) {
    213                 out << "While ";
    214                 PabloPrinter::print(cast<While>(expr)->getOperand(0), out);
    215                 out << ":";
    216             } else {
    217                 PabloPrinter::print(cast<Statement>(expr), "", out);
    218             }
    219         } else {
    220             PabloPrinter::print(expr, out);
    221         }
    222         out << "\"";
    223         if (!inCurrentBlock(expr, block)) {
    224             out << " style=dashed";
    225         }
    226         out << "];\n";
    227     }
    228     for (auto e : make_iterator_range(edges(G))) {
    229         out << "v" << source(e, G) << " -> v" << target(e, G) << ";\n";
    230     }
    231 
    232     if (num_vertices(G) > 0) {
    233 
    234         out << "{ rank=same;";
    235         for (auto u : make_iterator_range(vertices(G))) {
    236             if (in_degree(u, G) == 0 && out_degree(u, G) != 0) {
    237                 out << " v" << u;
    238             }
    239         }
    240         out << "}\n";
    241 
    242         out << "{ rank=same;";
    243         for (auto u : make_iterator_range(vertices(G))) {
    244             if (out_degree(u, G) == 0 && in_degree(u, G) != 0) {
    245                 out << " v" << u;
    246             }
    247         }
    248         out << "}\n";
    249 
    250     }
    251 
    252     out << "}\n\n";
    253     out.flush();
    254 }
    255 
    256 /** ------------------------------------------------------------------------------------------------------------- *
    257  * @brief printGraph
    258  ** ------------------------------------------------------------------------------------------------------------- */
    259 template<typename SubgraphType>
    260 static void printGraph(const PabloBlock & block, const SubgraphType & S, const Graph & G, const std::string name) {
    261     raw_os_ostream out(std::cerr);
    262     out << "digraph " << name << " {\n";
    263     for (auto u : make_iterator_range(vertices(S))) {
    264         if (in_degree(u, S) == 0 && out_degree(u, S) == 0) {
    265             continue;
    266         }
    267         out << "v" << u << " [label=\"";
    268         PabloAST * expr = G[S[u]];
    269         if (isa<Statement>(expr)) {
    270             if (LLVM_UNLIKELY(isa<If>(expr))) {
    271                 out << "If ";
    272                 PabloPrinter::print(cast<If>(expr)->getOperand(0), out);
    273                 out << ":";
    274             } else if (LLVM_UNLIKELY(isa<While>(expr))) {
    275                 out << "While ";
    276                 PabloPrinter::print(cast<While>(expr)->getOperand(0), out);
    277                 out << ":";
    278             } else {
    279                 PabloPrinter::print(cast<Statement>(expr), "", out);
    280             }
    281         } else {
    282             PabloPrinter::print(expr, out);
    283         }
    284         out << "\"";
    285         if (!inCurrentBlock(expr, block)) {
    286             out << " style=dashed";
    287         }
    288         out << "];\n";
    289     }
    290     for (auto e : make_iterator_range(edges(S))) {
    291         out << "v" << source(e, S) << " -> v" << target(e, S) << ";\n";
    292     }
    293 
    294     if (num_vertices(S) > 0) {
    295 
    296         out << "{ rank=same;";
    297         for (auto u : make_iterator_range(vertices(S))) {
    298             if (in_degree(u, S) == 0 && out_degree(u, S) != 0) {
    299                 out << " v" << u;
    300             }
    301         }
    302         out << "}\n";
    303 
    304         out << "{ rank=same;";
    305         for (auto u : make_iterator_range(vertices(S))) {
    306             if (out_degree(u, S) == 0 && in_degree(u, S) != 0) {
    307                 out << " v" << u;
    308             }
    309         }
    310         out << "}\n";
    311 
    312     }
    313 
    314     out << "}\n\n";
    315     out.flush();
     191    return expr;
    316192}
    317193
     
    325201    redistributeAST(block, G);
    326202
    327     raw_os_ostream out(std::cerr);
    328     PabloPrinter::print(block, "> ", out); // function.getEntryBlock().statements()
    329     out.flush();
    330 
    331203    circular_buffer<Vertex> Q(num_vertices(G));
    332204    topological_sort(G, std::front_inserter(Q));
    333     assert (Q.size() == num_vertices(G));
    334 
    335205    circular_buffer<PabloAST *> nodes;
    336206    block.setInsertPoint(nullptr);
     
    342212        if (LLVM_LIKELY(inCurrentBlock(expr, block))) {
    343213            if (isOptimizable(expr)) {
    344                 if (in_degree(u, G) == 0) {
    345                     cast<Statement>(expr)->eraseFromParent(false);
    346                     continue;
    347                 } else {
     214                if (in_degree(u, G) != 0 && out_degree(u, G) != 0) {
    348215                    if (LLVM_UNLIKELY(nodes.capacity() < in_degree(u, G))) {
    349216                        nodes.set_capacity(in_degree(u, G));
     
    363230        }
    364231    }
    365 
    366     PabloPrinter::print(block, "< ", out); // function.getEntryBlock().statements()
    367     out.flush();
    368 
    369232    PabloVerifier::verify(function);
    370233
     
    553416 ** ------------------------------------------------------------------------------------------------------------- */
    554417template <unsigned side>
    555 inline static BicliqueSet && independentCliqueSets(BicliqueSet && cliques) {
     418inline static BicliqueSet && independentCliqueSets(BicliqueSet && cliques, const unsigned minimum) {
    556419    using IndependentSetGraph = adjacency_list<hash_setS, vecS, undirectedS, unsigned>;
    557420
     
    584447            }
    585448        }
    586         if (w == 0) break;
     449        if (w < minimum) break;
    587450        selected.push_back(u);
    588451        I[u] = 0;
     
    634497 ** ------------------------------------------------------------------------------------------------------------- */
    635498static DistributionSets safeDistributionSets(const PabloBlock & block, const Graph & G, DistributionGraph & H) {
    636 
    637499    const auto F = makeGraphFacade(H);
    638 
    639 
    640     DistributionGraph X;
    641500    DistributionSets T;
    642 
    643 //    printGraph(block, H, G, "H0");
    644 
    645     BicliqueSet lowerSet = independentCliqueSets<1>(removeUnhelpfulBicliques(enumerateBicliques(F, sinks(H)), G, H));
    646 
    647 //    raw_os_ostream out(std::cerr);
    648 
     501    BicliqueSet lowerSet = independentCliqueSets<1>(removeUnhelpfulBicliques(enumerateBicliques(F, sinks(H)), G, H), 1);
    649502    for (Biclique & lower : lowerSet) {
    650 
    651 //        out << "LOWER[0]: ";
    652 //        for (Vertex u : std::get<0>(lower)) {
    653 //            PabloPrinter::print(G[H[u]], out);
    654 //            out << ' ';
    655 //        }
    656 //        out << '\n';
    657 
    658 //        out << "LOWER[1]: ";
    659 //        for (Vertex u : std::get<1>(lower)) {
    660 //            PabloPrinter::print(G[H[u]], out);
    661 //            out << ' ';
    662 //        }
    663 //        out << '\n';
    664 //        out.flush();
    665 
    666         BicliqueSet upperSet = independentCliqueSets<0>(enumerateBicliques(F, std::get<1>(lower)));
     503        BicliqueSet upperSet = independentCliqueSets<0>(enumerateBicliques(F, std::get<1>(lower)), 2);
    667504        for (Biclique & upper : upperSet) {
    668 
    669 //            out << "  UPPER[0]: ";
    670 //            for (Vertex u : std::get<0>(upper)) {
    671 //                PabloPrinter::print(G[H[u]], out);
    672 //                out << ' ';
    673 //            }
    674 //            out << '\n';
    675 
    676 //            out << "  UPPER[1]: ";
    677 //            for (Vertex u : std::get<1>(upper)) {
    678 //                PabloPrinter::print(G[H[u]], out);
    679 //                out << ' ';
    680 //            }
    681 //            out << '\n';
    682 //            out.flush();
    683 
    684             VertexSet sources;
    685             for (auto u : std::get<1>(upper)) {
    686                 sources.push_back(add_vertex(H[u], X));
    687             }
    688             VertexSet sinks;
    689             for (auto w : std::get<0>(lower)) {
    690                 sinks.push_back(add_vertex(H[w], X));
    691             }
    692 
    693             for (auto v : std::get<0>(upper)) {
    694                 const auto x = add_vertex(H[v], X);
    695                 for (auto u : sources) {
    696                     add_edge(u, x, X);
    697                 }
    698                 for (auto w : sinks) {
    699                     add_edge(x, w, X);
    700                 }
    701             }
    702 
    703 
    704505            T.emplace_back(std::move(std::get<1>(upper)), std::move(std::get<0>(upper)), std::get<0>(lower));
    705506        }
    706507    }
    707 
    708 //    printGraph(block, X, G, "H1");
    709 
    710508    return std::move(T);
    711509}
     
    714512 * @brief generateDistributionGraph
    715513 ** ------------------------------------------------------------------------------------------------------------- */
    716 void generateDistributionGraph(PabloBlock & block, Graph & G, DistributionGraph & H) {
     514void generateDistributionGraph(const PabloBlock & block, const Graph & G, DistributionGraph & H) {
    717515    DistributionMap M;
    718516    for (const Vertex u : make_iterator_range(vertices(G))) {
     
    786584    bool anyChanges = false;
    787585
    788     unsigned count = 0;
    789 
    790     // printGraph(block, G, "G" + std::to_string(count++));
    791 
    792586    for (;;) {
    793587
     
    819613            // Eliminate the edges from our original graph G
    820614            for (const Vertex u : intermediary) {
    821                 const auto uu = H[u];
     615                const auto x = H[u];
     616                assert (G[x]->getClassTypeId() == innerTypeId);
    822617                for (const Vertex s : sources) {
    823                     assert (edge(H[s], uu, G).second);
    824                     remove_edge(H[s], uu, G);
     618                    assert (edge(H[s], x, G).second);
     619                    remove_edge(H[s], x, G);
    825620                }
    826621                for (const Vertex t : sinks) {
    827                     assert (edge(uu, H[t], G).second);
    828                     remove_edge(uu, H[t], G);
     622                    assert (edge(x, H[t], G).second);
     623                    assert (G[H[t]]->getClassTypeId() == outerTypeId);
     624                    remove_edge(x, H[t], G);
    829625                }
    830626            }
     
    837633            }
    838634            for (const Vertex s : sources) {
    839                 const Vertex u = H[s];
    840                 // If we can merge the sources into this mask, do so.
    841                 if (LLVM_UNLIKELY(out_degree(u, G) == 0 && G[u]->getClassTypeId() == innerTypeId && inCurrentBlock(cast<Statement>(G[u]), block))) {
    842                     for (auto e : make_iterator_range(in_edges(u, G))) {
    843                         add_edge(source(e, G), y, G);
    844                     }
    845                     clear_in_edges(u, G);
    846                 } else {
    847                     add_edge(u, y, G);
    848                 }
     635                add_edge(H[s], y, G);
    849636            }
    850637            for (const Vertex t : sinks) {
     
    853640            add_edge(x, y, G);
    854641
    855             // Now begin transforming the AST
     642
     643            // Now begin transforming the AST (TODO: fix the abstraction so I can defer creation until the final phase)
    856644            circular_buffer<PabloAST *> Q(std::max(in_degree(x, G), in_degree(y, G)));
    857645            for (auto e : make_iterator_range(in_edges(x, G))) {
     
    863651            }
    864652            G[y] = createTree(block, innerTypeId, Q);
     653
     654            // Summarize the graph after transforming G
     655            std::vector<Vertex> ordering;
     656            ordering.reserve(num_vertices(G));
     657            for (const Vertex u : ordering) {
     658                if (LLVM_UNLIKELY(out_degree(u, G) == 1 && inCurrentBlock(G[u], block))) {
     659                    if (isOptimizable(G[u])) {
     660                        const Vertex v = target(*(out_edges(u, G).first), G);
     661                        if (LLVM_UNLIKELY(G[v]->getClassTypeId() == G[u]->getClassTypeId())) {
     662                            for (auto e : make_iterator_range(in_edges(u, G))) {
     663                                assert (source(e, G) != u);
     664                                add_edge(source(e, G), v, G);
     665                            }
     666                            clear_vertex(u, G);
     667                        }
     668                    }
     669                }
     670            }
    865671        }
    866672        anyChanges = true;
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/graph-facade.hpp

    r4760 r4767  
    33
    44#include <boost/graph/adjacency_list.hpp>
     5#include <vector>
    56
    67template <class Graph, bool transposed = false>
Note: See TracChangeset for help on using the changeset viewer.