[ARM] More MVE compare vector splat combines for ANDs
[llvm-complete.git] / lib / Analysis / BranchProbabilityInfo.cpp
blob5eb95003f5d8c79a94745635dc942efca5921e76
1 //===- BranchProbabilityInfo.cpp - Branch Probability Analysis ------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // Loops should be simplified before this analysis.
11 //===----------------------------------------------------------------------===//
13 #include "llvm/Analysis/BranchProbabilityInfo.h"
14 #include "llvm/ADT/PostOrderIterator.h"
15 #include "llvm/ADT/SCCIterator.h"
16 #include "llvm/ADT/STLExtras.h"
17 #include "llvm/ADT/SmallVector.h"
18 #include "llvm/Analysis/LoopInfo.h"
19 #include "llvm/Analysis/TargetLibraryInfo.h"
20 #include "llvm/IR/Attributes.h"
21 #include "llvm/IR/BasicBlock.h"
22 #include "llvm/IR/CFG.h"
23 #include "llvm/IR/Constants.h"
24 #include "llvm/IR/Dominators.h"
25 #include "llvm/IR/Function.h"
26 #include "llvm/IR/InstrTypes.h"
27 #include "llvm/IR/Instruction.h"
28 #include "llvm/IR/Instructions.h"
29 #include "llvm/IR/LLVMContext.h"
30 #include "llvm/IR/Metadata.h"
31 #include "llvm/IR/PassManager.h"
32 #include "llvm/IR/Type.h"
33 #include "llvm/IR/Value.h"
34 #include "llvm/Pass.h"
35 #include "llvm/Support/BranchProbability.h"
36 #include "llvm/Support/Casting.h"
37 #include "llvm/Support/Debug.h"
38 #include "llvm/Support/raw_ostream.h"
39 #include <cassert>
40 #include <cstdint>
41 #include <iterator>
42 #include <utility>
44 using namespace llvm;
46 #define DEBUG_TYPE "branch-prob"
48 static cl::opt<bool> PrintBranchProb(
49 "print-bpi", cl::init(false), cl::Hidden,
50 cl::desc("Print the branch probability info."));
52 cl::opt<std::string> PrintBranchProbFuncName(
53 "print-bpi-func-name", cl::Hidden,
54 cl::desc("The option to specify the name of the function "
55 "whose branch probability info is printed."));
57 INITIALIZE_PASS_BEGIN(BranchProbabilityInfoWrapperPass, "branch-prob",
58 "Branch Probability Analysis", false, true)
59 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
60 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
61 INITIALIZE_PASS_END(BranchProbabilityInfoWrapperPass, "branch-prob",
62 "Branch Probability Analysis", false, true)
64 char BranchProbabilityInfoWrapperPass::ID = 0;
66 // Weights are for internal use only. They are used by heuristics to help to
67 // estimate edges' probability. Example:
69 // Using "Loop Branch Heuristics" we predict weights of edges for the
70 // block BB2.
71 // ...
72 // |
73 // V
74 // BB1<-+
75 // | |
76 // | | (Weight = 124)
77 // V |
78 // BB2--+
79 // |
80 // | (Weight = 4)
81 // V
82 // BB3
84 // Probability of the edge BB2->BB1 = 124 / (124 + 4) = 0.96875
85 // Probability of the edge BB2->BB3 = 4 / (124 + 4) = 0.03125
86 static const uint32_t LBH_TAKEN_WEIGHT = 124;
87 static const uint32_t LBH_NONTAKEN_WEIGHT = 4;
88 // Unlikely edges within a loop are half as likely as other edges
89 static const uint32_t LBH_UNLIKELY_WEIGHT = 62;
91 /// Unreachable-terminating branch taken probability.
92 ///
93 /// This is the probability for a branch being taken to a block that terminates
94 /// (eventually) in unreachable. These are predicted as unlikely as possible.
95 /// All reachable probability will equally share the remaining part.
96 static const BranchProbability UR_TAKEN_PROB = BranchProbability::getRaw(1);
98 /// Weight for a branch taken going into a cold block.
99 ///
100 /// This is the weight for a branch taken toward a block marked
101 /// cold. A block is marked cold if it's postdominated by a
102 /// block containing a call to a cold function. Cold functions
103 /// are those marked with attribute 'cold'.
104 static const uint32_t CC_TAKEN_WEIGHT = 4;
106 /// Weight for a branch not-taken into a cold block.
108 /// This is the weight for a branch not taken toward a block marked
109 /// cold.
110 static const uint32_t CC_NONTAKEN_WEIGHT = 64;
112 static const uint32_t PH_TAKEN_WEIGHT = 20;
113 static const uint32_t PH_NONTAKEN_WEIGHT = 12;
115 static const uint32_t ZH_TAKEN_WEIGHT = 20;
116 static const uint32_t ZH_NONTAKEN_WEIGHT = 12;
118 static const uint32_t FPH_TAKEN_WEIGHT = 20;
119 static const uint32_t FPH_NONTAKEN_WEIGHT = 12;
121 /// Invoke-terminating normal branch taken weight
123 /// This is the weight for branching to the normal destination of an invoke
124 /// instruction. We expect this to happen most of the time. Set the weight to an
125 /// absurdly high value so that nested loops subsume it.
126 static const uint32_t IH_TAKEN_WEIGHT = 1024 * 1024 - 1;
128 /// Invoke-terminating normal branch not-taken weight.
130 /// This is the weight for branching to the unwind destination of an invoke
131 /// instruction. This is essentially never taken.
132 static const uint32_t IH_NONTAKEN_WEIGHT = 1;
134 /// Add \p BB to PostDominatedByUnreachable set if applicable.
135 void
136 BranchProbabilityInfo::updatePostDominatedByUnreachable(const BasicBlock *BB) {
137 const Instruction *TI = BB->getTerminator();
138 if (TI->getNumSuccessors() == 0) {
139 if (isa<UnreachableInst>(TI) ||
140 // If this block is terminated by a call to
141 // @llvm.experimental.deoptimize then treat it like an unreachable since
142 // the @llvm.experimental.deoptimize call is expected to practically
143 // never execute.
144 BB->getTerminatingDeoptimizeCall())
145 PostDominatedByUnreachable.insert(BB);
146 return;
149 // If the terminator is an InvokeInst, check only the normal destination block
150 // as the unwind edge of InvokeInst is also very unlikely taken.
151 if (auto *II = dyn_cast<InvokeInst>(TI)) {
152 if (PostDominatedByUnreachable.count(II->getNormalDest()))
153 PostDominatedByUnreachable.insert(BB);
154 return;
157 for (auto *I : successors(BB))
158 // If any of successor is not post dominated then BB is also not.
159 if (!PostDominatedByUnreachable.count(I))
160 return;
162 PostDominatedByUnreachable.insert(BB);
165 /// Add \p BB to PostDominatedByColdCall set if applicable.
166 void
167 BranchProbabilityInfo::updatePostDominatedByColdCall(const BasicBlock *BB) {
168 assert(!PostDominatedByColdCall.count(BB));
169 const Instruction *TI = BB->getTerminator();
170 if (TI->getNumSuccessors() == 0)
171 return;
173 // If all of successor are post dominated then BB is also done.
174 if (llvm::all_of(successors(BB), [&](const BasicBlock *SuccBB) {
175 return PostDominatedByColdCall.count(SuccBB);
176 })) {
177 PostDominatedByColdCall.insert(BB);
178 return;
181 // If the terminator is an InvokeInst, check only the normal destination
182 // block as the unwind edge of InvokeInst is also very unlikely taken.
183 if (auto *II = dyn_cast<InvokeInst>(TI))
184 if (PostDominatedByColdCall.count(II->getNormalDest())) {
185 PostDominatedByColdCall.insert(BB);
186 return;
189 // Otherwise, if the block itself contains a cold function, add it to the
190 // set of blocks post-dominated by a cold call.
191 for (auto &I : *BB)
192 if (const CallInst *CI = dyn_cast<CallInst>(&I))
193 if (CI->hasFnAttr(Attribute::Cold)) {
194 PostDominatedByColdCall.insert(BB);
195 return;
199 /// Calculate edge weights for successors lead to unreachable.
201 /// Predict that a successor which leads necessarily to an
202 /// unreachable-terminated block as extremely unlikely.
203 bool BranchProbabilityInfo::calcUnreachableHeuristics(const BasicBlock *BB) {
204 const Instruction *TI = BB->getTerminator();
205 (void) TI;
206 assert(TI->getNumSuccessors() > 1 && "expected more than one successor!");
207 assert(!isa<InvokeInst>(TI) &&
208 "Invokes should have already been handled by calcInvokeHeuristics");
210 SmallVector<unsigned, 4> UnreachableEdges;
211 SmallVector<unsigned, 4> ReachableEdges;
213 for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I)
214 if (PostDominatedByUnreachable.count(*I))
215 UnreachableEdges.push_back(I.getSuccessorIndex());
216 else
217 ReachableEdges.push_back(I.getSuccessorIndex());
219 // Skip probabilities if all were reachable.
220 if (UnreachableEdges.empty())
221 return false;
223 if (ReachableEdges.empty()) {
224 BranchProbability Prob(1, UnreachableEdges.size());
225 for (unsigned SuccIdx : UnreachableEdges)
226 setEdgeProbability(BB, SuccIdx, Prob);
227 return true;
230 auto UnreachableProb = UR_TAKEN_PROB;
231 auto ReachableProb =
232 (BranchProbability::getOne() - UR_TAKEN_PROB * UnreachableEdges.size()) /
233 ReachableEdges.size();
235 for (unsigned SuccIdx : UnreachableEdges)
236 setEdgeProbability(BB, SuccIdx, UnreachableProb);
237 for (unsigned SuccIdx : ReachableEdges)
238 setEdgeProbability(BB, SuccIdx, ReachableProb);
240 return true;
243 // Propagate existing explicit probabilities from either profile data or
244 // 'expect' intrinsic processing. Examine metadata against unreachable
245 // heuristic. The probability of the edge coming to unreachable block is
246 // set to min of metadata and unreachable heuristic.
247 bool BranchProbabilityInfo::calcMetadataWeights(const BasicBlock *BB) {
248 const Instruction *TI = BB->getTerminator();
249 assert(TI->getNumSuccessors() > 1 && "expected more than one successor!");
250 if (!(isa<BranchInst>(TI) || isa<SwitchInst>(TI) || isa<IndirectBrInst>(TI)))
251 return false;
253 MDNode *WeightsNode = TI->getMetadata(LLVMContext::MD_prof);
254 if (!WeightsNode)
255 return false;
257 // Check that the number of successors is manageable.
258 assert(TI->getNumSuccessors() < UINT32_MAX && "Too many successors");
260 // Ensure there are weights for all of the successors. Note that the first
261 // operand to the metadata node is a name, not a weight.
262 if (WeightsNode->getNumOperands() != TI->getNumSuccessors() + 1)
263 return false;
265 // Build up the final weights that will be used in a temporary buffer.
266 // Compute the sum of all weights to later decide whether they need to
267 // be scaled to fit in 32 bits.
268 uint64_t WeightSum = 0;
269 SmallVector<uint32_t, 2> Weights;
270 SmallVector<unsigned, 2> UnreachableIdxs;
271 SmallVector<unsigned, 2> ReachableIdxs;
272 Weights.reserve(TI->getNumSuccessors());
273 for (unsigned i = 1, e = WeightsNode->getNumOperands(); i != e; ++i) {
274 ConstantInt *Weight =
275 mdconst::dyn_extract<ConstantInt>(WeightsNode->getOperand(i));
276 if (!Weight)
277 return false;
278 assert(Weight->getValue().getActiveBits() <= 32 &&
279 "Too many bits for uint32_t");
280 Weights.push_back(Weight->getZExtValue());
281 WeightSum += Weights.back();
282 if (PostDominatedByUnreachable.count(TI->getSuccessor(i - 1)))
283 UnreachableIdxs.push_back(i - 1);
284 else
285 ReachableIdxs.push_back(i - 1);
287 assert(Weights.size() == TI->getNumSuccessors() && "Checked above");
289 // If the sum of weights does not fit in 32 bits, scale every weight down
290 // accordingly.
291 uint64_t ScalingFactor =
292 (WeightSum > UINT32_MAX) ? WeightSum / UINT32_MAX + 1 : 1;
294 if (ScalingFactor > 1) {
295 WeightSum = 0;
296 for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) {
297 Weights[i] /= ScalingFactor;
298 WeightSum += Weights[i];
301 assert(WeightSum <= UINT32_MAX &&
302 "Expected weights to scale down to 32 bits");
304 if (WeightSum == 0 || ReachableIdxs.size() == 0) {
305 for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
306 Weights[i] = 1;
307 WeightSum = TI->getNumSuccessors();
310 // Set the probability.
311 SmallVector<BranchProbability, 2> BP;
312 for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
313 BP.push_back({ Weights[i], static_cast<uint32_t>(WeightSum) });
315 // Examine the metadata against unreachable heuristic.
316 // If the unreachable heuristic is more strong then we use it for this edge.
317 if (UnreachableIdxs.size() > 0 && ReachableIdxs.size() > 0) {
318 auto ToDistribute = BranchProbability::getZero();
319 auto UnreachableProb = UR_TAKEN_PROB;
320 for (auto i : UnreachableIdxs)
321 if (UnreachableProb < BP[i]) {
322 ToDistribute += BP[i] - UnreachableProb;
323 BP[i] = UnreachableProb;
326 // If we modified the probability of some edges then we must distribute
327 // the difference between reachable blocks.
328 if (ToDistribute > BranchProbability::getZero()) {
329 BranchProbability PerEdge = ToDistribute / ReachableIdxs.size();
330 for (auto i : ReachableIdxs)
331 BP[i] += PerEdge;
335 for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
336 setEdgeProbability(BB, i, BP[i]);
338 return true;
341 /// Calculate edge weights for edges leading to cold blocks.
343 /// A cold block is one post-dominated by a block with a call to a
344 /// cold function. Those edges are unlikely to be taken, so we give
345 /// them relatively low weight.
347 /// Return true if we could compute the weights for cold edges.
348 /// Return false, otherwise.
349 bool BranchProbabilityInfo::calcColdCallHeuristics(const BasicBlock *BB) {
350 const Instruction *TI = BB->getTerminator();
351 (void) TI;
352 assert(TI->getNumSuccessors() > 1 && "expected more than one successor!");
353 assert(!isa<InvokeInst>(TI) &&
354 "Invokes should have already been handled by calcInvokeHeuristics");
356 // Determine which successors are post-dominated by a cold block.
357 SmallVector<unsigned, 4> ColdEdges;
358 SmallVector<unsigned, 4> NormalEdges;
359 for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I)
360 if (PostDominatedByColdCall.count(*I))
361 ColdEdges.push_back(I.getSuccessorIndex());
362 else
363 NormalEdges.push_back(I.getSuccessorIndex());
365 // Skip probabilities if no cold edges.
366 if (ColdEdges.empty())
367 return false;
369 if (NormalEdges.empty()) {
370 BranchProbability Prob(1, ColdEdges.size());
371 for (unsigned SuccIdx : ColdEdges)
372 setEdgeProbability(BB, SuccIdx, Prob);
373 return true;
376 auto ColdProb = BranchProbability::getBranchProbability(
377 CC_TAKEN_WEIGHT,
378 (CC_TAKEN_WEIGHT + CC_NONTAKEN_WEIGHT) * uint64_t(ColdEdges.size()));
379 auto NormalProb = BranchProbability::getBranchProbability(
380 CC_NONTAKEN_WEIGHT,
381 (CC_TAKEN_WEIGHT + CC_NONTAKEN_WEIGHT) * uint64_t(NormalEdges.size()));
383 for (unsigned SuccIdx : ColdEdges)
384 setEdgeProbability(BB, SuccIdx, ColdProb);
385 for (unsigned SuccIdx : NormalEdges)
386 setEdgeProbability(BB, SuccIdx, NormalProb);
388 return true;
391 // Calculate Edge Weights using "Pointer Heuristics". Predict a comparison
392 // between two pointer or pointer and NULL will fail.
393 bool BranchProbabilityInfo::calcPointerHeuristics(const BasicBlock *BB) {
394 const BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
395 if (!BI || !BI->isConditional())
396 return false;
398 Value *Cond = BI->getCondition();
399 ICmpInst *CI = dyn_cast<ICmpInst>(Cond);
400 if (!CI || !CI->isEquality())
401 return false;
403 Value *LHS = CI->getOperand(0);
405 if (!LHS->getType()->isPointerTy())
406 return false;
408 assert(CI->getOperand(1)->getType()->isPointerTy());
410 // p != 0 -> isProb = true
411 // p == 0 -> isProb = false
412 // p != q -> isProb = true
413 // p == q -> isProb = false;
414 unsigned TakenIdx = 0, NonTakenIdx = 1;
415 bool isProb = CI->getPredicate() == ICmpInst::ICMP_NE;
416 if (!isProb)
417 std::swap(TakenIdx, NonTakenIdx);
419 BranchProbability TakenProb(PH_TAKEN_WEIGHT,
420 PH_TAKEN_WEIGHT + PH_NONTAKEN_WEIGHT);
421 setEdgeProbability(BB, TakenIdx, TakenProb);
422 setEdgeProbability(BB, NonTakenIdx, TakenProb.getCompl());
423 return true;
426 static int getSCCNum(const BasicBlock *BB,
427 const BranchProbabilityInfo::SccInfo &SccI) {
428 auto SccIt = SccI.SccNums.find(BB);
429 if (SccIt == SccI.SccNums.end())
430 return -1;
431 return SccIt->second;
434 // Consider any block that is an entry point to the SCC as a header.
435 static bool isSCCHeader(const BasicBlock *BB, int SccNum,
436 BranchProbabilityInfo::SccInfo &SccI) {
437 assert(getSCCNum(BB, SccI) == SccNum);
439 // Lazily compute the set of headers for a given SCC and cache the results
440 // in the SccHeaderMap.
441 if (SccI.SccHeaders.size() <= static_cast<unsigned>(SccNum))
442 SccI.SccHeaders.resize(SccNum + 1);
443 auto &HeaderMap = SccI.SccHeaders[SccNum];
444 bool Inserted;
445 BranchProbabilityInfo::SccHeaderMap::iterator HeaderMapIt;
446 std::tie(HeaderMapIt, Inserted) = HeaderMap.insert(std::make_pair(BB, false));
447 if (Inserted) {
448 bool IsHeader = llvm::any_of(make_range(pred_begin(BB), pred_end(BB)),
449 [&](const BasicBlock *Pred) {
450 return getSCCNum(Pred, SccI) != SccNum;
452 HeaderMapIt->second = IsHeader;
453 return IsHeader;
454 } else
455 return HeaderMapIt->second;
458 // Compute the unlikely successors to the block BB in the loop L, specifically
459 // those that are unlikely because this is a loop, and add them to the
460 // UnlikelyBlocks set.
461 static void
462 computeUnlikelySuccessors(const BasicBlock *BB, Loop *L,
463 SmallPtrSetImpl<const BasicBlock*> &UnlikelyBlocks) {
464 // Sometimes in a loop we have a branch whose condition is made false by
465 // taking it. This is typically something like
466 // int n = 0;
467 // while (...) {
468 // if (++n >= MAX) {
469 // n = 0;
470 // }
471 // }
472 // In this sort of situation taking the branch means that at the very least it
473 // won't be taken again in the next iteration of the loop, so we should
474 // consider it less likely than a typical branch.
476 // We detect this by looking back through the graph of PHI nodes that sets the
477 // value that the condition depends on, and seeing if we can reach a successor
478 // block which can be determined to make the condition false.
480 // FIXME: We currently consider unlikely blocks to be half as likely as other
481 // blocks, but if we consider the example above the likelyhood is actually
482 // 1/MAX. We could therefore be more precise in how unlikely we consider
483 // blocks to be, but it would require more careful examination of the form
484 // of the comparison expression.
485 const BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
486 if (!BI || !BI->isConditional())
487 return;
489 // Check if the branch is based on an instruction compared with a constant
490 CmpInst *CI = dyn_cast<CmpInst>(BI->getCondition());
491 if (!CI || !isa<Instruction>(CI->getOperand(0)) ||
492 !isa<Constant>(CI->getOperand(1)))
493 return;
495 // Either the instruction must be a PHI, or a chain of operations involving
496 // constants that ends in a PHI which we can then collapse into a single value
497 // if the PHI value is known.
498 Instruction *CmpLHS = dyn_cast<Instruction>(CI->getOperand(0));
499 PHINode *CmpPHI = dyn_cast<PHINode>(CmpLHS);
500 Constant *CmpConst = dyn_cast<Constant>(CI->getOperand(1));
501 // Collect the instructions until we hit a PHI
502 SmallVector<BinaryOperator *, 1> InstChain;
503 while (!CmpPHI && CmpLHS && isa<BinaryOperator>(CmpLHS) &&
504 isa<Constant>(CmpLHS->getOperand(1))) {
505 // Stop if the chain extends outside of the loop
506 if (!L->contains(CmpLHS))
507 return;
508 InstChain.push_back(cast<BinaryOperator>(CmpLHS));
509 CmpLHS = dyn_cast<Instruction>(CmpLHS->getOperand(0));
510 if (CmpLHS)
511 CmpPHI = dyn_cast<PHINode>(CmpLHS);
513 if (!CmpPHI || !L->contains(CmpPHI))
514 return;
516 // Trace the phi node to find all values that come from successors of BB
517 SmallPtrSet<PHINode*, 8> VisitedInsts;
518 SmallVector<PHINode*, 8> WorkList;
519 WorkList.push_back(CmpPHI);
520 VisitedInsts.insert(CmpPHI);
521 while (!WorkList.empty()) {
522 PHINode *P = WorkList.back();
523 WorkList.pop_back();
524 for (BasicBlock *B : P->blocks()) {
525 // Skip blocks that aren't part of the loop
526 if (!L->contains(B))
527 continue;
528 Value *V = P->getIncomingValueForBlock(B);
529 // If the source is a PHI add it to the work list if we haven't
530 // already visited it.
531 if (PHINode *PN = dyn_cast<PHINode>(V)) {
532 if (VisitedInsts.insert(PN).second)
533 WorkList.push_back(PN);
534 continue;
536 // If this incoming value is a constant and B is a successor of BB, then
537 // we can constant-evaluate the compare to see if it makes the branch be
538 // taken or not.
539 Constant *CmpLHSConst = dyn_cast<Constant>(V);
540 if (!CmpLHSConst ||
541 std::find(succ_begin(BB), succ_end(BB), B) == succ_end(BB))
542 continue;
543 // First collapse InstChain
544 for (Instruction *I : llvm::reverse(InstChain)) {
545 CmpLHSConst = ConstantExpr::get(I->getOpcode(), CmpLHSConst,
546 cast<Constant>(I->getOperand(1)), true);
547 if (!CmpLHSConst)
548 break;
550 if (!CmpLHSConst)
551 continue;
552 // Now constant-evaluate the compare
553 Constant *Result = ConstantExpr::getCompare(CI->getPredicate(),
554 CmpLHSConst, CmpConst, true);
555 // If the result means we don't branch to the block then that block is
556 // unlikely.
557 if (Result &&
558 ((Result->isZeroValue() && B == BI->getSuccessor(0)) ||
559 (Result->isOneValue() && B == BI->getSuccessor(1))))
560 UnlikelyBlocks.insert(B);
565 // Calculate Edge Weights using "Loop Branch Heuristics". Predict backedges
566 // as taken, exiting edges as not-taken.
567 bool BranchProbabilityInfo::calcLoopBranchHeuristics(const BasicBlock *BB,
568 const LoopInfo &LI,
569 SccInfo &SccI) {
570 int SccNum;
571 Loop *L = LI.getLoopFor(BB);
572 if (!L) {
573 SccNum = getSCCNum(BB, SccI);
574 if (SccNum < 0)
575 return false;
578 SmallPtrSet<const BasicBlock*, 8> UnlikelyBlocks;
579 if (L)
580 computeUnlikelySuccessors(BB, L, UnlikelyBlocks);
582 SmallVector<unsigned, 8> BackEdges;
583 SmallVector<unsigned, 8> ExitingEdges;
584 SmallVector<unsigned, 8> InEdges; // Edges from header to the loop.
585 SmallVector<unsigned, 8> UnlikelyEdges;
587 for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
588 // Use LoopInfo if we have it, otherwise fall-back to SCC info to catch
589 // irreducible loops.
590 if (L) {
591 if (UnlikelyBlocks.count(*I) != 0)
592 UnlikelyEdges.push_back(I.getSuccessorIndex());
593 else if (!L->contains(*I))
594 ExitingEdges.push_back(I.getSuccessorIndex());
595 else if (L->getHeader() == *I)
596 BackEdges.push_back(I.getSuccessorIndex());
597 else
598 InEdges.push_back(I.getSuccessorIndex());
599 } else {
600 if (getSCCNum(*I, SccI) != SccNum)
601 ExitingEdges.push_back(I.getSuccessorIndex());
602 else if (isSCCHeader(*I, SccNum, SccI))
603 BackEdges.push_back(I.getSuccessorIndex());
604 else
605 InEdges.push_back(I.getSuccessorIndex());
609 if (BackEdges.empty() && ExitingEdges.empty() && UnlikelyEdges.empty())
610 return false;
612 // Collect the sum of probabilities of back-edges/in-edges/exiting-edges, and
613 // normalize them so that they sum up to one.
614 unsigned Denom = (BackEdges.empty() ? 0 : LBH_TAKEN_WEIGHT) +
615 (InEdges.empty() ? 0 : LBH_TAKEN_WEIGHT) +
616 (UnlikelyEdges.empty() ? 0 : LBH_UNLIKELY_WEIGHT) +
617 (ExitingEdges.empty() ? 0 : LBH_NONTAKEN_WEIGHT);
619 if (uint32_t numBackEdges = BackEdges.size()) {
620 BranchProbability TakenProb = BranchProbability(LBH_TAKEN_WEIGHT, Denom);
621 auto Prob = TakenProb / numBackEdges;
622 for (unsigned SuccIdx : BackEdges)
623 setEdgeProbability(BB, SuccIdx, Prob);
626 if (uint32_t numInEdges = InEdges.size()) {
627 BranchProbability TakenProb = BranchProbability(LBH_TAKEN_WEIGHT, Denom);
628 auto Prob = TakenProb / numInEdges;
629 for (unsigned SuccIdx : InEdges)
630 setEdgeProbability(BB, SuccIdx, Prob);
633 if (uint32_t numExitingEdges = ExitingEdges.size()) {
634 BranchProbability NotTakenProb = BranchProbability(LBH_NONTAKEN_WEIGHT,
635 Denom);
636 auto Prob = NotTakenProb / numExitingEdges;
637 for (unsigned SuccIdx : ExitingEdges)
638 setEdgeProbability(BB, SuccIdx, Prob);
641 if (uint32_t numUnlikelyEdges = UnlikelyEdges.size()) {
642 BranchProbability UnlikelyProb = BranchProbability(LBH_UNLIKELY_WEIGHT,
643 Denom);
644 auto Prob = UnlikelyProb / numUnlikelyEdges;
645 for (unsigned SuccIdx : UnlikelyEdges)
646 setEdgeProbability(BB, SuccIdx, Prob);
649 return true;
652 bool BranchProbabilityInfo::calcZeroHeuristics(const BasicBlock *BB,
653 const TargetLibraryInfo *TLI) {
654 const BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
655 if (!BI || !BI->isConditional())
656 return false;
658 Value *Cond = BI->getCondition();
659 ICmpInst *CI = dyn_cast<ICmpInst>(Cond);
660 if (!CI)
661 return false;
663 auto GetConstantInt = [](Value *V) {
664 if (auto *I = dyn_cast<BitCastInst>(V))
665 return dyn_cast<ConstantInt>(I->getOperand(0));
666 return dyn_cast<ConstantInt>(V);
669 Value *RHS = CI->getOperand(1);
670 ConstantInt *CV = GetConstantInt(RHS);
671 if (!CV)
672 return false;
674 // If the LHS is the result of AND'ing a value with a single bit bitmask,
675 // we don't have information about probabilities.
676 if (Instruction *LHS = dyn_cast<Instruction>(CI->getOperand(0)))
677 if (LHS->getOpcode() == Instruction::And)
678 if (ConstantInt *AndRHS = dyn_cast<ConstantInt>(LHS->getOperand(1)))
679 if (AndRHS->getValue().isPowerOf2())
680 return false;
682 // Check if the LHS is the return value of a library function
683 LibFunc Func = NumLibFuncs;
684 if (TLI)
685 if (CallInst *Call = dyn_cast<CallInst>(CI->getOperand(0)))
686 if (Function *CalledFn = Call->getCalledFunction())
687 TLI->getLibFunc(*CalledFn, Func);
689 bool isProb;
690 if (Func == LibFunc_strcasecmp ||
691 Func == LibFunc_strcmp ||
692 Func == LibFunc_strncasecmp ||
693 Func == LibFunc_strncmp ||
694 Func == LibFunc_memcmp) {
695 // strcmp and similar functions return zero, negative, or positive, if the
696 // first string is equal, less, or greater than the second. We consider it
697 // likely that the strings are not equal, so a comparison with zero is
698 // probably false, but also a comparison with any other number is also
699 // probably false given that what exactly is returned for nonzero values is
700 // not specified. Any kind of comparison other than equality we know
701 // nothing about.
702 switch (CI->getPredicate()) {
703 case CmpInst::ICMP_EQ:
704 isProb = false;
705 break;
706 case CmpInst::ICMP_NE:
707 isProb = true;
708 break;
709 default:
710 return false;
712 } else if (CV->isZero()) {
713 switch (CI->getPredicate()) {
714 case CmpInst::ICMP_EQ:
715 // X == 0 -> Unlikely
716 isProb = false;
717 break;
718 case CmpInst::ICMP_NE:
719 // X != 0 -> Likely
720 isProb = true;
721 break;
722 case CmpInst::ICMP_SLT:
723 // X < 0 -> Unlikely
724 isProb = false;
725 break;
726 case CmpInst::ICMP_SGT:
727 // X > 0 -> Likely
728 isProb = true;
729 break;
730 default:
731 return false;
733 } else if (CV->isOne() && CI->getPredicate() == CmpInst::ICMP_SLT) {
734 // InstCombine canonicalizes X <= 0 into X < 1.
735 // X <= 0 -> Unlikely
736 isProb = false;
737 } else if (CV->isMinusOne()) {
738 switch (CI->getPredicate()) {
739 case CmpInst::ICMP_EQ:
740 // X == -1 -> Unlikely
741 isProb = false;
742 break;
743 case CmpInst::ICMP_NE:
744 // X != -1 -> Likely
745 isProb = true;
746 break;
747 case CmpInst::ICMP_SGT:
748 // InstCombine canonicalizes X >= 0 into X > -1.
749 // X >= 0 -> Likely
750 isProb = true;
751 break;
752 default:
753 return false;
755 } else {
756 return false;
759 unsigned TakenIdx = 0, NonTakenIdx = 1;
761 if (!isProb)
762 std::swap(TakenIdx, NonTakenIdx);
764 BranchProbability TakenProb(ZH_TAKEN_WEIGHT,
765 ZH_TAKEN_WEIGHT + ZH_NONTAKEN_WEIGHT);
766 setEdgeProbability(BB, TakenIdx, TakenProb);
767 setEdgeProbability(BB, NonTakenIdx, TakenProb.getCompl());
768 return true;
771 bool BranchProbabilityInfo::calcFloatingPointHeuristics(const BasicBlock *BB) {
772 const BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
773 if (!BI || !BI->isConditional())
774 return false;
776 Value *Cond = BI->getCondition();
777 FCmpInst *FCmp = dyn_cast<FCmpInst>(Cond);
778 if (!FCmp)
779 return false;
781 bool isProb;
782 if (FCmp->isEquality()) {
783 // f1 == f2 -> Unlikely
784 // f1 != f2 -> Likely
785 isProb = !FCmp->isTrueWhenEqual();
786 } else if (FCmp->getPredicate() == FCmpInst::FCMP_ORD) {
787 // !isnan -> Likely
788 isProb = true;
789 } else if (FCmp->getPredicate() == FCmpInst::FCMP_UNO) {
790 // isnan -> Unlikely
791 isProb = false;
792 } else {
793 return false;
796 unsigned TakenIdx = 0, NonTakenIdx = 1;
798 if (!isProb)
799 std::swap(TakenIdx, NonTakenIdx);
801 BranchProbability TakenProb(FPH_TAKEN_WEIGHT,
802 FPH_TAKEN_WEIGHT + FPH_NONTAKEN_WEIGHT);
803 setEdgeProbability(BB, TakenIdx, TakenProb);
804 setEdgeProbability(BB, NonTakenIdx, TakenProb.getCompl());
805 return true;
808 bool BranchProbabilityInfo::calcInvokeHeuristics(const BasicBlock *BB) {
809 const InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator());
810 if (!II)
811 return false;
813 BranchProbability TakenProb(IH_TAKEN_WEIGHT,
814 IH_TAKEN_WEIGHT + IH_NONTAKEN_WEIGHT);
815 setEdgeProbability(BB, 0 /*Index for Normal*/, TakenProb);
816 setEdgeProbability(BB, 1 /*Index for Unwind*/, TakenProb.getCompl());
817 return true;
820 void BranchProbabilityInfo::releaseMemory() {
821 Probs.clear();
824 void BranchProbabilityInfo::print(raw_ostream &OS) const {
825 OS << "---- Branch Probabilities ----\n";
826 // We print the probabilities from the last function the analysis ran over,
827 // or the function it is currently running over.
828 assert(LastF && "Cannot print prior to running over a function");
829 for (const auto &BI : *LastF) {
830 for (succ_const_iterator SI = succ_begin(&BI), SE = succ_end(&BI); SI != SE;
831 ++SI) {
832 printEdgeProbability(OS << " ", &BI, *SI);
837 bool BranchProbabilityInfo::
838 isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const {
839 // Hot probability is at least 4/5 = 80%
840 // FIXME: Compare against a static "hot" BranchProbability.
841 return getEdgeProbability(Src, Dst) > BranchProbability(4, 5);
844 const BasicBlock *
845 BranchProbabilityInfo::getHotSucc(const BasicBlock *BB) const {
846 auto MaxProb = BranchProbability::getZero();
847 const BasicBlock *MaxSucc = nullptr;
849 for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
850 const BasicBlock *Succ = *I;
851 auto Prob = getEdgeProbability(BB, Succ);
852 if (Prob > MaxProb) {
853 MaxProb = Prob;
854 MaxSucc = Succ;
858 // Hot probability is at least 4/5 = 80%
859 if (MaxProb > BranchProbability(4, 5))
860 return MaxSucc;
862 return nullptr;
865 /// Get the raw edge probability for the edge. If can't find it, return a
866 /// default probability 1/N where N is the number of successors. Here an edge is
867 /// specified using PredBlock and an
868 /// index to the successors.
869 BranchProbability
870 BranchProbabilityInfo::getEdgeProbability(const BasicBlock *Src,
871 unsigned IndexInSuccessors) const {
872 auto I = Probs.find(std::make_pair(Src, IndexInSuccessors));
874 if (I != Probs.end())
875 return I->second;
877 return {1, static_cast<uint32_t>(succ_size(Src))};
880 BranchProbability
881 BranchProbabilityInfo::getEdgeProbability(const BasicBlock *Src,
882 succ_const_iterator Dst) const {
883 return getEdgeProbability(Src, Dst.getSuccessorIndex());
886 /// Get the raw edge probability calculated for the block pair. This returns the
887 /// sum of all raw edge probabilities from Src to Dst.
888 BranchProbability
889 BranchProbabilityInfo::getEdgeProbability(const BasicBlock *Src,
890 const BasicBlock *Dst) const {
891 auto Prob = BranchProbability::getZero();
892 bool FoundProb = false;
893 for (succ_const_iterator I = succ_begin(Src), E = succ_end(Src); I != E; ++I)
894 if (*I == Dst) {
895 auto MapI = Probs.find(std::make_pair(Src, I.getSuccessorIndex()));
896 if (MapI != Probs.end()) {
897 FoundProb = true;
898 Prob += MapI->second;
901 uint32_t succ_num = std::distance(succ_begin(Src), succ_end(Src));
902 return FoundProb ? Prob : BranchProbability(1, succ_num);
905 /// Set the edge probability for a given edge specified by PredBlock and an
906 /// index to the successors.
907 void BranchProbabilityInfo::setEdgeProbability(const BasicBlock *Src,
908 unsigned IndexInSuccessors,
909 BranchProbability Prob) {
910 Probs[std::make_pair(Src, IndexInSuccessors)] = Prob;
911 Handles.insert(BasicBlockCallbackVH(Src, this));
912 LLVM_DEBUG(dbgs() << "set edge " << Src->getName() << " -> "
913 << IndexInSuccessors << " successor probability to " << Prob
914 << "\n");
917 raw_ostream &
918 BranchProbabilityInfo::printEdgeProbability(raw_ostream &OS,
919 const BasicBlock *Src,
920 const BasicBlock *Dst) const {
921 const BranchProbability Prob = getEdgeProbability(Src, Dst);
922 OS << "edge " << Src->getName() << " -> " << Dst->getName()
923 << " probability is " << Prob
924 << (isEdgeHot(Src, Dst) ? " [HOT edge]\n" : "\n");
926 return OS;
929 void BranchProbabilityInfo::eraseBlock(const BasicBlock *BB) {
930 for (auto I = Probs.begin(), E = Probs.end(); I != E; ++I) {
931 auto Key = I->first;
932 if (Key.first == BB)
933 Probs.erase(Key);
937 void BranchProbabilityInfo::calculate(const Function &F, const LoopInfo &LI,
938 const TargetLibraryInfo *TLI) {
939 LLVM_DEBUG(dbgs() << "---- Branch Probability Info : " << F.getName()
940 << " ----\n\n");
941 LastF = &F; // Store the last function we ran on for printing.
942 assert(PostDominatedByUnreachable.empty());
943 assert(PostDominatedByColdCall.empty());
945 // Record SCC numbers of blocks in the CFG to identify irreducible loops.
946 // FIXME: We could only calculate this if the CFG is known to be irreducible
947 // (perhaps cache this info in LoopInfo if we can easily calculate it there?).
948 int SccNum = 0;
949 SccInfo SccI;
950 for (scc_iterator<const Function *> It = scc_begin(&F); !It.isAtEnd();
951 ++It, ++SccNum) {
952 // Ignore single-block SCCs since they either aren't loops or LoopInfo will
953 // catch them.
954 const std::vector<const BasicBlock *> &Scc = *It;
955 if (Scc.size() == 1)
956 continue;
958 LLVM_DEBUG(dbgs() << "BPI: SCC " << SccNum << ":");
959 for (auto *BB : Scc) {
960 LLVM_DEBUG(dbgs() << " " << BB->getName());
961 SccI.SccNums[BB] = SccNum;
963 LLVM_DEBUG(dbgs() << "\n");
966 // Walk the basic blocks in post-order so that we can build up state about
967 // the successors of a block iteratively.
968 for (auto BB : post_order(&F.getEntryBlock())) {
969 LLVM_DEBUG(dbgs() << "Computing probabilities for " << BB->getName()
970 << "\n");
971 updatePostDominatedByUnreachable(BB);
972 updatePostDominatedByColdCall(BB);
973 // If there is no at least two successors, no sense to set probability.
974 if (BB->getTerminator()->getNumSuccessors() < 2)
975 continue;
976 if (calcMetadataWeights(BB))
977 continue;
978 if (calcInvokeHeuristics(BB))
979 continue;
980 if (calcUnreachableHeuristics(BB))
981 continue;
982 if (calcColdCallHeuristics(BB))
983 continue;
984 if (calcLoopBranchHeuristics(BB, LI, SccI))
985 continue;
986 if (calcPointerHeuristics(BB))
987 continue;
988 if (calcZeroHeuristics(BB, TLI))
989 continue;
990 if (calcFloatingPointHeuristics(BB))
991 continue;
994 PostDominatedByUnreachable.clear();
995 PostDominatedByColdCall.clear();
997 if (PrintBranchProb &&
998 (PrintBranchProbFuncName.empty() ||
999 F.getName().equals(PrintBranchProbFuncName))) {
1000 print(dbgs());
1004 void BranchProbabilityInfoWrapperPass::getAnalysisUsage(
1005 AnalysisUsage &AU) const {
1006 // We require DT so it's available when LI is available. The LI updating code
1007 // asserts that DT is also present so if we don't make sure that we have DT
1008 // here, that assert will trigger.
1009 AU.addRequired<DominatorTreeWrapperPass>();
1010 AU.addRequired<LoopInfoWrapperPass>();
1011 AU.addRequired<TargetLibraryInfoWrapperPass>();
1012 AU.setPreservesAll();
1015 bool BranchProbabilityInfoWrapperPass::runOnFunction(Function &F) {
1016 const LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
1017 const TargetLibraryInfo &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
1018 BPI.calculate(F, LI, &TLI);
1019 return false;
1022 void BranchProbabilityInfoWrapperPass::releaseMemory() { BPI.releaseMemory(); }
1024 void BranchProbabilityInfoWrapperPass::print(raw_ostream &OS,
1025 const Module *) const {
1026 BPI.print(OS);
1029 AnalysisKey BranchProbabilityAnalysis::Key;
1030 BranchProbabilityInfo
1031 BranchProbabilityAnalysis::run(Function &F, FunctionAnalysisManager &AM) {
1032 BranchProbabilityInfo BPI;
1033 BPI.calculate(F, AM.getResult<LoopAnalysis>(F), &AM.getResult<TargetLibraryAnalysis>(F));
1034 return BPI;
1037 PreservedAnalyses
1038 BranchProbabilityPrinterPass::run(Function &F, FunctionAnalysisManager &AM) {
1039 OS << "Printing analysis results of BPI for function "
1040 << "'" << F.getName() << "':"
1041 << "\n";
1042 AM.getResult<BranchProbabilityAnalysis>(F).print(OS);
1043 return PreservedAnalyses::all();