Coverage Report

Created: 2018-07-18 22:01

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/Analysis/BranchProbabilityInfo.h
Line
Count
Source (jump to first uncovered line)
1
//===- BranchProbabilityInfo.h - Branch Probability Analysis ----*- C++ -*-===//
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
// This pass is used to evaluate branch probabilties.
11
//
12
//===----------------------------------------------------------------------===//
13
14
#ifndef LLVM_ANALYSIS_BRANCHPROBABILITYINFO_H
15
#define LLVM_ANALYSIS_BRANCHPROBABILITYINFO_H
16
17
#include "llvm/ADT/DenseMap.h"
18
#include "llvm/ADT/DenseMapInfo.h"
19
#include "llvm/ADT/DenseSet.h"
20
#include "llvm/ADT/SmallPtrSet.h"
21
#include "llvm/IR/BasicBlock.h"
22
#include "llvm/IR/CFG.h"
23
#include "llvm/IR/PassManager.h"
24
#include "llvm/IR/ValueHandle.h"
25
#include "llvm/Pass.h"
26
#include "llvm/Support/BranchProbability.h"
27
#include "llvm/Support/Casting.h"
28
#include <algorithm>
29
#include <cassert>
30
#include <cstdint>
31
#include <utility>
32
33
namespace llvm {
34
35
class Function;
36
class LoopInfo;
37
class raw_ostream;
38
class TargetLibraryInfo;
39
class Value;
40
41
/// Analysis providing branch probability information.
42
///
43
/// This is a function analysis which provides information on the relative
44
/// probabilities of each "edge" in the function's CFG where such an edge is
45
/// defined by a pair (PredBlock and an index in the successors). The
46
/// probability of an edge from one block is always relative to the
47
/// probabilities of other edges from the block. The probabilites of all edges
48
/// from a block sum to exactly one (100%).
49
/// We use a pair (PredBlock and an index in the successors) to uniquely
50
/// identify an edge, since we can have multiple edges from Src to Dst.
51
/// As an example, we can have a switch which jumps to Dst with value 0 and
52
/// value 10.
53
class BranchProbabilityInfo {
54
public:
55
5.53M
  BranchProbabilityInfo() = default;
56
57
  BranchProbabilityInfo(const Function &F, const LoopInfo &LI,
58
449k
                        const TargetLibraryInfo *TLI = nullptr) {
59
449k
    calculate(F, LI, TLI);
60
449k
  }
61
62
  BranchProbabilityInfo(BranchProbabilityInfo &&Arg)
63
      : Probs(std::move(Arg.Probs)), LastF(Arg.LastF),
64
        PostDominatedByUnreachable(std::move(Arg.PostDominatedByUnreachable)),
65
2.05k
        PostDominatedByColdCall(std::move(Arg.PostDominatedByColdCall)) {}
66
67
  BranchProbabilityInfo(const BranchProbabilityInfo &) = delete;
68
  BranchProbabilityInfo &operator=(const BranchProbabilityInfo &) = delete;
69
70
0
  BranchProbabilityInfo &operator=(BranchProbabilityInfo &&RHS) {
71
0
    releaseMemory();
72
0
    Probs = std::move(RHS.Probs);
73
0
    PostDominatedByColdCall = std::move(RHS.PostDominatedByColdCall);
74
0
    PostDominatedByUnreachable = std::move(RHS.PostDominatedByUnreachable);
75
0
    return *this;
76
0
  }
77
78
  void releaseMemory();
79
80
  void print(raw_ostream &OS) const;
81
82
  /// Get an edge's probability, relative to other out-edges of the Src.
83
  ///
84
  /// This routine provides access to the fractional probability between zero
85
  /// (0%) and one (100%) of this edge executing, relative to other edges
86
  /// leaving the 'Src' block. The returned probability is never zero, and can
87
  /// only be one if the source block has only one successor.
88
  BranchProbability getEdgeProbability(const BasicBlock *Src,
89
                                       unsigned IndexInSuccessors) const;
90
91
  /// Get the probability of going from Src to Dst.
92
  ///
93
  /// It returns the sum of all probabilities for edges from Src to Dst.
94
  BranchProbability getEdgeProbability(const BasicBlock *Src,
95
                                       const BasicBlock *Dst) const;
96
97
  BranchProbability getEdgeProbability(const BasicBlock *Src,
98
                                       succ_const_iterator Dst) const;
99
100
  /// Test if an edge is hot relative to other out-edges of the Src.
101
  ///
102
  /// Check whether this edge out of the source block is 'hot'. We define hot
103
  /// as having a relative probability >= 80%.
104
  bool isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const;
105
106
  /// Retrieve the hot successor of a block if one exists.
107
  ///
108
  /// Given a basic block, look through its successors and if one exists for
109
  /// which \see isEdgeHot would return true, return that successor block.
110
  const BasicBlock *getHotSucc(const BasicBlock *BB) const;
111
112
  /// Print an edge's probability.
113
  ///
114
  /// Retrieves an edge's probability similarly to \see getEdgeProbability, but
115
  /// then prints that probability to the provided stream. That stream is then
116
  /// returned.
117
  raw_ostream &printEdgeProbability(raw_ostream &OS, const BasicBlock *Src,
118
                                    const BasicBlock *Dst) const;
119
120
  /// Set the raw edge probability for the given edge.
121
  ///
122
  /// This allows a pass to explicitly set the edge probability for an edge. It
123
  /// can be used when updating the CFG to update and preserve the branch
124
  /// probability information. Read the implementation of how these edge
125
  /// probabilities are calculated carefully before using!
126
  void setEdgeProbability(const BasicBlock *Src, unsigned IndexInSuccessors,
127
                          BranchProbability Prob);
128
129
5.50k
  static BranchProbability getBranchProbStackProtector(bool IsLikely) {
130
5.50k
    static const BranchProbability LikelyProb((1u << 20) - 1, 1u << 20);
131
5.50k
    return IsLikely ? 
LikelyProb2.75k
:
LikelyProb.getCompl()2.75k
;
132
5.50k
  }
133
134
  void calculate(const Function &F, const LoopInfo &LI,
135
                 const TargetLibraryInfo *TLI = nullptr);
136
137
  /// Forget analysis results for the given basic block.
138
  void eraseBlock(const BasicBlock *BB);
139
140
  // Use to track SCCs for handling irreducible loops.
141
  using SccMap = DenseMap<const BasicBlock *, int>;
142
  using SccHeaderMap = DenseMap<const BasicBlock *, bool>;
143
  using SccHeaderMaps = std::vector<SccHeaderMap>;
144
  struct SccInfo {
145
    SccMap SccNums;
146
    SccHeaderMaps SccHeaders;
147
  };
148
149
private:
150
  // We need to store CallbackVH's in order to correctly handle basic block
151
  // removal.
152
0
  class BasicBlockCallbackVH final : public CallbackVH {
153
    BranchProbabilityInfo *BPI;
154
155
264k
    void deleted() override {
156
264k
      assert(BPI != nullptr);
157
264k
      BPI->eraseBlock(cast<BasicBlock>(getValPtr()));
158
264k
      BPI->Handles.erase(*this);
159
264k
    }
160
161
  public:
162
    BasicBlockCallbackVH(const Value *V, BranchProbabilityInfo *BPI = nullptr)
163
56.5M
        : CallbackVH(const_cast<Value *>(V)), BPI(BPI) {}
164
  };
165
166
  DenseSet<BasicBlockCallbackVH, DenseMapInfo<Value*>> Handles;
167
168
  // Since we allow duplicate edges from one basic block to another, we use
169
  // a pair (PredBlock and an index in the successors) to specify an edge.
170
  using Edge = std::pair<const BasicBlock *, unsigned>;
171
172
  // Default weight value. Used when we don't have information about the edge.
173
  // TODO: DEFAULT_WEIGHT makes sense during static predication, when none of
174
  // the successors have a weight yet. But it doesn't make sense when providing
175
  // weight to an edge that may have siblings with non-zero weights. This can
176
  // be handled various ways, but it's probably fine for an edge with unknown
177
  // weight to just "inherit" the non-zero weight of an adjacent successor.
178
  static const uint32_t DEFAULT_WEIGHT = 16;
179
180
  DenseMap<Edge, BranchProbability> Probs;
181
182
  /// Track the last function we run over for printing.
183
  const Function *LastF;
184
185
  /// Track the set of blocks directly succeeded by a returning block.
186
  SmallPtrSet<const BasicBlock *, 16> PostDominatedByUnreachable;
187
188
  /// Track the set of blocks that always lead to a cold call.
189
  SmallPtrSet<const BasicBlock *, 16> PostDominatedByColdCall;
190
191
  void updatePostDominatedByUnreachable(const BasicBlock *BB);
192
  void updatePostDominatedByColdCall(const BasicBlock *BB);
193
  bool calcUnreachableHeuristics(const BasicBlock *BB);
194
  bool calcMetadataWeights(const BasicBlock *BB);
195
  bool calcColdCallHeuristics(const BasicBlock *BB);
196
  bool calcPointerHeuristics(const BasicBlock *BB);
197
  bool calcLoopBranchHeuristics(const BasicBlock *BB, const LoopInfo &LI,
198
                                SccInfo &SccI);
199
  bool calcZeroHeuristics(const BasicBlock *BB, const TargetLibraryInfo *TLI);
200
  bool calcFloatingPointHeuristics(const BasicBlock *BB);
201
  bool calcInvokeHeuristics(const BasicBlock *BB);
202
};
203
204
/// Analysis pass which computes \c BranchProbabilityInfo.
205
class BranchProbabilityAnalysis
206
    : public AnalysisInfoMixin<BranchProbabilityAnalysis> {
207
  friend AnalysisInfoMixin<BranchProbabilityAnalysis>;
208
209
  static AnalysisKey Key;
210
211
public:
212
  /// Provide the result type for this analysis pass.
213
  using Result = BranchProbabilityInfo;
214
215
  /// Run the analysis pass over a function and produce BPI.
216
  BranchProbabilityInfo run(Function &F, FunctionAnalysisManager &AM);
217
};
218
219
/// Printer pass for the \c BranchProbabilityAnalysis results.
220
class BranchProbabilityPrinterPass
221
    : public PassInfoMixin<BranchProbabilityPrinterPass> {
222
  raw_ostream &OS;
223
224
public:
225
7
  explicit BranchProbabilityPrinterPass(raw_ostream &OS) : OS(OS) {}
226
227
  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
228
};
229
230
/// Legacy analysis pass which computes \c BranchProbabilityInfo.
231
class BranchProbabilityInfoWrapperPass : public FunctionPass {
232
  BranchProbabilityInfo BPI;
233
234
public:
235
  static char ID;
236
237
141k
  BranchProbabilityInfoWrapperPass() : FunctionPass(ID) {
238
141k
    initializeBranchProbabilityInfoWrapperPassPass(
239
141k
        *PassRegistry::getPassRegistry());
240
141k
  }
241
242
2.00M
  BranchProbabilityInfo &getBPI() { return BPI; }
243
0
  const BranchProbabilityInfo &getBPI() const { return BPI; }
244
245
  void getAnalysisUsage(AnalysisUsage &AU) const override;
246
  bool runOnFunction(Function &F) override;
247
  void releaseMemory() override;
248
  void print(raw_ostream &OS, const Module *M = nullptr) const override;
249
};
250
251
} // end namespace llvm
252
253
#endif // LLVM_ANALYSIS_BRANCHPROBABILITYINFO_H