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

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

Work on bug fixes for multiplexing pass.

File size: 8.9 KB
Line 
1#include "pablo_bddminimization.h"
2#include <pablo/codegenstate.h>
3#include <pablo/builder.hpp>
4#include <pablo/printer_pablos.h>
5#include <pablo/optimizers/pablo_simplifier.hpp>
6#include <pablo/analysis/pabloverifier.hpp>
7#include <stack>
8#include <bdd.h>
9
10using namespace llvm;
11using namespace boost;
12using namespace boost::container;
13
14namespace pablo {
15
16using TypeId = PabloAST::ClassTypeId;
17
18// TODO: add in analysis to verify that the outputs of an If would be zero if the If cond is false?
19
20// TODO: test whether an If node can be moved into another If body in the same scope?
21
22bool BDDMinimizationPass::optimize(PabloFunction & function) {
23    BDDMinimizationPass am;
24    am.initialize(function);
25    am.eliminateLogicallyEquivalentStatements(function);
26    bdd_done();
27    #ifndef NDEBUG
28    PabloVerifier::verify(function, "post-bdd-minimization");
29    #endif
30    return Simplifier::optimize(function);
31}
32
33/** ------------------------------------------------------------------------------------------------------------- *
34 * @brief initialize
35 *
36 * Scan through the program to identify any advances and calls then initialize the BDD engine with
37 * the proper variable ordering.
38 ** ------------------------------------------------------------------------------------------------------------- */
39void BDDMinimizationPass::initialize(PabloFunction & function) {
40
41    std::stack<Statement *> scope;
42    unsigned variableCount = function.getNumOfParameters(); // number of statements that cannot always be categorized without generating a new variable
43    unsigned statementCount = 0;
44    for (const Statement * stmt = function.getEntryBlock().front(); ; ) {
45        while ( stmt ) {
46            if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
47                // Set the next statement to be the first statement of the inner scope and push the
48                // next statement of the current statement into the scope stack.
49                const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
50                scope.push(stmt->getNextNode());
51                stmt = nested.front();
52                assert (stmt);
53                continue;
54            }
55            ++statementCount;
56            switch (stmt->getClassTypeId()) {
57                case TypeId::Advance:
58                case TypeId::Call:
59                case TypeId::MatchStar:
60                case TypeId::ScanThru:
61                    ++variableCount;
62                    break;
63                default: 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    bdd_init(1000000, 10000);
76    bdd_setvarnum(variableCount + function.getNumOfParameters());
77    bdd_setcacheratio(32);
78    bdd_setmaxincrease(1000000);
79    bdd_disable_reorder();
80
81    // Map the predefined 0/1 entries
82    mCharacterizationMap[PabloBlock::createZeroes()] = bdd_zero();
83    mCharacterizationMap[PabloBlock::createOnes()] = bdd_one();
84    // Order the variables so the input Vars are pushed to the end; they ought to
85    // be the most complex to resolve.   
86    for (mVariables = 0; mVariables != function.getNumOfParameters(); ++mVariables) {
87        mCharacterizationMap[function.getParameter(mVariables)] = bdd_ithvar(mVariables);
88    }
89}
90
91/** ------------------------------------------------------------------------------------------------------------- *
92 * @brief eliminateLogicallyEquivalentStatements
93 ** ------------------------------------------------------------------------------------------------------------- */
94void BDDMinimizationPass::eliminateLogicallyEquivalentStatements(PabloFunction & function) {
95    SubsitutionMap baseMap;
96    baseMap.insert(bdd_zero(), function.getEntryBlock().createZeroes());
97    baseMap.insert(bdd_one(), function.getEntryBlock().createOnes());
98    eliminateLogicallyEquivalentStatements(function.getEntryBlock(), baseMap);
99}
100
101/** ------------------------------------------------------------------------------------------------------------- *
102 * @brief eliminateLogicallyEquivalentStatements
103 ** ------------------------------------------------------------------------------------------------------------- */
104void BDDMinimizationPass::eliminateLogicallyEquivalentStatements(PabloBlock & block, SubsitutionMap & parent) {
105    SubsitutionMap map(&parent);
106    Statement * stmt = block.front();
107    while (stmt) {
108        if (LLVM_UNLIKELY(isa<If>(stmt))) {
109            eliminateLogicallyEquivalentStatements(cast<If>(stmt)->getBody(), map);
110        } else if (LLVM_UNLIKELY(isa<While>(stmt))) {
111            eliminateLogicallyEquivalentStatements(cast<While>(stmt)->getBody(), map);
112            for (Next * var : cast<const While>(stmt)->getVariants()) {
113                if (!escapes(var)) {
114                    bdd_delref(mCharacterizationMap[var]);
115                    mCharacterizationMap.erase(var);
116                }
117            }
118        } else { // attempt to characterize this statement and replace it if we've encountered an equivalent one
119
120            /// TODO: I found evidence that some of the UCD functions have disjunctions of nested marker values
121            /// in which one is a superset of the other. It's not safe to eliminate the subset marker unless the
122            /// condition that lead us to compute the first marker is a superset of the condition that let us
123            /// compute the subset value too. We can alter the superset condition to include the union of both
124            /// but this may lead to taking an expensive branch more often. So, we'd need to decide whether the
125            /// cost of each scope is close enough w.r.t. the probability both branches are taken.
126
127            BDD bdd = bdd_zero();
128            bool test = false;
129            std::tie(bdd, test) = characterize(stmt);
130            if (test) {
131                PabloAST * replacement = map.get(bdd);
132                if (LLVM_UNLIKELY(replacement != nullptr)) {
133                    bdd_delref(bdd);
134                    stmt = stmt->replaceWith(replacement, false, true);
135                    continue;
136                }
137            } else if (LLVM_LIKELY(!bdd_constant(bdd))) {
138                map.insert(bdd, stmt);
139            }
140            mCharacterizationMap.emplace(stmt, bdd);
141        }
142        stmt = stmt->getNextNode();
143    }   
144}
145
146/** ------------------------------------------------------------------------------------------------------------- *
147 * @brief characterize
148 ** ------------------------------------------------------------------------------------------------------------- */
149inline std::pair<BDD, bool> BDDMinimizationPass::characterize(Statement * const stmt) {
150
151    BDD bdd = bdd_zero();
152    // Map our operands to the computed BDDs
153    std::array<BDD, 3> input;
154    for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
155        PabloAST * const op = stmt->getOperand(i);
156        if (op == nullptr) {
157            throw std::runtime_error("Statement has Null operand!");
158        }
159        if (LLVM_UNLIKELY(isa<Integer>(op) || isa<String>(op))) {
160            continue;
161        }
162        auto f = mCharacterizationMap.find(op);
163        if (LLVM_UNLIKELY(f == mCharacterizationMap.end())) {
164            std::string tmp;
165            llvm::raw_string_ostream msg(tmp);
166            msg << "BDDMinimizationPass: uncharacterized operand " << std::to_string(i);
167            PabloPrinter::print(stmt, " of ", msg);
168            throw std::runtime_error(msg.str());
169        }
170        input[i] = f->second;
171    }
172
173    switch (stmt->getClassTypeId()) {
174        case TypeId::Assign:
175        case TypeId::Next:
176            return std::make_pair(input[0], false);
177        case TypeId::And:
178            bdd = bdd_and(input[0], input[1]);
179            break;
180        case TypeId::Or:
181            bdd = bdd_or(input[0], input[1]);
182            break;
183        case TypeId::Xor:
184            bdd = bdd_xor(input[0], input[1]);
185            break;
186        case TypeId::Not:
187            bdd = bdd_not(input[0]);
188            break;
189        case TypeId::Sel:
190            bdd = bdd_ite(input[0], input[1], input[2]);
191            break;
192        case TypeId::MatchStar:
193        case TypeId::ScanThru:
194            if (LLVM_UNLIKELY(input[1] == bdd_zero())) {
195                bdd = input[0];
196            }
197        case TypeId::Advance:
198            if (LLVM_UNLIKELY(input[0] == bdd_zero())) {
199                return std::make_pair(bdd_zero(), true);
200            }
201        case TypeId::Call:
202            // TODO: we may have more than one output. Need to fix call class to allow for it.
203            return std::make_pair(bdd_ithvar(mVariables++), false);
204        default:
205            throw std::runtime_error("Unexpected statement type " + stmt->getName()->to_string());
206    }
207    bdd_addref(bdd);
208    if (LLVM_UNLIKELY(bdd_satone(bdd) == bdd_zero())) {
209        bdd_delref(bdd);
210        bdd = bdd_zero();
211    }
212    return std::make_pair(bdd, true);
213}
214
215} // end of namespace pablo
216
Note: See TracBrowser for help on using the repository browser.