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

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

Couple modifications to the UCD compiler. Splitting Multiplexing from BDD Minimization.

File size: 4.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    using ConstraintGraph = boost::adjacency_matrix<boost::directedS>;
26    using ConstraintVertex = ConstraintGraph::vertex_descriptor;
27    using RNG = std::mt19937;
28    using IntDistribution = std::uniform_int_distribution<RNG::result_type>;
29    using MultiplexSetGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS>;
30    using IndependentSetGraph = boost::adjacency_matrix<boost::undirectedS, std::pair<int, int>>;
31    using SubsetGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS>;
32    // the Advance pointer, input BDD and the BDD variable of the i-th Advance
33    using AdvanceMap = boost::container::flat_map<const Statement *, unsigned>;
34    using AdvanceVector = std::vector<std::tuple<Advance *, DdNode *, DdNode *>>;
35    using IndependentSet = std::vector<ConstraintVertex>;
36
37    struct SubsitutionMap {
38        SubsitutionMap(SubsitutionMap * parent = nullptr) : mParent(parent) {}
39        PabloAST * test(const DdNode * node, PabloAST * stmt) {
40            PabloAST * replacement = find(node);
41            if (LLVM_LIKELY(replacement == nullptr)) {
42                mMap.insert(std::make_pair(node, stmt));
43            }
44            return replacement;
45        }
46        PabloAST * find(const DdNode * node) const {
47            auto f = mMap.find(node);
48            if (LLVM_LIKELY(f == mMap.end())) {
49                PabloAST * replacement = nullptr;
50                if (mParent == nullptr) {
51                    replacement = mParent->find(node);
52                }
53                return replacement;
54            }
55            return f->second;
56        }
57        void insert(const DdNode * node, PabloAST * stmt) {
58            mMap.insert(std::make_pair(node, stmt));
59        }
60    private:
61        const SubsitutionMap * const mParent;
62        llvm::DenseMap<const DdNode *, PabloAST *> mMap;
63    };
64
65public:
66    static bool optimize(const std::vector<Var *> & input, PabloBlock & entry);
67protected:
68    void initialize(const std::vector<Var *> & vars, PabloBlock & entry);
69    void characterize(PabloBlock & block);
70    DdNode * characterize(Statement * const stmt, const bool throwUncharacterizedOperandError);
71    DdNode * characterize(Advance * adv, DdNode * input);
72    void reevaluate(Next * next, DdNode * value);
73    void minimize(PabloBlock & entry);
74    void minimize(PabloBlock & block, SubsitutionMap & parent);
75
76    bool notTransitivelyDependant(const ConstraintVertex i, const ConstraintVertex j) const;
77    bool generateMultiplexSets(RNG & rng, unsigned k = 1);
78    void addMultiplexSet(const IndependentSet & N, const IndependentSet & M);
79    void selectMultiplexSets(RNG &);
80    void applySubsetConstraints();
81    void multiplexSelectedIndependentSets() const;
82    void topologicalSort(PabloBlock & entry) const;
83    inline AutoMultiplexing()
84    : mVariables(0)
85    , mConstraintGraph(0)
86    {
87    }
88private:
89    DdNode * Zero() const;
90    DdNode * One() const;
91    bool isZero(DdNode * const x) const;
92    DdNode * And(DdNode * const x, DdNode * const y);
93    DdNode * Intersect(DdNode * const x, DdNode * const y);
94    DdNode * Or(DdNode * const x, DdNode * const y);
95    DdNode * Xor(DdNode * const x, DdNode * const y);
96    DdNode * Not(DdNode * x) const;
97    DdNode * Ite(DdNode * const x, DdNode * const y, DdNode * const z);
98    DdNode * NewVar();
99    bool noSatisfyingAssignment(DdNode * const x);
100    void shutdown();
101private:
102    DdManager *             mManager;
103    unsigned                mVariables;
104    CharacterizationMap     mCharacterizationMap;
105    ConstraintGraph         mConstraintGraph;
106    SubsetGraph             mSubsetGraph;
107    AdvanceMap              mAdvanceMap;
108    AdvanceVector           mAdvance;
109    MultiplexSetGraph       mMultiplexSetGraph;
110};
111
112
113#endif // PABLO_BDDMINIMIZATION_H
Note: See TracBrowser for help on using the repository browser.