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