Ignore:
Timestamp:
Aug 29, 2015, 4:50:32 PM (4 years ago)
Author:
nmedfort
Message:

Temporary check in

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

Legend:

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

    r4748 r4751  
    33#include <boost/container/flat_map.hpp>
    44#include <boost/circular_buffer.hpp>
    5 #include <pablo/builder.hpp>
    65#include <boost/graph/adjacency_list.hpp>
    76#include <boost/graph/topological_sort.hpp>
     7#include <pablo/optimizers/pablo_simplifier.hpp>
    88#include <queue>
     9#include <iostream>
     10#include <pablo/printer_pablos.h>
     11
    912
    1013using namespace boost;
     
    1316namespace pablo {
    1417
     18using Graph = adjacency_list<hash_setS, vecS, bidirectionalS, PabloAST *>;
     19using Vertex = Graph::vertex_descriptor;
     20using VertexQueue = circular_buffer<Vertex>;
     21using Map = std::unordered_map<PabloAST *, Vertex>;
     22using EdgeQueue = std::queue<std::pair<Vertex, Vertex>>;
     23
     24static void summarizeAST(PabloBlock & block, std::vector<Statement *> && terminals, Graph & G);
     25
     26/** ------------------------------------------------------------------------------------------------------------- *
     27 * @brief optimize
     28 ** ------------------------------------------------------------------------------------------------------------- */
    1529bool BooleanReassociationPass::optimize(PabloFunction & function) {
    1630    BooleanReassociationPass brp;
     31//    raw_os_ostream out(std::cerr);
     32//    out << "BEFORE:\n\n";
     33//    PabloPrinter::print(function.getEntryBlock().statements(), out);
    1734    brp.scan(function);
     35    Simplifier::optimize(function);
     36
     37//    out << "\n\nAFTER:\n\n";
     38//    PabloPrinter::print(function.getEntryBlock().statements(), out);
    1839    return true;
    1940}
     
    2344 ** ------------------------------------------------------------------------------------------------------------- */
    2445void BooleanReassociationPass::scan(PabloFunction & function) {
    25     Terminals terminals;
     46    std::vector<Statement *> terminals;
    2647    for (unsigned i = 0; i != function.getNumOfResults(); ++i) {
    2748        terminals.push_back(function.getResult(i));
     
    3152
    3253/** ------------------------------------------------------------------------------------------------------------- *
     54 * @brief scan
     55 ** ------------------------------------------------------------------------------------------------------------- */
     56void BooleanReassociationPass::scan(PabloBlock & block, std::vector<Statement *> && terminals) {
     57
     58    processScope(block, std::move(terminals));
     59
     60    for (Statement * stmt : block) {
     61        if (isa<If>(stmt)) {
     62            const auto & defs = cast<const If>(stmt)->getDefined();
     63            std::vector<Statement *> terminals(defs.begin(), defs.end());
     64            scan(cast<If>(stmt)->getBody(), std::move(terminals));
     65        } else if (isa<While>(stmt)) {
     66            const auto & vars = cast<const While>(stmt)->getVariants();
     67            std::vector<Statement *> terminals(vars.begin(), vars.end());
     68            scan(cast<While>(stmt)->getBody(), std::move(terminals));
     69        }
     70    }
     71
     72}
     73
     74/** ------------------------------------------------------------------------------------------------------------- *
    3375 * @brief is_power_of_2
    3476 * @param n an integer
     
    4688
    4789/** ------------------------------------------------------------------------------------------------------------- *
    48  * @brief isACD
    49  ** ------------------------------------------------------------------------------------------------------------- */
    50 static inline bool isaBooleanOperation(const PabloAST * const expr) {
     90 * @brief isOptimizable
     91 *
     92 * And, Or and Xor instructions are all associative, commutative and distributive operations. Thus we can
     93 * safely rearrange expressions such as "((((a √ b) √ c) √ d) √ e) √ f" into "((a √ b) √ (c √ d)) √ (e √ f)".
     94 ** ------------------------------------------------------------------------------------------------------------- */
     95static inline bool isOptimizable(const PabloAST * const expr) {
    5196    assert (expr);
    5297    switch (expr->getClassTypeId()) {
     
    60105}
    61106
    62 using Graph = adjacency_list<hash_setS, vecS, bidirectionalS, PabloAST *>;
    63 using Vertex = Graph::vertex_descriptor;
    64 using VertexQueue = circular_buffer<Vertex>;
     107/** ------------------------------------------------------------------------------------------------------------- *
     108 * @brief inCurrentBlock
     109 ** ------------------------------------------------------------------------------------------------------------- */
     110static inline bool inCurrentBlock(const Statement * stmt, const PabloBlock & block) {
     111    return stmt->getParent() == &block;
     112}
     113
     114static inline bool inCurrentBlock(const PabloAST * expr, const PabloBlock & block) {
     115    return isa<Statement>(expr) && inCurrentBlock(cast<Statement>(expr), block);
     116}
    65117
    66118/** ------------------------------------------------------------------------------------------------------------- *
     
    100152
    101153/** ------------------------------------------------------------------------------------------------------------- *
    102  * @brief scan
    103  ** ------------------------------------------------------------------------------------------------------------- */
    104 void BooleanReassociationPass::scan(PabloBlock & block, Terminals && terminals) {
    105 
    106     using Map = std::unordered_map<PabloAST *, Vertex>;
    107     using EdgeQueue = std::queue<std::pair<Vertex, Vertex>>;
    108 
    109     for (Statement * stmt : block) {
    110         if (isa<If>(stmt)) {
    111             const auto & defs = cast<const If>(stmt)->getDefined();
    112             Terminals terminals(defs.begin(), defs.end());
    113             scan(cast<If>(stmt)->getBody(), std::move(terminals));
    114         } else if (isa<While>(stmt)) {
    115             const auto & vars = cast<const While>(stmt)->getVariants();
    116             Terminals terminals(vars.begin(), vars.end());
    117             scan(cast<While>(stmt)->getBody(), std::move(terminals));
    118         }
    119     }
    120 
    121     // And, Or and Xor instructions are all associative, commutative and distributive operations. Thus we can
    122     // safely rearrange expressions such as "((((a √ b) √ c) √ d) √ e) √ f" into "((a √ b) √ (c √ d)) √ (e √ f)".
    123 
     154 * @brief getVertex
     155 ** ------------------------------------------------------------------------------------------------------------- */
     156static inline Vertex getVertex(PabloAST * expr, Graph & G, Map & M) {
     157    const auto f = M.find(expr);
     158    if (f != M.end()) {
     159        return f->second;
     160    }
     161    const auto u = add_vertex(expr, G);
     162    M.insert(std::make_pair(expr, u));
     163    return u;
     164}
     165
     166/** ------------------------------------------------------------------------------------------------------------- *
     167 * @brief createTree
     168 ** ------------------------------------------------------------------------------------------------------------- */
     169static PabloAST * createTree(PabloBlock & block, const PabloAST::ClassTypeId typeId, circular_buffer<PabloAST *> & Q) {
     170    while (Q.size() > 1) {
     171        PabloAST * e1 = Q.front(); Q.pop_front();
     172        PabloAST * e2 = Q.front(); Q.pop_front();
     173        PabloAST * expr = nullptr;
     174        switch (typeId) {
     175            case PabloAST::ClassTypeId::And:
     176                expr = block.createAnd(e1, e2); break;
     177            case PabloAST::ClassTypeId::Or:
     178                expr = block.createOr(e1, e2); break;
     179            case PabloAST::ClassTypeId::Xor:
     180                expr = block.createXor(e1, e2); break;
     181            default: break;
     182        }
     183        Q.push_back(expr);
     184    }
     185    PabloAST * r = Q.front();
     186    Q.clear();
     187    return r;
     188}
     189
     190/** ------------------------------------------------------------------------------------------------------------- *
     191 * @brief applyDistributionLaw
     192 ** ------------------------------------------------------------------------------------------------------------- */
     193static bool applyDistributionLaw(PabloBlock & block, const PabloAST::ClassTypeId typeId, flat_set<PabloAST *> & vars) {
     194    circular_buffer<PabloAST *> Q0(vars.size());
     195    circular_buffer<PabloAST *> Q1(vars.size());
     196    std::vector<PabloAST *> distributedVars;
     197
     198    for (auto vi = vars.begin(); vi != vars.end(); ) {
     199        PabloAST * const e0 = *vi;
     200
     201        if (e0->getClassTypeId() == typeId) {
     202            Statement * const s0 = cast<Statement>(e0);
     203
     204            for (auto vj = vi + 1; vj != vars.end(); ) {
     205                PabloAST * const e1 = *vj;
     206
     207                if (e1->getClassTypeId() == typeId) {
     208                    Statement * const s1 = cast<Statement>(e1);
     209                    bool distributed = false;
     210
     211                    if (s0->getOperand(0) == s1->getOperand(0)) {
     212                        Q0.push_back(s1->getOperand(1));
     213                        distributed = true;
     214                    } else if (s0->getOperand(0) == s1->getOperand(1)) {
     215                        Q0.push_back(s1->getOperand(0));
     216                        distributed = true;
     217                    }
     218
     219                    if (s0->getOperand(1) == s1->getOperand(0)) {
     220                        Q1.push_back(s1->getOperand(1));
     221                        distributed = true;
     222                    } else if (s0->getOperand(1) == s1->getOperand(1)) {
     223                        Q1.push_back(s1->getOperand(0));
     224                        distributed = true;
     225                    }
     226
     227                    if (distributed) {
     228                        vj = vars.erase(vj);
     229                        continue;
     230                    }
     231                }
     232
     233                ++vj;
     234            }
     235
     236            if (LLVM_UNLIKELY(Q0.size() > 0 || Q1.size() > 0)) {
     237                const PabloAST::ClassTypeId innerTypeId =
     238                        (typeId == PabloAST::ClassTypeId::Or) ? PabloAST::ClassTypeId::And : PabloAST::ClassTypeId::Or;
     239
     240                vi = vars.erase(vi);
     241                if (Q0.size() > 0) {
     242                    Q0.push_back(s0->getOperand(1));
     243                    PabloAST * distributed = createTree(block, innerTypeId, Q0);
     244                    switch (typeId) {
     245                        case PabloAST::ClassTypeId::And:
     246                            distributed = block.createAnd(s0->getOperand(0), distributed); break;
     247                        case PabloAST::ClassTypeId::Or:
     248                            distributed = block.createOr(s0->getOperand(0), distributed); break;
     249                        default: break;
     250                    }
     251                    distributedVars.push_back(distributed);
     252                }
     253                if (Q1.size() > 0) {
     254                    Q1.push_front(s0->getOperand(0));
     255                    PabloAST * distributed = createTree(block, innerTypeId, Q1);
     256                    switch (typeId) {
     257                        case PabloAST::ClassTypeId::And:
     258                            distributed = block.createAnd(s0->getOperand(1), distributed); break;
     259                        case PabloAST::ClassTypeId::Or:
     260                            distributed = block.createOr(s0->getOperand(1), distributed); break;
     261                        default: break;
     262                    }
     263                    distributedVars.push_back(distributed);
     264                }
     265                continue;
     266            }
     267        }
     268        ++vi;
     269    }
     270    if (distributedVars.empty()) {
     271        return false;
     272    }
     273    for (PabloAST * var : distributedVars) {
     274        vars.insert(var);
     275    }
     276    return true;
     277}
     278
     279/** ------------------------------------------------------------------------------------------------------------- *
     280 * @brief processScope
     281 ** ------------------------------------------------------------------------------------------------------------- */
     282void BooleanReassociationPass::processScope(PabloBlock & block, std::vector<Statement *> && terminals) {
     283
     284    Graph G;
     285    summarizeAST(block, std::move(terminals), G);
     286
     287    raw_os_ostream out(std::cerr);
     288    out << "digraph G {\n";
     289    for (auto u : make_iterator_range(vertices(G))) {
     290        out << "v" << u << " [label=\"";
     291        if (in_degree(u, G) > 0) {
     292            PabloPrinter::print(cast<Statement>(G[u]), "", out);
     293        } else {
     294            PabloPrinter::print(G[u], out);
     295        }
     296        out << "\"];\n";
     297    }
     298    for (auto e : make_iterator_range(edges(G))) {
     299        out << "v" << source(e, G) << " -> v" << target(e, G) << ";\n";
     300    }
     301    out << "}\n\n";
     302    out.flush();
     303
     304
     305
     306
     307
     308}
     309
     310/** ------------------------------------------------------------------------------------------------------------- *
     311 * @brief summarizeAST
     312 *
     313 * This function scans through a basic block (starting by its terminals) and computes a DAG in which any sequences
     314 * of AND, OR or XOR functions are "flattened" and allowed to have any number of inputs. This allows us to
     315 * reassociate them in the most efficient way possible.
     316 ** ------------------------------------------------------------------------------------------------------------- */
     317static void summarizeAST(PabloBlock & block, std::vector<Statement *> && terminals, Graph & G) {
     318
     319    Map M;
    124320    VertexQueue Q(128);
     321    EdgeQueue E;
    125322
    126323    for (;;) {
    127324
    128         Graph G;
    129         Map M;
     325        Graph Gk;
     326        Map Mk;
    130327
    131328        // Generate a graph depicting the relationships between the terminals. If the original terminals
     
    133330        // be optimized, they'll be left as the initial terminals for the next "layer" of the AST.
    134331
    135         for (Statement * const term : terminals) {
    136             assert (term);
    137             if (isaBooleanOperation(term)) {
    138                 if (LLVM_LIKELY(M.count(term) == 0)) {                   
    139                     const Vertex v = add_vertex(term, G);
    140                     assert (v < num_vertices(G));
    141                     M.insert(std::make_pair(term, v));
    142                     push(v, Q);
    143                 }
    144             } else {
     332        for (Statement * term : terminals) {
     333            if (LLVM_LIKELY(Mk.count(term) == 0)) {
     334                // add or find this terminal in our global graph
     335                Vertex x = getVertex(term, G, M);
     336
     337                if (isOptimizable(term)) {
     338                    const Vertex u = add_vertex(term, Gk);
     339                    Mk.insert(std::make_pair(term, u));
     340                    push(u, Q);
     341                    continue;
     342                } else if ((isa<Assign>(term) || isa<Next>(term)) && !inCurrentBlock(term->getOperand(0), block)) {
     343                    // If this is an Assign (Next) node whose operand does not originate from the current block
     344                    // then check to see if there is an If (While) node that does.
     345                    Statement * branch = nullptr;
     346                    if (isa<Assign>(term)) {
     347                        for (PabloAST * user : term->users()) {
     348                            if (isa<If>(user)) {
     349                                const If * ifNode = cast<If>(user);
     350                                const auto & defs = ifNode->getDefined();
     351                                if (LLVM_LIKELY(std::find(defs.begin(), defs.end(), cast<Assign>(term)) != defs.end())) {
     352                                    if (inCurrentBlock(ifNode, block)) {
     353                                        branch = cast<Statement>(user);
     354                                    }
     355                                    break;
     356                                }
     357                            }
     358                        }
     359                    } else { // if (isa<Next>(term))
     360                        for (PabloAST * user : term->users()) {
     361                            if (isa<While>(user)) {
     362                                const While * whileNode = cast<While>(user);
     363                                const auto & vars = whileNode->getVariants();
     364                                if (LLVM_LIKELY(std::find(vars.begin(), vars.end(), cast<Next>(term)) != vars.end())) {
     365                                    if (inCurrentBlock(whileNode, block)) {
     366                                        branch = cast<Statement>(user);
     367                                    }
     368                                    break;
     369                                }
     370                            }
     371                        }
     372                    }
     373
     374                    // If we didn't find a branch, then the Assign (Next) node must have come from a preceeding
     375                    // block. Just skip it for now.
     376                    if (branch == nullptr) {
     377                        continue;
     378                    }
     379
     380                    // Otherwise add the branch to G and test its operands rather than the original terminal
     381                    const Vertex z = getVertex(branch, G, M);
     382                    add_edge(x, z, G);
     383                    x = z;
     384                    term = branch;
     385                }
     386
    145387                for (unsigned i = 0; i != term->getNumOperands(); ++i) {
    146388                    PabloAST * const op = term->getOperand(i);
    147                     assert (op);
    148                     if (LLVM_LIKELY(isa<Statement>(op) && M.count(op) == 0)) {
    149                         const Vertex v = add_vertex(op, G);
    150                         assert (v < num_vertices(G));
    151                         M.insert(std::make_pair(op, v));
     389                    const Vertex y = getVertex(op, G, M);
     390                    add_edge(x, y, G);
     391                    if (LLVM_LIKELY(in_degree(y, G) == 0 && Mk.count(op) == 0 && isa<Statement>(op))) {
     392                        const Vertex v = add_vertex(op, Gk);
     393                        Mk.insert(std::make_pair(op, v));
    152394                        push(v, Q);
    153395                    }
    154396                }
    155             }           
     397
     398            }
    156399        }
    157400
     
    162405        for (;;) {
    163406            const Vertex u = pop(Q);
    164             assert (u < num_vertices(G));
    165             if (isaBooleanOperation(G[u])) {
     407            if (isOptimizable(Gk[u])) {
    166408                // Scan through the use-def chains to locate any chains of rearrangable expressions and their inputs
    167                 Statement * stmt = cast<Statement>(G[u]);
     409                Statement * stmt = cast<Statement>(Gk[u]);
    168410                for (unsigned i = 0; i != 2; ++i) {
    169411                    PabloAST * op = stmt->getOperand(i);
    170                     auto f = M.find(op);
    171                     if (f == M.end()) {
    172                         const Vertex v = add_vertex(op, G);
    173                         assert (v < num_vertices(G));
    174                         f = M.insert(std::make_pair(op, v)).first;
     412                    auto f = Mk.find(op);
     413                    if (f == Mk.end()) {
     414                        const Vertex v = add_vertex(op, Gk);
     415                        f = Mk.insert(std::make_pair(op, v)).first;
    175416                        if (op->getClassTypeId() == stmt->getClassTypeId() && cast<Statement>(op)->getParent() == &block) {
    176417                            push(v, Q);
    177418                        }
    178419                    }
    179                     add_edge(f->second, u, G);
     420                    add_edge(f->second, u, Gk);
    180421                }
    181422            }
     
    188429        // another terminal, we need to make sure we compute it as an independent subexpression.
    189430        std::vector<unsigned> ordering;
    190         ordering.reserve(num_vertices(G));
    191         topological_sort(G, std::back_inserter(ordering));
    192         std::vector<unsigned> component(num_vertices(G));
     431        ordering.reserve(num_vertices(Gk));
     432        topological_sort(Gk, std::back_inserter(ordering));
     433        std::vector<unsigned> component(num_vertices(Gk));
    193434
    194435        for (;;) {
     
    199440                unsigned id = 0;
    200441                // If this is a sink in G, it is the root of a new component.
    201                 if (out_degree(u, G) == 0) {
     442                if (out_degree(u, Gk) == 0) {
    202443                    id = ++components;
    203444                } else {
    204                     for (auto e : make_iterator_range(out_edges(u, G))) {
    205                         id = std::max(id, component[target(e, G)]);
     445                    for (auto e : make_iterator_range(out_edges(u, Gk))) {
     446                        id = std::max(id, component[target(e, Gk)]);
    206447                    }
    207448                }
     
    212453            // Cut the graph wherever a computation crosses a component or whenever we need to cut the graph because
    213454            // the instructions corresponding to the pair of nodes differs.
    214             EdgeQueue E;
    215455            graph_traits<Graph>::edge_iterator ei, ei_end;
    216             for (std::tie(ei, ei_end) = edges(G); ei != ei_end; ) {
     456            for (std::tie(ei, ei_end) = edges(Gk); ei != ei_end; ) {
    217457                const Graph::edge_descriptor e = *ei++;
    218                 const Vertex u = source(e, G);
    219                 const Vertex v = target(e, G);
    220                 if (LLVM_UNLIKELY(isCutNecessary(u, v, G, component))) {
     458                const Vertex u = source(e, Gk);
     459                const Vertex v = target(e, Gk);
     460                if (LLVM_UNLIKELY(isCutNecessary(u, v, Gk, component))) {
    221461                    E.push(std::make_pair(u, v));
    222                     remove_edge(u, v, G);
     462                    remove_edge(u, v, Gk);
    223463                }
    224464            }
     
    243483
    244484                // Replicate u and fix the ordering and component vectors to reflect the change in G.
    245                 Vertex w = add_vertex(G[u], G);
     485                Vertex w = add_vertex(Gk[u], Gk);
    246486                ordering.insert(std::find(ordering.begin(), ordering.end(), u), w);
    247487                assert (component.size() == w);
    248488                component.push_back(component[v]);
    249                 add_edge(w, v, G);
     489                add_edge(w, v, Gk);
    250490
    251491                // However, after we do so, we need to make sure the original source vertex will be a
     
    253493                // extraneous isolated vertex. Otherwise, we need to make further cuts and replications.
    254494
    255                 if (in_degree(u, G) != 0) {
    256                     for (auto e : make_iterator_range(out_edges(u, G))) {
    257                         E.push(std::make_pair(source(e, G), target(e, G)));
    258                     }
    259                     clear_out_edges(u, G);
     495                if (in_degree(u, Gk) != 0) {
     496                    for (auto e : make_iterator_range(out_edges(u, Gk))) {
     497                        E.push(std::make_pair(source(e, Gk), target(e, Gk)));
     498                    }
     499                    clear_out_edges(u, Gk);
    260500                }
    261501
     
    263503                    break;
    264504                }
    265 
    266             }
    267         }
    268 
    269         // Scan through the graph in reverse order so that we find all subexpressions first
     505            }
     506        }
     507
     508        // Scan through the graph so that we process the outermost expressions first
    270509        for (const Vertex u : ordering) {
    271             if (out_degree(u, G) == 0 && in_degree(u, G) != 0) {
    272 
    273                 // While we're collecting our variable set V, keep track of the maximum path length L.
    274                 // If L == ceil(log2(|V|)), then this portion of the AST is already optimal.
    275 
    276                 flat_map<Vertex, unsigned> L;
    277                 flat_set<PabloAST *> V;
    278 
    279                 Vertex v = u;
    280                 unsigned maxPathLength = 0;
    281                 L.emplace(v, 0);
    282                 for (;;) {                   
    283                     if (in_degree(v, G) == 0) {
    284                         V.insert(G[v]);
    285                     } else {
    286                         const auto l = L[v] + 1;
    287                         maxPathLength = std::max(maxPathLength, l);
    288                         for (auto e : make_iterator_range(in_edges(v, G))) {
    289                             const Vertex w = source(e, G);
    290                             auto f = L.find(w);
    291                             if (LLVM_LIKELY(f == L.end())) {
    292                                 L.emplace(w, l);
    293                             } else {
    294                                 f->second = std::max(f->second, l);
     510            if (LLVM_UNLIKELY(out_degree(u, Gk) == 0)) {
     511                const Vertex x = getVertex(Gk[u], G, M);
     512                if (LLVM_LIKELY(in_degree(u, Gk) != 0)) {
     513                    flat_set<PabloAST *> vars;
     514                    flat_set<Vertex> visited;
     515                    for (Vertex v = u;;) {
     516                        if (in_degree(v, Gk) == 0) {
     517                            vars.insert(Gk[v]);
     518                        } else {
     519                            for (auto e : make_iterator_range(in_edges(v, Gk))) {
     520                                const Vertex w = source(e, Gk);
     521                                if (LLVM_LIKELY(visited.insert(w).second)) {
     522                                    push(w, Q);
     523                                }
    295524                            }
    296                             push(w, Q);
    297525                        }
    298                     }
    299                     if (Q.empty()) {
    300                         break;
    301                     }
    302                     v = pop(Q);
    303                 }
    304 
    305                 // Should we optimize this portion of the AST?
    306                 if (maxPathLength > ceil_log2(V.size())) {
    307 
    308                     Statement * stmt = cast<Statement>(G[u]);
    309 
    310                     circular_buffer<PabloAST *> Q(V.size());
    311                     for (PabloAST * var : V) {
    312                         Q.push_back(var);
    313                     }
    314 
    315                     block.setInsertPoint(stmt->getPrevNode());
    316                     if (isa<And>(stmt)) {
    317                         while (Q.size() > 1) {
    318                             PabloAST * e1 = Q.front(); Q.pop_front();
    319                             PabloAST * e2 = Q.front(); Q.pop_front();
    320                             Q.push_back(block.createAnd(e1, e2));
     526                        if (Q.empty()) {
     527                            break;
    321528                        }
    322                     } else if (isa<Or>(stmt)) {
    323                         while (Q.size() > 1) {
    324                             PabloAST * e1 = Q.front(); Q.pop_front();
    325                             PabloAST * e2 = Q.front(); Q.pop_front();
    326                             Q.push_back(block.createOr(e1, e2));
    327                         }
    328                     } else { assert(isa<Xor>(stmt));
    329                         while (Q.size() > 1) {
    330                             PabloAST * e1 = Q.front(); Q.pop_front();
    331                             PabloAST * e2 = Q.front(); Q.pop_front();
    332                             Q.push_back(block.createXor(e1, e2));
    333                         }
    334                     }
    335                     stmt->replaceWith(Q.front(), true, true);
     529                        v = pop(Q);
     530                    }
     531                    for (PabloAST * var : vars) {
     532                        add_edge(x, getVertex(var, G, M), G);
     533                    }
    336534                }
    337535            }
     
    341539        flat_set<Statement *> nextSet;
    342540        for (auto u : ordering) {
    343             if (in_degree(u, G) == 0) {
    344                 PabloAST * const var = G[u];
    345                 if (LLVM_LIKELY(isa<Statement>(var) && cast<Statement>(var)->getParent() == &block)) {
     541            if (in_degree(u, Gk) == 0) {
     542                PabloAST * const var = Gk[u];
     543                if (LLVM_LIKELY(inCurrentBlock(var, block))) {
    346544                    nextSet.insert(cast<Statement>(var));
    347545                }
    348             } else if (out_degree(u, G) == 0) { // an input may also be the output of some subgraph of G. We don't need to reevaluate it.
    349                 PabloAST * const var = G[u];
    350                 if (LLVM_LIKELY(isa<Statement>(var) && cast<Statement>(var)->getParent() == &block)) {
     546            } else if (out_degree(u, Gk) == 0) { // an input may also be the output of a subgraph of G. We don't need to reevaluate it.
     547                PabloAST * const var = Gk[u];
     548                if (LLVM_LIKELY(inCurrentBlock(var, block))) {
    351549                    nextSet.erase(cast<Statement>(var));
    352550                }
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/booleanreassociationpass.h

    r4748 r4751  
    77
    88class BooleanReassociationPass {   
    9     using Terminals = std::vector<Statement *>;
    109public:
    1110    static bool optimize(PabloFunction & function);
     
    1312    BooleanReassociationPass();
    1413    void scan(PabloFunction & function);
    15     void scan(PabloBlock & block, Terminals && terminals);
     14    void scan(PabloBlock & block, std::vector<Statement *> && terminals);
     15    void processScope(PabloBlock & block, std::vector<Statement *> && terminals);
    1616};
    1717
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.cpp

    r4748 r4751  
    388388    // Map our operands to the computed BDDs
    389389    std::array<DdNode *, 3> input;
    390     unsigned count = 0;
    391     for (; count != stmt->getNumOperands(); ++count) {
    392         PabloAST * const op = stmt->getOperand(count);
     390    for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
     391        PabloAST * const op = stmt->getOperand(i);
    393392        if (LLVM_UNLIKELY(isa<Integer>(op) || isa<String>(op))) {
    394393            continue;
     
    398397            std::string tmp;
    399398            llvm::raw_string_ostream msg(tmp);
    400             msg << "Uncharacterized operand " << std::to_string(count);
     399            msg << "AutoMultiplexing: Uncharacterized operand " << std::to_string(i);
    401400            PabloPrinter::print(stmt, " of ", msg);
    402401            throw std::runtime_error(msg.str());
    403402        }
    404         input[count] = f->second;
     403        input[i] = f->second;
    405404    }
    406405
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_bddminimization.cpp

    r4748 r4751  
    156156        auto f = mCharacterizationMap.find(op);
    157157        if (LLVM_UNLIKELY(f == mCharacterizationMap.end())) {
    158             throw std::runtime_error("BDDMinimizationPass: attempted to characterize statement with unknown operand!");
     158            std::string tmp;
     159            llvm::raw_string_ostream msg(tmp);
     160            msg << "BDDMinimizationPass: uncharacterized operand " << std::to_string(i);
     161            PabloPrinter::print(stmt, " of ", msg);
     162            throw std::runtime_error(msg.str());
    159163        }
    160164        input[i] = f->second;
Note: See TracChangeset for help on using the changeset viewer.