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

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

Temporary check-in.

File size: 3.6 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;
21class PabloFunction;
22
23class AutoMultiplexing {
24
25    using CharacterizationMap = llvm::DenseMap<const PabloAST *, DdNode *>;
26    using ConstraintGraph = boost::adjacency_matrix<boost::directedS>;
27    using ConstraintVertex = ConstraintGraph::vertex_descriptor;
28    using RNG = std::mt19937;
29    using IntDistribution = std::uniform_int_distribution<RNG::result_type>;
30    using MultiplexSetGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS>;
31    using Trie = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::directedS, ConstraintVertex, boost::no_property>;
32    using SubsetGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS>;
33    // the Advance pointer, input BDD and the BDD variable of the i-th Advance
34    using AdvanceMap = boost::container::flat_map<const Statement *, unsigned>;
35    using AdvanceVector = std::vector<std::tuple<Advance *, DdNode *, DdNode *>>;
36    using VertexVector = std::vector<ConstraintVertex>;
37    using RecentCharacterizations = std::vector<std::pair<const PabloAST *, DdNode *>>;   
38public:
39    static bool optimize(PabloFunction & function);
40protected:
41    bool initialize(PabloFunction & function);
42    void characterize(PabloBlock &block);
43    DdNode * characterize(Statement * const stmt);
44    DdNode * characterize(Advance * adv, DdNode * input);
45    bool notTransitivelyDependant(const ConstraintVertex i, const ConstraintVertex j) const;
46    bool generateCandidateSets(RNG & rng);
47    void addCandidateSet(const VertexVector & S);
48    void selectMultiplexSets(RNG &);
49    void applySubsetConstraints();
50    void multiplexSelectedIndependentSets() const;
51    void simplifyAST(Advance * const muxed[], const unsigned m, PabloBuilder & builder) const;
52    std::pair<PabloAST *, unsigned> simplifyAST(DdManager * manager, DdNode * const f, PabloAST * const variables[], PabloBuilder & builder) const;
53    std::pair<PabloAST *, unsigned> makeCoverAST(DdManager * manager, DdNode * const f, PabloAST * const variables[], PabloBuilder & builder) const;
54    void topologicalSort(PabloBlock & entry) const;
55    inline AutoMultiplexing()
56    : mVariables(0)
57    , mConstraintGraph(0)
58    {
59    }
60private:
61
62    DdNode * Zero() const;
63    DdNode * One() const;
64    bool isZero(DdNode * const x) const;
65    DdNode * And(DdNode * const x, DdNode * const y);
66    DdNode * Or(DdNode * const x, DdNode * const y);
67    DdNode * Xor(DdNode * const x, DdNode * const y);
68    DdNode * Not(DdNode * x) const;
69    DdNode * Ite(DdNode * const x, DdNode * const y, DdNode * const z);
70    DdNode * NewVar();
71    void Ref(DdNode * const x);
72    void Deref(DdNode * const x);
73    bool NoSatisfyingAssignment(DdNode * const x);
74    void Shutdown();
75
76private:
77    DdManager *                 mManager;
78    unsigned                    mVariables;
79    CharacterizationMap         mCharacterizationMap;
80    ConstraintGraph             mConstraintGraph;
81    SubsetGraph                 mSubsetGraph;
82    AdvanceMap                  mAdvanceMap;
83    AdvanceVector               mAdvance;
84    MultiplexSetGraph           mMultiplexSetGraph;
85    RecentCharacterizations     mRecentCharacterizations;
86};
87
88}
89
90#endif // PABLO_AUTOMULTIPLEXING_HPP
Note: See TracBrowser for help on using the repository browser.