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