Coverage Report

Created: 2017-10-03 07:32

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/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
/// \brief 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
7.50M
  BranchProbabilityInfo() = default;
56
57
  BranchProbabilityInfo(const Function &F, const LoopInfo &LI,
58
583
                        const TargetLibraryInfo *TLI = nullptr) {
59
583
    calculate(F, LI, TLI);
60
583
  }
61
62
  BranchProbabilityInfo(BranchProbabilityInfo &&Arg)
63
      : Probs(std::move(Arg.Probs)), LastF(Arg.LastF),
64
        PostDominatedByUnreachable(std::move(Arg.PostDominatedByUnreachable)),
65
0
        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
  /// \brief 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
  /// \brief 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
  /// \brief 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
  /// \brief 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
  /// \brief 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
  /// \brief 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
7.30k
  static BranchProbability getBranchProbStackProtector(bool IsLikely) {
130
7.30k
    static const BranchProbability LikelyProb((1u << 20) - 1, 1u << 20);
131
7.30k
    return IsLikely ? 
LikelyProb3.65k
:
LikelyProb.getCompl()3.65k
;
132
7.30k
  }
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
private:
141
  // We need to store CallbackVH's in order to correctly handle basic block
142
  // removal.
143
  class BasicBlockCallbackVH final : public CallbackVH {
144
    BranchProbabilityInfo *BPI;
145
146
202k
    void deleted() override {
147
202k
      assert(BPI != nullptr);
148
202k
      BPI->eraseBlock(cast<BasicBlock>(getValPtr()));
149
202k
      BPI->Handles.erase(*this);
150
202k
    }
151
152
  public:
153
    BasicBlockCallbackVH(const Value *V, BranchProbabilityInfo *BPI = nullptr)
154
72.5M
        : CallbackVH(const_cast<Value *>(V)), BPI(BPI) {}
155
  };
156
157
  DenseSet<BasicBlockCallbackVH, DenseMapInfo<Value*>> Handles;
158
159
  // Since we allow duplicate edges from one basic block to another, we use
160
  // a pair (PredBlock and an index in the successors) to specify an edge.
161
  using Edge = std::pair<const BasicBlock *, unsigned>;
162
163
  // Default weight value. Used when we don't have information about the edge.
164
  // TODO: DEFAULT_WEIGHT makes sense during static predication, when none of
165
  // the successors have a weight yet. But it doesn't make sense when providing
166
  // weight to an edge that may have siblings with non-zero weights. This can
167
  // be handled various ways, but it's probably fine for an edge with unknown
168
  // weight to just "inherit" the non-zero weight of an adjacent successor.
169
  static const uint32_t DEFAULT_WEIGHT = 16;
170
171
  DenseMap<Edge, BranchProbability> Probs;
172
173
  /// \brief Track the last function we run over for printing.
174
  const Function *LastF;
175
176
  /// \brief Track the set of blocks directly succeeded by a returning block.
177
  SmallPtrSet<const BasicBlock *, 16> PostDominatedByUnreachable;
178
179
  /// \brief Track the set of blocks that always lead to a cold call.
180
  SmallPtrSet<const BasicBlock *, 16> PostDominatedByColdCall;
181
182
  void updatePostDominatedByUnreachable(const BasicBlock *BB);
183
  void updatePostDominatedByColdCall(const BasicBlock *BB);
184
  bool calcUnreachableHeuristics(const BasicBlock *BB);
185
  bool calcMetadataWeights(const BasicBlock *BB);
186
  bool calcColdCallHeuristics(const BasicBlock *BB);
187
  bool calcPointerHeuristics(const BasicBlock *BB);
188
  bool calcLoopBranchHeuristics(const BasicBlock *BB, const LoopInfo &LI);
189
  bool calcZeroHeuristics(const BasicBlock *BB, const TargetLibraryInfo *TLI);
190
  bool calcFloatingPointHeuristics(const BasicBlock *BB);
191
  bool calcInvokeHeuristics(const BasicBlock *BB);
192
};
193
194
/// \brief Analysis pass which computes \c BranchProbabilityInfo.
195
class BranchProbabilityAnalysis
196
    : public AnalysisInfoMixin<BranchProbabilityAnalysis> {
197
  friend AnalysisInfoMixin<BranchProbabilityAnalysis>;
198
199
  static AnalysisKey Key;
200
201
public:
202
  /// \brief Provide the result type for this analysis pass.
203
  using Result = BranchProbabilityInfo;
204
205
  /// \brief Run the analysis pass over a function and produce BPI.
206
  BranchProbabilityInfo run(Function &F, FunctionAnalysisManager &AM);
207
};
208
209
/// \brief Printer pass for the \c BranchProbabilityAnalysis results.
210
class BranchProbabilityPrinterPass
211
    : public PassInfoMixin<BranchProbabilityPrinterPass> {
212
  raw_ostream &OS;
213
214
public:
215
0
  explicit BranchProbabilityPrinterPass(raw_ostream &OS) : OS(OS) {}
216
217
  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
218
};
219
220
/// \brief Legacy analysis pass which computes \c BranchProbabilityInfo.
221
class BranchProbabilityInfoWrapperPass : public FunctionPass {
222
  BranchProbabilityInfo BPI;
223
224
public:
225
  static char ID;
226
227
134k
  BranchProbabilityInfoWrapperPass() : FunctionPass(ID) {
228
134k
    initializeBranchProbabilityInfoWrapperPassPass(
229
134k
        *PassRegistry::getPassRegistry());
230
134k
  }
231
232
2.91M
  BranchProbabilityInfo &getBPI() { return BPI; }
233
0
  const BranchProbabilityInfo &getBPI() const { return BPI; }
234
235
  void getAnalysisUsage(AnalysisUsage &AU) const override;
236
  bool runOnFunction(Function &F) override;
237
  void releaseMemory() override;
238
  void print(raw_ostream &OS, const Module *M = nullptr) const override;
239
};
240
241
} // end namespace llvm
242
243
#endif // LLVM_ANALYSIS_BRANCHPROBABILITYINFO_H