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
 225   if (WeightSum == 0) {
 226     for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
 227       setEdgeProbability(BB, i, {1, e});
 228   } else {
 229     for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
 230       setEdgeProbability(BB, i, {Weights[i], static_cast<uint32_t>(WeightSum)});
 231   }
 232
 233   assert(WeightSum <= UINT32_MAX &&
 234          "Expected weights to scale down to 32 bits");
 235
 236   return true;
 237 }
 238
 239 /// \brief Calculate edge weights for edges leading to cold blocks.
 240 ///
 241 /// A cold block is one post-dominated by  a block with a call to a
 242 /// cold function.  Those edges are unlikely to be taken, so we give
 243 /// them relatively low weight.
 244 ///
 245 /// Return true if we could compute the weights for cold edges.
 246 /// Return false, otherwise.
 247 bool BranchProbabilityInfo::calcColdCallHeuristics(BasicBlock *BB) {
 248   TerminatorInst *TI = BB->getTerminator();
 249   if (TI->getNumSuccessors() == 0)
 250     return false;
 251
 252   // Determine which successors are post-dominated by a cold block.
 253   SmallVector<unsigned, 4> ColdEdges;
 254   SmallVector<unsigned, 4> NormalEdges;
 255   for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I)
 256     if (PostDominatedByColdCall.count(*I))
 257       ColdEdges.push_back(I.getSuccessorIndex());
 258     else
 259       NormalEdges.push_back(I.getSuccessorIndex());
 260
 261   // If all successors are in the set of blocks post-dominated by cold calls,
 262   // this block is in the set post-dominated by cold calls.
 263   if (ColdEdges.size() == TI->getNumSuccessors())
 264     PostDominatedByColdCall.insert(BB);
 265   else {
 266     // Otherwise, if the block itself contains a cold function, add it to the
 267     // set of blocks postdominated by a cold call.
 268     assert(!PostDominatedByColdCall.count(BB));
 269     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
 270       if (CallInst *CI = dyn_cast<CallInst>(I))
 271         if (CI->hasFnAttr(Attribute::Cold)) {
 272           PostDominatedByColdCall.insert(BB);
 273           break;
 274         }
 275   }
 276
 277   // Skip probabilities if this block has a single successor.
 278   if (TI->getNumSuccessors() == 1 || ColdEdges.empty())
 279     return false;
 280
 281   if (NormalEdges.empty()) {
 282     BranchProbability Prob(1, ColdEdges.size());
 283     for (unsigned SuccIdx : ColdEdges)
 284       setEdgeProbability(BB, SuccIdx, Prob);
 285     return true;
 286   }
 287
 288   BranchProbability ColdProb(CC_TAKEN_WEIGHT,
 289                              (CC_TAKEN_WEIGHT + CC_NONTAKEN_WEIGHT) *
 290                                  ColdEdges.size());
 291   BranchProbability NormalProb(CC_NONTAKEN_WEIGHT,
 292                                (CC_TAKEN_WEIGHT + CC_NONTAKEN_WEIGHT) *
 293                                    NormalEdges.size());
 294
 295   for (unsigned SuccIdx : ColdEdges)
 296     setEdgeProbability(BB, SuccIdx, ColdProb);
 297   for (unsigned SuccIdx : NormalEdges)
 298     setEdgeProbability(BB, SuccIdx, NormalProb);
 299
 300   return true;
 301 }
 302
 303 // Calculate Edge Weights using "Pointer Heuristics". Predict a comparsion
 304 // between two pointer or pointer and NULL will fail.
 305 bool BranchProbabilityInfo::calcPointerHeuristics(BasicBlock *BB) {
 306   BranchInst * BI = dyn_cast<BranchInst>(BB->getTerminator());
 307   if (!BI || !BI->isConditional())
 308     return false;
 309
 310   Value *Cond = BI->getCondition();
 311   ICmpInst *CI = dyn_cast<ICmpInst>(Cond);
 312   if (!CI || !CI->isEquality())
 313     return false;
 314
 315   Value *LHS = CI->getOperand(0);
 316
 317   if (!LHS->getType()->isPointerTy())
 318     return false;
 319
 320   assert(CI->getOperand(1)->getType()->isPointerTy());
 321
 322   // p != 0   ->   isProb = true
 323   // p == 0   ->   isProb = false
 324   // p != q   ->   isProb = true
 325   // p == q   ->   isProb = false;
 326   unsigned TakenIdx = 0, NonTakenIdx = 1;
 327   bool isProb = CI->getPredicate() == ICmpInst::ICMP_NE;
 328   if (!isProb)
 329     std::swap(TakenIdx, NonTakenIdx);
 330
 331   BranchProbability TakenProb(PH_TAKEN_WEIGHT,
 332                               PH_TAKEN_WEIGHT + PH_NONTAKEN_WEIGHT);
 333   setEdgeProbability(BB, TakenIdx, TakenProb);
 334   setEdgeProbability(BB, NonTakenIdx, TakenProb.getCompl());
 335   return true;
 336 }
 337
 338 // Calculate Edge Weights using "Loop Branch Heuristics". Predict backedges
 339 // as taken, exiting edges as not-taken.
 340 bool BranchProbabilityInfo::calcLoopBranchHeuristics(BasicBlock *BB,
 341                                                      const LoopInfo &LI) {
 342   Loop *L = LI.getLoopFor(BB);
 343   if (!L)
 344     return false;
 345
 346   SmallVector<unsigned, 8> BackEdges;
 347   SmallVector<unsigned, 8> ExitingEdges;
 348   SmallVector<unsigned, 8> InEdges; // Edges from header to the loop.
 349
 350   for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
 351     if (!L->contains(*I))
 352       ExitingEdges.push_back(I.getSuccessorIndex());
 353     else if (L->getHeader() == *I)
 354       BackEdges.push_back(I.getSuccessorIndex());
 355     else
 356       InEdges.push_back(I.getSuccessorIndex());
 357   }
 358
 359   if (BackEdges.empty() && ExitingEdges.empty())
 360     return false;
 361
 362   // Collect the sum of probabilities of back-edges/in-edges/exiting-edges, and
 363   // normalize them so that they sum up to one.
 364   SmallVector<BranchProbability, 4> Probs(3, BranchProbability::getZero());
 365   unsigned Denom = (BackEdges.empty() ? 0 : LBH_TAKEN_WEIGHT) +
 366                    (InEdges.empty() ? 0 : LBH_TAKEN_WEIGHT) +
 367                    (ExitingEdges.empty() ? 0 : LBH_NONTAKEN_WEIGHT);
 368   if (!BackEdges.empty())
 369     Probs[0] = BranchProbability(LBH_TAKEN_WEIGHT, Denom);
 370   if (!InEdges.empty())
 371     Probs[1] = BranchProbability(LBH_TAKEN_WEIGHT, Denom);
 372   if (!ExitingEdges.empty())
 373     Probs[2] = BranchProbability(LBH_NONTAKEN_WEIGHT, Denom);
 374
 375   if (uint32_t numBackEdges = BackEdges.size()) {
 376     auto Prob = Probs[0] / numBackEdges;
 377     for (unsigned SuccIdx : BackEdges)
 378       setEdgeProbability(BB, SuccIdx, Prob);
 379   }
 380
 381   if (uint32_t numInEdges = InEdges.size()) {
 382     auto Prob = Probs[1] / numInEdges;
 383     for (unsigned SuccIdx : InEdges)
 384       setEdgeProbability(BB, SuccIdx, Prob);
 385   }
 386
 387   if (uint32_t numExitingEdges = ExitingEdges.size()) {
 388     auto Prob = Probs[2] / numExitingEdges;
 389     for (unsigned SuccIdx : ExitingEdges)
 390       setEdgeProbability(BB, SuccIdx, Prob);
 391   }
 392
 393   return true;
 394 }
 395
 396 bool BranchProbabilityInfo::calcZeroHeuristics(BasicBlock *BB) {
 397   BranchInst * BI = dyn_cast<BranchInst>(BB->getTerminator());
 398   if (!BI || !BI->isConditional())
 399     return false;
 400
 401   Value *Cond = BI->getCondition();
 402   ICmpInst *CI = dyn_cast<ICmpInst>(Cond);
 403   if (!CI)
 404     return false;
 405
 406   Value *RHS = CI->getOperand(1);
 407   ConstantInt *CV = dyn_cast<ConstantInt>(RHS);
 408   if (!CV)
 409     return false;
 410
 411   // If the LHS is the result of AND'ing a value with a single bit bitmask,
 412   // we don't have information about probabilities.
 413   if (Instruction *LHS = dyn_cast<Instruction>(CI->getOperand(0)))
 414     if (LHS->getOpcode() == Instruction::And)
 415       if (ConstantInt *AndRHS = dyn_cast<ConstantInt>(LHS->getOperand(1)))
 416         if (AndRHS->getUniqueInteger().isPowerOf2())
 417           return false;
 418
 419   bool isProb;
 420   if (CV->isZero()) {
 421     switch (CI->getPredicate()) {
 422     case CmpInst::ICMP_EQ:
 423       // X == 0   ->  Unlikely
 424       isProb = false;
 425       break;
 426     case CmpInst::ICMP_NE:
 427       // X != 0   ->  Likely
 428       isProb = true;
 429       break;
 430     case CmpInst::ICMP_SLT:
 431       // X < 0   ->  Unlikely
 432       isProb = false;
 433       break;
 434     case CmpInst::ICMP_SGT:
 435       // X > 0   ->  Likely
 436       isProb = true;
 437       break;
 438     default:
 439       return false;
 440     }
 441   } else if (CV->isOne() && CI->getPredicate() == CmpInst::ICMP_SLT) {
 442     // InstCombine canonicalizes X <= 0 into X < 1.
 443     // X <= 0   ->  Unlikely
 444     isProb = false;
 445   } else if (CV->isAllOnesValue()) {
 446     switch (CI->getPredicate()) {
 447     case CmpInst::ICMP_EQ:
 448       // X == -1  ->  Unlikely
 449       isProb = false;
 450       break;
 451     case CmpInst::ICMP_NE:
 452       // X != -1  ->  Likely
 453       isProb = true;
 454       break;
 455     case CmpInst::ICMP_SGT:
 456       // InstCombine canonicalizes X >= 0 into X > -1.
 457       // X >= 0   ->  Likely
 458       isProb = true;
 459       break;
 460     default:
 461       return false;
 462     }
 463   } else {
 464     return false;
 465   }
 466
 467   unsigned TakenIdx = 0, NonTakenIdx = 1;
 468
 469   if (!isProb)
 470     std::swap(TakenIdx, NonTakenIdx);
 471
 472   BranchProbability TakenProb(ZH_TAKEN_WEIGHT,
 473                               ZH_TAKEN_WEIGHT + ZH_NONTAKEN_WEIGHT);
 474   setEdgeProbability(BB, TakenIdx, TakenProb);
 475   setEdgeProbability(BB, NonTakenIdx, TakenProb.getCompl());
 476   return true;
 477 }
 478
 479 bool BranchProbabilityInfo::calcFloatingPointHeuristics(BasicBlock *BB) {
 480   BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
 481   if (!BI || !BI->isConditional())
 482     return false;
 483
 484   Value *Cond = BI->getCondition();
 485   FCmpInst *FCmp = dyn_cast<FCmpInst>(Cond);
 486   if (!FCmp)
 487     return false;
 488
 489   bool isProb;
 490   if (FCmp->isEquality()) {
 491     // f1 == f2 -> Unlikely
 492     // f1 != f2 -> Likely
 493     isProb = !FCmp->isTrueWhenEqual();
 494   } else if (FCmp->getPredicate() == FCmpInst::FCMP_ORD) {
 495     // !isnan -> Likely
 496     isProb = true;
 497   } else if (FCmp->getPredicate() == FCmpInst::FCMP_UNO) {
 498     // isnan -> Unlikely
 499     isProb = false;
 500   } else {
 501     return false;
 502   }
 503
 504   unsigned TakenIdx = 0, NonTakenIdx = 1;
 505
 506   if (!isProb)
 507     std::swap(TakenIdx, NonTakenIdx);
 508
 509   BranchProbability TakenProb(FPH_TAKEN_WEIGHT,
 510                               FPH_TAKEN_WEIGHT + FPH_NONTAKEN_WEIGHT);
 511   setEdgeProbability(BB, TakenIdx, TakenProb);
 512   setEdgeProbability(BB, NonTakenIdx, TakenProb.getCompl());
 513   return true;
 514 }
 515
 516 bool BranchProbabilityInfo::calcInvokeHeuristics(BasicBlock *BB) {
 517   InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator());
 518   if (!II)
 519     return false;
 520
 521   BranchProbability TakenProb(IH_TAKEN_WEIGHT,
 522                               IH_TAKEN_WEIGHT + IH_NONTAKEN_WEIGHT);
 523   setEdgeProbability(BB, 0 /*Index for Normal*/, TakenProb);
 524   setEdgeProbability(BB, 1 /*Index for Unwind*/, TakenProb.getCompl());
 525   return true;
 526 }
 527
 528 void BranchProbabilityInfo::releaseMemory() {
 529   Probs.clear();
 530 }
 531
 532 void BranchProbabilityInfo::print(raw_ostream &OS) const {
 533   OS << "---- Branch Probabilities ----\n";
 534   // We print the probabilities from the last function the analysis ran over,
 535   // or the function it is currently running over.
 536   assert(LastF && "Cannot print prior to running over a function");
 537   for (const auto &BI : *LastF) {
 538     for (succ_const_iterator SI = succ_begin(&BI), SE = succ_end(&BI); SI != SE;
 539          ++SI) {
 540       printEdgeProbability(OS << "  ", &BI, *SI);
 541     }
 542   }
 543 }
 544
 545 bool BranchProbabilityInfo::
 546 isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const {
 547   // Hot probability is at least 4/5 = 80%
 548   // FIXME: Compare against a static "hot" BranchProbability.
 549   return getEdgeProbability(Src, Dst) > BranchProbability(4, 5);
 550 }
 551
 552 BasicBlock *BranchProbabilityInfo::getHotSucc(BasicBlock *BB) const {
 553   auto MaxProb = BranchProbability::getZero();
 554   BasicBlock *MaxSucc = nullptr;
 555
 556   for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
 557     BasicBlock *Succ = *I;
 558     auto Prob = getEdgeProbability(BB, Succ);
 559     if (Prob > MaxProb) {
 560       MaxProb = Prob;
 561       MaxSucc = Succ;
 562     }
 563   }
 564
 565   // Hot probability is at least 4/5 = 80%
 566   if (MaxProb > BranchProbability(4, 5))
 567     return MaxSucc;
 568
 569   return nullptr;
 570 }
 571
 572 /// Get the raw edge probability for the edge. If can't find it, return a
 573 /// default probability 1/N where N is the number of successors. Here an edge is
 574 /// specified using PredBlock and an
 575 /// index to the successors.
 576 BranchProbability
 577 BranchProbabilityInfo::getEdgeProbability(const BasicBlock *Src,
 578                                           unsigned IndexInSuccessors) const {
 579   auto I = Probs.find(std::make_pair(Src, IndexInSuccessors));
 580
 581   if (I != Probs.end())
 582     return I->second;
 583
 584   return {1,
 585           static_cast<uint32_t>(std::distance(succ_begin(Src), succ_end(Src)))};
 586 }
 587
 588 BranchProbability
 589 BranchProbabilityInfo::getEdgeProbability(const BasicBlock *Src,
 590                                           succ_const_iterator Dst) const {
 591   return getEdgeProbability(Src, Dst.getSuccessorIndex());
 592 }
 593
 594 /// Get the raw edge probability calculated for the block pair. This returns the
 595 /// sum of all raw edge probabilities from Src to Dst.
 596 BranchProbability
 597 BranchProbabilityInfo::getEdgeProbability(const BasicBlock *Src,
 598                                           const BasicBlock *Dst) const {
 599   auto Prob = BranchProbability::getZero();
 600   bool FoundProb = false;
 601   for (succ_const_iterator I = succ_begin(Src), E = succ_end(Src); I != E; ++I)
 602     if (*I == Dst) {
 603       auto MapI = Probs.find(std::make_pair(Src, I.getSuccessorIndex()));
 604       if (MapI != Probs.end()) {
 605         FoundProb = true;
 606         Prob += MapI->second;
 607       }
 608     }
 609   uint32_t succ_num = std::distance(succ_begin(Src), succ_end(Src));
 610   return FoundProb ? Prob : BranchProbability(1, succ_num);
 611 }
 612
 613 /// Set the edge probability for a given edge specified by PredBlock and an
 614 /// index to the successors.
 615 void BranchProbabilityInfo::setEdgeProbability(const BasicBlock *Src,
 616                                                unsigned IndexInSuccessors,
 617                                                BranchProbability Prob) {
 618   Probs[std::make_pair(Src, IndexInSuccessors)] = Prob;
 619   DEBUG(dbgs() << "set edge " << Src->getName() << " -> " << IndexInSuccessors
 620                << " successor probability to " << Prob << "\n");
 621 }
 622
 623 raw_ostream &
 624 BranchProbabilityInfo::printEdgeProbability(raw_ostream &OS,
 625                                             const BasicBlock *Src,
 626                                             const BasicBlock *Dst) const {
 627
 628   const BranchProbability Prob = getEdgeProbability(Src, Dst);
 629   OS << "edge " << Src->getName() << " -> " << Dst->getName()
 630      << " probability is " << Prob
 631      << (isEdgeHot(Src, Dst) ? " [HOT edge]\n" : "\n");
 632
 633   return OS;
 634 }
 635
 636 void BranchProbabilityInfo::calculate(Function &F, const LoopInfo& LI) {
 637   DEBUG(dbgs() << "---- Branch Probability Info : " << F.getName()
 638                << " ----\n\n");
 639   LastF = &F; // Store the last function we ran on for printing.
 640   assert(PostDominatedByUnreachable.empty());
 641   assert(PostDominatedByColdCall.empty());
 642
 643   // Walk the basic blocks in post-order so that we can build up state about
 644   // the successors of a block iteratively.
 645   for (auto BB : post_order(&F.getEntryBlock())) {
 646     DEBUG(dbgs() << "Computing probabilities for " << BB->getName() << "\n");
 647     if (calcUnreachableHeuristics(BB))
 648       continue;
 649     if (calcMetadataWeights(BB))
 650       continue;
 651     if (calcColdCallHeuristics(BB))
 652       continue;
 653     if (calcLoopBranchHeuristics(BB, LI))
 654       continue;
 655     if (calcPointerHeuristics(BB))
 656       continue;
 657     if (calcZeroHeuristics(BB))
 658       continue;
 659     if (calcFloatingPointHeuristics(BB))
 660       continue;
 661     calcInvokeHeuristics(BB);
 662   }
 663
 664   PostDominatedByUnreachable.clear();
 665   PostDominatedByColdCall.clear();
 666 }
 667
 668 void BranchProbabilityInfoWrapperPass::getAnalysisUsage(
 669     AnalysisUsage &AU) const {
 670   AU.addRequired<LoopInfoWrapperPass>();
 671   AU.setPreservesAll();
 672 }
 673
 674 bool BranchProbabilityInfoWrapperPass::runOnFunction(Function &F) {
 675   const LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
 676   BPI.calculate(F, LI);
 677   return false;
 678 }
 679
 680 void BranchProbabilityInfoWrapperPass::releaseMemory() { BPI.releaseMemory(); }
 681
 682 void BranchProbabilityInfoWrapperPass::print(raw_ostream &OS,
 683                                              const Module *) const {
 684   BPI.print(OS);
 685 }