Ignore:
Timestamp:
Jul 31, 2015, 5:26:50 PM (4 years ago)
Author:
nmedfort
Message:

Temporary check-in.

Location:
icGREP/icgrep-devel/icgrep/pablo
Files:
7 edited

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/pablo/builder.hpp

    r4699 r4711  
    2727    }
    2828
     29    using iterator = PabloBlock::iterator;
     30
     31    using const_iterator = PabloBlock::const_iterator;
     32
    2933    inline static PabloBuilder Create(PabloBuilder & parent) noexcept {
    3034        return std::move(PabloBuilder(PabloBlock::Create(*(parent.mPb)), parent));
     
    163167    }
    164168
     169    /// Statement Iterator Wrappers
     170
     171    iterator begin() {
     172        return mPb->begin();
     173    }
     174
     175    iterator end() {
     176        return mPb->end();
     177    }
     178
     179    const_iterator begin() const {
     180        return mPb->cbegin();
     181    }
     182
     183    const_iterator end() const {
     184        return mPb->cend();
     185    }
     186
     187    const_iterator cbegin() const {
     188        return mPb->cbegin();
     189    }
     190
     191    const_iterator cend() const {
     192        return mPb->cend();
     193    }
     194
    165195    inline Statement * front() const {
    166196        return mPb->front();
     
    194224    inline PabloBuilder * getParent() {
    195225        return mParent;
     226    }
     227
     228    inline void record(Statement * stmt) {
     229        mExprTable.findOrAdd(stmt);
    196230    }
    197231
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.cpp

    r4702 r4711  
    1111#include <llvm/ADT/BitVector.h>
    1212#include <cudd.h>
     13#include <cuddInt.h>
    1314#include <util.h>
    1415#include <stack>
    1516#include <queue>
    1617#include <unordered_set>
    17 
    18 #include <pablo/optimizers/pablo_simplifier.hpp>
    19 #include <pablo/optimizers/pablo_bddminimization.h>
    2018
    2119using namespace llvm;
     
    135133    LOG("GenerateMultiplexSets:   " << (end_create_multiplex_graph - start_create_multiplex_graph));
    136134
     135    RECORD_TIMESTAMP(start_shutdown);
     136    am.Shutdown();
     137    RECORD_TIMESTAMP(end_shutdown);
     138    LOG("Shutdown:                " << (end_shutdown - start_shutdown));
     139
    137140    if (multiplex) {
    138141
     
    148151
    149152        RECORD_TIMESTAMP(start_select_independent_sets);
    150         auto multiplexedSets = am.multiplexSelectedIndependentSets();
     153        am.multiplexSelectedIndependentSets();
    151154        RECORD_TIMESTAMP(end_select_independent_sets);
    152155        LOG("MultiplexSelectedSets:   " << (end_select_independent_sets - start_select_independent_sets));
     
    156159        RECORD_TIMESTAMP(end_topological_sort);
    157160        LOG("TopologicalSort:         " << (end_topological_sort - start_topological_sort));
    158 
    159         llvm::raw_os_ostream out(std::cerr);
    160         PabloPrinter::print(function.getEntryBlock(), out);
    161         out.flush();
    162 
    163         RECORD_TIMESTAMP(start_reduce);
    164         am.reduce(multiplexedSets);
    165         RECORD_TIMESTAMP(end_reduce);
    166         LOG("Reduce:                  " << (end_reduce - start_reduce));
    167     }
    168 
    169     RECORD_TIMESTAMP(start_shutdown);
    170     am.Shutdown();
    171     RECORD_TIMESTAMP(end_shutdown);
    172     LOG("Shutdown:                " << (end_shutdown - start_shutdown));
     161    }
    173162
    174163    LOG_NUMBER_OF_ADVANCES(function.getEntryBlock());
    175 
    176     // BDDMinimizationPass::optimize(function);
    177164
    178165    return multiplex;
     
    376363                }
    377364            }
    378 
    379             assert (Cudd_DebugCheck(mManager) == 0);
    380 
    381365            mRecentCharacterizations.erase(mRecentCharacterizations.begin() + start, mRecentCharacterizations.end());
    382366            continue;
     
    455439
    456440    Ref(bdd);
    457 
    458441    if (LLVM_UNLIKELY(NoSatisfyingAssignment(bdd))) {
    459442        Deref(bdd);
     
    463446        if (LLVM_UNLIKELY(isa<Advance>(stmt) || isa<Assign>(stmt) || isa<Next>(stmt))) {
    464447            stmt->setOperand(0, stmt->getParent()->createZeroes());
     448            bdd = Zero();
    465449        }
    466450        else {
    467451            stmt->replaceWith(stmt->getParent()->createZeroes());
    468         }
    469         bdd = Zero();
    470     }
    471 
     452            return nullptr;
     453        }
     454    }
    472455    mRecentCharacterizations.emplace_back(stmt, bdd);
    473456    return bdd;
     
    973956 * @brief multiplexSelectedIndependentSets
    974957 ** ------------------------------------------------------------------------------------------------------------- */
    975 std::vector<std::vector<PabloAST *>> AutoMultiplexing::multiplexSelectedIndependentSets() const {
     958void AutoMultiplexing::multiplexSelectedIndependentSets() const {
    976959
    977960    const unsigned f = num_vertices(mConstraintGraph);
     
    985968
    986969    std::vector<MultiplexSetGraph::vertex_descriptor> I(max_n);
    987     std::vector<Advance *> input(max_n);
    988     std::vector<std::vector<PabloAST *>> outputs;
    989970    circular_buffer<PabloAST *> Q(max_n);
    990971
     
    995976        const size_t n = out_degree(s, mMultiplexSetGraph);
    996977        if (n) {
    997 
    998978            const size_t m = log2_plus_one(n);
    999 
    1000             std::vector<PabloAST *> muxed(m);
     979            Advance * input[n];
     980            Advance * muxed[m];
    1001981
    1002982            graph_traits<MultiplexSetGraph>::out_edge_iterator ei, ei_end;
     
    10351015
    10361016                PabloAST * mux = Q.front(); Q.pop_front(); assert (mux);
    1037                 muxed[j] = builder.createAdvance(mux, adv->getOperand(1), prefix.str());
     1017                // The only way this did not return an Advance statement would be if either the mux or shift amount
     1018                // is zero. Since these cases would have been eliminated earlier, we are safe to cast here.
     1019                muxed[j] = cast<Advance>(builder.createAdvance(mux, adv->getOperand(1), prefix.str()));
    10381020            }
    10391021
     
    10431025                // Construct the demuxed values and replaces all the users of the original advances with them.
    10441026                for (size_t j = 0; j != m; ++j) {
    1045                     if ((i & (static_cast<size_t>(1) << j)) == 0) {
     1027                    if ((i & (1ULL << j)) == 0) {
    10461028                        Q.push_back(muxed[j]);
    10471029                    }
     
    10611043
    10621044                for (unsigned j = 0; j != m; ++j) {
    1063                     if ((i & (static_cast<unsigned>(1) << j)) != 0) {
     1045                    if ((i & (1ULL << j)) != 0) {
    10641046                        assert (!Q.full());
    10651047                        Q.push_back(muxed[j]);
     
    10771059                input[i - 1]->replaceWith(demuxed, true, true);
    10781060            }
    1079             outputs.push_back(std::move(muxed));
    1080         }
    1081     }
    1082     return outputs;
     1061
     1062            /// Attempt to simplify the demultiplexed values
     1063            // simplifyAST(muxed, m, builder);
     1064        }
     1065    }
    10831066}
    10841067
    10851068/** ------------------------------------------------------------------------------------------------------------- *
    1086  * @brief reduce
     1069 * @brief simplifyAST
    10871070 ** ------------------------------------------------------------------------------------------------------------- */
    1088 inline bool isBinaryOp(const PabloAST * const expr) {
    1089     switch (expr->getClassTypeId()) {
    1090         case PabloAST::ClassTypeId::And:
    1091         case PabloAST::ClassTypeId::Or:
    1092         case PabloAST::ClassTypeId::Not:
    1093         case PabloAST::ClassTypeId::Xor:
    1094         case PabloAST::ClassTypeId::Sel:
    1095             return true;
    1096         default:
    1097             return false;
    1098     }
    1099 }
    1100 
    1101 
    1102 void AutoMultiplexing::reduce(const std::vector<std::vector<PabloAST *>> & sets) const {
    1103 
    1104     for (const auto & set : sets) {
    1105 
    1106         // first do a BFS to build a topological ordering of statements we're going to end up visiting
    1107         // and determine which of those will be terminals in the BDD
    1108         using Graph = adjacency_list<hash_setS, vecS, bidirectionalS, PabloAST *>;
    1109         using Vertex = Graph::vertex_descriptor;
    1110 
    1111         Graph G;
    1112         std::unordered_map<PabloAST *, unsigned> M;
    1113 
    1114         std::queue<Statement *> Q;
    1115 
    1116         llvm::raw_os_ostream out(std::cerr);
    1117 
    1118         for (PabloAST * inst : set) {
    1119             if (LLVM_LIKELY(isa<Advance>(inst))) {
    1120                 const auto u = add_vertex(inst, G);
    1121                 M.insert(std::make_pair(inst, u));
    1122 
    1123                 for (PabloAST * user : inst->users()) {
    1124                     auto f = M.find(user);
    1125                     Vertex v = 0;
    1126                     if (f == M.end()) {
    1127                         v = add_vertex(user, G);
    1128                         M.insert(std::make_pair(user, v));
    1129                         if (isBinaryOp(user)) {
    1130                             Q.push(cast<Statement>(user));
    1131                         }
    1132                     } else { // if (f != M.end()) {
    1133                         v = f->second;
    1134                     }
    1135                     add_edge(u, v, G);
     1071void AutoMultiplexing::simplifyAST(Advance * const muxed[], const unsigned m, PabloBuilder & builder) const {
     1072
     1073    // first do a BFS to build a topological ordering of statements we're going to end up visiting
     1074    // and determine which of those will be terminals in the BDD
     1075    using Graph = adjacency_list<hash_setS, vecS, bidirectionalS, PabloAST *>;
     1076    using Vertex = Graph::vertex_descriptor;
     1077
     1078    Graph G;
     1079    std::unordered_map<PabloAST *, unsigned> M;
     1080    std::queue<Statement *> Q;
     1081
     1082    for (unsigned i = 0; i != m; ++i) {
     1083
     1084        const auto u = add_vertex(muxed[i], G);
     1085        M.insert(std::make_pair(muxed[i], u));
     1086        for (PabloAST * user : muxed[i]->users()) {
     1087            auto f = M.find(user);
     1088            Vertex v = 0;
     1089            if (f == M.end()) {
     1090                v = add_vertex(user, G);
     1091                M.insert(std::make_pair(user, v));
     1092                switch (user->getClassTypeId()) {
     1093                    case PabloAST::ClassTypeId::And:
     1094                    case PabloAST::ClassTypeId::Or:
     1095                    case PabloAST::ClassTypeId::Not:
     1096                    case PabloAST::ClassTypeId::Sel:
     1097                        Q.push(cast<Statement>(user));
     1098                    default: break;
    11361099                }
    1137 
    1138             }
    1139         }
    1140 
    1141         while (!Q.empty()) {
    1142             Statement * const var = Q.front(); Q.pop();
    1143             const Vertex u = M[var];
    1144 
    1145             for (unsigned i = 0; i != var->getNumOperands(); ++i) {
    1146                 PabloAST * operand = var->getOperand(i);
    1147                 auto f = M.find(operand);
    1148                 Vertex v;
    1149                 if (LLVM_UNLIKELY(f == M.end())) {
    1150                     v = add_vertex(operand, G);
    1151                     M.insert(std::make_pair(operand, v));
    1152                 } else { // if (f != M.end()) {
    1153                     v = f->second;
     1100            } else { // if (f != M.end()) {
     1101                v = f->second;
     1102            }
     1103            add_edge(u, v, G);
     1104        }
     1105    }
     1106
     1107    while (!Q.empty()) {
     1108        Statement * const var = Q.front(); Q.pop();
     1109        const Vertex u = M[var];
     1110        for (unsigned i = 0; i != var->getNumOperands(); ++i) {
     1111            PabloAST * operand = var->getOperand(i);
     1112            auto f = M.find(operand);
     1113            Vertex v = 0;
     1114            if (LLVM_UNLIKELY(f == M.end())) {
     1115                v = add_vertex(operand, G);
     1116                M.insert(std::make_pair(operand, v));
     1117            } else { // if (f != M.end()) {
     1118                v = f->second;
     1119            }
     1120            add_edge(v, u, G);
     1121        }
     1122
     1123        for (PabloAST * user : var->users()) {
     1124            auto f = M.find(user);
     1125            Vertex v = 0;
     1126            if (LLVM_LIKELY(f == M.end())) {
     1127                v = add_vertex(user, G);
     1128                M.insert(std::make_pair(user, v));
     1129                switch (user->getClassTypeId()) {
     1130                    case PabloAST::ClassTypeId::And:
     1131                    case PabloAST::ClassTypeId::Or:
     1132                    case PabloAST::ClassTypeId::Not:
     1133                    case PabloAST::ClassTypeId::Sel:
     1134                        Q.push(cast<Statement>(user));
     1135                    default: break;
    11541136                }
    1155                 add_edge(v, u, G);
    1156             }
    1157 
    1158             for (PabloAST * user : var->users()) {
    1159                 auto f = M.find(user);
    1160                 Vertex v = 0;
    1161                 if (LLVM_LIKELY(f == M.end())) {
    1162                     v = add_vertex(user, G);
    1163                     M.insert(std::make_pair(user, v));
    1164                     if (isBinaryOp(user)) {
    1165                         Q.push(cast<Statement>(user));
    1166                     }
    1167                 } else { // if (f != M.end()) {
    1168                     v = f->second;
    1169                 }
    1170                 add_edge(u, v, G);
    1171             }
    1172         }
    1173 
    1174         out << "\ndigraph G {\n";
    1175         for (auto u : make_iterator_range(vertices(G))) {
    1176             out << "  v" << u;
    1177             PabloPrinter::print(cast<Statement>(G[u]), " [label=\"", out);
    1178             out << "\"];\n";
    1179         }
    1180         for (auto e : make_iterator_range(edges(G))) {
    1181             out << "  v" << source(e, G) << " -> v" << target(e, G) << ";\n";
    1182         }
    1183         out << "}\n\n";
     1137            } else { // if (f != M.end()) {
     1138                v = f->second;
     1139            }
     1140            add_edge(u, v, G);
     1141        }
     1142    }
     1143
     1144    // count the number of sources (sinks) so we know how many inputs (terminals) will exist in the BDD
     1145    std::vector<Vertex> inputs;
     1146    flat_set<Vertex> terminals;
     1147    for (auto u : make_iterator_range(vertices(G))) {
     1148        if (in_degree(u, G) == 0) {
     1149            inputs.push_back(u);
     1150        }
     1151        if (out_degree(u, G) == 0) {
     1152            // the inputs to the sinks become the terminals in the BDD
     1153            for (auto e : make_iterator_range(in_edges(u, G))) {
     1154                terminals.insert(source(e, G));
     1155            }
     1156        }
     1157    }
     1158
     1159    const auto n = inputs.size();
     1160
     1161    DdManager * manager = Cudd_Init(n, 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0);
     1162    Cudd_AutodynEnable(manager, CUDD_REORDER_LAZY_SIFT);
     1163
     1164    PabloAST * variables[n];
     1165    std::vector<DdNode *> characterization(num_vertices(G), nullptr);
     1166    for (unsigned i = 0; i != n; ++i) {
     1167        variables[i] = G[inputs[i]];
     1168        characterization[inputs[i]] = Cudd_bddIthVar(manager, i);
     1169    }
     1170
     1171    std::vector<Vertex> ordering;
     1172    ordering.reserve(num_vertices(G));
     1173    topological_sort(G, std::back_inserter(ordering));
     1174
     1175    for (auto ui = ordering.rbegin(); ui != ordering.rend(); ++ui) {
     1176
     1177        const Vertex u = *ui;
     1178
     1179        if (characterization[u]) {
     1180            continue;
     1181        }
     1182
     1183        std::array<DdNode *, 3> input;
     1184
     1185        unsigned i = 0;
     1186        for (const auto e : make_iterator_range(in_edges(u, G))) {
     1187            input[i++] = characterization[source(e, G)];
     1188
     1189        }
     1190
     1191        assert (is<Statement>(G[u]) ? i == cast<Statement>(G[u])->getNumOperands() : i == 0);
     1192
     1193        DdNode * bdd = nullptr;
     1194        bool characterized = true;
     1195        switch (G[u]->getClassTypeId()) {
     1196            case PabloAST::ClassTypeId::And:
     1197                bdd = Cudd_bddAnd(manager, input[0], input[1]);
     1198                break;
     1199            case PabloAST::ClassTypeId::Or:
     1200                bdd = Cudd_bddOr(manager, input[0], input[1]);
     1201                break;
     1202            case PabloAST::ClassTypeId::Not:
     1203                bdd = Cudd_Not(input[0]);
     1204                break;
     1205            case PabloAST::ClassTypeId::Sel:
     1206                bdd = Cudd_bddIte(manager, input[0], input[1], input[2]);
     1207                break;
     1208            default: characterized = false; break;
     1209        }
     1210
     1211        if (characterized) {
     1212            Cudd_Ref(bdd);
     1213            characterization[u] = bdd;
     1214        }
     1215    }
     1216
     1217    Cudd_AutodynDisable(manager);
     1218    Cudd_ReduceHeap(manager, CUDD_REORDER_SIFT, 0);
     1219    Cudd_ReduceHeap(manager, CUDD_REORDER_EXACT, 0);
     1220
     1221    raw_os_ostream out(std::cerr);
     1222
     1223    for (Vertex t : terminals) {
     1224
     1225//        out << "*******************************************************************************************\n";
     1226//        PabloPrinter::print(*(builder.getPabloBlock()), "", out);
     1227//        out << "\n\n";
     1228        PabloPrinter::print(cast<Statement>(G[t]), " >> ", out);
     1229        out << '\n';
    11841230        out.flush();
    11851231
    1186         // count the number of sinks (sources) so we know how many variables (terminals) will exist in the BDD
    1187         std::vector<Vertex> variable;
    1188         flat_set<Vertex> terminal;
    1189         for (auto u : make_iterator_range(vertices(G))) {
    1190             if (in_degree(u, G) == 0) {
    1191                 variable.push_back(u);
    1192             }
    1193             if (out_degree(u, G) == 0) {
    1194                 // the inputs to the sinks become the terminals in the BDD
    1195                 for (auto e : make_iterator_range(in_edges(u, G))) {
    1196                     terminal.insert(target(e, G));
    1197                 }
    1198             }
    1199         }
    1200 
    1201         DdManager * manager = Cudd_Init(variable.size(), 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0);
    1202         Cudd_AutodynEnable(manager, CUDD_REORDER_LAZY_SIFT);
    1203 
    1204         std::vector<DdNode *> characterization(num_vertices(G), nullptr);
    1205         unsigned i = 0;
    1206         for (auto u : variable) {
    1207             characterization[u] = Cudd_bddIthVar(manager, i++);
    1208         }
    1209 
    1210         std::vector<Vertex> ordering;
    1211         ordering.reserve(num_vertices(G));
    1212         topological_sort(G, std::back_inserter(ordering));
    1213 
    1214         for (auto ui = ordering.rbegin(); ui != ordering.rend(); ++ui) {
    1215 
    1216             const Vertex u = *ui;
    1217 
    1218             Statement * stmt = cast<Statement>(G[u]);
    1219 
    1220             out << u; PabloPrinter::print(stmt, " : ", out); out << " = " << (long)characterization[u] << '\n';
     1232        DdNode * const f = characterization[t];
     1233        Cudd_Ref(f);
     1234        PabloAST * expr;
     1235        unsigned count;
     1236        std::tie(expr, count) = simplifyAST(manager, f, variables, builder);
     1237        if (expr) {
     1238
     1239            PabloPrinter::print(cast<Statement>(expr), "    replacement: ", out);
     1240            out << '\n';
    12211241            out.flush();
    12221242
    1223             if (characterization[u]) {
    1224                 continue;
    1225             }
    1226 
    1227             std::array<DdNode *, 3> input;
    1228 
    1229             unsigned i = 0;
    1230             for (const auto e : make_iterator_range(in_edges(u, G))) {
    1231                 input[i++] = characterization[source(e, G)];
    1232 
    1233             }
    1234 
    1235             assert (is<Statement>(G[u]) ? i == cast<Statement>(G[u])->getNumOperands() : i == 0);
    1236 
    1237             DdNode * bdd = nullptr;
    1238 
    1239             switch (G[u]->getClassTypeId()) {
    1240                 case PabloAST::ClassTypeId::And:
    1241                     bdd = Cudd_bddAnd(manager, input[0], input[1]);
    1242                     break;
    1243                 case PabloAST::ClassTypeId::Or:
    1244                     bdd = Cudd_bddOr(manager, input[0], input[1]);
    1245                     break;
    1246                 case PabloAST::ClassTypeId::Not:
    1247                     bdd = Cudd_Not(input[0]);
    1248                     break;
    1249                 case PabloAST::ClassTypeId::Xor:
    1250                     bdd = Cudd_bddXor(manager, input[0], input[1]);
    1251                     break;
    1252                 case PabloAST::ClassTypeId::Sel:
    1253                     bdd = Cudd_bddIte(manager, input[0], input[1], input[2]);
    1254                     break;
    1255                 default: break;
    1256             }
    1257 
    1258             characterization[u] = bdd;
    1259         }
    1260 
    1261         Cudd_ReduceHeap(manager, CUDD_REORDER_SIFT, 0);
    1262 
    1263         for (auto t : terminal) {
    1264 
    1265             llvm::raw_os_ostream out(std::cerr);
    1266             out << " REDUNCTION : "; PabloPrinter::print(G[t], out); out << '\n';
    1267             out.flush();
    1268 
    1269             DdNode * bdd = characterization[t];
    1270             Cudd_bddPrintCover(manager, bdd, bdd);
    1271 
    1272             out << '\n'; out.flush();
    1273         }
    1274 
    1275         Cudd_Quit(manager);
    1276     }
    1277 
    1278 }
     1243            cast<Statement>(G[t])->replaceWith(expr, true, true);
     1244        }
     1245        Cudd_RecursiveDeref(manager, f);
     1246    }
     1247
     1248//    out << "+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n";
     1249//    PabloPrinter::print(*(builder.getPabloBlock()), "", out);
     1250//    out << '\n';
     1251//    out.flush();
     1252
     1253    Cudd_Quit(manager);
     1254}
     1255
     1256/** ------------------------------------------------------------------------------------------------------------- *
     1257 * @brief simplifyAST
     1258 ** ------------------------------------------------------------------------------------------------------------- */
     1259std::pair<PabloAST *, unsigned> AutoMultiplexing::simplifyAST(DdManager * manager, DdNode * const f, PabloAST * const variables[], PabloBuilder & builder) const {
     1260    DdNode * g = Cudd_FindEssential(manager, f);
     1261    if (g && Cudd_SupportSize(manager, g) > 0) {
     1262        if (g == f) { // every variable is essential
     1263            return makeCoverAST(manager, f, variables, builder);
     1264        }
     1265        Cudd_Ref(g);
     1266        PabloAST * c0;
     1267        unsigned count0;
     1268        std::tie(c0, count0) = makeCoverAST(manager, g, variables, builder);
     1269        if (LLVM_UNLIKELY(c0 == nullptr)) {
     1270            Cudd_RecursiveDeref(manager, g);
     1271            return std::make_pair(nullptr, 0);
     1272        }
     1273        DdNode * h = Cudd_Cofactor(manager, f, g);
     1274        Cudd_Ref(h);
     1275        Cudd_RecursiveDeref(manager, g);
     1276        PabloAST * c1;
     1277        unsigned count1;
     1278        std::tie(c1, count1) = simplifyAST(manager, h, variables, builder);
     1279        Cudd_RecursiveDeref(manager, h);
     1280        if (LLVM_UNLIKELY(c1 == nullptr)) {
     1281            cast<Statement>(c0)->eraseFromParent(true);
     1282            return std::make_pair(nullptr, 0);
     1283        }
     1284        return std::make_pair(builder.createAnd(c0, c1), count0 + count1 + 1);
     1285    }
     1286
     1287    PabloAST * disjunctionAST = nullptr;
     1288    unsigned disjunctionCount = 0;
     1289    PabloAST * conjunctionAST = nullptr;
     1290    unsigned conjunctionCount = 0;
     1291
     1292    DdNode ** decomp = nullptr;
     1293    const auto disjuncts = Cudd_bddGenDisjDecomp(manager, f, &decomp);
     1294    if (LLVM_LIKELY(disjuncts == 2)) {
     1295        Cudd_Ref(decomp[0]);
     1296        Cudd_Ref(decomp[1]);
     1297        PabloAST * d0;
     1298        unsigned count0;
     1299        std::tie(d0, count0) = simplifyAST(manager, decomp[0], variables, builder);
     1300        Cudd_RecursiveDeref(manager, decomp[0]);
     1301        if (LLVM_UNLIKELY(d0 == nullptr)) {
     1302            Cudd_RecursiveDeref(manager, decomp[1]);
     1303            return std::make_pair(nullptr, 0);
     1304        }
     1305        PabloAST * d1;
     1306        unsigned count1;
     1307        std::tie(d1, count1) = simplifyAST(manager, decomp[1], variables, builder);
     1308        Cudd_RecursiveDeref(manager, decomp[1]);
     1309        FREE(decomp);
     1310        if (LLVM_UNLIKELY(d1 == nullptr)) {
     1311            cast<Statement>(d0)->eraseFromParent(true);
     1312            return std::make_pair(nullptr, 0);
     1313        }
     1314        disjunctionAST = builder.createOr(d0, d1);
     1315        disjunctionCount = count0 + count1 + 1;
     1316    }
     1317    FREE(decomp);
     1318
     1319    const auto conjuncts = Cudd_bddGenConjDecomp(manager, f, &decomp);
     1320    if (LLVM_LIKELY(conjuncts == 2)) {
     1321        Cudd_Ref(decomp[0]);
     1322        Cudd_Ref(decomp[1]);
     1323        PabloAST * d0;
     1324        unsigned count0;
     1325        std::tie(d0, count0) = simplifyAST(manager, decomp[0], variables, builder);
     1326        Cudd_RecursiveDeref(manager, decomp[0]);
     1327        if (LLVM_UNLIKELY(d0 == nullptr)) {
     1328            Cudd_RecursiveDeref(manager, decomp[1]);
     1329            return std::make_pair(nullptr, 0);
     1330        }
     1331        PabloAST * d1;
     1332        unsigned count1;
     1333        std::tie(d1, count1) = simplifyAST(manager, decomp[1], variables, builder);
     1334        Cudd_RecursiveDeref(manager, decomp[1]);
     1335        FREE(decomp);
     1336        if (LLVM_UNLIKELY(d1 == nullptr)) {
     1337            cast<Statement>(d0)->eraseFromParent(true);
     1338            return std::make_pair(nullptr, 0);
     1339        }
     1340        conjunctionAST = builder.createAnd(d0, d1);
     1341        conjunctionCount = count0 + count1 + 1;
     1342    }
     1343    FREE(decomp);
     1344
     1345    if (disjunctionAST && conjunctionAST) {
     1346        if (disjunctionCount > conjunctionCount) {
     1347            cast<Statement>(disjunctionAST)->eraseFromParent(true);
     1348            return std::make_pair(conjunctionAST, conjunctionCount);
     1349        } else {
     1350            cast<Statement>(conjunctionAST)->eraseFromParent(true);
     1351            return std::make_pair(disjunctionAST, disjunctionCount);
     1352        }
     1353    } else if (disjunctionAST) {
     1354        return std::make_pair(disjunctionAST, disjunctionCount);
     1355    } else if (conjunctionAST) {
     1356        return std::make_pair(conjunctionAST, conjunctionCount);
     1357    }
     1358    return makeCoverAST(manager, f, variables, builder);
     1359}
     1360
     1361/** ------------------------------------------------------------------------------------------------------------- *
     1362 * @brief makeCoverAST
     1363 ** ------------------------------------------------------------------------------------------------------------- */
     1364std::pair<PabloAST *, unsigned> AutoMultiplexing::makeCoverAST(DdManager * manager, DdNode * const f, PabloAST * const variables[], PabloBuilder & builder) const {
     1365
     1366    std::queue<PabloAST *> SQ;
     1367
     1368    circular_buffer<PabloAST *> CQ(manager->size);
     1369    circular_buffer<PabloAST *> DQ(manager->size);
     1370
     1371    int cube[manager->size];
     1372
     1373    unsigned count = 0;
     1374
     1375    DdNode * g = f;
     1376
     1377    Cudd_Ref(g);
     1378
     1379    while (g != Cudd_ReadLogicZero(manager)) {
     1380        int length;
     1381        DdNode * implicant = Cudd_LargestCube(manager, g, &length);
     1382        if (LLVM_UNLIKELY(implicant == nullptr)) {
     1383            Cudd_RecursiveDeref(manager, g);
     1384            return std::make_pair(nullptr, 0);
     1385        }
     1386        Cudd_Ref(implicant);
     1387        DdNode * prime = Cudd_bddMakePrime(manager, implicant, f);
     1388        if (LLVM_UNLIKELY(prime == nullptr)) {
     1389            Cudd_RecursiveDeref(manager, g);
     1390            Cudd_RecursiveDeref(manager, implicant);
     1391            return std::make_pair(nullptr, 0);
     1392        }
     1393        Cudd_Ref(prime);
     1394        Cudd_RecursiveDeref(manager, implicant);
     1395
     1396        DdNode * h = Cudd_bddAnd(manager, g, Cudd_Not(prime));
     1397        if (LLVM_UNLIKELY(h == nullptr)) {
     1398            Cudd_RecursiveDeref(manager, g);
     1399            Cudd_RecursiveDeref(manager, prime);
     1400            return std::make_pair(nullptr, 0);
     1401        }
     1402        Cudd_Ref(h);
     1403        Cudd_RecursiveDeref(manager, g);
     1404
     1405        g = h;
     1406        if (LLVM_UNLIKELY(Cudd_BddToCubeArray(manager, prime, cube) == 0)) {
     1407            Cudd_RecursiveDeref(manager, g);
     1408            Cudd_RecursiveDeref(manager, prime);
     1409            return std::make_pair(nullptr, 0);
     1410        }
     1411        Cudd_RecursiveDeref(manager, prime);
     1412
     1413        for (auto i = 0; i != manager->size; ++i) {
     1414            if (cube[i] == 0) {
     1415                DQ.push_back(variables[i]);
     1416            } else if (cube[i] == 1) {
     1417                CQ.push_back(variables[i]);
     1418            }
     1419        }
     1420        if (!DQ.empty()) {
     1421            while (DQ.size() > 1) {
     1422                PabloAST * v1 = DQ.front(); DQ.pop_front();
     1423                PabloAST * v2 = DQ.front(); DQ.pop_front();
     1424                DQ.push_back(builder.createOr(v1, v2));
     1425                ++count;
     1426            }
     1427            CQ.push_back(builder.createNot(DQ.front()));
     1428            DQ.clear();
     1429        }
     1430        while (CQ.size() > 1) {
     1431            PabloAST * v1 = CQ.front(); CQ.pop_front();
     1432            PabloAST * v2 = CQ.front(); CQ.pop_front();
     1433            CQ.push_back(builder.createAnd(v1, v2));
     1434            ++count;
     1435        }
     1436        SQ.push(CQ.front()); CQ.clear();
     1437    }
     1438    Cudd_RecursiveDeref(manager, g);
     1439
     1440    while (SQ.size() > 1) {
     1441        PabloAST * v1 = SQ.front(); SQ.pop();
     1442        PabloAST * v2 = SQ.front(); SQ.pop();
     1443        SQ.push(builder.createOr(v1, v2));
     1444        ++count;
     1445    }
     1446
     1447    return std::make_pair(SQ.front(), count);
     1448}
     1449
     1450///** ------------------------------------------------------------------------------------------------------------- *
     1451// * @brief reduce
     1452// ** ------------------------------------------------------------------------------------------------------------- */
     1453//inline bool isBinaryOp(const PabloAST * const expr) {
     1454//    switch (expr->getClassTypeId()) {
     1455//        case PabloAST::ClassTypeId::And:
     1456//        case PabloAST::ClassTypeId::Or:
     1457//        case PabloAST::ClassTypeId::Not:
     1458//        case PabloAST::ClassTypeId::Xor:
     1459//        case PabloAST::ClassTypeId::Sel:
     1460//            return true;
     1461//        default:
     1462//            return false;
     1463//    }
     1464//}
     1465
     1466///** ------------------------------------------------------------------------------------------------------------- *
     1467// * @brief minimizeCoFactor
     1468// ** ------------------------------------------------------------------------------------------------------------- */
     1469//PabloAST * minimizeCoFactor(DdManager * const manager, DdNode * const f, const std::vector<PabloAST *> & variables, PabloBuilder & builder) {
     1470
     1471//    std::queue<PabloAST *> SQ;
     1472//    std::queue<PabloAST *> CQ;
     1473//    std::queue<PabloAST *> DQ;
     1474
     1475//    int cube[manager->size];
     1476
     1477//    DdNode * g = f;
     1478
     1479//    Cudd_Ref(g);
     1480
     1481//    while (g != Cudd_ReadLogicZero(manager)) {
     1482//        int length;
     1483//        DdNode * implicant = Cudd_LargestCube(manager, g, &length);
     1484//        if (LLVM_UNLIKELY(implicant == nullptr)) {
     1485//            Cudd_RecursiveDeref(manager, g);
     1486//            std::cerr << "Cudd_LargestCube" << std::endl;
     1487//            return nullptr;
     1488//        }
     1489//        Cudd_Ref(implicant);
     1490//        DdNode * prime = Cudd_bddMakePrime(manager, implicant, f);
     1491//        if (LLVM_UNLIKELY(prime == nullptr)) {
     1492//            Cudd_RecursiveDeref(manager, g);
     1493//            Cudd_RecursiveDeref(manager, implicant);
     1494//            std::cerr << "Cudd_bddMakePrime" << std::endl;
     1495//            return nullptr;
     1496//        }
     1497//        Cudd_Ref(prime);
     1498//        Cudd_RecursiveDeref(manager, implicant);
     1499
     1500//        DdNode * h = Cudd_bddAnd(manager, g, Cudd_Not(prime));
     1501//        if (LLVM_UNLIKELY(h == nullptr)) {
     1502//            Cudd_RecursiveDeref(manager, g);
     1503//            Cudd_RecursiveDeref(manager, prime);
     1504//            std::cerr << "Cudd_bddAnd" << std::endl;
     1505//            return nullptr;
     1506//        }
     1507//        Cudd_Ref(h);
     1508//        Cudd_RecursiveDeref(manager, g);
     1509
     1510//        g = h;
     1511//        if (LLVM_UNLIKELY(Cudd_BddToCubeArray(manager, prime, cube) == 0)) {
     1512//            Cudd_RecursiveDeref(manager, g);
     1513//            Cudd_RecursiveDeref(manager, prime);
     1514//            std::cerr << "Cudd_BddToCubeArray" << std::endl;
     1515//            return nullptr;
     1516//        }
     1517//        Cudd_RecursiveDeref(manager, prime);
     1518
     1519//        for (auto i = 0; i != manager->size; ++i) {
     1520//            if (cube[i] == 0) {
     1521//                DQ.push(variables[i]);
     1522//            } else if (cube[i] == 1) {
     1523//                CQ.push(variables[i]);
     1524//            }
     1525//        }
     1526
     1527//        if (DQ.size() > 0) {
     1528//            while (DQ.size() > 1) {
     1529//                PabloAST * v1 = DQ.front(); DQ.pop();
     1530//                PabloAST * v2 = DQ.front(); DQ.pop();
     1531//                DQ.push(builder.createOr(v1, v2));
     1532//            }
     1533//            CQ.push(builder.createNot(DQ.front())); DQ.pop();
     1534//        }
     1535
     1536//        while (CQ.size() > 1) {
     1537//            PabloAST * v1 = CQ.front(); CQ.pop();
     1538//            PabloAST * v2 = CQ.front(); CQ.pop();
     1539//            CQ.push(builder.createAnd(v1, v2));
     1540//        }
     1541
     1542//        SQ.push(CQ.front()); CQ.pop();
     1543//    }
     1544//    Cudd_RecursiveDeref(manager, g);
     1545
     1546//    while (SQ.size() > 1) {
     1547//        PabloAST * v1 = SQ.front(); SQ.pop();
     1548//        PabloAST * v2 = SQ.front(); SQ.pop();
     1549//        SQ.push(builder.createOr(v1, v2));
     1550//    }
     1551
     1552//    return SQ.front();
     1553//}
     1554
     1555///** ------------------------------------------------------------------------------------------------------------- *
     1556// * @brief minimize
     1557// ** ------------------------------------------------------------------------------------------------------------- */
     1558//PabloAST * minimize(DdManager * const manager, DdNode * const f, const std::vector<PabloAST *> & variables, PabloBuilder & builder) {
     1559//     DdNode * g = Cudd_FindEssential(manager, f);
     1560//    if (f == g || g == nullptr || Cudd_SupportSize(manager, g) == 0) {
     1561////        g = Cudd_SubsetCompress(manager, f, Cudd_SupportSize(manager, f), Cudd_DagSize(f));
     1562////        if (f == g || g == nullptr) {
     1563//            return minimizeCoFactor(manager, f, variables, builder);
     1564////        }
     1565//    }
     1566//    Cudd_Ref(g);
     1567//    PabloAST * essentialAST = minimize(manager, g, variables, builder);
     1568//    if (LLVM_UNLIKELY(essentialAST == nullptr)) {
     1569//        Cudd_RecursiveDeref(manager, g);
     1570//        return nullptr;
     1571//    }
     1572//    DdNode * h = Cudd_Cofactor(manager, f, g);
     1573//    Cudd_Ref(h);
     1574//    Cudd_RecursiveDeref(manager, g);
     1575//    PabloAST * cofactorAST = minimize(manager, h, variables, builder);
     1576//    Cudd_RecursiveDeref(manager, h);
     1577//    if (LLVM_UNLIKELY(cofactorAST == nullptr)) {
     1578//        if (LLVM_LIKELY(isa<Statement>(essentialAST))) {
     1579//            cast<Statement>(essentialAST)->eraseFromParent(true);
     1580//        }
     1581//        return nullptr;
     1582//    }
     1583//    return builder.createAnd(essentialAST, cofactorAST);
     1584//}
     1585
     1586///** ------------------------------------------------------------------------------------------------------------- *
     1587// * @brief reduce
     1588// ** ------------------------------------------------------------------------------------------------------------- */
     1589//void AutoMultiplexing::reduce(const std::vector<std::vector<PabloAST *>> & sets) const {
     1590
     1591//    for (const auto & set : sets) {
     1592
     1593//        // first do a BFS to build a topological ordering of statements we're going to end up visiting
     1594//        // and determine which of those will be terminals in the BDD
     1595//        using Graph = adjacency_list<hash_setS, vecS, bidirectionalS, PabloAST *>;
     1596//        using Vertex = Graph::vertex_descriptor;
     1597
     1598//        Graph G;
     1599//        std::unordered_map<PabloAST *, unsigned> M;
     1600
     1601//        std::queue<Statement *> Q;
     1602
     1603//        for (PabloAST * inst : set) {
     1604//            if (LLVM_LIKELY(isa<Advance>(inst))) {
     1605//                const auto u = add_vertex(inst, G);
     1606//                M.insert(std::make_pair(inst, u));
     1607
     1608//                for (PabloAST * user : inst->users()) {
     1609//                    auto f = M.find(user);
     1610//                    Vertex v = 0;
     1611//                    if (f == M.end()) {
     1612//                        v = add_vertex(user, G);
     1613//                        M.insert(std::make_pair(user, v));
     1614//                        if (isBinaryOp(user)) {
     1615//                            Q.push(cast<Statement>(user));
     1616//                        }
     1617//                    } else { // if (f != M.end()) {
     1618//                        v = f->second;
     1619//                    }
     1620//                    add_edge(u, v, G);
     1621//                }
     1622
     1623//            }
     1624//        }
     1625
     1626//        while (!Q.empty()) {
     1627//            Statement * const var = Q.front(); Q.pop();
     1628//            const Vertex u = M[var];
     1629
     1630//            for (unsigned i = 0; i != var->getNumOperands(); ++i) {
     1631//                PabloAST * operand = var->getOperand(i);
     1632//                auto f = M.find(operand);
     1633//                Vertex v;
     1634//                if (LLVM_UNLIKELY(f == M.end())) {
     1635//                    v = add_vertex(operand, G);
     1636//                    M.insert(std::make_pair(operand, v));
     1637//                } else { // if (f != M.end()) {
     1638//                    v = f->second;
     1639//                }
     1640//                add_edge(v, u, G);
     1641//            }
     1642
     1643//            for (PabloAST * user : var->users()) {
     1644//                auto f = M.find(user);
     1645//                Vertex v = 0;
     1646//                if (LLVM_LIKELY(f == M.end())) {
     1647//                    v = add_vertex(user, G);
     1648//                    M.insert(std::make_pair(user, v));
     1649//                    if (isBinaryOp(user)) {
     1650//                        Q.push(cast<Statement>(user));
     1651//                    }
     1652//                } else { // if (f != M.end()) {
     1653//                    v = f->second;
     1654//                }
     1655//                add_edge(u, v, G);
     1656//            }
     1657//        }
     1658
     1659//        // count the number of sinks (sources) so we know how many variables (terminals) will exist in the BDD
     1660//        std::vector<Vertex> variable;
     1661//        flat_set<Vertex> terminal;
     1662//        for (auto u : make_iterator_range(vertices(G))) {
     1663//            if (in_degree(u, G) == 0) {
     1664//                variable.push_back(u);
     1665//            }
     1666//            if (out_degree(u, G) == 0) {
     1667//                // the inputs to the sinks become the terminals in the BDD
     1668//                for (auto e : make_iterator_range(in_edges(u, G))) {
     1669//                    terminal.insert(source(e, G));
     1670//                }
     1671//            }
     1672//        }
     1673
     1674//        DdManager * manager = Cudd_Init(variable.size(), 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0);
     1675//        Cudd_AutodynEnable(manager, CUDD_REORDER_SIFT);
     1676
     1677//        std::vector<DdNode *> characterization(num_vertices(G), nullptr);
     1678//        unsigned i = 0;
     1679//        for (auto u : variable) {
     1680//            characterization[u] = Cudd_bddIthVar(manager, i++);
     1681//        }
     1682
     1683//        std::vector<Vertex> ordering;
     1684//        ordering.reserve(num_vertices(G));
     1685//        topological_sort(G, std::back_inserter(ordering));
     1686
     1687//        for (auto ui = ordering.rbegin(); ui != ordering.rend(); ++ui) {
     1688
     1689//            const Vertex u = *ui;
     1690
     1691//            if (characterization[u]) {
     1692//                continue;
     1693//            }
     1694
     1695//            std::array<DdNode *, 3> input;
     1696
     1697//            unsigned i = 0;
     1698//            for (const auto e : make_iterator_range(in_edges(u, G))) {
     1699//                input[i++] = characterization[source(e, G)];
     1700
     1701//            }
     1702
     1703//            assert (is<Statement>(G[u]) ? i == cast<Statement>(G[u])->getNumOperands() : i == 0);
     1704
     1705//            DdNode * bdd = nullptr;
     1706//            bool characterized = true;
     1707//            switch (G[u]->getClassTypeId()) {
     1708//                case PabloAST::ClassTypeId::And:
     1709//                    bdd = Cudd_bddAnd(manager, input[0], input[1]);
     1710//                    break;
     1711//                case PabloAST::ClassTypeId::Or:
     1712//                    bdd = Cudd_bddOr(manager, input[0], input[1]);
     1713//                    break;
     1714//                case PabloAST::ClassTypeId::Not:
     1715//                    bdd = Cudd_Not(input[0]);
     1716//                    break;
     1717//                case PabloAST::ClassTypeId::Xor:
     1718//                    bdd = Cudd_bddXor(manager, input[0], input[1]);
     1719//                    break;
     1720//                case PabloAST::ClassTypeId::Sel:
     1721//                    bdd = Cudd_bddIte(manager, input[0], input[1], input[2]);
     1722//                    break;
     1723//                default: characterized = false; break;
     1724//            }
     1725
     1726//            if (characterized) {
     1727//                Cudd_Ref(bdd);
     1728//                characterization[u] = bdd;
     1729//            }
     1730//        }
     1731
     1732//        Cudd_AutodynDisable(manager);
     1733//        Cudd_ReduceHeap(manager, CUDD_REORDER_SIFT, 0);
     1734
     1735//        std::vector<PabloAST *> inputs;
     1736//        for (Vertex s : variable) {
     1737//            inputs.push_back(G[s]);
     1738//        }
     1739
     1740//        for (Vertex t : terminal) {
     1741//            Statement * const stmt = cast<Statement>(G[t]);
     1742//            PabloBlock * const block = stmt->getParent();
     1743//            block->setInsertPoint(stmt);
     1744//            PabloBuilder builder(*block);
     1745//            DdNode * const f = characterization[t];
     1746//            llvm::raw_os_ostream out(std::cerr);
     1747//            PabloPrinter::print(stmt, " > ", out); out << '\n'; out.flush();
     1748
     1749//            Cudd_Ref(f);
     1750//            PabloAST * expr = minimize(manager, f, inputs, builder);
     1751//            if (LLVM_LIKELY(expr != nullptr)) {
     1752//                stmt->replaceWith(expr);
     1753//            } else {
     1754//                llvm::raw_os_ostream out(std::cerr);
     1755//                PabloPrinter::print(stmt, "Failed to minimize: ", out); out << '\n'; out.flush();
     1756//            }
     1757//            Cudd_RecursiveDeref(manager, f);
     1758//        }
     1759//        Cudd_Quit(manager);
     1760//    }
     1761//}
    12791762
    12801763/** ------------------------------------------------------------------------------------------------------------- *
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.hpp

    r4702 r4711  
    4848    void selectMultiplexSets(RNG &);
    4949    void applySubsetConstraints();
    50     std::vector<std::vector<PabloAST *>> multiplexSelectedIndependentSets() const;
    51     void reduce(const std::vector<std::vector<PabloAST *>> & sets) const;
     50    void multiplexSelectedIndependentSets() const;
     51    void simplifyAST(Advance * const muxed[], const unsigned m, PabloBuilder & builder) const;
     52    std::pair<PabloAST *, unsigned> simplifyAST(DdManager * manager, DdNode * const f, PabloAST * const variables[], PabloBuilder & builder) const;
     53    std::pair<PabloAST *, unsigned> makeCoverAST(DdManager * manager, DdNode * const f, PabloAST * const variables[], PabloBuilder & builder) const;
    5254    void topologicalSort(PabloBlock & entry) const;
    5355    inline AutoMultiplexing()
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_bddminimization.cpp

    r4701 r4711  
    66#include <pablo/printer_pablos.h>
    77#include <cudd.h>
     8#include <cuddInt.h>
    89#include <util.h>
    9 #include <mtr.h>
     10#include <queue>
     11#include <boost/circular_buffer.hpp>
     12#include <pablo/optimizers/pablo_simplifier.hpp>
    1013
    1114using namespace llvm;
     15using namespace boost;
    1216
    1317namespace pablo {
    1418
    1519bool 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
    1627    BDDMinimizationPass am;
    1728    am.initialize(function);
     
    1930    am.simplifyAST(function);
    2031    am.shutdown();
    21     return true;
     32
     33    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 ** ------------------------------------------------------------------------------------------------------------- */
     43void 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    }
    2286}
    2387
     
    37101    for (const Statement * stmt = function.getEntryBlock().front(); ; ) {
    38102        while ( stmt ) {
    39 
    40103            if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
    41104                // Set the next statement to be the first statement of the inner scope and push the
    42105                // next statement of the current statement into the scope stack.
    43106                const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
    44                 variableCount += isa<If>(stmt) ? cast<If>(stmt)->getDefined().size() : cast<While>(stmt)->getVariants().size();
    45107                scope.push(stmt->getNextNode());
    46108                stmt = nested.front();
     
    49111            }
    50112            switch (stmt->getClassTypeId()) {
     113                case PabloAST::ClassTypeId::Assign:
     114                case PabloAST::ClassTypeId::Next:
    51115                case PabloAST::ClassTypeId::Advance:
    52116                case PabloAST::ClassTypeId::Call:
     
    68132
    69133    // Initialize the BDD engine ...
    70     unsigned maxVariableCount = variableCount + function.getNumOfParameters();
    71     mManager = Cudd_Init(maxVariableCount, 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0);
     134    mManager = Cudd_Init(variableCount + function.getNumOfParameters() - function.getNumOfResults(), 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0);
    72135    Cudd_MakeTreeNode(mManager, 0, function.getNumOfParameters(), MTR_DEFAULT);
    73136    // Map the predefined 0/1 entries
     
    76139    // Order the variables so the input Vars are pushed to the end; they ought to
    77140    // be the most complex to resolve.   
    78     mVariables = 0;
    79141    for (auto i = 0; i != function.getNumOfParameters(); ++i) {
    80         mCharacterizationMap[function.getParameter(i)] = NewVar();
     142        mCharacterizationMap[function.getParameter(i)] = NewVar(function.getParameter(i));
    81143    }
    82144}
     
    109171    while (stmt) {
    110172        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
    111179            characterizeAndEliminateLogicallyEquivalentStatements(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(), subsitutionMap);
    112             // The defined vars of If statements and variants of While statements are unique in the AST in that
    113             // they are the only way a value can escape its local block. When we simplify this code later, we
    114             // do not want to recompute whatever was found within a nested block so instead they are marked as
    115             // new variables.
    116             if (isa<If>(stmt)) {
    117                 for (const Assign * defVar : cast<const If>(stmt)->getDefined()) {
    118                     mCharacterizationMap[defVar] = NewVar();
    119                 }
    120             } else { // if (isa<While>(stmt)) {
    121                 for (const Next * variant : cast<const While>(stmt)->getVariants()) {
    122                     mCharacterizationMap[variant] = NewVar();
    123                 }
    124             }
     180
     181            for (auto promotion : mPromotions) {
     182                mCharacterizationMap[promotion] = NewVar(promotion);
     183            }
     184            mPromotions.clear();
     185
    125186        } else { // attempt to characterize this statement and replace it if
    126187            DdNode * bdd = characterizeAndEliminateLogicallyEquivalentStatements(stmt);
     
    167228        case PabloAST::ClassTypeId::Assign:
    168229        case PabloAST::ClassTypeId::Next:
     230            mPromotions.push_back(stmt);
    169231            return input[0];
    170232        case PabloAST::ClassTypeId::And:
     
    188250        case PabloAST::ClassTypeId::MatchStar:
    189251        case PabloAST::ClassTypeId::ScanThru:
    190             return NewVar();
     252            return NewVar(stmt);
    191253        default:
    192254            throw std::runtime_error("Unexpected statement type " + stmt->getName()->to_string());
     
    207269 ** ------------------------------------------------------------------------------------------------------------- */
    208270inline void BDDMinimizationPass::simplifyAST(PabloFunction & function) {
    209     simplifyAST(function.getEntryBlock());
     271    PabloBuilder builder(function.getEntryBlock());
     272    simplifyAST(builder);
    210273}
    211274
     
    213276 * @brief simplifyAST
    214277 ** ------------------------------------------------------------------------------------------------------------- */
    215 void BDDMinimizationPass::simplifyAST(PabloBlock & block) {
     278void BDDMinimizationPass::simplifyAST(PabloBuilder & block) {
    216279    for (Statement * stmt : block) {
    217280        switch (stmt->getClassTypeId()) {
    218281            case PabloAST::ClassTypeId::If:
    219             case PabloAST::ClassTypeId::While:
    220                 simplifyAST(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
     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                    }
     295                }
    221296                break;
    222297            case PabloAST::ClassTypeId::ScanThru:
    223298            case PabloAST::ClassTypeId::MatchStar:
    224                 simplifyAST(stmt->getOperand(1), block, stmt->getPrevNode());
     299                simplifyAST(stmt, dyn_cast<Statement>(stmt->getOperand(1)), block);
    225300            case PabloAST::ClassTypeId::Advance:
    226301            case PabloAST::ClassTypeId::Assign:
    227302            case PabloAST::ClassTypeId::Next:
    228                 simplifyAST(stmt->getOperand(0), block, stmt->getPrevNode());
    229             default: break;
    230         }
     303                simplifyAST(stmt, dyn_cast<Statement>(stmt->getOperand(0)), block);
     304            default: block.record(stmt);
     305        }       
    231306    }
    232307}
     
    235310 * @brief simplifyAST
    236311 ** ------------------------------------------------------------------------------------------------------------- */
    237 inline void BDDMinimizationPass::simplifyAST(PabloAST * const expr, PabloBlock & block, Statement * const insertionPoint) {
    238 
    239     DdNode * bdd = mCharacterizationMap[expr];
    240 
    241     llvm::raw_os_ostream out(std::cerr);
    242     PabloPrinter::print(expr, out); out << " : " << Cudd_SupportSize(mManager, bdd) << '\n';
    243     out.flush();
    244 
    245     Cudd_bddPrintCover(mManager, bdd, bdd);
    246 
    247 //    // TODO: look into 0/1/x dominators?
    248 //    CUDD_VALUE_TYPE value;
    249 //    int * cube = nullptr;
    250 
    251 //    char output[3] = { '0', '1', '.' };
    252 
    253 //    DdGen * gen = Cudd_FirstCube(mManager, bdd, &cube, &value);
    254 //    while (!Cudd_IsGenEmpty(gen)) {
    255 //        // cube[0 ... n - 1] = { 0 : false, 1: true, 2: don't care }
    256 //        for (unsigned i = 0; i != mVariables; ++i) {
    257 //            out << output[cube[i]];
    258 //        }
    259 //        out << '\n';
    260 //        Cudd_NextCube(gen, &cube, &value);
    261 //    }
    262 //    Cudd_GenFree(gen);
    263 
    264 //    out.flush();
    265 
    266     block.setInsertPoint(insertionPoint);
    267 
    268 //    DdNode * zdd = Cudd_zddPortFromBdd(mManager, bdd);
    269 //    Cudd_zddPrintCover(mManager, zdd);
    270 //    Cudd_RecursiveDerefZdd(mManager, zdd);
     312void 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 ** ------------------------------------------------------------------------------------------------------------- */
     330PabloAST * BDDMinimizationPass::simplifyAST(DdNode * const f, PabloBuilder & builder) {
     331    DdNode * g = Cudd_FindEssential(mManager, f);
     332    if (g && Cudd_SupportSize(mManager, g) > 0) {
     333        if (g == f) { // every variable is essential
     334            return makeCoverAST(f, builder);
     335        }
     336        Cudd_Ref(g);
     337        PabloAST * c0 = makeCoverAST(g, builder);
     338        if (LLVM_UNLIKELY(c0 == nullptr)) {
     339            Cudd_RecursiveDeref(mManager, g);
     340            return nullptr;
     341        }
     342        DdNode * h = Cudd_Cofactor(mManager, f, g);
     343        Cudd_Ref(h);
     344        Cudd_RecursiveDeref(mManager, g);
     345        PabloAST * c1 = simplifyAST(h, builder);
     346        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    }
     355    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]);
     362        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);
     369        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);
     379}
     380
     381/** ------------------------------------------------------------------------------------------------------------- *
     382 * @brief makeCoverAST
     383 ** ------------------------------------------------------------------------------------------------------------- */
     384PabloAST * BDDMinimizationPass::makeCoverAST(DdNode * const f, PabloBuilder & builder) {
     385
     386    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];
     395
     396    DdNode * g = f;
     397
     398    Cudd_Ref(g);
     399
     400    while (g != Cudd_ReadLogicZero(mManager)) {
     401        int length;
     402        DdNode * implicant = Cudd_LargestCube(mManager, g, &length);
     403        if (LLVM_UNLIKELY(implicant == nullptr)) {
     404            Cudd_RecursiveDeref(mManager, g);
     405            return nullptr;
     406        }
     407        Cudd_Ref(implicant);
     408        DdNode * prime = Cudd_bddMakePrime(mManager, implicant, f);
     409        if (LLVM_UNLIKELY(prime == nullptr)) {
     410            Cudd_RecursiveDeref(mManager, g);
     411            Cudd_RecursiveDeref(mManager, implicant);
     412            return nullptr;
     413        }
     414        Cudd_Ref(prime);
     415        Cudd_RecursiveDeref(mManager, implicant);
     416
     417        DdNode * h = Cudd_bddAnd(mManager, g, Cudd_Not(prime));
     418        if (LLVM_UNLIKELY(h == nullptr)) {
     419            Cudd_RecursiveDeref(mManager, g);
     420            Cudd_RecursiveDeref(mManager, prime);
     421            return nullptr;
     422        }
     423        Cudd_Ref(h);
     424        Cudd_RecursiveDeref(mManager, g);
     425
     426        g = h;
     427        if (LLVM_UNLIKELY(Cudd_BddToCubeArray(mManager, prime, cube) == 0)) {
     428            Cudd_RecursiveDeref(mManager, g);
     429            Cudd_RecursiveDeref(mManager, prime);
     430            return nullptr;
     431        }
     432        Cudd_RecursiveDeref(mManager, prime);
     433
     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)));
     496    }
     497    Cudd_RecursiveDeref(mManager, g);
     498
     499    while (SQ.size() > 1) {
     500        PabloAST * v1 = SQ.front(); SQ.pop();
     501        PabloAST * v2 = SQ.front(); SQ.pop();
     502        SQ.push(builder.createOr(v1, v2));
     503    }
     504
     505    return SQ.front();
    271506}
    272507
     
    283518}
    284519
    285 inline DdNode * BDDMinimizationPass::NewVar() {
    286     return Cudd_bddIthVar(mManager, mVariables++);
     520inline DdNode * BDDMinimizationPass::NewVar(const PabloAST * expr) {
     521    DdNode * var = Cudd_bddIthVar(mManager, mVariables.size());
     522    mVariables.push_back(const_cast<PabloAST *>(expr));
     523    return var;
    287524}
    288525
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_bddminimization.h

    r4701 r4711  
    1212class PabloBlock;
    1313class PabloFunction;
     14class PabloBuilder;
    1415class Statement;
    1516
     
    4142    static bool optimize(PabloFunction & function);
    4243protected:
     44    static void promoteCrossBlockReachingDefs(const PabloFunction & function);
    4345    void initialize(const PabloFunction & function);
    4446    void characterizeAndEliminateLogicallyEquivalentStatements(PabloFunction & function);
     
    4648    DdNode * characterizeAndEliminateLogicallyEquivalentStatements(const Statement * const stmt);
    4749    void simplifyAST(PabloFunction & function);
    48     void simplifyAST(PabloBlock & block);
    49     void simplifyAST(PabloAST * const value, PabloBlock & block, Statement * const insertionPoint);
    50 
     50    void simplifyAST(PabloBuilder & block);
     51    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);
    5154private:
    5255    DdNode * Zero() const;
     
    5962    DdNode * Not(DdNode * x) const;
    6063    DdNode * Ite(DdNode * const x, DdNode * const y, DdNode * const z);
    61     DdNode * NewVar();
     64    DdNode * NewVar(const PabloAST * expr);
    6265    bool noSatisfyingAssignment(DdNode * const x);
    6366    void shutdown();
    6467private:
    65     DdManager *             mManager;
    66     unsigned                mVariables;
    67     CharacterizationMap     mCharacterizationMap;
     68    DdManager *                     mManager;
     69    std::vector<PabloAST *>         mVariables;
     70    std::vector<const Statement *>  mPromotions;
     71    CharacterizationMap             mCharacterizationMap;
    6872};
    6973
  • icGREP/icgrep-devel/icgrep/pablo/pabloAST.cpp

    r4657 r4711  
    8989    Vector::size_type users = 0;
    9090    for (PabloAST * u : mUsers) {
    91         if (isa<Statement>(u)) {
     91        if (isa<Statement>(u) && u != expr) {
    9292            user[users++] = cast<Statement>(u);
    9393        }
  • icGREP/icgrep-devel/icgrep/pablo/pabloAST.h

    r4699 r4711  
    4040
    4141    enum class ClassTypeId : unsigned {
     42        /** Non-statements **/
    4243        // Constants
    4344        Zeroes
    4445        , Ones
     46        // Internal types
     47        , Var
     48        , Integer
     49        , String
     50        , Block
     51        , Function
     52        , Prototype
     53        /** Statements **/
    4554        // Boolean operations
    4655        , And
     
    5766        , Next
    5867        , Call
    59         , Var
    6068        , SetIthBit
    6169        // Scope blocks
    6270        , If
    6371        , While
    64         , Block
    65         , Function
    66         // Internal variables
    67         , Integer
    68         , String
    69         , Prototype
    7072    };
    7173    inline ClassTypeId getClassTypeId() const {
     
    157159    static inline bool classof(const PabloAST * e) {
    158160        switch (e->getClassTypeId()) {
    159             case PabloAST::ClassTypeId::String:
    160             case PabloAST::ClassTypeId::Integer:
    161161            case PabloAST::ClassTypeId::Zeroes:
    162162            case PabloAST::ClassTypeId::Ones:
    163163            case PabloAST::ClassTypeId::Var:
     164            case PabloAST::ClassTypeId::String:
     165            case PabloAST::ClassTypeId::Integer:
     166            case PabloAST::ClassTypeId::Block:
     167            case PabloAST::ClassTypeId::Function:
     168            case PabloAST::ClassTypeId::Prototype:
    164169                return false;
    165170            default:
Note: See TracChangeset for help on using the changeset viewer.