lib/Analysis/BranchProbabilityInfo.cpp

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