 Timestamp:
 Aug 21, 2015, 4:12:09 PM (4 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

icGREP/icgrepdevel/icgrep/pablo/optimizers/pablo_automultiplexing.cpp
r4728 r4736 160 160 LOG("SelectedIndependentSets: " << (end_select_independent_sets  start_select_independent_sets)); 161 161 162 BooleanReassociationPass::optimize(function); 163 162 164 RECORD_TIMESTAMP(start_topological_sort); 163 165 am.topologicalSort(function.getEntryBlock()); … … 165 167 LOG("TopologicalSort (1): " << (end_topological_sort  start_topological_sort)); 166 168 167 BDDMinimizationPass::optimize(function, true);169 BDDMinimizationPass::optimize(function, false); 168 170 } 169 171 170 172 LOG_NUMBER_OF_ADVANCES(function.getEntryBlock()); 171 172 173 return multiplex; 173 174 } … … 645 646 } 646 647 648 assert (S.size() > 0); 649 647 650 auto remainingVerticies = num_vertices(mConstraintGraph)  S.size(); 648 651 … … 653 656 bool noNewElements = true; 654 657 do { 658 assert (S.size() > 0); 655 659 // Randomly choose a vertex in S and discard it. 656 660 const auto i = S.begin() + IntDistribution(0, S.size()  1)(rng); 657 const ConstraintVertex u = *i;658 S.erase(i);659 remainingVerticies;661 assert (i != S.end()); 662 const ConstraintVertex u = *i; 663 S.erase(i); 660 664 661 665 for (auto e : make_iterator_range(out_edges(u, mConstraintGraph))) { … … 663 667 if ((D[v]) == 0) { 664 668 S.push_back(v); 669 remainingVerticies; 665 670 noNewElements = false; 666 671 } … … 851 856 graph_traits<MultiplexSetGraph>::out_edge_iterator ei, ei_end; 852 857 // For each member of a "set vertex" ... 853 std::tie(ei, ei_end) = out_edges(i, mMultiplexSetGraph); 854 for (; ei != ei_end; ++ei) { 855 const auto s = source(*ei, mMultiplexSetGraph); 858 for (auto e : make_iterator_range(out_edges(i, mMultiplexSetGraph))) { 859 const auto s = source(e, mMultiplexSetGraph); 856 860 if (out_degree(s, mMultiplexSetGraph) != 0) { 857 861 // First scan through the subgraph of vertices in M dominated by s and build up the set T, … … 942 946 void AutoMultiplexing::multiplexSelectedIndependentSets() { 943 947 944 const unsigned f = num_vertices(mConstraintGraph);945 const unsigned l = num_vertices(mMultiplexSetGraph);948 const unsigned first_set = num_vertices(mConstraintGraph); 949 const unsigned last_set = num_vertices(mMultiplexSetGraph); 946 950 947 951 // Preallocate the structures based on the size of the largest multiplex set 948 952 size_t max_n = 3; 949 for (unsigned s = f; s != l; ++s) {950 max_n = std::max<unsigned>(max_n, out_degree( s, mMultiplexSetGraph));953 for (unsigned idx = first_set; idx != last_set; ++idx) { 954 max_n = std::max<unsigned>(max_n, out_degree(idx, mMultiplexSetGraph)); 951 955 } 952 956 … … 956 960 // relationships of our independent sets. 957 961 958 for (unsigned s = f; s != l; ++s) {959 const size_t n = out_degree( s, mMultiplexSetGraph);962 for (unsigned idx = first_set; idx != last_set; ++idx) { 963 const size_t n = out_degree(idx, mMultiplexSetGraph); 960 964 if (n) { 961 965 const size_t m = log2_plus_one(n); 962 966 Advance * input[n]; 963 Advance * muxed[m]; 967 Advance * muxed[m]; 964 968 965 969 unsigned i = 0; 966 for (const auto e : make_iterator_range(out_edges( s, mMultiplexSetGraph))) {970 for (const auto e : make_iterator_range(out_edges(idx, mMultiplexSetGraph))) { 967 971 input[i] = std::get<0>(mAdvance[target(e, mMultiplexSetGraph)]); 968 972 assert (input[i]); … … 980 984 981 985 std::ostringstream prefix; 982 prefix << "mux" << n << "to" << m << ' _';983 for (size_t i = 1; i <= n; ++i) {984 if (( i & (static_cast<size_t>(1)<< j)) != 0) {985 Q.push_back(input[i  1]>getOperand(0));986 prefix << "mux" << n << "to" << m << '.' << (j + 1); 987 for (size_t i = 0; i != n; ++i) { 988 if (((i + 1) & (1ULL << j)) != 0) { 989 Q.push_back(input[i]>getOperand(0)); 986 990 } 987 991 } … … 1000 1004 } 1001 1005 1002 /// Perform mton Demultiplexing 1003 for (size_t i = 1; i <= n; ++i) {1006 /// Perform mton Demultiplexing 1007 for (size_t i = 0; i != n; ++i) { 1004 1008 1005 1009 // Construct the demuxed values and replaces all the users of the original advances with them. 1006 1010 for (size_t j = 0; j != m; ++j) { 1007 if (( i& (1ULL << j)) == 0) {1011 if (((i + 1) & (1ULL << j)) == 0) { 1008 1012 Q.push_back(muxed[j]); 1009 1013 } … … 1023 1027 1024 1028 for (unsigned j = 0; j != m; ++j) { 1025 if (( i& (1ULL << j)) != 0) {1029 if (((i + 1) & (1ULL << j)) != 0) { 1026 1030 assert (!Q.full()); 1027 1031 Q.push_back(muxed[j]); … … 1037 1041 1038 1042 PabloAST * demuxed = Q.front(); Q.pop_front(); assert (demuxed); 1039 input[i  1]>replaceWith(demuxed, true, true);1043 input[i]>replaceWith(demuxed, true, true); 1040 1044 } 1041 1045 } … … 1059 1063 std::stack<Statement *> scope; 1060 1064 1065 raw_os_ostream out(std::cerr); 1066 1061 1067 for (Statement * stmt = entry.front(); ; ) { restart: 1062 1068 while ( stmt ) { 1063 1064 1069 for (unsigned i = 0; i != stmt>getNumOperands(); ++i) { 1065 1070 PabloAST * const op = stmt>getOperand(i); … … 1098 1103 } 1099 1104 1105 /**  * 1106 * @brief reassociate 1107 **  */ 1108 inline void AutoMultiplexing::reassociate(PabloBuilder & builder, PabloAST * const demuxed[], const unsigned n) const { 1109 using Graph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS, PabloAST *>; 1110 using Map = std::unordered_map<PabloAST *, Graph::vertex_descriptor>; 1111 using Queue = std::queue<Graph::vertex_descriptor>; 1112 using Or = pablo::Or; 1113 using And = pablo::And; 1114 1115 1116 flat_set<PabloAST *> initial_vars; 1117 1118 1119 std::queue<And *> andQ; 1120 for (unsigned i = 0; i != n; ++i) { 1121 for (PabloAST * user : demuxed[i]>users()) { 1122 if (isa<And>(user)) { 1123 andQ.push(cast<And>(user)); 1124 } else if (isa<Or>(user)) { 1125 initial_vars.insert(demuxed[i]); 1126 } 1127 } 1128 } 1129 1130 while (!andQ.empty()) { 1131 And * inst = andQ.front(); andQ.pop(); 1132 for (PabloAST * user : inst>users()) { 1133 if (isa<And>(user)) { 1134 andQ.push(cast<And>(user)); 1135 } else if (isa<Or>(user)) { 1136 initial_vars.insert(inst); 1137 } 1138 } 1139 } 1140 1141 Graph G; 1142 Map M; 1143 Queue Q; 1144 1145 // First insert the demuxed variables as our initial sources (as vertices 0 ... n1) 1146 for (PabloAST * inst : initial_vars) { 1147 M.insert(std::make_pair(inst, add_vertex(inst, G))); 1148 } 1149 1150 // Now add in the users of those demuxed variables 1151 for (PabloAST * inst : initial_vars) { 1152 const auto i = M[inst]; 1153 for (PabloAST * user : inst>users()) { 1154 const auto f = M.find(user); 1155 if (LLVM_LIKELY(f == M.end())) { 1156 const auto j = add_vertex(user, G); 1157 M.insert(std::make_pair(user, j)); 1158 add_edge(i, j, G); 1159 if (isa<Or>(user)) { 1160 Q.push(j); 1161 } 1162 } else { 1163 add_edge(i, f>second, G); 1164 } 1165 } 1166 } 1167 1168 // Now scan through the graph to locate any disjunctions and the final outputs 1169 while (!Q.empty()) { 1170 const auto u = Q.front(); Q.pop(); 1171 Or * expr = cast<Or>(G[u]); 1172 for (unsigned i = 0; i != 2; ++i) { 1173 PabloAST * op = expr>getOperand(i); 1174 const auto f = M.find(op); 1175 if (LLVM_UNLIKELY(f == M.end())) { 1176 const auto v = add_vertex(op, G); 1177 M.insert(std::make_pair(op, v)); 1178 add_edge(v, u, G); 1179 if (isa<Or>(op)) { 1180 Q.push(v); 1181 } 1182 } 1183 } 1184 for (PabloAST * user : expr>users()) { 1185 const auto f = M.find(user); 1186 if (LLVM_UNLIKELY(f == M.end())) { 1187 const auto v = add_vertex(user, G); 1188 M.insert(std::make_pair(user, v)); 1189 add_edge(u, v, G); 1190 if (isa<Or>(user)) { 1191 Q.push(v); 1192 } 1193 } else { 1194 add_edge(u, f>second, G); 1195 } 1196 } 1197 } 1198 1199 // Clean up the graph to remove any nondisjunctions and their dependencies 1200 for (auto u : make_iterator_range(vertices(G))) { 1201 if (in_degree(u, G) == 0  isa<Or>(G[u])) { 1202 continue; 1203 } 1204 clear_in_edges(u, G); 1205 for (;;) { 1206 for (auto e : make_iterator_range(out_edges(u, G))) { 1207 Q.push(target(e, G)); 1208 } 1209 clear_out_edges(u, G); 1210 if (Q.empty()) { 1211 break; 1212 } 1213 u = Q.front(); Q.pop(); 1214 } 1215 } 1216 1217 // Now determine the number of source variables 1218 unsigned m = 0; 1219 for (auto u : make_iterator_range(vertices(G))) { 1220 if (in_degree(u, G) == 0 && out_degree(u, G) > 0) { 1221 ++m; 1222 } 1223 } 1224 1225 1226 circular_buffer<PabloAST *> R(m); 1227 // And then which variables required to compute each disjunction 1228 for (const auto u : make_iterator_range(vertices(G))) { 1229 if (out_degree(u, G) == 0 && in_degree(u, G) > 0) { 1230 1231 std::vector<bool> visited(num_vertices(G), false); 1232 flat_set<Graph::vertex_descriptor> variables; 1233 for (auto v = u; ; ) { 1234 if (in_degree(v, G) == 0) { 1235 variables.insert(v); 1236 } else { 1237 for (auto e : make_iterator_range(in_edges(v, G))) { 1238 const auto w = source(e, G); 1239 if (!visited[w]) { 1240 Q.push(w); 1241 visited[w] = true; 1242 } 1243 } 1244 } 1245 if (Q.empty()) { 1246 break; 1247 } 1248 v = Q.front(); Q.pop(); 1249 } 1250 if (variables.size() > 3) { 1251 unsigned i = 0; 1252 for (auto j : variables) { 1253 for (; i < j; ++i) { 1254 R.push_back(builder.createZeroes()); 1255 } 1256 R.push_back(G[j]); 1257 } 1258 for (; i < m; ++i) { 1259 R.push_back(builder.createZeroes()); 1260 } 1261 while (R.size() > 1) { 1262 PabloAST * e1 = R.front(); R.pop_front(); 1263 PabloAST * e2 = R.front(); R.pop_front(); 1264 R.push_back(builder.createOr(e1, e2)); 1265 } 1266 Statement * stmt = cast<Statement>(G[u]); 1267 stmt>replaceAllUsesWith(R.front()); 1268 R.clear(); 1269 } 1270 } 1271 } 1272 1273 } 1274 1275 1100 1276 } // end of namespace pablo 1101 1277
Note: See TracChangeset
for help on using the changeset viewer.