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