LLVM  mainline
BranchProbabilityInfo.cpp
Go to the documentation of this file.
00001 //===-- BranchProbabilityInfo.cpp - Branch Probability Analysis -----------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // Loops should be simplified before this analysis.
00011 //
00012 //===----------------------------------------------------------------------===//
00013 
00014 #include "llvm/Analysis/BranchProbabilityInfo.h"
00015 #include "llvm/ADT/PostOrderIterator.h"
00016 #include "llvm/Analysis/LoopInfo.h"
00017 #include "llvm/IR/CFG.h"
00018 #include "llvm/IR/Constants.h"
00019 #include "llvm/IR/Function.h"
00020 #include "llvm/IR/Instructions.h"
00021 #include "llvm/IR/LLVMContext.h"
00022 #include "llvm/IR/Metadata.h"
00023 #include "llvm/Support/Debug.h"
00024 #include "llvm/Support/raw_ostream.h"
00025 
00026 using namespace llvm;
00027 
00028 #define DEBUG_TYPE "branch-prob"
00029 
00030 INITIALIZE_PASS_BEGIN(BranchProbabilityInfoWrapperPass, "branch-prob",
00031                       "Branch Probability Analysis", false, true)
00032 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
00033 INITIALIZE_PASS_END(BranchProbabilityInfoWrapperPass, "branch-prob",
00034                     "Branch Probability Analysis", false, true)
00035 
00036 char BranchProbabilityInfoWrapperPass::ID = 0;
00037 
00038 // Weights are for internal use only. They are used by heuristics to help to
00039 // estimate edges' probability. Example:
00040 //
00041 // Using "Loop Branch Heuristics" we predict weights of edges for the
00042 // block BB2.
00043 //         ...
00044 //          |
00045 //          V
00046 //         BB1<-+
00047 //          |   |
00048 //          |   | (Weight = 124)
00049 //          V   |
00050 //         BB2--+
00051 //          |
00052 //          | (Weight = 4)
00053 //          V
00054 //         BB3
00055 //
00056 // Probability of the edge BB2->BB1 = 124 / (124 + 4) = 0.96875
00057 // Probability of the edge BB2->BB3 = 4 / (124 + 4) = 0.03125
00058 static const uint32_t LBH_TAKEN_WEIGHT = 124;
00059 static const uint32_t LBH_NONTAKEN_WEIGHT = 4;
00060 
00061 /// \brief Unreachable-terminating branch taken weight.
00062 ///
00063 /// This is the weight for a branch being taken to a block that terminates
00064 /// (eventually) in unreachable. These are predicted as unlikely as possible.
00065 static const uint32_t UR_TAKEN_WEIGHT = 1;
00066 
00067 /// \brief Unreachable-terminating branch not-taken weight.
00068 ///
00069 /// This is the weight for a branch not being taken toward a block that
00070 /// terminates (eventually) in unreachable. Such a branch is essentially never
00071 /// taken. Set the weight to an absurdly high value so that nested loops don't
00072 /// easily subsume it.
00073 static const uint32_t UR_NONTAKEN_WEIGHT = 1024*1024 - 1;
00074 
00075 /// \brief Weight for a branch taken going into a cold block.
00076 ///
00077 /// This is the weight for a branch taken toward a block marked
00078 /// cold.  A block is marked cold if it's postdominated by a
00079 /// block containing a call to a cold function.  Cold functions
00080 /// are those marked with attribute 'cold'.
00081 static const uint32_t CC_TAKEN_WEIGHT = 4;
00082 
00083 /// \brief Weight for a branch not-taken into a cold block.
00084 ///
00085 /// This is the weight for a branch not taken toward a block marked
00086 /// cold.
00087 static const uint32_t CC_NONTAKEN_WEIGHT = 64;
00088 
00089 static const uint32_t PH_TAKEN_WEIGHT = 20;
00090 static const uint32_t PH_NONTAKEN_WEIGHT = 12;
00091 
00092 static const uint32_t ZH_TAKEN_WEIGHT = 20;
00093 static const uint32_t ZH_NONTAKEN_WEIGHT = 12;
00094 
00095 static const uint32_t FPH_TAKEN_WEIGHT = 20;
00096 static const uint32_t FPH_NONTAKEN_WEIGHT = 12;
00097 
00098 /// \brief Invoke-terminating normal branch taken weight
00099 ///
00100 /// This is the weight for branching to the normal destination of an invoke
00101 /// instruction. We expect this to happen most of the time. Set the weight to an
00102 /// absurdly high value so that nested loops subsume it.
00103 static const uint32_t IH_TAKEN_WEIGHT = 1024 * 1024 - 1;
00104 
00105 /// \brief Invoke-terminating normal branch not-taken weight.
00106 ///
00107 /// This is the weight for branching to the unwind destination of an invoke
00108 /// instruction. This is essentially never taken.
00109 static const uint32_t IH_NONTAKEN_WEIGHT = 1;
00110 
00111 /// \brief Calculate edge weights for successors lead to unreachable.
00112 ///
00113 /// Predict that a successor which leads necessarily to an
00114 /// unreachable-terminated block as extremely unlikely.
00115 bool BranchProbabilityInfo::calcUnreachableHeuristics(BasicBlock *BB) {
00116   TerminatorInst *TI = BB->getTerminator();
00117   if (TI->getNumSuccessors() == 0) {
00118     if (isa<UnreachableInst>(TI))
00119       PostDominatedByUnreachable.insert(BB);
00120     return false;
00121   }
00122 
00123   SmallVector<unsigned, 4> UnreachableEdges;
00124   SmallVector<unsigned, 4> ReachableEdges;
00125 
00126   for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
00127     if (PostDominatedByUnreachable.count(*I))
00128       UnreachableEdges.push_back(I.getSuccessorIndex());
00129     else
00130       ReachableEdges.push_back(I.getSuccessorIndex());
00131   }
00132 
00133   // If all successors are in the set of blocks post-dominated by unreachable,
00134   // this block is too.
00135   if (UnreachableEdges.size() == TI->getNumSuccessors())
00136     PostDominatedByUnreachable.insert(BB);
00137 
00138   // Skip probabilities if this block has a single successor or if all were
00139   // reachable.
00140   if (TI->getNumSuccessors() == 1 || UnreachableEdges.empty())
00141     return false;
00142 
00143   // If the terminator is an InvokeInst, check only the normal destination block
00144   // as the unwind edge of InvokeInst is also very unlikely taken.
00145   if (auto *II = dyn_cast<InvokeInst>(TI))
00146     if (PostDominatedByUnreachable.count(II->getNormalDest())) {
00147       PostDominatedByUnreachable.insert(BB);
00148       // Return false here so that edge weights for InvokeInst could be decided
00149       // in calcInvokeHeuristics().
00150       return false;
00151     }
00152 
00153   if (ReachableEdges.empty()) {
00154     BranchProbability Prob(1, UnreachableEdges.size());
00155     for (unsigned SuccIdx : UnreachableEdges)
00156       setEdgeProbability(BB, SuccIdx, Prob);
00157     return true;
00158   }
00159 
00160   BranchProbability UnreachableProb(UR_TAKEN_WEIGHT,
00161                                     (UR_TAKEN_WEIGHT + UR_NONTAKEN_WEIGHT) *
00162                                         UnreachableEdges.size());
00163   BranchProbability ReachableProb(UR_NONTAKEN_WEIGHT,
00164                                   (UR_TAKEN_WEIGHT + UR_NONTAKEN_WEIGHT) *
00165                                       ReachableEdges.size());
00166 
00167   for (unsigned SuccIdx : UnreachableEdges)
00168     setEdgeProbability(BB, SuccIdx, UnreachableProb);
00169   for (unsigned SuccIdx : ReachableEdges)
00170     setEdgeProbability(BB, SuccIdx, ReachableProb);
00171 
00172   return true;
00173 }
00174 
00175 // Propagate existing explicit probabilities from either profile data or
00176 // 'expect' intrinsic processing.
00177 bool BranchProbabilityInfo::calcMetadataWeights(BasicBlock *BB) {
00178   TerminatorInst *TI = BB->getTerminator();
00179   if (TI->getNumSuccessors() == 1)
00180     return false;
00181   if (!isa<BranchInst>(TI) && !isa<SwitchInst>(TI))
00182     return false;
00183 
00184   MDNode *WeightsNode = TI->getMetadata(LLVMContext::MD_prof);
00185   if (!WeightsNode)
00186     return false;
00187 
00188   // Check that the number of successors is manageable.
00189   assert(TI->getNumSuccessors() < UINT32_MAX && "Too many successors");
00190 
00191   // Ensure there are weights for all of the successors. Note that the first
00192   // operand to the metadata node is a name, not a weight.
00193   if (WeightsNode->getNumOperands() != TI->getNumSuccessors() + 1)
00194     return false;
00195 
00196   // Build up the final weights that will be used in a temporary buffer.
00197   // Compute the sum of all weights to later decide whether they need to
00198   // be scaled to fit in 32 bits.
00199   uint64_t WeightSum = 0;
00200   SmallVector<uint32_t, 2> Weights;
00201   Weights.reserve(TI->getNumSuccessors());
00202   for (unsigned i = 1, e = WeightsNode->getNumOperands(); i != e; ++i) {
00203     ConstantInt *Weight =
00204         mdconst::dyn_extract<ConstantInt>(WeightsNode->getOperand(i));
00205     if (!Weight)
00206       return false;
00207     assert(Weight->getValue().getActiveBits() <= 32 &&
00208            "Too many bits for uint32_t");
00209     Weights.push_back(Weight->getZExtValue());
00210     WeightSum += Weights.back();
00211   }
00212   assert(Weights.size() == TI->getNumSuccessors() && "Checked above");
00213 
00214   // If the sum of weights does not fit in 32 bits, scale every weight down
00215   // accordingly.
00216   uint64_t ScalingFactor =
00217       (WeightSum > UINT32_MAX) ? WeightSum / UINT32_MAX + 1 : 1;
00218 
00219   WeightSum = 0;
00220   for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) {
00221     Weights[i] /= ScalingFactor;
00222     WeightSum += Weights[i];
00223   }
00224 
00225   if (WeightSum == 0) {
00226     for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
00227       setEdgeProbability(BB, i, {1, e});
00228   } else {
00229     for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
00230       setEdgeProbability(BB, i, {Weights[i], static_cast<uint32_t>(WeightSum)});
00231   }
00232 
00233   assert(WeightSum <= UINT32_MAX &&
00234          "Expected weights to scale down to 32 bits");
00235 
00236   return true;
00237 }
00238 
00239 /// \brief Calculate edge weights for edges leading to cold blocks.
00240 ///
00241 /// A cold block is one post-dominated by  a block with a call to a
00242 /// cold function.  Those edges are unlikely to be taken, so we give
00243 /// them relatively low weight.
00244 ///
00245 /// Return true if we could compute the weights for cold edges.
00246 /// Return false, otherwise.
00247 bool BranchProbabilityInfo::calcColdCallHeuristics(BasicBlock *BB) {
00248   TerminatorInst *TI = BB->getTerminator();
00249   if (TI->getNumSuccessors() == 0)
00250     return false;
00251 
00252   // Determine which successors are post-dominated by a cold block.
00253   SmallVector<unsigned, 4> ColdEdges;
00254   SmallVector<unsigned, 4> NormalEdges;
00255   for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I)
00256     if (PostDominatedByColdCall.count(*I))
00257       ColdEdges.push_back(I.getSuccessorIndex());
00258     else
00259       NormalEdges.push_back(I.getSuccessorIndex());
00260 
00261   // If all successors are in the set of blocks post-dominated by cold calls,
00262   // this block is in the set post-dominated by cold calls.
00263   if (ColdEdges.size() == TI->getNumSuccessors())
00264     PostDominatedByColdCall.insert(BB);
00265   else {
00266     // Otherwise, if the block itself contains a cold function, add it to the
00267     // set of blocks postdominated by a cold call.
00268     assert(!PostDominatedByColdCall.count(BB));
00269     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
00270       if (CallInst *CI = dyn_cast<CallInst>(I))
00271         if (CI->hasFnAttr(Attribute::Cold)) {
00272           PostDominatedByColdCall.insert(BB);
00273           break;
00274         }
00275   }
00276 
00277   // Skip probabilities if this block has a single successor.
00278   if (TI->getNumSuccessors() == 1 || ColdEdges.empty())
00279     return false;
00280 
00281   if (NormalEdges.empty()) {
00282     BranchProbability Prob(1, ColdEdges.size());
00283     for (unsigned SuccIdx : ColdEdges)
00284       setEdgeProbability(BB, SuccIdx, Prob);
00285     return true;
00286   }
00287 
00288   BranchProbability ColdProb(CC_TAKEN_WEIGHT,
00289                              (CC_TAKEN_WEIGHT + CC_NONTAKEN_WEIGHT) *
00290                                  ColdEdges.size());
00291   BranchProbability NormalProb(CC_NONTAKEN_WEIGHT,
00292                                (CC_TAKEN_WEIGHT + CC_NONTAKEN_WEIGHT) *
00293                                    NormalEdges.size());
00294 
00295   for (unsigned SuccIdx : ColdEdges)
00296     setEdgeProbability(BB, SuccIdx, ColdProb);
00297   for (unsigned SuccIdx : NormalEdges)
00298     setEdgeProbability(BB, SuccIdx, NormalProb);
00299 
00300   return true;
00301 }
00302 
00303 // Calculate Edge Weights using "Pointer Heuristics". Predict a comparsion
00304 // between two pointer or pointer and NULL will fail.
00305 bool BranchProbabilityInfo::calcPointerHeuristics(BasicBlock *BB) {
00306   BranchInst * BI = dyn_cast<BranchInst>(BB->getTerminator());
00307   if (!BI || !BI->isConditional())
00308     return false;
00309 
00310   Value *Cond = BI->getCondition();
00311   ICmpInst *CI = dyn_cast<ICmpInst>(Cond);
00312   if (!CI || !CI->isEquality())
00313     return false;
00314 
00315   Value *LHS = CI->getOperand(0);
00316 
00317   if (!LHS->getType()->isPointerTy())
00318     return false;
00319 
00320   assert(CI->getOperand(1)->getType()->isPointerTy());
00321 
00322   // p != 0   ->   isProb = true
00323   // p == 0   ->   isProb = false
00324   // p != q   ->   isProb = true
00325   // p == q   ->   isProb = false;
00326   unsigned TakenIdx = 0, NonTakenIdx = 1;
00327   bool isProb = CI->getPredicate() == ICmpInst::ICMP_NE;
00328   if (!isProb)
00329     std::swap(TakenIdx, NonTakenIdx);
00330 
00331   BranchProbability TakenProb(PH_TAKEN_WEIGHT,
00332                               PH_TAKEN_WEIGHT + PH_NONTAKEN_WEIGHT);
00333   setEdgeProbability(BB, TakenIdx, TakenProb);
00334   setEdgeProbability(BB, NonTakenIdx, TakenProb.getCompl());
00335   return true;
00336 }
00337 
00338 // Calculate Edge Weights using "Loop Branch Heuristics". Predict backedges
00339 // as taken, exiting edges as not-taken.
00340 bool BranchProbabilityInfo::calcLoopBranchHeuristics(BasicBlock *BB,
00341                                                      const LoopInfo &LI) {
00342   Loop *L = LI.getLoopFor(BB);
00343   if (!L)
00344     return false;
00345 
00346   SmallVector<unsigned, 8> BackEdges;
00347   SmallVector<unsigned, 8> ExitingEdges;
00348   SmallVector<unsigned, 8> InEdges; // Edges from header to the loop.
00349 
00350   for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
00351     if (!L->contains(*I))
00352       ExitingEdges.push_back(I.getSuccessorIndex());
00353     else if (L->getHeader() == *I)
00354       BackEdges.push_back(I.getSuccessorIndex());
00355     else
00356       InEdges.push_back(I.getSuccessorIndex());
00357   }
00358 
00359   if (BackEdges.empty() && ExitingEdges.empty())
00360     return false;
00361 
00362   // Collect the sum of probabilities of back-edges/in-edges/exiting-edges, and
00363   // normalize them so that they sum up to one.
00364   SmallVector<BranchProbability, 4> Probs(3, BranchProbability::getZero());
00365   unsigned Denom = (BackEdges.empty() ? 0 : LBH_TAKEN_WEIGHT) +
00366                    (InEdges.empty() ? 0 : LBH_TAKEN_WEIGHT) +
00367                    (ExitingEdges.empty() ? 0 : LBH_NONTAKEN_WEIGHT);
00368   if (!BackEdges.empty())
00369     Probs[0] = BranchProbability(LBH_TAKEN_WEIGHT, Denom);
00370   if (!InEdges.empty())
00371     Probs[1] = BranchProbability(LBH_TAKEN_WEIGHT, Denom);
00372   if (!ExitingEdges.empty())
00373     Probs[2] = BranchProbability(LBH_NONTAKEN_WEIGHT, Denom);
00374 
00375   if (uint32_t numBackEdges = BackEdges.size()) {
00376     auto Prob = Probs[0] / numBackEdges;
00377     for (unsigned SuccIdx : BackEdges)
00378       setEdgeProbability(BB, SuccIdx, Prob);
00379   }
00380 
00381   if (uint32_t numInEdges = InEdges.size()) {
00382     auto Prob = Probs[1] / numInEdges;
00383     for (unsigned SuccIdx : InEdges)
00384       setEdgeProbability(BB, SuccIdx, Prob);
00385   }
00386 
00387   if (uint32_t numExitingEdges = ExitingEdges.size()) {
00388     auto Prob = Probs[2] / numExitingEdges;
00389     for (unsigned SuccIdx : ExitingEdges)
00390       setEdgeProbability(BB, SuccIdx, Prob);
00391   }
00392 
00393   return true;
00394 }
00395 
00396 bool BranchProbabilityInfo::calcZeroHeuristics(BasicBlock *BB) {
00397   BranchInst * BI = dyn_cast<BranchInst>(BB->getTerminator());
00398   if (!BI || !BI->isConditional())
00399     return false;
00400 
00401   Value *Cond = BI->getCondition();
00402   ICmpInst *CI = dyn_cast<ICmpInst>(Cond);
00403   if (!CI)
00404     return false;
00405 
00406   Value *RHS = CI->getOperand(1);
00407   ConstantInt *CV = dyn_cast<ConstantInt>(RHS);
00408   if (!CV)
00409     return false;
00410 
00411   // If the LHS is the result of AND'ing a value with a single bit bitmask,
00412   // we don't have information about probabilities.
00413   if (Instruction *LHS = dyn_cast<Instruction>(CI->getOperand(0)))
00414     if (LHS->getOpcode() == Instruction::And)
00415       if (ConstantInt *AndRHS = dyn_cast<ConstantInt>(LHS->getOperand(1)))
00416         if (AndRHS->getUniqueInteger().isPowerOf2())
00417           return false;
00418 
00419   bool isProb;
00420   if (CV->isZero()) {
00421     switch (CI->getPredicate()) {
00422     case CmpInst::ICMP_EQ:
00423       // X == 0   ->  Unlikely
00424       isProb = false;
00425       break;
00426     case CmpInst::ICMP_NE:
00427       // X != 0   ->  Likely
00428       isProb = true;
00429       break;
00430     case CmpInst::ICMP_SLT:
00431       // X < 0   ->  Unlikely
00432       isProb = false;
00433       break;
00434     case CmpInst::ICMP_SGT:
00435       // X > 0   ->  Likely
00436       isProb = true;
00437       break;
00438     default:
00439       return false;
00440     }
00441   } else if (CV->isOne() && CI->getPredicate() == CmpInst::ICMP_SLT) {
00442     // InstCombine canonicalizes X <= 0 into X < 1.
00443     // X <= 0   ->  Unlikely
00444     isProb = false;
00445   } else if (CV->isAllOnesValue()) {
00446     switch (CI->getPredicate()) {
00447     case CmpInst::ICMP_EQ:
00448       // X == -1  ->  Unlikely
00449       isProb = false;
00450       break;
00451     case CmpInst::ICMP_NE:
00452       // X != -1  ->  Likely
00453       isProb = true;
00454       break;
00455     case CmpInst::ICMP_SGT:
00456       // InstCombine canonicalizes X >= 0 into X > -1.
00457       // X >= 0   ->  Likely
00458       isProb = true;
00459       break;
00460     default:
00461       return false;
00462     }
00463   } else {
00464     return false;
00465   }
00466 
00467   unsigned TakenIdx = 0, NonTakenIdx = 1;
00468 
00469   if (!isProb)
00470     std::swap(TakenIdx, NonTakenIdx);
00471 
00472   BranchProbability TakenProb(ZH_TAKEN_WEIGHT,
00473                               ZH_TAKEN_WEIGHT + ZH_NONTAKEN_WEIGHT);
00474   setEdgeProbability(BB, TakenIdx, TakenProb);
00475   setEdgeProbability(BB, NonTakenIdx, TakenProb.getCompl());
00476   return true;
00477 }
00478 
00479 bool BranchProbabilityInfo::calcFloatingPointHeuristics(BasicBlock *BB) {
00480   BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
00481   if (!BI || !BI->isConditional())
00482     return false;
00483 
00484   Value *Cond = BI->getCondition();
00485   FCmpInst *FCmp = dyn_cast<FCmpInst>(Cond);
00486   if (!FCmp)
00487     return false;
00488 
00489   bool isProb;
00490   if (FCmp->isEquality()) {
00491     // f1 == f2 -> Unlikely
00492     // f1 != f2 -> Likely
00493     isProb = !FCmp->isTrueWhenEqual();
00494   } else if (FCmp->getPredicate() == FCmpInst::FCMP_ORD) {
00495     // !isnan -> Likely
00496     isProb = true;
00497   } else if (FCmp->getPredicate() == FCmpInst::FCMP_UNO) {
00498     // isnan -> Unlikely
00499     isProb = false;
00500   } else {
00501     return false;
00502   }
00503 
00504   unsigned TakenIdx = 0, NonTakenIdx = 1;
00505 
00506   if (!isProb)
00507     std::swap(TakenIdx, NonTakenIdx);
00508 
00509   BranchProbability TakenProb(FPH_TAKEN_WEIGHT,
00510                               FPH_TAKEN_WEIGHT + FPH_NONTAKEN_WEIGHT);
00511   setEdgeProbability(BB, TakenIdx, TakenProb);
00512   setEdgeProbability(BB, NonTakenIdx, TakenProb.getCompl());
00513   return true;
00514 }
00515 
00516 bool BranchProbabilityInfo::calcInvokeHeuristics(BasicBlock *BB) {
00517   InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator());
00518   if (!II)
00519     return false;
00520 
00521   BranchProbability TakenProb(IH_TAKEN_WEIGHT,
00522                               IH_TAKEN_WEIGHT + IH_NONTAKEN_WEIGHT);
00523   setEdgeProbability(BB, 0 /*Index for Normal*/, TakenProb);
00524   setEdgeProbability(BB, 1 /*Index for Unwind*/, TakenProb.getCompl());
00525   return true;
00526 }
00527 
00528 void BranchProbabilityInfo::releaseMemory() {
00529   Probs.clear();
00530 }
00531 
00532 void BranchProbabilityInfo::print(raw_ostream &OS) const {
00533   OS << "---- Branch Probabilities ----\n";
00534   // We print the probabilities from the last function the analysis ran over,
00535   // or the function it is currently running over.
00536   assert(LastF && "Cannot print prior to running over a function");
00537   for (const auto &BI : *LastF) {
00538     for (succ_const_iterator SI = succ_begin(&BI), SE = succ_end(&BI); SI != SE;
00539          ++SI) {
00540       printEdgeProbability(OS << "  ", &BI, *SI);
00541     }
00542   }
00543 }
00544 
00545 bool BranchProbabilityInfo::
00546 isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const {
00547   // Hot probability is at least 4/5 = 80%
00548   // FIXME: Compare against a static "hot" BranchProbability.
00549   return getEdgeProbability(Src, Dst) > BranchProbability(4, 5);
00550 }
00551 
00552 BasicBlock *BranchProbabilityInfo::getHotSucc(BasicBlock *BB) const {
00553   auto MaxProb = BranchProbability::getZero();
00554   BasicBlock *MaxSucc = nullptr;
00555 
00556   for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
00557     BasicBlock *Succ = *I;
00558     auto Prob = getEdgeProbability(BB, Succ);
00559     if (Prob > MaxProb) {
00560       MaxProb = Prob;
00561       MaxSucc = Succ;
00562     }
00563   }
00564 
00565   // Hot probability is at least 4/5 = 80%
00566   if (MaxProb > BranchProbability(4, 5))
00567     return MaxSucc;
00568 
00569   return nullptr;
00570 }
00571 
00572 /// Get the raw edge probability for the edge. If can't find it, return a
00573 /// default probability 1/N where N is the number of successors. Here an edge is
00574 /// specified using PredBlock and an
00575 /// index to the successors.
00576 BranchProbability
00577 BranchProbabilityInfo::getEdgeProbability(const BasicBlock *Src,
00578                                           unsigned IndexInSuccessors) const {
00579   auto I = Probs.find(std::make_pair(Src, IndexInSuccessors));
00580 
00581   if (I != Probs.end())
00582     return I->second;
00583 
00584   return {1,
00585           static_cast<uint32_t>(std::distance(succ_begin(Src), succ_end(Src)))};
00586 }
00587 
00588 BranchProbability
00589 BranchProbabilityInfo::getEdgeProbability(const BasicBlock *Src,
00590                                           succ_const_iterator Dst) const {
00591   return getEdgeProbability(Src, Dst.getSuccessorIndex());
00592 }
00593 
00594 /// Get the raw edge probability calculated for the block pair. This returns the
00595 /// sum of all raw edge probabilities from Src to Dst.
00596 BranchProbability
00597 BranchProbabilityInfo::getEdgeProbability(const BasicBlock *Src,
00598                                           const BasicBlock *Dst) const {
00599   auto Prob = BranchProbability::getZero();
00600   bool FoundProb = false;
00601   for (succ_const_iterator I = succ_begin(Src), E = succ_end(Src); I != E; ++I)
00602     if (*I == Dst) {
00603       auto MapI = Probs.find(std::make_pair(Src, I.getSuccessorIndex()));
00604       if (MapI != Probs.end()) {
00605         FoundProb = true;
00606         Prob += MapI->second;
00607       }
00608     }
00609   uint32_t succ_num = std::distance(succ_begin(Src), succ_end(Src));
00610   return FoundProb ? Prob : BranchProbability(1, succ_num);
00611 }
00612 
00613 /// Set the edge probability for a given edge specified by PredBlock and an
00614 /// index to the successors.
00615 void BranchProbabilityInfo::setEdgeProbability(const BasicBlock *Src,
00616                                                unsigned IndexInSuccessors,
00617                                                BranchProbability Prob) {
00618   Probs[std::make_pair(Src, IndexInSuccessors)] = Prob;
00619   DEBUG(dbgs() << "set edge " << Src->getName() << " -> " << IndexInSuccessors
00620                << " successor probability to " << Prob << "\n");
00621 }
00622 
00623 raw_ostream &
00624 BranchProbabilityInfo::printEdgeProbability(raw_ostream &OS,
00625                                             const BasicBlock *Src,
00626                                             const BasicBlock *Dst) const {
00627 
00628   const BranchProbability Prob = getEdgeProbability(Src, Dst);
00629   OS << "edge " << Src->getName() << " -> " << Dst->getName()
00630      << " probability is " << Prob
00631      << (isEdgeHot(Src, Dst) ? " [HOT edge]\n" : "\n");
00632 
00633   return OS;
00634 }
00635 
00636 void BranchProbabilityInfo::calculate(Function &F, const LoopInfo& LI) {
00637   DEBUG(dbgs() << "---- Branch Probability Info : " << F.getName()
00638                << " ----\n\n");
00639   LastF = &F; // Store the last function we ran on for printing.
00640   assert(PostDominatedByUnreachable.empty());
00641   assert(PostDominatedByColdCall.empty());
00642 
00643   // Walk the basic blocks in post-order so that we can build up state about
00644   // the successors of a block iteratively.
00645   for (auto BB : post_order(&F.getEntryBlock())) {
00646     DEBUG(dbgs() << "Computing probabilities for " << BB->getName() << "\n");
00647     if (calcUnreachableHeuristics(BB))
00648       continue;
00649     if (calcMetadataWeights(BB))
00650       continue;
00651     if (calcColdCallHeuristics(BB))
00652       continue;
00653     if (calcLoopBranchHeuristics(BB, LI))
00654       continue;
00655     if (calcPointerHeuristics(BB))
00656       continue;
00657     if (calcZeroHeuristics(BB))
00658       continue;
00659     if (calcFloatingPointHeuristics(BB))
00660       continue;
00661     calcInvokeHeuristics(BB);
00662   }
00663 
00664   PostDominatedByUnreachable.clear();
00665   PostDominatedByColdCall.clear();
00666 }
00667 
00668 void BranchProbabilityInfoWrapperPass::getAnalysisUsage(
00669     AnalysisUsage &AU) const {
00670   AU.addRequired<LoopInfoWrapperPass>();
00671   AU.setPreservesAll();
00672 }
00673 
00674 bool BranchProbabilityInfoWrapperPass::runOnFunction(Function &F) {
00675   const LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
00676   BPI.calculate(F, LI);
00677   return false;
00678 }
00679 
00680 void BranchProbabilityInfoWrapperPass::releaseMemory() { BPI.releaseMemory(); }
00681 
00682 void BranchProbabilityInfoWrapperPass::print(raw_ostream &OS,
00683                                              const Module *) const {
00684   BPI.print(OS);
00685 }