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   SmallVector<BasicBlock *, 4> ReturningEdges;
 146   SmallVector<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.push_back(Succ);
 152     else
 153       StayEdges.push_back(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 (SmallVector<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 (SmallVector<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   SmallVector<BasicBlock *, 8> BackEdges;
 224   SmallVector<BasicBlock *, 8> ExitingEdges;
 225   SmallVector<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.push_back(Succ);
 234     else if (Succ == L->getHeader())
 235       BackEdges.push_back(Succ);
 236     else if (isHeader)
 237       InEdges.push_back(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 (SmallVector<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 (SmallVector<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 (SmallVector<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 *LHS = CI->getOperand(0);
 291   Value *RHS = CI->getOperand(1);
 292
 293   bool hasZero = false;
 294   bool lhsZero = false;
 295   if (ConstantInt *CI = dyn_cast<ConstantInt>(LHS)) {
 296     hasZero = CI->isZero();
 297     lhsZero = true;
 298   }
 299
 300   if (!hasZero)
 301     if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS))
 302       hasZero = CI->isZero();
 303
 304   if (!hasZero)
 305     return false;
 306
 307   bool isProb;
 308   switch (CI->getPredicate()) {
 309   case CmpInst::ICMP_EQ:
 310     // Equal to zero is not expected to be taken.
 311     isProb = false;
 312     break;
 313
 314   case CmpInst::ICMP_NE:
 315     // Not equal to zero is expected.
 316     isProb = true;
 317     break;
 318
 319   case CmpInst::ICMP_ULT:
 320   case CmpInst::ICMP_ULE:
 321   case CmpInst::ICMP_SLT:
 322   case CmpInst::ICMP_SLE:
 323     // Less or equal to zero is not expected.
 324     // 0 < X   ->   isProb = true
 325     // 0 <= X  ->   isProb = true
 326     // X < 0   ->   isProb = false
 327     // X <= 0  ->   isProb = false
 328     isProb = lhsZero;
 329     break;
 330
 331   case CmpInst::ICMP_UGT:
 332   case CmpInst::ICMP_UGE:
 333   case CmpInst::ICMP_SGT:
 334   case CmpInst::ICMP_SGE:
 335     // Greater or equal to zero is expected.
 336     // 0 > X   ->   isProb = false
 337     // 0 >= X  ->   isProb = false
 338     // X > 0   ->   isProb = true
 339     // X >= 0  ->   isProb = true
 340     isProb = !lhsZero;
 341     break;
 342
 343   default:
 344     return false;
 345   };
 346
 347   BasicBlock *Taken = BI->getSuccessor(0);
 348   BasicBlock *NonTaken = BI->getSuccessor(1);
 349
 350   if (!isProb)
 351     std::swap(Taken, NonTaken);
 352
 353   BP->setEdgeWeight(BB, Taken, ZH_TAKEN_WEIGHT);
 354   BP->setEdgeWeight(BB, NonTaken, ZH_NONTAKEN_WEIGHT);
 355
 356   return true;
 357 }
 358
 359
 360 bool BranchProbabilityAnalysis::runOnFunction(Function &F) {
 361
 362   for (Function::iterator I = F.begin(), E = F.end(); I != E; ) {
 363     BasicBlock *BB = I++;
 364
 365     // Only LBH uses setEdgeWeight method.
 366     if (calcLoopBranchHeuristics(BB))
 367       continue;
 368
 369     // PH and RH use only incEdgeWeight and decEwdgeWeight methods to
 370     // not efface LBH results.
 371     if (calcReturnHeuristics(BB))
 372       continue;
 373
 374     if (calcPointerHeuristics(BB))
 375       continue;
 376
 377     calcZeroHeuristics(BB);
 378   }
 379
 380   return false;
 381 }
 382
 383 void BranchProbabilityInfo::getAnalysisUsage(AnalysisUsage &AU) const {
 384     AU.addRequired<LoopInfo>();
 385     AU.setPreservesAll();
 386 }
 387
 388 bool BranchProbabilityInfo::runOnFunction(Function &F) {
 389   LoopInfo &LI = getAnalysis<LoopInfo>();
 390   BranchProbabilityAnalysis BPA(&Weights, this, &LI);
 391   return BPA.runOnFunction(F);
 392 }
 393
 394 uint32_t BranchProbabilityInfo::getSumForBlock(const BasicBlock *BB) const {
 395   uint32_t Sum = 0;
 396
 397   for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
 398     const BasicBlock *Succ = *I;
 399     uint32_t Weight = getEdgeWeight(BB, Succ);
 400     uint32_t PrevSum = Sum;
 401
 402     Sum += Weight;
 403     assert(Sum > PrevSum); (void) PrevSum;
 404   }
 405
 406   return Sum;
 407 }
 408
 409 bool BranchProbabilityInfo::
 410 isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const {
 411   // Hot probability is at least 4/5 = 80%
 412   uint32_t Weight = getEdgeWeight(Src, Dst);
 413   uint32_t Sum = getSumForBlock(Src);
 414
 415   // FIXME: Implement BranchProbability::compare then change this code to
 416   // compare this BranchProbability against a static "hot" BranchProbability.
 417   return (uint64_t)Weight * 5 > (uint64_t)Sum * 4;
 418 }
 419
 420 BasicBlock *BranchProbabilityInfo::getHotSucc(BasicBlock *BB) const {
 421   uint32_t Sum = 0;
 422   uint32_t MaxWeight = 0;
 423   BasicBlock *MaxSucc = 0;
 424
 425   for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
 426     BasicBlock *Succ = *I;
 427     uint32_t Weight = getEdgeWeight(BB, Succ);
 428     uint32_t PrevSum = Sum;
 429
 430     Sum += Weight;
 431     assert(Sum > PrevSum); (void) PrevSum;
 432
 433     if (Weight > MaxWeight) {
 434       MaxWeight = Weight;
 435       MaxSucc = Succ;
 436     }
 437   }
 438
 439   // FIXME: Use BranchProbability::compare.
 440   if ((uint64_t)MaxWeight * 5 > (uint64_t)Sum * 4)
 441     return MaxSucc;
 442
 443   return 0;
 444 }
 445
 446 // Return edge's weight. If can't find it, return DEFAULT_WEIGHT value.
 447 uint32_t BranchProbabilityInfo::
 448 getEdgeWeight(const BasicBlock *Src, const BasicBlock *Dst) const {
 449   Edge E(Src, Dst);
 450   DenseMap<Edge, uint32_t>::const_iterator I = Weights.find(E);
 451
 452   if (I != Weights.end())
 453     return I->second;
 454
 455   return DEFAULT_WEIGHT;
 456 }
 457
 458 void BranchProbabilityInfo::
 459 setEdgeWeight(const BasicBlock *Src, const BasicBlock *Dst, uint32_t Weight) {
 460   Weights[std::make_pair(Src, Dst)] = Weight;
 461   DEBUG(dbgs() << "set edge " << Src->getNameStr() << " -> "
 462                << Dst->getNameStr() << " weight to " << Weight
 463                << (isEdgeHot(Src, Dst) ? " [is HOT now]\n" : "\n"));
 464 }
 465
 466
 467 BranchProbability BranchProbabilityInfo::
 468 getEdgeProbability(const BasicBlock *Src, const BasicBlock *Dst) const {
 469
 470   uint32_t N = getEdgeWeight(Src, Dst);
 471   uint32_t D = getSumForBlock(Src);
 472
 473   return BranchProbability(N, D);
 474 }
 475
 476 raw_ostream &
 477 BranchProbabilityInfo::printEdgeProbability(raw_ostream &OS, BasicBlock *Src,
 478                                             BasicBlock *Dst) const {
 479
 480   const BranchProbability Prob = getEdgeProbability(Src, Dst);
 481   OS << "edge " << Src->getNameStr() << " -> " << Dst->getNameStr()
 482      << " probability is " << Prob
 483      << (isEdgeHot(Src, Dst) ? " [HOT edge]\n" : "\n");
 484
 485   return OS;
 486 }