source: icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.hpp @ 4639

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

Temporary check in for demuxing simplification.

File size: 3.3 KB
Line 
1#ifndef PABLO_AUTOMULTIPLEXING_HPP
2#define PABLO_AUTOMULTIPLEXING_HPP
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/container/flat_map.hpp>
10#include <boost/numeric/ublas/matrix.hpp>
11#include <random>
12#include <stdint.h>
13#include <llvm/ADT/DenseMap.h>
14
15struct DdManager; // forward declare of the CUDD manager
16struct DdNode;
17
18namespace pablo {
19
20class PabloBuilder;
21
22class AutoMultiplexing {
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
37public:
38    static bool optimize(const std::vector<Var *> & input, PabloBlock & entry);
39protected:
40    void initialize(PabloBlock & entry);
41    void characterize(PabloBlock & block);
42    DdNode * characterize(Statement * const stmt);
43    DdNode * characterize(Advance * adv, DdNode * input);
44    bool notTransitivelyDependant(const ConstraintVertex i, const ConstraintVertex j) const;
45    bool generateMultiplexSets(RNG & rng, unsigned k = 1);
46    void addMultiplexSet(const IndependentSet & N, const IndependentSet & M);
47    void selectMultiplexSets(RNG &);
48    void applySubsetConstraints();
49    void multiplexSelectedIndependentSets() const;
50    void simplify(const std::vector<PabloAST *> & variables, const unsigned n, PabloBuilder & block) const;
51    void topologicalSort(PabloBlock & entry) const;
52    inline AutoMultiplexing(const std::vector<Var *> & vars)
53    : mVariables(0)
54    , mConstraintGraph(0)
55    , mBaseVariables(vars)
56    {
57    }
58private:
59
60    DdNode * Zero() const;
61    DdNode * One() const;
62    bool isZero(DdNode * const x) const;
63    DdNode * And(DdNode * const x, DdNode * const y);
64    DdNode * Or(DdNode * const x, DdNode * const y);
65    DdNode * Xor(DdNode * const x, DdNode * const y);
66    DdNode * Not(DdNode * x) const;
67    DdNode * Ite(DdNode * const x, DdNode * const y, DdNode * const z);
68    DdNode * NewVar();
69    bool NoSatisfyingAssignment(DdNode * const x);
70    void Shutdown();
71
72private:
73    DdManager *                 mManager;
74    unsigned                    mVariables;
75    CharacterizationMap         mCharacterizationMap;
76    ConstraintGraph             mConstraintGraph;
77    SubsetGraph                 mSubsetGraph;
78    AdvanceMap                  mAdvanceMap;
79    AdvanceVector               mAdvance;
80    MultiplexSetGraph           mMultiplexSetGraph;
81    const std::vector<Var *> &  mBaseVariables;
82};
83
84}
85
86#endif // PABLO_AUTOMULTIPLEXING_HPP
Note: See TracBrowser for help on using the repository browser.