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

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

Temporary check-in.

File size: 21.6 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
14using namespace llvm;
15using namespace boost;
16
17namespace pablo {
18
19bool BDDMinimizationPass::optimize(PabloFunction & function) {
20    raw_os_ostream out(std::cerr);
21    PabloPrinter::print(function.getEntryBlock(), "", out);
22    out << "\n****************************************************************\n\n";
23    out.flush();
24
25    promoteCrossBlockReachingDefs(function);
26
27    BDDMinimizationPass am;
28    am.initialize(function);
29    am.characterizeAndEliminateLogicallyEquivalentStatements(function);
30    am.simplifyAST(function);
31    am.shutdown();
32
33    return Simplifier::optimize(function);
34}
35
36/** ------------------------------------------------------------------------------------------------------------- *
37 * @brief promoteCrossBlockReachingDefs
38 * @param function
39  *
40 * Scan through the function and promote any cross-block statements into Assign nodes to simplify the BDD node
41 * generation.
42 ** ------------------------------------------------------------------------------------------------------------- */
43void BDDMinimizationPass::promoteCrossBlockReachingDefs(const PabloFunction & function) {
44
45    std::unordered_map<const PabloAST *, unsigned> block;
46    std::stack<Statement *> scope;
47
48    unsigned blockIndex = 0;
49
50    for (const Statement * stmt = function.getEntryBlock().front(); ; ) {
51        while ( stmt ) {
52
53            if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
54                // Set the next statement to be the first statement of the inner scope and push the
55                // next statement of the current statement into the scope stack.
56                const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
57                scope.push(stmt->getNextNode());
58                stmt = nested.front();
59                assert (stmt);
60                ++blockIndex;
61                continue;
62            }
63
64            for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
65                Statement * const op = dyn_cast<Statement>(stmt->getOperand(i));
66                if (op == nullptr || isa<Assign>(op) || isa<Next>(op) || block[op] == blockIndex) {
67                    continue;
68                }
69                PabloBlock * const block = op->getParent();
70                block->setInsertPoint(op);
71
72                op->replaceAllUsesWith(block->createAssign("t", op));
73            }
74
75            block[stmt] = blockIndex;
76
77            stmt = stmt->getNextNode();
78        }
79        if (scope.empty()) {
80            break;
81        }
82        stmt = scope.top();
83        scope.pop();
84        ++blockIndex;
85    }
86}
87
88/** ------------------------------------------------------------------------------------------------------------- *
89 * @brief initialize
90 * @param vars the input vars for this program
91 * @param entry the entry block
92 *
93 * Scan through the program to identify any advances and calls then initialize the BDD engine with
94 * the proper variable ordering.
95 ** ------------------------------------------------------------------------------------------------------------- */
96void BDDMinimizationPass::initialize(const PabloFunction & function) {
97
98    std::stack<Statement *> scope;
99    unsigned variableCount = 0; // number of statements that cannot always be categorized without generating a new variable
100
101    for (const Statement * stmt = function.getEntryBlock().front(); ; ) {
102        while ( stmt ) {
103            if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
104                // Set the next statement to be the first statement of the inner scope and push the
105                // next statement of the current statement into the scope stack.
106                const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
107                scope.push(stmt->getNextNode());
108                stmt = nested.front();
109                assert (stmt);
110                continue;
111            }
112            switch (stmt->getClassTypeId()) {
113                case PabloAST::ClassTypeId::Assign:
114                case PabloAST::ClassTypeId::Next:
115                case PabloAST::ClassTypeId::Advance:
116                case PabloAST::ClassTypeId::Call:
117                case PabloAST::ClassTypeId::MatchStar:
118                case PabloAST::ClassTypeId::ScanThru:
119                    variableCount++;
120                    break;                                   
121                default:
122                    break;
123            }
124            stmt = stmt->getNextNode();
125        }
126        if (scope.empty()) {
127            break;
128        }
129        stmt = scope.top();
130        scope.pop();
131    }
132
133    // Initialize the BDD engine ...
134    mManager = Cudd_Init(variableCount + function.getNumOfParameters() - function.getNumOfResults(), 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0);
135    Cudd_MakeTreeNode(mManager, 0, function.getNumOfParameters(), MTR_DEFAULT);
136    // Map the predefined 0/1 entries
137    mCharacterizationMap[function.getEntryBlock().createZeroes()] = Zero();
138    mCharacterizationMap[function.getEntryBlock().createOnes()] = One();   
139    // Order the variables so the input Vars are pushed to the end; they ought to
140    // be the most complex to resolve.   
141    for (auto i = 0; i != function.getNumOfParameters(); ++i) {
142        mCharacterizationMap[function.getParameter(i)] = NewVar(function.getParameter(i));
143    }
144}
145
146/** ------------------------------------------------------------------------------------------------------------- *
147 * @brief characterize
148 * @param vars the input vars for this program
149 *
150 * Scan through the program and iteratively compute the BDDs for each statement.
151 ** ------------------------------------------------------------------------------------------------------------- */
152void BDDMinimizationPass::characterizeAndEliminateLogicallyEquivalentStatements(PabloFunction & function) {
153    SubsitutionMap baseMap;
154    baseMap.insert(Zero(), function.getEntryBlock().createZeroes());
155    baseMap.insert(One(), function.getEntryBlock().createOnes());
156    Cudd_AutodynEnable(mManager, CUDD_REORDER_LAZY_SIFT);
157    characterizeAndEliminateLogicallyEquivalentStatements(function.getEntryBlock(), baseMap);
158    Cudd_AutodynDisable(mManager);
159    Cudd_ReduceHeap(mManager, CUDD_REORDER_EXACT, 0);
160}
161
162/** ------------------------------------------------------------------------------------------------------------- *
163 * @brief characterize
164 * @param vars the input vars for this program
165 *
166 * Scan through the program and iteratively compute the BDDs for each statement.
167 ** ------------------------------------------------------------------------------------------------------------- */
168void BDDMinimizationPass::characterizeAndEliminateLogicallyEquivalentStatements(PabloBlock & block, SubsitutionMap & parent) {
169    SubsitutionMap subsitutionMap(&parent);
170    Statement * stmt = block.front();
171    while (stmt) {
172        if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
173
174            for (auto promotion : mPromotions) {
175                mCharacterizationMap[promotion] = NewVar(promotion);
176            }
177            mPromotions.clear();
178
179            characterizeAndEliminateLogicallyEquivalentStatements(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(), subsitutionMap);
180
181            for (auto promotion : mPromotions) {
182                mCharacterizationMap[promotion] = NewVar(promotion);
183            }
184            mPromotions.clear();
185
186        } else { // attempt to characterize this statement and replace it if
187            DdNode * bdd = characterizeAndEliminateLogicallyEquivalentStatements(stmt);
188            if (LLVM_LIKELY(!isa<Assign>(stmt) && !isa<Next>(stmt))) {
189                PabloAST * replacement = subsitutionMap[bdd];
190                if (replacement) {
191                    Cudd_RecursiveDeref(mManager, bdd);
192                    stmt = stmt->replaceWith(replacement, false, true);
193                    continue;
194                }
195                subsitutionMap.insert(bdd, stmt);
196            }
197            mCharacterizationMap.insert(std::make_pair(stmt, bdd));
198        }
199        stmt = stmt->getNextNode();
200    }
201    Cudd_ReduceHeap(mManager, CUDD_REORDER_SIFT, 0);
202}
203
204/** ------------------------------------------------------------------------------------------------------------- *
205 * @brief characterize
206 ** ------------------------------------------------------------------------------------------------------------- */
207inline DdNode * BDDMinimizationPass::characterizeAndEliminateLogicallyEquivalentStatements(const Statement * const stmt) {
208
209    DdNode * bdd = nullptr;
210    // Map our operands to the computed BDDs
211    std::array<DdNode *, 3> input;
212    for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
213        PabloAST * const op = stmt->getOperand(i);
214        if (op == nullptr) {
215            throw std::runtime_error("Statement has Null operand!");
216        }
217        if (LLVM_UNLIKELY(isa<Integer>(op) || isa<String>(op))) {
218            continue;
219        }
220        auto f = mCharacterizationMap.find(op);
221        if (LLVM_UNLIKELY(f == mCharacterizationMap.end())) {
222            throw std::runtime_error("Error in AST: attempted to characterize statement with unknown operand!");
223        }
224        input[i] = f->second;
225    }
226
227    switch (stmt->getClassTypeId()) {
228        case PabloAST::ClassTypeId::Assign:
229        case PabloAST::ClassTypeId::Next:
230            mPromotions.push_back(stmt);
231            return input[0];
232        case PabloAST::ClassTypeId::And:
233            bdd = And(input[0], input[1]);
234            break;       
235        case PabloAST::ClassTypeId::Or:
236            bdd = Or(input[0], input[1]);
237            break;
238        case PabloAST::ClassTypeId::Xor:
239            bdd = Xor(input[0], input[1]);
240            break;
241        case PabloAST::ClassTypeId::Not:
242            bdd = Not(input[0]);
243            break;
244        case PabloAST::ClassTypeId::Sel:
245            bdd = Ite(input[0], input[1], input[2]);
246            break;
247        case PabloAST::ClassTypeId::Call:
248            // TODO: we may have more than one output. Need to fix call class to allow for it.
249        case PabloAST::ClassTypeId::Advance:
250        case PabloAST::ClassTypeId::MatchStar:
251        case PabloAST::ClassTypeId::ScanThru:
252            return NewVar(stmt);
253        default:
254            throw std::runtime_error("Unexpected statement type " + stmt->getName()->to_string());
255    }
256
257    Cudd_Ref(bdd);
258
259    if (LLVM_UNLIKELY(noSatisfyingAssignment(bdd))) {
260        Cudd_RecursiveDeref(mManager, bdd);
261        bdd = Zero();
262    }
263
264    return bdd;
265}
266
267/** ------------------------------------------------------------------------------------------------------------- *
268 * @brief simplifyAST
269 ** ------------------------------------------------------------------------------------------------------------- */
270inline void BDDMinimizationPass::simplifyAST(PabloFunction & function) {
271    PabloBuilder builder(function.getEntryBlock());
272    simplifyAST(builder);
273}
274
275/** ------------------------------------------------------------------------------------------------------------- *
276 * @brief simplifyAST
277 ** ------------------------------------------------------------------------------------------------------------- */
278void BDDMinimizationPass::simplifyAST(PabloBuilder & block) {
279    for (Statement * stmt : block) {
280        switch (stmt->getClassTypeId()) {
281            case PabloAST::ClassTypeId::If:
282            case PabloAST::ClassTypeId::While: {
283                    PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
284                    PabloBuilder builder(nested, block);
285                    simplifyAST(builder);
286                    if (isa<If>(stmt)) {
287                        for (Assign * var : cast<const If>(stmt)->getDefined()) {
288                            block.record(var);
289                        }
290                    } else {
291                        for (Next * var : cast<const While>(stmt)->getVariants()) {
292                            block.record(var);
293                        }
294                    }
295                }
296                break;
297            case PabloAST::ClassTypeId::ScanThru:
298            case PabloAST::ClassTypeId::MatchStar:
299                simplifyAST(stmt, dyn_cast<Statement>(stmt->getOperand(1)), block);
300            case PabloAST::ClassTypeId::Advance:
301            case PabloAST::ClassTypeId::Assign:
302            case PabloAST::ClassTypeId::Next:
303                simplifyAST(stmt, dyn_cast<Statement>(stmt->getOperand(0)), block);
304            default: block.record(stmt);
305        }       
306    }
307}
308
309/** ------------------------------------------------------------------------------------------------------------- *
310 * @brief simplifyAST
311 ** ------------------------------------------------------------------------------------------------------------- */
312void BDDMinimizationPass::simplifyAST(Statement * stmt, Statement * const expr, PabloBuilder & builder) {
313    if (expr && expr->getParent() == stmt->getParent()) {
314        DdNode * const bdd = mCharacterizationMap[expr];
315        if (bdd) {
316            builder.getPabloBlock()->setInsertPoint(stmt->getPrevNode());
317            Cudd_Ref(bdd);
318            PabloAST * replacement = simplifyAST(bdd, builder);
319            Cudd_RecursiveDeref(mManager, bdd);
320            if (replacement) {
321                expr->replaceWith(replacement, true, true);
322            }
323        }
324    }
325}
326
327/** ------------------------------------------------------------------------------------------------------------- *
328 * @brief simplifyAST
329 ** ------------------------------------------------------------------------------------------------------------- */
330PabloAST * BDDMinimizationPass::simplifyAST(DdNode * const f, PabloBuilder & builder) {
331    DdNode * g = Cudd_FindEssential(mManager, f);
332    if (g && Cudd_SupportSize(mManager, g) > 0) {
333        if (g == f) { // every variable is essential
334            return makeCoverAST(f, builder);
335        }
336        Cudd_Ref(g);
337        PabloAST * c0 = makeCoverAST(g, builder);
338        if (LLVM_UNLIKELY(c0 == nullptr)) {
339            Cudd_RecursiveDeref(mManager, g);
340            return nullptr;
341        }
342        DdNode * h = Cudd_Cofactor(mManager, f, g);
343        Cudd_Ref(h);
344        Cudd_RecursiveDeref(mManager, g);
345        PabloAST * c1 = simplifyAST(h, builder);
346        Cudd_RecursiveDeref(mManager, h);
347        if (LLVM_UNLIKELY(c1 == nullptr)) {
348            if (LLVM_LIKELY(isa<Statement>(c0))) {
349                cast<Statement>(c0)->eraseFromParent(true);
350            }
351            return nullptr;
352        }
353        return builder.createAnd(c0, c1);
354    }
355    DdNode ** disjunct = nullptr;
356    const auto disjuncts = Cudd_bddVarConjDecomp(mManager, f, &disjunct);
357    if (LLVM_LIKELY(disjuncts == 2)) {
358        Cudd_Ref(disjunct[0]);
359        Cudd_Ref(disjunct[1]);
360        PabloAST * d0 = simplifyAST(disjunct[0], builder);
361        Cudd_RecursiveDeref(mManager, disjunct[0]);
362        if (LLVM_UNLIKELY(d0 == nullptr)) {
363            Cudd_RecursiveDeref(mManager, disjunct[1]);
364            return nullptr;
365        }
366        PabloAST * d1 = simplifyAST(disjunct[1], builder);
367        Cudd_RecursiveDeref(mManager, disjunct[1]);
368        FREE(disjunct);
369        if (LLVM_UNLIKELY(d1 == nullptr)) {
370            if (LLVM_LIKELY(isa<Statement>(d0))) {
371                cast<Statement>(d0)->eraseFromParent(true);
372            }
373            return nullptr;
374        }
375        return builder.createAnd(d0, d1);
376    }
377    FREE(disjunct);
378    return makeCoverAST(f, builder);
379}
380
381/** ------------------------------------------------------------------------------------------------------------- *
382 * @brief makeCoverAST
383 ** ------------------------------------------------------------------------------------------------------------- */
384PabloAST * BDDMinimizationPass::makeCoverAST(DdNode * const f, PabloBuilder & builder) {
385
386    std::queue<PabloAST *> SQ;
387
388    circular_buffer<PabloAST *> CQE(mManager->size);
389    circular_buffer<PabloAST *> CQO(mManager->size);
390
391    circular_buffer<PabloAST *> DQE(mManager->size);
392    circular_buffer<PabloAST *> DQO(mManager->size);
393
394    int cube[mManager->size];
395
396    DdNode * g = f;
397
398    Cudd_Ref(g);
399
400    while (g != Cudd_ReadLogicZero(mManager)) {
401        int length;
402        DdNode * implicant = Cudd_LargestCube(mManager, g, &length);
403        if (LLVM_UNLIKELY(implicant == nullptr)) {
404            Cudd_RecursiveDeref(mManager, g);
405            return nullptr;
406        }
407        Cudd_Ref(implicant);
408        DdNode * prime = Cudd_bddMakePrime(mManager, implicant, f);
409        if (LLVM_UNLIKELY(prime == nullptr)) {
410            Cudd_RecursiveDeref(mManager, g);
411            Cudd_RecursiveDeref(mManager, implicant);
412            return nullptr;
413        }
414        Cudd_Ref(prime);
415        Cudd_RecursiveDeref(mManager, implicant);
416
417        DdNode * h = Cudd_bddAnd(mManager, g, Cudd_Not(prime));
418        if (LLVM_UNLIKELY(h == nullptr)) {
419            Cudd_RecursiveDeref(mManager, g);
420            Cudd_RecursiveDeref(mManager, prime);
421            return nullptr;
422        }
423        Cudd_Ref(h);
424        Cudd_RecursiveDeref(mManager, g);
425
426        g = h;
427        if (LLVM_UNLIKELY(Cudd_BddToCubeArray(mManager, prime, cube) == 0)) {
428            Cudd_RecursiveDeref(mManager, g);
429            Cudd_RecursiveDeref(mManager, prime);
430            return nullptr;
431        }
432        Cudd_RecursiveDeref(mManager, prime);
433
434        for (auto i = 0; i != mManager->size; ++i) {
435            if ((i & 1) == 0) { // i is even
436                if (cube[i] == 0) {
437                    DQE.push_back(mVariables[i]);
438                } else if (cube[i] == 1) {
439                    CQE.push_back(mVariables[i]);
440                }
441            } else { // i is odd
442                if (cube[i] == 0) {
443                    DQO.push_back(mVariables[i]);
444                } else if (cube[i] == 1) {
445                    CQO.push_back(mVariables[i]);
446                }
447            }
448        }
449
450        PabloAST * dq = builder.createZeroes();
451        if (!DQE.empty() || !DQO.empty()) {
452            while (DQE.size() > 1) {
453                PabloAST * v1 = DQE.front(); DQE.pop_front();
454                PabloAST * v2 = DQE.front(); DQE.pop_front();
455                DQE.push_back(builder.createOr(v1, v2));
456            }
457            while (DQO.size() > 1) {
458                PabloAST * v1 = DQO.front(); DQO.pop_front();
459                PabloAST * v2 = DQO.front(); DQO.pop_front();
460                DQO.push_back(builder.createOr(v1, v2));
461            }
462            if (DQE.empty()) {
463                dq = DQO.front();
464            } else if (DQO.empty()) {
465                dq = DQE.front();
466            } else {
467                dq = builder.createOr(DQE.front(), DQO.front());
468            }
469            DQE.clear();
470            DQO.clear();
471        }
472
473        PabloAST * cq = builder.createOnes();
474        if (!CQE.empty() || !CQO.empty()) {
475            while (CQE.size() > 1) {
476                PabloAST * v1 = CQE.front(); CQE.pop_front();
477                PabloAST * v2 = CQE.front(); CQE.pop_front();
478                CQE.push_back(builder.createOr(v1, v2));
479            }
480            while (CQO.size() > 1) {
481                PabloAST * v1 = CQO.front(); CQO.pop_front();
482                PabloAST * v2 = CQO.front(); CQO.pop_front();
483                CQO.push_back(builder.createOr(v1, v2));
484            }
485            if (CQE.empty()) {
486                dq = CQO.front();
487            } else if (CQO.empty()) {
488                dq = CQE.front();
489            } else {
490                dq = builder.createAnd(CQE.front(), CQO.front());
491            }
492            CQE.clear();
493            CQO.clear();
494        }
495        SQ.push(builder.createAnd(cq, builder.createNot(dq)));
496    }
497    Cudd_RecursiveDeref(mManager, g);
498
499    while (SQ.size() > 1) {
500        PabloAST * v1 = SQ.front(); SQ.pop();
501        PabloAST * v2 = SQ.front(); SQ.pop();
502        SQ.push(builder.createOr(v1, v2));
503    }
504
505    return SQ.front();
506}
507
508/** ------------------------------------------------------------------------------------------------------------- *
509 * @brief CUDD wrappers
510 ** ------------------------------------------------------------------------------------------------------------- */
511
512inline DdNode * BDDMinimizationPass::Zero() const {
513    return Cudd_ReadLogicZero(mManager);
514}
515
516inline DdNode * BDDMinimizationPass::One() const {
517    return Cudd_ReadOne(mManager);
518}
519
520inline DdNode * BDDMinimizationPass::NewVar(const PabloAST * expr) {
521    DdNode * var = Cudd_bddIthVar(mManager, mVariables.size());
522    mVariables.push_back(const_cast<PabloAST *>(expr));
523    return var;
524}
525
526inline bool BDDMinimizationPass::isZero(DdNode * const x) const {
527    return x == Zero();
528}
529
530inline DdNode * BDDMinimizationPass::And(DdNode * const x, DdNode * const y) {
531    DdNode * r = Cudd_bddAnd(mManager, x, y);
532    return r;
533}
534
535inline DdNode * BDDMinimizationPass::Intersect(DdNode * const x, DdNode * const y) {
536    DdNode * r = Cudd_bddIntersect(mManager, x, y); Cudd_Ref(r);
537    return r;
538}
539
540inline DdNode * BDDMinimizationPass::Or(DdNode * const x, DdNode * const y) {
541    DdNode * r = Cudd_bddOr(mManager, x, y);
542    return r;
543}
544
545inline DdNode * BDDMinimizationPass::Xor(DdNode * const x, DdNode * const y) {
546    DdNode * r = Cudd_bddXor(mManager, x, y);
547    return r;
548}
549
550inline DdNode * BDDMinimizationPass::Not(DdNode * const x) const {
551    return Cudd_Not(x);
552}
553
554inline DdNode * BDDMinimizationPass::Ite(DdNode * const x, DdNode * const y, DdNode * const z) {
555    DdNode * r = Cudd_bddIte(mManager, x, y, z);
556    return r;
557}
558
559inline bool BDDMinimizationPass::noSatisfyingAssignment(DdNode * const x) {
560    return Cudd_bddLeq(mManager, x, Zero());
561}
562
563inline void BDDMinimizationPass::shutdown() {
564    Cudd_Quit(mManager);
565}
566
567} // end of namespace pablo
568
Note: See TracBrowser for help on using the repository browser.