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

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

Temporary check in.

File size: 12.2 KB
Line 
1#include "pablo_bddminimization.h"
2#include <pablo/codegenstate.h>
3#include <llvm/ADT/BitVector.h>
4#include <stack>
5#include <queue>
6#include <unordered_set>
7#include <boost/container/flat_set.hpp>
8#include <boost/numeric/ublas/matrix.hpp>
9#include <boost/circular_buffer.hpp>
10#include <include/simd-lib/builtins.hpp>
11#include <pablo/builder.hpp>
12#include <boost/range/iterator_range.hpp>
13#include <pablo/printer_pablos.h>
14#include <cudd.h>
15#include <util.h>
16
17using namespace llvm;
18using namespace boost;
19using namespace boost::container;
20using namespace boost::numeric::ublas;
21
22// #define PRINT_DEBUG_OUTPUT
23
24#if !defined(NDEBUG) || defined(PRINT_DEBUG_OUTPUT)
25#include <iostream>
26
27using namespace pablo;
28typedef uint64_t timestamp_t;
29
30static inline timestamp_t read_cycle_counter() {
31#ifdef __GNUC__
32timestamp_t ts;
33#ifdef __x86_64__
34  unsigned int eax, edx;
35  asm volatile("rdtsc" : "=a" (eax), "=d" (edx));
36  ts = ((timestamp_t) eax) | (((timestamp_t) edx) << 32);
37#else
38  asm volatile("rdtsc\n" : "=A" (ts));
39#endif
40  return(ts);
41#endif
42#ifdef _MSC_VER
43  return __rdtsc();
44#endif
45}
46
47#define LOG(x) std::cerr << x << std::endl;
48#define RECORD_TIMESTAMP(Name) const timestamp_t Name = read_cycle_counter()
49#define LOG_GRAPH(Name, G) \
50    LOG(Name << " |V|=" << num_vertices(G) << ", |E|="  << num_edges(G) << \
51                " (" << (((double)num_edges(G)) / ((double)(num_vertices(G) * (num_vertices(G) - 1) / 2))) << ')')
52
53
54#else
55#define LOG(x)
56#define RECORD_TIMESTAMP(Name)
57#define LOG_GRAPH(Name, G)
58#define LOG_NUMBER_OF_ADVANCES(entry)
59#endif
60
61
62namespace pablo {
63
64bool BDDMinimizationPass::optimize(PabloFunction & function) {
65
66    BDDMinimizationPass am;
67    RECORD_TIMESTAMP(start_initialize);
68    am.initialize(function);
69    RECORD_TIMESTAMP(end_initialize);
70
71    LOG("Initialize:              " << (end_initialize - start_initialize));
72
73    RECORD_TIMESTAMP(start_characterize);
74    am.characterize(entry);
75    RECORD_TIMESTAMP(end_characterize);
76
77    LOG("Characterize:            " << (end_characterize - start_characterize));
78
79    RECORD_TIMESTAMP(start_minimization);
80    am.eliminateLogicallyEquivalentStatements(entry);
81    RECORD_TIMESTAMP(end_minimization);
82    LOG("Minimize:                " << (end_minimization - start_minimization));
83
84    RECORD_TIMESTAMP(start_minimization);
85    am.simplify(entry);
86    RECORD_TIMESTAMP(end_minimization);
87    LOG("Minimize:                " << (end_minimization - start_minimization));
88
89    RECORD_TIMESTAMP(start_shutdown);
90    am.shutdown();
91    RECORD_TIMESTAMP(end_shutdown);
92    LOG("Shutdown:                " << (end_shutdown - start_shutdown));
93
94
95
96    return multiplex;
97}
98
99/** ------------------------------------------------------------------------------------------------------------- *
100 * @brief initialize
101 * @param vars the input vars for this program
102 * @param entry the entry block
103 *
104 * Scan through the program to identify any advances and calls then initialize the BDD engine with
105 * the proper variable ordering.
106 ** ------------------------------------------------------------------------------------------------------------- */
107void BDDMinimizationPass::initialize(PabloFunction &function) {
108
109    std::stack<Statement *> scope;
110    unsigned variableCount = 0; // number of statements that cannot always be categorized without generating a new variable
111
112    for (Statement * stmt = function.getEntryBlock().front(); ; ) {
113        while ( stmt ) {
114
115            if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
116                // Set the next statement to be the first statement of the inner scope and push the
117                // next statement of the current statement into the scope stack.
118                const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
119                scope.push(stmt->getNextNode());
120                stmt = nested.front();
121                assert (stmt);
122                continue;
123            }
124
125            switch (stmt->getClassTypeId()) {
126                case PabloAST::ClassTypeId::Advance:
127                case PabloAST::ClassTypeId::Call:
128                case PabloAST::ClassTypeId::ScanThru:
129                case PabloAST::ClassTypeId::MatchStar:
130                    variableCount++;
131                    break;
132                default:
133                    break;
134            }
135            stmt = stmt->getNextNode();
136        }
137        if (scope.empty()) {
138            break;
139        }
140        stmt = scope.top();
141        scope.pop();
142    }
143
144    // Initialize the BDD engine ...
145    mManager = Cudd_Init((variableCount + function.getNumOfParameters()), 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0);
146    Cudd_AutodynDisable(mManager);
147
148    // Map the predefined 0/1 entries
149    mCharacterizationMap[function.getEntryBlock().createZeroes()] = Zero();
150    mCharacterizationMap[function.getEntryBlock().createOnes()] = One();
151
152    // Order the variables so the input Vars are pushed to the end; they ought to
153    // be the most complex to resolve.
154    for (auto i = 0; i != function.getNumOfParameters(); ++i) {
155        mCharacterizationMap[function.getParameter(i)] = Cudd_bddIthVar(mManager, variableCount++);
156    }
157}
158
159/** ------------------------------------------------------------------------------------------------------------- *
160 * @brief characterize
161 * @param vars the input vars for this program
162 *
163 * Scan through the program and iteratively compute the BDDs for each statement.
164 ** ------------------------------------------------------------------------------------------------------------- */
165void BDDMinimizationPass::characterize(const PabloBlock & block) {
166    for (Statement * stmt : block) {
167        if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
168            // Set the next statement to be the first statement of the inner scope and push the
169            // next statement of the current statement into the scope stack.
170            characterize(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
171            continue;
172        }
173        mCharacterizationMap[stmt] =  characterize(stmt);
174    }
175}
176
177/** ------------------------------------------------------------------------------------------------------------- *
178 * @brief characterize
179 ** ------------------------------------------------------------------------------------------------------------- */
180inline DdNode * BDDMinimizationPass::characterize(const Statement * const stmt) {
181
182    DdNode * bdd = nullptr;
183    // Map our operands to the computed BDDs
184    std::array<DdNode *, 3> input;
185    for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
186        PabloAST * const op = stmt->getOperand(i);
187        if (LLVM_UNLIKELY(isa<Integer>(op) || isa<String>(op))) {
188            continue;
189        }
190        input[i] = mCharacterizationMap[op];
191    }
192
193    switch (stmt->getClassTypeId()) {
194        case PabloAST::ClassTypeId::Assign:
195            return input[0];
196        case PabloAST::ClassTypeId::And:
197            bdd = And(input[0], input[1]);
198            break;
199        case PabloAST::ClassTypeId::Next:
200        case PabloAST::ClassTypeId::Or:
201            bdd = Or(input[0], input[1]);
202            break;
203        case PabloAST::ClassTypeId::Xor:
204            bdd = Xor(input[0], input[1]);
205            break;
206        case PabloAST::ClassTypeId::Not:
207            bdd = Not(input[0]);
208            break;
209        case PabloAST::ClassTypeId::Sel:
210            bdd = Ite(input[0], input[1], input[2]);
211            break;
212        case PabloAST::ClassTypeId::ScanThru:
213        case PabloAST::ClassTypeId::MatchStar:
214        case PabloAST::ClassTypeId::Call:
215        case PabloAST::ClassTypeId::Advance:
216            return NewVar();
217        default:
218            throw std::runtime_error("Unexpected statement type " + stmt->getName()->to_string());
219    }
220
221    if (LLVM_UNLIKELY(noSatisfyingAssignment(bdd))) {
222        Cudd_RecursiveDeref(mManager, bdd);
223        bdd = Zero();
224    }
225
226    return bdd;
227
228}
229
230/** ------------------------------------------------------------------------------------------------------------- *
231 * @brief eliminateLogicallyEquivalentStatements
232 * @param entry the entry block of the program
233 *
234 * Scan through the program using the precomputed BDDs and replace any statements with equivalent BDDs with the
235 * earlier one (assuming its in scope) and replace any contradictions with Zero.
236 ** ------------------------------------------------------------------------------------------------------------- */
237inline void BDDMinimizationPass::eliminateLogicallyEquivalentStatements(PabloBlock & entry) {
238    SubsitutionMap baseMap;
239    baseMap.insert(Zero(), entry.createZeroes());
240    baseMap.insert(One(), entry.createOnes());
241    eliminateLogicallyEquivalentStatements(entry, baseMap);
242}
243
244/** ------------------------------------------------------------------------------------------------------------- *
245 * @brief eliminateLogicallyEquivalentStatements
246 ** ------------------------------------------------------------------------------------------------------------- */
247void BDDMinimizationPass::eliminateLogicallyEquivalentStatements(PabloBlock & block, SubsitutionMap & parent) {
248    SubsitutionMap subsitutionMap(&parent);
249    Statement * stmt = block.front();
250    while (stmt) {
251        if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
252            // Set the next statement to be the first statement of the inner scope and push the
253            // next statement of the current statement into the scope stack.
254            eliminateLogicallyEquivalentStatements(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(), subsitutionMap);
255            continue;
256        }
257
258        if (LLVM_UNLIKELY(isa<Assign>(stmt) || isa<Next>(stmt))) {
259            continue;
260        }
261
262        DdNode * bdd = mCharacterizationMap[stmt];
263        PabloAST * replacement = subsitutionMap[bdd];
264        if (replacement) {
265            Cudd_RecursiveDeref(mManager, bdd);
266            stmt = stmt->replaceWith(replacement, false, true);
267        }
268        else {
269            stmt = stmt->getNextNode();
270        }
271    }
272}
273
274/** ------------------------------------------------------------------------------------------------------------- *
275 * @brief simplify
276 ** ------------------------------------------------------------------------------------------------------------- */
277PabloAST * BDDMinimizationPass::simplify(DdNode * bdd) const {
278
279    CUDD_VALUE_TYPE value;
280    int * cube = nullptr;
281
282    DdGen * gen = Cudd_FirstCube(mManager, bdd, &cube, &value);
283    while (!Cudd_IsGenEmpty(gen)) {
284        // cube[0 ... n - 1] = { 0 : false, 1: true, 2: don't care }
285
286
287
288
289        Cudd_NextCube(gen, &cube, &value);
290    }
291    Cudd_GenFree(gen);
292
293}
294
295/** ------------------------------------------------------------------------------------------------------------- *
296 * @brief CUDD wrappers
297 ** ------------------------------------------------------------------------------------------------------------- */
298
299inline DdNode * BDDMinimizationPass::Zero() const {
300    return Cudd_ReadLogicZero(mManager);
301}
302
303inline DdNode * BDDMinimizationPass::One() const {
304    return Cudd_ReadOne(mManager);
305}
306
307inline DdNode * BDDMinimizationPass::NewVar() {
308    return Cudd_bddIthVar(mManager, mVariables++);
309}
310
311inline bool BDDMinimizationPass::isZero(DdNode * const x) const {
312    return x == Zero();
313}
314
315inline DdNode * BDDMinimizationPass::And(DdNode * const x, DdNode * const y) {
316    DdNode * r = Cudd_bddAnd(mManager, x, y);
317    Cudd_Ref(r);
318    return r;
319}
320
321inline DdNode * BDDMinimizationPass::Intersect(DdNode * const x, DdNode * const y) {
322    DdNode * r = Cudd_bddIntersect(mManager, x, y); Cudd_Ref(r);
323    return r;
324}
325
326inline DdNode * BDDMinimizationPass::Or(DdNode * const x, DdNode * const y) {
327    DdNode * r = Cudd_bddOr(mManager, x, y);
328    Cudd_Ref(r);
329    return r;
330}
331
332inline DdNode * BDDMinimizationPass::Xor(DdNode * const x, DdNode * const y) {
333    DdNode * r = Cudd_bddXor(mManager, x, y);
334    Cudd_Ref(r);
335    return r;
336}
337
338inline DdNode * BDDMinimizationPass::Not(DdNode * const x) const {
339    return Cudd_Not(x);
340}
341
342inline DdNode * BDDMinimizationPass::Ite(DdNode * const x, DdNode * const y, DdNode * const z) {
343    DdNode * r = Cudd_bddIte(mManager, x, y, z);
344    Cudd_Ref(r);
345    return r;
346}
347
348inline bool BDDMinimizationPass::noSatisfyingAssignment(DdNode * const x) {
349    return Cudd_bddLeq(mManager, x, Zero());
350}
351
352inline void BDDMinimizationPass::shutdown() {
353    Cudd_Quit(mManager);
354}
355
356
357
358} // end of namespace pablo
359
Note: See TracBrowser for help on using the repository browser.