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

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

Temporary check in.

File size: 12.8 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 <util.h>
9#include <mtr.h>
10
11using namespace llvm;
12
13namespace pablo {
14
15bool BDDMinimizationPass::optimize(PabloFunction & function) {
16    BDDMinimizationPass am;
17    am.initialize(function);
18    am.characterize(function.getEntryBlock());
19    am.eliminateLogicallyEquivalentStatements(function.getEntryBlock());
20    am.simplifyAST(function);
21    am.shutdown();
22    return true;
23}
24
25/** ------------------------------------------------------------------------------------------------------------- *
26 * @brief initialize
27 * @param vars the input vars for this program
28 * @param entry the entry block
29 *
30 * Scan through the program to identify any advances and calls then initialize the BDD engine with
31 * the proper variable ordering.
32 ** ------------------------------------------------------------------------------------------------------------- */
33void BDDMinimizationPass::initialize(const PabloFunction & function) {
34
35    std::stack<Statement *> scope;
36    unsigned variableCount = 0; // number of statements that cannot always be categorized without generating a new variable
37
38    for (Statement * stmt = function.getEntryBlock().front(); ; ) {
39        while ( stmt ) {
40
41            if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
42                // Set the next statement to be the first statement of the inner scope and push the
43                // next statement of the current statement into the scope stack.
44                const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
45                scope.push(stmt->getNextNode());
46                stmt = nested.front();
47                assert (stmt);
48                continue;
49            }
50
51            switch (stmt->getClassTypeId()) {
52                case PabloAST::ClassTypeId::Advance:
53                case PabloAST::ClassTypeId::Call:
54                case PabloAST::ClassTypeId::MatchStar:
55                case PabloAST::ClassTypeId::ScanThru:               
56                    variableCount++;
57                    break;
58                default:
59                    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    unsigned maxVariableCount = variableCount + function.getNumOfParameters();
72    mManager = Cudd_Init(maxVariableCount, 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0);
73    Cudd_MakeTreeNode(mManager, variableCount, function.getNumOfParameters(), MTR_DEFAULT);
74    Cudd_AutodynEnable(mManager, CUDD_REORDER_LAZY_SIFT);
75    // Map the predefined 0/1 entries
76    mCharacterizationMap[function.getEntryBlock().createZeroes()] = Zero();
77    mCharacterizationMap[function.getEntryBlock().createOnes()] = One();
78
79    mVariables = 0;
80
81    mStatementVector.resize(maxVariableCount, nullptr);
82    // Order the variables so the input Vars are pushed to the end; they ought to
83    // be the most complex to resolve.   
84    for (auto i = 0; i != function.getNumOfParameters(); ++i) {
85        mStatementVector[variableCount] = const_cast<Var *>(function.getParameter(i));
86        mCharacterizationMap[function.getParameter(i)] = Cudd_bddIthVar(mManager, variableCount++);
87    }
88}
89
90/** ------------------------------------------------------------------------------------------------------------- *
91 * @brief characterize
92 * @param vars the input vars for this program
93 *
94 * Scan through the program and iteratively compute the BDDs for each statement.
95 ** ------------------------------------------------------------------------------------------------------------- */
96void BDDMinimizationPass::characterize(const PabloBlock & block) {
97    for (const Statement * stmt : block) {
98        if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
99            // Set the next statement to be the first statement of the inner scope and push the
100            // next statement of the current statement into the scope stack.
101            characterize(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());           
102            continue;
103        }
104        mCharacterizationMap.insert(std::make_pair(stmt, characterize(stmt)));
105    }
106    Cudd_ReduceHeap(mManager, CUDD_REORDER_SIFT, 0);
107}
108
109/** ------------------------------------------------------------------------------------------------------------- *
110 * @brief characterize
111 ** ------------------------------------------------------------------------------------------------------------- */
112inline DdNode * BDDMinimizationPass::characterize(const Statement * const stmt) {
113
114//    llvm::raw_os_ostream out(std::cerr);
115//    PabloPrinter::print(stmt, "> ", out); out << "\n"; out.flush();
116
117    DdNode * bdd = nullptr;
118    // Map our operands to the computed BDDs
119    std::array<DdNode *, 3> input;
120    for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
121        PabloAST * const op = stmt->getOperand(i);
122        if (op == nullptr) {
123            throw std::runtime_error("Statement has Null operand!");
124        }
125        if (LLVM_UNLIKELY(isa<Integer>(op) || isa<String>(op))) {
126            continue;
127        }
128        auto f = mCharacterizationMap.find(op);
129        if (LLVM_UNLIKELY(f == mCharacterizationMap.end())) {
130            throw std::runtime_error("Error in AST: attempted to characterize statement with unknown operand!");
131        }
132        input[i] = f->second;
133    }
134
135    switch (stmt->getClassTypeId()) {
136        case PabloAST::ClassTypeId::Assign:
137            return input[0];
138        case PabloAST::ClassTypeId::And:
139            bdd = And(input[0], input[1]);
140            break;
141        case PabloAST::ClassTypeId::Next:
142        case PabloAST::ClassTypeId::Or:
143            bdd = Or(input[0], input[1]);
144            break;
145        case PabloAST::ClassTypeId::Xor:
146            bdd = Xor(input[0], input[1]);
147            break;
148        case PabloAST::ClassTypeId::Not:
149            bdd = Not(input[0]);
150            break;
151        case PabloAST::ClassTypeId::Sel:
152            bdd = Ite(input[0], input[1], input[2]);
153            break;
154        case PabloAST::ClassTypeId::Advance:
155        case PabloAST::ClassTypeId::Call:
156        case PabloAST::ClassTypeId::MatchStar:
157        case PabloAST::ClassTypeId::ScanThru:
158            return NewVar(const_cast<Statement *>(stmt));
159        default:
160            throw std::runtime_error("Unexpected statement type " + stmt->getName()->to_string());
161    }
162
163    Cudd_Ref(bdd);
164
165    if (LLVM_UNLIKELY(noSatisfyingAssignment(bdd))) {
166        Cudd_RecursiveDeref(mManager, bdd);
167        bdd = Zero();
168    }
169
170    return bdd;
171}
172
173/** ------------------------------------------------------------------------------------------------------------- *
174 * @brief eliminateLogicallyEquivalentStatements
175 * @param entry the entry block of the program
176 *
177 * Scan through the program using the precomputed BDDs and replace any statements with equivalent BDDs with the
178 * earlier one (assuming its in scope) and replace any contradictions with Zero.
179 ** ------------------------------------------------------------------------------------------------------------- */
180inline void BDDMinimizationPass::eliminateLogicallyEquivalentStatements(PabloBlock & entry) {
181    SubsitutionMap baseMap;
182    baseMap.insert(Zero(), entry.createZeroes());
183    baseMap.insert(One(), entry.createOnes());
184    Cudd_AutodynDisable(mManager);
185    eliminateLogicallyEquivalentStatements(entry, baseMap);
186}
187
188/** ------------------------------------------------------------------------------------------------------------- *
189 * @brief eliminateLogicallyEquivalentStatements
190 ** ------------------------------------------------------------------------------------------------------------- */
191void BDDMinimizationPass::eliminateLogicallyEquivalentStatements(PabloBlock & block, SubsitutionMap & parent) {
192    SubsitutionMap subsitutionMap(&parent);
193    Statement * stmt = block.front();
194    while (stmt) {
195        if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
196            eliminateLogicallyEquivalentStatements(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(), subsitutionMap);
197        } else if (LLVM_LIKELY(!isa<Assign>(stmt) && !isa<Next>(stmt))) {
198            DdNode * bdd = mCharacterizationMap[stmt];
199            PabloAST * replacement = subsitutionMap[bdd];
200            if (replacement) {
201                Cudd_RecursiveDeref(mManager, bdd);
202                stmt = stmt->replaceWith(replacement, false, true);
203                continue;
204            }
205            subsitutionMap.insert(bdd, stmt);
206        }
207        stmt = stmt->getNextNode();
208    }
209}
210
211/** ------------------------------------------------------------------------------------------------------------- *
212 * @brief simplifyAST
213 *
214 * Assignment and Next statements are unique in the AST in that they are the only way a value can escape its
215 * local block. By trying to simplify those aggressively
216 ** ------------------------------------------------------------------------------------------------------------- */
217inline void BDDMinimizationPass::simplifyAST(PabloFunction & function) {
218    Cudd_ReduceHeap(mManager, CUDD_REORDER_EXACT, 0);
219    Cudd_zddVarsFromBddVars(mManager, 1);
220    simplifyAST(function.getEntryBlock());
221    Cudd_PrintInfo(mManager, stderr);
222}
223
224/** ------------------------------------------------------------------------------------------------------------- *
225 * @brief simplifyAST
226 ** ------------------------------------------------------------------------------------------------------------- */
227void BDDMinimizationPass::simplifyAST(PabloBlock & block) {
228    for (Statement * stmt : block) {
229        if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
230            simplifyAST(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
231        } else if (isa<Advance>(stmt) || isa<Assign>(stmt) || isa<Next>(stmt)) {
232            simplifyAST(block, stmt->getOperand(0));
233        }
234    }
235}
236
237/** ------------------------------------------------------------------------------------------------------------- *
238 * @brief simplifyAST
239 ** ------------------------------------------------------------------------------------------------------------- */
240inline void BDDMinimizationPass::simplifyAST(PabloBlock & block, PabloAST * const stmt) {
241
242    DdNode * const bdd = mCharacterizationMap[stmt];
243
244    llvm::raw_os_ostream out(std::cerr);
245    out << " >>>>>>>> "; PabloPrinter::print(stmt, out); out << " <<<<<<<<"; out.flush();
246
247//    unsigned count = 0;
248//    // TODO: look into 0/1/x dominators?
249//    CUDD_VALUE_TYPE value;
250//    int * cube = nullptr;
251//    DdGen * gen = Cudd_FirstCube(mManager, bdd, &cube, &value);
252//    while (!Cudd_IsGenEmpty(gen)) {
253//        ++count;
254//        // cube[0 ... n - 1] = { 0 : false, 1: true, 2: don't care }
255//        Cudd_NextCube(gen, &cube, &value);
256//    }
257//    Cudd_GenFree(gen);
258
259//    out << count;
260
261    out << "\n"; out.flush();
262
263
264
265
266//    block.setInsertPoint(stmt->getPrevNode());
267
268//    DdNode * zdd = Cudd_zddPortFromBdd(mManager, bdd);
269//    Cudd_zddPrintCover(mManager, zdd);
270//    Cudd_RecursiveDerefZdd(mManager, zdd);
271}
272
273/** ------------------------------------------------------------------------------------------------------------- *
274 * @brief CUDD wrappers
275 ** ------------------------------------------------------------------------------------------------------------- */
276
277inline DdNode * BDDMinimizationPass::Zero() const {
278    return Cudd_ReadLogicZero(mManager);
279}
280
281inline DdNode * BDDMinimizationPass::One() const {
282    return Cudd_ReadOne(mManager);
283}
284
285inline DdNode * BDDMinimizationPass::NewVar(Statement * const stmt) {
286    mStatementVector[mVariables] = stmt;
287    return Cudd_bddIthVar(mManager, mVariables++);
288}
289
290inline bool BDDMinimizationPass::isZero(DdNode * const x) const {
291    return x == Zero();
292}
293
294inline DdNode * BDDMinimizationPass::And(DdNode * const x, DdNode * const y) {
295    DdNode * r = Cudd_bddAnd(mManager, x, y);
296    return r;
297}
298
299inline DdNode * BDDMinimizationPass::Intersect(DdNode * const x, DdNode * const y) {
300    DdNode * r = Cudd_bddIntersect(mManager, x, y); Cudd_Ref(r);
301    return r;
302}
303
304inline DdNode * BDDMinimizationPass::Or(DdNode * const x, DdNode * const y) {
305    DdNode * r = Cudd_bddOr(mManager, x, y);
306    return r;
307}
308
309inline DdNode * BDDMinimizationPass::Xor(DdNode * const x, DdNode * const y) {
310    DdNode * r = Cudd_bddXor(mManager, x, y);
311    return r;
312}
313
314inline DdNode * BDDMinimizationPass::Not(DdNode * const x) const {
315    return Cudd_Not(x);
316}
317
318inline DdNode * BDDMinimizationPass::Ite(DdNode * const x, DdNode * const y, DdNode * const z) {
319    DdNode * r = Cudd_bddIte(mManager, x, y, z);
320    return r;
321}
322
323inline bool BDDMinimizationPass::noSatisfyingAssignment(DdNode * const x) {
324    return Cudd_bddLeq(mManager, x, Zero());
325}
326
327inline void BDDMinimizationPass::shutdown() {
328    Cudd_Quit(mManager);
329}
330
331} // end of namespace pablo
332
Note: See TracBrowser for help on using the repository browser.