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/STLExtras.h"
  17 #include "llvm/ADT/SmallVector.h"
  18 #include "llvm/Analysis/LoopInfo.h"
  19 #include "llvm/Analysis/TargetLibraryInfo.h"
  20 #include "llvm/IR/Attributes.h"
  21 #include "llvm/IR/BasicBlock.h"
  22 #include "llvm/IR/CFG.h"
  23 #include "llvm/IR/Constants.h"
  24 #include "llvm/IR/Function.h"
  25 #include "llvm/IR/InstrTypes.h"
  26 #include "llvm/IR/Instruction.h"
  27 #include "llvm/IR/Instructions.h"
  28 #include "llvm/IR/LLVMContext.h"
  29 #include "llvm/IR/Metadata.h"
  30 #include "llvm/IR/PassManager.h"
  31 #include "llvm/IR/Type.h"
  32 #include "llvm/IR/Value.h"
  33 #include "llvm/Pass.h"
  34 #include "llvm/Support/BranchProbability.h"
  35 #include "llvm/Support/Casting.h"
  36 #include "llvm/Support/Debug.h"
  37 #include "llvm/Support/raw_ostream.h"
  38 #include <cassert>
  39 #include <cstdint>
  40 #include <iterator>
  41 #include <utility>
  42
  43 using namespace llvm;
  44
  45 #define DEBUG_TYPE "branch-prob"
  46
  47 static cl::opt<bool> PrintBranchProb(
  48     "print-bpi", cl::init(false), cl::Hidden,
  49     cl::desc("Print the branch probability info."));
  50
  51 cl::opt<std::string> PrintBranchProbFuncName(
  52     "print-bpi-func-name", cl::Hidden,
  53     cl::desc("The option to specify the name of the function "
  54              "whose branch probability info is printed."));
  55
  56 INITIALIZE_PASS_BEGIN(BranchProbabilityInfoWrapperPass, "branch-prob",
  57                       "Branch Probability Analysis", false, true)
  58 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
  59 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
  60 INITIALIZE_PASS_END(BranchProbabilityInfoWrapperPass, "branch-prob",
  61                     "Branch Probability Analysis", false, true)
  62
  63 char BranchProbabilityInfoWrapperPass::ID = 0;
  64
  65 // Weights are for internal use only. They are used by heuristics to help to
  66 // estimate edges' probability. Example:
  67 //
  68 // Using "Loop Branch Heuristics" we predict weights of edges for the
  69 // block BB2.
  70 //         ...
  71 //          |
  72 //          V
  73 //         BB1<-+
  74 //          |   |
  75 //          |   | (Weight = 124)
  76 //          V   |
  77 //         BB2--+
  78 //          |
  79 //          | (Weight = 4)
  80 //          V
  81 //         BB3
  82 //
  83 // Probability of the edge BB2->BB1 = 124 / (124 + 4) = 0.96875
  84 // Probability of the edge BB2->BB3 = 4 / (124 + 4) = 0.03125
  85 static const uint32_t LBH_TAKEN_WEIGHT = 124;
  86 static const uint32_t LBH_NONTAKEN_WEIGHT = 4;
  87
  88 /// \brief Unreachable-terminating branch taken probability.
  89 ///
  90 /// This is the probability for a branch being taken to a block that terminates
  91 /// (eventually) in unreachable. These are predicted as unlikely as possible.
  92 /// All reachable probability will equally share the remaining part.
  93 static const BranchProbability UR_TAKEN_PROB = BranchProbability::getRaw(1);
  94
  95 /// \brief Weight for a branch taken going into a cold block.
  96 ///
  97 /// This is the weight for a branch taken toward a block marked
  98 /// cold.  A block is marked cold if it's postdominated by a
  99 /// block containing a call to a cold function.  Cold functions
 100 /// are those marked with attribute 'cold'.
 101 static const uint32_t CC_TAKEN_WEIGHT = 4;
 102
 103 /// \brief Weight for a branch not-taken into a cold block.
 104 ///
 105 /// This is the weight for a branch not taken toward a block marked
 106 /// cold.
 107 static const uint32_t CC_NONTAKEN_WEIGHT = 64;
 108
 109 static const uint32_t PH_TAKEN_WEIGHT = 20;
 110 static const uint32_t PH_NONTAKEN_WEIGHT = 12;
 111
 112 static const uint32_t ZH_TAKEN_WEIGHT = 20;
 113 static const uint32_t ZH_NONTAKEN_WEIGHT = 12;
 114
 115 static const uint32_t FPH_TAKEN_WEIGHT = 20;
 116 static const uint32_t FPH_NONTAKEN_WEIGHT = 12;
 117
 118 /// \brief Invoke-terminating normal branch taken weight
 119 ///
 120 /// This is the weight for branching to the normal destination of an invoke
 121 /// instruction. We expect this to happen most of the time. Set the weight to an
 122 /// absurdly high value so that nested loops subsume it.
 123 static const uint32_t IH_TAKEN_WEIGHT = 1024 * 1024 - 1;
 124
 125 /// \brief Invoke-terminating normal branch not-taken weight.
 126 ///
 127 /// This is the weight for branching to the unwind destination of an invoke
 128 /// instruction. This is essentially never taken.
 129 static const uint32_t IH_NONTAKEN_WEIGHT = 1;
 130
 131 /// \brief Add \p BB to PostDominatedByUnreachable set if applicable.
 132 void
 133 BranchProbabilityInfo::updatePostDominatedByUnreachable(const BasicBlock *BB) {
 134   const TerminatorInst *TI = BB->getTerminator();
 135   if (TI->getNumSuccessors() == 0) {
 136     if (isa<UnreachableInst>(TI) ||
 137         // If this block is terminated by a call to
 138         // @llvm.experimental.deoptimize then treat it like an unreachable since
 139         // the @llvm.experimental.deoptimize call is expected to practically
 140         // never execute.
 141         BB->getTerminatingDeoptimizeCall())
 142       PostDominatedByUnreachable.insert(BB);
 143     return;
 144   }
 145
 146   // If the terminator is an InvokeInst, check only the normal destination block
 147   // as the unwind edge of InvokeInst is also very unlikely taken.
 148   if (auto *II = dyn_cast<InvokeInst>(TI)) {
 149     if (PostDominatedByUnreachable.count(II->getNormalDest()))
 150       PostDominatedByUnreachable.insert(BB);
 151     return;
 152   }
 153
 154   for (auto *I : successors(BB))
 155     // If any of successor is not post dominated then BB is also not.
 156     if (!PostDominatedByUnreachable.count(I))
 157       return;
 158
 159   PostDominatedByUnreachable.insert(BB);
 160 }
 161
 162 /// \brief Add \p BB to PostDominatedByColdCall set if applicable.
 163 void
 164 BranchProbabilityInfo::updatePostDominatedByColdCall(const BasicBlock *BB) {
 165   assert(!PostDominatedByColdCall.count(BB));
 166   const TerminatorInst *TI = BB->getTerminator();
 167   if (TI->getNumSuccessors() == 0)
 168     return;
 169
 170   // If all of successor are post dominated then BB is also done.
 171   if (llvm::all_of(successors(BB), [&](const BasicBlock *SuccBB) {
 172         return PostDominatedByColdCall.count(SuccBB);
 173       })) {
 174     PostDominatedByColdCall.insert(BB);
 175     return;
 176   }
 177
 178   // If the terminator is an InvokeInst, check only the normal destination
 179   // block as the unwind edge of InvokeInst is also very unlikely taken.
 180   if (auto *II = dyn_cast<InvokeInst>(TI))
 181     if (PostDominatedByColdCall.count(II->getNormalDest())) {
 182       PostDominatedByColdCall.insert(BB);
 183       return;
 184     }
 185
 186   // Otherwise, if the block itself contains a cold function, add it to the
 187   // set of blocks post-dominated by a cold call.
 188   for (auto &I : *BB)
 189     if (const CallInst *CI = dyn_cast<CallInst>(&I))
 190       if (CI->hasFnAttr(Attribute::Cold)) {
 191         PostDominatedByColdCall.insert(BB);
 192         return;
 193       }
 194 }
 195
 196 /// \brief Calculate edge weights for successors lead to unreachable.
 197 ///
 198 /// Predict that a successor which leads necessarily to an
 199 /// unreachable-terminated block as extremely unlikely.
 200 bool BranchProbabilityInfo::calcUnreachableHeuristics(const BasicBlock *BB) {
 201   const TerminatorInst *TI = BB->getTerminator();
 202   assert(TI->getNumSuccessors() > 1 && "expected more than one successor!");
 203
 204   // Return false here so that edge weights for InvokeInst could be decided
 205   // in calcInvokeHeuristics().
 206   if (isa<InvokeInst>(TI))
 207     return false;
 208
 209   SmallVector<unsigned, 4> UnreachableEdges;
 210   SmallVector<unsigned, 4> ReachableEdges;
 211
 212   for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I)
 213     if (PostDominatedByUnreachable.count(*I))
 214       UnreachableEdges.push_back(I.getSuccessorIndex());
 215     else
 216       ReachableEdges.push_back(I.getSuccessorIndex());
 217
 218   // Skip probabilities if all were reachable.
 219   if (UnreachableEdges.empty())
 220     return false;
 221
 222   if (ReachableEdges.empty()) {
 223     BranchProbability Prob(1, UnreachableEdges.size());
 224     for (unsigned SuccIdx : UnreachableEdges)
 225       setEdgeProbability(BB, SuccIdx, Prob);
 226     return true;
 227   }
 228
 229   auto UnreachableProb = UR_TAKEN_PROB;
 230   auto ReachableProb =
 231       (BranchProbability::getOne() - UR_TAKEN_PROB * UnreachableEdges.size()) /
 232       ReachableEdges.size();
 233
 234   for (unsigned SuccIdx : UnreachableEdges)
 235     setEdgeProbability(BB, SuccIdx, UnreachableProb);
 236   for (unsigned SuccIdx : ReachableEdges)
 237     setEdgeProbability(BB, SuccIdx, ReachableProb);
 238
 239   return true;
 240 }
 241
 242 // Propagate existing explicit probabilities from either profile data or
 243 // 'expect' intrinsic processing. Examine metadata against unreachable
 244 // heuristic. The probability of the edge coming to unreachable block is
 245 // set to min of metadata and unreachable heuristic.
 246 bool BranchProbabilityInfo::calcMetadataWeights(const BasicBlock *BB) {
 247   const TerminatorInst *TI = BB->getTerminator();
 248   assert(TI->getNumSuccessors() > 1 && "expected more than one successor!");
 249   if (!(isa<BranchInst>(TI) || isa<SwitchInst>(TI) || isa<IndirectBrInst>(TI)))
 250     return false;
 251
 252   MDNode *WeightsNode = TI->getMetadata(LLVMContext::MD_prof);
 253   if (!WeightsNode)
 254     return false;
 255
 256   // Check that the number of successors is manageable.
 257   assert(TI->getNumSuccessors() < UINT32_MAX && "Too many successors");
 258
 259   // Ensure there are weights for all of the successors. Note that the first
 260   // operand to the metadata node is a name, not a weight.
 261   if (WeightsNode->getNumOperands() != TI->getNumSuccessors() + 1)
 262     return false;
 263
 264   // Build up the final weights that will be used in a temporary buffer.
 265   // Compute the sum of all weights to later decide whether they need to
 266   // be scaled to fit in 32 bits.
 267   uint64_t WeightSum = 0;
 268   SmallVector<uint32_t, 2> Weights;
 269   SmallVector<unsigned, 2> UnreachableIdxs;
 270   SmallVector<unsigned, 2> ReachableIdxs;
 271   Weights.reserve(TI->getNumSuccessors());
 272   for (unsigned i = 1, e = WeightsNode->getNumOperands(); i != e; ++i) {
 273     ConstantInt *Weight =
 274         mdconst::dyn_extract<ConstantInt>(WeightsNode->getOperand(i));
 275     if (!Weight)
 276       return false;
 277     assert(Weight->getValue().getActiveBits() <= 32 &&
 278            "Too many bits for uint32_t");
 279     Weights.push_back(Weight->getZExtValue());
 280     WeightSum += Weights.back();
 281     if (PostDominatedByUnreachable.count(TI->getSuccessor(i - 1)))
 282       UnreachableIdxs.push_back(i - 1);
 283     else
 284       ReachableIdxs.push_back(i - 1);
 285   }
 286   assert(Weights.size() == TI->getNumSuccessors() && "Checked above");
 287
 288   // If the sum of weights does not fit in 32 bits, scale every weight down
 289   // accordingly.
 290   uint64_t ScalingFactor =
 291       (WeightSum > UINT32_MAX) ? WeightSum / UINT32_MAX + 1 : 1;
 292
 293   if (ScalingFactor > 1) {
 294     WeightSum = 0;
 295     for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) {
 296       Weights[i] /= ScalingFactor;
 297       WeightSum += Weights[i];
 298     }
 299   }
 300   assert(WeightSum <= UINT32_MAX &&
 301          "Expected weights to scale down to 32 bits");
 302
 303   if (WeightSum == 0 || ReachableIdxs.size() == 0) {
 304     for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
 305       Weights[i] = 1;
 306     WeightSum = TI->getNumSuccessors();
 307   }
 308
 309   // Set the probability.
 310   SmallVector<BranchProbability, 2> BP;
 311   for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
 312     BP.push_back({ Weights[i], static_cast<uint32_t>(WeightSum) });
 313
 314   // Examine the metadata against unreachable heuristic.
 315   // If the unreachable heuristic is more strong then we use it for this edge.
 316   if (UnreachableIdxs.size() > 0 && ReachableIdxs.size() > 0) {
 317     auto ToDistribute = BranchProbability::getZero();
 318     auto UnreachableProb = UR_TAKEN_PROB;
 319     for (auto i : UnreachableIdxs)
 320       if (UnreachableProb < BP[i]) {
 321         ToDistribute += BP[i] - UnreachableProb;
 322         BP[i] = UnreachableProb;
 323       }
 324
 325     // If we modified the probability of some edges then we must distribute
 326     // the difference between reachable blocks.
 327     if (ToDistribute > BranchProbability::getZero()) {
 328       BranchProbability PerEdge = ToDistribute / ReachableIdxs.size();
 329       for (auto i : ReachableIdxs)
 330         BP[i] += PerEdge;
 331     }
 332   }
 333
 334   for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
 335     setEdgeProbability(BB, i, BP[i]);
 336
 337   return true;
 338 }
 339
 340 /// \brief Calculate edge weights for edges leading to cold blocks.
 341 ///
 342 /// A cold block is one post-dominated by  a block with a call to a
 343 /// cold function.  Those edges are unlikely to be taken, so we give
 344 /// them relatively low weight.
 345 ///
 346 /// Return true if we could compute the weights for cold edges.
 347 /// Return false, otherwise.
 348 bool BranchProbabilityInfo::calcColdCallHeuristics(const BasicBlock *BB) {
 349   const TerminatorInst *TI = BB->getTerminator();
 350   assert(TI->getNumSuccessors() > 1 && "expected more than one successor!");
 351
 352   // Return false here so that edge weights for InvokeInst could be decided
 353   // in calcInvokeHeuristics().
 354   if (isa<InvokeInst>(TI))
 355     return false;
 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 comparsion
 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 // Calculate Edge Weights using "Loop Branch Heuristics". Predict backedges
 428 // as taken, exiting edges as not-taken.
 429 bool BranchProbabilityInfo::calcLoopBranchHeuristics(const BasicBlock *BB,
 430                                                      const LoopInfo &LI) {
 431   Loop *L = LI.getLoopFor(BB);
 432   if (!L)
 433     return false;
 434
 435   SmallVector<unsigned, 8> BackEdges;
 436   SmallVector<unsigned, 8> ExitingEdges;
 437   SmallVector<unsigned, 8> InEdges; // Edges from header to the loop.
 438
 439   for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
 440     if (!L->contains(*I))
 441       ExitingEdges.push_back(I.getSuccessorIndex());
 442     else if (L->getHeader() == *I)
 443       BackEdges.push_back(I.getSuccessorIndex());
 444     else
 445       InEdges.push_back(I.getSuccessorIndex());
 446   }
 447
 448   if (BackEdges.empty() && ExitingEdges.empty())
 449     return false;
 450
 451   // Collect the sum of probabilities of back-edges/in-edges/exiting-edges, and
 452   // normalize them so that they sum up to one.
 453   BranchProbability Probs[] = {BranchProbability::getZero(),
 454                                BranchProbability::getZero(),
 455                                BranchProbability::getZero()};
 456   unsigned Denom = (BackEdges.empty() ? 0 : LBH_TAKEN_WEIGHT) +
 457                    (InEdges.empty() ? 0 : LBH_TAKEN_WEIGHT) +
 458                    (ExitingEdges.empty() ? 0 : LBH_NONTAKEN_WEIGHT);
 459   if (!BackEdges.empty())
 460     Probs[0] = BranchProbability(LBH_TAKEN_WEIGHT, Denom);
 461   if (!InEdges.empty())
 462     Probs[1] = BranchProbability(LBH_TAKEN_WEIGHT, Denom);
 463   if (!ExitingEdges.empty())
 464     Probs[2] = BranchProbability(LBH_NONTAKEN_WEIGHT, Denom);
 465
 466   if (uint32_t numBackEdges = BackEdges.size()) {
 467     auto Prob = Probs[0] / numBackEdges;
 468     for (unsigned SuccIdx : BackEdges)
 469       setEdgeProbability(BB, SuccIdx, Prob);
 470   }
 471
 472   if (uint32_t numInEdges = InEdges.size()) {
 473     auto Prob = Probs[1] / numInEdges;
 474     for (unsigned SuccIdx : InEdges)
 475       setEdgeProbability(BB, SuccIdx, Prob);
 476   }
 477
 478   if (uint32_t numExitingEdges = ExitingEdges.size()) {
 479     auto Prob = Probs[2] / numExitingEdges;
 480     for (unsigned SuccIdx : ExitingEdges)
 481       setEdgeProbability(BB, SuccIdx, Prob);
 482   }
 483
 484   return true;
 485 }
 486
 487 bool BranchProbabilityInfo::calcZeroHeuristics(const BasicBlock *BB,
 488                                                const TargetLibraryInfo *TLI) {
 489   const BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
 490   if (!BI || !BI->isConditional())
 491     return false;
 492
 493   Value *Cond = BI->getCondition();
 494   ICmpInst *CI = dyn_cast<ICmpInst>(Cond);
 495   if (!CI)
 496     return false;
 497
 498   Value *RHS = CI->getOperand(1);
 499   ConstantInt *CV = dyn_cast<ConstantInt>(RHS);
 500   if (!CV)
 501     return false;
 502
 503   // If the LHS is the result of AND'ing a value with a single bit bitmask,
 504   // we don't have information about probabilities.
 505   if (Instruction *LHS = dyn_cast<Instruction>(CI->getOperand(0)))
 506     if (LHS->getOpcode() == Instruction::And)
 507       if (ConstantInt *AndRHS = dyn_cast<ConstantInt>(LHS->getOperand(1)))
 508         if (AndRHS->getValue().isPowerOf2())
 509           return false;
 510
 511   // Check if the LHS is the return value of a library function
 512   LibFunc Func = NumLibFuncs;
 513   if (TLI)
 514     if (CallInst *Call = dyn_cast<CallInst>(CI->getOperand(0)))
 515       if (Function *CalledFn = Call->getCalledFunction())
 516         TLI->getLibFunc(*CalledFn, Func);
 517
 518   bool isProb;
 519   if (Func == LibFunc_strcasecmp ||
 520       Func == LibFunc_strcmp ||
 521       Func == LibFunc_strncasecmp ||
 522       Func == LibFunc_strncmp ||
 523       Func == LibFunc_memcmp) {
 524     // strcmp and similar functions return zero, negative, or positive, if the
 525     // first string is equal, less, or greater than the second. We consider it
 526     // likely that the strings are not equal, so a comparison with zero is
 527     // probably false, but also a comparison with any other number is also
 528     // probably false given that what exactly is returned for nonzero values is
 529     // not specified. Any kind of comparison other than equality we know
 530     // nothing about.
 531     switch (CI->getPredicate()) {
 532     case CmpInst::ICMP_EQ:
 533       isProb = false;
 534       break;
 535     case CmpInst::ICMP_NE:
 536       isProb = true;
 537       break;
 538     default:
 539       return false;
 540     }
 541   } else if (CV->isZero()) {
 542     switch (CI->getPredicate()) {
 543     case CmpInst::ICMP_EQ:
 544       // X == 0   ->  Unlikely
 545       isProb = false;
 546       break;
 547     case CmpInst::ICMP_NE:
 548       // X != 0   ->  Likely
 549       isProb = true;
 550       break;
 551     case CmpInst::ICMP_SLT:
 552       // X < 0   ->  Unlikely
 553       isProb = false;
 554       break;
 555     case CmpInst::ICMP_SGT:
 556       // X > 0   ->  Likely
 557       isProb = true;
 558       break;
 559     default:
 560       return false;
 561     }
 562   } else if (CV->isOne() && CI->getPredicate() == CmpInst::ICMP_SLT) {
 563     // InstCombine canonicalizes X <= 0 into X < 1.
 564     // X <= 0   ->  Unlikely
 565     isProb = false;
 566   } else if (CV->isMinusOne()) {
 567     switch (CI->getPredicate()) {
 568     case CmpInst::ICMP_EQ:
 569       // X == -1  ->  Unlikely
 570       isProb = false;
 571       break;
 572     case CmpInst::ICMP_NE:
 573       // X != -1  ->  Likely
 574       isProb = true;
 575       break;
 576     case CmpInst::ICMP_SGT:
 577       // InstCombine canonicalizes X >= 0 into X > -1.
 578       // X >= 0   ->  Likely
 579       isProb = true;
 580       break;
 581     default:
 582       return false;
 583     }
 584   } else {
 585     return false;
 586   }
 587
 588   unsigned TakenIdx = 0, NonTakenIdx = 1;
 589
 590   if (!isProb)
 591     std::swap(TakenIdx, NonTakenIdx);
 592
 593   BranchProbability TakenProb(ZH_TAKEN_WEIGHT,
 594                               ZH_TAKEN_WEIGHT + ZH_NONTAKEN_WEIGHT);
 595   setEdgeProbability(BB, TakenIdx, TakenProb);
 596   setEdgeProbability(BB, NonTakenIdx, TakenProb.getCompl());
 597   return true;
 598 }
 599
 600 bool BranchProbabilityInfo::calcFloatingPointHeuristics(const BasicBlock *BB) {
 601   const BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
 602   if (!BI || !BI->isConditional())
 603     return false;
 604
 605   Value *Cond = BI->getCondition();
 606   FCmpInst *FCmp = dyn_cast<FCmpInst>(Cond);
 607   if (!FCmp)
 608     return false;
 609
 610   bool isProb;
 611   if (FCmp->isEquality()) {
 612     // f1 == f2 -> Unlikely
 613     // f1 != f2 -> Likely
 614     isProb = !FCmp->isTrueWhenEqual();
 615   } else if (FCmp->getPredicate() == FCmpInst::FCMP_ORD) {
 616     // !isnan -> Likely
 617     isProb = true;
 618   } else if (FCmp->getPredicate() == FCmpInst::FCMP_UNO) {
 619     // isnan -> Unlikely
 620     isProb = false;
 621   } else {
 622     return false;
 623   }
 624
 625   unsigned TakenIdx = 0, NonTakenIdx = 1;
 626
 627   if (!isProb)
 628     std::swap(TakenIdx, NonTakenIdx);
 629
 630   BranchProbability TakenProb(FPH_TAKEN_WEIGHT,
 631                               FPH_TAKEN_WEIGHT + FPH_NONTAKEN_WEIGHT);
 632   setEdgeProbability(BB, TakenIdx, TakenProb);
 633   setEdgeProbability(BB, NonTakenIdx, TakenProb.getCompl());
 634   return true;
 635 }
 636
 637 bool BranchProbabilityInfo::calcInvokeHeuristics(const BasicBlock *BB) {
 638   const InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator());
 639   if (!II)
 640     return false;
 641
 642   BranchProbability TakenProb(IH_TAKEN_WEIGHT,
 643                               IH_TAKEN_WEIGHT + IH_NONTAKEN_WEIGHT);
 644   setEdgeProbability(BB, 0 /*Index for Normal*/, TakenProb);
 645   setEdgeProbability(BB, 1 /*Index for Unwind*/, TakenProb.getCompl());
 646   return true;
 647 }
 648
 649 void BranchProbabilityInfo::releaseMemory() {
 650   Probs.clear();
 651 }
 652
 653 void BranchProbabilityInfo::print(raw_ostream &OS) const {
 654   OS << "---- Branch Probabilities ----\n";
 655   // We print the probabilities from the last function the analysis ran over,
 656   // or the function it is currently running over.
 657   assert(LastF && "Cannot print prior to running over a function");
 658   for (const auto &BI : *LastF) {
 659     for (succ_const_iterator SI = succ_begin(&BI), SE = succ_end(&BI); SI != SE;
 660          ++SI) {
 661       printEdgeProbability(OS << "  ", &BI, *SI);
 662     }
 663   }
 664 }
 665
 666 bool BranchProbabilityInfo::
 667 isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const {
 668   // Hot probability is at least 4/5 = 80%
 669   // FIXME: Compare against a static "hot" BranchProbability.
 670   return getEdgeProbability(Src, Dst) > BranchProbability(4, 5);
 671 }
 672
 673 const BasicBlock *
 674 BranchProbabilityInfo::getHotSucc(const BasicBlock *BB) const {
 675   auto MaxProb = BranchProbability::getZero();
 676   const BasicBlock *MaxSucc = nullptr;
 677
 678   for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
 679     const BasicBlock *Succ = *I;
 680     auto Prob = getEdgeProbability(BB, Succ);
 681     if (Prob > MaxProb) {
 682       MaxProb = Prob;
 683       MaxSucc = Succ;
 684     }
 685   }
 686
 687   // Hot probability is at least 4/5 = 80%
 688   if (MaxProb > BranchProbability(4, 5))
 689     return MaxSucc;
 690
 691   return nullptr;
 692 }
 693
 694 /// Get the raw edge probability for the edge. If can't find it, return a
 695 /// default probability 1/N where N is the number of successors. Here an edge is
 696 /// specified using PredBlock and an
 697 /// index to the successors.
 698 BranchProbability
 699 BranchProbabilityInfo::getEdgeProbability(const BasicBlock *Src,
 700                                           unsigned IndexInSuccessors) const {
 701   auto I = Probs.find(std::make_pair(Src, IndexInSuccessors));
 702
 703   if (I != Probs.end())
 704     return I->second;
 705
 706   return {1,
 707           static_cast<uint32_t>(std::distance(succ_begin(Src), succ_end(Src)))};
 708 }
 709
 710 BranchProbability
 711 BranchProbabilityInfo::getEdgeProbability(const BasicBlock *Src,
 712                                           succ_const_iterator Dst) const {
 713   return getEdgeProbability(Src, Dst.getSuccessorIndex());
 714 }
 715
 716 /// Get the raw edge probability calculated for the block pair. This returns the
 717 /// sum of all raw edge probabilities from Src to Dst.
 718 BranchProbability
 719 BranchProbabilityInfo::getEdgeProbability(const BasicBlock *Src,
 720                                           const BasicBlock *Dst) const {
 721   auto Prob = BranchProbability::getZero();
 722   bool FoundProb = false;
 723   for (succ_const_iterator I = succ_begin(Src), E = succ_end(Src); I != E; ++I)
 724     if (*I == Dst) {
 725       auto MapI = Probs.find(std::make_pair(Src, I.getSuccessorIndex()));
 726       if (MapI != Probs.end()) {
 727         FoundProb = true;
 728         Prob += MapI->second;
 729       }
 730     }
 731   uint32_t succ_num = std::distance(succ_begin(Src), succ_end(Src));
 732   return FoundProb ? Prob : BranchProbability(1, succ_num);
 733 }
 734
 735 /// Set the edge probability for a given edge specified by PredBlock and an
 736 /// index to the successors.
 737 void BranchProbabilityInfo::setEdgeProbability(const BasicBlock *Src,
 738                                                unsigned IndexInSuccessors,
 739                                                BranchProbability Prob) {
 740   Probs[std::make_pair(Src, IndexInSuccessors)] = Prob;
 741   Handles.insert(BasicBlockCallbackVH(Src, this));
 742   DEBUG(dbgs() << "set edge " << Src->getName() << " -> " << IndexInSuccessors
 743                << " successor probability to " << Prob << "\n");
 744 }
 745
 746 raw_ostream &
 747 BranchProbabilityInfo::printEdgeProbability(raw_ostream &OS,
 748                                             const BasicBlock *Src,
 749                                             const BasicBlock *Dst) const {
 750   const BranchProbability Prob = getEdgeProbability(Src, Dst);
 751   OS << "edge " << Src->getName() << " -> " << Dst->getName()
 752      << " probability is " << Prob
 753      << (isEdgeHot(Src, Dst) ? " [HOT edge]\n" : "\n");
 754
 755   return OS;
 756 }
 757
 758 void BranchProbabilityInfo::eraseBlock(const BasicBlock *BB) {
 759   for (auto I = Probs.begin(), E = Probs.end(); I != E; ++I) {
 760     auto Key = I->first;
 761     if (Key.first == BB)
 762       Probs.erase(Key);
 763   }
 764 }
 765
 766 void BranchProbabilityInfo::calculate(const Function &F, const LoopInfo &LI,
 767                                       const TargetLibraryInfo *TLI) {
 768   DEBUG(dbgs() << "---- Branch Probability Info : " << F.getName()
 769                << " ----\n\n");
 770   LastF = &F; // Store the last function we ran on for printing.
 771   assert(PostDominatedByUnreachable.empty());
 772   assert(PostDominatedByColdCall.empty());
 773
 774   // Walk the basic blocks in post-order so that we can build up state about
 775   // the successors of a block iteratively.
 776   for (auto BB : post_order(&F.getEntryBlock())) {
 777     DEBUG(dbgs() << "Computing probabilities for " << BB->getName() << "\n");
 778     updatePostDominatedByUnreachable(BB);
 779     updatePostDominatedByColdCall(BB);
 780     // If there is no at least two successors, no sense to set probability.
 781     if (BB->getTerminator()->getNumSuccessors() < 2)
 782       continue;
 783     if (calcMetadataWeights(BB))
 784       continue;
 785     if (calcUnreachableHeuristics(BB))
 786       continue;
 787     if (calcColdCallHeuristics(BB))
 788       continue;
 789     if (calcLoopBranchHeuristics(BB, LI))
 790       continue;
 791     if (calcPointerHeuristics(BB))
 792       continue;
 793     if (calcZeroHeuristics(BB, TLI))
 794       continue;
 795     if (calcFloatingPointHeuristics(BB))
 796       continue;
 797     calcInvokeHeuristics(BB);
 798   }
 799
 800   PostDominatedByUnreachable.clear();
 801   PostDominatedByColdCall.clear();
 802
 803   if (PrintBranchProb &&
 804       (PrintBranchProbFuncName.empty() ||
 805        F.getName().equals(PrintBranchProbFuncName))) {
 806     print(dbgs());
 807   }
 808 }
 809
 810 void BranchProbabilityInfoWrapperPass::getAnalysisUsage(
 811     AnalysisUsage &AU) const {
 812   AU.addRequired<LoopInfoWrapperPass>();
 813   AU.addRequired<TargetLibraryInfoWrapperPass>();
 814   AU.setPreservesAll();
 815 }
 816
 817 bool BranchProbabilityInfoWrapperPass::runOnFunction(Function &F) {
 818   const LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
 819   const TargetLibraryInfo &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
 820   BPI.calculate(F, LI, &TLI);
 821   return false;
 822 }
 823
 824 void BranchProbabilityInfoWrapperPass::releaseMemory() { BPI.releaseMemory(); }
 825
 826 void BranchProbabilityInfoWrapperPass::print(raw_ostream &OS,
 827                                              const Module *) const {
 828   BPI.print(OS);
 829 }
 830
 831 AnalysisKey BranchProbabilityAnalysis::Key;
 832 BranchProbabilityInfo
 833 BranchProbabilityAnalysis::run(Function &F, FunctionAnalysisManager &AM) {
 834   BranchProbabilityInfo BPI;
 835   BPI.calculate(F, AM.getResult<LoopAnalysis>(F), &AM.getResult<TargetLibraryAnalysis>(F));
 836   return BPI;
 837 }
 838
 839 PreservedAnalyses
 840 BranchProbabilityPrinterPass::run(Function &F, FunctionAnalysisManager &AM) {
 841   OS << "Printing analysis results of BPI for function "
 842      << "'" << F.getName() << "':"
 843      << "\n";
 844   AM.getResult<BranchProbabilityAnalysis>(F).print(OS);
 845   return PreservedAnalyses::all();
 846 }