Changeset 4722 for icGREP


Ignore:
Timestamp:
Aug 10, 2015, 3:30:31 PM (4 years ago)
Author:
nmedfort
Message:

Misc. changes and start of dependency chain analysis in ucd generator.

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

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/compiler.cpp

    r4684 r4722  
    2222#include <pablo/optimizers/pablo_automultiplexing.hpp>
    2323#endif
    24 #include <llvm/Support/CommandLine.h>
    2524#include <pablo/function.h>
    2625#include <re/printer_re.h>
    2726#include <pablo/printer_pablos.h>
    2827#include <iostream>
     28#include <llvm/Support/CommandLine.h>
    2929
    3030static cl::OptionCategory cRegexOutputOptions("Regex Dump Options",
     
    4444static cl::opt<bool> PrintOptimizedREcode("print-pablo", cl::init(false), cl::desc("print final optimized Pablo code"), cl::cat(dPabloDumpOptions));
    4545
    46 
    47 static cl::OptionCategory cPabloOptimizationsOptions("Pablo Optimizations",
    48                                               "These options control Pablo optimization passes.");
     46static cl::OptionCategory cPabloOptimizationsOptions("Pablo Optimizations", "These options control Pablo optimization passes.");
    4947
    5048static cl::opt<bool> DisablePabloCSE("disable-CSE", cl::init(false),
     
    5452                                      cl::desc("Moves all instructions into the innermost legal If-scope so that they are only executed when needed."),
    5553                                      cl::cat(cPabloOptimizationsOptions));
     54
    5655#ifdef ENABLE_MULTIPLEXING
    57 static cl::opt<bool> EnableMultiplexing("enable-multiplexing", cl::init(false),
    58                                       cl::desc("combine Advances whose inputs are mutual exclusive into the fewest number of advances possible (expensive)."),
    59                                       cl::cat(cPabloOptimizationsOptions));
     56static cl::opt<bool> EnableMultiplexing("multiplexing", cl::init(false),
     57    cl::desc("combine Advances whose inputs are mutual exclusive into the fewest number of advances possible (expensive)."),
     58    cl::cat(cPabloOptimizationsOptions));
    6059#endif
    6160
  • icGREP/icgrep-devel/icgrep/generate_predefined_ucd_functions.cpp

    r4692 r4722  
    3838#include <llvm/Analysis/DependenceAnalysis.h>
    3939
     40#include <queue>
     41#include <unordered_map>
     42
    4043using namespace pablo;
    4144using namespace UCD;
     
    4952UCDSourcePath("dir", cl::desc("UCD source code directory"), cl::value_desc("directory"), cl::Required);
    5053
    51 static cl::opt<bool> PrintDependenceAnalysis("print-da", cl::init(false), cl::desc("print Dependence Analysis."));
     54static cl::opt<bool> PrintDependenceAnalysis("pablo-ldc", cl::init(false), cl::desc("print Pablo longest dependency chain metrics."));
    5255
    5356
    5457#ifdef ENABLE_MULTIPLEXING
    5558static cl::opt<bool> EnableMultiplexing("multiplexing", cl::init(false),
    56                                         cl::desc("combine Advances whose inputs are mutual exclusive into the fewest number of advances possible (expensive)."));
     59    cl::desc("combine Advances whose inputs are mutual exclusive into the fewest number of advances possible (expensive)."));
    5760
    5861static cl::opt<std::string>
    59 MultiplexingDistribution("multiplexing-dist", cl::desc("Generate a CSV containing the # of Advances found in each UCD function before and after applying multiplexing."), cl::value_desc("filename"));
     62MultiplexingDistribution("multiplexing-dist",
     63    cl::desc("Generate a CSV containing the # of Advances found in each UCD function before and after applying multiplexing."), cl::value_desc("filename"));
    6064
    6165static raw_fd_ostream * MultiplexingDistributionFile = nullptr;
     
    7882    }
    7983    return advances;
     84}
     85
     86/** ------------------------------------------------------------------------------------------------------------- *
     87 * @brief computePabloDependencyMetrics
     88 ** ------------------------------------------------------------------------------------------------------------- */
     89void computePabloDependencyChainMetrics(const PabloFunction & f) {
     90
     91    std::queue<const PabloAST *> Q;
     92    std::unordered_map<const PabloAST *, unsigned> V;
     93
     94    for (unsigned i = 0; i != f.getNumOfResults(); ++i) {
     95        V.insert(std::make_pair(f.getResult(i), 0));
     96        const PabloAST * expr = f.getResult(i)->getExpression();
     97        if (expr->getNumUses() == 1 && V.count(expr) == 0) {
     98            V.insert(std::make_pair(expr, 1));
     99            if (LLVM_LIKELY(isa<Statement>(expr))) {
     100                Q.push(cast<Statement>(expr));
     101            }
     102        }
     103    }
     104
     105    while (!Q.empty()) {
     106        const PabloAST * expr = Q.front(); Q.pop();
     107        unsigned lpl = 0; // longest path length
     108        for (const PabloAST * user : expr->users()) {
     109            lpl = std::max<unsigned>(lpl, V[user]);
     110        }
     111        V.insert(std::make_pair(expr, lpl + 1));
     112        if (const Statement * stmt = dyn_cast<Statement>(expr)) {
     113            for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
     114                assert (V.count(stmt->getOperand(i)) == 0);
     115                bool everyUserOfThisOperandWasProcessed = true;
     116                for (const PabloAST * user : stmt->getOperand(i)->users()) {
     117                    if (V.count(user) == 0) {
     118                        everyUserOfThisOperandWasProcessed = false;
     119                        break;
     120                    }
     121                }
     122                if (everyUserOfThisOperandWasProcessed) {
     123                    Q.push(stmt->getOperand(i));
     124                }
     125            }
     126        }
     127    }
     128
     129    unsigned lpl = 0;
     130    for (unsigned i = 0; i != f.getNumOfParameters(); ++i) {
     131        assert (V.count(f.getParameter(i)));
     132        lpl = std::max<unsigned>(lpl, V[f.getParameter(i)]);
     133    }
     134
     135
     136
     137}
     138
     139/** ------------------------------------------------------------------------------------------------------------- *
     140 * @brief computeLLVMDependencyMetrics
     141 ** ------------------------------------------------------------------------------------------------------------- */
     142void computeLLVMDependencyChainMetrics(const llvm::Function & f) {
     143
     144
     145
    80146}
    81147
     
    195261}
    196262
    197 
    198263/** ------------------------------------------------------------------------------------------------------------- *
    199264 * @brief generateUCDModule
  • icGREP/icgrep-devel/icgrep/pablo/builder.cpp

    r4718 r4722  
    103103
    104104PabloAST * PabloBuilder::createAnd(PabloAST * expr1, PabloAST * expr2) {
     105    assert (expr1);
     106    assert (expr2);
    105107    if (isa<Not>(expr1) || expr1 > expr2) {
    106108        std::swap(expr1, expr2);
     
    111113
    112114PabloAST * PabloBuilder::createAnd(PabloAST * expr1, PabloAST * expr2, const std::string prefix) {
     115    assert (expr1);
     116    assert (expr2);
    113117    if (isa<Not>(expr1) || expr1 > expr2) {
    114118        std::swap(expr1, expr2);
     
    119123
    120124PabloAST * PabloBuilder::createOr(PabloAST * expr1, PabloAST * expr2) {
     125    assert (expr1);
     126    assert (expr2);
    121127    if (expr1 > expr2) {
    122128        std::swap(expr1, expr2);
     
    127133
    128134PabloAST * PabloBuilder::createOr(PabloAST * expr1, PabloAST * expr2, const std::string prefix) {
     135    assert (expr1);
     136    assert (expr2);
    129137    if (expr1 > expr2) {
    130138        std::swap(expr1, expr2);
     
    135143
    136144PabloAST * PabloBuilder::createXor(PabloAST * expr1, PabloAST * expr2) {
     145    assert (expr1);
     146    assert (expr2);
    137147    if (expr1 > expr2) {
    138148        std::swap(expr1, expr2);
     
    143153
    144154PabloAST * PabloBuilder::createXor(PabloAST * expr1, PabloAST * expr2, const std::string prefix) {
     155    assert (expr1);
     156    assert (expr2);
    145157    if (expr1 > expr2) {
    146158        std::swap(expr1, expr2);
  • icGREP/icgrep-devel/icgrep/pablo/carry_manager.cpp

    r4721 r4722  
    1313#include <pablo/pabloAST.h>
    1414#include <iostream>
    15 
     15#include <llvm/Support/CommandLine.h>
    1616
    1717static cl::opt<CarryManagerStrategy> Strategy(cl::desc("Choose carry management strategy:"),
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.cpp

    r4711 r4722  
    1616#include <queue>
    1717#include <unordered_set>
     18#include <pablo/optimizers/pablo_simplifier.hpp>
    1819
    1920using namespace llvm;
     
    2223using namespace boost::numeric::ublas;
    2324
    24 // #define PRINT_DEBUG_OUTPUT
     25#define PRINT_DEBUG_OUTPUT
    2526
    2627#if !defined(NDEBUG) && !defined(PRINT_DEBUG_OUTPUT)
     
    131132    const bool multiplex = am.generateCandidateSets(rng);
    132133    RECORD_TIMESTAMP(end_create_multiplex_graph);
    133     LOG("GenerateMultiplexSets:   " << (end_create_multiplex_graph - start_create_multiplex_graph));
     134    LOG("GenerateCandidateSets:   " << (end_create_multiplex_graph - start_create_multiplex_graph));
    134135
    135136    RECORD_TIMESTAMP(start_shutdown);
     
    153154        am.multiplexSelectedIndependentSets();
    154155        RECORD_TIMESTAMP(end_select_independent_sets);
    155         LOG("MultiplexSelectedSets:  " << (end_select_independent_sets - start_select_independent_sets));
     156        LOG("SelectedIndependentSets: " << (end_select_independent_sets - start_select_independent_sets));
    156157
    157158        RECORD_TIMESTAMP(start_topological_sort);
    158159        am.topologicalSort(function.getEntryBlock());
    159160        RECORD_TIMESTAMP(end_topological_sort);
    160         LOG("TopologicalSort:         " << (end_topological_sort - start_topological_sort));
     161        LOG("TopologicalSort (1):     " << (end_topological_sort - start_topological_sort));
     162
     163//        RECORD_TIMESTAMP(start_simplify_ast);
     164//        am.simplifyAST(function);
     165//        RECORD_TIMESTAMP(end_simplify_ast);
     166//        LOG("SimplifyAST:             " << (end_simplify_ast - start_simplify_ast));
     167
     168//        RECORD_TIMESTAMP(start_topological_sort2);
     169//        am.topologicalSort(function.getEntryBlock());
     170//        RECORD_TIMESTAMP(end_topological_sort2);
     171//        LOG("TopologicalSort (2):     " << (end_topological_sort2 - start_topological_sort2));
    161172    }
    162173
     
    368379
    369380        DdNode * var = characterize(stmt);
    370         mCharacterizationMap[stmt] = var;
    371         assert (Cudd_DebugCheck(mManager) == 0);
     381        mCharacterizationMap[stmt] = var;       
    372382    }
    373383}
     
    956966 * @brief multiplexSelectedIndependentSets
    957967 ** ------------------------------------------------------------------------------------------------------------- */
    958 void AutoMultiplexing::multiplexSelectedIndependentSets() const {
     968void AutoMultiplexing::multiplexSelectedIndependentSets() {
    959969
    960970    const unsigned f = num_vertices(mConstraintGraph);
     
    978988            const size_t m = log2_plus_one(n);
    979989            Advance * input[n];
    980             Advance * muxed[m];
     990            std::vector<PabloAST *> muxed(m);
    981991
    982992            graph_traits<MultiplexSetGraph>::out_edge_iterator ei, ei_end;
     
    10161026                PabloAST * mux = Q.front(); Q.pop_front(); assert (mux);
    10171027                // 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()));
     1028                // is zero. Since these cases would have been eliminated earlier, we are safe to cast here.               
     1029                muxed[j] = builder.createAdvance(mux, adv->getOperand(1), prefix.str());
    10201030            }
    10211031
     
    10601070            }
    10611071
    1062             /// Attempt to simplify the demultiplexed values
    1063             // simplifyAST(muxed, m, builder);
    1064         }
     1072            mMuxedVariables.push_back(std::move(muxed));
     1073        }       
    10651074    }
    10661075}
     
    10691078 * @brief simplifyAST
    10701079 ** ------------------------------------------------------------------------------------------------------------- */
    1071 void AutoMultiplexing::simplifyAST(Advance * const muxed[], const unsigned m, PabloBuilder & builder) const {
     1080void AutoMultiplexing::simplifyAST(const PabloFunction & function) {
    10721081
    10731082    // first do a BFS to build a topological ordering of statements we're going to end up visiting
     
    10761085    using Vertex = Graph::vertex_descriptor;
    10771086
    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;
    1099                 }
    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;
    1136                 }
    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 
    12211087    raw_os_ostream out(std::cerr);
    12221088
    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';
    1230         out.flush();
    1231 
    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);
     1089    PabloPrinter::print(function.getEntryBlock(), "", out);
     1090    out << "\n+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n\n";
     1091    out.flush();
     1092
     1093
     1094    // TODO: this should build a single graph and iterate by connected component instead.
     1095    for (const auto & muxed : mMuxedVariables) {
     1096
     1097        Graph G;
     1098        std::unordered_map<PabloAST *, unsigned> M;
     1099        std::queue<Statement *> Q;
     1100
     1101        for (unsigned i = 0; i != muxed.size(); ++i) {
     1102
     1103            const auto u = add_vertex(muxed[i], G);
     1104            M.insert(std::make_pair(muxed[i], u));
     1105            for (PabloAST * user : muxed[i]->users()) {
     1106                auto f = M.find(user);
     1107                Vertex v = 0;
     1108                if (f == M.end()) {
     1109                    v = add_vertex(user, G);
     1110                    M.insert(std::make_pair(user, v));
     1111                    switch (user->getClassTypeId()) {
     1112                        case PabloAST::ClassTypeId::And:
     1113                        case PabloAST::ClassTypeId::Or:
     1114                        case PabloAST::ClassTypeId::Not:
     1115                        case PabloAST::ClassTypeId::Sel:
     1116                            Q.push(cast<Statement>(user));
     1117                        default: break;
     1118                    }
     1119                } else { // if (f != M.end()) {
     1120                    v = f->second;
     1121                }
     1122                add_edge(u, v, G);
     1123            }
     1124        }
     1125
     1126        while (!Q.empty()) {
     1127            Statement * const var = Q.front(); Q.pop();
     1128            const Vertex u = M[var];
     1129            for (unsigned i = 0; i != var->getNumOperands(); ++i) {
     1130                PabloAST * operand = var->getOperand(i);
     1131                auto f = M.find(operand);
     1132                Vertex v = 0;
     1133                if (LLVM_UNLIKELY(f == M.end())) {
     1134                    v = add_vertex(operand, G);
     1135                    M.insert(std::make_pair(operand, v));
     1136                } else { // if (f != M.end()) {
     1137                    v = f->second;
     1138                }
     1139                add_edge(v, u, G);
     1140            }
     1141
     1142            for (PabloAST * user : var->users()) {
     1143                auto f = M.find(user);
     1144                Vertex v = 0;
     1145                if (LLVM_LIKELY(f == M.end())) {
     1146                    v = add_vertex(user, G);
     1147                    M.insert(std::make_pair(user, v));
     1148                    switch (user->getClassTypeId()) {
     1149                        case PabloAST::ClassTypeId::And:
     1150                        case PabloAST::ClassTypeId::Or:
     1151                        case PabloAST::ClassTypeId::Not:
     1152                        case PabloAST::ClassTypeId::Sel:
     1153                            Q.push(cast<Statement>(user));
     1154                        default: break;
     1155                    }
     1156                } else { // if (f != M.end()) {
     1157                    v = f->second;
     1158                }
     1159                add_edge(u, v, G);
     1160            }
     1161        }
     1162
     1163        // count the number of sources (sinks) so we know how many variables (terminals) will exist in the BDD
     1164        std::vector<Vertex> inputs;
     1165        flat_set<Vertex> terminals;
     1166        for (auto u : make_iterator_range(vertices(G))) {
     1167            if (in_degree(u, G) == 0) {
     1168                inputs.push_back(u);
     1169            }
     1170            if (out_degree(u, G) == 0) {
     1171                // the inputs to the sinks become the terminals in the BDD
     1172                for (auto e : make_iterator_range(in_edges(u, G))) {
     1173                    terminals.insert(source(e, G));
     1174                }
     1175            }
     1176        }
     1177
     1178        const auto n = inputs.size();
     1179
     1180        mManager = Cudd_Init(n, 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0);
     1181        Cudd_AutodynEnable(mManager, CUDD_REORDER_LAZY_SIFT);
     1182
     1183        std::vector<PabloAST *> nodes(n);
     1184        std::vector<DdNode *> characterization(num_vertices(G), nullptr);
     1185        for (unsigned i = 0; i != n; ++i) {
     1186            nodes[i] = G[inputs[i]];
     1187            assert (nodes[i]);
     1188            characterization[inputs[i]] = Cudd_bddIthVar(mManager, i);
     1189        }
     1190
     1191        std::vector<Vertex> ordering;
     1192        ordering.reserve(num_vertices(G));
     1193        topological_sort(G, std::back_inserter(ordering));
     1194
     1195        for (auto ui = ordering.rbegin(); ui != ordering.rend(); ++ui) {
     1196
     1197            const Vertex u = *ui;
     1198
     1199            if (characterization[u]) {
     1200                continue;
     1201            }
     1202
     1203            std::array<DdNode *, 3> input;
     1204
     1205            unsigned i = 0;
     1206            for (const auto e : make_iterator_range(in_edges(u, G))) {               
     1207                input[i] = characterization[source(e, G)];
     1208                if (input[i] == nullptr) {
     1209                    throw std::runtime_error("Uncharacterized input!");
     1210                }
     1211                ++i;
     1212            }
     1213
     1214            DdNode * bdd = nullptr;
     1215            bool characterized = true;
     1216            switch (G[u]->getClassTypeId()) {
     1217                case PabloAST::ClassTypeId::And:
     1218                    bdd = And(input[0], input[1]);
     1219                    break;
     1220                case PabloAST::ClassTypeId::Or:
     1221                    bdd = Or(input[0], input[1]);
     1222                    break;
     1223                case PabloAST::ClassTypeId::Not:
     1224                    bdd = Not(input[0]);
     1225                    break;
     1226                case PabloAST::ClassTypeId::Sel:
     1227                    bdd = Ite(input[0], input[1], input[2]);
     1228                    break;
     1229                default: characterized = false; break;
     1230            }
     1231
     1232            if (characterized) {
     1233                Ref(bdd);
     1234                characterization[u] = bdd;
     1235            }
     1236        }
     1237
     1238        Cudd_AutodynDisable(mManager);
     1239        assert (Cudd_DebugCheck(mManager) == 0);
     1240        Cudd_ReduceHeap(mManager, CUDD_REORDER_SIFT, 0);
     1241
     1242        mSimplifyDepth = 0;
     1243
     1244        assert (mManager->size == nodes.size());
     1245
     1246        for (Vertex t : terminals) {
     1247
     1248            PabloPrinter::print(cast<Statement>(G[t]), " >> ", out);
    12401249            out << '\n';
    12411250            out.flush();
    12421251
    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);
     1252            Statement * stmt = cast<Statement>(G[t]);
     1253
     1254            PabloBuilder builder(*(stmt->getParent()));
     1255
     1256            DdNode * const f = characterization[t];
     1257            Cudd_Ref(f);
     1258
     1259            PabloAST * expr = simplifyAST(f, nodes, builder);
     1260            if (expr) {
     1261
     1262                PabloPrinter::print(cast<Statement>(expr), "    replacement: ", out);
     1263                out << '\n';
     1264                out.flush();
     1265
     1266                stmt->replaceWith(expr, false, true);
     1267            }
     1268            Cudd_RecursiveDeref(mManager, f);
     1269        }
     1270
     1271        Cudd_Quit(mManager);
     1272
     1273    }
    12541274}
    12551275
     
    12571277 * @brief simplifyAST
    12581278 ** ------------------------------------------------------------------------------------------------------------- */
    1259 std::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) {
     1279PabloAST * AutoMultiplexing::simplifyAST(DdNode * const f, const std::vector<PabloAST *> & variables, PabloBuilder & builder) {
     1280    assert (!NoSatisfyingAssignment(f));
     1281    DdNode * g = Cudd_FindEssential(mManager, f);
     1282    if (g && Cudd_SupportSize(mManager, g) > 0) {
    12621283        if (g == f) { // every variable is essential
    1263             return makeCoverAST(manager, f, variables, builder);
     1284            return makeCoverAST(f, variables, builder);
    12641285        }
    12651286        Cudd_Ref(g);
    1266         PabloAST * c0;
    1267         unsigned count0;
    1268         std::tie(c0, count0) = makeCoverAST(manager, g, variables, builder);
     1287        PabloAST * c0 = makeCoverAST(g, variables, builder);
    12691288        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);
     1289            Cudd_RecursiveDeref(mManager, g);
     1290            return nullptr;
     1291        }
     1292        DdNode * h = Cudd_Cofactor(mManager, f, g);
    12741293        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);
     1294        Cudd_RecursiveDeref(mManager, g);
     1295        PabloAST * c1 = simplifyAST(h, variables, builder);
     1296        Cudd_RecursiveDeref(mManager, h);
    12801297        if (LLVM_UNLIKELY(c1 == nullptr)) {
    12811298            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;
     1299            return nullptr;
     1300        }
     1301        return builder.createAnd(c0, c1);
     1302    }
     1303
     1304    DdNode ** disjunct = nullptr;
     1305    int disjuncts = Cudd_bddIterDisjDecomp(mManager, f, &disjunct);
     1306    assert (disjuncts < 2 || Or(disjunct[0], disjunct[1]) == f);
     1307
     1308    DdNode ** conjunct = nullptr;
     1309    int conjuncts = Cudd_bddIterConjDecomp(mManager, f, &conjunct);
     1310    assert (conjuncts < 2 || And(conjunct[0], conjunct[1]) == f);
     1311
     1312    if (LLVM_LIKELY(disjuncts == 2 && conjuncts == 2)) {
     1313        if (Cudd_SharingSize(disjunct, 2) > Cudd_SharingSize(conjunct, 2)) {
     1314            disjuncts = 0;
     1315        }
     1316    }
    12911317
    12921318    DdNode ** decomp = nullptr;
    1293     const auto disjuncts = Cudd_bddGenDisjDecomp(manager, f, &decomp);
    1294     if (LLVM_LIKELY(disjuncts == 2)) {
     1319    if (disjuncts == 2) {
     1320        FREE(conjunct); conjunct = nullptr; decomp = disjunct;
     1321    } else if (conjuncts == 2) {
     1322        FREE(disjunct); disjunct = nullptr; decomp = conjunct;
     1323    }
     1324
     1325    if (decomp && (decomp[0] != decomp[1]) && (decomp[0] != f) && (decomp[1] != f)) {
    12951326        Cudd_Ref(decomp[0]);
    12961327        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]);
     1328        PabloAST * d0 = simplifyAST(decomp[0], variables, builder);
     1329        Cudd_RecursiveDeref(mManager, decomp[0]);
    13011330        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]);
     1331            Cudd_RecursiveDeref(mManager, decomp[1]);
     1332            return nullptr;
     1333        }
     1334
     1335        PabloAST * d1 = simplifyAST(decomp[1], variables, builder);
     1336        Cudd_RecursiveDeref(mManager, decomp[1]);
    13091337        FREE(decomp);
    13101338        if (LLVM_UNLIKELY(d1 == nullptr)) {
    13111339            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);
     1340            return nullptr;
     1341        }
     1342
     1343        std::cerr << "d0: " << (ptruint)(d0) << "  d1: " << (ptruint)(d1) << " disjunct: " << (disjunct != 0) << " conjunct: " << (conjunct != 0) << std::endl;
     1344
     1345        if (disjunct) {
     1346            return builder.createOr(d0, d1);
    13491347        } 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);
     1348            return builder.createAnd(d0, d1);
     1349        }
     1350    }
     1351    return makeCoverAST(f, variables, builder);
    13591352}
    13601353
     
    13621355 * @brief makeCoverAST
    13631356 ** ------------------------------------------------------------------------------------------------------------- */
    1364 std::pair<PabloAST *, unsigned> AutoMultiplexing::makeCoverAST(DdManager * manager, DdNode * const f, PabloAST * const variables[], PabloBuilder & builder) const {
     1357PabloAST * AutoMultiplexing::makeCoverAST(DdNode * const f, const std::vector<PabloAST *> & variables, PabloBuilder & builder) {
    13651358
    13661359    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;
     1360    const unsigned n = variables.size();
     1361    circular_buffer<PabloAST *> CQ(n);
     1362    circular_buffer<PabloAST *> DQ(n);
     1363
     1364    assert (mManager->size == variables.size());
     1365
     1366    int cube[n];
    13741367
    13751368    DdNode * g = f;
     
    13771370    Cudd_Ref(g);
    13781371
    1379     while (g != Cudd_ReadLogicZero(manager)) {
    1380         int length;
    1381         DdNode * implicant = Cudd_LargestCube(manager, g, &length);
     1372    while (g != Cudd_ReadLogicZero(mManager)) {
     1373        int length = 0;
     1374        DdNode * implicant = Cudd_LargestCube(mManager, g, &length);
    13821375        if (LLVM_UNLIKELY(implicant == nullptr)) {
    1383             Cudd_RecursiveDeref(manager, g);
    1384             return std::make_pair(nullptr, 0);
     1376            Cudd_RecursiveDeref(mManager, g);
     1377            return nullptr;
    13851378        }
    13861379        Cudd_Ref(implicant);
    1387         DdNode * prime = Cudd_bddMakePrime(manager, implicant, f);
     1380        DdNode * prime = Cudd_bddMakePrime(mManager, implicant, f);
    13881381        if (LLVM_UNLIKELY(prime == nullptr)) {
    1389             Cudd_RecursiveDeref(manager, g);
    1390             Cudd_RecursiveDeref(manager, implicant);
    1391             return std::make_pair(nullptr, 0);
     1382            Cudd_RecursiveDeref(mManager, g);
     1383            Cudd_RecursiveDeref(mManager, implicant);
     1384            return nullptr;
    13921385        }
    13931386        Cudd_Ref(prime);
    1394         Cudd_RecursiveDeref(manager, implicant);
    1395 
    1396         DdNode * h = Cudd_bddAnd(manager, g, Cudd_Not(prime));
     1387        Cudd_RecursiveDeref(mManager, implicant);
     1388
     1389        DdNode * h = Cudd_bddAnd(mManager, g, Cudd_Not(prime));
    13971390        if (LLVM_UNLIKELY(h == nullptr)) {
    1398             Cudd_RecursiveDeref(manager, g);
    1399             Cudd_RecursiveDeref(manager, prime);
    1400             return std::make_pair(nullptr, 0);
     1391            Cudd_RecursiveDeref(mManager, g);
     1392            Cudd_RecursiveDeref(mManager, prime);
     1393            return nullptr;
    14011394        }
    14021395        Cudd_Ref(h);
    1403         Cudd_RecursiveDeref(manager, g);
     1396        Cudd_RecursiveDeref(mManager, g);
    14041397
    14051398        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) {
     1399        if (LLVM_UNLIKELY(Cudd_BddToCubeArray(mManager, prime, cube) == 0)) {
     1400            Cudd_RecursiveDeref(mManager, g);
     1401            Cudd_RecursiveDeref(mManager, prime);
     1402            return nullptr;
     1403        }
     1404        Cudd_RecursiveDeref(mManager, prime);
     1405
     1406        assert (DQ.empty() && CQ.empty());
     1407
     1408        for (auto i = 0; i != n; ++i) {
    14141409            if (cube[i] == 0) {
     1410                assert (!DQ.full());
    14151411                DQ.push_back(variables[i]);
    14161412            } else if (cube[i] == 1) {
     1413                assert (!CQ.full());
    14171414                CQ.push_back(variables[i]);
    14181415            }
    14191416        }
    1420         if (!DQ.empty()) {
     1417
     1418        if (LLVM_UNLIKELY(DQ.empty() && CQ.empty())) {
     1419            continue;
     1420        }
     1421
     1422        if (DQ.size() > 0) {
    14211423            while (DQ.size() > 1) {
    14221424                PabloAST * v1 = DQ.front(); DQ.pop_front();
    14231425                PabloAST * v2 = DQ.front(); DQ.pop_front();
    14241426                DQ.push_back(builder.createOr(v1, v2));
    1425                 ++count;
    14261427            }
    14271428            CQ.push_back(builder.createNot(DQ.front()));
    1428             DQ.clear();
    1429         }
     1429            DQ.pop_front();
     1430        }
     1431
     1432        assert (!CQ.empty());
    14301433        while (CQ.size() > 1) {
    14311434            PabloAST * v1 = CQ.front(); CQ.pop_front();
    14321435            PabloAST * v2 = CQ.front(); CQ.pop_front();
    14331436            CQ.push_back(builder.createAnd(v1, v2));
    1434             ++count;
    1435         }
    1436         SQ.push(CQ.front()); CQ.clear();
    1437     }
    1438     Cudd_RecursiveDeref(manager, g);
    1439 
     1437        }
     1438        SQ.push(CQ.front()); CQ.pop_front();
     1439    }
     1440    Cudd_RecursiveDeref(mManager, g);
     1441    if (LLVM_UNLIKELY(SQ.empty())) {
     1442        return nullptr;
     1443    }
    14401444    while (SQ.size() > 1) {
    14411445        PabloAST * v1 = SQ.front(); SQ.pop();
    14421446        PabloAST * v2 = SQ.front(); SQ.pop();
    14431447        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 //}
     1448    }
     1449    return SQ.front();
     1450}
    17621451
    17631452/** ------------------------------------------------------------------------------------------------------------- *
     
    17761465    std::unordered_set<const PabloAST *> encountered;
    17771466    std::stack<Statement *> scope;
     1467
    17781468    for (Statement * stmt = entry.front(); ; ) { restart:
    17791469        while ( stmt ) {
     1470
    17801471            for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
    17811472                PabloAST * const op = stmt->getOperand(i);
     
    18021493                continue;
    18031494            }
     1495
    18041496            encountered.insert(stmt);
    18051497            stmt = stmt->getNextNode();
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.hpp

    r4711 r4722  
    3535    using AdvanceVector = std::vector<std::tuple<Advance *, DdNode *, DdNode *>>;
    3636    using VertexVector = std::vector<ConstraintVertex>;
    37     using RecentCharacterizations = std::vector<std::pair<const PabloAST *, DdNode *>>;   
     37    using RecentCharacterizations = std::vector<std::pair<const PabloAST *, DdNode *>>;
     38    using MuxedVariables = std::vector<std::vector<PabloAST *>>;
    3839public:
    3940    static bool optimize(PabloFunction & function);
     
    4849    void selectMultiplexSets(RNG &);
    4950    void applySubsetConstraints();
    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;
     51    void multiplexSelectedIndependentSets();
     52    void simplifyAST(const PabloFunction & function);
     53    PabloAST * simplifyAST(DdNode * const f, const std::vector<PabloAST *> & variables, PabloBuilder & builder);
     54    PabloAST * makeCoverAST(DdNode * const f, const std::vector<PabloAST *> & variables, PabloBuilder & builder);
    5455    void topologicalSort(PabloBlock & entry) const;
    5556    inline AutoMultiplexing()
     
    8485    MultiplexSetGraph           mMultiplexSetGraph;
    8586    RecentCharacterizations     mRecentCharacterizations;
     87    MuxedVariables              mMuxedVariables;
     88    unsigned                    mSimplifyDepth;
    8689};
    8790
  • icGREP/icgrep-devel/icgrep/pablo/pabloAST.cpp

    r4711 r4722  
    99#include <llvm/Support/Compiler.h>
    1010#include <pablo/printer_pablos.h>
    11 
    1211#ifndef NDEBUG
    1312#include <queue>
     13#include <unordered_set>
    1414#endif
     15
    1516namespace pablo {
    1617
     
    104105    assert (index < getNumOperands());
    105106    assert (noRecursiveOperand(value));
    106     if (LLVM_UNLIKELY(getOperand(index) == value)) {
     107    PabloAST * const priorValue = getOperand(index);
     108    if (LLVM_UNLIKELY(priorValue == value)) {
    107109        return;
    108     }
    109     PabloAST * priorValue = getOperand(index);
     110    }   
    110111    if (LLVM_LIKELY(priorValue != nullptr)) {
    111112        // Test just to be sure that we don't have multiple operands pointing to
     
    259260#ifndef NDEBUG
    260261bool Statement::noRecursiveOperand(const PabloAST * const operand) {
    261     if (operand && isa<Statement>(operand)) {
     262    if (const Statement * stmt = dyn_cast<Statement>(operand)) {
    262263        std::queue<const Statement *> Q;
    263         Q.push(cast<Statement>(operand));
    264         while (!Q.empty()) {
    265             const Statement * stmt = Q.front();
     264        std::unordered_set<const PabloAST *> V;
     265        V.insert(stmt);
     266        for (;;) {
    266267            if (stmt == this) {
    267268                return false;
    268269            }
     270            for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
     271                const PabloAST * op = stmt->getOperand(i);               
     272                if (isa<Statement>(op) && V.count(op) == 0) {
     273                    Q.push(cast<Statement>(op));
     274                    V.insert(op);
     275                }
     276            }
     277            if (LLVM_UNLIKELY(Q.empty())) {
     278                break;
     279            }
     280            stmt = Q.front();
    269281            Q.pop();
    270             for (auto i = 0; i != stmt->getNumOperands(); ++i) {
    271                 const PabloAST * op = stmt->getOperand(i);
    272                 if (isa<Statement>(op)) {
    273                     Q.push(cast<Statement>(op));
    274                 }
    275             }
    276282        }
    277283    }
Note: See TracChangeset for help on using the changeset viewer.