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