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

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

Bug fixes for reassociation pass; passes make check.

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