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

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

Temporary check in

File size: 10.3 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            std::string tmp;
159            llvm::raw_string_ostream msg(tmp);
160            msg << "BDDMinimizationPass: uncharacterized operand " << std::to_string(i);
161            PabloPrinter::print(stmt, " of ", msg);
162            throw std::runtime_error(msg.str());
163        }
164        input[i] = f->second;
165    }
166
167    switch (stmt->getClassTypeId()) {
168        case PabloAST::ClassTypeId::Assign:
169        case PabloAST::ClassTypeId::Next:
170            return std::make_pair(input[0], false);
171        case PabloAST::ClassTypeId::And:
172            bdd = And(input[0], input[1]);
173            break;
174        case PabloAST::ClassTypeId::Or:
175            bdd = Or(input[0], input[1]);
176            break;
177        case PabloAST::ClassTypeId::Xor:
178            bdd = Xor(input[0], input[1]);
179            break;
180        case PabloAST::ClassTypeId::Not:
181            bdd = Not(input[0]);
182            break;
183        case PabloAST::ClassTypeId::Sel:
184            bdd = Ite(input[0], input[1], input[2]);
185            break;
186        case PabloAST::ClassTypeId::MatchStar:
187        case PabloAST::ClassTypeId::ScanThru:
188            if (LLVM_UNLIKELY(input[1] == Zero())) {
189                return std::make_pair(Zero(), true);
190            }
191        case PabloAST::ClassTypeId::Advance:
192            if (LLVM_UNLIKELY(input[0] == Zero())) {
193                return std::make_pair(Zero(), true);
194            }
195        case PabloAST::ClassTypeId::Call:
196            // TODO: we may have more than one output. Need to fix call class to allow for it.
197            return std::make_pair(NewVar(stmt), false);
198        default:
199            throw std::runtime_error("Unexpected statement type " + stmt->getName()->to_string());
200    }
201    Cudd_Ref(bdd);
202    if (LLVM_UNLIKELY(noSatisfyingAssignment(bdd))) {
203        Cudd_RecursiveDeref(mManager, bdd);
204        bdd = Zero();
205    }
206    return std::make_pair(bdd, true);
207}
208
209/** ------------------------------------------------------------------------------------------------------------- *
210 * @brief CUDD wrappers
211 ** ------------------------------------------------------------------------------------------------------------- */
212
213inline DdNode * BDDMinimizationPass::Zero() const {
214    return Cudd_ReadLogicZero(mManager);
215}
216
217inline DdNode * BDDMinimizationPass::One() const {
218    return Cudd_ReadOne(mManager);
219}
220
221inline DdNode * BDDMinimizationPass::NewVar(const PabloAST * expr) {
222    DdNode * var = Cudd_bddIthVar(mManager, mVariables.size());
223    mVariables.push_back(const_cast<PabloAST *>(expr));
224    return var;
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    DdNode * r = Cudd_bddAnd(mManager, x, y);
233    return r;
234}
235
236inline DdNode * BDDMinimizationPass::Intersect(DdNode * const x, DdNode * const y) {
237    DdNode * r = Cudd_bddIntersect(mManager, x, y); Cudd_Ref(r);
238    return r;
239}
240
241inline DdNode * BDDMinimizationPass::Or(DdNode * const x, DdNode * const y) {
242    DdNode * r = Cudd_bddOr(mManager, x, y);
243    return r;
244}
245
246inline DdNode * BDDMinimizationPass::Xor(DdNode * const x, DdNode * const y) {
247    DdNode * r = Cudd_bddXor(mManager, x, y);
248    return r;
249}
250
251inline DdNode * BDDMinimizationPass::Not(DdNode * const x) const {
252    return Cudd_Not(x);
253}
254
255inline DdNode * BDDMinimizationPass::Ite(DdNode * const x, DdNode * const y, DdNode * const z) {
256    DdNode * r = Cudd_bddIte(mManager, x, y, z);
257    return r;
258}
259
260inline bool BDDMinimizationPass::noSatisfyingAssignment(DdNode * const x) {
261    return Cudd_bddLeq(mManager, x, Zero());
262}
263
264inline void BDDMinimizationPass::shutdown() {
265    Cudd_Quit(mManager);
266    mCharacterizationMap.clear();
267    mVariables.clear();
268}
269
270} // end of namespace pablo
271
Note: See TracBrowser for help on using the repository browser.