LLVM: include/llvm/Support/BalancedPartitioning.h Source File (original) (raw)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39#ifndef LLVM_SUPPORT_BALANCED_PARTITIONING_H
40#define LLVM_SUPPORT_BALANCED_PARTITIONING_H
41
45
46#include
47#include <condition_variable>
48#include
49#include
50#include
51
52namespace llvm {
53
55
56
59
60public:
63
64
67
68
70
72
73protected:
74
76
78
80
84};
85
86
88
90
92
93
95
96
97
99};
100
102public:
104
105
106 LLVM_ABI void run(std::vector &Nodes) const;
107
108private:
109 struct UtilitySignature;
111 using FunctionNodeRange =
113
114
115
116
117
118 struct BPThreadPool {
120 std::mutex mtx;
121 std::condition_variable cv;
122
123 std::atomic NumActiveThreads = 0;
124
125 bool IsFinishedSpawning = false;
126
127 template void async(Func &&F);
128
129
130
133 : TheThreadPool(TheThreadPool) {}
134 };
135
136
137
138
139
140
141 void bisect(const FunctionNodeRange Nodes, unsigned RecDepth,
142 unsigned RootBucket, unsigned Offset,
143 std::optional &TP) const;
144
145
146 void runIterations(const FunctionNodeRange Nodes, unsigned LeftBucket,
147 unsigned RightBucket, std::mt19937 &RNG) const;
148
149
150
151 unsigned runIteration(const FunctionNodeRange Nodes, unsigned LeftBucket,
152 unsigned RightBucket, SignaturesT &Signatures,
153 std::mt19937 &RNG) const;
154
155
156
157 bool moveFunctionNode(BPFunctionNode &N, unsigned LeftBucket,
158 unsigned RightBucket, SignaturesT &Signatures,
159 std::mt19937 &RNG) const;
160
161
162
163 void split(const FunctionNodeRange Nodes, unsigned StartBucket) const;
164
165
166
167 float logCost(unsigned X, unsigned Y) const;
168
169 float log2Cached(unsigned i) const;
170
172
173
174 static constexpr unsigned LOG_CACHE_SIZE = 16384;
175 float Log2Cache[LOG_CACHE_SIZE];
176
177
178
179 struct UtilitySignature {
180
181 unsigned LeftCount = 0;
182
183 unsigned RightCount = 0;
184
185
186 float CachedGainLR;
187
188
189 float CachedGainRL;
190
191 bool CachedGainIsValid = false;
192 };
193
194protected:
195
197 const SignaturesT &Signatures);
199};
200
201}
202
203#endif
static TableGen::Emitter::Opt Y("gen-skeleton-entry", EmitSkeleton, "Generate example skeleton entry")
static TableGen::Emitter::OptClass< SkeletonEmitter > X("gen-skeleton-class", "Generate example skeleton class")
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
A function with a set of utility nodes where it is beneficial to order two functions close together i...
Definition BalancedPartitioning.h:57
friend class BalancedPartitioning
Definition BalancedPartitioning.h:58
uint64_t IDT
Definition BalancedPartitioning.h:61
IDT Id
The ID of this node.
Definition BalancedPartitioning.h:69
friend class BPFunctionNodeTest_Basic_Test
Definition BalancedPartitioning.h:81
BPFunctionNode(IDT Id, ArrayRef< UtilityNodeT > UtilityNodes)
Definition BalancedPartitioning.h:65
friend class BalancedPartitioningTest_Large_Test
Definition BalancedPartitioning.h:83
uint32_t UtilityNodeT
Definition BalancedPartitioning.h:62
SmallVector< UtilityNodeT, 4 > UtilityNodes
The list of utility nodes associated with this node.
Definition BalancedPartitioning.h:75
uint64_t InputOrderIndex
The index of the input order of the FunctionNodes.
Definition BalancedPartitioning.h:79
friend class BalancedPartitioningTest_Basic_Test
Definition BalancedPartitioning.h:82
std::optional< unsigned > Bucket
The bucket assigned by balanced partitioning.
Definition BalancedPartitioning.h:77
LLVM_ABI void dump(raw_ostream &OS) const
static LLVM_ABI float moveGain(const BPFunctionNode &N, bool FromLeftToRight, const SignaturesT &Signatures)
Compute the move gain for uniform log-gap cost.
LLVM_ABI void run(std::vector< BPFunctionNode > &Nodes) const
Run recursive graph partitioning that optimizes a given objective.
friend class BalancedPartitioningTest_MoveGain_Test
Definition BalancedPartitioning.h:198
LLVM_ABI BalancedPartitioning(const BalancedPartitioningConfig &Config)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
This defines the abstract base interface for a ThreadPool allowing asynchronous parallel execution on...
A range adaptor for a pair of iterators.
This class implements an extremely fast bulk output stream that can only output to a stream.
This is an optimization pass for GlobalISel generic memory operations.
Algorithm parameters; default values are tuned on real-world binaries.
Definition BalancedPartitioning.h:87
unsigned SplitDepth
The depth of the recursive bisection.
Definition BalancedPartitioning.h:89
float SkipProbability
The probability for a vertex to skip a move from its current bucket to another bucket; it often helps...
Definition BalancedPartitioning.h:94
unsigned TaskSplitDepth
Recursive subtasks up to the given depth are added to the queue and distributed among threads by Thre...
Definition BalancedPartitioning.h:98
unsigned IterationsPerSplit
The maximum number of bp iterations per split.
Definition BalancedPartitioning.h:91