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/Instructions.h"
     15 #include "llvm/Analysis/BranchProbabilityInfo.h"
     16 #include "llvm/Analysis/LoopInfo.h"
     17 #include "llvm/Support/Debug.h"
     18 
     19 using namespace llvm;
     20 
     21 INITIALIZE_PASS_BEGIN(BranchProbabilityInfo, "branch-prob",
     22                       "Branch Probability Analysis", false, true)
     23 INITIALIZE_PASS_DEPENDENCY(LoopInfo)
     24 INITIALIZE_PASS_END(BranchProbabilityInfo, "branch-prob",
     25                     "Branch Probability Analysis", false, true)
     26 
     27 char BranchProbabilityInfo::ID = 0;
     28 
     29 namespace {
     30 // Please note that BranchProbabilityAnalysis is not a FunctionPass.
     31 // It is created by BranchProbabilityInfo (which is a FunctionPass), which
     32 // provides a clear interface. Thanks to that, all heuristics and other
     33 // private methods are hidden in the .cpp file.
     34 class BranchProbabilityAnalysis {
     35 
     36   typedef std::pair<BasicBlock *, BasicBlock *> Edge;
     37 
     38   DenseMap<Edge, uint32_t> *Weights;
     39 
     40   BranchProbabilityInfo *BP;
     41 
     42   LoopInfo *LI;
     43 
     44 
     45   // Weights are for internal use only. They are used by heuristics to help to
     46   // estimate edges' probability. Example:
     47   //
     48   // Using "Loop Branch Heuristics" we predict weights of edges for the
     49   // block BB2.
     50   //         ...
     51   //          |
     52   //          V
     53   //         BB1<-+
     54   //          |   |
     55   //          |   | (Weight = 128)
     56   //          V   |
     57   //         BB2--+
     58   //          |
     59   //          | (Weight = 4)
     60   //          V
     61   //         BB3
     62   //
     63   // Probability of the edge BB2->BB1 = 128 / (128 + 4) = 0.9696..
     64   // Probability of the edge BB2->BB3 = 4 / (128 + 4) = 0.0303..
     65 
     66   static const uint32_t LBH_TAKEN_WEIGHT = 128;
     67   static const uint32_t LBH_NONTAKEN_WEIGHT = 4;
     68 
     69   // Standard weight value. Used when none of the heuristics set weight for
     70   // the edge.
     71   static const uint32_t NORMAL_WEIGHT = 16;
     72 
     73   // Minimum weight of an edge. Please note, that weight is NEVER 0.
     74   static const uint32_t MIN_WEIGHT = 1;
     75 
     76   // Return TRUE if BB leads directly to a Return Instruction.
     77   static bool isReturningBlock(BasicBlock *BB) {
     78     SmallPtrSet<BasicBlock *, 8> Visited;
     79 
     80     while (true) {
     81       TerminatorInst *TI = BB->getTerminator();
     82       if (isa<ReturnInst>(TI))
     83         return true;
     84 
     85       if (TI->getNumSuccessors() > 1)
     86         break;
     87 
     88       // It is unreachable block which we can consider as a return instruction.
     89       if (TI->getNumSuccessors() == 0)
     90         return true;
     91 
     92       Visited.insert(BB);
     93       BB = TI->getSuccessor(0);
     94 
     95       // Stop if cycle is detected.
     96       if (Visited.count(BB))
     97         return false;
     98     }
     99 
    100     return false;
    101   }
    102 
    103   // Multiply Edge Weight by two.
    104   void incEdgeWeight(BasicBlock *Src, BasicBlock *Dst) {
    105     uint32_t Weight = BP->getEdgeWeight(Src, Dst);
    106     uint32_t MaxWeight = getMaxWeightFor(Src);
    107 
    108     if (Weight * 2 > MaxWeight)
    109       BP->setEdgeWeight(Src, Dst, MaxWeight);
    110     else
    111       BP->setEdgeWeight(Src, Dst, Weight * 2);
    112   }
    113 
    114   // Divide Edge Weight by two.
    115   void decEdgeWeight(BasicBlock *Src, BasicBlock *Dst) {
    116     uint32_t Weight = BP->getEdgeWeight(Src, Dst);
    117 
    118     assert(Weight > 0);
    119     if (Weight / 2 < MIN_WEIGHT)
    120       BP->setEdgeWeight(Src, Dst, MIN_WEIGHT);
    121     else
    122       BP->setEdgeWeight(Src, Dst, Weight / 2);
    123   }
    124 
    125 
    126   uint32_t getMaxWeightFor(BasicBlock *BB) const {
    127     return UINT32_MAX / BB->getTerminator()->getNumSuccessors();
    128   }
    129 
    130 public:
    131   BranchProbabilityAnalysis(DenseMap<Edge, uint32_t> *W,
    132                             BranchProbabilityInfo *BP, LoopInfo *LI)
    133     : Weights(W), BP(BP), LI(LI) {
    134   }
    135 
    136   // Return Heuristics
    137   void calcReturnHeuristics(BasicBlock *BB);
    138 
    139   // Pointer Heuristics
    140   void calcPointerHeuristics(BasicBlock *BB);
    141 
    142   // Loop Branch Heuristics
    143   void calcLoopBranchHeuristics(BasicBlock *BB);
    144 
    145   bool runOnFunction(Function &F);
    146 };
    147 } // end anonymous namespace
    148 
    149 // Calculate Edge Weights using "Return Heuristics". Predict a successor which
    150 // leads directly to Return Instruction will not be taken.
    151 void BranchProbabilityAnalysis::calcReturnHeuristics(BasicBlock *BB){
    152   if (BB->getTerminator()->getNumSuccessors() == 1)
    153     return;
    154 
    155   for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
    156     BasicBlock *Succ = *I;
    157     if (isReturningBlock(Succ)) {
    158       decEdgeWeight(BB, Succ);
    159     }
    160   }
    161 }
    162 
    163 // Calculate Edge Weights using "Pointer Heuristics". Predict a comparsion
    164 // between two pointer or pointer and NULL will fail.
    165 void BranchProbabilityAnalysis::calcPointerHeuristics(BasicBlock *BB) {
    166   BranchInst * BI = dyn_cast<BranchInst>(BB->getTerminator());
    167   if (!BI || !BI->isConditional())
    168     return;
    169 
    170   Value *Cond = BI->getCondition();
    171   ICmpInst *CI = dyn_cast<ICmpInst>(Cond);
    172   if (!CI || !CI->isEquality())
    173     return;
    174 
    175   Value *LHS = CI->getOperand(0);
    176 
    177   if (!LHS->getType()->isPointerTy())
    178     return;
    179 
    180   assert(CI->getOperand(1)->getType()->isPointerTy());
    181 
    182   BasicBlock *Taken = BI->getSuccessor(0);
    183   BasicBlock *NonTaken = BI->getSuccessor(1);
    184 
    185   // p != 0   ->   isProb = true
    186   // p == 0   ->   isProb = false
    187   // p != q   ->   isProb = true
    188   // p == q   ->   isProb = false;
    189   bool isProb = CI->getPredicate() == ICmpInst::ICMP_NE;
    190   if (!isProb)
    191     std::swap(Taken, NonTaken);
    192 
    193   incEdgeWeight(BB, Taken);
    194   decEdgeWeight(BB, NonTaken);
    195 }
    196 
    197 // Calculate Edge Weights using "Loop Branch Heuristics". Predict backedges
    198 // as taken, exiting edges as not-taken.
    199 void BranchProbabilityAnalysis::calcLoopBranchHeuristics(BasicBlock *BB) {
    200   uint32_t numSuccs = BB->getTerminator()->getNumSuccessors();
    201 
    202   Loop *L = LI->getLoopFor(BB);
    203   if (!L)
    204     return;
    205 
    206   SmallVector<BasicBlock *, 8> BackEdges;
    207   SmallVector<BasicBlock *, 8> ExitingEdges;
    208 
    209   for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
    210     BasicBlock *Succ = *I;
    211     Loop *SuccL = LI->getLoopFor(Succ);
    212     if (SuccL != L)
    213       ExitingEdges.push_back(Succ);
    214     else if (Succ == L->getHeader())
    215       BackEdges.push_back(Succ);
    216   }
    217 
    218   if (uint32_t numBackEdges = BackEdges.size()) {
    219     uint32_t backWeight = LBH_TAKEN_WEIGHT / numBackEdges;
    220     if (backWeight < NORMAL_WEIGHT)
    221       backWeight = NORMAL_WEIGHT;
    222 
    223     for (SmallVector<BasicBlock *, 8>::iterator EI = BackEdges.begin(),
    224          EE = BackEdges.end(); EI != EE; ++EI) {
    225       BasicBlock *Back = *EI;
    226       BP->setEdgeWeight(BB, Back, backWeight);
    227     }
    228   }
    229 
    230   uint32_t numExitingEdges = ExitingEdges.size();
    231   if (uint32_t numNonExitingEdges = numSuccs - numExitingEdges) {
    232     uint32_t exitWeight = LBH_NONTAKEN_WEIGHT / numNonExitingEdges;
    233     if (exitWeight < MIN_WEIGHT)
    234       exitWeight = MIN_WEIGHT;
    235 
    236     for (SmallVector<BasicBlock *, 8>::iterator EI = ExitingEdges.begin(),
    237          EE = ExitingEdges.end(); EI != EE; ++EI) {
    238       BasicBlock *Exiting = *EI;
    239       BP->setEdgeWeight(BB, Exiting, exitWeight);
    240     }
    241   }
    242 }
    243 
    244 bool BranchProbabilityAnalysis::runOnFunction(Function &F) {
    245 
    246   for (Function::iterator I = F.begin(), E = F.end(); I != E; ) {
    247     BasicBlock *BB = I++;
    248 
    249     // Only LBH uses setEdgeWeight method.
    250     calcLoopBranchHeuristics(BB);
    251 
    252     // PH and RH use only incEdgeWeight and decEwdgeWeight methods to
    253     // not efface LBH results.
    254     calcPointerHeuristics(BB);
    255     calcReturnHeuristics(BB);
    256   }
    257 
    258   return false;
    259 }
    260 
    261 void BranchProbabilityInfo::getAnalysisUsage(AnalysisUsage &AU) const {
    262     AU.addRequired<LoopInfo>();
    263     AU.setPreservesAll();
    264 }
    265 
    266 bool BranchProbabilityInfo::runOnFunction(Function &F) {
    267   LoopInfo &LI = getAnalysis<LoopInfo>();
    268   BranchProbabilityAnalysis BPA(&Weights, this, &LI);
    269   return BPA.runOnFunction(F);
    270 }
    271 
    272 uint32_t BranchProbabilityInfo::getSumForBlock(BasicBlock *BB) const {
    273   uint32_t Sum = 0;
    274 
    275   for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
    276     BasicBlock *Succ = *I;
    277     uint32_t Weight = getEdgeWeight(BB, Succ);
    278     uint32_t PrevSum = Sum;
    279 
    280     Sum += Weight;
    281     assert(Sum > PrevSum); (void) PrevSum;
    282   }
    283 
    284   return Sum;
    285 }
    286 
    287 bool BranchProbabilityInfo::isEdgeHot(BasicBlock *Src, BasicBlock *Dst) const {
    288   // Hot probability is at least 4/5 = 80%
    289   uint32_t Weight = getEdgeWeight(Src, Dst);
    290   uint32_t Sum = getSumForBlock(Src);
    291 
    292   // FIXME: Implement BranchProbability::compare then change this code to
    293   // compare this BranchProbability against a static "hot" BranchProbability.
    294   return (uint64_t)Weight * 5 > (uint64_t)Sum * 4;
    295 }
    296 
    297 BasicBlock *BranchProbabilityInfo::getHotSucc(BasicBlock *BB) const {
    298   uint32_t Sum = 0;
    299   uint32_t MaxWeight = 0;
    300   BasicBlock *MaxSucc = 0;
    301 
    302   for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
    303     BasicBlock *Succ = *I;
    304     uint32_t Weight = getEdgeWeight(BB, Succ);
    305     uint32_t PrevSum = Sum;
    306 
    307     Sum += Weight;
    308     assert(Sum > PrevSum); (void) PrevSum;
    309 
    310     if (Weight > MaxWeight) {
    311       MaxWeight = Weight;
    312       MaxSucc = Succ;
    313     }
    314   }
    315 
    316   // FIXME: Use BranchProbability::compare.
    317   if ((uint64_t)MaxWeight * 5 > (uint64_t)Sum * 4)
    318     return MaxSucc;
    319 
    320   return 0;
    321 }
    322 
    323 // Return edge's weight. If can't find it, return DEFAULT_WEIGHT value.
    324 uint32_t
    325 BranchProbabilityInfo::getEdgeWeight(BasicBlock *Src, BasicBlock *Dst) const {
    326   Edge E(Src, Dst);
    327   DenseMap<Edge, uint32_t>::const_iterator I = Weights.find(E);
    328 
    329   if (I != Weights.end())
    330     return I->second;
    331 
    332   return DEFAULT_WEIGHT;
    333 }
    334 
    335 void BranchProbabilityInfo::setEdgeWeight(BasicBlock *Src, BasicBlock *Dst,
    336                                      uint32_t Weight) {
    337   Weights[std::make_pair(Src, Dst)] = Weight;
    338   DEBUG(dbgs() << "set edge " << Src->getNameStr() << " -> "
    339                << Dst->getNameStr() << " weight to " << Weight
    340                << (isEdgeHot(Src, Dst) ? " [is HOT now]\n" : "\n"));
    341 }
    342 
    343 
    344 BranchProbability BranchProbabilityInfo::
    345 getEdgeProbability(BasicBlock *Src, BasicBlock *Dst) const {
    346 
    347   uint32_t N = getEdgeWeight(Src, Dst);
    348   uint32_t D = getSumForBlock(Src);
    349 
    350   return BranchProbability(N, D);
    351 }
    352 
    353 raw_ostream &
    354 BranchProbabilityInfo::printEdgeProbability(raw_ostream &OS, BasicBlock *Src,
    355                                             BasicBlock *Dst) const {
    356 
    357   const BranchProbability Prob = getEdgeProbability(Src, Dst);
    358   OS << "edge " << Src->getNameStr() << " -> " << Dst->getNameStr()
    359      << " probability is " << Prob
    360      << (isEdgeHot(Src, Dst) ? " [HOT edge]\n" : "\n");
    361 
    362   return OS;
    363 }
    364