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/ADT/SCCIterator.h"
  17 #include "llvm/ADT/STLExtras.h"
  18 #include "llvm/ADT/SmallVector.h"
  19 #include "llvm/Analysis/LoopInfo.h"
  20 #include "llvm/Analysis/TargetLibraryInfo.h"
  21 #include "llvm/IR/Attributes.h"
  22 #include "llvm/IR/BasicBlock.h"
  23 #include "llvm/IR/CFG.h"
  24 #include "llvm/IR/Constants.h"
  25 #include "llvm/IR/Dominators.h"
  26 #include "llvm/IR/Function.h"
  27 #include "llvm/IR/InstrTypes.h"
  28 #include "llvm/IR/Instruction.h"
  29 #include "llvm/IR/Instructions.h"
  30 #include "llvm/IR/LLVMContext.h"
  31 #include "llvm/IR/Metadata.h"
  32 #include "llvm/IR/PassManager.h"
  33 #include "llvm/IR/Type.h"
  34 #include "llvm/IR/Value.h"
  35 #include "llvm/Pass.h"
  36 #include "llvm/Support/BranchProbability.h"
  37 #include "llvm/Support/Casting.h"
  38 #include "llvm/Support/Debug.h"
  39 #include "llvm/Support/raw_ostream.h"
  40 #include <cassert>
  41 #include <cstdint>
  42 #include <iterator>
  43 #include <utility>
  44
  45 using namespace llvm;
  46
  47 #define DEBUG_TYPE "branch-prob"
  48
  49 static cl::opt<bool> PrintBranchProb(
  50     "print-bpi", cl::init(false), cl::Hidden,
  51     cl::desc("Print the branch probability info."));
  52
  53 cl::opt<std::string> PrintBranchProbFuncName(
  54     "print-bpi-func-name", cl::Hidden,
  55     cl::desc("The option to specify the name of the function "
  56              "whose branch probability info is printed."));
  57
  58 INITIALIZE_PASS_BEGIN(BranchProbabilityInfoWrapperPass, "branch-prob",
  59                       "Branch Probability Analysis", false, true)
  60 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
  61 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
  62 INITIALIZE_PASS_END(BranchProbabilityInfoWrapperPass, "branch-prob",
  63                     "Branch Probability Analysis", false, true)
  64
  65 char BranchProbabilityInfoWrapperPass::ID = 0;
  66
  67 // Weights are for internal use only. They are used by heuristics to help to
  68 // estimate edges' probability. Example:
  69 //
  70 // Using "Loop Branch Heuristics" we predict weights of edges for the
  71 // block BB2.
  72 //         ...
  73 //          |
  74 //          V
  75 //         BB1<-+
  76 //          |   |
  77 //          |   | (Weight = 124)
  78 //          V   |
  79 //         BB2--+
  80 //          |
  81 //          | (Weight = 4)
  82 //          V
  83 //         BB3
  84 //
  85 // Probability of the edge BB2->BB1 = 124 / (124 + 4) = 0.96875
  86 // Probability of the edge BB2->BB3 = 4 / (124 + 4) = 0.03125
  87 static const uint32_t LBH_TAKEN_WEIGHT = 124;
  88 static const uint32_t LBH_NONTAKEN_WEIGHT = 4;
  89 // Unlikely edges within a loop are half as likely as other edges
  90 static const uint32_t LBH_UNLIKELY_WEIGHT = 62;
  91
  92 /// Unreachable-terminating branch taken probability.
  93 ///
  94 /// This is the probability for a branch being taken to a block that terminates
  95 /// (eventually) in unreachable. These are predicted as unlikely as possible.
  96 /// All reachable probability will equally share the remaining part.
  97 static const BranchProbability UR_TAKEN_PROB = BranchProbability::getRaw(1);
  98
  99 /// Weight for a branch taken going into a cold block.
 100 ///
 101 /// This is the weight for a branch taken toward a block marked
 102 /// cold.  A block is marked cold if it's postdominated by a
 103 /// block containing a call to a cold function.  Cold functions
 104 /// are those marked with attribute 'cold'.
 105 static const uint32_t CC_TAKEN_WEIGHT = 4;
 106
 107 /// Weight for a branch not-taken into a cold block.
 108 ///
 109 /// This is the weight for a branch not taken toward a block marked
 110 /// cold.
 111 static const uint32_t CC_NONTAKEN_WEIGHT = 64;
 112
 113 static const uint32_t PH_TAKEN_WEIGHT = 20;
 114 static const uint32_t PH_NONTAKEN_WEIGHT = 12;
 115
 116 static const uint32_t ZH_TAKEN_WEIGHT = 20;
 117 static const uint32_t ZH_NONTAKEN_WEIGHT = 12;
 118
 119 static const uint32_t FPH_TAKEN_WEIGHT = 20;
 120 static const uint32_t FPH_NONTAKEN_WEIGHT = 12;
 121
 122 /// Invoke-terminating normal branch taken weight
 123 ///
 124 /// This is the weight for branching to the normal destination of an invoke
 125 /// instruction. We expect this to happen most of the time. Set the weight to an
 126 /// absurdly high value so that nested loops subsume it.
 127 static const uint32_t IH_TAKEN_WEIGHT = 1024 * 1024 - 1;
 128
 129 /// Invoke-terminating normal branch not-taken weight.
 130 ///
 131 /// This is the weight for branching to the unwind destination of an invoke
 132 /// instruction. This is essentially never taken.
 133 static const uint32_t IH_NONTAKEN_WEIGHT = 1;
 134
 135 /// Add \p BB to PostDominatedByUnreachable set if applicable.
 136 void
 137 BranchProbabilityInfo::updatePostDominatedByUnreachable(const BasicBlock *BB) {
 138   const TerminatorInst *TI = BB->getTerminator();
 139   if (TI->getNumSuccessors() == 0) {
 140     if (isa<UnreachableInst>(TI) ||
 141         // If this block is terminated by a call to
 142         // @llvm.experimental.deoptimize then treat it like an unreachable since
 143         // the @llvm.experimental.deoptimize call is expected to practically
 144         // never execute.
 145         BB->getTerminatingDeoptimizeCall())
 146       PostDominatedByUnreachable.insert(BB);
 147     return;
 148   }
 149
 150   // If the terminator is an InvokeInst, check only the normal destination block
 151   // as the unwind edge of InvokeInst is also very unlikely taken.
 152   if (auto *II = dyn_cast<InvokeInst>(TI)) {
 153     if (PostDominatedByUnreachable.count(II->getNormalDest()))
 154       PostDominatedByUnreachable.insert(BB);
 155     return;
 156   }
 157
 158   for (auto *I : successors(BB))
 159     // If any of successor is not post dominated then BB is also not.
 160     if (!PostDominatedByUnreachable.count(I))
 161       return;
 162
 163   PostDominatedByUnreachable.insert(BB);
 164 }
 165
 166 /// Add \p BB to PostDominatedByColdCall set if applicable.
 167 void
 168 BranchProbabilityInfo::updatePostDominatedByColdCall(const BasicBlock *BB) {
 169   assert(!PostDominatedByColdCall.count(BB));
 170   const TerminatorInst *TI = BB->getTerminator();
 171   if (TI->getNumSuccessors() == 0)
 172     return;
 173
 174   // If all of successor are post dominated then BB is also done.
 175   if (llvm::all_of(successors(BB), [&](const BasicBlock *SuccBB) {
 176         return PostDominatedByColdCall.count(SuccBB);
 177       })) {
 178     PostDominatedByColdCall.insert(BB);
 179     return;
 180   }
 181
 182   // If the terminator is an InvokeInst, check only the normal destination
 183   // block as the unwind edge of InvokeInst is also very unlikely taken.
 184   if (auto *II = dyn_cast<InvokeInst>(TI))
 185     if (PostDominatedByColdCall.count(II->getNormalDest())) {
 186       PostDominatedByColdCall.insert(BB);
 187       return;
 188     }
 189
 190   // Otherwise, if the block itself contains a cold function, add it to the
 191   // set of blocks post-dominated by a cold call.
 192   for (auto &I : *BB)
 193     if (const CallInst *CI = dyn_cast<CallInst>(&I))
 194       if (CI->hasFnAttr(Attribute::Cold)) {
 195         PostDominatedByColdCall.insert(BB);
 196         return;
 197       }
 198 }
 199
 200 /// Calculate edge weights for successors lead to unreachable.
 201 ///
 202 /// Predict that a successor which leads necessarily to an
 203 /// unreachable-terminated block as extremely unlikely.
 204 bool BranchProbabilityInfo::calcUnreachableHeuristics(const BasicBlock *BB) {
 205   const TerminatorInst *TI = BB->getTerminator();
 206   (void) TI;
 207   assert(TI->getNumSuccessors() > 1 && "expected more than one successor!");
 208   assert(!isa<InvokeInst>(TI) &&
 209          "Invokes should have already been handled by calcInvokeHeuristics");
 210
 211   SmallVector<unsigned, 4> UnreachableEdges;
 212   SmallVector<unsigned, 4> ReachableEdges;
 213
 214   for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I)
 215     if (PostDominatedByUnreachable.count(*I))
 216       UnreachableEdges.push_back(I.getSuccessorIndex());
 217     else
 218       ReachableEdges.push_back(I.getSuccessorIndex());
 219
 220   // Skip probabilities if all were reachable.
 221   if (UnreachableEdges.empty())
 222     return false;
 223
 224   if (ReachableEdges.empty()) {
 225     BranchProbability Prob(1, UnreachableEdges.size());
 226     for (unsigned SuccIdx : UnreachableEdges)
 227       setEdgeProbability(BB, SuccIdx, Prob);
 228     return true;
 229   }
 230
 231   auto UnreachableProb = UR_TAKEN_PROB;
 232   auto ReachableProb =
 233       (BranchProbability::getOne() - UR_TAKEN_PROB * UnreachableEdges.size()) /
 234       ReachableEdges.size();
 235
 236   for (unsigned SuccIdx : UnreachableEdges)
 237     setEdgeProbability(BB, SuccIdx, UnreachableProb);
 238   for (unsigned SuccIdx : ReachableEdges)
 239     setEdgeProbability(BB, SuccIdx, ReachableProb);
 240
 241   return true;
 242 }
 243
 244 // Propagate existing explicit probabilities from either profile data or
 245 // 'expect' intrinsic processing. Examine metadata against unreachable
 246 // heuristic. The probability of the edge coming to unreachable block is
 247 // set to min of metadata and unreachable heuristic.
 248 bool BranchProbabilityInfo::calcMetadataWeights(const BasicBlock *BB) {
 249   const TerminatorInst *TI = BB->getTerminator();
 250   assert(TI->getNumSuccessors() > 1 && "expected more than one successor!");
 251   if (!(isa<BranchInst>(TI) || isa<SwitchInst>(TI) || isa<IndirectBrInst>(TI)))
 252     return false;
 253
 254   MDNode *WeightsNode = TI->getMetadata(LLVMContext::MD_prof);
 255   if (!WeightsNode)
 256     return false;
 257
 258   // Check that the number of successors is manageable.
 259   assert(TI->getNumSuccessors() < UINT32_MAX && "Too many successors");
 260
 261   // Ensure there are weights for all of the successors. Note that the first
 262   // operand to the metadata node is a name, not a weight.
 263   if (WeightsNode->getNumOperands() != TI->getNumSuccessors() + 1)
 264     return false;
 265
 266   // Build up the final weights that will be used in a temporary buffer.
 267   // Compute the sum of all weights to later decide whether they need to
 268   // be scaled to fit in 32 bits.
 269   uint64_t WeightSum = 0;
 270   SmallVector<uint32_t, 2> Weights;
 271   SmallVector<unsigned, 2> UnreachableIdxs;
 272   SmallVector<unsigned, 2> ReachableIdxs;
 273   Weights.reserve(TI->getNumSuccessors());
 274   for (unsigned i = 1, e = WeightsNode->getNumOperands(); i != e; ++i) {
 275     ConstantInt *Weight =
 276         mdconst::dyn_extract<ConstantInt>(WeightsNode->getOperand(i));
 277     if (!Weight)
 278       return false;
 279     assert(Weight->getValue().getActiveBits() <= 32 &&
 280            "Too many bits for uint32_t");
 281     Weights.push_back(Weight->getZExtValue());
 282     WeightSum += Weights.back();
 283     if (PostDominatedByUnreachable.count(TI->getSuccessor(i - 1)))
 284       UnreachableIdxs.push_back(i - 1);
 285     else
 286       ReachableIdxs.push_back(i - 1);
 287   }
 288   assert(Weights.size() == TI->getNumSuccessors() && "Checked above");
 289
 290   // If the sum of weights does not fit in 32 bits, scale every weight down
 291   // accordingly.
 292   uint64_t ScalingFactor =
 293       (WeightSum > UINT32_MAX) ? WeightSum / UINT32_MAX + 1 : 1;
 294
 295   if (ScalingFactor > 1) {
 296     WeightSum = 0;
 297     for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) {
 298       Weights[i] /= ScalingFactor;
 299       WeightSum += Weights[i];
 300     }
 301   }
 302   assert(WeightSum <= UINT32_MAX &&
 303          "Expected weights to scale down to 32 bits");
 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 = UR_TAKEN_PROB;
 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     }
 334   }
 335
 336   for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
 337     setEdgeProbability(BB, i, BP[i]);
 338
 339   return true;
 340 }
 341
 342 /// Calculate edge weights for edges leading to cold blocks.
 343 ///
 344 /// A cold block is one post-dominated by  a block with a call to a
 345 /// cold function.  Those edges are unlikely to be taken, so we give
 346 /// them relatively low weight.
 347 ///
 348 /// Return true if we could compute the weights for cold edges.
 349 /// Return false, otherwise.
 350 bool BranchProbabilityInfo::calcColdCallHeuristics(const BasicBlock *BB) {
 351   const TerminatorInst *TI = BB->getTerminator();
 352   (void) TI;
 353   assert(TI->getNumSuccessors() > 1 && "expected more than one successor!");
 354   assert(!isa<InvokeInst>(TI) &&
 355          "Invokes should have already been handled by calcInvokeHeuristics");
 356
 357   // Determine which successors are post-dominated by a cold block.
 358   SmallVector<unsigned, 4> ColdEdges;
 359   SmallVector<unsigned, 4> NormalEdges;
 360   for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I)
 361     if (PostDominatedByColdCall.count(*I))
 362       ColdEdges.push_back(I.getSuccessorIndex());
 363     else
 364       NormalEdges.push_back(I.getSuccessorIndex());
 365
 366   // Skip probabilities if no cold edges.
 367   if (ColdEdges.empty())
 368     return false;
 369
 370   if (NormalEdges.empty()) {
 371     BranchProbability Prob(1, ColdEdges.size());
 372     for (unsigned SuccIdx : ColdEdges)
 373       setEdgeProbability(BB, SuccIdx, Prob);
 374     return true;
 375   }
 376
 377   auto ColdProb = BranchProbability::getBranchProbability(
 378       CC_TAKEN_WEIGHT,
 379       (CC_TAKEN_WEIGHT + CC_NONTAKEN_WEIGHT) * uint64_t(ColdEdges.size()));
 380   auto NormalProb = BranchProbability::getBranchProbability(
 381       CC_NONTAKEN_WEIGHT,
 382       (CC_TAKEN_WEIGHT + CC_NONTAKEN_WEIGHT) * uint64_t(NormalEdges.size()));
 383
 384   for (unsigned SuccIdx : ColdEdges)
 385     setEdgeProbability(BB, SuccIdx, ColdProb);
 386   for (unsigned SuccIdx : NormalEdges)
 387     setEdgeProbability(BB, SuccIdx, NormalProb);
 388
 389   return true;
 390 }
 391
 392 // Calculate Edge Weights using "Pointer Heuristics". Predict a comparison
 393 // between two pointer or pointer and NULL will fail.
 394 bool BranchProbabilityInfo::calcPointerHeuristics(const BasicBlock *BB) {
 395   const BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
 396   if (!BI || !BI->isConditional())
 397     return false;
 398
 399   Value *Cond = BI->getCondition();
 400   ICmpInst *CI = dyn_cast<ICmpInst>(Cond);
 401   if (!CI || !CI->isEquality())
 402     return false;
 403
 404   Value *LHS = CI->getOperand(0);
 405
 406   if (!LHS->getType()->isPointerTy())
 407     return false;
 408
 409   assert(CI->getOperand(1)->getType()->isPointerTy());
 410
 411   // p != 0   ->   isProb = true
 412   // p == 0   ->   isProb = false
 413   // p != q   ->   isProb = true
 414   // p == q   ->   isProb = false;
 415   unsigned TakenIdx = 0, NonTakenIdx = 1;
 416   bool isProb = CI->getPredicate() == ICmpInst::ICMP_NE;
 417   if (!isProb)
 418     std::swap(TakenIdx, NonTakenIdx);
 419
 420   BranchProbability TakenProb(PH_TAKEN_WEIGHT,
 421                               PH_TAKEN_WEIGHT + PH_NONTAKEN_WEIGHT);
 422   setEdgeProbability(BB, TakenIdx, TakenProb);
 423   setEdgeProbability(BB, NonTakenIdx, TakenProb.getCompl());
 424   return true;
 425 }
 426
 427 static int getSCCNum(const BasicBlock *BB,
 428                      const BranchProbabilityInfo::SccInfo &SccI) {
 429   auto SccIt = SccI.SccNums.find(BB);
 430   if (SccIt == SccI.SccNums.end())
 431     return -1;
 432   return SccIt->second;
 433 }
 434
 435 // Consider any block that is an entry point to the SCC as a header.
 436 static bool isSCCHeader(const BasicBlock *BB, int SccNum,
 437                         BranchProbabilityInfo::SccInfo &SccI) {
 438   assert(getSCCNum(BB, SccI) == SccNum);
 439
 440   // Lazily compute the set of headers for a given SCC and cache the results
 441   // in the SccHeaderMap.
 442   if (SccI.SccHeaders.size() <= static_cast<unsigned>(SccNum))
 443     SccI.SccHeaders.resize(SccNum + 1);
 444   auto &HeaderMap = SccI.SccHeaders[SccNum];
 445   bool Inserted;
 446   BranchProbabilityInfo::SccHeaderMap::iterator HeaderMapIt;
 447   std::tie(HeaderMapIt, Inserted) = HeaderMap.insert(std::make_pair(BB, false));
 448   if (Inserted) {
 449     bool IsHeader = llvm::any_of(make_range(pred_begin(BB), pred_end(BB)),
 450                                  [&](const BasicBlock *Pred) {
 451                                    return getSCCNum(Pred, SccI) != SccNum;
 452                                  });
 453     HeaderMapIt->second = IsHeader;
 454     return IsHeader;
 455   } else
 456     return HeaderMapIt->second;
 457 }
 458
 459 // Compute the unlikely successors to the block BB in the loop L, specifically
 460 // those that are unlikely because this is a loop, and add them to the
 461 // UnlikelyBlocks set.
 462 static void
 463 computeUnlikelySuccessors(const BasicBlock *BB, Loop *L,
 464                           SmallPtrSetImpl<const BasicBlock*> &UnlikelyBlocks) {
 465   // Sometimes in a loop we have a branch whose condition is made false by
 466   // taking it. This is typically something like
 467   //  int n = 0;
 468   //  while (...) {
 469   //    if (++n >= MAX) {
 470   //      n = 0;
 471   //    }
 472   //  }
 473   // In this sort of situation taking the branch means that at the very least it
 474   // won't be taken again in the next iteration of the loop, so we should
 475   // consider it less likely than a typical branch.
 476   //
 477   // We detect this by looking back through the graph of PHI nodes that sets the
 478   // value that the condition depends on, and seeing if we can reach a successor
 479   // block which can be determined to make the condition false.
 480   //
 481   // FIXME: We currently consider unlikely blocks to be half as likely as other
 482   // blocks, but if we consider the example above the likelyhood is actually
 483   // 1/MAX. We could therefore be more precise in how unlikely we consider
 484   // blocks to be, but it would require more careful examination of the form
 485   // of the comparison expression.
 486   const BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
 487   if (!BI || !BI->isConditional())
 488     return;
 489
 490   // Check if the branch is based on an instruction compared with a constant
 491   CmpInst *CI = dyn_cast<CmpInst>(BI->getCondition());
 492   if (!CI || !isa<Instruction>(CI->getOperand(0)) ||
 493       !isa<Constant>(CI->getOperand(1)))
 494     return;
 495
 496   // Either the instruction must be a PHI, or a chain of operations involving
 497   // constants that ends in a PHI which we can then collapse into a single value
 498   // if the PHI value is known.
 499   Instruction *CmpLHS = dyn_cast<Instruction>(CI->getOperand(0));
 500   PHINode *CmpPHI = dyn_cast<PHINode>(CmpLHS);
 501   Constant *CmpConst = dyn_cast<Constant>(CI->getOperand(1));
 502   // Collect the instructions until we hit a PHI
 503   SmallVector<BinaryOperator *, 1> InstChain;
 504   while (!CmpPHI && CmpLHS && isa<BinaryOperator>(CmpLHS) &&
 505          isa<Constant>(CmpLHS->getOperand(1))) {
 506     // Stop if the chain extends outside of the loop
 507     if (!L->contains(CmpLHS))
 508       return;
 509     InstChain.push_back(cast<BinaryOperator>(CmpLHS));
 510     CmpLHS = dyn_cast<Instruction>(CmpLHS->getOperand(0));
 511     if (CmpLHS)
 512       CmpPHI = dyn_cast<PHINode>(CmpLHS);
 513   }
 514   if (!CmpPHI || !L->contains(CmpPHI))
 515     return;
 516
 517   // Trace the phi node to find all values that come from successors of BB
 518   SmallPtrSet<PHINode*, 8> VisitedInsts;
 519   SmallVector<PHINode*, 8> WorkList;
 520   WorkList.push_back(CmpPHI);
 521   VisitedInsts.insert(CmpPHI);
 522   while (!WorkList.empty()) {
 523     PHINode *P = WorkList.back();
 524     WorkList.pop_back();
 525     for (BasicBlock *B : P->blocks()) {
 526       // Skip blocks that aren't part of the loop
 527       if (!L->contains(B))
 528         continue;
 529       Value *V = P->getIncomingValueForBlock(B);
 530       // If the source is a PHI add it to the work list if we haven't
 531       // already visited it.
 532       if (PHINode *PN = dyn_cast<PHINode>(V)) {
 533         if (VisitedInsts.insert(PN).second)
 534           WorkList.push_back(PN);
 535         continue;
 536       }
 537       // If this incoming value is a constant and B is a successor of BB, then
 538       // we can constant-evaluate the compare to see if it makes the branch be
 539       // taken or not.
 540       Constant *CmpLHSConst = dyn_cast<Constant>(V);
 541       if (!CmpLHSConst ||
 542           std::find(succ_begin(BB), succ_end(BB), B) == succ_end(BB))
 543         continue;
 544       // First collapse InstChain
 545       for (Instruction *I : llvm::reverse(InstChain)) {
 546         CmpLHSConst = ConstantExpr::get(I->getOpcode(), CmpLHSConst,
 547                                         cast<Constant>(I->getOperand(1)), true);
 548         if (!CmpLHSConst)
 549           break;
 550       }
 551       if (!CmpLHSConst)
 552         continue;
 553       // Now constant-evaluate the compare
 554       Constant *Result = ConstantExpr::getCompare(CI->getPredicate(),
 555                                                   CmpLHSConst, CmpConst, true);
 556       // If the result means we don't branch to the block then that block is
 557       // unlikely.
 558       if (Result &&
 559           ((Result->isZeroValue() && B == BI->getSuccessor(0)) ||
 560            (Result->isOneValue() && B == BI->getSuccessor(1))))
 561         UnlikelyBlocks.insert(B);
 562     }
 563   }
 564 }
 565
 566 // Calculate Edge Weights using "Loop Branch Heuristics". Predict backedges
 567 // as taken, exiting edges as not-taken.
 568 bool BranchProbabilityInfo::calcLoopBranchHeuristics(const BasicBlock *BB,
 569                                                      const LoopInfo &LI,
 570                                                      SccInfo &SccI) {
 571   int SccNum;
 572   Loop *L = LI.getLoopFor(BB);
 573   if (!L) {
 574     SccNum = getSCCNum(BB, SccI);
 575     if (SccNum < 0)
 576       return false;
 577   }
 578
 579   SmallPtrSet<const BasicBlock*, 8> UnlikelyBlocks;
 580   if (L)
 581     computeUnlikelySuccessors(BB, L, UnlikelyBlocks);
 582
 583   SmallVector<unsigned, 8> BackEdges;
 584   SmallVector<unsigned, 8> ExitingEdges;
 585   SmallVector<unsigned, 8> InEdges; // Edges from header to the loop.
 586   SmallVector<unsigned, 8> UnlikelyEdges;
 587
 588   for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
 589     // Use LoopInfo if we have it, otherwise fall-back to SCC info to catch
 590     // irreducible loops.
 591     if (L) {
 592       if (UnlikelyBlocks.count(*I) != 0)
 593         UnlikelyEdges.push_back(I.getSuccessorIndex());
 594       else if (!L->contains(*I))
 595         ExitingEdges.push_back(I.getSuccessorIndex());
 596       else if (L->getHeader() == *I)
 597         BackEdges.push_back(I.getSuccessorIndex());
 598       else
 599         InEdges.push_back(I.getSuccessorIndex());
 600     } else {
 601       if (getSCCNum(*I, SccI) != SccNum)
 602         ExitingEdges.push_back(I.getSuccessorIndex());
 603       else if (isSCCHeader(*I, SccNum, SccI))
 604         BackEdges.push_back(I.getSuccessorIndex());
 605       else
 606         InEdges.push_back(I.getSuccessorIndex());
 607     }
 608   }
 609
 610   if (BackEdges.empty() && ExitingEdges.empty() && UnlikelyEdges.empty())
 611     return false;
 612
 613   // Collect the sum of probabilities of back-edges/in-edges/exiting-edges, and
 614   // normalize them so that they sum up to one.
 615   unsigned Denom = (BackEdges.empty() ? 0 : LBH_TAKEN_WEIGHT) +
 616                    (InEdges.empty() ? 0 : LBH_TAKEN_WEIGHT) +
 617                    (UnlikelyEdges.empty() ? 0 : LBH_UNLIKELY_WEIGHT) +
 618                    (ExitingEdges.empty() ? 0 : LBH_NONTAKEN_WEIGHT);
 619
 620   if (uint32_t numBackEdges = BackEdges.size()) {
 621     BranchProbability TakenProb = BranchProbability(LBH_TAKEN_WEIGHT, Denom);
 622     auto Prob = TakenProb / numBackEdges;
 623     for (unsigned SuccIdx : BackEdges)
 624       setEdgeProbability(BB, SuccIdx, Prob);
 625   }
 626
 627   if (uint32_t numInEdges = InEdges.size()) {
 628     BranchProbability TakenProb = BranchProbability(LBH_TAKEN_WEIGHT, Denom);
 629     auto Prob = TakenProb / numInEdges;
 630     for (unsigned SuccIdx : InEdges)
 631       setEdgeProbability(BB, SuccIdx, Prob);
 632   }
 633
 634   if (uint32_t numExitingEdges = ExitingEdges.size()) {
 635     BranchProbability NotTakenProb = BranchProbability(LBH_NONTAKEN_WEIGHT,
 636                                                        Denom);
 637     auto Prob = NotTakenProb / numExitingEdges;
 638     for (unsigned SuccIdx : ExitingEdges)
 639       setEdgeProbability(BB, SuccIdx, Prob);
 640   }
 641
 642   if (uint32_t numUnlikelyEdges = UnlikelyEdges.size()) {
 643     BranchProbability UnlikelyProb = BranchProbability(LBH_UNLIKELY_WEIGHT,
 644                                                        Denom);
 645     auto Prob = UnlikelyProb / numUnlikelyEdges;
 646     for (unsigned SuccIdx : UnlikelyEdges)
 647       setEdgeProbability(BB, SuccIdx, Prob);
 648   }
 649
 650   return true;
 651 }
 652
 653 bool BranchProbabilityInfo::calcZeroHeuristics(const BasicBlock *BB,
 654                                                const TargetLibraryInfo *TLI) {
 655   const BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
 656   if (!BI || !BI->isConditional())
 657     return false;
 658
 659   Value *Cond = BI->getCondition();
 660   ICmpInst *CI = dyn_cast<ICmpInst>(Cond);
 661   if (!CI)
 662     return false;
 663
 664   Value *RHS = CI->getOperand(1);
 665   ConstantInt *CV = dyn_cast<ConstantInt>(RHS);
 666   if (!CV)
 667     return false;
 668
 669   // If the LHS is the result of AND'ing a value with a single bit bitmask,
 670   // we don't have information about probabilities.
 671   if (Instruction *LHS = dyn_cast<Instruction>(CI->getOperand(0)))
 672     if (LHS->getOpcode() == Instruction::And)
 673       if (ConstantInt *AndRHS = dyn_cast<ConstantInt>(LHS->getOperand(1)))
 674         if (AndRHS->getValue().isPowerOf2())
 675           return false;
 676
 677   // Check if the LHS is the return value of a library function
 678   LibFunc Func = NumLibFuncs;
 679   if (TLI)
 680     if (CallInst *Call = dyn_cast<CallInst>(CI->getOperand(0)))
 681       if (Function *CalledFn = Call->getCalledFunction())
 682         TLI->getLibFunc(*CalledFn, Func);
 683
 684   bool isProb;
 685   if (Func == LibFunc_strcasecmp ||
 686       Func == LibFunc_strcmp ||
 687       Func == LibFunc_strncasecmp ||
 688       Func == LibFunc_strncmp ||
 689       Func == LibFunc_memcmp) {
 690     // strcmp and similar functions return zero, negative, or positive, if the
 691     // first string is equal, less, or greater than the second. We consider it
 692     // likely that the strings are not equal, so a comparison with zero is
 693     // probably false, but also a comparison with any other number is also
 694     // probably false given that what exactly is returned for nonzero values is
 695     // not specified. Any kind of comparison other than equality we know
 696     // nothing about.
 697     switch (CI->getPredicate()) {
 698     case CmpInst::ICMP_EQ:
 699       isProb = false;
 700       break;
 701     case CmpInst::ICMP_NE:
 702       isProb = true;
 703       break;
 704     default:
 705       return false;
 706     }
 707   } else if (CV->isZero()) {
 708     switch (CI->getPredicate()) {
 709     case CmpInst::ICMP_EQ:
 710       // X == 0   ->  Unlikely
 711       isProb = false;
 712       break;
 713     case CmpInst::ICMP_NE:
 714       // X != 0   ->  Likely
 715       isProb = true;
 716       break;
 717     case CmpInst::ICMP_SLT:
 718       // X < 0   ->  Unlikely
 719       isProb = false;
 720       break;
 721     case CmpInst::ICMP_SGT:
 722       // X > 0   ->  Likely
 723       isProb = true;
 724       break;
 725     default:
 726       return false;
 727     }
 728   } else if (CV->isOne() && CI->getPredicate() == CmpInst::ICMP_SLT) {
 729     // InstCombine canonicalizes X <= 0 into X < 1.
 730     // X <= 0   ->  Unlikely
 731     isProb = false;
 732   } else if (CV->isMinusOne()) {
 733     switch (CI->getPredicate()) {
 734     case CmpInst::ICMP_EQ:
 735       // X == -1  ->  Unlikely
 736       isProb = false;
 737       break;
 738     case CmpInst::ICMP_NE:
 739       // X != -1  ->  Likely
 740       isProb = true;
 741       break;
 742     case CmpInst::ICMP_SGT:
 743       // InstCombine canonicalizes X >= 0 into X > -1.
 744       // X >= 0   ->  Likely
 745       isProb = true;
 746       break;
 747     default:
 748       return false;
 749     }
 750   } else {
 751     return false;
 752   }
 753
 754   unsigned TakenIdx = 0, NonTakenIdx = 1;
 755
 756   if (!isProb)
 757     std::swap(TakenIdx, NonTakenIdx);
 758
 759   BranchProbability TakenProb(ZH_TAKEN_WEIGHT,
 760                               ZH_TAKEN_WEIGHT + ZH_NONTAKEN_WEIGHT);
 761   setEdgeProbability(BB, TakenIdx, TakenProb);
 762   setEdgeProbability(BB, NonTakenIdx, TakenProb.getCompl());
 763   return true;
 764 }
 765
 766 bool BranchProbabilityInfo::calcFloatingPointHeuristics(const BasicBlock *BB) {
 767   const BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
 768   if (!BI || !BI->isConditional())
 769     return false;
 770
 771   Value *Cond = BI->getCondition();
 772   FCmpInst *FCmp = dyn_cast<FCmpInst>(Cond);
 773   if (!FCmp)
 774     return false;
 775
 776   bool isProb;
 777   if (FCmp->isEquality()) {
 778     // f1 == f2 -> Unlikely
 779     // f1 != f2 -> Likely
 780     isProb = !FCmp->isTrueWhenEqual();
 781   } else if (FCmp->getPredicate() == FCmpInst::FCMP_ORD) {
 782     // !isnan -> Likely
 783     isProb = true;
 784   } else if (FCmp->getPredicate() == FCmpInst::FCMP_UNO) {
 785     // isnan -> Unlikely
 786     isProb = false;
 787   } else {
 788     return false;
 789   }
 790
 791   unsigned TakenIdx = 0, NonTakenIdx = 1;
 792
 793   if (!isProb)
 794     std::swap(TakenIdx, NonTakenIdx);
 795
 796   BranchProbability TakenProb(FPH_TAKEN_WEIGHT,
 797                               FPH_TAKEN_WEIGHT + FPH_NONTAKEN_WEIGHT);
 798   setEdgeProbability(BB, TakenIdx, TakenProb);
 799   setEdgeProbability(BB, NonTakenIdx, TakenProb.getCompl());
 800   return true;
 801 }
 802
 803 bool BranchProbabilityInfo::calcInvokeHeuristics(const BasicBlock *BB) {
 804   const InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator());
 805   if (!II)
 806     return false;
 807
 808   BranchProbability TakenProb(IH_TAKEN_WEIGHT,
 809                               IH_TAKEN_WEIGHT + IH_NONTAKEN_WEIGHT);
 810   setEdgeProbability(BB, 0 /*Index for Normal*/, TakenProb);
 811   setEdgeProbability(BB, 1 /*Index for Unwind*/, TakenProb.getCompl());
 812   return true;
 813 }
 814
 815 void BranchProbabilityInfo::releaseMemory() {
 816   Probs.clear();
 817 }
 818
 819 void BranchProbabilityInfo::print(raw_ostream &OS) const {
 820   OS << "---- Branch Probabilities ----\n";
 821   // We print the probabilities from the last function the analysis ran over,
 822   // or the function it is currently running over.
 823   assert(LastF && "Cannot print prior to running over a function");
 824   for (const auto &BI : *LastF) {
 825     for (succ_const_iterator SI = succ_begin(&BI), SE = succ_end(&BI); SI != SE;
 826          ++SI) {
 827       printEdgeProbability(OS << "  ", &BI, *SI);
 828     }
 829   }
 830 }
 831
 832 bool BranchProbabilityInfo::
 833 isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const {
 834   // Hot probability is at least 4/5 = 80%
 835   // FIXME: Compare against a static "hot" BranchProbability.
 836   return getEdgeProbability(Src, Dst) > BranchProbability(4, 5);
 837 }
 838
 839 const BasicBlock *
 840 BranchProbabilityInfo::getHotSucc(const BasicBlock *BB) const {
 841   auto MaxProb = BranchProbability::getZero();
 842   const BasicBlock *MaxSucc = nullptr;
 843
 844   for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
 845     const BasicBlock *Succ = *I;
 846     auto Prob = getEdgeProbability(BB, Succ);
 847     if (Prob > MaxProb) {
 848       MaxProb = Prob;
 849       MaxSucc = Succ;
 850     }
 851   }
 852
 853   // Hot probability is at least 4/5 = 80%
 854   if (MaxProb > BranchProbability(4, 5))
 855     return MaxSucc;
 856
 857   return nullptr;
 858 }
 859
 860 /// Get the raw edge probability for the edge. If can't find it, return a
 861 /// default probability 1/N where N is the number of successors. Here an edge is
 862 /// specified using PredBlock and an
 863 /// index to the successors.
 864 BranchProbability
 865 BranchProbabilityInfo::getEdgeProbability(const BasicBlock *Src,
 866                                           unsigned IndexInSuccessors) const {
 867   auto I = Probs.find(std::make_pair(Src, IndexInSuccessors));
 868
 869   if (I != Probs.end())
 870     return I->second;
 871
 872   return {1, static_cast<uint32_t>(succ_size(Src))};
 873 }
 874
 875 BranchProbability
 876 BranchProbabilityInfo::getEdgeProbability(const BasicBlock *Src,
 877                                           succ_const_iterator Dst) const {
 878   return getEdgeProbability(Src, Dst.getSuccessorIndex());
 879 }
 880
 881 /// Get the raw edge probability calculated for the block pair. This returns the
 882 /// sum of all raw edge probabilities from Src to Dst.
 883 BranchProbability
 884 BranchProbabilityInfo::getEdgeProbability(const BasicBlock *Src,
 885                                           const BasicBlock *Dst) const {
 886   auto Prob = BranchProbability::getZero();
 887   bool FoundProb = false;
 888   for (succ_const_iterator I = succ_begin(Src), E = succ_end(Src); I != E; ++I)
 889     if (*I == Dst) {
 890       auto MapI = Probs.find(std::make_pair(Src, I.getSuccessorIndex()));
 891       if (MapI != Probs.end()) {
 892         FoundProb = true;
 893         Prob += MapI->second;
 894       }
 895     }
 896   uint32_t succ_num = std::distance(succ_begin(Src), succ_end(Src));
 897   return FoundProb ? Prob : BranchProbability(1, succ_num);
 898 }
 899
 900 /// Set the edge probability for a given edge specified by PredBlock and an
 901 /// index to the successors.
 902 void BranchProbabilityInfo::setEdgeProbability(const BasicBlock *Src,
 903                                                unsigned IndexInSuccessors,
 904                                                BranchProbability Prob) {
 905   Probs[std::make_pair(Src, IndexInSuccessors)] = Prob;
 906   Handles.insert(BasicBlockCallbackVH(Src, this));
 907   LLVM_DEBUG(dbgs() << "set edge " << Src->getName() << " -> "
 908                     << IndexInSuccessors << " successor probability to " << Prob
 909                     << "\n");
 910 }
 911
 912 raw_ostream &
 913 BranchProbabilityInfo::printEdgeProbability(raw_ostream &OS,
 914                                             const BasicBlock *Src,
 915                                             const BasicBlock *Dst) const {
 916   const BranchProbability Prob = getEdgeProbability(Src, Dst);
 917   OS << "edge " << Src->getName() << " -> " << Dst->getName()
 918      << " probability is " << Prob
 919      << (isEdgeHot(Src, Dst) ? " [HOT edge]\n" : "\n");
 920
 921   return OS;
 922 }
 923
 924 void BranchProbabilityInfo::eraseBlock(const BasicBlock *BB) {
 925   for (auto I = Probs.begin(), E = Probs.end(); I != E; ++I) {
 926     auto Key = I->first;
 927     if (Key.first == BB)
 928       Probs.erase(Key);
 929   }
 930 }
 931
 932 void BranchProbabilityInfo::calculate(const Function &F, const LoopInfo &LI,
 933                                       const TargetLibraryInfo *TLI) {
 934   LLVM_DEBUG(dbgs() << "---- Branch Probability Info : " << F.getName()
 935                     << " ----\n\n");
 936   LastF = &F; // Store the last function we ran on for printing.
 937   assert(PostDominatedByUnreachable.empty());
 938   assert(PostDominatedByColdCall.empty());
 939
 940   // Record SCC numbers of blocks in the CFG to identify irreducible loops.
 941   // FIXME: We could only calculate this if the CFG is known to be irreducible
 942   // (perhaps cache this info in LoopInfo if we can easily calculate it there?).
 943   int SccNum = 0;
 944   SccInfo SccI;
 945   for (scc_iterator<const Function *> It = scc_begin(&F); !It.isAtEnd();
 946        ++It, ++SccNum) {
 947     // Ignore single-block SCCs since they either aren't loops or LoopInfo will
 948     // catch them.
 949     const std::vector<const BasicBlock *> &Scc = *It;
 950     if (Scc.size() == 1)
 951       continue;
 952
 953     LLVM_DEBUG(dbgs() << "BPI: SCC " << SccNum << ":");
 954     for (auto *BB : Scc) {
 955       LLVM_DEBUG(dbgs() << " " << BB->getName());
 956       SccI.SccNums[BB] = SccNum;
 957     }
 958     LLVM_DEBUG(dbgs() << "\n");
 959   }
 960
 961   // Walk the basic blocks in post-order so that we can build up state about
 962   // the successors of a block iteratively.
 963   for (auto BB : post_order(&F.getEntryBlock())) {
 964     LLVM_DEBUG(dbgs() << "Computing probabilities for " << BB->getName()
 965                       << "\n");
 966     updatePostDominatedByUnreachable(BB);
 967     updatePostDominatedByColdCall(BB);
 968     // If there is no at least two successors, no sense to set probability.
 969     if (BB->getTerminator()->getNumSuccessors() < 2)
 970       continue;
 971     if (calcMetadataWeights(BB))
 972       continue;
 973     if (calcInvokeHeuristics(BB))
 974       continue;
 975     if (calcUnreachableHeuristics(BB))
 976       continue;
 977     if (calcColdCallHeuristics(BB))
 978       continue;
 979     if (calcLoopBranchHeuristics(BB, LI, SccI))
 980       continue;
 981     if (calcPointerHeuristics(BB))
 982       continue;
 983     if (calcZeroHeuristics(BB, TLI))
 984       continue;
 985     if (calcFloatingPointHeuristics(BB))
 986       continue;
 987   }
 988
 989   PostDominatedByUnreachable.clear();
 990   PostDominatedByColdCall.clear();
 991
 992   if (PrintBranchProb &&
 993       (PrintBranchProbFuncName.empty() ||
 994        F.getName().equals(PrintBranchProbFuncName))) {
 995     print(dbgs());
 996   }
 997 }
 998
 999 void BranchProbabilityInfoWrapperPass::getAnalysisUsage(
1000     AnalysisUsage &AU) const {
1001   // We require DT so it's available when LI is available. The LI updating code
1002   // asserts that DT is also present so if we don't make sure that we have DT
1003   // here, that assert will trigger.
1004   AU.addRequired<DominatorTreeWrapperPass>();
1005   AU.addRequired<LoopInfoWrapperPass>();
1006   AU.addRequired<TargetLibraryInfoWrapperPass>();
1007   AU.setPreservesAll();
1008 }
1009
1010 bool BranchProbabilityInfoWrapperPass::runOnFunction(Function &F) {
1011   const LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
1012   const TargetLibraryInfo &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
1013   BPI.calculate(F, LI, &TLI);
1014   return false;
1015 }
1016
1017 void BranchProbabilityInfoWrapperPass::releaseMemory() { BPI.releaseMemory(); }
1018
1019 void BranchProbabilityInfoWrapperPass::print(raw_ostream &OS,
1020                                              const Module *) const {
1021   BPI.print(OS);
1022 }
1023
1024 AnalysisKey BranchProbabilityAnalysis::Key;
1025 BranchProbabilityInfo
1026 BranchProbabilityAnalysis::run(Function &F, FunctionAnalysisManager &AM) {
1027   BranchProbabilityInfo BPI;
1028   BPI.calculate(F, AM.getResult<LoopAnalysis>(F), &AM.getResult<TargetLibraryAnalysis>(F));
1029   return BPI;
1030 }
1031
1032 PreservedAnalyses
1033 BranchProbabilityPrinterPass::run(Function &F, FunctionAnalysisManager &AM) {
1034   OS << "Printing analysis results of BPI for function "
1035      << "'" << F.getName() << "':"
1036      << "\n";
1037   AM.getResult<BranchProbabilityAnalysis>(F).print(OS);
1038   return PreservedAnalyses::all();
1039 }