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