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

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

First (hopefully) working version of the boolean reassociation pass + some bug fixes.

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