Home | History | Annotate | Download | only in Analysis 
      1 //===-- BranchProbabilityInfo.cpp - Branch Probability Analysis -*- C++ -*-===//
      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/Constants.h"
     15 #include "llvm/Function.h"
     16 #include "llvm/Instructions.h"
     17 #include "llvm/LLVMContext.h"
     18 #include "llvm/Metadata.h"
     19 #include "llvm/Analysis/BranchProbabilityInfo.h"
     20 #include "llvm/Analysis/LoopInfo.h"
     21 #include "llvm/ADT/PostOrderIterator.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 static const uint32_t PH_TAKEN_WEIGHT = 20;
     73 static const uint32_t PH_NONTAKEN_WEIGHT = 12;
     74 
     75 static const uint32_t ZH_TAKEN_WEIGHT = 20;
     76 static const uint32_t ZH_NONTAKEN_WEIGHT = 12;
     77 
     78 static const uint32_t FPH_TAKEN_WEIGHT = 20;
     79 static const uint32_t FPH_NONTAKEN_WEIGHT = 12;
     80 
     81 // Standard weight value. Used when none of the heuristics set weight for
     82 // the edge.
     83 static const uint32_t NORMAL_WEIGHT = 16;
     84 
     85 // Minimum weight of an edge. Please note, that weight is NEVER 0.
     86 static const uint32_t MIN_WEIGHT = 1;
     87 
     88 static uint32_t getMaxWeightFor(BasicBlock *BB) {
     89   return UINT32_MAX / BB->getTerminator()->getNumSuccessors();
     90 }
     91 
     92 
     93 /// \brief Calculate edge weights for successors lead to unreachable.
     94 ///
     95 /// Predict that a successor which leads necessarily to an
     96 /// unreachable-terminated block as extremely unlikely.
     97 bool BranchProbabilityInfo::calcUnreachableHeuristics(BasicBlock *BB) {
     98   TerminatorInst *TI = BB->getTerminator();
     99   if (TI->getNumSuccessors() == 0) {
    100     if (isa<UnreachableInst>(TI))
    101       PostDominatedByUnreachable.insert(BB);
    102     return false;
    103   }
    104 
    105   SmallPtrSet<BasicBlock *, 4> UnreachableEdges;
    106   SmallPtrSet<BasicBlock *, 4> ReachableEdges;
    107 
    108   for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
    109     if (PostDominatedByUnreachable.count(*I))
    110       UnreachableEdges.insert(*I);
    111     else
    112       ReachableEdges.insert(*I);
    113   }
    114 
    115   // If all successors are in the set of blocks post-dominated by unreachable,
    116   // this block is too.
    117   if (UnreachableEdges.size() == TI->getNumSuccessors())
    118     PostDominatedByUnreachable.insert(BB);
    119 
    120   // Skip probabilities if this block has a single successor or if all were
    121   // reachable.
    122   if (TI->getNumSuccessors() == 1 || UnreachableEdges.empty())
    123     return false;
    124 
    125   uint32_t UnreachableWeight =
    126     std::max(UR_TAKEN_WEIGHT / UnreachableEdges.size(), MIN_WEIGHT);
    127   for (SmallPtrSet<BasicBlock *, 4>::iterator I = UnreachableEdges.begin(),
    128                                               E = UnreachableEdges.end();
    129        I != E; ++I)
    130     setEdgeWeight(BB, *I, UnreachableWeight);
    131 
    132   if (ReachableEdges.empty())
    133     return true;
    134   uint32_t ReachableWeight =
    135     std::max(UR_NONTAKEN_WEIGHT / ReachableEdges.size(), NORMAL_WEIGHT);
    136   for (SmallPtrSet<BasicBlock *, 4>::iterator I = ReachableEdges.begin(),
    137                                               E = ReachableEdges.end();
    138        I != E; ++I)
    139     setEdgeWeight(BB, *I, ReachableWeight);
    140 
    141   return true;
    142 }
    143 
    144 // Propagate existing explicit probabilities from either profile data or
    145 // 'expect' intrinsic processing.
    146 bool BranchProbabilityInfo::calcMetadataWeights(BasicBlock *BB) {
    147   TerminatorInst *TI = BB->getTerminator();
    148   if (TI->getNumSuccessors() == 1)
    149     return false;
    150   if (!isa<BranchInst>(TI) && !isa<SwitchInst>(TI))
    151     return false;
    152 
    153   MDNode *WeightsNode = TI->getMetadata(LLVMContext::MD_prof);
    154   if (!WeightsNode)
    155     return false;
    156 
    157   // Ensure there are weights for all of the successors. Note that the first
    158   // operand to the metadata node is a name, not a weight.
    159   if (WeightsNode->getNumOperands() != TI->getNumSuccessors() + 1)
    160     return false;
    161 
    162   // Build up the final weights that will be used in a temporary buffer, but
    163   // don't add them until all weihts are present. Each weight value is clamped
    164   // to [1, getMaxWeightFor(BB)].
    165   uint32_t WeightLimit = getMaxWeightFor(BB);
    166   SmallVector<uint32_t, 2> Weights;
    167   Weights.reserve(TI->getNumSuccessors());
    168   for (unsigned i = 1, e = WeightsNode->getNumOperands(); i != e; ++i) {
    169     ConstantInt *Weight = dyn_cast<ConstantInt>(WeightsNode->getOperand(i));
    170     if (!Weight)
    171       return false;
    172     Weights.push_back(
    173       std::max<uint32_t>(1, Weight->getLimitedValue(WeightLimit)));
    174   }
    175   assert(Weights.size() == TI->getNumSuccessors() && "Checked above");
    176   for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
    177     setEdgeWeight(BB, TI->getSuccessor(i), Weights[i]);
    178 
    179   return true;
    180 }
    181 
    182 // Calculate Edge Weights using "Pointer Heuristics". Predict a comparsion
    183 // between two pointer or pointer and NULL will fail.
    184 bool BranchProbabilityInfo::calcPointerHeuristics(BasicBlock *BB) {
    185   BranchInst * BI = dyn_cast<BranchInst>(BB->getTerminator());
    186   if (!BI || !BI->isConditional())
    187     return false;
    188 
    189   Value *Cond = BI->getCondition();
    190   ICmpInst *CI = dyn_cast<ICmpInst>(Cond);
    191   if (!CI || !CI->isEquality())
    192     return false;
    193 
    194   Value *LHS = CI->getOperand(0);
    195 
    196   if (!LHS->getType()->isPointerTy())
    197     return false;
    198 
    199   assert(CI->getOperand(1)->getType()->isPointerTy());
    200 
    201   BasicBlock *Taken = BI->getSuccessor(0);
    202   BasicBlock *NonTaken = BI->getSuccessor(1);
    203 
    204   // p != 0   ->   isProb = true
    205   // p == 0   ->   isProb = false
    206   // p != q   ->   isProb = true
    207   // p == q   ->   isProb = false;
    208   bool isProb = CI->getPredicate() == ICmpInst::ICMP_NE;
    209   if (!isProb)
    210     std::swap(Taken, NonTaken);
    211 
    212   setEdgeWeight(BB, Taken, PH_TAKEN_WEIGHT);
    213   setEdgeWeight(BB, NonTaken, PH_NONTAKEN_WEIGHT);
    214   return true;
    215 }
    216 
    217 // Calculate Edge Weights using "Loop Branch Heuristics". Predict backedges
    218 // as taken, exiting edges as not-taken.
    219 bool BranchProbabilityInfo::calcLoopBranchHeuristics(BasicBlock *BB) {
    220   Loop *L = LI->getLoopFor(BB);
    221   if (!L)
    222     return false;
    223 
    224   SmallPtrSet<BasicBlock *, 8> BackEdges;
    225   SmallPtrSet<BasicBlock *, 8> ExitingEdges;
    226   SmallPtrSet<BasicBlock *, 8> InEdges; // Edges from header to the loop.
    227 
    228   for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
    229     if (!L->contains(*I))
    230       ExitingEdges.insert(*I);
    231     else if (L->getHeader() == *I)
    232       BackEdges.insert(*I);
    233     else
    234       InEdges.insert(*I);
    235   }
    236 
    237   if (uint32_t numBackEdges = BackEdges.size()) {
    238     uint32_t backWeight = LBH_TAKEN_WEIGHT / numBackEdges;
    239     if (backWeight < NORMAL_WEIGHT)
    240       backWeight = NORMAL_WEIGHT;
    241 
    242     for (SmallPtrSet<BasicBlock *, 8>::iterator EI = BackEdges.begin(),
    243          EE = BackEdges.end(); EI != EE; ++EI) {
    244       BasicBlock *Back = *EI;
    245       setEdgeWeight(BB, Back, backWeight);
    246     }
    247   }
    248 
    249   if (uint32_t numInEdges = InEdges.size()) {
    250     uint32_t inWeight = LBH_TAKEN_WEIGHT / numInEdges;
    251     if (inWeight < NORMAL_WEIGHT)
    252       inWeight = NORMAL_WEIGHT;
    253 
    254     for (SmallPtrSet<BasicBlock *, 8>::iterator EI = InEdges.begin(),
    255          EE = InEdges.end(); EI != EE; ++EI) {
    256       BasicBlock *Back = *EI;
    257       setEdgeWeight(BB, Back, inWeight);
    258     }
    259   }
    260 
    261   if (uint32_t numExitingEdges = ExitingEdges.size()) {
    262     uint32_t exitWeight = LBH_NONTAKEN_WEIGHT / numExitingEdges;
    263     if (exitWeight < MIN_WEIGHT)
    264       exitWeight = MIN_WEIGHT;
    265 
    266     for (SmallPtrSet<BasicBlock *, 8>::iterator EI = ExitingEdges.begin(),
    267          EE = ExitingEdges.end(); EI != EE; ++EI) {
    268       BasicBlock *Exiting = *EI;
    269       setEdgeWeight(BB, Exiting, exitWeight);
    270     }
    271   }
    272 
    273   return true;
    274 }
    275 
    276 bool BranchProbabilityInfo::calcZeroHeuristics(BasicBlock *BB) {
    277   BranchInst * BI = dyn_cast<BranchInst>(BB->getTerminator());
    278   if (!BI || !BI->isConditional())
    279     return false;
    280 
    281   Value *Cond = BI->getCondition();
    282   ICmpInst *CI = dyn_cast<ICmpInst>(Cond);
    283   if (!CI)
    284     return false;
    285 
    286   Value *RHS = CI->getOperand(1);
    287   ConstantInt *CV = dyn_cast<ConstantInt>(RHS);
    288   if (!CV)
    289     return false;
    290 
    291   bool isProb;
    292   if (CV->isZero()) {
    293     switch (CI->getPredicate()) {
    294     case CmpInst::ICMP_EQ:
    295       // X == 0   ->  Unlikely
    296       isProb = false;
    297       break;
    298     case CmpInst::ICMP_NE:
    299       // X != 0   ->  Likely
    300       isProb = true;
    301       break;
    302     case CmpInst::ICMP_SLT:
    303       // X < 0   ->  Unlikely
    304       isProb = false;
    305       break;
    306     case CmpInst::ICMP_SGT:
    307       // X > 0   ->  Likely
    308       isProb = true;
    309       break;
    310     default:
    311       return false;
    312     }
    313   } else if (CV->isOne() && CI->getPredicate() == CmpInst::ICMP_SLT) {
    314     // InstCombine canonicalizes X <= 0 into X < 1.
    315     // X <= 0   ->  Unlikely
    316     isProb = false;
    317   } else if (CV->isAllOnesValue() && CI->getPredicate() == CmpInst::ICMP_SGT) {
    318     // InstCombine canonicalizes X >= 0 into X > -1.
    319     // X >= 0   ->  Likely
    320     isProb = true;
    321   } else {
    322     return false;
    323   }
    324 
    325   BasicBlock *Taken = BI->getSuccessor(0);
    326   BasicBlock *NonTaken = BI->getSuccessor(1);
    327 
    328   if (!isProb)
    329     std::swap(Taken, NonTaken);
    330 
    331   setEdgeWeight(BB, Taken, ZH_TAKEN_WEIGHT);
    332   setEdgeWeight(BB, NonTaken, ZH_NONTAKEN_WEIGHT);
    333 
    334   return true;
    335 }
    336 
    337 bool BranchProbabilityInfo::calcFloatingPointHeuristics(BasicBlock *BB) {
    338   BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
    339   if (!BI || !BI->isConditional())
    340     return false;
    341 
    342   Value *Cond = BI->getCondition();
    343   FCmpInst *FCmp = dyn_cast<FCmpInst>(Cond);
    344   if (!FCmp)
    345     return false;
    346 
    347   bool isProb;
    348   if (FCmp->isEquality()) {
    349     // f1 == f2 -> Unlikely
    350     // f1 != f2 -> Likely
    351     isProb = !FCmp->isTrueWhenEqual();
    352   } else if (FCmp->getPredicate() == FCmpInst::FCMP_ORD) {
    353     // !isnan -> Likely
    354     isProb = true;
    355   } else if (FCmp->getPredicate() == FCmpInst::FCMP_UNO) {
    356     // isnan -> Unlikely
    357     isProb = false;
    358   } else {
    359     return false;
    360   }
    361 
    362   BasicBlock *Taken = BI->getSuccessor(0);
    363   BasicBlock *NonTaken = BI->getSuccessor(1);
    364 
    365   if (!isProb)
    366     std::swap(Taken, NonTaken);
    367 
    368   setEdgeWeight(BB, Taken, FPH_TAKEN_WEIGHT);
    369   setEdgeWeight(BB, NonTaken, FPH_NONTAKEN_WEIGHT);
    370 
    371   return true;
    372 }
    373 
    374 void BranchProbabilityInfo::getAnalysisUsage(AnalysisUsage &AU) const {
    375   AU.addRequired<LoopInfo>();
    376   AU.setPreservesAll();
    377 }
    378 
    379 bool BranchProbabilityInfo::runOnFunction(Function &F) {
    380   LastF = &F; // Store the last function we ran on for printing.
    381   LI = &getAnalysis<LoopInfo>();
    382   assert(PostDominatedByUnreachable.empty());
    383 
    384   // Walk the basic blocks in post-order so that we can build up state about
    385   // the successors of a block iteratively.
    386   for (po_iterator<BasicBlock *> I = po_begin(&F.getEntryBlock()),
    387                                  E = po_end(&F.getEntryBlock());
    388        I != E; ++I) {
    389     DEBUG(dbgs() << "Computing probabilities for " << I->getName() << "\n");
    390     if (calcUnreachableHeuristics(*I))
    391       continue;
    392     if (calcMetadataWeights(*I))
    393       continue;
    394     if (calcLoopBranchHeuristics(*I))
    395       continue;
    396     if (calcPointerHeuristics(*I))
    397       continue;
    398     if (calcZeroHeuristics(*I))
    399       continue;
    400     calcFloatingPointHeuristics(*I);
    401   }
    402 
    403   PostDominatedByUnreachable.clear();
    404   return false;
    405 }
    406 
    407 void BranchProbabilityInfo::print(raw_ostream &OS, const Module *) const {
    408   OS << "---- Branch Probabilities ----\n";
    409   // We print the probabilities from the last function the analysis ran over,
    410   // or the function it is currently running over.
    411   assert(LastF && "Cannot print prior to running over a function");
    412   for (Function::const_iterator BI = LastF->begin(), BE = LastF->end();
    413        BI != BE; ++BI) {
    414     for (succ_const_iterator SI = succ_begin(BI), SE = succ_end(BI);
    415          SI != SE; ++SI) {
    416       printEdgeProbability(OS << "  ", BI, *SI);
    417     }
    418   }
    419 }
    420 
    421 uint32_t BranchProbabilityInfo::getSumForBlock(const BasicBlock *BB) const {
    422   uint32_t Sum = 0;
    423 
    424   for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
    425     const BasicBlock *Succ = *I;
    426     uint32_t Weight = getEdgeWeight(BB, Succ);
    427     uint32_t PrevSum = Sum;
    428 
    429     Sum += Weight;
    430     assert(Sum > PrevSum); (void) PrevSum;
    431   }
    432 
    433   return Sum;
    434 }
    435 
    436 bool BranchProbabilityInfo::
    437 isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const {
    438   // Hot probability is at least 4/5 = 80%
    439   // FIXME: Compare against a static "hot" BranchProbability.
    440   return getEdgeProbability(Src, Dst) > BranchProbability(4, 5);
    441 }
    442 
    443 BasicBlock *BranchProbabilityInfo::getHotSucc(BasicBlock *BB) const {
    444   uint32_t Sum = 0;
    445   uint32_t MaxWeight = 0;
    446   BasicBlock *MaxSucc = 0;
    447 
    448   for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
    449     BasicBlock *Succ = *I;
    450     uint32_t Weight = getEdgeWeight(BB, Succ);
    451     uint32_t PrevSum = Sum;
    452 
    453     Sum += Weight;
    454     assert(Sum > PrevSum); (void) PrevSum;
    455 
    456     if (Weight > MaxWeight) {
    457       MaxWeight = Weight;
    458       MaxSucc = Succ;
    459     }
    460   }
    461 
    462   // Hot probability is at least 4/5 = 80%
    463   if (BranchProbability(MaxWeight, Sum) > BranchProbability(4, 5))
    464     return MaxSucc;
    465 
    466   return 0;
    467 }
    468 
    469 // Return edge's weight. If can't find it, return DEFAULT_WEIGHT value.
    470 uint32_t BranchProbabilityInfo::
    471 getEdgeWeight(const BasicBlock *Src, const BasicBlock *Dst) const {
    472   Edge E(Src, Dst);
    473   DenseMap<Edge, uint32_t>::const_iterator I = Weights.find(E);
    474 
    475   if (I != Weights.end())
    476     return I->second;
    477 
    478   return DEFAULT_WEIGHT;
    479 }
    480 
    481 void BranchProbabilityInfo::
    482 setEdgeWeight(const BasicBlock *Src, const BasicBlock *Dst, uint32_t Weight) {
    483   Weights[std::make_pair(Src, Dst)] = Weight;
    484   DEBUG(dbgs() << "set edge " << Src->getName() << " -> "
    485                << Dst->getName() << " weight to " << Weight
    486                << (isEdgeHot(Src, Dst) ? " [is HOT now]\n" : "\n"));
    487 }
    488 
    489 
    490 BranchProbability BranchProbabilityInfo::
    491 getEdgeProbability(const BasicBlock *Src, const BasicBlock *Dst) const {
    492 
    493   uint32_t N = getEdgeWeight(Src, Dst);
    494   uint32_t D = getSumForBlock(Src);
    495 
    496   return BranchProbability(N, D);
    497 }
    498 
    499 raw_ostream &
    500 BranchProbabilityInfo::printEdgeProbability(raw_ostream &OS,
    501                                             const BasicBlock *Src,
    502                                             const BasicBlock *Dst) const {
    503 
    504   const BranchProbability Prob = getEdgeProbability(Src, Dst);
    505   OS << "edge " << Src->getName() << " -> " << Dst->getName()
    506      << " probability is " << Prob
    507      << (isEdgeHot(Src, Dst) ? " [HOT edge]\n" : "\n");
    508 
    509   return OS;
    510 }
    511