LLVM  7.0.0svn
BranchProbabilityInfo.cpp
Go to the documentation of this file.
1 //===- BranchProbabilityInfo.cpp - Branch Probability Analysis ------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // Loops should be simplified before this analysis.
11 //
12 //===----------------------------------------------------------------------===//
13 
16 #include "llvm/ADT/SCCIterator.h"
17 #include "llvm/ADT/STLExtras.h"
18 #include "llvm/ADT/SmallVector.h"
19 #include "llvm/Analysis/LoopInfo.h"
21 #include "llvm/IR/Attributes.h"
22 #include "llvm/IR/BasicBlock.h"
23 #include "llvm/IR/CFG.h"
24 #include "llvm/IR/Constants.h"
25 #include "llvm/IR/Dominators.h"
26 #include "llvm/IR/Function.h"
27 #include "llvm/IR/InstrTypes.h"
28 #include "llvm/IR/Instruction.h"
29 #include "llvm/IR/Instructions.h"
30 #include "llvm/IR/LLVMContext.h"
31 #include "llvm/IR/Metadata.h"
32 #include "llvm/IR/PassManager.h"
33 #include "llvm/IR/Type.h"
34 #include "llvm/IR/Value.h"
35 #include "llvm/Pass.h"
37 #include "llvm/Support/Casting.h"
38 #include "llvm/Support/Debug.h"
40 #include <cassert>
41 #include <cstdint>
42 #include <iterator>
43 #include <utility>
44 
45 using namespace llvm;
46 
47 #define DEBUG_TYPE "branch-prob"
48 
50  "print-bpi", cl::init(false), cl::Hidden,
51  cl::desc("Print the branch probability info."));
52 
54  "print-bpi-func-name", cl::Hidden,
55  cl::desc("The option to specify the name of the function "
56  "whose branch probability info is printed."));
57 
59  "Branch Probability Analysis", false, true)
63  "Branch Probability Analysis", false, true)
64 
65 char BranchProbabilityInfoWrapperPass::ID = 0;
66 
67 // Weights are for internal use only. They are used by heuristics to help to
68 // estimate edges' probability. Example:
69 //
70 // Using "Loop Branch Heuristics" we predict weights of edges for the
71 // block BB2.
72 // ...
73 // |
74 // V
75 // BB1<-+
76 // | |
77 // | | (Weight = 124)
78 // V |
79 // BB2--+
80 // |
81 // | (Weight = 4)
82 // V
83 // BB3
84 //
85 // Probability of the edge BB2->BB1 = 124 / (124 + 4) = 0.96875
86 // Probability of the edge BB2->BB3 = 4 / (124 + 4) = 0.03125
89 // Unlikely edges within a loop are half as likely as other edges
91 
92 /// Unreachable-terminating branch taken probability.
93 ///
94 /// This is the probability for a branch being taken to a block that terminates
95 /// (eventually) in unreachable. These are predicted as unlikely as possible.
96 /// All reachable probability will equally share the remaining part.
98 
99 /// Weight for a branch taken going into a cold block.
100 ///
101 /// This is the weight for a branch taken toward a block marked
102 /// cold. A block is marked cold if it's postdominated by a
103 /// block containing a call to a cold function. Cold functions
104 /// are those marked with attribute 'cold'.
106 
107 /// Weight for a branch not-taken into a cold block.
108 ///
109 /// This is the weight for a branch not taken toward a block marked
110 /// cold.
112 
115 
118 
121 
122 /// Invoke-terminating normal branch taken weight
123 ///
124 /// This is the weight for branching to the normal destination of an invoke
125 /// instruction. We expect this to happen most of the time. Set the weight to an
126 /// absurdly high value so that nested loops subsume it.
127 static const uint32_t IH_TAKEN_WEIGHT = 1024 * 1024 - 1;
128 
129 /// Invoke-terminating normal branch not-taken weight.
130 ///
131 /// This is the weight for branching to the unwind destination of an invoke
132 /// instruction. This is essentially never taken.
134 
135 /// Add \p BB to PostDominatedByUnreachable set if applicable.
136 void
137 BranchProbabilityInfo::updatePostDominatedByUnreachable(const BasicBlock *BB) {
138  const TerminatorInst *TI = BB->getTerminator();
139  if (TI->getNumSuccessors() == 0) {
140  if (isa<UnreachableInst>(TI) ||
141  // If this block is terminated by a call to
142  // @llvm.experimental.deoptimize then treat it like an unreachable since
143  // the @llvm.experimental.deoptimize call is expected to practically
144  // never execute.
145  BB->getTerminatingDeoptimizeCall())
146  PostDominatedByUnreachable.insert(BB);
147  return;
148  }
149 
150  // If the terminator is an InvokeInst, check only the normal destination block
151  // as the unwind edge of InvokeInst is also very unlikely taken.
152  if (auto *II = dyn_cast<InvokeInst>(TI)) {
153  if (PostDominatedByUnreachable.count(II->getNormalDest()))
154  PostDominatedByUnreachable.insert(BB);
155  return;
156  }
157 
158  for (auto *I : successors(BB))
159  // If any of successor is not post dominated then BB is also not.
160  if (!PostDominatedByUnreachable.count(I))
161  return;
162 
163  PostDominatedByUnreachable.insert(BB);
164 }
165 
166 /// Add \p BB to PostDominatedByColdCall set if applicable.
167 void
168 BranchProbabilityInfo::updatePostDominatedByColdCall(const BasicBlock *BB) {
169  assert(!PostDominatedByColdCall.count(BB));
170  const TerminatorInst *TI = BB->getTerminator();
171  if (TI->getNumSuccessors() == 0)
172  return;
173 
174  // If all of successor are post dominated then BB is also done.
175  if (llvm::all_of(successors(BB), [&](const BasicBlock *SuccBB) {
176  return PostDominatedByColdCall.count(SuccBB);
177  })) {
178  PostDominatedByColdCall.insert(BB);
179  return;
180  }
181 
182  // If the terminator is an InvokeInst, check only the normal destination
183  // block as the unwind edge of InvokeInst is also very unlikely taken.
184  if (auto *II = dyn_cast<InvokeInst>(TI))
185  if (PostDominatedByColdCall.count(II->getNormalDest())) {
186  PostDominatedByColdCall.insert(BB);
187  return;
188  }
189 
190  // Otherwise, if the block itself contains a cold function, add it to the
191  // set of blocks post-dominated by a cold call.
192  for (auto &I : *BB)
193  if (const CallInst *CI = dyn_cast<CallInst>(&I))
194  if (CI->hasFnAttr(Attribute::Cold)) {
195  PostDominatedByColdCall.insert(BB);
196  return;
197  }
198 }
199 
200 /// Calculate edge weights for successors lead to unreachable.
201 ///
202 /// Predict that a successor which leads necessarily to an
203 /// unreachable-terminated block as extremely unlikely.
204 bool BranchProbabilityInfo::calcUnreachableHeuristics(const BasicBlock *BB) {
205  const TerminatorInst *TI = BB->getTerminator();
206  (void) TI;
207  assert(TI->getNumSuccessors() > 1 && "expected more than one successor!");
208  assert(!isa<InvokeInst>(TI) &&
209  "Invokes should have already been handled by calcInvokeHeuristics");
210 
211  SmallVector<unsigned, 4> UnreachableEdges;
212  SmallVector<unsigned, 4> ReachableEdges;
213 
214  for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I)
215  if (PostDominatedByUnreachable.count(*I))
216  UnreachableEdges.push_back(I.getSuccessorIndex());
217  else
218  ReachableEdges.push_back(I.getSuccessorIndex());
219 
220  // Skip probabilities if all were reachable.
221  if (UnreachableEdges.empty())
222  return false;
223 
224  if (ReachableEdges.empty()) {
225  BranchProbability Prob(1, UnreachableEdges.size());
226  for (unsigned SuccIdx : UnreachableEdges)
227  setEdgeProbability(BB, SuccIdx, Prob);
228  return true;
229  }
230 
231  auto UnreachableProb = UR_TAKEN_PROB;
232  auto ReachableProb =
233  (BranchProbability::getOne() - UR_TAKEN_PROB * UnreachableEdges.size()) /
234  ReachableEdges.size();
235 
236  for (unsigned SuccIdx : UnreachableEdges)
237  setEdgeProbability(BB, SuccIdx, UnreachableProb);
238  for (unsigned SuccIdx : ReachableEdges)
239  setEdgeProbability(BB, SuccIdx, ReachableProb);
240 
241  return true;
242 }
243 
244 // Propagate existing explicit probabilities from either profile data or
245 // 'expect' intrinsic processing. Examine metadata against unreachable
246 // heuristic. The probability of the edge coming to unreachable block is
247 // set to min of metadata and unreachable heuristic.
248 bool BranchProbabilityInfo::calcMetadataWeights(const BasicBlock *BB) {
249  const TerminatorInst *TI = BB->getTerminator();
250  assert(TI->getNumSuccessors() > 1 && "expected more than one successor!");
251  if (!(isa<BranchInst>(TI) || isa<SwitchInst>(TI) || isa<IndirectBrInst>(TI)))
252  return false;
253 
254  MDNode *WeightsNode = TI->getMetadata(LLVMContext::MD_prof);
255  if (!WeightsNode)
256  return false;
257 
258  // Check that the number of successors is manageable.
259  assert(TI->getNumSuccessors() < UINT32_MAX && "Too many successors");
260 
261  // Ensure there are weights for all of the successors. Note that the first
262  // operand to the metadata node is a name, not a weight.
263  if (WeightsNode->getNumOperands() != TI->getNumSuccessors() + 1)
264  return false;
265 
266  // Build up the final weights that will be used in a temporary buffer.
267  // Compute the sum of all weights to later decide whether they need to
268  // be scaled to fit in 32 bits.
269  uint64_t WeightSum = 0;
270  SmallVector<uint32_t, 2> Weights;
271  SmallVector<unsigned, 2> UnreachableIdxs;
272  SmallVector<unsigned, 2> ReachableIdxs;
273  Weights.reserve(TI->getNumSuccessors());
274  for (unsigned i = 1, e = WeightsNode->getNumOperands(); i != e; ++i) {
275  ConstantInt *Weight =
276  mdconst::dyn_extract<ConstantInt>(WeightsNode->getOperand(i));
277  if (!Weight)
278  return false;
279  assert(Weight->getValue().getActiveBits() <= 32 &&
280  "Too many bits for uint32_t");
281  Weights.push_back(Weight->getZExtValue());
282  WeightSum += Weights.back();
283  if (PostDominatedByUnreachable.count(TI->getSuccessor(i - 1)))
284  UnreachableIdxs.push_back(i - 1);
285  else
286  ReachableIdxs.push_back(i - 1);
287  }
288  assert(Weights.size() == TI->getNumSuccessors() && "Checked above");
289 
290  // If the sum of weights does not fit in 32 bits, scale every weight down
291  // accordingly.
292  uint64_t ScalingFactor =
293  (WeightSum > UINT32_MAX) ? WeightSum / UINT32_MAX + 1 : 1;
294 
295  if (ScalingFactor > 1) {
296  WeightSum = 0;
297  for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) {
298  Weights[i] /= ScalingFactor;
299  WeightSum += Weights[i];
300  }
301  }
302  assert(WeightSum <= UINT32_MAX &&
303  "Expected weights to scale down to 32 bits");
304 
305  if (WeightSum == 0 || ReachableIdxs.size() == 0) {
306  for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
307  Weights[i] = 1;
308  WeightSum = TI->getNumSuccessors();
309  }
310 
311  // Set the probability.
313  for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
314  BP.push_back({ Weights[i], static_cast<uint32_t>(WeightSum) });
315 
316  // Examine the metadata against unreachable heuristic.
317  // If the unreachable heuristic is more strong then we use it for this edge.
318  if (UnreachableIdxs.size() > 0 && ReachableIdxs.size() > 0) {
319  auto ToDistribute = BranchProbability::getZero();
320  auto UnreachableProb = UR_TAKEN_PROB;
321  for (auto i : UnreachableIdxs)
322  if (UnreachableProb < BP[i]) {
323  ToDistribute += BP[i] - UnreachableProb;
324  BP[i] = UnreachableProb;
325  }
326 
327  // If we modified the probability of some edges then we must distribute
328  // the difference between reachable blocks.
329  if (ToDistribute > BranchProbability::getZero()) {
330  BranchProbability PerEdge = ToDistribute / ReachableIdxs.size();
331  for (auto i : ReachableIdxs)
332  BP[i] += PerEdge;
333  }
334  }
335 
336  for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
337  setEdgeProbability(BB, i, BP[i]);
338 
339  return true;
340 }
341 
342 /// Calculate edge weights for edges leading to cold blocks.
343 ///
344 /// A cold block is one post-dominated by a block with a call to a
345 /// cold function. Those edges are unlikely to be taken, so we give
346 /// them relatively low weight.
347 ///
348 /// Return true if we could compute the weights for cold edges.
349 /// Return false, otherwise.
350 bool BranchProbabilityInfo::calcColdCallHeuristics(const BasicBlock *BB) {
351  const TerminatorInst *TI = BB->getTerminator();
352  (void) TI;
353  assert(TI->getNumSuccessors() > 1 && "expected more than one successor!");
354  assert(!isa<InvokeInst>(TI) &&
355  "Invokes should have already been handled by calcInvokeHeuristics");
356 
357  // Determine which successors are post-dominated by a cold block.
358  SmallVector<unsigned, 4> ColdEdges;
359  SmallVector<unsigned, 4> NormalEdges;
360  for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I)
361  if (PostDominatedByColdCall.count(*I))
362  ColdEdges.push_back(I.getSuccessorIndex());
363  else
364  NormalEdges.push_back(I.getSuccessorIndex());
365 
366  // Skip probabilities if no cold edges.
367  if (ColdEdges.empty())
368  return false;
369 
370  if (NormalEdges.empty()) {
371  BranchProbability Prob(1, ColdEdges.size());
372  for (unsigned SuccIdx : ColdEdges)
373  setEdgeProbability(BB, SuccIdx, Prob);
374  return true;
375  }
376 
379  (CC_TAKEN_WEIGHT + CC_NONTAKEN_WEIGHT) * uint64_t(ColdEdges.size()));
380  auto NormalProb = BranchProbability::getBranchProbability(
382  (CC_TAKEN_WEIGHT + CC_NONTAKEN_WEIGHT) * uint64_t(NormalEdges.size()));
383 
384  for (unsigned SuccIdx : ColdEdges)
385  setEdgeProbability(BB, SuccIdx, ColdProb);
386  for (unsigned SuccIdx : NormalEdges)
387  setEdgeProbability(BB, SuccIdx, NormalProb);
388 
389  return true;
390 }
391 
392 // Calculate Edge Weights using "Pointer Heuristics". Predict a comparison
393 // between two pointer or pointer and NULL will fail.
394 bool BranchProbabilityInfo::calcPointerHeuristics(const BasicBlock *BB) {
395  const BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
396  if (!BI || !BI->isConditional())
397  return false;
398 
399  Value *Cond = BI->getCondition();
400  ICmpInst *CI = dyn_cast<ICmpInst>(Cond);
401  if (!CI || !CI->isEquality())
402  return false;
403 
404  Value *LHS = CI->getOperand(0);
405 
406  if (!LHS->getType()->isPointerTy())
407  return false;
408 
409  assert(CI->getOperand(1)->getType()->isPointerTy());
410 
411  // p != 0 -> isProb = true
412  // p == 0 -> isProb = false
413  // p != q -> isProb = true
414  // p == q -> isProb = false;
415  unsigned TakenIdx = 0, NonTakenIdx = 1;
416  bool isProb = CI->getPredicate() == ICmpInst::ICMP_NE;
417  if (!isProb)
418  std::swap(TakenIdx, NonTakenIdx);
419 
422  setEdgeProbability(BB, TakenIdx, TakenProb);
423  setEdgeProbability(BB, NonTakenIdx, TakenProb.getCompl());
424  return true;
425 }
426 
427 static int getSCCNum(const BasicBlock *BB,
428  const BranchProbabilityInfo::SccInfo &SccI) {
429  auto SccIt = SccI.SccNums.find(BB);
430  if (SccIt == SccI.SccNums.end())
431  return -1;
432  return SccIt->second;
433 }
434 
435 // Consider any block that is an entry point to the SCC as a header.
436 static bool isSCCHeader(const BasicBlock *BB, int SccNum,
438  assert(getSCCNum(BB, SccI) == SccNum);
439 
440  // Lazily compute the set of headers for a given SCC and cache the results
441  // in the SccHeaderMap.
442  if (SccI.SccHeaders.size() <= static_cast<unsigned>(SccNum))
443  SccI.SccHeaders.resize(SccNum + 1);
444  auto &HeaderMap = SccI.SccHeaders[SccNum];
445  bool Inserted;
447  std::tie(HeaderMapIt, Inserted) = HeaderMap.insert(std::make_pair(BB, false));
448  if (Inserted) {
449  bool IsHeader = llvm::any_of(make_range(pred_begin(BB), pred_end(BB)),
450  [&](const BasicBlock *Pred) {
451  return getSCCNum(Pred, SccI) != SccNum;
452  });
453  HeaderMapIt->second = IsHeader;
454  return IsHeader;
455  } else
456  return HeaderMapIt->second;
457 }
458 
459 // Compute the unlikely successors to the block BB in the loop L, specifically
460 // those that are unlikely because this is a loop, and add them to the
461 // UnlikelyBlocks set.
462 static void
464  SmallPtrSetImpl<const BasicBlock*> &UnlikelyBlocks) {
465  // Sometimes in a loop we have a branch whose condition is made false by
466  // taking it. This is typically something like
467  // int n = 0;
468  // while (...) {
469  // if (++n >= MAX) {
470  // n = 0;
471  // }
472  // }
473  // In this sort of situation taking the branch means that at the very least it
474  // won't be taken again in the next iteration of the loop, so we should
475  // consider it less likely than a typical branch.
476  //
477  // We detect this by looking back through the graph of PHI nodes that sets the
478  // value that the condition depends on, and seeing if we can reach a successor
479  // block which can be determined to make the condition false.
480  //
481  // FIXME: We currently consider unlikely blocks to be half as likely as other
482  // blocks, but if we consider the example above the likelyhood is actually
483  // 1/MAX. We could therefore be more precise in how unlikely we consider
484  // blocks to be, but it would require more careful examination of the form
485  // of the comparison expression.
486  const BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
487  if (!BI || !BI->isConditional())
488  return;
489 
490  // Check if the branch is based on an instruction compared with a constant
491  CmpInst *CI = dyn_cast<CmpInst>(BI->getCondition());
492  if (!CI || !isa<Instruction>(CI->getOperand(0)) ||
493  !isa<Constant>(CI->getOperand(1)))
494  return;
495 
496  // Either the instruction must be a PHI, or a chain of operations involving
497  // constants that ends in a PHI which we can then collapse into a single value
498  // if the PHI value is known.
499  Instruction *CmpLHS = dyn_cast<Instruction>(CI->getOperand(0));
500  PHINode *CmpPHI = dyn_cast<PHINode>(CmpLHS);
501  Constant *CmpConst = dyn_cast<Constant>(CI->getOperand(1));
502  // Collect the instructions until we hit a PHI
504  while (!CmpPHI && CmpLHS && isa<BinaryOperator>(CmpLHS) &&
505  isa<Constant>(CmpLHS->getOperand(1))) {
506  // Stop if the chain extends outside of the loop
507  if (!L->contains(CmpLHS))
508  return;
509  InstChain.push_back(cast<BinaryOperator>(CmpLHS));
510  CmpLHS = dyn_cast<Instruction>(CmpLHS->getOperand(0));
511  if (CmpLHS)
512  CmpPHI = dyn_cast<PHINode>(CmpLHS);
513  }
514  if (!CmpPHI || !L->contains(CmpPHI))
515  return;
516 
517  // Trace the phi node to find all values that come from successors of BB
518  SmallPtrSet<PHINode*, 8> VisitedInsts;
519  SmallVector<PHINode*, 8> WorkList;
520  WorkList.push_back(CmpPHI);
521  VisitedInsts.insert(CmpPHI);
522  while (!WorkList.empty()) {
523  PHINode *P = WorkList.back();
524  WorkList.pop_back();
525  for (BasicBlock *B : P->blocks()) {
526  // Skip blocks that aren't part of the loop
527  if (!L->contains(B))
528  continue;
530  // If the source is a PHI add it to the work list if we haven't
531  // already visited it.
532  if (PHINode *PN = dyn_cast<PHINode>(V)) {
533  if (VisitedInsts.insert(PN).second)
534  WorkList.push_back(PN);
535  continue;
536  }
537  // If this incoming value is a constant and B is a successor of BB, then
538  // we can constant-evaluate the compare to see if it makes the branch be
539  // taken or not.
540  Constant *CmpLHSConst = dyn_cast<Constant>(V);
541  if (!CmpLHSConst ||
542  std::find(succ_begin(BB), succ_end(BB), B) == succ_end(BB))
543  continue;
544  // First collapse InstChain
545  for (Instruction *I : llvm::reverse(InstChain)) {
546  CmpLHSConst = ConstantExpr::get(I->getOpcode(), CmpLHSConst,
547  cast<Constant>(I->getOperand(1)), true);
548  if (!CmpLHSConst)
549  break;
550  }
551  if (!CmpLHSConst)
552  continue;
553  // Now constant-evaluate the compare
555  CmpLHSConst, CmpConst, true);
556  // If the result means we don't branch to the block then that block is
557  // unlikely.
558  if (Result &&
559  ((Result->isZeroValue() && B == BI->getSuccessor(0)) ||
560  (Result->isOneValue() && B == BI->getSuccessor(1))))
561  UnlikelyBlocks.insert(B);
562  }
563  }
564 }
565 
566 // Calculate Edge Weights using "Loop Branch Heuristics". Predict backedges
567 // as taken, exiting edges as not-taken.
568 bool BranchProbabilityInfo::calcLoopBranchHeuristics(const BasicBlock *BB,
569  const LoopInfo &LI,
570  SccInfo &SccI) {
571  int SccNum;
572  Loop *L = LI.getLoopFor(BB);
573  if (!L) {
574  SccNum = getSCCNum(BB, SccI);
575  if (SccNum < 0)
576  return false;
577  }
578 
579  SmallPtrSet<const BasicBlock*, 8> UnlikelyBlocks;
580  if (L)
581  computeUnlikelySuccessors(BB, L, UnlikelyBlocks);
582 
583  SmallVector<unsigned, 8> BackEdges;
584  SmallVector<unsigned, 8> ExitingEdges;
585  SmallVector<unsigned, 8> InEdges; // Edges from header to the loop.
586  SmallVector<unsigned, 8> UnlikelyEdges;
587 
588  for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
589  // Use LoopInfo if we have it, otherwise fall-back to SCC info to catch
590  // irreducible loops.
591  if (L) {
592  if (UnlikelyBlocks.count(*I) != 0)
593  UnlikelyEdges.push_back(I.getSuccessorIndex());
594  else if (!L->contains(*I))
595  ExitingEdges.push_back(I.getSuccessorIndex());
596  else if (L->getHeader() == *I)
597  BackEdges.push_back(I.getSuccessorIndex());
598  else
599  InEdges.push_back(I.getSuccessorIndex());
600  } else {
601  if (getSCCNum(*I, SccI) != SccNum)
602  ExitingEdges.push_back(I.getSuccessorIndex());
603  else if (isSCCHeader(*I, SccNum, SccI))
604  BackEdges.push_back(I.getSuccessorIndex());
605  else
606  InEdges.push_back(I.getSuccessorIndex());
607  }
608  }
609 
610  if (BackEdges.empty() && ExitingEdges.empty() && UnlikelyEdges.empty())
611  return false;
612 
613  // Collect the sum of probabilities of back-edges/in-edges/exiting-edges, and
614  // normalize them so that they sum up to one.
615  unsigned Denom = (BackEdges.empty() ? 0 : LBH_TAKEN_WEIGHT) +
616  (InEdges.empty() ? 0 : LBH_TAKEN_WEIGHT) +
617  (UnlikelyEdges.empty() ? 0 : LBH_UNLIKELY_WEIGHT) +
618  (ExitingEdges.empty() ? 0 : LBH_NONTAKEN_WEIGHT);
619 
620  if (uint32_t numBackEdges = BackEdges.size()) {
622  auto Prob = TakenProb / numBackEdges;
623  for (unsigned SuccIdx : BackEdges)
624  setEdgeProbability(BB, SuccIdx, Prob);
625  }
626 
627  if (uint32_t numInEdges = InEdges.size()) {
629  auto Prob = TakenProb / numInEdges;
630  for (unsigned SuccIdx : InEdges)
631  setEdgeProbability(BB, SuccIdx, Prob);
632  }
633 
634  if (uint32_t numExitingEdges = ExitingEdges.size()) {
636  Denom);
637  auto Prob = NotTakenProb / numExitingEdges;
638  for (unsigned SuccIdx : ExitingEdges)
639  setEdgeProbability(BB, SuccIdx, Prob);
640  }
641 
642  if (uint32_t numUnlikelyEdges = UnlikelyEdges.size()) {
644  Denom);
645  auto Prob = UnlikelyProb / numUnlikelyEdges;
646  for (unsigned SuccIdx : UnlikelyEdges)
647  setEdgeProbability(BB, SuccIdx, Prob);
648  }
649 
650  return true;
651 }
652 
653 bool BranchProbabilityInfo::calcZeroHeuristics(const BasicBlock *BB,
654  const TargetLibraryInfo *TLI) {
655  const BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
656  if (!BI || !BI->isConditional())
657  return false;
658 
659  Value *Cond = BI->getCondition();
660  ICmpInst *CI = dyn_cast<ICmpInst>(Cond);
661  if (!CI)
662  return false;
663 
664  Value *RHS = CI->getOperand(1);
665  ConstantInt *CV = dyn_cast<ConstantInt>(RHS);
666  if (!CV)
667  return false;
668 
669  // If the LHS is the result of AND'ing a value with a single bit bitmask,
670  // we don't have information about probabilities.
671  if (Instruction *LHS = dyn_cast<Instruction>(CI->getOperand(0)))
672  if (LHS->getOpcode() == Instruction::And)
673  if (ConstantInt *AndRHS = dyn_cast<ConstantInt>(LHS->getOperand(1)))
674  if (AndRHS->getValue().isPowerOf2())
675  return false;
676 
677  // Check if the LHS is the return value of a library function
678  LibFunc Func = NumLibFuncs;
679  if (TLI)
680  if (CallInst *Call = dyn_cast<CallInst>(CI->getOperand(0)))
681  if (Function *CalledFn = Call->getCalledFunction())
682  TLI->getLibFunc(*CalledFn, Func);
683 
684  bool isProb;
685  if (Func == LibFunc_strcasecmp ||
686  Func == LibFunc_strcmp ||
687  Func == LibFunc_strncasecmp ||
688  Func == LibFunc_strncmp ||
689  Func == LibFunc_memcmp) {
690  // strcmp and similar functions return zero, negative, or positive, if the
691  // first string is equal, less, or greater than the second. We consider it
692  // likely that the strings are not equal, so a comparison with zero is
693  // probably false, but also a comparison with any other number is also
694  // probably false given that what exactly is returned for nonzero values is
695  // not specified. Any kind of comparison other than equality we know
696  // nothing about.
697  switch (CI->getPredicate()) {
698  case CmpInst::ICMP_EQ:
699  isProb = false;
700  break;
701  case CmpInst::ICMP_NE:
702  isProb = true;
703  break;
704  default:
705  return false;
706  }
707  } else if (CV->isZero()) {
708  switch (CI->getPredicate()) {
709  case CmpInst::ICMP_EQ:
710  // X == 0 -> Unlikely
711  isProb = false;
712  break;
713  case CmpInst::ICMP_NE:
714  // X != 0 -> Likely
715  isProb = true;
716  break;
717  case CmpInst::ICMP_SLT:
718  // X < 0 -> Unlikely
719  isProb = false;
720  break;
721  case CmpInst::ICMP_SGT:
722  // X > 0 -> Likely
723  isProb = true;
724  break;
725  default:
726  return false;
727  }
728  } else if (CV->isOne() && CI->getPredicate() == CmpInst::ICMP_SLT) {
729  // InstCombine canonicalizes X <= 0 into X < 1.
730  // X <= 0 -> Unlikely
731  isProb = false;
732  } else if (CV->isMinusOne()) {
733  switch (CI->getPredicate()) {
734  case CmpInst::ICMP_EQ:
735  // X == -1 -> Unlikely
736  isProb = false;
737  break;
738  case CmpInst::ICMP_NE:
739  // X != -1 -> Likely
740  isProb = true;
741  break;
742  case CmpInst::ICMP_SGT:
743  // InstCombine canonicalizes X >= 0 into X > -1.
744  // X >= 0 -> Likely
745  isProb = true;
746  break;
747  default:
748  return false;
749  }
750  } else {
751  return false;
752  }
753 
754  unsigned TakenIdx = 0, NonTakenIdx = 1;
755 
756  if (!isProb)
757  std::swap(TakenIdx, NonTakenIdx);
758 
761  setEdgeProbability(BB, TakenIdx, TakenProb);
762  setEdgeProbability(BB, NonTakenIdx, TakenProb.getCompl());
763  return true;
764 }
765 
766 bool BranchProbabilityInfo::calcFloatingPointHeuristics(const BasicBlock *BB) {
767  const BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
768  if (!BI || !BI->isConditional())
769  return false;
770 
771  Value *Cond = BI->getCondition();
772  FCmpInst *FCmp = dyn_cast<FCmpInst>(Cond);
773  if (!FCmp)
774  return false;
775 
776  bool isProb;
777  if (FCmp->isEquality()) {
778  // f1 == f2 -> Unlikely
779  // f1 != f2 -> Likely
780  isProb = !FCmp->isTrueWhenEqual();
781  } else if (FCmp->getPredicate() == FCmpInst::FCMP_ORD) {
782  // !isnan -> Likely
783  isProb = true;
784  } else if (FCmp->getPredicate() == FCmpInst::FCMP_UNO) {
785  // isnan -> Unlikely
786  isProb = false;
787  } else {
788  return false;
789  }
790 
791  unsigned TakenIdx = 0, NonTakenIdx = 1;
792 
793  if (!isProb)
794  std::swap(TakenIdx, NonTakenIdx);
795 
798  setEdgeProbability(BB, TakenIdx, TakenProb);
799  setEdgeProbability(BB, NonTakenIdx, TakenProb.getCompl());
800  return true;
801 }
802 
803 bool BranchProbabilityInfo::calcInvokeHeuristics(const BasicBlock *BB) {
804  const InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator());
805  if (!II)
806  return false;
807 
810  setEdgeProbability(BB, 0 /*Index for Normal*/, TakenProb);
811  setEdgeProbability(BB, 1 /*Index for Unwind*/, TakenProb.getCompl());
812  return true;
813 }
814 
816  Probs.clear();
817 }
818 
820  OS << "---- Branch Probabilities ----\n";
821  // We print the probabilities from the last function the analysis ran over,
822  // or the function it is currently running over.
823  assert(LastF && "Cannot print prior to running over a function");
824  for (const auto &BI : *LastF) {
825  for (succ_const_iterator SI = succ_begin(&BI), SE = succ_end(&BI); SI != SE;
826  ++SI) {
827  printEdgeProbability(OS << " ", &BI, *SI);
828  }
829  }
830 }
831 
833 isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const {
834  // Hot probability is at least 4/5 = 80%
835  // FIXME: Compare against a static "hot" BranchProbability.
836  return getEdgeProbability(Src, Dst) > BranchProbability(4, 5);
837 }
838 
839 const BasicBlock *
841  auto MaxProb = BranchProbability::getZero();
842  const BasicBlock *MaxSucc = nullptr;
843 
844  for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
845  const BasicBlock *Succ = *I;
846  auto Prob = getEdgeProbability(BB, Succ);
847  if (Prob > MaxProb) {
848  MaxProb = Prob;
849  MaxSucc = Succ;
850  }
851  }
852 
853  // Hot probability is at least 4/5 = 80%
854  if (MaxProb > BranchProbability(4, 5))
855  return MaxSucc;
856 
857  return nullptr;
858 }
859 
860 /// Get the raw edge probability for the edge. If can't find it, return a
861 /// default probability 1/N where N is the number of successors. Here an edge is
862 /// specified using PredBlock and an
863 /// index to the successors.
866  unsigned IndexInSuccessors) const {
867  auto I = Probs.find(std::make_pair(Src, IndexInSuccessors));
868 
869  if (I != Probs.end())
870  return I->second;
871 
872  return {1, static_cast<uint32_t>(succ_size(Src))};
873 }
874 
877  succ_const_iterator Dst) const {
878  return getEdgeProbability(Src, Dst.getSuccessorIndex());
879 }
880 
881 /// Get the raw edge probability calculated for the block pair. This returns the
882 /// sum of all raw edge probabilities from Src to Dst.
885  const BasicBlock *Dst) const {
886  auto Prob = BranchProbability::getZero();
887  bool FoundProb = false;
888  for (succ_const_iterator I = succ_begin(Src), E = succ_end(Src); I != E; ++I)
889  if (*I == Dst) {
890  auto MapI = Probs.find(std::make_pair(Src, I.getSuccessorIndex()));
891  if (MapI != Probs.end()) {
892  FoundProb = true;
893  Prob += MapI->second;
894  }
895  }
896  uint32_t succ_num = std::distance(succ_begin(Src), succ_end(Src));
897  return FoundProb ? Prob : BranchProbability(1, succ_num);
898 }
899 
900 /// Set the edge probability for a given edge specified by PredBlock and an
901 /// index to the successors.
903  unsigned IndexInSuccessors,
904  BranchProbability Prob) {
905  Probs[std::make_pair(Src, IndexInSuccessors)] = Prob;
906  Handles.insert(BasicBlockCallbackVH(Src, this));
907  LLVM_DEBUG(dbgs() << "set edge " << Src->getName() << " -> "
908  << IndexInSuccessors << " successor probability to " << Prob
909  << "\n");
910 }
911 
912 raw_ostream &
914  const BasicBlock *Src,
915  const BasicBlock *Dst) const {
916  const BranchProbability Prob = getEdgeProbability(Src, Dst);
917  OS << "edge " << Src->getName() << " -> " << Dst->getName()
918  << " probability is " << Prob
919  << (isEdgeHot(Src, Dst) ? " [HOT edge]\n" : "\n");
920 
921  return OS;
922 }
923 
925  for (auto I = Probs.begin(), E = Probs.end(); I != E; ++I) {
926  auto Key = I->first;
927  if (Key.first == BB)
928  Probs.erase(Key);
929  }
930 }
931 
933  const TargetLibraryInfo *TLI) {
934  LLVM_DEBUG(dbgs() << "---- Branch Probability Info : " << F.getName()
935  << " ----\n\n");
936  LastF = &F; // Store the last function we ran on for printing.
937  assert(PostDominatedByUnreachable.empty());
938  assert(PostDominatedByColdCall.empty());
939 
940  // Record SCC numbers of blocks in the CFG to identify irreducible loops.
941  // FIXME: We could only calculate this if the CFG is known to be irreducible
942  // (perhaps cache this info in LoopInfo if we can easily calculate it there?).
943  int SccNum = 0;
944  SccInfo SccI;
945  for (scc_iterator<const Function *> It = scc_begin(&F); !It.isAtEnd();
946  ++It, ++SccNum) {
947  // Ignore single-block SCCs since they either aren't loops or LoopInfo will
948  // catch them.
949  const std::vector<const BasicBlock *> &Scc = *It;
950  if (Scc.size() == 1)
951  continue;
952 
953  LLVM_DEBUG(dbgs() << "BPI: SCC " << SccNum << ":");
954  for (auto *BB : Scc) {
955  LLVM_DEBUG(dbgs() << " " << BB->getName());
956  SccI.SccNums[BB] = SccNum;
957  }
958  LLVM_DEBUG(dbgs() << "\n");
959  }
960 
961  // Walk the basic blocks in post-order so that we can build up state about
962  // the successors of a block iteratively.
963  for (auto BB : post_order(&F.getEntryBlock())) {
964  LLVM_DEBUG(dbgs() << "Computing probabilities for " << BB->getName()
965  << "\n");
966  updatePostDominatedByUnreachable(BB);
967  updatePostDominatedByColdCall(BB);
968  // If there is no at least two successors, no sense to set probability.
969  if (BB->getTerminator()->getNumSuccessors() < 2)
970  continue;
971  if (calcMetadataWeights(BB))
972  continue;
973  if (calcInvokeHeuristics(BB))
974  continue;
975  if (calcUnreachableHeuristics(BB))
976  continue;
977  if (calcColdCallHeuristics(BB))
978  continue;
979  if (calcLoopBranchHeuristics(BB, LI, SccI))
980  continue;
981  if (calcPointerHeuristics(BB))
982  continue;
983  if (calcZeroHeuristics(BB, TLI))
984  continue;
985  if (calcFloatingPointHeuristics(BB))
986  continue;
987  }
988 
989  PostDominatedByUnreachable.clear();
990  PostDominatedByColdCall.clear();
991 
992  if (PrintBranchProb &&
993  (PrintBranchProbFuncName.empty() ||
995  print(dbgs());
996  }
997 }
998 
1000  AnalysisUsage &AU) const {
1001  // We require DT so it's available when LI is available. The LI updating code
1002  // asserts that DT is also present so if we don't make sure that we have DT
1003  // here, that assert will trigger.
1007  AU.setPreservesAll();
1008 }
1009 
1011  const LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
1012  const TargetLibraryInfo &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
1013  BPI.calculate(F, LI, &TLI);
1014  return false;
1015 }
1016 
1018 
1020  const Module *) const {
1021  BPI.print(OS);
1022 }
1023 
1024 AnalysisKey BranchProbabilityAnalysis::Key;
1029  return BPI;
1030 }
1031 
1034  OS << "Printing analysis results of BPI for function "
1035  << "'" << F.getName() << "':"
1036  << "\n";
1038  return PreservedAnalyses::all();
1039 }
void push_back(const T &Elt)
Definition: SmallVector.h:213
static bool isEquality(Predicate Pred)
This builds on the llvm/ADT/GraphTraits.h file to find the strongly connected components (SCCs) of a ...
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:875
unsigned getSuccessorIndex() const
This is used to interface between code that wants to operate on terminator instructions directly...
Definition: InstrTypes.h:162
BranchProbability getCompl() const
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:687
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:63
BasicBlock * getSuccessor(unsigned idx) const
Return the specified successor.
LLVM_ATTRIBUTE_ALWAYS_INLINE size_type size() const
Definition: SmallVector.h:137
void calculate(const Function &F, const LoopInfo &LI, const TargetLibraryInfo *TLI=nullptr)
unsigned succ_size(const BasicBlock *BB)
Definition: CFG.h:146
This class represents a function call, abstracting a target machine&#39;s calling convention.
This file contains the declarations for metadata subclasses.
static const uint32_t FPH_TAKEN_WEIGHT
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:908
BasicBlock * getSuccessor(unsigned i) const
static bool isEquality(Predicate P)
Return true if this predicate is either EQ or NE.
Metadata node.
Definition: Metadata.h:862
F(f)
const MDOperand & getOperand(unsigned I) const
Definition: Metadata.h:1067
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass...
static Constant * getCompare(unsigned short pred, Constant *C1, Constant *C2, bool OnlyIfReduced=false)
Return an ICmp or FCmp comparison operator constant expression.
Definition: Constants.cpp:1903
Value * getCondition() const
static BranchProbability getOne()
void reserve(size_type N)
Definition: SmallVector.h:377
branch prob
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
1 0 0 0 True if unordered: isnan(X) | isnan(Y)
Definition: InstrTypes.h:895
const BasicBlock * getHotSucc(const BasicBlock *BB) const
Retrieve the hot successor of a block if one exists.
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:684
INITIALIZE_PASS_BEGIN(BranchProbabilityInfoWrapperPass, "branch-prob", "Branch Probability Analysis", false, true) INITIALIZE_PASS_END(BranchProbabilityInfoWrapperPass
static int getSCCNum(const BasicBlock *BB, const BranchProbabilityInfo::SccInfo &SccI)
This file contains the simple types necessary to represent the attributes associated with functions a...
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:939
BlockT * getHeader() const
Definition: LoopInfo.h:100
Interval::succ_iterator succ_begin(Interval *I)
succ_begin/succ_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:103
scc_iterator< T > scc_begin(const T &G)
Construct the begin iterator for a deduced graph type T.
Definition: SCCIterator.h:226
Analysis pass which computes BranchProbabilityInfo.
auto reverse(ContainerTy &&C, typename std::enable_if< has_rbegin< ContainerTy >::value >::type *=nullptr) -> decltype(make_range(C.rbegin(), C.rend()))
Definition: STLExtras.h:237
unsigned getActiveBits() const
Compute the number of active bits in the value.
Definition: APInt.h:1526
bool isOne() const
This is just a convenience method to make client code smaller for a common case.
Definition: Constants.h:201
static Constant * get(unsigned Opcode, Constant *C1, Constant *C2, unsigned Flags=0, Type *OnlyIfReducedTy=nullptr)
get - Return a binary or shift operator constant expression, folding if possible. ...
Definition: Constants.cpp:1783
Key
PAL metadata keys.
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
This instruction compares its operands according to the predicate given to the constructor.
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
Definition: Instruction.h:200
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:138
bool isMinusOne() const
This function will return true iff every bit in this constant is set to true.
Definition: Constants.h:209
Legacy analysis pass which computes BranchProbabilityInfo.
Value * getOperand(unsigned i) const
Definition: User.h:170
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:106
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:146
bool isZeroValue() const
Return true if the value is negative zero or null value.
Definition: Constants.cpp:65
const BasicBlock & getEntryBlock() const
Definition: Function.h:626
#define P(N)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:410
uint64_t getZExtValue() const
Return the constant as a 64-bit unsigned integer value after it has been zero extended as appropriate...
Definition: Constants.h:149
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
Subclasses of this class are all able to terminate a basic block.
Definition: InstrTypes.h:55
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
static const uint32_t IH_NONTAKEN_WEIGHT
Invoke-terminating normal branch not-taken weight.
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
Conditional or Unconditional Branch instruction.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This is an important base class in LLVM.
Definition: Constant.h:42
Value * getIncomingValueForBlock(const BasicBlock *BB) const
This file contains the declarations for the subclasses of Constant, which represent the different fla...
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:224
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:371
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:113
static const uint32_t CC_TAKEN_WEIGHT
Weight for a branch taken going into a cold block.
void eraseBlock(const BasicBlock *BB)
Forget analysis results for the given basic block.
Represent the analysis usage information of a pass.
bool any_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:915
static void computeUnlikelySuccessors(const BasicBlock *BB, Loop *L, SmallPtrSetImpl< const BasicBlock *> &UnlikelyBlocks)
This instruction compares its operands according to the predicate given to the constructor.
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:116
0 1 1 1 True if ordered (no nans)
Definition: InstrTypes.h:894
iterator_range< po_iterator< T > > post_order(const T &G)
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:382
iterator_range< block_iterator > blocks()
static const uint32_t ZH_NONTAKEN_WEIGHT
BranchProbabilityInfo run(Function &F, FunctionAnalysisManager &AM)
Run the analysis pass over a function and produce BPI.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:159
auto find(R &&Range, const T &Val) -> decltype(adl_begin(Range))
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:929
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
signed greater than
Definition: InstrTypes.h:912
BranchProbability getEdgeProbability(const BasicBlock *Src, unsigned IndexInSuccessors) const
Get an edge&#39;s probability, relative to other out-edges of the Src.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:110
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:418
This is the shared class of boolean and integer constants.
Definition: Constants.h:84
static bool isSCCHeader(const BasicBlock *BB, int SccNum, BranchProbabilityInfo::SccInfo &SccI)
Provides information about what library functions are available for the current target.
static BranchProbability getBranchProbability(uint64_t Numerator, uint64_t Denominator)
signed less than
Definition: InstrTypes.h:914
void setEdgeProbability(const BasicBlock *Src, unsigned IndexInSuccessors, BranchProbability Prob)
Set the raw edge probability for the given edge.
bool isConditional() const
branch Branch Probability Analysis
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:133
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:924
bool isTrueWhenEqual() const
This is just a convenience.
Definition: InstrTypes.h:1079
void print(raw_ostream &OS) const
static const uint32_t FPH_NONTAKEN_WEIGHT
void setPreservesAll()
Set by analyses that do not transform their input at all.
static const BranchProbability UR_TAKEN_PROB
Unreachable-terminating branch taken probability.
bool getLibFunc(StringRef funcName, LibFunc &F) const
Searches for a particular function name.
LLVM_NODISCARD LLVM_ATTRIBUTE_ALWAYS_INLINE bool equals(StringRef RHS) const
equals - Check for string equality, this is more efficient than compare() when the relative ordering ...
Definition: StringRef.h:169
static const uint32_t IH_TAKEN_WEIGHT
Invoke-terminating normal branch taken weight.
Basic Alias true
Predicate getPredicate() const
Return the predicate for this instruction.
Definition: InstrTypes.h:959
Analysis providing branch probability information.
static const uint32_t LBH_UNLIKELY_WEIGHT
static const uint32_t PH_NONTAKEN_WEIGHT
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:62
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:459
static const uint32_t LBH_NONTAKEN_WEIGHT
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:224
#define I(x, y, z)
Definition: MD5.cpp:58
static const uint32_t LBH_TAKEN_WEIGHT
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
iterator end()
Definition: DenseMap.h:79
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
Definition: Constants.h:193
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:323
Analysis pass providing the TargetLibraryInfo.
bool isOneValue() const
Returns true if the value is one.
Definition: Constants.cpp:126
static const uint32_t CC_NONTAKEN_WEIGHT
Weight for a branch not-taken into a cold block.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
unsigned getNumSuccessors() const
Return the number of successors that this terminator has.
aarch64 promote const
LLVM Value Representation.
Definition: Value.h:73
succ_range successors(BasicBlock *BB)
Definition: CFG.h:149
bool isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const
Test if an edge is hot relative to other out-edges of the Src.
static const uint32_t ZH_TAKEN_WEIGHT
static const uint32_t PH_TAKEN_WEIGHT
raw_ostream & printEdgeProbability(raw_ostream &OS, const BasicBlock *Src, const BasicBlock *Dst) const
Print an edge&#39;s probability.
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:46
Invoke instruction.
The legacy pass manager&#39;s analysis pass to compute loop information.
Definition: LoopInfo.h:964
A container for analyses that lazily runs them and caches their results.
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:254
static BranchProbability getZero()
cl::opt< std::string > PrintBranchProbFuncName("print-bpi-func-name", cl::Hidden, cl::desc("The option to specify the name of the function " "whose branch probability info is printed."))
const TerminatorInst * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:138
This header defines various interfaces for pass management in LLVM.
unsigned getNumOperands() const
Return number of MDNode operands.
Definition: Metadata.h:1073
#define LLVM_DEBUG(X)
Definition: Debug.h:119
void print(raw_ostream &OS, const Module *M=nullptr) const override
print - Print out the internal state of the pass.
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:70
static cl::opt< bool > PrintBranchProb("print-bpi", cl::init(false), cl::Hidden, cl::desc("Print the branch probability info."))
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Enumerate the SCCs of a directed graph in reverse topological order of the SCC DAG.
Definition: SCCIterator.h:43