← Back to branch summary

~pali/+junk/llvm-toolchain-3.7

« back to all changes in this revision

Viewing changes to lib/Analysis/BranchProbabilityInfo.cpp

  • Committer: Package Import Robot
  • Author(s): Sylvestre Ledru
  • Date: 2015-07-15 17:51:08 UTC
  • Revision ID: package-import@ubuntu.com-20150715175108-l8mynwovkx4zx697
Tags: upstream-3.7~+rc2
Import upstream version 3.7~+rc2

Show diffs side-by-side

added added

removed removed

Lines of Context:
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(BranchProbabilityInfo, "branch-prob",
 
31
                      "Branch Probability Analysis", false, true)
 
32
INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
 
33
INITIALIZE_PASS_END(BranchProbabilityInfo, "branch-prob",
 
34
                    "Branch Probability Analysis", false, true)
 
35
 
 
36
char BranchProbabilityInfo::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 Weight for a branch taken going into a cold block.
 
76
///
 
77
/// This is the weight for a branch taken toward a block marked
 
78
/// cold.  A block is marked cold if it's postdominated by a
 
79
/// block containing a call to a cold function.  Cold functions
 
80
/// are those marked with attribute 'cold'.
 
81
static const uint32_t CC_TAKEN_WEIGHT = 4;
 
82
 
 
83
/// \brief Weight for a branch not-taken into a cold block.
 
84
///
 
85
/// This is the weight for a branch not taken toward a block marked
 
86
/// cold.
 
87
static const uint32_t CC_NONTAKEN_WEIGHT = 64;
 
88
 
 
89
static const uint32_t PH_TAKEN_WEIGHT = 20;
 
90
static const uint32_t PH_NONTAKEN_WEIGHT = 12;
 
91
 
 
92
static const uint32_t ZH_TAKEN_WEIGHT = 20;
 
93
static const uint32_t ZH_NONTAKEN_WEIGHT = 12;
 
94
 
 
95
static const uint32_t FPH_TAKEN_WEIGHT = 20;
 
96
static const uint32_t FPH_NONTAKEN_WEIGHT = 12;
 
97
 
 
98
/// \brief Invoke-terminating normal branch taken weight
 
99
///
 
100
/// This is the weight for branching to the normal destination of an invoke
 
101
/// instruction. We expect this to happen most of the time. Set the weight to an
 
102
/// absurdly high value so that nested loops subsume it.
 
103
static const uint32_t IH_TAKEN_WEIGHT = 1024 * 1024 - 1;
 
104
 
 
105
/// \brief Invoke-terminating normal branch not-taken weight.
 
106
///
 
107
/// This is the weight for branching to the unwind destination of an invoke
 
108
/// instruction. This is essentially never taken.
 
109
static const uint32_t IH_NONTAKEN_WEIGHT = 1;
 
110
 
 
111
// Standard weight value. Used when none of the heuristics set weight for
 
112
// the edge.
 
113
static const uint32_t NORMAL_WEIGHT = 16;
 
114
 
 
115
// Minimum weight of an edge. Please note, that weight is NEVER 0.
 
116
static const uint32_t MIN_WEIGHT = 1;
 
117
 
 
118
/// \brief Calculate edge weights for successors lead to unreachable.
 
119
///
 
120
/// Predict that a successor which leads necessarily to an
 
121
/// unreachable-terminated block as extremely unlikely.
 
122
bool BranchProbabilityInfo::calcUnreachableHeuristics(BasicBlock *BB) {
 
123
  TerminatorInst *TI = BB->getTerminator();
 
124
  if (TI->getNumSuccessors() == 0) {
 
125
    if (isa<UnreachableInst>(TI))
 
126
      PostDominatedByUnreachable.insert(BB);
 
127
    return false;
 
128
  }
 
129
 
 
130
  SmallVector<unsigned, 4> UnreachableEdges;
 
131
  SmallVector<unsigned, 4> ReachableEdges;
 
132
 
 
133
  for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
 
134
    if (PostDominatedByUnreachable.count(*I))
 
135
      UnreachableEdges.push_back(I.getSuccessorIndex());
 
136
    else
 
137
      ReachableEdges.push_back(I.getSuccessorIndex());
 
138
  }
 
139
 
 
140
  // If all successors are in the set of blocks post-dominated by unreachable,
 
141
  // this block is too.
 
142
  if (UnreachableEdges.size() == TI->getNumSuccessors())
 
143
    PostDominatedByUnreachable.insert(BB);
 
144
 
 
145
  // Skip probabilities if this block has a single successor or if all were
 
146
  // reachable.
 
147
  if (TI->getNumSuccessors() == 1 || UnreachableEdges.empty())
 
148
    return false;
 
149
 
 
150
  uint32_t UnreachableWeight =
 
151
    std::max(UR_TAKEN_WEIGHT / (unsigned)UnreachableEdges.size(), MIN_WEIGHT);
 
152
  for (SmallVectorImpl<unsigned>::iterator I = UnreachableEdges.begin(),
 
153
                                           E = UnreachableEdges.end();
 
154
       I != E; ++I)
 
155
    setEdgeWeight(BB, *I, UnreachableWeight);
 
156
 
 
157
  if (ReachableEdges.empty())
 
158
    return true;
 
159
  uint32_t ReachableWeight =
 
160
    std::max(UR_NONTAKEN_WEIGHT / (unsigned)ReachableEdges.size(),
 
161
             NORMAL_WEIGHT);
 
162
  for (SmallVectorImpl<unsigned>::iterator I = ReachableEdges.begin(),
 
163
                                           E = ReachableEdges.end();
 
164
       I != E; ++I)
 
165
    setEdgeWeight(BB, *I, ReachableWeight);
 
166
 
 
167
  return true;
 
168
}
 
169
 
 
170
// Propagate existing explicit probabilities from either profile data or
 
171
// 'expect' intrinsic processing.
 
172
bool BranchProbabilityInfo::calcMetadataWeights(BasicBlock *BB) {
 
173
  TerminatorInst *TI = BB->getTerminator();
 
174
  if (TI->getNumSuccessors() == 1)
 
175
    return false;
 
176
  if (!isa<BranchInst>(TI) && !isa<SwitchInst>(TI))
 
177
    return false;
 
178
 
 
179
  MDNode *WeightsNode = TI->getMetadata(LLVMContext::MD_prof);
 
180
  if (!WeightsNode)
 
181
    return false;
 
182
 
 
183
  // Check that the number of successors is manageable.
 
184
  assert(TI->getNumSuccessors() < UINT32_MAX && "Too many successors");
 
185
 
 
186
  // Ensure there are weights for all of the successors. Note that the first
 
187
  // operand to the metadata node is a name, not a weight.
 
188
  if (WeightsNode->getNumOperands() != TI->getNumSuccessors() + 1)
 
189
    return false;
 
190
 
 
191
  // Build up the final weights that will be used in a temporary buffer.
 
192
  // Compute the sum of all weights to later decide whether they need to
 
193
  // be scaled to fit in 32 bits.
 
194
  uint64_t WeightSum = 0;
 
195
  SmallVector<uint32_t, 2> Weights;
 
196
  Weights.reserve(TI->getNumSuccessors());
 
197
  for (unsigned i = 1, e = WeightsNode->getNumOperands(); i != e; ++i) {
 
198
    ConstantInt *Weight =
 
199
        mdconst::dyn_extract<ConstantInt>(WeightsNode->getOperand(i));
 
200
    if (!Weight)
 
201
      return false;
 
202
    assert(Weight->getValue().getActiveBits() <= 32 &&
 
203
           "Too many bits for uint32_t");
 
204
    Weights.push_back(Weight->getZExtValue());
 
205
    WeightSum += Weights.back();
 
206
  }
 
207
  assert(Weights.size() == TI->getNumSuccessors() && "Checked above");
 
208
 
 
209
  // If the sum of weights does not fit in 32 bits, scale every weight down
 
210
  // accordingly.
 
211
  uint64_t ScalingFactor =
 
212
      (WeightSum > UINT32_MAX) ? WeightSum / UINT32_MAX + 1 : 1;
 
213
 
 
214
  WeightSum = 0;
 
215
  for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) {
 
216
    uint32_t W = Weights[i] / ScalingFactor;
 
217
    WeightSum += W;
 
218
    setEdgeWeight(BB, i, W);
 
219
  }
 
220
  assert(WeightSum <= UINT32_MAX &&
 
221
         "Expected weights to scale down to 32 bits");
 
222
 
 
223
  return true;
 
224
}
 
225
 
 
226
/// \brief Calculate edge weights for edges leading to cold blocks.
 
227
///
 
228
/// A cold block is one post-dominated by  a block with a call to a
 
229
/// cold function.  Those edges are unlikely to be taken, so we give
 
230
/// them relatively low weight.
 
231
///
 
232
/// Return true if we could compute the weights for cold edges.
 
233
/// Return false, otherwise.
 
234
bool BranchProbabilityInfo::calcColdCallHeuristics(BasicBlock *BB) {
 
235
  TerminatorInst *TI = BB->getTerminator();
 
236
  if (TI->getNumSuccessors() == 0)
 
237
    return false;
 
238
 
 
239
  // Determine which successors are post-dominated by a cold block.
 
240
  SmallVector<unsigned, 4> ColdEdges;
 
241
  SmallVector<unsigned, 4> NormalEdges;
 
242
  for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I)
 
243
    if (PostDominatedByColdCall.count(*I))
 
244
      ColdEdges.push_back(I.getSuccessorIndex());
 
245
    else
 
246
      NormalEdges.push_back(I.getSuccessorIndex());
 
247
 
 
248
  // If all successors are in the set of blocks post-dominated by cold calls,
 
249
  // this block is in the set post-dominated by cold calls.
 
250
  if (ColdEdges.size() == TI->getNumSuccessors())
 
251
    PostDominatedByColdCall.insert(BB);
 
252
  else {
 
253
    // Otherwise, if the block itself contains a cold function, add it to the
 
254
    // set of blocks postdominated by a cold call.
 
255
    assert(!PostDominatedByColdCall.count(BB));
 
256
    for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
 
257
      if (CallInst *CI = dyn_cast<CallInst>(I))
 
258
        if (CI->hasFnAttr(Attribute::Cold)) {
 
259
          PostDominatedByColdCall.insert(BB);
 
260
          break;
 
261
        }
 
262
  }
 
263
 
 
264
  // Skip probabilities if this block has a single successor.
 
265
  if (TI->getNumSuccessors() == 1 || ColdEdges.empty())
 
266
    return false;
 
267
 
 
268
  uint32_t ColdWeight =
 
269
      std::max(CC_TAKEN_WEIGHT / (unsigned) ColdEdges.size(), MIN_WEIGHT);
 
270
  for (SmallVectorImpl<unsigned>::iterator I = ColdEdges.begin(),
 
271
                                           E = ColdEdges.end();
 
272
       I != E; ++I)
 
273
    setEdgeWeight(BB, *I, ColdWeight);
 
274
 
 
275
  if (NormalEdges.empty())
 
276
    return true;
 
277
  uint32_t NormalWeight = std::max(
 
278
      CC_NONTAKEN_WEIGHT / (unsigned) NormalEdges.size(), NORMAL_WEIGHT);
 
279
  for (SmallVectorImpl<unsigned>::iterator I = NormalEdges.begin(),
 
280
                                           E = NormalEdges.end();
 
281
       I != E; ++I)
 
282
    setEdgeWeight(BB, *I, NormalWeight);
 
283
 
 
284
  return true;
 
285
}
 
286
 
 
287
// Calculate Edge Weights using "Pointer Heuristics". Predict a comparsion
 
288
// between two pointer or pointer and NULL will fail.
 
289
bool BranchProbabilityInfo::calcPointerHeuristics(BasicBlock *BB) {
 
290
  BranchInst * BI = dyn_cast<BranchInst>(BB->getTerminator());
 
291
  if (!BI || !BI->isConditional())
 
292
    return false;
 
293
 
 
294
  Value *Cond = BI->getCondition();
 
295
  ICmpInst *CI = dyn_cast<ICmpInst>(Cond);
 
296
  if (!CI || !CI->isEquality())
 
297
    return false;
 
298
 
 
299
  Value *LHS = CI->getOperand(0);
 
300
 
 
301
  if (!LHS->getType()->isPointerTy())
 
302
    return false;
 
303
 
 
304
  assert(CI->getOperand(1)->getType()->isPointerTy());
 
305
 
 
306
  // p != 0   ->   isProb = true
 
307
  // p == 0   ->   isProb = false
 
308
  // p != q   ->   isProb = true
 
309
  // p == q   ->   isProb = false;
 
310
  unsigned TakenIdx = 0, NonTakenIdx = 1;
 
311
  bool isProb = CI->getPredicate() == ICmpInst::ICMP_NE;
 
312
  if (!isProb)
 
313
    std::swap(TakenIdx, NonTakenIdx);
 
314
 
 
315
  setEdgeWeight(BB, TakenIdx, PH_TAKEN_WEIGHT);
 
316
  setEdgeWeight(BB, NonTakenIdx, PH_NONTAKEN_WEIGHT);
 
317
  return true;
 
318
}
 
319
 
 
320
// Calculate Edge Weights using "Loop Branch Heuristics". Predict backedges
 
321
// as taken, exiting edges as not-taken.
 
322
bool BranchProbabilityInfo::calcLoopBranchHeuristics(BasicBlock *BB) {
 
323
  Loop *L = LI->getLoopFor(BB);
 
324
  if (!L)
 
325
    return false;
 
326
 
 
327
  SmallVector<unsigned, 8> BackEdges;
 
328
  SmallVector<unsigned, 8> ExitingEdges;
 
329
  SmallVector<unsigned, 8> InEdges; // Edges from header to the loop.
 
330
 
 
331
  for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
 
332
    if (!L->contains(*I))
 
333
      ExitingEdges.push_back(I.getSuccessorIndex());
 
334
    else if (L->getHeader() == *I)
 
335
      BackEdges.push_back(I.getSuccessorIndex());
 
336
    else
 
337
      InEdges.push_back(I.getSuccessorIndex());
 
338
  }
 
339
 
 
340
  if (BackEdges.empty() && ExitingEdges.empty())
 
341
    return false;
 
342
 
 
343
  if (uint32_t numBackEdges = BackEdges.size()) {
 
344
    uint32_t backWeight = LBH_TAKEN_WEIGHT / numBackEdges;
 
345
    if (backWeight < NORMAL_WEIGHT)
 
346
      backWeight = NORMAL_WEIGHT;
 
347
 
 
348
    for (SmallVectorImpl<unsigned>::iterator EI = BackEdges.begin(),
 
349
         EE = BackEdges.end(); EI != EE; ++EI) {
 
350
      setEdgeWeight(BB, *EI, backWeight);
 
351
    }
 
352
  }
 
353
 
 
354
  if (uint32_t numInEdges = InEdges.size()) {
 
355
    uint32_t inWeight = LBH_TAKEN_WEIGHT / numInEdges;
 
356
    if (inWeight < NORMAL_WEIGHT)
 
357
      inWeight = NORMAL_WEIGHT;
 
358
 
 
359
    for (SmallVectorImpl<unsigned>::iterator EI = InEdges.begin(),
 
360
         EE = InEdges.end(); EI != EE; ++EI) {
 
361
      setEdgeWeight(BB, *EI, inWeight);
 
362
    }
 
363
  }
 
364
 
 
365
  if (uint32_t numExitingEdges = ExitingEdges.size()) {
 
366
    uint32_t exitWeight = LBH_NONTAKEN_WEIGHT / numExitingEdges;
 
367
    if (exitWeight < MIN_WEIGHT)
 
368
      exitWeight = MIN_WEIGHT;
 
369
 
 
370
    for (SmallVectorImpl<unsigned>::iterator EI = ExitingEdges.begin(),
 
371
         EE = ExitingEdges.end(); EI != EE; ++EI) {
 
372
      setEdgeWeight(BB, *EI, exitWeight);
 
373
    }
 
374
  }
 
375
 
 
376
  return true;
 
377
}
 
378
 
 
379
bool BranchProbabilityInfo::calcZeroHeuristics(BasicBlock *BB) {
 
380
  BranchInst * BI = dyn_cast<BranchInst>(BB->getTerminator());
 
381
  if (!BI || !BI->isConditional())
 
382
    return false;
 
383
 
 
384
  Value *Cond = BI->getCondition();
 
385
  ICmpInst *CI = dyn_cast<ICmpInst>(Cond);
 
386
  if (!CI)
 
387
    return false;
 
388
 
 
389
  Value *RHS = CI->getOperand(1);
 
390
  ConstantInt *CV = dyn_cast<ConstantInt>(RHS);
 
391
  if (!CV)
 
392
    return false;
 
393
 
 
394
  // If the LHS is the result of AND'ing a value with a single bit bitmask,
 
395
  // we don't have information about probabilities.
 
396
  if (Instruction *LHS = dyn_cast<Instruction>(CI->getOperand(0)))
 
397
    if (LHS->getOpcode() == Instruction::And)
 
398
      if (ConstantInt *AndRHS = dyn_cast<ConstantInt>(LHS->getOperand(1)))
 
399
        if (AndRHS->getUniqueInteger().isPowerOf2())
 
400
          return false;
 
401
 
 
402
  bool isProb;
 
403
  if (CV->isZero()) {
 
404
    switch (CI->getPredicate()) {
 
405
    case CmpInst::ICMP_EQ:
 
406
      // X == 0   ->  Unlikely
 
407
      isProb = false;
 
408
      break;
 
409
    case CmpInst::ICMP_NE:
 
410
      // X != 0   ->  Likely
 
411
      isProb = true;
 
412
      break;
 
413
    case CmpInst::ICMP_SLT:
 
414
      // X < 0   ->  Unlikely
 
415
      isProb = false;
 
416
      break;
 
417
    case CmpInst::ICMP_SGT:
 
418
      // X > 0   ->  Likely
 
419
      isProb = true;
 
420
      break;
 
421
    default:
 
422
      return false;
 
423
    }
 
424
  } else if (CV->isOne() && CI->getPredicate() == CmpInst::ICMP_SLT) {
 
425
    // InstCombine canonicalizes X <= 0 into X < 1.
 
426
    // X <= 0   ->  Unlikely
 
427
    isProb = false;
 
428
  } else if (CV->isAllOnesValue()) {
 
429
    switch (CI->getPredicate()) {
 
430
    case CmpInst::ICMP_EQ:
 
431
      // X == -1  ->  Unlikely
 
432
      isProb = false;
 
433
      break;
 
434
    case CmpInst::ICMP_NE:
 
435
      // X != -1  ->  Likely
 
436
      isProb = true;
 
437
      break;
 
438
    case CmpInst::ICMP_SGT:
 
439
      // InstCombine canonicalizes X >= 0 into X > -1.
 
440
      // X >= 0   ->  Likely
 
441
      isProb = true;
 
442
      break;
 
443
    default:
 
444
      return false;
 
445
    }
 
446
  } else {
 
447
    return false;
 
448
  }
 
449
 
 
450
  unsigned TakenIdx = 0, NonTakenIdx = 1;
 
451
 
 
452
  if (!isProb)
 
453
    std::swap(TakenIdx, NonTakenIdx);
 
454
 
 
455
  setEdgeWeight(BB, TakenIdx, ZH_TAKEN_WEIGHT);
 
456
  setEdgeWeight(BB, NonTakenIdx, ZH_NONTAKEN_WEIGHT);
 
457
 
 
458
  return true;
 
459
}
 
460
 
 
461
bool BranchProbabilityInfo::calcFloatingPointHeuristics(BasicBlock *BB) {
 
462
  BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
 
463
  if (!BI || !BI->isConditional())
 
464
    return false;
 
465
 
 
466
  Value *Cond = BI->getCondition();
 
467
  FCmpInst *FCmp = dyn_cast<FCmpInst>(Cond);
 
468
  if (!FCmp)
 
469
    return false;
 
470
 
 
471
  bool isProb;
 
472
  if (FCmp->isEquality()) {
 
473
    // f1 == f2 -> Unlikely
 
474
    // f1 != f2 -> Likely
 
475
    isProb = !FCmp->isTrueWhenEqual();
 
476
  } else if (FCmp->getPredicate() == FCmpInst::FCMP_ORD) {
 
477
    // !isnan -> Likely
 
478
    isProb = true;
 
479
  } else if (FCmp->getPredicate() == FCmpInst::FCMP_UNO) {
 
480
    // isnan -> Unlikely
 
481
    isProb = false;
 
482
  } else {
 
483
    return false;
 
484
  }
 
485
 
 
486
  unsigned TakenIdx = 0, NonTakenIdx = 1;
 
487
 
 
488
  if (!isProb)
 
489
    std::swap(TakenIdx, NonTakenIdx);
 
490
 
 
491
  setEdgeWeight(BB, TakenIdx, FPH_TAKEN_WEIGHT);
 
492
  setEdgeWeight(BB, NonTakenIdx, FPH_NONTAKEN_WEIGHT);
 
493
 
 
494
  return true;
 
495
}
 
496
 
 
497
bool BranchProbabilityInfo::calcInvokeHeuristics(BasicBlock *BB) {
 
498
  InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator());
 
499
  if (!II)
 
500
    return false;
 
501
 
 
502
  setEdgeWeight(BB, 0/*Index for Normal*/, IH_TAKEN_WEIGHT);
 
503
  setEdgeWeight(BB, 1/*Index for Unwind*/, IH_NONTAKEN_WEIGHT);
 
504
  return true;
 
505
}
 
506
 
 
507
void BranchProbabilityInfo::getAnalysisUsage(AnalysisUsage &AU) const {
 
508
  AU.addRequired<LoopInfoWrapperPass>();
 
509
  AU.setPreservesAll();
 
510
}
 
511
 
 
512
bool BranchProbabilityInfo::runOnFunction(Function &F) {
 
513
  DEBUG(dbgs() << "---- Branch Probability Info : " << F.getName()
 
514
               << " ----\n\n");
 
515
  LastF = &F; // Store the last function we ran on for printing.
 
516
  LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
 
517
  assert(PostDominatedByUnreachable.empty());
 
518
  assert(PostDominatedByColdCall.empty());
 
519
 
 
520
  // Walk the basic blocks in post-order so that we can build up state about
 
521
  // the successors of a block iteratively.
 
522
  for (auto BB : post_order(&F.getEntryBlock())) {
 
523
    DEBUG(dbgs() << "Computing probabilities for " << BB->getName() << "\n");
 
524
    if (calcUnreachableHeuristics(BB))
 
525
      continue;
 
526
    if (calcMetadataWeights(BB))
 
527
      continue;
 
528
    if (calcColdCallHeuristics(BB))
 
529
      continue;
 
530
    if (calcLoopBranchHeuristics(BB))
 
531
      continue;
 
532
    if (calcPointerHeuristics(BB))
 
533
      continue;
 
534
    if (calcZeroHeuristics(BB))
 
535
      continue;
 
536
    if (calcFloatingPointHeuristics(BB))
 
537
      continue;
 
538
    calcInvokeHeuristics(BB);
 
539
  }
 
540
 
 
541
  PostDominatedByUnreachable.clear();
 
542
  PostDominatedByColdCall.clear();
 
543
  return false;
 
544
}
 
545
 
 
546
void BranchProbabilityInfo::releaseMemory() {
 
547
  Weights.clear();
 
548
}
 
549
 
 
550
void BranchProbabilityInfo::print(raw_ostream &OS, const Module *) const {
 
551
  OS << "---- Branch Probabilities ----\n";
 
552
  // We print the probabilities from the last function the analysis ran over,
 
553
  // or the function it is currently running over.
 
554
  assert(LastF && "Cannot print prior to running over a function");
 
555
  for (Function::const_iterator BI = LastF->begin(), BE = LastF->end();
 
556
       BI != BE; ++BI) {
 
557
    for (succ_const_iterator SI = succ_begin(BI), SE = succ_end(BI);
 
558
         SI != SE; ++SI) {
 
559
      printEdgeProbability(OS << "  ", BI, *SI);
 
560
    }
 
561
  }
 
562
}
 
563
 
 
564
uint32_t BranchProbabilityInfo::getSumForBlock(const BasicBlock *BB) const {
 
565
  uint32_t Sum = 0;
 
566
 
 
567
  for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
 
568
    uint32_t Weight = getEdgeWeight(BB, I.getSuccessorIndex());
 
569
    uint32_t PrevSum = Sum;
 
570
 
 
571
    Sum += Weight;
 
572
    assert(Sum >= PrevSum); (void) PrevSum;
 
573
  }
 
574
 
 
575
  return Sum;
 
576
}
 
577
 
 
578
bool BranchProbabilityInfo::
 
579
isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const {
 
580
  // Hot probability is at least 4/5 = 80%
 
581
  // FIXME: Compare against a static "hot" BranchProbability.
 
582
  return getEdgeProbability(Src, Dst) > BranchProbability(4, 5);
 
583
}
 
584
 
 
585
BasicBlock *BranchProbabilityInfo::getHotSucc(BasicBlock *BB) const {
 
586
  uint32_t Sum = 0;
 
587
  uint32_t MaxWeight = 0;
 
588
  BasicBlock *MaxSucc = nullptr;
 
589
 
 
590
  for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
 
591
    BasicBlock *Succ = *I;
 
592
    uint32_t Weight = getEdgeWeight(BB, Succ);
 
593
    uint32_t PrevSum = Sum;
 
594
 
 
595
    Sum += Weight;
 
596
    assert(Sum > PrevSum); (void) PrevSum;
 
597
 
 
598
    if (Weight > MaxWeight) {
 
599
      MaxWeight = Weight;
 
600
      MaxSucc = Succ;
 
601
    }
 
602
  }
 
603
 
 
604
  // Hot probability is at least 4/5 = 80%
 
605
  if (BranchProbability(MaxWeight, Sum) > BranchProbability(4, 5))
 
606
    return MaxSucc;
 
607
 
 
608
  return nullptr;
 
609
}
 
610
 
 
611
/// Get the raw edge weight for the edge. If can't find it, return
 
612
/// DEFAULT_WEIGHT value. Here an edge is specified using PredBlock and an index
 
613
/// to the successors.
 
614
uint32_t BranchProbabilityInfo::
 
615
getEdgeWeight(const BasicBlock *Src, unsigned IndexInSuccessors) const {
 
616
  DenseMap<Edge, uint32_t>::const_iterator I =
 
617
      Weights.find(std::make_pair(Src, IndexInSuccessors));
 
618
 
 
619
  if (I != Weights.end())
 
620
    return I->second;
 
621
 
 
622
  return DEFAULT_WEIGHT;
 
623
}
 
624
 
 
625
uint32_t BranchProbabilityInfo::getEdgeWeight(const BasicBlock *Src,
 
626
                                              succ_const_iterator Dst) const {
 
627
  return getEdgeWeight(Src, Dst.getSuccessorIndex());
 
628
}
 
629
 
 
630
/// Get the raw edge weight calculated for the block pair. This returns the sum
 
631
/// of all raw edge weights from Src to Dst.
 
632
uint32_t BranchProbabilityInfo::
 
633
getEdgeWeight(const BasicBlock *Src, const BasicBlock *Dst) const {
 
634
  uint32_t Weight = 0;
 
635
  bool FoundWeight = false;
 
636
  DenseMap<Edge, uint32_t>::const_iterator MapI;
 
637
  for (succ_const_iterator I = succ_begin(Src), E = succ_end(Src); I != E; ++I)
 
638
    if (*I == Dst) {
 
639
      MapI = Weights.find(std::make_pair(Src, I.getSuccessorIndex()));
 
640
      if (MapI != Weights.end()) {
 
641
        FoundWeight = true;
 
642
        Weight += MapI->second;
 
643
      }
 
644
    }
 
645
  return (!FoundWeight) ? DEFAULT_WEIGHT : Weight;
 
646
}
 
647
 
 
648
/// Set the edge weight for a given edge specified by PredBlock and an index
 
649
/// to the successors.
 
650
void BranchProbabilityInfo::
 
651
setEdgeWeight(const BasicBlock *Src, unsigned IndexInSuccessors,
 
652
              uint32_t Weight) {
 
653
  Weights[std::make_pair(Src, IndexInSuccessors)] = Weight;
 
654
  DEBUG(dbgs() << "set edge " << Src->getName() << " -> "
 
655
               << IndexInSuccessors << " successor weight to "
 
656
               << Weight << "\n");
 
657
}
 
658
 
 
659
/// Get an edge's probability, relative to other out-edges from Src.
 
660
BranchProbability BranchProbabilityInfo::
 
661
getEdgeProbability(const BasicBlock *Src, unsigned IndexInSuccessors) const {
 
662
  uint32_t N = getEdgeWeight(Src, IndexInSuccessors);
 
663
  uint32_t D = getSumForBlock(Src);
 
664
 
 
665
  return BranchProbability(N, D);
 
666
}
 
667
 
 
668
/// Get the probability of going from Src to Dst. It returns the sum of all
 
669
/// probabilities for edges from Src to Dst.
 
670
BranchProbability BranchProbabilityInfo::
 
671
getEdgeProbability(const BasicBlock *Src, const BasicBlock *Dst) const {
 
672
 
 
673
  uint32_t N = getEdgeWeight(Src, Dst);
 
674
  uint32_t D = getSumForBlock(Src);
 
675
 
 
676
  return BranchProbability(N, D);
 
677
}
 
678
 
 
679
raw_ostream &
 
680
BranchProbabilityInfo::printEdgeProbability(raw_ostream &OS,
 
681
                                            const BasicBlock *Src,
 
682
                                            const BasicBlock *Dst) const {
 
683
 
 
684
  const BranchProbability Prob = getEdgeProbability(Src, Dst);
 
685
  OS << "edge " << Src->getName() << " -> " << Dst->getName()
 
686
     << " probability is " << Prob
 
687
     << (isEdgeHot(Src, Dst) ? " [HOT edge]\n" : "\n");
 
688
 
 
689
  return OS;
 
690
}