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

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

Temporary check-in.

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