 Timestamp:
 Jul 31, 2015, 5:26:50 PM (4 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

icGREP/icgrepdevel/icgrep/pablo/optimizers/pablo_automultiplexing.cpp
r4702 r4711 11 11 #include <llvm/ADT/BitVector.h> 12 12 #include <cudd.h> 13 #include <cuddInt.h> 13 14 #include <util.h> 14 15 #include <stack> 15 16 #include <queue> 16 17 #include <unordered_set> 17 18 #include <pablo/optimizers/pablo_simplifier.hpp>19 #include <pablo/optimizers/pablo_bddminimization.h>20 18 21 19 using namespace llvm; … … 135 133 LOG("GenerateMultiplexSets: " << (end_create_multiplex_graph  start_create_multiplex_graph)); 136 134 135 RECORD_TIMESTAMP(start_shutdown); 136 am.Shutdown(); 137 RECORD_TIMESTAMP(end_shutdown); 138 LOG("Shutdown: " << (end_shutdown  start_shutdown)); 139 137 140 if (multiplex) { 138 141 … … 148 151 149 152 RECORD_TIMESTAMP(start_select_independent_sets); 150 a uto multiplexedSets = am.multiplexSelectedIndependentSets();153 am.multiplexSelectedIndependentSets(); 151 154 RECORD_TIMESTAMP(end_select_independent_sets); 152 155 LOG("MultiplexSelectedSets: " << (end_select_independent_sets  start_select_independent_sets)); … … 156 159 RECORD_TIMESTAMP(end_topological_sort); 157 160 LOG("TopologicalSort: " << (end_topological_sort  start_topological_sort)); 158 159 llvm::raw_os_ostream out(std::cerr); 160 PabloPrinter::print(function.getEntryBlock(), out); 161 out.flush(); 162 163 RECORD_TIMESTAMP(start_reduce); 164 am.reduce(multiplexedSets); 165 RECORD_TIMESTAMP(end_reduce); 166 LOG("Reduce: " << (end_reduce  start_reduce)); 167 } 168 169 RECORD_TIMESTAMP(start_shutdown); 170 am.Shutdown(); 171 RECORD_TIMESTAMP(end_shutdown); 172 LOG("Shutdown: " << (end_shutdown  start_shutdown)); 161 } 173 162 174 163 LOG_NUMBER_OF_ADVANCES(function.getEntryBlock()); 175 176 // BDDMinimizationPass::optimize(function);177 164 178 165 return multiplex; … … 376 363 } 377 364 } 378 379 assert (Cudd_DebugCheck(mManager) == 0);380 381 365 mRecentCharacterizations.erase(mRecentCharacterizations.begin() + start, mRecentCharacterizations.end()); 382 366 continue; … … 455 439 456 440 Ref(bdd); 457 458 441 if (LLVM_UNLIKELY(NoSatisfyingAssignment(bdd))) { 459 442 Deref(bdd); … … 463 446 if (LLVM_UNLIKELY(isa<Advance>(stmt)  isa<Assign>(stmt)  isa<Next>(stmt))) { 464 447 stmt>setOperand(0, stmt>getParent()>createZeroes()); 448 bdd = Zero(); 465 449 } 466 450 else { 467 451 stmt>replaceWith(stmt>getParent()>createZeroes()); 468 } 469 bdd = Zero(); 470 } 471 452 return nullptr; 453 } 454 } 472 455 mRecentCharacterizations.emplace_back(stmt, bdd); 473 456 return bdd; … … 973 956 * @brief multiplexSelectedIndependentSets 974 957 **  */ 975 std::vector<std::vector<PabloAST *>>AutoMultiplexing::multiplexSelectedIndependentSets() const {958 void AutoMultiplexing::multiplexSelectedIndependentSets() const { 976 959 977 960 const unsigned f = num_vertices(mConstraintGraph); … … 985 968 986 969 std::vector<MultiplexSetGraph::vertex_descriptor> I(max_n); 987 std::vector<Advance *> input(max_n);988 std::vector<std::vector<PabloAST *>> outputs;989 970 circular_buffer<PabloAST *> Q(max_n); 990 971 … … 995 976 const size_t n = out_degree(s, mMultiplexSetGraph); 996 977 if (n) { 997 998 978 const size_t m = log2_plus_one(n); 999 1000 std::vector<PabloAST *> muxed(m);979 Advance * input[n]; 980 Advance * muxed[m]; 1001 981 1002 982 graph_traits<MultiplexSetGraph>::out_edge_iterator ei, ei_end; … … 1035 1015 1036 1016 PabloAST * mux = Q.front(); Q.pop_front(); assert (mux); 1037 muxed[j] = builder.createAdvance(mux, adv>getOperand(1), prefix.str()); 1017 // The only way this did not return an Advance statement would be if either the mux or shift amount 1018 // is zero. Since these cases would have been eliminated earlier, we are safe to cast here. 1019 muxed[j] = cast<Advance>(builder.createAdvance(mux, adv>getOperand(1), prefix.str())); 1038 1020 } 1039 1021 … … 1043 1025 // Construct the demuxed values and replaces all the users of the original advances with them. 1044 1026 for (size_t j = 0; j != m; ++j) { 1045 if ((i & ( static_cast<size_t>(1)<< j)) == 0) {1027 if ((i & (1ULL << j)) == 0) { 1046 1028 Q.push_back(muxed[j]); 1047 1029 } … … 1061 1043 1062 1044 for (unsigned j = 0; j != m; ++j) { 1063 if ((i & ( static_cast<unsigned>(1)<< j)) != 0) {1045 if ((i & (1ULL << j)) != 0) { 1064 1046 assert (!Q.full()); 1065 1047 Q.push_back(muxed[j]); … … 1077 1059 input[i  1]>replaceWith(demuxed, true, true); 1078 1060 } 1079 outputs.push_back(std::move(muxed)); 1080 } 1081 } 1082 return outputs; 1061 1062 /// Attempt to simplify the demultiplexed values 1063 // simplifyAST(muxed, m, builder); 1064 } 1065 } 1083 1066 } 1084 1067 1085 1068 /**  * 1086 * @brief reduce1069 * @brief simplifyAST 1087 1070 **  */ 1088 inline bool isBinaryOp(const PabloAST * const expr) { 1089 switch (expr>getClassTypeId()) { 1090 case PabloAST::ClassTypeId::And: 1091 case PabloAST::ClassTypeId::Or: 1092 case PabloAST::ClassTypeId::Not: 1093 case PabloAST::ClassTypeId::Xor: 1094 case PabloAST::ClassTypeId::Sel: 1095 return true; 1096 default: 1097 return false; 1098 } 1099 } 1100 1101 1102 void AutoMultiplexing::reduce(const std::vector<std::vector<PabloAST *>> & sets) const { 1103 1104 for (const auto & set : sets) { 1105 1106 // first do a BFS to build a topological ordering of statements we're going to end up visiting 1107 // and determine which of those will be terminals in the BDD 1108 using Graph = adjacency_list<hash_setS, vecS, bidirectionalS, PabloAST *>; 1109 using Vertex = Graph::vertex_descriptor; 1110 1111 Graph G; 1112 std::unordered_map<PabloAST *, unsigned> M; 1113 1114 std::queue<Statement *> Q; 1115 1116 llvm::raw_os_ostream out(std::cerr); 1117 1118 for (PabloAST * inst : set) { 1119 if (LLVM_LIKELY(isa<Advance>(inst))) { 1120 const auto u = add_vertex(inst, G); 1121 M.insert(std::make_pair(inst, u)); 1122 1123 for (PabloAST * user : inst>users()) { 1124 auto f = M.find(user); 1125 Vertex v = 0; 1126 if (f == M.end()) { 1127 v = add_vertex(user, G); 1128 M.insert(std::make_pair(user, v)); 1129 if (isBinaryOp(user)) { 1130 Q.push(cast<Statement>(user)); 1131 } 1132 } else { // if (f != M.end()) { 1133 v = f>second; 1134 } 1135 add_edge(u, v, G); 1071 void AutoMultiplexing::simplifyAST(Advance * const muxed[], const unsigned m, PabloBuilder & builder) const { 1072 1073 // first do a BFS to build a topological ordering of statements we're going to end up visiting 1074 // and determine which of those will be terminals in the BDD 1075 using Graph = adjacency_list<hash_setS, vecS, bidirectionalS, PabloAST *>; 1076 using Vertex = Graph::vertex_descriptor; 1077 1078 Graph G; 1079 std::unordered_map<PabloAST *, unsigned> M; 1080 std::queue<Statement *> Q; 1081 1082 for (unsigned i = 0; i != m; ++i) { 1083 1084 const auto u = add_vertex(muxed[i], G); 1085 M.insert(std::make_pair(muxed[i], u)); 1086 for (PabloAST * user : muxed[i]>users()) { 1087 auto f = M.find(user); 1088 Vertex v = 0; 1089 if (f == M.end()) { 1090 v = add_vertex(user, G); 1091 M.insert(std::make_pair(user, v)); 1092 switch (user>getClassTypeId()) { 1093 case PabloAST::ClassTypeId::And: 1094 case PabloAST::ClassTypeId::Or: 1095 case PabloAST::ClassTypeId::Not: 1096 case PabloAST::ClassTypeId::Sel: 1097 Q.push(cast<Statement>(user)); 1098 default: break; 1136 1099 } 1137 1138 } 1139 } 1140 1141 while (!Q.empty()) { 1142 Statement * const var = Q.front(); Q.pop(); 1143 const Vertex u = M[var]; 1144 1145 for (unsigned i = 0; i != var>getNumOperands(); ++i) { 1146 PabloAST * operand = var>getOperand(i); 1147 auto f = M.find(operand); 1148 Vertex v; 1149 if (LLVM_UNLIKELY(f == M.end())) { 1150 v = add_vertex(operand, G); 1151 M.insert(std::make_pair(operand, v)); 1152 } else { // if (f != M.end()) { 1153 v = f>second; 1100 } else { // if (f != M.end()) { 1101 v = f>second; 1102 } 1103 add_edge(u, v, G); 1104 } 1105 } 1106 1107 while (!Q.empty()) { 1108 Statement * const var = Q.front(); Q.pop(); 1109 const Vertex u = M[var]; 1110 for (unsigned i = 0; i != var>getNumOperands(); ++i) { 1111 PabloAST * operand = var>getOperand(i); 1112 auto f = M.find(operand); 1113 Vertex v = 0; 1114 if (LLVM_UNLIKELY(f == M.end())) { 1115 v = add_vertex(operand, G); 1116 M.insert(std::make_pair(operand, v)); 1117 } else { // if (f != M.end()) { 1118 v = f>second; 1119 } 1120 add_edge(v, u, G); 1121 } 1122 1123 for (PabloAST * user : var>users()) { 1124 auto f = M.find(user); 1125 Vertex v = 0; 1126 if (LLVM_LIKELY(f == M.end())) { 1127 v = add_vertex(user, G); 1128 M.insert(std::make_pair(user, v)); 1129 switch (user>getClassTypeId()) { 1130 case PabloAST::ClassTypeId::And: 1131 case PabloAST::ClassTypeId::Or: 1132 case PabloAST::ClassTypeId::Not: 1133 case PabloAST::ClassTypeId::Sel: 1134 Q.push(cast<Statement>(user)); 1135 default: break; 1154 1136 } 1155 add_edge(v, u, G); 1156 } 1157 1158 for (PabloAST * user : var>users()) { 1159 auto f = M.find(user); 1160 Vertex v = 0; 1161 if (LLVM_LIKELY(f == M.end())) { 1162 v = add_vertex(user, G); 1163 M.insert(std::make_pair(user, v)); 1164 if (isBinaryOp(user)) { 1165 Q.push(cast<Statement>(user)); 1166 } 1167 } else { // if (f != M.end()) { 1168 v = f>second; 1169 } 1170 add_edge(u, v, G); 1171 } 1172 } 1173 1174 out << "\ndigraph G {\n"; 1175 for (auto u : make_iterator_range(vertices(G))) { 1176 out << " v" << u; 1177 PabloPrinter::print(cast<Statement>(G[u]), " [label=\"", out); 1178 out << "\"];\n"; 1179 } 1180 for (auto e : make_iterator_range(edges(G))) { 1181 out << " v" << source(e, G) << " > v" << target(e, G) << ";\n"; 1182 } 1183 out << "}\n\n"; 1137 } else { // if (f != M.end()) { 1138 v = f>second; 1139 } 1140 add_edge(u, v, G); 1141 } 1142 } 1143 1144 // count the number of sources (sinks) so we know how many inputs (terminals) will exist in the BDD 1145 std::vector<Vertex> inputs; 1146 flat_set<Vertex> terminals; 1147 for (auto u : make_iterator_range(vertices(G))) { 1148 if (in_degree(u, G) == 0) { 1149 inputs.push_back(u); 1150 } 1151 if (out_degree(u, G) == 0) { 1152 // the inputs to the sinks become the terminals in the BDD 1153 for (auto e : make_iterator_range(in_edges(u, G))) { 1154 terminals.insert(source(e, G)); 1155 } 1156 } 1157 } 1158 1159 const auto n = inputs.size(); 1160 1161 DdManager * manager = Cudd_Init(n, 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0); 1162 Cudd_AutodynEnable(manager, CUDD_REORDER_LAZY_SIFT); 1163 1164 PabloAST * variables[n]; 1165 std::vector<DdNode *> characterization(num_vertices(G), nullptr); 1166 for (unsigned i = 0; i != n; ++i) { 1167 variables[i] = G[inputs[i]]; 1168 characterization[inputs[i]] = Cudd_bddIthVar(manager, i); 1169 } 1170 1171 std::vector<Vertex> ordering; 1172 ordering.reserve(num_vertices(G)); 1173 topological_sort(G, std::back_inserter(ordering)); 1174 1175 for (auto ui = ordering.rbegin(); ui != ordering.rend(); ++ui) { 1176 1177 const Vertex u = *ui; 1178 1179 if (characterization[u]) { 1180 continue; 1181 } 1182 1183 std::array<DdNode *, 3> input; 1184 1185 unsigned i = 0; 1186 for (const auto e : make_iterator_range(in_edges(u, G))) { 1187 input[i++] = characterization[source(e, G)]; 1188 1189 } 1190 1191 assert (is<Statement>(G[u]) ? i == cast<Statement>(G[u])>getNumOperands() : i == 0); 1192 1193 DdNode * bdd = nullptr; 1194 bool characterized = true; 1195 switch (G[u]>getClassTypeId()) { 1196 case PabloAST::ClassTypeId::And: 1197 bdd = Cudd_bddAnd(manager, input[0], input[1]); 1198 break; 1199 case PabloAST::ClassTypeId::Or: 1200 bdd = Cudd_bddOr(manager, input[0], input[1]); 1201 break; 1202 case PabloAST::ClassTypeId::Not: 1203 bdd = Cudd_Not(input[0]); 1204 break; 1205 case PabloAST::ClassTypeId::Sel: 1206 bdd = Cudd_bddIte(manager, input[0], input[1], input[2]); 1207 break; 1208 default: characterized = false; break; 1209 } 1210 1211 if (characterized) { 1212 Cudd_Ref(bdd); 1213 characterization[u] = bdd; 1214 } 1215 } 1216 1217 Cudd_AutodynDisable(manager); 1218 Cudd_ReduceHeap(manager, CUDD_REORDER_SIFT, 0); 1219 Cudd_ReduceHeap(manager, CUDD_REORDER_EXACT, 0); 1220 1221 raw_os_ostream out(std::cerr); 1222 1223 for (Vertex t : terminals) { 1224 1225 // out << "*******************************************************************************************\n"; 1226 // PabloPrinter::print(*(builder.getPabloBlock()), "", out); 1227 // out << "\n\n"; 1228 PabloPrinter::print(cast<Statement>(G[t]), " >> ", out); 1229 out << '\n'; 1184 1230 out.flush(); 1185 1231 1186 // count the number of sinks (sources) so we know how many variables (terminals) will exist in the BDD 1187 std::vector<Vertex> variable; 1188 flat_set<Vertex> terminal; 1189 for (auto u : make_iterator_range(vertices(G))) { 1190 if (in_degree(u, G) == 0) { 1191 variable.push_back(u); 1192 } 1193 if (out_degree(u, G) == 0) { 1194 // the inputs to the sinks become the terminals in the BDD 1195 for (auto e : make_iterator_range(in_edges(u, G))) { 1196 terminal.insert(target(e, G)); 1197 } 1198 } 1199 } 1200 1201 DdManager * manager = Cudd_Init(variable.size(), 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0); 1202 Cudd_AutodynEnable(manager, CUDD_REORDER_LAZY_SIFT); 1203 1204 std::vector<DdNode *> characterization(num_vertices(G), nullptr); 1205 unsigned i = 0; 1206 for (auto u : variable) { 1207 characterization[u] = Cudd_bddIthVar(manager, i++); 1208 } 1209 1210 std::vector<Vertex> ordering; 1211 ordering.reserve(num_vertices(G)); 1212 topological_sort(G, std::back_inserter(ordering)); 1213 1214 for (auto ui = ordering.rbegin(); ui != ordering.rend(); ++ui) { 1215 1216 const Vertex u = *ui; 1217 1218 Statement * stmt = cast<Statement>(G[u]); 1219 1220 out << u; PabloPrinter::print(stmt, " : ", out); out << " = " << (long)characterization[u] << '\n'; 1232 DdNode * const f = characterization[t]; 1233 Cudd_Ref(f); 1234 PabloAST * expr; 1235 unsigned count; 1236 std::tie(expr, count) = simplifyAST(manager, f, variables, builder); 1237 if (expr) { 1238 1239 PabloPrinter::print(cast<Statement>(expr), " replacement: ", out); 1240 out << '\n'; 1221 1241 out.flush(); 1222 1242 1223 if (characterization[u]) { 1224 continue; 1225 } 1226 1227 std::array<DdNode *, 3> input; 1228 1229 unsigned i = 0; 1230 for (const auto e : make_iterator_range(in_edges(u, G))) { 1231 input[i++] = characterization[source(e, G)]; 1232 1233 } 1234 1235 assert (is<Statement>(G[u]) ? i == cast<Statement>(G[u])>getNumOperands() : i == 0); 1236 1237 DdNode * bdd = nullptr; 1238 1239 switch (G[u]>getClassTypeId()) { 1240 case PabloAST::ClassTypeId::And: 1241 bdd = Cudd_bddAnd(manager, input[0], input[1]); 1242 break; 1243 case PabloAST::ClassTypeId::Or: 1244 bdd = Cudd_bddOr(manager, input[0], input[1]); 1245 break; 1246 case PabloAST::ClassTypeId::Not: 1247 bdd = Cudd_Not(input[0]); 1248 break; 1249 case PabloAST::ClassTypeId::Xor: 1250 bdd = Cudd_bddXor(manager, input[0], input[1]); 1251 break; 1252 case PabloAST::ClassTypeId::Sel: 1253 bdd = Cudd_bddIte(manager, input[0], input[1], input[2]); 1254 break; 1255 default: break; 1256 } 1257 1258 characterization[u] = bdd; 1259 } 1260 1261 Cudd_ReduceHeap(manager, CUDD_REORDER_SIFT, 0); 1262 1263 for (auto t : terminal) { 1264 1265 llvm::raw_os_ostream out(std::cerr); 1266 out << " REDUNCTION : "; PabloPrinter::print(G[t], out); out << '\n'; 1267 out.flush(); 1268 1269 DdNode * bdd = characterization[t]; 1270 Cudd_bddPrintCover(manager, bdd, bdd); 1271 1272 out << '\n'; out.flush(); 1273 } 1274 1275 Cudd_Quit(manager); 1276 } 1277 1278 } 1243 cast<Statement>(G[t])>replaceWith(expr, true, true); 1244 } 1245 Cudd_RecursiveDeref(manager, f); 1246 } 1247 1248 // out << "+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n"; 1249 // PabloPrinter::print(*(builder.getPabloBlock()), "", out); 1250 // out << '\n'; 1251 // out.flush(); 1252 1253 Cudd_Quit(manager); 1254 } 1255 1256 /**  * 1257 * @brief simplifyAST 1258 **  */ 1259 std::pair<PabloAST *, unsigned> AutoMultiplexing::simplifyAST(DdManager * manager, DdNode * const f, PabloAST * const variables[], PabloBuilder & builder) const { 1260 DdNode * g = Cudd_FindEssential(manager, f); 1261 if (g && Cudd_SupportSize(manager, g) > 0) { 1262 if (g == f) { // every variable is essential 1263 return makeCoverAST(manager, f, variables, builder); 1264 } 1265 Cudd_Ref(g); 1266 PabloAST * c0; 1267 unsigned count0; 1268 std::tie(c0, count0) = makeCoverAST(manager, g, variables, builder); 1269 if (LLVM_UNLIKELY(c0 == nullptr)) { 1270 Cudd_RecursiveDeref(manager, g); 1271 return std::make_pair(nullptr, 0); 1272 } 1273 DdNode * h = Cudd_Cofactor(manager, f, g); 1274 Cudd_Ref(h); 1275 Cudd_RecursiveDeref(manager, g); 1276 PabloAST * c1; 1277 unsigned count1; 1278 std::tie(c1, count1) = simplifyAST(manager, h, variables, builder); 1279 Cudd_RecursiveDeref(manager, h); 1280 if (LLVM_UNLIKELY(c1 == nullptr)) { 1281 cast<Statement>(c0)>eraseFromParent(true); 1282 return std::make_pair(nullptr, 0); 1283 } 1284 return std::make_pair(builder.createAnd(c0, c1), count0 + count1 + 1); 1285 } 1286 1287 PabloAST * disjunctionAST = nullptr; 1288 unsigned disjunctionCount = 0; 1289 PabloAST * conjunctionAST = nullptr; 1290 unsigned conjunctionCount = 0; 1291 1292 DdNode ** decomp = nullptr; 1293 const auto disjuncts = Cudd_bddGenDisjDecomp(manager, f, &decomp); 1294 if (LLVM_LIKELY(disjuncts == 2)) { 1295 Cudd_Ref(decomp[0]); 1296 Cudd_Ref(decomp[1]); 1297 PabloAST * d0; 1298 unsigned count0; 1299 std::tie(d0, count0) = simplifyAST(manager, decomp[0], variables, builder); 1300 Cudd_RecursiveDeref(manager, decomp[0]); 1301 if (LLVM_UNLIKELY(d0 == nullptr)) { 1302 Cudd_RecursiveDeref(manager, decomp[1]); 1303 return std::make_pair(nullptr, 0); 1304 } 1305 PabloAST * d1; 1306 unsigned count1; 1307 std::tie(d1, count1) = simplifyAST(manager, decomp[1], variables, builder); 1308 Cudd_RecursiveDeref(manager, decomp[1]); 1309 FREE(decomp); 1310 if (LLVM_UNLIKELY(d1 == nullptr)) { 1311 cast<Statement>(d0)>eraseFromParent(true); 1312 return std::make_pair(nullptr, 0); 1313 } 1314 disjunctionAST = builder.createOr(d0, d1); 1315 disjunctionCount = count0 + count1 + 1; 1316 } 1317 FREE(decomp); 1318 1319 const auto conjuncts = Cudd_bddGenConjDecomp(manager, f, &decomp); 1320 if (LLVM_LIKELY(conjuncts == 2)) { 1321 Cudd_Ref(decomp[0]); 1322 Cudd_Ref(decomp[1]); 1323 PabloAST * d0; 1324 unsigned count0; 1325 std::tie(d0, count0) = simplifyAST(manager, decomp[0], variables, builder); 1326 Cudd_RecursiveDeref(manager, decomp[0]); 1327 if (LLVM_UNLIKELY(d0 == nullptr)) { 1328 Cudd_RecursiveDeref(manager, decomp[1]); 1329 return std::make_pair(nullptr, 0); 1330 } 1331 PabloAST * d1; 1332 unsigned count1; 1333 std::tie(d1, count1) = simplifyAST(manager, decomp[1], variables, builder); 1334 Cudd_RecursiveDeref(manager, decomp[1]); 1335 FREE(decomp); 1336 if (LLVM_UNLIKELY(d1 == nullptr)) { 1337 cast<Statement>(d0)>eraseFromParent(true); 1338 return std::make_pair(nullptr, 0); 1339 } 1340 conjunctionAST = builder.createAnd(d0, d1); 1341 conjunctionCount = count0 + count1 + 1; 1342 } 1343 FREE(decomp); 1344 1345 if (disjunctionAST && conjunctionAST) { 1346 if (disjunctionCount > conjunctionCount) { 1347 cast<Statement>(disjunctionAST)>eraseFromParent(true); 1348 return std::make_pair(conjunctionAST, conjunctionCount); 1349 } else { 1350 cast<Statement>(conjunctionAST)>eraseFromParent(true); 1351 return std::make_pair(disjunctionAST, disjunctionCount); 1352 } 1353 } else if (disjunctionAST) { 1354 return std::make_pair(disjunctionAST, disjunctionCount); 1355 } else if (conjunctionAST) { 1356 return std::make_pair(conjunctionAST, conjunctionCount); 1357 } 1358 return makeCoverAST(manager, f, variables, builder); 1359 } 1360 1361 /**  * 1362 * @brief makeCoverAST 1363 **  */ 1364 std::pair<PabloAST *, unsigned> AutoMultiplexing::makeCoverAST(DdManager * manager, DdNode * const f, PabloAST * const variables[], PabloBuilder & builder) const { 1365 1366 std::queue<PabloAST *> SQ; 1367 1368 circular_buffer<PabloAST *> CQ(manager>size); 1369 circular_buffer<PabloAST *> DQ(manager>size); 1370 1371 int cube[manager>size]; 1372 1373 unsigned count = 0; 1374 1375 DdNode * g = f; 1376 1377 Cudd_Ref(g); 1378 1379 while (g != Cudd_ReadLogicZero(manager)) { 1380 int length; 1381 DdNode * implicant = Cudd_LargestCube(manager, g, &length); 1382 if (LLVM_UNLIKELY(implicant == nullptr)) { 1383 Cudd_RecursiveDeref(manager, g); 1384 return std::make_pair(nullptr, 0); 1385 } 1386 Cudd_Ref(implicant); 1387 DdNode * prime = Cudd_bddMakePrime(manager, implicant, f); 1388 if (LLVM_UNLIKELY(prime == nullptr)) { 1389 Cudd_RecursiveDeref(manager, g); 1390 Cudd_RecursiveDeref(manager, implicant); 1391 return std::make_pair(nullptr, 0); 1392 } 1393 Cudd_Ref(prime); 1394 Cudd_RecursiveDeref(manager, implicant); 1395 1396 DdNode * h = Cudd_bddAnd(manager, g, Cudd_Not(prime)); 1397 if (LLVM_UNLIKELY(h == nullptr)) { 1398 Cudd_RecursiveDeref(manager, g); 1399 Cudd_RecursiveDeref(manager, prime); 1400 return std::make_pair(nullptr, 0); 1401 } 1402 Cudd_Ref(h); 1403 Cudd_RecursiveDeref(manager, g); 1404 1405 g = h; 1406 if (LLVM_UNLIKELY(Cudd_BddToCubeArray(manager, prime, cube) == 0)) { 1407 Cudd_RecursiveDeref(manager, g); 1408 Cudd_RecursiveDeref(manager, prime); 1409 return std::make_pair(nullptr, 0); 1410 } 1411 Cudd_RecursiveDeref(manager, prime); 1412 1413 for (auto i = 0; i != manager>size; ++i) { 1414 if (cube[i] == 0) { 1415 DQ.push_back(variables[i]); 1416 } else if (cube[i] == 1) { 1417 CQ.push_back(variables[i]); 1418 } 1419 } 1420 if (!DQ.empty()) { 1421 while (DQ.size() > 1) { 1422 PabloAST * v1 = DQ.front(); DQ.pop_front(); 1423 PabloAST * v2 = DQ.front(); DQ.pop_front(); 1424 DQ.push_back(builder.createOr(v1, v2)); 1425 ++count; 1426 } 1427 CQ.push_back(builder.createNot(DQ.front())); 1428 DQ.clear(); 1429 } 1430 while (CQ.size() > 1) { 1431 PabloAST * v1 = CQ.front(); CQ.pop_front(); 1432 PabloAST * v2 = CQ.front(); CQ.pop_front(); 1433 CQ.push_back(builder.createAnd(v1, v2)); 1434 ++count; 1435 } 1436 SQ.push(CQ.front()); CQ.clear(); 1437 } 1438 Cudd_RecursiveDeref(manager, g); 1439 1440 while (SQ.size() > 1) { 1441 PabloAST * v1 = SQ.front(); SQ.pop(); 1442 PabloAST * v2 = SQ.front(); SQ.pop(); 1443 SQ.push(builder.createOr(v1, v2)); 1444 ++count; 1445 } 1446 1447 return std::make_pair(SQ.front(), count); 1448 } 1449 1450 ///**  * 1451 // * @brief reduce 1452 // **  */ 1453 //inline bool isBinaryOp(const PabloAST * const expr) { 1454 // switch (expr>getClassTypeId()) { 1455 // case PabloAST::ClassTypeId::And: 1456 // case PabloAST::ClassTypeId::Or: 1457 // case PabloAST::ClassTypeId::Not: 1458 // case PabloAST::ClassTypeId::Xor: 1459 // case PabloAST::ClassTypeId::Sel: 1460 // return true; 1461 // default: 1462 // return false; 1463 // } 1464 //} 1465 1466 ///**  * 1467 // * @brief minimizeCoFactor 1468 // **  */ 1469 //PabloAST * minimizeCoFactor(DdManager * const manager, DdNode * const f, const std::vector<PabloAST *> & variables, PabloBuilder & builder) { 1470 1471 // std::queue<PabloAST *> SQ; 1472 // std::queue<PabloAST *> CQ; 1473 // std::queue<PabloAST *> DQ; 1474 1475 // int cube[manager>size]; 1476 1477 // DdNode * g = f; 1478 1479 // Cudd_Ref(g); 1480 1481 // while (g != Cudd_ReadLogicZero(manager)) { 1482 // int length; 1483 // DdNode * implicant = Cudd_LargestCube(manager, g, &length); 1484 // if (LLVM_UNLIKELY(implicant == nullptr)) { 1485 // Cudd_RecursiveDeref(manager, g); 1486 // std::cerr << "Cudd_LargestCube" << std::endl; 1487 // return nullptr; 1488 // } 1489 // Cudd_Ref(implicant); 1490 // DdNode * prime = Cudd_bddMakePrime(manager, implicant, f); 1491 // if (LLVM_UNLIKELY(prime == nullptr)) { 1492 // Cudd_RecursiveDeref(manager, g); 1493 // Cudd_RecursiveDeref(manager, implicant); 1494 // std::cerr << "Cudd_bddMakePrime" << std::endl; 1495 // return nullptr; 1496 // } 1497 // Cudd_Ref(prime); 1498 // Cudd_RecursiveDeref(manager, implicant); 1499 1500 // DdNode * h = Cudd_bddAnd(manager, g, Cudd_Not(prime)); 1501 // if (LLVM_UNLIKELY(h == nullptr)) { 1502 // Cudd_RecursiveDeref(manager, g); 1503 // Cudd_RecursiveDeref(manager, prime); 1504 // std::cerr << "Cudd_bddAnd" << std::endl; 1505 // return nullptr; 1506 // } 1507 // Cudd_Ref(h); 1508 // Cudd_RecursiveDeref(manager, g); 1509 1510 // g = h; 1511 // if (LLVM_UNLIKELY(Cudd_BddToCubeArray(manager, prime, cube) == 0)) { 1512 // Cudd_RecursiveDeref(manager, g); 1513 // Cudd_RecursiveDeref(manager, prime); 1514 // std::cerr << "Cudd_BddToCubeArray" << std::endl; 1515 // return nullptr; 1516 // } 1517 // Cudd_RecursiveDeref(manager, prime); 1518 1519 // for (auto i = 0; i != manager>size; ++i) { 1520 // if (cube[i] == 0) { 1521 // DQ.push(variables[i]); 1522 // } else if (cube[i] == 1) { 1523 // CQ.push(variables[i]); 1524 // } 1525 // } 1526 1527 // if (DQ.size() > 0) { 1528 // while (DQ.size() > 1) { 1529 // PabloAST * v1 = DQ.front(); DQ.pop(); 1530 // PabloAST * v2 = DQ.front(); DQ.pop(); 1531 // DQ.push(builder.createOr(v1, v2)); 1532 // } 1533 // CQ.push(builder.createNot(DQ.front())); DQ.pop(); 1534 // } 1535 1536 // while (CQ.size() > 1) { 1537 // PabloAST * v1 = CQ.front(); CQ.pop(); 1538 // PabloAST * v2 = CQ.front(); CQ.pop(); 1539 // CQ.push(builder.createAnd(v1, v2)); 1540 // } 1541 1542 // SQ.push(CQ.front()); CQ.pop(); 1543 // } 1544 // Cudd_RecursiveDeref(manager, g); 1545 1546 // while (SQ.size() > 1) { 1547 // PabloAST * v1 = SQ.front(); SQ.pop(); 1548 // PabloAST * v2 = SQ.front(); SQ.pop(); 1549 // SQ.push(builder.createOr(v1, v2)); 1550 // } 1551 1552 // return SQ.front(); 1553 //} 1554 1555 ///**  * 1556 // * @brief minimize 1557 // **  */ 1558 //PabloAST * minimize(DdManager * const manager, DdNode * const f, const std::vector<PabloAST *> & variables, PabloBuilder & builder) { 1559 // DdNode * g = Cudd_FindEssential(manager, f); 1560 // if (f == g  g == nullptr  Cudd_SupportSize(manager, g) == 0) { 1561 //// g = Cudd_SubsetCompress(manager, f, Cudd_SupportSize(manager, f), Cudd_DagSize(f)); 1562 //// if (f == g  g == nullptr) { 1563 // return minimizeCoFactor(manager, f, variables, builder); 1564 //// } 1565 // } 1566 // Cudd_Ref(g); 1567 // PabloAST * essentialAST = minimize(manager, g, variables, builder); 1568 // if (LLVM_UNLIKELY(essentialAST == nullptr)) { 1569 // Cudd_RecursiveDeref(manager, g); 1570 // return nullptr; 1571 // } 1572 // DdNode * h = Cudd_Cofactor(manager, f, g); 1573 // Cudd_Ref(h); 1574 // Cudd_RecursiveDeref(manager, g); 1575 // PabloAST * cofactorAST = minimize(manager, h, variables, builder); 1576 // Cudd_RecursiveDeref(manager, h); 1577 // if (LLVM_UNLIKELY(cofactorAST == nullptr)) { 1578 // if (LLVM_LIKELY(isa<Statement>(essentialAST))) { 1579 // cast<Statement>(essentialAST)>eraseFromParent(true); 1580 // } 1581 // return nullptr; 1582 // } 1583 // return builder.createAnd(essentialAST, cofactorAST); 1584 //} 1585 1586 ///**  * 1587 // * @brief reduce 1588 // **  */ 1589 //void AutoMultiplexing::reduce(const std::vector<std::vector<PabloAST *>> & sets) const { 1590 1591 // for (const auto & set : sets) { 1592 1593 // // first do a BFS to build a topological ordering of statements we're going to end up visiting 1594 // // and determine which of those will be terminals in the BDD 1595 // using Graph = adjacency_list<hash_setS, vecS, bidirectionalS, PabloAST *>; 1596 // using Vertex = Graph::vertex_descriptor; 1597 1598 // Graph G; 1599 // std::unordered_map<PabloAST *, unsigned> M; 1600 1601 // std::queue<Statement *> Q; 1602 1603 // for (PabloAST * inst : set) { 1604 // if (LLVM_LIKELY(isa<Advance>(inst))) { 1605 // const auto u = add_vertex(inst, G); 1606 // M.insert(std::make_pair(inst, u)); 1607 1608 // for (PabloAST * user : inst>users()) { 1609 // auto f = M.find(user); 1610 // Vertex v = 0; 1611 // if (f == M.end()) { 1612 // v = add_vertex(user, G); 1613 // M.insert(std::make_pair(user, v)); 1614 // if (isBinaryOp(user)) { 1615 // Q.push(cast<Statement>(user)); 1616 // } 1617 // } else { // if (f != M.end()) { 1618 // v = f>second; 1619 // } 1620 // add_edge(u, v, G); 1621 // } 1622 1623 // } 1624 // } 1625 1626 // while (!Q.empty()) { 1627 // Statement * const var = Q.front(); Q.pop(); 1628 // const Vertex u = M[var]; 1629 1630 // for (unsigned i = 0; i != var>getNumOperands(); ++i) { 1631 // PabloAST * operand = var>getOperand(i); 1632 // auto f = M.find(operand); 1633 // Vertex v; 1634 // if (LLVM_UNLIKELY(f == M.end())) { 1635 // v = add_vertex(operand, G); 1636 // M.insert(std::make_pair(operand, v)); 1637 // } else { // if (f != M.end()) { 1638 // v = f>second; 1639 // } 1640 // add_edge(v, u, G); 1641 // } 1642 1643 // for (PabloAST * user : var>users()) { 1644 // auto f = M.find(user); 1645 // Vertex v = 0; 1646 // if (LLVM_LIKELY(f == M.end())) { 1647 // v = add_vertex(user, G); 1648 // M.insert(std::make_pair(user, v)); 1649 // if (isBinaryOp(user)) { 1650 // Q.push(cast<Statement>(user)); 1651 // } 1652 // } else { // if (f != M.end()) { 1653 // v = f>second; 1654 // } 1655 // add_edge(u, v, G); 1656 // } 1657 // } 1658 1659 // // count the number of sinks (sources) so we know how many variables (terminals) will exist in the BDD 1660 // std::vector<Vertex> variable; 1661 // flat_set<Vertex> terminal; 1662 // for (auto u : make_iterator_range(vertices(G))) { 1663 // if (in_degree(u, G) == 0) { 1664 // variable.push_back(u); 1665 // } 1666 // if (out_degree(u, G) == 0) { 1667 // // the inputs to the sinks become the terminals in the BDD 1668 // for (auto e : make_iterator_range(in_edges(u, G))) { 1669 // terminal.insert(source(e, G)); 1670 // } 1671 // } 1672 // } 1673 1674 // DdManager * manager = Cudd_Init(variable.size(), 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0); 1675 // Cudd_AutodynEnable(manager, CUDD_REORDER_SIFT); 1676 1677 // std::vector<DdNode *> characterization(num_vertices(G), nullptr); 1678 // unsigned i = 0; 1679 // for (auto u : variable) { 1680 // characterization[u] = Cudd_bddIthVar(manager, i++); 1681 // } 1682 1683 // std::vector<Vertex> ordering; 1684 // ordering.reserve(num_vertices(G)); 1685 // topological_sort(G, std::back_inserter(ordering)); 1686 1687 // for (auto ui = ordering.rbegin(); ui != ordering.rend(); ++ui) { 1688 1689 // const Vertex u = *ui; 1690 1691 // if (characterization[u]) { 1692 // continue; 1693 // } 1694 1695 // std::array<DdNode *, 3> input; 1696 1697 // unsigned i = 0; 1698 // for (const auto e : make_iterator_range(in_edges(u, G))) { 1699 // input[i++] = characterization[source(e, G)]; 1700 1701 // } 1702 1703 // assert (is<Statement>(G[u]) ? i == cast<Statement>(G[u])>getNumOperands() : i == 0); 1704 1705 // DdNode * bdd = nullptr; 1706 // bool characterized = true; 1707 // switch (G[u]>getClassTypeId()) { 1708 // case PabloAST::ClassTypeId::And: 1709 // bdd = Cudd_bddAnd(manager, input[0], input[1]); 1710 // break; 1711 // case PabloAST::ClassTypeId::Or: 1712 // bdd = Cudd_bddOr(manager, input[0], input[1]); 1713 // break; 1714 // case PabloAST::ClassTypeId::Not: 1715 // bdd = Cudd_Not(input[0]); 1716 // break; 1717 // case PabloAST::ClassTypeId::Xor: 1718 // bdd = Cudd_bddXor(manager, input[0], input[1]); 1719 // break; 1720 // case PabloAST::ClassTypeId::Sel: 1721 // bdd = Cudd_bddIte(manager, input[0], input[1], input[2]); 1722 // break; 1723 // default: characterized = false; break; 1724 // } 1725 1726 // if (characterized) { 1727 // Cudd_Ref(bdd); 1728 // characterization[u] = bdd; 1729 // } 1730 // } 1731 1732 // Cudd_AutodynDisable(manager); 1733 // Cudd_ReduceHeap(manager, CUDD_REORDER_SIFT, 0); 1734 1735 // std::vector<PabloAST *> inputs; 1736 // for (Vertex s : variable) { 1737 // inputs.push_back(G[s]); 1738 // } 1739 1740 // for (Vertex t : terminal) { 1741 // Statement * const stmt = cast<Statement>(G[t]); 1742 // PabloBlock * const block = stmt>getParent(); 1743 // block>setInsertPoint(stmt); 1744 // PabloBuilder builder(*block); 1745 // DdNode * const f = characterization[t]; 1746 // llvm::raw_os_ostream out(std::cerr); 1747 // PabloPrinter::print(stmt, " > ", out); out << '\n'; out.flush(); 1748 1749 // Cudd_Ref(f); 1750 // PabloAST * expr = minimize(manager, f, inputs, builder); 1751 // if (LLVM_LIKELY(expr != nullptr)) { 1752 // stmt>replaceWith(expr); 1753 // } else { 1754 // llvm::raw_os_ostream out(std::cerr); 1755 // PabloPrinter::print(stmt, "Failed to minimize: ", out); out << '\n'; out.flush(); 1756 // } 1757 // Cudd_RecursiveDeref(manager, f); 1758 // } 1759 // Cudd_Quit(manager); 1760 // } 1761 //} 1279 1762 1280 1763 /**  *
Note: See TracChangeset
for help on using the changeset viewer.