 Timestamp:
 Sep 10, 2015, 4:38:24 PM (4 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

icGREP/icgrepdevel/icgrep/pablo/optimizers/booleanreassociationpass.cpp
r4765 r4766 7 7 #include <boost/graph/topological_sort.hpp> 8 8 #include <pablo/optimizers/pablo_simplifier.hpp> 9 #include <pablo/analysis/pabloverifier.hpp> 9 10 #include <algorithm> 10 11 #include <queue> … … 56 57 } 57 58 59 template <class Graph> 60 static VertexSet sinks(const Graph & G) { 61 VertexSet V; 62 for (const Vertex u : make_iterator_range(vertices(G))) { 63 if (out_degree(u, G) == 0) { 64 V.push_back(u); 65 } 66 } 67 std::sort(V.begin(), V.end()); 68 return std::move(V); 69 } 70 58 71 /**  * 59 72 * @brief optimize … … 92 105 **  */ 93 106 inline void BooleanReassociationPass::processScopes(PabloFunction & function) { 94 processScopes(function .getEntryBlock());107 processScopes(function, function.getEntryBlock()); 95 108 } 96 109 … … 98 111 * @brief processScopes 99 112 **  */ 100 void BooleanReassociationPass::processScopes(Pablo Block & block) {113 void BooleanReassociationPass::processScopes(PabloFunction & function, PabloBlock & block) { 101 114 for (Statement * stmt : block) { 102 115 if (isa<If>(stmt)) { 103 processScopes( cast<If>(stmt)>getBody());116 processScopes(function, cast<If>(stmt)>getBody()); 104 117 } else if (isa<While>(stmt)) { 105 processScopes( cast<While>(stmt)>getBody());106 } 107 } 108 processScope( block);118 processScopes(function, cast<While>(stmt)>getBody()); 119 } 120 } 121 processScope(function, block); 109 122 } 110 123 … … 183 196 * @brief printGraph 184 197 **  */ 185 static void printGraph( PabloBlock & block, const Graph & G, const std::string name) {198 static void printGraph(const PabloBlock & block, const Graph & G, const std::string name) { 186 199 raw_os_ostream out(std::cerr); 187 200 out << "digraph " << name << " {\n"; … … 245 258 **  */ 246 259 template<typename SubgraphType> 247 static void printGraph( PabloBlock & block, const SubgraphType & S, const Graph & G, const std::string name) {260 static void printGraph(const PabloBlock & block, const SubgraphType & S, const Graph & G, const std::string name) { 248 261 raw_os_ostream out(std::cerr); 249 262 out << "digraph " << name << " {\n"; … … 306 319 * @brief processScope 307 320 **  */ 308 inline void BooleanReassociationPass::processScope(Pablo Block & block) {321 inline void BooleanReassociationPass::processScope(PabloFunction & function, PabloBlock & block) { 309 322 Graph G; 310 323 311 324 summarizeAST(block, G); 312 325 redistributeAST(block, G); 326 327 raw_os_ostream out(std::cerr); 328 PabloPrinter::print(block, "> ", out); // function.getEntryBlock().statements() 329 out.flush(); 313 330 314 331 circular_buffer<Vertex> Q(num_vertices(G)); … … 347 364 } 348 365 366 PabloPrinter::print(block, "< ", out); // function.getEntryBlock().statements() 367 out.flush(); 368 369 PabloVerifier::verify(function); 370 349 371 } 350 372 … … 456 478 } 457 479 458 IntersectionSets B(B1 .begin(), B1.end());480 IntersectionSets B(B1); 459 481 460 482 IntersectionSets Bi; … … 496 518 cliques.reserve(B.size()); 497 519 for (auto Bi = B.begin(); Bi != B.end(); ++Bi) { 498 // Compute our A set 499 auto bi = Bi>begin(); 500 VertexSet Ai = outgoingVertexSet(*bi, G); 501 while (++bi != Bi>end()) { 502 VertexSet Aj = outgoingVertexSet(*bi, G); 520 VertexSet Ai(A); 521 for (const Vertex u : *Bi) { 522 VertexSet Aj = outgoingVertexSet(u, G); 503 523 VertexSet Ak; 504 524 std::set_intersection(Ai.begin(), Ai.end(), Aj.begin(), Aj.end(), std::back_inserter(Ak)); … … 507 527 cliques.emplace_back(std::move(Ai), std::move(*Bi)); 508 528 } 509 510 529 return std::move(cliques); 511 530 } 512 531 513 532 /**  * 514 * @brief safeDistributionSets 515 **  */ 516 static DistributionSets safeDistributionSets(DistributionGraph & H, const Graph & G) { 517 518 VertexSet terminals; 519 for (const Vertex u : make_iterator_range(vertices(H))) { 520 if (out_degree(u, H) == 0) { 521 terminals.push_back(u); 522 } 523 } 524 525 BicliqueSet lowerSet = enumerateBicliques(makeGraphFacade(H), terminals); 526 // An intermediary vertex could have more than one outgoing edge but if any edge 527 // is not directed to a vertex in our biclique, we'll need to compute that specific 528 // value anyway. Remove them from the clique set and if there are not enough vertices 529 // in the biclique to make distribution profitable, eliminate the clique. 530 for (auto ci = lowerSet.begin(); ci != lowerSet.end(); ) { 531 VertexSet & A = std::get<0>(*ci); 533 * @brief intersects 534 **  */ 535 template <class Type> 536 inline bool intersects(const Type & A, const Type & B) { 537 auto first1 = A.begin(), last1 = A.end(); 538 auto first2 = B.begin(), last2 = B.end(); 539 while (first1 != last1 && first2 != last2) { 540 if (*first1 < *first2) { 541 ++first1; 542 } else if (*first2 < *first1) { 543 ++first2; 544 } else { 545 return true; 546 } 547 } 548 return false; 549 } 550 551 /**  * 552 * @brief independentCliqueSets 553 **  */ 554 template <unsigned side> 555 inline static BicliqueSet && independentCliqueSets(BicliqueSet && cliques) { 556 using IndependentSetGraph = adjacency_list<hash_setS, vecS, undirectedS, unsigned>; 557 558 const auto l = cliques.size(); 559 IndependentSetGraph I(l); 560 561 // Initialize our weights 562 for (unsigned i = 0; i != l; ++i) { 563 I[i] = std::pow(std::get<side>(cliques[i]).size(), 2); 564 } 565 566 // Determine our constraints 567 for (unsigned i = 0; i != l; ++i) { 568 for (unsigned j = i + 1; j != l; ++j) { 569 if (intersects(std::get<side>(cliques[i]), std::get<side>(cliques[j]))) { 570 add_edge(i, j, I); 571 } 572 } 573 } 574 575 // Use the greedy algorithm to choose our independent set 576 VertexSet selected; 577 for (;;) { 578 unsigned w = 0; 579 Vertex u = 0; 580 for (unsigned i = 0; i != l; ++i) { 581 if (I[i] > w) { 582 w = I[i]; 583 u = i; 584 } 585 } 586 if (w == 0) break; 587 selected.push_back(u); 588 I[u] = 0; 589 for (auto v : make_iterator_range(adjacent_vertices(u, I))) { 590 I[v] = 0; 591 } 592 } 593 594 // Sort the selected list and then remove the unselected cliques 595 std::sort(selected.begin(), selected.end(), std::greater<Vertex>()); 596 auto end = cliques.end(); 597 for (const unsigned offset : selected) { 598 end = cliques.erase(cliques.begin() + offset + 1, end)  1; 599 } 600 cliques.erase(cliques.begin(), end); 601 602 return std::move(cliques); 603 } 604 605 /**  * 606 * @brief removeUnhelpfulBicliques 607 * 608 * An intermediary vertex could have more than one outgoing edge but if any edge is not directed to a vertex in our 609 * biclique, we'll need to compute that specific value anyway. Remove them from the clique set and if there are not 610 * enough vertices in the biclique to make distribution profitable, eliminate the clique. 611 **  */ 612 static BicliqueSet && removeUnhelpfulBicliques(BicliqueSet && cliques, const Graph & G, DistributionGraph & H) { 613 for (auto ci = cliques.begin(); ci != cliques.end(); ) { 614 const auto cardinalityA = std::get<0>(*ci).size(); 532 615 VertexSet & B = std::get<1>(*ci); 533 const auto cardinalityA = A.size();534 616 for (auto bi = B.begin(); bi != B.end(); ) { 535 617 if (out_degree(H[*bi], G) == cardinalityA) { … … 539 621 } 540 622 } 541 542 623 if (B.size() > 1) { 543 624 ++ci; 544 625 } else { 545 ci = lowerSet.erase(ci); 546 } 547 } 548 549 // Each distribution tuple consists of the sources, intermediary, and sink nodes. 626 ci = cliques.erase(ci); 627 } 628 } 629 return std::move(cliques); 630 } 631 632 /**  * 633 * @brief safeDistributionSets 634 **  */ 635 static DistributionSets safeDistributionSets(const PabloBlock & block, const Graph & G, DistributionGraph & H) { 636 637 const auto F = makeGraphFacade(H); 638 639 640 DistributionGraph X; 550 641 DistributionSets T; 551 for (const Biclique & lower : lowerSet) { 552 BicliqueSet upperSet = enumerateBicliques(makeGraphFacade(H), std::get<1>(lower)); 553 for (Biclique upper : upperSet) { 554 T.emplace_back(std::get<1>(upper), std::get<0>(upper), std::get<0>(lower)); 555 } 556 } 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 649 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))); 667 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 T.emplace_back(std::move(std::get<1>(upper)), std::move(std::get<0>(upper)), std::get<0>(lower)); 705 } 706 } 707 708 // printGraph(block, X, G, "H1"); 557 709 558 710 return std::move(T); … … 565 717 DistributionMap M; 566 718 for (const Vertex u : make_iterator_range(vertices(G))) { 567 const TypeId outerTypeId = G[u]>getClassTypeId(); 568 if (outerTypeId == TypeId::And  outerTypeId == TypeId::Or) { 569 if (inCurrentBlock(cast<Statement>(G[u]), block)) { 570 const TypeId innerTypeId = (outerTypeId == TypeId::And) ? TypeId::Or : TypeId::And; 571 flat_set<Vertex> distributable; 572 for (auto e : make_iterator_range(in_edges(u, G))) { 573 const Vertex v = source(e, G); 574 if (LLVM_UNLIKELY(G[v]>getClassTypeId() == innerTypeId && inCurrentBlock(cast<Statement>(G[v]), block))) { 575 bool safe = true; 576 for (const auto e : make_iterator_range(out_edges(v, G))) { 577 if (G[target(e, G)]>getClassTypeId() != outerTypeId) { 578 safe = false; 579 break; 719 if (in_degree(u, G) > 0) { 720 const TypeId outerTypeId = G[u]>getClassTypeId(); 721 if (outerTypeId == TypeId::And  outerTypeId == TypeId::Or) { 722 if (inCurrentBlock(cast<Statement>(G[u]), block)) { 723 const TypeId innerTypeId = (outerTypeId == TypeId::And) ? TypeId::Or : TypeId::And; 724 flat_set<Vertex> distributable; 725 for (auto e : make_iterator_range(in_edges(u, G))) { 726 const Vertex v = source(e, G); 727 if (LLVM_UNLIKELY(G[v]>getClassTypeId() == innerTypeId && inCurrentBlock(cast<Statement>(G[v]), block))) { 728 bool safe = true; 729 for (const auto e : make_iterator_range(out_edges(v, G))) { 730 if (G[target(e, G)]>getClassTypeId() != outerTypeId) { 731 safe = false; 732 break; 733 } 580 734 } 581 } 582 if (safe) { 583 distributable.insert(v); 584 } 585 } 586 } 587 if (LLVM_LIKELY(distributable.size() > 1)) { 588 // We're only interested in computing a subgraph of G in which every source has an outdegree 589 // greater than 1. Otherwise we'd only end up permuting the AND/OR sequence with no logical 590 // benefit. (Note: this does not consider register pressure / liveness.) 591 flat_map<Vertex, bool> observedMoreThanOnce; 592 bool anyOpportunities = false; 593 for (const Vertex v : distributable) { 594 for (auto e : make_iterator_range(in_edges(v, G))) { 595 const Vertex w = source(e, G); 596 auto ob = observedMoreThanOnce.find(w); 597 if (ob == observedMoreThanOnce.end()) { 598 observedMoreThanOnce.emplace(w, false); 599 } else { 600 ob>second = true; 601 anyOpportunities = true; 735 if (safe) { 736 distributable.insert(v); 602 737 } 603 738 } 604 739 } 605 if (anyOpportunities) { 606 for (const auto ob : observedMoreThanOnce) { 607 if (ob.second) { 608 const Vertex w = ob.first; 609 for (auto e : make_iterator_range(out_edges(w, G))) { 610 const Vertex v = target(e, G); 611 if (distributable.count(v)) { 612 const Vertex y = getVertex(v, H, M); 613 add_edge(y, getVertex(u, H, M), H); 614 add_edge(getVertex(w, H, M), y, H); 740 if (LLVM_LIKELY(distributable.size() > 1)) { 741 // We're only interested in computing a subgraph of G in which every source has an outdegree 742 // greater than 1. Otherwise we'd only end up permuting the AND/OR sequence with no logical 743 // benefit. (Note: this does not consider register pressure / liveness.) 744 flat_map<Vertex, bool> observedMoreThanOnce; 745 bool anyOpportunities = false; 746 for (const Vertex v : distributable) { 747 for (auto e : make_iterator_range(in_edges(v, G))) { 748 const Vertex w = source(e, G); 749 auto ob = observedMoreThanOnce.find(w); 750 if (ob == observedMoreThanOnce.end()) { 751 observedMoreThanOnce.emplace(w, false); 752 } else { 753 ob>second = true; 754 anyOpportunities = true; 755 } 756 } 757 } 758 if (anyOpportunities) { 759 for (const auto ob : observedMoreThanOnce) { 760 if (ob.second) { 761 const Vertex w = ob.first; 762 for (auto e : make_iterator_range(out_edges(w, G))) { 763 const Vertex v = target(e, G); 764 if (distributable.count(v)) { 765 const Vertex y = getVertex(v, H, M); 766 add_edge(y, getVertex(u, H, M), H); 767 add_edge(getVertex(w, H, M), y, H); 768 } 615 769 } 616 770 } … … 631 785 bool BooleanReassociationPass::redistributeAST(PabloBlock & block, Graph & G) const { 632 786 bool anyChanges = false; 787 788 unsigned count = 0; 789 790 // printGraph(block, G, "G" + std::to_string(count++)); 791 633 792 for (;;) { 634 793 … … 642 801 } 643 802 644 DistributionSets distributionSets = safeDistributionSets(H, G);803 const DistributionSets distributionSets = safeDistributionSets(block, G, H); 645 804 646 805 if (LLVM_UNLIKELY(distributionSets.empty())) { … … 648 807 } 649 808 650 651 break; 652 653 654 655 // for (const Vertex s : make_iterator_range(vertices(H))) { 656 657 // if (in_degree(s, H) == 0) { 658 659 // assert (sources.size() > 0); 660 // const VertexSet intermediary = outgoingVertexSet(sources.front(), makeGraphFacade(H)); 661 // assert (intermediary.size() > 0); 662 // const VertexSet sinks = outgoingVertexSet(intermediary.front(), makeGraphFacade(H)); 663 // assert (sinks.size() > 0); 664 665 // // Now begin transforming the AST 666 // circular_buffer<PabloAST *> Q(std::max(sources.size(), intermediary.size() + 1)); 667 // for (const Vertex u : intermediary) { 668 // Q.push_back(G[H[u]]); 669 // } 670 // const TypeId typeId = G[H[sinks.front()]]>getClassTypeId(); 671 // assert (typeId == TypeId::And  typeId == TypeId::Or); 672 // PabloAST * merged = createTree(block, typeId, Q); 673 // for (const Vertex s : sources) { 674 // Q.push_back(G[H[s]]); 675 // } 676 // Q.push_back(merged); 677 // PabloAST * masked = createTree(block, (typeId == TypeId::Or) ? TypeId::And : TypeId::Or, Q); 678 679 // // Eliminate the edges from our original graph G 680 // for (const Vertex u : intermediary) { 681 // const auto uu = H[u]; 682 // for (const Vertex s : sources) { 683 // assert(edge(H[s], uu, G).second); 684 // remove_edge(H[s], uu, G); 685 // } 686 // for (const Vertex t : sinks) { 687 // assert(edge(uu, H[t], G).second); 688 // remove_edge(uu, H[t], G); 689 // } 690 // } 691 692 // // Finally update G to match the desired changes 693 // const Vertex x = add_vertex(merged, G); 694 // const Vertex y = add_vertex(masked, G); 695 // for (const Vertex u : intermediary) { 696 // add_edge(H[u], x, G); 697 // } 698 // add_edge(x, y, G); 699 // for (const Vertex s : sources) { 700 // add_edge(H[s], y, G); 701 // } 702 // for (const Vertex t : sinks) { 703 // add_edge(y, H[t], G); 704 // } 705 706 // } 707 708 // } 709 // anyChanges = true; 710 711 } 712 809 for (const DistributionSet & set : distributionSets) { 810 // Each distribution tuple consists of the sources, intermediary, and sink nodes. 811 const VertexSet & sources = std::get<0>(set); 812 const VertexSet & intermediary = std::get<1>(set); 813 const VertexSet & sinks = std::get<2>(set); 814 815 const TypeId outerTypeId = G[H[sinks.front()]]>getClassTypeId(); 816 assert (outerTypeId == TypeId::And  outerTypeId == TypeId::Or); 817 const TypeId innerTypeId = (outerTypeId == TypeId::Or) ? TypeId::And : TypeId::Or; 818 819 // Eliminate the edges from our original graph G 820 for (const Vertex u : intermediary) { 821 const auto uu = H[u]; 822 for (const Vertex s : sources) { 823 assert (edge(H[s], uu, G).second); 824 remove_edge(H[s], uu, G); 825 } 826 for (const Vertex t : sinks) { 827 assert (edge(uu, H[t], G).second); 828 remove_edge(uu, H[t], G); 829 } 830 } 831 832 // Update G to match the desired changes 833 const Vertex x = add_vertex(nullptr, G); 834 const Vertex y = add_vertex(nullptr, G); 835 for (const Vertex u : intermediary) { 836 add_edge(H[u], x, G); 837 } 838 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 } 849 } 850 for (const Vertex t : sinks) { 851 add_edge(y, H[t], G); 852 } 853 add_edge(x, y, G); 854 855 // Now begin transforming the AST 856 circular_buffer<PabloAST *> Q(std::max(in_degree(x, G), in_degree(y, G))); 857 for (auto e : make_iterator_range(in_edges(x, G))) { 858 Q.push_back(G[source(e, G)]); 859 } 860 G[x] = createTree(block, outerTypeId, Q); 861 for (auto e : make_iterator_range(in_edges(y, G))) { 862 Q.push_back(G[source(e, G)]); 863 } 864 G[y] = createTree(block, innerTypeId, Q); 865 } 866 anyChanges = true; 867 } 713 868 return anyChanges; 714 869 }
Note: See TracChangeset
for help on using the changeset viewer.