Changeset 4959 for icGREP/icgrepdevel/icgrep/pablo/optimizers
 Timestamp:
 Mar 7, 2016, 3:37:30 PM (3 years ago)
 Location:
 icGREP/icgrepdevel/icgrep/pablo/optimizers
 Files:

 3 edited
Legend:
 Unmodified
 Added
 Removed

icGREP/icgrepdevel/icgrep/pablo/optimizers/pablo_automultiplexing.cpp
r4942 r4959 166 166 bool MultiplexingPass::optimize(PabloFunction & function, const bool independent) { 167 167 168 if (LLVM_UNLIKELY(Samples < 1)) { 169 return false; 170 } 171 172 168 173 LOG("Seed: " << Seed); 169 174 … … 395 400 for (unsigned j = 0; j < i; ++j) { 396 401 if (G(i, j)) { 397 add_edge(j, i, mConstraintGraph);402 add_edge(j, i, true, mConstraintGraph); 398 403 } 399 404 } 400 405 for (unsigned j = i + 1; j < advances; ++j) { 401 406 if (G(i, j)) { 402 add_edge(j, i, mConstraintGraph);407 add_edge(j, i, true, mConstraintGraph); 403 408 } 404 409 } … … 607 612 608 613 BDD Ak = bdd_ithvar(mVariables++); 609 const BDD Nk = bdd_addref(bdd_not(Ak)); 614 const BDD Nk = bdd_addref(bdd_not(Ak)); 610 615 for (unsigned i = 0; i != k; ++i) { 611 616 if (unconstrained[i]) { … … 627 632 } 628 633 } 629 add_edge(i, k, mConstraintGraph);634 add_edge(i, k, false, mConstraintGraph); 630 635 } 631 636 // To minimize the number of BDD computations, we store the negated variable instead of negating it each time. … … 639 644 inline bool MultiplexingPass::independent(const ConstraintVertex i, const ConstraintVertex j) const { 640 645 assert (i < num_vertices(mConstraintGraph) && j < num_vertices(mConstraintGraph)); 641 return (mConstraintGraph.get_edge(i, j) == 0);646 return mConstraintGraph.get_edge(i, j).first == false; 642 647 } 643 648 … … 719 724 mCandidateGraph = CandidateGraph(num_vertices(mConstraintGraph)); 720 725 721 for (unsigned iteration = 0; iteration < Samples; ++iteration) {726 for (unsigned r = Samples; r; r) { 722 727 723 728 // Push all source nodes into the (initial) independent set S … … 768 773 } 769 774 775 #ifdef PRINT_DEBUG_OUTPUT 776 const auto n = num_vertices(mConstraintGraph); 777 const auto m = num_vertices(mCandidateGraph); 778 unsigned sets = 0; 779 for (auto i = n; i < m; ++i) { 780 if (degree(i, mCandidateGraph) > 0) { 781 ++sets; 782 } 783 } 784 LOG("Unique Candidate Sets: " << (sets)); 785 #endif 786 770 787 return num_vertices(mCandidateGraph) > num_vertices(mConstraintGraph); 771 788 } … … 912 929 const size_t n = num_vertices(mCandidateGraph)  m; 913 930 914 degree_t remaining[n]; 915 vertex_t chosen_set[m]; 916 917 for (unsigned i = 0; i != n; ++i) { 918 remaining[i] = degree(i + m, mCandidateGraph); 919 } 920 for (unsigned i = 0; i != m; ++i) { 921 chosen_set[i] = 0; 922 } 931 std::vector<bool> chosen(n, false); 923 932 924 933 for (;;) { 925 934 926 935 // Choose the set with the greatest number of vertices not already included in some other set. 927 vertex_t k= 0;936 vertex_t u = 0; 928 937 degree_t w = 0; 929 938 for (vertex_t i = 0; i != n; ++i) { 930 degree_t r = remaining[i]; 931 if (r > 2) { // if this set has at least 3 elements. 939 if (chosen[i]) continue; 940 const auto t = i + m; 941 degree_t r = degree(t, mCandidateGraph); 942 if (LLVM_LIKELY(r >= 3)) { // if this set has at least 3 elements. 932 943 r *= r; 933 944 AdjIterator begin, end; 934 std::tie(begin, end) = adjacent_vertices( i + m, mCandidateGraph);945 std::tie(begin, end) = adjacent_vertices(t, mCandidateGraph); 935 946 for (auto ei = begin; ei != end; ++ei) { 936 947 for (auto ej = ei; ++ej != end; ) { … … 941 952 } 942 953 if (w < r) { 943 k = i;954 u = t; 944 955 w = r; 945 956 } 957 } else if (r) { 958 clear_vertex(t, mCandidateGraph); 946 959 } 947 960 } 948 961 949 962 // Multiplexing requires 3 or more elements; if no set contains at least 3, abort. 950 if ( w == 0) {963 if (LLVM_UNLIKELY(w == 0)) { 951 964 break; 952 965 } 953 966 954 for (const auto u : make_iterator_range(adjacent_vertices(k + m, mCandidateGraph))) { 955 if (chosen_set[u] == 0) { 956 chosen_set[u] = (k + m); 957 for (const auto v : make_iterator_range(adjacent_vertices(u, mCandidateGraph))) { 958 assert (v >= m); 959 remaining[v  m]; 960 } 961 } 962 } 963 964 assert (remaining[k] == 0); 967 chosen[u  m] = true; 965 968 966 969 // If this contains 2^n elements for any n, discard the member that is most likely to be added 967 970 // to some future set. 968 if (LLVM_UNLIKELY(is_power_of_2( w))) {969 vertex_t j= 0;971 if (LLVM_UNLIKELY(is_power_of_2(degree(u, mCandidateGraph)))) { 972 vertex_t x = 0; 970 973 degree_t w = 0; 971 for (vertex_t i = 0; i != m; ++i) { 972 if (chosen_set[i] == (k + m)) { 973 degree_t r = 1; 974 for (const auto u : make_iterator_range(adjacent_vertices(i, mCandidateGraph))) { 975 // strongly prefer adding weight to unvisited sets that have more remaining vertices 976 r += std::pow(remaining[u  m], 2); 977 } 978 if (w < r) { 979 j = i; 980 w = r; 981 } 982 } 983 } 984 assert (w > 0); 985 chosen_set[j] = 0; 986 for (const auto u : make_iterator_range(adjacent_vertices(j, mCandidateGraph))) { 987 assert (u >= m); 988 remaining[u  m]++; 989 } 990 } 991 992 // If Samples > 1 then our candidate sets were generated by more than one traversal through the constraint graph. 993 // Sets generated by differing traversals may generate a cycle in the AST if multiplex even when they are not 994 // multiplexed together. For example, 995 996 // Assume we're multiplexing set {A,B,C} and {D,E,F} and that no constraint exists between any nodes in 997 // either set. If A is dependent on D and E is dependent on B, multiplexing both sets would result in a cycle 998 // in the AST. To fix this, we'd have to remove A, D, B or E. 999 1000 // This cannot occur with only one traversal (or between sets generated by the same traversal) because of the 1001 // DAG traversal strategy used in "generateCandidateSets". 1002 1003 1004 } 1005 1006 for (unsigned i = 0; i != m; ++i) { 1007 AdjIterator ei, ei_end; 1008 std::tie(ei, ei_end) = adjacent_vertices(i, mCandidateGraph); 1009 for (auto next = ei; ei != ei_end; ei = next) { 1010 ++next; 1011 if (*ei != chosen_set[i]) { 1012 remove_edge(i, *ei, mCandidateGraph); 1013 } 974 for (const auto v : make_iterator_range(adjacent_vertices(u, mCandidateGraph))) { 975 if (degree(v, mCandidateGraph) > w) { 976 x = v; 977 w = degree(v, mCandidateGraph); 978 } 979 } 980 remove_edge(u, x, mCandidateGraph); 981 } 982 983 AdjIterator begin, end; 984 std::tie(begin, end) = adjacent_vertices(u, mCandidateGraph); 985 for (auto vi = begin; vi != end; ) { 986 const auto v = *vi++; 987 clear_vertex(v, mCandidateGraph); 988 add_edge(v, u, mCandidateGraph); 989 } 990 991 if (Samples > 1) { 992 removePotentialCycles(u); 1014 993 } 1015 994 } … … 1060 1039 1061 1040 1041 } 1042 1043 /**  * 1044 * @brief removePotentialCycles 1045 * 1046 * If Samples > 1, our candidate sets were generated by more than one traversal through the constraint DAG. 1047 * Multiplexing disjoint sets generated by differing traversals can induce a cycle in the AST. For example, 1048 * suppose sets {A,B} and {C,D} and A is dependent on C and D on B; multiplexing both will result in a cycle. 1049 * 1050 * Eliminating all potential cycles will likely lead to the removal of many candidate sets. Instead we "fix" 1051 * the candidate sets after the selection of a particular candidate set. 1052 **  */ 1053 void MultiplexingPass::removePotentialCycles(const CandidateGraph::vertex_descriptor i) { 1054 1055 using AdjIterator = graph_traits<CandidateGraph>::adjacency_iterator; 1056 1057 const auto m = num_vertices(mConstraintGraph); 1058 const auto n = num_vertices(mCandidateGraph); 1059 1060 // Suppose we construct a graph G that indicates whether selecting candidate set V will induce a cycle, given 1061 // that we've already chosen candidate set U. This can occur here only because some elements of V are dependent 1062 // on U and vice versa. 1063 1064 // We want the minimal minimum weight feedback arc set of G; however, we also know any edge will either have 1065 // 1066 1067 for (auto j = m; j < n; ++j) { 1068 if (LLVM_UNLIKELY(i == j)) continue; 1069 AdjIterator begin, end; 1070 std::tie(begin, end) = adjacent_vertices(j, mCandidateGraph); 1071 for (auto ui = begin; ui != end; ) { 1072 const auto u = *ui++; 1073 unsigned outgoing = 0; 1074 unsigned incoming = 0; 1075 for (auto v : make_iterator_range(adjacent_vertices(i, mCandidateGraph))) { 1076 if (dependent(u, v)) { 1077 ++outgoing; 1078 } else if (dependent(v, u)) { 1079 ++incoming; 1080 } 1081 } 1082 if (LLVM_UNLIKELY(outgoing > 0 && incoming > 0)) { 1083 remove_edge(j, u, mCandidateGraph); 1084 } 1085 } 1086 } 1087 } 1088 1089 /**  * 1090 * @brief dependent 1091 **  */ 1092 inline bool MultiplexingPass::dependent(const ConstraintVertex i, const ConstraintVertex j) const { 1093 const auto e = mConstraintGraph.get_edge(i, j); 1094 return (e.second && e.first); 1062 1095 } 1063 1096 … … 1267 1300 work = 2; 1268 1301 break; 1269 //case TypeId::Not:1302 case TypeId::Not: 1270 1303 case TypeId::Assign: 1271 1304 case TypeId::Next: … … 1366 1399 bool ready = true; 1367 1400 const auto v = target(ei, G); 1401 assert (rank[v] != 0); 1368 1402 for (auto ej : make_iterator_range(in_edges(v, G))) { 1369 1403 if (rank[source(ej, G)] != 0) { … … 1373 1407 } 1374 1408 if (ready) { 1375 assert (rank[v] != 0);1376 1409 readySet.insert(std::lower_bound(readySet.begin(), readySet.end(), v, by_nonincreasing_rank), v); 1377 1410 assert (std::is_sorted(readySet.cbegin(), readySet.cend(), by_nonincreasing_rank)); … … 1606 1639 1607 1640 #ifndef NDEBUG 1608 std::vector< typename Graph::vertex_descriptor> nothing;1641 std::vector<Vertex> nothing; 1609 1642 topological_sort(G, std::back_inserter(nothing)); 1610 1643 #endif 
icGREP/icgrepdevel/icgrep/pablo/optimizers/pablo_automultiplexing.hpp
r4937 r4959 25 25 using CharacterizationMap = llvm::DenseMap<const PabloAST *, BDD>; 26 26 27 using ConstraintGraph = boost::adjacency_matrix<boost::directedS >;27 using ConstraintGraph = boost::adjacency_matrix<boost::directedS, boost::no_property, bool>; 28 28 using ConstraintVertex = ConstraintGraph::vertex_descriptor; 29 29 using Constraints = std::vector<ConstraintVertex>; … … 42 42 43 43 using AdvanceVector = std::vector<Advance *>; 44 using Advance Depth= std::vector<int>;44 using AdvanceRank = std::vector<int>; 45 45 using AdvanceVariable = std::vector<BDD>; 46 46 … … 78 78 void selectMultiplexSetsWorkingSet(); 79 79 80 void removePotentialCycles(const CandidateGraph::vertex_descriptor u); 81 bool dependent(const ConstraintVertex i, const ConstraintVertex j) const; 82 80 83 void eliminateSubsetConstraints(); 81 84 void doTransitiveReductionOfSubsetGraph(); … … 109 112 ConstraintGraph mConstraintGraph; 110 113 AdvanceVector mAdvance; 111 Advance DepthmAdvanceRank;114 AdvanceRank mAdvanceRank; 112 115 AdvanceVariable mAdvanceNegatedVariable; 113 116 SubsetGraph mSubsetGraph; 114 117 CliqueGraph mUsageGraph; 115 CandidateGraph mCandidateGraph;118 CandidateGraph mCandidateGraph; 116 119 }; 117 120 
icGREP/icgrepdevel/icgrep/pablo/optimizers/pablo_simplifier.cpp
r4937 r4959 525 525 526 526 /**  * 527 * @brief unused 528 **  */ 529 inline static bool unused(const Statement * const stmt) { 530 if (LLVM_UNLIKELY(stmt>getNumUses() == 0)) { 531 // TODO: prototypes ought to state whether they have side effects. 532 if (LLVM_UNLIKELY(isa<Call>(stmt) && cast<Call>(stmt)>getPrototype()>getNumOfResults() == 0)) { 533 return false; 534 } 535 return true; 536 } 537 return false; 538 } 539 540 /**  * 527 541 * @brief deadCodeElimination 528 542 **  */ … … 530 544 Statement * stmt = block>front(); 531 545 while (stmt) { 532 if ( isa<If>(stmt)) {546 if (LLVM_UNLIKELY(isa<If>(stmt))) { 533 547 deadCodeElimination(cast<If>(stmt)>getBody()); 534 } else if ( isa<While>(stmt)) {548 } else if (LLVM_UNLIKELY(isa<While>(stmt))) { 535 549 deadCodeElimination(cast<While>(stmt)>getBody()); 536 } else if ( stmt>getNumUses() == 0){550 } else if (LLVM_UNLIKELY(unused(stmt))){ 537 551 stmt = stmt>eraseFromParent(true); 538 552 continue; … … 562 576 if (LLVM_UNLIKELY(op>getNumUses() == 1)) { 563 577 adv>setOperand(0, op>getOperand(0)); 564 adv>setOperand(1, block>getInteger(adv>getA dvanceAmount() + op>getAdvanceAmount()));578 adv>setOperand(1, block>getInteger(adv>getAmount() + op>getAmount())); 565 579 op>eraseFromParent(false); 566 580 } … … 573 587 if (LLVM_UNLIKELY(op>getNumUses() == 1)) { 574 588 block>setInsertPoint(scanThru>getPrevNode()); 575 PabloAST * expr = block>createAdvance(op>getOperand(0), op>getA dvanceAmount()  1);589 PabloAST * expr = block>createAdvance(op>getOperand(0), op>getAmount()  1); 576 590 scanThru>setOperand(0, expr); 577 591 scanThru>setOperand(1, block>createOr(scanThru>getOperand(1), expr));
Note: See TracChangeset
for help on using the changeset viewer.