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

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

Continued work on multiplexing pass.

File size: 4.2 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 <boost/graph/adjacency_list.hpp>
7#include <boost/graph/adjacency_matrix.hpp>
8#include <boost/container/flat_set.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
15typedef int BDD;
16
17namespace pablo {
18
19class PabloBuilder;
20class PabloFunction;
21struct OrderingVerifier;
22
23class MultiplexingPass {
24
25    using CharacterizationMap = llvm::DenseMap<const PabloAST *, BDD>;
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 SubsetGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS>;
32    using SubsetEdgeIterator = boost::graph_traits<SubsetGraph>::edge_iterator;
33    using CliqueGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::undirectedS>;
34    using CliqueSet = boost::container::flat_set<CliqueGraph::vertex_descriptor>;
35    using CliqueSets = boost::container::flat_set<std::vector<CliqueGraph::vertex_descriptor>>;
36
37    using AdvanceVector = std::vector<Advance *>;
38    using AdvanceDepth = std::vector<int>;
39    using AdvanceVariable = std::vector<BDD>;
40    using VertexVector = std::vector<ConstraintVertex>;
41
42public:
43
44    static bool optimize(PabloFunction & function, const unsigned limit = std::numeric_limits<unsigned>::max(), const unsigned maxSelections = 100, const unsigned windowSize = 1, const bool independent = false);
45
46protected:
47
48    unsigned initialize(PabloFunction & function, const bool independent);
49    void initializeBaseConstraintGraph(PabloBlock * const block, const unsigned statements, const unsigned advances);
50    void initializeAdvanceDepth(PabloBlock * const block, const unsigned advances) ;
51
52    void characterize(PabloBlock * const block);
53    BDD characterize(Statement * const stmt);
54    BDD characterize(Advance * const adv, const BDD Ik);
55    bool independent(const ConstraintVertex i, const ConstraintVertex j) const;
56    bool exceedsWindowSize(const ConstraintVertex i, const ConstraintVertex j) const;
57
58    void generateUsageWeightingGraph();
59    CliqueSets findMaximalCliques(const CliqueGraph & G);
60    void findMaximalCliques(const CliqueGraph & G, CliqueSet & R, CliqueSet && P, CliqueSet && X, CliqueSets & S);
61
62    bool generateCandidateSets();
63    void addCandidateSet(const VertexVector & S);
64    void selectMultiplexSets();
65
66    void eliminateSubsetConstraints();
67    void doTransitiveReductionOfSubsetGraph();
68
69    void multiplexSelectedIndependentSets(PabloFunction & function);
70
71    static void topologicalSort(PabloFunction & function);
72    static void topologicalSort(PabloBlock * block, OrderingVerifier & parent);
73
74    BDD & get(const PabloAST * const expr);
75
76    inline MultiplexingPass(const RNG::result_type seed, const unsigned limit, const unsigned maxSelections, const unsigned windowSize)
77    : mMultiplexingSetSizeLimit(limit)
78    , mMaxMultiplexingSetSelections(maxSelections)
79    , mWindowSize(windowSize)
80    , mTestConstrainedAdvances(true)
81    , mVariables(0)
82    , mRNG(seed)
83    , mConstraintGraph(0)
84    , mAdvance(0, nullptr)
85    , mAdvanceDepth(0, 0)
86    , mAdvanceNegatedVariable(0, 0)
87    {
88
89    }
90
91private:
92    const unsigned              mMultiplexingSetSizeLimit;
93    const unsigned              mMaxMultiplexingSetSelections;
94    const unsigned              mWindowSize;
95    const bool                  mTestConstrainedAdvances;
96    unsigned                    mVariables;
97    RNG                         mRNG;
98    CharacterizationMap         mCharacterization;
99    ConstraintGraph             mConstraintGraph;   
100    AdvanceVector               mAdvance;
101    AdvanceDepth                mAdvanceDepth;
102    AdvanceVariable             mAdvanceNegatedVariable;
103    SubsetGraph                 mSubsetGraph;
104    CliqueGraph                 mUsageWeightingGraph;
105    MultiplexSetGraph           mMultiplexSetGraph;
106};
107
108}
109
110#endif // PABLO_AUTOMULTIPLEXING_HPP
Note: See TracBrowser for help on using the repository browser.