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