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