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

Temporary check-in.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • 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
Note: See TracChangeset for help on using the changeset viewer.