Changeset 4758
 Timestamp:
 Sep 3, 2015, 4:06:46 PM (4 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

icGREP/icgrepdevel/icgrep/pablo/optimizers/booleanreassociationpass.cpp
r4757 r4758 269 269 out << "digraph " << name << " {\n"; 270 270 for (auto u : make_iterator_range(vertices(S))) { 271 if (in_degree(u, S) == 0 && out_degree(u, S) == 0) { 272 continue; 273 } 271 274 out << "v" << u << " [label=\""; 272 275 PabloAST * expr = G[S[u]]; … … 608 611 using VertexSets = std::vector<VertexSet>; 609 612 613 template <class Graph> 614 static VertexSet incomingVertexSet(const Vertex u, const Graph & G) { 615 VertexSet V; 616 V.reserve(in_degree(u, G)); 617 for (auto e : make_iterator_range(in_edges(u, G))) { 618 V.push_back(source(e, G)); 619 } 620 std::sort(V.begin(), V.end()); 621 return std::move(V); 622 } 623 624 template <class Graph> 625 static VertexSet outgoingVertexSet(const Vertex u, const Graph & G) { 626 VertexSet V; 627 V.reserve(out_degree(u, G)); 628 for (auto e : make_iterator_range(out_edges(u, G))) { 629 V.push_back(target(e, G)); 630 } 631 std::sort(V.begin(), V.end()); 632 return std::move(V); 633 } 634 610 635 /**  * 611 636 * @brief mica … … 613 638 * Adaptation of the MICA algorithm as described in "Consensus algorithms for the generation of all maximal 614 639 * bicliques" by Alexe et. al. (2003). Note: this implementation considers all verticies with an indegree of 0 615 * to be in bipartition A and their adjacencies to be in bipartition B. Because we do not care about the rank 1 616 * (star) cliques, this does not record them. 617 **  */ 618 template <class Graph> 640 * (or outdegree of 0 if the graph is transposed) to be in bipartition A and their adjacencies to be in B. 641 **  */ 642 template <bool transposed, class Graph> 619 643 static VertexSets mica(const Graph & G) { 620 644 using IntersectionSets = std::set<VertexSet>; 621 645 646 IntersectionSets C; 647 622 648 IntersectionSets B1; 623 649 for (auto u : make_iterator_range(vertices(G))) { 624 if (in_degree(u, G) == 0) { 625 VertexSet B; 626 B.reserve(out_degree(u, G)); 627 for (auto e : make_iterator_range(out_edges(u, G))) { 628 B.push_back(target(e, G)); 629 } 630 std::sort(B.begin(), B.end()); // note: these already ought to be in order 631 B1.insert(std::move(B)); 632 } 633 } 650 if ((transposed ? out_degree(u, G) : in_degree(u, G)) == 0) { 651 B1.insert(std::move(transposed ? incomingVertexSet(u, G) : outgoingVertexSet(u, G))); 652 } 653 } 654 655 C.insert(B1.begin(), B1.end()); 634 656 635 657 IntersectionSets Bi; … … 639 661 std::set_intersection(i>begin(), i>end(), j>begin(), j>end(), std::back_inserter(clique)); 640 662 if (clique.size() > 0) { 641 Bi.insert(clique); 663 if (C.count(clique) == 0) { 664 Bi.insert(clique); 665 } 642 666 clique.clear(); 643 667 } … … 645 669 } 646 670 647 IntersectionSets C;648 671 for (;;) { 649 672 if (Bi.empty()) { … … 671 694 672 695 /**  * 673 * @brief areNonDisjoint696 * @brief intersects 674 697 **  */ 675 698 template <class Type> … … 692 715 * @brief maximalIndependentSet 693 716 **  */ 694 static void maximalIndependentSet(VertexSets& V) {717 static VertexSets && maximalIndependentSet(VertexSets && V) { 695 718 using IndependentSetGraph = adjacency_list<hash_setS, vecS, undirectedS, unsigned>; 696 719 const auto l = V.size(); … … 698 721 // Initialize our weights 699 722 for (unsigned i = 0; i != l; ++i) { 700 I[i] = std::pow(V[i].size(), 2);723 I[i] = V[i].size(); 701 724 } 702 725 // Determine our constraints … … 720 743 } 721 744 } 722 if (w < 2) break;745 if (w == 0) break; 723 746 selected.push_back(u); 724 747 ignored[u] = true; … … 727 750 } 728 751 } 729 730 752 // Sort the selected list and then remove the unselected sets from V 731 753 std::sort(selected.begin(), selected.end(), std::greater<Vertex>()); … … 735 757 } 736 758 V.erase(V.begin(), end); 759 return std::move(V); 760 } 761 762 /**  * 763 * @brief filterBicliqueGraph 764 **  */ 765 template <bool transposed, class Graph> 766 static VertexSets filterBicliqueGraph(Graph & G) { 767 VertexSets B(std::move(maximalIndependentSet(std::move(mica<transposed>(G))))); 768 VertexSets A; 769 A.reserve(B.size()); 770 for (const VertexSet & Bi : B) { 771 // Compute our A set 772 auto bi = Bi.begin(); 773 VertexSet Ai(std::move(transposed ? outgoingVertexSet(*bi, G) : incomingVertexSet(*bi, G))); 774 while (++bi != Bi.end()) { 775 VertexSet Ai(std::move(transposed ? outgoingVertexSet(*bi, G) : incomingVertexSet(*bi, G))); 776 VertexSet Ak; 777 std::set_intersection(Ai.begin(), Ai.end(), Ai.begin(), Ai.end(), std::back_inserter(Ak)); 778 Ai.swap(Ak); 779 } 780 A.emplace_back(std::move(Ai)); 781 } 782 if (transposed) { 783 std::vector<Vertex> sinks; 784 std::vector<Vertex> intermediary; 785 for (auto u : make_iterator_range(vertices(G))) { 786 if (out_degree(u, G) == 0) { 787 sinks.push_back(u); 788 } else if (in_degree(u, G) != 0) { 789 intermediary.push_back(u); 790 } 791 } 792 for (auto u : sinks) { 793 clear_in_edges(u, G); 794 } 795 for (unsigned i = 0; i != B.size(); ++i) { 796 for (auto u : A[i]) { 797 for (auto v : B[i]) { 798 add_edge(v, u, G); 799 } 800 } 801 } 802 for (auto u : intermediary) { 803 if (out_degree(u, G) == 0) { 804 clear_in_edges(u, G); 805 } 806 } 807 } else { 808 std::vector<Vertex> sources; 809 std::vector<Vertex> intermediary; 810 for (auto u : make_iterator_range(vertices(G))) { 811 if (in_degree(u, G) == 0) { 812 sources.push_back(u); 813 } else if (out_degree(u, G) != 0) { 814 intermediary.push_back(u); 815 } 816 } 817 for (auto u : sources) { 818 clear_out_edges(u, G); 819 } 820 for (unsigned i = 0; i != B.size(); ++i) { 821 for (auto u : A[i]) { 822 for (auto v : B[i]) { 823 add_edge(u, v, G); 824 } 825 } 826 } 827 for (auto u : intermediary) { 828 if (in_degree(u, G) == 0) { 829 clear_out_edges(u, G); 830 } 831 } 832 } 833 return std::move(A); 737 834 } 738 835 … … 741 838 **  */ 742 839 template <class Graph> 743 static void computeSafeBicliqueSet(Graph & G) { 744 // First enumerate our bicliques in G. 745 auto R = mica(G); 746 // Then compute the maximal independent set of the vertices in the B bipartition. 747 maximalIndependentSet(R); 748 // Finally update G to reflect our chosen bicliques 749 VertexSets L; 750 L.reserve(R.size()); 751 for (const VertexSet & B : R) { 752 // Compute our A set 753 VertexSet A; 754 auto bi = B.begin(); 755 A.reserve(in_degree(*bi, G)); 756 for (auto e : make_iterator_range(in_edges(*bi, G))) { 757 A.push_back(source(e, G)); 758 } 759 std::sort(A.begin(), A.end()); 760 while (++bi != B.end()) { 761 VertexSet Ai; 762 Ai.reserve(in_degree(*bi, G)); 763 for (auto e : make_iterator_range(in_edges(*bi, G))) { 764 Ai.push_back(source(e, G)); 765 } 766 std::sort(Ai.begin(), Ai.end()); 767 VertexSet Ak; 768 std::set_intersection(A.begin(), A.end(), Ai.begin(), Ai.end(), std::back_inserter(Ak)); 769 A.swap(Ak); 770 } 771 L.emplace_back(std::move(A)); 772 } 773 std::vector<Vertex> sources; 774 for (auto u : make_iterator_range(vertices(G))) { 775 if (in_degree(u, G) == 0) { 776 sources.push_back(u); 777 } 778 } 779 for (auto u : sources) { 780 clear_out_edges(u, G); 781 } 782 for (unsigned i = 0; i != R.size(); ++i) { 783 for (auto u : L[i]) { 784 for (auto v : R[i]) { 785 add_edge(u, v, G); 786 } 787 } 788 } 840 static VertexSets computeSafeBicliqueSet(Graph & G) { 841 VertexSets sinks(std::move(filterBicliqueGraph<true>(G))); 842 // scan through G and replicate any source that has more than one sink until G is broken 843 // into weakly connected components with exactly one sink. 844 if (sinks.size() > 1) { 845 std::vector<unsigned> component(num_vertices(G), 0); 846 unsigned components = 0; 847 for (const VertexSet & S : sinks) { 848 ++components; 849 for (auto e : make_iterator_range(in_edges(S.front(), G))) { 850 component[source(e, G)] = components; 851 } 852 } 853 for (const Vertex u : make_iterator_range(vertices(G))) { 854 if (LLVM_UNLIKELY(in_degree(u, G) == 0)) { 855 flat_set<unsigned> membership; 856 for (auto e : make_iterator_range(out_edges(u, G))) { 857 membership.insert(component[target(e, G)]); 858 } 859 if (LLVM_UNLIKELY(membership.size() > 1)) { 860 VertexSet adjacent; 861 adjacent.reserve(out_degree(u, G)); 862 for (auto e : make_iterator_range(out_edges(u, G))) { 863 adjacent.push_back(target(e, G)); 864 } 865 clear_out_edges(u, G); 866 auto mi = membership.begin(); 867 for (Vertex uu = u; ;) { 868 const unsigned m = *mi; 869 for (auto v : adjacent) { 870 if (component[v] == m) { 871 add_edge(uu, v, G); 872 } 873 } 874 if (++mi == membership.end()) { 875 break; 876 } 877 uu = add_vertex(G[u], G); 878 } 879 } 880 } 881 } 882 } 883 return std::move(filterBicliqueGraph<false>(G)); 789 884 } 790 885 … … 870 965 // By finding the maximal set of bicliques in H=(A,B) âª T in which the verticies in bipartition B are 871 966 // 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)) {967 VertexSets sources(std::move(computeSafeBicliqueSet(H))); 968 969 // If no sources remain, no bicliques were found that would have a meaningful impact on the AST. 970 if (LLVM_UNLIKELY(sources.size() == 0)) { 876 971 return false; 877 972 } … … 879 974 printGraph(block, H, G, "H1"); 880 975 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 887 976 888 977
Note: See TracChangeset
for help on using the changeset viewer.