Changeset 4744


Ignore:
Timestamp:
Aug 23, 2015, 2:27:12 PM (4 years ago)
Author:
nmedfort
Message:

Temporary check in

File:
1 edited

Legend:

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

    r4741 r4744  
    2929        terminals.push_back(function.getResult(i));
    3030    }
    31     scan(function.getEntryBlock(), std::move(terminals));
     31    return scan(function.getEntryBlock(), std::move(terminals));
    3232}
    3333
     
    6868 ** ------------------------------------------------------------------------------------------------------------- */
    6969static inline bool isCutNecessary(const Vertex u, const Vertex v, const Graph & G, const std::vector<unsigned> & component) {
     70    // Either this edge crosses a component boundary or the operations performed by the vertices differs, we need to cut
     71    // the graph here and generate two partial equations.
    7072    if (LLVM_UNLIKELY(component[u] != component[v])) {
    7173        return true;
     
    7779
    7880/** ------------------------------------------------------------------------------------------------------------- *
    79  * @brief isCutNecessary
    80  ** ------------------------------------------------------------------------------------------------------------- */
    81 static bool print(const Graph & G, const std::vector<unsigned> & component, raw_os_ostream & out) {
    82     bool hasError = false;
    83     out << "digraph G {\n";
    84     unsigned i = 0;
    85     for (auto u : make_iterator_range(vertices(G))) {
    86         out << "u" << u << " [label=\"";
    87         out << i++ << " : ";
    88         PabloPrinter::print(G[u], out);
    89         out << " (" << component[u] << ')';
    90         out << "\"";
    91         if (isaBooleanOperation(G[u]) && (in_degree(u, G) == 1 || in_degree(u, G) > 2)) {
    92             out << " color=red";
    93             hasError = true;
    94         }
    95         out << "];\n";
    96     }
    97     for (auto e : make_iterator_range(edges(G))) {
    98         Vertex u = source(e, G);
    99         Vertex v = target(e, G);
    100         out << "u" << u << " -> u" << v;
    101         if (isCutNecessary(u, v, G, component)) {
    102             out << " [color=red]";
    103             hasError = true;
    104         }
    105         out << ";\n";
    106     }
    107     out << "}\n";
    108     out.flush();
    109     return hasError;
    110 }
    111 
    112 /** ------------------------------------------------------------------------------------------------------------- *
    11381 * @brief scan
    11482 ** ------------------------------------------------------------------------------------------------------------- */
     
    11886    using VertexQueue = std::queue<Vertex>;
    11987    using EdgeQueue = std::queue<std::pair<Vertex, Vertex>>;
     88
     89    PabloBuilder builder(block);
    12090
    12191    for (Statement * stmt : block) {
     
    12898            Terminals terminals(vars.begin(), vars.end());
    12999            scan(cast<While>(stmt)->getBody(), std::move(terminals));
     100        } else {
     101            builder.record(stmt);
    130102        }
    131103    }
     
    134106    // safely rearrange expressions such as "((((a √ b) √ c) √ d) √ e) √ f" into "((a √ b) √ (c √ d)) √ (e √ f)".
    135107
    136     raw_os_ostream out(std::cerr);
    137 
    138     out << "=================================================\n";
    139 
    140     PabloBuilder builder(block);
     108    bool modifiedAST = false;
    141109
    142110    for (;;) {
     
    167135                }
    168136            }
    169 
    170137        }
    171138
     
    194161
    195162        // Generate a topological ordering for G; if one of our terminals happens to also be a partial computation of
    196         // another terminal, we need to make sure we compute it.
     163        // another terminal, we need to make sure we compute it as an independent subexpression.
    197164        std::vector<unsigned> ordering;
    198165        ordering.reserve(num_vertices(G));
     
    203170
    204171            // Mark which computation component these vertices are in based on their topological (occurence) order.
    205             unsigned count = 0;
     172            unsigned components = 0;
    206173            for (auto u : ordering) {
    207174                unsigned id = 0;
    208                 // If this one of our original terminals or a sink in G, it is the root of a new component.
     175                // If this is a sink in G, it is the root of a new component.
    209176                if (out_degree(u, G) == 0) {
    210                     id = ++count;
     177                    id = ++components;
    211178                } else {
    212179                    for (auto e : make_iterator_range(out_edges(u, G))) {
     
    218185            }
    219186
    220             if (count > 1) {
    221                 // Cut the graph wherever a computation crosses a component
    222                 EdgeQueue Q;
    223                 graph_traits<Graph>::edge_iterator ei, ei_end;
    224 
    225                 for (std::tie(ei, ei_end) = edges(G); ei != ei_end; ) {
    226                     const Graph::edge_descriptor e = *ei++;
    227                     const Vertex u = source(e, G);
    228                     const Vertex v = target(e, G);
    229                     if (LLVM_UNLIKELY(isCutNecessary(u, v, G, component))) {
    230                         Q.push(std::make_pair(u, v));
    231                         remove_edge(u, v, G);
    232                     }
    233                 }
    234 
    235                 // If no edges cross a component, we're done.
     187            // Cut the graph wherever a computation crosses a component or whenever we need to cut the graph because
     188            // the instructions corresponding to the pair of nodes differs.
     189            EdgeQueue Q;
     190            graph_traits<Graph>::edge_iterator ei, ei_end;
     191
     192            for (std::tie(ei, ei_end) = edges(G); ei != ei_end; ) {
     193                const Graph::edge_descriptor e = *ei++;
     194                const Vertex u = source(e, G);
     195                const Vertex v = target(e, G);
     196                if (LLVM_UNLIKELY(isCutNecessary(u, v, G, component))) {
     197                    Q.push(std::make_pair(u, v));
     198                    remove_edge(u, v, G);
     199                }
     200            }
     201
     202            // If no cuts are necessary, we're done.
     203            if (Q.empty()) {
     204                break;
     205            }
     206
     207            for (;;) {
     208
     209                Vertex u, v;
     210                std::tie(u, v) = Q.front(); Q.pop();
     211
     212                // The vertex belonging to a component with a greater number must come "earlier"
     213                // in the program. By replicating it, this ensures it's computed as an output of
     214                // one component and used as an input of another.
     215
     216                if (component[u] < component[v]) {
     217                    std::swap(u, v);
     218                }
     219
     220                // Replicate u and fix the ordering and component vectors to reflect the change in G.
     221                Vertex w = add_vertex(G[u], G);
     222                ordering.insert(std::find(ordering.begin(), ordering.end(), u), w);
     223                assert (component.size() == w);
     224                component.push_back(component[v]);
     225                add_edge(w, v, G);
     226
     227                // However, after we do so, we need to make sure the original source vertex will be a
     228                // sink in G unless it is also an input variable (in which case we'd simply end up with
     229                // extraneous isolated vertex. Otherwise, we need to make further cuts and replications.
     230
     231                if (in_degree(u, G) != 0) {
     232                    for (auto e : make_iterator_range(out_edges(u, G))) {
     233                        Q.push(std::make_pair(source(e, G), target(e, G)));
     234                    }
     235                    clear_out_edges(u, G);
     236                }
     237
    236238                if (Q.empty()) {
    237                     break; // outer for loop
    238                 }
    239 
    240                 for (;;) {
    241 
    242                     Vertex u, v;
    243                     std::tie(u, v) = Q.front(); Q.pop();
    244 
    245                     // The vertex belonging to a component with a greater number must come "earlier"
    246                     // in the program. By replicating it, this ensures it's computed as an output of
    247                     // one component and used as an input of another.
    248 
    249                     if (component[u] < component[v]) {
    250                         std::swap(u, v);
    251                     }
    252 
    253                     // Replicate u and fix the ordering and component vectors to reflect the change in G.
    254                     Vertex w = add_vertex(G[u], G);
    255                     ordering.insert(std::find(ordering.begin(), ordering.end(), u), w);
    256                     assert (component.size() == w);
    257                     component.push_back(component[v]);
    258                     add_edge(w, v, G);
    259 
    260                     // However, after we do so, we need to make sure the original source vertex will be a
    261                     // sink in G unless it is also an input variable (in which case we'd simply end up with
    262                     // extraneous isolated vertex. Otherwise, we need to make further cuts and replications.
    263 
    264                     if (in_degree(u, G) != 0) {
    265                         for (auto e : make_iterator_range(out_edges(u, G))) {
    266                             Q.push(std::make_pair(source(e, G), target(e, G)));
    267                         }
    268                         clear_out_edges(u, G);
    269                     }
    270 
    271                     if (Q.empty()) {
    272                         break;
    273                     }
    274 
    275                 }
    276                 continue; // outer for loop
    277             }
    278             break; // outer for loop
    279         }
    280 
    281         if (print(G, component, out)) {
    282             PabloPrinter::print(block.statements(), out);
    283             out.flush();
    284             throw std::runtime_error("Illegal graph generated!");
     239                    break;
     240                }
     241
     242            }
    285243        }
    286244
    287245        // Scan through the graph in reverse order so that we find all subexpressions first
    288         for (auto ui = ordering.begin(); ui != ordering.end(); ++ui) {
    289             const Vertex u = *ui;
     246        for (const Vertex u : ordering) {
    290247            if (out_degree(u, G) == 0 && in_degree(u, G) != 0) {
    291 
    292                 out << " -- checking component " << component[u] << " : ";
    293                 PabloPrinter::print(G[u], out);
    294                 out << "\n";
    295                 out.flush();
    296248
    297249                // While we're collecting our variable set V, keep track of the maximum path length L.
     
    305257                unsigned maxPathLength = 0;
    306258                L.emplace(v, 0);
    307                 for (;;) {
    308                     assert (isa<Statement>(G[v]) ? cast<Statement>(G[v])->getParent() != nullptr : true);
     259                for (;;) {                   
    309260                    if (in_degree(v, G) == 0) {
    310261                        V.insert(G[v]);
     
    332283                // Should we optimize this portion of the AST?
    333284                if (maxPathLength > ceil_log2(V.size())) {
    334 
    335                     out << " -- rewriting component " << component[u] << " : |P|=" << maxPathLength << ", |V|=" << V.size() << " (" << ceil_log2(V.size()) << ")\n";
    336                     out.flush();
    337 
     285                    Statement * stmt = cast<Statement>(G[u]);
    338286                    circular_buffer<PabloAST *> Q(V.size());
    339287                    for (PabloAST * var : V) {
    340288                        Q.push_back(var);
    341289                    }
    342                     Statement * stmt = cast<Statement>(G[u]);
    343290
    344291                    block.setInsertPoint(stmt->getPrevNode());
     
    355302                            Q.push_back(builder.createOr(e1, e2));
    356303                        }
    357                     } else { // if (isa<Xor>(stmt)) {
     304                    } else { assert(isa<Xor>(stmt));
    358305                        while (Q.size() > 1) {
    359306                            PabloAST * e1 = Q.front(); Q.pop_front();
     
    362309                        }
    363310                    }
    364                     stmt->replaceWith(Q.front(), true, true);
    365                 }
    366 
    367                 for (auto uj = ui; ++uj != ordering.end(); ) {
    368                     assert (isa<Statement>(G[*uj]) ? cast<Statement>(G[*uj])->getParent() != nullptr : true);
    369                 }
    370 
     311                    stmt->replaceAllUsesWith(Q.front());
     312                    modifiedAST = true;
     313                }
    371314            }
    372315        }
     
    393336
    394337        terminals.assign(nextSet.begin(), nextSet.end());
    395 
    396         out << "-------------------------------------------------\n";
     338    }
     339
     340    // If we modified the AST, we likely left dead code in it. Go through and remove any from this block.
     341    if (modifiedAST) {
     342        Statement * stmt = block.front();
     343        while (stmt) {
     344            if (stmt->getNumUses() == 0 && !(isa<If>(stmt) || isa<While>(stmt))){
     345                stmt = stmt->eraseFromParent(true);
     346            } else {
     347                stmt = stmt->getNextNode();
     348            }
     349        }
    397350    }
    398351}
Note: See TracChangeset for help on using the changeset viewer.