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

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

Temporary check in.

File size: 13.1 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.characterizeAndEliminateLogicallyEquivalentStatements(function);
19    am.simplifyAST(function);
20    am.shutdown();
21    return true;
22}
23
24/** ------------------------------------------------------------------------------------------------------------- *
25 * @brief initialize
26 * @param vars the input vars for this program
27 * @param entry the entry block
28 *
29 * Scan through the program to identify any advances and calls then initialize the BDD engine with
30 * the proper variable ordering.
31 ** ------------------------------------------------------------------------------------------------------------- */
32void BDDMinimizationPass::initialize(const PabloFunction & function) {
33
34    std::stack<Statement *> scope;
35    unsigned variableCount = 0; // number of statements that cannot always be categorized without generating a new variable
36
37    for (const Statement * stmt = function.getEntryBlock().front(); ; ) {
38        while ( stmt ) {
39
40            if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
41                // Set the next statement to be the first statement of the inner scope and push the
42                // next statement of the current statement into the scope stack.
43                const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
44                variableCount += isa<If>(stmt) ? cast<If>(stmt)->getDefined().size() : cast<While>(stmt)->getVariants().size();
45                scope.push(stmt->getNextNode());
46                stmt = nested.front();
47                assert (stmt);
48                continue;
49            }
50            switch (stmt->getClassTypeId()) {
51                case PabloAST::ClassTypeId::Advance:
52                case PabloAST::ClassTypeId::Call:
53                case PabloAST::ClassTypeId::MatchStar:
54                case PabloAST::ClassTypeId::ScanThru:
55                    variableCount++;
56                    break;                                   
57                default:
58                    break;
59            }
60            stmt = stmt->getNextNode();
61        }
62        if (scope.empty()) {
63            break;
64        }
65        stmt = scope.top();
66        scope.pop();
67    }
68
69    // Initialize the BDD engine ...
70    unsigned maxVariableCount = variableCount + function.getNumOfParameters();
71    mManager = Cudd_Init(maxVariableCount, 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0);
72    Cudd_MakeTreeNode(mManager, 0, function.getNumOfParameters(), MTR_DEFAULT);
73    // Map the predefined 0/1 entries
74    mCharacterizationMap[function.getEntryBlock().createZeroes()] = Zero();
75    mCharacterizationMap[function.getEntryBlock().createOnes()] = One();   
76    // Order the variables so the input Vars are pushed to the end; they ought to
77    // be the most complex to resolve.   
78    mVariables = 0;
79    for (auto i = 0; i != function.getNumOfParameters(); ++i) {
80        mCharacterizationMap[function.getParameter(i)] = NewVar();
81    }
82}
83
84/** ------------------------------------------------------------------------------------------------------------- *
85 * @brief characterize
86 * @param vars the input vars for this program
87 *
88 * Scan through the program and iteratively compute the BDDs for each statement.
89 ** ------------------------------------------------------------------------------------------------------------- */
90void BDDMinimizationPass::characterizeAndEliminateLogicallyEquivalentStatements(PabloFunction & function) {
91    SubsitutionMap baseMap;
92    baseMap.insert(Zero(), function.getEntryBlock().createZeroes());
93    baseMap.insert(One(), function.getEntryBlock().createOnes());
94    Cudd_AutodynEnable(mManager, CUDD_REORDER_LAZY_SIFT);
95    characterizeAndEliminateLogicallyEquivalentStatements(function.getEntryBlock(), baseMap);
96    Cudd_AutodynDisable(mManager);
97    Cudd_ReduceHeap(mManager, CUDD_REORDER_EXACT, 0);
98}
99
100/** ------------------------------------------------------------------------------------------------------------- *
101 * @brief characterize
102 * @param vars the input vars for this program
103 *
104 * Scan through the program and iteratively compute the BDDs for each statement.
105 ** ------------------------------------------------------------------------------------------------------------- */
106void BDDMinimizationPass::characterizeAndEliminateLogicallyEquivalentStatements(PabloBlock & block, SubsitutionMap & parent) {
107    SubsitutionMap subsitutionMap(&parent);
108    Statement * stmt = block.front();
109    while (stmt) {
110        if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
111            characterizeAndEliminateLogicallyEquivalentStatements(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(), subsitutionMap);
112            // The defined vars of If statements and variants of While statements are unique in the AST in that
113            // they are the only way a value can escape its local block. When we simplify this code later, we
114            // do not want to recompute whatever was found within a nested block so instead they are marked as
115            // new variables.
116            if (isa<If>(stmt)) {
117                for (const Assign * defVar : cast<const If>(stmt)->getDefined()) {
118                    mCharacterizationMap[defVar] = NewVar();
119                }
120            } else { // if (isa<While>(stmt)) {
121                for (const Next * variant : cast<const While>(stmt)->getVariants()) {
122                    mCharacterizationMap[variant] = NewVar();
123                }
124            }
125        } else { // attempt to characterize this statement and replace it if
126            DdNode * bdd = characterizeAndEliminateLogicallyEquivalentStatements(stmt);
127            if (LLVM_LIKELY(!isa<Assign>(stmt) && !isa<Next>(stmt))) {
128                PabloAST * replacement = subsitutionMap[bdd];
129                if (replacement) {
130                    Cudd_RecursiveDeref(mManager, bdd);
131                    stmt = stmt->replaceWith(replacement, false, true);
132                    continue;
133                }
134                subsitutionMap.insert(bdd, stmt);
135            }
136            mCharacterizationMap.insert(std::make_pair(stmt, bdd));
137        }
138        stmt = stmt->getNextNode();
139    }
140    Cudd_ReduceHeap(mManager, CUDD_REORDER_SIFT, 0);
141}
142
143/** ------------------------------------------------------------------------------------------------------------- *
144 * @brief characterize
145 ** ------------------------------------------------------------------------------------------------------------- */
146inline DdNode * BDDMinimizationPass::characterizeAndEliminateLogicallyEquivalentStatements(const 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            throw std::runtime_error("Error in AST: attempted to characterize statement with unknown operand!");
162        }
163        input[i] = f->second;
164    }
165
166    switch (stmt->getClassTypeId()) {
167        case PabloAST::ClassTypeId::Assign:
168        case PabloAST::ClassTypeId::Next:
169            return input[0];
170        case PabloAST::ClassTypeId::And:
171            bdd = And(input[0], input[1]);
172            break;       
173        case PabloAST::ClassTypeId::Or:
174            bdd = Or(input[0], input[1]);
175            break;
176        case PabloAST::ClassTypeId::Xor:
177            bdd = Xor(input[0], input[1]);
178            break;
179        case PabloAST::ClassTypeId::Not:
180            bdd = Not(input[0]);
181            break;
182        case PabloAST::ClassTypeId::Sel:
183            bdd = Ite(input[0], input[1], input[2]);
184            break;
185        case PabloAST::ClassTypeId::Call:
186            // TODO: we may have more than one output. Need to fix call class to allow for it.
187        case PabloAST::ClassTypeId::Advance:
188        case PabloAST::ClassTypeId::MatchStar:
189        case PabloAST::ClassTypeId::ScanThru:
190            return NewVar();
191        default:
192            throw std::runtime_error("Unexpected statement type " + stmt->getName()->to_string());
193    }
194
195    Cudd_Ref(bdd);
196
197    if (LLVM_UNLIKELY(noSatisfyingAssignment(bdd))) {
198        Cudd_RecursiveDeref(mManager, bdd);
199        bdd = Zero();
200    }
201
202    return bdd;
203}
204
205/** ------------------------------------------------------------------------------------------------------------- *
206 * @brief simplifyAST
207 ** ------------------------------------------------------------------------------------------------------------- */
208inline void BDDMinimizationPass::simplifyAST(PabloFunction & function) {
209    simplifyAST(function.getEntryBlock());
210}
211
212/** ------------------------------------------------------------------------------------------------------------- *
213 * @brief simplifyAST
214 ** ------------------------------------------------------------------------------------------------------------- */
215void BDDMinimizationPass::simplifyAST(PabloBlock & block) {
216    for (Statement * stmt : block) {
217        switch (stmt->getClassTypeId()) {
218            case PabloAST::ClassTypeId::If:
219            case PabloAST::ClassTypeId::While:
220                simplifyAST(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
221                break;
222            case PabloAST::ClassTypeId::ScanThru:
223            case PabloAST::ClassTypeId::MatchStar:
224                simplifyAST(stmt->getOperand(1), block, stmt->getPrevNode());
225            case PabloAST::ClassTypeId::Advance:
226            case PabloAST::ClassTypeId::Assign:
227            case PabloAST::ClassTypeId::Next:
228                simplifyAST(stmt->getOperand(0), block, stmt->getPrevNode());
229            default: break;
230        }
231    }
232}
233
234/** ------------------------------------------------------------------------------------------------------------- *
235 * @brief simplifyAST
236 ** ------------------------------------------------------------------------------------------------------------- */
237inline void BDDMinimizationPass::simplifyAST(PabloAST * const expr, PabloBlock & block, Statement * const insertionPoint) {
238
239    DdNode * bdd = mCharacterizationMap[expr];
240
241    llvm::raw_os_ostream out(std::cerr);
242    PabloPrinter::print(expr, out); out << " : " << Cudd_SupportSize(mManager, bdd) << '\n';
243    out.flush();
244
245    Cudd_bddPrintCover(mManager, bdd, bdd);
246
247//    // TODO: look into 0/1/x dominators?
248//    CUDD_VALUE_TYPE value;
249//    int * cube = nullptr;
250
251//    char output[3] = { '0', '1', '.' };
252
253//    DdGen * gen = Cudd_FirstCube(mManager, bdd, &cube, &value);
254//    while (!Cudd_IsGenEmpty(gen)) {
255//        // cube[0 ... n - 1] = { 0 : false, 1: true, 2: don't care }
256//        for (unsigned i = 0; i != mVariables; ++i) {
257//            out << output[cube[i]];
258//        }
259//        out << '\n';
260//        Cudd_NextCube(gen, &cube, &value);
261//    }
262//    Cudd_GenFree(gen);
263
264//    out.flush();
265
266    block.setInsertPoint(insertionPoint);
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() {
286    return Cudd_bddIthVar(mManager, mVariables++);
287}
288
289inline bool BDDMinimizationPass::isZero(DdNode * const x) const {
290    return x == Zero();
291}
292
293inline DdNode * BDDMinimizationPass::And(DdNode * const x, DdNode * const y) {
294    DdNode * r = Cudd_bddAnd(mManager, x, y);
295    return r;
296}
297
298inline DdNode * BDDMinimizationPass::Intersect(DdNode * const x, DdNode * const y) {
299    DdNode * r = Cudd_bddIntersect(mManager, x, y); Cudd_Ref(r);
300    return r;
301}
302
303inline DdNode * BDDMinimizationPass::Or(DdNode * const x, DdNode * const y) {
304    DdNode * r = Cudd_bddOr(mManager, x, y);
305    return r;
306}
307
308inline DdNode * BDDMinimizationPass::Xor(DdNode * const x, DdNode * const y) {
309    DdNode * r = Cudd_bddXor(mManager, x, y);
310    return r;
311}
312
313inline DdNode * BDDMinimizationPass::Not(DdNode * const x) const {
314    return Cudd_Not(x);
315}
316
317inline DdNode * BDDMinimizationPass::Ite(DdNode * const x, DdNode * const y, DdNode * const z) {
318    DdNode * r = Cudd_bddIte(mManager, x, y, z);
319    return r;
320}
321
322inline bool BDDMinimizationPass::noSatisfyingAssignment(DdNode * const x) {
323    return Cudd_bddLeq(mManager, x, Zero());
324}
325
326inline void BDDMinimizationPass::shutdown() {
327    Cudd_Quit(mManager);
328}
329
330} // end of namespace pablo
331
Note: See TracBrowser for help on using the repository browser.