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