Ignore:
Timestamp:
Nov 12, 2015, 4:26:25 PM (4 years ago)
Author:
nmedfort
Message:

Work on bug fixes for multiplexing pass.

File:
1 edited

Legend:

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

    r4804 r4868  
    33#include <pablo/builder.hpp>
    44#include <pablo/printer_pablos.h>
    5 #include <cudd.h>
    6 #include <util.h>
    75#include <pablo/optimizers/pablo_simplifier.hpp>
    86#include <pablo/analysis/pabloverifier.hpp>
    97#include <stack>
     8#include <bdd.h>
    109
    1110using namespace llvm;
     
    1615
    1716using TypeId = PabloAST::ClassTypeId;
     17
     18// TODO: add in analysis to verify that the outputs of an If would be zero if the If cond is false?
     19
     20// TODO: test whether an If node can be moved into another If body in the same scope?
    1821
    1922bool BDDMinimizationPass::optimize(PabloFunction & function) {
     
    2124    am.initialize(function);
    2225    am.eliminateLogicallyEquivalentStatements(function);
    23     am.shutdown();
     26    bdd_done();
    2427    #ifndef NDEBUG
    2528    PabloVerifier::verify(function, "post-bdd-minimization");
     
    3740
    3841    std::stack<Statement *> scope;
    39     unsigned variableCount = 0; // number of statements that cannot always be categorized without generating a new variable
    40 
     42    unsigned variableCount = function.getNumOfParameters(); // number of statements that cannot always be categorized without generating a new variable
     43    unsigned statementCount = 0;
    4144    for (const Statement * stmt = function.getEntryBlock().front(); ; ) {
    4245        while ( stmt ) {
     
    5053                continue;
    5154            }
     55            ++statementCount;
    5256            switch (stmt->getClassTypeId()) {
    5357                case TypeId::Advance:
     
    6973
    7074    // Initialize the BDD engine ...
    71     mManager = Cudd_Init(variableCount + function.getNumOfParameters() - function.getNumOfResults(), 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0);
    72     mVariables = 0;
    73     Cudd_MakeTreeNode(mManager, 0, function.getNumOfParameters(), MTR_DEFAULT);
     75    bdd_init(1000000, 10000);
     76    bdd_setvarnum(variableCount + function.getNumOfParameters());
     77    bdd_setcacheratio(32);
     78    bdd_setmaxincrease(1000000);
     79    bdd_disable_reorder();
     80
    7481    // Map the predefined 0/1 entries
    75     mCharacterizationMap[PabloBlock::createZeroes()] = Zero();
    76     mCharacterizationMap[PabloBlock::createOnes()] = One();
     82    mCharacterizationMap[PabloBlock::createZeroes()] = bdd_zero();
     83    mCharacterizationMap[PabloBlock::createOnes()] = bdd_one();
    7784    // Order the variables so the input Vars are pushed to the end; they ought to
    7885    // be the most complex to resolve.   
    79     for (auto i = 0; i != function.getNumOfParameters(); ++i) {
    80         mCharacterizationMap[function.getParameter(i)] = NewVar(function.getParameter(i));
    81     }
    82     Cudd_SetSiftMaxVar(mManager, 1000000);
    83     Cudd_SetSiftMaxSwap(mManager, 1000000000);
    84     Cudd_AutodynEnable(mManager, CUDD_REORDER_LAZY_SIFT);
     86    for (mVariables = 0; mVariables != function.getNumOfParameters(); ++mVariables) {
     87        mCharacterizationMap[function.getParameter(mVariables)] = bdd_ithvar(mVariables);
     88    }
    8589}
    8690
     
    9094void BDDMinimizationPass::eliminateLogicallyEquivalentStatements(PabloFunction & function) {
    9195    SubsitutionMap baseMap;
    92     baseMap.insert(Zero(), function.getEntryBlock().createZeroes());
    93     baseMap.insert(One(), function.getEntryBlock().createOnes());
     96    baseMap.insert(bdd_zero(), function.getEntryBlock().createZeroes());
     97    baseMap.insert(bdd_one(), function.getEntryBlock().createOnes());
    9498    eliminateLogicallyEquivalentStatements(function.getEntryBlock(), baseMap);
    9599}
     
    108112            for (Next * var : cast<const While>(stmt)->getVariants()) {
    109113                if (!escapes(var)) {
    110                     Cudd_RecursiveDeref(mManager, mCharacterizationMap[var]);
     114                    bdd_delref(mCharacterizationMap[var]);
    111115                    mCharacterizationMap.erase(var);
    112116                }
     
    121125            /// cost of each scope is close enough w.r.t. the probability both branches are taken.
    122126
    123             DdNode * bdd = nullptr;
     127            BDD bdd = bdd_zero();
    124128            bool test = false;
    125129            std::tie(bdd, test) = characterize(stmt);
     
    127131                PabloAST * replacement = map.get(bdd);
    128132                if (LLVM_UNLIKELY(replacement != nullptr)) {
    129                     Cudd_RecursiveDeref(mManager, bdd);
     133                    bdd_delref(bdd);
    130134                    stmt = stmt->replaceWith(replacement, false, true);
    131135                    continue;
    132136                }
    133             } else if (LLVM_LIKELY(nonConstant(bdd))) {
     137            } else if (LLVM_LIKELY(!bdd_constant(bdd))) {
    134138                map.insert(bdd, stmt);
    135139            }
     
    143147 * @brief characterize
    144148 ** ------------------------------------------------------------------------------------------------------------- */
    145 inline std::pair<DdNode *, bool> BDDMinimizationPass::characterize(Statement * const stmt) {
    146 
    147     DdNode * bdd = nullptr;
     149inline std::pair<BDD, bool> BDDMinimizationPass::characterize(Statement * const stmt) {
     150
     151    BDD bdd = bdd_zero();
    148152    // Map our operands to the computed BDDs
    149     std::array<DdNode *, 3> input;
     153    std::array<BDD, 3> input;
    150154    for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
    151155        PabloAST * const op = stmt->getOperand(i);
     
    172176            return std::make_pair(input[0], false);
    173177        case TypeId::And:
    174             bdd = And(input[0], input[1]);
     178            bdd = bdd_and(input[0], input[1]);
    175179            break;
    176180        case TypeId::Or:
    177             bdd = Or(input[0], input[1]);
     181            bdd = bdd_or(input[0], input[1]);
    178182            break;
    179183        case TypeId::Xor:
    180             bdd = Xor(input[0], input[1]);
     184            bdd = bdd_xor(input[0], input[1]);
    181185            break;
    182186        case TypeId::Not:
    183             bdd = Not(input[0]);
     187            bdd = bdd_not(input[0]);
    184188            break;
    185189        case TypeId::Sel:
    186             bdd = Ite(input[0], input[1], input[2]);
     190            bdd = bdd_ite(input[0], input[1], input[2]);
    187191            break;
    188192        case TypeId::MatchStar:
    189193        case TypeId::ScanThru:
    190             if (LLVM_UNLIKELY(input[1] == Zero())) {
    191                 return std::make_pair(Zero(), true);
     194            if (LLVM_UNLIKELY(input[1] == bdd_zero())) {
     195                bdd = input[0];
    192196            }
    193197        case TypeId::Advance:
    194             if (LLVM_UNLIKELY(input[0] == Zero())) {
    195                 return std::make_pair(Zero(), true);
     198            if (LLVM_UNLIKELY(input[0] == bdd_zero())) {
     199                return std::make_pair(bdd_zero(), true);
    196200            }
    197201        case TypeId::Call:
    198202            // TODO: we may have more than one output. Need to fix call class to allow for it.
    199             return std::make_pair(NewVar(stmt), false);
     203            return std::make_pair(bdd_ithvar(mVariables++), false);
    200204        default:
    201205            throw std::runtime_error("Unexpected statement type " + stmt->getName()->to_string());
    202206    }
    203     Cudd_Ref(bdd);
    204     if (LLVM_UNLIKELY(noSatisfyingAssignment(bdd))) {
    205         Cudd_RecursiveDeref(mManager, bdd);
    206         bdd = Zero();
     207    bdd_addref(bdd);
     208    if (LLVM_UNLIKELY(bdd_satone(bdd) == bdd_zero())) {
     209        bdd_delref(bdd);
     210        bdd = bdd_zero();
    207211    }
    208212    return std::make_pair(bdd, true);
    209213}
    210214
    211 /** ------------------------------------------------------------------------------------------------------------- *
    212  * @brief CUDD wrappers
    213  ** ------------------------------------------------------------------------------------------------------------- */
    214 
    215 inline DdNode * BDDMinimizationPass::Zero() const {
    216     return Cudd_ReadLogicZero(mManager);
    217 }
    218 
    219 inline DdNode * BDDMinimizationPass::One() const {
    220     return Cudd_ReadOne(mManager);
    221 }
    222 
    223 inline DdNode * BDDMinimizationPass::NewVar(const PabloAST *) {
    224     return Cudd_bddIthVar(mManager, mVariables++);
    225 }
    226 
    227 inline bool BDDMinimizationPass::nonConstant(DdNode * const x) const {
    228     return x != Zero() && x != One();
    229 }
    230 
    231 inline DdNode * BDDMinimizationPass::And(DdNode * const x, DdNode * const y) {
    232     return Cudd_bddAnd(mManager, x, y);
    233 }
    234 
    235 inline DdNode * BDDMinimizationPass::Or(DdNode * const x, DdNode * const y) {
    236     return Cudd_bddOr(mManager, x, y);
    237 }
    238 
    239 inline DdNode * BDDMinimizationPass::Xor(DdNode * const x, DdNode * const y) {
    240     return Cudd_bddXor(mManager, x, y);
    241 }
    242 
    243 inline DdNode * BDDMinimizationPass::Not(DdNode * const x) const {
    244     return Cudd_Not(x);
    245 }
    246 
    247 inline DdNode * BDDMinimizationPass::Ite(DdNode * const x, DdNode * const y, DdNode * const z) {
    248     return Cudd_bddIte(mManager, x, y, z);
    249 }
    250 
    251 inline bool BDDMinimizationPass::noSatisfyingAssignment(DdNode * const x) {
    252     return Cudd_bddLeq(mManager, x, Zero());
    253 }
    254 
    255 inline void BDDMinimizationPass::shutdown() {
    256     Cudd_Quit(mManager);
    257     mCharacterizationMap.clear();
    258 }
    259 
    260215} // end of namespace pablo
    261216
Note: See TracChangeset for help on using the changeset viewer.