Changeset 4761 for icGREP/icgrepdevel/icgrep/pablo/optimizers
 Timestamp:
 Sep 5, 2015, 1:16:12 AM (4 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

icGREP/icgrepdevel/icgrep/pablo/optimizers/booleanreassociationpass.cpp
r4760 r4761 24 24 using Map = BooleanReassociationPass::Map; 25 25 using EdgeQueue = std::queue<std::pair<Vertex, Vertex>>; 26 using TypeId = PabloAST::ClassTypeId; 26 27 27 28 /**  * … … 56 57 } 57 58 58 59 /**  * 60 * @brief scan 59 /**  * 60 * @brief processScopes 61 61 **  */ 62 62 inline void BooleanReassociationPass::processScopes(PabloFunction & function) { … … 69 69 70 70 /**  * 71 * @brief scan71 * @brief processScopes 72 72 **  */ 73 73 void BooleanReassociationPass::processScopes(PabloBlock & block, std::vector<Statement *> && terminals) { … … 183 183 **  */ 184 184 static PabloAST * createTree(PabloBlock & block, const PabloAST::ClassTypeId typeId, circular_buffer<PabloAST *> & Q) { 185 assert (!Q.empty()); 185 186 while (Q.size() > 1) { 186 187 PabloAST * e1 = Q.front(); Q.pop_front(); … … 327 328 * @brief processScope 328 329 **  */ 329 void BooleanReassociationPass::processScope(PabloBlock & block, std::vector<Statement *> && terminals) { 330 330 inline void BooleanReassociationPass::processScope(PabloBlock & block, std::vector<Statement *> && terminals) { 331 331 Graph G; 332 333 332 summarizeAST(block, terminals, G); 334 printGraph(block, G, "G"); 335 if (redistributeAST(block, G)) { 336 printGraph(block, G, "H"); 337 } 333 334 printGraph(block, G, "G0"); 335 336 redistributeAST(block, G); 337 338 printGraph(block, G, "G1"); 339 340 circular_buffer<Vertex> Q(num_vertices(G)); 341 topological_sort(G, std::front_inserter(Q)); 342 343 circular_buffer<PabloAST *> nodes; 344 block.setInsertPoint(nullptr); 345 346 while (!Q.empty()) { 347 const Vertex u = Q.front(); 348 Q.pop_front(); 349 PabloAST * expr = G[u]; 350 if (LLVM_LIKELY(inCurrentBlock(expr, block))) { 351 switch (expr>getClassTypeId()) { 352 case TypeId::And: 353 case TypeId::Or: 354 case TypeId::Xor: 355 if (LLVM_UNLIKELY(in_degree(u, G) < 2)) { 356 std::string tmp; 357 raw_string_ostream str(tmp); 358 PabloPrinter::print(cast<Statement>(expr), "Unexpected error: ", str); 359 str << " only had " << in_degree(u, G) << " nodes!"; 360 throw std::runtime_error(str.str()); 361 } 362 nodes.set_capacity(in_degree(u, G)); 363 for (auto e : make_iterator_range(in_edges(u, G))) { 364 nodes.push_back(G[source(e, G)]); 365 } 366 expr = createTree(block, expr>getClassTypeId(), nodes); 367 default: 368 block.insert(cast<Statement>(expr)); 369 } 370 } 371 } 372 373 338 374 } 339 375 … … 687 723 Bi.swap(Bk); 688 724 } 689 690 725 return VertexSets(C.begin(), C.end()); 691 726 } … … 759 794 760 795 /**  * 761 * @brief sinkIndependent Bicliques796 * @brief sinkIndependentMaximalBicliques 762 797 **  */ 763 798 template <class Graph> 764 static VertexSets sinkIndependent Bicliques(Graph && G) {799 static VertexSets sinkIndependentMaximalBicliques(Graph && G) { 765 800 VertexSets B = maximalIndependentSet(std::move(enumerateBicliques(G))); 766 801 VertexSets A; … … 810 845 template <class Graph> 811 846 static VertexSets safeDistributionSets(Graph & G) { 812 VertexSets sinks (std::move(sinkIndependentBicliques(makeTransposedGraphFacade(G))));847 VertexSets sinks = sinkIndependentMaximalBicliques(makeTransposedGraphFacade(G)); 813 848 // Scan through G and replicate any source that has more than one sink until G is broken 814 849 // into weakly connected components in which each has exactly one sink. … … 852 887 } 853 888 } 854 return std::move(sinkIndependent Bicliques(makeGraphFacade(G)));889 return std::move(sinkIndependentMaximalBicliques(makeGraphFacade(G))); 855 890 } 856 891 … … 858 893 * @brief segmentInto3LevelGraph 859 894 * 860 * Ensure that every sourcetosink path in G has a distance of exactly 2. 895 * Ensure that every sourcetosink path in G has an edgedistance of exactly 2. The safeDistributionSets algorithm 896 * expects that G exibits this property but if an input to a distributable function is also the output of another 897 * distributable function, this complicates the analysis process. Thus method resolves that by replicating the 898 * appropriate vertices into inputonly and outputonly vertices. 861 899 **  */ 862 900 template <class Graph> 863 901 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 902 std::vector<unsigned> distance(num_vertices(G), 0); 903 std::queue<Vertex> Q; 904 for (const Vertex u : make_iterator_range(vertices(G))) { 905 if (in_degree(u, G) == 0) { 906 distance[u] = 1; 907 for (const auto e : make_iterator_range(out_edges(u, G))) { 908 Q.push(target(e, G)); 909 } 910 } 911 } 912 for (;;) { 913 const Vertex u = Q.front(); Q.pop(); 914 unsigned dist = 0; 915 bool ready = true; 916 for (const auto e : make_iterator_range(in_edges(u, G))) { 917 const Vertex v = source(e, G); 918 if (LLVM_UNLIKELY(distance[v] == 0)) { 919 ready = false; 920 break; 921 } 922 dist = std::max(dist, distance[v]); 923 } 924 assert (dist <= 4); 925 if (ready) { 926 if (LLVM_UNLIKELY(dist == 4)) { 927 for (const auto e : make_iterator_range(in_edges(u, G))) { 928 const Vertex v = source(e, G); 929 if (distance[v] == 3) { 930 const Vertex w = add_vertex(G[v], G); 931 for (const auto e : make_iterator_range(out_edges(v, G))) { 932 add_edge(w, target(e, G), G); 933 } 934 clear_out_edges(v, G); 935 assert (w == distance.size()); 936 distance.push_back(0); 937 Q.push(w); 938 } 939 } 940 } else { // update the distance and add in the adjacent vertices to Q 941 distance[u] = dist + 1; 942 for (const auto e : make_iterator_range(out_edges(u, G))) { 943 Q.push(target(e, G)); 944 } 945 } 946 } 947 if (Q.empty()) { 948 break; 949 } 950 } 883 951 return G; 884 952 } … … 890 958 **  */ 891 959 bool BooleanReassociationPass::redistributeAST(PabloBlock & block, Graph & G) const { 892 using TypeId = PabloAST::ClassTypeId;893 894 960 bool anyChanges = false; 895 896 961 for (;;) { 897 962 … … 963 1028 } 964 1029 965 const VertexSets distributionSets = safeDistributionSets(segmentInto3LevelGraph(H)); 1030 printGraph(block, H, G, "H0"); 1031 1032 segmentInto3LevelGraph(H); 1033 1034 printGraph(block, H, G, "H1"); 1035 1036 const VertexSets distributionSets = safeDistributionSets(H); 1037 1038 printGraph(block, H, G, "H2"); 966 1039 967 1040 // If no sources remain, no bicliques were found that would have a meaningful impact on the AST. … … 1018 1091 anyChanges = true; 1019 1092 } 1020 1021 1093 return anyChanges; 1022 1094 }
Note: See TracChangeset
for help on using the changeset viewer.