lib/Analysis/BranchProbabilityInfo.cpp

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