contrib/llvm/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 Add \p BB to PostDominatedByUnreachable set if applicable.
 112 void
 113 BranchProbabilityInfo::updatePostDominatedByUnreachable(const BasicBlock *BB) {
 114   const TerminatorInst *TI = BB->getTerminator();
 115   if (TI->getNumSuccessors() == 0) {
 116     if (isa<UnreachableInst>(TI) ||
 117         // If this block is terminated by a call to
 118         // @llvm.experimental.deoptimize then treat it like an unreachable since
 119         // the @llvm.experimental.deoptimize call is expected to practically
 120         // never execute.
 121         BB->getTerminatingDeoptimizeCall())
 122       PostDominatedByUnreachable.insert(BB);
 123     return;
 124   }
 125
 126   // If the terminator is an InvokeInst, check only the normal destination block
 127   // as the unwind edge of InvokeInst is also very unlikely taken.
 128   if (auto *II = dyn_cast<InvokeInst>(TI)) {
 129     if (PostDominatedByUnreachable.count(II->getNormalDest()))
 130       PostDominatedByUnreachable.insert(BB);
 131     return;
 132   }
 133
 134   for (auto *I : successors(BB))
 135     // If any of successor is not post dominated then BB is also not.
 136     if (!PostDominatedByUnreachable.count(I))
 137       return;
 138
 139   PostDominatedByUnreachable.insert(BB);
 140 }
 141
 142 /// \brief Add \p BB to PostDominatedByColdCall set if applicable.
 143 void
 144 BranchProbabilityInfo::updatePostDominatedByColdCall(const BasicBlock *BB) {
 145   assert(!PostDominatedByColdCall.count(BB));
 146   const TerminatorInst *TI = BB->getTerminator();
 147   if (TI->getNumSuccessors() == 0)
 148     return;
 149
 150   // If all of successor are post dominated then BB is also done.
 151   if (llvm::all_of(successors(BB), [&](const BasicBlock *SuccBB) {
 152         return PostDominatedByColdCall.count(SuccBB);
 153       })) {
 154     PostDominatedByColdCall.insert(BB);
 155     return;
 156   }
 157
 158   // If the terminator is an InvokeInst, check only the normal destination
 159   // block as the unwind edge of InvokeInst is also very unlikely taken.
 160   if (auto *II = dyn_cast<InvokeInst>(TI))
 161     if (PostDominatedByColdCall.count(II->getNormalDest())) {
 162       PostDominatedByColdCall.insert(BB);
 163       return;
 164     }
 165
 166   // Otherwise, if the block itself contains a cold function, add it to the
 167   // set of blocks post-dominated by a cold call.
 168   for (auto &I : *BB)
 169     if (const CallInst *CI = dyn_cast<CallInst>(&I))
 170       if (CI->hasFnAttr(Attribute::Cold)) {
 171         PostDominatedByColdCall.insert(BB);
 172         return;
 173       }
 174 }
 175
 176 /// \brief Calculate edge weights for successors lead to unreachable.
 177 ///
 178 /// Predict that a successor which leads necessarily to an
 179 /// unreachable-terminated block as extremely unlikely.
 180 bool BranchProbabilityInfo::calcUnreachableHeuristics(const BasicBlock *BB) {
 181   const TerminatorInst *TI = BB->getTerminator();
 182   if (TI->getNumSuccessors() == 0)
 183     return false;
 184
 185   SmallVector<unsigned, 4> UnreachableEdges;
 186   SmallVector<unsigned, 4> ReachableEdges;
 187
 188   for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I)
 189     if (PostDominatedByUnreachable.count(*I))
 190       UnreachableEdges.push_back(I.getSuccessorIndex());
 191     else
 192       ReachableEdges.push_back(I.getSuccessorIndex());
 193
 194   // Skip probabilities if this block has a single successor or if all were
 195   // reachable.
 196   if (TI->getNumSuccessors() == 1 || UnreachableEdges.empty())
 197     return false;
 198
 199   // Return false here so that edge weights for InvokeInst could be decided
 200   // in calcInvokeHeuristics().
 201   if (isa<InvokeInst>(TI))
 202     return false;
 203
 204   if (ReachableEdges.empty()) {
 205     BranchProbability Prob(1, UnreachableEdges.size());
 206     for (unsigned SuccIdx : UnreachableEdges)
 207       setEdgeProbability(BB, SuccIdx, Prob);
 208     return true;
 209   }
 210
 211   auto UnreachableProb = BranchProbability::getBranchProbability(
 212       UR_TAKEN_WEIGHT, (UR_TAKEN_WEIGHT + UR_NONTAKEN_WEIGHT) *
 213                            uint64_t(UnreachableEdges.size()));
 214   auto ReachableProb = BranchProbability::getBranchProbability(
 215       UR_NONTAKEN_WEIGHT,
 216       (UR_TAKEN_WEIGHT + UR_NONTAKEN_WEIGHT) * uint64_t(ReachableEdges.size()));
 217
 218   for (unsigned SuccIdx : UnreachableEdges)
 219     setEdgeProbability(BB, SuccIdx, UnreachableProb);
 220   for (unsigned SuccIdx : ReachableEdges)
 221     setEdgeProbability(BB, SuccIdx, ReachableProb);
 222
 223   return true;
 224 }
 225
 226 // Propagate existing explicit probabilities from either profile data or
 227 // 'expect' intrinsic processing.
 228 bool BranchProbabilityInfo::calcMetadataWeights(const BasicBlock *BB) {
 229   const TerminatorInst *TI = BB->getTerminator();
 230   if (TI->getNumSuccessors() == 1)
 231     return false;
 232   if (!isa<BranchInst>(TI) && !isa<SwitchInst>(TI))
 233     return false;
 234
 235   MDNode *WeightsNode = TI->getMetadata(LLVMContext::MD_prof);
 236   if (!WeightsNode)
 237     return false;
 238
 239   // Check that the number of successors is manageable.
 240   assert(TI->getNumSuccessors() < UINT32_MAX && "Too many successors");
 241
 242   // Ensure there are weights for all of the successors. Note that the first
 243   // operand to the metadata node is a name, not a weight.
 244   if (WeightsNode->getNumOperands() != TI->getNumSuccessors() + 1)
 245     return false;
 246
 247   // Build up the final weights that will be used in a temporary buffer.
 248   // Compute the sum of all weights to later decide whether they need to
 249   // be scaled to fit in 32 bits.
 250   uint64_t WeightSum = 0;
 251   SmallVector<uint32_t, 2> Weights;
 252   Weights.reserve(TI->getNumSuccessors());
 253   for (unsigned i = 1, e = WeightsNode->getNumOperands(); i != e; ++i) {
 254     ConstantInt *Weight =
 255         mdconst::dyn_extract<ConstantInt>(WeightsNode->getOperand(i));
 256     if (!Weight)
 257       return false;
 258     assert(Weight->getValue().getActiveBits() <= 32 &&
 259            "Too many bits for uint32_t");
 260     Weights.push_back(Weight->getZExtValue());
 261     WeightSum += Weights.back();
 262   }
 263   assert(Weights.size() == TI->getNumSuccessors() && "Checked above");
 264
 265   // If the sum of weights does not fit in 32 bits, scale every weight down
 266   // accordingly.
 267   uint64_t ScalingFactor =
 268       (WeightSum > UINT32_MAX) ? WeightSum / UINT32_MAX + 1 : 1;
 269
 270   WeightSum = 0;
 271   for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) {
 272     Weights[i] /= ScalingFactor;
 273     WeightSum += Weights[i];
 274   }
 275
 276   if (WeightSum == 0) {
 277     for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
 278       setEdgeProbability(BB, i, {1, e});
 279   } else {
 280     for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
 281       setEdgeProbability(BB, i, {Weights[i], static_cast<uint32_t>(WeightSum)});
 282   }
 283
 284   assert(WeightSum <= UINT32_MAX &&
 285          "Expected weights to scale down to 32 bits");
 286
 287   return true;
 288 }
 289
 290 /// \brief Calculate edge weights for edges leading to cold blocks.
 291 ///
 292 /// A cold block is one post-dominated by  a block with a call to a
 293 /// cold function.  Those edges are unlikely to be taken, so we give
 294 /// them relatively low weight.
 295 ///
 296 /// Return true if we could compute the weights for cold edges.
 297 /// Return false, otherwise.
 298 bool BranchProbabilityInfo::calcColdCallHeuristics(const BasicBlock *BB) {
 299   const TerminatorInst *TI = BB->getTerminator();
 300   if (TI->getNumSuccessors() == 0)
 301     return false;
 302
 303   // Determine which successors are post-dominated by a cold block.
 304   SmallVector<unsigned, 4> ColdEdges;
 305   SmallVector<unsigned, 4> NormalEdges;
 306   for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I)
 307     if (PostDominatedByColdCall.count(*I))
 308       ColdEdges.push_back(I.getSuccessorIndex());
 309     else
 310       NormalEdges.push_back(I.getSuccessorIndex());
 311
 312   // Return false here so that edge weights for InvokeInst could be decided
 313   // in calcInvokeHeuristics().
 314   if (isa<InvokeInst>(TI))
 315     return false;
 316
 317   // Skip probabilities if this block has a single successor.
 318   if (TI->getNumSuccessors() == 1 || ColdEdges.empty())
 319     return false;
 320
 321   if (NormalEdges.empty()) {
 322     BranchProbability Prob(1, ColdEdges.size());
 323     for (unsigned SuccIdx : ColdEdges)
 324       setEdgeProbability(BB, SuccIdx, Prob);
 325     return true;
 326   }
 327
 328   auto ColdProb = BranchProbability::getBranchProbability(
 329       CC_TAKEN_WEIGHT,
 330       (CC_TAKEN_WEIGHT + CC_NONTAKEN_WEIGHT) * uint64_t(ColdEdges.size()));
 331   auto NormalProb = BranchProbability::getBranchProbability(
 332       CC_NONTAKEN_WEIGHT,
 333       (CC_TAKEN_WEIGHT + CC_NONTAKEN_WEIGHT) * uint64_t(NormalEdges.size()));
 334
 335   for (unsigned SuccIdx : ColdEdges)
 336     setEdgeProbability(BB, SuccIdx, ColdProb);
 337   for (unsigned SuccIdx : NormalEdges)
 338     setEdgeProbability(BB, SuccIdx, NormalProb);
 339
 340   return true;
 341 }
 342
 343 // Calculate Edge Weights using "Pointer Heuristics". Predict a comparsion
 344 // between two pointer or pointer and NULL will fail.
 345 bool BranchProbabilityInfo::calcPointerHeuristics(const BasicBlock *BB) {
 346   const BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
 347   if (!BI || !BI->isConditional())
 348     return false;
 349
 350   Value *Cond = BI->getCondition();
 351   ICmpInst *CI = dyn_cast<ICmpInst>(Cond);
 352   if (!CI || !CI->isEquality())
 353     return false;
 354
 355   Value *LHS = CI->getOperand(0);
 356
 357   if (!LHS->getType()->isPointerTy())
 358     return false;
 359
 360   assert(CI->getOperand(1)->getType()->isPointerTy());
 361
 362   // p != 0   ->   isProb = true
 363   // p == 0   ->   isProb = false
 364   // p != q   ->   isProb = true
 365   // p == q   ->   isProb = false;
 366   unsigned TakenIdx = 0, NonTakenIdx = 1;
 367   bool isProb = CI->getPredicate() == ICmpInst::ICMP_NE;
 368   if (!isProb)
 369     std::swap(TakenIdx, NonTakenIdx);
 370
 371   BranchProbability TakenProb(PH_TAKEN_WEIGHT,
 372                               PH_TAKEN_WEIGHT + PH_NONTAKEN_WEIGHT);
 373   setEdgeProbability(BB, TakenIdx, TakenProb);
 374   setEdgeProbability(BB, NonTakenIdx, TakenProb.getCompl());
 375   return true;
 376 }
 377
 378 // Calculate Edge Weights using "Loop Branch Heuristics". Predict backedges
 379 // as taken, exiting edges as not-taken.
 380 bool BranchProbabilityInfo::calcLoopBranchHeuristics(const BasicBlock *BB,
 381                                                      const LoopInfo &LI) {
 382   Loop *L = LI.getLoopFor(BB);
 383   if (!L)
 384     return false;
 385
 386   SmallVector<unsigned, 8> BackEdges;
 387   SmallVector<unsigned, 8> ExitingEdges;
 388   SmallVector<unsigned, 8> InEdges; // Edges from header to the loop.
 389
 390   for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
 391     if (!L->contains(*I))
 392       ExitingEdges.push_back(I.getSuccessorIndex());
 393     else if (L->getHeader() == *I)
 394       BackEdges.push_back(I.getSuccessorIndex());
 395     else
 396       InEdges.push_back(I.getSuccessorIndex());
 397   }
 398
 399   if (BackEdges.empty() && ExitingEdges.empty())
 400     return false;
 401
 402   // Collect the sum of probabilities of back-edges/in-edges/exiting-edges, and
 403   // normalize them so that they sum up to one.
 404   BranchProbability Probs[] = {BranchProbability::getZero(),
 405                                BranchProbability::getZero(),
 406                                BranchProbability::getZero()};
 407   unsigned Denom = (BackEdges.empty() ? 0 : LBH_TAKEN_WEIGHT) +
 408                    (InEdges.empty() ? 0 : LBH_TAKEN_WEIGHT) +
 409                    (ExitingEdges.empty() ? 0 : LBH_NONTAKEN_WEIGHT);
 410   if (!BackEdges.empty())
 411     Probs[0] = BranchProbability(LBH_TAKEN_WEIGHT, Denom);
 412   if (!InEdges.empty())
 413     Probs[1] = BranchProbability(LBH_TAKEN_WEIGHT, Denom);
 414   if (!ExitingEdges.empty())
 415     Probs[2] = BranchProbability(LBH_NONTAKEN_WEIGHT, Denom);
 416
 417   if (uint32_t numBackEdges = BackEdges.size()) {
 418     auto Prob = Probs[0] / numBackEdges;
 419     for (unsigned SuccIdx : BackEdges)
 420       setEdgeProbability(BB, SuccIdx, Prob);
 421   }
 422
 423   if (uint32_t numInEdges = InEdges.size()) {
 424     auto Prob = Probs[1] / numInEdges;
 425     for (unsigned SuccIdx : InEdges)
 426       setEdgeProbability(BB, SuccIdx, Prob);
 427   }
 428
 429   if (uint32_t numExitingEdges = ExitingEdges.size()) {
 430     auto Prob = Probs[2] / numExitingEdges;
 431     for (unsigned SuccIdx : ExitingEdges)
 432       setEdgeProbability(BB, SuccIdx, Prob);
 433   }
 434
 435   return true;
 436 }
 437
 438 bool BranchProbabilityInfo::calcZeroHeuristics(const BasicBlock *BB) {
 439   const BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
 440   if (!BI || !BI->isConditional())
 441     return false;
 442
 443   Value *Cond = BI->getCondition();
 444   ICmpInst *CI = dyn_cast<ICmpInst>(Cond);
 445   if (!CI)
 446     return false;
 447
 448   Value *RHS = CI->getOperand(1);
 449   ConstantInt *CV = dyn_cast<ConstantInt>(RHS);
 450   if (!CV)
 451     return false;
 452
 453   // If the LHS is the result of AND'ing a value with a single bit bitmask,
 454   // we don't have information about probabilities.
 455   if (Instruction *LHS = dyn_cast<Instruction>(CI->getOperand(0)))
 456     if (LHS->getOpcode() == Instruction::And)
 457       if (ConstantInt *AndRHS = dyn_cast<ConstantInt>(LHS->getOperand(1)))
 458         if (AndRHS->getUniqueInteger().isPowerOf2())
 459           return false;
 460
 461   bool isProb;
 462   if (CV->isZero()) {
 463     switch (CI->getPredicate()) {
 464     case CmpInst::ICMP_EQ:
 465       // X == 0   ->  Unlikely
 466       isProb = false;
 467       break;
 468     case CmpInst::ICMP_NE:
 469       // X != 0   ->  Likely
 470       isProb = true;
 471       break;
 472     case CmpInst::ICMP_SLT:
 473       // X < 0   ->  Unlikely
 474       isProb = false;
 475       break;
 476     case CmpInst::ICMP_SGT:
 477       // X > 0   ->  Likely
 478       isProb = true;
 479       break;
 480     default:
 481       return false;
 482     }
 483   } else if (CV->isOne() && CI->getPredicate() == CmpInst::ICMP_SLT) {
 484     // InstCombine canonicalizes X <= 0 into X < 1.
 485     // X <= 0   ->  Unlikely
 486     isProb = false;
 487   } else if (CV->isAllOnesValue()) {
 488     switch (CI->getPredicate()) {
 489     case CmpInst::ICMP_EQ:
 490       // X == -1  ->  Unlikely
 491       isProb = false;
 492       break;
 493     case CmpInst::ICMP_NE:
 494       // X != -1  ->  Likely
 495       isProb = true;
 496       break;
 497     case CmpInst::ICMP_SGT:
 498       // InstCombine canonicalizes X >= 0 into X > -1.
 499       // X >= 0   ->  Likely
 500       isProb = true;
 501       break;
 502     default:
 503       return false;
 504     }
 505   } else {
 506     return false;
 507   }
 508
 509   unsigned TakenIdx = 0, NonTakenIdx = 1;
 510
 511   if (!isProb)
 512     std::swap(TakenIdx, NonTakenIdx);
 513
 514   BranchProbability TakenProb(ZH_TAKEN_WEIGHT,
 515                               ZH_TAKEN_WEIGHT + ZH_NONTAKEN_WEIGHT);
 516   setEdgeProbability(BB, TakenIdx, TakenProb);
 517   setEdgeProbability(BB, NonTakenIdx, TakenProb.getCompl());
 518   return true;
 519 }
 520
 521 bool BranchProbabilityInfo::calcFloatingPointHeuristics(const BasicBlock *BB) {
 522   const BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
 523   if (!BI || !BI->isConditional())
 524     return false;
 525
 526   Value *Cond = BI->getCondition();
 527   FCmpInst *FCmp = dyn_cast<FCmpInst>(Cond);
 528   if (!FCmp)
 529     return false;
 530
 531   bool isProb;
 532   if (FCmp->isEquality()) {
 533     // f1 == f2 -> Unlikely
 534     // f1 != f2 -> Likely
 535     isProb = !FCmp->isTrueWhenEqual();
 536   } else if (FCmp->getPredicate() == FCmpInst::FCMP_ORD) {
 537     // !isnan -> Likely
 538     isProb = true;
 539   } else if (FCmp->getPredicate() == FCmpInst::FCMP_UNO) {
 540     // isnan -> Unlikely
 541     isProb = false;
 542   } else {
 543     return false;
 544   }
 545
 546   unsigned TakenIdx = 0, NonTakenIdx = 1;
 547
 548   if (!isProb)
 549     std::swap(TakenIdx, NonTakenIdx);
 550
 551   BranchProbability TakenProb(FPH_TAKEN_WEIGHT,
 552                               FPH_TAKEN_WEIGHT + FPH_NONTAKEN_WEIGHT);
 553   setEdgeProbability(BB, TakenIdx, TakenProb);
 554   setEdgeProbability(BB, NonTakenIdx, TakenProb.getCompl());
 555   return true;
 556 }
 557
 558 bool BranchProbabilityInfo::calcInvokeHeuristics(const BasicBlock *BB) {
 559   const InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator());
 560   if (!II)
 561     return false;
 562
 563   BranchProbability TakenProb(IH_TAKEN_WEIGHT,
 564                               IH_TAKEN_WEIGHT + IH_NONTAKEN_WEIGHT);
 565   setEdgeProbability(BB, 0 /*Index for Normal*/, TakenProb);
 566   setEdgeProbability(BB, 1 /*Index for Unwind*/, TakenProb.getCompl());
 567   return true;
 568 }
 569
 570 void BranchProbabilityInfo::releaseMemory() {
 571   Probs.clear();
 572 }
 573
 574 void BranchProbabilityInfo::print(raw_ostream &OS) const {
 575   OS << "---- Branch Probabilities ----\n";
 576   // We print the probabilities from the last function the analysis ran over,
 577   // or the function it is currently running over.
 578   assert(LastF && "Cannot print prior to running over a function");
 579   for (const auto &BI : *LastF) {
 580     for (succ_const_iterator SI = succ_begin(&BI), SE = succ_end(&BI); SI != SE;
 581          ++SI) {
 582       printEdgeProbability(OS << "  ", &BI, *SI);
 583     }
 584   }
 585 }
 586
 587 bool BranchProbabilityInfo::
 588 isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const {
 589   // Hot probability is at least 4/5 = 80%
 590   // FIXME: Compare against a static "hot" BranchProbability.
 591   return getEdgeProbability(Src, Dst) > BranchProbability(4, 5);
 592 }
 593
 594 const BasicBlock *
 595 BranchProbabilityInfo::getHotSucc(const BasicBlock *BB) const {
 596   auto MaxProb = BranchProbability::getZero();
 597   const BasicBlock *MaxSucc = nullptr;
 598
 599   for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
 600     const BasicBlock *Succ = *I;
 601     auto Prob = getEdgeProbability(BB, Succ);
 602     if (Prob > MaxProb) {
 603       MaxProb = Prob;
 604       MaxSucc = Succ;
 605     }
 606   }
 607
 608   // Hot probability is at least 4/5 = 80%
 609   if (MaxProb > BranchProbability(4, 5))
 610     return MaxSucc;
 611
 612   return nullptr;
 613 }
 614
 615 /// Get the raw edge probability for the edge. If can't find it, return a
 616 /// default probability 1/N where N is the number of successors. Here an edge is
 617 /// specified using PredBlock and an
 618 /// index to the successors.
 619 BranchProbability
 620 BranchProbabilityInfo::getEdgeProbability(const BasicBlock *Src,
 621                                           unsigned IndexInSuccessors) const {
 622   auto I = Probs.find(std::make_pair(Src, IndexInSuccessors));
 623
 624   if (I != Probs.end())
 625     return I->second;
 626
 627   return {1,
 628           static_cast<uint32_t>(std::distance(succ_begin(Src), succ_end(Src)))};
 629 }
 630
 631 BranchProbability
 632 BranchProbabilityInfo::getEdgeProbability(const BasicBlock *Src,
 633                                           succ_const_iterator Dst) const {
 634   return getEdgeProbability(Src, Dst.getSuccessorIndex());
 635 }
 636
 637 /// Get the raw edge probability calculated for the block pair. This returns the
 638 /// sum of all raw edge probabilities from Src to Dst.
 639 BranchProbability
 640 BranchProbabilityInfo::getEdgeProbability(const BasicBlock *Src,
 641                                           const BasicBlock *Dst) const {
 642   auto Prob = BranchProbability::getZero();
 643   bool FoundProb = false;
 644   for (succ_const_iterator I = succ_begin(Src), E = succ_end(Src); I != E; ++I)
 645     if (*I == Dst) {
 646       auto MapI = Probs.find(std::make_pair(Src, I.getSuccessorIndex()));
 647       if (MapI != Probs.end()) {
 648         FoundProb = true;
 649         Prob += MapI->second;
 650       }
 651     }
 652   uint32_t succ_num = std::distance(succ_begin(Src), succ_end(Src));
 653   return FoundProb ? Prob : BranchProbability(1, succ_num);
 654 }
 655
 656 /// Set the edge probability for a given edge specified by PredBlock and an
 657 /// index to the successors.
 658 void BranchProbabilityInfo::setEdgeProbability(const BasicBlock *Src,
 659                                                unsigned IndexInSuccessors,
 660                                                BranchProbability Prob) {
 661   Probs[std::make_pair(Src, IndexInSuccessors)] = Prob;
 662   Handles.insert(BasicBlockCallbackVH(Src, this));
 663   DEBUG(dbgs() << "set edge " << Src->getName() << " -> " << IndexInSuccessors
 664                << " successor probability to " << Prob << "\n");
 665 }
 666
 667 raw_ostream &
 668 BranchProbabilityInfo::printEdgeProbability(raw_ostream &OS,
 669                                             const BasicBlock *Src,
 670                                             const BasicBlock *Dst) const {
 671
 672   const BranchProbability Prob = getEdgeProbability(Src, Dst);
 673   OS << "edge " << Src->getName() << " -> " << Dst->getName()
 674      << " probability is " << Prob
 675      << (isEdgeHot(Src, Dst) ? " [HOT edge]\n" : "\n");
 676
 677   return OS;
 678 }
 679
 680 void BranchProbabilityInfo::eraseBlock(const BasicBlock *BB) {
 681   for (auto I = Probs.begin(), E = Probs.end(); I != E; ++I) {
 682     auto Key = I->first;
 683     if (Key.first == BB)
 684       Probs.erase(Key);
 685   }
 686 }
 687
 688 void BranchProbabilityInfo::calculate(const Function &F, const LoopInfo &LI) {
 689   DEBUG(dbgs() << "---- Branch Probability Info : " << F.getName()
 690                << " ----\n\n");
 691   LastF = &F; // Store the last function we ran on for printing.
 692   assert(PostDominatedByUnreachable.empty());
 693   assert(PostDominatedByColdCall.empty());
 694
 695   // Walk the basic blocks in post-order so that we can build up state about
 696   // the successors of a block iteratively.
 697   for (auto BB : post_order(&F.getEntryBlock())) {
 698     DEBUG(dbgs() << "Computing probabilities for " << BB->getName() << "\n");
 699     updatePostDominatedByUnreachable(BB);
 700     updatePostDominatedByColdCall(BB);
 701     if (calcUnreachableHeuristics(BB))
 702       continue;
 703     if (calcMetadataWeights(BB))
 704       continue;
 705     if (calcColdCallHeuristics(BB))
 706       continue;
 707     if (calcLoopBranchHeuristics(BB, LI))
 708       continue;
 709     if (calcPointerHeuristics(BB))
 710       continue;
 711     if (calcZeroHeuristics(BB))
 712       continue;
 713     if (calcFloatingPointHeuristics(BB))
 714       continue;
 715     calcInvokeHeuristics(BB);
 716   }
 717
 718   PostDominatedByUnreachable.clear();
 719   PostDominatedByColdCall.clear();
 720 }
 721
 722 void BranchProbabilityInfoWrapperPass::getAnalysisUsage(
 723     AnalysisUsage &AU) const {
 724   AU.addRequired<LoopInfoWrapperPass>();
 725   AU.setPreservesAll();
 726 }
 727
 728 bool BranchProbabilityInfoWrapperPass::runOnFunction(Function &F) {
 729   const LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
 730   BPI.calculate(F, LI);
 731   return false;
 732 }
 733
 734 void BranchProbabilityInfoWrapperPass::releaseMemory() { BPI.releaseMemory(); }
 735
 736 void BranchProbabilityInfoWrapperPass::print(raw_ostream &OS,
 737                                              const Module *) const {
 738   BPI.print(OS);
 739 }
 740
 741 AnalysisKey BranchProbabilityAnalysis::Key;
 742 BranchProbabilityInfo
 743 BranchProbabilityAnalysis::run(Function &F, FunctionAnalysisManager &AM) {
 744   BranchProbabilityInfo BPI;
 745   BPI.calculate(F, AM.getResult<LoopAnalysis>(F));
 746   return BPI;
 747 }
 748
 749 PreservedAnalyses
 750 BranchProbabilityPrinterPass::run(Function &F, FunctionAnalysisManager &AM) {
 751   OS << "Printing analysis results of BPI for function "
 752      << "'" << F.getName() << "':"
 753      << "\n";
 754   AM.getResult<BranchProbabilityAnalysis>(F).print(OS);
 755   return PreservedAnalyses::all();
 756 }