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