 Timestamp:
 Aug 10, 2015, 3:30:31 PM (4 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

icGREP/icgrepdevel/icgrep/pablo/optimizers/pablo_automultiplexing.cpp
r4711 r4722 16 16 #include <queue> 17 17 #include <unordered_set> 18 #include <pablo/optimizers/pablo_simplifier.hpp> 18 19 19 20 using namespace llvm; … … 22 23 using namespace boost::numeric::ublas; 23 24 24 //#define PRINT_DEBUG_OUTPUT25 #define PRINT_DEBUG_OUTPUT 25 26 26 27 #if !defined(NDEBUG) && !defined(PRINT_DEBUG_OUTPUT) … … 131 132 const bool multiplex = am.generateCandidateSets(rng); 132 133 RECORD_TIMESTAMP(end_create_multiplex_graph); 133 LOG("Generate MultiplexSets: " << (end_create_multiplex_graph  start_create_multiplex_graph));134 LOG("GenerateCandidateSets: " << (end_create_multiplex_graph  start_create_multiplex_graph)); 134 135 135 136 RECORD_TIMESTAMP(start_shutdown); … … 153 154 am.multiplexSelectedIndependentSets(); 154 155 RECORD_TIMESTAMP(end_select_independent_sets); 155 LOG(" MultiplexSelectedSets:" << (end_select_independent_sets  start_select_independent_sets));156 LOG("SelectedIndependentSets: " << (end_select_independent_sets  start_select_independent_sets)); 156 157 157 158 RECORD_TIMESTAMP(start_topological_sort); 158 159 am.topologicalSort(function.getEntryBlock()); 159 160 RECORD_TIMESTAMP(end_topological_sort); 160 LOG("TopologicalSort: " << (end_topological_sort  start_topological_sort)); 161 LOG("TopologicalSort (1): " << (end_topological_sort  start_topological_sort)); 162 163 // RECORD_TIMESTAMP(start_simplify_ast); 164 // am.simplifyAST(function); 165 // RECORD_TIMESTAMP(end_simplify_ast); 166 // LOG("SimplifyAST: " << (end_simplify_ast  start_simplify_ast)); 167 168 // RECORD_TIMESTAMP(start_topological_sort2); 169 // am.topologicalSort(function.getEntryBlock()); 170 // RECORD_TIMESTAMP(end_topological_sort2); 171 // LOG("TopologicalSort (2): " << (end_topological_sort2  start_topological_sort2)); 161 172 } 162 173 … … 368 379 369 380 DdNode * var = characterize(stmt); 370 mCharacterizationMap[stmt] = var; 371 assert (Cudd_DebugCheck(mManager) == 0); 381 mCharacterizationMap[stmt] = var; 372 382 } 373 383 } … … 956 966 * @brief multiplexSelectedIndependentSets 957 967 **  */ 958 void AutoMultiplexing::multiplexSelectedIndependentSets() const{968 void AutoMultiplexing::multiplexSelectedIndependentSets() { 959 969 960 970 const unsigned f = num_vertices(mConstraintGraph); … … 978 988 const size_t m = log2_plus_one(n); 979 989 Advance * input[n]; 980 Advance * muxed[m];990 std::vector<PabloAST *> muxed(m); 981 991 982 992 graph_traits<MultiplexSetGraph>::out_edge_iterator ei, ei_end; … … 1016 1026 PabloAST * mux = Q.front(); Q.pop_front(); assert (mux); 1017 1027 // 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()));1028 // is zero. Since these cases would have been eliminated earlier, we are safe to cast here. 1029 muxed[j] = builder.createAdvance(mux, adv>getOperand(1), prefix.str()); 1020 1030 } 1021 1031 … … 1060 1070 } 1061 1071 1062 /// Attempt to simplify the demultiplexed values 1063 // simplifyAST(muxed, m, builder); 1064 } 1072 mMuxedVariables.push_back(std::move(muxed)); 1073 } 1065 1074 } 1066 1075 } … … 1069 1078 * @brief simplifyAST 1070 1079 **  */ 1071 void AutoMultiplexing::simplifyAST( Advance * const muxed[], const unsigned m, PabloBuilder & builder) const{1080 void AutoMultiplexing::simplifyAST(const PabloFunction & function) { 1072 1081 1073 1082 // first do a BFS to build a topological ordering of statements we're going to end up visiting … … 1076 1085 using Vertex = Graph::vertex_descriptor; 1077 1086 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;1099 }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;1136 }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 BDD1145 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 BDD1153 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 1087 raw_os_ostream out(std::cerr); 1222 1088 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'; 1230 out.flush(); 1231 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); 1089 PabloPrinter::print(function.getEntryBlock(), "", out); 1090 out << "\n+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n\n"; 1091 out.flush(); 1092 1093 1094 // TODO: this should build a single graph and iterate by connected component instead. 1095 for (const auto & muxed : mMuxedVariables) { 1096 1097 Graph G; 1098 std::unordered_map<PabloAST *, unsigned> M; 1099 std::queue<Statement *> Q; 1100 1101 for (unsigned i = 0; i != muxed.size(); ++i) { 1102 1103 const auto u = add_vertex(muxed[i], G); 1104 M.insert(std::make_pair(muxed[i], u)); 1105 for (PabloAST * user : muxed[i]>users()) { 1106 auto f = M.find(user); 1107 Vertex v = 0; 1108 if (f == M.end()) { 1109 v = add_vertex(user, G); 1110 M.insert(std::make_pair(user, v)); 1111 switch (user>getClassTypeId()) { 1112 case PabloAST::ClassTypeId::And: 1113 case PabloAST::ClassTypeId::Or: 1114 case PabloAST::ClassTypeId::Not: 1115 case PabloAST::ClassTypeId::Sel: 1116 Q.push(cast<Statement>(user)); 1117 default: break; 1118 } 1119 } else { // if (f != M.end()) { 1120 v = f>second; 1121 } 1122 add_edge(u, v, G); 1123 } 1124 } 1125 1126 while (!Q.empty()) { 1127 Statement * const var = Q.front(); Q.pop(); 1128 const Vertex u = M[var]; 1129 for (unsigned i = 0; i != var>getNumOperands(); ++i) { 1130 PabloAST * operand = var>getOperand(i); 1131 auto f = M.find(operand); 1132 Vertex v = 0; 1133 if (LLVM_UNLIKELY(f == M.end())) { 1134 v = add_vertex(operand, G); 1135 M.insert(std::make_pair(operand, v)); 1136 } else { // if (f != M.end()) { 1137 v = f>second; 1138 } 1139 add_edge(v, u, G); 1140 } 1141 1142 for (PabloAST * user : var>users()) { 1143 auto f = M.find(user); 1144 Vertex v = 0; 1145 if (LLVM_LIKELY(f == M.end())) { 1146 v = add_vertex(user, G); 1147 M.insert(std::make_pair(user, v)); 1148 switch (user>getClassTypeId()) { 1149 case PabloAST::ClassTypeId::And: 1150 case PabloAST::ClassTypeId::Or: 1151 case PabloAST::ClassTypeId::Not: 1152 case PabloAST::ClassTypeId::Sel: 1153 Q.push(cast<Statement>(user)); 1154 default: break; 1155 } 1156 } else { // if (f != M.end()) { 1157 v = f>second; 1158 } 1159 add_edge(u, v, G); 1160 } 1161 } 1162 1163 // count the number of sources (sinks) so we know how many variables (terminals) will exist in the BDD 1164 std::vector<Vertex> inputs; 1165 flat_set<Vertex> terminals; 1166 for (auto u : make_iterator_range(vertices(G))) { 1167 if (in_degree(u, G) == 0) { 1168 inputs.push_back(u); 1169 } 1170 if (out_degree(u, G) == 0) { 1171 // the inputs to the sinks become the terminals in the BDD 1172 for (auto e : make_iterator_range(in_edges(u, G))) { 1173 terminals.insert(source(e, G)); 1174 } 1175 } 1176 } 1177 1178 const auto n = inputs.size(); 1179 1180 mManager = Cudd_Init(n, 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0); 1181 Cudd_AutodynEnable(mManager, CUDD_REORDER_LAZY_SIFT); 1182 1183 std::vector<PabloAST *> nodes(n); 1184 std::vector<DdNode *> characterization(num_vertices(G), nullptr); 1185 for (unsigned i = 0; i != n; ++i) { 1186 nodes[i] = G[inputs[i]]; 1187 assert (nodes[i]); 1188 characterization[inputs[i]] = Cudd_bddIthVar(mManager, i); 1189 } 1190 1191 std::vector<Vertex> ordering; 1192 ordering.reserve(num_vertices(G)); 1193 topological_sort(G, std::back_inserter(ordering)); 1194 1195 for (auto ui = ordering.rbegin(); ui != ordering.rend(); ++ui) { 1196 1197 const Vertex u = *ui; 1198 1199 if (characterization[u]) { 1200 continue; 1201 } 1202 1203 std::array<DdNode *, 3> input; 1204 1205 unsigned i = 0; 1206 for (const auto e : make_iterator_range(in_edges(u, G))) { 1207 input[i] = characterization[source(e, G)]; 1208 if (input[i] == nullptr) { 1209 throw std::runtime_error("Uncharacterized input!"); 1210 } 1211 ++i; 1212 } 1213 1214 DdNode * bdd = nullptr; 1215 bool characterized = true; 1216 switch (G[u]>getClassTypeId()) { 1217 case PabloAST::ClassTypeId::And: 1218 bdd = And(input[0], input[1]); 1219 break; 1220 case PabloAST::ClassTypeId::Or: 1221 bdd = Or(input[0], input[1]); 1222 break; 1223 case PabloAST::ClassTypeId::Not: 1224 bdd = Not(input[0]); 1225 break; 1226 case PabloAST::ClassTypeId::Sel: 1227 bdd = Ite(input[0], input[1], input[2]); 1228 break; 1229 default: characterized = false; break; 1230 } 1231 1232 if (characterized) { 1233 Ref(bdd); 1234 characterization[u] = bdd; 1235 } 1236 } 1237 1238 Cudd_AutodynDisable(mManager); 1239 assert (Cudd_DebugCheck(mManager) == 0); 1240 Cudd_ReduceHeap(mManager, CUDD_REORDER_SIFT, 0); 1241 1242 mSimplifyDepth = 0; 1243 1244 assert (mManager>size == nodes.size()); 1245 1246 for (Vertex t : terminals) { 1247 1248 PabloPrinter::print(cast<Statement>(G[t]), " >> ", out); 1240 1249 out << '\n'; 1241 1250 out.flush(); 1242 1251 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); 1252 Statement * stmt = cast<Statement>(G[t]); 1253 1254 PabloBuilder builder(*(stmt>getParent())); 1255 1256 DdNode * const f = characterization[t]; 1257 Cudd_Ref(f); 1258 1259 PabloAST * expr = simplifyAST(f, nodes, builder); 1260 if (expr) { 1261 1262 PabloPrinter::print(cast<Statement>(expr), " replacement: ", out); 1263 out << '\n'; 1264 out.flush(); 1265 1266 stmt>replaceWith(expr, false, true); 1267 } 1268 Cudd_RecursiveDeref(mManager, f); 1269 } 1270 1271 Cudd_Quit(mManager); 1272 1273 } 1254 1274 } 1255 1275 … … 1257 1277 * @brief simplifyAST 1258 1278 **  */ 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) { 1279 PabloAST * AutoMultiplexing::simplifyAST(DdNode * const f, const std::vector<PabloAST *> & variables, PabloBuilder & builder) { 1280 assert (!NoSatisfyingAssignment(f)); 1281 DdNode * g = Cudd_FindEssential(mManager, f); 1282 if (g && Cudd_SupportSize(mManager, g) > 0) { 1262 1283 if (g == f) { // every variable is essential 1263 return makeCoverAST( manager,f, variables, builder);1284 return makeCoverAST(f, variables, builder); 1264 1285 } 1265 1286 Cudd_Ref(g); 1266 PabloAST * c0; 1267 unsigned count0; 1268 std::tie(c0, count0) = makeCoverAST(manager, g, variables, builder); 1287 PabloAST * c0 = makeCoverAST(g, variables, builder); 1269 1288 if (LLVM_UNLIKELY(c0 == nullptr)) { 1270 Cudd_RecursiveDeref(m anager, g);1271 return std::make_pair(nullptr, 0);1272 } 1273 DdNode * h = Cudd_Cofactor(m anager, f, g);1289 Cudd_RecursiveDeref(mManager, g); 1290 return nullptr; 1291 } 1292 DdNode * h = Cudd_Cofactor(mManager, f, g); 1274 1293 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); 1294 Cudd_RecursiveDeref(mManager, g); 1295 PabloAST * c1 = simplifyAST(h, variables, builder); 1296 Cudd_RecursiveDeref(mManager, h); 1280 1297 if (LLVM_UNLIKELY(c1 == nullptr)) { 1281 1298 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; 1299 return nullptr; 1300 } 1301 return builder.createAnd(c0, c1); 1302 } 1303 1304 DdNode ** disjunct = nullptr; 1305 int disjuncts = Cudd_bddIterDisjDecomp(mManager, f, &disjunct); 1306 assert (disjuncts < 2  Or(disjunct[0], disjunct[1]) == f); 1307 1308 DdNode ** conjunct = nullptr; 1309 int conjuncts = Cudd_bddIterConjDecomp(mManager, f, &conjunct); 1310 assert (conjuncts < 2  And(conjunct[0], conjunct[1]) == f); 1311 1312 if (LLVM_LIKELY(disjuncts == 2 && conjuncts == 2)) { 1313 if (Cudd_SharingSize(disjunct, 2) > Cudd_SharingSize(conjunct, 2)) { 1314 disjuncts = 0; 1315 } 1316 } 1291 1317 1292 1318 DdNode ** decomp = nullptr; 1293 const auto disjuncts = Cudd_bddGenDisjDecomp(manager, f, &decomp); 1294 if (LLVM_LIKELY(disjuncts == 2)) { 1319 if (disjuncts == 2) { 1320 FREE(conjunct); conjunct = nullptr; decomp = disjunct; 1321 } else if (conjuncts == 2) { 1322 FREE(disjunct); disjunct = nullptr; decomp = conjunct; 1323 } 1324 1325 if (decomp && (decomp[0] != decomp[1]) && (decomp[0] != f) && (decomp[1] != f)) { 1295 1326 Cudd_Ref(decomp[0]); 1296 1327 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]); 1328 PabloAST * d0 = simplifyAST(decomp[0], variables, builder); 1329 Cudd_RecursiveDeref(mManager, decomp[0]); 1301 1330 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]); 1331 Cudd_RecursiveDeref(mManager, decomp[1]); 1332 return nullptr; 1333 } 1334 1335 PabloAST * d1 = simplifyAST(decomp[1], variables, builder); 1336 Cudd_RecursiveDeref(mManager, decomp[1]); 1309 1337 FREE(decomp); 1310 1338 if (LLVM_UNLIKELY(d1 == nullptr)) { 1311 1339 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); 1340 return nullptr; 1341 } 1342 1343 std::cerr << "d0: " << (ptruint)(d0) << " d1: " << (ptruint)(d1) << " disjunct: " << (disjunct != 0) << " conjunct: " << (conjunct != 0) << std::endl; 1344 1345 if (disjunct) { 1346 return builder.createOr(d0, d1); 1349 1347 } 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); 1348 return builder.createAnd(d0, d1); 1349 } 1350 } 1351 return makeCoverAST(f, variables, builder); 1359 1352 } 1360 1353 … … 1362 1355 * @brief makeCoverAST 1363 1356 **  */ 1364 std::pair<PabloAST *, unsigned> AutoMultiplexing::makeCoverAST(DdManager * manager, DdNode * const f, PabloAST * const variables[], PabloBuilder & builder) const{1357 PabloAST * AutoMultiplexing::makeCoverAST(DdNode * const f, const std::vector<PabloAST *> & variables, PabloBuilder & builder) { 1365 1358 1366 1359 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;1360 const unsigned n = variables.size(); 1361 circular_buffer<PabloAST *> CQ(n); 1362 circular_buffer<PabloAST *> DQ(n); 1363 1364 assert (mManager>size == variables.size()); 1365 1366 int cube[n]; 1374 1367 1375 1368 DdNode * g = f; … … 1377 1370 Cudd_Ref(g); 1378 1371 1379 while (g != Cudd_ReadLogicZero(m anager)) {1380 int length ;1381 DdNode * implicant = Cudd_LargestCube(m anager, g, &length);1372 while (g != Cudd_ReadLogicZero(mManager)) { 1373 int length = 0; 1374 DdNode * implicant = Cudd_LargestCube(mManager, g, &length); 1382 1375 if (LLVM_UNLIKELY(implicant == nullptr)) { 1383 Cudd_RecursiveDeref(m anager, g);1384 return std::make_pair(nullptr, 0);1376 Cudd_RecursiveDeref(mManager, g); 1377 return nullptr; 1385 1378 } 1386 1379 Cudd_Ref(implicant); 1387 DdNode * prime = Cudd_bddMakePrime(m anager, implicant, f);1380 DdNode * prime = Cudd_bddMakePrime(mManager, implicant, f); 1388 1381 if (LLVM_UNLIKELY(prime == nullptr)) { 1389 Cudd_RecursiveDeref(m anager, g);1390 Cudd_RecursiveDeref(m anager, implicant);1391 return std::make_pair(nullptr, 0);1382 Cudd_RecursiveDeref(mManager, g); 1383 Cudd_RecursiveDeref(mManager, implicant); 1384 return nullptr; 1392 1385 } 1393 1386 Cudd_Ref(prime); 1394 Cudd_RecursiveDeref(m anager, implicant);1395 1396 DdNode * h = Cudd_bddAnd(m anager, g, Cudd_Not(prime));1387 Cudd_RecursiveDeref(mManager, implicant); 1388 1389 DdNode * h = Cudd_bddAnd(mManager, g, Cudd_Not(prime)); 1397 1390 if (LLVM_UNLIKELY(h == nullptr)) { 1398 Cudd_RecursiveDeref(m anager, g);1399 Cudd_RecursiveDeref(m anager, prime);1400 return std::make_pair(nullptr, 0);1391 Cudd_RecursiveDeref(mManager, g); 1392 Cudd_RecursiveDeref(mManager, prime); 1393 return nullptr; 1401 1394 } 1402 1395 Cudd_Ref(h); 1403 Cudd_RecursiveDeref(m anager, g);1396 Cudd_RecursiveDeref(mManager, g); 1404 1397 1405 1398 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) { 1399 if (LLVM_UNLIKELY(Cudd_BddToCubeArray(mManager, prime, cube) == 0)) { 1400 Cudd_RecursiveDeref(mManager, g); 1401 Cudd_RecursiveDeref(mManager, prime); 1402 return nullptr; 1403 } 1404 Cudd_RecursiveDeref(mManager, prime); 1405 1406 assert (DQ.empty() && CQ.empty()); 1407 1408 for (auto i = 0; i != n; ++i) { 1414 1409 if (cube[i] == 0) { 1410 assert (!DQ.full()); 1415 1411 DQ.push_back(variables[i]); 1416 1412 } else if (cube[i] == 1) { 1413 assert (!CQ.full()); 1417 1414 CQ.push_back(variables[i]); 1418 1415 } 1419 1416 } 1420 if (!DQ.empty()) { 1417 1418 if (LLVM_UNLIKELY(DQ.empty() && CQ.empty())) { 1419 continue; 1420 } 1421 1422 if (DQ.size() > 0) { 1421 1423 while (DQ.size() > 1) { 1422 1424 PabloAST * v1 = DQ.front(); DQ.pop_front(); 1423 1425 PabloAST * v2 = DQ.front(); DQ.pop_front(); 1424 1426 DQ.push_back(builder.createOr(v1, v2)); 1425 ++count;1426 1427 } 1427 1428 CQ.push_back(builder.createNot(DQ.front())); 1428 DQ.clear(); 1429 } 1429 DQ.pop_front(); 1430 } 1431 1432 assert (!CQ.empty()); 1430 1433 while (CQ.size() > 1) { 1431 1434 PabloAST * v1 = CQ.front(); CQ.pop_front(); 1432 1435 PabloAST * v2 = CQ.front(); CQ.pop_front(); 1433 1436 CQ.push_back(builder.createAnd(v1, v2)); 1434 ++count; 1435 } 1436 SQ.push(CQ.front()); CQ.clear(); 1437 } 1438 Cudd_RecursiveDeref(manager, g); 1439 1437 } 1438 SQ.push(CQ.front()); CQ.pop_front(); 1439 } 1440 Cudd_RecursiveDeref(mManager, g); 1441 if (LLVM_UNLIKELY(SQ.empty())) { 1442 return nullptr; 1443 } 1440 1444 while (SQ.size() > 1) { 1441 1445 PabloAST * v1 = SQ.front(); SQ.pop(); 1442 1446 PabloAST * v2 = SQ.front(); SQ.pop(); 1443 1447 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 //} 1448 } 1449 return SQ.front(); 1450 } 1762 1451 1763 1452 /**  * … … 1776 1465 std::unordered_set<const PabloAST *> encountered; 1777 1466 std::stack<Statement *> scope; 1467 1778 1468 for (Statement * stmt = entry.front(); ; ) { restart: 1779 1469 while ( stmt ) { 1470 1780 1471 for (unsigned i = 0; i != stmt>getNumOperands(); ++i) { 1781 1472 PabloAST * const op = stmt>getOperand(i); … … 1802 1493 continue; 1803 1494 } 1495 1804 1496 encountered.insert(stmt); 1805 1497 stmt = stmt>getNextNode();
Note: See TracChangeset
for help on using the changeset viewer.