/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 |