 Timestamp:
 Sep 11, 2015, 8:55:52 AM (4 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

icGREP/icgrepdevel/icgrep/pablo/optimizers/booleanreassociationpass.cpp
r4766 r4767 6 6 #include <boost/graph/filtered_graph.hpp> 7 7 #include <boost/graph/topological_sort.hpp> 8 #include <boost/graph/strong_components.hpp> 8 9 #include <pablo/optimizers/pablo_simplifier.hpp> 9 10 #include <pablo/analysis/pabloverifier.hpp> … … 169 170 **  */ 170 171 static PabloAST * createTree(PabloBlock & block, const PabloAST::ClassTypeId typeId, circular_buffer<PabloAST *> & Q) { 171 assert ( !Q.empty());172 assert (Q.size() > 0); 172 173 while (Q.size() > 1) { 173 174 PabloAST * e1 = Q.front(); Q.pop_front(); 174 // assert (isa<Statement>(e1) ? cast<Statement>(e1)>getParent() != nullptr : true);175 175 PabloAST * e2 = Q.front(); Q.pop_front(); 176 // assert (isa<Statement>(e2) ? cast<Statement>(e2)>getParent() != nullptr : true);177 176 PabloAST * expr = nullptr; 178 177 // Note: this switch ought to compile to an array of function pointers to the appropriate method. … … 188 187 Q.push_back(expr); 189 188 } 190 PabloAST * r = Q.front();189 PabloAST * const expr = Q.front(); 191 190 Q.clear(); 192 return r; 193 } 194 195 /**  * 196 * @brief printGraph 197 **  */ 198 static void printGraph(const PabloBlock & block, const Graph & G, const std::string name) { 199 raw_os_ostream out(std::cerr); 200 out << "digraph " << name << " {\n"; 201 for (auto u : make_iterator_range(vertices(G))) { 202 if (in_degree(u, G) == 0 && out_degree(u, G) == 0) { 203 continue; 204 } 205 out << "v" << u << " [label=\""; 206 PabloAST * expr = G[u]; 207 if (isa<Statement>(expr)) { 208 if (LLVM_UNLIKELY(isa<If>(expr))) { 209 out << "If "; 210 PabloPrinter::print(cast<If>(expr)>getOperand(0), out); 211 out << ":"; 212 } else if (LLVM_UNLIKELY(isa<While>(expr))) { 213 out << "While "; 214 PabloPrinter::print(cast<While>(expr)>getOperand(0), out); 215 out << ":"; 216 } else { 217 PabloPrinter::print(cast<Statement>(expr), "", out); 218 } 219 } else { 220 PabloPrinter::print(expr, out); 221 } 222 out << "\""; 223 if (!inCurrentBlock(expr, block)) { 224 out << " style=dashed"; 225 } 226 out << "];\n"; 227 } 228 for (auto e : make_iterator_range(edges(G))) { 229 out << "v" << source(e, G) << " > v" << target(e, G) << ";\n"; 230 } 231 232 if (num_vertices(G) > 0) { 233 234 out << "{ rank=same;"; 235 for (auto u : make_iterator_range(vertices(G))) { 236 if (in_degree(u, G) == 0 && out_degree(u, G) != 0) { 237 out << " v" << u; 238 } 239 } 240 out << "}\n"; 241 242 out << "{ rank=same;"; 243 for (auto u : make_iterator_range(vertices(G))) { 244 if (out_degree(u, G) == 0 && in_degree(u, G) != 0) { 245 out << " v" << u; 246 } 247 } 248 out << "}\n"; 249 250 } 251 252 out << "}\n\n"; 253 out.flush(); 254 } 255 256 /**  * 257 * @brief printGraph 258 **  */ 259 template<typename SubgraphType> 260 static void printGraph(const PabloBlock & block, const SubgraphType & S, const Graph & G, const std::string name) { 261 raw_os_ostream out(std::cerr); 262 out << "digraph " << name << " {\n"; 263 for (auto u : make_iterator_range(vertices(S))) { 264 if (in_degree(u, S) == 0 && out_degree(u, S) == 0) { 265 continue; 266 } 267 out << "v" << u << " [label=\""; 268 PabloAST * expr = G[S[u]]; 269 if (isa<Statement>(expr)) { 270 if (LLVM_UNLIKELY(isa<If>(expr))) { 271 out << "If "; 272 PabloPrinter::print(cast<If>(expr)>getOperand(0), out); 273 out << ":"; 274 } else if (LLVM_UNLIKELY(isa<While>(expr))) { 275 out << "While "; 276 PabloPrinter::print(cast<While>(expr)>getOperand(0), out); 277 out << ":"; 278 } else { 279 PabloPrinter::print(cast<Statement>(expr), "", out); 280 } 281 } else { 282 PabloPrinter::print(expr, out); 283 } 284 out << "\""; 285 if (!inCurrentBlock(expr, block)) { 286 out << " style=dashed"; 287 } 288 out << "];\n"; 289 } 290 for (auto e : make_iterator_range(edges(S))) { 291 out << "v" << source(e, S) << " > v" << target(e, S) << ";\n"; 292 } 293 294 if (num_vertices(S) > 0) { 295 296 out << "{ rank=same;"; 297 for (auto u : make_iterator_range(vertices(S))) { 298 if (in_degree(u, S) == 0 && out_degree(u, S) != 0) { 299 out << " v" << u; 300 } 301 } 302 out << "}\n"; 303 304 out << "{ rank=same;"; 305 for (auto u : make_iterator_range(vertices(S))) { 306 if (out_degree(u, S) == 0 && in_degree(u, S) != 0) { 307 out << " v" << u; 308 } 309 } 310 out << "}\n"; 311 312 } 313 314 out << "}\n\n"; 315 out.flush(); 191 return expr; 316 192 } 317 193 … … 325 201 redistributeAST(block, G); 326 202 327 raw_os_ostream out(std::cerr);328 PabloPrinter::print(block, "> ", out); // function.getEntryBlock().statements()329 out.flush();330 331 203 circular_buffer<Vertex> Q(num_vertices(G)); 332 204 topological_sort(G, std::front_inserter(Q)); 333 assert (Q.size() == num_vertices(G));334 335 205 circular_buffer<PabloAST *> nodes; 336 206 block.setInsertPoint(nullptr); … … 342 212 if (LLVM_LIKELY(inCurrentBlock(expr, block))) { 343 213 if (isOptimizable(expr)) { 344 if (in_degree(u, G) == 0) { 345 cast<Statement>(expr)>eraseFromParent(false); 346 continue; 347 } else { 214 if (in_degree(u, G) != 0 && out_degree(u, G) != 0) { 348 215 if (LLVM_UNLIKELY(nodes.capacity() < in_degree(u, G))) { 349 216 nodes.set_capacity(in_degree(u, G)); … … 363 230 } 364 231 } 365 366 PabloPrinter::print(block, "< ", out); // function.getEntryBlock().statements()367 out.flush();368 369 232 PabloVerifier::verify(function); 370 233 … … 553 416 **  */ 554 417 template <unsigned side> 555 inline static BicliqueSet && independentCliqueSets(BicliqueSet && cliques ) {418 inline static BicliqueSet && independentCliqueSets(BicliqueSet && cliques, const unsigned minimum) { 556 419 using IndependentSetGraph = adjacency_list<hash_setS, vecS, undirectedS, unsigned>; 557 420 … … 584 447 } 585 448 } 586 if (w == 0) break;449 if (w < minimum) break; 587 450 selected.push_back(u); 588 451 I[u] = 0; … … 634 497 **  */ 635 498 static DistributionSets safeDistributionSets(const PabloBlock & block, const Graph & G, DistributionGraph & H) { 636 637 499 const auto F = makeGraphFacade(H); 638 639 640 DistributionGraph X;641 500 DistributionSets T; 642 643 // printGraph(block, H, G, "H0"); 644 645 BicliqueSet lowerSet = independentCliqueSets<1>(removeUnhelpfulBicliques(enumerateBicliques(F, sinks(H)), G, H)); 646 647 // raw_os_ostream out(std::cerr); 648 501 BicliqueSet lowerSet = independentCliqueSets<1>(removeUnhelpfulBicliques(enumerateBicliques(F, sinks(H)), G, H), 1); 649 502 for (Biclique & lower : lowerSet) { 650 651 // out << "LOWER[0]: "; 652 // for (Vertex u : std::get<0>(lower)) { 653 // PabloPrinter::print(G[H[u]], out); 654 // out << ' '; 655 // } 656 // out << '\n'; 657 658 // out << "LOWER[1]: "; 659 // for (Vertex u : std::get<1>(lower)) { 660 // PabloPrinter::print(G[H[u]], out); 661 // out << ' '; 662 // } 663 // out << '\n'; 664 // out.flush(); 665 666 BicliqueSet upperSet = independentCliqueSets<0>(enumerateBicliques(F, std::get<1>(lower))); 503 BicliqueSet upperSet = independentCliqueSets<0>(enumerateBicliques(F, std::get<1>(lower)), 2); 667 504 for (Biclique & upper : upperSet) { 668 669 // out << " UPPER[0]: ";670 // for (Vertex u : std::get<0>(upper)) {671 // PabloPrinter::print(G[H[u]], out);672 // out << ' ';673 // }674 // out << '\n';675 676 // out << " UPPER[1]: ";677 // for (Vertex u : std::get<1>(upper)) {678 // PabloPrinter::print(G[H[u]], out);679 // out << ' ';680 // }681 // out << '\n';682 // out.flush();683 684 VertexSet sources;685 for (auto u : std::get<1>(upper)) {686 sources.push_back(add_vertex(H[u], X));687 }688 VertexSet sinks;689 for (auto w : std::get<0>(lower)) {690 sinks.push_back(add_vertex(H[w], X));691 }692 693 for (auto v : std::get<0>(upper)) {694 const auto x = add_vertex(H[v], X);695 for (auto u : sources) {696 add_edge(u, x, X);697 }698 for (auto w : sinks) {699 add_edge(x, w, X);700 }701 }702 703 704 505 T.emplace_back(std::move(std::get<1>(upper)), std::move(std::get<0>(upper)), std::get<0>(lower)); 705 506 } 706 507 } 707 708 // printGraph(block, X, G, "H1");709 710 508 return std::move(T); 711 509 } … … 714 512 * @brief generateDistributionGraph 715 513 **  */ 716 void generateDistributionGraph( PabloBlock & block,Graph & G, DistributionGraph & H) {514 void generateDistributionGraph(const PabloBlock & block, const Graph & G, DistributionGraph & H) { 717 515 DistributionMap M; 718 516 for (const Vertex u : make_iterator_range(vertices(G))) { … … 786 584 bool anyChanges = false; 787 585 788 unsigned count = 0;789 790 // printGraph(block, G, "G" + std::to_string(count++));791 792 586 for (;;) { 793 587 … … 819 613 // Eliminate the edges from our original graph G 820 614 for (const Vertex u : intermediary) { 821 const auto uu = H[u]; 615 const auto x = H[u]; 616 assert (G[x]>getClassTypeId() == innerTypeId); 822 617 for (const Vertex s : sources) { 823 assert (edge(H[s], uu, G).second);824 remove_edge(H[s], uu, G);618 assert (edge(H[s], x, G).second); 619 remove_edge(H[s], x, G); 825 620 } 826 621 for (const Vertex t : sinks) { 827 assert (edge(uu, H[t], G).second); 828 remove_edge(uu, H[t], G); 622 assert (edge(x, H[t], G).second); 623 assert (G[H[t]]>getClassTypeId() == outerTypeId); 624 remove_edge(x, H[t], G); 829 625 } 830 626 } … … 837 633 } 838 634 for (const Vertex s : sources) { 839 const Vertex u = H[s]; 840 // If we can merge the sources into this mask, do so. 841 if (LLVM_UNLIKELY(out_degree(u, G) == 0 && G[u]>getClassTypeId() == innerTypeId && inCurrentBlock(cast<Statement>(G[u]), block))) { 842 for (auto e : make_iterator_range(in_edges(u, G))) { 843 add_edge(source(e, G), y, G); 844 } 845 clear_in_edges(u, G); 846 } else { 847 add_edge(u, y, G); 848 } 635 add_edge(H[s], y, G); 849 636 } 850 637 for (const Vertex t : sinks) { … … 853 640 add_edge(x, y, G); 854 641 855 // Now begin transforming the AST 642 643 // Now begin transforming the AST (TODO: fix the abstraction so I can defer creation until the final phase) 856 644 circular_buffer<PabloAST *> Q(std::max(in_degree(x, G), in_degree(y, G))); 857 645 for (auto e : make_iterator_range(in_edges(x, G))) { … … 863 651 } 864 652 G[y] = createTree(block, innerTypeId, Q); 653 654 // Summarize the graph after transforming G 655 std::vector<Vertex> ordering; 656 ordering.reserve(num_vertices(G)); 657 for (const Vertex u : ordering) { 658 if (LLVM_UNLIKELY(out_degree(u, G) == 1 && inCurrentBlock(G[u], block))) { 659 if (isOptimizable(G[u])) { 660 const Vertex v = target(*(out_edges(u, G).first), G); 661 if (LLVM_UNLIKELY(G[v]>getClassTypeId() == G[u]>getClassTypeId())) { 662 for (auto e : make_iterator_range(in_edges(u, G))) { 663 assert (source(e, G) != u); 664 add_edge(source(e, G), v, G); 665 } 666 clear_vertex(u, G); 667 } 668 } 669 } 670 } 865 671 } 866 672 anyChanges = true;
Note: See TracChangeset
for help on using the changeset viewer.