Changeset 4727
- Timestamp:
- Aug 16, 2015, 4:23:57 PM (4 years ago)
- Location:
- icGREP/icgrep-devel/icgrep/pablo/optimizers
- Files:
-
- 4 edited
Legend:
- Unmodified
- Added
- Removed
-
icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.cpp
r4725 r4727 1002 1002 assert (i == n); 1003 1003 1004 // MultiplexSetGraph::vertex_descriptor indices[n];1005 // unsigned i = 0;1006 // for (const auto e : make_iterator_range(out_edges(s, mMultiplexSetGraph))) {1007 // indices[i++] = target(e, mMultiplexSetGraph);1008 // }1009 // assert (i == n);1010 // std::sort(std::begin(indices), std::begin(indices) + n);1011 // for (unsigned i = 0; i != n; ++i) {1012 // input[i] = std::get<0>(indices[i]);1013 // assert (input[i]);1014 // }1015 1016 1004 PabloBlock * const block = input[0]->getParent(); 1017 1005 block->setInsertPoint(block->back()); … … 1086 1074 } 1087 1075 } 1088 }1089 1090 /** ------------------------------------------------------------------------------------------------------------- *1091 * @brief isSimplifiable1092 ** ------------------------------------------------------------------------------------------------------------- */1093 inline bool isSimplifiable(const PabloAST * const expr, const PabloBlock * const pb) {1094 switch (expr->getClassTypeId()) {1095 case PabloAST::ClassTypeId::And:1096 case PabloAST::ClassTypeId::Or:1097 case PabloAST::ClassTypeId::Not:1098 case PabloAST::ClassTypeId::Sel:1099 return cast<Statement>(expr)->getParent() == pb;1100 default:1101 return false;1102 }1103 }1104 1105 /** ------------------------------------------------------------------------------------------------------------- *1106 * @brief simplifyAST1107 ** ------------------------------------------------------------------------------------------------------------- */1108 void AutoMultiplexing::simplifyAST(const PabloFunction & function) {1109 1110 // first do a BFS to build a topological ordering of statements we're going to end up visiting1111 // and determine which of those will be terminals in the BDD1112 using Graph = adjacency_list<hash_setS, vecS, bidirectionalS, PabloAST *>;1113 using Vertex = Graph::vertex_descriptor;1114 1115 raw_os_ostream out(std::cerr);1116 1117 unsigned index = 0;1118 1119 // TODO: this should build a single graph and iterate by connected component instead.1120 while (!mSimplificationQueue.empty()) {1121 1122 Graph G;1123 std::unordered_map<PabloAST *, unsigned> M;1124 std::queue<Statement *> Q;1125 const std::vector<Statement *> set(std::move(mSimplificationQueue.front()));1126 1127 mSimplificationQueue.pop();1128 1129 ++index;1130 1131 for (unsigned i = 0; i != set.size(); ++i) {1132 1133 const auto u = add_vertex(set[i], G);1134 M.insert(std::make_pair(set[i], u));1135 for (PabloAST * user : set[i]->users()) {1136 auto f = M.find(user);1137 Vertex v = 0;1138 if (f == M.end()) {1139 v = add_vertex(user, G);1140 M.insert(std::make_pair(user, v));1141 if (isSimplifiable(user, set[i]->getParent())) {1142 Q.push(cast<Statement>(user));1143 }1144 } else { // if (f != M.end()) {1145 v = f->second;1146 }1147 add_edge(u, v, G);1148 }1149 }1150 1151 while (!Q.empty()) {1152 1153 Statement * const var = Q.front(); Q.pop();1154 1155 const Vertex u = M[var];1156 1157 for (unsigned i = 0; i != var->getNumOperands(); ++i) {1158 PabloAST * operand = var->getOperand(i);1159 auto f = M.find(operand);1160 Vertex v = 0;1161 if (LLVM_UNLIKELY(f == M.end())) {1162 v = add_vertex(operand, G);1163 M.insert(std::make_pair(operand, v));1164 } else { // if (f != M.end()) {1165 v = f->second;1166 }1167 add_edge(v, u, G);1168 }1169 1170 for (PabloAST * user : var->users()) {1171 auto f = M.find(user);1172 Vertex v = 0;1173 if (LLVM_LIKELY(f == M.end())) {1174 v = add_vertex(user, G);1175 M.insert(std::make_pair(user, v));1176 if (isSimplifiable(user, var->getParent())) {1177 Q.push(cast<Statement>(user));1178 }1179 } else { // if (f != M.end()) {1180 v = f->second;1181 }1182 add_edge(u, v, G);1183 }1184 }1185 1186 // Even though the above BFS attempts to stop at each non-Boolean function, it's possible1187 // that one takes an input derived from the initial set whose output is used as part of1188 // another computation.1189 1190 std::vector<unsigned> C(num_vertices(G), 0);1191 std::vector<Vertex> ordering;1192 ordering.reserve(num_vertices(G));1193 topological_sort(G, std::back_inserter(ordering));1194 1195 unsigned n = 0;1196 1197 for (auto ui = ordering.rbegin(); ui != ordering.rend(); ++ui) {1198 Vertex u = *ui;1199 PabloAST * expr = G[u];1200 switch (expr->getClassTypeId()) {1201 case PabloAST::ClassTypeId::And:1202 case PabloAST::ClassTypeId::Or:1203 case PabloAST::ClassTypeId::Not:1204 case PabloAST::ClassTypeId::Sel:1205 1206 1207 break;1208 default: // this vertex corresponds to a non-Boolean function. Everything that depends1209 // on it must be removed from the current graph.1210 if (in_degree(u, G) > 0 && out_degree(u, G) > 0) {1211 ++n;1212 // std::queue<Vertex> Q;1213 // for (;;) {1214 // C[u] = n;1215 // for (const auto e : make_iterator_range(out_edges(u, G))) {1216 // Q.push(target(e, G));1217 // }1218 // if (Q.empty()) {1219 // break;1220 // }1221 // u = Q.front();1222 // Q.pop();1223 // }1224 }1225 }1226 }1227 1228 1229 if (n) {1230 continue;1231 }1232 1233 1234 1235 // std::vector<Statement *> split_set;1236 1237 // for (auto ui = ordering.rbegin(); ui != ordering.rend(); ++ui) {1238 // Vertex u = *ui;1239 // PabloAST * expr = G[u];1240 // switch (expr->getClassTypeId()) {1241 // case PabloAST::ClassTypeId::And:1242 // case PabloAST::ClassTypeId::Or:1243 // case PabloAST::ClassTypeId::Not:1244 // case PabloAST::ClassTypeId::Sel:1245 // break;1246 // default: // this vertex corresponds to a non-Boolean function. Everything that depends1247 // // on it must be removed from the current graph.1248 // if (in_degree(u, G) > 0 && out_degree(u, G) > 0) {1249 // split_set.push_back(cast<Statement>(G[u]));1250 // std::queue<Vertex> Q;1251 // for (;;) {1252 // for (const auto e : make_iterator_range(out_edges(u, G))) {1253 // Q.push(target(e, G));1254 // }1255 // clear_out_edges(u, G);1256 // if (Q.empty()) {1257 // break;1258 // }1259 // u = Q.front();1260 // Q.pop();1261 // }1262 // }1263 // }1264 // }1265 1266 // if (!split_set.empty()) {1267 // mSimplificationQueue.push(std::move(split_set));1268 // }1269 1270 // count the number of sources (sinks) so we know how many variables (terminals) will exist in the BDD1271 std::vector<Vertex> inputs;1272 flat_set<Vertex> terminals;1273 1274 for (Vertex u : ordering) {1275 if (in_degree(u, G) == 0) {1276 inputs.push_back(u);1277 }1278 if (out_degree(u, G) == 0) {1279 // the inputs to the sinks are the terminals of the BDD1280 for (auto e : make_iterator_range(in_edges(u, G))) {1281 terminals.insert(source(e, G));1282 }1283 }1284 }1285 1286 // for (auto ui = ordering.begin(); ui != ordering.end(); ) {1287 // const Vertex u = *ui;1288 // if (in_degree(u, G) == 0 && out_degree(u, G) == 0) {1289 // ui = ordering.erase(ui);1290 // continue;1291 // } else if (in_degree(u, G) == 0) {1292 // inputs.push_back(u);1293 // } else if (out_degree(u, G) == 0) {1294 // // the inputs to the sinks are the terminals of the BDD1295 // for (auto e : make_iterator_range(in_edges(u, G))) {1296 // terminals.insert(source(e, G));1297 // }1298 // }1299 // ++ui;1300 // }1301 1302 out << "\ndigraph G" << index << " {\n";1303 for (auto ui = ordering.rbegin(); ui != ordering.rend(); ++ui) {1304 std::string tmp;1305 raw_string_ostream name(tmp);1306 PabloPrinter::print(G[*ui], name);1307 out << "v" << *ui << " [label=\"" << name.str() << "\"];\n";1308 }1309 for (auto e : make_iterator_range(edges(G))) {1310 out << "v" << source(e, G) << " -> v" << target(e, G) << '\n';1311 }1312 1313 out << "{ rank=same;";1314 for (auto u : make_iterator_range(vertices(G))) {1315 if (in_degree(u, G) == 0) {1316 out << " v" << u;1317 }1318 }1319 out << "}\n";1320 1321 out << "{ rank=same;";1322 for (auto u : make_iterator_range(vertices(G))) {1323 if (out_degree(u, G) == 0) {1324 out << " v" << u;1325 }1326 }1327 out << "}\n";1328 1329 out << "}\n\n";1330 out.flush();1331 1332 if (index == 9) {1333 continue;1334 }1335 n = inputs.size();1336 1337 mManager = Cudd_Init(n, 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0);1338 Cudd_AutodynEnable(mManager, CUDD_REORDER_LAZY_SIFT);1339 1340 std::vector<PabloAST *> nodes(n);1341 std::vector<DdNode *> characterization(num_vertices(G), nullptr);1342 for (unsigned i = 0; i != n; ++i) {1343 nodes[i] = G[inputs[i]];1344 assert (nodes[i]);1345 characterization[inputs[i]] = Cudd_bddIthVar(mManager, i);1346 }1347 1348 for (auto ui = ordering.rbegin(); ui != ordering.rend(); ++ui) {1349 1350 const Vertex u = *ui;1351 1352 if (characterization[u]) {1353 continue;1354 }1355 1356 std::array<DdNode *, 3> input;1357 1358 unsigned i = 0;1359 for (const auto e : make_iterator_range(in_edges(u, G))) {1360 input[i] = characterization[source(e, G)];1361 if (input[i] == nullptr) {1362 std::string tmp;1363 raw_string_ostream out(tmp);1364 out << "Uncharacterized input! ";1365 PabloPrinter::print(G[source(e, G)], out);1366 throw std::runtime_error(out.str());1367 }1368 ++i;1369 }1370 1371 DdNode * bdd = nullptr;1372 bool characterized = true;1373 switch (G[u]->getClassTypeId()) {1374 case PabloAST::ClassTypeId::And:1375 bdd = And(input[0], input[1]);1376 break;1377 case PabloAST::ClassTypeId::Or:1378 bdd = Or(input[0], input[1]);1379 break;1380 case PabloAST::ClassTypeId::Not:1381 bdd = Not(input[0]);1382 break;1383 case PabloAST::ClassTypeId::Sel:1384 bdd = Ite(input[0], input[1], input[2]);1385 break;1386 default: characterized = false; break;1387 }1388 1389 if (characterized) {1390 Ref(bdd);1391 characterization[u] = bdd;1392 }1393 }1394 1395 assert (Cudd_DebugCheck(mManager) == 0);1396 Cudd_ReduceHeap(mManager, CUDD_REORDER_SIFT, 0);1397 1398 assert (mManager->size == nodes.size());1399 1400 for (Vertex t : terminals) {1401 1402 PabloPrinter::print(cast<Statement>(G[t]), " >> ", out);1403 out << '\n';1404 out.flush();1405 1406 Statement * stmt = cast<Statement>(G[t]);1407 1408 PabloBuilder builder(*(stmt->getParent()));1409 1410 DdNode * const f = characterization[t];1411 assert (f);1412 Cudd_Ref(f);1413 1414 PabloAST * expr = simplifyAST(f, nodes, builder);1415 if (expr) {1416 1417 PabloPrinter::print(cast<Statement>(expr), " replacement: ", out);1418 out << '\n';1419 out.flush();1420 1421 stmt->replaceWith(expr, false, true);1422 }1423 Cudd_RecursiveDeref(mManager, f);1424 }1425 1426 Cudd_Quit(mManager);1427 1428 }1429 }1430 1431 /** ------------------------------------------------------------------------------------------------------------- *1432 * @brief simplifyAST1433 ** ------------------------------------------------------------------------------------------------------------- */1434 //void AutoMultiplexing::simplifyAST(const PabloFunction & function) {1435 1436 // // first do a BFS to build a topological ordering of statements we're going to end up visiting1437 // // and determine which of those will be terminals in the BDD1438 // using Graph = adjacency_list<hash_setS, vecS, bidirectionalS, PabloAST *>;1439 // using Vertex = Graph::vertex_descriptor;1440 1441 // raw_os_ostream out(std::cerr);1442 1443 // // TODO: this should build a single graph and iterate by connected component instead.1444 // for (const auto & muxed : mSimplificationQueue) {1445 1446 // Graph G;1447 // std::unordered_map<PabloAST *, unsigned> M;1448 // std::queue<Statement *> Q;1449 1450 // out << "-----------------------------------------------------------------------------------\n";1451 // PabloPrinter::print(function.getEntryBlock().statements(), out);1452 // out << "-----------------------------------------------------------------------------------\n"; out.flush();1453 1454 1455 // for (unsigned i = 0; i != muxed.size(); ++i) {1456 1457 // const auto u = add_vertex(muxed[i], G);1458 // M.insert(std::make_pair(muxed[i], u));1459 // for (PabloAST * user : muxed[i]->users()) {1460 // auto f = M.find(user);1461 // Vertex v = 0;1462 // if (f == M.end()) {1463 // v = add_vertex(user, G);1464 // M.insert(std::make_pair(user, v));1465 // switch (user->getClassTypeId()) {1466 // case PabloAST::ClassTypeId::And:1467 // case PabloAST::ClassTypeId::Or:1468 // case PabloAST::ClassTypeId::Not:1469 // case PabloAST::ClassTypeId::Sel:1470 // Q.push(cast<Statement>(user));1471 // default: break;1472 // }1473 // } else { // if (f != M.end()) {1474 // v = f->second;1475 // }1476 // add_edge(u, v, G);1477 // }1478 // }1479 1480 // while (!Q.empty()) {1481 // Statement * const var = Q.front(); Q.pop();1482 1483 // const Vertex u = M[var];1484 1485 // for (unsigned i = 0; i != var->getNumOperands(); ++i) {1486 // PabloAST * operand = var->getOperand(i);1487 // auto f = M.find(operand);1488 // Vertex v = 0;1489 // if (LLVM_UNLIKELY(f == M.end())) {1490 // v = add_vertex(operand, G);1491 // M.insert(std::make_pair(operand, v));1492 // } else { // if (f != M.end()) {1493 // v = f->second;1494 // }1495 // add_edge(v, u, G);1496 // }1497 1498 // for (PabloAST * user : var->users()) {1499 // auto f = M.find(user);1500 // Vertex v = 0;1501 // if (LLVM_LIKELY(f == M.end())) {1502 // v = add_vertex(user, G);1503 // M.insert(std::make_pair(user, v));1504 // switch (user->getClassTypeId()) {1505 // case PabloAST::ClassTypeId::And:1506 // case PabloAST::ClassTypeId::Or:1507 // case PabloAST::ClassTypeId::Not:1508 // case PabloAST::ClassTypeId::Sel:1509 // Q.push(cast<Statement>(user));1510 // default: break;1511 // }1512 // } else { // if (f != M.end()) {1513 // v = f->second;1514 // }1515 // add_edge(u, v, G);1516 // }1517 // }1518 1519 // for (auto u : make_iterator_range(vertices(G))) {1520 // PabloAST * expr = G[u];1521 // switch (expr->getClassTypeId()) {1522 // case PabloAST::ClassTypeId::And:1523 // case PabloAST::ClassTypeId::Or:1524 // case PabloAST::ClassTypeId::Not:1525 // case PabloAST::ClassTypeId::Sel:1526 // break;1527 // default: // this vertex corresponds to a non-Boolean function. It needs to be split.1528 // if (in_degree(u, G) > 0 && out_degree(u, G) > 0) {1529 // Vertex v = add_vertex(expr, G);1530 // for (auto e : make_iterator_range(out_edges(u, G))) {1531 // add_edge(v, target(e, G), G);1532 // }1533 // clear_out_edges(u, G);1534 // }1535 // }1536 // }1537 1538 // out << "\ndigraph x {\n";1539 // for (auto u : make_iterator_range(vertices(G))) {1540 // std::string tmp;1541 // raw_string_ostream name(tmp);1542 // PabloPrinter::print(G[u], name);1543 // out << "v" << u << " [label=\"" << name.str() << "\"];\n";1544 // }1545 // for (auto e : make_iterator_range(edges(G))) {1546 // out << "v" << source(e, G) << " -> v" << target(e, G) << '\n';1547 // }1548 1549 // out << " { rank=same;";1550 // for (auto u : make_iterator_range(vertices(G))) {1551 // if (in_degree(u, G) == 0) {1552 // out << " v" << u;1553 // }1554 // }1555 // out << "}\n";1556 1557 // out << " { rank=same;";1558 // for (auto u : make_iterator_range(vertices(G))) {1559 // if (out_degree(u, G) == 0) {1560 // out << " v" << u;1561 // }1562 // }1563 // out << "}\n";1564 1565 // out << "}\n\n";1566 // out.flush();1567 1568 // // count the number of sources (sinks) so we know how many variables (terminals) will exist in the BDD1569 // std::vector<Vertex> inputs;1570 // flat_set<Vertex> terminals;1571 1572 // for (auto u : make_iterator_range(vertices(G))) {1573 // if (in_degree(u, G) == 0) {1574 // inputs.push_back(u);1575 // }1576 // if (out_degree(u, G) == 0) {1577 // // the inputs to the sinks become the terminals in the BDD1578 // for (auto e : make_iterator_range(in_edges(u, G))) {1579 // terminals.insert(source(e, G));1580 // }1581 // }1582 // }1583 1584 1585 1586 1587 // const auto n = inputs.size();1588 1589 // mManager = Cudd_Init(n, 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0);1590 // Cudd_AutodynEnable(mManager, CUDD_REORDER_LAZY_SIFT);1591 1592 // std::vector<PabloAST *> nodes(n);1593 // std::vector<DdNode *> characterization(num_vertices(G), nullptr);1594 // for (unsigned i = 0; i != n; ++i) {1595 // nodes[i] = G[inputs[i]];1596 // assert (nodes[i]);1597 // characterization[inputs[i]] = Cudd_bddIthVar(mManager, i);1598 // }1599 1600 // std::vector<Vertex> ordering;1601 // ordering.reserve(num_vertices(G));1602 // topological_sort(G, std::back_inserter(ordering));1603 1604 // for (auto ui = ordering.rbegin(); ui != ordering.rend(); ++ui) {1605 1606 // const Vertex u = *ui;1607 1608 // if (characterization[u]) {1609 // continue;1610 // }1611 1612 // std::array<DdNode *, 3> input;1613 1614 // unsigned i = 0;1615 // for (const auto e : make_iterator_range(in_edges(u, G))) {1616 // input[i] = characterization[source(e, G)];1617 // if (input[i] == nullptr) {1618 // std::string tmp;1619 // raw_string_ostream out(tmp);1620 // out << "Uncharacterized input! ";1621 // PabloPrinter::print(G[source(e, G)], out);1622 // throw std::runtime_error(out.str());1623 // }1624 // ++i;1625 // }1626 1627 // DdNode * bdd = nullptr;1628 // bool characterized = true;1629 // switch (G[u]->getClassTypeId()) {1630 // case PabloAST::ClassTypeId::And:1631 // bdd = And(input[0], input[1]);1632 // break;1633 // case PabloAST::ClassTypeId::Or:1634 // bdd = Or(input[0], input[1]);1635 // break;1636 // case PabloAST::ClassTypeId::Not:1637 // bdd = Not(input[0]);1638 // break;1639 // case PabloAST::ClassTypeId::Sel:1640 // bdd = Ite(input[0], input[1], input[2]);1641 // break;1642 // default: characterized = false; break;1643 // }1644 1645 // if (characterized) {1646 // Ref(bdd);1647 // characterization[u] = bdd;1648 // }1649 // }1650 1651 // assert (Cudd_DebugCheck(mManager) == 0);1652 // Cudd_ReduceHeap(mManager, CUDD_REORDER_SIFT, 0);1653 1654 // assert (mManager->size == nodes.size());1655 1656 // for (Vertex t : terminals) {1657 1658 // PabloPrinter::print(cast<Statement>(G[t]), " >> ", out);1659 // out << '\n';1660 // out.flush();1661 1662 // Statement * stmt = cast<Statement>(G[t]);1663 1664 // PabloBuilder builder(*(stmt->getParent()));1665 1666 // DdNode * const f = characterization[t];1667 // Cudd_Ref(f);1668 1669 // PabloAST * expr = simplifyAST(f, nodes, builder);1670 // if (expr) {1671 1672 // PabloPrinter::print(cast<Statement>(expr), " replacement: ", out);1673 // out << '\n';1674 // out.flush();1675 1676 // stmt->replaceWith(expr, false, true);1677 // }1678 // Cudd_RecursiveDeref(mManager, f);1679 // }1680 1681 // Cudd_Quit(mManager);1682 1683 // }1684 //}1685 1686 /** ------------------------------------------------------------------------------------------------------------- *1687 * @brief simplifyAST1688 ** ------------------------------------------------------------------------------------------------------------- */1689 PabloAST * AutoMultiplexing::simplifyAST(DdNode * const f, const std::vector<PabloAST *> & variables, PabloBuilder & builder) {1690 assert (!NoSatisfyingAssignment(f));1691 DdNode * g = Cudd_FindEssential(mManager, f);1692 if (g && Cudd_SupportSize(mManager, g) > 0) {1693 if (g == f) { // every variable is essential1694 return makeCoverAST(f, variables, builder);1695 }1696 Cudd_Ref(g);1697 PabloAST * c0 = makeCoverAST(g, variables, builder);1698 if (LLVM_UNLIKELY(c0 == nullptr)) {1699 Cudd_RecursiveDeref(mManager, g);1700 return nullptr;1701 }1702 DdNode * h = Cudd_Cofactor(mManager, f, g);1703 Cudd_Ref(h);1704 PabloAST * c1 = simplifyAST(h, variables, builder);1705 if (LLVM_UNLIKELY(c1 == nullptr)) {1706 Cudd_RecursiveDeref(mManager, g);1707 Cudd_RecursiveDeref(mManager, h);1708 cast<Statement>(c0)->eraseFromParent(true);1709 return nullptr;1710 }1711 assert (And(g, h) == f);1712 Cudd_RecursiveDeref(mManager, g);1713 Cudd_RecursiveDeref(mManager, h);1714 return builder.createAnd(c0, c1, "escf");1715 }1716 1717 DdNode ** disjunct = nullptr;1718 int disjuncts = Cudd_bddIterDisjDecomp(mManager, f, &disjunct);1719 assert (disjuncts < 2 || Or(disjunct[0], disjunct[1]) == f);1720 1721 DdNode ** conjunct = nullptr;1722 int conjuncts = Cudd_bddIterConjDecomp(mManager, f, &conjunct);1723 assert (conjuncts < 2 || And(conjunct[0], conjunct[1]) == f);1724 1725 if (LLVM_LIKELY(disjuncts == 2 && conjuncts == 2)) {1726 if (Cudd_SharingSize(disjunct, 2) > Cudd_SharingSize(conjunct, 2)) {1727 disjuncts = 0;1728 }1729 }1730 1731 DdNode * decomp[] = { nullptr, nullptr };1732 if (disjuncts == 2) {1733 memcpy(decomp, disjunct, sizeof(DdNode *) * 2);1734 } else if (conjuncts == 2) {1735 memcpy(decomp, conjunct, sizeof(DdNode *) * 2);1736 }1737 1738 FREE(disjunct);1739 FREE(conjunct);1740 1741 if ((decomp[0] != decomp[1]) && (decomp[0] != f) && (decomp[1] != f)) {1742 Cudd_Ref(decomp[0]);1743 Cudd_Ref(decomp[1]);1744 PabloAST * d0 = simplifyAST(decomp[0], variables, builder);1745 Cudd_RecursiveDeref(mManager, decomp[0]);1746 if (LLVM_UNLIKELY(d0 == nullptr)) {1747 Cudd_RecursiveDeref(mManager, decomp[1]);1748 return nullptr;1749 }1750 1751 PabloAST * d1 = simplifyAST(decomp[1], variables, builder);1752 Cudd_RecursiveDeref(mManager, decomp[1]);1753 if (LLVM_UNLIKELY(d1 == nullptr)) {1754 cast<Statement>(d0)->eraseFromParent(true);1755 return nullptr;1756 }1757 1758 if (disjuncts == 2) {1759 return builder.createOr(d0, d1, "disj");1760 } else {1761 return builder.createAnd(d0, d1, "conj");1762 }1763 }1764 return makeCoverAST(f, variables, builder);1765 }1766 1767 /** ------------------------------------------------------------------------------------------------------------- *1768 * @brief makeCoverAST1769 ** ------------------------------------------------------------------------------------------------------------- */1770 PabloAST * AutoMultiplexing::makeCoverAST(DdNode * const f, const std::vector<PabloAST *> & variables, PabloBuilder & builder) {1771 1772 std::queue<PabloAST *> SQ;1773 const unsigned n = variables.size();1774 circular_buffer<PabloAST *> CQ(n);1775 circular_buffer<PabloAST *> DQ(n);1776 1777 assert (mManager->size == variables.size());1778 1779 int cube[n];1780 1781 DdNode * g = f;1782 1783 Cudd_Ref(g);1784 1785 while (g != Cudd_ReadLogicZero(mManager)) {1786 int length = 0;1787 DdNode * implicant = Cudd_LargestCube(mManager, g, &length);1788 if (LLVM_UNLIKELY(implicant == nullptr)) {1789 Cudd_RecursiveDeref(mManager, g);1790 return nullptr;1791 }1792 Cudd_Ref(implicant);1793 DdNode * prime = Cudd_bddMakePrime(mManager, implicant, f);1794 if (LLVM_UNLIKELY(prime == nullptr)) {1795 Cudd_RecursiveDeref(mManager, g);1796 Cudd_RecursiveDeref(mManager, implicant);1797 return nullptr;1798 }1799 Cudd_Ref(prime);1800 Cudd_RecursiveDeref(mManager, implicant);1801 1802 DdNode * h = Cudd_bddAnd(mManager, g, Cudd_Not(prime));1803 if (LLVM_UNLIKELY(h == nullptr)) {1804 Cudd_RecursiveDeref(mManager, g);1805 Cudd_RecursiveDeref(mManager, prime);1806 return nullptr;1807 }1808 Cudd_Ref(h);1809 Cudd_RecursiveDeref(mManager, g);1810 1811 g = h;1812 if (LLVM_UNLIKELY(Cudd_BddToCubeArray(mManager, prime, cube) == 0)) {1813 Cudd_RecursiveDeref(mManager, g);1814 Cudd_RecursiveDeref(mManager, prime);1815 return nullptr;1816 }1817 Cudd_RecursiveDeref(mManager, prime);1818 1819 assert (DQ.empty() && CQ.empty());1820 1821 for (auto i = 0; i != n; ++i) {1822 assert (cube[i] >= 0 && cube[i] <= 2);1823 if (cube[i] == 0) {1824 assert (!DQ.full());1825 DQ.push_back(variables[i]);1826 } else if (cube[i] == 1) {1827 assert (!CQ.full());1828 CQ.push_back(variables[i]);1829 }1830 }1831 1832 if (LLVM_UNLIKELY(DQ.empty() && CQ.empty())) {1833 throw std::runtime_error("Error! statement contains no elements!");1834 }1835 1836 if (DQ.size() > 0) {1837 while (DQ.size() > 1) {1838 PabloAST * v1 = DQ.front(); DQ.pop_front();1839 PabloAST * v2 = DQ.front(); DQ.pop_front();1840 DQ.push_back(builder.createOr(v1, v2));1841 }1842 CQ.push_back(builder.createNot(DQ.front()));1843 DQ.pop_front();1844 }1845 1846 assert (!CQ.empty());1847 while (CQ.size() > 1) {1848 PabloAST * v1 = CQ.front(); CQ.pop_front();1849 PabloAST * v2 = CQ.front(); CQ.pop_front();1850 CQ.push_back(builder.createAnd(v1, v2));1851 }1852 SQ.push(CQ.front()); CQ.pop_front();1853 }1854 Cudd_RecursiveDeref(mManager, g);1855 if (LLVM_UNLIKELY(SQ.empty())) {1856 throw std::runtime_error("Error! statement queue empty!");1857 }1858 while (SQ.size() > 1) {1859 PabloAST * v1 = SQ.front(); SQ.pop();1860 PabloAST * v2 = SQ.front(); SQ.pop();1861 SQ.push(builder.createOr(v1, v2));1862 }1863 return SQ.front();1864 1076 } 1865 1077 … … 1919 1131 } 1920 1132 1921 /** ------------------------------------------------------------------------------------------------------------- *1922 * @brief reassociation1923 *1924 ** ------------------------------------------------------------------------------------------------------------- */1925 inline void AutoMultiplexing::reassociate(PabloBlock & entry) const {1926 1927 }1928 1929 1133 } // end of namespace pablo 1930 1134 -
icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.hpp
r4725 r4727 50 50 void applySubsetConstraints(); 51 51 void multiplexSelectedIndependentSets(); 52 void simplifyAST(const PabloFunction & function);53 PabloAST * simplifyAST(DdNode * const f, const std::vector<PabloAST *> & variables, PabloBuilder & builder);54 PabloAST * makeCoverAST(DdNode * const f, const std::vector<PabloAST *> & variables, PabloBuilder & builder);55 52 void topologicalSort(PabloBlock & entry) const; 56 void reassociate(PabloBlock & entry) const;57 53 inline AutoMultiplexing() 58 54 : mVariables(0) -
icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_bddminimization.cpp
r4725 r4727 12 12 #include <pablo/optimizers/pablo_simplifier.hpp> 13 13 #include <boost/container/flat_set.hpp> 14 #include <boost/container/flat_map.hpp> 15 #include <boost/graph/adjacency_list.hpp> 14 16 15 17 using namespace llvm; … … 21 23 bool BDDMinimizationPass::optimize(PabloFunction & function, const bool full) { 22 24 BDDMinimizationPass am; 23 am.eliminateLogicallyEquivalentStatements(function);24 25 if (full) { 25 26 am.simplifyAST(function); 26 27 } 28 am.eliminateLogicallyEquivalentStatements(function); 27 29 return Simplifier::optimize(function); 28 30 } … … 196 198 ** ------------------------------------------------------------------------------------------------------------- */ 197 199 inline void BDDMinimizationPass::simplifyAST(PabloFunction & function) { 198 PabloBuilder builder(function.getEntryBlock()); 199 std::vector<Statement *> terminals; 200 Terminals terminals; 200 201 for (unsigned i = 0; i != function.getNumOfResults(); ++i) { 201 202 terminals.push_back(function.getResult(i)); 202 203 } 203 simplifyAST(builder, terminals); 204 } 204 simplifyAST(function.getEntryBlock(), std::move(terminals)); 205 } 206 207 /** ------------------------------------------------------------------------------------------------------------- * 208 * @brief promoteSimpleInputDerivationsToAssigns 209 ** ------------------------------------------------------------------------------------------------------------- */ 210 inline void BDDMinimizationPass::promoteSimpleInputDerivationsToAssigns(PabloFunction & function) { 211 212 using Graph = adjacency_list<hash_setS, vecS, bidirectionalS, PabloAST *>; 213 using Vertex = Graph::vertex_descriptor; 214 215 Graph G; 216 flat_map<PabloAST *, Vertex> M; 217 std::queue<Vertex> Q; 218 for (unsigned i = 0; i != function.getNumOfParameters(); ++i) { 219 PabloAST * var = function.getParameter(i); 220 const Vertex u = add_vertex(var, G); 221 Q.push(u); 222 M[var] = u; 223 } 224 225 for (;;) { 226 const Vertex u = Q.front(); Q.pop(); 227 for (PabloAST * user : G[u]->users()) { 228 auto f = M.find(user); 229 Vertex v = 0; 230 if (f == M.end()) { 231 v = add_vertex(user, G); 232 switch (user->getClassTypeId()) { 233 case PabloAST::ClassTypeId::And: 234 case PabloAST::ClassTypeId::Or: 235 case PabloAST::ClassTypeId::Not: 236 case PabloAST::ClassTypeId::Xor: 237 case PabloAST::ClassTypeId::Sel: 238 Q.push(v); 239 default: 240 M[user] = v; 241 } 242 } else { 243 v = f->second; 244 } 245 add_edge(u, v, G); 246 } 247 248 if (Q.empty()) { 249 break; 250 } 251 } 252 253 flat_set<Statement *> promotions; 254 255 for (Vertex u : make_iterator_range(vertices(G))) { 256 if (out_degree(u, G) == 0) { 257 Statement * stmt = cast<Statement>(G[u]); 258 if (isa<Assign>(stmt)) { 259 continue; 260 } 261 for (unsigned i = 0; i != stmt->getNumOperands(); ++i) { 262 if (Statement * expr = dyn_cast<Statement>(stmt->getOperand(i))) { 263 promotions.insert(expr); 264 } 265 } 266 } 267 } 268 269 for (Statement * promoted : promotions) { 270 PabloBlock * block = promoted->getParent(); 271 block->setInsertPoint(promoted); 272 Assign * replacement = block->createAssign("t", promoted); 273 promoted->replaceAllUsesWith(replacement); 274 } 275 276 raw_os_ostream out(std::cerr); 277 PabloPrinter::print(function.getEntryBlock().statements(), out); 278 out << "**************************************\n"; 279 out.flush(); 280 } 281 205 282 206 283 /** ------------------------------------------------------------------------------------------------------------- * … … 212 289 case PabloAST::ClassTypeId::Or: 213 290 case PabloAST::ClassTypeId::Not: 214 case PabloAST::ClassTypeId::Sel:291 // case PabloAST::ClassTypeId::Sel: 215 292 return cast<Statement>(expr)->getParent() == pb; 216 293 default: … … 222 299 * @brief simplifyAST 223 300 ** ------------------------------------------------------------------------------------------------------------- */ 224 void BDDMinimizationPass::simplifyAST(PabloB uilder & block, std::vector<Statement *>& terminals) {301 void BDDMinimizationPass::simplifyAST(PabloBlock & block, Terminals && terminals) { 225 302 226 303 for (Statement * stmt : block) { 227 if (isa<While>(stmt)) { 228 PabloBuilder builder(cast<If>(stmt)->getBody(), block); 229 std::vector<Statement *> terminals; 304 if (isa<If>(stmt)) { 305 Terminals terminals; 230 306 for (Assign * var : cast<const If>(stmt)->getDefined()) { 231 307 terminals.push_back(var); 232 308 } 233 simplifyAST( builder, terminals);234 for (Assign * var : cast<const If>(stmt)->getDefined()) {235 block.record(var);236 }237 continue;309 simplifyAST(cast<If>(stmt)->getBody(), std::move(terminals)); 310 // for (Assign * var : cast<const If>(stmt)->getDefined()) { 311 // block.record(var); 312 // } 313 // continue; 238 314 } else if (isa<While>(stmt)) { 239 PabloBuilder builder(cast<While>(stmt)->getBody(), block); 240 std::vector<Statement *> terminals; 315 Terminals terminals; 241 316 for (Next * var : cast<const While>(stmt)->getVariants()) { 242 317 terminals.push_back(var); 243 318 } 244 simplifyAST(builder, terminals); 245 for (Next * var : cast<const While>(stmt)->getVariants()) { 246 block.record(var); 247 } 248 continue; 249 } 250 block.record(stmt); 251 } 252 253 std::queue<Statement *> Q; 254 std::vector<PabloAST *> variables; 255 256 while (!terminals.empty()) { 257 319 simplifyAST(cast<While>(stmt)->getBody(), std::move(terminals)); 320 // for (Next * var : cast<const While>(stmt)->getVariants()) { 321 // block.record(var); 322 // } 323 // continue; 324 } 325 // block.record(stmt); 326 } 327 328 for (;;) { 329 330 flat_set<Statement *> inputs; 258 331 for (Statement * term : terminals) { 332 for (unsigned i = 0; i != term->getNumOperands(); ++i) { 333 if (isSimplifiable(term->getOperand(i), term->getParent())) { 334 inputs.insert(cast<Statement>(term->getOperand(i))); 335 } 336 } 337 } 338 339 if (inputs.empty()) { 340 break; 341 } 342 343 std::queue<Statement *> Q; 344 for (Statement * term : inputs) { 259 345 Q.push(term); 260 346 } 261 347 348 flat_set<PabloAST *> visited; 349 flat_set<PabloAST *> variables; 262 350 // find the variables for this set of terminals 263 351 for (;;) { 264 352 Statement * stmt = Q.front(); 265 353 Q.pop(); 266 mCharacterizationMap[stmt] = nullptr;267 354 for (unsigned i = 0; i != stmt->getNumOperands(); ++i) { 268 if (isSimplifiable(stmt->getOperand(i), stmt->getParent())) { 269 Q.push(cast<Statement>(stmt->getOperand(i))); 270 } else { 271 variables.push_back(stmt->getOperand(i)); 355 if (visited.count(stmt->getOperand(i)) == 0) { 356 if (isSimplifiable(stmt->getOperand(i), stmt->getParent())) { 357 Q.push(cast<Statement>(stmt->getOperand(i))); 358 } else { 359 variables.insert(stmt->getOperand(i)); 360 } 361 visited.insert(stmt->getOperand(i)); 272 362 } 273 363 } … … 277 367 } 278 368 279 std::sort(variables.begin(), variables.end()); 280 std::unique(variables.begin(), variables.end()); 281 282 369 mVariables.clear(); 283 370 mManager = Cudd_Init(variables.size(), 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0); 284 371 Cudd_AutodynEnable(mManager, CUDD_REORDER_LAZY_SIFT); 285 286 unsigned i = 0;287 372 for (PabloAST * var : variables) { 288 mCharacterizationMap[var] = Cudd_bddIthVar(mManager, i++); 289 } 290 291 for (PabloAST * term : terminals) { 292 characterizeTerminalBddTree(term); 293 } 373 mCharacterizationMap.insert(std::make_pair(var, Cudd_bddIthVar(mManager, mVariables.size()))); 374 mVariables.push_back(var); 375 } 376 377 378 std::vector<DdNode *> nodes; 379 for (PabloAST * term : inputs) { 380 nodes.push_back(characterizeTerminal(term)); 381 } 382 Cudd_AutodynDisable(mManager); 294 383 Cudd_ReduceHeap(mManager, CUDD_REORDER_SIFT, 0); 295 384 296 for (Statement * term : terminals) { 297 DdNode * const f = mCharacterizationMap[term]; 385 visited.clear(); 386 for (Statement * input : inputs) { 387 DdNode * const f = mCharacterizationMap[input]; assert (f); 298 388 Cudd_Ref(f); 299 PabloAST * replacement = simplifyAST(f, variables, block); 389 block.setInsertPoint(input); 390 PabloBuilder builder(block); 391 PabloAST * replacement = simplifyAST(f, builder); 300 392 if (replacement) { 301 term->replaceWith(replacement, false, true);393 input->replaceWith(replacement, false, true); 302 394 } 303 395 Cudd_RecursiveDeref(mManager, f); … … 311 403 terminals.clear(); 312 404 for (PabloAST * var : variables) { 313 if ( isa<Statement>(var) && cast<Statement>(var)->getParent() == block.getPabloBlock()) {405 if (LLVM_LIKELY(isa<Statement>(var) && cast<Statement>(var)->getParent() == &block)) { 314 406 terminals.push_back(cast<Statement>(var)); 315 407 } 316 408 } 317 } 318 319 } 320 321 ///** ------------------------------------------------------------------------------------------------------------- * 322 // * @brief simplifyAST 323 // ** ------------------------------------------------------------------------------------------------------------- */ 324 DdNode * BDDMinimizationPass::characterizeTerminalBddTree(PabloAST * expr) { 325 409 410 if (terminals.empty()) { 411 break; 412 } 413 414 } 415 416 } 417 418 /** ------------------------------------------------------------------------------------------------------------- * 419 * @brief characterizeTerminal 420 ** ------------------------------------------------------------------------------------------------------------- */ 421 DdNode * BDDMinimizationPass::characterizeTerminal(PabloAST * expr) { 326 422 const auto f = mCharacterizationMap.find(expr); 327 if (f == mCharacterizationMap.end()) { 328 return nullptr; 329 } else if (f->second) { 423 if (f != mCharacterizationMap.end()) { 330 424 return f->second; 331 425 } 332 333 Statement * stmt = cast<Statement>(expr);334 426 std::array<DdNode *, 3> input; 335 336 for (unsigned i = 0; i != stmt->getNumOperands(); ++i) { 337 input[i] = characterizeTerminalBddTree(stmt->getOperand(i)); 338 } 339 427 for (unsigned i = 0; i != cast<Statement>(expr)->getNumOperands(); ++i) { 428 input[i] = characterizeTerminal(cast<Statement>(expr)->getOperand(i)); assert (input[i]); 429 } 340 430 DdNode * bdd = nullptr; 341 431 switch (expr->getClassTypeId()) { … … 349 439 bdd = Not(input[0]); 350 440 break; 351 case PabloAST::ClassTypeId::Sel:352 bdd = Ite(input[0], input[1], input[2]);353 break;441 // case PabloAST::ClassTypeId::Sel: 442 // bdd = Ite(input[0], input[1], input[2]); 443 // break; 354 444 default: 355 throw std::runtime_error("Unexpected operand given to BDDMinimizationPass::characterizeTerminalBddTree!");445 return nullptr; 356 446 } 357 447 Cudd_Ref(bdd); 448 mCharacterizationMap.insert(std::make_pair(expr, bdd)); 358 449 return bdd; 359 450 } … … 362 453 * @brief simplifyAST 363 454 ** ------------------------------------------------------------------------------------------------------------- */ 364 PabloAST * BDDMinimizationPass::simplifyAST(DdNode * const f, const std::vector<PabloAST *> & variables, PabloBuilder & builder) {455 PabloAST * BDDMinimizationPass::simplifyAST(DdNode * const f, PabloBuilder &block) { 365 456 assert (!noSatisfyingAssignment(f)); 366 457 DdNode * g = Cudd_FindEssential(mManager, f); 367 458 if (g && Cudd_SupportSize(mManager, g) > 0) { 368 459 if (g == f) { // every variable is essential 369 return makeCoverAST(f, variables, builder);460 return makeCoverAST(f, block); 370 461 } 371 462 Cudd_Ref(g); 372 PabloAST * c0 = makeCoverAST(g, variables, builder);463 PabloAST * c0 = makeCoverAST(g, block); 373 464 if (LLVM_UNLIKELY(c0 == nullptr)) { 374 465 Cudd_RecursiveDeref(mManager, g); … … 377 468 DdNode * h = Cudd_Cofactor(mManager, f, g); 378 469 Cudd_Ref(h); 379 PabloAST * c1 = simplifyAST(h, variables, builder);470 PabloAST * c1 = simplifyAST(h, block); 380 471 if (LLVM_UNLIKELY(c1 == nullptr)) { 381 472 Cudd_RecursiveDeref(mManager, g); … … 387 478 Cudd_RecursiveDeref(mManager, g); 388 479 Cudd_RecursiveDeref(mManager, h); 389 return b uilder.createAnd(c0, c1, "escf");480 return block.createAnd(c0, c1, "t"); 390 481 } 391 482 … … 417 508 Cudd_Ref(decomp[0]); 418 509 Cudd_Ref(decomp[1]); 419 PabloAST * d0 = simplifyAST(decomp[0], variables, builder);510 PabloAST * d0 = simplifyAST(decomp[0], block); 420 511 Cudd_RecursiveDeref(mManager, decomp[0]); 421 512 if (LLVM_UNLIKELY(d0 == nullptr)) { … … 424 515 } 425 516 426 PabloAST * d1 = simplifyAST(decomp[1], variables, builder);517 PabloAST * d1 = simplifyAST(decomp[1], block); 427 518 Cudd_RecursiveDeref(mManager, decomp[1]); 428 519 if (LLVM_UNLIKELY(d1 == nullptr)) { … … 432 523 433 524 if (disjuncts == 2) { 434 return b uilder.createOr(d0, d1, "disj");525 return block.createOr(d0, d1, "t"); 435 526 } else { 436 return b uilder.createAnd(d0, d1, "conj");437 } 438 } 439 return makeCoverAST(f, variables, builder);527 return block.createAnd(d0, d1, "t"); 528 } 529 } 530 return makeCoverAST(f, block); 440 531 } 441 532 … … 443 534 * @brief makeCoverAST 444 535 ** ------------------------------------------------------------------------------------------------------------- */ 445 PabloAST * BDDMinimizationPass::makeCoverAST(DdNode * const f, const std::vector<PabloAST *> & variables, PabloBuilder & builder) {536 PabloAST * BDDMinimizationPass::makeCoverAST(DdNode * const f, PabloBuilder & block) { 446 537 447 538 std::queue<PabloAST *> SQ; 448 const unsigned n = variables.size();449 circular_buffer<PabloAST *> CQ(n );450 circular_buffer<PabloAST *> DQ(n );451 452 assert (mManager->size == variables.size());539 const auto n = mVariables.size(); 540 circular_buffer<PabloAST *> CQ(n + 1); 541 circular_buffer<PabloAST *> DQ(n + 1); 542 543 assert (mManager->size == n); 453 544 454 545 int cube[n]; … … 497 588 assert (cube[i] >= 0 && cube[i] <= 2); 498 589 if (cube[i] == 0) { 499 assert (!DQ.full());500 DQ.push_back(variables[i]);590 DQ.push_back(mVariables[i]); 591 // CQ.push_back(block.createOnes()); 501 592 } else if (cube[i] == 1) { 502 assert (!CQ.full());503 CQ.push_back(variables[i]);593 CQ.push_back(mVariables[i]); 594 // DQ.push_back(block.createZeroes()); 504 595 } 505 596 } … … 513 604 PabloAST * v1 = DQ.front(); DQ.pop_front(); 514 605 PabloAST * v2 = DQ.front(); DQ.pop_front(); 515 DQ.push_back(b uilder.createOr(v1, v2));516 } 517 CQ.push_back(b uilder.createNot(DQ.front()));606 DQ.push_back(block.createOr(v1, v2)); 607 } 608 CQ.push_back(block.createNot(DQ.front())); 518 609 DQ.pop_front(); 519 610 } … … 523 614 PabloAST * v1 = CQ.front(); CQ.pop_front(); 524 615 PabloAST * v2 = CQ.front(); CQ.pop_front(); 525 CQ.push_back(b uilder.createAnd(v1, v2));616 CQ.push_back(block.createAnd(v1, v2)); 526 617 } 527 618 SQ.push(CQ.front()); CQ.pop_front(); … … 534 625 PabloAST * v1 = SQ.front(); SQ.pop(); 535 626 PabloAST * v2 = SQ.front(); SQ.pop(); 536 SQ.push(b uilder.createOr(v1, v2));627 SQ.push(block.createOr(v1, v2)); 537 628 } 538 629 return SQ.front(); -
icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_bddminimization.h
r4725 r4727 46 46 DdNode * eliminateLogicallyEquivalentStatements(const Statement * const stmt); 47 47 void simplifyAST(PabloFunction & function); 48 void simplifyAST(PabloBuilder & block, std::vector<Statement *> &terminals);49 DdNode * characterizeTerminalBddTree(PabloAST * expr);50 void simplifyAST(Statement *stmt, Statement * const value, PabloBuilder & builder);51 PabloAST * simplifyAST(DdNode * const f, const std::vector<PabloAST *> & variables, PabloBuilder & builder);52 PabloAST * makeCoverAST(DdNode * const f, const std::vector<PabloAST *> & variables, PabloBuilder & builder);48 void promoteSimpleInputDerivationsToAssigns(PabloFunction & function); 49 void simplifyAST(PabloBlock & block, Terminals && terminals); 50 DdNode * characterizeTerminal(PabloAST * expr); 51 PabloAST * simplifyAST(DdNode * const f, PabloBuilder &block); 52 PabloAST * makeCoverAST(DdNode * const f, PabloBuilder &block); 53 53 private: 54 54 DdNode * Zero() const;
Note: See TracChangeset
for help on using the changeset viewer.