Ignore:
Timestamp:
Aug 15, 2015, 7:30:14 PM (4 years ago)
Author:
nmedfort
Message:

Temporary check-in.

Location:
icGREP/icgrep-devel/icgrep
Files:
5 edited

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/CMakeLists.txt

    r4699 r4725  
    6464SET(PABLO_SRC ${PABLO_SRC} pablo/pablo_compiler.cpp pablo/optimizers/pablo_simplifier.cpp pablo/optimizers/pablo_codesinking.cpp pablo/carry_manager.cpp IDISA/idisa_builder.cpp)
    6565IF (ENABLE_MULTIPLEXING)
    66 SET(PABLO_SRC ${PABLO_SRC} pablo/optimizers/pablo_automultiplexing.cpp pablo/optimizers/pablo_bddminimization.cpp)
     66SET(PABLO_SRC ${PABLO_SRC} pablo/optimizers/pablo_automultiplexing.cpp pablo/optimizers/pablo_bddminimization.cpp pablo/optimizers/booleanreassociationpass.cpp)
    6767ENDIF()
    6868
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.cpp

    r4724 r4725  
    1717#include <unordered_set>
    1818#include <pablo/optimizers/pablo_simplifier.hpp>
     19#include <pablo/optimizers/booleanreassociationpass.h>
     20#include <pablo/optimizers/pablo_bddminimization.h>
    1921
    2022using namespace llvm;
     
    104106bool AutoMultiplexing::optimize(PabloFunction & function) {
    105107
     108    BDDMinimizationPass::optimize(function);
     109
    106110    // std::random_device rd;
    107111    const auto seed = 83234827342;
     
    160164        RECORD_TIMESTAMP(end_topological_sort);
    161165        LOG("TopologicalSort (1):     " << (end_topological_sort - start_topological_sort));
     166
     167        BDDMinimizationPass::optimize(function, true);
     168
     169//        LOG_NUMBER_OF_ADVANCES(function.getEntryBlock());
    162170
    163171//        RECORD_TIMESTAMP(start_simplify_ast);
     
    772780        }
    773781
    774         OutEdgeIterator ei, ei_end;
    775         for (std::tie(ei, ei_end) = out_edges(k + m, mMultiplexSetGraph); ei != ei_end; ++ei) {
    776             const vertex_t j = target(*ei, mMultiplexSetGraph);
     782        for (const auto ei : make_iterator_range(out_edges(k + m, mMultiplexSetGraph))) {
     783            const vertex_t j = target(ei, mMultiplexSetGraph);
    777784            if (chosen_set[j] == 0) {
    778785                chosen_set[j] = (k + m);
    779                 InEdgeIterator ej, ej_end;
    780                 for (std::tie(ej, ej_end) = in_edges(j, mMultiplexSetGraph); ej != ej_end; ++ej) {
    781                     remaining[source(*ej, mMultiplexSetGraph) - m]--;
     786                for (const auto ej : make_iterator_range(in_edges(j, mMultiplexSetGraph))) {
     787                    remaining[source(ej, mMultiplexSetGraph) - m]--;
    782788                }
    783789            }
     
    793799            for (vertex_t i = 0; i != m; ++i) {
    794800                if (chosen_set[i] == (k + m)) {
    795                     InEdgeIterator ej, ej_end;
    796801                    degree_t r = 1;
    797                     for (std::tie(ej, ej_end) = in_edges(i, mMultiplexSetGraph); ej != ej_end; ++ej) {
     802                    for (const auto ej : make_iterator_range(in_edges(i, mMultiplexSetGraph))) {
    798803                        // strongly prefer adding weight to unvisited sets that have more remaining vertices
    799                         r += std::pow(remaining[source(*ej, mMultiplexSetGraph) - m], 2);
     804                        r += std::pow(remaining[source(ej, mMultiplexSetGraph) - m], 2);
    800805                    }
    801806                    if (w < r) {
     
    807812            assert (w > 0);
    808813            chosen_set[j] = 0;
    809             InEdgeIterator ej, ej_end;
    810             for (std::tie(ej, ej_end) = in_edges(j, mMultiplexSetGraph); ej != ej_end; ++ej) {
    811                 remaining[source(*ej, mMultiplexSetGraph) - m]++;
     814            for (const auto ej : make_iterator_range(in_edges(j, mMultiplexSetGraph))) {
     815                remaining[source(ej, mMultiplexSetGraph) - m]++;
    812816            }
    813817        }
     
    978982    }
    979983
    980     std::vector<MultiplexSetGraph::vertex_descriptor> I(max_n);
    981984    circular_buffer<PabloAST *> Q(max_n);
    982985
     
    988991        if (n) {
    989992            const size_t m = log2_plus_one(n);
     993            std::vector<Statement *> muxed(m);
    990994            Advance * input[n];
    991             std::vector<Advance *> muxed(m);
    992 
    993             graph_traits<MultiplexSetGraph>::out_edge_iterator ei, ei_end;
    994             std::tie(ei, ei_end) = out_edges(s, mMultiplexSetGraph);
    995             for (unsigned i = 0; i != n; ++ei, ++i) {
    996                 I[i] = target(*ei, mMultiplexSetGraph);
    997             }
    998             std::sort(I.begin(), I.begin() + n);
    999 
    1000             for (unsigned i = 0; i != n; ++i) {
    1001                 input[i] = std::get<0>(mAdvance[I[i]]);
    1002             }
     995
     996            unsigned i = 0;
     997            for (const auto e : make_iterator_range(out_edges(s, mMultiplexSetGraph))) {
     998                input[i] = std::get<0>(mAdvance[target(e, mMultiplexSetGraph)]);
     999                assert (input[i]);
     1000                ++i;
     1001            }
     1002            assert (i == n);
     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//            }
    10031015
    10041016            PabloBlock * const block = input[0]->getParent();
     
    10281040                // The only way this did not return an Advance statement would be if either the mux or shift amount
    10291041                // is zero. Since these cases would have been eliminated earlier, we are safe to cast here.               
    1030                 muxed[j] = cast<Advance>(builder.createAdvance(mux, adv->getOperand(1), prefix.str()));
     1042                muxed[j] = cast<Statement>(builder.createAdvance(mux, adv->getOperand(1), prefix.str()));
    10311043            }
    10321044
     
    10711083            }
    10721084
    1073             mMuxedVariables.push_back(std::move(muxed));
     1085            mSimplificationQueue.push(std::move(muxed));
    10741086        }       
     1087    }
     1088}
     1089
     1090/** ------------------------------------------------------------------------------------------------------------- *
     1091 * @brief isSimplifiable
     1092 ** ------------------------------------------------------------------------------------------------------------- */
     1093inline 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;
    10751102    }
    10761103}
     
    10881115    raw_os_ostream out(std::cerr);
    10891116
     1117    unsigned index = 0;
     1118
    10901119    // TODO: this should build a single graph and iterate by connected component instead.
    1091     for (const auto & muxed : mMuxedVariables) {
     1120    while (!mSimplificationQueue.empty()) {
    10921121
    10931122        Graph G;
    1094         std::unordered_map<PabloAST *, unsigned> M;
     1123        std::unordered_map<PabloAST *, unsigned> M;       
    10951124        std::queue<Statement *> Q;
    1096 
    1097         out << "-----------------------------------------------------------------------------------\n";
    1098         PabloPrinter::print(function.getEntryBlock().statements(), out);
    1099         out << "-----------------------------------------------------------------------------------\n"; out.flush();
    1100 
    1101 
    1102         for (unsigned i = 0; i != muxed.size(); ++i) {
    1103 
    1104             const auto u = add_vertex(muxed[i], G);
    1105             M.insert(std::make_pair(muxed[i], u));
    1106             for (PabloAST * user : muxed[i]->users()) {
     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()) {
    11071136                auto f = M.find(user);
    11081137                Vertex v = 0;
     
    11101139                    v = add_vertex(user, G);
    11111140                    M.insert(std::make_pair(user, v));
    1112                     switch (user->getClassTypeId()) {
    1113                         case PabloAST::ClassTypeId::And:
    1114                         case PabloAST::ClassTypeId::Or:
    1115                         case PabloAST::ClassTypeId::Not:
    1116                         case PabloAST::ClassTypeId::Sel:
    1117                             Q.push(cast<Statement>(user));
    1118                         default: break;
     1141                    if (isSimplifiable(user, set[i]->getParent())) {
     1142                        Q.push(cast<Statement>(user));
    11191143                    }
    11201144                } else { // if (f != M.end()) {
     
    11261150
    11271151        while (!Q.empty()) {
     1152
    11281153            Statement * const var = Q.front(); Q.pop();
    11291154
    1130 
    11311155            const Vertex u = M[var];
     1156
    11321157            for (unsigned i = 0; i != var->getNumOperands(); ++i) {
    11331158                PabloAST * operand = var->getOperand(i);
     
    11491174                    v = add_vertex(user, G);
    11501175                    M.insert(std::make_pair(user, v));
    1151                     switch (user->getClassTypeId()) {
    1152                         case PabloAST::ClassTypeId::And:
    1153                         case PabloAST::ClassTypeId::Or:
    1154                         case PabloAST::ClassTypeId::Not:
    1155                         case PabloAST::ClassTypeId::Sel:
    1156                             Q.push(cast<Statement>(user));
    1157                         default: break;
     1176                    if (isSimplifiable(user, var->getParent())) {
     1177                        Q.push(cast<Statement>(user));
    11581178                    }
    11591179                } else { // if (f != M.end()) {
     
    11641184        }
    11651185
    1166         for (auto u : make_iterator_range(vertices(G))) {
     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;
    11671199            PabloAST * expr = G[u];
    11681200            switch (expr->getClassTypeId()) {
     
    11711203                case PabloAST::ClassTypeId::Not:
    11721204                case PabloAST::ClassTypeId::Sel:
     1205
     1206
    11731207                    break;
    1174                 default: // this vertex corresponds to a non-Boolean function. It needs to be split.
     1208                default: // this vertex corresponds to a non-Boolean function. Everything that depends
     1209                         // on it must be removed from the current graph.
    11751210                    if (in_degree(u, G) > 0 && out_degree(u, G) > 0) {
    1176                         Vertex v = add_vertex(expr, G);
    1177                         for (auto e : make_iterator_range(out_edges(u, G))) {
    1178                             add_edge(v, target(e, G), G);
    1179                         }
    1180                         clear_out_edges(u, G);
    1181                     }
    1182             }
    1183         }
    1184 
    1185         out << "\ndigraph x {\n";
    1186         for (auto u : make_iterator_range(vertices(G))) {
     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) {
    11871304            std::string tmp;
    11881305            raw_string_ostream name(tmp);
    1189             PabloPrinter::print(G[u], name);
    1190             out << "v" << u << " [label=\"" << name.str() << "\"];\n";
     1306            PabloPrinter::print(G[*ui], name);
     1307            out << "v" << *ui << " [label=\"" << name.str() << "\"];\n";
    11911308        }
    11921309        for (auto e : make_iterator_range(edges(G))) {
     
    11941311        }
    11951312
    1196         out << " { rank=same;";
     1313        out << "{ rank=same;";
    11971314        for (auto u : make_iterator_range(vertices(G))) {
    11981315            if (in_degree(u, G) == 0) {
     
    12021319        out << "}\n";
    12031320
    1204         out << " { rank=same;";
     1321        out << "{ rank=same;";
    12051322        for (auto u : make_iterator_range(vertices(G))) {
    12061323            if (out_degree(u, G) == 0) {
     
    12131330        out.flush();
    12141331
    1215         // count the number of sources (sinks) so we know how many variables (terminals) will exist in the BDD
    1216         std::vector<Vertex> inputs;
    1217         flat_set<Vertex> terminals;
    1218 
    1219         for (auto u : make_iterator_range(vertices(G))) {
    1220             if (in_degree(u, G) == 0) {
    1221                 inputs.push_back(u);
    1222             }
    1223             if (out_degree(u, G) == 0) {
    1224                 // the inputs to the sinks become the terminals in the BDD
    1225                 for (auto e : make_iterator_range(in_edges(u, G))) {
    1226                     terminals.insert(source(e, G));
    1227                 }
    1228             }
    1229         }
    1230 
    1231 
    1232 
    1233 
    1234         const auto n = inputs.size();
     1332        if (index == 9) {
     1333            continue;
     1334        }
     1335        n = inputs.size();
    12351336
    12361337        mManager = Cudd_Init(n, 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0);
     
    12451346        }
    12461347
    1247         std::vector<Vertex> ordering;
    1248         ordering.reserve(num_vertices(G));
    1249         topological_sort(G, std::back_inserter(ordering));
    1250 
    12511348        for (auto ui = ordering.rbegin(); ui != ordering.rend(); ++ui) {
    12521349
     
    12601357
    12611358            unsigned i = 0;
    1262             for (const auto e : make_iterator_range(in_edges(u, G))) {               
     1359            for (const auto e : make_iterator_range(in_edges(u, G))) {
    12631360                input[i] = characterization[source(e, G)];
    12641361                if (input[i] == nullptr) {
     
    13121409
    13131410            DdNode * const f = characterization[t];
     1411            assert (f);
    13141412            Cudd_Ref(f);
    13151413
     
    13301428    }
    13311429}
     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//}
    13321685
    13331686/** ------------------------------------------------------------------------------------------------------------- *
     
    15661919}
    15671920
     1921/** ------------------------------------------------------------------------------------------------------------- *
     1922 * @brief reassociation
     1923 *
     1924 ** ------------------------------------------------------------------------------------------------------------- */
     1925inline void AutoMultiplexing::reassociate(PabloBlock & entry) const {
     1926
     1927}
     1928
    15681929} // end of namespace pablo
    15691930
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.hpp

    r4724 r4725  
    3636    using VertexVector = std::vector<ConstraintVertex>;
    3737    using RecentCharacterizations = std::vector<std::pair<const PabloAST *, DdNode *>>;
    38     using MuxedVariables = std::vector<std::vector<Advance *>>;
     38    using SimplificationQueue = std::queue<std::vector<Statement *>>;
    3939public:
    4040    static bool optimize(PabloFunction & function);
     
    5454    PabloAST * makeCoverAST(DdNode * const f, const std::vector<PabloAST *> & variables, PabloBuilder & builder);
    5555    void topologicalSort(PabloBlock & entry) const;
     56    void reassociate(PabloBlock & entry) const;
    5657    inline AutoMultiplexing()
    5758    : mVariables(0)
     
    8586    MultiplexSetGraph           mMultiplexSetGraph;
    8687    RecentCharacterizations     mRecentCharacterizations;
    87     MuxedVariables              mMuxedVariables;
     88    SimplificationQueue         mSimplificationQueue;
    8889};
    8990
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_bddminimization.cpp

    r4711 r4725  
    1111#include <boost/circular_buffer.hpp>
    1212#include <pablo/optimizers/pablo_simplifier.hpp>
     13#include <boost/container/flat_set.hpp>
    1314
    1415using namespace llvm;
    1516using namespace boost;
     17using namespace boost::container;
    1618
    1719namespace pablo {
    1820
    19 bool BDDMinimizationPass::optimize(PabloFunction & function) {
    20     raw_os_ostream out(std::cerr);
    21     PabloPrinter::print(function.getEntryBlock(), "", out);
    22     out << "\n****************************************************************\n\n";
    23     out.flush();
    24 
    25     promoteCrossBlockReachingDefs(function);
    26 
     21bool BDDMinimizationPass::optimize(PabloFunction & function, const bool full) {
    2722    BDDMinimizationPass am;
    28     am.initialize(function);
    29     am.characterizeAndEliminateLogicallyEquivalentStatements(function);
    30     am.simplifyAST(function);
    31     am.shutdown();
    32 
     23    am.eliminateLogicallyEquivalentStatements(function);
     24    if (full) {
     25        am.simplifyAST(function);
     26    }
    3327    return Simplifier::optimize(function);
    34 }
    35 
    36 /** ------------------------------------------------------------------------------------------------------------- *
    37  * @brief promoteCrossBlockReachingDefs
    38  * @param function
    39   *
    40  * Scan through the function and promote any cross-block statements into Assign nodes to simplify the BDD node
    41  * generation.
    42  ** ------------------------------------------------------------------------------------------------------------- */
    43 void BDDMinimizationPass::promoteCrossBlockReachingDefs(const PabloFunction & function) {
    44 
    45     std::unordered_map<const PabloAST *, unsigned> block;
    46     std::stack<Statement *> scope;
    47 
    48     unsigned blockIndex = 0;
    49 
    50     for (const Statement * stmt = function.getEntryBlock().front(); ; ) {
    51         while ( stmt ) {
    52 
    53             if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
    54                 // Set the next statement to be the first statement of the inner scope and push the
    55                 // next statement of the current statement into the scope stack.
    56                 const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
    57                 scope.push(stmt->getNextNode());
    58                 stmt = nested.front();
    59                 assert (stmt);
    60                 ++blockIndex;
    61                 continue;
    62             }
    63 
    64             for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
    65                 Statement * const op = dyn_cast<Statement>(stmt->getOperand(i));
    66                 if (op == nullptr || isa<Assign>(op) || isa<Next>(op) || block[op] == blockIndex) {
    67                     continue;
    68                 }
    69                 PabloBlock * const block = op->getParent();
    70                 block->setInsertPoint(op);
    71 
    72                 op->replaceAllUsesWith(block->createAssign("t", op));
    73             }
    74 
    75             block[stmt] = blockIndex;
    76 
    77             stmt = stmt->getNextNode();
    78         }
    79         if (scope.empty()) {
    80             break;
    81         }
    82         stmt = scope.top();
    83         scope.pop();
    84         ++blockIndex;
    85     }
    8628}
    8729
     
    9436 * the proper variable ordering.
    9537 ** ------------------------------------------------------------------------------------------------------------- */
    96 void BDDMinimizationPass::initialize(const PabloFunction & function) {
     38void BDDMinimizationPass::eliminateLogicallyEquivalentStatements(PabloFunction & function) {
    9739
    9840    std::stack<Statement *> scope;
     
    14284        mCharacterizationMap[function.getParameter(i)] = NewVar(function.getParameter(i));
    14385    }
     86
     87    SubsitutionMap baseMap;
     88    baseMap.insert(Zero(), function.getEntryBlock().createZeroes());
     89    baseMap.insert(One(), function.getEntryBlock().createOnes());
     90
     91    Cudd_AutodynEnable(mManager, CUDD_REORDER_LAZY_SIFT);
     92
     93    eliminateLogicallyEquivalentStatements(function.getEntryBlock(), baseMap);
     94
     95    Cudd_Quit(mManager);
     96    mCharacterizationMap.clear();
    14497}
    14598
     
    150103 * Scan through the program and iteratively compute the BDDs for each statement.
    151104 ** ------------------------------------------------------------------------------------------------------------- */
    152 void BDDMinimizationPass::characterizeAndEliminateLogicallyEquivalentStatements(PabloFunction & function) {
    153     SubsitutionMap baseMap;
    154     baseMap.insert(Zero(), function.getEntryBlock().createZeroes());
    155     baseMap.insert(One(), function.getEntryBlock().createOnes());
    156     Cudd_AutodynEnable(mManager, CUDD_REORDER_LAZY_SIFT);
    157     characterizeAndEliminateLogicallyEquivalentStatements(function.getEntryBlock(), baseMap);
    158     Cudd_AutodynDisable(mManager);
    159     Cudd_ReduceHeap(mManager, CUDD_REORDER_EXACT, 0);
    160 }
    161 
    162 /** ------------------------------------------------------------------------------------------------------------- *
    163  * @brief characterize
    164  * @param vars the input vars for this program
    165  *
    166  * Scan through the program and iteratively compute the BDDs for each statement.
    167  ** ------------------------------------------------------------------------------------------------------------- */
    168 void BDDMinimizationPass::characterizeAndEliminateLogicallyEquivalentStatements(PabloBlock & block, SubsitutionMap & parent) {
     105void BDDMinimizationPass::eliminateLogicallyEquivalentStatements(PabloBlock & block, SubsitutionMap & parent) {
    169106    SubsitutionMap subsitutionMap(&parent);
    170107    Statement * stmt = block.front();
     108
    171109    while (stmt) {
    172         if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
    173 
    174             for (auto promotion : mPromotions) {
    175                 mCharacterizationMap[promotion] = NewVar(promotion);
    176             }
    177             mPromotions.clear();
    178 
    179             characterizeAndEliminateLogicallyEquivalentStatements(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(), subsitutionMap);
    180 
    181             for (auto promotion : mPromotions) {
    182                 mCharacterizationMap[promotion] = NewVar(promotion);
    183             }
    184             mPromotions.clear();
    185 
     110        if (LLVM_UNLIKELY(isa<If>(stmt))) {
     111            eliminateLogicallyEquivalentStatements(cast<If>(stmt)->getBody(), subsitutionMap);
     112        } else if (LLVM_UNLIKELY(isa<While>(stmt))) {
     113            eliminateLogicallyEquivalentStatements(cast<While>(stmt)->getBody(), subsitutionMap);
    186114        } else { // attempt to characterize this statement and replace it if
    187             DdNode * bdd = characterizeAndEliminateLogicallyEquivalentStatements(stmt);
     115            DdNode * bdd = eliminateLogicallyEquivalentStatements(stmt);
    188116            if (LLVM_LIKELY(!isa<Assign>(stmt) && !isa<Next>(stmt))) {
    189117                PabloAST * replacement = subsitutionMap[bdd];
     
    205133 * @brief characterize
    206134 ** ------------------------------------------------------------------------------------------------------------- */
    207 inline DdNode * BDDMinimizationPass::characterizeAndEliminateLogicallyEquivalentStatements(const Statement * const stmt) {
     135inline DdNode * BDDMinimizationPass::eliminateLogicallyEquivalentStatements(const Statement * const stmt) {
    208136
    209137    DdNode * bdd = nullptr;
     
    228156        case PabloAST::ClassTypeId::Assign:
    229157        case PabloAST::ClassTypeId::Next:
    230             mPromotions.push_back(stmt);
    231158            return input[0];
    232159        case PabloAST::ClassTypeId::And:
     
    270197inline void BDDMinimizationPass::simplifyAST(PabloFunction & function) {
    271198    PabloBuilder builder(function.getEntryBlock());
    272     simplifyAST(builder);
     199    std::vector<Statement *> terminals;
     200    for (unsigned i = 0; i != function.getNumOfResults(); ++i) {
     201        terminals.push_back(function.getResult(i));
     202    }
     203    simplifyAST(builder, terminals);
     204}
     205
     206/** ------------------------------------------------------------------------------------------------------------- *
     207 * @brief isSimplifiable
     208 ** ------------------------------------------------------------------------------------------------------------- */
     209inline bool isSimplifiable(const PabloAST * const expr, const PabloBlock * const pb) {
     210    switch (expr->getClassTypeId()) {
     211        case PabloAST::ClassTypeId::And:
     212        case PabloAST::ClassTypeId::Or:
     213        case PabloAST::ClassTypeId::Not:
     214        case PabloAST::ClassTypeId::Sel:
     215            return cast<Statement>(expr)->getParent() == pb;
     216        default:
     217            return false;
     218    }
    273219}
    274220
     
    276222 * @brief simplifyAST
    277223 ** ------------------------------------------------------------------------------------------------------------- */
    278 void BDDMinimizationPass::simplifyAST(PabloBuilder & block) {
     224void BDDMinimizationPass::simplifyAST(PabloBuilder & block, std::vector<Statement *> & terminals) {
     225
    279226    for (Statement * stmt : block) {
    280         switch (stmt->getClassTypeId()) {
    281             case PabloAST::ClassTypeId::If:
    282             case PabloAST::ClassTypeId::While: {
    283                     PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
    284                     PabloBuilder builder(nested, block);
    285                     simplifyAST(builder);
    286                     if (isa<If>(stmt)) {
    287                         for (Assign * var : cast<const If>(stmt)->getDefined()) {
    288                             block.record(var);
    289                         }
    290                     } else {
    291                         for (Next * var : cast<const While>(stmt)->getVariants()) {
    292                             block.record(var);
    293                         }
    294                     }
     227        if (isa<While>(stmt)) {
     228            PabloBuilder builder(cast<If>(stmt)->getBody(), block);
     229            std::vector<Statement *> terminals;
     230            for (Assign * var : cast<const If>(stmt)->getDefined()) {
     231                terminals.push_back(var);
     232            }
     233            simplifyAST(builder, terminals);
     234            for (Assign * var : cast<const If>(stmt)->getDefined()) {
     235                block.record(var);
     236            }
     237            continue;
     238        } else if (isa<While>(stmt)) {
     239            PabloBuilder builder(cast<While>(stmt)->getBody(), block);
     240            std::vector<Statement *> terminals;
     241            for (Next * var : cast<const While>(stmt)->getVariants()) {
     242                terminals.push_back(var);
     243            }
     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
     258        for (Statement * term : terminals) {
     259            Q.push(term);
     260        }
     261
     262        // find the variables for this set of terminals
     263        for (;;) {
     264            Statement * stmt = Q.front();
     265            Q.pop();
     266            mCharacterizationMap[stmt] = nullptr;
     267            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));
    295272                }
     273            }
     274            if (Q.empty()) {
    296275                break;
    297             case PabloAST::ClassTypeId::ScanThru:
    298             case PabloAST::ClassTypeId::MatchStar:
    299                 simplifyAST(stmt, dyn_cast<Statement>(stmt->getOperand(1)), block);
    300             case PabloAST::ClassTypeId::Advance:
    301             case PabloAST::ClassTypeId::Assign:
    302             case PabloAST::ClassTypeId::Next:
    303                 simplifyAST(stmt, dyn_cast<Statement>(stmt->getOperand(0)), block);
    304             default: block.record(stmt);
    305         }       
    306     }
     276            }
     277        }
     278
     279        std::sort(variables.begin(), variables.end());
     280        std::unique(variables.begin(), variables.end());
     281
     282
     283        mManager = Cudd_Init(variables.size(), 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0);
     284        Cudd_AutodynEnable(mManager, CUDD_REORDER_LAZY_SIFT);
     285
     286        unsigned i = 0;
     287        for (PabloAST * var : variables) {
     288            mCharacterizationMap[var] = Cudd_bddIthVar(mManager, i++);
     289        }
     290
     291        for (PabloAST * term : terminals) {
     292            characterizeTerminalBddTree(term);
     293        }
     294        Cudd_ReduceHeap(mManager, CUDD_REORDER_SIFT, 0);
     295
     296        for (Statement * term : terminals) {
     297            DdNode * const f = mCharacterizationMap[term];
     298            Cudd_Ref(f);
     299            PabloAST * replacement = simplifyAST(f, variables, block);
     300            if (replacement) {
     301                term->replaceWith(replacement, false, true);
     302            }
     303            Cudd_RecursiveDeref(mManager, f);
     304        }
     305
     306        Cudd_Quit(mManager);
     307
     308        mCharacterizationMap.clear();
     309
     310        // Now clear our terminals and test whether we can process another layer within this block
     311        terminals.clear();
     312        for (PabloAST * var : variables) {
     313            if (isa<Statement>(var) && cast<Statement>(var)->getParent() == block.getPabloBlock()) {
     314                terminals.push_back(cast<Statement>(var));
     315            }
     316        }
     317    }
     318
     319}
     320
     321///** ------------------------------------------------------------------------------------------------------------- *
     322// * @brief simplifyAST
     323// ** ------------------------------------------------------------------------------------------------------------- */
     324DdNode * BDDMinimizationPass::characterizeTerminalBddTree(PabloAST * expr) {
     325
     326    const auto f = mCharacterizationMap.find(expr);
     327    if (f == mCharacterizationMap.end()) {
     328        return nullptr;
     329    } else if (f->second) {
     330        return f->second;
     331    }
     332
     333    Statement * stmt = cast<Statement>(expr);
     334    std::array<DdNode *, 3> input;
     335
     336    for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
     337        input[i] = characterizeTerminalBddTree(stmt->getOperand(i));
     338    }
     339
     340    DdNode * bdd = nullptr;
     341    switch (expr->getClassTypeId()) {
     342        case PabloAST::ClassTypeId::And:
     343            bdd = And(input[0], input[1]);
     344            break;
     345        case PabloAST::ClassTypeId::Or:
     346            bdd = Or(input[0], input[1]);
     347            break;
     348        case PabloAST::ClassTypeId::Not:
     349            bdd = Not(input[0]);
     350            break;
     351        case PabloAST::ClassTypeId::Sel:
     352            bdd = Ite(input[0], input[1], input[2]);
     353            break;
     354        default:
     355            throw std::runtime_error("Unexpected operand given to BDDMinimizationPass::characterizeTerminalBddTree!");
     356    }
     357    Cudd_Ref(bdd);
     358    return bdd;
    307359}
    308360
     
    310362 * @brief simplifyAST
    311363 ** ------------------------------------------------------------------------------------------------------------- */
    312 void BDDMinimizationPass::simplifyAST(Statement * stmt, Statement * const expr, PabloBuilder & builder) {
    313     if (expr && expr->getParent() == stmt->getParent()) {
    314         DdNode * const bdd = mCharacterizationMap[expr];
    315         if (bdd) {
    316             builder.getPabloBlock()->setInsertPoint(stmt->getPrevNode());
    317             Cudd_Ref(bdd);
    318             PabloAST * replacement = simplifyAST(bdd, builder);
    319             Cudd_RecursiveDeref(mManager, bdd);
    320             if (replacement) {
    321                 expr->replaceWith(replacement, true, true);
    322             }
    323         }
    324     }
    325 }
    326 
    327 /** ------------------------------------------------------------------------------------------------------------- *
    328  * @brief simplifyAST
    329  ** ------------------------------------------------------------------------------------------------------------- */
    330 PabloAST * BDDMinimizationPass::simplifyAST(DdNode * const f, PabloBuilder & builder) {
     364PabloAST * BDDMinimizationPass::simplifyAST(DdNode * const f, const std::vector<PabloAST *> & variables, PabloBuilder & builder) {
     365    assert (!noSatisfyingAssignment(f));
    331366    DdNode * g = Cudd_FindEssential(mManager, f);
    332367    if (g && Cudd_SupportSize(mManager, g) > 0) {
    333368        if (g == f) { // every variable is essential
    334             return makeCoverAST(f, builder);
     369            return makeCoverAST(f, variables, builder);
    335370        }
    336371        Cudd_Ref(g);
    337         PabloAST * c0 = makeCoverAST(g, builder);
     372        PabloAST * c0 = makeCoverAST(g, variables, builder);
    338373        if (LLVM_UNLIKELY(c0 == nullptr)) {
    339374            Cudd_RecursiveDeref(mManager, g);
     
    342377        DdNode * h = Cudd_Cofactor(mManager, f, g);
    343378        Cudd_Ref(h);
     379        PabloAST * c1 = simplifyAST(h, variables, builder);
     380        if (LLVM_UNLIKELY(c1 == nullptr)) {
     381            Cudd_RecursiveDeref(mManager, g);
     382            Cudd_RecursiveDeref(mManager, h);
     383            cast<Statement>(c0)->eraseFromParent(true);
     384            return nullptr;
     385        }
     386        assert (And(g, h) == f);
    344387        Cudd_RecursiveDeref(mManager, g);
    345         PabloAST * c1 = simplifyAST(h, builder);
    346388        Cudd_RecursiveDeref(mManager, h);
    347         if (LLVM_UNLIKELY(c1 == nullptr)) {
    348             if (LLVM_LIKELY(isa<Statement>(c0))) {
    349                 cast<Statement>(c0)->eraseFromParent(true);
    350             }
    351             return nullptr;
    352         }
    353         return builder.createAnd(c0, c1);
    354     }
     389        return builder.createAnd(c0, c1, "escf");
     390    }
     391
    355392    DdNode ** disjunct = nullptr;
    356     const auto disjuncts = Cudd_bddVarConjDecomp(mManager, f, &disjunct);
    357     if (LLVM_LIKELY(disjuncts == 2)) {
    358         Cudd_Ref(disjunct[0]);
    359         Cudd_Ref(disjunct[1]);
    360         PabloAST * d0 = simplifyAST(disjunct[0], builder);
    361         Cudd_RecursiveDeref(mManager, disjunct[0]);
     393    int disjuncts = Cudd_bddIterDisjDecomp(mManager, f, &disjunct);
     394    assert (disjuncts < 2 || Or(disjunct[0], disjunct[1]) == f);
     395
     396    DdNode ** conjunct = nullptr;
     397    int conjuncts = Cudd_bddIterConjDecomp(mManager, f, &conjunct);
     398    assert (conjuncts < 2 || And(conjunct[0], conjunct[1]) == f);
     399
     400    if (LLVM_LIKELY(disjuncts == 2 && conjuncts == 2)) {
     401        if (Cudd_SharingSize(disjunct, 2) > Cudd_SharingSize(conjunct, 2)) {
     402            disjuncts = 0;
     403        }
     404    }
     405
     406    DdNode * decomp[] = { nullptr, nullptr };
     407    if (disjuncts == 2) {
     408        memcpy(decomp, disjunct, sizeof(DdNode *) * 2);
     409    } else if (conjuncts == 2) {
     410        memcpy(decomp, conjunct, sizeof(DdNode *) * 2);
     411    }
     412
     413    FREE(disjunct);
     414    FREE(conjunct);
     415
     416    if ((decomp[0] != decomp[1]) && (decomp[0] != f) && (decomp[1] != f)) {
     417        Cudd_Ref(decomp[0]);
     418        Cudd_Ref(decomp[1]);
     419        PabloAST * d0 = simplifyAST(decomp[0], variables, builder);
     420        Cudd_RecursiveDeref(mManager, decomp[0]);
    362421        if (LLVM_UNLIKELY(d0 == nullptr)) {
    363             Cudd_RecursiveDeref(mManager, disjunct[1]);
    364             return nullptr;
    365         }
    366         PabloAST * d1 = simplifyAST(disjunct[1], builder);
    367         Cudd_RecursiveDeref(mManager, disjunct[1]);
    368         FREE(disjunct);
     422            Cudd_RecursiveDeref(mManager, decomp[1]);
     423            return nullptr;
     424        }
     425
     426        PabloAST * d1 = simplifyAST(decomp[1], variables, builder);
     427        Cudd_RecursiveDeref(mManager, decomp[1]);
    369428        if (LLVM_UNLIKELY(d1 == nullptr)) {
    370             if (LLVM_LIKELY(isa<Statement>(d0))) {
    371                 cast<Statement>(d0)->eraseFromParent(true);
    372             }
    373             return nullptr;
    374         }
    375         return builder.createAnd(d0, d1);
    376     }
    377     FREE(disjunct);
    378     return makeCoverAST(f, builder);
     429            cast<Statement>(d0)->eraseFromParent(true);
     430            return nullptr;
     431        }
     432
     433        if (disjuncts == 2) {
     434            return builder.createOr(d0, d1, "disj");
     435        } else {
     436            return builder.createAnd(d0, d1, "conj");
     437        }
     438    }
     439    return makeCoverAST(f, variables, builder);
    379440}
    380441
     
    382443 * @brief makeCoverAST
    383444 ** ------------------------------------------------------------------------------------------------------------- */
    384 PabloAST * BDDMinimizationPass::makeCoverAST(DdNode * const f, PabloBuilder & builder) {
     445PabloAST * BDDMinimizationPass::makeCoverAST(DdNode * const f, const std::vector<PabloAST *> & variables, PabloBuilder & builder) {
    385446
    386447    std::queue<PabloAST *> SQ;
    387 
    388     circular_buffer<PabloAST *> CQE(mManager->size);
    389     circular_buffer<PabloAST *> CQO(mManager->size);
    390 
    391     circular_buffer<PabloAST *> DQE(mManager->size);
    392     circular_buffer<PabloAST *> DQO(mManager->size);
    393 
    394     int cube[mManager->size];
     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());
     453
     454    int cube[n];
    395455
    396456    DdNode * g = f;
     
    399459
    400460    while (g != Cudd_ReadLogicZero(mManager)) {
    401         int length;
     461        int length = 0;
    402462        DdNode * implicant = Cudd_LargestCube(mManager, g, &length);
    403463        if (LLVM_UNLIKELY(implicant == nullptr)) {
     
    432492        Cudd_RecursiveDeref(mManager, prime);
    433493
    434         for (auto i = 0; i != mManager->size; ++i) {
    435             if ((i & 1) == 0) { // i is even
    436                 if (cube[i] == 0) {
    437                     DQE.push_back(mVariables[i]);
    438                 } else if (cube[i] == 1) {
    439                     CQE.push_back(mVariables[i]);
    440                 }
    441             } else { // i is odd
    442                 if (cube[i] == 0) {
    443                     DQO.push_back(mVariables[i]);
    444                 } else if (cube[i] == 1) {
    445                     CQO.push_back(mVariables[i]);
    446                 }
    447             }
    448         }
    449 
    450         PabloAST * dq = builder.createZeroes();
    451         if (!DQE.empty() || !DQO.empty()) {
    452             while (DQE.size() > 1) {
    453                 PabloAST * v1 = DQE.front(); DQE.pop_front();
    454                 PabloAST * v2 = DQE.front(); DQE.pop_front();
    455                 DQE.push_back(builder.createOr(v1, v2));
    456             }
    457             while (DQO.size() > 1) {
    458                 PabloAST * v1 = DQO.front(); DQO.pop_front();
    459                 PabloAST * v2 = DQO.front(); DQO.pop_front();
    460                 DQO.push_back(builder.createOr(v1, v2));
    461             }
    462             if (DQE.empty()) {
    463                 dq = DQO.front();
    464             } else if (DQO.empty()) {
    465                 dq = DQE.front();
    466             } else {
    467                 dq = builder.createOr(DQE.front(), DQO.front());
    468             }
    469             DQE.clear();
    470             DQO.clear();
    471         }
    472 
    473         PabloAST * cq = builder.createOnes();
    474         if (!CQE.empty() || !CQO.empty()) {
    475             while (CQE.size() > 1) {
    476                 PabloAST * v1 = CQE.front(); CQE.pop_front();
    477                 PabloAST * v2 = CQE.front(); CQE.pop_front();
    478                 CQE.push_back(builder.createOr(v1, v2));
    479             }
    480             while (CQO.size() > 1) {
    481                 PabloAST * v1 = CQO.front(); CQO.pop_front();
    482                 PabloAST * v2 = CQO.front(); CQO.pop_front();
    483                 CQO.push_back(builder.createOr(v1, v2));
    484             }
    485             if (CQE.empty()) {
    486                 dq = CQO.front();
    487             } else if (CQO.empty()) {
    488                 dq = CQE.front();
    489             } else {
    490                 dq = builder.createAnd(CQE.front(), CQO.front());
    491             }
    492             CQE.clear();
    493             CQO.clear();
    494         }
    495         SQ.push(builder.createAnd(cq, builder.createNot(dq)));
     494        assert (DQ.empty() && CQ.empty());
     495
     496        for (auto i = 0; i != n; ++i) {
     497            assert (cube[i] >= 0 && cube[i] <= 2);
     498            if (cube[i] == 0) {
     499                assert (!DQ.full());
     500                DQ.push_back(variables[i]);
     501            } else if (cube[i] == 1) {
     502                assert (!CQ.full());
     503                CQ.push_back(variables[i]);
     504            }
     505        }
     506
     507        if (LLVM_UNLIKELY(DQ.empty() && CQ.empty())) {
     508            throw std::runtime_error("Error! statement contains no elements!");
     509        }
     510
     511        if (DQ.size() > 0) {
     512            while (DQ.size() > 1) {
     513                PabloAST * v1 = DQ.front(); DQ.pop_front();
     514                PabloAST * v2 = DQ.front(); DQ.pop_front();
     515                DQ.push_back(builder.createOr(v1, v2));
     516            }
     517            CQ.push_back(builder.createNot(DQ.front()));
     518            DQ.pop_front();
     519        }
     520
     521        assert (!CQ.empty());
     522        while (CQ.size() > 1) {
     523            PabloAST * v1 = CQ.front(); CQ.pop_front();
     524            PabloAST * v2 = CQ.front(); CQ.pop_front();
     525            CQ.push_back(builder.createAnd(v1, v2));
     526        }
     527        SQ.push(CQ.front()); CQ.pop_front();
    496528    }
    497529    Cudd_RecursiveDeref(mManager, g);
    498 
     530    if (LLVM_UNLIKELY(SQ.empty())) {
     531        throw std::runtime_error("Error! statement queue empty!");
     532    }
    499533    while (SQ.size() > 1) {
    500534        PabloAST * v1 = SQ.front(); SQ.pop();
     
    502536        SQ.push(builder.createOr(v1, v2));
    503537    }
    504 
    505538    return SQ.front();
    506539}
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_bddminimization.h

    r4711 r4725  
    1818
    1919    using CharacterizationMap = llvm::DenseMap<const PabloAST *, DdNode *>;
    20     using StatementVector = std::vector<PabloAST *>;
     20    using Terminals = std::vector<Statement *>;
    2121
    2222    struct SubsitutionMap {
     
    4040
    4141public:
    42     static bool optimize(PabloFunction & function);
     42    static bool optimize(PabloFunction & function, const bool full = false);
    4343protected:
    44     static void promoteCrossBlockReachingDefs(const PabloFunction & function);
    45     void initialize(const PabloFunction & function);
    46     void characterizeAndEliminateLogicallyEquivalentStatements(PabloFunction & function);
    47     void characterizeAndEliminateLogicallyEquivalentStatements(PabloBlock & block, SubsitutionMap & parent);
    48     DdNode * characterizeAndEliminateLogicallyEquivalentStatements(const Statement * const stmt);
     44    void eliminateLogicallyEquivalentStatements(PabloFunction & function);
     45    void eliminateLogicallyEquivalentStatements(PabloBlock & block, SubsitutionMap & parent);
     46    DdNode * eliminateLogicallyEquivalentStatements(const Statement * const stmt);
    4947    void simplifyAST(PabloFunction & function);
    50     void simplifyAST(PabloBuilder & block);
     48    void simplifyAST(PabloBuilder & block, std::vector<Statement *> &terminals);
     49    DdNode * characterizeTerminalBddTree(PabloAST * expr);
    5150    void simplifyAST(Statement *stmt, Statement * const value, PabloBuilder & builder);
    52     PabloAST * simplifyAST(DdNode * const f, PabloBuilder & builder);
    53     PabloAST * makeCoverAST(DdNode * const f, 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);
    5453private:
    5554    DdNode * Zero() const;
     
    6867    DdManager *                     mManager;
    6968    std::vector<PabloAST *>         mVariables;
    70     std::vector<const Statement *>  mPromotions;
    7169    CharacterizationMap             mCharacterizationMap;
    7270};
Note: See TracChangeset for help on using the changeset viewer.