Home | History | Annotate | Download | only in Analysis
      1 //===-- BranchProbabilityInfo.cpp - Branch Probability Analysis -----------===//
      2 //
      3 //                     The LLVM Compiler Infrastructure
      4 //
      5 // This file is distributed under the University of Illinois Open Source
      6 // License. See LICENSE.TXT for details.
      7 //
      8 //===----------------------------------------------------------------------===//
      9 //
     10 // Loops should be simplified before this analysis.
     11 //
     12 //===----------------------------------------------------------------------===//
     13 
     14 #include "llvm/Analysis/BranchProbabilityInfo.h"
     15 #include "llvm/ADT/PostOrderIterator.h"
     16 #include "llvm/Analysis/LoopInfo.h"
     17 #include "llvm/IR/Constants.h"
     18 #include "llvm/IR/Function.h"
     19 #include "llvm/IR/Instructions.h"
     20 #include "llvm/IR/LLVMContext.h"
     21 #include "llvm/IR/Metadata.h"
     22 #include "llvm/Support/CFG.h"
     23 #include "llvm/Support/Debug.h"
     24 
     25 using namespace llvm;
     26 
     27 INITIALIZE_PASS_BEGIN(BranchProbabilityInfo, "branch-prob",
     28                       "Branch Probability Analysis", false, true)
     29 INITIALIZE_PASS_DEPENDENCY(LoopInfo)
     30 INITIALIZE_PASS_END(BranchProbabilityInfo, "branch-prob",
     31                     "Branch Probability Analysis", false, true)
     32 
     33 char BranchProbabilityInfo::ID = 0;
     34 
     35 // Weights are for internal use only. They are used by heuristics to help to
     36 // estimate edges' probability. Example:
     37 //
     38 // Using "Loop Branch Heuristics" we predict weights of edges for the
     39 // block BB2.
     40 //         ...
     41 //          |
     42 //          V
     43 //         BB1<-+
     44 //          |   |
     45 //          |   | (Weight = 124)
     46 //          V   |
     47 //         BB2--+
     48 //          |
     49 //          | (Weight = 4)
     50 //          V
     51 //         BB3
     52 //
     53 // Probability of the edge BB2->BB1 = 124 / (124 + 4) = 0.96875
     54 // Probability of the edge BB2->BB3 = 4 / (124 + 4) = 0.03125
     55 static const uint32_t LBH_TAKEN_WEIGHT = 124;
     56 static const uint32_t LBH_NONTAKEN_WEIGHT = 4;
     57 
     58 /// \brief Unreachable-terminating branch taken weight.
     59 ///
     60 /// This is the weight for a branch being taken to a block that terminates
     61 /// (eventually) in unreachable. These are predicted as unlikely as possible.
     62 static const uint32_t UR_TAKEN_WEIGHT = 1;
     63 
     64 /// \brief Unreachable-terminating branch not-taken weight.
     65 ///
     66 /// This is the weight for a branch not being taken toward a block that
     67 /// terminates (eventually) in unreachable. Such a branch is essentially never
     68 /// taken. Set the weight to an absurdly high value so that nested loops don't
     69 /// easily subsume it.
     70 static const uint32_t UR_NONTAKEN_WEIGHT = 1024*1024 - 1;
     71 
     72 /// \brief Weight for a branch taken going into a cold block.
     73 ///
     74 /// This is the weight for a branch taken toward a block marked
     75 /// cold.  A block is marked cold if it's postdominated by a
     76 /// block containing a call to a cold function.  Cold functions
     77 /// are those marked with attribute 'cold'.
     78 static const uint32_t CC_TAKEN_WEIGHT = 4;
     79 
     80 /// \brief Weight for a branch not-taken into a cold block.
     81 ///
     82 /// This is the weight for a branch not taken toward a block marked
     83 /// cold.
     84 static const uint32_t CC_NONTAKEN_WEIGHT = 64;
     85 
     86 static const uint32_t PH_TAKEN_WEIGHT = 20;
     87 static const uint32_t PH_NONTAKEN_WEIGHT = 12;
     88 
     89 static const uint32_t ZH_TAKEN_WEIGHT = 20;
     90 static const uint32_t ZH_NONTAKEN_WEIGHT = 12;
     91 
     92 static const uint32_t FPH_TAKEN_WEIGHT = 20;
     93 static const uint32_t FPH_NONTAKEN_WEIGHT = 12;
     94 
     95 /// \brief Invoke-terminating normal branch taken weight
     96 ///
     97 /// This is the weight for branching to the normal destination of an invoke
     98 /// instruction. We expect this to happen most of the time. Set the weight to an
     99 /// absurdly high value so that nested loops subsume it.
    100 static const uint32_t IH_TAKEN_WEIGHT = 1024 * 1024 - 1;
    101 
    102 /// \brief Invoke-terminating normal branch not-taken weight.
    103 ///
    104 /// This is the weight for branching to the unwind destination of an invoke
    105 /// instruction. This is essentially never taken.
    106 static const uint32_t IH_NONTAKEN_WEIGHT = 1;
    107 
    108 // Standard weight value. Used when none of the heuristics set weight for
    109 // the edge.
    110 static const uint32_t NORMAL_WEIGHT = 16;
    111 
    112 // Minimum weight of an edge. Please note, that weight is NEVER 0.
    113 static const uint32_t MIN_WEIGHT = 1;
    114 
    115 static uint32_t getMaxWeightFor(BasicBlock *BB) {
    116   return UINT32_MAX / BB->getTerminator()->getNumSuccessors();
    117 }
    118 
    119 
    120 /// \brief Calculate edge weights for successors lead to unreachable.
    121 ///
    122 /// Predict that a successor which leads necessarily to an
    123 /// unreachable-terminated block as extremely unlikely.
    124 bool BranchProbabilityInfo::calcUnreachableHeuristics(BasicBlock *BB) {
    125   TerminatorInst *TI = BB->getTerminator();
    126   if (TI->getNumSuccessors() == 0) {
    127     if (isa<UnreachableInst>(TI))
    128       PostDominatedByUnreachable.insert(BB);
    129     return false;
    130   }
    131 
    132   SmallVector<unsigned, 4> UnreachableEdges;
    133   SmallVector<unsigned, 4> ReachableEdges;
    134 
    135   for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
    136     if (PostDominatedByUnreachable.count(*I))
    137       UnreachableEdges.push_back(I.getSuccessorIndex());
    138     else
    139       ReachableEdges.push_back(I.getSuccessorIndex());
    140   }
    141 
    142   // If all successors are in the set of blocks post-dominated by unreachable,
    143   // this block is too.
    144   if (UnreachableEdges.size() == TI->getNumSuccessors())
    145     PostDominatedByUnreachable.insert(BB);
    146 
    147   // Skip probabilities if this block has a single successor or if all were
    148   // reachable.
    149   if (TI->getNumSuccessors() == 1 || UnreachableEdges.empty())
    150     return false;
    151 
    152   uint32_t UnreachableWeight =
    153     std::max(UR_TAKEN_WEIGHT / (unsigned)UnreachableEdges.size(), MIN_WEIGHT);
    154   for (SmallVectorImpl<unsigned>::iterator I = UnreachableEdges.begin(),
    155                                            E = UnreachableEdges.end();
    156        I != E; ++I)
    157     setEdgeWeight(BB, *I, UnreachableWeight);
    158 
    159   if (ReachableEdges.empty())
    160     return true;
    161   uint32_t ReachableWeight =
    162     std::max(UR_NONTAKEN_WEIGHT / (unsigned)ReachableEdges.size(),
    163              NORMAL_WEIGHT);
    164   for (SmallVectorImpl<unsigned>::iterator I = ReachableEdges.begin(),
    165                                            E = ReachableEdges.end();
    166        I != E; ++I)
    167     setEdgeWeight(BB, *I, ReachableWeight);
    168 
    169   return true;
    170 }
    171 
    172 // Propagate existing explicit probabilities from either profile data or
    173 // 'expect' intrinsic processing.
    174 bool BranchProbabilityInfo::calcMetadataWeights(BasicBlock *BB) {
    175   TerminatorInst *TI = BB->getTerminator();
    176   if (TI->getNumSuccessors() == 1)
    177     return false;
    178   if (!isa<BranchInst>(TI) && !isa<SwitchInst>(TI))
    179     return false;
    180 
    181   MDNode *WeightsNode = TI->getMetadata(LLVMContext::MD_prof);
    182   if (!WeightsNode)
    183     return false;
    184 
    185   // Ensure there are weights for all of the successors. Note that the first
    186   // operand to the metadata node is a name, not a weight.
    187   if (WeightsNode->getNumOperands() != TI->getNumSuccessors() + 1)
    188     return false;
    189 
    190   // Build up the final weights that will be used in a temporary buffer, but
    191   // don't add them until all weihts are present. Each weight value is clamped
    192   // to [1, getMaxWeightFor(BB)].
    193   uint32_t WeightLimit = getMaxWeightFor(BB);
    194   SmallVector<uint32_t, 2> Weights;
    195   Weights.reserve(TI->getNumSuccessors());
    196   for (unsigned i = 1, e = WeightsNode->getNumOperands(); i != e; ++i) {
    197     ConstantInt *Weight = dyn_cast<ConstantInt>(WeightsNode->getOperand(i));
    198     if (!Weight)
    199       return false;
    200     Weights.push_back(
    201       std::max<uint32_t>(1, Weight->getLimitedValue(WeightLimit)));
    202   }
    203   assert(Weights.size() == TI->getNumSuccessors() && "Checked above");
    204   for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
    205     setEdgeWeight(BB, i, Weights[i]);
    206 
    207   return true;
    208 }
    209 
    210 /// \brief Calculate edge weights for edges leading to cold blocks.
    211 ///
    212 /// A cold block is one post-dominated by  a block with a call to a
    213 /// cold function.  Those edges are unlikely to be taken, so we give
    214 /// them relatively low weight.
    215 ///
    216 /// Return true if we could compute the weights for cold edges.
    217 /// Return false, otherwise.
    218 bool BranchProbabilityInfo::calcColdCallHeuristics(BasicBlock *BB) {
    219   TerminatorInst *TI = BB->getTerminator();
    220   if (TI->getNumSuccessors() == 0)
    221     return false;
    222 
    223   // Determine which successors are post-dominated by a cold block.
    224   SmallVector<unsigned, 4> ColdEdges;
    225   SmallVector<unsigned, 4> NormalEdges;
    226   for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I)
    227     if (PostDominatedByColdCall.count(*I))
    228       ColdEdges.push_back(I.getSuccessorIndex());
    229     else
    230       NormalEdges.push_back(I.getSuccessorIndex());
    231 
    232   // If all successors are in the set of blocks post-dominated by cold calls,
    233   // this block is in the set post-dominated by cold calls.
    234   if (ColdEdges.size() == TI->getNumSuccessors())
    235     PostDominatedByColdCall.insert(BB);
    236   else {
    237     // Otherwise, if the block itself contains a cold function, add it to the
    238     // set of blocks postdominated by a cold call.
    239     assert(!PostDominatedByColdCall.count(BB));
    240     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
    241       if (CallInst *CI = dyn_cast<CallInst>(I))
    242         if (CI->hasFnAttr(Attribute::Cold)) {
    243           PostDominatedByColdCall.insert(BB);
    244           break;
    245         }
    246   }
    247 
    248   // Skip probabilities if this block has a single successor.
    249   if (TI->getNumSuccessors() == 1 || ColdEdges.empty())
    250     return false;
    251 
    252   uint32_t ColdWeight =
    253       std::max(CC_TAKEN_WEIGHT / (unsigned) ColdEdges.size(), MIN_WEIGHT);
    254   for (SmallVectorImpl<unsigned>::iterator I = ColdEdges.begin(),
    255                                            E = ColdEdges.end();
    256        I != E; ++I)
    257     setEdgeWeight(BB, *I, ColdWeight);
    258 
    259   if (NormalEdges.empty())
    260     return true;
    261   uint32_t NormalWeight = std::max(
    262       CC_NONTAKEN_WEIGHT / (unsigned) NormalEdges.size(), NORMAL_WEIGHT);
    263   for (SmallVectorImpl<unsigned>::iterator I = NormalEdges.begin(),
    264                                            E = NormalEdges.end();
    265        I != E; ++I)
    266     setEdgeWeight(BB, *I, NormalWeight);
    267 
    268   return true;
    269 }
    270 
    271 // Calculate Edge Weights using "Pointer Heuristics". Predict a comparsion
    272 // between two pointer or pointer and NULL will fail.
    273 bool BranchProbabilityInfo::calcPointerHeuristics(BasicBlock *BB) {
    274   BranchInst * BI = dyn_cast<BranchInst>(BB->getTerminator());
    275   if (!BI || !BI->isConditional())
    276     return false;
    277 
    278   Value *Cond = BI->getCondition();
    279   ICmpInst *CI = dyn_cast<ICmpInst>(Cond);
    280   if (!CI || !CI->isEquality())
    281     return false;
    282 
    283   Value *LHS = CI->getOperand(0);
    284 
    285   if (!LHS->getType()->isPointerTy())
    286     return false;
    287 
    288   assert(CI->getOperand(1)->getType()->isPointerTy());
    289 
    290   // p != 0   ->   isProb = true
    291   // p == 0   ->   isProb = false
    292   // p != q   ->   isProb = true
    293   // p == q   ->   isProb = false;
    294   unsigned TakenIdx = 0, NonTakenIdx = 1;
    295   bool isProb = CI->getPredicate() == ICmpInst::ICMP_NE;
    296   if (!isProb)
    297     std::swap(TakenIdx, NonTakenIdx);
    298 
    299   setEdgeWeight(BB, TakenIdx, PH_TAKEN_WEIGHT);
    300   setEdgeWeight(BB, NonTakenIdx, PH_NONTAKEN_WEIGHT);
    301   return true;
    302 }
    303 
    304 // Calculate Edge Weights using "Loop Branch Heuristics". Predict backedges
    305 // as taken, exiting edges as not-taken.
    306 bool BranchProbabilityInfo::calcLoopBranchHeuristics(BasicBlock *BB) {
    307   Loop *L = LI->getLoopFor(BB);
    308   if (!L)
    309     return false;
    310 
    311   SmallVector<unsigned, 8> BackEdges;
    312   SmallVector<unsigned, 8> ExitingEdges;
    313   SmallVector<unsigned, 8> InEdges; // Edges from header to the loop.
    314 
    315   for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
    316     if (!L->contains(*I))
    317       ExitingEdges.push_back(I.getSuccessorIndex());
    318     else if (L->getHeader() == *I)
    319       BackEdges.push_back(I.getSuccessorIndex());
    320     else
    321       InEdges.push_back(I.getSuccessorIndex());
    322   }
    323 
    324   if (uint32_t numBackEdges = BackEdges.size()) {
    325     uint32_t backWeight = LBH_TAKEN_WEIGHT / numBackEdges;
    326     if (backWeight < NORMAL_WEIGHT)
    327       backWeight = NORMAL_WEIGHT;
    328 
    329     for (SmallVectorImpl<unsigned>::iterator EI = BackEdges.begin(),
    330          EE = BackEdges.end(); EI != EE; ++EI) {
    331       setEdgeWeight(BB, *EI, backWeight);
    332     }
    333   }
    334 
    335   if (uint32_t numInEdges = InEdges.size()) {
    336     uint32_t inWeight = LBH_TAKEN_WEIGHT / numInEdges;
    337     if (inWeight < NORMAL_WEIGHT)
    338       inWeight = NORMAL_WEIGHT;
    339 
    340     for (SmallVectorImpl<unsigned>::iterator EI = InEdges.begin(),
    341          EE = InEdges.end(); EI != EE; ++EI) {
    342       setEdgeWeight(BB, *EI, inWeight);
    343     }
    344   }
    345 
    346   if (uint32_t numExitingEdges = ExitingEdges.size()) {
    347     uint32_t exitWeight = LBH_NONTAKEN_WEIGHT / numExitingEdges;
    348     if (exitWeight < MIN_WEIGHT)
    349       exitWeight = MIN_WEIGHT;
    350 
    351     for (SmallVectorImpl<unsigned>::iterator EI = ExitingEdges.begin(),
    352          EE = ExitingEdges.end(); EI != EE; ++EI) {
    353       setEdgeWeight(BB, *EI, exitWeight);
    354     }
    355   }
    356 
    357   return true;
    358 }
    359 
    360 bool BranchProbabilityInfo::calcZeroHeuristics(BasicBlock *BB) {
    361   BranchInst * BI = dyn_cast<BranchInst>(BB->getTerminator());
    362   if (!BI || !BI->isConditional())
    363     return false;
    364 
    365   Value *Cond = BI->getCondition();
    366   ICmpInst *CI = dyn_cast<ICmpInst>(Cond);
    367   if (!CI)
    368     return false;
    369 
    370   Value *RHS = CI->getOperand(1);
    371   ConstantInt *CV = dyn_cast<ConstantInt>(RHS);
    372   if (!CV)
    373     return false;
    374 
    375   bool isProb;
    376   if (CV->isZero()) {
    377     switch (CI->getPredicate()) {
    378     case CmpInst::ICMP_EQ:
    379       // X == 0   ->  Unlikely
    380       isProb = false;
    381       break;
    382     case CmpInst::ICMP_NE:
    383       // X != 0   ->  Likely
    384       isProb = true;
    385       break;
    386     case CmpInst::ICMP_SLT:
    387       // X < 0   ->  Unlikely
    388       isProb = false;
    389       break;
    390     case CmpInst::ICMP_SGT:
    391       // X > 0   ->  Likely
    392       isProb = true;
    393       break;
    394     default:
    395       return false;
    396     }
    397   } else if (CV->isOne() && CI->getPredicate() == CmpInst::ICMP_SLT) {
    398     // InstCombine canonicalizes X <= 0 into X < 1.
    399     // X <= 0   ->  Unlikely
    400     isProb = false;
    401   } else if (CV->isAllOnesValue() && CI->getPredicate() == CmpInst::ICMP_SGT) {
    402     // InstCombine canonicalizes X >= 0 into X > -1.
    403     // X >= 0   ->  Likely
    404     isProb = true;
    405   } else {
    406     return false;
    407   }
    408 
    409   unsigned TakenIdx = 0, NonTakenIdx = 1;
    410 
    411   if (!isProb)
    412     std::swap(TakenIdx, NonTakenIdx);
    413 
    414   setEdgeWeight(BB, TakenIdx, ZH_TAKEN_WEIGHT);
    415   setEdgeWeight(BB, NonTakenIdx, ZH_NONTAKEN_WEIGHT);
    416 
    417   return true;
    418 }
    419 
    420 bool BranchProbabilityInfo::calcFloatingPointHeuristics(BasicBlock *BB) {
    421   BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
    422   if (!BI || !BI->isConditional())
    423     return false;
    424 
    425   Value *Cond = BI->getCondition();
    426   FCmpInst *FCmp = dyn_cast<FCmpInst>(Cond);
    427   if (!FCmp)
    428     return false;
    429 
    430   bool isProb;
    431   if (FCmp->isEquality()) {
    432     // f1 == f2 -> Unlikely
    433     // f1 != f2 -> Likely
    434     isProb = !FCmp->isTrueWhenEqual();
    435   } else if (FCmp->getPredicate() == FCmpInst::FCMP_ORD) {
    436     // !isnan -> Likely
    437     isProb = true;
    438   } else if (FCmp->getPredicate() == FCmpInst::FCMP_UNO) {
    439     // isnan -> Unlikely
    440     isProb = false;
    441   } else {
    442     return false;
    443   }
    444 
    445   unsigned TakenIdx = 0, NonTakenIdx = 1;
    446 
    447   if (!isProb)
    448     std::swap(TakenIdx, NonTakenIdx);
    449 
    450   setEdgeWeight(BB, TakenIdx, FPH_TAKEN_WEIGHT);
    451   setEdgeWeight(BB, NonTakenIdx, FPH_NONTAKEN_WEIGHT);
    452 
    453   return true;
    454 }
    455 
    456 bool BranchProbabilityInfo::calcInvokeHeuristics(BasicBlock *BB) {
    457   InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator());
    458   if (!II)
    459     return false;
    460 
    461   setEdgeWeight(BB, 0/*Index for Normal*/, IH_TAKEN_WEIGHT);
    462   setEdgeWeight(BB, 1/*Index for Unwind*/, IH_NONTAKEN_WEIGHT);
    463   return true;
    464 }
    465 
    466 void BranchProbabilityInfo::getAnalysisUsage(AnalysisUsage &AU) const {
    467   AU.addRequired<LoopInfo>();
    468   AU.setPreservesAll();
    469 }
    470 
    471 bool BranchProbabilityInfo::runOnFunction(Function &F) {
    472   LastF = &F; // Store the last function we ran on for printing.
    473   LI = &getAnalysis<LoopInfo>();
    474   assert(PostDominatedByUnreachable.empty());
    475   assert(PostDominatedByColdCall.empty());
    476 
    477   // Walk the basic blocks in post-order so that we can build up state about
    478   // the successors of a block iteratively.
    479   for (po_iterator<BasicBlock *> I = po_begin(&F.getEntryBlock()),
    480                                  E = po_end(&F.getEntryBlock());
    481        I != E; ++I) {
    482     DEBUG(dbgs() << "Computing probabilities for " << I->getName() << "\n");
    483     if (calcUnreachableHeuristics(*I))
    484       continue;
    485     if (calcMetadataWeights(*I))
    486       continue;
    487     if (calcColdCallHeuristics(*I))
    488       continue;
    489     if (calcLoopBranchHeuristics(*I))
    490       continue;
    491     if (calcPointerHeuristics(*I))
    492       continue;
    493     if (calcZeroHeuristics(*I))
    494       continue;
    495     if (calcFloatingPointHeuristics(*I))
    496       continue;
    497     calcInvokeHeuristics(*I);
    498   }
    499 
    500   PostDominatedByUnreachable.clear();
    501   PostDominatedByColdCall.clear();
    502   return false;
    503 }
    504 
    505 void BranchProbabilityInfo::print(raw_ostream &OS, const Module *) const {
    506   OS << "---- Branch Probabilities ----\n";
    507   // We print the probabilities from the last function the analysis ran over,
    508   // or the function it is currently running over.
    509   assert(LastF && "Cannot print prior to running over a function");
    510   for (Function::const_iterator BI = LastF->begin(), BE = LastF->end();
    511        BI != BE; ++BI) {
    512     for (succ_const_iterator SI = succ_begin(BI), SE = succ_end(BI);
    513          SI != SE; ++SI) {
    514       printEdgeProbability(OS << "  ", BI, *SI);
    515     }
    516   }
    517 }
    518 
    519 uint32_t BranchProbabilityInfo::getSumForBlock(const BasicBlock *BB) const {
    520   uint32_t Sum = 0;
    521 
    522   for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
    523     uint32_t Weight = getEdgeWeight(BB, I.getSuccessorIndex());
    524     uint32_t PrevSum = Sum;
    525 
    526     Sum += Weight;
    527     assert(Sum > PrevSum); (void) PrevSum;
    528   }
    529 
    530   return Sum;
    531 }
    532 
    533 bool BranchProbabilityInfo::
    534 isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const {
    535   // Hot probability is at least 4/5 = 80%
    536   // FIXME: Compare against a static "hot" BranchProbability.
    537   return getEdgeProbability(Src, Dst) > BranchProbability(4, 5);
    538 }
    539 
    540 BasicBlock *BranchProbabilityInfo::getHotSucc(BasicBlock *BB) const {
    541   uint32_t Sum = 0;
    542   uint32_t MaxWeight = 0;
    543   BasicBlock *MaxSucc = 0;
    544 
    545   for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
    546     BasicBlock *Succ = *I;
    547     uint32_t Weight = getEdgeWeight(BB, Succ);
    548     uint32_t PrevSum = Sum;
    549 
    550     Sum += Weight;
    551     assert(Sum > PrevSum); (void) PrevSum;
    552 
    553     if (Weight > MaxWeight) {
    554       MaxWeight = Weight;
    555       MaxSucc = Succ;
    556     }
    557   }
    558 
    559   // Hot probability is at least 4/5 = 80%
    560   if (BranchProbability(MaxWeight, Sum) > BranchProbability(4, 5))
    561     return MaxSucc;
    562 
    563   return 0;
    564 }
    565 
    566 /// Get the raw edge weight for the edge. If can't find it, return
    567 /// DEFAULT_WEIGHT value. Here an edge is specified using PredBlock and an index
    568 /// to the successors.
    569 uint32_t BranchProbabilityInfo::
    570 getEdgeWeight(const BasicBlock *Src, unsigned IndexInSuccessors) const {
    571   DenseMap<Edge, uint32_t>::const_iterator I =
    572       Weights.find(std::make_pair(Src, IndexInSuccessors));
    573 
    574   if (I != Weights.end())
    575     return I->second;
    576 
    577   return DEFAULT_WEIGHT;
    578 }
    579 
    580 /// Get the raw edge weight calculated for the block pair. This returns the sum
    581 /// of all raw edge weights from Src to Dst.
    582 uint32_t BranchProbabilityInfo::
    583 getEdgeWeight(const BasicBlock *Src, const BasicBlock *Dst) const {
    584   uint32_t Weight = 0;
    585   DenseMap<Edge, uint32_t>::const_iterator MapI;
    586   for (succ_const_iterator I = succ_begin(Src), E = succ_end(Src); I != E; ++I)
    587     if (*I == Dst) {
    588       MapI = Weights.find(std::make_pair(Src, I.getSuccessorIndex()));
    589       if (MapI != Weights.end())
    590         Weight += MapI->second;
    591     }
    592   return (Weight == 0) ? DEFAULT_WEIGHT : Weight;
    593 }
    594 
    595 /// Set the edge weight for a given edge specified by PredBlock and an index
    596 /// to the successors.
    597 void BranchProbabilityInfo::
    598 setEdgeWeight(const BasicBlock *Src, unsigned IndexInSuccessors,
    599               uint32_t Weight) {
    600   Weights[std::make_pair(Src, IndexInSuccessors)] = Weight;
    601   DEBUG(dbgs() << "set edge " << Src->getName() << " -> "
    602                << IndexInSuccessors << " successor weight to "
    603                << Weight << "\n");
    604 }
    605 
    606 /// Get an edge's probability, relative to other out-edges from Src.
    607 BranchProbability BranchProbabilityInfo::
    608 getEdgeProbability(const BasicBlock *Src, unsigned IndexInSuccessors) const {
    609   uint32_t N = getEdgeWeight(Src, IndexInSuccessors);
    610   uint32_t D = getSumForBlock(Src);
    611 
    612   return BranchProbability(N, D);
    613 }
    614 
    615 /// Get the probability of going from Src to Dst. It returns the sum of all
    616 /// probabilities for edges from Src to Dst.
    617 BranchProbability BranchProbabilityInfo::
    618 getEdgeProbability(const BasicBlock *Src, const BasicBlock *Dst) const {
    619 
    620   uint32_t N = getEdgeWeight(Src, Dst);
    621   uint32_t D = getSumForBlock(Src);
    622 
    623   return BranchProbability(N, D);
    624 }
    625 
    626 raw_ostream &
    627 BranchProbabilityInfo::printEdgeProbability(raw_ostream &OS,
    628                                             const BasicBlock *Src,
    629                                             const BasicBlock *Dst) const {
    630 
    631   const BranchProbability Prob = getEdgeProbability(Src, Dst);
    632   OS << "edge " << Src->getName() << " -> " << Dst->getName()
    633      << " probability is " << Prob
    634      << (isEdgeHot(Src, Dst) ? " [HOT edge]\n" : "\n");
    635 
    636   return OS;
    637 }
    638