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