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

Last change on this file since 4725 was 4725, 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 Terminals = std::vector<Statement *>;
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, const bool full = false);
43protected:
44    void eliminateLogicallyEquivalentStatements(PabloFunction & function);
45    void eliminateLogicallyEquivalentStatements(PabloBlock & block, SubsitutionMap & parent);
46    DdNode * eliminateLogicallyEquivalentStatements(const Statement * const stmt);
47    void simplifyAST(PabloFunction & function);
48    void simplifyAST(PabloBuilder & block, std::vector<Statement *> &terminals);
49    DdNode * characterizeTerminalBddTree(PabloAST * expr);
50    void simplifyAST(Statement *stmt, Statement * const value, PabloBuilder & builder);
51    PabloAST * simplifyAST(DdNode * const f, const std::vector<PabloAST *> & variables, PabloBuilder & builder);
52    PabloAST * makeCoverAST(DdNode * const f, const std::vector<PabloAST *> & variables, PabloBuilder & builder);
53private:
54    DdNode * Zero() const;
55    DdNode * One() const;
56    bool isZero(DdNode * const x) const;
57    DdNode * And(DdNode * const x, DdNode * const y);
58    DdNode * Intersect(DdNode * const x, DdNode * const y);
59    DdNode * Or(DdNode * const x, DdNode * const y);
60    DdNode * Xor(DdNode * const x, DdNode * const y);
61    DdNode * Not(DdNode * x) const;
62    DdNode * Ite(DdNode * const x, DdNode * const y, DdNode * const z);
63    DdNode * NewVar(const PabloAST * expr);
64    bool noSatisfyingAssignment(DdNode * const x);
65    void shutdown();
66private:
67    DdManager *                     mManager;
68    std::vector<PabloAST *>         mVariables;
69    CharacterizationMap             mCharacterizationMap;
70};
71
72}
73
74#endif // PABLO_BDDMINIMIZATION_H
Note: See TracBrowser for help on using the repository browser.