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
14#include "llvm/Analysis/BranchProbabilityInfo.h"
15#include "llvm/ADT/PostOrderIterator.h"
16#include "llvm/Analysis/LoopInfo.h"
17#include "llvm/IR/Constants.h"
18#include "llvm/IR/Function.h"
19#include "llvm/IR/Instructions.h"
20#include "llvm/IR/LLVMContext.h"
21#include "llvm/IR/Metadata.h"
22#include "llvm/Support/CFG.h"
23#include "llvm/Support/Debug.h"
24
25using namespace llvm;
26
27INITIALIZE_PASS_BEGIN(BranchProbabilityInfo, "branch-prob",
28                      "Branch Probability Analysis", false, true)
29INITIALIZE_PASS_DEPENDENCY(LoopInfo)
30INITIALIZE_PASS_END(BranchProbabilityInfo, "branch-prob",
31                    "Branch Probability Analysis", false, true)
32
33char BranchProbabilityInfo::ID = 0;
34
35// Weights are for internal use only. They are used by heuristics to help to
36// estimate edges' probability. Example:
37//
38// Using "Loop Branch Heuristics" we predict weights of edges for the
39// block BB2.
40//         ...
41//          |
42//          V
43//         BB1<-+
44//          |   |
45//          |   | (Weight = 124)
46//          V   |
47//         BB2--+
48//          |
49//          | (Weight = 4)
50//          V
51//         BB3
52//
53// Probability of the edge BB2->BB1 = 124 / (124 + 4) = 0.96875
54// Probability of the edge BB2->BB3 = 4 / (124 + 4) = 0.03125
55static const uint32_t LBH_TAKEN_WEIGHT = 124;
56static const uint32_t LBH_NONTAKEN_WEIGHT = 4;
57
58/// \brief Unreachable-terminating branch taken weight.
59///
60/// This is the weight for a branch being taken to a block that terminates
61/// (eventually) in unreachable. These are predicted as unlikely as possible.
62static const uint32_t UR_TAKEN_WEIGHT = 1;
63
64/// \brief Unreachable-terminating branch not-taken weight.
65///
66/// This is the weight for a branch not being taken toward a block that
67/// terminates (eventually) in unreachable. Such a branch is essentially never
68/// taken. Set the weight to an absurdly high value so that nested loops don't
69/// easily subsume it.
70static const uint32_t UR_NONTAKEN_WEIGHT = 1024*1024 - 1;
71
72/// \brief Weight for a branch taken going into a cold block.
73///
74/// This is the weight for a branch taken toward a block marked
75/// cold.  A block is marked cold if it's postdominated by a
76/// block containing a call to a cold function.  Cold functions
77/// are those marked with attribute 'cold'.
78static const uint32_t CC_TAKEN_WEIGHT = 4;
79
80/// \brief Weight for a branch not-taken into a cold block.
81///
82/// This is the weight for a branch not taken toward a block marked
83/// cold.
84static const uint32_t CC_NONTAKEN_WEIGHT = 64;
85
86static const uint32_t PH_TAKEN_WEIGHT = 20;
87static const uint32_t PH_NONTAKEN_WEIGHT = 12;
88
89static const uint32_t ZH_TAKEN_WEIGHT = 20;
90static const uint32_t ZH_NONTAKEN_WEIGHT = 12;
91
92static const uint32_t FPH_TAKEN_WEIGHT = 20;
93static const uint32_t FPH_NONTAKEN_WEIGHT = 12;
94
95/// \brief Invoke-terminating normal branch taken weight
96///
97/// This is the weight for branching to the normal destination of an invoke
98/// instruction. We expect this to happen most of the time. Set the weight to an
99/// absurdly high value so that nested loops subsume it.
100static const uint32_t IH_TAKEN_WEIGHT = 1024 * 1024 - 1;
101
102/// \brief Invoke-terminating normal branch not-taken weight.
103///
104/// This is the weight for branching to the unwind destination of an invoke
105/// instruction. This is essentially never taken.
106static const uint32_t IH_NONTAKEN_WEIGHT = 1;
107
108// Standard weight value. Used when none of the heuristics set weight for
109// the edge.
110static const uint32_t NORMAL_WEIGHT = 16;
111
112// Minimum weight of an edge. Please note, that weight is NEVER 0.
113static const uint32_t MIN_WEIGHT = 1;
114
115static uint32_t getMaxWeightFor(BasicBlock *BB) {
116  return UINT32_MAX / BB->getTerminator()->getNumSuccessors();
117}
118
119
120/// \brief Calculate edge weights for successors lead to unreachable.
121///
122/// Predict that a successor which leads necessarily to an
123/// unreachable-terminated block as extremely unlikely.
124bool BranchProbabilityInfo::calcUnreachableHeuristics(BasicBlock *BB) {
125  TerminatorInst *TI = BB->getTerminator();
126  if (TI->getNumSuccessors() == 0) {
127    if (isa<UnreachableInst>(TI))
128      PostDominatedByUnreachable.insert(BB);
129    return false;
130  }
131
132  SmallVector<unsigned, 4> UnreachableEdges;
133  SmallVector<unsigned, 4> ReachableEdges;
134
135  for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
136    if (PostDominatedByUnreachable.count(*I))
137      UnreachableEdges.push_back(I.getSuccessorIndex());
138    else
139      ReachableEdges.push_back(I.getSuccessorIndex());
140  }
141
142  // If all successors are in the set of blocks post-dominated by unreachable,
143  // this block is too.
144  if (UnreachableEdges.size() == TI->getNumSuccessors())
145    PostDominatedByUnreachable.insert(BB);
146
147  // Skip probabilities if this block has a single successor or if all were
148  // reachable.
149  if (TI->getNumSuccessors() == 1 || UnreachableEdges.empty())
150    return false;
151
152  uint32_t UnreachableWeight =
153    std::max(UR_TAKEN_WEIGHT / (unsigned)UnreachableEdges.size(), MIN_WEIGHT);
154  for (SmallVectorImpl<unsigned>::iterator I = UnreachableEdges.begin(),
155                                           E = UnreachableEdges.end();
156       I != E; ++I)
157    setEdgeWeight(BB, *I, UnreachableWeight);
158
159  if (ReachableEdges.empty())
160    return true;
161  uint32_t ReachableWeight =
162    std::max(UR_NONTAKEN_WEIGHT / (unsigned)ReachableEdges.size(),
163             NORMAL_WEIGHT);
164  for (SmallVectorImpl<unsigned>::iterator I = ReachableEdges.begin(),
165                                           E = ReachableEdges.end();
166       I != E; ++I)
167    setEdgeWeight(BB, *I, ReachableWeight);
168
169  return true;
170}
171
172// Propagate existing explicit probabilities from either profile data or
173// 'expect' intrinsic processing.
174bool BranchProbabilityInfo::calcMetadataWeights(BasicBlock *BB) {
175  TerminatorInst *TI = BB->getTerminator();
176  if (TI->getNumSuccessors() == 1)
177    return false;
178  if (!isa<BranchInst>(TI) && !isa<SwitchInst>(TI))
179    return false;
180
181  MDNode *WeightsNode = TI->getMetadata(LLVMContext::MD_prof);
182  if (!WeightsNode)
183    return false;
184
185  // Ensure there are weights for all of the successors. Note that the first
186  // operand to the metadata node is a name, not a weight.
187  if (WeightsNode->getNumOperands() != TI->getNumSuccessors() + 1)
188    return false;
189
190  // Build up the final weights that will be used in a temporary buffer, but
191  // don't add them until all weihts are present. Each weight value is clamped
192  // to [1, getMaxWeightFor(BB)].
193  uint32_t WeightLimit = getMaxWeightFor(BB);
194  SmallVector<uint32_t, 2> Weights;
195  Weights.reserve(TI->getNumSuccessors());
196  for (unsigned i = 1, e = WeightsNode->getNumOperands(); i != e; ++i) {
197    ConstantInt *Weight = dyn_cast<ConstantInt>(WeightsNode->getOperand(i));
198    if (!Weight)
199      return false;
200    Weights.push_back(
201      std::max<uint32_t>(1, Weight->getLimitedValue(WeightLimit)));
202  }
203  assert(Weights.size() == TI->getNumSuccessors() && "Checked above");
204  for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
205    setEdgeWeight(BB, i, Weights[i]);
206
207  return true;
208}
209
210/// \brief Calculate edge weights for edges leading to cold blocks.
211///
212/// A cold block is one post-dominated by  a block with a call to a
213/// cold function.  Those edges are unlikely to be taken, so we give
214/// them relatively low weight.
215///
216/// Return true if we could compute the weights for cold edges.
217/// Return false, otherwise.
218bool BranchProbabilityInfo::calcColdCallHeuristics(BasicBlock *BB) {
219  TerminatorInst *TI = BB->getTerminator();
220  if (TI->getNumSuccessors() == 0)
221    return false;
222
223  // Determine which successors are post-dominated by a cold block.
224  SmallVector<unsigned, 4> ColdEdges;
225  SmallVector<unsigned, 4> NormalEdges;
226  for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I)
227    if (PostDominatedByColdCall.count(*I))
228      ColdEdges.push_back(I.getSuccessorIndex());
229    else
230      NormalEdges.push_back(I.getSuccessorIndex());
231
232  // If all successors are in the set of blocks post-dominated by cold calls,
233  // this block is in the set post-dominated by cold calls.
234  if (ColdEdges.size() == TI->getNumSuccessors())
235    PostDominatedByColdCall.insert(BB);
236  else {
237    // Otherwise, if the block itself contains a cold function, add it to the
238    // set of blocks postdominated by a cold call.
239    assert(!PostDominatedByColdCall.count(BB));
240    for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
241      if (CallInst *CI = dyn_cast<CallInst>(I))
242        if (CI->hasFnAttr(Attribute::Cold)) {
243          PostDominatedByColdCall.insert(BB);
244          break;
245        }
246  }
247
248  // Skip probabilities if this block has a single successor.
249  if (TI->getNumSuccessors() == 1 || ColdEdges.empty())
250    return false;
251
252  uint32_t ColdWeight =
253      std::max(CC_TAKEN_WEIGHT / (unsigned) ColdEdges.size(), MIN_WEIGHT);
254  for (SmallVectorImpl<unsigned>::iterator I = ColdEdges.begin(),
255                                           E = ColdEdges.end();
256       I != E; ++I)
257    setEdgeWeight(BB, *I, ColdWeight);
258
259  if (NormalEdges.empty())
260    return true;
261  uint32_t NormalWeight = std::max(
262      CC_NONTAKEN_WEIGHT / (unsigned) NormalEdges.size(), NORMAL_WEIGHT);
263  for (SmallVectorImpl<unsigned>::iterator I = NormalEdges.begin(),
264                                           E = NormalEdges.end();
265       I != E; ++I)
266    setEdgeWeight(BB, *I, NormalWeight);
267
268  return true;
269}
270
271// Calculate Edge Weights using "Pointer Heuristics". Predict a comparsion
272// between two pointer or pointer and NULL will fail.
273bool BranchProbabilityInfo::calcPointerHeuristics(BasicBlock *BB) {
274  BranchInst * BI = dyn_cast<BranchInst>(BB->getTerminator());
275  if (!BI || !BI->isConditional())
276    return false;
277
278  Value *Cond = BI->getCondition();
279  ICmpInst *CI = dyn_cast<ICmpInst>(Cond);
280  if (!CI || !CI->isEquality())
281    return false;
282
283  Value *LHS = CI->getOperand(0);
284
285  if (!LHS->getType()->isPointerTy())
286    return false;
287
288  assert(CI->getOperand(1)->getType()->isPointerTy());
289
290  // p != 0   ->   isProb = true
291  // p == 0   ->   isProb = false
292  // p != q   ->   isProb = true
293  // p == q   ->   isProb = false;
294  unsigned TakenIdx = 0, NonTakenIdx = 1;
295  bool isProb = CI->getPredicate() == ICmpInst::ICMP_NE;
296  if (!isProb)
297    std::swap(TakenIdx, NonTakenIdx);
298
299  setEdgeWeight(BB, TakenIdx, PH_TAKEN_WEIGHT);
300  setEdgeWeight(BB, NonTakenIdx, PH_NONTAKEN_WEIGHT);
301  return true;
302}
303
304// Calculate Edge Weights using "Loop Branch Heuristics". Predict backedges
305// as taken, exiting edges as not-taken.
306bool BranchProbabilityInfo::calcLoopBranchHeuristics(BasicBlock *BB) {
307  Loop *L = LI->getLoopFor(BB);
308  if (!L)
309    return false;
310
311  SmallVector<unsigned, 8> BackEdges;
312  SmallVector<unsigned, 8> ExitingEdges;
313  SmallVector<unsigned, 8> InEdges; // Edges from header to the loop.
314
315  for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
316    if (!L->contains(*I))
317      ExitingEdges.push_back(I.getSuccessorIndex());
318    else if (L->getHeader() == *I)
319      BackEdges.push_back(I.getSuccessorIndex());
320    else
321      InEdges.push_back(I.getSuccessorIndex());
322  }
323
324  if (uint32_t numBackEdges = BackEdges.size()) {
325    uint32_t backWeight = LBH_TAKEN_WEIGHT / numBackEdges;
326    if (backWeight < NORMAL_WEIGHT)
327      backWeight = NORMAL_WEIGHT;
328
329    for (SmallVectorImpl<unsigned>::iterator EI = BackEdges.begin(),
330         EE = BackEdges.end(); EI != EE; ++EI) {
331      setEdgeWeight(BB, *EI, backWeight);
332    }
333  }
334
335  if (uint32_t numInEdges = InEdges.size()) {
336    uint32_t inWeight = LBH_TAKEN_WEIGHT / numInEdges;
337    if (inWeight < NORMAL_WEIGHT)
338      inWeight = NORMAL_WEIGHT;
339
340    for (SmallVectorImpl<unsigned>::iterator EI = InEdges.begin(),
341         EE = InEdges.end(); EI != EE; ++EI) {
342      setEdgeWeight(BB, *EI, inWeight);
343    }
344  }
345
346  if (uint32_t numExitingEdges = ExitingEdges.size()) {
347    uint32_t exitWeight = LBH_NONTAKEN_WEIGHT / numExitingEdges;
348    if (exitWeight < MIN_WEIGHT)
349      exitWeight = MIN_WEIGHT;
350
351    for (SmallVectorImpl<unsigned>::iterator EI = ExitingEdges.begin(),
352         EE = ExitingEdges.end(); EI != EE; ++EI) {
353      setEdgeWeight(BB, *EI, exitWeight);
354    }
355  }
356
357  return true;
358}
359
360bool BranchProbabilityInfo::calcZeroHeuristics(BasicBlock *BB) {
361  BranchInst * BI = dyn_cast<BranchInst>(BB->getTerminator());
362  if (!BI || !BI->isConditional())
363    return false;
364
365  Value *Cond = BI->getCondition();
366  ICmpInst *CI = dyn_cast<ICmpInst>(Cond);
367  if (!CI)
368    return false;
369
370  Value *RHS = CI->getOperand(1);
371  ConstantInt *CV = dyn_cast<ConstantInt>(RHS);
372  if (!CV)
373    return false;
374
375  bool isProb;
376  if (CV->isZero()) {
377    switch (CI->getPredicate()) {
378    case CmpInst::ICMP_EQ:
379      // X == 0   ->  Unlikely
380      isProb = false;
381      break;
382    case CmpInst::ICMP_NE:
383      // X != 0   ->  Likely
384      isProb = true;
385      break;
386    case CmpInst::ICMP_SLT:
387      // X < 0   ->  Unlikely
388      isProb = false;
389      break;
390    case CmpInst::ICMP_SGT:
391      // X > 0   ->  Likely
392      isProb = true;
393      break;
394    default:
395      return false;
396    }
397  } else if (CV->isOne() && CI->getPredicate() == CmpInst::ICMP_SLT) {
398    // InstCombine canonicalizes X <= 0 into X < 1.
399    // X <= 0   ->  Unlikely
400    isProb = false;
401  } else if (CV->isAllOnesValue() && CI->getPredicate() == CmpInst::ICMP_SGT) {
402    // InstCombine canonicalizes X >= 0 into X > -1.
403    // X >= 0   ->  Likely
404    isProb = true;
405  } else {
406    return false;
407  }
408
409  unsigned TakenIdx = 0, NonTakenIdx = 1;
410
411  if (!isProb)
412    std::swap(TakenIdx, NonTakenIdx);
413
414  setEdgeWeight(BB, TakenIdx, ZH_TAKEN_WEIGHT);
415  setEdgeWeight(BB, NonTakenIdx, ZH_NONTAKEN_WEIGHT);
416
417  return true;
418}
419
420bool BranchProbabilityInfo::calcFloatingPointHeuristics(BasicBlock *BB) {
421  BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
422  if (!BI || !BI->isConditional())
423    return false;
424
425  Value *Cond = BI->getCondition();
426  FCmpInst *FCmp = dyn_cast<FCmpInst>(Cond);
427  if (!FCmp)
428    return false;
429
430  bool isProb;
431  if (FCmp->isEquality()) {
432    // f1 == f2 -> Unlikely
433    // f1 != f2 -> Likely
434    isProb = !FCmp->isTrueWhenEqual();
435  } else if (FCmp->getPredicate() == FCmpInst::FCMP_ORD) {
436    // !isnan -> Likely
437    isProb = true;
438  } else if (FCmp->getPredicate() == FCmpInst::FCMP_UNO) {
439    // isnan -> Unlikely
440    isProb = false;
441  } else {
442    return false;
443  }
444
445  unsigned TakenIdx = 0, NonTakenIdx = 1;
446
447  if (!isProb)
448    std::swap(TakenIdx, NonTakenIdx);
449
450  setEdgeWeight(BB, TakenIdx, FPH_TAKEN_WEIGHT);
451  setEdgeWeight(BB, NonTakenIdx, FPH_NONTAKEN_WEIGHT);
452
453  return true;
454}
455
456bool BranchProbabilityInfo::calcInvokeHeuristics(BasicBlock *BB) {
457  InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator());
458  if (!II)
459    return false;
460
461  setEdgeWeight(BB, 0/*Index for Normal*/, IH_TAKEN_WEIGHT);
462  setEdgeWeight(BB, 1/*Index for Unwind*/, IH_NONTAKEN_WEIGHT);
463  return true;
464}
465
466void BranchProbabilityInfo::getAnalysisUsage(AnalysisUsage &AU) const {
467  AU.addRequired<LoopInfo>();
468  AU.setPreservesAll();
469}
470
471bool BranchProbabilityInfo::runOnFunction(Function &F) {
472  LastF = &F; // Store the last function we ran on for printing.
473  LI = &getAnalysis<LoopInfo>();
474  assert(PostDominatedByUnreachable.empty());
475  assert(PostDominatedByColdCall.empty());
476
477  // Walk the basic blocks in post-order so that we can build up state about
478  // the successors of a block iteratively.
479  for (po_iterator<BasicBlock *> I = po_begin(&F.getEntryBlock()),
480                                 E = po_end(&F.getEntryBlock());
481       I != E; ++I) {
482    DEBUG(dbgs() << "Computing probabilities for " << I->getName() << "\n");
483    if (calcUnreachableHeuristics(*I))
484      continue;
485    if (calcMetadataWeights(*I))
486      continue;
487    if (calcColdCallHeuristics(*I))
488      continue;
489    if (calcLoopBranchHeuristics(*I))
490      continue;
491    if (calcPointerHeuristics(*I))
492      continue;
493    if (calcZeroHeuristics(*I))
494      continue;
495    if (calcFloatingPointHeuristics(*I))
496      continue;
497    calcInvokeHeuristics(*I);
498  }
499
500  PostDominatedByUnreachable.clear();
501  PostDominatedByColdCall.clear();
502  return false;
503}
504
505void BranchProbabilityInfo::print(raw_ostream &OS, const Module *) const {
506  OS << "---- Branch Probabilities ----\n";
507  // We print the probabilities from the last function the analysis ran over,
508  // or the function it is currently running over.
509  assert(LastF && "Cannot print prior to running over a function");
510  for (Function::const_iterator BI = LastF->begin(), BE = LastF->end();
511       BI != BE; ++BI) {
512    for (succ_const_iterator SI = succ_begin(BI), SE = succ_end(BI);
513         SI != SE; ++SI) {
514      printEdgeProbability(OS << "  ", BI, *SI);
515    }
516  }
517}
518
519uint32_t BranchProbabilityInfo::getSumForBlock(const BasicBlock *BB) const {
520  uint32_t Sum = 0;
521
522  for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
523    uint32_t Weight = getEdgeWeight(BB, I.getSuccessorIndex());
524    uint32_t PrevSum = Sum;
525
526    Sum += Weight;
527    assert(Sum > PrevSum); (void) PrevSum;
528  }
529
530  return Sum;
531}
532
533bool BranchProbabilityInfo::
534isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const {
535  // Hot probability is at least 4/5 = 80%
536  // FIXME: Compare against a static "hot" BranchProbability.
537  return getEdgeProbability(Src, Dst) > BranchProbability(4, 5);
538}
539
540BasicBlock *BranchProbabilityInfo::getHotSucc(BasicBlock *BB) const {
541  uint32_t Sum = 0;
542  uint32_t MaxWeight = 0;
543  BasicBlock *MaxSucc = 0;
544
545  for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
546    BasicBlock *Succ = *I;
547    uint32_t Weight = getEdgeWeight(BB, Succ);
548    uint32_t PrevSum = Sum;
549
550    Sum += Weight;
551    assert(Sum > PrevSum); (void) PrevSum;
552
553    if (Weight > MaxWeight) {
554      MaxWeight = Weight;
555      MaxSucc = Succ;
556    }
557  }
558
559  // Hot probability is at least 4/5 = 80%
560  if (BranchProbability(MaxWeight, Sum) > BranchProbability(4, 5))
561    return MaxSucc;
562
563  return 0;
564}
565
566/// Get the raw edge weight for the edge. If can't find it, return
567/// DEFAULT_WEIGHT value. Here an edge is specified using PredBlock and an index
568/// to the successors.
569uint32_t BranchProbabilityInfo::
570getEdgeWeight(const BasicBlock *Src, unsigned IndexInSuccessors) const {
571  DenseMap<Edge, uint32_t>::const_iterator I =
572      Weights.find(std::make_pair(Src, IndexInSuccessors));
573
574  if (I != Weights.end())
575    return I->second;
576
577  return DEFAULT_WEIGHT;
578}
579
580/// Get the raw edge weight calculated for the block pair. This returns the sum
581/// of all raw edge weights from Src to Dst.
582uint32_t BranchProbabilityInfo::
583getEdgeWeight(const BasicBlock *Src, const BasicBlock *Dst) const {
584  uint32_t Weight = 0;
585  DenseMap<Edge, uint32_t>::const_iterator MapI;
586  for (succ_const_iterator I = succ_begin(Src), E = succ_end(Src); I != E; ++I)
587    if (*I == Dst) {
588      MapI = Weights.find(std::make_pair(Src, I.getSuccessorIndex()));
589      if (MapI != Weights.end())
590        Weight += MapI->second;
591    }
592  return (Weight == 0) ? DEFAULT_WEIGHT : Weight;
593}
594
595/// Set the edge weight for a given edge specified by PredBlock and an index
596/// to the successors.
597void BranchProbabilityInfo::
598setEdgeWeight(const BasicBlock *Src, unsigned IndexInSuccessors,
599              uint32_t Weight) {
600  Weights[std::make_pair(Src, IndexInSuccessors)] = Weight;
601  DEBUG(dbgs() << "set edge " << Src->getName() << " -> "
602               << IndexInSuccessors << " successor weight to "
603               << Weight << "\n");
604}
605
606/// Get an edge's probability, relative to other out-edges from Src.
607BranchProbability BranchProbabilityInfo::
608getEdgeProbability(const BasicBlock *Src, unsigned IndexInSuccessors) const {
609  uint32_t N = getEdgeWeight(Src, IndexInSuccessors);
610  uint32_t D = getSumForBlock(Src);
611
612  return BranchProbability(N, D);
613}
614
615/// Get the probability of going from Src to Dst. It returns the sum of all
616/// probabilities for edges from Src to Dst.
617BranchProbability BranchProbabilityInfo::
618getEdgeProbability(const BasicBlock *Src, const BasicBlock *Dst) const {
619
620  uint32_t N = getEdgeWeight(Src, Dst);
621  uint32_t D = getSumForBlock(Src);
622
623  return BranchProbability(N, D);
624}
625
626raw_ostream &
627BranchProbabilityInfo::printEdgeProbability(raw_ostream &OS,
628                                            const BasicBlock *Src,
629                                            const BasicBlock *Dst) const {
630
631  const BranchProbability Prob = getEdgeProbability(Src, Dst);
632  OS << "edge " << Src->getName() << " -> " << Dst->getName()
633     << " probability is " << Prob
634     << (isEdgeHot(Src, Dst) ? " [HOT edge]\n" : "\n");
635
636  return OS;
637}
638