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/LLVMContext.h"
  17 #include "llvm/Metadata.h"
  18 #include "llvm/Analysis/BranchProbabilityInfo.h"
  19 #include "llvm/Analysis/LoopInfo.h"
  20 #include "llvm/Support/Debug.h"
  21
  22 using namespace llvm;
  23
  24 INITIALIZE_PASS_BEGIN(BranchProbabilityInfo, "branch-prob",
  25                       "Branch Probability Analysis", false, true)
  26 INITIALIZE_PASS_DEPENDENCY(LoopInfo)
  27 INITIALIZE_PASS_END(BranchProbabilityInfo, "branch-prob",
  28                     "Branch Probability Analysis", false, true)
  29
  30 char BranchProbabilityInfo::ID = 0;
  31
  32 namespace {
  33 // Please note that BranchProbabilityAnalysis is not a FunctionPass.
  34 // It is created by BranchProbabilityInfo (which is a FunctionPass), which
  35 // provides a clear interface. Thanks to that, all heuristics and other
  36 // private methods are hidden in the .cpp file.
  37 class BranchProbabilityAnalysis {
  38
  39   typedef std::pair<const BasicBlock *, const BasicBlock *> Edge;
  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   static const uint32_t FPH_TAKEN_WEIGHT = 20;
  80   static const uint32_t FPH_NONTAKEN_WEIGHT = 12;
  81
  82   // Standard weight value. Used when none of the heuristics set weight for
  83   // the edge.
  84   static const uint32_t NORMAL_WEIGHT = 16;
  85
  86   // Minimum weight of an edge. Please note, that weight is NEVER 0.
  87   static const uint32_t MIN_WEIGHT = 1;
  88
  89   // Return TRUE if BB leads directly to a Return Instruction.
  90   static bool isReturningBlock(BasicBlock *BB) {
  91     SmallPtrSet<BasicBlock *, 8> Visited;
  92
  93     while (true) {
  94       TerminatorInst *TI = BB->getTerminator();
  95       if (isa<ReturnInst>(TI))
  96         return true;
  97
  98       if (TI->getNumSuccessors() > 1)
  99         break;
 100
 101       // It is unreachable block which we can consider as a return instruction.
 102       if (TI->getNumSuccessors() == 0)
 103         return true;
 104
 105       Visited.insert(BB);
 106       BB = TI->getSuccessor(0);
 107
 108       // Stop if cycle is detected.
 109       if (Visited.count(BB))
 110         return false;
 111     }
 112
 113     return false;
 114   }
 115
 116   uint32_t getMaxWeightFor(BasicBlock *BB) const {
 117     return UINT32_MAX / BB->getTerminator()->getNumSuccessors();
 118   }
 119
 120 public:
 121   BranchProbabilityAnalysis(BranchProbabilityInfo *BP, LoopInfo *LI)
 122     : BP(BP), LI(LI) {
 123   }
 124
 125   // Metadata Weights
 126   bool calcMetadataWeights(BasicBlock *BB);
 127
 128   // Return Heuristics
 129   bool calcReturnHeuristics(BasicBlock *BB);
 130
 131   // Pointer Heuristics
 132   bool calcPointerHeuristics(BasicBlock *BB);
 133
 134   // Loop Branch Heuristics
 135   bool calcLoopBranchHeuristics(BasicBlock *BB);
 136
 137   // Zero Heuristics
 138   bool calcZeroHeuristics(BasicBlock *BB);
 139
 140   // Floating Point Heuristics
 141   bool calcFloatingPointHeuristics(BasicBlock *BB);
 142
 143   bool runOnFunction(Function &F);
 144 };
 145 } // end anonymous namespace
 146
 147 // Propagate existing explicit probabilities from either profile data or
 148 // 'expect' intrinsic processing.
 149 bool BranchProbabilityAnalysis::calcMetadataWeights(BasicBlock *BB) {
 150   TerminatorInst *TI = BB->getTerminator();
 151   if (TI->getNumSuccessors() == 1)
 152     return false;
 153   if (!isa<BranchInst>(TI) && !isa<SwitchInst>(TI))
 154     return false;
 155
 156   MDNode *WeightsNode = TI->getMetadata(LLVMContext::MD_prof);
 157   if (!WeightsNode)
 158     return false;
 159
 160   // Ensure there are weights for all of the successors. Note that the first
 161   // operand to the metadata node is a name, not a weight.
 162   if (WeightsNode->getNumOperands() != TI->getNumSuccessors() + 1)
 163     return false;
 164
 165   // Build up the final weights that will be used in a temporary buffer, but
 166   // don't add them until all weihts are present. Each weight value is clamped
 167   // to [1, getMaxWeightFor(BB)].
 168   uint32_t WeightLimit = getMaxWeightFor(BB);
 169   SmallVector<uint32_t, 2> Weights;
 170   Weights.reserve(TI->getNumSuccessors());
 171   for (unsigned i = 1, e = WeightsNode->getNumOperands(); i != e; ++i) {
 172     ConstantInt *Weight = dyn_cast<ConstantInt>(WeightsNode->getOperand(i));
 173     if (!Weight)
 174       return false;
 175     Weights.push_back(
 176       std::max<uint32_t>(1, Weight->getLimitedValue(WeightLimit)));
 177   }
 178   assert(Weights.size() == TI->getNumSuccessors() && "Checked above");
 179   for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
 180     BP->setEdgeWeight(BB, TI->getSuccessor(i), Weights[i]);
 181
 182   return true;
 183 }
 184
 185 // Calculate Edge Weights using "Return Heuristics". Predict a successor which
 186 // leads directly to Return Instruction will not be taken.
 187 bool BranchProbabilityAnalysis::calcReturnHeuristics(BasicBlock *BB){
 188   if (BB->getTerminator()->getNumSuccessors() == 1)
 189     return false;
 190
 191   SmallPtrSet<BasicBlock *, 4> ReturningEdges;
 192   SmallPtrSet<BasicBlock *, 4> StayEdges;
 193
 194   for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
 195     BasicBlock *Succ = *I;
 196     if (isReturningBlock(Succ))
 197       ReturningEdges.insert(Succ);
 198     else
 199       StayEdges.insert(Succ);
 200   }
 201
 202   if (uint32_t numStayEdges = StayEdges.size()) {
 203     uint32_t stayWeight = RH_TAKEN_WEIGHT / numStayEdges;
 204     if (stayWeight < NORMAL_WEIGHT)
 205       stayWeight = NORMAL_WEIGHT;
 206
 207     for (SmallPtrSet<BasicBlock *, 4>::iterator I = StayEdges.begin(),
 208          E = StayEdges.end(); I != E; ++I)
 209       BP->setEdgeWeight(BB, *I, stayWeight);
 210   }
 211
 212   if (uint32_t numRetEdges = ReturningEdges.size()) {
 213     uint32_t retWeight = RH_NONTAKEN_WEIGHT / numRetEdges;
 214     if (retWeight < MIN_WEIGHT)
 215       retWeight = MIN_WEIGHT;
 216     for (SmallPtrSet<BasicBlock *, 4>::iterator I = ReturningEdges.begin(),
 217          E = ReturningEdges.end(); I != E; ++I) {
 218       BP->setEdgeWeight(BB, *I, retWeight);
 219     }
 220   }
 221
 222   return ReturningEdges.size() > 0;
 223 }
 224
 225 // Calculate Edge Weights using "Pointer Heuristics". Predict a comparsion
 226 // between two pointer or pointer and NULL will fail.
 227 bool BranchProbabilityAnalysis::calcPointerHeuristics(BasicBlock *BB) {
 228   BranchInst * BI = dyn_cast<BranchInst>(BB->getTerminator());
 229   if (!BI || !BI->isConditional())
 230     return false;
 231
 232   Value *Cond = BI->getCondition();
 233   ICmpInst *CI = dyn_cast<ICmpInst>(Cond);
 234   if (!CI || !CI->isEquality())
 235     return false;
 236
 237   Value *LHS = CI->getOperand(0);
 238
 239   if (!LHS->getType()->isPointerTy())
 240     return false;
 241
 242   assert(CI->getOperand(1)->getType()->isPointerTy());
 243
 244   BasicBlock *Taken = BI->getSuccessor(0);
 245   BasicBlock *NonTaken = BI->getSuccessor(1);
 246
 247   // p != 0   ->   isProb = true
 248   // p == 0   ->   isProb = false
 249   // p != q   ->   isProb = true
 250   // p == q   ->   isProb = false;
 251   bool isProb = CI->getPredicate() == ICmpInst::ICMP_NE;
 252   if (!isProb)
 253     std::swap(Taken, NonTaken);
 254
 255   BP->setEdgeWeight(BB, Taken, PH_TAKEN_WEIGHT);
 256   BP->setEdgeWeight(BB, NonTaken, PH_NONTAKEN_WEIGHT);
 257   return true;
 258 }
 259
 260 // Calculate Edge Weights using "Loop Branch Heuristics". Predict backedges
 261 // as taken, exiting edges as not-taken.
 262 bool BranchProbabilityAnalysis::calcLoopBranchHeuristics(BasicBlock *BB) {
 263   uint32_t numSuccs = BB->getTerminator()->getNumSuccessors();
 264
 265   Loop *L = LI->getLoopFor(BB);
 266   if (!L)
 267     return false;
 268
 269   SmallPtrSet<BasicBlock *, 8> BackEdges;
 270   SmallPtrSet<BasicBlock *, 8> ExitingEdges;
 271   SmallPtrSet<BasicBlock *, 8> InEdges; // Edges from header to the loop.
 272
 273   bool isHeader = BB == L->getHeader();
 274
 275   for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
 276     BasicBlock *Succ = *I;
 277     Loop *SuccL = LI->getLoopFor(Succ);
 278     if (SuccL != L)
 279       ExitingEdges.insert(Succ);
 280     else if (Succ == L->getHeader())
 281       BackEdges.insert(Succ);
 282     else if (isHeader)
 283       InEdges.insert(Succ);
 284   }
 285
 286   if (uint32_t numBackEdges = BackEdges.size()) {
 287     uint32_t backWeight = LBH_TAKEN_WEIGHT / numBackEdges;
 288     if (backWeight < NORMAL_WEIGHT)
 289       backWeight = NORMAL_WEIGHT;
 290
 291     for (SmallPtrSet<BasicBlock *, 8>::iterator EI = BackEdges.begin(),
 292          EE = BackEdges.end(); EI != EE; ++EI) {
 293       BasicBlock *Back = *EI;
 294       BP->setEdgeWeight(BB, Back, backWeight);
 295     }
 296   }
 297
 298   if (uint32_t numInEdges = InEdges.size()) {
 299     uint32_t inWeight = LBH_TAKEN_WEIGHT / numInEdges;
 300     if (inWeight < NORMAL_WEIGHT)
 301       inWeight = NORMAL_WEIGHT;
 302
 303     for (SmallPtrSet<BasicBlock *, 8>::iterator EI = InEdges.begin(),
 304          EE = InEdges.end(); EI != EE; ++EI) {
 305       BasicBlock *Back = *EI;
 306       BP->setEdgeWeight(BB, Back, inWeight);
 307     }
 308   }
 309
 310   uint32_t numExitingEdges = ExitingEdges.size();
 311   if (uint32_t numNonExitingEdges = numSuccs - numExitingEdges) {
 312     uint32_t exitWeight = LBH_NONTAKEN_WEIGHT / numNonExitingEdges;
 313     if (exitWeight < MIN_WEIGHT)
 314       exitWeight = MIN_WEIGHT;
 315
 316     for (SmallPtrSet<BasicBlock *, 8>::iterator EI = ExitingEdges.begin(),
 317          EE = ExitingEdges.end(); EI != EE; ++EI) {
 318       BasicBlock *Exiting = *EI;
 319       BP->setEdgeWeight(BB, Exiting, exitWeight);
 320     }
 321   }
 322
 323   return true;
 324 }
 325
 326 bool BranchProbabilityAnalysis::calcZeroHeuristics(BasicBlock *BB) {
 327   BranchInst * BI = dyn_cast<BranchInst>(BB->getTerminator());
 328   if (!BI || !BI->isConditional())
 329     return false;
 330
 331   Value *Cond = BI->getCondition();
 332   ICmpInst *CI = dyn_cast<ICmpInst>(Cond);
 333   if (!CI)
 334     return false;
 335
 336   Value *RHS = CI->getOperand(1);
 337   ConstantInt *CV = dyn_cast<ConstantInt>(RHS);
 338   if (!CV)
 339     return false;
 340
 341   bool isProb;
 342   if (CV->isZero()) {
 343     switch (CI->getPredicate()) {
 344     case CmpInst::ICMP_EQ:
 345       // X == 0   ->  Unlikely
 346       isProb = false;
 347       break;
 348     case CmpInst::ICMP_NE:
 349       // X != 0   ->  Likely
 350       isProb = true;
 351       break;
 352     case CmpInst::ICMP_SLT:
 353       // X < 0   ->  Unlikely
 354       isProb = false;
 355       break;
 356     case CmpInst::ICMP_SGT:
 357       // X > 0   ->  Likely
 358       isProb = true;
 359       break;
 360     default:
 361       return false;
 362     }
 363   } else if (CV->isOne() && CI->getPredicate() == CmpInst::ICMP_SLT) {
 364     // InstCombine canonicalizes X <= 0 into X < 1.
 365     // X <= 0   ->  Unlikely
 366     isProb = false;
 367   } else if (CV->isAllOnesValue() && CI->getPredicate() == CmpInst::ICMP_SGT) {
 368     // InstCombine canonicalizes X >= 0 into X > -1.
 369     // X >= 0   ->  Likely
 370     isProb = true;
 371   } else {
 372     return false;
 373   }
 374
 375   BasicBlock *Taken = BI->getSuccessor(0);
 376   BasicBlock *NonTaken = BI->getSuccessor(1);
 377
 378   if (!isProb)
 379     std::swap(Taken, NonTaken);
 380
 381   BP->setEdgeWeight(BB, Taken, ZH_TAKEN_WEIGHT);
 382   BP->setEdgeWeight(BB, NonTaken, ZH_NONTAKEN_WEIGHT);
 383
 384   return true;
 385 }
 386
 387 bool BranchProbabilityAnalysis::calcFloatingPointHeuristics(BasicBlock *BB) {
 388   BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
 389   if (!BI || !BI->isConditional())
 390     return false;
 391
 392   Value *Cond = BI->getCondition();
 393   FCmpInst *FCmp = dyn_cast<FCmpInst>(Cond);
 394   if (!FCmp || !FCmp->isEquality())
 395     return false;
 396
 397   BasicBlock *Taken = BI->getSuccessor(0);
 398   BasicBlock *NonTaken = BI->getSuccessor(1);
 399
 400   // f1 == f2 -> Unlikely
 401   // f1 != f2 -> Likely
 402   if (FCmp->isTrueWhenEqual())
 403     std::swap(Taken, NonTaken);
 404
 405   BP->setEdgeWeight(BB, Taken, FPH_TAKEN_WEIGHT);
 406   BP->setEdgeWeight(BB, NonTaken, FPH_NONTAKEN_WEIGHT);
 407
 408   return true;
 409 }
 410
 411 bool BranchProbabilityAnalysis::runOnFunction(Function &F) {
 412
 413   for (Function::iterator I = F.begin(), E = F.end(); I != E; ) {
 414     BasicBlock *BB = I++;
 415
 416     if (calcMetadataWeights(BB))
 417       continue;
 418
 419     if (calcLoopBranchHeuristics(BB))
 420       continue;
 421
 422     if (calcReturnHeuristics(BB))
 423       continue;
 424
 425     if (calcPointerHeuristics(BB))
 426       continue;
 427
 428     if (calcZeroHeuristics(BB))
 429       continue;
 430
 431     calcFloatingPointHeuristics(BB);
 432   }
 433
 434   return false;
 435 }
 436
 437 void BranchProbabilityInfo::getAnalysisUsage(AnalysisUsage &AU) const {
 438     AU.addRequired<LoopInfo>();
 439     AU.setPreservesAll();
 440 }
 441
 442 bool BranchProbabilityInfo::runOnFunction(Function &F) {
 443   LoopInfo &LI = getAnalysis<LoopInfo>();
 444   BranchProbabilityAnalysis BPA(this, &LI);
 445   return BPA.runOnFunction(F);
 446 }
 447
 448 uint32_t BranchProbabilityInfo::getSumForBlock(const BasicBlock *BB) const {
 449   uint32_t Sum = 0;
 450
 451   for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
 452     const BasicBlock *Succ = *I;
 453     uint32_t Weight = getEdgeWeight(BB, Succ);
 454     uint32_t PrevSum = Sum;
 455
 456     Sum += Weight;
 457     assert(Sum > PrevSum); (void) PrevSum;
 458   }
 459
 460   return Sum;
 461 }
 462
 463 bool BranchProbabilityInfo::
 464 isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const {
 465   // Hot probability is at least 4/5 = 80%
 466   uint32_t Weight = getEdgeWeight(Src, Dst);
 467   uint32_t Sum = getSumForBlock(Src);
 468
 469   // FIXME: Implement BranchProbability::compare then change this code to
 470   // compare this BranchProbability against a static "hot" BranchProbability.
 471   return (uint64_t)Weight * 5 > (uint64_t)Sum * 4;
 472 }
 473
 474 BasicBlock *BranchProbabilityInfo::getHotSucc(BasicBlock *BB) const {
 475   uint32_t Sum = 0;
 476   uint32_t MaxWeight = 0;
 477   BasicBlock *MaxSucc = 0;
 478
 479   for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
 480     BasicBlock *Succ = *I;
 481     uint32_t Weight = getEdgeWeight(BB, Succ);
 482     uint32_t PrevSum = Sum;
 483
 484     Sum += Weight;
 485     assert(Sum > PrevSum); (void) PrevSum;
 486
 487     if (Weight > MaxWeight) {
 488       MaxWeight = Weight;
 489       MaxSucc = Succ;
 490     }
 491   }
 492
 493   // FIXME: Use BranchProbability::compare.
 494   if ((uint64_t)MaxWeight * 5 > (uint64_t)Sum * 4)
 495     return MaxSucc;
 496
 497   return 0;
 498 }
 499
 500 // Return edge's weight. If can't find it, return DEFAULT_WEIGHT value.
 501 uint32_t BranchProbabilityInfo::
 502 getEdgeWeight(const BasicBlock *Src, const BasicBlock *Dst) const {
 503   Edge E(Src, Dst);
 504   DenseMap<Edge, uint32_t>::const_iterator I = Weights.find(E);
 505
 506   if (I != Weights.end())
 507     return I->second;
 508
 509   return DEFAULT_WEIGHT;
 510 }
 511
 512 void BranchProbabilityInfo::
 513 setEdgeWeight(const BasicBlock *Src, const BasicBlock *Dst, uint32_t Weight) {
 514   Weights[std::make_pair(Src, Dst)] = Weight;
 515   DEBUG(dbgs() << "set edge " << Src->getNameStr() << " -> "
 516                << Dst->getNameStr() << " weight to " << Weight
 517                << (isEdgeHot(Src, Dst) ? " [is HOT now]\n" : "\n"));
 518 }
 519
 520
 521 BranchProbability BranchProbabilityInfo::
 522 getEdgeProbability(const BasicBlock *Src, const BasicBlock *Dst) const {
 523
 524   uint32_t N = getEdgeWeight(Src, Dst);
 525   uint32_t D = getSumForBlock(Src);
 526
 527   return BranchProbability(N, D);
 528 }
 529
 530 raw_ostream &
 531 BranchProbabilityInfo::printEdgeProbability(raw_ostream &OS, BasicBlock *Src,
 532                                             BasicBlock *Dst) const {
 533
 534   const BranchProbability Prob = getEdgeProbability(Src, Dst);
 535   OS << "edge " << Src->getNameStr() << " -> " << Dst->getNameStr()
 536      << " probability is " << Prob
 537      << (isEdgeHot(Src, Dst) ? " [HOT edge]\n" : "\n");
 538
 539   return OS;
 540 }