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/Instructions.h"
  15 #include "llvm/Analysis/BranchProbabilityInfo.h"
  16 #include "llvm/Analysis/LoopInfo.h"
  17 #include "llvm/Support/Debug.h"
  18
  19 using namespace llvm;
  20
  21 INITIALIZE_PASS_BEGIN(BranchProbabilityInfo, "branch-prob",
  22                       "Branch Probability Analysis", false, true)
  23 INITIALIZE_PASS_DEPENDENCY(LoopInfo)
  24 INITIALIZE_PASS_END(BranchProbabilityInfo, "branch-prob",
  25                     "Branch Probability Analysis", false, true)
  26
  27 char BranchProbabilityInfo::ID = 0;
  28
  29 namespace {
  30 // Please note that BranchProbabilityAnalysis is not a FunctionPass.
  31 // It is created by BranchProbabilityInfo (which is a FunctionPass), which
  32 // provides a clear interface. Thanks to that, all heuristics and other
  33 // private methods are hidden in the .cpp file.
  34 class BranchProbabilityAnalysis {
  35
  36   typedef std::pair<const BasicBlock *, const BasicBlock *> Edge;
  37
  38   DenseMap<Edge, uint32_t> *Weights;
  39
  40   BranchProbabilityInfo *BP;
  41
  42   LoopInfo *LI;
  43
  44
  45   // Weights are for internal use only. They are used by heuristics to help to
  46   // estimate edges' probability. Example:
  47   //
  48   // Using "Loop Branch Heuristics" we predict weights of edges for the
  49   // block BB2.
  50   //         ...
  51   //          |
  52   //          V
  53   //         BB1<-+
  54   //          |   |
  55   //          |   | (Weight = 124)
  56   //          V   |
  57   //         BB2--+
  58   //          |
  59   //          | (Weight = 4)
  60   //          V
  61   //         BB3
  62   //
  63   // Probability of the edge BB2->BB1 = 124 / (124 + 4) = 0.96875
  64   // Probability of the edge BB2->BB3 = 4 / (124 + 4) = 0.03125
  65
  66   static const uint32_t LBH_TAKEN_WEIGHT = 124;
  67   static const uint32_t LBH_NONTAKEN_WEIGHT = 4;
  68
  69   static const uint32_t RH_TAKEN_WEIGHT = 24;
  70   static const uint32_t RH_NONTAKEN_WEIGHT = 8;
  71
  72   static const uint32_t PH_TAKEN_WEIGHT = 20;
  73   static const uint32_t PH_NONTAKEN_WEIGHT = 12;
  74
  75   // Standard weight value. Used when none of the heuristics set weight for
  76   // the edge.
  77   static const uint32_t NORMAL_WEIGHT = 16;
  78
  79   // Minimum weight of an edge. Please note, that weight is NEVER 0.
  80   static const uint32_t MIN_WEIGHT = 1;
  81
  82   // Return TRUE if BB leads directly to a Return Instruction.
  83   static bool isReturningBlock(BasicBlock *BB) {
  84     SmallPtrSet<BasicBlock *, 8> Visited;
  85
  86     while (true) {
  87       TerminatorInst *TI = BB->getTerminator();
  88       if (isa<ReturnInst>(TI))
  89         return true;
  90
  91       if (TI->getNumSuccessors() > 1)
  92         break;
  93
  94       // It is unreachable block which we can consider as a return instruction.
  95       if (TI->getNumSuccessors() == 0)
  96         return true;
  97
  98       Visited.insert(BB);
  99       BB = TI->getSuccessor(0);
 100
 101       // Stop if cycle is detected.
 102       if (Visited.count(BB))
 103         return false;
 104     }
 105
 106     return false;
 107   }
 108
 109   uint32_t getMaxWeightFor(BasicBlock *BB) const {
 110     return UINT32_MAX / BB->getTerminator()->getNumSuccessors();
 111   }
 112
 113 public:
 114   BranchProbabilityAnalysis(DenseMap<Edge, uint32_t> *W,
 115                             BranchProbabilityInfo *BP, LoopInfo *LI)
 116     : Weights(W), BP(BP), LI(LI) {
 117   }
 118
 119   // Return Heuristics
 120   bool calcReturnHeuristics(BasicBlock *BB);
 121
 122   // Pointer Heuristics
 123   bool calcPointerHeuristics(BasicBlock *BB);
 124
 125   // Loop Branch Heuristics
 126   bool calcLoopBranchHeuristics(BasicBlock *BB);
 127
 128   bool runOnFunction(Function &F);
 129 };
 130 } // end anonymous namespace
 131
 132 // Calculate Edge Weights using "Return Heuristics". Predict a successor which
 133 // leads directly to Return Instruction will not be taken.
 134 bool BranchProbabilityAnalysis::calcReturnHeuristics(BasicBlock *BB){
 135   if (BB->getTerminator()->getNumSuccessors() == 1)
 136     return false;
 137
 138   SmallVector<BasicBlock *, 4> ReturningEdges;
 139   SmallVector<BasicBlock *, 4> StayEdges;
 140
 141   for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
 142     BasicBlock *Succ = *I;
 143     if (isReturningBlock(Succ))
 144       ReturningEdges.push_back(Succ);
 145     else
 146       StayEdges.push_back(Succ);
 147   }
 148
 149   if (uint32_t numStayEdges = StayEdges.size()) {
 150     uint32_t stayWeight = RH_TAKEN_WEIGHT / numStayEdges;
 151     if (stayWeight < NORMAL_WEIGHT)
 152       stayWeight = NORMAL_WEIGHT;
 153
 154     for (SmallVector<BasicBlock *, 4>::iterator I = StayEdges.begin(),
 155          E = StayEdges.end(); I != E; ++I)
 156       BP->setEdgeWeight(BB, *I, stayWeight);
 157   }
 158
 159   if (uint32_t numRetEdges = ReturningEdges.size()) {
 160     uint32_t retWeight = RH_NONTAKEN_WEIGHT / numRetEdges;
 161     if (retWeight < MIN_WEIGHT)
 162       retWeight = MIN_WEIGHT;
 163     for (SmallVector<BasicBlock *, 4>::iterator I = ReturningEdges.begin(),
 164          E = ReturningEdges.end(); I != E; ++I) {
 165       BP->setEdgeWeight(BB, *I, retWeight);
 166     }
 167   }
 168
 169   return ReturningEdges.size() > 0;
 170 }
 171
 172 // Calculate Edge Weights using "Pointer Heuristics". Predict a comparsion
 173 // between two pointer or pointer and NULL will fail.
 174 bool BranchProbabilityAnalysis::calcPointerHeuristics(BasicBlock *BB) {
 175   BranchInst * BI = dyn_cast<BranchInst>(BB->getTerminator());
 176   if (!BI || !BI->isConditional())
 177     return false;
 178
 179   Value *Cond = BI->getCondition();
 180   ICmpInst *CI = dyn_cast<ICmpInst>(Cond);
 181   if (!CI || !CI->isEquality())
 182     return false;
 183
 184   Value *LHS = CI->getOperand(0);
 185
 186   if (!LHS->getType()->isPointerTy())
 187     return false;
 188
 189   assert(CI->getOperand(1)->getType()->isPointerTy());
 190
 191   BasicBlock *Taken = BI->getSuccessor(0);
 192   BasicBlock *NonTaken = BI->getSuccessor(1);
 193
 194   // p != 0   ->   isProb = true
 195   // p == 0   ->   isProb = false
 196   // p != q   ->   isProb = true
 197   // p == q   ->   isProb = false;
 198   bool isProb = CI->getPredicate() == ICmpInst::ICMP_NE;
 199   if (!isProb)
 200     std::swap(Taken, NonTaken);
 201
 202   BP->setEdgeWeight(BB, Taken, PH_TAKEN_WEIGHT);
 203   BP->setEdgeWeight(BB, NonTaken, PH_NONTAKEN_WEIGHT);
 204   return true;
 205 }
 206
 207 // Calculate Edge Weights using "Loop Branch Heuristics". Predict backedges
 208 // as taken, exiting edges as not-taken.
 209 bool BranchProbabilityAnalysis::calcLoopBranchHeuristics(BasicBlock *BB) {
 210   uint32_t numSuccs = BB->getTerminator()->getNumSuccessors();
 211
 212   Loop *L = LI->getLoopFor(BB);
 213   if (!L)
 214     return false;
 215
 216   SmallVector<BasicBlock *, 8> BackEdges;
 217   SmallVector<BasicBlock *, 8> ExitingEdges;
 218   SmallVector<BasicBlock *, 8> InEdges; // Edges from header to the loop.
 219
 220   bool isHeader = BB == L->getHeader();
 221
 222   for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
 223     BasicBlock *Succ = *I;
 224     Loop *SuccL = LI->getLoopFor(Succ);
 225     if (SuccL != L)
 226       ExitingEdges.push_back(Succ);
 227     else if (Succ == L->getHeader())
 228       BackEdges.push_back(Succ);
 229     else if (isHeader)
 230       InEdges.push_back(Succ);
 231   }
 232
 233   if (uint32_t numBackEdges = BackEdges.size()) {
 234     uint32_t backWeight = LBH_TAKEN_WEIGHT / numBackEdges;
 235     if (backWeight < NORMAL_WEIGHT)
 236       backWeight = NORMAL_WEIGHT;
 237
 238     for (SmallVector<BasicBlock *, 8>::iterator EI = BackEdges.begin(),
 239          EE = BackEdges.end(); EI != EE; ++EI) {
 240       BasicBlock *Back = *EI;
 241       BP->setEdgeWeight(BB, Back, backWeight);
 242     }
 243   }
 244
 245   if (uint32_t numInEdges = InEdges.size()) {
 246     uint32_t inWeight = LBH_TAKEN_WEIGHT / numInEdges;
 247     if (inWeight < NORMAL_WEIGHT)
 248       inWeight = NORMAL_WEIGHT;
 249
 250     for (SmallVector<BasicBlock *, 8>::iterator EI = InEdges.begin(),
 251          EE = InEdges.end(); EI != EE; ++EI) {
 252       BasicBlock *Back = *EI;
 253       BP->setEdgeWeight(BB, Back, inWeight);
 254     }
 255   }
 256
 257   uint32_t numExitingEdges = ExitingEdges.size();
 258   if (uint32_t numNonExitingEdges = numSuccs - numExitingEdges) {
 259     uint32_t exitWeight = LBH_NONTAKEN_WEIGHT / numNonExitingEdges;
 260     if (exitWeight < MIN_WEIGHT)
 261       exitWeight = MIN_WEIGHT;
 262
 263     for (SmallVector<BasicBlock *, 8>::iterator EI = ExitingEdges.begin(),
 264          EE = ExitingEdges.end(); EI != EE; ++EI) {
 265       BasicBlock *Exiting = *EI;
 266       BP->setEdgeWeight(BB, Exiting, exitWeight);
 267     }
 268   }
 269
 270   return true;
 271 }
 272
 273 bool BranchProbabilityAnalysis::runOnFunction(Function &F) {
 274
 275   for (Function::iterator I = F.begin(), E = F.end(); I != E; ) {
 276     BasicBlock *BB = I++;
 277
 278     // Only LBH uses setEdgeWeight method.
 279     if (calcLoopBranchHeuristics(BB))
 280       continue;
 281
 282     // PH and RH use only incEdgeWeight and decEwdgeWeight methods to
 283     // not efface LBH results.
 284     if (calcReturnHeuristics(BB))
 285       continue;
 286
 287     calcPointerHeuristics(BB);
 288   }
 289
 290   return false;
 291 }
 292
 293 void BranchProbabilityInfo::getAnalysisUsage(AnalysisUsage &AU) const {
 294     AU.addRequired<LoopInfo>();
 295     AU.setPreservesAll();
 296 }
 297
 298 bool BranchProbabilityInfo::runOnFunction(Function &F) {
 299   LoopInfo &LI = getAnalysis<LoopInfo>();
 300   BranchProbabilityAnalysis BPA(&Weights, this, &LI);
 301   return BPA.runOnFunction(F);
 302 }
 303
 304 uint32_t BranchProbabilityInfo::getSumForBlock(const BasicBlock *BB) const {
 305   uint32_t Sum = 0;
 306
 307   for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
 308     const BasicBlock *Succ = *I;
 309     uint32_t Weight = getEdgeWeight(BB, Succ);
 310     uint32_t PrevSum = Sum;
 311
 312     Sum += Weight;
 313     assert(Sum > PrevSum); (void) PrevSum;
 314   }
 315
 316   return Sum;
 317 }
 318
 319 bool BranchProbabilityInfo::
 320 isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const {
 321   // Hot probability is at least 4/5 = 80%
 322   uint32_t Weight = getEdgeWeight(Src, Dst);
 323   uint32_t Sum = getSumForBlock(Src);
 324
 325   // FIXME: Implement BranchProbability::compare then change this code to
 326   // compare this BranchProbability against a static "hot" BranchProbability.
 327   return (uint64_t)Weight * 5 > (uint64_t)Sum * 4;
 328 }
 329
 330 BasicBlock *BranchProbabilityInfo::getHotSucc(BasicBlock *BB) const {
 331   uint32_t Sum = 0;
 332   uint32_t MaxWeight = 0;
 333   BasicBlock *MaxSucc = 0;
 334
 335   for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
 336     BasicBlock *Succ = *I;
 337     uint32_t Weight = getEdgeWeight(BB, Succ);
 338     uint32_t PrevSum = Sum;
 339
 340     Sum += Weight;
 341     assert(Sum > PrevSum); (void) PrevSum;
 342
 343     if (Weight > MaxWeight) {
 344       MaxWeight = Weight;
 345       MaxSucc = Succ;
 346     }
 347   }
 348
 349   // FIXME: Use BranchProbability::compare.
 350   if ((uint64_t)MaxWeight * 5 > (uint64_t)Sum * 4)
 351     return MaxSucc;
 352
 353   return 0;
 354 }
 355
 356 // Return edge's weight. If can't find it, return DEFAULT_WEIGHT value.
 357 uint32_t BranchProbabilityInfo::
 358 getEdgeWeight(const BasicBlock *Src, const BasicBlock *Dst) const {
 359   Edge E(Src, Dst);
 360   DenseMap<Edge, uint32_t>::const_iterator I = Weights.find(E);
 361
 362   if (I != Weights.end())
 363     return I->second;
 364
 365   return DEFAULT_WEIGHT;
 366 }
 367
 368 void BranchProbabilityInfo::
 369 setEdgeWeight(const BasicBlock *Src, const BasicBlock *Dst, uint32_t Weight) {
 370   Weights[std::make_pair(Src, Dst)] = Weight;
 371   DEBUG(dbgs() << "set edge " << Src->getNameStr() << " -> "
 372                << Dst->getNameStr() << " weight to " << Weight
 373                << (isEdgeHot(Src, Dst) ? " [is HOT now]\n" : "\n"));
 374 }
 375
 376
 377 BranchProbability BranchProbabilityInfo::
 378 getEdgeProbability(const BasicBlock *Src, const BasicBlock *Dst) const {
 379
 380   uint32_t N = getEdgeWeight(Src, Dst);
 381   uint32_t D = getSumForBlock(Src);
 382
 383   return BranchProbability(N, D);
 384 }
 385
 386 raw_ostream &
 387 BranchProbabilityInfo::printEdgeProbability(raw_ostream &OS, BasicBlock *Src,
 388                                             BasicBlock *Dst) const {
 389
 390   const BranchProbability Prob = getEdgeProbability(Src, Dst);
 391   OS << "edge " << Src->getNameStr() << " -> " << Dst->getNameStr()
 392      << " probability is " << Prob
 393      << (isEdgeHot(Src, Dst) ? " [HOT edge]\n" : "\n");
 394
 395   return OS;
 396 }