Ignore:
Timestamp:
Aug 24, 2015, 4:14:48 PM (4 years ago)
Author:
nmedfort
Message:

First (hopefully) working version of the boolean reassociation pass + some bug fixes.

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

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/booleanreassociationpass.cpp

    r4747 r4748  
    6262using Graph = adjacency_list<hash_setS, vecS, bidirectionalS, PabloAST *>;
    6363using Vertex = Graph::vertex_descriptor;
     64using VertexQueue = circular_buffer<Vertex>;
    6465
    6566/** ------------------------------------------------------------------------------------------------------------- *
     
    7879
    7980/** ------------------------------------------------------------------------------------------------------------- *
     81 * @brief push
     82 ** ------------------------------------------------------------------------------------------------------------- */
     83static inline void push(const Vertex u, VertexQueue & Q) {
     84    if (LLVM_UNLIKELY(Q.full())) {
     85        Q.set_capacity(Q.capacity() * 2);
     86    }
     87    Q.push_back(u);
     88    assert (Q.back() == u);
     89}
     90
     91/** ------------------------------------------------------------------------------------------------------------- *
     92 * @brief pop
     93 ** ------------------------------------------------------------------------------------------------------------- */
     94static inline Vertex pop(VertexQueue & Q) {
     95    assert (!Q.empty() && "Popping an empty vertex queue");
     96    const Vertex u = Q.front();
     97    Q.pop_front();
     98    return u;
     99}
     100
     101/** ------------------------------------------------------------------------------------------------------------- *
    80102 * @brief scan
    81103 ** ------------------------------------------------------------------------------------------------------------- */
     
    83105
    84106    using Map = std::unordered_map<PabloAST *, Vertex>;
    85     using VertexQueue = std::queue<Vertex>;
    86107    using EdgeQueue = std::queue<std::pair<Vertex, Vertex>>;
    87 
    88     PabloBuilder builder(block);
    89108
    90109    for (Statement * stmt : block) {
     
    97116            Terminals terminals(vars.begin(), vars.end());
    98117            scan(cast<While>(stmt)->getBody(), std::move(terminals));
    99         } else {
    100             builder.record(stmt);
    101         }
    102 
     118        }
    103119    }
    104120
     
    106122    // safely rearrange expressions such as "((((a √ b) √ c) √ d) √ e) √ f" into "((a √ b) √ (c √ d)) √ (e √ f)".
    107123
    108     bool modifiedAST = false;
     124    VertexQueue Q(128);
    109125
    110126    for (;;) {
     
    114130
    115131        // Generate a graph depicting the relationships between the terminals. If the original terminals
    116         // cannot be optimized with this algorithm bypass them in favour of their operands.
    117 
    118         VertexQueue Q;
    119         unsigned count = 0;
     132        // cannot be optimized with this algorithm bypass them in favour of their operands. If those cannot
     133        // be optimized, they'll be left as the initial terminals for the next "layer" of the AST.
     134
    120135        for (Statement * const term : terminals) {
    121136            assert (term);
    122             assert (Q.size() == count);
    123137            if (isaBooleanOperation(term)) {
    124138                if (LLVM_LIKELY(M.count(term) == 0)) {                   
    125                     const auto v = add_vertex(term, G);
     139                    const Vertex v = add_vertex(term, G);
    126140                    assert (v < num_vertices(G));
    127141                    M.insert(std::make_pair(term, v));
    128                     Q.push(v);
    129                     ++count;
     142                    push(v, Q);
    130143                }
    131144            } else {
     
    134147                    assert (op);
    135148                    if (LLVM_LIKELY(isa<Statement>(op) && M.count(op) == 0)) {
    136                         const auto v = add_vertex(op, G);
     149                        const Vertex v = add_vertex(op, G);
    137150                        assert (v < num_vertices(G));
    138151                        M.insert(std::make_pair(op, v));
    139                         Q.push(v);
    140                         ++count;
     152                        push(v, Q);
    141153                    }
    142154                }
     
    144156        }
    145157
     158        if (Q.empty()) {
     159            break;
     160        }
     161
    146162        for (;;) {
    147             assert (Q.size() == count);
    148             const Vertex u = Q.front(); Q.pop();
    149             --count;
     163            const Vertex u = pop(Q);
    150164            assert (u < num_vertices(G));
    151165            if (isaBooleanOperation(G[u])) {
     
    156170                    auto f = M.find(op);
    157171                    if (f == M.end()) {
    158                         const auto v = add_vertex(op, G);
     172                        const Vertex v = add_vertex(op, G);
    159173                        assert (v < num_vertices(G));
    160174                        f = M.insert(std::make_pair(op, v)).first;
    161175                        if (op->getClassTypeId() == stmt->getClassTypeId() && cast<Statement>(op)->getParent() == &block) {
    162                             Q.push(v);
    163                             ++count;
     176                            push(v, Q);
    164177                        }
    165178                    }
     
    199212            // Cut the graph wherever a computation crosses a component or whenever we need to cut the graph because
    200213            // the instructions corresponding to the pair of nodes differs.
    201             EdgeQueue Q;
     214            EdgeQueue E;
    202215            graph_traits<Graph>::edge_iterator ei, ei_end;
    203216            for (std::tie(ei, ei_end) = edges(G); ei != ei_end; ) {
     
    206219                const Vertex v = target(e, G);
    207220                if (LLVM_UNLIKELY(isCutNecessary(u, v, G, component))) {
    208                     Q.push(std::make_pair(u, v));
     221                    E.push(std::make_pair(u, v));
    209222                    remove_edge(u, v, G);
    210223                }
     
    212225
    213226            // If no cuts are necessary, we're done.
    214             if (Q.empty()) {
     227            if (E.empty()) {
    215228                break;
    216229            }
     
    219232
    220233                Vertex u, v;
    221                 std::tie(u, v) = Q.front(); Q.pop();
     234                std::tie(u, v) = E.front(); E.pop();
    222235
    223236                // The vertex belonging to a component with a greater number must come "earlier"
     
    242255                if (in_degree(u, G) != 0) {
    243256                    for (auto e : make_iterator_range(out_edges(u, G))) {
    244                         Q.push(std::make_pair(source(e, G), target(e, G)));
     257                        E.push(std::make_pair(source(e, G), target(e, G)));
    245258                    }
    246259                    clear_out_edges(u, G);
    247260                }
    248261
    249                 if (Q.empty()) {
     262                if (E.empty()) {
    250263                    break;
    251264                }
     
    263276                flat_map<Vertex, unsigned> L;
    264277                flat_set<PabloAST *> V;
    265                 VertexQueue Q;
    266278
    267279                Vertex v = u;
     
    282294                                f->second = std::max(f->second, l);
    283295                            }
    284                             Q.push(w);
     296                            push(w, Q);
    285297                        }
    286298                    }
     
    288300                        break;
    289301                    }
    290                     v = Q.front();
    291                     Q.pop();
     302                    v = pop(Q);
    292303                }
    293304
     
    307318                            PabloAST * e1 = Q.front(); Q.pop_front();
    308319                            PabloAST * e2 = Q.front(); Q.pop_front();
    309                             Q.push_back(builder.createAnd(e1, e2));
     320                            Q.push_back(block.createAnd(e1, e2));
    310321                        }
    311322                    } else if (isa<Or>(stmt)) {
     
    313324                            PabloAST * e1 = Q.front(); Q.pop_front();
    314325                            PabloAST * e2 = Q.front(); Q.pop_front();
    315                             Q.push_back(builder.createOr(e1, e2));
     326                            Q.push_back(block.createOr(e1, e2));
    316327                        }
    317328                    } else { assert(isa<Xor>(stmt));
     
    319330                            PabloAST * e1 = Q.front(); Q.pop_front();
    320331                            PabloAST * e2 = Q.front(); Q.pop_front();
    321                             Q.push_back(builder.createXor(e1, e2));
    322                         }
    323                     }
    324                     stmt->replaceWith(Q.front(), true, false);
    325                     modifiedAST = true;
     332                            Q.push_back(block.createXor(e1, e2));
     333                        }
     334                    }
     335                    stmt->replaceWith(Q.front(), true, true);
    326336                }
    327337            }
     
    350360        terminals.assign(nextSet.begin(), nextSet.end());
    351361    }
    352 
    353     // If we modified the AST, we likely left dead code in it. Go through and remove any from this block.
    354     if (modifiedAST) {
    355         Statement * stmt = block.front();
    356         while (stmt) {
    357             if (stmt->getNumUses() == 0 && !(isa<If>(stmt) || isa<While>(stmt))){
    358                 stmt = stmt->eraseFromParent(true);
    359             } else {
    360                 stmt = stmt->getNextNode();
    361             }
    362         }
    363     }
    364362}
    365363
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/booleanreassociationpass.h

    r4736 r4748  
    77
    88class BooleanReassociationPass {   
    9 
    10 //    using Vertex = Graph::vertex_descriptor;
    11 //    using Map = std::unordered_map<PabloAST *, Vertex>;
    12 //    using Queue = boost::circular_buffer<PabloAST *>;
    139    using Terminals = std::vector<Statement *>;
    1410public:
     
    1814    void scan(PabloFunction & function);
    1915    void scan(PabloBlock & block, Terminals && terminals);
    20 
    21 
    2216};
    2317
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.cpp

    r4747 r4748  
    2525using namespace boost::numeric::ublas;
    2626
    27 #define PRINT_DEBUG_OUTPUT
     27// #define PRINT_DEBUG_OUTPUT
    2828
    2929#if !defined(NDEBUG) && !defined(PRINT_DEBUG_OUTPUT)
     
    160160        LOG("SelectedIndependentSets: " << (end_select_independent_sets - start_select_independent_sets));
    161161
    162         BooleanReassociationPass::optimize(function);
    163 
    164162        RECORD_TIMESTAMP(start_topological_sort);
    165163        am.topologicalSort(function.getEntryBlock());
    166164        RECORD_TIMESTAMP(end_topological_sort);
    167         LOG("TopologicalSort (1):     " << (end_topological_sort - start_topological_sort));
    168 
    169         BDDMinimizationPass::optimize(function, false);
     165        LOG("TopologicalSort:        " << (end_topological_sort - start_topological_sort));
     166
     167        BooleanReassociationPass::optimize(function);
     168
     169        BDDMinimizationPass::optimize(function);
    170170    }
    171171
     
    10591059    std::stack<Statement *> scope;
    10601060
    1061     raw_os_ostream out(std::cerr);
    1062 
    10631061    for (Statement * stmt = entry.front(); ; ) { restart:
    10641062        while ( stmt ) {
     
    10731071                        }
    10741072                        Statement * const next = stmt->getNextNode();
     1073                        Statement * after = cast<Statement>(op);
     1074                        if (LLVM_UNLIKELY(after->getParent() != stmt->getParent())) {
     1075                            if (after->getParent()) {
     1076                                throw std::runtime_error("Operand is not in the same scope as the statement!");
     1077                            } else {
     1078                                throw std::runtime_error("Operand is not in any pablo scope!");
     1079                            }
     1080                        }
    10751081                        stmt->insertAfter(cast<Statement>(op));
    10761082                        stmt = next;
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_bddminimization.cpp

    r4736 r4748  
    2121namespace pablo {
    2222
    23 bool BDDMinimizationPass::optimize(PabloFunction & function, const bool full) {
     23bool BDDMinimizationPass::optimize(PabloFunction & function) {
    2424    BDDMinimizationPass am;
    2525    am.eliminateLogicallyEquivalentStatements(function);
    26     if (full) {
    27         am.simplifyAST(function);
    28     }
    29     am.shutdown();
    3026    return Simplifier::optimize(function);
    3127}
     
    9894    eliminateLogicallyEquivalentStatements(function.getEntryBlock(), baseMap);
    9995
    100     Cudd_AutodynDisable(mManager);
     96    Cudd_Quit(mManager);
    10197}
    10298
     
    108104 ** ------------------------------------------------------------------------------------------------------------- */
    109105void BDDMinimizationPass::eliminateLogicallyEquivalentStatements(PabloBlock & block, SubsitutionMap & parent) {
    110     SubsitutionMap subsitutionMap(&parent);
     106    SubsitutionMap map(&parent);
    111107    Statement * stmt = block.front();
    112108    while (stmt) {
    113109        if (LLVM_UNLIKELY(isa<If>(stmt))) {
    114             eliminateLogicallyEquivalentStatements(cast<If>(stmt)->getBody(), subsitutionMap);
    115             for (Assign * var : cast<const If>(stmt)->getDefined()) {
    116                 mCharacterizationMap[var] = NewVar(var);
     110            eliminateLogicallyEquivalentStatements(cast<If>(stmt)->getBody(), map);
     111            for (Assign * def : cast<const If>(stmt)->getDefined()) {
     112                map.insert(mCharacterizationMap[def], def);
    117113            }
    118114        } else if (LLVM_UNLIKELY(isa<While>(stmt))) {
    119             eliminateLogicallyEquivalentStatements(cast<While>(stmt)->getBody(), subsitutionMap);
     115            eliminateLogicallyEquivalentStatements(cast<While>(stmt)->getBody(), map);
    120116            for (Next * var : cast<const While>(stmt)->getVariants()) {
    121                 mCharacterizationMap[var] = NewVar(var);
    122             }
    123         } else { // attempt to characterize this statement and replace it if
    124             DdNode * bdd = eliminateLogicallyEquivalentStatements(stmt);
    125             if (LLVM_LIKELY(!isa<Assign>(stmt) && !isa<Next>(stmt))) {
    126                 PabloAST * replacement = subsitutionMap[bdd];
    127                 if (replacement) {
     117                map.insert(mCharacterizationMap[var], var);
     118            }
     119        } else { // attempt to characterize this statement and replace it if we've encountered an equivalent one
     120            DdNode * bdd = nullptr;
     121            bool test = false;
     122            std::tie(bdd, test) = characterize(stmt);
     123            if (test) {
     124                PabloAST * replacement = map.get(bdd);
     125                if (LLVM_UNLIKELY(replacement != nullptr)) {
    128126                    Cudd_RecursiveDeref(mManager, bdd);
    129127                    stmt = stmt->replaceWith(replacement, false, true);
    130128                    continue;
    131129                }
    132                 subsitutionMap.insert(bdd, stmt);
     130            } else if (LLVM_LIKELY(nonConstant(bdd))) {
     131                map.insert(bdd, stmt);
    133132            }
    134133            mCharacterizationMap.insert(std::make_pair(stmt, bdd));
     
    142141 * @brief characterize
    143142 ** ------------------------------------------------------------------------------------------------------------- */
    144 inline DdNode * BDDMinimizationPass::eliminateLogicallyEquivalentStatements(const Statement * const stmt) {
     143inline std::pair<DdNode *, bool> BDDMinimizationPass::characterize(Statement * const stmt) {
    145144
    146145    DdNode * bdd = nullptr;
     
    157156        auto f = mCharacterizationMap.find(op);
    158157        if (LLVM_UNLIKELY(f == mCharacterizationMap.end())) {
    159             throw std::runtime_error("Error in AST: attempted to characterize statement with unknown operand!");
     158            throw std::runtime_error("BDDMinimizationPass: attempted to characterize statement with unknown operand!");
    160159        }
    161160        input[i] = f->second;
     
    165164        case PabloAST::ClassTypeId::Assign:
    166165        case PabloAST::ClassTypeId::Next:
    167             return input[0];
     166            return std::make_pair(input[0], false);
    168167        case PabloAST::ClassTypeId::And:
    169168            bdd = And(input[0], input[1]);
    170             break;       
     169            break;
    171170        case PabloAST::ClassTypeId::Or:
    172171            bdd = Or(input[0], input[1]);
     
    183182        case PabloAST::ClassTypeId::MatchStar:
    184183        case PabloAST::ClassTypeId::ScanThru:
    185             if (LLVM_UNLIKELY(isZero(input[1]))) {
    186                 return Zero();
     184            if (LLVM_UNLIKELY(input[1] == Zero())) {
     185                return std::make_pair(Zero(), true);
    187186            }
    188187        case PabloAST::ClassTypeId::Advance:
    189             if (LLVM_UNLIKELY(isZero(input[0]))) {
    190                 return Zero();
     188            if (LLVM_UNLIKELY(input[0] == Zero())) {
     189                return std::make_pair(Zero(), true);
    191190            }
    192191        case PabloAST::ClassTypeId::Call:
    193192            // TODO: we may have more than one output. Need to fix call class to allow for it.
    194             return NewVar(stmt);
     193            return std::make_pair(NewVar(stmt), false);
    195194        default:
    196195            throw std::runtime_error("Unexpected statement type " + stmt->getName()->to_string());
    197196    }
    198 
    199197    Cudd_Ref(bdd);
    200 
    201198    if (LLVM_UNLIKELY(noSatisfyingAssignment(bdd))) {
    202199        Cudd_RecursiveDeref(mManager, bdd);
    203200        bdd = Zero();
    204201    }
    205 
    206     return bdd;
    207 }
    208 
    209 /** ------------------------------------------------------------------------------------------------------------- *
    210  * @brief simplifyAST
    211  ** ------------------------------------------------------------------------------------------------------------- */
    212 inline void BDDMinimizationPass::simplifyAST(PabloFunction & function) {
    213     Terminals terminals;
    214     for (unsigned i = 0; i != function.getNumOfResults(); ++i) {
    215         terminals.push_back(function.getResult(i));
    216     }   
    217     Cudd_ReduceHeap(mManager, CUDD_REORDER_EXACT, 1);
    218     simplifyAST(function.getEntryBlock(), std::move(terminals));
    219 }
    220 
    221 
    222 /** ------------------------------------------------------------------------------------------------------------- *
    223  * @brief simplifyAST
    224  ** ------------------------------------------------------------------------------------------------------------- */
    225 void BDDMinimizationPass::simplifyAST(PabloBlock & block, Terminals && terminals) {
    226 
    227     for (Statement * stmt : block) {
    228         if (isa<If>(stmt)) {
    229             Terminals terminals;
    230             for (Assign * var : cast<const If>(stmt)->getDefined()) {
    231                 terminals.push_back(var);
    232             }
    233             simplifyAST(cast<If>(stmt)->getBody(), std::move(terminals));
    234         } else if (isa<While>(stmt)) {
    235             Terminals terminals;
    236             for (Next * var : cast<const While>(stmt)->getVariants()) {
    237                 terminals.push_back(var);
    238             }
    239             simplifyAST(cast<While>(stmt)->getBody(), std::move(terminals));
    240         }
    241     }
    242 
    243 //    // find the variables for this set of terminals
    244 //    DdNode * careSet = One();
    245 //    std::queue<Statement *> Q;
    246 //    for (Statement * term : terminals) {
    247 //        Q.push(term);
    248 //    }
    249 //    flat_set<PabloAST *> visited;
    250 //    for (;;) {
    251 //        Statement * stmt = Q.front();
    252 //        Q.pop();
    253 //        for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
    254 //            PabloAST * const op = stmt->getOperand(i);
    255 //            if (visited.count(op) == 0) {
    256 //                DdNode * n = mCharacterizationMap[op];
    257 //                if (Cudd_bddIsVar(mManager, n)) {
    258 //                    careSet = And(careSet, n);
    259 //                    Cudd_Ref(careSet);
    260 //                } else if (isa<Statement>(op)){
    261 //                    Q.push(cast<Statement>(op));
    262 //                }
    263 //                visited.insert(op);
    264 //            }
    265 //        }
    266 //        if (Q.empty()) {
    267 //            break;
    268 //        }
    269 //    }
    270 
    271     flat_set<Statement *> inputs;
    272 
    273     for (Statement * term : terminals) {
    274         for (unsigned i = 0; i != term->getNumOperands(); ++i) {
    275             if (isa<Statement>(term->getOperand(i))) {
    276                 inputs.insert(cast<Statement>(term->getOperand(i)));
    277             }
    278         }
    279     }
    280 
    281     for (Statement * input : inputs) {
    282 
    283         DdNode * f = mCharacterizationMap[input]; assert (f);
    284         Cudd_Ref(f);
    285 
    286         block.setInsertPoint(input);
    287         PabloAST * replacement = simplifyAST(f, block);
    288         if (replacement) {
    289             input->replaceWith(replacement, false, true);
    290         }
    291 
    292         Cudd_RecursiveDeref(mManager, f);
    293     }
    294 }
    295 
    296 
    297 /** ------------------------------------------------------------------------------------------------------------- *
    298  * @brief simplifyAST
    299  ** ------------------------------------------------------------------------------------------------------------- */
    300 PabloAST * BDDMinimizationPass::simplifyAST(DdNode * const f, PabloBlock &block) {
    301 
    302     DdNode * g = Cudd_FindEssential(mManager, f);
    303 
    304     if (g && Cudd_SupportSize(mManager, g) > 0) {
    305         if (g == f) { // every variable is essential
    306             return makeCoverAST(f, block);
    307         }
    308         Cudd_Ref(g);
    309         PabloAST * c0 = makeCoverAST(g, block);
    310         if (LLVM_UNLIKELY(c0 == nullptr)) {
    311             Cudd_RecursiveDeref(mManager, g);
    312             return nullptr;
    313         }
    314         DdNode * h = Cudd_Cofactor(mManager, f, g);
    315         Cudd_Ref(h);
    316         PabloAST * c1 = simplifyAST(h, block);
    317         if (LLVM_UNLIKELY(c1 == nullptr)) {
    318             Cudd_RecursiveDeref(mManager, g);
    319             Cudd_RecursiveDeref(mManager, h);
    320             cast<Statement>(c0)->eraseFromParent(true);
    321             return nullptr;
    322         }
    323         assert (And(g, h) == f);
    324         Cudd_RecursiveDeref(mManager, g);
    325         Cudd_RecursiveDeref(mManager, h);
    326         return block.createAnd(c0, c1, "e");
    327     }
    328 
    329     DdNode ** disjunct = nullptr;
    330     int disjuncts = Cudd_bddIterDisjDecomp(mManager, f, &disjunct);
    331     assert (disjuncts < 2 || Or(disjunct[0], disjunct[1]) == f);
    332 
    333     DdNode ** conjunct = nullptr;
    334     int conjuncts = Cudd_bddIterConjDecomp(mManager, f, &conjunct);
    335     assert (conjuncts < 2 || And(conjunct[0], conjunct[1]) == f);
    336 
    337     if (LLVM_LIKELY(disjuncts == 2 && conjuncts == 2)) {
    338         if (Cudd_SharingSize(disjunct, 2) > Cudd_SharingSize(conjunct, 2)) {
    339             disjuncts = 0;
    340         }
    341     }
    342 
    343     DdNode * decomp[] = { nullptr, nullptr };
    344     if (disjuncts == 2) {
    345         memcpy(decomp, disjunct, sizeof(DdNode *) * 2);
    346     } else if (conjuncts == 2) {
    347         memcpy(decomp, conjunct, sizeof(DdNode *) * 2);
    348     }
    349 
    350     FREE(disjunct);
    351     FREE(conjunct);
    352 
    353     if ((decomp[0] != decomp[1]) && (decomp[0] != f) && (decomp[1] != f)) {
    354 
    355         Cudd_Ref(decomp[0]);
    356         Cudd_Ref(decomp[1]);
    357         PabloAST * d0 = simplifyAST(decomp[0], block);
    358         Cudd_RecursiveDeref(mManager, decomp[0]);
    359         if (LLVM_UNLIKELY(d0 == nullptr)) {
    360             Cudd_RecursiveDeref(mManager, decomp[1]);
    361             return nullptr;
    362         }
    363 
    364         PabloAST * d1 = simplifyAST(decomp[1], block);
    365         Cudd_RecursiveDeref(mManager, decomp[1]);
    366         if (LLVM_UNLIKELY(d1 == nullptr)) {
    367             cast<Statement>(d0)->eraseFromParent(true);
    368             return nullptr;
    369         }
    370 
    371         if (disjuncts == 2) {
    372             return block.createOr(d0, d1, "d");
    373         } else {
    374             return block.createAnd(d0, d1, "c");
    375         }
    376     }
    377     return makeCoverAST(f, block);
    378 }
    379 
    380 ///** ------------------------------------------------------------------------------------------------------------- *
    381 // * @brief makeCoverAST
    382 // ** ------------------------------------------------------------------------------------------------------------- */
    383 //PabloAST * BDDMinimizationPass::makeCover(DdNode * const f, PabloBlock & block) {
    384 
    385 //    const auto n = mVariables.size();
    386 
    387 //    if (Cudd_DagSize(f) > 100) {
    388 
    389 //        int * indices = nullptr;
    390 //        const int count = Cudd_SupportIndices(mManager, f, &indices);
    391 //        DdManager * manager = Cudd_Init(count, 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0);
    392 
    393 //        std::vector<DdNode *> var(n, nullptr);
    394 
    395 //        for (unsigned i = 0; i != count; ++i) {
    396 //            var[indicies[i]] = Cudd_bddIthVar(manager, i);
    397 //        }
    398 
    399 //        makeCloneOf()
    400 
    401 
    402 
    403 //        Cudd_Quit(manager);
    404 //    }
    405 
    406 
    407 
    408 //}
    409 
    410 /** ------------------------------------------------------------------------------------------------------------- *
    411  * @brief makeCoverAST
    412  ** ------------------------------------------------------------------------------------------------------------- */
    413 PabloAST * BDDMinimizationPass::makeCoverAST(DdNode * const f, PabloBlock & block) {
    414 
    415     const auto n = mVariables.size();
    416     assert (mManager->size == n);
    417 
    418     DdNode * g = f;
    419 
    420     Cudd_Ref(g);
    421 
    422     std::queue<PabloAST *> SQ;
    423     circular_buffer<PabloAST *> CQ(n + 1);
    424     circular_buffer<PabloAST *> DQ(n + 1);
    425 
    426     int cube[n];
    427 
    428     while (g != Cudd_ReadLogicZero(mManager)) {
    429         int length = 0;
    430         DdNode * implicant = Cudd_LargestCube(mManager, g, &length);
    431         if (LLVM_UNLIKELY(implicant == nullptr)) {
    432             Cudd_RecursiveDeref(mManager, g);
    433             return nullptr;
    434         }
    435         Cudd_Ref(implicant);
    436         DdNode * prime = Cudd_bddMakePrime(mManager, implicant, f);
    437         if (LLVM_UNLIKELY(prime == nullptr)) {
    438             Cudd_RecursiveDeref(mManager, g);
    439             Cudd_RecursiveDeref(mManager, implicant);
    440             return nullptr;
    441         }
    442         Cudd_Ref(prime);
    443         Cudd_RecursiveDeref(mManager, implicant);
    444 
    445         DdNode * h = Cudd_bddAnd(mManager, g, Cudd_Not(prime));
    446         if (LLVM_UNLIKELY(h == nullptr)) {
    447             Cudd_RecursiveDeref(mManager, g);
    448             Cudd_RecursiveDeref(mManager, prime);
    449             return nullptr;
    450         }
    451         Cudd_Ref(h);
    452         Cudd_RecursiveDeref(mManager, g);
    453 
    454         g = h;
    455         if (LLVM_UNLIKELY(Cudd_BddToCubeArray(mManager, prime, cube) == 0)) {
    456             Cudd_RecursiveDeref(mManager, g);
    457             Cudd_RecursiveDeref(mManager, prime);
    458             return nullptr;
    459         }
    460         Cudd_RecursiveDeref(mManager, prime);
    461 
    462         assert (DQ.empty() && CQ.empty());
    463 
    464         for (auto i = 0; i != n; ++i) {
    465             assert (cube[i] >= 0 && cube[i] <= 2);
    466             if (cube[i] == 0) {
    467                 DQ.push_back(mVariables[i]);
    468             } else if (cube[i] == 1) {
    469                 CQ.push_back(mVariables[i]);
    470             }
    471         }
    472 
    473         if (LLVM_UNLIKELY(DQ.empty() && CQ.empty())) {
    474             throw std::runtime_error("Error! statement contains no elements!");
    475         }
    476 
    477         if (DQ.size() > 0) {
    478             while (DQ.size() > 1) {
    479                 PabloAST * v1 = DQ.front(); DQ.pop_front();
    480                 PabloAST * v2 = DQ.front(); DQ.pop_front();
    481                 DQ.push_back(block.createOr(v1, v2));
    482             }
    483             CQ.push_back(block.createNot(DQ.front()));
    484             DQ.pop_front();
    485         }
    486 
    487         assert (!CQ.empty());
    488         while (CQ.size() > 1) {
    489             PabloAST * v1 = CQ.front(); CQ.pop_front();
    490             PabloAST * v2 = CQ.front(); CQ.pop_front();
    491             CQ.push_back(block.createAnd(v1, v2));
    492         }
    493         SQ.push(CQ.front()); CQ.pop_front();
    494     }
    495 
    496     Cudd_RecursiveDeref(mManager, g);
    497 
    498     if (LLVM_UNLIKELY(SQ.empty())) {
    499         throw std::runtime_error("Error! statement queue empty!");
    500     }
    501 
    502     while (SQ.size() > 1) {
    503         PabloAST * v1 = SQ.front(); SQ.pop();
    504         PabloAST * v2 = SQ.front(); SQ.pop();
    505         SQ.push(block.createOr(v1, v2));
    506     }
    507     return SQ.front();
    508 
    509 }
    510 
    511 //DdNode * BDDMinimizationPass::makeCloneOf(DdManager * sourceMgr, DdNode * const f, DdManager * destinationMgr) {
    512 
    513 //    const auto n = mVariables.size();
    514 //    assert (sourceMgr->size == n);
    515 
    516 //    std::queue<DdNode *> SQ;
    517 //    circular_buffer<DdNode *> CQ(n + 1);
    518 //    circular_buffer<DdNode *> DQ(n + 1);
    519 
    520 //    int cube[n];
    521 
    522 //    DdNode * g = f;
    523 
    524 //    Cudd_Ref(g);
    525 
    526 //    Cudd_AutodynEnable(destinationMgr, CUDD_REORDER_SIFT);
    527 
    528 //    while (g != Cudd_ReadLogicZero(sourceMgr)) {
    529 //        int length = 0;
    530 //        DdNode * implicant = Cudd_LargestCube(sourceMgr, g, &length);
    531 //        if (LLVM_UNLIKELY(implicant == nullptr)) {
    532 //            Cudd_RecursiveDeref(sourceMgr, g);
    533 //            return nullptr;
    534 //        }
    535 //        Cudd_Ref(implicant);
    536 //        DdNode * prime = Cudd_bddMakePrime(sourceMgr, implicant, f);
    537 //        if (LLVM_UNLIKELY(prime == nullptr)) {
    538 //            Cudd_RecursiveDeref(sourceMgr, g);
    539 //            Cudd_RecursiveDeref(sourceMgr, implicant);
    540 //            return nullptr;
    541 //        }
    542 //        Cudd_Ref(prime);
    543 //        Cudd_RecursiveDeref(sourceMgr, implicant);
    544 
    545 //        DdNode * h = Cudd_bddAnd(sourceMgr, g, Cudd_Not(prime));
    546 //        if (LLVM_UNLIKELY(h == nullptr)) {
    547 //            Cudd_RecursiveDeref(sourceMgr, g);
    548 //            Cudd_RecursiveDeref(sourceMgr, prime);
    549 //            return nullptr;
    550 //        }
    551 //        Cudd_Ref(h);
    552 //        Cudd_RecursiveDeref(sourceMgr, g);
    553 
    554 //        g = h;
    555 //        if (LLVM_UNLIKELY(Cudd_BddToCubeArray(sourceMgr, prime, cube) == 0)) {
    556 //            Cudd_RecursiveDeref(sourceMgr, g);
    557 //            Cudd_RecursiveDeref(sourceMgr, prime);
    558 //            return nullptr;
    559 //        }
    560 //        Cudd_RecursiveDeref(sourceMgr, prime);
    561 
    562 //        assert (DQ.empty() && CQ.empty());
    563 
    564 //        for (auto i = 0; i != n; ++i) {
    565 //            assert (cube[i] >= 0 && cube[i] <= 2);
    566 //            if (cube[i] == 0) {
    567 //                DQ.push_back(var[i]);
    568 //            } else if (cube[i] == 1) {
    569 //                CQ.push_back(var[i]);
    570 //            }
    571 //        }
    572 
    573 //        if (LLVM_UNLIKELY(DQ.empty() && CQ.empty())) {
    574 //            throw std::runtime_error("Error! statement contains no elements!");
    575 //        }
    576 
    577 //        if (DQ.size() > 0) {
    578 //            while (DQ.size() > 1) {
    579 //                PabloAST * v1 = DQ.front(); DQ.pop_front();
    580 //                PabloAST * v2 = DQ.front(); DQ.pop_front();
    581 //                DQ.push_back(Cudd_bddOr(destinationMgr, v1, v2));
    582 //            }
    583 //            CQ.push_back(Cudd_Not(DQ.front()));
    584 //            DQ.pop_front();
    585 //        }
    586 
    587 //        assert (!CQ.empty());
    588 //        while (CQ.size() > 1) {
    589 //            PabloAST * v1 = CQ.front(); CQ.pop_front();
    590 //            PabloAST * v2 = CQ.front(); CQ.pop_front();
    591 //            CQ.push_back(Cudd_bddOr(destinationMgr, v1, v2));
    592 //        }
    593 //        SQ.push(CQ.front()); CQ.pop_front();
    594 //    }
    595 
    596 //    Cudd_RecursiveDeref(sourceMgr, g);
    597 
    598 //    if (LLVM_UNLIKELY(SQ.empty())) {
    599 //        throw std::runtime_error("Error! statement queue empty!");
    600 //    }
    601 
    602 //    while (SQ.size() > 1) {
    603 //        PabloAST * v1 = SQ.front(); SQ.pop();
    604 //        PabloAST * v2 = SQ.front(); SQ.pop();
    605 //        SQ.push(Cudd_bddOr(destinationMgr, v1, v2));
    606 //    }
    607 
    608 //    Cudd_ReduceHeap(destinationMgr, CUDD_REORDER_EXACT, 0);
    609 
    610 //    return SQ.front();
    611 
    612 //}
    613 
    614 ///** ------------------------------------------------------------------------------------------------------------- *
    615 // * @brief simplifyAST
    616 // ** ------------------------------------------------------------------------------------------------------------- */
    617 //PabloAST * BDDMinimizationPass::simplifyAST(DdNode * const f, PabloBlock &block) {
    618 
    619 //    DdNode * g = Cudd_FindEssential(mManager, f);
    620 
    621 //    if (g && Cudd_SupportSize(mManager, g) > 0) {
    622 //        if (g == f) { // every variable is essential
    623 //            return makeCoverAST(f, block);
    624 //        }
    625 //        Cudd_Ref(g);
    626 //        PabloAST * c0 = makeCoverAST(g, block);
    627 //        if (LLVM_UNLIKELY(c0 == nullptr)) {
    628 //            Cudd_RecursiveDeref(mManager, g);
    629 //            return nullptr;
    630 //        }
    631 //        DdNode * h = Cudd_Cofactor(mManager, f, g);
    632 //        Cudd_Ref(h);
    633 //        PabloAST * c1 = simplifyAST(h, block);
    634 //        if (LLVM_UNLIKELY(c1 == nullptr)) {
    635 //            Cudd_RecursiveDeref(mManager, g);
    636 //            Cudd_RecursiveDeref(mManager, h);
    637 //            cast<Statement>(c0)->eraseFromParent(true);
    638 //            return nullptr;
    639 //        }
    640 //        assert (And(g, h) == f);
    641 //        Cudd_RecursiveDeref(mManager, g);
    642 //        Cudd_RecursiveDeref(mManager, h);
    643 //        return block.createAnd(c0, c1, "e");
    644 //    }
    645 
    646 //    DdNode ** disjunct = nullptr;
    647 //    int disjuncts = Cudd_bddIterDisjDecomp(mManager, f, &disjunct);
    648 //    assert (disjuncts < 2 || Or(disjunct[0], disjunct[1]) == f);
    649 
    650 //    DdNode ** conjunct = nullptr;
    651 //    int conjuncts = Cudd_bddIterConjDecomp(mManager, f, &conjunct);
    652 //    assert (conjuncts < 2 || And(conjunct[0], conjunct[1]) == f);
    653 
    654 //    if (LLVM_LIKELY(disjuncts == 2 && conjuncts == 2)) {
    655 //        if (Cudd_SharingSize(disjunct, 2) > Cudd_SharingSize(conjunct, 2)) {
    656 //            disjuncts = 0;
    657 //        }
    658 //    }
    659 
    660 //    DdNode * decomp[] = { nullptr, nullptr };
    661 //    if (disjuncts == 2) {
    662 //        memcpy(decomp, disjunct, sizeof(DdNode *) * 2);
    663 //    } else if (conjuncts == 2) {
    664 //        memcpy(decomp, conjunct, sizeof(DdNode *) * 2);
    665 //    }
    666 
    667 //    FREE(disjunct);
    668 //    FREE(conjunct);
    669 
    670 //    if ((decomp[0] != decomp[1]) && (decomp[0] != f) && (decomp[1] != f)) {
    671 //        Cudd_Ref(decomp[0]);
    672 //        Cudd_Ref(decomp[1]);
    673 //        PabloAST * d0 = simplifyAST(decomp[0], block);
    674 //        Cudd_RecursiveDeref(mManager, decomp[0]);
    675 //        if (LLVM_UNLIKELY(d0 == nullptr)) {
    676 //            Cudd_RecursiveDeref(mManager, decomp[1]);
    677 //            return nullptr;
    678 //        }
    679 
    680 //        PabloAST * d1 = simplifyAST(decomp[1], block);
    681 //        Cudd_RecursiveDeref(mManager, decomp[1]);
    682 //        if (LLVM_UNLIKELY(d1 == nullptr)) {
    683 //            cast<Statement>(d0)->eraseFromParent(true);
    684 //            return nullptr;
    685 //        }
    686 
    687 //        if (disjuncts == 2) {
    688 //            return block.createOr(d0, d1, "t");
    689 //        } else {
    690 //            return block.createAnd(d0, d1, "t");
    691 //        }
    692 //    }
    693 //    return makeCoverAST(f, block);
    694 //}
    695 
    696 ///** ------------------------------------------------------------------------------------------------------------- *
    697 // * @brief makeCoverAST
    698 // ** ------------------------------------------------------------------------------------------------------------- */
    699 //PabloAST * BDDMinimizationPass::makeCoverAST(DdNode * const f, PabloBlock & block) {
    700 
    701 //    std::queue<PabloAST *> SQ;
    702 
    703 //    const auto n = mVariables.size();
    704 //    circular_buffer<PabloAST *> CQ(n + 1);
    705 //    circular_buffer<PabloAST *> DQ(n + 1);
    706 
    707 //    assert (mManager->size == n);
    708 
    709 //    int cube[n];
    710 
    711 //    std::cout << std::endl;
    712 
    713 //    Cudd_PrintMinterm(mManager, f);
    714 
    715 //    DdNode * g = f;
    716 
    717 //    Cudd_Ref(g);
    718 
    719 //    PabloBuilder builder(block);
    720 
    721 //    while (g != Cudd_ReadLogicZero(mManager)) {
    722 //        int length = 0;
    723 //        DdNode * implicant = Cudd_LargestCube(mManager, g, &length);
    724 //        if (LLVM_UNLIKELY(implicant == nullptr)) {
    725 //            Cudd_RecursiveDeref(mManager, g);
    726 //            return nullptr;
    727 //        }
    728 //        Cudd_Ref(implicant);
    729 //        DdNode * prime = Cudd_bddMakePrime(mManager, implicant, f);
    730 //        if (LLVM_UNLIKELY(prime == nullptr)) {
    731 //            Cudd_RecursiveDeref(mManager, g);
    732 //            Cudd_RecursiveDeref(mManager, implicant);
    733 //            return nullptr;
    734 //        }
    735 //        Cudd_Ref(prime);
    736 //        Cudd_RecursiveDeref(mManager, implicant);
    737 
    738 //        DdNode * h = Cudd_bddAnd(mManager, g, Cudd_Not(prime));
    739 //        if (LLVM_UNLIKELY(h == nullptr)) {
    740 //            Cudd_RecursiveDeref(mManager, g);
    741 //            Cudd_RecursiveDeref(mManager, prime);
    742 //            return nullptr;
    743 //        }
    744 //        Cudd_Ref(h);
    745 //        Cudd_RecursiveDeref(mManager, g);
    746 
    747 //        g = h;
    748 //        if (LLVM_UNLIKELY(Cudd_BddToCubeArray(mManager, prime, cube) == 0)) {
    749 //            Cudd_RecursiveDeref(mManager, g);
    750 //            Cudd_RecursiveDeref(mManager, prime);
    751 //            return nullptr;
    752 //        }
    753 //        Cudd_RecursiveDeref(mManager, prime);
    754 
    755 //        assert (DQ.empty() && CQ.empty());
    756 
    757 //        for (auto i = 0; i != n; ++i) {
    758 //            assert (cube[i] >= 0 && cube[i] <= 2);
    759 //            if (cube[i] == 0) {
    760 //                DQ.push_back(mVariables[i]);
    761 //                CQ.push_back(builder.createOnes());
    762 //            } else if (cube[i] == 1) {
    763 //                CQ.push_back(mVariables[i]);
    764 //                DQ.push_back(builder.createZeroes());
    765 //            }
    766 //        }
    767 
    768 //        if (LLVM_UNLIKELY(DQ.empty() && CQ.empty())) {
    769 //            throw std::runtime_error("Error! statement contains no elements!");
    770 //        }
    771 
    772 //        if (DQ.size() > 0) {
    773 //            while (DQ.size() > 1) {
    774 //                PabloAST * v1 = DQ.front(); DQ.pop_front();
    775 //                PabloAST * v2 = DQ.front(); DQ.pop_front();
    776 //                DQ.push_back(builder.createOr(v1, v2));
    777 //            }
    778 //            CQ.push_back(builder.createNot(DQ.front()));
    779 //            DQ.pop_front();
    780 //        }
    781 
    782 //        assert (!CQ.empty());
    783 //        while (CQ.size() > 1) {
    784 //            PabloAST * v1 = CQ.front(); CQ.pop_front();
    785 //            PabloAST * v2 = CQ.front(); CQ.pop_front();
    786 //            CQ.push_back(builder.createAnd(v1, v2));
    787 //        }
    788 //        SQ.push(CQ.front()); CQ.pop_front();
    789 //    }
    790 //    Cudd_RecursiveDeref(mManager, g);
    791 
    792 //    if (LLVM_UNLIKELY(SQ.empty())) {
    793 //        throw std::runtime_error("Error! statement queue empty!");
    794 //    }
    795 
    796 //    while (SQ.size() > 1) {
    797 //        PabloAST * v1 = SQ.front(); SQ.pop();
    798 //        PabloAST * v2 = SQ.front(); SQ.pop();
    799 //        SQ.push(builder.createOr(v1, v2));
    800 //    }
    801 //    return SQ.front();
    802 //}
     202    return std::make_pair(bdd, true);
     203}
    803204
    804205/** ------------------------------------------------------------------------------------------------------------- *
     
    820221}
    821222
    822 inline bool BDDMinimizationPass::isZero(DdNode * const x) const {
    823     return x == Zero();
     223inline bool BDDMinimizationPass::nonConstant(DdNode * const x) const {
     224    return x != Zero() && x != One();
    824225}
    825226
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_bddminimization.h

    r4741 r4748  
    22#define PABLO_BDDMINIMIZATION_H
    33
    4 #include <llvm/ADT/DenseMap.h>
     4#include <unordered_map>
     5#include <vector>
    56
    67struct DdManager; // forward declare of the CUDD manager
     
    1718class BDDMinimizationPass {
    1819
    19     using CharacterizationMap = llvm::DenseMap<const PabloAST *, DdNode *>;
    20     using ReverseCharacterizationMap = llvm::DenseMap<const DdNode *, PabloAST *>;
     20    using CharacterizationMap = std::unordered_map<const PabloAST *, DdNode *>;
    2121    using Terminals = std::vector<Statement *>;
    2222
     
    2424        SubsitutionMap(SubsitutionMap * parent = nullptr) : mParent(parent) {}
    2525
    26         PabloAST * operator [](const DdNode * node) const {
     26        PabloAST * get(const DdNode * node) const {
    2727            auto f = mMap.find(node);
    2828            if (f == mMap.end()) {
    29                 return mParent ? mParent->operator [](node) : nullptr;
     29                return mParent ? mParent->get(node) : nullptr;
    3030            }
    3131            return f->second;
     
    3737    private:
    3838        const SubsitutionMap * const mParent;
    39         llvm::DenseMap<const DdNode *, PabloAST *> mMap;
     39        std::unordered_map<const DdNode *, PabloAST *> mMap;
    4040    };
    4141
    4242public:
    43     static bool optimize(PabloFunction & function, const bool full = false);
     43    static bool optimize(PabloFunction & function);
    4444protected:
    4545    void eliminateLogicallyEquivalentStatements(PabloFunction & function);
    4646    void eliminateLogicallyEquivalentStatements(PabloBlock & block, SubsitutionMap & parent);
    47     DdNode * eliminateLogicallyEquivalentStatements(const Statement * const stmt);
    48     void simplifyAST(PabloFunction & function);
    49     void promoteSimpleInputDerivationsToAssigns(PabloFunction & function);
    50     void simplifyAST(PabloBlock & block, Terminals && terminals);
    51     DdNode * characterizeTerminal(PabloAST * expr);
    52     PabloAST * simplifyAST(DdNode * const f, PabloBlock &block);
    53     PabloAST * makeCoverAST(DdNode * const f, PabloBlock &block);
     47    void eliminateLogicallyEquivalentStatements(Statement * const stmt, SubsitutionMap & map);
     48    std::pair<DdNode *, bool> characterize(Statement * const stmt);
    5449private:
    5550    DdNode * Zero() const;
    5651    DdNode * One() const;
    57     bool isZero(DdNode * const x) const;
     52    bool nonConstant(DdNode * const x) const;
    5853    DdNode * And(DdNode * const x, DdNode * const y);
    5954    DdNode * Intersect(DdNode * const x, DdNode * const y);
     
    6964    std::vector<PabloAST *>         mVariables;
    7065    CharacterizationMap             mCharacterizationMap;
    71     ReverseCharacterizationMap      mLookupMap;
    7266};
    7367
Note: See TracChangeset for help on using the changeset viewer.