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

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

Minor revisions.

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