 Timestamp:
 Nov 12, 2015, 4:26:25 PM (4 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

icGREP/icgrepdevel/icgrep/pablo/optimizers/pablo_bddminimization.cpp
r4804 r4868 3 3 #include <pablo/builder.hpp> 4 4 #include <pablo/printer_pablos.h> 5 #include <cudd.h>6 #include <util.h>7 5 #include <pablo/optimizers/pablo_simplifier.hpp> 8 6 #include <pablo/analysis/pabloverifier.hpp> 9 7 #include <stack> 8 #include <bdd.h> 10 9 11 10 using namespace llvm; … … 16 15 17 16 using 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? 18 21 19 22 bool BDDMinimizationPass::optimize(PabloFunction & function) { … … 21 24 am.initialize(function); 22 25 am.eliminateLogicallyEquivalentStatements(function); 23 am.shutdown();26 bdd_done(); 24 27 #ifndef NDEBUG 25 28 PabloVerifier::verify(function, "postbddminimization"); … … 37 40 38 41 std::stack<Statement *> scope; 39 unsigned variableCount = 0; // number of statements that cannot always be categorized without generating a new variable40 42 unsigned variableCount = function.getNumOfParameters(); // number of statements that cannot always be categorized without generating a new variable 43 unsigned statementCount = 0; 41 44 for (const Statement * stmt = function.getEntryBlock().front(); ; ) { 42 45 while ( stmt ) { … … 50 53 continue; 51 54 } 55 ++statementCount; 52 56 switch (stmt>getClassTypeId()) { 53 57 case TypeId::Advance: … … 69 73 70 74 // 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 74 81 // 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(); 77 84 // Order the variables so the input Vars are pushed to the end; they ought to 78 85 // 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 } 85 89 } 86 90 … … 90 94 void BDDMinimizationPass::eliminateLogicallyEquivalentStatements(PabloFunction & function) { 91 95 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()); 94 98 eliminateLogicallyEquivalentStatements(function.getEntryBlock(), baseMap); 95 99 } … … 108 112 for (Next * var : cast<const While>(stmt)>getVariants()) { 109 113 if (!escapes(var)) { 110 Cudd_RecursiveDeref(mManager,mCharacterizationMap[var]);114 bdd_delref(mCharacterizationMap[var]); 111 115 mCharacterizationMap.erase(var); 112 116 } … … 121 125 /// cost of each scope is close enough w.r.t. the probability both branches are taken. 122 126 123 DdNode * bdd = nullptr;127 BDD bdd = bdd_zero(); 124 128 bool test = false; 125 129 std::tie(bdd, test) = characterize(stmt); … … 127 131 PabloAST * replacement = map.get(bdd); 128 132 if (LLVM_UNLIKELY(replacement != nullptr)) { 129 Cudd_RecursiveDeref(mManager,bdd);133 bdd_delref(bdd); 130 134 stmt = stmt>replaceWith(replacement, false, true); 131 135 continue; 132 136 } 133 } else if (LLVM_LIKELY( nonConstant(bdd))) {137 } else if (LLVM_LIKELY(!bdd_constant(bdd))) { 134 138 map.insert(bdd, stmt); 135 139 } … … 143 147 * @brief characterize 144 148 **  */ 145 inline std::pair< DdNode *, bool> BDDMinimizationPass::characterize(Statement * const stmt) {146 147 DdNode * bdd = nullptr;149 inline std::pair<BDD, bool> BDDMinimizationPass::characterize(Statement * const stmt) { 150 151 BDD bdd = bdd_zero(); 148 152 // Map our operands to the computed BDDs 149 std::array< DdNode *, 3> input;153 std::array<BDD, 3> input; 150 154 for (unsigned i = 0; i != stmt>getNumOperands(); ++i) { 151 155 PabloAST * const op = stmt>getOperand(i); … … 172 176 return std::make_pair(input[0], false); 173 177 case TypeId::And: 174 bdd = And(input[0], input[1]);178 bdd = bdd_and(input[0], input[1]); 175 179 break; 176 180 case TypeId::Or: 177 bdd = Or(input[0], input[1]);181 bdd = bdd_or(input[0], input[1]); 178 182 break; 179 183 case TypeId::Xor: 180 bdd = Xor(input[0], input[1]);184 bdd = bdd_xor(input[0], input[1]); 181 185 break; 182 186 case TypeId::Not: 183 bdd = Not(input[0]);187 bdd = bdd_not(input[0]); 184 188 break; 185 189 case TypeId::Sel: 186 bdd = Ite(input[0], input[1], input[2]);190 bdd = bdd_ite(input[0], input[1], input[2]); 187 191 break; 188 192 case TypeId::MatchStar: 189 193 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]; 192 196 } 193 197 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); 196 200 } 197 201 case TypeId::Call: 198 202 // 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); 200 204 default: 201 205 throw std::runtime_error("Unexpected statement type " + stmt>getName()>to_string()); 202 206 } 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(); 207 211 } 208 212 return std::make_pair(bdd, true); 209 213 } 210 214 211 /**  *212 * @brief CUDD wrappers213 **  */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 260 215 } // end of namespace pablo 261 216
Note: See TracChangeset
for help on using the changeset viewer.