Changeset 4757 for icGREP/icgrepdevel/icgrep
 Timestamp:
 Sep 3, 2015, 11:17:33 AM (4 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

icGREP/icgrepdevel/icgrep/pablo/optimizers/booleanreassociationpass.cpp
r4756 r4757 329 329 summarizeAST(block, terminals, G); 330 330 redistributeAST(block, G); 331 332 // for (;;) {333 // summarizeAST(block, terminals, G);334 // if (redistributeAST(block, G)) {335 // G.clear();336 // } else {337 // break;338 // }339 // }340 331 341 332 printGraph(block, G, "G"); … … 615 606 616 607 using VertexSet = std::vector<Vertex>; 617 using VertexSets = std:: set<VertexSet>;608 using VertexSets = std::vector<VertexSet>; 618 609 619 610 /**  * … … 625 616 * (star) cliques, this does not record them. 626 617 **  */ 627 static std::vector<VertexSet> mica(const Graph & G) { 628 629 VertexSets B1; 618 template <class Graph> 619 static VertexSets mica(const Graph & G) { 620 using IntersectionSets = std::set<VertexSet>; 621 622 IntersectionSets B1; 630 623 for (auto u : make_iterator_range(vertices(G))) { 631 624 if (in_degree(u, G) == 0) { … … 640 633 } 641 634 642 VertexSets Bi; 643 635 IntersectionSets Bi; 644 636 VertexSet clique; 645 637 for (auto i = B1.begin(); i != B1.end(); ++i) { … … 653 645 } 654 646 655 VertexSets C; 656 647 IntersectionSets C; 657 648 for (;;) { 658 649 if (Bi.empty()) { … … 661 652 C.insert(Bi.begin(), Bi.end()); 662 653 663 VertexSets Bk;654 IntersectionSets Bk; 664 655 for (auto i = B1.begin(); i != B1.end(); ++i) { 665 656 for (auto j = Bi.begin(); j != Bi.end(); ++j) { … … 676 667 } 677 668 678 return std::vector<VertexSet>(C.begin(), C.end());669 return VertexSets(C.begin(), C.end()); 679 670 } 680 671 … … 683 674 **  */ 684 675 template <class Type> 685 inline bool areNonDisjoint(const Type & A, const Type & B) {676 inline bool intersects(const Type & A, const Type & B) { 686 677 auto first1 = A.begin(), last1 = A.end(); 687 678 auto first2 = B.begin(), last2 = B.end(); … … 701 692 * @brief maximalIndependentSet 702 693 **  */ 703 static void maximalIndependentSet( std::vector<VertexSet>& V) {694 static void maximalIndependentSet(VertexSets & V) { 704 695 using IndependentSetGraph = adjacency_list<hash_setS, vecS, undirectedS, unsigned>; 705 696 const auto l = V.size(); … … 712 703 for (unsigned i = 0; i != l; ++i) { 713 704 for (unsigned j = i + 1; j != l; ++j) { 714 if ( areNonDisjoint(V[i], V[j])) {705 if (intersects(V[i], V[j])) { 715 706 add_edge(i, j, I); 716 707 } … … 718 709 } 719 710 // Use the greedy algorithm to choose our independent set (TODO: try the similar randomized approach) 720 std::vector<Vertex> selected; 721 711 VertexSet selected; 722 712 std::vector<bool> ignored(l, false); 723 713 for (;;) { … … 739 729 740 730 // Sort the selected list and then remove the unselected sets from V 741 std::sort(selected.begin(), selected.end(), std::greater< unsigned>());731 std::sort(selected.begin(), selected.end(), std::greater<Vertex>()); 742 732 auto end = V.end(); 743 733 for (const unsigned offset : selected) { … … 745 735 } 746 736 V.erase(V.begin(), end); 747 748 } 749 750 751 /**  * 752 * @brief maximalIndependentBicliqueSet 753 **  */ 754 static void maximalIndependentBicliqueSet(Graph & G) { 737 } 738 739 /**  * 740 * @brief computeSafeBicliqueSet 741 **  */ 742 template <class Graph> 743 static void computeSafeBicliqueSet(Graph & G) { 755 744 // First enumerate our bicliques in G. 756 745 auto R = mica(G); 757 746 // Then compute the maximal independent set of the vertices in the B bipartition. 758 // NOTE: this means vertices in A can point to more than one vertex in B. These759 // have to be resolved specially later.760 747 maximalIndependentSet(R); 761 // Update G to reflect our maximal independent biclique set 762 std::vector<VertexSet> L; 748 // Finally update G to reflect our chosen bicliques 749 VertexSets L; 750 L.reserve(R.size()); 763 751 for (const VertexSet & B : R) { 764 752 // Compute our A set … … 783 771 L.emplace_back(std::move(A)); 784 772 } 773 std::vector<Vertex> sources; 785 774 for (auto u : make_iterator_range(vertices(G))) { 786 775 if (in_degree(u, G) == 0) { 787 clear_out_edges(u, G); 788 } 776 sources.push_back(u); 777 } 778 } 779 for (auto u : sources) { 780 clear_out_edges(u, G); 789 781 } 790 782 for (unsigned i = 0; i != R.size(); ++i) { … … 805 797 using TypeId = PabloAST::ClassTypeId; 806 798 807 Graph B;808 MapM;799 adjacency_list<hash_setS, vecS, bidirectionalS, Vertex> H; 800 flat_map<Vertex, Vertex> M; 809 801 810 802 for (const Vertex u : make_iterator_range(vertices(G))) { … … 847 839 } 848 840 } 849 if (anyOpportunities) { 841 if (anyOpportunities) { 850 842 for (auto ob : observed) { 851 843 if (std::get<1>(ob)) { 852 const Vertex v = std::get<0>(ob); 853 for (auto e : make_iterator_range(out_edges(v, G))) { 854 const Vertex w = target(e, G); 855 if (distributable.count(w)) { 856 add_edge(getVertex(G[v], B, M), getVertex(G[w], B, M), B); 844 const Vertex w = std::get<0>(ob); 845 for (auto e : make_iterator_range(out_edges(w, G))) { 846 const Vertex v = target(e, G); 847 if (distributable.count(v)) { 848 const Vertex x = getVertex(u, H, M); 849 const Vertex y = getVertex(v, H, M); 850 const Vertex z = getVertex(w, H, M); 851 add_edge(y, x, H); 852 add_edge(z, y, H); 857 853 } 858 854 } … … 866 862 867 863 // If we found no potential opportunities then we cannot apply the distribution law to any part of G. 868 if (num_vertices( B) == 0) {864 if (num_vertices(H) == 0) { 869 865 return false; 870 866 } 871 867 872 printGraph(block, B, "B0"); 873 874 // By finding the maximal set of independent bicliques in S, 875 876 maximalIndependentBicliqueSet(B); 877 878 879 printGraph(block, B, "B1"); 868 printGraph(block, H, G, "H0"); 869 870 // By finding the maximal set of bicliques in H=(A,B) âª T in which the verticies in bipartition B are 871 // independent, we can identify a safe set of vertices to apply the distribution law to. 872 computeSafeBicliqueSet(H); 873 874 // If no edges are remaining, no bicliques were found that would have a meaningful impact on the AST. 875 if (LLVM_UNLIKELY(num_edges(H) == 0)) { 876 return false; 877 } 878 879 printGraph(block, H, G, "H1"); 880 881 // for (const Vertex u : make_iterator_range(vertices(H))) { 882 // if (LLVM_UNLIKELY(in_degree(u, H) == 0 && out_degree(u, H) != 0)) { 883 884 // } 885 // } 886 880 887 881 888
Note: See TracChangeset
for help on using the changeset viewer.