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/Constants.h"
  15 #include "llvm/Instructions.h"
  16 #include "llvm/Analysis/BranchProbabilityInfo.h"
  17 #include "llvm/Analysis/LoopInfo.h"
  18 #include "llvm/Support/Debug.h"
  19
  20 using namespace llvm;
  21
  22 INITIALIZE_PASS_BEGIN(BranchProbabilityInfo, "branch-prob",
  23                       "Branch Probability Analysis", false, true)
  24 INITIALIZE_PASS_DEPENDENCY(LoopInfo)
  25 INITIALIZE_PASS_END(BranchProbabilityInfo, "branch-prob",
  26                     "Branch Probability Analysis", false, true)
  27
  28 char BranchProbabilityInfo::ID = 0;
  29
  30 namespace {
  31 // Please note that BranchProbabilityAnalysis is not a FunctionPass.
  32 // It is created by BranchProbabilityInfo (which is a FunctionPass), which
  33 // provides a clear interface. Thanks to that, all heuristics and other
  34 // private methods are hidden in the .cpp file.
  35 class BranchProbabilityAnalysis {
  36
  37   typedef std::pair<const BasicBlock *, const BasicBlock *> Edge;
  38
  39   DenseMap<Edge, uint32_t> *Weights;
  40
  41   BranchProbabilityInfo *BP;
  42
  43   LoopInfo *LI;
  44
  45
  46   // Weights are for internal use only. They are used by heuristics to help to
  47   // estimate edges' probability. Example:
  48   //
  49   // Using "Loop Branch Heuristics" we predict weights of edges for the
  50   // block BB2.
  51   //         ...
  52   //          |
  53   //          V
  54   //         BB1<-+
  55   //          |   |
  56   //          |   | (Weight = 124)
  57   //          V   |
  58   //         BB2--+
  59   //          |
  60   //          | (Weight = 4)
  61   //          V
  62   //         BB3
  63   //
  64   // Probability of the edge BB2->BB1 = 124 / (124 + 4) = 0.96875
  65   // Probability of the edge BB2->BB3 = 4 / (124 + 4) = 0.03125
  66
  67   static const uint32_t LBH_TAKEN_WEIGHT = 124;
  68   static const uint32_t LBH_NONTAKEN_WEIGHT = 4;
  69
  70   static const uint32_t RH_TAKEN_WEIGHT = 24;
  71   static const uint32_t RH_NONTAKEN_WEIGHT = 8;
  72
  73   static const uint32_t PH_TAKEN_WEIGHT = 20;
  74   static const uint32_t PH_NONTAKEN_WEIGHT = 12;
  75
  76   static const uint32_t ZH_TAKEN_WEIGHT = 20;
  77   static const uint32_t ZH_NONTAKEN_WEIGHT = 12;
  78
  79   // Standard weight value. Used when none of the heuristics set weight for
  80   // the edge.
  81   static const uint32_t NORMAL_WEIGHT = 16;
  82
  83   // Minimum weight of an edge. Please note, that weight is NEVER 0.
  84   static const uint32_t MIN_WEIGHT = 1;
  85
  86   // Return TRUE if BB leads directly to a Return Instruction.
  87   static bool isReturningBlock(BasicBlock *BB) {
  88     SmallPtrSet<BasicBlock *, 8> Visited;
  89
  90     while (true) {
  91       TerminatorInst *TI = BB->getTerminator();
  92       if (isa<ReturnInst>(TI))
  93         return true;
  94
  95       if (TI->getNumSuccessors() > 1)
  96         break;
  97
  98       // It is unreachable block which we can consider as a return instruction.
  99       if (TI->getNumSuccessors() == 0)
 100         return true;
 101
 102       Visited.insert(BB);
 103       BB = TI->getSuccessor(0);
 104
 105       // Stop if cycle is detected.
 106       if (Visited.count(BB))
 107         return false;
 108     }
 109
 110     return false;
 111   }
 112
 113   uint32_t getMaxWeightFor(BasicBlock *BB) const {
 114     return UINT32_MAX / BB->getTerminator()->getNumSuccessors();
 115   }
 116
 117 public:
 118   BranchProbabilityAnalysis(DenseMap<Edge, uint32_t> *W,
 119                             BranchProbabilityInfo *BP, LoopInfo *LI)
 120     : Weights(W), BP(BP), LI(LI) {
 121   }
 122
 123   // Return Heuristics
 124   bool calcReturnHeuristics(BasicBlock *BB);
 125
 126   // Pointer Heuristics
 127   bool calcPointerHeuristics(BasicBlock *BB);
 128
 129   // Loop Branch Heuristics
 130   bool calcLoopBranchHeuristics(BasicBlock *BB);
 131
 132   // Zero Heurestics
 133   bool calcZeroHeuristics(BasicBlock *BB);
 134
 135   bool runOnFunction(Function &F);
 136 };
 137 } // end anonymous namespace
 138
 139 // Calculate Edge Weights using "Return Heuristics". Predict a successor which
 140 // leads directly to Return Instruction will not be taken.
 141 bool BranchProbabilityAnalysis::calcReturnHeuristics(BasicBlock *BB){
 142   if (BB->getTerminator()->getNumSuccessors() == 1)
 143     return false;
 144
 145   SmallPtrSet<BasicBlock *, 4> ReturningEdges;
 146   SmallPtrSet<BasicBlock *, 4> StayEdges;
 147
 148   for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
 149     BasicBlock *Succ = *I;
 150     if (isReturningBlock(Succ))
 151       ReturningEdges.insert(Succ);
 152     else
 153       StayEdges.insert(Succ);
 154   }
 155
 156   if (uint32_t numStayEdges = StayEdges.size()) {
 157     uint32_t stayWeight = RH_TAKEN_WEIGHT / numStayEdges;
 158     if (stayWeight < NORMAL_WEIGHT)
 159       stayWeight = NORMAL_WEIGHT;
 160
 161     for (SmallPtrSet<BasicBlock *, 4>::iterator I = StayEdges.begin(),
 162          E = StayEdges.end(); I != E; ++I)
 163       BP->setEdgeWeight(BB, *I, stayWeight);
 164   }
 165
 166   if (uint32_t numRetEdges = ReturningEdges.size()) {
 167     uint32_t retWeight = RH_NONTAKEN_WEIGHT / numRetEdges;
 168     if (retWeight < MIN_WEIGHT)
 169       retWeight = MIN_WEIGHT;
 170     for (SmallPtrSet<BasicBlock *, 4>::iterator I = ReturningEdges.begin(),
 171          E = ReturningEdges.end(); I != E; ++I) {
 172       BP->setEdgeWeight(BB, *I, retWeight);
 173     }
 174   }
 175
 176   return ReturningEdges.size() > 0;
 177 }
 178
 179 // Calculate Edge Weights using "Pointer Heuristics". Predict a comparsion
 180 // between two pointer or pointer and NULL will fail.
 181 bool BranchProbabilityAnalysis::calcPointerHeuristics(BasicBlock *BB) {
 182   BranchInst * BI = dyn_cast<BranchInst>(BB->getTerminator());
 183   if (!BI || !BI->isConditional())
 184     return false;
 185
 186   Value *Cond = BI->getCondition();
 187   ICmpInst *CI = dyn_cast<ICmpInst>(Cond);
 188   if (!CI || !CI->isEquality())
 189     return false;
 190
 191   Value *LHS = CI->getOperand(0);
 192
 193   if (!LHS->getType()->isPointerTy())
 194     return false;
 195
 196   assert(CI->getOperand(1)->getType()->isPointerTy());
 197
 198   BasicBlock *Taken = BI->getSuccessor(0);
 199   BasicBlock *NonTaken = BI->getSuccessor(1);
 200
 201   // p != 0   ->   isProb = true
 202   // p == 0   ->   isProb = false
 203   // p != q   ->   isProb = true
 204   // p == q   ->   isProb = false;
 205   bool isProb = CI->getPredicate() == ICmpInst::ICMP_NE;
 206   if (!isProb)
 207     std::swap(Taken, NonTaken);
 208
 209   BP->setEdgeWeight(BB, Taken, PH_TAKEN_WEIGHT);
 210   BP->setEdgeWeight(BB, NonTaken, PH_NONTAKEN_WEIGHT);
 211   return true;
 212 }
 213
 214 // Calculate Edge Weights using "Loop Branch Heuristics". Predict backedges
 215 // as taken, exiting edges as not-taken.
 216 bool BranchProbabilityAnalysis::calcLoopBranchHeuristics(BasicBlock *BB) {
 217   uint32_t numSuccs = BB->getTerminator()->getNumSuccessors();
 218
 219   Loop *L = LI->getLoopFor(BB);
 220   if (!L)
 221     return false;
 222
 223   SmallPtrSet<BasicBlock *, 8> BackEdges;
 224   SmallPtrSet<BasicBlock *, 8> ExitingEdges;
 225   SmallPtrSet<BasicBlock *, 8> InEdges; // Edges from header to the loop.
 226
 227   bool isHeader = BB == L->getHeader();
 228
 229   for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
 230     BasicBlock *Succ = *I;
 231     Loop *SuccL = LI->getLoopFor(Succ);
 232     if (SuccL != L)
 233       ExitingEdges.insert(Succ);
 234     else if (Succ == L->getHeader())
 235       BackEdges.insert(Succ);
 236     else if (isHeader)
 237       InEdges.insert(Succ);
 238   }
 239
 240   if (uint32_t numBackEdges = BackEdges.size()) {
 241     uint32_t backWeight = LBH_TAKEN_WEIGHT / numBackEdges;
 242     if (backWeight < NORMAL_WEIGHT)
 243       backWeight = NORMAL_WEIGHT;
 244
 245     for (SmallPtrSet<BasicBlock *, 8>::iterator EI = BackEdges.begin(),
 246          EE = BackEdges.end(); EI != EE; ++EI) {
 247       BasicBlock *Back = *EI;
 248       BP->setEdgeWeight(BB, Back, backWeight);
 249     }
 250   }
 251
 252   if (uint32_t numInEdges = InEdges.size()) {
 253     uint32_t inWeight = LBH_TAKEN_WEIGHT / numInEdges;
 254     if (inWeight < NORMAL_WEIGHT)
 255       inWeight = NORMAL_WEIGHT;
 256
 257     for (SmallPtrSet<BasicBlock *, 8>::iterator EI = InEdges.begin(),
 258          EE = InEdges.end(); EI != EE; ++EI) {
 259       BasicBlock *Back = *EI;
 260       BP->setEdgeWeight(BB, Back, inWeight);
 261     }
 262   }
 263
 264   uint32_t numExitingEdges = ExitingEdges.size();
 265   if (uint32_t numNonExitingEdges = numSuccs - numExitingEdges) {
 266     uint32_t exitWeight = LBH_NONTAKEN_WEIGHT / numNonExitingEdges;
 267     if (exitWeight < MIN_WEIGHT)
 268       exitWeight = MIN_WEIGHT;
 269
 270     for (SmallPtrSet<BasicBlock *, 8>::iterator EI = ExitingEdges.begin(),
 271          EE = ExitingEdges.end(); EI != EE; ++EI) {
 272       BasicBlock *Exiting = *EI;
 273       BP->setEdgeWeight(BB, Exiting, exitWeight);
 274     }
 275   }
 276
 277   return true;
 278 }
 279
 280 bool BranchProbabilityAnalysis::calcZeroHeuristics(BasicBlock *BB) {
 281   BranchInst * BI = dyn_cast<BranchInst>(BB->getTerminator());
 282   if (!BI || !BI->isConditional())
 283     return false;
 284
 285   Value *Cond = BI->getCondition();
 286   ICmpInst *CI = dyn_cast<ICmpInst>(Cond);
 287   if (!CI)
 288     return false;
 289
 290   Value *RHS = CI->getOperand(1);
 291   ConstantInt *CV = dyn_cast<ConstantInt>(RHS);
 292   if (!CV || !CV->isZero())
 293     return false;
 294
 295   bool isProb;
 296   switch (CI->getPredicate()) {
 297   case CmpInst::ICMP_EQ:
 298     // Equal to zero is not expected to be taken.
 299     isProb = false;
 300     break;
 301
 302   case CmpInst::ICMP_NE:
 303     // Not equal to zero is expected.
 304     isProb = true;
 305     break;
 306
 307   case CmpInst::ICMP_SLT:
 308     // Less or equal to zero is not expected.
 309     // X < 0   ->  Unlikely
 310     isProb = false;
 311     break;
 312
 313   case CmpInst::ICMP_UGT:
 314   case CmpInst::ICMP_SGT:
 315     // Greater or equal to zero is expected.
 316     // X > 0   ->  Likely
 317     isProb = true;
 318     break;
 319
 320   default:
 321     return false;
 322   };
 323
 324   BasicBlock *Taken = BI->getSuccessor(0);
 325   BasicBlock *NonTaken = BI->getSuccessor(1);
 326
 327   if (!isProb)
 328     std::swap(Taken, NonTaken);
 329
 330   BP->setEdgeWeight(BB, Taken, ZH_TAKEN_WEIGHT);
 331   BP->setEdgeWeight(BB, NonTaken, ZH_NONTAKEN_WEIGHT);
 332
 333   return true;
 334 }
 335
 336
 337 bool BranchProbabilityAnalysis::runOnFunction(Function &F) {
 338
 339   for (Function::iterator I = F.begin(), E = F.end(); I != E; ) {
 340     BasicBlock *BB = I++;
 341
 342     if (calcLoopBranchHeuristics(BB))
 343       continue;
 344
 345     if (calcReturnHeuristics(BB))
 346       continue;
 347
 348     if (calcPointerHeuristics(BB))
 349       continue;
 350
 351     calcZeroHeuristics(BB);
 352   }
 353
 354   return false;
 355 }
 356
 357 void BranchProbabilityInfo::getAnalysisUsage(AnalysisUsage &AU) const {
 358     AU.addRequired<LoopInfo>();
 359     AU.setPreservesAll();
 360 }
 361
 362 bool BranchProbabilityInfo::runOnFunction(Function &F) {
 363   LoopInfo &LI = getAnalysis<LoopInfo>();
 364   BranchProbabilityAnalysis BPA(&Weights, this, &LI);
 365   return BPA.runOnFunction(F);
 366 }
 367
 368 uint32_t BranchProbabilityInfo::getSumForBlock(const BasicBlock *BB) const {
 369   uint32_t Sum = 0;
 370
 371   for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
 372     const BasicBlock *Succ = *I;
 373     uint32_t Weight = getEdgeWeight(BB, Succ);
 374     uint32_t PrevSum = Sum;
 375
 376     Sum += Weight;
 377     assert(Sum > PrevSum); (void) PrevSum;
 378   }
 379
 380   return Sum;
 381 }
 382
 383 bool BranchProbabilityInfo::
 384 isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const {
 385   // Hot probability is at least 4/5 = 80%
 386   uint32_t Weight = getEdgeWeight(Src, Dst);
 387   uint32_t Sum = getSumForBlock(Src);
 388
 389   // FIXME: Implement BranchProbability::compare then change this code to
 390   // compare this BranchProbability against a static "hot" BranchProbability.
 391   return (uint64_t)Weight * 5 > (uint64_t)Sum * 4;
 392 }
 393
 394 BasicBlock *BranchProbabilityInfo::getHotSucc(BasicBlock *BB) const {
 395   uint32_t Sum = 0;
 396   uint32_t MaxWeight = 0;
 397   BasicBlock *MaxSucc = 0;
 398
 399   for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
 400     BasicBlock *Succ = *I;
 401     uint32_t Weight = getEdgeWeight(BB, Succ);
 402     uint32_t PrevSum = Sum;
 403
 404     Sum += Weight;
 405     assert(Sum > PrevSum); (void) PrevSum;
 406
 407     if (Weight > MaxWeight) {
 408       MaxWeight = Weight;
 409       MaxSucc = Succ;
 410     }
 411   }
 412
 413   // FIXME: Use BranchProbability::compare.
 414   if ((uint64_t)MaxWeight * 5 > (uint64_t)Sum * 4)
 415     return MaxSucc;
 416
 417   return 0;
 418 }
 419
 420 // Return edge's weight. If can't find it, return DEFAULT_WEIGHT value.
 421 uint32_t BranchProbabilityInfo::
 422 getEdgeWeight(const BasicBlock *Src, const BasicBlock *Dst) const {
 423   Edge E(Src, Dst);
 424   DenseMap<Edge, uint32_t>::const_iterator I = Weights.find(E);
 425
 426   if (I != Weights.end())
 427     return I->second;
 428
 429   return DEFAULT_WEIGHT;
 430 }
 431
 432 void BranchProbabilityInfo::
 433 setEdgeWeight(const BasicBlock *Src, const BasicBlock *Dst, uint32_t Weight) {
 434   Weights[std::make_pair(Src, Dst)] = Weight;
 435   DEBUG(dbgs() << "set edge " << Src->getNameStr() << " -> "
 436                << Dst->getNameStr() << " weight to " << Weight
 437                << (isEdgeHot(Src, Dst) ? " [is HOT now]\n" : "\n"));
 438 }
 439
 440
 441 BranchProbability BranchProbabilityInfo::
 442 getEdgeProbability(const BasicBlock *Src, const BasicBlock *Dst) const {
 443
 444   uint32_t N = getEdgeWeight(Src, Dst);
 445   uint32_t D = getSumForBlock(Src);
 446
 447   return BranchProbability(N, D);
 448 }
 449
 450 raw_ostream &
 451 BranchProbabilityInfo::printEdgeProbability(raw_ostream &OS, BasicBlock *Src,
 452                                             BasicBlock *Dst) const {
 453
 454   const BranchProbability Prob = getEdgeProbability(Src, Dst);
 455   OS << "edge " << Src->getNameStr() << " -> " << Dst->getNameStr()
 456      << " probability is " << Prob
 457      << (isEdgeHot(Src, Dst) ? " [HOT edge]\n" : "\n");
 458
 459   return OS;
 460 }