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)
 293     return false;
 294
 295   bool isProb;
 296   if (CV->isZero()) {
 297     switch (CI->getPredicate()) {
 298     case CmpInst::ICMP_EQ:
 299       // X == 0   ->  Unlikely
 300       isProb = false;
 301       break;
 302     case CmpInst::ICMP_NE:
 303       // X != 0   ->  Likely
 304       isProb = true;
 305       break;
 306     case CmpInst::ICMP_SLT:
 307       // X < 0   ->  Unlikely
 308       isProb = false;
 309       break;
 310     case CmpInst::ICMP_SGT:
 311       // X > 0   ->  Likely
 312       isProb = true;
 313       break;
 314     default:
 315       return false;
 316     }
 317   } else if (CV->isOne() && CI->getPredicate() == CmpInst::ICMP_SLT) {
 318     // InstCombine canonicalizes X <= 0 into X < 1.
 319     // X <= 0   ->  Unlikely
 320     isProb = false;
 321   } else if (CV->isAllOnesValue() && CI->getPredicate() == CmpInst::ICMP_SGT) {
 322     // InstCombine canonicalizes X >= 0 into X > -1.
 323     // X >= 0   ->  Likely
 324     isProb = true;
 325   } else {
 326     return false;
 327   }
 328
 329   BasicBlock *Taken = BI->getSuccessor(0);
 330   BasicBlock *NonTaken = BI->getSuccessor(1);
 331
 332   if (!isProb)
 333     std::swap(Taken, NonTaken);
 334
 335   BP->setEdgeWeight(BB, Taken, ZH_TAKEN_WEIGHT);
 336   BP->setEdgeWeight(BB, NonTaken, ZH_NONTAKEN_WEIGHT);
 337
 338   return true;
 339 }
 340
 341
 342 bool BranchProbabilityAnalysis::runOnFunction(Function &F) {
 343
 344   for (Function::iterator I = F.begin(), E = F.end(); I != E; ) {
 345     BasicBlock *BB = I++;
 346
 347     if (calcLoopBranchHeuristics(BB))
 348       continue;
 349
 350     if (calcReturnHeuristics(BB))
 351       continue;
 352
 353     if (calcPointerHeuristics(BB))
 354       continue;
 355
 356     calcZeroHeuristics(BB);
 357   }
 358
 359   return false;
 360 }
 361
 362 void BranchProbabilityInfo::getAnalysisUsage(AnalysisUsage &AU) const {
 363     AU.addRequired<LoopInfo>();
 364     AU.setPreservesAll();
 365 }
 366
 367 bool BranchProbabilityInfo::runOnFunction(Function &F) {
 368   LoopInfo &LI = getAnalysis<LoopInfo>();
 369   BranchProbabilityAnalysis BPA(&Weights, this, &LI);
 370   return BPA.runOnFunction(F);
 371 }
 372
 373 uint32_t BranchProbabilityInfo::getSumForBlock(const BasicBlock *BB) const {
 374   uint32_t Sum = 0;
 375
 376   for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
 377     const BasicBlock *Succ = *I;
 378     uint32_t Weight = getEdgeWeight(BB, Succ);
 379     uint32_t PrevSum = Sum;
 380
 381     Sum += Weight;
 382     assert(Sum > PrevSum); (void) PrevSum;
 383   }
 384
 385   return Sum;
 386 }
 387
 388 bool BranchProbabilityInfo::
 389 isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const {
 390   // Hot probability is at least 4/5 = 80%
 391   uint32_t Weight = getEdgeWeight(Src, Dst);
 392   uint32_t Sum = getSumForBlock(Src);
 393
 394   // FIXME: Implement BranchProbability::compare then change this code to
 395   // compare this BranchProbability against a static "hot" BranchProbability.
 396   return (uint64_t)Weight * 5 > (uint64_t)Sum * 4;
 397 }
 398
 399 BasicBlock *BranchProbabilityInfo::getHotSucc(BasicBlock *BB) const {
 400   uint32_t Sum = 0;
 401   uint32_t MaxWeight = 0;
 402   BasicBlock *MaxSucc = 0;
 403
 404   for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
 405     BasicBlock *Succ = *I;
 406     uint32_t Weight = getEdgeWeight(BB, Succ);
 407     uint32_t PrevSum = Sum;
 408
 409     Sum += Weight;
 410     assert(Sum > PrevSum); (void) PrevSum;
 411
 412     if (Weight > MaxWeight) {
 413       MaxWeight = Weight;
 414       MaxSucc = Succ;
 415     }
 416   }
 417
 418   // FIXME: Use BranchProbability::compare.
 419   if ((uint64_t)MaxWeight * 5 > (uint64_t)Sum * 4)
 420     return MaxSucc;
 421
 422   return 0;
 423 }
 424
 425 // Return edge's weight. If can't find it, return DEFAULT_WEIGHT value.
 426 uint32_t BranchProbabilityInfo::
 427 getEdgeWeight(const BasicBlock *Src, const BasicBlock *Dst) const {
 428   Edge E(Src, Dst);
 429   DenseMap<Edge, uint32_t>::const_iterator I = Weights.find(E);
 430
 431   if (I != Weights.end())
 432     return I->second;
 433
 434   return DEFAULT_WEIGHT;
 435 }
 436
 437 void BranchProbabilityInfo::
 438 setEdgeWeight(const BasicBlock *Src, const BasicBlock *Dst, uint32_t Weight) {
 439   Weights[std::make_pair(Src, Dst)] = Weight;
 440   DEBUG(dbgs() << "set edge " << Src->getNameStr() << " -> "
 441                << Dst->getNameStr() << " weight to " << Weight
 442                << (isEdgeHot(Src, Dst) ? " [is HOT now]\n" : "\n"));
 443 }
 444
 445
 446 BranchProbability BranchProbabilityInfo::
 447 getEdgeProbability(const BasicBlock *Src, const BasicBlock *Dst) const {
 448
 449   uint32_t N = getEdgeWeight(Src, Dst);
 450   uint32_t D = getSumForBlock(Src);
 451
 452   return BranchProbability(N, D);
 453 }
 454
 455 raw_ostream &
 456 BranchProbabilityInfo::printEdgeProbability(raw_ostream &OS, BasicBlock *Src,
 457                                             BasicBlock *Dst) const {
 458
 459   const BranchProbability Prob = getEdgeProbability(Src, Dst);
 460   OS << "edge " << Src->getNameStr() << " -> " << Dst->getNameStr()
 461      << " probability is " << Prob
 462      << (isEdgeHot(Src, Dst) ? " [HOT edge]\n" : "\n");
 463
 464   return OS;
 465 }