 Timestamp:
 Sep 14, 2015, 3:57:02 PM (4 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

icGREP/icgrepdevel/icgrep/pablo/optimizers/booleanreassociationpass.cpp
r4769 r4770 6 6 #include <boost/graph/filtered_graph.hpp> 7 7 #include <boost/graph/topological_sort.hpp> 8 #include <boost/graph/strong_components.hpp>9 8 #include <pablo/optimizers/pablo_simplifier.hpp> 10 9 #include <pablo/analysis/pabloverifier.hpp> … … 80 79 81 80 inline void add_edge(PabloAST * expr, const Vertex u, const Vertex v, Graph & G) { 81 assert (u != v); 82 82 G[add_edge(u, v, G).first] = expr; 83 83 } … … 180 180 } 181 181 182 183 182 /**  * 184 183 * @brief getVertex … … 200 199 static void printGraph(const PabloBlock & block, const Graph & G, const std::string name) { 201 200 raw_os_ostream out(std::cerr); 201 std::vector<unsigned> visible(num_vertices(G), false); 202 202 out << "digraph " << name << " {\n"; 203 203 for (auto u : make_iterator_range(vertices(G))) { … … 205 205 continue; 206 206 } 207 out << "v" << u << " [label=\""; 207 visible[u] = true; 208 209 out << "v" << u << " [label=\"" << u << ": "; 208 210 PabloAST * expr; 209 211 TypeId typeId; … … 213 215 if (expr == nullptr) { 214 216 temporary = true; 215 out << u << ": ";216 217 switch (typeId) { 217 218 case TypeId::And: … … 229 230 break; 230 231 } 231 } else if ( isa<Statement>(expr)) {232 } else if (G[u].first != TypeId::Var) { 232 233 if (LLVM_UNLIKELY(isa<If>(expr))) { 233 234 out << "If "; … … 245 246 } 246 247 out << "\""; 247 if ( BooleanReassociationPass::isMutable(G[u], block) == false) {248 if (!BooleanReassociationPass::isMutable(G[u], block)) { 248 249 out << " style=dashed"; 249 250 } … … 256 257 } 257 258 for (auto e : make_iterator_range(edges(G))) { 258 out << "v" << source(e, G) << " > v" << target(e, G); 259 if (visible[source(e, G)] && visible[target(e, G)]) { 260 out << "v" << source(e, G) << " > v" << target(e, G); 261 } 259 262 if (G[e]) { 260 263 out << " [label=\""; … … 269 272 out << "{ rank=same;"; 270 273 for (auto u : make_iterator_range(vertices(G))) { 271 if ( in_degree(u, G) == 0 && out_degree(u, G) != 0) {274 if (visible[u] && in_degree(u, G) == 0 && out_degree(u, G) != 0) { 272 275 out << " v" << u; 273 276 } … … 277 280 out << "{ rank=same;"; 278 281 for (auto u : make_iterator_range(vertices(G))) { 279 if ( out_degree(u, G) == 0 && in_degree(u, G) != 0) {282 if (visible[u] && out_degree(u, G) == 0 && in_degree(u, G) != 0) { 280 283 out << " v" << u; 281 284 } … … 292 295 * @brief createTree 293 296 **  */ 294 static Statement* createTree(PabloBlock & block, const Vertex u, Graph & G) {295 circular_buffer<PabloAST *> Q(in_degree(u, G));297 static PabloAST * createTree(PabloBlock & block, const Vertex u, Graph & G) { 298 flat_set<PabloAST *> sources; 296 299 for (const auto e : make_iterator_range(in_edges(u, G))) { 297 300 PabloAST * expr = G[source(e, G)].second; 298 assert (expr); 299 assert (std::find(Q.begin(), Q.end(), expr) == Q.end()); 300 Q.push_back(expr); 301 } 302 assert (Q.size() > 1); 301 assert ("G contains a null input variable!" && (expr != nullptr)); 302 sources.insert(expr); 303 } 304 circular_buffer<PabloAST *> Q(sources.begin(), sources.end()); 303 305 const TypeId typeId = G[u].first; 304 306 while (Q.size() > 1) { … … 318 320 Q.push_back(expr); 319 321 } 320 Statement * const result = cast<Statement>(Q.front()); 322 PabloAST * const result = Q.front(); 323 assert (result); 321 324 G[u].second = result; 322 325 return result; … … 329 332 Graph G; 330 333 331 raw_os_ostream out(std::cerr);332 out << "============================================================\n";333 PabloPrinter::print(function.getEntryBlock().statements(), out);334 out << "\n";335 out.flush();334 // raw_os_ostream out(std::cerr); 335 // out << "============================================================\n"; 336 // PabloPrinter::print(block.statements(), " > ", out); 337 // out << "\n"; 338 // out.flush(); 336 339 337 340 summarizeAST(block, G); … … 345 348 const Vertex u = Q.back(); Q.pop_back(); 346 349 if (LLVM_LIKELY(isMutable(G[u], block))) { 347 out << "Mutable: " << u << ": "; 348 PabloPrinter::print(G[u].second, out); 349 out.flush(); 350 // out << "Mutable: " << u << ": "; 351 // PabloPrinter::print(G[u].second, out); 352 // out << '\n'; 353 // out.flush(); 350 354 Statement * stmt = nullptr; 351 355 if (isOptimizable(G[u])) { 352 stmt = createTree(block, u, G); 356 PabloAST * replacement = createTree(block, u, G); 357 if (LLVM_LIKELY(inCurrentBlock(replacement, block))) { 358 stmt = cast<Statement>(replacement); 359 } else { // optimization reduced this to a Constant, Var or an outerscope statement 360 continue; 361 } 353 362 } else { // update any potential mappings 354 363 stmt = cast<Statement>(G[u].second); 355 364 } 356 365 assert (stmt); 357 PabloPrinter::print(stmt, " > ", out); 358 out << '\n'; 359 out.flush(); 360 assert (stmt>getParent() == &block); 366 assert (inCurrentBlock(stmt, block)); 361 367 for (auto e : make_iterator_range(out_edges(u, G))) { 362 368 if (G[e] && G[e] != stmt) { … … 371 377 } 372 378 373 Simplifier::deadCodeElimination(function.getEntryBlock());374 375 out << "\n";376 PabloPrinter::print(function.getEntryBlock().statements(), out);377 out.flush();378 379 PabloVerifier::verify(function);379 // Simplifier::deadCodeElimination(block); 380 381 // out << "\n"; 382 // PabloPrinter::print(block.statements(), " < ", out); 383 // out.flush(); 384 385 // PabloVerifier::verify(function); 380 386 } 381 387 … … 531 537 } 532 538 } 533 534 // Test whether any operation has (A op2 B) op1 (Â¬A op3 C) contained within it, where op1, op2 and op3 are all535 // optimizable operations; if so, modify G to reflect the result. The main goal is to optimize the underlying536 // equations but this also eliminates a problematic case in which the internal boolean simplification logic537 // could detect the contradiction and return an unexpected value.538 539 // VertexSet inputs;540 // VertexSets lit;541 // VertexSets neg;542 // for (const Vertex t : reverse_topological_ordering) {543 // if (isOptimizable(G[t])) {544 // for (auto e : make_iterator_range(in_edges(t, G))) {545 // const Vertex u = source(e, G);546 // if (isOptimizable(G[u])) {547 // inputs.push_back(u);548 // }549 // }550 // if (inputs.size() > 1) {551 // unsigned count = 0;552 553 // for (const Vertex u : inputs) {554 // lit[count].clear();555 // neg[count].clear();556 // for (auto ei : make_iterator_range(in_edges(u, G))) {557 // const Vertex w = source(ei, G);558 // if (isOptimizable(G[w])) {559 // lit[count].push_back(w);560 // } else if (LLVM_UNLIKELY(isNegated(G[w]))) {561 // assert (in_degree(w, G) > 0);562 // neg[count].push_back(source(first(in_edges(w, G)), G));563 // }564 // }565 // std::sort(lit[count].begin(), lit[count].end());566 // std::sort(neg[count].begin(), neg[count].end());567 // ++count;568 // }569 570 571 // for (unsigned i = 0; i != count; ++i) {572 // for (unsigned j = 0; j != count; ++j) {573 // VertexSet cap;574 // std::set_intersection(lit[i].begin(), lit[i].end(), neg[j].begin(), neg[j].end(), std::back_inserter(cap));575 576 577 // }578 // }579 580 581 582 // }583 // inputs.clear();584 // }585 // }586 539 } 587 540 … … 842 795 void BooleanReassociationPass::redistributeAST(const PabloBlock & block, Graph & G) const { 843 796 844 printGraph(block, G, "G0");845 846 unsigned count = 0;797 // printGraph(block, G, "G0"); 798 799 // unsigned count = 0; 847 800 848 801 std::vector<Vertex> mapping(num_vertices(G) + 16); … … 866 819 } 867 820 868 raw_os_ostream out(std::cerr); 869 out << "DISTRIBUTION SETS: " << distributionSets.size() << '\n'; 870 871 ++count; 872 873 unsigned subcount = 0; 874 875 821 // raw_os_ostream out(std::cerr); 822 // out << "DISTRIBUTION SETS: " << distributionSets.size() << '\n'; 823 824 // ++count; 825 826 // unsigned subcount = 0; 876 827 877 828 for (const DistributionSet & set : distributionSets) { … … 882 833 const VertexSet & sinks = std::get<2>(set); 883 834 884 out << "SOURCES:";885 for (const Vertex u : sources) {886 const Vertex x = mapping[H[u]];887 out << " " << x << ": "; PabloPrinter::print(G[x].second, out);888 }889 out << "\n";890 out << "INTERMEDIARY:";891 for (const Vertex u : intermediary) {892 const Vertex x = mapping[H[u]];893 out << " " << x << ": "; PabloPrinter::print(G[x].second, out);894 }895 out << "\n";896 out << "SINKS:";897 for (const Vertex u : sinks) {898 const Vertex x = mapping[H[u]];899 out << " " << x << ": "; PabloPrinter::print(G[x].second, out);900 }901 out << "\n";902 out.flush();835 // out << "SOURCES:"; 836 // for (const Vertex u : sources) { 837 // const Vertex x = mapping[H[u]]; 838 // out << " " << x << ": "; PabloPrinter::print(G[x].second, out); 839 // } 840 // out << "\n"; 841 // out << "INTERMEDIARY:"; 842 // for (const Vertex u : intermediary) { 843 // const Vertex x = mapping[H[u]]; 844 // out << " " << x << ": "; PabloPrinter::print(G[x].second, out); 845 // } 846 // out << "\n"; 847 // out << "SINKS:"; 848 // for (const Vertex u : sinks) { 849 // const Vertex x = mapping[H[u]]; 850 // out << " " << x << ": "; PabloPrinter::print(G[x].second, out); 851 // } 852 // out << "\n"; 853 // out.flush(); 903 854 904 855 const TypeId outerTypeId = G[mapping[H[sinks.front()]]].first; … … 921 872 for (auto e : make_iterator_range(out_edges(u, G))) { 922 873 if (target(e, G) == v) { 874 assert (u != v); 923 875 remove_edge(e, G); 924 876 } … … 934 886 for (auto e : make_iterator_range(out_edges(u, G))) { 935 887 if (target(e, G) == v) { 888 assert (u != v); 936 889 remove_edge(e, G); 937 890 } … … 950 903 summarizeGraph(G, mapping); 951 904 952 printGraph(block, G, "G" + std::to_string(count) + "_" + std::to_string(++subcount));953 } 954 } 955 } 956 957 } 905 // printGraph(block, G, "G" + std::to_string(count) + "_" + std::to_string(++subcount)); 906 } 907 } 908 } 909 910 }
Note: See TracChangeset
for help on using the changeset viewer.