Changeset 4768


Ignore:
Timestamp:
Sep 11, 2015, 4:57:13 PM (4 years ago)
Author:
nmedfort
Message:

More reassociation pass work.

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

Legend:

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

    r4767 r4768  
    3636using DistributionSets = std::vector<DistributionSet>;
    3737
     38/** ------------------------------------------------------------------------------------------------------------- *
     39 * @brief helper functions
     40 ** ------------------------------------------------------------------------------------------------------------- */
    3841template <class Graph>
    3942static VertexSet incomingVertexSet(const Vertex u, const Graph & G) {
     
    7073}
    7174
     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
     81inline void add_edge(PabloAST * expr, const Vertex u, const Vertex v, Graph & G) {
     82    G[add_edge(u, v, G).first] = expr;
     83}
     84
     85static unsigned distributionCount = 0;
    7286/** ------------------------------------------------------------------------------------------------------------- *
    7387 * @brief optimize
     
    167181
    168182/** ------------------------------------------------------------------------------------------------------------- *
     183 * @brief printGraph
     184 ** ------------------------------------------------------------------------------------------------------------- */
     185static void printGraph(const PabloBlock & block, const Graph & G, const std::string name) {
     186    raw_os_ostream out(std::cerr);
     187
     188    std::vector<unsigned> component(num_vertices(G));
     189    strong_components(G, make_iterator_property_map(component.begin(), get(vertex_index, G)));
     190
     191    std::vector<Vertex> ordering;
     192    ordering.reserve(num_vertices(G));
     193    topological_sort(G, std::back_inserter(ordering));
     194    std::reverse(ordering.begin(), ordering.end());
     195
     196    out << "digraph " << name << " {\n";
     197    for (auto u : ordering) {
     198        if (in_degree(u, G) == 0 && out_degree(u, G) == 0) {
     199            continue;
     200        }
     201        out << "v" << u << " [label=\"";
     202        PabloAST * expr = G[u];
     203        if (isa<Statement>(expr)) {
     204            if (LLVM_UNLIKELY(isa<If>(expr))) {
     205                out << "If ";
     206                PabloPrinter::print(cast<If>(expr)->getOperand(0), out);
     207                out << ":";
     208            } else if (LLVM_UNLIKELY(isa<While>(expr))) {
     209                out << "While ";
     210                PabloPrinter::print(cast<While>(expr)->getOperand(0), out);
     211                out << ":";
     212            } else {
     213                PabloPrinter::print(cast<Statement>(expr), "", out);
     214            }
     215        } else {
     216            PabloPrinter::print(expr, out);
     217        }
     218        out << "\"";
     219        if (!inCurrentBlock(expr, block)) {
     220            out << " style=dashed";
     221        }
     222        out << "];\n";
     223    }
     224
     225    for (auto e : make_iterator_range(edges(G))) {
     226        const auto i = source(e, G), j = target(e, G);
     227        out << "v" << i << " -> v" << j;
     228        if (LLVM_UNLIKELY(component[i] == component[j])) {
     229            out << "[color=red]";
     230        }
     231        out << ";\n";
     232    }
     233
     234    if (num_vertices(G) > 0) {
     235
     236        out << "{ rank=same;";
     237        for (auto u : ordering) {
     238            if (in_degree(u, G) == 0 && out_degree(u, G) != 0) {
     239                out << " v" << u;
     240            }
     241        }
     242        out << "}\n";
     243
     244        out << "{ rank=same;";
     245        for (auto u : ordering) {
     246            if (out_degree(u, G) == 0 && in_degree(u, G) != 0) {
     247                out << " v" << u;
     248            }
     249        }
     250        out << "}\n";
     251
     252    }
     253
     254    out << "}\n\n";
     255    out.flush();
     256}
     257
     258/** ------------------------------------------------------------------------------------------------------------- *
     259 * @brief printGraph
     260 ** ------------------------------------------------------------------------------------------------------------- */
     261template<typename SubgraphType>
     262static void printGraph(const PabloBlock & block, const SubgraphType & S, const Graph & G, const std::string name) {
     263    raw_os_ostream out(std::cerr);
     264    out << "digraph " << name << " {\n";
     265    for (auto u : make_iterator_range(vertices(S))) {
     266        if (in_degree(u, S) == 0 && out_degree(u, S) == 0) {
     267            continue;
     268        }
     269        out << "v" << u << " [label=\"";
     270        PabloAST * expr = G[S[u]];
     271        if (isa<Statement>(expr)) {
     272            if (LLVM_UNLIKELY(isa<If>(expr))) {
     273                out << "If ";
     274                PabloPrinter::print(cast<If>(expr)->getOperand(0), out);
     275                out << ":";
     276            } else if (LLVM_UNLIKELY(isa<While>(expr))) {
     277                out << "While ";
     278                PabloPrinter::print(cast<While>(expr)->getOperand(0), out);
     279                out << ":";
     280            } else {
     281                PabloPrinter::print(cast<Statement>(expr), "", out);
     282            }
     283        } else {
     284            PabloPrinter::print(expr, out);
     285        }
     286        out << "\"";
     287        if (!inCurrentBlock(expr, block)) {
     288            out << " style=dashed";
     289        }
     290        out << "];\n";
     291    }
     292    for (auto e : make_iterator_range(edges(S))) {
     293        out << "v" << source(e, S) << " -> v" << target(e, S) << ";\n";
     294    }
     295
     296    if (num_vertices(S) > 0) {
     297
     298        out << "{ rank=same;";
     299        for (auto u : make_iterator_range(vertices(S))) {
     300            if (in_degree(u, S) == 0 && out_degree(u, S) != 0) {
     301                out << " v" << u;
     302            }
     303        }
     304        out << "}\n";
     305
     306        out << "{ rank=same;";
     307        for (auto u : make_iterator_range(vertices(S))) {
     308            if (out_degree(u, S) == 0 && in_degree(u, S) != 0) {
     309                out << " v" << u;
     310            }
     311        }
     312        out << "}\n";
     313
     314    }
     315
     316    out << "}\n\n";
     317    out.flush();
     318}
     319
     320
     321/** ------------------------------------------------------------------------------------------------------------- *
    169322 * @brief createTree
    170323 ** ------------------------------------------------------------------------------------------------------------- */
    171324static PabloAST * createTree(PabloBlock & block, const PabloAST::ClassTypeId typeId, circular_buffer<PabloAST *> & Q) {
    172     assert (Q.size() > 0);
     325    assert (Q.size() > 1);
    173326    while (Q.size() > 1) {
    174327        PabloAST * e1 = Q.front(); Q.pop_front();
     
    199352
    200353    summarizeAST(block, G);
     354    assert (summarizeGraph(block, G) == false);
    201355    redistributeAST(block, G);
     356    assert (summarizeGraph(block, G) == false);
     357
     358    raw_os_ostream out(std::cerr);
     359    out << "======================================================\n";
     360    PabloPrinter::print(block, " > ", out);
     361    out << "------------------------------------------------------\n";
     362    out.flush();
     363
     364    printGraph(block, G, "G");
     365
     366    out << "------------------------------------------------------\n";
    202367
    203368    circular_buffer<Vertex> Q(num_vertices(G));
    204     topological_sort(G, std::front_inserter(Q));
    205     circular_buffer<PabloAST *> nodes;
     369    topological_sort(G, std::back_inserter(Q));
    206370    block.setInsertPoint(nullptr);
    207371
    208372    while (!Q.empty()) {
    209         const Vertex u = Q.front();
    210         Q.pop_front();
    211         PabloAST * expr = G[u];
    212         if (LLVM_LIKELY(inCurrentBlock(expr, block))) {
    213             if (isOptimizable(expr)) {
    214                 if (in_degree(u, G) != 0 && out_degree(u, G) != 0) {
    215                     if (LLVM_UNLIKELY(nodes.capacity() < in_degree(u, G))) {
    216                         nodes.set_capacity(in_degree(u, G));
    217                     }
     373        const Vertex u = Q.back(); Q.pop_back();
     374        if (LLVM_LIKELY(in_degree(u, G) != 0 || out_degree(u, G) != 0)) {
     375            if (LLVM_LIKELY(inCurrentBlock(G[u], block))) {
     376                Statement * stmt = cast<Statement>(G[u]);
     377                PabloPrinter::print(stmt, " - ", out); out << '\n';
     378                if (isOptimizable(stmt)) {
     379                    circular_buffer<PabloAST *> nodes(in_degree(u, G));
    218380                    for (auto e : make_iterator_range(in_edges(u, G))) {
    219381                        nodes.push_back(G[source(e, G)]);
    220382                    }
    221                     G[u] = createTree(block, expr->getClassTypeId(), nodes);
    222                     cast<Statement>(expr)->replaceWith(G[u], true, true);
    223                     if (LLVM_UNLIKELY(isa<Var>(G[u]))) {
    224                         continue;
     383                    Statement * replacement = cast<Statement>(createTree(block, stmt->getClassTypeId(), nodes));
     384                    stmt->replaceWith(replacement, false, true);
     385                    G[u] = stmt = replacement;
     386                    PabloPrinter::print(replacement, "   -> replaced with ", out); out << '\n';
     387                } else {
     388                    for (const auto e : make_iterator_range(in_edges(u, G))) {
     389                        const auto v = source(e, G);
     390                        if (LLVM_UNLIKELY(G[v] != G[e])) {
     391
     392
     393
     394                        }
    225395                    }
    226                     expr = G[u];
    227396                }
    228             }
    229             block.insert(cast<Statement>(expr));
    230         }
    231     }
     397                block.insert(stmt);
     398            }
     399        }
     400    }
     401
     402    out << "------------------------------------------------------\n";
     403    PabloPrinter::print(block, " < ", out);
     404    out << "------------------------------------------------------\n";
     405    out.flush();
     406
    232407    PabloVerifier::verify(function);
    233 
    234408}
    235409
     
    242416 ** ------------------------------------------------------------------------------------------------------------- */
    243417void BooleanReassociationPass::summarizeAST(PabloBlock & block, Graph & G) const {
    244 
    245418    Map M;
    246 
    247419    // Compute the base def-use graph ...
    248420    for (Statement * stmt : block) {
     
    253425                continue;
    254426            }
    255             add_edge(getVertex(op, G, M), u, G);
     427            add_edge(op, getVertex(op, G, M), u, G);
    256428        }
    257429        if (isa<If>(stmt)) {
    258430            for (Assign * def : cast<const If>(stmt)->getDefined()) {
    259431                const Vertex v = getVertex(def, G, M);
    260                 add_edge(u, v, G);
    261                 resolveUsages(v, def, block, G, M);
     432                add_edge(def, u, v, G);
     433                resolveUsages(v, def, block, G, M, stmt);
    262434            }
    263435        } else if (isa<While>(stmt)) {
    264436            for (Next * var : cast<const While>(stmt)->getVariants()) {
    265437                const Vertex v = getVertex(var, G, M);
    266                 add_edge(u, v, G);
    267                 resolveUsages(v, var, block, G, M);
     438                add_edge(var, u, v, G);
     439                resolveUsages(v, var, block, G, M, stmt);
    268440            }
    269441        } else {
     
    271443        }
    272444    }
    273 
    274     std::vector<Vertex> ordering;
    275     ordering.reserve(num_vertices(G));
    276     topological_sort(G, std::back_inserter(ordering));
    277 
    278     for (auto i = ordering.rbegin(); i != ordering.rend(); ++i) {
    279         const Vertex u = *i;
    280         if (isOptimizable(G[u])) {
    281             std::vector<Vertex> removable;
    282             for (auto e : make_iterator_range(in_edges(u, G))) {
    283                 const Vertex v = source(e, G);
    284                 if (out_degree(v, G) == 1 && in_degree(v, G) != 0 && G[u]->getClassTypeId() == G[v]->getClassTypeId()) {
    285                     removable.push_back(v);
    286                     for (auto e : make_iterator_range(in_edges(v, G))) {
    287                         add_edge(source(e, G), u, G);
     445    summarizeGraph(block, G);
     446}
     447
     448/** ------------------------------------------------------------------------------------------------------------- *
     449 * @brief resolveUsages
     450 ** ------------------------------------------------------------------------------------------------------------- */
     451bool BooleanReassociationPass::summarizeGraph(PabloBlock & block, Graph & G) {
     452    bool modified = false;
     453    std::vector<Vertex> reverseTopologicalOrdering;
     454    reverseTopologicalOrdering.reserve(num_vertices(G));
     455    topological_sort(G, std::back_inserter(reverseTopologicalOrdering));
     456    for (const Vertex u : reverseTopologicalOrdering) {
     457        if (isOptimizable(G[u]) && inCurrentBlock(G[u], block)) {
     458            if (LLVM_UNLIKELY(in_degree(u, G) == 1)) {
     459                // We have a redundant node here that'll simply end up being a duplicate
     460                // of the input value. Remove it and add any of its outgoing edges to its
     461                // input node.
     462                const auto ei = first(in_edges(u, G));
     463                const Vertex v = source(ei, G);
     464                for (auto ej : make_iterator_range(out_edges(u, G))) {
     465                    add_edge(G[ei], v, target(ej, G), G);
     466                }
     467                clear_vertex(u, G);
     468                modified = true;
     469                continue;
     470            } else if (LLVM_UNLIKELY(out_degree(u, G) == 1)) {
     471                // Otherwise if we have a single user, we have a similar case as above but
     472                // we can only merge this vertex into the outgoing instruction if they are
     473                // of the same type.
     474                const auto ei = first(out_edges(u, G));
     475                const Vertex v = target(ei, G);
     476                if (LLVM_UNLIKELY(G[v]->getClassTypeId() == G[u]->getClassTypeId())) {
     477                    for (auto ej : make_iterator_range(in_edges(u, G))) {
     478                        add_edge(G[ei], source(ej, G), v, G);
    288479                    }
     480                    clear_vertex(u, G);
     481                    modified = true;
     482                    continue;
    289483                }
    290484            }
    291             for (auto v : removable) {
    292                 clear_vertex(v, G);
    293             }
    294         }
    295     }
     485        }
     486        // Finally, eliminate any unnecessary instruction
     487        if (LLVM_UNLIKELY(out_degree(u, G) == 0 && !(isa<Assign>(G[u]) || isa<Next>(G[u])))) {
     488            clear_in_edges(u, G);
     489        }
     490    }
     491    assert (modified ? (summarizeGraph(block, G) == false) : true);
     492    return modified;
    296493}
    297494
     
    299496 * @brief resolveUsages
    300497 ** ------------------------------------------------------------------------------------------------------------- */
    301 void BooleanReassociationPass::resolveUsages(const Vertex u, PabloAST * expr, PabloBlock & block, Graph & G, Map & M) const {
     498void BooleanReassociationPass::resolveUsages(const Vertex u, PabloAST * expr, PabloBlock & block, Graph & G, Map & M, Statement * ignoreIfThis) const {
    302499    for (PabloAST * user : expr->users()) {
    303500        assert (user);
     
    314511                        if (LLVM_UNLIKELY(f == mResolvedScopes.end())) {
    315512                            throw std::runtime_error("Failed to resolve scope block!");
     513                        }
     514                        if (LLVM_UNLIKELY(f->second == ignoreIfThis)) {
     515                            break;
    316516                        }
    317517                        add_edge(u, getVertex(f->second, G, M), G);
     
    584784    bool anyChanges = false;
    585785
     786    ++distributionCount;
     787
    586788    for (;;) {
    587789
     
    630832            const Vertex y = add_vertex(nullptr, G);
    631833            for (const Vertex u : intermediary) {
    632                 add_edge(H[u], x, G);
     834                add_edge(nullptr, H[u], x, G);
    633835            }
    634836            for (const Vertex s : sources) {
    635                 add_edge(H[s], y, G);
     837                add_edge(nullptr, H[s], y, G);
    636838            }
    637839            for (const Vertex t : sinks) {
    638                 add_edge(y, H[t], G);
    639             }
    640             add_edge(x, y, G);
    641 
     840                add_edge(nullptr, y, H[t], G);
     841            }
     842            add_edge(nullptr, x, y, G);
    642843
    643844            // Now begin transforming the AST (TODO: fix the abstraction so I can defer creation until the final phase)
     
    653854
    654855            // 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             }
     856            summarizeGraph(block, G);
    671857        }
    672858        anyChanges = true;
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/booleanreassociationpass.h

    r4766 r4768  
    1010class BooleanReassociationPass {
    1111public:
    12     using Graph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS, PabloAST *>;
     12    using Graph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS, PabloAST *, PabloAST *>;
    1313    using Vertex = Graph::vertex_descriptor;
    1414    using Map = std::unordered_map<const PabloAST *, Vertex>;
     
    2323    void processScope(PabloFunction & function, PabloBlock & block);
    2424    void summarizeAST(PabloBlock & block, Graph & G) const;
    25     void resolveUsages(const Vertex u, PabloAST * expr, PabloBlock & block, Graph & G, Map & M) const;
     25    static bool summarizeGraph(PabloBlock & block, Graph & G);
     26    void resolveUsages(const Vertex u, PabloAST * expr, PabloBlock & block, Graph & G, Map & M, Statement * ignoreIfThis = nullptr) const;
    2627    bool redistributeAST(PabloBlock & block, Graph & G) const;
    2728private:
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_simplifier.hpp

    r4658 r4768  
    1212public:
    1313    static bool optimize(PabloFunction & function);
     14    static void deadCodeElimination(PabloBlock & block);
    1415protected:
    1516    Simplifier();
    1617private:
    1718    static void eliminateRedundantCode(PabloBlock & block, ExpressionTable * predecessor = nullptr);
    18     static void deadCodeElimination(PabloBlock & block);
    1919    static void eliminateRedundantComplexStatements(PabloBlock & block);
    2020    static bool isSuperfluous(const Assign * const assign);
Note: See TracChangeset for help on using the changeset viewer.