LLVM  13.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  /// Retrieve the hot successor of a block if one exists.
172  ///
173  /// Given a basic block, look through its successors and if one exists for
174  /// which \see isEdgeHot would return true, return that successor block.
175  const BasicBlock *getHotSucc(const BasicBlock *BB) const;
176 
177  /// Print an edge's probability.
178  ///
179  /// Retrieves an edge's probability similarly to \see getEdgeProbability, but
180  /// then prints that probability to the provided stream. That stream is then
181  /// returned.
183  const BasicBlock *Dst) const;
184 
185 public:
186  /// Set the raw probabilities for all edges from the given block.
187  ///
188  /// This allows a pass to explicitly set edge probabilities for a block. It
189  /// can be used when updating the CFG to update the branch probability
190  /// information.
191  void setEdgeProbability(const BasicBlock *Src,
193 
194  /// Copy outgoing edge probabilities from \p Src to \p Dst.
195  ///
196  /// This allows to keep probabilities unset for the destination if they were
197  /// unset for source.
199 
201  static const BranchProbability LikelyProb((1u << 20) - 1, 1u << 20);
202  return IsLikely ? LikelyProb : LikelyProb.getCompl();
203  }
204 
205  void calculate(const Function &F, const LoopInfo &LI,
206  const TargetLibraryInfo *TLI, DominatorTree *DT,
207  PostDominatorTree *PDT);
208 
209  /// Forget analysis results for the given basic block.
210  void eraseBlock(const BasicBlock *BB);
211 
212  // Data structure to track SCCs for handling irreducible loops.
213  class SccInfo {
214  // Enum of types to classify basic blocks in SCC. Basic block belonging to
215  // SCC is 'Inner' until it is either 'Header' or 'Exiting'. Note that a
216  // basic block can be 'Header' and 'Exiting' at the same time.
217  enum SccBlockType {
218  Inner = 0x0,
219  Header = 0x1,
220  Exiting = 0x2,
221  };
222  // Map of basic blocks to SCC IDs they belong to. If basic block doesn't
223  // belong to any SCC it is not in the map.
225  // Each basic block in SCC is attributed with one or several types from
226  // SccBlockType. Map value has uint32_t type (instead of SccBlockType)
227  // since basic block may be for example "Header" and "Exiting" at the same
228  // time and we need to be able to keep more than one value from
229  // SccBlockType.
231  // Vector containing classification of basic blocks for all SCCs where i'th
232  // vector element corresponds to SCC with ID equal to i.
233  using SccBlockTypeMaps = std::vector<SccBlockTypeMap>;
234 
235  SccMap SccNums;
236  SccBlockTypeMaps SccBlocks;
237 
238  public:
239  explicit SccInfo(const Function &F);
240 
241  /// If \p BB belongs to some SCC then ID of that SCC is returned, otherwise
242  /// -1 is returned. If \p BB belongs to more than one SCC at the same time
243  /// result is undefined.
244  int getSCCNum(const BasicBlock *BB) const;
245  /// Returns true if \p BB is a 'header' block in SCC with \p SccNum ID,
246  /// false otherwise.
247  bool isSCCHeader(const BasicBlock *BB, int SccNum) const {
248  return getSccBlockType(BB, SccNum) & Header;
249  }
250  /// Returns true if \p BB is an 'exiting' block in SCC with \p SccNum ID,
251  /// false otherwise.
252  bool isSCCExitingBlock(const BasicBlock *BB, int SccNum) const {
253  return getSccBlockType(BB, SccNum) & Exiting;
254  }
255  /// Fills in \p Enters vector with all such blocks that don't belong to
256  /// SCC with \p SccNum ID but there is an edge to a block belonging to the
257  /// SCC.
258  void getSccEnterBlocks(int SccNum,
259  SmallVectorImpl<BasicBlock *> &Enters) const;
260  /// Fills in \p Exits vector with all such blocks that don't belong to
261  /// SCC with \p SccNum ID but there is an edge from a block belonging to the
262  /// SCC.
263  void getSccExitBlocks(int SccNum,
264  SmallVectorImpl<BasicBlock *> &Exits) const;
265 
266  private:
267  /// Returns \p BB's type according to classification given by SccBlockType
268  /// enum. Please note that \p BB must belong to SSC with \p SccNum ID.
269  uint32_t getSccBlockType(const BasicBlock *BB, int SccNum) const;
270  /// Calculates \p BB's type and stores it in internal data structures for
271  /// future use. Please note that \p BB must belong to SSC with \p SccNum ID.
272  void calculateSccBlockType(const BasicBlock *BB, int SccNum);
273  };
274 
275 private:
276  // We need to store CallbackVH's in order to correctly handle basic block
277  // removal.
278  class BasicBlockCallbackVH final : public CallbackVH {
280 
281  void deleted() override {
282  assert(BPI != nullptr);
283  BPI->eraseBlock(cast<BasicBlock>(getValPtr()));
284  }
285 
286  public:
287  BasicBlockCallbackVH(const Value *V, BranchProbabilityInfo *BPI = nullptr)
288  : CallbackVH(const_cast<Value *>(V)), BPI(BPI) {}
289  };
290 
291  /// Pair of Loop and SCC ID number. Used to unify handling of normal and
292  /// SCC based loop representations.
293  using LoopData = std::pair<Loop *, int>;
294  /// Helper class to keep basic block along with its loop data information.
295  class LoopBlock {
296  public:
297  explicit LoopBlock(const BasicBlock *BB, const LoopInfo &LI,
298  const SccInfo &SccI);
299 
300  const BasicBlock *getBlock() const { return BB; }
301  BasicBlock *getBlock() { return const_cast<BasicBlock *>(BB); }
302  LoopData getLoopData() const { return LD; }
303  Loop *getLoop() const { return LD.first; }
304  int getSccNum() const { return LD.second; }
305 
306  bool belongsToLoop() const { return getLoop() || getSccNum() != -1; }
307  bool belongsToSameLoop(const LoopBlock &LB) const {
308  return (LB.getLoop() && getLoop() == LB.getLoop()) ||
309  (LB.getSccNum() != -1 && getSccNum() == LB.getSccNum());
310  }
311 
312  private:
313  const BasicBlock *const BB = nullptr;
314  LoopData LD = {nullptr, -1};
315  };
316 
317  // Pair of LoopBlocks representing an edge from first to second block.
318  using LoopEdge = std::pair<const LoopBlock &, const LoopBlock &>;
319 
320  DenseSet<BasicBlockCallbackVH, DenseMapInfo<Value*>> Handles;
321 
322  // Since we allow duplicate edges from one basic block to another, we use
323  // a pair (PredBlock and an index in the successors) to specify an edge.
324  using Edge = std::pair<const BasicBlock *, unsigned>;
325 
326  DenseMap<Edge, BranchProbability> Probs;
327 
328  /// Track the last function we run over for printing.
329  const Function *LastF = nullptr;
330 
331  const LoopInfo *LI = nullptr;
332 
333  /// Keeps information about all SCCs in a function.
334  std::unique_ptr<const SccInfo> SccI;
335 
336  /// Keeps mapping of a basic block to its estimated weight.
337  SmallDenseMap<const BasicBlock *, uint32_t> EstimatedBlockWeight;
338 
339  /// Keeps mapping of a loop to estimated weight to enter the loop.
340  SmallDenseMap<LoopData, uint32_t> EstimatedLoopWeight;
341 
342  /// Helper to construct LoopBlock for \p BB.
343  LoopBlock getLoopBlock(const BasicBlock *BB) const {
344  return LoopBlock(BB, *LI, *SccI.get());
345  }
346 
347  /// Returns true if destination block belongs to some loop and source block is
348  /// either doesn't belong to any loop or belongs to a loop which is not inner
349  /// relative to the destination block.
350  bool isLoopEnteringEdge(const LoopEdge &Edge) const;
351  /// Returns true if source block belongs to some loop and destination block is
352  /// either doesn't belong to any loop or belongs to a loop which is not inner
353  /// relative to the source block.
354  bool isLoopExitingEdge(const LoopEdge &Edge) const;
355  /// Returns true if \p Edge is either enters to or exits from some loop, false
356  /// in all other cases.
357  bool isLoopEnteringExitingEdge(const LoopEdge &Edge) const;
358  /// Returns true if source and destination blocks belongs to the same loop and
359  /// destination block is loop header.
360  bool isLoopBackEdge(const LoopEdge &Edge) const;
361  // Fills in \p Enters vector with all "enter" blocks to a loop \LB belongs to.
362  void getLoopEnterBlocks(const LoopBlock &LB,
363  SmallVectorImpl<BasicBlock *> &Enters) const;
364  // Fills in \p Exits vector with all "exit" blocks from a loop \LB belongs to.
365  void getLoopExitBlocks(const LoopBlock &LB,
366  SmallVectorImpl<BasicBlock *> &Exits) const;
367 
368  /// Returns estimated weight for \p BB. None if \p BB has no estimated weight.
369  Optional<uint32_t> getEstimatedBlockWeight(const BasicBlock *BB) const;
370 
371  /// Returns estimated weight to enter \p L. In other words it is weight of
372  /// loop's header block not scaled by trip count. Returns None if \p L has no
373  /// no estimated weight.
374  Optional<uint32_t> getEstimatedLoopWeight(const LoopData &L) const;
375 
376  /// Return estimated weight for \p Edge. Returns None if estimated weight is
377  /// unknown.
378  Optional<uint32_t> getEstimatedEdgeWeight(const LoopEdge &Edge) const;
379 
380  /// Iterates over all edges leading from \p SrcBB to \p Successors and
381  /// returns maximum of all estimated weights. If at least one edge has unknown
382  /// estimated weight None is returned.
383  template <class IterT>
384  Optional<uint32_t>
385  getMaxEstimatedEdgeWeight(const LoopBlock &SrcBB,
386  iterator_range<IterT> Successors) const;
387 
388  /// If \p LoopBB has no estimated weight then set it to \p BBWeight and
389  /// return true. Otherwise \p BB's weight remains unchanged and false is
390  /// returned. In addition all blocks/loops that might need their weight to be
391  /// re-estimated are put into BlockWorkList/LoopWorkList.
392  bool updateEstimatedBlockWeight(LoopBlock &LoopBB, uint32_t BBWeight,
393  SmallVectorImpl<BasicBlock *> &BlockWorkList,
394  SmallVectorImpl<LoopBlock> &LoopWorkList);
395 
396  /// Starting from \p LoopBB (including \p LoopBB itself) propagate \p BBWeight
397  /// up the domination tree.
398  void propagateEstimatedBlockWeight(const LoopBlock &LoopBB, DominatorTree *DT,
399  PostDominatorTree *PDT, uint32_t BBWeight,
400  SmallVectorImpl<BasicBlock *> &WorkList,
401  SmallVectorImpl<LoopBlock> &LoopWorkList);
402 
403  /// Returns block's weight encoded in the IR.
404  Optional<uint32_t> getInitialEstimatedBlockWeight(const BasicBlock *BB);
405 
406  // Computes estimated weights for all blocks in \p F.
407  void computeEestimateBlockWeight(const Function &F, DominatorTree *DT,
408  PostDominatorTree *PDT);
409 
410  /// Based on computed weights by \p computeEstimatedBlockWeight set
411  /// probabilities on branches.
412  bool calcEstimatedHeuristics(const BasicBlock *BB);
413  bool calcMetadataWeights(const BasicBlock *BB);
414  bool calcPointerHeuristics(const BasicBlock *BB);
415  bool calcZeroHeuristics(const BasicBlock *BB, const TargetLibraryInfo *TLI);
416  bool calcFloatingPointHeuristics(const BasicBlock *BB);
417 };
418 
419 /// Analysis pass which computes \c BranchProbabilityInfo.
421  : public AnalysisInfoMixin<BranchProbabilityAnalysis> {
423 
424  static AnalysisKey Key;
425 
426 public:
427  /// Provide the result type for this analysis pass.
429 
430  /// Run the analysis pass over a function and produce BPI.
432 };
433 
434 /// Printer pass for the \c BranchProbabilityAnalysis results.
436  : public PassInfoMixin<BranchProbabilityPrinterPass> {
437  raw_ostream &OS;
438 
439 public:
440  explicit BranchProbabilityPrinterPass(raw_ostream &OS) : OS(OS) {}
441 
443 };
444 
445 /// Legacy analysis pass which computes \c BranchProbabilityInfo.
448 
449 public:
450  static char ID;
451 
453 
454  BranchProbabilityInfo &getBPI() { return BPI; }
455  const BranchProbabilityInfo &getBPI() const { return BPI; }
456 
457  void getAnalysisUsage(AnalysisUsage &AU) const override;
458  bool runOnFunction(Function &F) override;
459  void releaseMemory() override;
460  void print(raw_ostream &OS, const Module *M = nullptr) const override;
461 };
462 
463 } // end namespace llvm
464 
465 #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:435
llvm
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:247
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
llvm::BranchProbabilityInfo::getHotSucc
const BasicBlock * getHotSucc(const BasicBlock *BB) const
Retrieve the hot successor of a block if one exists.
Definition: BranchProbabilityInfo.cpp:1109
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:205
llvm::BranchProbabilityAnalysis
Analysis pass which computes BranchProbabilityInfo.
Definition: BranchProbabilityInfo.h:420
llvm::BranchProbabilityInfoWrapperPass
Legacy analysis pass which computes BranchProbabilityInfo.
Definition: BranchProbabilityInfo.h:446
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:252
llvm::BranchProbabilityInfoWrapperPass::getBPI
BranchProbabilityInfo & getBPI()
Definition: BranchProbabilityInfo.h:454
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:1342
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:50
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:440
llvm::BranchProbabilityInfo::getBranchProbStackProtector
static BranchProbability getBranchProbStackProtector(bool IsLikely)
Definition: BranchProbabilityInfo.h:200
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:1196
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:1333
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:1540
llvm::ISD::BasicBlock
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:64
llvm::BranchProbabilityInfo::eraseBlock
void eraseBlock(const BasicBlock *BB)
Forget analysis results for the given basic block.
Definition: BranchProbabilityInfo.cpp:1227
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:1335
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:1133
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:1170
llvm::LoopInfo
Definition: LoopInfo.h:1080
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:1216
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:1322
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:208
llvm::BranchProbabilityInfo::SccInfo
Definition: BranchProbabilityInfo.h:213
llvm::BranchProbabilityInfo::calculate
void calculate(const Function &F, const LoopInfo &LI, const TargetLibraryInfo *TLI, DominatorTree *DT, PostDominatorTree *PDT)
Definition: BranchProbabilityInfo.cpp:1249
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:455
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:450
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:1309
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:1352
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