Changeset 4769


Ignore:
Timestamp:
Sep 13, 2015, 1:17:44 AM (3 years ago)
Author:
nmedfort
Message:

Progress on reassociation pass

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

Legend:

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

    r4768 r4769  
    2121namespace pablo {
    2222
     23using TypeId = PabloAST::ClassTypeId;
    2324using Graph = BooleanReassociationPass::Graph;
    2425using Vertex = Graph::vertex_descriptor;
     
    2627using Map = BooleanReassociationPass::Map;
    2728using EdgeQueue = std::queue<std::pair<Vertex, Vertex>>;
    28 using TypeId = PabloAST::ClassTypeId;
    2929using DistributionGraph = adjacency_list<hash_setS, vecS, bidirectionalS, Vertex>;
    3030using DistributionMap = flat_map<Graph::vertex_descriptor, DistributionGraph::vertex_descriptor>;
     
    3333using Biclique = std::pair<VertexSet, VertexSet>;
    3434using BicliqueSet = std::vector<Biclique>;
    35 using DistributionSet = std::tuple<std::vector<Vertex>, std::vector<Vertex>, std::vector<Vertex>>;
     35using DistributionSet = std::tuple<VertexSet, VertexSet, VertexSet>;
    3636using DistributionSets = std::vector<DistributionSet>;
    3737
     
    8383}
    8484
    85 static unsigned distributionCount = 0;
    8685/** ------------------------------------------------------------------------------------------------------------- *
    8786 * @brief optimize
     
    138137
    139138/** ------------------------------------------------------------------------------------------------------------- *
     139 * @brief inCurrentBlock
     140 ** ------------------------------------------------------------------------------------------------------------- */
     141static inline bool inCurrentBlock(const Statement * stmt, const PabloBlock & block) {
     142    return stmt->getParent() == &block;
     143}
     144
     145static inline bool inCurrentBlock(const PabloAST * expr, const PabloBlock & block) {
     146    return expr ? isa<Statement>(expr) && inCurrentBlock(cast<Statement>(expr), block) : true;
     147}
     148
     149/** ------------------------------------------------------------------------------------------------------------- *
    140150 * @brief isOptimizable
    141151 *
     
    143153 * safely rearrange expressions such as "((((a √ b) √ c) √ d) √ e) √ f" into "((a √ b) √ (c √ d)) √ (e √ f)".
    144154 ** ------------------------------------------------------------------------------------------------------------- */
    145 static inline bool isOptimizable(const PabloAST * const expr) {
    146     assert (expr);
    147     switch (expr->getClassTypeId()) {
     155inline bool BooleanReassociationPass::isOptimizable(const VertexData & data) {
     156    switch (data.first) {
    148157        case PabloAST::ClassTypeId::And:
    149158        case PabloAST::ClassTypeId::Or:
     
    155164}
    156165
    157 /** ------------------------------------------------------------------------------------------------------------- *
    158  * @brief inCurrentBlock
    159  ** ------------------------------------------------------------------------------------------------------------- */
    160 static inline bool inCurrentBlock(const Statement * stmt, const PabloBlock & block) {
    161     return stmt->getParent() == &block;
    162 }
    163 
    164 static inline bool inCurrentBlock(const PabloAST * expr, const PabloBlock & block) {
    165     return isa<Statement>(expr) && inCurrentBlock(cast<Statement>(expr), block);
    166 }
     166inline bool isNegated(const BooleanReassociationPass::VertexData & data) {
     167    return (data.first == TypeId::Not) && (data.second != nullptr);
     168}
     169
     170inline bool BooleanReassociationPass::isMutable(const VertexData & data, const PabloBlock &) {
     171    return (data.first != TypeId::Var);
     172}
     173
     174inline bool BooleanReassociationPass::isNonEscaping(const VertexData & data) {
     175    return data.first != TypeId::Assign && data.first != TypeId::Next;
     176}
     177
     178inline bool BooleanReassociationPass::isSameType(const VertexData & data1, const VertexData & data2) {
     179    return data1.first == data2.first;
     180}
     181
    167182
    168183/** ------------------------------------------------------------------------------------------------------------- *
     
    185200static void printGraph(const PabloBlock & block, const Graph & G, const std::string name) {
    186201    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 
    196202    out << "digraph " << name << " {\n";
    197     for (auto u : ordering) {
     203    for (auto u : make_iterator_range(vertices(G))) {
    198204        if (in_degree(u, G) == 0 && out_degree(u, G) == 0) {
    199205            continue;
    200206        }
    201207        out << "v" << u << " [label=\"";
    202         PabloAST * expr = G[u];
    203         if (isa<Statement>(expr)) {
     208        PabloAST * expr;
     209        TypeId typeId;
     210        std::tie(typeId, expr) = G[u];
     211        bool temporary = false;
     212        bool error = false;
     213        if (expr == nullptr) {
     214            temporary = true;
     215            out << u << ": ";
     216            switch (typeId) {
     217                case TypeId::And:
     218                    out << "And";
     219                    break;
     220                case TypeId::Or:
     221                    out << "Or";
     222                    break;
     223                case TypeId::Xor:
     224                    out << "Xor";
     225                    break;
     226                default:
     227                    out << "???";
     228                    error = true;
     229                    break;
     230            }
     231        } else if (isa<Statement>(expr)) {
    204232            if (LLVM_UNLIKELY(isa<If>(expr))) {
    205233                out << "If ";
     
    217245        }
    218246        out << "\"";
    219         if (!inCurrentBlock(expr, block)) {
     247        if (BooleanReassociationPass::isMutable(G[u], block) == false) {
    220248            out << " style=dashed";
    221249        }
     250        if (error) {
     251            out << " color=red";
     252        } else if (temporary) {
     253            out << " color=blue";
     254        }
    222255        out << "];\n";
    223256    }
    224 
    225257    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]";
     258        out << "v" << source(e, G) << " -> v" << target(e, G);
     259        if (G[e]) {
     260             out << " [label=\"";
     261             PabloPrinter::print(G[e], out);
     262             out << "\"]";
    230263        }
    231264        out << ";\n";
     
    235268
    236269        out << "{ rank=same;";
    237         for (auto u : ordering) {
     270        for (auto u : make_iterator_range(vertices(G))) {
    238271            if (in_degree(u, G) == 0 && out_degree(u, G) != 0) {
    239272                out << " v" << u;
     
    243276
    244277        out << "{ rank=same;";
    245         for (auto u : ordering) {
     278        for (auto u : make_iterator_range(vertices(G))) {
    246279            if (out_degree(u, G) == 0 && in_degree(u, G) != 0) {
    247280                out << " v" << u;
     
    257290
    258291/** ------------------------------------------------------------------------------------------------------------- *
    259  * @brief printGraph
    260  ** ------------------------------------------------------------------------------------------------------------- */
    261 template<typename SubgraphType>
    262 static 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 /** ------------------------------------------------------------------------------------------------------------- *
    322292 * @brief createTree
    323293 ** ------------------------------------------------------------------------------------------------------------- */
    324 static PabloAST * createTree(PabloBlock & block, const PabloAST::ClassTypeId typeId, circular_buffer<PabloAST *> & Q) {
     294static Statement * createTree(PabloBlock & block, const Vertex u, Graph & G) {
     295    circular_buffer<PabloAST *> Q(in_degree(u, G));
     296    for (const auto e : make_iterator_range(in_edges(u, G))) {
     297        PabloAST * expr = G[source(e, G)].second;
     298        assert (expr);
     299        assert (std::find(Q.begin(), Q.end(), expr) == Q.end());
     300        Q.push_back(expr);
     301    }
    325302    assert (Q.size() > 1);
     303    const TypeId typeId = G[u].first;
    326304    while (Q.size() > 1) {
    327305        PabloAST * e1 = Q.front(); Q.pop_front();
     
    340318        Q.push_back(expr);
    341319    }
    342     PabloAST * const expr = Q.front();
    343     Q.clear();
    344     return expr;
     320    Statement * const result = cast<Statement>(Q.front());
     321    G[u].second = result;
     322    return result;
    345323}
    346324
     
    351329    Graph G;
    352330
     331    raw_os_ostream out(std::cerr);
     332    out << "============================================================\n";
     333    PabloPrinter::print(function.getEntryBlock().statements(), out);
     334    out << "------------------------------------------------------------\n";
     335    out.flush();
     336
    353337    summarizeAST(block, G);
    354     assert (summarizeGraph(block, G) == false);
    355338    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";
    367339
    368340    circular_buffer<Vertex> Q(num_vertices(G));
     
    372344    while (!Q.empty()) {
    373345        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));
    380                     for (auto e : make_iterator_range(in_edges(u, G))) {
    381                         nodes.push_back(G[source(e, G)]);
    382                     }
    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                         }
    395                     }
    396                 }
    397                 block.insert(stmt);
    398             }
    399         }
    400     }
    401 
    402     out << "------------------------------------------------------\n";
    403     PabloPrinter::print(block, " < ", out);
    404     out << "------------------------------------------------------\n";
     346        if (LLVM_LIKELY(isMutable(G[u], block))) {
     347            out << "Mutable: " << u << ": ";
     348            PabloPrinter::print(G[u].second, out);
     349            out.flush();
     350            Statement * stmt = nullptr;
     351            if (isOptimizable(G[u])) {
     352                stmt = createTree(block, u, G);
     353            } else { // update any potential mappings
     354                stmt = cast<Statement>(G[u].second);
     355            }
     356            assert (stmt);
     357            PabloPrinter::print(stmt, " -> ", out);
     358            out << '\n';
     359            out.flush();
     360            assert (stmt->getParent() == &block);
     361            for (auto e : make_iterator_range(out_edges(u, G))) {
     362                if (G[e] && G[e] != stmt) {
     363                    PabloAST * expr = G[target(e, G)].second;
     364                    if (expr) { // processing a yet-to-be created value
     365                        cast<Statement>(expr)->replaceUsesOfWith(G[e], stmt);
     366                    }
     367                }
     368            }
     369            block.insert(stmt);
     370        }
     371    }
     372
     373    Simplifier::deadCodeElimination(function.getEntryBlock());
     374
     375    out << "------------------------------------------------------------\n";
     376    PabloPrinter::print(function.getEntryBlock().statements(), out);
    405377    out.flush();
    406378
    407379    PabloVerifier::verify(function);
     380}
     381
     382/** ------------------------------------------------------------------------------------------------------------- *
     383 * @brief getVertex
     384 ** ------------------------------------------------------------------------------------------------------------- */
     385static inline Vertex getVertex(PabloAST * expr, Graph & G, Map & M, const PabloBlock & block) {
     386    const auto f = M.find(expr);
     387    if (f != M.end()) {
     388        return f->second;
     389    }
     390    // To simplify future analysis, every statement not in the current block will be recorded as a Var.
     391    const TypeId typeId = inCurrentBlock(expr, block) ? expr->getClassTypeId() : TypeId::Var;
     392    const auto u = add_vertex(std::make_pair(typeId, expr), G);
     393    M.insert(std::make_pair(expr, u));
     394    return u;
    408395}
    409396
     
    411398 * @brief summarizeAST
    412399 *
    413  * This function scans through a basic block (starting by its terminals) and computes a DAG in which any sequences
    414  * of AND, OR or XOR functions are "flattened" (i.e., allowed to have any number of inputs.) This allows us to
    415  * reassociate them in the most efficient way possible.
     400 * This function scans through a scope blockand computes a DAG G in which any sequences of AND, OR or XOR functions
     401 * are "flattened" (i.e., allowed to have any number of inputs.)
    416402 ** ------------------------------------------------------------------------------------------------------------- */
    417403void BooleanReassociationPass::summarizeAST(PabloBlock & block, Graph & G) const {
     
    419405    // Compute the base def-use graph ...
    420406    for (Statement * stmt : block) {
    421         const Vertex u = getVertex(stmt, G, M);
     407        const Vertex u = getVertex(stmt, G, M, block);
    422408        for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
    423409            PabloAST * const op = stmt->getOperand(i);
     
    425411                continue;
    426412            }
    427             add_edge(op, getVertex(op, G, M), u, G);
     413            const Vertex v = getVertex(op, G, M, block);
     414            if (!edge(v, u, G).second) {
     415                add_edge(op, v, u, G);
     416            }
     417            // If this operand is a Not operation that is not in this PabloBlock,
     418            // pull its input operand in. It may lead to future optimizations.
     419            if (LLVM_UNLIKELY(isa<Not>(op) && !inCurrentBlock(cast<Not>(op), block))) {
     420                PabloAST * const neg = cast<Not>(op)->getExpr();
     421                const Vertex w = getVertex(neg, G, M, block);
     422                if (!edge(w, v, G).second) {
     423                    add_edge(neg, w, v, G);
     424                }
     425            }
    428426        }
    429427        if (isa<If>(stmt)) {
    430428            for (Assign * def : cast<const If>(stmt)->getDefined()) {
    431                 const Vertex v = getVertex(def, G, M);
     429                const Vertex v = getVertex(def, G, M, block);
    432430                add_edge(def, u, v, G);
    433431                resolveUsages(v, def, block, G, M, stmt);
     
    435433        } else if (isa<While>(stmt)) {
    436434            for (Next * var : cast<const While>(stmt)->getVariants()) {
    437                 const Vertex v = getVertex(var, G, M);
     435                const Vertex v = getVertex(var, G, M, block);
    438436                add_edge(var, u, v, G);
    439437                resolveUsages(v, var, block, G, M, stmt);
     
    443441        }
    444442    }
    445     summarizeGraph(block, G);
    446 }
    447 
    448 /** ------------------------------------------------------------------------------------------------------------- *
    449  * @brief resolveUsages
    450  ** ------------------------------------------------------------------------------------------------------------- */
    451 bool 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);
    479                     }
    480                     clear_vertex(u, G);
    481                     modified = true;
    482                     continue;
    483                 }
    484             }
    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;
     443    std::vector<Vertex> mapping(num_vertices(G));
     444    summarizeGraph(G, mapping);
    493445}
    494446
     
    512464                            throw std::runtime_error("Failed to resolve scope block!");
    513465                        }
    514                         if (LLVM_UNLIKELY(f->second == ignoreIfThis)) {
     466                        Statement * branch = f->second;
     467                        if (LLVM_UNLIKELY(branch == ignoreIfThis)) {
    515468                            break;
    516469                        }
    517                         add_edge(u, getVertex(f->second, G, M), G);
     470                        // Add in a Var denoting the user of this expression so that it can be updated if expr changes.
     471                        const Vertex v = getVertex(user, G, M, block);
     472                        add_edge(expr, u, v, G);
     473                        const Vertex w = getVertex(branch, G, M, block);
     474                        add_edge(nullptr, v, w, G);
    518475                        break;
    519476                    }
     
    523480        }
    524481    }
     482}
     483
     484/** ------------------------------------------------------------------------------------------------------------- *
     485 * @brief summarizeGraph
     486 ** ------------------------------------------------------------------------------------------------------------- */
     487inline void BooleanReassociationPass::summarizeGraph(Graph & G, std::vector<Vertex> & mapping) {
     488    std::vector<Vertex> reverse_topological_ordering;
     489    reverse_topological_ordering.reserve(num_vertices(G));
     490    topological_sort(G, std::back_inserter(reverse_topological_ordering));
     491    assert(mapping.size() >= num_vertices(G));
     492    for (const Vertex u : reverse_topological_ordering) {
     493        if (LLVM_LIKELY(out_degree(u, G) > 0)) {
     494            if (isOptimizable(G[u])) {
     495                if (LLVM_UNLIKELY(in_degree(u, G) == 1)) {
     496                    // We have a redundant node here that'll simply end up being a duplicate
     497                    // of the input value. Remove it and add any of its outgoing edges to its
     498                    // input node.
     499                    const auto ei = first(in_edges(u, G));
     500                    const Vertex v = source(ei, G);
     501                    for (auto ej : make_iterator_range(out_edges(u, G))) {
     502                        const Vertex w = target(ej, G);
     503                        add_edge(G[ei], v, w, G);
     504                        if (mapping[w] == mapping[u]) {
     505                            mapping[w] = v;
     506                        }
     507                    }
     508                    clear_vertex(u, G);
     509                    G[u].first = TypeId::Var;
     510                    mapping[u] = v;
     511                    continue;
     512                } else if (LLVM_UNLIKELY(out_degree(u, G) == 1)) {
     513                    // Otherwise if we have a single user, we have a similar case as above but
     514                    // we can only merge this vertex into the outgoing instruction if they are
     515                    // of the same type.
     516                    const auto ei = first(out_edges(u, G));
     517                    const Vertex v = target(ei, G);
     518                    if (LLVM_UNLIKELY(isSameType(G[v], G[u]))) {
     519                        for (auto ej : make_iterator_range(in_edges(u, G))) {
     520                            add_edge(G[ei], source(ej, G), v, G);
     521                        }
     522                        clear_vertex(u, G);
     523                        G[u].first = TypeId::Var;
     524                        mapping[u] = v;
     525                    }
     526                }
     527            }
     528        } else if (isNonEscaping(G[u])) {
     529            clear_in_edges(u, G);
     530            G[u].first = TypeId::Var;
     531        }
     532    }
     533
     534    // Test whether any operation has (A op2 B) op1 (¬A op3 C) contained within it, where op1, op2 and op3 are all
     535    // optimizable operations; if so, modify G to reflect the result. The main goal is to optimize the underlying
     536    // equations but this also eliminates a problematic case in which the internal boolean simplification logic
     537    // could detect the contradiction and return an unexpected value.
     538
     539//    VertexSet inputs;
     540//    VertexSets lit;
     541//    VertexSets neg;
     542//    for (const Vertex t : reverse_topological_ordering) {
     543//        if (isOptimizable(G[t])) {
     544//            for (auto e : make_iterator_range(in_edges(t, G))) {
     545//                const Vertex u = source(e, G);
     546//                if (isOptimizable(G[u])) {
     547//                    inputs.push_back(u);
     548//                }
     549//            }
     550//            if (inputs.size() > 1) {
     551//                unsigned count = 0;
     552
     553//                for (const Vertex u : inputs) {
     554//                    lit[count].clear();
     555//                    neg[count].clear();
     556//                    for (auto ei : make_iterator_range(in_edges(u, G))) {
     557//                        const Vertex w = source(ei, G);
     558//                        if (isOptimizable(G[w])) {
     559//                            lit[count].push_back(w);
     560//                        } else if (LLVM_UNLIKELY(isNegated(G[w]))) {
     561//                            assert (in_degree(w, G) > 0);
     562//                            neg[count].push_back(source(first(in_edges(w, G)), G));
     563//                        }
     564//                    }
     565//                    std::sort(lit[count].begin(), lit[count].end());
     566//                    std::sort(neg[count].begin(), neg[count].end());
     567//                    ++count;
     568//                }
     569
     570
     571//                for (unsigned i = 0; i != count; ++i) {
     572//                    for (unsigned j = 0; j != count; ++j) {
     573//                        VertexSet cap;
     574//                        std::set_intersection(lit[i].begin(), lit[i].end(), neg[j].begin(), neg[j].end(), std::back_inserter(cap));
     575
     576
     577//                    }
     578//                }
     579
     580
     581
     582//            }
     583//            inputs.clear();
     584//        }
     585//    }
    525586}
    526587
     
    696757 * @brief safeDistributionSets
    697758 ** ------------------------------------------------------------------------------------------------------------- */
    698 static DistributionSets safeDistributionSets(const PabloBlock & block, const Graph & G, DistributionGraph & H) {
     759static DistributionSets safeDistributionSets(const Graph & G, DistributionGraph & H) {
    699760    const auto F = makeGraphFacade(H);
    700761    DistributionSets T;
     
    712773 * @brief generateDistributionGraph
    713774 ** ------------------------------------------------------------------------------------------------------------- */
    714 void generateDistributionGraph(const PabloBlock & block, const Graph & G, DistributionGraph & H) {
     775void generateDistributionGraph(const Graph & G, DistributionGraph & H) {
    715776    DistributionMap M;
    716777    for (const Vertex u : make_iterator_range(vertices(G))) {
    717         if (in_degree(u, G) > 0) {
    718             const TypeId outerTypeId = G[u]->getClassTypeId();
    719             if (outerTypeId == TypeId::And || outerTypeId == TypeId::Or) {
    720                 if (inCurrentBlock(cast<Statement>(G[u]), block)) {
    721                     const TypeId innerTypeId = (outerTypeId == TypeId::And) ? TypeId::Or : TypeId::And;
    722                     flat_set<Vertex> distributable;
    723                     for (auto e : make_iterator_range(in_edges(u, G))) {
    724                         const Vertex v = source(e, G);
    725                         if (LLVM_UNLIKELY(G[v]->getClassTypeId() == innerTypeId && inCurrentBlock(cast<Statement>(G[v]), block))) {
    726                             bool safe = true;
    727                             for (const auto e : make_iterator_range(out_edges(v, G))) {
    728                                 if (G[target(e, G)]->getClassTypeId() != outerTypeId) {
    729                                     safe = false;
    730                                     break;
    731                                 }
    732                             }
    733                             if (safe) {
    734                                 distributable.insert(v);
    735                             }
     778        const TypeId outerTypeId = G[u].first;
     779        if (outerTypeId == TypeId::And || outerTypeId == TypeId::Or) {
     780            const TypeId innerTypeId = (outerTypeId == TypeId::And) ? TypeId::Or : TypeId::And;
     781            flat_set<Vertex> distributable;
     782            for (auto e : make_iterator_range(in_edges(u, G))) {
     783                const Vertex v = source(e, G);
     784                if (LLVM_UNLIKELY(G[v].first == innerTypeId)) {
     785                    bool safe = true;
     786                    for (const auto e : make_iterator_range(out_edges(v, G))) {
     787                        if (G[target(e, G)].first != outerTypeId) {
     788                            safe = false;
     789                            break;
    736790                        }
    737791                    }
    738                     if (LLVM_LIKELY(distributable.size() > 1)) {
    739                         // We're only interested in computing a subgraph of G in which every source has an out-degree
    740                         // greater than 1. Otherwise we'd only end up permuting the AND/OR sequence with no logical
    741                         // benefit. (Note: this does not consider register pressure / liveness.)
    742                         flat_map<Vertex, bool> observedMoreThanOnce;
    743                         bool anyOpportunities = false;
    744                         for (const Vertex v : distributable) {
    745                             for (auto e : make_iterator_range(in_edges(v, G))) {
    746                                 const Vertex w = source(e, G);
    747                                 auto ob = observedMoreThanOnce.find(w);
    748                                 if (ob == observedMoreThanOnce.end()) {
    749                                     observedMoreThanOnce.emplace(w, false);
    750                                 } else {
    751                                     ob->second = true;
    752                                     anyOpportunities = true;
     792                    if (safe) {
     793                        distributable.insert(v);
     794                    }
     795                }
     796            }
     797            if (LLVM_LIKELY(distributable.size() > 1)) {
     798                // We're only interested in computing a subgraph of G in which every source has an out-degree
     799                // greater than 1. Otherwise we'd only end up permuting the AND/OR sequence with no logical
     800                // benefit. (Note: this does not consider register pressure / liveness.)
     801                flat_map<Vertex, bool> observedMoreThanOnce;
     802                bool anyOpportunities = false;
     803                for (const Vertex v : distributable) {
     804                    for (auto e : make_iterator_range(in_edges(v, G))) {
     805                        const Vertex w = source(e, G);
     806                        auto ob = observedMoreThanOnce.find(w);
     807                        if (ob == observedMoreThanOnce.end()) {
     808                            observedMoreThanOnce.emplace(w, false);
     809                        } else {
     810                            ob->second = true;
     811                            anyOpportunities = true;
     812                        }
     813                    }
     814                }
     815                if (anyOpportunities) {
     816                    for (const auto ob : observedMoreThanOnce) {
     817                        if (ob.second) {
     818                            const Vertex w = ob.first;
     819                            for (auto e : make_iterator_range(out_edges(w, G))) {
     820                                const Vertex v = target(e, G);
     821                                if (distributable.count(v)) {
     822                                    const Vertex y = getVertex(v, H, M);
     823                                    add_edge(y, getVertex(u, H, M), H);
     824                                    add_edge(getVertex(w, H, M), y, H);
    753825                                }
    754826                            }
    755827                        }
    756                         if (anyOpportunities) {
    757                             for (const auto ob : observedMoreThanOnce) {
    758                                 if (ob.second) {
    759                                     const Vertex w = ob.first;
    760                                     for (auto e : make_iterator_range(out_edges(w, G))) {
    761                                         const Vertex v = target(e, G);
    762                                         if (distributable.count(v)) {
    763                                             const Vertex y = getVertex(v, H, M);
    764                                             add_edge(y, getVertex(u, H, M), H);
    765                                             add_edge(getVertex(w, H, M), y, H);
    766                                         }
    767                                     }
    768                                 }
    769                             }
    770                         }
    771                     }
    772                 }
    773             }
    774         }
    775     }
    776 }
     828                    }
     829                }
     830            }
     831        }
     832    }
     833}
     834
     835
    777836
    778837/** ------------------------------------------------------------------------------------------------------------- *
     
    781840 * Apply the distribution law to reduce computations whenever possible.
    782841 ** ------------------------------------------------------------------------------------------------------------- */
    783 bool BooleanReassociationPass::redistributeAST(PabloBlock & block, Graph & G) const {
    784     bool anyChanges = false;
    785 
    786     ++distributionCount;
     842void BooleanReassociationPass::redistributeAST(const PabloBlock & block, Graph & G) const {
     843
     844    printGraph(block, G, "G0");
     845
     846    unsigned count = 0;
     847
     848    std::vector<Vertex> mapping(num_vertices(G) + 16);
     849    std::iota(mapping.begin(), mapping.end(), 0); // 0,1,.....n
    787850
    788851    for (;;) {
     
    790853        DistributionGraph H;
    791854
    792         generateDistributionGraph(block, G, H);
     855        generateDistributionGraph(G, H);
    793856
    794857        // If we found no potential opportunities then we cannot apply the distribution law to any part of G.
     
    797860        }
    798861
    799         const DistributionSets distributionSets = safeDistributionSets(block, G, H);
     862        const DistributionSets distributionSets = safeDistributionSets(G, H);
    800863
    801864        if (LLVM_UNLIKELY(distributionSets.empty())) {
     
    803866        }
    804867
     868        raw_os_ostream out(std::cerr);
     869        out << "DISTRIBUTION SETS: " << distributionSets.size() << '\n';
     870
     871        ++count;
     872
     873        unsigned subcount = 0;
     874
     875
     876
    805877        for (const DistributionSet & set : distributionSets) {
     878
    806879            // Each distribution tuple consists of the sources, intermediary, and sink nodes.
    807880            const VertexSet & sources = std::get<0>(set);
     
    809882            const VertexSet & sinks = std::get<2>(set);
    810883
    811             const TypeId outerTypeId = G[H[sinks.front()]]->getClassTypeId();
     884            out << "SOURCES:";
     885            for (const Vertex u : sources) {
     886                const Vertex x = mapping[H[u]];
     887                out << " " << x << ": "; PabloPrinter::print(G[x].second, out);
     888            }
     889            out << "\n";
     890            out << "INTERMEDIARY:";
     891            for (const Vertex u : intermediary) {
     892                const Vertex x = mapping[H[u]];
     893                out << " " << x << ": "; PabloPrinter::print(G[x].second, out);
     894            }
     895            out << "\n";
     896            out << "SINKS:";
     897            for (const Vertex u : sinks) {
     898                const Vertex x = mapping[H[u]];
     899                out << " " << x << ": "; PabloPrinter::print(G[x].second, out);
     900            }
     901            out << "\n";
     902            out.flush();
     903
     904            const TypeId outerTypeId = G[mapping[H[sinks.front()]]].first;
    812905            assert (outerTypeId == TypeId::And || outerTypeId == TypeId::Or);
    813906            const TypeId innerTypeId = (outerTypeId == TypeId::Or) ? TypeId::And : TypeId::Or;
    814907
    815             // Eliminate the edges from our original graph G
    816             for (const Vertex u : intermediary) {
    817                 const auto x = H[u];
    818                 assert (G[x]->getClassTypeId() == innerTypeId);
    819                 for (const Vertex s : sources) {
    820                     assert (edge(H[s], x, G).second);
    821                     remove_edge(H[s], x, G);
    822                 }
     908            // Update G to match the desired changes (TODO: modify this to reuse a discarded vertex instead)
     909            const Vertex x = add_vertex(std::make_pair(outerTypeId, nullptr), G);
     910            const Vertex y = add_vertex(std::make_pair(innerTypeId, nullptr), G);
     911            mapping.resize(num_vertices(G));
     912            mapping[x] = x;
     913            mapping[y] = y;
     914
     915            for (const Vertex i : intermediary) {
     916                const auto u = mapping[H[i]];
     917                assert (G[u].first == innerTypeId);
    823918                for (const Vertex t : sinks) {
    824                     assert (edge(x, H[t], G).second);
    825                     assert (G[H[t]]->getClassTypeId() == outerTypeId);
    826                     remove_edge(x, H[t], G);
    827                 }
    828             }
    829 
    830             // Update G to match the desired changes
    831             const Vertex x = add_vertex(nullptr, G);
    832             const Vertex y = add_vertex(nullptr, G);
    833             for (const Vertex u : intermediary) {
    834                 add_edge(nullptr, H[u], x, G);
    835             }
     919                    const auto v = mapping[H[t]];
     920                    assert (G[v].first == outerTypeId);
     921                    for (auto e : make_iterator_range(out_edges(u, G))) {
     922                        if (target(e, G) == v) {
     923                            remove_edge(e, G);
     924                        }
     925                    }
     926                }
     927                add_edge(nullptr, u, x, G);
     928            }           
     929
    836930            for (const Vertex s : sources) {
    837                 add_edge(nullptr, H[s], y, G);
    838             }
     931                const auto u = mapping[H[s]];
     932                for (const Vertex i : intermediary) {
     933                    const auto v = mapping[H[i]];
     934                    for (auto e : make_iterator_range(out_edges(u, G))) {
     935                        if (target(e, G) == v) {
     936                            remove_edge(e, G);
     937                        }
     938                    }
     939                }
     940                add_edge(nullptr, u, y, G);
     941            }
     942
     943            add_edge(nullptr, x, y, G);
     944
    839945            for (const Vertex t : sinks) {
    840                 add_edge(nullptr, y, H[t], G);
    841             }
    842             add_edge(nullptr, x, y, G);
    843 
    844             // Now begin transforming the AST (TODO: fix the abstraction so I can defer creation until the final phase)
    845             circular_buffer<PabloAST *> Q(std::max(in_degree(x, G), in_degree(y, G)));
    846             for (auto e : make_iterator_range(in_edges(x, G))) {
    847                 Q.push_back(G[source(e, G)]);
    848             }
    849             G[x] = createTree(block, outerTypeId, Q);
    850             for (auto e : make_iterator_range(in_edges(y, G))) {
    851                 Q.push_back(G[source(e, G)]);
    852             }
    853             G[y] = createTree(block, innerTypeId, Q);
    854 
    855             // Summarize the graph after transforming G
    856             summarizeGraph(block, G);
    857         }
    858         anyChanges = true;
    859     }
    860     return anyChanges;
    861 }
    862 
    863 }
     946                const auto v = mapping[H[t]];
     947                add_edge(G[v].second, y, v, G);
     948            }
     949
     950            summarizeGraph(G, mapping);
     951
     952            printGraph(block, G, "G" + std::to_string(count) + "_" + std::to_string(++subcount));
     953        }
     954    }
     955}
     956
     957}
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/booleanreassociationpass.h

    r4768 r4769  
    33
    44#include <pablo/codegenstate.h>
     5#include <boost/container/flat_set.hpp>
    56#include <boost/container/flat_map.hpp>
    67#include <boost/graph/adjacency_list.hpp>
     
    1011class BooleanReassociationPass {
    1112public:
    12     using Graph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS, PabloAST *, PabloAST *>;
     13    using VertexData = std::pair<PabloAST::ClassTypeId, PabloAST *>;
     14    using Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, VertexData, PabloAST *>;
    1315    using Vertex = Graph::vertex_descriptor;
    1416    using Map = std::unordered_map<const PabloAST *, Vertex>;
     
    2325    void processScope(PabloFunction & function, PabloBlock & block);
    2426    void summarizeAST(PabloBlock & block, Graph & G) const;
    25     static bool summarizeGraph(PabloBlock & block, Graph & G);
     27    static void summarizeGraph(Graph & G, std::vector<Vertex> & mapping);
    2628    void resolveUsages(const Vertex u, PabloAST * expr, PabloBlock & block, Graph & G, Map & M, Statement * ignoreIfThis = nullptr) const;
    27     bool redistributeAST(PabloBlock & block, Graph & G) const;
     29    void redistributeAST(const PabloBlock & block, Graph & G) const;
     30public:
     31    static bool isOptimizable(const VertexData & data);
     32    static bool isMutable(const VertexData & data, const PabloBlock &block);
     33    static bool isNonEscaping(const VertexData & data);
     34    static bool isSameType(const VertexData & data1, const VertexData & data2);
    2835private:
    2936    boost::container::flat_map<PabloBlock *, Statement *> mResolvedScopes;
  • icGREP/icgrep-devel/icgrep/pablo/printer_pablos.cpp

    r4762 r4769  
    208208        print(whl->getCondition(), strm);
    209209    } else if (const Statement * stmt = dyn_cast<Statement>(expr)) {
     210        assert (stmt->getName());
    210211        strm << stmt->getName();
    211212    } else {
    212         strm << "**UNKNOWN Pablo Expression type **\n" << "\n";
    213     }
    214 }
    215 
    216 
     213        strm << "???";
     214    }
     215}
     216
     217
Note: See TracChangeset for help on using the changeset viewer.