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

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

Temporary check in.

File size: 2.4 KB
Line 
1#ifndef PABLO_BDDMINIMIZATION_H
2#define PABLO_BDDMINIMIZATION_H
3
4#include <pablo/codegenstate.h>
5#include <slab_allocator.h>
6#include <queue>
7#include <boost/graph/adjacency_list.hpp>
8#include <boost/graph/adjacency_matrix.hpp>
9#include <boost/graph/edge_list.hpp>
10#include <boost/container/flat_map.hpp>
11#include <boost/container/flat_set.hpp>
12#include <boost/numeric/ublas/matrix.hpp>
13#include <random>
14#include <stdint.h>
15#include <llvm/ADT/DenseMap.h>
16
17struct DdManager; // forward declare of the CUDD manager
18struct DdNode;
19
20namespace pablo {
21
22class BDDMinimizationPass {
23
24    using CharacterizationMap = llvm::DenseMap<const PabloAST *, DdNode *>;
25
26    struct SubsitutionMap {
27        SubsitutionMap(SubsitutionMap * parent = nullptr) : mParent(parent) {}
28
29        PabloAST * operator [](const DdNode * node) const {
30            auto f = mMap.find(node);
31            if (f == mMap.end()) {
32                return mParent ? mParent->find(node) : nullptr;
33            }
34            return f->second;
35        }
36
37        void insert(const DdNode * node, PabloAST * stmt) {
38            mMap.insert(std::make_pair(node, stmt));
39        }
40    private:
41        const SubsitutionMap * const mParent;
42        llvm::DenseMap<const DdNode *, PabloAST *> mMap;
43    };
44
45public:
46    static bool optimize(PabloFunction & function);
47protected:
48    void initialize(PabloFunction & function);
49    void characterize(const PabloBlock &block);
50    DdNode * characterize(const Statement * const stmt);
51    void eliminateLogicallyEquivalentStatements(PabloBlock & entry);
52    void eliminateLogicallyEquivalentStatements(PabloBlock & block, SubsitutionMap & parent);
53    void simplify(PabloBlock & entry);
54    PabloAST * simplify(DdNode * bdd);
55
56private:
57    DdNode * Zero() const;
58    DdNode * One() const;
59    bool isZero(DdNode * const x) const;
60    DdNode * And(DdNode * const x, DdNode * const y);
61    DdNode * Intersect(DdNode * const x, DdNode * const y);
62    DdNode * Or(DdNode * const x, DdNode * const y);
63    DdNode * Xor(DdNode * const x, DdNode * const y);
64    DdNode * Not(DdNode * x) const;
65    DdNode * Ite(DdNode * const x, DdNode * const y, DdNode * const z);
66    DdNode * NewVar();
67    bool noSatisfyingAssignment(DdNode * const x);
68    void shutdown();
69private:
70    DdManager *             mManager;
71    unsigned                mVariables;
72    CharacterizationMap     mCharacterizationMap;
73};
74
75
76#endif // PABLO_BDDMINIMIZATION_H
Note: See TracBrowser for help on using the repository browser.