LLVM 19.0.0git
SampleProfileInference.h
Go to the documentation of this file.
1//===- Transforms/Utils/SampleProfileInference.h ----------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9/// \file
10/// This file provides the interface for the profile inference algorithm, profi.
11//
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_TRANSFORMS_UTILS_SAMPLEPROFILEINFERENCE_H
15#define LLVM_TRANSFORMS_UTILS_SAMPLEPROFILEINFERENCE_H
16
17#include "llvm/ADT/DenseMap.h"
20
21namespace llvm {
22
23struct FlowJump;
24
25/// A wrapper of a binary basic block.
26struct FlowBlock {
29 bool HasUnknownWeight{true};
30 bool IsUnlikely{false};
32 std::vector<FlowJump *> SuccJumps;
33 std::vector<FlowJump *> PredJumps;
34
35 /// Check if it is the entry block in the function.
36 bool isEntry() const { return PredJumps.empty(); }
37
38 /// Check if it is an exit block in the function.
39 bool isExit() const { return SuccJumps.empty(); }
40};
41
42/// A wrapper of a jump between two basic blocks.
43struct FlowJump {
47 bool HasUnknownWeight{true};
48 bool IsUnlikely{false};
50};
51
52/// A wrapper of binary function with basic blocks and jumps.
54 /// Basic blocks in the function.
55 std::vector<FlowBlock> Blocks;
56 /// Jumps between the basic blocks.
57 std::vector<FlowJump> Jumps;
58 /// The index of the entry block.
60};
61
62/// Various thresholds and options controlling the behavior of the profile
63/// inference algorithm. Default values are tuned for several large-scale
64/// applications, and can be modified via corresponding command-line flags.
66 /// Evenly distribute flow when there are multiple equally likely options.
68
69 /// Evenly re-distribute flow among unknown subgraphs.
70 bool RebalanceUnknown{false};
71
72 /// Join isolated components having positive flow.
73 bool JoinIslands{false};
74
75 /// The cost of increasing a block's count by one.
76 unsigned CostBlockInc{0};
77
78 /// The cost of decreasing a block's count by one.
79 unsigned CostBlockDec{0};
80
81 /// The cost of increasing a count of zero-weight block by one.
82 unsigned CostBlockZeroInc{0};
83
84 /// The cost of increasing the entry block's count by one.
85 unsigned CostBlockEntryInc{0};
86
87 /// The cost of decreasing the entry block's count by one.
88 unsigned CostBlockEntryDec{0};
89
90 /// The cost of increasing an unknown block's count by one.
92
93 /// The cost of increasing a jump's count by one.
94 unsigned CostJumpInc{0};
95
96 /// The cost of increasing a fall-through jump's count by one.
97 unsigned CostJumpFTInc{0};
98
99 /// The cost of decreasing a jump's count by one.
100 unsigned CostJumpDec{0};
101
102 /// The cost of decreasing a fall-through jump's count by one.
103 unsigned CostJumpFTDec{0};
104
105 /// The cost of increasing an unknown jump's count by one.
107
108 /// The cost of increasing an unknown fall-through jump's count by one.
110
111 /// The cost of taking an unlikely block/jump.
112 const int64_t CostUnlikely = ((int64_t)1) << 30;
113};
114
115void applyFlowInference(const ProfiParams &Params, FlowFunction &Func);
117
118/// Sample profile inference pass.
119template <typename FT> class SampleProfileInference {
120public:
122 using BasicBlockT = std::remove_pointer_t<NodeRef>;
123 using FunctionT = FT;
124 using Edge = std::pair<const BasicBlockT *, const BasicBlockT *>;
129
131 BlockWeightMap &SampleBlockWeights)
132 : F(F), Successors(Successors), SampleBlockWeights(SampleBlockWeights) {}
133
134 /// Apply the profile inference algorithm for a given function
135 void apply(BlockWeightMap &BlockWeights, EdgeWeightMap &EdgeWeights);
136
137private:
138 /// Initialize flow function blocks, jumps and misc metadata.
140 createFlowFunction(const std::vector<const BasicBlockT *> &BasicBlocks,
142
143 /// Try to infer branch probabilities mimicking implementation of
144 /// BranchProbabilityInfo. Unlikely taken branches are marked so that the
145 /// inference algorithm can avoid sending flow along corresponding edges.
146 void findUnlikelyJumps(const std::vector<const BasicBlockT *> &BasicBlocks,
147 BlockEdgeMap &Successors, FlowFunction &Func);
148
149 /// Determine whether the block is an exit in the CFG.
150 bool isExit(const BasicBlockT *BB);
151
152 /// Function.
153 const FunctionT &F;
154
155 /// Successors for each basic block in the CFG.
156 BlockEdgeMap &Successors;
157
158 /// Map basic blocks to their sampled weights.
159 BlockWeightMap &SampleBlockWeights;
160};
161
162template <typename BT>
164 EdgeWeightMap &EdgeWeights) {
165 // Find all forwards reachable blocks which the inference algorithm will be
166 // applied on.
168 for (auto *BB : depth_first_ext(&F, Reachable))
169 (void)BB /* Mark all reachable blocks */;
170
171 // Find all backwards reachable blocks which the inference algorithm will be
172 // applied on.
174 for (const auto &BB : F) {
175 // An exit block is a block without any successors.
176 if (isExit(&BB)) {
177 for (auto *RBB : inverse_depth_first_ext(&BB, InverseReachable))
178 (void)RBB;
179 }
180 }
181
182 // Keep a stable order for reachable blocks
184 std::vector<const BasicBlockT *> BasicBlocks;
185 BlockIndex.reserve(Reachable.size());
186 BasicBlocks.reserve(Reachable.size());
187 for (const auto &BB : F) {
188 if (Reachable.count(&BB) && InverseReachable.count(&BB)) {
189 BlockIndex[&BB] = BasicBlocks.size();
190 BasicBlocks.push_back(&BB);
191 }
192 }
193
194 BlockWeights.clear();
195 EdgeWeights.clear();
196 bool HasSamples = false;
197 for (const auto *BB : BasicBlocks) {
198 auto It = SampleBlockWeights.find(BB);
199 if (It != SampleBlockWeights.end() && It->second > 0) {
200 HasSamples = true;
201 BlockWeights[BB] = It->second;
202 }
203 }
204 // Quit early for functions with a single block or ones w/o samples
205 if (BasicBlocks.size() <= 1 || !HasSamples) {
206 return;
207 }
208
209 // Create necessary objects
210 FlowFunction Func = createFlowFunction(BasicBlocks, BlockIndex);
211
212 // Create and apply the inference network model.
213 applyFlowInference(Func);
214
215 // Extract the resulting weights from the control flow
216 // All weights are increased by one to avoid propagation errors introduced by
217 // zero weights.
218 for (const auto *BB : BasicBlocks) {
219 BlockWeights[BB] = Func.Blocks[BlockIndex[BB]].Flow;
220 }
221 for (auto &Jump : Func.Jumps) {
222 Edge E = std::make_pair(BasicBlocks[Jump.Source], BasicBlocks[Jump.Target]);
223 EdgeWeights[E] = Jump.Flow;
224 }
225
226#ifndef NDEBUG
227 // Unreachable blocks and edges should not have a weight.
228 for (auto &I : BlockWeights) {
229 assert(Reachable.contains(I.first));
230 assert(InverseReachable.contains(I.first));
231 }
232 for (auto &I : EdgeWeights) {
233 assert(Reachable.contains(I.first.first) &&
234 Reachable.contains(I.first.second));
235 assert(InverseReachable.contains(I.first.first) &&
236 InverseReachable.contains(I.first.second));
237 }
238#endif
239}
240
241template <typename BT>
243 const std::vector<const BasicBlockT *> &BasicBlocks,
245 FlowFunction Func;
246 Func.Blocks.reserve(BasicBlocks.size());
247 // Create FlowBlocks
248 for (const auto *BB : BasicBlocks) {
250 if (SampleBlockWeights.contains(BB)) {
251 Block.HasUnknownWeight = false;
252 Block.Weight = SampleBlockWeights[BB];
253 } else {
254 Block.HasUnknownWeight = true;
255 Block.Weight = 0;
256 }
257 Block.Index = Func.Blocks.size();
258 Func.Blocks.push_back(Block);
259 }
260 // Create FlowEdges
261 for (const auto *BB : BasicBlocks) {
262 for (auto *Succ : Successors[BB]) {
263 if (!BlockIndex.count(Succ))
264 continue;
265 FlowJump Jump;
266 Jump.Source = BlockIndex[BB];
267 Jump.Target = BlockIndex[Succ];
268 Func.Jumps.push_back(Jump);
269 }
270 }
271 for (auto &Jump : Func.Jumps) {
272 uint64_t Src = Jump.Source;
273 uint64_t Dst = Jump.Target;
274 Func.Blocks[Src].SuccJumps.push_back(&Jump);
275 Func.Blocks[Dst].PredJumps.push_back(&Jump);
276 }
277
278 // Try to infer probabilities of jumps based on the content of basic block
279 findUnlikelyJumps(BasicBlocks, Successors, Func);
280
281 // Find the entry block
282 for (size_t I = 0; I < Func.Blocks.size(); I++) {
283 if (Func.Blocks[I].isEntry()) {
284 Func.Entry = I;
285 break;
286 }
287 }
288 assert(Func.Entry == 0 && "incorrect index of the entry block");
289
290 // Pre-process data: make sure the entry weight is at least 1
291 auto &EntryBlock = Func.Blocks[Func.Entry];
292 if (EntryBlock.Weight == 0 && !EntryBlock.HasUnknownWeight) {
293 EntryBlock.Weight = 1;
294 EntryBlock.HasUnknownWeight = false;
295 }
296
297 return Func;
298}
299
300template <typename BT>
301inline void SampleProfileInference<BT>::findUnlikelyJumps(
302 const std::vector<const BasicBlockT *> &BasicBlocks,
303 BlockEdgeMap &Successors, FlowFunction &Func) {}
304
305template <typename BT>
306inline bool SampleProfileInference<BT>::isExit(const BasicBlockT *BB) {
307 return BB->succ_empty();
308}
309
310} // end namespace llvm
311#endif // LLVM_TRANSFORMS_UTILS_SAMPLEPROFILEINFERENCE_H
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file defines the DenseMap class.
This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallVector class.
unsigned size() const
Definition: DenseMap.h:99
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Definition: DenseMap.h:151
void reserve(size_type NumEntries)
Grow the densemap so that it can contain at least NumEntries items before resizing again.
Definition: DenseMap.h:103
Sample profile inference pass.
std::remove_pointer_t< NodeRef > BasicBlockT
DenseMap< const BasicBlockT *, uint64_t > BlockWeightMap
typename GraphTraits< FT * >::NodeRef NodeRef
DenseMap< const BasicBlockT *, SmallVector< const BasicBlockT *, 8 > > BlockEdgeMap
DenseMap< Edge, uint64_t > EdgeWeightMap
std::pair< const BasicBlockT *, const BasicBlockT * > Edge
void apply(BlockWeightMap &BlockWeights, EdgeWeightMap &EdgeWeights)
Apply the profile inference algorithm for a given function.
SampleProfileInference(FunctionT &F, BlockEdgeMap &Successors, BlockWeightMap &SampleBlockWeights)
size_type size() const
Definition: SmallPtrSet.h:94
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:360
bool contains(ConstPtrType Ptr) const
Definition: SmallPtrSet.h:366
NodeAddr< FuncNode * > Func
Definition: RDFGraph.h:393
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
iterator_range< df_ext_iterator< T, SetTy > > depth_first_ext(const T &G, SetTy &S)
iterator_range< idf_ext_iterator< T, SetTy > > inverse_depth_first_ext(const T &G, SetTy &S)
void applyFlowInference(const ProfiParams &Params, FlowFunction &Func)
Apply the profile inference algorithm for a given function and provided profi options.
A wrapper of a binary basic block.
bool isEntry() const
Check if it is the entry block in the function.
bool isExit() const
Check if it is an exit block in the function.
std::vector< FlowJump * > PredJumps
std::vector< FlowJump * > SuccJumps
A wrapper of binary function with basic blocks and jumps.
std::vector< FlowJump > Jumps
Jumps between the basic blocks.
std::vector< FlowBlock > Blocks
Basic blocks in the function.
uint64_t Entry
The index of the entry block.
A wrapper of a jump between two basic blocks.
typename GraphType::UnknownGraphTypeError NodeRef
Definition: GraphTraits.h:80
Various thresholds and options controlling the behavior of the profile inference algorithm.
unsigned CostJumpUnknownFTInc
The cost of increasing an unknown fall-through jump's count by one.
unsigned CostBlockInc
The cost of increasing a block's count by one.
unsigned CostJumpFTInc
The cost of increasing a fall-through jump's count by one.
bool RebalanceUnknown
Evenly re-distribute flow among unknown subgraphs.
const int64_t CostUnlikely
The cost of taking an unlikely block/jump.
unsigned CostJumpDec
The cost of decreasing a jump's count by one.
bool JoinIslands
Join isolated components having positive flow.
unsigned CostBlockZeroInc
The cost of increasing a count of zero-weight block by one.
unsigned CostBlockEntryDec
The cost of decreasing the entry block's count by one.
unsigned CostJumpInc
The cost of increasing a jump's count by one.
unsigned CostJumpUnknownInc
The cost of increasing an unknown jump's count by one.
unsigned CostBlockUnknownInc
The cost of increasing an unknown block's count by one.
unsigned CostJumpFTDec
The cost of decreasing a fall-through jump's count by one.
unsigned CostBlockDec
The cost of decreasing a block's count by one.
unsigned CostBlockEntryInc
The cost of increasing the entry block's count by one.
bool EvenFlowDistribution
Evenly distribute flow when there are multiple equally likely options.