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