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 #include "llvm/Analysis/BranchProbabilityInfo.h"
15 #include "llvm/ADT/PostOrderIterator.h"
16 #include "llvm/Analysis/LoopInfo.h"
17 #include "llvm/Analysis/TargetLibraryInfo.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"
25 #include "llvm/Support/raw_ostream.h"
29 #define DEBUG_TYPE "branch-prob"
31 INITIALIZE_PASS_BEGIN(BranchProbabilityInfoWrapperPass, "branch-prob",
32 "Branch Probability Analysis", false, true)
33 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
34 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
35 INITIALIZE_PASS_END(BranchProbabilityInfoWrapperPass, "branch-prob",
36 "Branch Probability Analysis", false, true)
38 char BranchProbabilityInfoWrapperPass::ID = 0;
40 // Weights are for internal use only. They are used by heuristics to help to
41 // estimate edges' probability. Example:
43 // Using "Loop Branch Heuristics" we predict weights of edges for the
58 // Probability of the edge BB2->BB1 = 124 / (124 + 4) = 0.96875
59 // Probability of the edge BB2->BB3 = 4 / (124 + 4) = 0.03125
60 static const uint32_t LBH_TAKEN_WEIGHT = 124;
61 static const uint32_t LBH_NONTAKEN_WEIGHT = 4;
63 /// \brief Unreachable-terminating branch taken probability.
65 /// This is the probability for a branch being taken to a block that terminates
66 /// (eventually) in unreachable. These are predicted as unlikely as possible.
67 /// All reachable probability will equally share the remaining part.
68 static const BranchProbability UR_TAKEN_PROB = BranchProbability::getRaw(1);
70 /// \brief Weight for a branch taken going into a cold block.
72 /// This is the weight for a branch taken toward a block marked
73 /// cold. A block is marked cold if it's postdominated by a
74 /// block containing a call to a cold function. Cold functions
75 /// are those marked with attribute 'cold'.
76 static const uint32_t CC_TAKEN_WEIGHT = 4;
78 /// \brief Weight for a branch not-taken into a cold block.
80 /// This is the weight for a branch not taken toward a block marked
82 static const uint32_t CC_NONTAKEN_WEIGHT = 64;
84 static const uint32_t PH_TAKEN_WEIGHT = 20;
85 static const uint32_t PH_NONTAKEN_WEIGHT = 12;
87 static const uint32_t ZH_TAKEN_WEIGHT = 20;
88 static const uint32_t ZH_NONTAKEN_WEIGHT = 12;
90 static const uint32_t FPH_TAKEN_WEIGHT = 20;
91 static const uint32_t FPH_NONTAKEN_WEIGHT = 12;
93 /// \brief Invoke-terminating normal branch taken weight
95 /// This is the weight for branching to the normal destination of an invoke
96 /// instruction. We expect this to happen most of the time. Set the weight to an
97 /// absurdly high value so that nested loops subsume it.
98 static const uint32_t IH_TAKEN_WEIGHT = 1024 * 1024 - 1;
100 /// \brief Invoke-terminating normal branch not-taken weight.
102 /// This is the weight for branching to the unwind destination of an invoke
103 /// instruction. This is essentially never taken.
104 static const uint32_t IH_NONTAKEN_WEIGHT = 1;
106 /// \brief Add \p BB to PostDominatedByUnreachable set if applicable.
108 BranchProbabilityInfo::updatePostDominatedByUnreachable(const BasicBlock *BB) {
109 const TerminatorInst *TI = BB->getTerminator();
110 if (TI->getNumSuccessors() == 0) {
111 if (isa<UnreachableInst>(TI) ||
112 // If this block is terminated by a call to
113 // @llvm.experimental.deoptimize then treat it like an unreachable since
114 // the @llvm.experimental.deoptimize call is expected to practically
116 BB->getTerminatingDeoptimizeCall())
117 PostDominatedByUnreachable.insert(BB);
121 // If the terminator is an InvokeInst, check only the normal destination block
122 // as the unwind edge of InvokeInst is also very unlikely taken.
123 if (auto *II = dyn_cast<InvokeInst>(TI)) {
124 if (PostDominatedByUnreachable.count(II->getNormalDest()))
125 PostDominatedByUnreachable.insert(BB);
129 for (auto *I : successors(BB))
130 // If any of successor is not post dominated then BB is also not.
131 if (!PostDominatedByUnreachable.count(I))
134 PostDominatedByUnreachable.insert(BB);
137 /// \brief Add \p BB to PostDominatedByColdCall set if applicable.
139 BranchProbabilityInfo::updatePostDominatedByColdCall(const BasicBlock *BB) {
140 assert(!PostDominatedByColdCall.count(BB));
141 const TerminatorInst *TI = BB->getTerminator();
142 if (TI->getNumSuccessors() == 0)
145 // If all of successor are post dominated then BB is also done.
146 if (llvm::all_of(successors(BB), [&](const BasicBlock *SuccBB) {
147 return PostDominatedByColdCall.count(SuccBB);
149 PostDominatedByColdCall.insert(BB);
153 // If the terminator is an InvokeInst, check only the normal destination
154 // block as the unwind edge of InvokeInst is also very unlikely taken.
155 if (auto *II = dyn_cast<InvokeInst>(TI))
156 if (PostDominatedByColdCall.count(II->getNormalDest())) {
157 PostDominatedByColdCall.insert(BB);
161 // Otherwise, if the block itself contains a cold function, add it to the
162 // set of blocks post-dominated by a cold call.
164 if (const CallInst *CI = dyn_cast<CallInst>(&I))
165 if (CI->hasFnAttr(Attribute::Cold)) {
166 PostDominatedByColdCall.insert(BB);
171 /// \brief Calculate edge weights for successors lead to unreachable.
173 /// Predict that a successor which leads necessarily to an
174 /// unreachable-terminated block as extremely unlikely.
175 bool BranchProbabilityInfo::calcUnreachableHeuristics(const BasicBlock *BB) {
176 const TerminatorInst *TI = BB->getTerminator();
177 assert(TI->getNumSuccessors() > 1 && "expected more than one successor!");
179 // Return false here so that edge weights for InvokeInst could be decided
180 // in calcInvokeHeuristics().
181 if (isa<InvokeInst>(TI))
184 SmallVector<unsigned, 4> UnreachableEdges;
185 SmallVector<unsigned, 4> ReachableEdges;
187 for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I)
188 if (PostDominatedByUnreachable.count(*I))
189 UnreachableEdges.push_back(I.getSuccessorIndex());
191 ReachableEdges.push_back(I.getSuccessorIndex());
193 // Skip probabilities if all were reachable.
194 if (UnreachableEdges.empty())
197 if (ReachableEdges.empty()) {
198 BranchProbability Prob(1, UnreachableEdges.size());
199 for (unsigned SuccIdx : UnreachableEdges)
200 setEdgeProbability(BB, SuccIdx, Prob);
204 auto UnreachableProb = UR_TAKEN_PROB;
206 (BranchProbability::getOne() - UR_TAKEN_PROB * UnreachableEdges.size()) /
207 ReachableEdges.size();
209 for (unsigned SuccIdx : UnreachableEdges)
210 setEdgeProbability(BB, SuccIdx, UnreachableProb);
211 for (unsigned SuccIdx : ReachableEdges)
212 setEdgeProbability(BB, SuccIdx, ReachableProb);
217 // Propagate existing explicit probabilities from either profile data or
218 // 'expect' intrinsic processing. Examine metadata against unreachable
219 // heuristic. The probability of the edge coming to unreachable block is
220 // set to min of metadata and unreachable heuristic.
221 bool BranchProbabilityInfo::calcMetadataWeights(const BasicBlock *BB) {
222 const TerminatorInst *TI = BB->getTerminator();
223 assert(TI->getNumSuccessors() > 1 && "expected more than one successor!");
224 if (!isa<BranchInst>(TI) && !isa<SwitchInst>(TI))
227 MDNode *WeightsNode = TI->getMetadata(LLVMContext::MD_prof);
231 // Check that the number of successors is manageable.
232 assert(TI->getNumSuccessors() < UINT32_MAX && "Too many successors");
234 // Ensure there are weights for all of the successors. Note that the first
235 // operand to the metadata node is a name, not a weight.
236 if (WeightsNode->getNumOperands() != TI->getNumSuccessors() + 1)
239 // Build up the final weights that will be used in a temporary buffer.
240 // Compute the sum of all weights to later decide whether they need to
241 // be scaled to fit in 32 bits.
242 uint64_t WeightSum = 0;
243 SmallVector<uint32_t, 2> Weights;
244 SmallVector<unsigned, 2> UnreachableIdxs;
245 SmallVector<unsigned, 2> ReachableIdxs;
246 Weights.reserve(TI->getNumSuccessors());
247 for (unsigned i = 1, e = WeightsNode->getNumOperands(); i != e; ++i) {
248 ConstantInt *Weight =
249 mdconst::dyn_extract<ConstantInt>(WeightsNode->getOperand(i));
252 assert(Weight->getValue().getActiveBits() <= 32 &&
253 "Too many bits for uint32_t");
254 Weights.push_back(Weight->getZExtValue());
255 WeightSum += Weights.back();
256 if (PostDominatedByUnreachable.count(TI->getSuccessor(i - 1)))
257 UnreachableIdxs.push_back(i - 1);
259 ReachableIdxs.push_back(i - 1);
261 assert(Weights.size() == TI->getNumSuccessors() && "Checked above");
263 // If the sum of weights does not fit in 32 bits, scale every weight down
265 uint64_t ScalingFactor =
266 (WeightSum > UINT32_MAX) ? WeightSum / UINT32_MAX + 1 : 1;
268 if (ScalingFactor > 1) {
270 for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) {
271 Weights[i] /= ScalingFactor;
272 WeightSum += Weights[i];
275 assert(WeightSum <= UINT32_MAX &&
276 "Expected weights to scale down to 32 bits");
278 if (WeightSum == 0 || ReachableIdxs.size() == 0) {
279 for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
281 WeightSum = TI->getNumSuccessors();
284 // Set the probability.
285 SmallVector<BranchProbability, 2> BP;
286 for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
287 BP.push_back({ Weights[i], static_cast<uint32_t>(WeightSum) });
289 // Examine the metadata against unreachable heuristic.
290 // If the unreachable heuristic is more strong then we use it for this edge.
291 if (UnreachableIdxs.size() > 0 && ReachableIdxs.size() > 0) {
292 auto ToDistribute = BranchProbability::getZero();
293 auto UnreachableProb = UR_TAKEN_PROB;
294 for (auto i : UnreachableIdxs)
295 if (UnreachableProb < BP[i]) {
296 ToDistribute += BP[i] - UnreachableProb;
297 BP[i] = UnreachableProb;
300 // If we modified the probability of some edges then we must distribute
301 // the difference between reachable blocks.
302 if (ToDistribute > BranchProbability::getZero()) {
303 BranchProbability PerEdge = ToDistribute / ReachableIdxs.size();
304 for (auto i : ReachableIdxs)
309 for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
310 setEdgeProbability(BB, i, BP[i]);
315 /// \brief Calculate edge weights for edges leading to cold blocks.
317 /// A cold block is one post-dominated by a block with a call to a
318 /// cold function. Those edges are unlikely to be taken, so we give
319 /// them relatively low weight.
321 /// Return true if we could compute the weights for cold edges.
322 /// Return false, otherwise.
323 bool BranchProbabilityInfo::calcColdCallHeuristics(const BasicBlock *BB) {
324 const TerminatorInst *TI = BB->getTerminator();
325 assert(TI->getNumSuccessors() > 1 && "expected more than one successor!");
327 // Return false here so that edge weights for InvokeInst could be decided
328 // in calcInvokeHeuristics().
329 if (isa<InvokeInst>(TI))
332 // Determine which successors are post-dominated by a cold block.
333 SmallVector<unsigned, 4> ColdEdges;
334 SmallVector<unsigned, 4> NormalEdges;
335 for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I)
336 if (PostDominatedByColdCall.count(*I))
337 ColdEdges.push_back(I.getSuccessorIndex());
339 NormalEdges.push_back(I.getSuccessorIndex());
341 // Skip probabilities if no cold edges.
342 if (ColdEdges.empty())
345 if (NormalEdges.empty()) {
346 BranchProbability Prob(1, ColdEdges.size());
347 for (unsigned SuccIdx : ColdEdges)
348 setEdgeProbability(BB, SuccIdx, Prob);
352 auto ColdProb = BranchProbability::getBranchProbability(
354 (CC_TAKEN_WEIGHT + CC_NONTAKEN_WEIGHT) * uint64_t(ColdEdges.size()));
355 auto NormalProb = BranchProbability::getBranchProbability(
357 (CC_TAKEN_WEIGHT + CC_NONTAKEN_WEIGHT) * uint64_t(NormalEdges.size()));
359 for (unsigned SuccIdx : ColdEdges)
360 setEdgeProbability(BB, SuccIdx, ColdProb);
361 for (unsigned SuccIdx : NormalEdges)
362 setEdgeProbability(BB, SuccIdx, NormalProb);
367 // Calculate Edge Weights using "Pointer Heuristics". Predict a comparsion
368 // between two pointer or pointer and NULL will fail.
369 bool BranchProbabilityInfo::calcPointerHeuristics(const BasicBlock *BB) {
370 const BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
371 if (!BI || !BI->isConditional())
374 Value *Cond = BI->getCondition();
375 ICmpInst *CI = dyn_cast<ICmpInst>(Cond);
376 if (!CI || !CI->isEquality())
379 Value *LHS = CI->getOperand(0);
381 if (!LHS->getType()->isPointerTy())
384 assert(CI->getOperand(1)->getType()->isPointerTy());
386 // p != 0 -> isProb = true
387 // p == 0 -> isProb = false
388 // p != q -> isProb = true
389 // p == q -> isProb = false;
390 unsigned TakenIdx = 0, NonTakenIdx = 1;
391 bool isProb = CI->getPredicate() == ICmpInst::ICMP_NE;
393 std::swap(TakenIdx, NonTakenIdx);
395 BranchProbability TakenProb(PH_TAKEN_WEIGHT,
396 PH_TAKEN_WEIGHT + PH_NONTAKEN_WEIGHT);
397 setEdgeProbability(BB, TakenIdx, TakenProb);
398 setEdgeProbability(BB, NonTakenIdx, TakenProb.getCompl());
402 // Calculate Edge Weights using "Loop Branch Heuristics". Predict backedges
403 // as taken, exiting edges as not-taken.
404 bool BranchProbabilityInfo::calcLoopBranchHeuristics(const BasicBlock *BB,
405 const LoopInfo &LI) {
406 Loop *L = LI.getLoopFor(BB);
410 SmallVector<unsigned, 8> BackEdges;
411 SmallVector<unsigned, 8> ExitingEdges;
412 SmallVector<unsigned, 8> InEdges; // Edges from header to the loop.
414 for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
415 if (!L->contains(*I))
416 ExitingEdges.push_back(I.getSuccessorIndex());
417 else if (L->getHeader() == *I)
418 BackEdges.push_back(I.getSuccessorIndex());
420 InEdges.push_back(I.getSuccessorIndex());
423 if (BackEdges.empty() && ExitingEdges.empty())
426 // Collect the sum of probabilities of back-edges/in-edges/exiting-edges, and
427 // normalize them so that they sum up to one.
428 BranchProbability Probs[] = {BranchProbability::getZero(),
429 BranchProbability::getZero(),
430 BranchProbability::getZero()};
431 unsigned Denom = (BackEdges.empty() ? 0 : LBH_TAKEN_WEIGHT) +
432 (InEdges.empty() ? 0 : LBH_TAKEN_WEIGHT) +
433 (ExitingEdges.empty() ? 0 : LBH_NONTAKEN_WEIGHT);
434 if (!BackEdges.empty())
435 Probs[0] = BranchProbability(LBH_TAKEN_WEIGHT, Denom);
436 if (!InEdges.empty())
437 Probs[1] = BranchProbability(LBH_TAKEN_WEIGHT, Denom);
438 if (!ExitingEdges.empty())
439 Probs[2] = BranchProbability(LBH_NONTAKEN_WEIGHT, Denom);
441 if (uint32_t numBackEdges = BackEdges.size()) {
442 auto Prob = Probs[0] / numBackEdges;
443 for (unsigned SuccIdx : BackEdges)
444 setEdgeProbability(BB, SuccIdx, Prob);
447 if (uint32_t numInEdges = InEdges.size()) {
448 auto Prob = Probs[1] / numInEdges;
449 for (unsigned SuccIdx : InEdges)
450 setEdgeProbability(BB, SuccIdx, Prob);
453 if (uint32_t numExitingEdges = ExitingEdges.size()) {
454 auto Prob = Probs[2] / numExitingEdges;
455 for (unsigned SuccIdx : ExitingEdges)
456 setEdgeProbability(BB, SuccIdx, Prob);
462 bool BranchProbabilityInfo::calcZeroHeuristics(const BasicBlock *BB,
463 const TargetLibraryInfo *TLI) {
464 const BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
465 if (!BI || !BI->isConditional())
468 Value *Cond = BI->getCondition();
469 ICmpInst *CI = dyn_cast<ICmpInst>(Cond);
473 Value *RHS = CI->getOperand(1);
474 ConstantInt *CV = dyn_cast<ConstantInt>(RHS);
478 // If the LHS is the result of AND'ing a value with a single bit bitmask,
479 // we don't have information about probabilities.
480 if (Instruction *LHS = dyn_cast<Instruction>(CI->getOperand(0)))
481 if (LHS->getOpcode() == Instruction::And)
482 if (ConstantInt *AndRHS = dyn_cast<ConstantInt>(LHS->getOperand(1)))
483 if (AndRHS->getUniqueInteger().isPowerOf2())
486 // Check if the LHS is the return value of a library function
487 LibFunc Func = NumLibFuncs;
489 if (CallInst *Call = dyn_cast<CallInst>(CI->getOperand(0)))
490 if (Function *CalledFn = Call->getCalledFunction())
491 TLI->getLibFunc(*CalledFn, Func);
494 if (Func == LibFunc_strcasecmp ||
495 Func == LibFunc_strcmp ||
496 Func == LibFunc_strncasecmp ||
497 Func == LibFunc_strncmp ||
498 Func == LibFunc_memcmp) {
499 // strcmp and similar functions return zero, negative, or positive, if the
500 // first string is equal, less, or greater than the second. We consider it
501 // likely that the strings are not equal, so a comparison with zero is
502 // probably false, but also a comparison with any other number is also
503 // probably false given that what exactly is returned for nonzero values is
504 // not specified. Any kind of comparison other than equality we know
506 switch (CI->getPredicate()) {
507 case CmpInst::ICMP_EQ:
510 case CmpInst::ICMP_NE:
516 } else if (CV->isZero()) {
517 switch (CI->getPredicate()) {
518 case CmpInst::ICMP_EQ:
519 // X == 0 -> Unlikely
522 case CmpInst::ICMP_NE:
526 case CmpInst::ICMP_SLT:
530 case CmpInst::ICMP_SGT:
537 } else if (CV->isOne() && CI->getPredicate() == CmpInst::ICMP_SLT) {
538 // InstCombine canonicalizes X <= 0 into X < 1.
539 // X <= 0 -> Unlikely
541 } else if (CV->isMinusOne()) {
542 switch (CI->getPredicate()) {
543 case CmpInst::ICMP_EQ:
544 // X == -1 -> Unlikely
547 case CmpInst::ICMP_NE:
551 case CmpInst::ICMP_SGT:
552 // InstCombine canonicalizes X >= 0 into X > -1.
563 unsigned TakenIdx = 0, NonTakenIdx = 1;
566 std::swap(TakenIdx, NonTakenIdx);
568 BranchProbability TakenProb(ZH_TAKEN_WEIGHT,
569 ZH_TAKEN_WEIGHT + ZH_NONTAKEN_WEIGHT);
570 setEdgeProbability(BB, TakenIdx, TakenProb);
571 setEdgeProbability(BB, NonTakenIdx, TakenProb.getCompl());
575 bool BranchProbabilityInfo::calcFloatingPointHeuristics(const BasicBlock *BB) {
576 const BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
577 if (!BI || !BI->isConditional())
580 Value *Cond = BI->getCondition();
581 FCmpInst *FCmp = dyn_cast<FCmpInst>(Cond);
586 if (FCmp->isEquality()) {
587 // f1 == f2 -> Unlikely
588 // f1 != f2 -> Likely
589 isProb = !FCmp->isTrueWhenEqual();
590 } else if (FCmp->getPredicate() == FCmpInst::FCMP_ORD) {
593 } else if (FCmp->getPredicate() == FCmpInst::FCMP_UNO) {
600 unsigned TakenIdx = 0, NonTakenIdx = 1;
603 std::swap(TakenIdx, NonTakenIdx);
605 BranchProbability TakenProb(FPH_TAKEN_WEIGHT,
606 FPH_TAKEN_WEIGHT + FPH_NONTAKEN_WEIGHT);
607 setEdgeProbability(BB, TakenIdx, TakenProb);
608 setEdgeProbability(BB, NonTakenIdx, TakenProb.getCompl());
612 bool BranchProbabilityInfo::calcInvokeHeuristics(const BasicBlock *BB) {
613 const InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator());
617 BranchProbability TakenProb(IH_TAKEN_WEIGHT,
618 IH_TAKEN_WEIGHT + IH_NONTAKEN_WEIGHT);
619 setEdgeProbability(BB, 0 /*Index for Normal*/, TakenProb);
620 setEdgeProbability(BB, 1 /*Index for Unwind*/, TakenProb.getCompl());
624 void BranchProbabilityInfo::releaseMemory() {
628 void BranchProbabilityInfo::print(raw_ostream &OS) const {
629 OS << "---- Branch Probabilities ----\n";
630 // We print the probabilities from the last function the analysis ran over,
631 // or the function it is currently running over.
632 assert(LastF && "Cannot print prior to running over a function");
633 for (const auto &BI : *LastF) {
634 for (succ_const_iterator SI = succ_begin(&BI), SE = succ_end(&BI); SI != SE;
636 printEdgeProbability(OS << " ", &BI, *SI);
641 bool BranchProbabilityInfo::
642 isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const {
643 // Hot probability is at least 4/5 = 80%
644 // FIXME: Compare against a static "hot" BranchProbability.
645 return getEdgeProbability(Src, Dst) > BranchProbability(4, 5);
649 BranchProbabilityInfo::getHotSucc(const BasicBlock *BB) const {
650 auto MaxProb = BranchProbability::getZero();
651 const BasicBlock *MaxSucc = nullptr;
653 for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
654 const BasicBlock *Succ = *I;
655 auto Prob = getEdgeProbability(BB, Succ);
656 if (Prob > MaxProb) {
662 // Hot probability is at least 4/5 = 80%
663 if (MaxProb > BranchProbability(4, 5))
669 /// Get the raw edge probability for the edge. If can't find it, return a
670 /// default probability 1/N where N is the number of successors. Here an edge is
671 /// specified using PredBlock and an
672 /// index to the successors.
674 BranchProbabilityInfo::getEdgeProbability(const BasicBlock *Src,
675 unsigned IndexInSuccessors) const {
676 auto I = Probs.find(std::make_pair(Src, IndexInSuccessors));
678 if (I != Probs.end())
682 static_cast<uint32_t>(std::distance(succ_begin(Src), succ_end(Src)))};
686 BranchProbabilityInfo::getEdgeProbability(const BasicBlock *Src,
687 succ_const_iterator Dst) const {
688 return getEdgeProbability(Src, Dst.getSuccessorIndex());
691 /// Get the raw edge probability calculated for the block pair. This returns the
692 /// sum of all raw edge probabilities from Src to Dst.
694 BranchProbabilityInfo::getEdgeProbability(const BasicBlock *Src,
695 const BasicBlock *Dst) const {
696 auto Prob = BranchProbability::getZero();
697 bool FoundProb = false;
698 for (succ_const_iterator I = succ_begin(Src), E = succ_end(Src); I != E; ++I)
700 auto MapI = Probs.find(std::make_pair(Src, I.getSuccessorIndex()));
701 if (MapI != Probs.end()) {
703 Prob += MapI->second;
706 uint32_t succ_num = std::distance(succ_begin(Src), succ_end(Src));
707 return FoundProb ? Prob : BranchProbability(1, succ_num);
710 /// Set the edge probability for a given edge specified by PredBlock and an
711 /// index to the successors.
712 void BranchProbabilityInfo::setEdgeProbability(const BasicBlock *Src,
713 unsigned IndexInSuccessors,
714 BranchProbability Prob) {
715 Probs[std::make_pair(Src, IndexInSuccessors)] = Prob;
716 Handles.insert(BasicBlockCallbackVH(Src, this));
717 DEBUG(dbgs() << "set edge " << Src->getName() << " -> " << IndexInSuccessors
718 << " successor probability to " << Prob << "\n");
722 BranchProbabilityInfo::printEdgeProbability(raw_ostream &OS,
723 const BasicBlock *Src,
724 const BasicBlock *Dst) const {
726 const BranchProbability Prob = getEdgeProbability(Src, Dst);
727 OS << "edge " << Src->getName() << " -> " << Dst->getName()
728 << " probability is " << Prob
729 << (isEdgeHot(Src, Dst) ? " [HOT edge]\n" : "\n");
734 void BranchProbabilityInfo::eraseBlock(const BasicBlock *BB) {
735 for (auto I = Probs.begin(), E = Probs.end(); I != E; ++I) {
742 void BranchProbabilityInfo::calculate(const Function &F, const LoopInfo &LI,
743 const TargetLibraryInfo *TLI) {
744 DEBUG(dbgs() << "---- Branch Probability Info : " << F.getName()
746 LastF = &F; // Store the last function we ran on for printing.
747 assert(PostDominatedByUnreachable.empty());
748 assert(PostDominatedByColdCall.empty());
750 // Walk the basic blocks in post-order so that we can build up state about
751 // the successors of a block iteratively.
752 for (auto BB : post_order(&F.getEntryBlock())) {
753 DEBUG(dbgs() << "Computing probabilities for " << BB->getName() << "\n");
754 updatePostDominatedByUnreachable(BB);
755 updatePostDominatedByColdCall(BB);
756 // If there is no at least two successors, no sense to set probability.
757 if (BB->getTerminator()->getNumSuccessors() < 2)
759 if (calcMetadataWeights(BB))
761 if (calcUnreachableHeuristics(BB))
763 if (calcColdCallHeuristics(BB))
765 if (calcLoopBranchHeuristics(BB, LI))
767 if (calcPointerHeuristics(BB))
769 if (calcZeroHeuristics(BB, TLI))
771 if (calcFloatingPointHeuristics(BB))
773 calcInvokeHeuristics(BB);
776 PostDominatedByUnreachable.clear();
777 PostDominatedByColdCall.clear();
780 void BranchProbabilityInfoWrapperPass::getAnalysisUsage(
781 AnalysisUsage &AU) const {
782 AU.addRequired<LoopInfoWrapperPass>();
783 AU.addRequired<TargetLibraryInfoWrapperPass>();
784 AU.setPreservesAll();
787 bool BranchProbabilityInfoWrapperPass::runOnFunction(Function &F) {
788 const LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
789 const TargetLibraryInfo &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
790 BPI.calculate(F, LI, &TLI);
794 void BranchProbabilityInfoWrapperPass::releaseMemory() { BPI.releaseMemory(); }
796 void BranchProbabilityInfoWrapperPass::print(raw_ostream &OS,
797 const Module *) const {
801 AnalysisKey BranchProbabilityAnalysis::Key;
802 BranchProbabilityInfo
803 BranchProbabilityAnalysis::run(Function &F, FunctionAnalysisManager &AM) {
804 BranchProbabilityInfo BPI;
805 BPI.calculate(F, AM.getResult<LoopAnalysis>(F), &AM.getResult<TargetLibraryAnalysis>(F));
810 BranchProbabilityPrinterPass::run(Function &F, FunctionAnalysisManager &AM) {
811 OS << "Printing analysis results of BPI for function "
812 << "'" << F.getName() << "':"
814 AM.getResult<BranchProbabilityAnalysis>(F).print(OS);
815 return PreservedAnalyses::all();