 Timestamp:
 Sep 2, 2015, 4:39:39 PM (4 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

icGREP/icgrepdevel/icgrep/pablo/optimizers/booleanreassociationpass.cpp
r4754 r4756 4 4 #include <boost/circular_buffer.hpp> 5 5 #include <boost/graph/adjacency_list.hpp> 6 #include <boost/graph/filtered_graph.hpp> 6 7 #include <boost/graph/topological_sort.hpp> 7 8 #include <pablo/optimizers/pablo_simplifier.hpp> 9 #include <algorithm> 8 10 #include <queue> 11 #include <set> 9 12 #include <iostream> 10 13 #include <pablo/printer_pablos.h> … … 19 22 using Vertex = Graph::vertex_descriptor; 20 23 using VertexQueue = circular_buffer<Vertex>; 21 using Map = std::unordered_map<PabloAST *, Vertex>;24 using Map = BooleanReassociationPass::Map; 22 25 using EdgeQueue = std::queue<std::pair<Vertex, Vertex>>; 23 24 static void redistributeAST(PabloBlock &block, Graph & G);25 26 26 27 /**  * … … 167 168 * @brief getVertex 168 169 **  */ 169 static inline Vertex getVertex(PabloAST * expr, Graph & G, Map & M) { 170 const auto f = M.find(expr); 170 template<typename ValueType, typename GraphType, typename MapType> 171 static inline Vertex getVertex(ValueType value, GraphType & G, MapType & M) { 172 const auto f = M.find(value); 171 173 if (f != M.end()) { 172 174 return f>second; 173 175 } 174 const auto u = add_vertex( expr, G);175 M.insert(std::make_pair( expr, u));176 const auto u = add_vertex(value, G); 177 M.insert(std::make_pair(value, u)); 176 178 return u; 177 179 } … … 204 206 * @brief printGraph 205 207 **  */ 206 static void printGraph(PabloBlock & block, const Graph & G ) {208 static void printGraph(PabloBlock & block, const Graph & G, const std::string name) { 207 209 raw_os_ostream out(std::cerr); 208 out << "digraph G{\n";210 out << "digraph " << name << " {\n"; 209 211 for (auto u : make_iterator_range(vertices(G))) { 210 212 out << "v" << u << " [label=\""; … … 235 237 } 236 238 237 out << "{ rank=same;"; 238 for (auto u : make_iterator_range(vertices(G))) { 239 if (in_degree(u, G) == 0 && out_degree(u, G) != 0) { 240 out << " v" << u; 241 } 242 } 243 out << "}\n"; 244 245 out << "{ rank=same;"; 246 for (auto u : make_iterator_range(vertices(G))) { 247 if (out_degree(u, G) == 0 && in_degree(u, G) != 0) { 248 out << " v" << u; 249 } 250 } 251 out << "}\n"; 239 if (num_vertices(G) > 0) { 240 241 out << "{ rank=same;"; 242 for (auto u : make_iterator_range(vertices(G))) { 243 if (in_degree(u, G) == 0 && out_degree(u, G) != 0) { 244 out << " v" << u; 245 } 246 } 247 out << "}\n"; 248 249 out << "{ rank=same;"; 250 for (auto u : make_iterator_range(vertices(G))) { 251 if (out_degree(u, G) == 0 && in_degree(u, G) != 0) { 252 out << " v" << u; 253 } 254 } 255 out << "}\n"; 256 257 } 252 258 253 259 out << "}\n\n"; … … 256 262 257 263 /**  * 264 * @brief printGraph 265 **  */ 266 template<typename SubgraphType> 267 static void printGraph(PabloBlock & block, const SubgraphType & S, const Graph & G, const std::string name) { 268 raw_os_ostream out(std::cerr); 269 out << "digraph " << name << " {\n"; 270 for (auto u : make_iterator_range(vertices(S))) { 271 out << "v" << u << " [label=\""; 272 PabloAST * expr = G[S[u]]; 273 if (isa<Statement>(expr)) { 274 if (LLVM_UNLIKELY(isa<If>(expr))) { 275 out << "If "; 276 PabloPrinter::print(cast<If>(expr)>getOperand(0), out); 277 out << ":"; 278 } else if (LLVM_UNLIKELY(isa<While>(expr))) { 279 out << "While "; 280 PabloPrinter::print(cast<While>(expr)>getOperand(0), out); 281 out << ":"; 282 } else { 283 PabloPrinter::print(cast<Statement>(expr), "", out); 284 } 285 } else { 286 PabloPrinter::print(expr, out); 287 } 288 out << "\""; 289 if (!inCurrentBlock(expr, block)) { 290 out << " style=dashed"; 291 } 292 out << "];\n"; 293 } 294 for (auto e : make_iterator_range(edges(S))) { 295 out << "v" << source(e, S) << " > v" << target(e, S) << ";\n"; 296 } 297 298 if (num_vertices(S) > 0) { 299 300 out << "{ rank=same;"; 301 for (auto u : make_iterator_range(vertices(S))) { 302 if (in_degree(u, S) == 0 && out_degree(u, S) != 0) { 303 out << " v" << u; 304 } 305 } 306 out << "}\n"; 307 308 out << "{ rank=same;"; 309 for (auto u : make_iterator_range(vertices(S))) { 310 if (out_degree(u, S) == 0 && in_degree(u, S) != 0) { 311 out << " v" << u; 312 } 313 } 314 out << "}\n"; 315 316 } 317 318 out << "}\n\n"; 319 out.flush(); 320 } 321 322 /**  * 258 323 * @brief processScope 259 324 **  */ … … 261 326 262 327 Graph G; 263 summarizeAST(block, std::move(terminals), G); 328 329 summarizeAST(block, terminals, G); 264 330 redistributeAST(block, G); 265 331 266 267 268 269 printGraph(block, G); 332 // for (;;) { 333 // summarizeAST(block, terminals, G); 334 // if (redistributeAST(block, G)) { 335 // G.clear(); 336 // } else { 337 // break; 338 // } 339 // } 340 341 printGraph(block, G, "G"); 270 342 271 343 } … … 275 347 * 276 348 * This function scans through a basic block (starting by its terminals) and computes a DAG in which any sequences 277 * of AND, OR or XOR functions are "flattened" and allowed to have any number of inputs.This allows us to349 * of AND, OR or XOR functions are "flattened" (i.e., allowed to have any number of inputs.) This allows us to 278 350 * reassociate them in the most efficient way possible. 279 351 **  */ 280 void BooleanReassociationPass::summarizeAST(PabloBlock & block, std::vector<Statement *> && terminals, Graph & G) { 281 282 Map M; 352 void BooleanReassociationPass::summarizeAST(PabloBlock & block, std::vector<Statement *> terminals, Graph & G) const { 353 283 354 VertexQueue Q(128); 284 355 EdgeQueue E; 356 Map M; 285 357 286 358 for (;;) { … … 542 614 } 543 615 616 using VertexSet = std::vector<Vertex>; 617 using VertexSets = std::set<VertexSet>; 618 619 /**  * 620 * @brief mica 621 * 622 * Adaptation of the MICA algorithm as described in "Consensus algorithms for the generation of all maximal 623 * bicliques" by Alexe et. al. (2003). Note: this implementation considers all verticies with an indegree of 0 624 * to be in bipartition A and their adjacencies to be in bipartition B. Because we do not care about the rank 1 625 * (star) cliques, this does not record them. 626 **  */ 627 static std::vector<VertexSet> mica(const Graph & G) { 628 629 VertexSets B1; 630 for (auto u : make_iterator_range(vertices(G))) { 631 if (in_degree(u, G) == 0) { 632 VertexSet B; 633 B.reserve(out_degree(u, G)); 634 for (auto e : make_iterator_range(out_edges(u, G))) { 635 B.push_back(target(e, G)); 636 } 637 std::sort(B.begin(), B.end()); // note: these already ought to be in order 638 B1.insert(std::move(B)); 639 } 640 } 641 642 VertexSets Bi; 643 644 VertexSet clique; 645 for (auto i = B1.begin(); i != B1.end(); ++i) { 646 for (auto j = i; ++j != B1.end(); ) { 647 std::set_intersection(i>begin(), i>end(), j>begin(), j>end(), std::back_inserter(clique)); 648 if (clique.size() > 0) { 649 Bi.insert(clique); 650 clique.clear(); 651 } 652 } 653 } 654 655 VertexSets C; 656 657 for (;;) { 658 if (Bi.empty()) { 659 break; 660 } 661 C.insert(Bi.begin(), Bi.end()); 662 663 VertexSets Bk; 664 for (auto i = B1.begin(); i != B1.end(); ++i) { 665 for (auto j = Bi.begin(); j != Bi.end(); ++j) { 666 std::set_intersection(i>begin(), i>end(), j>begin(), j>end(), std::back_inserter(clique)); 667 if (clique.size() > 0) { 668 if (C.count(clique) == 0) { 669 Bk.insert(clique); 670 } 671 clique.clear(); 672 } 673 } 674 } 675 Bi.swap(Bk); 676 } 677 678 return std::vector<VertexSet>(C.begin(), C.end()); 679 } 680 681 /**  * 682 * @brief areNonDisjoint 683 **  */ 684 template <class Type> 685 inline bool areNonDisjoint(const Type & A, const Type & B) { 686 auto first1 = A.begin(), last1 = A.end(); 687 auto first2 = B.begin(), last2 = B.end(); 688 while (first1 != last1 && first2 != last2) { 689 if (*first1 < *first2) { 690 ++first1; 691 } else if (*first2 < *first1) { 692 ++first2; 693 } else { 694 return true; 695 } 696 } 697 return false; 698 } 699 700 /**  * 701 * @brief maximalIndependentSet 702 **  */ 703 static void maximalIndependentSet(std::vector<VertexSet> & V) { 704 using IndependentSetGraph = adjacency_list<hash_setS, vecS, undirectedS, unsigned>; 705 const auto l = V.size(); 706 IndependentSetGraph I(l); 707 // Initialize our weights 708 for (unsigned i = 0; i != l; ++i) { 709 I[i] = std::pow(V[i].size(), 2); 710 } 711 // Determine our constraints 712 for (unsigned i = 0; i != l; ++i) { 713 for (unsigned j = i + 1; j != l; ++j) { 714 if (areNonDisjoint(V[i], V[j])) { 715 add_edge(i, j, I); 716 } 717 } 718 } 719 // Use the greedy algorithm to choose our independent set (TODO: try the similar randomized approach) 720 std::vector<Vertex> selected; 721 722 std::vector<bool> ignored(l, false); 723 for (;;) { 724 unsigned w = 0; 725 Vertex u = 0; 726 for (unsigned i = 0; i != l; ++i) { 727 if (!ignored[i] && I[i] > w) { 728 w = I[i]; 729 u = i; 730 } 731 } 732 if (w < 2) break; 733 selected.push_back(u); 734 ignored[u] = true; 735 for (auto v : make_iterator_range(adjacent_vertices(u, I))) { 736 ignored[v] = true; 737 } 738 } 739 740 // Sort the selected list and then remove the unselected sets from V 741 std::sort(selected.begin(), selected.end(), std::greater<unsigned>()); 742 auto end = V.end(); 743 for (const unsigned offset : selected) { 744 end = V.erase(V.begin() + offset + 1, end)  1; 745 } 746 V.erase(V.begin(), end); 747 748 } 749 750 751 /**  * 752 * @brief maximalIndependentBicliqueSet 753 **  */ 754 static void maximalIndependentBicliqueSet(Graph & G) { 755 // First enumerate our bicliques in G. 756 auto R = mica(G); 757 // 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. These 759 // have to be resolved specially later. 760 maximalIndependentSet(R); 761 // Update G to reflect our maximal independent biclique set 762 std::vector<VertexSet> L; 763 for (const VertexSet & B : R) { 764 // Compute our A set 765 VertexSet A; 766 auto bi = B.begin(); 767 A.reserve(in_degree(*bi, G)); 768 for (auto e : make_iterator_range(in_edges(*bi, G))) { 769 A.push_back(source(e, G)); 770 } 771 std::sort(A.begin(), A.end()); 772 while (++bi != B.end()) { 773 VertexSet Ai; 774 Ai.reserve(in_degree(*bi, G)); 775 for (auto e : make_iterator_range(in_edges(*bi, G))) { 776 Ai.push_back(source(e, G)); 777 } 778 std::sort(Ai.begin(), Ai.end()); 779 VertexSet Ak; 780 std::set_intersection(A.begin(), A.end(), Ai.begin(), Ai.end(), std::back_inserter(Ak)); 781 A.swap(Ak); 782 } 783 L.emplace_back(std::move(A)); 784 } 785 for (auto u : make_iterator_range(vertices(G))) { 786 if (in_degree(u, G) == 0) { 787 clear_out_edges(u, G); 788 } 789 } 790 for (unsigned i = 0; i != R.size(); ++i) { 791 for (auto u : L[i]) { 792 for (auto v : R[i]) { 793 add_edge(u, v, G); 794 } 795 } 796 } 797 } 798 544 799 /**  * 545 800 * @brief redistributeAST … … 547 802 * Apply the distribution law to reduce computations whenever possible. 548 803 **  */ 549 static void redistributeAST(PabloBlock & block, Graph & G){804 bool BooleanReassociationPass::redistributeAST(PabloBlock & block, Graph & G) const { 550 805 using TypeId = PabloAST::ClassTypeId; 551 806 552 // Process the graph in reverse topological order so that we end up recursively applying the distribution law 553 // to the entire AST. 554 std::vector<unsigned> ordering; 555 ordering.reserve(num_vertices(G)); 556 topological_sort(G, std::back_inserter(ordering)); 557 558 for (const Vertex u : ordering) { 807 Graph B; 808 Map M; 809 810 for (const Vertex u : make_iterator_range(vertices(G))) { 559 811 const TypeId outerTypeId = G[u]>getClassTypeId(); 560 812 if (outerTypeId == TypeId::And  outerTypeId == TypeId::Or) { 561 813 if (inCurrentBlock(cast<Statement>(G[u]), block)) { 562 814 const TypeId innerTypeId = (outerTypeId == TypeId::And) ? TypeId::Or : TypeId::And; 563 564 Graph H;565 Map M;566 567 815 flat_set<Vertex> distributable; 568 569 816 for (auto e : make_iterator_range(in_edges(u, G))) { 570 817 const Vertex v = source(e, G); 571 818 if (G[v]>getClassTypeId() == innerTypeId && inCurrentBlock(cast<Statement>(G[v]), block)) { 572 819 bool safe = true; 573 // This operation is safe to transform if all of its users are AND or OR instructions. 574 if (out_degree(v, G) > 1) { 575 for (auto e : make_iterator_range(out_edges(v, G))) { 576 const PabloAST * expr = G[target(e, G)]; 577 if (expr>getClassTypeId() != TypeId::And && expr>getClassTypeId() != TypeId::Or) { 578 safe = false; 579 break; 580 } 820 for (PabloAST * user : G[v]>users()) { 821 if (user>getClassTypeId() != outerTypeId) { 822 safe = false; 823 break; 581 824 } 582 825 } … … 586 829 } 587 830 } 588 589 if (distributable.size() > 1) { 590 flat_map<Vertex, unsigned> sources; 591 bool canRedistribute = false; 831 if (LLVM_LIKELY(distributable.size() > 1)) { 832 // We're only interested in computing a subgraph of G in which every source has an outdegree 833 // greater than 1. Otherwise we'd only end up permuting the AND/OR sequence with no logical 834 // benefit. (Note: this does not consider register pressure / liveness.) 835 flat_map<Vertex, unsigned> observed; 836 bool anyOpportunities = false; 592 837 for (const Vertex v : distributable) { 593 838 for (auto e : make_iterator_range(in_edges(v, G))) { 594 839 const Vertex w = source(e, G); 595 const auto f = sources.find(w);596 if (f == sources.end()) {597 sources.emplace(w, 1);840 const auto f = observed.find(w); 841 if (f == observed.end()) { 842 observed.emplace(w, 0); 598 843 } else { 599 844 f>second += 1; 600 canRedistribute= true;845 anyOpportunities = true; 601 846 } 602 847 } 603 848 } 604 if (canRedistribute) { 605 Vertex w = 0; 606 unsigned count = 0; 607 const Vertex x = getVertex(G[u], H, M); 608 for (auto s : sources) { 609 std::tie(w, count) = s; 610 if (count > 1) { 611 const Vertex z = getVertex(G[w], H, M); 612 for (auto e : make_iterator_range(out_edges(w, G))) { 613 const Vertex v = target(e, G); 614 if (distributable.count(v)) { 615 const Vertex y = getVertex(G[v], H, M); 616 add_edge(y, x, H); 617 add_edge(z, y, H); 849 if (anyOpportunities) { 850 for (auto ob : observed) { 851 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); 618 857 } 619 858 } … … 622 861 } 623 862 } 624 625 printGraph(block, H); 626 } 627 } 628 } 629 630 631 632 633 634 } 635 636 /**  * 637 * @brief applyDistributionLaw 638 **  */ 639 BooleanReassociationPass::BooleanReassociationPass() { } 640 641 642 } 863 } 864 } 865 } 866 867 // If we found no potential opportunities then we cannot apply the distribution law to any part of G. 868 if (num_vertices(B) == 0) { 869 return false; 870 } 871 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"); 880 881 882 883 return true; 884 } 885 886 }
Note: See TracChangeset
for help on using the changeset viewer.