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