source: icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_bddminimization.cpp @ 4852

Last change on this file since 4852 was 4804, checked in by nmedfort, 4 years ago

Bug fixes

File size: 10.3 KB
Line 
1#include "pablo_bddminimization.h"
2#include <pablo/codegenstate.h>
3#include <pablo/builder.hpp>
4#include <pablo/printer_pablos.h>
5#include <cudd.h>
6#include <util.h>
7#include <pablo/optimizers/pablo_simplifier.hpp>
8#include <pablo/analysis/pabloverifier.hpp>
9#include <stack>
10
11using namespace llvm;
12using namespace boost;
13using namespace boost::container;
14
15namespace pablo {
16
17using TypeId = PabloAST::ClassTypeId;
18
19bool BDDMinimizationPass::optimize(PabloFunction & function) {
20    BDDMinimizationPass am;
21    am.initialize(function);
22    am.eliminateLogicallyEquivalentStatements(function);
23    am.shutdown();
24    #ifndef NDEBUG
25    PabloVerifier::verify(function, "post-bdd-minimization");
26    #endif
27    return Simplifier::optimize(function);
28}
29
30/** ------------------------------------------------------------------------------------------------------------- *
31 * @brief initialize
32 *
33 * Scan through the program to identify any advances and calls then initialize the BDD engine with
34 * the proper variable ordering.
35 ** ------------------------------------------------------------------------------------------------------------- */
36void BDDMinimizationPass::initialize(PabloFunction & function) {
37
38    std::stack<Statement *> scope;
39    unsigned variableCount = 0; // number of statements that cannot always be categorized without generating a new variable
40
41    for (const Statement * stmt = function.getEntryBlock().front(); ; ) {
42        while ( stmt ) {
43            if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
44                // Set the next statement to be the first statement of the inner scope and push the
45                // next statement of the current statement into the scope stack.
46                const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
47                scope.push(stmt->getNextNode());
48                stmt = nested.front();
49                assert (stmt);
50                continue;
51            }
52            switch (stmt->getClassTypeId()) {
53                case TypeId::Advance:
54                case TypeId::Call:
55                case TypeId::MatchStar:
56                case TypeId::ScanThru:
57                    ++variableCount;
58                    break;
59                default: break;
60            }
61            stmt = stmt->getNextNode();
62        }
63        if (scope.empty()) {
64            break;
65        }
66        stmt = scope.top();
67        scope.pop();
68    }
69
70    // 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);
74    // Map the predefined 0/1 entries
75    mCharacterizationMap[PabloBlock::createZeroes()] = Zero();
76    mCharacterizationMap[PabloBlock::createOnes()] = One();
77    // Order the variables so the input Vars are pushed to the end; they ought to
78    // 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);
85}
86
87/** ------------------------------------------------------------------------------------------------------------- *
88 * @brief eliminateLogicallyEquivalentStatements
89 ** ------------------------------------------------------------------------------------------------------------- */
90void BDDMinimizationPass::eliminateLogicallyEquivalentStatements(PabloFunction & function) {
91    SubsitutionMap baseMap;
92    baseMap.insert(Zero(), function.getEntryBlock().createZeroes());
93    baseMap.insert(One(), function.getEntryBlock().createOnes());
94    eliminateLogicallyEquivalentStatements(function.getEntryBlock(), baseMap);
95}
96
97/** ------------------------------------------------------------------------------------------------------------- *
98 * @brief eliminateLogicallyEquivalentStatements
99 ** ------------------------------------------------------------------------------------------------------------- */
100void BDDMinimizationPass::eliminateLogicallyEquivalentStatements(PabloBlock & block, SubsitutionMap & parent) {
101    SubsitutionMap map(&parent);
102    Statement * stmt = block.front();
103    while (stmt) {
104        if (LLVM_UNLIKELY(isa<If>(stmt))) {
105            eliminateLogicallyEquivalentStatements(cast<If>(stmt)->getBody(), map);
106        } else if (LLVM_UNLIKELY(isa<While>(stmt))) {
107            eliminateLogicallyEquivalentStatements(cast<While>(stmt)->getBody(), map);
108            for (Next * var : cast<const While>(stmt)->getVariants()) {
109                if (!escapes(var)) {
110                    Cudd_RecursiveDeref(mManager, mCharacterizationMap[var]);
111                    mCharacterizationMap.erase(var);
112                }
113            }
114        } else { // attempt to characterize this statement and replace it if we've encountered an equivalent one
115
116            /// TODO: I found evidence that some of the UCD functions have disjunctions of nested marker values
117            /// in which one is a superset of the other. It's not safe to eliminate the subset marker unless the
118            /// condition that lead us to compute the first marker is a superset of the condition that let us
119            /// compute the subset value too. We can alter the superset condition to include the union of both
120            /// but this may lead to taking an expensive branch more often. So, we'd need to decide whether the
121            /// cost of each scope is close enough w.r.t. the probability both branches are taken.
122
123            DdNode * bdd = nullptr;
124            bool test = false;
125            std::tie(bdd, test) = characterize(stmt);
126            if (test) {
127                PabloAST * replacement = map.get(bdd);
128                if (LLVM_UNLIKELY(replacement != nullptr)) {
129                    Cudd_RecursiveDeref(mManager, bdd);
130                    stmt = stmt->replaceWith(replacement, false, true);
131                    continue;
132                }
133            } else if (LLVM_LIKELY(nonConstant(bdd))) {
134                map.insert(bdd, stmt);
135            }
136            mCharacterizationMap.emplace(stmt, bdd);
137        }
138        stmt = stmt->getNextNode();
139    }   
140}
141
142/** ------------------------------------------------------------------------------------------------------------- *
143 * @brief characterize
144 ** ------------------------------------------------------------------------------------------------------------- */
145inline std::pair<DdNode *, bool> BDDMinimizationPass::characterize(Statement * const stmt) {
146
147    DdNode * bdd = nullptr;
148    // Map our operands to the computed BDDs
149    std::array<DdNode *, 3> input;
150    for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
151        PabloAST * const op = stmt->getOperand(i);
152        if (op == nullptr) {
153            throw std::runtime_error("Statement has Null operand!");
154        }
155        if (LLVM_UNLIKELY(isa<Integer>(op) || isa<String>(op))) {
156            continue;
157        }
158        auto f = mCharacterizationMap.find(op);
159        if (LLVM_UNLIKELY(f == mCharacterizationMap.end())) {
160            std::string tmp;
161            llvm::raw_string_ostream msg(tmp);
162            msg << "BDDMinimizationPass: uncharacterized operand " << std::to_string(i);
163            PabloPrinter::print(stmt, " of ", msg);
164            throw std::runtime_error(msg.str());
165        }
166        input[i] = f->second;
167    }
168
169    switch (stmt->getClassTypeId()) {
170        case TypeId::Assign:
171        case TypeId::Next:
172            return std::make_pair(input[0], false);
173        case TypeId::And:
174            bdd = And(input[0], input[1]);
175            break;
176        case TypeId::Or:
177            bdd = Or(input[0], input[1]);
178            break;
179        case TypeId::Xor:
180            bdd = Xor(input[0], input[1]);
181            break;
182        case TypeId::Not:
183            bdd = Not(input[0]);
184            break;
185        case TypeId::Sel:
186            bdd = Ite(input[0], input[1], input[2]);
187            break;
188        case TypeId::MatchStar:
189        case TypeId::ScanThru:
190            if (LLVM_UNLIKELY(input[1] == Zero())) {
191                return std::make_pair(Zero(), true);
192            }
193        case TypeId::Advance:
194            if (LLVM_UNLIKELY(input[0] == Zero())) {
195                return std::make_pair(Zero(), true);
196            }
197        case TypeId::Call:
198            // 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);
200        default:
201            throw std::runtime_error("Unexpected statement type " + stmt->getName()->to_string());
202    }
203    Cudd_Ref(bdd);
204    if (LLVM_UNLIKELY(noSatisfyingAssignment(bdd))) {
205        Cudd_RecursiveDeref(mManager, bdd);
206        bdd = Zero();
207    }
208    return std::make_pair(bdd, true);
209}
210
211/** ------------------------------------------------------------------------------------------------------------- *
212 * @brief CUDD wrappers
213 ** ------------------------------------------------------------------------------------------------------------- */
214
215inline DdNode * BDDMinimizationPass::Zero() const {
216    return Cudd_ReadLogicZero(mManager);
217}
218
219inline DdNode * BDDMinimizationPass::One() const {
220    return Cudd_ReadOne(mManager);
221}
222
223inline DdNode * BDDMinimizationPass::NewVar(const PabloAST *) {
224    return Cudd_bddIthVar(mManager, mVariables++);
225}
226
227inline bool BDDMinimizationPass::nonConstant(DdNode * const x) const {
228    return x != Zero() && x != One();
229}
230
231inline DdNode * BDDMinimizationPass::And(DdNode * const x, DdNode * const y) {
232    return Cudd_bddAnd(mManager, x, y);
233}
234
235inline DdNode * BDDMinimizationPass::Or(DdNode * const x, DdNode * const y) {
236    return Cudd_bddOr(mManager, x, y);
237}
238
239inline DdNode * BDDMinimizationPass::Xor(DdNode * const x, DdNode * const y) {
240    return Cudd_bddXor(mManager, x, y);
241}
242
243inline DdNode * BDDMinimizationPass::Not(DdNode * const x) const {
244    return Cudd_Not(x);
245}
246
247inline DdNode * BDDMinimizationPass::Ite(DdNode * const x, DdNode * const y, DdNode * const z) {
248    return Cudd_bddIte(mManager, x, y, z);
249}
250
251inline bool BDDMinimizationPass::noSatisfyingAssignment(DdNode * const x) {
252    return Cudd_bddLeq(mManager, x, Zero());
253}
254
255inline void BDDMinimizationPass::shutdown() {
256    Cudd_Quit(mManager);
257    mCharacterizationMap.clear();
258}
259
260} // end of namespace pablo
261
Note: See TracBrowser for help on using the repository browser.