LLVM  14.0.0git
BranchProbabilityInfo.h
Go to the documentation of this file.
1 //===- BranchProbabilityInfo.h - Branch Probability Analysis ----*- 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 // This pass is used to evaluate branch probabilties.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #ifndef LLVM_ANALYSIS_BRANCHPROBABILITYINFO_H
14 #define LLVM_ANALYSIS_BRANCHPROBABILITYINFO_H
15 
16 #include "llvm/ADT/DenseMap.h"
17 #include "llvm/ADT/DenseMapInfo.h"
18 #include "llvm/ADT/DenseSet.h"
19 #include "llvm/ADT/SmallPtrSet.h"
20 #include "llvm/IR/BasicBlock.h"
21 #include "llvm/IR/CFG.h"
22 #include "llvm/IR/PassManager.h"
23 #include "llvm/IR/ValueHandle.h"
24 #include "llvm/Pass.h"
26 #include "llvm/Support/Casting.h"
27 #include <algorithm>
28 #include <cassert>
29 #include <cstdint>
30 #include <memory>
31 #include <utility>
32 
33 namespace llvm {
34 
35 class Function;
36 class Loop;
37 class LoopInfo;
38 class raw_ostream;
39 class DominatorTree;
40 class PostDominatorTree;
41 class TargetLibraryInfo;
42 class Value;
43 
44 /// Analysis providing branch probability information.
45 ///
46 /// This is a function analysis which provides information on the relative
47 /// probabilities of each "edge" in the function's CFG where such an edge is
48 /// defined by a pair (PredBlock and an index in the successors). The
49 /// probability of an edge from one block is always relative to the
50 /// probabilities of other edges from the block. The probabilites of all edges
51 /// from a block sum to exactly one (100%).
52 /// We use a pair (PredBlock and an index in the successors) to uniquely
53 /// identify an edge, since we can have multiple edges from Src to Dst.
54 /// As an example, we can have a switch which jumps to Dst with value 0 and
55 /// value 10.
56 ///
57 /// Process of computing branch probabilities can be logically viewed as three
58 /// step process:
59 ///
60 /// First, if there is a profile information associated with the branch then
61 /// it is trivially translated to branch probabilities. There is one exception
62 /// from this rule though. Probabilities for edges leading to "unreachable"
63 /// blocks (blocks with the estimated weight not greater than
64 /// UNREACHABLE_WEIGHT) are evaluated according to static estimation and
65 /// override profile information. If no branch probabilities were calculated
66 /// on this step then take the next one.
67 ///
68 /// Second, estimate absolute execution weights for each block based on
69 /// statically known information. Roots of such information are "cold",
70 /// "unreachable", "noreturn" and "unwind" blocks. Those blocks get their
71 /// weights set to BlockExecWeight::COLD, BlockExecWeight::UNREACHABLE,
72 /// BlockExecWeight::NORETURN and BlockExecWeight::UNWIND respectively. Then the
73 /// weights are propagated to the other blocks up the domination line. In
74 /// addition, if all successors have estimated weights set then maximum of these
75 /// weights assigned to the block itself (while this is not ideal heuristic in
76 /// theory it's simple and works reasonably well in most cases) and the process
77 /// repeats. Once the process of weights propagation converges branch
78 /// probabilities are set for all such branches that have at least one successor
79 /// with the weight set. Default execution weight (BlockExecWeight::DEFAULT) is
80 /// used for any successors which doesn't have its weight set. For loop back
81 /// branches we use their weights scaled by loop trip count equal to
82 /// 'LBH_TAKEN_WEIGHT/LBH_NOTTAKEN_WEIGHT'.
83 ///
84 /// Here is a simple example demonstrating how the described algorithm works.
85 ///
86 /// BB1
87 /// / \
88 /// v v
89 /// BB2 BB3
90 /// / \
91 /// v v
92 /// ColdBB UnreachBB
93 ///
94 /// Initially, ColdBB is associated with COLD_WEIGHT and UnreachBB with
95 /// UNREACHABLE_WEIGHT. COLD_WEIGHT is set to BB2 as maximum between its
96 /// successors. BB1 and BB3 has no explicit estimated weights and assumed to
97 /// have DEFAULT_WEIGHT. Based on assigned weights branches will have the
98 /// following probabilities:
99 /// P(BB1->BB2) = COLD_WEIGHT/(COLD_WEIGHT + DEFAULT_WEIGHT) =
100 /// 0xffff / (0xffff + 0xfffff) = 0.0588(5.9%)
101 /// P(BB1->BB3) = DEFAULT_WEIGHT_WEIGHT/(COLD_WEIGHT + DEFAULT_WEIGHT) =
102 /// 0xfffff / (0xffff + 0xfffff) = 0.941(94.1%)
103 /// P(BB2->ColdBB) = COLD_WEIGHT/(COLD_WEIGHT + UNREACHABLE_WEIGHT) = 1(100%)
104 /// P(BB2->UnreachBB) =
105 /// UNREACHABLE_WEIGHT/(COLD_WEIGHT+UNREACHABLE_WEIGHT) = 0(0%)
106 ///
107 /// If no branch probabilities were calculated on this step then take the next
108 /// one.
109 ///
110 /// Third, apply different kinds of local heuristics for each individual
111 /// branch until first match. For example probability of a pointer to be null is
112 /// estimated as PH_TAKEN_WEIGHT/(PH_TAKEN_WEIGHT + PH_NONTAKEN_WEIGHT). If
113 /// no local heuristic has been matched then branch is left with no explicit
114 /// probability set and assumed to have default probability.
116 public:
117  BranchProbabilityInfo() = default;
118 
120  const TargetLibraryInfo *TLI = nullptr,
121  DominatorTree *DT = nullptr,
122  PostDominatorTree *PDT = nullptr) {
123  calculate(F, LI, TLI, DT, PDT);
124  }
125 
127  : Probs(std::move(Arg.Probs)), LastF(Arg.LastF),
128  EstimatedBlockWeight(std::move(Arg.EstimatedBlockWeight)) {}
129 
132 
134  releaseMemory();
135  Probs = std::move(RHS.Probs);
136  EstimatedBlockWeight = std::move(RHS.EstimatedBlockWeight);
137  return *this;
138  }
139 
140  bool invalidate(Function &, const PreservedAnalyses &PA,
142 
143  void releaseMemory();
144 
145  void print(raw_ostream &OS) const;
146 
147  /// Get an edge's probability, relative to other out-edges of the Src.
148  ///
149  /// This routine provides access to the fractional probability between zero
150  /// (0%) and one (100%) of this edge executing, relative to other edges
151  /// leaving the 'Src' block. The returned probability is never zero, and can
152  /// only be one if the source block has only one successor.
154  unsigned IndexInSuccessors) const;
155 
156  /// Get the probability of going from Src to Dst.
157  ///
158  /// It returns the sum of all probabilities for edges from Src to Dst.
160  const BasicBlock *Dst) const;
161 
163  const_succ_iterator Dst) const;
164 
165  /// Test if an edge is hot relative to other out-edges of the Src.
166  ///
167  /// Check whether this edge out of the source block is 'hot'. We define hot
168  /// as having a relative probability >= 80%.
169  bool isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const;
170 
171  /// Print an edge's probability.
172  ///
173  /// Retrieves an edge's probability similarly to \see getEdgeProbability, but
174  /// then prints that probability to the provided stream. That stream is then
175  /// returned.
177  const BasicBlock *Dst) const;
178 
179 public:
180  /// Set the raw probabilities for all edges from the given block.
181  ///
182  /// This allows a pass to explicitly set edge probabilities for a block. It
183  /// can be used when updating the CFG to update the branch probability
184  /// information.
185  void setEdgeProbability(const BasicBlock *Src,
187 
188  /// Copy outgoing edge probabilities from \p Src to \p Dst.
189  ///
190  /// This allows to keep probabilities unset for the destination if they were
191  /// unset for source.
193 
195  static const BranchProbability LikelyProb((1u << 20) - 1, 1u << 20);
196  return IsLikely ? LikelyProb : LikelyProb.getCompl();
197  }
198 
199  void calculate(const Function &F, const LoopInfo &LI,
200  const TargetLibraryInfo *TLI, DominatorTree *DT,
201  PostDominatorTree *PDT);
202 
203  /// Forget analysis results for the given basic block.
204  void eraseBlock(const BasicBlock *BB);
205 
206  // Data structure to track SCCs for handling irreducible loops.
207  class SccInfo {
208  // Enum of types to classify basic blocks in SCC. Basic block belonging to
209  // SCC is 'Inner' until it is either 'Header' or 'Exiting'. Note that a
210  // basic block can be 'Header' and 'Exiting' at the same time.
211  enum SccBlockType {
212  Inner = 0x0,
213  Header = 0x1,
214  Exiting = 0x2,
215  };
216  // Map of basic blocks to SCC IDs they belong to. If basic block doesn't
217  // belong to any SCC it is not in the map.
219  // Each basic block in SCC is attributed with one or several types from
220  // SccBlockType. Map value has uint32_t type (instead of SccBlockType)
221  // since basic block may be for example "Header" and "Exiting" at the same
222  // time and we need to be able to keep more than one value from
223  // SccBlockType.
225  // Vector containing classification of basic blocks for all SCCs where i'th
226  // vector element corresponds to SCC with ID equal to i.
227  using SccBlockTypeMaps = std::vector<SccBlockTypeMap>;
228 
229  SccMap SccNums;
230  SccBlockTypeMaps SccBlocks;
231 
232  public:
233  explicit SccInfo(const Function &F);
234 
235  /// If \p BB belongs to some SCC then ID of that SCC is returned, otherwise
236  /// -1 is returned. If \p BB belongs to more than one SCC at the same time
237  /// result is undefined.
238  int getSCCNum(const BasicBlock *BB) const;
239  /// Returns true if \p BB is a 'header' block in SCC with \p SccNum ID,
240  /// false otherwise.
241  bool isSCCHeader(const BasicBlock *BB, int SccNum) const {
242  return getSccBlockType(BB, SccNum) & Header;
243  }
244  /// Returns true if \p BB is an 'exiting' block in SCC with \p SccNum ID,
245  /// false otherwise.
246  bool isSCCExitingBlock(const BasicBlock *BB, int SccNum) const {
247  return getSccBlockType(BB, SccNum) & Exiting;
248  }
249  /// Fills in \p Enters vector with all such blocks that don't belong to
250  /// SCC with \p SccNum ID but there is an edge to a block belonging to the
251  /// SCC.
252  void getSccEnterBlocks(int SccNum,
253  SmallVectorImpl<BasicBlock *> &Enters) const;
254  /// Fills in \p Exits vector with all such blocks that don't belong to
255  /// SCC with \p SccNum ID but there is an edge from a block belonging to the
256  /// SCC.
257  void getSccExitBlocks(int SccNum,
258  SmallVectorImpl<BasicBlock *> &Exits) const;
259 
260  private:
261  /// Returns \p BB's type according to classification given by SccBlockType
262  /// enum. Please note that \p BB must belong to SSC with \p SccNum ID.
263  uint32_t getSccBlockType(const BasicBlock *BB, int SccNum) const;
264  /// Calculates \p BB's type and stores it in internal data structures for
265  /// future use. Please note that \p BB must belong to SSC with \p SccNum ID.
266  void calculateSccBlockType(const BasicBlock *BB, int SccNum);
267  };
268 
269 private:
270  // We need to store CallbackVH's in order to correctly handle basic block
271  // removal.
272  class BasicBlockCallbackVH final : public CallbackVH {
274 
275  void deleted() override {
276  assert(BPI != nullptr);
277  BPI->eraseBlock(cast<BasicBlock>(getValPtr()));
278  }
279 
280  public:
281  BasicBlockCallbackVH(const Value *V, BranchProbabilityInfo *BPI = nullptr)
282  : CallbackVH(const_cast<Value *>(V)), BPI(BPI) {}
283  };
284 
285  /// Pair of Loop and SCC ID number. Used to unify handling of normal and
286  /// SCC based loop representations.
287  using LoopData = std::pair<Loop *, int>;
288  /// Helper class to keep basic block along with its loop data information.
289  class LoopBlock {
290  public:
291  explicit LoopBlock(const BasicBlock *BB, const LoopInfo &LI,
292  const SccInfo &SccI);
293 
294  const BasicBlock *getBlock() const { return BB; }
295  BasicBlock *getBlock() { return const_cast<BasicBlock *>(BB); }
296  LoopData getLoopData() const { return LD; }
297  Loop *getLoop() const { return LD.first; }
298  int getSccNum() const { return LD.second; }
299 
300  bool belongsToLoop() const { return getLoop() || getSccNum() != -1; }
301  bool belongsToSameLoop(const LoopBlock &LB) const {
302  return (LB.getLoop() && getLoop() == LB.getLoop()) ||
303  (LB.getSccNum() != -1 && getSccNum() == LB.getSccNum());
304  }
305 
306  private:
307  const BasicBlock *const BB = nullptr;
308  LoopData LD = {nullptr, -1};
309  };
310 
311  // Pair of LoopBlocks representing an edge from first to second block.
312  using LoopEdge = std::pair<const LoopBlock &, const LoopBlock &>;
313 
314  DenseSet<BasicBlockCallbackVH, DenseMapInfo<Value*>> Handles;
315 
316  // Since we allow duplicate edges from one basic block to another, we use
317  // a pair (PredBlock and an index in the successors) to specify an edge.
318  using Edge = std::pair<const BasicBlock *, unsigned>;
319 
320  DenseMap<Edge, BranchProbability> Probs;
321 
322  /// Track the last function we run over for printing.
323  const Function *LastF = nullptr;
324 
325  const LoopInfo *LI = nullptr;
326 
327  /// Keeps information about all SCCs in a function.
328  std::unique_ptr<const SccInfo> SccI;
329 
330  /// Keeps mapping of a basic block to its estimated weight.
331  SmallDenseMap<const BasicBlock *, uint32_t> EstimatedBlockWeight;
332 
333  /// Keeps mapping of a loop to estimated weight to enter the loop.
334  SmallDenseMap<LoopData, uint32_t> EstimatedLoopWeight;
335 
336  /// Helper to construct LoopBlock for \p BB.
337  LoopBlock getLoopBlock(const BasicBlock *BB) const {
338  return LoopBlock(BB, *LI, *SccI.get());
339  }
340 
341  /// Returns true if destination block belongs to some loop and source block is
342  /// either doesn't belong to any loop or belongs to a loop which is not inner
343  /// relative to the destination block.
344  bool isLoopEnteringEdge(const LoopEdge &Edge) const;
345  /// Returns true if source block belongs to some loop and destination block is
346  /// either doesn't belong to any loop or belongs to a loop which is not inner
347  /// relative to the source block.
348  bool isLoopExitingEdge(const LoopEdge &Edge) const;
349  /// Returns true if \p Edge is either enters to or exits from some loop, false
350  /// in all other cases.
351  bool isLoopEnteringExitingEdge(const LoopEdge &Edge) const;
352  /// Returns true if source and destination blocks belongs to the same loop and
353  /// destination block is loop header.
354  bool isLoopBackEdge(const LoopEdge &Edge) const;
355  // Fills in \p Enters vector with all "enter" blocks to a loop \LB belongs to.
356  void getLoopEnterBlocks(const LoopBlock &LB,
357  SmallVectorImpl<BasicBlock *> &Enters) const;
358  // Fills in \p Exits vector with all "exit" blocks from a loop \LB belongs to.
359  void getLoopExitBlocks(const LoopBlock &LB,
360  SmallVectorImpl<BasicBlock *> &Exits) const;
361 
362  /// Returns estimated weight for \p BB. None if \p BB has no estimated weight.
363  Optional<uint32_t> getEstimatedBlockWeight(const BasicBlock *BB) const;
364 
365  /// Returns estimated weight to enter \p L. In other words it is weight of
366  /// loop's header block not scaled by trip count. Returns None if \p L has no
367  /// no estimated weight.
368  Optional<uint32_t> getEstimatedLoopWeight(const LoopData &L) const;
369 
370  /// Return estimated weight for \p Edge. Returns None if estimated weight is
371  /// unknown.
372  Optional<uint32_t> getEstimatedEdgeWeight(const LoopEdge &Edge) const;
373 
374  /// Iterates over all edges leading from \p SrcBB to \p Successors and
375  /// returns maximum of all estimated weights. If at least one edge has unknown
376  /// estimated weight None is returned.
377  template <class IterT>
378  Optional<uint32_t>
379  getMaxEstimatedEdgeWeight(const LoopBlock &SrcBB,
380  iterator_range<IterT> Successors) const;
381 
382  /// If \p LoopBB has no estimated weight then set it to \p BBWeight and
383  /// return true. Otherwise \p BB's weight remains unchanged and false is
384  /// returned. In addition all blocks/loops that might need their weight to be
385  /// re-estimated are put into BlockWorkList/LoopWorkList.
386  bool updateEstimatedBlockWeight(LoopBlock &LoopBB, uint32_t BBWeight,
387  SmallVectorImpl<BasicBlock *> &BlockWorkList,
388  SmallVectorImpl<LoopBlock> &LoopWorkList);
389 
390  /// Starting from \p LoopBB (including \p LoopBB itself) propagate \p BBWeight
391  /// up the domination tree.
392  void propagateEstimatedBlockWeight(const LoopBlock &LoopBB, DominatorTree *DT,
393  PostDominatorTree *PDT, uint32_t BBWeight,
394  SmallVectorImpl<BasicBlock *> &WorkList,
395  SmallVectorImpl<LoopBlock> &LoopWorkList);
396 
397  /// Returns block's weight encoded in the IR.
398  Optional<uint32_t> getInitialEstimatedBlockWeight(const BasicBlock *BB);
399 
400  // Computes estimated weights for all blocks in \p F.
401  void computeEestimateBlockWeight(const Function &F, DominatorTree *DT,
402  PostDominatorTree *PDT);
403 
404  /// Based on computed weights by \p computeEstimatedBlockWeight set
405  /// probabilities on branches.
406  bool calcEstimatedHeuristics(const BasicBlock *BB);
407  bool calcMetadataWeights(const BasicBlock *BB);
408  bool calcPointerHeuristics(const BasicBlock *BB);
409  bool calcZeroHeuristics(const BasicBlock *BB, const TargetLibraryInfo *TLI);
410  bool calcFloatingPointHeuristics(const BasicBlock *BB);
411 };
412 
413 /// Analysis pass which computes \c BranchProbabilityInfo.
415  : public AnalysisInfoMixin<BranchProbabilityAnalysis> {
417 
418  static AnalysisKey Key;
419 
420 public:
421  /// Provide the result type for this analysis pass.
423 
424  /// Run the analysis pass over a function and produce BPI.
426 };
427 
428 /// Printer pass for the \c BranchProbabilityAnalysis results.
430  : public PassInfoMixin<BranchProbabilityPrinterPass> {
431  raw_ostream &OS;
432 
433 public:
434  explicit BranchProbabilityPrinterPass(raw_ostream &OS) : OS(OS) {}
435 
437 };
438 
439 /// Legacy analysis pass which computes \c BranchProbabilityInfo.
442 
443 public:
444  static char ID;
445 
447 
448  BranchProbabilityInfo &getBPI() { return BPI; }
449  const BranchProbabilityInfo &getBPI() const { return BPI; }
450 
451  void getAnalysisUsage(AnalysisUsage &AU) const override;
452  bool runOnFunction(Function &F) override;
453  void releaseMemory() override;
454  void print(raw_ostream &OS, const Module *M = nullptr) const override;
455 };
456 
457 } // end namespace llvm
458 
459 #endif // LLVM_ANALYSIS_BRANCHPROBABILITYINFO_H
llvm::SuccIterator
Definition: CFG.h:139
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm::BranchProbabilityPrinterPass
Printer pass for the BranchProbabilityAnalysis results.
Definition: BranchProbabilityInfo.h:429
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::BranchProbabilityInfo::SccInfo::getSccExitBlocks
void getSccExitBlocks(int SccNum, SmallVectorImpl< BasicBlock * > &Exits) const
Fills in Exits vector with all such blocks that don't belong to SCC with SccNum ID but there is an ed...
Definition: BranchProbabilityInfo.cpp:186
llvm::PassInfoMixin
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:374
llvm::Function
Definition: Function.h:61
Pass.h
llvm::ARM_MB::LD
@ LD
Definition: ARMBaseInfo.h:72
llvm::BranchProbabilityInfo::operator=
BranchProbabilityInfo & operator=(BranchProbabilityInfo &&RHS)
Definition: BranchProbabilityInfo.h:133
llvm::BranchProbabilityInfo::SccInfo::isSCCHeader
bool isSCCHeader(const BasicBlock *BB, int SccNum) const
Returns true if BB is a 'header' block in SCC with SccNum ID, false otherwise.
Definition: BranchProbabilityInfo.h:241
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
DenseMap.h
llvm::BranchProbabilityInfo::releaseMemory
void releaseMemory()
Definition: BranchProbabilityInfo.cpp:1076
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::BranchProbabilityInfo::BranchProbabilityInfo
BranchProbabilityInfo(const Function &F, const LoopInfo &LI, const TargetLibraryInfo *TLI=nullptr, DominatorTree *DT=nullptr, PostDominatorTree *PDT=nullptr)
Definition: BranchProbabilityInfo.h:119
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
Arg
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Definition: AMDGPULibCalls.cpp:206
llvm::BranchProbabilityAnalysis
Analysis pass which computes BranchProbabilityInfo.
Definition: BranchProbabilityInfo.h:414
llvm::BranchProbabilityInfoWrapperPass
Legacy analysis pass which computes BranchProbabilityInfo.
Definition: BranchProbabilityInfo.h:440
llvm::BranchProbabilityInfo::SccInfo::getSccEnterBlocks
void getSccEnterBlocks(int SccNum, SmallVectorImpl< BasicBlock * > &Enters) const
Fills in Enters vector with all such blocks that don't belong to SCC with SccNum ID but there is an e...
Definition: BranchProbabilityInfo.cpp:174
llvm::BranchProbabilityInfo::BranchProbabilityInfo
BranchProbabilityInfo(BranchProbabilityInfo &&Arg)
Definition: BranchProbabilityInfo.h:126
llvm::BranchProbabilityInfo::SccInfo::isSCCExitingBlock
bool isSCCExitingBlock(const BasicBlock *BB, int SccNum) const
Returns true if BB is an 'exiting' block in SCC with SccNum ID, false otherwise.
Definition: BranchProbabilityInfo.h:246
llvm::BranchProbabilityInfoWrapperPass::getBPI
BranchProbabilityInfo & getBPI()
Definition: BranchProbabilityInfo.h:448
llvm::BranchProbabilityInfo
Analysis providing branch probability information.
Definition: BranchProbabilityInfo.h:115
llvm::BranchProbabilityInfo::BranchProbabilityInfo
BranchProbabilityInfo()=default
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
DenseSet.h
llvm::BranchProbabilityAnalysis::run
BranchProbabilityInfo run(Function &F, FunctionAnalysisManager &AM)
Run the analysis pass over a function and produce BPI.
Definition: BranchProbabilityInfo.cpp:1323
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
SmallPtrSet.h
llvm::AnalysisManager::Invalidator
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:656
llvm::BranchProbabilityPrinterPass::BranchProbabilityPrinterPass
BranchProbabilityPrinterPass(raw_ostream &OS)
Definition: BranchProbabilityInfo.h:434
llvm::BranchProbabilityInfo::getBranchProbStackProtector
static BranchProbability getBranchProbStackProtector(bool IsLikely)
Definition: BranchProbabilityInfo.h:194
BranchProbability.h
CFG.h
BasicBlock.h
move
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
Definition: README.txt:546
llvm::BranchProbabilityInfo::copyEdgeProbabilities
void copyEdgeProbabilities(BasicBlock *Src, BasicBlock *Dst)
Copy outgoing edge probabilities from Src to Dst.
Definition: BranchProbabilityInfo.cpp:1177
llvm::DenseMap< const BasicBlock *, int >
llvm::AnalysisKey
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:72
llvm::BranchProbabilityInfoWrapperPass::releaseMemory
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
Definition: BranchProbabilityInfo.cpp:1314
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::move
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1605
llvm::ISD::BasicBlock
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
llvm::BranchProbabilityInfo::eraseBlock
void eraseBlock(const BasicBlock *BB)
Forget analysis results for the given basic block.
Definition: BranchProbabilityInfo.cpp:1208
llvm::BranchProbabilityInfoWrapperPass::print
void print(raw_ostream &OS, const Module *M=nullptr) const override
print - Print out the internal state of the pass.
Definition: BranchProbabilityInfo.cpp:1316
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:67
llvm::AnalysisInfoMixin
A CRTP mix-in that provides informational APIs needed for analysis passes.
Definition: PassManager.h:391
llvm::BranchProbabilityInfo::getEdgeProbability
BranchProbability getEdgeProbability(const BasicBlock *Src, unsigned IndexInSuccessors) const
Get an edge's probability, relative to other out-edges of the Src.
Definition: BranchProbabilityInfo.cpp:1113
llvm::BranchProbabilityInfo::setEdgeProbability
void setEdgeProbability(const BasicBlock *Src, const SmallVectorImpl< BranchProbability > &Probs)
Set the raw probabilities for all edges from the given block.
Definition: BranchProbabilityInfo.cpp:1150
llvm::LoopInfo
Definition: LoopInfo.h:1083
llvm::BranchProbabilityInfoWrapperPass::BranchProbabilityInfoWrapperPass
BranchProbabilityInfoWrapperPass()
Definition: BranchProbabilityInfo.cpp:69
llvm::PostDominatorTree
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
Definition: PostDominators.h:28
uint32_t
llvm::BranchProbability
Definition: BranchProbability.h:30
ValueHandle.h
llvm::BranchProbabilityInfo::printEdgeProbability
raw_ostream & printEdgeProbability(raw_ostream &OS, const BasicBlock *Src, const BasicBlock *Dst) const
Print an edge's probability.
Definition: BranchProbabilityInfo.cpp:1197
std
Definition: BitVector.h:838
llvm::BranchProbabilityInfoWrapperPass::runOnFunction
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
Definition: BranchProbabilityInfo.cpp:1303
llvm::BranchProbabilityInfo::print
void print(raw_ostream &OS) const
Definition: BranchProbabilityInfo.cpp:1090
Casting.h
llvm::BranchProbabilityInfo::operator=
BranchProbabilityInfo & operator=(const BranchProbabilityInfo &)=delete
llvm::TargetStackID::Value
Value
Definition: TargetFrameLowering.h:27
PassManager.h
llvm::TargetLibraryInfo
Provides information about what library functions are available for the current target.
Definition: TargetLibraryInfo.h:219
llvm::BranchProbabilityInfo::SccInfo
Definition: BranchProbabilityInfo.h:207
llvm::BranchProbabilityInfo::calculate
void calculate(const Function &F, const LoopInfo &LI, const TargetLibraryInfo *TLI, DominatorTree *DT, PostDominatorTree *PDT)
Definition: BranchProbabilityInfo.cpp:1230
llvm::CallbackVH
Value handle with callbacks on RAUW and destruction.
Definition: ValueHandle.h:383
llvm::BranchProbability::getCompl
BranchProbability getCompl() const
Definition: BranchProbability.h:69
llvm::BranchProbabilityInfoWrapperPass::getBPI
const BranchProbabilityInfo & getBPI() const
Definition: BranchProbabilityInfo.h:449
llvm::BranchProbabilityInfo::isEdgeHot
bool isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const
Test if an edge is hot relative to other out-edges of the Src.
Definition: BranchProbabilityInfo.cpp:1102
llvm::BranchProbabilityInfoWrapperPass::ID
static char ID
Definition: BranchProbabilityInfo.h:444
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:43
DenseMapInfo.h
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
llvm::BranchProbabilityInfo::invalidate
bool invalidate(Function &, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &)
Definition: BranchProbabilityInfo.cpp:1081
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
llvm::BranchProbabilityInfoWrapperPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: BranchProbabilityInfo.cpp:1290
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::BranchProbabilityPrinterPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: BranchProbabilityInfo.cpp:1333
llvm::BranchProbabilityInfo::SccInfo::getSCCNum
int getSCCNum(const BasicBlock *BB) const
If BB belongs to some SCC then ID of that SCC is returned, otherwise -1 is returned.
Definition: BranchProbabilityInfo.cpp:167
llvm::codeview::PublicSymFlags::Function
@ Function
llvm::BranchProbabilityInfo::SccInfo::SccInfo
SccInfo(const Function &F)
Definition: BranchProbabilityInfo.cpp:144