LLVM API Documentation

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