Line data Source code
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 521781 : BranchProbabilityInfo() = default;
56 :
57 198709 : BranchProbabilityInfo(const Function &F, const LoopInfo &LI,
58 198709 : const TargetLibraryInfo *TLI = nullptr) {
59 198709 : calculate(F, LI, TLI);
60 198709 : }
61 :
62 2178 : BranchProbabilityInfo(BranchProbabilityInfo &&Arg)
63 2178 : : Probs(std::move(Arg.Probs)), LastF(Arg.LastF),
64 : PostDominatedByUnreachable(std::move(Arg.PostDominatedByUnreachable)),
65 2178 : PostDominatedByColdCall(std::move(Arg.PostDominatedByColdCall)) {}
66 :
67 : BranchProbabilityInfo(const BranchProbabilityInfo &) = delete;
68 : BranchProbabilityInfo &operator=(const BranchProbabilityInfo &) = delete;
69 :
70 : BranchProbabilityInfo &operator=(BranchProbabilityInfo &&RHS) {
71 : releaseMemory();
72 : Probs = std::move(RHS.Probs);
73 : PostDominatedByColdCall = std::move(RHS.PostDominatedByColdCall);
74 : PostDominatedByUnreachable = std::move(RHS.PostDominatedByUnreachable);
75 : return *this;
76 : }
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 2454 : static BranchProbability getBranchProbStackProtector(bool IsLikely) {
130 2454 : static const BranchProbability LikelyProb((1u << 20) - 1, 1u << 20);
131 2454 : return IsLikely ? LikelyProb : LikelyProb.getCompl();
132 : }
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 697895 : 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 9210241 : class BasicBlockCallbackVH final : public CallbackVH {
153 : BranchProbabilityInfo *BPI;
154 :
155 18857 : void deleted() override {
156 : assert(BPI != nullptr);
157 18857 : BPI->eraseBlock(cast<BasicBlock>(getValPtr()));
158 18857 : BPI->Handles.erase(*this);
159 18857 : }
160 :
161 : public:
162 : BasicBlockCallbackVH(const Value *V, BranchProbabilityInfo *BPI = nullptr)
163 7101139 : : 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 103742 : BranchProbabilityInfoWrapperPass() : FunctionPass(ID) {
238 51871 : initializeBranchProbabilityInfoWrapperPassPass(
239 51871 : *PassRegistry::getPassRegistry());
240 51871 : }
241 :
242 485237 : BranchProbabilityInfo &getBPI() { return BPI; }
243 : 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
|
