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   assert(WeightSum <= UINT32_MAX &&
 305          "Expected weights to scale down to 32 bits");
 306
 307   if (WeightSum == 0 || ReachableIdxs.size() == 0) {
 308     for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
 309       Weights[i] = 1;
 310     WeightSum = TI->getNumSuccessors();
 311   }
 312
 313   // Set the probability.
 314   SmallVector<BranchProbability, 2> BP;
 315   for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
 316     BP.push_back({ Weights[i], static_cast<uint32_t>(WeightSum) });
 317
 318   // Examine the metadata against unreachable heuristic.
 319   // If the unreachable heuristic is more strong then we use it for this edge.
 320   if (UnreachableIdxs.size() > 0 && ReachableIdxs.size() > 0) {
 321     auto ToDistribute = BranchProbability::getZero();
 322     auto UnreachableProb = getUnreachableProbability(UnreachableIdxs.size());
 323     for (auto i : UnreachableIdxs)
 324       if (UnreachableProb < BP[i]) {
 325         ToDistribute += BP[i] - UnreachableProb;
 326         BP[i] = UnreachableProb;
 327       }
 328
 329     // If we modified the probability of some edges then we must distribute
 330     // the difference between reachable blocks.
 331     if (ToDistribute > BranchProbability::getZero()) {
 332       BranchProbability PerEdge = ToDistribute / ReachableIdxs.size();
 333       for (auto i : ReachableIdxs)
 334         BP[i] += PerEdge;
 335     }
 336   }
 337
 338   for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
 339     setEdgeProbability(BB, i, BP[i]);
 340
 341   return true;
 342 }
 343
 344 /// \brief Calculate edge weights for edges leading to cold blocks.
 345 ///
 346 /// A cold block is one post-dominated by  a block with a call to a
 347 /// cold function.  Those edges are unlikely to be taken, so we give
 348 /// them relatively low weight.
 349 ///
 350 /// Return true if we could compute the weights for cold edges.
 351 /// Return false, otherwise.
 352 bool BranchProbabilityInfo::calcColdCallHeuristics(const BasicBlock *BB) {
 353   const TerminatorInst *TI = BB->getTerminator();
 354   assert(TI->getNumSuccessors() > 1 && "expected more than one successor!");
 355
 356   // Return false here so that edge weights for InvokeInst could be decided
 357   // in calcInvokeHeuristics().
 358   if (isa<InvokeInst>(TI))
 359     return false;
 360
 361   // Determine which successors are post-dominated by a cold block.
 362   SmallVector<unsigned, 4> ColdEdges;
 363   SmallVector<unsigned, 4> NormalEdges;
 364   for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I)
 365     if (PostDominatedByColdCall.count(*I))
 366       ColdEdges.push_back(I.getSuccessorIndex());
 367     else
 368       NormalEdges.push_back(I.getSuccessorIndex());
 369
 370   // Skip probabilities if no cold edges.
 371   if (ColdEdges.empty())
 372     return false;
 373
 374   if (NormalEdges.empty()) {
 375     BranchProbability Prob(1, ColdEdges.size());
 376     for (unsigned SuccIdx : ColdEdges)
 377       setEdgeProbability(BB, SuccIdx, Prob);
 378     return true;
 379   }
 380
 381   auto ColdProb = BranchProbability::getBranchProbability(
 382       CC_TAKEN_WEIGHT,
 383       (CC_TAKEN_WEIGHT + CC_NONTAKEN_WEIGHT) * uint64_t(ColdEdges.size()));
 384   auto NormalProb = BranchProbability::getBranchProbability(
 385       CC_NONTAKEN_WEIGHT,
 386       (CC_TAKEN_WEIGHT + CC_NONTAKEN_WEIGHT) * uint64_t(NormalEdges.size()));
 387
 388   for (unsigned SuccIdx : ColdEdges)
 389     setEdgeProbability(BB, SuccIdx, ColdProb);
 390   for (unsigned SuccIdx : NormalEdges)
 391     setEdgeProbability(BB, SuccIdx, NormalProb);
 392
 393   return true;
 394 }
 395
 396 // Calculate Edge Weights using "Pointer Heuristics". Predict a comparsion
 397 // between two pointer or pointer and NULL will fail.
 398 bool BranchProbabilityInfo::calcPointerHeuristics(const BasicBlock *BB) {
 399   const BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
 400   if (!BI || !BI->isConditional())
 401     return false;
 402
 403   Value *Cond = BI->getCondition();
 404   ICmpInst *CI = dyn_cast<ICmpInst>(Cond);
 405   if (!CI || !CI->isEquality())
 406     return false;
 407
 408   Value *LHS = CI->getOperand(0);
 409
 410   if (!LHS->getType()->isPointerTy())
 411     return false;
 412
 413   assert(CI->getOperand(1)->getType()->isPointerTy());
 414
 415   // p != 0   ->   isProb = true
 416   // p == 0   ->   isProb = false
 417   // p != q   ->   isProb = true
 418   // p == q   ->   isProb = false;
 419   unsigned TakenIdx = 0, NonTakenIdx = 1;
 420   bool isProb = CI->getPredicate() == ICmpInst::ICMP_NE;
 421   if (!isProb)
 422     std::swap(TakenIdx, NonTakenIdx);
 423
 424   BranchProbability TakenProb(PH_TAKEN_WEIGHT,
 425                               PH_TAKEN_WEIGHT + PH_NONTAKEN_WEIGHT);
 426   setEdgeProbability(BB, TakenIdx, TakenProb);
 427   setEdgeProbability(BB, NonTakenIdx, TakenProb.getCompl());
 428   return true;
 429 }
 430
 431 // Calculate Edge Weights using "Loop Branch Heuristics". Predict backedges
 432 // as taken, exiting edges as not-taken.
 433 bool BranchProbabilityInfo::calcLoopBranchHeuristics(const BasicBlock *BB,
 434                                                      const LoopInfo &LI) {
 435   Loop *L = LI.getLoopFor(BB);
 436   if (!L)
 437     return false;
 438
 439   SmallVector<unsigned, 8> BackEdges;
 440   SmallVector<unsigned, 8> ExitingEdges;
 441   SmallVector<unsigned, 8> InEdges; // Edges from header to the loop.
 442
 443   for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
 444     if (!L->contains(*I))
 445       ExitingEdges.push_back(I.getSuccessorIndex());
 446     else if (L->getHeader() == *I)
 447       BackEdges.push_back(I.getSuccessorIndex());
 448     else
 449       InEdges.push_back(I.getSuccessorIndex());
 450   }
 451
 452   if (BackEdges.empty() && ExitingEdges.empty())
 453     return false;
 454
 455   // Collect the sum of probabilities of back-edges/in-edges/exiting-edges, and
 456   // normalize them so that they sum up to one.
 457   BranchProbability Probs[] = {BranchProbability::getZero(),
 458                                BranchProbability::getZero(),
 459                                BranchProbability::getZero()};
 460   unsigned Denom = (BackEdges.empty() ? 0 : LBH_TAKEN_WEIGHT) +
 461                    (InEdges.empty() ? 0 : LBH_TAKEN_WEIGHT) +
 462                    (ExitingEdges.empty() ? 0 : LBH_NONTAKEN_WEIGHT);
 463   if (!BackEdges.empty())
 464     Probs[0] = BranchProbability(LBH_TAKEN_WEIGHT, Denom);
 465   if (!InEdges.empty())
 466     Probs[1] = BranchProbability(LBH_TAKEN_WEIGHT, Denom);
 467   if (!ExitingEdges.empty())
 468     Probs[2] = BranchProbability(LBH_NONTAKEN_WEIGHT, Denom);
 469
 470   if (uint32_t numBackEdges = BackEdges.size()) {
 471     auto Prob = Probs[0] / numBackEdges;
 472     for (unsigned SuccIdx : BackEdges)
 473       setEdgeProbability(BB, SuccIdx, Prob);
 474   }
 475
 476   if (uint32_t numInEdges = InEdges.size()) {
 477     auto Prob = Probs[1] / numInEdges;
 478     for (unsigned SuccIdx : InEdges)
 479       setEdgeProbability(BB, SuccIdx, Prob);
 480   }
 481
 482   if (uint32_t numExitingEdges = ExitingEdges.size()) {
 483     auto Prob = Probs[2] / numExitingEdges;
 484     for (unsigned SuccIdx : ExitingEdges)
 485       setEdgeProbability(BB, SuccIdx, Prob);
 486   }
 487
 488   return true;
 489 }
 490
 491 bool BranchProbabilityInfo::calcZeroHeuristics(const BasicBlock *BB) {
 492   const BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
 493   if (!BI || !BI->isConditional())
 494     return false;
 495
 496   Value *Cond = BI->getCondition();
 497   ICmpInst *CI = dyn_cast<ICmpInst>(Cond);
 498   if (!CI)
 499     return false;
 500
 501   Value *RHS = CI->getOperand(1);
 502   ConstantInt *CV = dyn_cast<ConstantInt>(RHS);
 503   if (!CV)
 504     return false;
 505
 506   // If the LHS is the result of AND'ing a value with a single bit bitmask,
 507   // we don't have information about probabilities.
 508   if (Instruction *LHS = dyn_cast<Instruction>(CI->getOperand(0)))
 509     if (LHS->getOpcode() == Instruction::And)
 510       if (ConstantInt *AndRHS = dyn_cast<ConstantInt>(LHS->getOperand(1)))
 511         if (AndRHS->getUniqueInteger().isPowerOf2())
 512           return false;
 513
 514   bool isProb;
 515   if (CV->isZero()) {
 516     switch (CI->getPredicate()) {
 517     case CmpInst::ICMP_EQ:
 518       // X == 0   ->  Unlikely
 519       isProb = false;
 520       break;
 521     case CmpInst::ICMP_NE:
 522       // X != 0   ->  Likely
 523       isProb = true;
 524       break;
 525     case CmpInst::ICMP_SLT:
 526       // X < 0   ->  Unlikely
 527       isProb = false;
 528       break;
 529     case CmpInst::ICMP_SGT:
 530       // X > 0   ->  Likely
 531       isProb = true;
 532       break;
 533     default:
 534       return false;
 535     }
 536   } else if (CV->isOne() && CI->getPredicate() == CmpInst::ICMP_SLT) {
 537     // InstCombine canonicalizes X <= 0 into X < 1.
 538     // X <= 0   ->  Unlikely
 539     isProb = false;
 540   } else if (CV->isAllOnesValue()) {
 541     switch (CI->getPredicate()) {
 542     case CmpInst::ICMP_EQ:
 543       // X == -1  ->  Unlikely
 544       isProb = false;
 545       break;
 546     case CmpInst::ICMP_NE:
 547       // X != -1  ->  Likely
 548       isProb = true;
 549       break;
 550     case CmpInst::ICMP_SGT:
 551       // InstCombine canonicalizes X >= 0 into X > -1.
 552       // X >= 0   ->  Likely
 553       isProb = true;
 554       break;
 555     default:
 556       return false;
 557     }
 558   } else {
 559     return false;
 560   }
 561
 562   unsigned TakenIdx = 0, NonTakenIdx = 1;
 563
 564   if (!isProb)
 565     std::swap(TakenIdx, NonTakenIdx);
 566
 567   BranchProbability TakenProb(ZH_TAKEN_WEIGHT,
 568                               ZH_TAKEN_WEIGHT + ZH_NONTAKEN_WEIGHT);
 569   setEdgeProbability(BB, TakenIdx, TakenProb);
 570   setEdgeProbability(BB, NonTakenIdx, TakenProb.getCompl());
 571   return true;
 572 }
 573
 574 bool BranchProbabilityInfo::calcFloatingPointHeuristics(const BasicBlock *BB) {
 575   const BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
 576   if (!BI || !BI->isConditional())
 577     return false;
 578
 579   Value *Cond = BI->getCondition();
 580   FCmpInst *FCmp = dyn_cast<FCmpInst>(Cond);
 581   if (!FCmp)
 582     return false;
 583
 584   bool isProb;
 585   if (FCmp->isEquality()) {
 586     // f1 == f2 -> Unlikely
 587     // f1 != f2 -> Likely
 588     isProb = !FCmp->isTrueWhenEqual();
 589   } else if (FCmp->getPredicate() == FCmpInst::FCMP_ORD) {
 590     // !isnan -> Likely
 591     isProb = true;
 592   } else if (FCmp->getPredicate() == FCmpInst::FCMP_UNO) {
 593     // isnan -> Unlikely
 594     isProb = false;
 595   } else {
 596     return false;
 597   }
 598
 599   unsigned TakenIdx = 0, NonTakenIdx = 1;
 600
 601   if (!isProb)
 602     std::swap(TakenIdx, NonTakenIdx);
 603
 604   BranchProbability TakenProb(FPH_TAKEN_WEIGHT,
 605                               FPH_TAKEN_WEIGHT + FPH_NONTAKEN_WEIGHT);
 606   setEdgeProbability(BB, TakenIdx, TakenProb);
 607   setEdgeProbability(BB, NonTakenIdx, TakenProb.getCompl());
 608   return true;
 609 }
 610
 611 bool BranchProbabilityInfo::calcInvokeHeuristics(const BasicBlock *BB) {
 612   const InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator());
 613   if (!II)
 614     return false;
 615
 616   BranchProbability TakenProb(IH_TAKEN_WEIGHT,
 617                               IH_TAKEN_WEIGHT + IH_NONTAKEN_WEIGHT);
 618   setEdgeProbability(BB, 0 /*Index for Normal*/, TakenProb);
 619   setEdgeProbability(BB, 1 /*Index for Unwind*/, TakenProb.getCompl());
 620   return true;
 621 }
 622
 623 void BranchProbabilityInfo::releaseMemory() {
 624   Probs.clear();
 625 }
 626
 627 void BranchProbabilityInfo::print(raw_ostream &OS) const {
 628   OS << "---- Branch Probabilities ----\n";
 629   // We print the probabilities from the last function the analysis ran over,
 630   // or the function it is currently running over.
 631   assert(LastF && "Cannot print prior to running over a function");
 632   for (const auto &BI : *LastF) {
 633     for (succ_const_iterator SI = succ_begin(&BI), SE = succ_end(&BI); SI != SE;
 634          ++SI) {
 635       printEdgeProbability(OS << "  ", &BI, *SI);
 636     }
 637   }
 638 }
 639
 640 bool BranchProbabilityInfo::
 641 isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const {
 642   // Hot probability is at least 4/5 = 80%
 643   // FIXME: Compare against a static "hot" BranchProbability.
 644   return getEdgeProbability(Src, Dst) > BranchProbability(4, 5);
 645 }
 646
 647 const BasicBlock *
 648 BranchProbabilityInfo::getHotSucc(const BasicBlock *BB) const {
 649   auto MaxProb = BranchProbability::getZero();
 650   const BasicBlock *MaxSucc = nullptr;
 651
 652   for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
 653     const BasicBlock *Succ = *I;
 654     auto Prob = getEdgeProbability(BB, Succ);
 655     if (Prob > MaxProb) {
 656       MaxProb = Prob;
 657       MaxSucc = Succ;
 658     }
 659   }
 660
 661   // Hot probability is at least 4/5 = 80%
 662   if (MaxProb > BranchProbability(4, 5))
 663     return MaxSucc;
 664
 665   return nullptr;
 666 }
 667
 668 /// Get the raw edge probability for the edge. If can't find it, return a
 669 /// default probability 1/N where N is the number of successors. Here an edge is
 670 /// specified using PredBlock and an
 671 /// index to the successors.
 672 BranchProbability
 673 BranchProbabilityInfo::getEdgeProbability(const BasicBlock *Src,
 674                                           unsigned IndexInSuccessors) const {
 675   auto I = Probs.find(std::make_pair(Src, IndexInSuccessors));
 676
 677   if (I != Probs.end())
 678     return I->second;
 679
 680   return {1,
 681           static_cast<uint32_t>(std::distance(succ_begin(Src), succ_end(Src)))};
 682 }
 683
 684 BranchProbability
 685 BranchProbabilityInfo::getEdgeProbability(const BasicBlock *Src,
 686                                           succ_const_iterator Dst) const {
 687   return getEdgeProbability(Src, Dst.getSuccessorIndex());
 688 }
 689
 690 /// Get the raw edge probability calculated for the block pair. This returns the
 691 /// sum of all raw edge probabilities from Src to Dst.
 692 BranchProbability
 693 BranchProbabilityInfo::getEdgeProbability(const BasicBlock *Src,
 694                                           const BasicBlock *Dst) const {
 695   auto Prob = BranchProbability::getZero();
 696   bool FoundProb = false;
 697   for (succ_const_iterator I = succ_begin(Src), E = succ_end(Src); I != E; ++I)
 698     if (*I == Dst) {
 699       auto MapI = Probs.find(std::make_pair(Src, I.getSuccessorIndex()));
 700       if (MapI != Probs.end()) {
 701         FoundProb = true;
 702         Prob += MapI->second;
 703       }
 704     }
 705   uint32_t succ_num = std::distance(succ_begin(Src), succ_end(Src));
 706   return FoundProb ? Prob : BranchProbability(1, succ_num);
 707 }
 708
 709 /// Set the edge probability for a given edge specified by PredBlock and an
 710 /// index to the successors.
 711 void BranchProbabilityInfo::setEdgeProbability(const BasicBlock *Src,
 712                                                unsigned IndexInSuccessors,
 713                                                BranchProbability Prob) {
 714   Probs[std::make_pair(Src, IndexInSuccessors)] = Prob;
 715   Handles.insert(BasicBlockCallbackVH(Src, this));
 716   DEBUG(dbgs() << "set edge " << Src->getName() << " -> " << IndexInSuccessors
 717                << " successor probability to " << Prob << "\n");
 718 }
 719
 720 raw_ostream &
 721 BranchProbabilityInfo::printEdgeProbability(raw_ostream &OS,
 722                                             const BasicBlock *Src,
 723                                             const BasicBlock *Dst) const {
 724
 725   const BranchProbability Prob = getEdgeProbability(Src, Dst);
 726   OS << "edge " << Src->getName() << " -> " << Dst->getName()
 727      << " probability is " << Prob
 728      << (isEdgeHot(Src, Dst) ? " [HOT edge]\n" : "\n");
 729
 730   return OS;
 731 }
 732
 733 void BranchProbabilityInfo::eraseBlock(const BasicBlock *BB) {
 734   for (auto I = Probs.begin(), E = Probs.end(); I != E; ++I) {
 735     auto Key = I->first;
 736     if (Key.first == BB)
 737       Probs.erase(Key);
 738   }
 739 }
 740
 741 void BranchProbabilityInfo::calculate(const Function &F, const LoopInfo &LI) {
 742   DEBUG(dbgs() << "---- Branch Probability Info : " << F.getName()
 743                << " ----\n\n");
 744   LastF = &F; // Store the last function we ran on for printing.
 745   assert(PostDominatedByUnreachable.empty());
 746   assert(PostDominatedByColdCall.empty());
 747
 748   // Walk the basic blocks in post-order so that we can build up state about
 749   // the successors of a block iteratively.
 750   for (auto BB : post_order(&F.getEntryBlock())) {
 751     DEBUG(dbgs() << "Computing probabilities for " << BB->getName() << "\n");
 752     updatePostDominatedByUnreachable(BB);
 753     updatePostDominatedByColdCall(BB);
 754     // If there is no at least two successors, no sense to set probability.
 755     if (BB->getTerminator()->getNumSuccessors() < 2)
 756       continue;
 757     if (calcMetadataWeights(BB))
 758       continue;
 759     if (calcUnreachableHeuristics(BB))
 760       continue;
 761     if (calcColdCallHeuristics(BB))
 762       continue;
 763     if (calcLoopBranchHeuristics(BB, LI))
 764       continue;
 765     if (calcPointerHeuristics(BB))
 766       continue;
 767     if (calcZeroHeuristics(BB))
 768       continue;
 769     if (calcFloatingPointHeuristics(BB))
 770       continue;
 771     calcInvokeHeuristics(BB);
 772   }
 773
 774   PostDominatedByUnreachable.clear();
 775   PostDominatedByColdCall.clear();
 776 }
 777
 778 void BranchProbabilityInfoWrapperPass::getAnalysisUsage(
 779     AnalysisUsage &AU) const {
 780   AU.addRequired<LoopInfoWrapperPass>();
 781   AU.setPreservesAll();
 782 }
 783
 784 bool BranchProbabilityInfoWrapperPass::runOnFunction(Function &F) {
 785   const LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
 786   BPI.calculate(F, LI);
 787   return false;
 788 }
 789
 790 void BranchProbabilityInfoWrapperPass::releaseMemory() { BPI.releaseMemory(); }
 791
 792 void BranchProbabilityInfoWrapperPass::print(raw_ostream &OS,
 793                                              const Module *) const {
 794   BPI.print(OS);
 795 }
 796
 797 AnalysisKey BranchProbabilityAnalysis::Key;
 798 BranchProbabilityInfo
 799 BranchProbabilityAnalysis::run(Function &F, FunctionAnalysisManager &AM) {
 800   BranchProbabilityInfo BPI;
 801   BPI.calculate(F, AM.getResult<LoopAnalysis>(F));
 802   return BPI;
 803 }
 804
 805 PreservedAnalyses
 806 BranchProbabilityPrinterPass::run(Function &F, FunctionAnalysisManager &AM) {
 807   OS << "Printing analysis results of BPI for function "
 808      << "'" << F.getName() << "':"
 809      << "\n";
 810   AM.getResult<BranchProbabilityAnalysis>(F).print(OS);
 811   return PreservedAnalyses::all();
 812 }