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

Last change on this file since 5119 was 5119, checked in by nmedfort, 3 years ago

Work on multiplexing using a fixed window.

File size: 3.5 KB
Line 
1#ifndef PABLO_AUTOMULTIPLEXING_HPP
2#define PABLO_AUTOMULTIPLEXING_HPP
3
4#include <pablo/codegenstate.h>
5#include <util/slab_allocator.h>
6#include <boost/graph/adjacency_list.hpp>
7#include <boost/type_traits/ice.hpp>
8#include <boost/graph/adjacency_matrix.hpp>
9#include <boost/container/flat_set.hpp>
10#include <boost/container/flat_map.hpp>
11#include <boost/numeric/ublas/matrix.hpp>
12#include <random>
13#include <stdint.h>
14#include <llvm/ADT/DenseMap.h>
15#include <llvm/ADT/DenseSet.h>
16#include <llvm/ADT/SmallVector.h>
17#include <z3.h>
18#include <stack>
19
20namespace pablo {
21
22class PabloBuilder;
23class PabloFunction;
24
25class MultiplexingPass {
26
27    using CharacterizationRef = std::pair<Z3_ast, unsigned>;
28    using CharacterizationMap = llvm::DenseMap<const PabloAST *, CharacterizationRef>;
29
30    using ConstraintGraph = boost::adjacency_matrix<boost::undirectedS, Advance *>;
31    using ConstraintVertex = ConstraintGraph::vertex_descriptor;
32    using Constraints = std::vector<ConstraintVertex>;
33    using ConstraintMap = boost::container::flat_map<Advance *, ConstraintVertex>;
34
35    using RNG = std::mt19937;
36    using IntDistribution = std::uniform_int_distribution<RNG::result_type>;
37
38    using CandidateGraph = boost::adjacency_list<boost::setS, boost::vecS, boost::undirectedS>;
39    using Candidates = std::vector<CandidateGraph::vertex_descriptor>;
40
41    using SubsetGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS>;
42
43    using CliqueGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::undirectedS>;
44    using CliqueSet = boost::container::flat_set<CliqueGraph::vertex_descriptor>;
45    using CliqueSets = boost::container::flat_set<std::vector<CliqueGraph::vertex_descriptor>>;
46
47    using AdvanceVector = std::vector<Advance *>;
48    using AdvanceRank = std::vector<int>;
49    using AdvanceVariable = std::vector<Z3_ast>;
50
51public:
52
53    static bool optimize(PabloFunction & function);
54
55protected:
56
57    unsigned initialize(PabloFunction & function);
58    Statement * initialize(Statement * const initial);
59
60    void reset();
61
62    void optimize();
63    void optimize(PabloBlock * const block);
64    Z3_ast characterize(Statement * const stmt);
65    Z3_ast characterize(Advance * const adv, Z3_ast Ik);
66    void multiplex(PabloBlock * const block, Statement * const begin, Statement * const end);
67
68    bool generateCandidateSets(Statement * const begin, Statement * const end);
69    void generateCandidateSets(Z3_context ctx, Z3_solver solver, const std::vector<std::pair<unsigned, unsigned>> & S, const std::vector<Z3_ast> & N);
70
71    void selectMultiplexSetsGreedy();
72
73    void eliminateSubsetConstraints();
74    void doTransitiveReductionOfSubsetGraph();
75
76    void multiplexSelectedSets(PabloBlock * const block, Statement * const begin, Statement * const end);
77
78
79    Z3_ast make(const PabloAST * const expr);
80    Z3_ast add(const PabloAST * const expr, Z3_ast node);
81    Z3_ast & get(const PabloAST * const expr, const bool deref = false);
82    bool equals(Z3_ast a, Z3_ast b);
83
84    MultiplexingPass(PabloFunction & f, const RNG::result_type seed, Z3_context context, Z3_solver solver);
85
86private:
87
88    Z3_context                  mContext;
89    Z3_solver                   mSolver;
90    PabloFunction &             mFunction;
91    RNG                         mRNG;
92
93    CharacterizationMap         mCharacterization;
94    ConstraintGraph             mConstraintGraph;
95
96    AdvanceVariable             mNegatedAdvance;
97    SubsetGraph                 mSubsetGraph;
98    CandidateGraph              mCandidateGraph;
99};
100
101}
102
103#endif // PABLO_AUTOMULTIPLEXING_HPP
Note: See TracBrowser for help on using the repository browser.