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