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