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