1 //===-- BranchProbabilityInfo.cpp - Branch Probability Analysis -----------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // Loops should be simplified before this analysis.
12 //===----------------------------------------------------------------------===//
14 #define DEBUG_TYPE "branch-prob"
15 #include "llvm/Analysis/BranchProbabilityInfo.h"
16 #include "llvm/ADT/PostOrderIterator.h"
17 #include "llvm/Analysis/LoopInfo.h"
18 #include "llvm/IR/CFG.h"
19 #include "llvm/IR/Constants.h"
20 #include "llvm/IR/Function.h"
21 #include "llvm/IR/Instructions.h"
22 #include "llvm/IR/LLVMContext.h"
23 #include "llvm/IR/Metadata.h"
24 #include "llvm/Support/Debug.h"
28 INITIALIZE_PASS_BEGIN(BranchProbabilityInfo, "branch-prob",
29 "Branch Probability Analysis", false, true)
30 INITIALIZE_PASS_DEPENDENCY(LoopInfo)
31 INITIALIZE_PASS_END(BranchProbabilityInfo, "branch-prob",
32 "Branch Probability Analysis", false, true)
34 char BranchProbabilityInfo::ID = 0;
36 // Weights are for internal use only. They are used by heuristics to help to
37 // estimate edges' probability. Example:
39 // Using "Loop Branch Heuristics" we predict weights of edges for the
54 // Probability of the edge BB2->BB1 = 124 / (124 + 4) = 0.96875
55 // Probability of the edge BB2->BB3 = 4 / (124 + 4) = 0.03125
56 static const uint32_t LBH_TAKEN_WEIGHT = 124;
57 static const uint32_t LBH_NONTAKEN_WEIGHT = 4;
59 /// \brief Unreachable-terminating branch taken weight.
61 /// This is the weight for a branch being taken to a block that terminates
62 /// (eventually) in unreachable. These are predicted as unlikely as possible.
63 static const uint32_t UR_TAKEN_WEIGHT = 1;
65 /// \brief Unreachable-terminating branch not-taken weight.
67 /// This is the weight for a branch not being taken toward a block that
68 /// terminates (eventually) in unreachable. Such a branch is essentially never
69 /// taken. Set the weight to an absurdly high value so that nested loops don't
70 /// easily subsume it.
71 static const uint32_t UR_NONTAKEN_WEIGHT = 1024*1024 - 1;
73 /// \brief Weight for a branch taken going into a cold block.
75 /// This is the weight for a branch taken toward a block marked
76 /// cold. A block is marked cold if it's postdominated by a
77 /// block containing a call to a cold function. Cold functions
78 /// are those marked with attribute 'cold'.
79 static const uint32_t CC_TAKEN_WEIGHT = 4;
81 /// \brief Weight for a branch not-taken into a cold block.
83 /// This is the weight for a branch not taken toward a block marked
85 static const uint32_t CC_NONTAKEN_WEIGHT = 64;
87 static const uint32_t PH_TAKEN_WEIGHT = 20;
88 static const uint32_t PH_NONTAKEN_WEIGHT = 12;
90 static const uint32_t ZH_TAKEN_WEIGHT = 20;
91 static const uint32_t ZH_NONTAKEN_WEIGHT = 12;
93 static const uint32_t FPH_TAKEN_WEIGHT = 20;
94 static const uint32_t FPH_NONTAKEN_WEIGHT = 12;
96 /// \brief Invoke-terminating normal branch taken weight
98 /// This is the weight for branching to the normal destination of an invoke
99 /// instruction. We expect this to happen most of the time. Set the weight to an
100 /// absurdly high value so that nested loops subsume it.
101 static const uint32_t IH_TAKEN_WEIGHT = 1024 * 1024 - 1;
103 /// \brief Invoke-terminating normal branch not-taken weight.
105 /// This is the weight for branching to the unwind destination of an invoke
106 /// instruction. This is essentially never taken.
107 static const uint32_t IH_NONTAKEN_WEIGHT = 1;
109 // Standard weight value. Used when none of the heuristics set weight for
111 static const uint32_t NORMAL_WEIGHT = 16;
113 // Minimum weight of an edge. Please note, that weight is NEVER 0.
114 static const uint32_t MIN_WEIGHT = 1;
116 static uint32_t getMaxWeightFor(BasicBlock *BB) {
117 return UINT32_MAX / BB->getTerminator()->getNumSuccessors();
121 /// \brief Calculate edge weights for successors lead to unreachable.
123 /// Predict that a successor which leads necessarily to an
124 /// unreachable-terminated block as extremely unlikely.
125 bool BranchProbabilityInfo::calcUnreachableHeuristics(BasicBlock *BB) {
126 TerminatorInst *TI = BB->getTerminator();
127 if (TI->getNumSuccessors() == 0) {
128 if (isa<UnreachableInst>(TI))
129 PostDominatedByUnreachable.insert(BB);
133 SmallVector<unsigned, 4> UnreachableEdges;
134 SmallVector<unsigned, 4> ReachableEdges;
136 for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
137 if (PostDominatedByUnreachable.count(*I))
138 UnreachableEdges.push_back(I.getSuccessorIndex());
140 ReachableEdges.push_back(I.getSuccessorIndex());
143 // If all successors are in the set of blocks post-dominated by unreachable,
144 // this block is too.
145 if (UnreachableEdges.size() == TI->getNumSuccessors())
146 PostDominatedByUnreachable.insert(BB);
148 // Skip probabilities if this block has a single successor or if all were
150 if (TI->getNumSuccessors() == 1 || UnreachableEdges.empty())
153 uint32_t UnreachableWeight =
154 std::max(UR_TAKEN_WEIGHT / (unsigned)UnreachableEdges.size(), MIN_WEIGHT);
155 for (SmallVectorImpl<unsigned>::iterator I = UnreachableEdges.begin(),
156 E = UnreachableEdges.end();
158 setEdgeWeight(BB, *I, UnreachableWeight);
160 if (ReachableEdges.empty())
162 uint32_t ReachableWeight =
163 std::max(UR_NONTAKEN_WEIGHT / (unsigned)ReachableEdges.size(),
165 for (SmallVectorImpl<unsigned>::iterator I = ReachableEdges.begin(),
166 E = ReachableEdges.end();
168 setEdgeWeight(BB, *I, ReachableWeight);
173 // Propagate existing explicit probabilities from either profile data or
174 // 'expect' intrinsic processing.
175 bool BranchProbabilityInfo::calcMetadataWeights(BasicBlock *BB) {
176 TerminatorInst *TI = BB->getTerminator();
177 if (TI->getNumSuccessors() == 1)
179 if (!isa<BranchInst>(TI) && !isa<SwitchInst>(TI))
182 MDNode *WeightsNode = TI->getMetadata(LLVMContext::MD_prof);
186 // Ensure there are weights for all of the successors. Note that the first
187 // operand to the metadata node is a name, not a weight.
188 if (WeightsNode->getNumOperands() != TI->getNumSuccessors() + 1)
191 // Build up the final weights that will be used in a temporary buffer, but
192 // don't add them until all weihts are present. Each weight value is clamped
193 // to [1, getMaxWeightFor(BB)].
194 uint32_t WeightLimit = getMaxWeightFor(BB);
195 SmallVector<uint32_t, 2> Weights;
196 Weights.reserve(TI->getNumSuccessors());
197 for (unsigned i = 1, e = WeightsNode->getNumOperands(); i != e; ++i) {
198 ConstantInt *Weight = dyn_cast<ConstantInt>(WeightsNode->getOperand(i));
202 std::max<uint32_t>(1, Weight->getLimitedValue(WeightLimit)));
204 assert(Weights.size() == TI->getNumSuccessors() && "Checked above");
205 for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
206 setEdgeWeight(BB, i, Weights[i]);
211 /// \brief Calculate edge weights for edges leading to cold blocks.
213 /// A cold block is one post-dominated by a block with a call to a
214 /// cold function. Those edges are unlikely to be taken, so we give
215 /// them relatively low weight.
217 /// Return true if we could compute the weights for cold edges.
218 /// Return false, otherwise.
219 bool BranchProbabilityInfo::calcColdCallHeuristics(BasicBlock *BB) {
220 TerminatorInst *TI = BB->getTerminator();
221 if (TI->getNumSuccessors() == 0)
224 // Determine which successors are post-dominated by a cold block.
225 SmallVector<unsigned, 4> ColdEdges;
226 SmallVector<unsigned, 4> NormalEdges;
227 for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I)
228 if (PostDominatedByColdCall.count(*I))
229 ColdEdges.push_back(I.getSuccessorIndex());
231 NormalEdges.push_back(I.getSuccessorIndex());
233 // If all successors are in the set of blocks post-dominated by cold calls,
234 // this block is in the set post-dominated by cold calls.
235 if (ColdEdges.size() == TI->getNumSuccessors())
236 PostDominatedByColdCall.insert(BB);
238 // Otherwise, if the block itself contains a cold function, add it to the
239 // set of blocks postdominated by a cold call.
240 assert(!PostDominatedByColdCall.count(BB));
241 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
242 if (CallInst *CI = dyn_cast<CallInst>(I))
243 if (CI->hasFnAttr(Attribute::Cold)) {
244 PostDominatedByColdCall.insert(BB);
249 // Skip probabilities if this block has a single successor.
250 if (TI->getNumSuccessors() == 1 || ColdEdges.empty())
253 uint32_t ColdWeight =
254 std::max(CC_TAKEN_WEIGHT / (unsigned) ColdEdges.size(), MIN_WEIGHT);
255 for (SmallVectorImpl<unsigned>::iterator I = ColdEdges.begin(),
258 setEdgeWeight(BB, *I, ColdWeight);
260 if (NormalEdges.empty())
262 uint32_t NormalWeight = std::max(
263 CC_NONTAKEN_WEIGHT / (unsigned) NormalEdges.size(), NORMAL_WEIGHT);
264 for (SmallVectorImpl<unsigned>::iterator I = NormalEdges.begin(),
265 E = NormalEdges.end();
267 setEdgeWeight(BB, *I, NormalWeight);
272 // Calculate Edge Weights using "Pointer Heuristics". Predict a comparsion
273 // between two pointer or pointer and NULL will fail.
274 bool BranchProbabilityInfo::calcPointerHeuristics(BasicBlock *BB) {
275 BranchInst * BI = dyn_cast<BranchInst>(BB->getTerminator());
276 if (!BI || !BI->isConditional())
279 Value *Cond = BI->getCondition();
280 ICmpInst *CI = dyn_cast<ICmpInst>(Cond);
281 if (!CI || !CI->isEquality())
284 Value *LHS = CI->getOperand(0);
286 if (!LHS->getType()->isPointerTy())
289 assert(CI->getOperand(1)->getType()->isPointerTy());
291 // p != 0 -> isProb = true
292 // p == 0 -> isProb = false
293 // p != q -> isProb = true
294 // p == q -> isProb = false;
295 unsigned TakenIdx = 0, NonTakenIdx = 1;
296 bool isProb = CI->getPredicate() == ICmpInst::ICMP_NE;
298 std::swap(TakenIdx, NonTakenIdx);
300 setEdgeWeight(BB, TakenIdx, PH_TAKEN_WEIGHT);
301 setEdgeWeight(BB, NonTakenIdx, PH_NONTAKEN_WEIGHT);
305 // Calculate Edge Weights using "Loop Branch Heuristics". Predict backedges
306 // as taken, exiting edges as not-taken.
307 bool BranchProbabilityInfo::calcLoopBranchHeuristics(BasicBlock *BB) {
308 Loop *L = LI->getLoopFor(BB);
312 SmallVector<unsigned, 8> BackEdges;
313 SmallVector<unsigned, 8> ExitingEdges;
314 SmallVector<unsigned, 8> InEdges; // Edges from header to the loop.
316 for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
317 if (!L->contains(*I))
318 ExitingEdges.push_back(I.getSuccessorIndex());
319 else if (L->getHeader() == *I)
320 BackEdges.push_back(I.getSuccessorIndex());
322 InEdges.push_back(I.getSuccessorIndex());
325 if (uint32_t numBackEdges = BackEdges.size()) {
326 uint32_t backWeight = LBH_TAKEN_WEIGHT / numBackEdges;
327 if (backWeight < NORMAL_WEIGHT)
328 backWeight = NORMAL_WEIGHT;
330 for (SmallVectorImpl<unsigned>::iterator EI = BackEdges.begin(),
331 EE = BackEdges.end(); EI != EE; ++EI) {
332 setEdgeWeight(BB, *EI, backWeight);
336 if (uint32_t numInEdges = InEdges.size()) {
337 uint32_t inWeight = LBH_TAKEN_WEIGHT / numInEdges;
338 if (inWeight < NORMAL_WEIGHT)
339 inWeight = NORMAL_WEIGHT;
341 for (SmallVectorImpl<unsigned>::iterator EI = InEdges.begin(),
342 EE = InEdges.end(); EI != EE; ++EI) {
343 setEdgeWeight(BB, *EI, inWeight);
347 if (uint32_t numExitingEdges = ExitingEdges.size()) {
348 uint32_t exitWeight = LBH_NONTAKEN_WEIGHT / numExitingEdges;
349 if (exitWeight < MIN_WEIGHT)
350 exitWeight = MIN_WEIGHT;
352 for (SmallVectorImpl<unsigned>::iterator EI = ExitingEdges.begin(),
353 EE = ExitingEdges.end(); EI != EE; ++EI) {
354 setEdgeWeight(BB, *EI, exitWeight);
361 bool BranchProbabilityInfo::calcZeroHeuristics(BasicBlock *BB) {
362 BranchInst * BI = dyn_cast<BranchInst>(BB->getTerminator());
363 if (!BI || !BI->isConditional())
366 Value *Cond = BI->getCondition();
367 ICmpInst *CI = dyn_cast<ICmpInst>(Cond);
371 Value *RHS = CI->getOperand(1);
372 ConstantInt *CV = dyn_cast<ConstantInt>(RHS);
378 switch (CI->getPredicate()) {
379 case CmpInst::ICMP_EQ:
380 // X == 0 -> Unlikely
383 case CmpInst::ICMP_NE:
387 case CmpInst::ICMP_SLT:
391 case CmpInst::ICMP_SGT:
398 } else if (CV->isOne() && CI->getPredicate() == CmpInst::ICMP_SLT) {
399 // InstCombine canonicalizes X <= 0 into X < 1.
400 // X <= 0 -> Unlikely
402 } else if (CV->isAllOnesValue()) {
403 switch (CI->getPredicate()) {
404 case CmpInst::ICMP_EQ:
405 // X == -1 -> Unlikely
408 case CmpInst::ICMP_NE:
412 case CmpInst::ICMP_SGT:
413 // InstCombine canonicalizes X >= 0 into X > -1.
424 unsigned TakenIdx = 0, NonTakenIdx = 1;
427 std::swap(TakenIdx, NonTakenIdx);
429 setEdgeWeight(BB, TakenIdx, ZH_TAKEN_WEIGHT);
430 setEdgeWeight(BB, NonTakenIdx, ZH_NONTAKEN_WEIGHT);
435 bool BranchProbabilityInfo::calcFloatingPointHeuristics(BasicBlock *BB) {
436 BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
437 if (!BI || !BI->isConditional())
440 Value *Cond = BI->getCondition();
441 FCmpInst *FCmp = dyn_cast<FCmpInst>(Cond);
446 if (FCmp->isEquality()) {
447 // f1 == f2 -> Unlikely
448 // f1 != f2 -> Likely
449 isProb = !FCmp->isTrueWhenEqual();
450 } else if (FCmp->getPredicate() == FCmpInst::FCMP_ORD) {
453 } else if (FCmp->getPredicate() == FCmpInst::FCMP_UNO) {
460 unsigned TakenIdx = 0, NonTakenIdx = 1;
463 std::swap(TakenIdx, NonTakenIdx);
465 setEdgeWeight(BB, TakenIdx, FPH_TAKEN_WEIGHT);
466 setEdgeWeight(BB, NonTakenIdx, FPH_NONTAKEN_WEIGHT);
471 bool BranchProbabilityInfo::calcInvokeHeuristics(BasicBlock *BB) {
472 InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator());
476 setEdgeWeight(BB, 0/*Index for Normal*/, IH_TAKEN_WEIGHT);
477 setEdgeWeight(BB, 1/*Index for Unwind*/, IH_NONTAKEN_WEIGHT);
481 void BranchProbabilityInfo::getAnalysisUsage(AnalysisUsage &AU) const {
482 AU.addRequired<LoopInfo>();
483 AU.setPreservesAll();
486 bool BranchProbabilityInfo::runOnFunction(Function &F) {
487 DEBUG(dbgs() << "---- Branch Probability Info : " << F.getName()
489 LastF = &F; // Store the last function we ran on for printing.
490 LI = &getAnalysis<LoopInfo>();
491 assert(PostDominatedByUnreachable.empty());
492 assert(PostDominatedByColdCall.empty());
494 // Walk the basic blocks in post-order so that we can build up state about
495 // the successors of a block iteratively.
496 for (po_iterator<BasicBlock *> I = po_begin(&F.getEntryBlock()),
497 E = po_end(&F.getEntryBlock());
499 DEBUG(dbgs() << "Computing probabilities for " << I->getName() << "\n");
500 if (calcUnreachableHeuristics(*I))
502 if (calcMetadataWeights(*I))
504 if (calcColdCallHeuristics(*I))
506 if (calcLoopBranchHeuristics(*I))
508 if (calcPointerHeuristics(*I))
510 if (calcZeroHeuristics(*I))
512 if (calcFloatingPointHeuristics(*I))
514 calcInvokeHeuristics(*I);
517 PostDominatedByUnreachable.clear();
518 PostDominatedByColdCall.clear();
522 void BranchProbabilityInfo::print(raw_ostream &OS, const Module *) const {
523 OS << "---- Branch Probabilities ----\n";
524 // We print the probabilities from the last function the analysis ran over,
525 // or the function it is currently running over.
526 assert(LastF && "Cannot print prior to running over a function");
527 for (Function::const_iterator BI = LastF->begin(), BE = LastF->end();
529 for (succ_const_iterator SI = succ_begin(BI), SE = succ_end(BI);
531 printEdgeProbability(OS << " ", BI, *SI);
536 uint32_t BranchProbabilityInfo::getSumForBlock(const BasicBlock *BB) const {
539 for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
540 uint32_t Weight = getEdgeWeight(BB, I.getSuccessorIndex());
541 uint32_t PrevSum = Sum;
544 assert(Sum > PrevSum); (void) PrevSum;
550 bool BranchProbabilityInfo::
551 isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const {
552 // Hot probability is at least 4/5 = 80%
553 // FIXME: Compare against a static "hot" BranchProbability.
554 return getEdgeProbability(Src, Dst) > BranchProbability(4, 5);
557 BasicBlock *BranchProbabilityInfo::getHotSucc(BasicBlock *BB) const {
559 uint32_t MaxWeight = 0;
560 BasicBlock *MaxSucc = 0;
562 for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
563 BasicBlock *Succ = *I;
564 uint32_t Weight = getEdgeWeight(BB, Succ);
565 uint32_t PrevSum = Sum;
568 assert(Sum > PrevSum); (void) PrevSum;
570 if (Weight > MaxWeight) {
576 // Hot probability is at least 4/5 = 80%
577 if (BranchProbability(MaxWeight, Sum) > BranchProbability(4, 5))
583 /// Get the raw edge weight for the edge. If can't find it, return
584 /// DEFAULT_WEIGHT value. Here an edge is specified using PredBlock and an index
585 /// to the successors.
586 uint32_t BranchProbabilityInfo::
587 getEdgeWeight(const BasicBlock *Src, unsigned IndexInSuccessors) const {
588 DenseMap<Edge, uint32_t>::const_iterator I =
589 Weights.find(std::make_pair(Src, IndexInSuccessors));
591 if (I != Weights.end())
594 return DEFAULT_WEIGHT;
598 BranchProbabilityInfo::
599 getEdgeWeight(const BasicBlock *Src, succ_const_iterator Dst) const {
600 size_t index = std::distance(succ_begin(Src), Dst);
601 return getEdgeWeight(Src, index);
604 /// Get the raw edge weight calculated for the block pair. This returns the sum
605 /// of all raw edge weights from Src to Dst.
606 uint32_t BranchProbabilityInfo::
607 getEdgeWeight(const BasicBlock *Src, const BasicBlock *Dst) const {
609 DenseMap<Edge, uint32_t>::const_iterator MapI;
610 for (succ_const_iterator I = succ_begin(Src), E = succ_end(Src); I != E; ++I)
612 MapI = Weights.find(std::make_pair(Src, I.getSuccessorIndex()));
613 if (MapI != Weights.end())
614 Weight += MapI->second;
616 return (Weight == 0) ? DEFAULT_WEIGHT : Weight;
619 /// Set the edge weight for a given edge specified by PredBlock and an index
620 /// to the successors.
621 void BranchProbabilityInfo::
622 setEdgeWeight(const BasicBlock *Src, unsigned IndexInSuccessors,
624 Weights[std::make_pair(Src, IndexInSuccessors)] = Weight;
625 DEBUG(dbgs() << "set edge " << Src->getName() << " -> "
626 << IndexInSuccessors << " successor weight to "
630 /// Get an edge's probability, relative to other out-edges from Src.
631 BranchProbability BranchProbabilityInfo::
632 getEdgeProbability(const BasicBlock *Src, unsigned IndexInSuccessors) const {
633 uint32_t N = getEdgeWeight(Src, IndexInSuccessors);
634 uint32_t D = getSumForBlock(Src);
636 return BranchProbability(N, D);
639 /// Get the probability of going from Src to Dst. It returns the sum of all
640 /// probabilities for edges from Src to Dst.
641 BranchProbability BranchProbabilityInfo::
642 getEdgeProbability(const BasicBlock *Src, const BasicBlock *Dst) const {
644 uint32_t N = getEdgeWeight(Src, Dst);
645 uint32_t D = getSumForBlock(Src);
647 return BranchProbability(N, D);
651 BranchProbabilityInfo::printEdgeProbability(raw_ostream &OS,
652 const BasicBlock *Src,
653 const BasicBlock *Dst) const {
655 const BranchProbability Prob = getEdgeProbability(Src, Dst);
656 OS << "edge " << Src->getName() << " -> " << Dst->getName()
657 << " probability is " << Prob
658 << (isEdgeHot(Src, Dst) ? " [HOT edge]\n" : "\n");