Ignore:
Timestamp:
Aug 16, 2015, 4:23:57 PM (4 years ago)
Author:
nmedfort
Message:

More minimization work.

File:
1 edited

Legend:

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

    r4725 r4727  
    1212#include <pablo/optimizers/pablo_simplifier.hpp>
    1313#include <boost/container/flat_set.hpp>
     14#include <boost/container/flat_map.hpp>
     15#include <boost/graph/adjacency_list.hpp>
    1416
    1517using namespace llvm;
     
    2123bool BDDMinimizationPass::optimize(PabloFunction & function, const bool full) {
    2224    BDDMinimizationPass am;
    23     am.eliminateLogicallyEquivalentStatements(function);
    2425    if (full) {
    2526        am.simplifyAST(function);
    2627    }
     28    am.eliminateLogicallyEquivalentStatements(function);
    2729    return Simplifier::optimize(function);
    2830}
     
    196198 ** ------------------------------------------------------------------------------------------------------------- */
    197199inline void BDDMinimizationPass::simplifyAST(PabloFunction & function) {
    198     PabloBuilder builder(function.getEntryBlock());
    199     std::vector<Statement *> terminals;
     200    Terminals terminals;
    200201    for (unsigned i = 0; i != function.getNumOfResults(); ++i) {
    201202        terminals.push_back(function.getResult(i));
    202203    }
    203     simplifyAST(builder, terminals);
    204 }
     204    simplifyAST(function.getEntryBlock(), std::move(terminals));
     205}
     206
     207/** ------------------------------------------------------------------------------------------------------------- *
     208 * @brief promoteSimpleInputDerivationsToAssigns
     209 ** ------------------------------------------------------------------------------------------------------------- */
     210inline void BDDMinimizationPass::promoteSimpleInputDerivationsToAssigns(PabloFunction & function) {
     211
     212    using Graph = adjacency_list<hash_setS, vecS, bidirectionalS, PabloAST *>;
     213    using Vertex = Graph::vertex_descriptor;
     214
     215    Graph G;
     216    flat_map<PabloAST *, Vertex> M;
     217    std::queue<Vertex> Q;
     218    for (unsigned i = 0; i != function.getNumOfParameters(); ++i) {
     219        PabloAST * var = function.getParameter(i);
     220        const Vertex u = add_vertex(var, G);
     221        Q.push(u);
     222        M[var] = u;
     223    }
     224
     225    for (;;) {
     226        const Vertex u = Q.front(); Q.pop();
     227        for (PabloAST * user : G[u]->users()) {
     228            auto f = M.find(user);
     229            Vertex v = 0;
     230            if (f == M.end()) {
     231                v = add_vertex(user, G);
     232                switch (user->getClassTypeId()) {
     233                    case PabloAST::ClassTypeId::And:
     234                    case PabloAST::ClassTypeId::Or:
     235                    case PabloAST::ClassTypeId::Not:
     236                    case PabloAST::ClassTypeId::Xor:
     237                    case PabloAST::ClassTypeId::Sel:
     238                        Q.push(v);
     239                    default:
     240                        M[user] = v;
     241                }
     242            } else {
     243                v = f->second;
     244            }
     245            add_edge(u, v, G);
     246        }
     247
     248        if (Q.empty()) {
     249            break;
     250        }
     251    }
     252
     253    flat_set<Statement *> promotions;
     254
     255    for (Vertex u : make_iterator_range(vertices(G))) {
     256        if (out_degree(u, G) == 0) {
     257            Statement * stmt = cast<Statement>(G[u]);
     258            if (isa<Assign>(stmt)) {
     259                continue;
     260            }
     261            for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
     262                if (Statement * expr = dyn_cast<Statement>(stmt->getOperand(i))) {
     263                    promotions.insert(expr);
     264                }
     265            }
     266        }
     267    }
     268
     269    for (Statement * promoted : promotions) {
     270        PabloBlock * block = promoted->getParent();
     271        block->setInsertPoint(promoted);
     272        Assign * replacement = block->createAssign("t", promoted);
     273        promoted->replaceAllUsesWith(replacement);
     274    }
     275
     276    raw_os_ostream out(std::cerr);
     277    PabloPrinter::print(function.getEntryBlock().statements(), out);
     278    out << "**************************************\n";
     279    out.flush();
     280}
     281
    205282
    206283/** ------------------------------------------------------------------------------------------------------------- *
     
    212289        case PabloAST::ClassTypeId::Or:
    213290        case PabloAST::ClassTypeId::Not:
    214         case PabloAST::ClassTypeId::Sel:
     291//        case PabloAST::ClassTypeId::Sel:
    215292            return cast<Statement>(expr)->getParent() == pb;
    216293        default:
     
    222299 * @brief simplifyAST
    223300 ** ------------------------------------------------------------------------------------------------------------- */
    224 void BDDMinimizationPass::simplifyAST(PabloBuilder & block, std::vector<Statement *> & terminals) {
     301void BDDMinimizationPass::simplifyAST(PabloBlock & block, Terminals && terminals) {
    225302
    226303    for (Statement * stmt : block) {
    227         if (isa<While>(stmt)) {
    228             PabloBuilder builder(cast<If>(stmt)->getBody(), block);
    229             std::vector<Statement *> terminals;
     304        if (isa<If>(stmt)) {
     305            Terminals terminals;
    230306            for (Assign * var : cast<const If>(stmt)->getDefined()) {
    231307                terminals.push_back(var);
    232308            }
    233             simplifyAST(builder, terminals);
    234             for (Assign * var : cast<const If>(stmt)->getDefined()) {
    235                 block.record(var);
    236             }
    237             continue;
     309            simplifyAST(cast<If>(stmt)->getBody(), std::move(terminals));
     310//            for (Assign * var : cast<const If>(stmt)->getDefined()) {
     311//                block.record(var);
     312//            }
     313//            continue;
    238314        } else if (isa<While>(stmt)) {
    239             PabloBuilder builder(cast<While>(stmt)->getBody(), block);
    240             std::vector<Statement *> terminals;
     315            Terminals terminals;
    241316            for (Next * var : cast<const While>(stmt)->getVariants()) {
    242317                terminals.push_back(var);
    243318            }
    244             simplifyAST(builder, terminals);
    245             for (Next * var : cast<const While>(stmt)->getVariants()) {
    246                 block.record(var);
    247             }
    248             continue;
    249         }
    250         block.record(stmt);
    251     }
    252 
    253     std::queue<Statement *> Q;
    254     std::vector<PabloAST *> variables;
    255 
    256     while (!terminals.empty()) {
    257 
     319            simplifyAST(cast<While>(stmt)->getBody(), std::move(terminals));
     320//            for (Next * var : cast<const While>(stmt)->getVariants()) {
     321//                block.record(var);
     322//            }
     323//            continue;
     324        }
     325        // block.record(stmt);
     326    }
     327
     328    for (;;) {
     329
     330        flat_set<Statement *> inputs;
    258331        for (Statement * term : terminals) {
     332            for (unsigned i = 0; i != term->getNumOperands(); ++i) {
     333                if (isSimplifiable(term->getOperand(i), term->getParent())) {
     334                    inputs.insert(cast<Statement>(term->getOperand(i)));
     335                }
     336            }
     337        }
     338
     339        if (inputs.empty()) {
     340            break;
     341        }
     342
     343        std::queue<Statement *> Q;
     344        for (Statement * term : inputs) {
    259345            Q.push(term);
    260346        }
    261347
     348        flat_set<PabloAST *> visited;
     349        flat_set<PabloAST *> variables;
    262350        // find the variables for this set of terminals
    263351        for (;;) {
    264352            Statement * stmt = Q.front();
    265353            Q.pop();
    266             mCharacterizationMap[stmt] = nullptr;
    267354            for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
    268                 if (isSimplifiable(stmt->getOperand(i), stmt->getParent())) {
    269                     Q.push(cast<Statement>(stmt->getOperand(i)));
    270                 } else {
    271                     variables.push_back(stmt->getOperand(i));
     355                if (visited.count(stmt->getOperand(i)) == 0) {
     356                    if (isSimplifiable(stmt->getOperand(i), stmt->getParent())) {
     357                        Q.push(cast<Statement>(stmt->getOperand(i)));
     358                    } else {
     359                        variables.insert(stmt->getOperand(i));
     360                    }
     361                    visited.insert(stmt->getOperand(i));
    272362                }
    273363            }
     
    277367        }
    278368
    279         std::sort(variables.begin(), variables.end());
    280         std::unique(variables.begin(), variables.end());
    281 
    282 
     369        mVariables.clear();
    283370        mManager = Cudd_Init(variables.size(), 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0);
    284371        Cudd_AutodynEnable(mManager, CUDD_REORDER_LAZY_SIFT);
    285 
    286         unsigned i = 0;
    287372        for (PabloAST * var : variables) {
    288             mCharacterizationMap[var] = Cudd_bddIthVar(mManager, i++);
    289         }
    290 
    291         for (PabloAST * term : terminals) {
    292             characterizeTerminalBddTree(term);
    293         }
     373            mCharacterizationMap.insert(std::make_pair(var, Cudd_bddIthVar(mManager, mVariables.size())));
     374            mVariables.push_back(var);
     375        }
     376
     377
     378        std::vector<DdNode *> nodes;
     379        for (PabloAST * term : inputs) {
     380            nodes.push_back(characterizeTerminal(term));
     381        }
     382        Cudd_AutodynDisable(mManager);
    294383        Cudd_ReduceHeap(mManager, CUDD_REORDER_SIFT, 0);
    295384
    296         for (Statement * term : terminals) {
    297             DdNode * const f = mCharacterizationMap[term];
     385        visited.clear();
     386        for (Statement * input : inputs) {
     387            DdNode * const f = mCharacterizationMap[input]; assert (f);
    298388            Cudd_Ref(f);
    299             PabloAST * replacement = simplifyAST(f, variables, block);
     389            block.setInsertPoint(input);
     390            PabloBuilder builder(block);
     391            PabloAST * replacement = simplifyAST(f, builder);
    300392            if (replacement) {
    301                 term->replaceWith(replacement, false, true);
     393                input->replaceWith(replacement, false, true);
    302394            }
    303395            Cudd_RecursiveDeref(mManager, f);
     
    311403        terminals.clear();
    312404        for (PabloAST * var : variables) {
    313             if (isa<Statement>(var) && cast<Statement>(var)->getParent() == block.getPabloBlock()) {
     405            if (LLVM_LIKELY(isa<Statement>(var) && cast<Statement>(var)->getParent() == &block)) {
    314406                terminals.push_back(cast<Statement>(var));
    315407            }
    316408        }
    317     }
    318 
    319 }
    320 
    321 ///** ------------------------------------------------------------------------------------------------------------- *
    322 // * @brief simplifyAST
    323 // ** ------------------------------------------------------------------------------------------------------------- */
    324 DdNode * BDDMinimizationPass::characterizeTerminalBddTree(PabloAST * expr) {
    325 
     409
     410        if (terminals.empty()) {
     411            break;
     412        }
     413
     414    }
     415
     416}
     417
     418/** ------------------------------------------------------------------------------------------------------------- *
     419 * @brief characterizeTerminal
     420 ** ------------------------------------------------------------------------------------------------------------- */
     421DdNode * BDDMinimizationPass::characterizeTerminal(PabloAST * expr) {
    326422    const auto f = mCharacterizationMap.find(expr);
    327     if (f == mCharacterizationMap.end()) {
    328         return nullptr;
    329     } else if (f->second) {
     423    if (f != mCharacterizationMap.end()) {
    330424        return f->second;
    331425    }
    332 
    333     Statement * stmt = cast<Statement>(expr);
    334426    std::array<DdNode *, 3> input;
    335 
    336     for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
    337         input[i] = characterizeTerminalBddTree(stmt->getOperand(i));
    338     }
    339 
     427    for (unsigned i = 0; i != cast<Statement>(expr)->getNumOperands(); ++i) {
     428        input[i] = characterizeTerminal(cast<Statement>(expr)->getOperand(i)); assert (input[i]);
     429    }
    340430    DdNode * bdd = nullptr;
    341431    switch (expr->getClassTypeId()) {
     
    349439            bdd = Not(input[0]);
    350440            break;
    351         case PabloAST::ClassTypeId::Sel:
    352             bdd = Ite(input[0], input[1], input[2]);
    353             break;
     441//        case PabloAST::ClassTypeId::Sel:
     442//            bdd = Ite(input[0], input[1], input[2]);
     443//            break;
    354444        default:
    355             throw std::runtime_error("Unexpected operand given to BDDMinimizationPass::characterizeTerminalBddTree!");
     445            return nullptr;
    356446    }
    357447    Cudd_Ref(bdd);
     448    mCharacterizationMap.insert(std::make_pair(expr, bdd));
    358449    return bdd;
    359450}
     
    362453 * @brief simplifyAST
    363454 ** ------------------------------------------------------------------------------------------------------------- */
    364 PabloAST * BDDMinimizationPass::simplifyAST(DdNode * const f, const std::vector<PabloAST *> & variables, PabloBuilder & builder) {
     455PabloAST * BDDMinimizationPass::simplifyAST(DdNode * const f, PabloBuilder &block) {
    365456    assert (!noSatisfyingAssignment(f));
    366457    DdNode * g = Cudd_FindEssential(mManager, f);
    367458    if (g && Cudd_SupportSize(mManager, g) > 0) {
    368459        if (g == f) { // every variable is essential
    369             return makeCoverAST(f, variables, builder);
     460            return makeCoverAST(f, block);
    370461        }
    371462        Cudd_Ref(g);
    372         PabloAST * c0 = makeCoverAST(g, variables, builder);
     463        PabloAST * c0 = makeCoverAST(g, block);
    373464        if (LLVM_UNLIKELY(c0 == nullptr)) {
    374465            Cudd_RecursiveDeref(mManager, g);
     
    377468        DdNode * h = Cudd_Cofactor(mManager, f, g);
    378469        Cudd_Ref(h);
    379         PabloAST * c1 = simplifyAST(h, variables, builder);
     470        PabloAST * c1 = simplifyAST(h, block);
    380471        if (LLVM_UNLIKELY(c1 == nullptr)) {
    381472            Cudd_RecursiveDeref(mManager, g);
     
    387478        Cudd_RecursiveDeref(mManager, g);
    388479        Cudd_RecursiveDeref(mManager, h);
    389         return builder.createAnd(c0, c1, "escf");
     480        return block.createAnd(c0, c1, "t");
    390481    }
    391482
     
    417508        Cudd_Ref(decomp[0]);
    418509        Cudd_Ref(decomp[1]);
    419         PabloAST * d0 = simplifyAST(decomp[0], variables, builder);
     510        PabloAST * d0 = simplifyAST(decomp[0], block);
    420511        Cudd_RecursiveDeref(mManager, decomp[0]);
    421512        if (LLVM_UNLIKELY(d0 == nullptr)) {
     
    424515        }
    425516
    426         PabloAST * d1 = simplifyAST(decomp[1], variables, builder);
     517        PabloAST * d1 = simplifyAST(decomp[1], block);
    427518        Cudd_RecursiveDeref(mManager, decomp[1]);
    428519        if (LLVM_UNLIKELY(d1 == nullptr)) {
     
    432523
    433524        if (disjuncts == 2) {
    434             return builder.createOr(d0, d1, "disj");
     525            return block.createOr(d0, d1, "t");
    435526        } else {
    436             return builder.createAnd(d0, d1, "conj");
    437         }
    438     }
    439     return makeCoverAST(f, variables, builder);
     527            return block.createAnd(d0, d1, "t");
     528        }
     529    }
     530    return makeCoverAST(f, block);
    440531}
    441532
     
    443534 * @brief makeCoverAST
    444535 ** ------------------------------------------------------------------------------------------------------------- */
    445 PabloAST * BDDMinimizationPass::makeCoverAST(DdNode * const f, const std::vector<PabloAST *> & variables, PabloBuilder & builder) {
     536PabloAST * BDDMinimizationPass::makeCoverAST(DdNode * const f, PabloBuilder & block) {
    446537
    447538    std::queue<PabloAST *> SQ;
    448     const unsigned n = variables.size();
    449     circular_buffer<PabloAST *> CQ(n);
    450     circular_buffer<PabloAST *> DQ(n);
    451 
    452     assert (mManager->size == variables.size());
     539    const auto n = mVariables.size();
     540    circular_buffer<PabloAST *> CQ(n + 1);
     541    circular_buffer<PabloAST *> DQ(n + 1);
     542
     543    assert (mManager->size == n);
    453544
    454545    int cube[n];
     
    497588            assert (cube[i] >= 0 && cube[i] <= 2);
    498589            if (cube[i] == 0) {
    499                 assert (!DQ.full());
    500                 DQ.push_back(variables[i]);
     590                DQ.push_back(mVariables[i]);
     591                // CQ.push_back(block.createOnes());
    501592            } else if (cube[i] == 1) {
    502                 assert (!CQ.full());
    503                 CQ.push_back(variables[i]);
     593                CQ.push_back(mVariables[i]);
     594                // DQ.push_back(block.createZeroes());
    504595            }
    505596        }
     
    513604                PabloAST * v1 = DQ.front(); DQ.pop_front();
    514605                PabloAST * v2 = DQ.front(); DQ.pop_front();
    515                 DQ.push_back(builder.createOr(v1, v2));
    516             }
    517             CQ.push_back(builder.createNot(DQ.front()));
     606                DQ.push_back(block.createOr(v1, v2));
     607            }
     608            CQ.push_back(block.createNot(DQ.front()));
    518609            DQ.pop_front();
    519610        }
     
    523614            PabloAST * v1 = CQ.front(); CQ.pop_front();
    524615            PabloAST * v2 = CQ.front(); CQ.pop_front();
    525             CQ.push_back(builder.createAnd(v1, v2));
     616            CQ.push_back(block.createAnd(v1, v2));
    526617        }
    527618        SQ.push(CQ.front()); CQ.pop_front();
     
    534625        PabloAST * v1 = SQ.front(); SQ.pop();
    535626        PabloAST * v2 = SQ.front(); SQ.pop();
    536         SQ.push(builder.createOr(v1, v2));
     627        SQ.push(block.createOr(v1, v2));
    537628    }
    538629    return SQ.front();
Note: See TracChangeset for help on using the changeset viewer.