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