Changeset 4760
 Timestamp:
 Sep 4, 2015, 4:44:59 PM (4 years ago)
 Location:
 icGREP/icgrepdevel/icgrep/pablo/optimizers
 Files:

 1 added
 1 edited
Legend:
 Unmodified
 Added
 Removed

icGREP/icgrepdevel/icgrep/pablo/optimizers/booleanreassociationpass.cpp
r4759 r4760 12 12 #include <iostream> 13 13 #include <pablo/printer_pablos.h> 14 14 #include "graphfacade.hpp" 15 15 16 16 using namespace boost; … … 187 187 PabloAST * e2 = Q.front(); Q.pop_front(); 188 188 PabloAST * expr = nullptr; 189 // Note: this switch ought to compile to an array of function pointers to the appropriate method. 189 190 switch (typeId) { 190 191 case PabloAST::ClassTypeId::And: … … 331 332 332 333 summarizeAST(block, terminals, G); 333 redistributeAST(block, G);334 335 334 printGraph(block, G, "G"); 336 335 if (redistributeAST(block, G)) { 336 printGraph(block, G, "H"); 337 } 337 338 } 338 339 … … 614 615 static VertexSet incomingVertexSet(const Vertex u, const Graph & G) { 615 616 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));617 V.reserve(G.in_degree(u)); 618 for (auto e : make_iterator_range(G.in_edges(u))) { 619 V.push_back(G.source(e)); 619 620 } 620 621 std::sort(V.begin(), V.end()); … … 625 626 static VertexSet outgoingVertexSet(const Vertex u, const Graph & G) { 626 627 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));628 V.reserve(G.out_degree(u)); 629 for (auto e : make_iterator_range(G.out_edges(u))) { 630 V.push_back(G.target(e)); 630 631 } 631 632 std::sort(V.begin(), V.end()); … … 634 635 635 636 /**  * 636 * @brief mica637 * @brief enumerateBicliques 637 638 * 638 639 * Adaptation of the MICA algorithm as described in "Consensus algorithms for the generation of all maximal 639 640 * bicliques" by Alexe et. al. (2003). Note: this implementation considers all verticies with an indegree of 0 640 * (or outdegree of 0 if the graph is transposed)to be in bipartition A and their adjacencies to be in B.641 * to be in bipartition A and their adjacencies to be in B. 641 642 **  */ 642 template < bool transposed,class Graph>643 static VertexSets mica(const Graph & G) {643 template <class Graph> 644 static VertexSets enumerateBicliques(const Graph & G) { 644 645 using IntersectionSets = std::set<VertexSet>; 645 646 646 IntersectionSets C;647 648 647 IntersectionSets B1; 649 for (auto u : make_iterator_range( vertices(G))) {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());648 for (auto u : make_iterator_range(G.vertices())) { 649 if (G.in_degree(u) == 0) { 650 B1.insert(std::move(outgoingVertexSet(u, G))); 651 } 652 } 653 654 IntersectionSets C(B1.begin(), B1.end()); 656 655 657 656 IntersectionSets Bi; … … 674 673 } 675 674 C.insert(Bi.begin(), Bi.end()); 676 677 675 IntersectionSets Bk; 678 676 for (auto i = B1.begin(); i != B1.end(); ++i) { … … 761 759 762 760 /**  * 763 * @brief filterBicliqueGraph764 **  */ 765 template < bool transposed,class Graph>766 static VertexSets filterBicliqueGraph(Graph& G) {767 VertexSets B (std::move(maximalIndependentSet(std::move(mica<transposed>(G)))));761 * @brief sinkIndependentBicliques 762 **  */ 763 template <class Graph> 764 static VertexSets sinkIndependentBicliques(Graph && G) { 765 VertexSets B = maximalIndependentSet(std::move(enumerateBicliques(G))); 768 766 VertexSets A; 769 767 A.reserve(B.size()); … … 771 769 // Compute our A set 772 770 auto bi = Bi.begin(); 773 VertexSet Ai (std::move(transposed ? outgoingVertexSet(*bi, G) : incomingVertexSet(*bi, G)));771 VertexSet Ai = incomingVertexSet(*bi, G); 774 772 while (++bi != Bi.end()) { 775 VertexSet Ai (std::move(transposed ? outgoingVertexSet(*bi, G) : incomingVertexSet(*bi, G)));773 VertexSet Ai = incomingVertexSet(*bi, G); 776 774 VertexSet Ak; 777 775 std::set_intersection(Ai.begin(), Ai.end(), Ai.begin(), Ai.end(), std::back_inserter(Ak)); … … 780 778 A.emplace_back(std::move(Ai)); 781 779 } 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 } 780 std::vector<Vertex> sources; 781 std::vector<Vertex> intermediary; 782 for (auto u : make_iterator_range(G.vertices())) { 783 if (G.in_degree(u) == 0) { 784 sources.push_back(u); 785 } else if (G.out_degree(u) != 0) { 786 intermediary.push_back(u); 787 } 788 } 789 for (auto u : sources) { 790 G.clear_out_edges(u); 791 } 792 for (unsigned i = 0; i != B.size(); ++i) { 793 for (auto u : A[i]) { 794 for (auto v : B[i]) { 795 G.add_edge(u, v); 796 } 797 } 798 } 799 for (auto u : intermediary) { 800 if (G.in_degree(u) == 0) { 801 G.clear_out_edges(u); 831 802 } 832 803 } … … 835 806 836 807 /**  * 837 * @brief computeSafeBicliqueSet808 * @brief safeDistributionSets 838 809 **  */ 839 810 template <class Graph> 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 broken843 // into weakly connected components withexactly one sink.811 static VertexSets safeDistributionSets(Graph & G) { 812 VertexSets sinks(std::move(sinkIndependentBicliques(makeTransposedGraphFacade(G)))); 813 // Scan through G and replicate any source that has more than one sink until G is broken 814 // into weakly connected components in which each has exactly one sink. 844 815 if (sinks.size() > 1) { 845 816 std::vector<unsigned> component(num_vertices(G), 0); … … 881 852 } 882 853 } 883 return std::move(filterBicliqueGraph<false>(G)); 854 return std::move(sinkIndependentBicliques(makeGraphFacade(G))); 855 } 856 857 /**  * 858 * @brief segmentInto3LevelGraph 859 * 860 * Ensure that every sourcetosink path in G has a distance of exactly 2. 861 **  */ 862 template <class Graph> 863 Graph & segmentInto3LevelGraph(Graph & G) { 864 865 std::vector<Vertex> ordering; 866 ordering.reserve(num_vertices(G)); 867 868 topological_sort(G, std::back_inserter(ordering)); 869 870 std::vector<unsigned> distance(num_vertices(G)); 871 // Compute the distance to furthest sink for each node 872 for (Vertex u : ordering) { 873 unsigned d = 0; 874 for (auto e : make_iterator_range(out_edges(u, G))) { 875 d = std::max<unsigned>(d, distance[target(e, G)] + 1); 876 } 877 distance[u] = d; 878 } 879 880 881 882 883 return G; 884 884 } 885 885 … … 892 892 using TypeId = PabloAST::ClassTypeId; 893 893 894 adjacency_list<hash_setS, vecS, bidirectionalS, Vertex> H; 895 flat_map<Vertex, Vertex> M; 896 897 for (const Vertex u : make_iterator_range(vertices(G))) { 898 const TypeId outerTypeId = G[u]>getClassTypeId(); 899 if (outerTypeId == TypeId::And  outerTypeId == TypeId::Or) { 900 if (inCurrentBlock(cast<Statement>(G[u]), block)) { 901 const TypeId innerTypeId = (outerTypeId == TypeId::And) ? TypeId::Or : TypeId::And; 902 flat_set<Vertex> distributable; 903 for (auto e : make_iterator_range(in_edges(u, G))) { 904 const Vertex v = source(e, G); 905 if (G[v]>getClassTypeId() == innerTypeId && inCurrentBlock(cast<Statement>(G[v]), block)) { 906 bool safe = true; 907 for (PabloAST * user : G[v]>users()) { 908 if (user>getClassTypeId() != outerTypeId  !inCurrentBlock(cast<Statement>(user), block)) { 909 safe = false; 910 break; 894 bool anyChanges = false; 895 896 for (;;) { 897 898 adjacency_list<hash_setS, vecS, bidirectionalS, Vertex> H; 899 flat_map<Vertex, Vertex> M; 900 901 for (const Vertex u : make_iterator_range(vertices(G))) { 902 const TypeId outerTypeId = G[u]>getClassTypeId(); 903 if (outerTypeId == TypeId::And  outerTypeId == TypeId::Or) { 904 if (inCurrentBlock(cast<Statement>(G[u]), block)) { 905 const TypeId innerTypeId = (outerTypeId == TypeId::And) ? TypeId::Or : TypeId::And; 906 flat_set<Vertex> distributable; 907 for (auto e : make_iterator_range(in_edges(u, G))) { 908 const Vertex v = source(e, G); 909 if (LLVM_UNLIKELY(G[v]>getClassTypeId() == innerTypeId) && LLVM_LIKELY(inCurrentBlock(cast<Statement>(G[v]), block))) { 910 bool safe = true; 911 for (const auto e : make_iterator_range(out_edges(v, G))) { 912 if (G[target(e, G)]>getClassTypeId() != outerTypeId) { 913 safe = false; 914 break; 915 } 911 916 } 912 } 913 if (safe) { 914 distributable.insert(v); 915 } 916 } 917 } 918 if (LLVM_LIKELY(distributable.size() > 1)) { 919 // We're only interested in computing a subgraph of G in which every source has an outdegree 920 // greater than 1. Otherwise we'd only end up permuting the AND/OR sequence with no logical 921 // benefit. (Note: this does not consider register pressure / liveness.) 922 flat_map<Vertex, unsigned> observed; 923 bool anyOpportunities = false; 924 for (const Vertex v : distributable) { 925 for (auto e : make_iterator_range(in_edges(v, G))) { 926 const Vertex w = source(e, G); 927 const auto f = observed.find(w); 928 if (f == observed.end()) { 929 observed.emplace(w, 0); 930 } else { 931 f>second += 1; 932 anyOpportunities = true; 917 if (safe) { 918 distributable.insert(v); 933 919 } 934 920 } 935 921 } 936 if (anyOpportunities) { 937 for (auto ob : observed) { 938 if (std::get<1>(ob)) { 939 const Vertex w = std::get<0>(ob); 940 for (auto e : make_iterator_range(out_edges(w, G))) { 941 const Vertex v = target(e, G); 942 if (distributable.count(v)) { 943 const Vertex x = getVertex(u, H, M); 944 const Vertex y = getVertex(v, H, M); 945 const Vertex z = getVertex(w, H, M); 946 add_edge(y, x, H); 947 add_edge(z, y, H); 922 if (LLVM_LIKELY(distributable.size() > 1)) { 923 // We're only interested in computing a subgraph of G in which every source has an outdegree 924 // greater than 1. Otherwise we'd only end up permuting the AND/OR sequence with no logical 925 // benefit. (Note: this does not consider register pressure / liveness.) 926 flat_map<Vertex, unsigned> observed; 927 bool anyOpportunities = false; 928 for (const Vertex v : distributable) { 929 for (auto e : make_iterator_range(in_edges(v, G))) { 930 const Vertex w = source(e, G); 931 const auto f = observed.find(w); 932 if (f == observed.end()) { 933 observed.emplace(w, 0); 934 } else { 935 f>second += 1; 936 anyOpportunities = true; 937 } 938 } 939 } 940 if (anyOpportunities) { 941 for (auto ob : observed) { 942 if (std::get<1>(ob)) { 943 const Vertex w = std::get<0>(ob); 944 for (auto e : make_iterator_range(out_edges(w, G))) { 945 const Vertex v = target(e, G); 946 if (distributable.count(v)) { 947 const Vertex y = getVertex(v, H, M); 948 add_edge(y, getVertex(u, H, M), H); 949 add_edge(getVertex(w, H, M), y, H); 950 } 948 951 } 949 952 } … … 954 957 } 955 958 } 956 } 957 958 // If we found no potential opportunities then we cannot apply the distribution law to any part of G. 959 if (num_vertices(H) == 0) { 960 return false; 961 } 962 963 // printGraph(block, H, G, "H0"); 964 965 // By finding the maximal set of bicliques in H=(A,B) âª T in which the verticies in bipartition B are 966 // independent, we can identify a safe set of vertices to apply the distribution law to. 967 VertexSets sourceSets(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(sourceSets.size() == 0)) { 971 return false; 972 } 973 974 // printGraph(block, H, G, "H1"); 975 976 for (VertexSet & sources : sourceSets) { 977 VertexSet intermediary; 978 intermediary.reserve(out_degree(sources.front(), H)); 979 for (auto e : make_iterator_range(out_edges(sources.front(), H))) { 980 const Vertex v = H[target(e, H)]; 981 982 983 intermediary.push_back(v); 984 } 985 VertexSet terminals; 986 terminals.reserve(out_degree(intermediary.front(), H)); 987 for (auto e : make_iterator_range(out_edges(intermediary.front(), H))) { 988 terminals.push_back(H[target(e, H)]); 989 } 990 const TypeId typeId = G[H[terminals.front()]]>getClassTypeId(); 991 assert (typeId == TypeId::And  typeId == TypeId::Or); 992 circular_buffer<Vertex> Q(std::max(sources.size(), intermediary.size() + 1)); 993 for (const Vertex u : intermediary) { 994 Q.push_back(G[H[u]]); 995 } 996 PabloAST * merged = createTree(block, typeId, Q); 997 for (const Vertex u : sources) { 998 Q.push_back(G[H[u]]); 999 } 1000 Q.push_back(merged); 1001 PabloAST * masked = createTree(block, typeId == TypeId::Or ? TypeId::And : TypeId::Or, Q); 1002 1003 1004 1005 1006 1007 circular_buffer<Vertex> I(out_degree(S.front(), H)); 1008 for (auto e : make_iterator_range(out_edges(S.front(), H))) { 1009 I.push_back(H[target(e, H)]); 1010 } 1011 1012 1013 1014 1015 1016 } 1017 1018 1019 return true; 1020 } 1021 1022 } 959 960 // If we found no potential opportunities then we cannot apply the distribution law to any part of G. 961 if (num_vertices(H) == 0) { 962 break; 963 } 964 965 const VertexSets distributionSets = safeDistributionSets(segmentInto3LevelGraph(H)); 966 967 // If no sources remain, no bicliques were found that would have a meaningful impact on the AST. 968 if (LLVM_UNLIKELY(distributionSets.size() == 0)) { 969 break; 970 } 971 972 for (const VertexSet & sources : distributionSets) { 973 assert (sources.size() > 0); 974 const VertexSet intermediary = outgoingVertexSet(sources.front(), makeGraphFacade(H)); 975 assert (intermediary.size() > 0); 976 const VertexSet sinks = outgoingVertexSet(intermediary.front(), makeGraphFacade(H)); 977 assert (sinks.size() > 0); 978 979 // Now begin transforming the AST 980 const TypeId typeId = G[H[sinks.front()]]>getClassTypeId(); 981 assert (typeId == TypeId::And  typeId == TypeId::Or); 982 983 circular_buffer<PabloAST *> Q(std::max(sources.size(), intermediary.size() + 1)); 984 for (const Vertex u : intermediary) { 985 Q.push_back(G[H[u]]); 986 } 987 PabloAST * merged = createTree(block, typeId, Q); 988 for (const Vertex s : sources) { 989 Q.push_back(G[H[s]]); 990 } 991 Q.push_back(merged); 992 PabloAST * masked = createTree(block, typeId == TypeId::Or ? TypeId::And : TypeId::Or, Q); 993 994 // Eliminate the edges from our original graph 995 for (const Vertex u : intermediary) { 996 for (const Vertex s : sources) { 997 remove_edge(H[s], H[u], G); 998 } 999 for (const Vertex t : sinks) { 1000 remove_edge(H[u], H[t], G); 1001 } 1002 } 1003 1004 // Finally update G to match the desired changes 1005 const Vertex x = add_vertex(merged, G); 1006 const Vertex y = add_vertex(masked, G); 1007 for (const Vertex u : intermediary) { 1008 add_edge(H[u], x, G); 1009 } 1010 add_edge(x, y, G); 1011 for (const Vertex s : sources) { 1012 add_edge(H[s], y, G); 1013 } 1014 for (const Vertex t : sinks) { 1015 add_edge(y, H[t], G); 1016 } 1017 } 1018 anyChanges = true; 1019 } 1020 1021 return anyChanges; 1022 } 1023 1024 }
Note: See TracChangeset
for help on using the changeset viewer.