]> CyberLeo.Net >> Repos - FreeBSD/FreeBSD.git/blob - contrib/llvm/lib/Analysis/BranchProbabilityInfo.cpp
Merge libc++ trunk r300890, and update build glue.
[FreeBSD/FreeBSD.git] / contrib / llvm / lib / Analysis / BranchProbabilityInfo.cpp
1 //===-- 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/Analysis/LoopInfo.h"
17 #include "llvm/IR/CFG.h"
18 #include "llvm/IR/Constants.h"
19 #include "llvm/IR/Function.h"
20 #include "llvm/IR/Instructions.h"
21 #include "llvm/IR/LLVMContext.h"
22 #include "llvm/IR/Metadata.h"
23 #include "llvm/Support/Debug.h"
24 #include "llvm/Support/raw_ostream.h"
25
26 using namespace llvm;
27
28 #define DEBUG_TYPE "branch-prob"
29
30 INITIALIZE_PASS_BEGIN(BranchProbabilityInfoWrapperPass, "branch-prob",
31                       "Branch Probability Analysis", false, true)
32 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
33 INITIALIZE_PASS_END(BranchProbabilityInfoWrapperPass, "branch-prob",
34                     "Branch Probability Analysis", false, true)
35
36 char BranchProbabilityInfoWrapperPass::ID = 0;
37
38 // Weights are for internal use only. They are used by heuristics to help to
39 // estimate edges' probability. Example:
40 //
41 // Using "Loop Branch Heuristics" we predict weights of edges for the
42 // block BB2.
43 //         ...
44 //          |
45 //          V
46 //         BB1<-+
47 //          |   |
48 //          |   | (Weight = 124)
49 //          V   |
50 //         BB2--+
51 //          |
52 //          | (Weight = 4)
53 //          V
54 //         BB3
55 //
56 // Probability of the edge BB2->BB1 = 124 / (124 + 4) = 0.96875
57 // Probability of the edge BB2->BB3 = 4 / (124 + 4) = 0.03125
58 static const uint32_t LBH_TAKEN_WEIGHT = 124;
59 static const uint32_t LBH_NONTAKEN_WEIGHT = 4;
60
61 /// \brief Unreachable-terminating branch taken weight.
62 ///
63 /// This is the weight for a branch being taken to a block that terminates
64 /// (eventually) in unreachable. These are predicted as unlikely as possible.
65 static const uint32_t UR_TAKEN_WEIGHT = 1;
66
67 /// \brief Unreachable-terminating branch not-taken weight.
68 ///
69 /// This is the weight for a branch not being taken toward a block that
70 /// terminates (eventually) in unreachable. Such a branch is essentially never
71 /// taken. Set the weight to an absurdly high value so that nested loops don't
72 /// easily subsume it.
73 static const uint32_t UR_NONTAKEN_WEIGHT = 1024*1024 - 1;
74
75 /// \brief Returns the branch probability for unreachable edge according to
76 /// heuristic.
77 ///
78 /// This is the branch probability being taken to a block that terminates
79 /// (eventually) in unreachable. These are predicted as unlikely as possible.
80 static BranchProbability getUnreachableProbability(uint64_t UnreachableCount) {
81   assert(UnreachableCount > 0 && "UnreachableCount must be > 0");
82   return BranchProbability::getBranchProbability(
83       UR_TAKEN_WEIGHT,
84       (UR_TAKEN_WEIGHT + UR_NONTAKEN_WEIGHT) * UnreachableCount);
85 }
86
87 /// \brief Returns the branch probability for reachable edge according to
88 /// heuristic.
89 ///
90 /// This is the branch probability not being taken toward a block that
91 /// terminates (eventually) in unreachable. Such a branch is essentially never
92 /// taken. Set the weight to an absurdly high value so that nested loops don't
93 /// easily subsume it.
94 static BranchProbability getReachableProbability(uint64_t ReachableCount) {
95   assert(ReachableCount > 0 && "ReachableCount must be > 0");
96   return BranchProbability::getBranchProbability(
97       UR_NONTAKEN_WEIGHT,
98       (UR_TAKEN_WEIGHT + UR_NONTAKEN_WEIGHT) * ReachableCount);
99 }
100
101 /// \brief Weight for a branch taken going into a cold block.
102 ///
103 /// This is the weight for a branch taken toward a block marked
104 /// cold.  A block is marked cold if it's postdominated by a
105 /// block containing a call to a cold function.  Cold functions
106 /// are those marked with attribute 'cold'.
107 static const uint32_t CC_TAKEN_WEIGHT = 4;
108
109 /// \brief Weight for a branch not-taken into a cold block.
110 ///
111 /// This is the weight for a branch not taken toward a block marked
112 /// cold.
113 static const uint32_t CC_NONTAKEN_WEIGHT = 64;
114
115 static const uint32_t PH_TAKEN_WEIGHT = 20;
116 static const uint32_t PH_NONTAKEN_WEIGHT = 12;
117
118 static const uint32_t ZH_TAKEN_WEIGHT = 20;
119 static const uint32_t ZH_NONTAKEN_WEIGHT = 12;
120
121 static const uint32_t FPH_TAKEN_WEIGHT = 20;
122 static const uint32_t FPH_NONTAKEN_WEIGHT = 12;
123
124 /// \brief Invoke-terminating normal branch taken weight
125 ///
126 /// This is the weight for branching to the normal destination of an invoke
127 /// instruction. We expect this to happen most of the time. Set the weight to an
128 /// absurdly high value so that nested loops subsume it.
129 static const uint32_t IH_TAKEN_WEIGHT = 1024 * 1024 - 1;
130
131 /// \brief Invoke-terminating normal branch not-taken weight.
132 ///
133 /// This is the weight for branching to the unwind destination of an invoke
134 /// instruction. This is essentially never taken.
135 static const uint32_t IH_NONTAKEN_WEIGHT = 1;
136
137 /// \brief Add \p BB to PostDominatedByUnreachable set if applicable.
138 void
139 BranchProbabilityInfo::updatePostDominatedByUnreachable(const BasicBlock *BB) {
140   const TerminatorInst *TI = BB->getTerminator();
141   if (TI->getNumSuccessors() == 0) {
142     if (isa<UnreachableInst>(TI) ||
143         // If this block is terminated by a call to
144         // @llvm.experimental.deoptimize then treat it like an unreachable since
145         // the @llvm.experimental.deoptimize call is expected to practically
146         // never execute.
147         BB->getTerminatingDeoptimizeCall())
148       PostDominatedByUnreachable.insert(BB);
149     return;
150   }
151
152   // If the terminator is an InvokeInst, check only the normal destination block
153   // as the unwind edge of InvokeInst is also very unlikely taken.
154   if (auto *II = dyn_cast<InvokeInst>(TI)) {
155     if (PostDominatedByUnreachable.count(II->getNormalDest()))
156       PostDominatedByUnreachable.insert(BB);
157     return;
158   }
159
160   for (auto *I : successors(BB))
161     // If any of successor is not post dominated then BB is also not.
162     if (!PostDominatedByUnreachable.count(I))
163       return;
164
165   PostDominatedByUnreachable.insert(BB);
166 }
167
168 /// \brief Add \p BB to PostDominatedByColdCall set if applicable.
169 void
170 BranchProbabilityInfo::updatePostDominatedByColdCall(const BasicBlock *BB) {
171   assert(!PostDominatedByColdCall.count(BB));
172   const TerminatorInst *TI = BB->getTerminator();
173   if (TI->getNumSuccessors() == 0)
174     return;
175
176   // If all of successor are post dominated then BB is also done.
177   if (llvm::all_of(successors(BB), [&](const BasicBlock *SuccBB) {
178         return PostDominatedByColdCall.count(SuccBB);
179       })) {
180     PostDominatedByColdCall.insert(BB);
181     return;
182   }
183
184   // If the terminator is an InvokeInst, check only the normal destination
185   // block as the unwind edge of InvokeInst is also very unlikely taken.
186   if (auto *II = dyn_cast<InvokeInst>(TI))
187     if (PostDominatedByColdCall.count(II->getNormalDest())) {
188       PostDominatedByColdCall.insert(BB);
189       return;
190     }
191
192   // Otherwise, if the block itself contains a cold function, add it to the
193   // set of blocks post-dominated by a cold call.
194   for (auto &I : *BB)
195     if (const CallInst *CI = dyn_cast<CallInst>(&I))
196       if (CI->hasFnAttr(Attribute::Cold)) {
197         PostDominatedByColdCall.insert(BB);
198         return;
199       }
200 }
201
202 /// \brief Calculate edge weights for successors lead to unreachable.
203 ///
204 /// Predict that a successor which leads necessarily to an
205 /// unreachable-terminated block as extremely unlikely.
206 bool BranchProbabilityInfo::calcUnreachableHeuristics(const BasicBlock *BB) {
207   const TerminatorInst *TI = BB->getTerminator();
208   assert(TI->getNumSuccessors() > 1 && "expected more than one successor!");
209
210   // Return false here so that edge weights for InvokeInst could be decided
211   // in calcInvokeHeuristics().
212   if (isa<InvokeInst>(TI))
213     return false;
214
215   SmallVector<unsigned, 4> UnreachableEdges;
216   SmallVector<unsigned, 4> ReachableEdges;
217
218   for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I)
219     if (PostDominatedByUnreachable.count(*I))
220       UnreachableEdges.push_back(I.getSuccessorIndex());
221     else
222       ReachableEdges.push_back(I.getSuccessorIndex());
223
224   // Skip probabilities if all were reachable.
225   if (UnreachableEdges.empty())
226     return false;
227
228   if (ReachableEdges.empty()) {
229     BranchProbability Prob(1, UnreachableEdges.size());
230     for (unsigned SuccIdx : UnreachableEdges)
231       setEdgeProbability(BB, SuccIdx, Prob);
232     return true;
233   }
234
235   auto UnreachableProb = getUnreachableProbability(UnreachableEdges.size());
236   auto ReachableProb = getReachableProbability(ReachableEdges.size());
237
238   for (unsigned SuccIdx : UnreachableEdges)
239     setEdgeProbability(BB, SuccIdx, UnreachableProb);
240   for (unsigned SuccIdx : ReachableEdges)
241     setEdgeProbability(BB, SuccIdx, ReachableProb);
242
243   return true;
244 }
245
246 // Propagate existing explicit probabilities from either profile data or
247 // 'expect' intrinsic processing. Examine metadata against unreachable
248 // heuristic. The probability of the edge coming to unreachable block is
249 // set to min of metadata and unreachable heuristic.
250 bool BranchProbabilityInfo::calcMetadataWeights(const BasicBlock *BB) {
251   const TerminatorInst *TI = BB->getTerminator();
252   assert(TI->getNumSuccessors() > 1 && "expected more than one successor!");
253   if (!isa<BranchInst>(TI) && !isa<SwitchInst>(TI))
254     return false;
255
256   MDNode *WeightsNode = TI->getMetadata(LLVMContext::MD_prof);
257   if (!WeightsNode)
258     return false;
259
260   // Check that the number of successors is manageable.
261   assert(TI->getNumSuccessors() < UINT32_MAX && "Too many successors");
262
263   // Ensure there are weights for all of the successors. Note that the first
264   // operand to the metadata node is a name, not a weight.
265   if (WeightsNode->getNumOperands() != TI->getNumSuccessors() + 1)
266     return false;
267
268   // Build up the final weights that will be used in a temporary buffer.
269   // Compute the sum of all weights to later decide whether they need to
270   // be scaled to fit in 32 bits.
271   uint64_t WeightSum = 0;
272   SmallVector<uint32_t, 2> Weights;
273   SmallVector<unsigned, 2> UnreachableIdxs;
274   SmallVector<unsigned, 2> ReachableIdxs;
275   Weights.reserve(TI->getNumSuccessors());
276   for (unsigned i = 1, e = WeightsNode->getNumOperands(); i != e; ++i) {
277     ConstantInt *Weight =
278         mdconst::dyn_extract<ConstantInt>(WeightsNode->getOperand(i));
279     if (!Weight)
280       return false;
281     assert(Weight->getValue().getActiveBits() <= 32 &&
282            "Too many bits for uint32_t");
283     Weights.push_back(Weight->getZExtValue());
284     WeightSum += Weights.back();
285     if (PostDominatedByUnreachable.count(TI->getSuccessor(i - 1)))
286       UnreachableIdxs.push_back(i - 1);
287     else
288       ReachableIdxs.push_back(i - 1);
289   }
290   assert(Weights.size() == TI->getNumSuccessors() && "Checked above");
291
292   // If the sum of weights does not fit in 32 bits, scale every weight down
293   // accordingly.
294   uint64_t ScalingFactor =
295       (WeightSum > UINT32_MAX) ? WeightSum / UINT32_MAX + 1 : 1;
296
297   if (ScalingFactor > 1) {
298     WeightSum = 0;
299     for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) {
300       Weights[i] /= ScalingFactor;
301       WeightSum += Weights[i];
302     }
303   }
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 = getUnreachableProbability(UnreachableIdxs.size());
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         ToDistribute -= PerEdge;
334       }
335       // Tail goes to the first reachable edge.
336       BP[ReachableIdxs[0]] += ToDistribute;
337     }
338   }
339
340   for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
341     setEdgeProbability(BB, i, BP[i]);
342
343   assert(WeightSum <= UINT32_MAX &&
344          "Expected weights to scale down to 32 bits");
345
346   return true;
347 }
348
349 /// \brief Calculate edge weights for edges leading to cold blocks.
350 ///
351 /// A cold block is one post-dominated by  a block with a call to a
352 /// cold function.  Those edges are unlikely to be taken, so we give
353 /// them relatively low weight.
354 ///
355 /// Return true if we could compute the weights for cold edges.
356 /// Return false, otherwise.
357 bool BranchProbabilityInfo::calcColdCallHeuristics(const BasicBlock *BB) {
358   const TerminatorInst *TI = BB->getTerminator();
359   assert(TI->getNumSuccessors() > 1 && "expected more than one successor!");
360
361   // Return false here so that edge weights for InvokeInst could be decided
362   // in calcInvokeHeuristics().
363   if (isa<InvokeInst>(TI))
364     return false;
365
366   // Determine which successors are post-dominated by a cold block.
367   SmallVector<unsigned, 4> ColdEdges;
368   SmallVector<unsigned, 4> NormalEdges;
369   for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I)
370     if (PostDominatedByColdCall.count(*I))
371       ColdEdges.push_back(I.getSuccessorIndex());
372     else
373       NormalEdges.push_back(I.getSuccessorIndex());
374
375   // Skip probabilities if no cold edges.
376   if (ColdEdges.empty())
377     return false;
378
379   if (NormalEdges.empty()) {
380     BranchProbability Prob(1, ColdEdges.size());
381     for (unsigned SuccIdx : ColdEdges)
382       setEdgeProbability(BB, SuccIdx, Prob);
383     return true;
384   }
385
386   auto ColdProb = BranchProbability::getBranchProbability(
387       CC_TAKEN_WEIGHT,
388       (CC_TAKEN_WEIGHT + CC_NONTAKEN_WEIGHT) * uint64_t(ColdEdges.size()));
389   auto NormalProb = BranchProbability::getBranchProbability(
390       CC_NONTAKEN_WEIGHT,
391       (CC_TAKEN_WEIGHT + CC_NONTAKEN_WEIGHT) * uint64_t(NormalEdges.size()));
392
393   for (unsigned SuccIdx : ColdEdges)
394     setEdgeProbability(BB, SuccIdx, ColdProb);
395   for (unsigned SuccIdx : NormalEdges)
396     setEdgeProbability(BB, SuccIdx, NormalProb);
397
398   return true;
399 }
400
401 // Calculate Edge Weights using "Pointer Heuristics". Predict a comparsion
402 // between two pointer or pointer and NULL will fail.
403 bool BranchProbabilityInfo::calcPointerHeuristics(const BasicBlock *BB) {
404   const BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
405   if (!BI || !BI->isConditional())
406     return false;
407
408   Value *Cond = BI->getCondition();
409   ICmpInst *CI = dyn_cast<ICmpInst>(Cond);
410   if (!CI || !CI->isEquality())
411     return false;
412
413   Value *LHS = CI->getOperand(0);
414
415   if (!LHS->getType()->isPointerTy())
416     return false;
417
418   assert(CI->getOperand(1)->getType()->isPointerTy());
419
420   // p != 0   ->   isProb = true
421   // p == 0   ->   isProb = false
422   // p != q   ->   isProb = true
423   // p == q   ->   isProb = false;
424   unsigned TakenIdx = 0, NonTakenIdx = 1;
425   bool isProb = CI->getPredicate() == ICmpInst::ICMP_NE;
426   if (!isProb)
427     std::swap(TakenIdx, NonTakenIdx);
428
429   BranchProbability TakenProb(PH_TAKEN_WEIGHT,
430                               PH_TAKEN_WEIGHT + PH_NONTAKEN_WEIGHT);
431   setEdgeProbability(BB, TakenIdx, TakenProb);
432   setEdgeProbability(BB, NonTakenIdx, TakenProb.getCompl());
433   return true;
434 }
435
436 // Calculate Edge Weights using "Loop Branch Heuristics". Predict backedges
437 // as taken, exiting edges as not-taken.
438 bool BranchProbabilityInfo::calcLoopBranchHeuristics(const BasicBlock *BB,
439                                                      const LoopInfo &LI) {
440   Loop *L = LI.getLoopFor(BB);
441   if (!L)
442     return false;
443
444   SmallVector<unsigned, 8> BackEdges;
445   SmallVector<unsigned, 8> ExitingEdges;
446   SmallVector<unsigned, 8> InEdges; // Edges from header to the loop.
447
448   for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
449     if (!L->contains(*I))
450       ExitingEdges.push_back(I.getSuccessorIndex());
451     else if (L->getHeader() == *I)
452       BackEdges.push_back(I.getSuccessorIndex());
453     else
454       InEdges.push_back(I.getSuccessorIndex());
455   }
456
457   if (BackEdges.empty() && ExitingEdges.empty())
458     return false;
459
460   // Collect the sum of probabilities of back-edges/in-edges/exiting-edges, and
461   // normalize them so that they sum up to one.
462   BranchProbability Probs[] = {BranchProbability::getZero(),
463                                BranchProbability::getZero(),
464                                BranchProbability::getZero()};
465   unsigned Denom = (BackEdges.empty() ? 0 : LBH_TAKEN_WEIGHT) +
466                    (InEdges.empty() ? 0 : LBH_TAKEN_WEIGHT) +
467                    (ExitingEdges.empty() ? 0 : LBH_NONTAKEN_WEIGHT);
468   if (!BackEdges.empty())
469     Probs[0] = BranchProbability(LBH_TAKEN_WEIGHT, Denom);
470   if (!InEdges.empty())
471     Probs[1] = BranchProbability(LBH_TAKEN_WEIGHT, Denom);
472   if (!ExitingEdges.empty())
473     Probs[2] = BranchProbability(LBH_NONTAKEN_WEIGHT, Denom);
474
475   if (uint32_t numBackEdges = BackEdges.size()) {
476     auto Prob = Probs[0] / numBackEdges;
477     for (unsigned SuccIdx : BackEdges)
478       setEdgeProbability(BB, SuccIdx, Prob);
479   }
480
481   if (uint32_t numInEdges = InEdges.size()) {
482     auto Prob = Probs[1] / numInEdges;
483     for (unsigned SuccIdx : InEdges)
484       setEdgeProbability(BB, SuccIdx, Prob);
485   }
486
487   if (uint32_t numExitingEdges = ExitingEdges.size()) {
488     auto Prob = Probs[2] / numExitingEdges;
489     for (unsigned SuccIdx : ExitingEdges)
490       setEdgeProbability(BB, SuccIdx, Prob);
491   }
492
493   return true;
494 }
495
496 bool BranchProbabilityInfo::calcZeroHeuristics(const BasicBlock *BB) {
497   const BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
498   if (!BI || !BI->isConditional())
499     return false;
500
501   Value *Cond = BI->getCondition();
502   ICmpInst *CI = dyn_cast<ICmpInst>(Cond);
503   if (!CI)
504     return false;
505
506   Value *RHS = CI->getOperand(1);
507   ConstantInt *CV = dyn_cast<ConstantInt>(RHS);
508   if (!CV)
509     return false;
510
511   // If the LHS is the result of AND'ing a value with a single bit bitmask,
512   // we don't have information about probabilities.
513   if (Instruction *LHS = dyn_cast<Instruction>(CI->getOperand(0)))
514     if (LHS->getOpcode() == Instruction::And)
515       if (ConstantInt *AndRHS = dyn_cast<ConstantInt>(LHS->getOperand(1)))
516         if (AndRHS->getUniqueInteger().isPowerOf2())
517           return false;
518
519   bool isProb;
520   if (CV->isZero()) {
521     switch (CI->getPredicate()) {
522     case CmpInst::ICMP_EQ:
523       // X == 0   ->  Unlikely
524       isProb = false;
525       break;
526     case CmpInst::ICMP_NE:
527       // X != 0   ->  Likely
528       isProb = true;
529       break;
530     case CmpInst::ICMP_SLT:
531       // X < 0   ->  Unlikely
532       isProb = false;
533       break;
534     case CmpInst::ICMP_SGT:
535       // X > 0   ->  Likely
536       isProb = true;
537       break;
538     default:
539       return false;
540     }
541   } else if (CV->isOne() && CI->getPredicate() == CmpInst::ICMP_SLT) {
542     // InstCombine canonicalizes X <= 0 into X < 1.
543     // X <= 0   ->  Unlikely
544     isProb = false;
545   } else if (CV->isAllOnesValue()) {
546     switch (CI->getPredicate()) {
547     case CmpInst::ICMP_EQ:
548       // X == -1  ->  Unlikely
549       isProb = false;
550       break;
551     case CmpInst::ICMP_NE:
552       // X != -1  ->  Likely
553       isProb = true;
554       break;
555     case CmpInst::ICMP_SGT:
556       // InstCombine canonicalizes X >= 0 into X > -1.
557       // X >= 0   ->  Likely
558       isProb = true;
559       break;
560     default:
561       return false;
562     }
563   } else {
564     return false;
565   }
566
567   unsigned TakenIdx = 0, NonTakenIdx = 1;
568
569   if (!isProb)
570     std::swap(TakenIdx, NonTakenIdx);
571
572   BranchProbability TakenProb(ZH_TAKEN_WEIGHT,
573                               ZH_TAKEN_WEIGHT + ZH_NONTAKEN_WEIGHT);
574   setEdgeProbability(BB, TakenIdx, TakenProb);
575   setEdgeProbability(BB, NonTakenIdx, TakenProb.getCompl());
576   return true;
577 }
578
579 bool BranchProbabilityInfo::calcFloatingPointHeuristics(const BasicBlock *BB) {
580   const BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
581   if (!BI || !BI->isConditional())
582     return false;
583
584   Value *Cond = BI->getCondition();
585   FCmpInst *FCmp = dyn_cast<FCmpInst>(Cond);
586   if (!FCmp)
587     return false;
588
589   bool isProb;
590   if (FCmp->isEquality()) {
591     // f1 == f2 -> Unlikely
592     // f1 != f2 -> Likely
593     isProb = !FCmp->isTrueWhenEqual();
594   } else if (FCmp->getPredicate() == FCmpInst::FCMP_ORD) {
595     // !isnan -> Likely
596     isProb = true;
597   } else if (FCmp->getPredicate() == FCmpInst::FCMP_UNO) {
598     // isnan -> Unlikely
599     isProb = false;
600   } else {
601     return false;
602   }
603
604   unsigned TakenIdx = 0, NonTakenIdx = 1;
605
606   if (!isProb)
607     std::swap(TakenIdx, NonTakenIdx);
608
609   BranchProbability TakenProb(FPH_TAKEN_WEIGHT,
610                               FPH_TAKEN_WEIGHT + FPH_NONTAKEN_WEIGHT);
611   setEdgeProbability(BB, TakenIdx, TakenProb);
612   setEdgeProbability(BB, NonTakenIdx, TakenProb.getCompl());
613   return true;
614 }
615
616 bool BranchProbabilityInfo::calcInvokeHeuristics(const BasicBlock *BB) {
617   const InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator());
618   if (!II)
619     return false;
620
621   BranchProbability TakenProb(IH_TAKEN_WEIGHT,
622                               IH_TAKEN_WEIGHT + IH_NONTAKEN_WEIGHT);
623   setEdgeProbability(BB, 0 /*Index for Normal*/, TakenProb);
624   setEdgeProbability(BB, 1 /*Index for Unwind*/, TakenProb.getCompl());
625   return true;
626 }
627
628 void BranchProbabilityInfo::releaseMemory() {
629   Probs.clear();
630 }
631
632 void BranchProbabilityInfo::print(raw_ostream &OS) const {
633   OS << "---- Branch Probabilities ----\n";
634   // We print the probabilities from the last function the analysis ran over,
635   // or the function it is currently running over.
636   assert(LastF && "Cannot print prior to running over a function");
637   for (const auto &BI : *LastF) {
638     for (succ_const_iterator SI = succ_begin(&BI), SE = succ_end(&BI); SI != SE;
639          ++SI) {
640       printEdgeProbability(OS << "  ", &BI, *SI);
641     }
642   }
643 }
644
645 bool BranchProbabilityInfo::
646 isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const {
647   // Hot probability is at least 4/5 = 80%
648   // FIXME: Compare against a static "hot" BranchProbability.
649   return getEdgeProbability(Src, Dst) > BranchProbability(4, 5);
650 }
651
652 const BasicBlock *
653 BranchProbabilityInfo::getHotSucc(const BasicBlock *BB) const {
654   auto MaxProb = BranchProbability::getZero();
655   const BasicBlock *MaxSucc = nullptr;
656
657   for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
658     const BasicBlock *Succ = *I;
659     auto Prob = getEdgeProbability(BB, Succ);
660     if (Prob > MaxProb) {
661       MaxProb = Prob;
662       MaxSucc = Succ;
663     }
664   }
665
666   // Hot probability is at least 4/5 = 80%
667   if (MaxProb > BranchProbability(4, 5))
668     return MaxSucc;
669
670   return nullptr;
671 }
672
673 /// Get the raw edge probability for the edge. If can't find it, return a
674 /// default probability 1/N where N is the number of successors. Here an edge is
675 /// specified using PredBlock and an
676 /// index to the successors.
677 BranchProbability
678 BranchProbabilityInfo::getEdgeProbability(const BasicBlock *Src,
679                                           unsigned IndexInSuccessors) const {
680   auto I = Probs.find(std::make_pair(Src, IndexInSuccessors));
681
682   if (I != Probs.end())
683     return I->second;
684
685   return {1,
686           static_cast<uint32_t>(std::distance(succ_begin(Src), succ_end(Src)))};
687 }
688
689 BranchProbability
690 BranchProbabilityInfo::getEdgeProbability(const BasicBlock *Src,
691                                           succ_const_iterator Dst) const {
692   return getEdgeProbability(Src, Dst.getSuccessorIndex());
693 }
694
695 /// Get the raw edge probability calculated for the block pair. This returns the
696 /// sum of all raw edge probabilities from Src to Dst.
697 BranchProbability
698 BranchProbabilityInfo::getEdgeProbability(const BasicBlock *Src,
699                                           const BasicBlock *Dst) const {
700   auto Prob = BranchProbability::getZero();
701   bool FoundProb = false;
702   for (succ_const_iterator I = succ_begin(Src), E = succ_end(Src); I != E; ++I)
703     if (*I == Dst) {
704       auto MapI = Probs.find(std::make_pair(Src, I.getSuccessorIndex()));
705       if (MapI != Probs.end()) {
706         FoundProb = true;
707         Prob += MapI->second;
708       }
709     }
710   uint32_t succ_num = std::distance(succ_begin(Src), succ_end(Src));
711   return FoundProb ? Prob : BranchProbability(1, succ_num);
712 }
713
714 /// Set the edge probability for a given edge specified by PredBlock and an
715 /// index to the successors.
716 void BranchProbabilityInfo::setEdgeProbability(const BasicBlock *Src,
717                                                unsigned IndexInSuccessors,
718                                                BranchProbability Prob) {
719   Probs[std::make_pair(Src, IndexInSuccessors)] = Prob;
720   Handles.insert(BasicBlockCallbackVH(Src, this));
721   DEBUG(dbgs() << "set edge " << Src->getName() << " -> " << IndexInSuccessors
722                << " successor probability to " << Prob << "\n");
723 }
724
725 raw_ostream &
726 BranchProbabilityInfo::printEdgeProbability(raw_ostream &OS,
727                                             const BasicBlock *Src,
728                                             const BasicBlock *Dst) const {
729
730   const BranchProbability Prob = getEdgeProbability(Src, Dst);
731   OS << "edge " << Src->getName() << " -> " << Dst->getName()
732      << " probability is " << Prob
733      << (isEdgeHot(Src, Dst) ? " [HOT edge]\n" : "\n");
734
735   return OS;
736 }
737
738 void BranchProbabilityInfo::eraseBlock(const BasicBlock *BB) {
739   for (auto I = Probs.begin(), E = Probs.end(); I != E; ++I) {
740     auto Key = I->first;
741     if (Key.first == BB)
742       Probs.erase(Key);
743   }
744 }
745
746 void BranchProbabilityInfo::calculate(const Function &F, const LoopInfo &LI) {
747   DEBUG(dbgs() << "---- Branch Probability Info : " << F.getName()
748                << " ----\n\n");
749   LastF = &F; // Store the last function we ran on for printing.
750   assert(PostDominatedByUnreachable.empty());
751   assert(PostDominatedByColdCall.empty());
752
753   // Walk the basic blocks in post-order so that we can build up state about
754   // the successors of a block iteratively.
755   for (auto BB : post_order(&F.getEntryBlock())) {
756     DEBUG(dbgs() << "Computing probabilities for " << BB->getName() << "\n");
757     updatePostDominatedByUnreachable(BB);
758     updatePostDominatedByColdCall(BB);
759     // If there is no at least two successors, no sense to set probability.
760     if (BB->getTerminator()->getNumSuccessors() < 2)
761       continue;
762     if (calcMetadataWeights(BB))
763       continue;
764     if (calcUnreachableHeuristics(BB))
765       continue;
766     if (calcColdCallHeuristics(BB))
767       continue;
768     if (calcLoopBranchHeuristics(BB, LI))
769       continue;
770     if (calcPointerHeuristics(BB))
771       continue;
772     if (calcZeroHeuristics(BB))
773       continue;
774     if (calcFloatingPointHeuristics(BB))
775       continue;
776     calcInvokeHeuristics(BB);
777   }
778
779   PostDominatedByUnreachable.clear();
780   PostDominatedByColdCall.clear();
781 }
782
783 void BranchProbabilityInfoWrapperPass::getAnalysisUsage(
784     AnalysisUsage &AU) const {
785   AU.addRequired<LoopInfoWrapperPass>();
786   AU.setPreservesAll();
787 }
788
789 bool BranchProbabilityInfoWrapperPass::runOnFunction(Function &F) {
790   const LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
791   BPI.calculate(F, LI);
792   return false;
793 }
794
795 void BranchProbabilityInfoWrapperPass::releaseMemory() { BPI.releaseMemory(); }
796
797 void BranchProbabilityInfoWrapperPass::print(raw_ostream &OS,
798                                              const Module *) const {
799   BPI.print(OS);
800 }
801
802 AnalysisKey BranchProbabilityAnalysis::Key;
803 BranchProbabilityInfo
804 BranchProbabilityAnalysis::run(Function &F, FunctionAnalysisManager &AM) {
805   BranchProbabilityInfo BPI;
806   BPI.calculate(F, AM.getResult<LoopAnalysis>(F));
807   return BPI;
808 }
809
810 PreservedAnalyses
811 BranchProbabilityPrinterPass::run(Function &F, FunctionAnalysisManager &AM) {
812   OS << "Printing analysis results of BPI for function "
813      << "'" << F.getName() << "':"
814      << "\n";
815   AM.getResult<BranchProbabilityAnalysis>(F).print(OS);
816   return PreservedAnalyses::all();
817 }