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