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

Last change on this file since 5233 was 5202, checked in by nmedfort, 3 years ago

Initial work on adding types to PabloAST and mutable Var objects.

File size: 9.8 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 * const 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(), PabloBlock::createZeroes());
97    baseMap.insert(bdd_one(), PabloBlock::createOnes());
98    eliminateLogicallyEquivalentStatements(function.getEntryBlock(), baseMap);
99}
100
101/** ------------------------------------------------------------------------------------------------------------- *
102 * @brief eliminateLogicallyEquivalentStatements
103 ** ------------------------------------------------------------------------------------------------------------- */
104void BDDMinimizationPass::eliminateLogicallyEquivalentStatements(PabloBlock * const 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 (Var * var : cast<const While>(stmt)->getVariants()) {
113                bdd_delref(mCharacterizationMap[var]);
114                mCharacterizationMap.erase(var);
115            }
116        } else { // attempt to characterize this statement and replace it if we've encountered an equivalent one
117
118            /// TODO: I found evidence that some of the UCD functions have disjunctions of nested marker values
119            /// in which one is a superset of the other. It's not safe to eliminate the subset marker unless the
120            /// condition that lead us to compute the first marker is a superset of the condition that let us
121            /// compute the subset value too. We can alter the superset condition to include the union of both
122            /// but this may lead to taking an expensive branch more often. So, we'd need to decide whether the
123            /// cost of each scope is close enough w.r.t. the probability both branches are taken.
124
125            BDD bdd = bdd_zero();
126            bool test = false;
127            std::tie(bdd, test) = characterize(stmt);
128            if (test) {
129                PabloAST * replacement = map.get(bdd);
130                if (LLVM_UNLIKELY(replacement != nullptr)) {
131                    bdd_delref(bdd);
132                    stmt = stmt->replaceWith(replacement, false, true);
133                    continue;
134                }
135            } else if (LLVM_LIKELY(!bdd_constant(bdd))) {
136                map.insert(bdd, stmt);
137            }
138            mCharacterizationMap.emplace(stmt, bdd);
139        }
140        stmt = stmt->getNextNode();
141    }   
142}
143
144/** ------------------------------------------------------------------------------------------------------------- *
145 * @brief throwUnexpectedStatementTypeError
146 ** ------------------------------------------------------------------------------------------------------------- */
147static void throwUnexpectedStatementTypeError(const Statement * const stmt) {
148    std::string tmp;
149    raw_string_ostream err(tmp);
150    err << "Unexpected statement type ";
151    PabloPrinter::print(stmt, err);
152    throw std::runtime_error(err.str());
153}
154
155/** ------------------------------------------------------------------------------------------------------------- *
156 * @brief characterize
157 ** ------------------------------------------------------------------------------------------------------------- */
158inline std::pair<BDD, bool> BDDMinimizationPass::characterize(Statement * const stmt) {
159    BDD bdd = get(stmt->getOperand(0));
160    switch (stmt->getClassTypeId()) {
161        case TypeId::Assign:
162        case TypeId::Next:
163            break;
164        case TypeId::And:
165            for (unsigned i = 1; i != stmt->getNumOperands(); ++i) {
166                bdd = bdd_and(bdd, get(stmt->getOperand(i)));
167            }
168            break;
169        case TypeId::Or:
170            for (unsigned i = 1; i != stmt->getNumOperands(); ++i) {
171                bdd = bdd_or(bdd, get(stmt->getOperand(i)));
172            }
173            break;
174        case TypeId::Xor:
175            for (unsigned i = 1; i != stmt->getNumOperands(); ++i) {
176                bdd = bdd_xor(bdd, get(stmt->getOperand(i)));
177            }
178            break;
179        case TypeId::Not:
180            bdd = bdd_not(bdd);
181            break;
182        case TypeId::Sel:
183            bdd = bdd_ite(bdd, get(stmt->getOperand(1)), get(stmt->getOperand(2)));
184            break;
185        case TypeId::MatchStar:
186        case TypeId::ScanThru:
187            if (LLVM_UNLIKELY(get(stmt->getOperand(1)) == bdd_zero())) {
188                break;
189            }
190        case TypeId::Advance:
191            if (LLVM_UNLIKELY(bdd == bdd_zero())) {
192                return std::make_pair(bdd_zero(), true);
193            }
194        case TypeId::Call:
195            // TODO: we may have more than one output. Need to fix call class to allow for it.
196            return std::make_pair(bdd_ithvar(mVariables++), false);
197        default:
198            throwUnexpectedStatementTypeError(stmt);
199    }
200    bdd_addref(bdd);
201    if (LLVM_UNLIKELY(bdd_satone(bdd) == bdd_zero())) {
202        bdd_delref(bdd);
203        bdd = bdd_zero();
204    }
205    return std::make_pair(bdd, true);
206}
207
208/** ------------------------------------------------------------------------------------------------------------- *
209 * @brief throwUnexpectedStatementTypeError
210 ** ------------------------------------------------------------------------------------------------------------- */
211static void throwUncharacterizedOperand(const PabloAST * const expr) {
212    std::string tmp;
213    raw_string_ostream err(tmp);
214    err << "Uncharacterized operand ";
215    PabloPrinter::print(expr, err);
216    throw std::runtime_error(err.str());
217}
218
219/** ------------------------------------------------------------------------------------------------------------- *
220 * @brief get
221 ** ------------------------------------------------------------------------------------------------------------- */
222inline BDD & BDDMinimizationPass::get(const PabloAST * const expr) {
223    auto f = mCharacterizationMap.find(expr);
224    if (LLVM_UNLIKELY(f == mCharacterizationMap.end())) {
225        throwUncharacterizedOperand(expr);
226    }
227    return f->second;
228}
229
230} // end of namespace pablo
231
Note: See TracBrowser for help on using the repository browser.