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