Coverage Report

Created: 2019-07-24 05:18

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