Ignore:
Timestamp:
Aug 22, 2015, 1:53:05 PM (4 years ago)
Author:
nmedfort
Message:

More work on the boolean reassociation pass.

File:
1 edited

Legend:

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

    r4736 r4738  
    2121}
    2222
     23/** ------------------------------------------------------------------------------------------------------------- *
     24 * @brief scan
     25 ** ------------------------------------------------------------------------------------------------------------- */
    2326void BooleanReassociationPass::scan(PabloFunction & function) {
    2427    Terminals terminals;
     
    2932}
    3033
     34/** ------------------------------------------------------------------------------------------------------------- *
     35 * @brief is_power_of_2
     36 * @param n an integer
     37 ** ------------------------------------------------------------------------------------------------------------- */
     38static inline bool is_power_of_2(const size_t n) {
     39    return ((n & (n - 1)) == 0);
     40}
     41
     42/** ------------------------------------------------------------------------------------------------------------- *
     43 * @brief log2_plus_one
     44 ** ------------------------------------------------------------------------------------------------------------- */
     45static inline size_t ceil_log2(const size_t n) {
     46    return std::log2<size_t>(n) + (is_power_of_2(n) ? 1 : 0);
     47}
     48
     49/** ------------------------------------------------------------------------------------------------------------- *
     50 * @brief scan
     51 ** ------------------------------------------------------------------------------------------------------------- */
    3152void BooleanReassociationPass::scan(PabloBlock & block, Terminals && terminals) {
    3253
     
    3455    using Vertex = Graph::vertex_descriptor;
    3556    using Map = std::unordered_map<PabloAST *, Vertex>;
    36     using Queue = std::queue<Vertex>;
     57    using VertexQueue = std::queue<Vertex>;
     58    using EdgeQueue = std::queue<std::pair<Vertex, Vertex>>;
    3759
    3860    for (Statement * stmt : block) {
     
    79101                    f = M.insert(std::make_pair(var, v)).first;
    80102                    if ((isa<And>(var) || isa<Or>(var) || isa<Xor>(var))) {
    81                         Queue Q;
     103                        VertexQueue Q;
    82104                        // Scan through the use-def chains to locate any chains of rearrangable expressions and their inputs
    83105                        for (Statement * stmt = cast<Statement>(var); ;) {
     
    111133        std::vector<unsigned> component(num_vertices(G));
    112134
    113         for (unsigned i = 0; ;) {
     135        // unsigned i = 0;
     136
     137        for (;;) {
    114138
    115139            // Mark which computation component these vertices are in based on their topological (occurence) order.
     
    117141            for (auto u : ordering) {
    118142                unsigned id = 0;
    119                 if (out_degree(u, G) == 0) {
     143                // If this one of our original terminals or a sink in G, it is the root of a new component.
     144                if (u < terminals.size() || out_degree(u, G) == 0) {
    120145                    id = ++count;
    121146                } else {
     
    130155            if (count > 1) {
    131156
    132                 if (i++ == 0) {
    133 
    134                     out << "digraph G_" << i << " {\n";
    135                     unsigned i = 0;
    136                     for (auto u : ordering) {
    137                         out << "u" << u << " [label=\"";
    138                         out << i++ << " : ";
    139                         PabloPrinter::print(G[u], out);
    140                         out << " (" << component[u] << ')';
    141                         out << "\"];\n";
    142                     }
    143                     for (auto e : make_iterator_range(edges(G))) {
    144                         out << "u" << source(e, G) << " -> u" << target(e, G) << ";\n";
    145                     }
    146                     out << "}\n";
    147                     out.flush();
    148 
    149                     out << "*************************************************\n";
    150 
    151                 }
    152 
    153                 // Cut the graph wherever a computation is crosses a component
    154                 std::queue<std::pair<Vertex, Vertex>> Q;
     157//                if (i++ == 0) {
     158
     159//                    out << "digraph G_" << i << " {\n";
     160//                    unsigned i = 0;
     161//                    for (auto u : ordering) {
     162//                        out << "u" << u << " [label=\"";
     163//                        out << i++ << " : ";
     164//                        PabloPrinter::print(G[u], out);
     165//                        out << " (" << component[u] << ')';
     166//                        out << "\"];\n";
     167//                    }
     168//                    for (auto e : make_iterator_range(edges(G))) {
     169//                        out << "u" << source(e, G) << " -> u" << target(e, G) << ";\n";
     170//                    }
     171//                    out << "}\n";
     172//                    out.flush();
     173
     174//                    out << "*************************************************\n";
     175
     176//                }
     177
     178                // Cut the graph wherever a computation crosses a component
     179                EdgeQueue Q;
    155180                graph_traits<Graph>::edge_iterator ei, ei_end;
    156181
     
    176201
    177202                    // The vertex belonging to a component with a greater number must come "earlier"
    178                     // in the program. Thus it must be computed first.
     203                    // in the program. By replicating it, this ensures it's computed as an output of
     204                    // one component and used as an input of another.
    179205
    180206                    if (component[u] < component[v]) {
     
    182208                    }
    183209
    184                     out << " -- replicating ";
    185                     PabloPrinter::print(G[u], out);
    186                     out << " for component " << component[v] << '\n';
    187                     out.flush();
     210//                    out << " -- replicating ";
     211//                    PabloPrinter::print(G[u], out);
     212//                    out << " for component " << component[v] << '\n';
     213//                    out.flush();
    188214
    189215                    // Replicate u and fix the ordering and component vectors to reflect the change in G.
     
    211237                }
    212238
    213                 out << "*************************************************\n";
     239//                out << "*************************************************\n";
    214240
    215241                continue; // outer for loop
     
    233259        out.flush();
    234260
    235 
    236         // Determine the source variables in this portion of the AST
    237         flat_set<PabloAST *> variables;
    238 
    239         for (auto u : make_iterator_range(vertices(G))) {
     261        // Scan through the graph in reverse order so that we find all subexpressions first
     262        for (auto ui = ordering.rbegin(), ui_end = ordering.rend(); ui != ui_end; ++ui) {
     263            const Vertex u = *ui;
     264            if (out_degree(u, G) == 0 && in_degree(u, G) != 0) {
     265
     266                PabloAST * expr = G[u];
     267
     268
     269                std::array<Vertex, 3> root;
     270                unsigned count = 0;
     271
     272                if (isa<And>(expr) || isa<Or>(expr) || isa<Xor>(expr)) {
     273                    root[count++] = u;
     274                } else {
     275                    for (auto e : make_iterator_range(in_edges(u, G))) {
     276                        root[count++] = source(e, G);
     277                    }
     278                }
     279
     280                for (unsigned i = 0; i != count; ++i) {
     281                    // While we're collecting our variable set V, keep track of the maximum path length L.
     282                    // If L == ceil(log2(|V|)), then this portion of the AST is already optimal.
     283
     284                    flat_map<Vertex, unsigned> L;
     285                    flat_set<PabloAST *> V;
     286                    VertexQueue Q;
     287
     288                    Vertex v = root[i];
     289                    unsigned maxPathLength = 0;
     290                    L.emplace(v, 0);
     291                    for (;;) {
     292                        if (in_degree(v, G) == 0) {
     293                            V.insert(G[v]);
     294                        } else {
     295                            const auto l = L[v] + 1;
     296                            maxPathLength = std::max(maxPathLength, l);
     297                            for (auto e : make_iterator_range(in_edges(v, G))) {
     298                                const Vertex w = source(e, G);
     299                                auto f = L.find(w);
     300                                if (LLVM_LIKELY(f == L.end())) {
     301                                    L.emplace(w, l);
     302                                } else {
     303                                    f->second = std::max(f->second, l);
     304                                }
     305                                Q.push(w);
     306                            }
     307                        }
     308                        if (Q.empty()) {
     309                            break;
     310                        }
     311                        v = Q.front();
     312                        Q.pop();
     313                    }
     314
     315                    // Should we optimize this portion of the AST?
     316                    if (maxPathLength != ceil_log2(V.size())) {
     317
     318
     319
     320                    }
     321
     322
     323                }
     324
     325
     326
     327
     328
     329            }
     330        }
     331
     332        // if (u < terminals.size() || out_degree(u, G) == 0) {
     333
     334        for (auto e : make_iterator_range(edges(G))) {
     335            Vertex u = target(e, G);
     336            Vertex v = source(e, G);
     337            if (u >= terminals.size() && out_degree(v, G) != 0 && G[u]->getClassTypeId() != G[v]->getClassTypeId()) {
     338                throw std::runtime_error("Illegal graph generated!");
     339            }
     340        }
     341
     342        // Determine the source variables of the next "layer" of the AST
     343        flat_set<Statement *> nextSet;
     344        for (auto u : ordering) {
    240345            if (in_degree(u, G) == 0) {
    241                 variables.insert(G[u]);
    242             }
    243         }
    244 
    245         terminals.clear();
    246         for (PabloAST * var : variables) {
    247             if (isa<Statement>(var) && cast<Statement>(var)->getParent() == &block) {
    248                 terminals.push_back(cast<Statement>(var));
    249             }
    250         }
    251 
    252         if (terminals.empty()) {
     346                PabloAST * const var = G[u];
     347                if (LLVM_LIKELY(isa<Statement>(var) && cast<Statement>(var)->getParent() == &block)) {
     348                    nextSet.insert(cast<Statement>(var));
     349                }
     350            } 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.
     351                PabloAST * const var = G[u];
     352                if (LLVM_LIKELY(isa<Statement>(var) && cast<Statement>(var)->getParent() == &block)) {
     353                    nextSet.erase(cast<Statement>(var));
     354                }
     355            }
     356        }
     357
     358        if (nextSet.empty()) {
    253359            break;
    254360        }
     361
     362        terminals.assign(nextSet.begin(), nextSet.end());
    255363
    256364        out << "-------------------------------------------------\n";
Note: See TracChangeset for help on using the changeset viewer.