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

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

Work on multiplexing and distribution passes + a few AST modification bug fixes.

File size: 2.8 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 <stdint.h>
11#include <llvm/ADT/DenseMap.h>
12#include <z3.h>
13
14namespace pablo {
15
16class PabloBuilder;
17class PabloFunction;
18
19class MultiplexingPass {
20
21    using CharacterizationRef = std::pair<Z3_ast, size_t>;
22    using CharacterizationMap = llvm::DenseMap<const PabloAST *, CharacterizationRef>;
23
24    enum class ConstraintType : uint8_t {
25        Dependency,
26        Inclusive
27    };
28
29    using ConstraintGraph = boost::adjacency_matrix<boost::undirectedS, Advance *, ConstraintType>;
30    using ConstraintVertex = ConstraintGraph::vertex_descriptor;
31    using Constraints = std::vector<ConstraintVertex>;
32
33    using CandidateGraph = boost::adjacency_list<boost::setS, boost::vecS, boost::undirectedS>;
34    using Candidates = std::vector<CandidateGraph::vertex_descriptor>;
35
36    using SubsetGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS>;
37
38    using AdvanceVariable = std::vector<Z3_ast>;
39
40public:
41
42    static bool optimize(PabloFunction & function);
43
44protected:
45
46    unsigned initialize(PabloFunction & function);
47    Statement * initialize(Statement * const initial);
48
49    void reset();
50
51    void optimize();
52    void optimize(PabloBlock * const block);
53    Z3_ast characterize(const Statement * const stmt, const bool deref = true);
54    Z3_ast characterize(const Advance * const adv, Z3_ast Ik);
55    void multiplex(PabloBlock * const block, Statement * const begin, Statement * const end);
56
57    bool generateCandidateSets(Statement * const begin, Statement * const end);
58    void generateCandidateSets(Z3_context ctx, Z3_solver solver, const std::vector<std::pair<unsigned, unsigned>> & S, const std::vector<Z3_ast> & N);
59
60    void selectMultiplexSetsGreedy();
61
62    void eliminateSubsetConstraints();
63    void doTransitiveReductionOfSubsetGraph();
64
65    void multiplexSelectedSets(PabloBlock * const block, Statement * const begin, Statement * const end);
66
67
68    Z3_ast makeVar();
69    Z3_ast add(const PabloAST * const expr, Z3_ast node, const size_t refs);
70    Z3_ast & get(const PabloAST * const expr, const bool deref = false);
71    bool equals(Z3_ast a, Z3_ast b);
72
73    MultiplexingPass(PabloFunction & f, Z3_context context, Z3_solver solver);
74
75private:
76
77    Z3_context                  mContext;
78    Z3_solver                   mSolver;
79    PabloFunction &             mFunction;
80
81    CharacterizationMap         mCharacterization;
82    ConstraintGraph             mConstraintGraph;
83
84    AdvanceVariable             mNegatedAdvance;
85    SubsetGraph                 mSubsetGraph;
86    CandidateGraph              mCandidateGraph;
87};
88
89}
90
91#endif // PABLO_AUTOMULTIPLEXING_HPP
Note: See TracBrowser for help on using the repository browser.