Changeset 4762 for icGREP


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

Temporary check in

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

Legend:

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

    r4761 r4762  
    3333    brp.resolveScopes(function);
    3434    brp.processScopes(function);
     35
     36    raw_os_ostream out(std::cerr);
     37    PabloPrinter::print(function.getEntryBlock().statements(), out);
     38
    3539    Simplifier::optimize(function);
    3640    return true;
     
    130134}
    131135
    132 /** ------------------------------------------------------------------------------------------------------------- *
    133  * @brief isCutNecessary
    134  ** ------------------------------------------------------------------------------------------------------------- */
    135 static inline bool isCutNecessary(const Vertex u, const Vertex v, const Graph & G, const std::vector<unsigned> & component) {
    136     // Either this edge crosses a component boundary or the operations performed by the vertices differs, we need to cut
    137     // the graph here and generate two partial equations.
    138     if (LLVM_UNLIKELY(component[u] != component[v])) {
    139         return true;
    140     } else if (LLVM_UNLIKELY((in_degree(u, G) != 0) && (G[u]->getClassTypeId() != G[v]->getClassTypeId()))) {
    141         return true;
    142     }
    143     return false;
    144 }
    145 
    146 /** ------------------------------------------------------------------------------------------------------------- *
    147  * @brief push
    148  ** ------------------------------------------------------------------------------------------------------------- */
    149 static inline void push(const Vertex u, VertexQueue & Q) {
    150     if (LLVM_UNLIKELY(Q.full())) {
    151         Q.set_capacity(Q.capacity() * 2);
    152     }
    153     Q.push_back(u);
    154     assert (Q.back() == u);
    155 }
    156 
    157 /** ------------------------------------------------------------------------------------------------------------- *
    158  * @brief pop
    159  ** ------------------------------------------------------------------------------------------------------------- */
    160 static inline Vertex pop(VertexQueue & Q) {
    161     assert (!Q.empty() && "Popping an empty vertex queue");
    162     const Vertex u = Q.front();
    163     Q.pop_front();
    164     return u;
    165 }
     136///** ------------------------------------------------------------------------------------------------------------- *
     137// * @brief isCutNecessary
     138// ** ------------------------------------------------------------------------------------------------------------- */
     139//static inline bool isCutNecessary(const Vertex u, const Vertex v, const Graph & G, const std::vector<unsigned> & component) {
     140//    // Either this edge crosses a component boundary or the operations performed by the vertices differs, we need to cut
     141//    // the graph here and generate two partial equations.
     142//    if (LLVM_UNLIKELY(component[u] != component[v])) {
     143//        return true;
     144//    } else if (LLVM_UNLIKELY((in_degree(u, G) != 0) && (G[u]->getClassTypeId() != G[v]->getClassTypeId()))) {
     145//        return true;
     146//    }
     147//    return false;
     148//}
     149
     150///** ------------------------------------------------------------------------------------------------------------- *
     151// * @brief push
     152// ** ------------------------------------------------------------------------------------------------------------- */
     153//static inline void push(const Vertex u, VertexQueue & Q) {
     154//    if (LLVM_UNLIKELY(Q.full())) {
     155//        Q.set_capacity(Q.capacity() * 2);
     156//    }
     157//    Q.push_back(u);
     158//    assert (Q.back() == u);
     159//}
     160
     161///** ------------------------------------------------------------------------------------------------------------- *
     162// * @brief pop
     163// ** ------------------------------------------------------------------------------------------------------------- */
     164//static inline Vertex pop(VertexQueue & Q) {
     165//    assert (!Q.empty() && "Popping an empty vertex queue");
     166//    const Vertex u = Q.front();
     167//    Q.pop_front();
     168//    return u;
     169//}
    166170
    167171/** ------------------------------------------------------------------------------------------------------------- *
     
    170174template<typename ValueType, typename GraphType, typename MapType>
    171175static inline Vertex getVertex(ValueType value, GraphType & G, MapType & M) {
     176    assert (value);
    172177    const auto f = M.find(value);
    173178    if (f != M.end()) {
     
    212217    out << "digraph " << name << " {\n";
    213218    for (auto u : make_iterator_range(vertices(G))) {
     219        if (in_degree(u, G) == 0 && out_degree(u, G) == 0) {
     220            continue;
     221        }
    214222        out << "v" << u << " [label=\"";
    215223        PabloAST * expr = G[u];
     
    330338inline void BooleanReassociationPass::processScope(PabloBlock & block, std::vector<Statement *> && terminals) {
    331339    Graph G;
    332     summarizeAST(block, terminals, G);
    333 
    334     printGraph(block, G, "G0");
    335 
     340    summarizeAST(block, G);
    336341    redistributeAST(block, G);
    337 
    338     printGraph(block, G, "G1");
     342    printGraph(block, G, "G");
     343
     344
     345
     346
    339347
    340348    circular_buffer<Vertex> Q(num_vertices(G));
     
    347355        const Vertex u = Q.front();
    348356        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));
     357        if (LLVM_LIKELY(in_degree(u, G) != 0 || out_degree(u, G) != 0)) {
     358            PabloAST * expr = G[u];
     359            if (LLVM_LIKELY(inCurrentBlock(expr, block))) {
     360                switch (expr->getClassTypeId()) {
     361                    case TypeId::And:
     362                    case TypeId::Or:
     363                case TypeId::Xor: {
     364                            nodes.set_capacity(in_degree(u, G));
     365                            for (auto e : make_iterator_range(in_edges(u, G))) {
     366                                nodes.push_back(G[source(e, G)]);
     367                            }
     368                            PabloAST * replacement = createTree(block, expr->getClassTypeId(), nodes);
     369                            cast<Statement>(expr)->replaceWith(replacement, true, true);
     370                            expr = replacement;
     371                        }
     372                    default:
     373                        block.insert(cast<Statement>(expr));
     374                }
    369375            }
    370376        }
     
    381387 * reassociate them in the most efficient way possible.
    382388 ** ------------------------------------------------------------------------------------------------------------- */
    383 void BooleanReassociationPass::summarizeAST(PabloBlock & block, std::vector<Statement *> terminals, Graph & G) const {
    384 
    385     VertexQueue Q(128);
    386     EdgeQueue E;
     389void BooleanReassociationPass::summarizeAST(PabloBlock & block, Graph & G) const {
     390
    387391    Map M;
    388392
    389     for (;;) {
    390 
    391         Graph Gk;
    392         Map Mk;
    393 
    394         // Generate a graph depicting the relationships between the terminals. If the original terminals
    395         // cannot be optimized with this algorithm bypass them in favour of their operands. If those cannot
    396         // be optimized, they'll be left as the initial terminals for the next "layer" of the AST.
    397 
    398         for (Statement * term : terminals) {
    399             if (LLVM_LIKELY(Mk.count(term) == 0)) {
    400                 // add or find this terminal in our global graph
    401                 Vertex x = getVertex(term, G, M);
    402                 if (inCurrentBlock(term, block)) {
    403                     if (isOptimizable(term)) {
    404                         const Vertex u = add_vertex(term, Gk);
    405                         Mk.insert(std::make_pair(term, u));
    406                         push(u, Q);
    407                         continue;
    408                     }
    409                 } else if (isa<Assign>(term) || isa<Next>(term)) {
    410                     // If this is an Assign (Next) node whose operand does not originate from the current block
    411                     // then check to see if there is an If (While) node that does.
    412                     Statement * branch = nullptr;
    413                     if (isa<Assign>(term)) {
    414                         for (PabloAST * user : term->users()) {
    415                             if (isa<If>(user)) {
    416                                 const If * ifNode = cast<If>(user);
    417                                 if (inCurrentBlock(ifNode, block)) {
    418                                     const auto & defs = ifNode->getDefined();
    419                                     if (LLVM_LIKELY(std::find(defs.begin(), defs.end(), cast<Assign>(term)) != defs.end())) {
    420                                         branch = cast<Statement>(user);
    421                                         break;
    422                                     }
    423                                 }
    424                             }
     393    // Compute the base def-use graph ...
     394    for (Statement * stmt : block) {
     395        const Vertex u = getVertex(stmt, G, M);
     396        for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
     397            PabloAST * const op = stmt->getOperand(i);
     398            if (LLVM_UNLIKELY(isa<Integer>(op) || isa<String>(op))) {
     399                continue;
     400            }
     401            add_edge(getVertex(op, G, M), u, G);
     402        }
     403        if (isa<If>(stmt)) {
     404            for (Assign * def : cast<const If>(stmt)->getDefined()) {
     405                add_edge(u, getVertex(def, G, M), G);
     406            }
     407        } else if (isa<While>(stmt)) {
     408            for (Next * var : cast<const While>(stmt)->getVariants()) {
     409                add_edge(u, getVertex(var, G, M), G);
     410            }
     411        } else if (isOptimizable(stmt)) {
     412            for (PabloAST * user : stmt->users()) {
     413                if (LLVM_LIKELY(isa<Statement>(user))) {
     414                    PabloBlock * parent = cast<Statement>(user)->getParent();
     415                    if (LLVM_UNLIKELY(parent != &block)) {
     416                        while (parent->getParent() != &block) {
     417                            parent = parent->getParent();
    425418                        }
    426                     } else { // if (isa<Next>(term))
    427                         for (PabloAST * user : term->users()) {
    428                             if (isa<While>(user)) {
    429                                 const While * whileNode = cast<While>(user);
    430                                 if (inCurrentBlock(whileNode, block)) {
    431                                     const auto & vars = whileNode->getVariants();
    432                                     if (LLVM_LIKELY(std::find(vars.begin(), vars.end(), cast<Next>(term)) != vars.end())) {
    433                                         branch = cast<Statement>(user);
    434                                         break;
    435                                     }
    436                                 }
    437                             }
     419                        if (LLVM_UNLIKELY(parent == nullptr)) {
     420                            throw std::runtime_error("Could not locate nested scope block!");
    438421                        }
    439                     }
    440 
    441                     // If we didn't find a branch, then the Assign (Next) node must have come from a preceeding
    442                     // block. Just skip it for now.
    443                     if (branch == nullptr) {
    444                         continue;
    445                     }
    446 
    447                     // Otherwise add the branch to G and test its operands rather than the original terminal
    448                     const Vertex z = getVertex(branch, G, M);
    449                     add_edge(z, x, G);
    450                     x = z;
    451                     term = branch;
    452                 }
    453 
    454                 for (unsigned i = 0; i != term->getNumOperands(); ++i) {
    455                     PabloAST * const op = term->getOperand(i);
    456                     if (LLVM_LIKELY(inCurrentBlock(op, block))) {
    457                         const Vertex y = getVertex(op, G, M);
    458                         add_edge(y, x, G);
    459                         if (LLVM_LIKELY(Mk.count(op) == 0)) {
    460                             const Vertex v = add_vertex(op, Gk);
    461                             Mk.insert(std::make_pair(op, v));
    462                             push(v, Q);
     422                        const auto f = mResolvedScopes.find(parent);
     423                        if (LLVM_UNLIKELY(f == mResolvedScopes.end())) {
     424                            throw std::runtime_error("Failed to resolve scope block!");
    463425                        }
     426                        add_edge(u, getVertex(f->second, G, M), G);
    464427                    }
    465428                }
    466429            }
    467430        }
    468 
    469         if (LLVM_UNLIKELY(Q.empty())) {
    470             break;
    471         }
    472 
    473         for (;;) {
    474             const Vertex u = pop(Q);
    475             if (isOptimizable(Gk[u])) {
    476                 Statement * stmt = cast<Statement>(Gk[u]);
    477                 // If any user of this statement is not in the current block, determine the outermost If/While node
    478                 // that contains this statement within and add an edge from this statement to it to denote both the
    479                 // topological ordering necessary and that this statement must be computed.
    480                 for (PabloAST * user : stmt->users()) {
    481                     if (LLVM_LIKELY(isa<Statement>(user))) {
    482                         PabloBlock * parent = cast<Statement>(user)->getParent();
    483                         if (LLVM_UNLIKELY(parent != &block)) {
    484                             while (parent->getParent() != &block) {
    485                                 parent = parent->getParent();
    486                             }
    487                             if (LLVM_UNLIKELY(parent == nullptr)) {
    488                                 throw std::runtime_error("Could not locate nested scope block!");
    489                             }
    490                             const auto f = mResolvedScopes.find(parent);
    491                             if (LLVM_UNLIKELY(f == mResolvedScopes.end())) {
    492                                 throw std::runtime_error("Failed to resolve scope block!");
    493                             }
    494                             add_edge(u, getVertex(f->second, Gk, Mk), Gk);
    495                         }
     431    }
     432
     433    std::vector<Vertex> ordering;
     434    ordering.reserve(num_vertices(G));
     435    topological_sort(G, std::back_inserter(ordering));
     436
     437    for (auto i = ordering.rbegin(); i != ordering.rend(); ++i) {
     438        const Vertex u = *i;
     439        if (isOptimizable(G[u])) {
     440            std::vector<Vertex> removable;
     441            for (auto e : make_iterator_range(in_edges(u, G))) {
     442                const Vertex v = source(e, G);
     443                if (out_degree(v, G) == 1 && in_degree(v, G) != 0 && G[u]->getClassTypeId() == G[v]->getClassTypeId()) {
     444                    removable.push_back(v);
     445                    for (auto e : make_iterator_range(in_edges(v, G))) {
     446                        add_edge(source(e, G), u, G);
    496447                    }
    497448                }
    498                 // Scan through the use-def chains to locate any chains of rearrangable expressions and their inputs
    499                 for (unsigned i = 0; i != 2; ++i) {
    500                     PabloAST * op = stmt->getOperand(i);
    501                     auto f = Mk.find(op);
    502                     if (f == Mk.end()) {
    503                         const Vertex v = add_vertex(op, Gk);
    504                         f = Mk.insert(std::make_pair(op, v)).first;
    505                         if (op->getClassTypeId() == stmt->getClassTypeId() && inCurrentBlock(cast<Statement>(op), block)) {
    506                             push(v, Q);
    507                         }
    508                     }
    509                     add_edge(f->second, u, Gk);
    510                 }
    511             }
    512             if (Q.empty()) {
    513                 break;
    514             }
    515         }
    516 
    517         // Generate a topological ordering for G; if one of our terminals happens to also be a partial computation of
    518         // another terminal, we need to make sure we compute it as an independent subexpression.
    519         std::vector<unsigned> ordering;
    520         ordering.reserve(num_vertices(Gk));
    521         topological_sort(Gk, std::back_inserter(ordering));
    522         std::vector<unsigned> component(num_vertices(Gk));
    523 
    524         for (;;) {
    525 
    526             // Mark which computation component these vertices are in based on their topological (occurence) order.
    527             unsigned components = 0;
    528             for (auto u : ordering) {
    529                 unsigned id = 0;
    530                 // If this is a sink in G, it is the root of a new component.
    531                 if (out_degree(u, Gk) == 0) {
    532                     id = ++components;
    533                 } else { // otherwise it belongs to the outermost component.
    534                     for (auto e : make_iterator_range(out_edges(u, Gk))) {
    535                         id = std::max(id, component[target(e, Gk)]);
    536                     }
    537                 }
    538                 assert (id && "Topological ordering failed!");
    539                 component[u] = id;
    540             }
    541 
    542             // Cut the graph wherever a computation crosses a component or whenever we need to cut the graph because
    543             // the instructions corresponding to the pair of nodes differs.
    544             graph_traits<Graph>::edge_iterator ei, ei_end;
    545             for (std::tie(ei, ei_end) = edges(Gk); ei != ei_end; ) {
    546                 const Graph::edge_descriptor e = *ei++;
    547                 const Vertex u = source(e, Gk);
    548                 const Vertex v = target(e, Gk);
    549                 if (LLVM_UNLIKELY(isCutNecessary(u, v, Gk, component))) {
    550                     E.push(std::make_pair(u, v));
    551                     remove_edge(u, v, Gk);
    552                 }
    553             }
    554 
    555             // If no cuts are necessary, we're done.
    556             if (E.empty()) {
    557                 break;
    558             }
    559 
    560             for (;;) {
    561 
    562                 Vertex u, v;
    563                 std::tie(u, v) = E.front(); E.pop();
    564 
    565                 // The vertex belonging to a component with a greater number must come "earlier"
    566                 // in the program. By replicating it, this ensures it's computed as an output of
    567                 // one component and used as an input of another.
    568                 if (component[u] < component[v]) {
    569                     std::swap(u, v);
    570                 }
    571 
    572                 // Replicate u and fix the ordering and component vectors to reflect the change in Gk.
    573                 Vertex w = add_vertex(Gk[u], Gk);
    574                 ordering.insert(std::find(ordering.begin(), ordering.end(), u), w);
    575                 assert (component.size() == w);
    576                 component.push_back(component[v]);
    577                 add_edge(w, v, Gk);
    578 
    579                 // However, after we do so, we need to make sure the original source vertex will be a
    580                 // sink in Gk unless it is also an input variable (in which case we'd simply end up with
    581                 // extraneous isolated vertex. Otherwise, we need to make further cuts and replications.
    582                 if (in_degree(u, Gk) != 0) {
    583                     for (auto e : make_iterator_range(out_edges(u, Gk))) {
    584                         E.push(std::make_pair(source(e, Gk), target(e, Gk)));
    585                     }
    586                     clear_out_edges(u, Gk);
    587                 }
    588 
    589                 if (E.empty()) {
    590                     break;
    591                 }
    592             }
    593         }
    594 
    595         // Scan through the graph so that we process the outermost expressions first
    596         for (const Vertex u : ordering) {
    597             if (LLVM_UNLIKELY(out_degree(u, Gk) == 0)) {
    598                 // Create a vertex marking the output statement we may end up replacing
    599                 // and collect the set of source variables in the component
    600                 const Vertex x = getVertex(Gk[u], G, M);
    601                 if (LLVM_LIKELY(in_degree(u, Gk) > 0)) {
    602                     flat_set<PabloAST *> vars;
    603                     flat_set<Vertex> visited;
    604                     for (Vertex v = u;;) {
    605                         if (in_degree(v, Gk) == 0) {
    606                             vars.insert(Gk[v]);
    607                         } else {
    608                             for (auto e : make_iterator_range(in_edges(v, Gk))) {
    609                                 const Vertex w = source(e, Gk);
    610                                 if (LLVM_LIKELY(visited.insert(w).second)) {
    611                                     push(w, Q);
    612                                 }
    613                             }
    614                         }
    615                         if (Q.empty()) {
    616                             break;
    617                         }
    618                         v = pop(Q);
    619                     }
    620                     for (PabloAST * var : vars) {
    621                         add_edge(getVertex(var, G, M), x, G);
    622                     }
    623                 }
    624             }
    625         }
    626 
    627         // Determine the source variables of the next "layer" of the AST
    628         flat_set<Statement *> nextSet;
    629         for (auto u : ordering) {
    630             if (LLVM_UNLIKELY(in_degree(u, Gk) == 0 && isa<Statement>(Gk[u]))) {
    631                 nextSet.insert(cast<Statement>(Gk[u]));
    632             } else if (LLVM_UNLIKELY(out_degree(u, Gk) == 0 && isa<Statement>(Gk[u]))) {
    633                 // some input will also be the output of some subgraph of Gk whenever we cut and
    634                 // replicated a vertex. We don't need to reevaluate it as part of the next layer.
    635                 nextSet.erase(cast<Statement>(Gk[u]));
    636             }
    637         }
    638 
    639         if (LLVM_UNLIKELY(nextSet.empty())) {
    640             break;
    641         }
    642 
    643         terminals.assign(nextSet.begin(), nextSet.end());
    644     }
    645 }
     449            }
     450            for (auto v : removable) {
     451                clear_vertex(v, G);
     452            }
     453        }
     454    }
     455
     456}
     457
     458
     459///** ------------------------------------------------------------------------------------------------------------- *
     460// * @brief summarizeAST
     461// *
     462// * This function scans through a basic block (starting by its terminals) and computes a DAG in which any sequences
     463// * of AND, OR or XOR functions are "flattened" (i.e., allowed to have any number of inputs.) This allows us to
     464// * reassociate them in the most efficient way possible.
     465// ** ------------------------------------------------------------------------------------------------------------- */
     466//void BooleanReassociationPass::summarizeAST(PabloBlock & block, std::vector<Statement *> terminals, Graph & G) const {
     467
     468//    VertexQueue Q(128);
     469//    EdgeQueue E;
     470//    Map M;
     471
     472
     473
     474//    raw_os_ostream out(std::cerr);
     475
     476//    out << "================================================================\n";
     477
     478//    for (;;) {
     479
     480
     481//        Graph Gk;
     482//        Map Mk;
     483
     484//        // Generate a graph depicting the relationships between the terminals. If the original terminals
     485//        // cannot be optimized with this algorithm bypass them in favour of their operands. If those cannot
     486//        // be optimized, they'll be left as the initial terminals for the next "layer" of the AST.
     487
     488//        for (Statement * term : terminals) {
     489//            if (LLVM_LIKELY(Mk.count(term) == 0)) {
     490//                // add or find this terminal in our global graph
     491//                Vertex x = getVertex(term, G, M);
     492
     493//                PabloPrinter::print(term, "term: ", out);
     494//                out << '\n';
     495
     496
     497//                if (inCurrentBlock(term, block)) {
     498//                    if (isOptimizable(term)) {
     499//                        const Vertex u = add_vertex(term, Gk);
     500//                        Mk.insert(std::make_pair(term, u));
     501//                        push(u, Q);
     502//                        continue;
     503//                    }
     504//                } else if (isa<Assign>(term) || isa<Next>(term)) {
     505//                    // If this is an Assign (Next) node whose operand does not originate from the current block
     506//                    // then check to see if there is an If (While) node that does.
     507//                    Statement * branch = nullptr;
     508//                    if (isa<Assign>(term)) {
     509//                        for (PabloAST * user : term->users()) {
     510//                            if (isa<If>(user)) {
     511//                                const If * ifNode = cast<If>(user);
     512//                                if (inCurrentBlock(ifNode, block)) {
     513//                                    const auto & defs = ifNode->getDefined();
     514//                                    if (LLVM_LIKELY(std::find(defs.begin(), defs.end(), cast<Assign>(term)) != defs.end())) {
     515//                                        branch = cast<Statement>(user);
     516//                                        break;
     517//                                    }
     518//                                }
     519//                            }
     520//                        }
     521//                    } else { // if (isa<Next>(term))
     522//                        for (PabloAST * user : term->users()) {
     523//                            if (isa<While>(user)) {
     524//                                const While * whileNode = cast<While>(user);
     525//                                if (inCurrentBlock(whileNode, block)) {
     526//                                    const auto & vars = whileNode->getVariants();
     527//                                    if (LLVM_LIKELY(std::find(vars.begin(), vars.end(), cast<Next>(term)) != vars.end())) {
     528//                                        branch = cast<Statement>(user);
     529//                                        break;
     530//                                    }
     531//                                }
     532//                            }
     533//                        }
     534//                    }
     535
     536//                    // If we didn't find a branch, then the Assign (Next) node must have come from a preceeding
     537//                    // block. Just skip it for now.
     538//                    if (branch == nullptr) {
     539//                        continue;
     540//                    }
     541
     542//                    // Otherwise add the branch to G and test its operands rather than the original terminal
     543//                    const Vertex z = getVertex(branch, G, M);
     544//                    add_edge(z, x, G);
     545//                    x = z;
     546//                    term = branch;
     547
     548//                }
     549
     550//                for (unsigned i = 0; i != term->getNumOperands(); ++i) {
     551//                    PabloAST * const op = term->getOperand(i);
     552//                    if (LLVM_LIKELY(inCurrentBlock(op, block))) {
     553//                        const Vertex y = getVertex(op, G, M);
     554//                        add_edge(y, x, G);
     555
     556//                        if (LLVM_LIKELY(Mk.count(op) == 0)) {
     557//                            const Vertex v = add_vertex(op, Gk);
     558//                            Mk.insert(std::make_pair(op, v));
     559//                            push(v, Q);
     560//                        }
     561//                    }
     562//                }
     563//            }
     564//        }
     565
     566//        out << "----------------------------------------------------------------\n";
     567//        out.flush();
     568
     569//        if (LLVM_UNLIKELY(Q.empty())) {
     570//            break;
     571//        }
     572
     573//        for (;;) {
     574//            const Vertex u = pop(Q);
     575//            if (isOptimizable(Gk[u])) {
     576//                Statement * stmt = cast<Statement>(Gk[u]);
     577//                // If any user of this statement is not in the current block, determine the outermost If/While node
     578//                // that contains this statement within and add an edge from this statement to it to denote both the
     579//                // topological ordering necessary and that this statement must be computed.
     580//                for (PabloAST * user : stmt->users()) {
     581//                    if (LLVM_LIKELY(isa<Statement>(user))) {
     582//                        PabloBlock * parent = cast<Statement>(user)->getParent();
     583//                        if (LLVM_UNLIKELY(parent != &block)) {
     584//                            while (parent->getParent() != &block) {
     585//                                parent = parent->getParent();
     586//                            }
     587//                            if (LLVM_UNLIKELY(parent == nullptr)) {
     588//                                throw std::runtime_error("Could not locate nested scope block!");
     589//                            }
     590//                            const auto f = mResolvedScopes.find(parent);
     591//                            if (LLVM_UNLIKELY(f == mResolvedScopes.end())) {
     592//                                throw std::runtime_error("Failed to resolve scope block!");
     593//                            }
     594//                            add_edge(u, getVertex(f->second, Gk, Mk), Gk);
     595//                        }
     596//                    }
     597//                }
     598//                // Scan through the use-def chains to locate any chains of rearrangable expressions and their inputs
     599//                for (unsigned i = 0; i != 2; ++i) {
     600//                    PabloAST * op = stmt->getOperand(i);
     601//                    auto f = Mk.find(op);
     602//                    if (f == Mk.end()) {
     603//                        const Vertex v = add_vertex(op, Gk);
     604//                        f = Mk.insert(std::make_pair(op, v)).first;
     605//                        if (op->getClassTypeId() == stmt->getClassTypeId() && inCurrentBlock(cast<Statement>(op), block)) {
     606//                            push(v, Q);
     607//                        }
     608//                    }
     609//                    add_edge(f->second, u, Gk);
     610//                }
     611//            }
     612//            if (Q.empty()) {
     613//                break;
     614//            }
     615//        }
     616
     617//        printGraph(block, Gk, "Gk1");
     618
     619//        // Generate a topological ordering for G; if one of our terminals happens to also be a partial computation of
     620//        // another terminal, we need to make sure we compute it as an independent subexpression.
     621//        std::vector<unsigned> ordering;
     622//        ordering.reserve(num_vertices(Gk));
     623//        topological_sort(Gk, std::back_inserter(ordering));
     624//        std::vector<unsigned> component(num_vertices(Gk), 0);
     625
     626//        // Mark which computation component each terminal is in based on their topological (occurence) order.
     627//        unsigned components = 0;
     628//        std::sort(terminals.begin(), terminals.end());
     629//        for (auto u : ordering) {
     630//            unsigned id = 0;
     631//            // If this is a sink in G, it is the root of a new component.
     632//            if (out_degree(u, Gk) == 0 || std::binary_search(terminals.begin(), terminals.end(), Gk[u])) {
     633//                id = ++components;
     634//            } else { // otherwise it belongs to the outermost component.
     635//                for (auto e : make_iterator_range(out_edges(u, Gk))) {
     636//                    assert (component[target(e, Gk)] != 0);
     637//                    id = std::max(id, component[target(e, Gk)]);
     638//                }
     639//            }
     640//            assert (id && "Topological ordering failed!");
     641//            component[u] = id;
     642//        }
     643
     644//        for (;;) {
     645
     646//            // Cut the graph wherever a computation crosses a component or whenever we need to cut the graph because
     647//            // the instructions corresponding to the pair of nodes differs.
     648//            graph_traits<Graph>::edge_iterator ei, ei_end;
     649//            for (std::tie(ei, ei_end) = edges(Gk); ei != ei_end; ) {
     650//                const Graph::edge_descriptor e = *ei++;
     651//                const Vertex u = source(e, Gk);
     652//                const Vertex v = target(e, Gk);
     653//                if (LLVM_UNLIKELY(isCutNecessary(u, v, Gk, component))) {
     654//                    E.push(std::make_pair(u, v));
     655//                    remove_edge(u, v, Gk);
     656//                }
     657//            }
     658
     659//            // If no cuts are necessary, we're done.
     660//            if (E.empty()) {
     661//                break;
     662//            }
     663
     664//            for (;;) {
     665
     666//                Vertex u, v;
     667//                std::tie(u, v) = E.front(); E.pop();
     668
     669//                // The vertex belonging to a component with a greater number must come "earlier"
     670//                // in the program. By replicating it, this ensures it's computed as an output of
     671//                // one component and used as an input of another.
     672//                if (component[u] < component[v]) {
     673//                    std::swap(u, v);
     674//                }
     675
     676//                // Replicate u and fix the ordering and component vectors to reflect the change in Gk.
     677//                const Vertex w = add_vertex(Gk[u], Gk);
     678//                ordering.insert(std::find(ordering.begin(), ordering.end(), u), w);
     679//                assert (component.size() == w);
     680//                component.push_back(component[v]);
     681//                add_edge(w, v, Gk);
     682
     683//                // However, after we do so, we need to make sure the original source vertex will be a
     684//                // sink in Gk unless it is also an input variable (in which case we'd simply end up with
     685//                // extraneous isolated vertex. Otherwise, we need to make further cuts and replications.
     686//                if (in_degree(u, Gk) != 0) {
     687//                    for (auto e : make_iterator_range(out_edges(u, Gk))) {
     688//                        E.push(std::make_pair(source(e, Gk), target(e, Gk)));
     689//                    }
     690//                    clear_out_edges(u, Gk);
     691//                }
     692
     693//                if (E.empty()) {
     694//                    break;
     695//                }
     696//            }
     697
     698//            // Mark which computation component each sink is in based on their topological (occurence) order.
     699//            unsigned components = 0;
     700//            #ifndef NDEBUG
     701//            std::fill(component.begin(), component.end(), 0);
     702//            #endif
     703//            for (auto u : ordering) {
     704//                unsigned id = 0;
     705//                // If this is a sink in G, it is the root of a new component.
     706//                if (out_degree(u, Gk) == 0) {
     707//                    id = ++components;
     708//                } else { // otherwise it belongs to the outermost component.
     709//                    for (auto e : make_iterator_range(out_edges(u, Gk))) {
     710//                        assert (component[target(e, Gk)] != 0);
     711//                        id = std::max(id, component[target(e, Gk)]);
     712//                    }
     713//                }
     714//                assert (id && "Topological ordering failed!");
     715//                component[u] = id;
     716//            }
     717//        }
     718
     719//        printGraph(block, Gk, "Gk2");
     720
     721//        // Scan through the graph so that we process the outermost expressions first
     722//        for (const Vertex u : ordering) {
     723//            if (LLVM_UNLIKELY(out_degree(u, Gk) == 0)) {
     724//                // Create a vertex marking the output statement we may end up replacing
     725//                // and collect the set of source variables in the component
     726//                const Vertex x = getVertex(Gk[u], G, M);
     727//                if (LLVM_LIKELY(in_degree(u, Gk) > 0)) {
     728//                    flat_set<PabloAST *> vars;
     729//                    flat_set<Vertex> visited;
     730//                    for (Vertex v = u;;) {
     731//                        if (in_degree(v, Gk) == 0) {
     732//                            vars.insert(Gk[v]);
     733//                        } else {
     734//                            for (auto e : make_iterator_range(in_edges(v, Gk))) {
     735//                                const Vertex w = source(e, Gk);
     736//                                if (LLVM_LIKELY(visited.insert(w).second)) {
     737//                                    push(w, Q);
     738//                                }
     739//                            }
     740//                        }
     741//                        if (Q.empty()) {
     742//                            break;
     743//                        }
     744//                        v = pop(Q);
     745//                    }
     746//                    for (PabloAST * var : vars) {
     747//                        add_edge(getVertex(var, G, M), x, G);
     748//                    }
     749//                }
     750//            }
     751//        }
     752
     753//        // Determine the source variables of the next "layer" of the AST
     754//        flat_set<Statement *> nextSet;
     755//        for (auto u : ordering) {
     756//            if (LLVM_UNLIKELY(in_degree(u, Gk) == 0 && isa<Statement>(Gk[u]))) {
     757//                nextSet.insert(cast<Statement>(Gk[u]));
     758//            } else if (LLVM_UNLIKELY(out_degree(u, Gk) == 0 && isa<Statement>(Gk[u]))) {
     759//                // some input will also be the output of some subgraph of Gk whenever we cut and
     760//                // replicated a vertex. We don't need to reevaluate it as part of the next layer.
     761//                nextSet.erase(cast<Statement>(Gk[u]));
     762//            }
     763//        }
     764
     765//        if (LLVM_UNLIKELY(nextSet.empty())) {
     766//            break;
     767//        }
     768
     769//        out << "----------------------------------------------------------------\n";
     770
     771//        terminals.assign(nextSet.begin(), nextSet.end());
     772//    }
     773
     774
     775
     776//}
    646777
    647778using VertexSet = std::vector<Vertex>;
     
    10281159        }
    10291160
    1030         printGraph(block, H, G, "H0");
    1031 
    10321161        segmentInto3LevelGraph(H);
    10331162
    1034         printGraph(block, H, G, "H1");
    1035 
    10361163        const VertexSets distributionSets = safeDistributionSets(H);
    10371164
    1038         printGraph(block, H, G, "H2");
     1165        printGraph(block, H, G, "H");
    10391166
    10401167        // If no sources remain, no bicliques were found that would have a meaningful impact on the AST.
     
    10881215                add_edge(y, H[t], G);
    10891216            }
     1217            for (const Vertex u : intermediary) {
     1218                if (LLVM_UNLIKELY(in_degree(H[u], G) == 0)) {
     1219                    clear_out_edges(H[u], G);
     1220                }
     1221            }
    10901222        }
    10911223        anyChanges = true;
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/booleanreassociationpass.h

    r4756 r4762  
    2222    void processScopes(PabloBlock & block, std::vector<Statement *> && terminals);
    2323    void processScope(PabloBlock & block, std::vector<Statement *> && terminals);
    24     void summarizeAST(PabloBlock & block, std::vector<Statement *> terminals, Graph & G) const;
     24    void summarizeAST(PabloBlock & block, Graph & G) const;
    2525    bool redistributeAST(PabloBlock & block, Graph & G) const;
    2626private:
  • icGREP/icgrep-devel/icgrep/pablo/printer_pablos.cpp

    r4718 r4762  
    193193    if (expr == nullptr) {
    194194        strm << "<null-expr>";
    195     }
    196     else if (isa<const Zeroes>(expr)) {
     195    } else if (isa<const Zeroes>(expr)) {
    197196        strm << "0";
    198     }
    199     else if (isa<const Ones>(expr)) {
     197    } else if (isa<const Ones>(expr)) {
    200198        strm << "1";
    201     }
    202     else if (const Var * var = dyn_cast<const Var>(expr)) {
     199    } else if (const Var * var = dyn_cast<const Var>(expr)) {
    203200        strm  << var->getName();
    204     }
    205     else if (const Next * next = dyn_cast<const Next>(expr)) {
     201    } else if (const Next * next = dyn_cast<const Next>(expr)) {
    206202        strm << "Next(" << next->getName() << ")";
    207     }
    208     else if (const Statement * stmt = dyn_cast<Statement>(expr)) {
     203    } else if (const If * ifstmt = dyn_cast<If>(expr)) {
     204        strm << "if ";
     205        print(ifstmt->getCondition(), strm);
     206    } else if (const While * whl = dyn_cast<While>(expr)) {
     207        strm << "while ";
     208        print(whl->getCondition(), strm);
     209    } else if (const Statement * stmt = dyn_cast<Statement>(expr)) {
    209210        strm << stmt->getName();
    210     }
    211     else {
     211    } else {
    212212        strm << "**UNKNOWN Pablo Expression type **\n" << "\n";
    213213    }
Note: See TracChangeset for help on using the changeset viewer.