Changeset 4727


Ignore:
Timestamp:
Aug 16, 2015, 4:23:57 PM (4 years ago)
Author:
nmedfort
Message:

More minimization work.

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  
    10021002            assert (i == n);
    10031003
    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 
    10161004            PabloBlock * const block = input[0]->getParent();
    10171005            block->setInsertPoint(block->back());
    … …  
    10861074        }       
    10871075    }
    1088 }
    1089 
    1090 /** ------------------------------------------------------------------------------------------------------------- *
    1091  * @brief isSimplifiable
    1092  ** ------------------------------------------------------------------------------------------------------------- */
    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 simplifyAST
    1107  ** ------------------------------------------------------------------------------------------------------------- */
    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 visiting
    1111     // and determine which of those will be terminals in the BDD
    1112     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 possible
    1187         // that one takes an input derived from the initial set whose output is used as part of
    1188         // 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 depends
    1209                          // 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 depends
    1247 //                         // 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 BDD
    1271         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 BDD
    1280                 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 BDD
    1295 //                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 simplifyAST
    1433  ** ------------------------------------------------------------------------------------------------------------- */
    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 visiting
    1437 //    // and determine which of those will be terminals in the BDD
    1438 //    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 BDD
    1569 //        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 BDD
    1578 //                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 simplifyAST
    1688  ** ------------------------------------------------------------------------------------------------------------- */
    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 essential
    1694             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 makeCoverAST
    1769  ** ------------------------------------------------------------------------------------------------------------- */
    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();
    18641076}
    18651077
    … …  
    19191131}
    19201132
    1921 /** ------------------------------------------------------------------------------------------------------------- *
    1922  * @brief reassociation
    1923  *
    1924  ** ------------------------------------------------------------------------------------------------------------- */
    1925 inline void AutoMultiplexing::reassociate(PabloBlock & entry) const {
    1926 
    1927 }
    1928 
    19291133} // end of namespace pablo
    19301134

  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.hpp

    r4725 r4727  
    5050    void applySubsetConstraints();
    5151    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);
    5552    void topologicalSort(PabloBlock & entry) const;
    56     void reassociate(PabloBlock & entry) const;
    5753    inline AutoMultiplexing()
    5854    : mVariables(0)

  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_bddminimization.cpp

    r4725 r4727  
    1212#include <pablo/optimizers/pablo_simplifier.hpp>
    1313#include <boost/container/flat_set.hpp>
     14#include <boost/container/flat_map.hpp>
     15#include <boost/graph/adjacency_list.hpp>
    1416
    1517using namespace llvm;
    … …  
    2123bool BDDMinimizationPass::optimize(PabloFunction & function, const bool full) {
    2224    BDDMinimizationPass am;
    23     am.eliminateLogicallyEquivalentStatements(function);
    2425    if (full) {
    2526        am.simplifyAST(function);
    2627    }
     28    am.eliminateLogicallyEquivalentStatements(function);
    2729    return Simplifier::optimize(function);
    2830}
    … …  
    196198 ** ------------------------------------------------------------------------------------------------------------- */
    197199inline void BDDMinimizationPass::simplifyAST(PabloFunction & function) {
    198     PabloBuilder builder(function.getEntryBlock());
    199     std::vector<Statement *> terminals;
     200    Terminals terminals;
    200201    for (unsigned i = 0; i != function.getNumOfResults(); ++i) {
    201202        terminals.push_back(function.getResult(i));
    202203    }
    203     simplifyAST(builder, terminals);
    204 }
     204    simplifyAST(function.getEntryBlock(), std::move(terminals));
     205}
     206
     207/** ------------------------------------------------------------------------------------------------------------- *
     208 * @brief promoteSimpleInputDerivationsToAssigns
     209 ** ------------------------------------------------------------------------------------------------------------- */
     210inline 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
    205282
    206283/** ------------------------------------------------------------------------------------------------------------- *
    … …  
    212289        case PabloAST::ClassTypeId::Or:
    213290        case PabloAST::ClassTypeId::Not:
    214         case PabloAST::ClassTypeId::Sel:
     291//        case PabloAST::ClassTypeId::Sel:
    215292            return cast<Statement>(expr)->getParent() == pb;
    216293        default:
    … …  
    222299 * @brief simplifyAST
    223300 ** ------------------------------------------------------------------------------------------------------------- */
    224 void BDDMinimizationPass::simplifyAST(PabloBuilder & block, std::vector<Statement *> & terminals) {
     301void BDDMinimizationPass::simplifyAST(PabloBlock & block, Terminals && terminals) {
    225302
    226303    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;
    230306            for (Assign * var : cast<const If>(stmt)->getDefined()) {
    231307                terminals.push_back(var);
    232308            }
    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;
    238314        } else if (isa<While>(stmt)) {
    239             PabloBuilder builder(cast<While>(stmt)->getBody(), block);
    240             std::vector<Statement *> terminals;
     315            Terminals terminals;
    241316            for (Next * var : cast<const While>(stmt)->getVariants()) {
    242317                terminals.push_back(var);
    243318            }
    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;
    258331        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) {
    259345            Q.push(term);
    260346        }
    261347
     348        flat_set<PabloAST *> visited;
     349        flat_set<PabloAST *> variables;
    262350        // find the variables for this set of terminals
    263351        for (;;) {
    264352            Statement * stmt = Q.front();
    265353            Q.pop();
    266             mCharacterizationMap[stmt] = nullptr;
    267354            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));
    272362                }
    273363            }
    … …  
    277367        }
    278368
    279         std::sort(variables.begin(), variables.end());
    280         std::unique(variables.begin(), variables.end());
    281 
    282 
     369        mVariables.clear();
    283370        mManager = Cudd_Init(variables.size(), 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0);
    284371        Cudd_AutodynEnable(mManager, CUDD_REORDER_LAZY_SIFT);
    285 
    286         unsigned i = 0;
    287372        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);
    294383        Cudd_ReduceHeap(mManager, CUDD_REORDER_SIFT, 0);
    295384
    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);
    298388            Cudd_Ref(f);
    299             PabloAST * replacement = simplifyAST(f, variables, block);
     389            block.setInsertPoint(input);
     390            PabloBuilder builder(block);
     391            PabloAST * replacement = simplifyAST(f, builder);
    300392            if (replacement) {
    301                 term->replaceWith(replacement, false, true);
     393                input->replaceWith(replacement, false, true);
    302394            }
    303395            Cudd_RecursiveDeref(mManager, f);
    … …  
    311403        terminals.clear();
    312404        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)) {
    314406                terminals.push_back(cast<Statement>(var));
    315407            }
    316408        }
    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 ** ------------------------------------------------------------------------------------------------------------- */
     421DdNode * BDDMinimizationPass::characterizeTerminal(PabloAST * expr) {
    326422    const auto f = mCharacterizationMap.find(expr);
    327     if (f == mCharacterizationMap.end()) {
    328         return nullptr;
    329     } else if (f->second) {
     423    if (f != mCharacterizationMap.end()) {
    330424        return f->second;
    331425    }
    332 
    333     Statement * stmt = cast<Statement>(expr);
    334426    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    }
    340430    DdNode * bdd = nullptr;
    341431    switch (expr->getClassTypeId()) {
    … …  
    349439            bdd = Not(input[0]);
    350440            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;
    354444        default:
    355             throw std::runtime_error("Unexpected operand given to BDDMinimizationPass::characterizeTerminalBddTree!");
     445            return nullptr;
    356446    }
    357447    Cudd_Ref(bdd);
     448    mCharacterizationMap.insert(std::make_pair(expr, bdd));
    358449    return bdd;
    359450}
    … …  
    362453 * @brief simplifyAST
    363454 ** ------------------------------------------------------------------------------------------------------------- */
    364 PabloAST * BDDMinimizationPass::simplifyAST(DdNode * const f, const std::vector<PabloAST *> & variables, PabloBuilder & builder) {
     455PabloAST * BDDMinimizationPass::simplifyAST(DdNode * const f, PabloBuilder &block) {
    365456    assert (!noSatisfyingAssignment(f));
    366457    DdNode * g = Cudd_FindEssential(mManager, f);
    367458    if (g && Cudd_SupportSize(mManager, g) > 0) {
    368459        if (g == f) { // every variable is essential
    369             return makeCoverAST(f, variables, builder);
     460            return makeCoverAST(f, block);
    370461        }
    371462        Cudd_Ref(g);
    372         PabloAST * c0 = makeCoverAST(g, variables, builder);
     463        PabloAST * c0 = makeCoverAST(g, block);
    373464        if (LLVM_UNLIKELY(c0 == nullptr)) {
    374465            Cudd_RecursiveDeref(mManager, g);
    … …  
    377468        DdNode * h = Cudd_Cofactor(mManager, f, g);
    378469        Cudd_Ref(h);
    379         PabloAST * c1 = simplifyAST(h, variables, builder);
     470        PabloAST * c1 = simplifyAST(h, block);
    380471        if (LLVM_UNLIKELY(c1 == nullptr)) {
    381472            Cudd_RecursiveDeref(mManager, g);
    … …  
    387478        Cudd_RecursiveDeref(mManager, g);
    388479        Cudd_RecursiveDeref(mManager, h);
    389         return builder.createAnd(c0, c1, "escf");
     480        return block.createAnd(c0, c1, "t");
    390481    }
    391482
    … …  
    417508        Cudd_Ref(decomp[0]);
    418509        Cudd_Ref(decomp[1]);
    419         PabloAST * d0 = simplifyAST(decomp[0], variables, builder);
     510        PabloAST * d0 = simplifyAST(decomp[0], block);
    420511        Cudd_RecursiveDeref(mManager, decomp[0]);
    421512        if (LLVM_UNLIKELY(d0 == nullptr)) {
    … …  
    424515        }
    425516
    426         PabloAST * d1 = simplifyAST(decomp[1], variables, builder);
     517        PabloAST * d1 = simplifyAST(decomp[1], block);
    427518        Cudd_RecursiveDeref(mManager, decomp[1]);
    428519        if (LLVM_UNLIKELY(d1 == nullptr)) {
    … …  
    432523
    433524        if (disjuncts == 2) {
    434             return builder.createOr(d0, d1, "disj");
     525            return block.createOr(d0, d1, "t");
    435526        } else {
    436             return builder.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);
    440531}
    441532
    … …  
    443534 * @brief makeCoverAST
    444535 ** ------------------------------------------------------------------------------------------------------------- */
    445 PabloAST * BDDMinimizationPass::makeCoverAST(DdNode * const f, const std::vector<PabloAST *> & variables, PabloBuilder & builder) {
     536PabloAST * BDDMinimizationPass::makeCoverAST(DdNode * const f, PabloBuilder & block) {
    446537
    447538    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);
    453544
    454545    int cube[n];
    … …  
    497588            assert (cube[i] >= 0 && cube[i] <= 2);
    498589            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());
    501592            } 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());
    504595            }
    505596        }
    … …  
    513604                PabloAST * v1 = DQ.front(); DQ.pop_front();
    514605                PabloAST * v2 = DQ.front(); DQ.pop_front();
    515                 DQ.push_back(builder.createOr(v1, v2));
    516             }
    517             CQ.push_back(builder.createNot(DQ.front()));
     606                DQ.push_back(block.createOr(v1, v2));
     607            }
     608            CQ.push_back(block.createNot(DQ.front()));
    518609            DQ.pop_front();
    519610        }
    … …  
    523614            PabloAST * v1 = CQ.front(); CQ.pop_front();
    524615            PabloAST * v2 = CQ.front(); CQ.pop_front();
    525             CQ.push_back(builder.createAnd(v1, v2));
     616            CQ.push_back(block.createAnd(v1, v2));
    526617        }
    527618        SQ.push(CQ.front()); CQ.pop_front();
    … …  
    534625        PabloAST * v1 = SQ.front(); SQ.pop();
    535626        PabloAST * v2 = SQ.front(); SQ.pop();
    536         SQ.push(builder.createOr(v1, v2));
     627        SQ.push(block.createOr(v1, v2));
    537628    }
    538629    return SQ.front();

  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_bddminimization.h

    r4725 r4727  
    4646    DdNode * eliminateLogicallyEquivalentStatements(const Statement * const stmt);
    4747    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);
    5353private:
    5454    DdNode * Zero() const;
Note: See TracChangeset for help on using the changeset viewer.