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

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

First (hopefully) working version of the boolean reassociation pass + some bug fixes.

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