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 weights 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   // If the LHS is the result of AND'ing a value with a single bit bitmask,
00383   // we don't have information about probabilities.
00384   if (Instruction *LHS = dyn_cast<Instruction>(CI->getOperand(0)))
00385     if (LHS->getOpcode() == Instruction::And)
00386       if (ConstantInt *AndRHS = dyn_cast<ConstantInt>(LHS->getOperand(1)))
00387         if (AndRHS->getUniqueInteger().isPowerOf2())
00388           return false;
00389 
00390   bool isProb;
00391   if (CV->isZero()) {
00392     switch (CI->getPredicate()) {
00393     case CmpInst::ICMP_EQ:
00394       // X == 0   ->  Unlikely
00395       isProb = false;
00396       break;
00397     case CmpInst::ICMP_NE:
00398       // X != 0   ->  Likely
00399       isProb = true;
00400       break;
00401     case CmpInst::ICMP_SLT:
00402       // X < 0   ->  Unlikely
00403       isProb = false;
00404       break;
00405     case CmpInst::ICMP_SGT:
00406       // X > 0   ->  Likely
00407       isProb = true;
00408       break;
00409     default:
00410       return false;
00411     }
00412   } else if (CV->isOne() && CI->getPredicate() == CmpInst::ICMP_SLT) {
00413     // InstCombine canonicalizes X <= 0 into X < 1.
00414     // X <= 0   ->  Unlikely
00415     isProb = false;
00416   } else if (CV->isAllOnesValue()) {
00417     switch (CI->getPredicate()) {
00418     case CmpInst::ICMP_EQ:
00419       // X == -1  ->  Unlikely
00420       isProb = false;
00421       break;
00422     case CmpInst::ICMP_NE:
00423       // X != -1  ->  Likely
00424       isProb = true;
00425       break;
00426     case CmpInst::ICMP_SGT:
00427       // InstCombine canonicalizes X >= 0 into X > -1.
00428       // X >= 0   ->  Likely
00429       isProb = true;
00430       break;
00431     default:
00432       return false;
00433     }
00434   } else {
00435     return false;
00436   }
00437 
00438   unsigned TakenIdx = 0, NonTakenIdx = 1;
00439 
00440   if (!isProb)
00441     std::swap(TakenIdx, NonTakenIdx);
00442 
00443   setEdgeWeight(BB, TakenIdx, ZH_TAKEN_WEIGHT);
00444   setEdgeWeight(BB, NonTakenIdx, ZH_NONTAKEN_WEIGHT);
00445 
00446   return true;
00447 }
00448 
00449 bool BranchProbabilityInfo::calcFloatingPointHeuristics(BasicBlock *BB) {
00450   BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
00451   if (!BI || !BI->isConditional())
00452     return false;
00453 
00454   Value *Cond = BI->getCondition();
00455   FCmpInst *FCmp = dyn_cast<FCmpInst>(Cond);
00456   if (!FCmp)
00457     return false;
00458 
00459   bool isProb;
00460   if (FCmp->isEquality()) {
00461     // f1 == f2 -> Unlikely
00462     // f1 != f2 -> Likely
00463     isProb = !FCmp->isTrueWhenEqual();
00464   } else if (FCmp->getPredicate() == FCmpInst::FCMP_ORD) {
00465     // !isnan -> Likely
00466     isProb = true;
00467   } else if (FCmp->getPredicate() == FCmpInst::FCMP_UNO) {
00468     // isnan -> Unlikely
00469     isProb = false;
00470   } else {
00471     return false;
00472   }
00473 
00474   unsigned TakenIdx = 0, NonTakenIdx = 1;
00475 
00476   if (!isProb)
00477     std::swap(TakenIdx, NonTakenIdx);
00478 
00479   setEdgeWeight(BB, TakenIdx, FPH_TAKEN_WEIGHT);
00480   setEdgeWeight(BB, NonTakenIdx, FPH_NONTAKEN_WEIGHT);
00481 
00482   return true;
00483 }
00484 
00485 bool BranchProbabilityInfo::calcInvokeHeuristics(BasicBlock *BB) {
00486   InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator());
00487   if (!II)
00488     return false;
00489 
00490   setEdgeWeight(BB, 0/*Index for Normal*/, IH_TAKEN_WEIGHT);
00491   setEdgeWeight(BB, 1/*Index for Unwind*/, IH_NONTAKEN_WEIGHT);
00492   return true;
00493 }
00494 
00495 void BranchProbabilityInfo::getAnalysisUsage(AnalysisUsage &AU) const {
00496   AU.addRequired<LoopInfoWrapperPass>();
00497   AU.setPreservesAll();
00498 }
00499 
00500 bool BranchProbabilityInfo::runOnFunction(Function &F) {
00501   DEBUG(dbgs() << "---- Branch Probability Info : " << F.getName()
00502                << " ----\n\n");
00503   LastF = &F; // Store the last function we ran on for printing.
00504   LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
00505   assert(PostDominatedByUnreachable.empty());
00506   assert(PostDominatedByColdCall.empty());
00507 
00508   // Walk the basic blocks in post-order so that we can build up state about
00509   // the successors of a block iteratively.
00510   for (auto BB : post_order(&F.getEntryBlock())) {
00511     DEBUG(dbgs() << "Computing probabilities for " << BB->getName() << "\n");
00512     if (calcUnreachableHeuristics(BB))
00513       continue;
00514     if (calcMetadataWeights(BB))
00515       continue;
00516     if (calcColdCallHeuristics(BB))
00517       continue;
00518     if (calcLoopBranchHeuristics(BB))
00519       continue;
00520     if (calcPointerHeuristics(BB))
00521       continue;
00522     if (calcZeroHeuristics(BB))
00523       continue;
00524     if (calcFloatingPointHeuristics(BB))
00525       continue;
00526     calcInvokeHeuristics(BB);
00527   }
00528 
00529   PostDominatedByUnreachable.clear();
00530   PostDominatedByColdCall.clear();
00531   return false;
00532 }
00533 
00534 void BranchProbabilityInfo::print(raw_ostream &OS, const Module *) const {
00535   OS << "---- Branch Probabilities ----\n";
00536   // We print the probabilities from the last function the analysis ran over,
00537   // or the function it is currently running over.
00538   assert(LastF && "Cannot print prior to running over a function");
00539   for (Function::const_iterator BI = LastF->begin(), BE = LastF->end();
00540        BI != BE; ++BI) {
00541     for (succ_const_iterator SI = succ_begin(BI), SE = succ_end(BI);
00542          SI != SE; ++SI) {
00543       printEdgeProbability(OS << "  ", BI, *SI);
00544     }
00545   }
00546 }
00547 
00548 uint32_t BranchProbabilityInfo::getSumForBlock(const BasicBlock *BB) const {
00549   uint32_t Sum = 0;
00550 
00551   for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
00552     uint32_t Weight = getEdgeWeight(BB, I.getSuccessorIndex());
00553     uint32_t PrevSum = Sum;
00554 
00555     Sum += Weight;
00556     assert(Sum > PrevSum); (void) PrevSum;
00557   }
00558 
00559   return Sum;
00560 }
00561 
00562 bool BranchProbabilityInfo::
00563 isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const {
00564   // Hot probability is at least 4/5 = 80%
00565   // FIXME: Compare against a static "hot" BranchProbability.
00566   return getEdgeProbability(Src, Dst) > BranchProbability(4, 5);
00567 }
00568 
00569 BasicBlock *BranchProbabilityInfo::getHotSucc(BasicBlock *BB) const {
00570   uint32_t Sum = 0;
00571   uint32_t MaxWeight = 0;
00572   BasicBlock *MaxSucc = nullptr;
00573 
00574   for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
00575     BasicBlock *Succ = *I;
00576     uint32_t Weight = getEdgeWeight(BB, Succ);
00577     uint32_t PrevSum = Sum;
00578 
00579     Sum += Weight;
00580     assert(Sum > PrevSum); (void) PrevSum;
00581 
00582     if (Weight > MaxWeight) {
00583       MaxWeight = Weight;
00584       MaxSucc = Succ;
00585     }
00586   }
00587 
00588   // Hot probability is at least 4/5 = 80%
00589   if (BranchProbability(MaxWeight, Sum) > BranchProbability(4, 5))
00590     return MaxSucc;
00591 
00592   return nullptr;
00593 }
00594 
00595 /// Get the raw edge weight for the edge. If can't find it, return
00596 /// DEFAULT_WEIGHT value. Here an edge is specified using PredBlock and an index
00597 /// to the successors.
00598 uint32_t BranchProbabilityInfo::
00599 getEdgeWeight(const BasicBlock *Src, unsigned IndexInSuccessors) const {
00600   DenseMap<Edge, uint32_t>::const_iterator I =
00601       Weights.find(std::make_pair(Src, IndexInSuccessors));
00602 
00603   if (I != Weights.end())
00604     return I->second;
00605 
00606   return DEFAULT_WEIGHT;
00607 }
00608 
00609 uint32_t BranchProbabilityInfo::getEdgeWeight(const BasicBlock *Src,
00610                                               succ_const_iterator Dst) const {
00611   return getEdgeWeight(Src, Dst.getSuccessorIndex());
00612 }
00613 
00614 /// Get the raw edge weight calculated for the block pair. This returns the sum
00615 /// of all raw edge weights from Src to Dst.
00616 uint32_t BranchProbabilityInfo::
00617 getEdgeWeight(const BasicBlock *Src, const BasicBlock *Dst) const {
00618   uint32_t Weight = 0;
00619   DenseMap<Edge, uint32_t>::const_iterator MapI;
00620   for (succ_const_iterator I = succ_begin(Src), E = succ_end(Src); I != E; ++I)
00621     if (*I == Dst) {
00622       MapI = Weights.find(std::make_pair(Src, I.getSuccessorIndex()));
00623       if (MapI != Weights.end())
00624         Weight += MapI->second;
00625     }
00626   return (Weight == 0) ? DEFAULT_WEIGHT : Weight;
00627 }
00628 
00629 /// Set the edge weight for a given edge specified by PredBlock and an index
00630 /// to the successors.
00631 void BranchProbabilityInfo::
00632 setEdgeWeight(const BasicBlock *Src, unsigned IndexInSuccessors,
00633               uint32_t Weight) {
00634   Weights[std::make_pair(Src, IndexInSuccessors)] = Weight;
00635   DEBUG(dbgs() << "set edge " << Src->getName() << " -> "
00636                << IndexInSuccessors << " successor weight to "
00637                << Weight << "\n");
00638 }
00639 
00640 /// Get an edge's probability, relative to other out-edges from Src.
00641 BranchProbability BranchProbabilityInfo::
00642 getEdgeProbability(const BasicBlock *Src, unsigned IndexInSuccessors) const {
00643   uint32_t N = getEdgeWeight(Src, IndexInSuccessors);
00644   uint32_t D = getSumForBlock(Src);
00645 
00646   return BranchProbability(N, D);
00647 }
00648 
00649 /// Get the probability of going from Src to Dst. It returns the sum of all
00650 /// probabilities for edges from Src to Dst.
00651 BranchProbability BranchProbabilityInfo::
00652 getEdgeProbability(const BasicBlock *Src, const BasicBlock *Dst) const {
00653 
00654   uint32_t N = getEdgeWeight(Src, Dst);
00655   uint32_t D = getSumForBlock(Src);
00656 
00657   return BranchProbability(N, D);
00658 }
00659 
00660 raw_ostream &
00661 BranchProbabilityInfo::printEdgeProbability(raw_ostream &OS,
00662                                             const BasicBlock *Src,
00663                                             const BasicBlock *Dst) const {
00664 
00665   const BranchProbability Prob = getEdgeProbability(Src, Dst);
00666   OS << "edge " << Src->getName() << " -> " << Dst->getName()
00667      << " probability is " << Prob
00668      << (isEdgeHot(Src, Dst) ? " [HOT edge]\n" : "\n");
00669 
00670   return OS;
00671 }