LLVM 17.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
21#include "llvm/IR/BasicBlock.h"
22#include "llvm/IR/Instruction.h"
24
25namespace llvm {
26
27class Function;
28class MachineBasicBlock;
29class MachineFunction;
30
31namespace afdo_detail {
32
33template <class BlockT> struct TypeMap {};
34template <> struct TypeMap<BasicBlock> {
37};
38template <> struct TypeMap<MachineBasicBlock> {
41};
42
43} // end namespace afdo_detail
44
45struct FlowJump;
46
47/// A wrapper of a binary basic block.
48struct FlowBlock {
51 bool HasUnknownWeight{true};
52 bool IsUnlikely{false};
54 std::vector<FlowJump *> SuccJumps;
55 std::vector<FlowJump *> PredJumps;
56
57 /// Check if it is the entry block in the function.
58 bool isEntry() const { return PredJumps.empty(); }
59
60 /// Check if it is an exit block in the function.
61 bool isExit() const { return SuccJumps.empty(); }
62};
63
64/// A wrapper of a jump between two basic blocks.
65struct FlowJump {
69 bool HasUnknownWeight{true};
70 bool IsUnlikely{false};
72};
73
74/// A wrapper of binary function with basic blocks and jumps.
76 /// Basic blocks in the function.
77 std::vector<FlowBlock> Blocks;
78 /// Jumps between the basic blocks.
79 std::vector<FlowJump> Jumps;
80 /// The index of the entry block.
82};
83
84/// Various thresholds and options controlling the behavior of the profile
85/// inference algorithm. Default values are tuned for several large-scale
86/// applications, and can be modified via corresponding command-line flags.
88 /// Evenly distribute flow when there are multiple equally likely options.
90
91 /// Evenly re-distribute flow among unknown subgraphs.
92 bool RebalanceUnknown{false};
93
94 /// Join isolated components having positive flow.
95 bool JoinIslands{false};
96
97 /// The cost of increasing a block's count by one.
98 unsigned CostBlockInc{0};
99
100 /// The cost of decreasing a block's count by one.
101 unsigned CostBlockDec{0};
102
103 /// The cost of increasing a count of zero-weight block by one.
104 unsigned CostBlockZeroInc{0};
105
106 /// The cost of increasing the entry block's count by one.
107 unsigned CostBlockEntryInc{0};
108
109 /// The cost of decreasing the entry block's count by one.
110 unsigned CostBlockEntryDec{0};
111
112 /// The cost of increasing an unknown block's count by one.
114
115 /// The cost of increasing a jump's count by one.
116 unsigned CostJumpInc{0};
117
118 /// The cost of increasing a fall-through jump's count by one.
119 unsigned CostJumpFTInc{0};
120
121 /// The cost of decreasing a jump's count by one.
122 unsigned CostJumpDec{0};
123
124 /// The cost of decreasing a fall-through jump's count by one.
125 unsigned CostJumpFTDec{0};
126
127 /// The cost of increasing an unknown jump's count by one.
129
130 /// The cost of increasing an unknown fall-through jump's count by one.
132
133 /// The cost of taking an unlikely block/jump.
134 const int64_t CostUnlikely = ((int64_t)1) << 30;
135};
136
137void applyFlowInference(const ProfiParams &Params, FlowFunction &Func);
139
140/// Sample profile inference pass.
141template <typename BT> class SampleProfileInference {
142public:
145 using Edge = std::pair<const BasicBlockT *, const BasicBlockT *>;
150
152 BlockWeightMap &SampleBlockWeights)
153 : F(F), Successors(Successors), SampleBlockWeights(SampleBlockWeights) {}
154
155 /// Apply the profile inference algorithm for a given function
156 void apply(BlockWeightMap &BlockWeights, EdgeWeightMap &EdgeWeights);
157
158private:
159 /// Initialize flow function blocks, jumps and misc metadata.
160 void initFunction(FlowFunction &Func,
161 const std::vector<const BasicBlockT *> &BasicBlocks,
163
164 /// Try to infer branch probabilities mimicking implementation of
165 /// BranchProbabilityInfo. Unlikely taken branches are marked so that the
166 /// inference algorithm can avoid sending flow along corresponding edges.
167 void findUnlikelyJumps(const std::vector<const BasicBlockT *> &BasicBlocks,
168 BlockEdgeMap &Successors, FlowFunction &Func);
169
170 /// Determine whether the block is an exit in the CFG.
171 bool isExit(const BasicBlockT *BB);
172
173 /// Function.
174 const FunctionT &F;
175
176 /// Successors for each basic block in the CFG.
177 BlockEdgeMap &Successors;
178
179 /// Map basic blocks to their sampled weights.
180 BlockWeightMap &SampleBlockWeights;
181};
182
183template <typename BT>
185 EdgeWeightMap &EdgeWeights) {
186 // Find all forwards reachable blocks which the inference algorithm will be
187 // applied on.
189 for (auto *BB : depth_first_ext(&F, Reachable))
190 (void)BB /* Mark all reachable blocks */;
191
192 // Find all backwards reachable blocks which the inference algorithm will be
193 // applied on.
195 for (const auto &BB : F) {
196 // An exit block is a block without any successors.
197 if (isExit(&BB)) {
198 for (auto *RBB : inverse_depth_first_ext(&BB, InverseReachable))
199 (void)RBB;
200 }
201 }
202
203 // Keep a stable order for reachable blocks
205 std::vector<const BasicBlockT *> BasicBlocks;
206 BlockIndex.reserve(Reachable.size());
207 BasicBlocks.reserve(Reachable.size());
208 for (const auto &BB : F) {
209 if (Reachable.count(&BB) && InverseReachable.count(&BB)) {
210 BlockIndex[&BB] = BasicBlocks.size();
211 BasicBlocks.push_back(&BB);
212 }
213 }
214
215 BlockWeights.clear();
216 EdgeWeights.clear();
217 bool HasSamples = false;
218 for (const auto *BB : BasicBlocks) {
219 auto It = SampleBlockWeights.find(BB);
220 if (It != SampleBlockWeights.end() && It->second > 0) {
221 HasSamples = true;
222 BlockWeights[BB] = It->second;
223 }
224 }
225 // Quit early for functions with a single block or ones w/o samples
226 if (BasicBlocks.size() <= 1 || !HasSamples) {
227 return;
228 }
229
230 // Create necessary objects
231 FlowFunction Func;
232 initFunction(Func, BasicBlocks, BlockIndex);
233
234 // Create and apply the inference network model.
235 applyFlowInference(Func);
236
237 // Extract the resulting weights from the control flow
238 // All weights are increased by one to avoid propagation errors introduced by
239 // zero weights.
240 for (const auto *BB : BasicBlocks) {
241 BlockWeights[BB] = Func.Blocks[BlockIndex[BB]].Flow;
242 }
243 for (auto &Jump : Func.Jumps) {
244 Edge E = std::make_pair(BasicBlocks[Jump.Source], BasicBlocks[Jump.Target]);
245 EdgeWeights[E] = Jump.Flow;
246 }
247
248#ifndef NDEBUG
249 // Unreachable blocks and edges should not have a weight.
250 for (auto &I : BlockWeights) {
251 assert(Reachable.contains(I.first));
252 assert(InverseReachable.contains(I.first));
253 }
254 for (auto &I : EdgeWeights) {
255 assert(Reachable.contains(I.first.first) &&
256 Reachable.contains(I.first.second));
257 assert(InverseReachable.contains(I.first.first) &&
258 InverseReachable.contains(I.first.second));
259 }
260#endif
261}
262
263template <typename BT>
265 FlowFunction &Func, const std::vector<const BasicBlockT *> &BasicBlocks,
267 Func.Blocks.reserve(BasicBlocks.size());
268 // Create FlowBlocks
269 for (const auto *BB : BasicBlocks) {
271 if (SampleBlockWeights.find(BB) != SampleBlockWeights.end()) {
272 Block.HasUnknownWeight = false;
273 Block.Weight = SampleBlockWeights[BB];
274 } else {
275 Block.HasUnknownWeight = true;
276 Block.Weight = 0;
277 }
278 Block.Index = Func.Blocks.size();
279 Func.Blocks.push_back(Block);
280 }
281 // Create FlowEdges
282 for (const auto *BB : BasicBlocks) {
283 for (auto *Succ : Successors[BB]) {
284 if (!BlockIndex.count(Succ))
285 continue;
286 FlowJump Jump;
287 Jump.Source = BlockIndex[BB];
288 Jump.Target = BlockIndex[Succ];
289 Func.Jumps.push_back(Jump);
290 }
291 }
292 for (auto &Jump : Func.Jumps) {
293 uint64_t Src = Jump.Source;
294 uint64_t Dst = Jump.Target;
295 Func.Blocks[Src].SuccJumps.push_back(&Jump);
296 Func.Blocks[Dst].PredJumps.push_back(&Jump);
297 }
298
299 // Try to infer probabilities of jumps based on the content of basic block
300 findUnlikelyJumps(BasicBlocks, Successors, Func);
301
302 // Find the entry block
303 for (size_t I = 0; I < Func.Blocks.size(); I++) {
304 if (Func.Blocks[I].isEntry()) {
305 Func.Entry = I;
306 break;
307 }
308 }
309 assert(Func.Entry == 0 && "incorrect index of the entry block");
310
311 // Pre-process data: make sure the entry weight is at least 1
312 auto &EntryBlock = Func.Blocks[Func.Entry];
313 if (EntryBlock.Weight == 0 && !EntryBlock.HasUnknownWeight) {
314 EntryBlock.Weight = 1;
315 EntryBlock.HasUnknownWeight = false;
316 }
317}
318
319template <typename BT>
320inline void SampleProfileInference<BT>::findUnlikelyJumps(
321 const std::vector<const BasicBlockT *> &BasicBlocks,
322 BlockEdgeMap &Successors, FlowFunction &Func) {}
323
324template <>
325inline void SampleProfileInference<BasicBlock>::findUnlikelyJumps(
326 const std::vector<const BasicBlockT *> &BasicBlocks,
327 BlockEdgeMap &Successors, FlowFunction &Func) {
328 for (auto &Jump : Func.Jumps) {
329 const auto *BB = BasicBlocks[Jump.Source];
330 const auto *Succ = BasicBlocks[Jump.Target];
331 const Instruction *TI = BB->getTerminator();
332 // Check if a block ends with InvokeInst and mark non-taken branch unlikely.
333 // In that case block Succ should be a landing pad
334 if (Successors[BB].size() == 2 && Successors[BB].back() == Succ) {
335 if (isa<InvokeInst>(TI)) {
336 Jump.IsUnlikely = true;
337 }
338 }
339 const Instruction *SuccTI = Succ->getTerminator();
340 // Check if the target block contains UnreachableInst and mark it unlikely
341 if (SuccTI->getNumSuccessors() == 0) {
342 if (isa<UnreachableInst>(SuccTI)) {
343 Jump.IsUnlikely = true;
344 }
345 }
346 }
347}
348
349template <typename BT>
350inline bool SampleProfileInference<BT>::isExit(const BasicBlockT *BB) {
351 return BB->succ_empty();
352}
353
354template <>
355inline bool SampleProfileInference<BasicBlock>::isExit(const BasicBlock *BB) {
356 return succ_empty(BB);
357}
358
359} // end namespace llvm
360#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.
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
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.
DenseMap< const BasicBlockT *, SmallVector< const BasicBlockT *, 8 > > BlockEdgeMap
typename afdo_detail::TypeMap< BT >::FunctionT FunctionT
SampleProfileInference(FunctionT &F, BlockEdgeMap &Successors, BlockWeightMap &SampleBlockWeights)
typename afdo_detail::TypeMap< BT >::BasicBlockT BasicBlockT
DenseMap< const BasicBlockT *, uint64_t > BlockWeightMap
void apply(BlockWeightMap &BlockWeights, EdgeWeightMap &EdgeWeights)
Apply the profile inference algorithm for a given function.
std::pair< const BasicBlockT *, const BasicBlockT * > Edge
DenseMap< Edge, uint64_t > EdgeWeightMap
size_type size() const
Definition: SmallPtrSet.h:93
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:383
bool contains(ConstPtrType Ptr) const
Definition: SmallPtrSet.h:389
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)
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
Definition: STLExtras.h:1777
bool succ_empty(const Instruction *I)
Definition: CFG.h:255
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.
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.