Changeset 4862
- Timestamp:
- Nov 7, 2015, 3:57:52 PM (3 years ago)
- Location:
- icGREP/icgrep-devel/icgrep/pablo/optimizers
- Files:
-
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
icGREP/icgrep-devel/icgrep/pablo/optimizers/booleanreassociationpass.cpp
r4861 r4862 4 4 #include <boost/circular_buffer.hpp> 5 5 #include <boost/graph/adjacency_list.hpp> 6 #include <boost/graph/filtered_graph.hpp>7 6 #include <boost/graph/topological_sort.hpp> 8 7 #include <pablo/optimizers/pablo_simplifier.hpp> … … 10 9 #include <algorithm> 11 10 #include <numeric> // std::iota 12 #include <queue>13 #include <set>14 #include <pablo/printer_pablos.h>15 #include <iostream>16 #include <llvm/Support/raw_os_ostream.h>17 #include <boost/graph/strong_components.hpp>18 11 19 12 using namespace boost; … … 159 152 } 160 153 161 ///** ------------------------------------------------------------------------------------------------------------- *162 // * @brief printGraph163 // ** ------------------------------------------------------------------------------------------------------------- */164 //static void printGraph(const Graph & G, const std::string name, raw_ostream & out) {165 166 // std::vector<unsigned> c(num_vertices(G));167 // strong_components(G, make_iterator_property_map(c.begin(), get(vertex_index, G), c[0]));168 169 // out << "digraph " << name << " {\n";170 // for (auto u : make_iterator_range(vertices(G))) {171 // if (in_degree(u, G) == 0 && out_degree(u, G) == 0) {172 // continue;173 // }174 // out << "v" << u << " [label=\"" << u << ": ";175 // PabloAST * expr;176 // TypeId typeId;177 // std::tie(typeId, expr) = G[u];178 // bool temporary = false;179 // bool error = false;180 // if (expr == nullptr) {181 // temporary = true;182 // switch (typeId) {183 // case TypeId::And:184 // out << "And";185 // break;186 // case TypeId::Or:187 // out << "Or";188 // break;189 // case TypeId::Xor:190 // out << "Xor";191 // break;192 // default:193 // out << "???";194 // error = true;195 // break;196 // }197 // } else if (isMutable(G[u])) {198 // if (LLVM_UNLIKELY(isa<If>(expr))) {199 // out << "If ";200 // PabloPrinter::print(cast<If>(expr)->getOperand(0), out);201 // out << ":";202 // } else if (LLVM_UNLIKELY(isa<While>(expr))) {203 // out << "While ";204 // PabloPrinter::print(cast<While>(expr)->getOperand(0), out);205 // out << ":";206 // } else {207 // PabloPrinter::print(cast<Statement>(expr), "", out);208 // }209 // } else {210 // PabloPrinter::print(expr, out);211 // }212 // out << "\"";213 // if (!isMutable(G[u])) {214 // out << " style=dashed";215 // }216 // if (error) {217 // out << " color=red";218 // } else if (temporary) {219 // out << " color=blue";220 // }221 // out << "];\n";222 // }223 // for (auto e : make_iterator_range(edges(G))) {224 // const auto s = source(e, G);225 // const auto t = target(e, G);226 // out << "v" << s << " -> v" << t;227 // bool cyclic = (c[s] == c[t]);228 // if (G[e] || cyclic) {229 // out << " [";230 // if (G[e]) {231 // out << "label=\"";232 // PabloPrinter::print(G[e], out);233 // out << "\" ";234 // }235 // if (cyclic) {236 // out << "color=red ";237 // }238 // out << "]";239 // }240 // out << ";\n";241 // }242 243 // if (num_vertices(G) > 0) {244 245 // out << "{ rank=same;";246 // for (auto u : make_iterator_range(vertices(G))) {247 // if (in_degree(u, G) == 0 && out_degree(u, G) != 0) {248 // out << " v" << u;249 // }250 // }251 // out << "}\n";252 253 // out << "{ rank=same;";254 // for (auto u : make_iterator_range(vertices(G))) {255 // if (out_degree(u, G) == 0 && in_degree(u, G) != 0) {256 // out << " v" << u;257 // }258 // }259 // out << "}\n";260 261 // }262 263 // out << "}\n\n";264 // out.flush();265 //}266 267 154 /** ------------------------------------------------------------------------------------------------------------- * 268 155 * @brief optimize … … 363 250 // if expr is not a statement, it's always reachable 364 251 if (isa<Statement>(expr)) { 365 const PabloBlock * constparent = cast<Statement>(expr)->getParent();252 const PabloBlock * parent = cast<Statement>(expr)->getParent(); 366 253 // if expr is in the current block, it's not reachable at the entry point of this block 367 254 if (parent == &block) { … … 369 256 } 370 257 const PabloBlock * current = block.getParent(); 371 // if we can find expr in a preceeding block, it's reachable 372 while (current) { 258 // If expr is an Assign or Next node, it must escape its block (presuming the Simplifier has eliminated any 259 // unnecessary Assign or Next nodes.) We'll want to test whether the parent of its block is an ancestor of 260 // the current block. 261 if (isa<Assign>(expr) || isa<Next>(expr)) { 262 parent = parent->getParent(); 263 } 264 // If we can find expr in a preceeding block, it's reachable 265 for (;;) { 373 266 if (parent == current) { 374 267 return true; 268 } 269 if (current == nullptr) { 270 break; 375 271 } 376 272 current = current->getParent(); … … 525 421 for (const Vertex u : make_iterator_range(vertices(G))) { 526 422 if (in_degree(u, G) == 0 && out_degree(u, G) != 0) { 423 527 424 readySet.emplace_back(ordering[u], u); 528 425 } … … 576 473 Vertex u; unsigned weight; 577 474 std::tie(weight, u) = *chosen; 578 readySet.erase(chosen); 579 475 readySet.erase(chosen); 580 476 PabloAST * expr = getValue(G[u]); 581 477 … … 583 479 584 480 if (LLVM_LIKELY(isMutable(G[u]))) { 585 Statement * stmt = nullptr;586 481 if (isAssociative(G[u])) { 587 PabloAST * replacement = createTree(block, u, G); 588 if (LLVM_LIKELY(inCurrentBlock(replacement, block))) { 589 stmt = cast<Statement>(replacement); 590 } else { // optimization reduced this to a Constant, Var or a prior-scope statement 591 getType(G[u]) = TypeId::Var; 592 goto check_ready; 593 } 594 } else { // update any potential mappings 595 stmt = cast<Statement>(expr); 596 } 597 assert (stmt); 482 expr = createTree(block, u, G); 483 } 484 assert (expr); 598 485 for (auto e : make_iterator_range(out_edges(u, G))) { 599 if (G[e] && G[e] != stmt) {486 if (G[e] && G[e] != expr) { 600 487 if (PabloAST * user = getValue(G[target(e, G)])) { 601 cast<Statement>(user)->replaceUsesOfWith(G[e], stmt);488 cast<Statement>(user)->replaceUsesOfWith(G[e], expr); 602 489 } 603 490 } 604 491 } 605 492 // Make sure that optimization doesn't reduce this to an already written statement 606 if (stmt->getParent() == nullptr) { 607 block.insert(stmt); 608 } 609 expr = stmt; 610 } 611 check_ready: 493 if (LLVM_LIKELY(isa<Statement>(expr) && cast<Statement>(expr)->getParent() == nullptr)) { 494 block.insert(cast<Statement>(expr)); 495 } 496 } 497 612 498 // mark this instruction as written 613 499 ordering[u] = 0; … … 626 512 if (ready) { 627 513 auto entry = std::make_pair(ordering[v], v); 628 auto li = std::lower_bound(readySet.begin(), readySet.end(), entry, readyComparator); 629 while (li != readySet.end()) { 630 auto next = li + 1; 631 if (next == readySet.end() || std::get<0>(*next) == ordering[v]) { 632 li = next; 633 continue; 634 } 635 break; 636 } 637 readySet.insert(li, entry); 514 auto position = std::lower_bound(readySet.begin(), readySet.end(), entry, readyComparator); 515 readySet.insert(position, entry); 516 assert (std::is_sorted(readySet.cbegin(), readySet.cend(), readyComparator)); 638 517 } 639 518 } -
icGREP/icgrep-devel/icgrep/pablo/optimizers/booleanreassociationpass.h
r4861 r4862 14 14 using Vertex = Graph::vertex_descriptor; 15 15 using Map = std::unordered_map<const PabloAST *, Vertex>; 16 using WrittenAt = boost::container::flat_map<const PabloAST *, unsigned>;17 16 using ScopeMap = boost::container::flat_map<const PabloBlock *, Statement *>; 18 17 static bool optimize(PabloFunction & function);
Note: See TracChangeset
for help on using the changeset viewer.