LLVM  15.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"
19 #include "llvm/ADT/SmallVector.h"
20 
21 #include "llvm/IR/BasicBlock.h"
22 #include "llvm/IR/Instruction.h"
23 #include "llvm/IR/Instructions.h"
24 
25 namespace llvm {
26 
27 class Function;
28 class MachineBasicBlock;
29 class MachineFunction;
30 
31 namespace afdo_detail {
32 
33 template <class BlockT> struct TypeMap {};
34 template <> struct TypeMap<BasicBlock> {
37 };
38 template <> struct TypeMap<MachineBasicBlock> {
41 };
42 
43 } // end namespace afdo_detail
44 
45 struct FlowJump;
46 
47 /// A wrapper of a binary basic block.
48 struct FlowBlock {
51  bool UnknownWeight{false};
53  bool HasSelfEdge{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.
65 struct FlowJump {
69  bool IsUnlikely{false};
70 };
71 
72 /// A wrapper of binary function with basic blocks and jumps.
73 struct FlowFunction {
74  std::vector<FlowBlock> Blocks;
75  std::vector<FlowJump> Jumps;
76  /// The index of the entry block.
78 };
79 
81 
82 /// Sample profile inference pass.
83 template <typename BT> class SampleProfileInference {
84 public:
87  using Edge = std::pair<const BasicBlockT *, const BasicBlockT *>;
90  using BlockEdgeMap =
92 
94  BlockWeightMap &SampleBlockWeights)
95  : F(F), Successors(Successors), SampleBlockWeights(SampleBlockWeights) {}
96 
97  /// Apply the profile inference algorithm for a given function
98  void apply(BlockWeightMap &BlockWeights, EdgeWeightMap &EdgeWeights);
99 
100 private:
101  /// Try to infer branch probabilities mimicking implementation of
102  /// BranchProbabilityInfo. Unlikely taken branches are marked so that the
103  /// inference algorithm can avoid sending flow along corresponding edges.
104  void findUnlikelyJumps(const std::vector<const BasicBlockT *> &BasicBlocks,
105  BlockEdgeMap &Successors, FlowFunction &Func);
106 
107  /// Determine whether the block is an exit in the CFG.
108  bool isExit(const BasicBlockT *BB);
109 
110  /// Function.
111  const FunctionT &F;
112 
113  /// Successors for each basic block in the CFG.
114  BlockEdgeMap &Successors;
115 
116  /// Map basic blocks to their sampled weights.
117  BlockWeightMap &SampleBlockWeights;
118 };
119 
120 template <typename BT>
122  EdgeWeightMap &EdgeWeights) {
123  // Find all forwards reachable blocks which the inference algorithm will be
124  // applied on.
126  for (auto *BB : depth_first_ext(&F, Reachable))
127  (void)BB /* Mark all reachable blocks */;
128 
129  // Find all backwards reachable blocks which the inference algorithm will be
130  // applied on.
132  for (const auto &BB : F) {
133  // An exit block is a block without any successors.
134  if (isExit(&BB)) {
135  for (auto *RBB : inverse_depth_first_ext(&BB, InverseReachable))
136  (void)RBB;
137  }
138  }
139 
140  // Keep a stable order for reachable blocks
142  std::vector<const BasicBlockT *> BasicBlocks;
143  BlockIndex.reserve(Reachable.size());
144  BasicBlocks.reserve(Reachable.size());
145  for (const auto &BB : F) {
146  if (Reachable.count(&BB) && InverseReachable.count(&BB)) {
147  BlockIndex[&BB] = BasicBlocks.size();
148  BasicBlocks.push_back(&BB);
149  }
150  }
151 
152  BlockWeights.clear();
153  EdgeWeights.clear();
154  bool HasSamples = false;
155  for (const auto *BB : BasicBlocks) {
156  auto It = SampleBlockWeights.find(BB);
157  if (It != SampleBlockWeights.end() && It->second > 0) {
158  HasSamples = true;
159  BlockWeights[BB] = It->second;
160  }
161  }
162  // Quit early for functions with a single block or ones w/o samples
163  if (BasicBlocks.size() <= 1 || !HasSamples) {
164  return;
165  }
166 
167  // Create necessary objects
168  FlowFunction Func;
169  Func.Blocks.reserve(BasicBlocks.size());
170  // Create FlowBlocks
171  for (const auto *BB : BasicBlocks) {
172  FlowBlock Block;
173  if (SampleBlockWeights.find(BB) != SampleBlockWeights.end()) {
174  Block.UnknownWeight = false;
175  Block.Weight = SampleBlockWeights[BB];
176  } else {
177  Block.UnknownWeight = true;
178  Block.Weight = 0;
179  }
180  Block.Index = Func.Blocks.size();
181  Func.Blocks.push_back(Block);
182  }
183  // Create FlowEdges
184  for (const auto *BB : BasicBlocks) {
185  for (auto *Succ : Successors[BB]) {
186  if (!BlockIndex.count(Succ))
187  continue;
188  FlowJump Jump;
189  Jump.Source = BlockIndex[BB];
190  Jump.Target = BlockIndex[Succ];
191  Func.Jumps.push_back(Jump);
192  if (BB == Succ) {
193  Func.Blocks[BlockIndex[BB]].HasSelfEdge = true;
194  }
195  }
196  }
197  for (auto &Jump : Func.Jumps) {
198  Func.Blocks[Jump.Source].SuccJumps.push_back(&Jump);
199  Func.Blocks[Jump.Target].PredJumps.push_back(&Jump);
200  }
201 
202  // Try to infer probabilities of jumps based on the content of basic block
203  findUnlikelyJumps(BasicBlocks, Successors, Func);
204 
205  // Find the entry block
206  for (size_t I = 0; I < Func.Blocks.size(); I++) {
207  if (Func.Blocks[I].isEntry()) {
208  Func.Entry = I;
209  break;
210  }
211  }
212 
213  // Create and apply the inference network model.
214  applyFlowInference(Func);
215 
216  // Extract the resulting weights from the control flow
217  // All weights are increased by one to avoid propagation errors introduced by
218  // zero weights.
219  for (const auto *BB : BasicBlocks) {
220  BlockWeights[BB] = Func.Blocks[BlockIndex[BB]].Flow;
221  }
222  for (auto &Jump : Func.Jumps) {
223  Edge E = std::make_pair(BasicBlocks[Jump.Source], BasicBlocks[Jump.Target]);
224  EdgeWeights[E] = Jump.Flow;
225  }
226 
227 #ifndef NDEBUG
228  // Unreachable blocks and edges should not have a weight.
229  for (auto &I : BlockWeights) {
230  assert(Reachable.contains(I.first));
231  assert(InverseReachable.contains(I.first));
232  }
233  for (auto &I : EdgeWeights) {
234  assert(Reachable.contains(I.first.first) &&
235  Reachable.contains(I.first.second));
236  assert(InverseReachable.contains(I.first.first) &&
237  InverseReachable.contains(I.first.second));
238  }
239 #endif
240 }
241 
242 template <typename BT>
244  const std::vector<const BasicBlockT *> &BasicBlocks,
245  BlockEdgeMap &Successors, FlowFunction &Func) {}
246 
247 template <>
248 inline void SampleProfileInference<BasicBlock>::findUnlikelyJumps(
249  const std::vector<const BasicBlockT *> &BasicBlocks,
250  BlockEdgeMap &Successors, FlowFunction &Func) {
251  for (auto &Jump : Func.Jumps) {
252  const auto *BB = BasicBlocks[Jump.Source];
253  const auto *Succ = BasicBlocks[Jump.Target];
254  const Instruction *TI = BB->getTerminator();
255  // Check if a block ends with InvokeInst and mark non-taken branch unlikely.
256  // In that case block Succ should be a landing pad
257  if (Successors[BB].size() == 2 && Successors[BB].back() == Succ) {
258  if (isa<InvokeInst>(TI)) {
259  Jump.IsUnlikely = true;
260  }
261  }
262  const Instruction *SuccTI = Succ->getTerminator();
263  // Check if the target block contains UnreachableInst and mark it unlikely
264  if (SuccTI->getNumSuccessors() == 0) {
265  if (isa<UnreachableInst>(SuccTI)) {
266  Jump.IsUnlikely = true;
267  }
268  }
269  }
270 }
271 
272 template <typename BT>
273 inline bool SampleProfileInference<BT>::isExit(const BasicBlockT *BB) {
274  return BB->succ_empty();
275 }
276 
277 template <>
278 inline bool SampleProfileInference<BasicBlock>::isExit(const BasicBlock *BB) {
279  return succ_empty(BB);
280 }
281 
282 } // end namespace llvm
283 #endif // LLVM_TRANSFORMS_UTILS_SAMPLEPROFILEINFERENCE_H
llvm::applyFlowInference
void applyFlowInference(FlowFunction &Func)
Apply the profile inference algorithm for a given flow function.
Definition: SampleProfileInference.cpp:1239
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::SampleProfileInference::apply
void apply(BlockWeightMap &BlockWeights, EdgeWeightMap &EdgeWeights)
Apply the profile inference algorithm for a given function.
Definition: SampleProfileInference.h:121
llvm::Function
Definition: Function.h:60
llvm::FlowFunction::Entry
uint64_t Entry
The index of the entry block.
Definition: SampleProfileInference.h:77
llvm::FlowFunction::Jumps
std::vector< FlowJump > Jumps
Definition: SampleProfileInference.h:75
DenseMap.h
llvm::DenseMapBase::count
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:147
llvm::succ_empty
bool succ_empty(const Instruction *I)
Definition: CFG.h:255
DepthFirstIterator.h
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
Instruction.h
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::FlowJump::Source
uint64_t Source
Definition: SampleProfileInference.h:66
llvm::SampleProfileInference::BasicBlockT
typename afdo_detail::TypeMap< BT >::BasicBlockT BasicBlockT
Definition: SampleProfileInference.h:85
llvm::depth_first_ext
iterator_range< df_ext_iterator< T, SetTy > > depth_first_ext(const T &G, SetTy &S)
Definition: DepthFirstIterator.h:252
llvm::FlowBlock
A wrapper of a binary basic block.
Definition: SampleProfileInference.h:48
llvm::FlowBlock::HasSelfEdge
bool HasSelfEdge
Definition: SampleProfileInference.h:53
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:94
BasicBlock.h
llvm::FlowBlock::Flow
uint64_t Flow
Definition: SampleProfileInference.h:52
llvm::FlowJump::Flow
uint64_t Flow
Definition: SampleProfileInference.h:68
llvm::FlowBlock::isExit
bool isExit() const
Check if it is an exit block in the function.
Definition: SampleProfileInference.h:61
llvm::SampleProfileInference::BlockWeightMap
DenseMap< const BasicBlockT *, uint64_t > BlockWeightMap
Definition: SampleProfileInference.h:88
llvm::FlowJump::IsUnlikely
bool IsUnlikely
Definition: SampleProfileInference.h:69
llvm::DenseMapBase::clear
void clear()
Definition: DenseMap.h:112
uint64_t
llvm::DenseMap< const BasicBlockT *, uint64_t >
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::SampleProfileInference::SampleProfileInference
SampleProfileInference(FunctionT &F, BlockEdgeMap &Successors, BlockWeightMap &SampleBlockWeights)
Definition: SampleProfileInference.h:93
llvm::SampleProfileInference::FunctionT
typename afdo_detail::TypeMap< BT >::FunctionT FunctionT
Definition: SampleProfileInference.h:86
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::ISD::BasicBlock
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
llvm::SampleProfileInference::BlockEdgeMap
DenseMap< const BasicBlockT *, SmallVector< const BasicBlockT *, 8 > > BlockEdgeMap
Definition: SampleProfileInference.h:91
llvm::SmallPtrSetImpl< NodeRef >::count
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:383
llvm::MachineFunction
Definition: MachineFunction.h:257
llvm::df_iterator_default_set
Definition: DepthFirstIterator.h:70
llvm::size
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:1598
llvm::SampleProfileInference::Edge
std::pair< const BasicBlockT *, const BasicBlockT * > Edge
Definition: SampleProfileInference.h:87
llvm::afdo_detail::TypeMap
Definition: SampleProfileInference.h:33
llvm::FlowFunction::Blocks
std::vector< FlowBlock > Blocks
Definition: SampleProfileInference.h:74
llvm::FlowJump::Target
uint64_t Target
Definition: SampleProfileInference.h:67
llvm::SmallPtrSetImplBase::size
size_type size() const
Definition: SmallPtrSet.h:93
llvm::FlowBlock::Index
uint64_t Index
Definition: SampleProfileInference.h:49
llvm::FlowBlock::UnknownWeight
bool UnknownWeight
Definition: SampleProfileInference.h:51
llvm::FlowFunction
A wrapper of binary function with basic blocks and jumps.
Definition: SampleProfileInference.h:73
llvm::DenseMapBase::size
unsigned size() const
Definition: DenseMap.h:101
Instructions.h
llvm::SampleProfileInference
Sample profile inference pass.
Definition: SampleProfileInference.h:83
SmallVector.h
llvm::FlowBlock::isEntry
bool isEntry() const
Check if it is the entry block in the function.
Definition: SampleProfileInference.h:58
llvm::FlowBlock::SuccJumps
std::vector< FlowJump * > SuccJumps
Definition: SampleProfileInference.h:54
llvm::DenseMapBase::reserve
void reserve(size_type NumEntries)
Grow the densemap so that it can contain at least NumEntries items before resizing again.
Definition: DenseMap.h:105
llvm::FlowBlock::Weight
uint64_t Weight
Definition: SampleProfileInference.h:50
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::inverse_depth_first_ext
iterator_range< idf_ext_iterator< T, SetTy > > inverse_depth_first_ext(const T &G, SetTy &S)
Definition: DepthFirstIterator.h:303
llvm::SmallPtrSetImpl< NodeRef >::contains
bool contains(ConstPtrType Ptr) const
Definition: SmallPtrSet.h:389
llvm::FlowBlock::PredJumps
std::vector< FlowJump * > PredJumps
Definition: SampleProfileInference.h:55
llvm::codeview::PublicSymFlags::Function
@ Function
llvm::SampleProfileInference::EdgeWeightMap
DenseMap< Edge, uint64_t > EdgeWeightMap
Definition: SampleProfileInference.h:89
llvm::FlowJump
A wrapper of a jump between two basic blocks.
Definition: SampleProfileInference.h:65