1 | //===- BranchProbabilityInfo.h - Branch Probability Analysis ----*- C++ -*-===// |
2 | // |
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | // See https://llvm.org/LICENSE.txt for license information. |
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | // |
7 | //===----------------------------------------------------------------------===// |
8 | // |
9 | // This pass is used to evaluate branch probabilties. |
10 | // |
11 | //===----------------------------------------------------------------------===// |
12 | |
13 | #ifndef LLVM_ANALYSIS_BRANCHPROBABILITYINFO_H |
14 | #define LLVM_ANALYSIS_BRANCHPROBABILITYINFO_H |
15 | |
16 | #include "llvm/ADT/DenseMap.h" |
17 | #include "llvm/ADT/DenseMapInfo.h" |
18 | #include "llvm/ADT/DenseSet.h" |
19 | #include "llvm/IR/BasicBlock.h" |
20 | #include "llvm/IR/CFG.h" |
21 | #include "llvm/IR/PassManager.h" |
22 | #include "llvm/IR/ValueHandle.h" |
23 | #include "llvm/Pass.h" |
24 | #include "llvm/Support/BranchProbability.h" |
25 | #include <algorithm> |
26 | #include <cassert> |
27 | #include <cstdint> |
28 | #include <memory> |
29 | #include <utility> |
30 | |
31 | namespace llvm { |
32 | |
33 | class Function; |
34 | class Loop; |
35 | class LoopInfo; |
36 | class raw_ostream; |
37 | class DominatorTree; |
38 | class PostDominatorTree; |
39 | class TargetLibraryInfo; |
40 | class Value; |
41 | |
42 | /// Analysis providing branch probability information. |
43 | /// |
44 | /// This is a function analysis which provides information on the relative |
45 | /// probabilities of each "edge" in the function's CFG where such an edge is |
46 | /// defined by a pair (PredBlock and an index in the successors). The |
47 | /// probability of an edge from one block is always relative to the |
48 | /// probabilities of other edges from the block. The probabilites of all edges |
49 | /// from a block sum to exactly one (100%). |
50 | /// We use a pair (PredBlock and an index in the successors) to uniquely |
51 | /// identify an edge, since we can have multiple edges from Src to Dst. |
52 | /// As an example, we can have a switch which jumps to Dst with value 0 and |
53 | /// value 10. |
54 | /// |
55 | /// Process of computing branch probabilities can be logically viewed as three |
56 | /// step process: |
57 | /// |
58 | /// First, if there is a profile information associated with the branch then |
59 | /// it is trivially translated to branch probabilities. There is one exception |
60 | /// from this rule though. Probabilities for edges leading to "unreachable" |
61 | /// blocks (blocks with the estimated weight not greater than |
62 | /// UNREACHABLE_WEIGHT) are evaluated according to static estimation and |
63 | /// override profile information. If no branch probabilities were calculated |
64 | /// on this step then take the next one. |
65 | /// |
66 | /// Second, estimate absolute execution weights for each block based on |
67 | /// statically known information. Roots of such information are "cold", |
68 | /// "unreachable", "noreturn" and "unwind" blocks. Those blocks get their |
69 | /// weights set to BlockExecWeight::COLD, BlockExecWeight::UNREACHABLE, |
70 | /// BlockExecWeight::NORETURN and BlockExecWeight::UNWIND respectively. Then the |
71 | /// weights are propagated to the other blocks up the domination line. In |
72 | /// addition, if all successors have estimated weights set then maximum of these |
73 | /// weights assigned to the block itself (while this is not ideal heuristic in |
74 | /// theory it's simple and works reasonably well in most cases) and the process |
75 | /// repeats. Once the process of weights propagation converges branch |
76 | /// probabilities are set for all such branches that have at least one successor |
77 | /// with the weight set. Default execution weight (BlockExecWeight::DEFAULT) is |
78 | /// used for any successors which doesn't have its weight set. For loop back |
79 | /// branches we use their weights scaled by loop trip count equal to |
80 | /// 'LBH_TAKEN_WEIGHT/LBH_NOTTAKEN_WEIGHT'. |
81 | /// |
82 | /// Here is a simple example demonstrating how the described algorithm works. |
83 | /// |
84 | /// BB1 |
85 | /// / \ |
86 | /// v v |
87 | /// BB2 BB3 |
88 | /// / \ |
89 | /// v v |
90 | /// ColdBB UnreachBB |
91 | /// |
92 | /// Initially, ColdBB is associated with COLD_WEIGHT and UnreachBB with |
93 | /// UNREACHABLE_WEIGHT. COLD_WEIGHT is set to BB2 as maximum between its |
94 | /// successors. BB1 and BB3 has no explicit estimated weights and assumed to |
95 | /// have DEFAULT_WEIGHT. Based on assigned weights branches will have the |
96 | /// following probabilities: |
97 | /// P(BB1->BB2) = COLD_WEIGHT/(COLD_WEIGHT + DEFAULT_WEIGHT) = |
98 | /// 0xffff / (0xffff + 0xfffff) = 0.0588(5.9%) |
99 | /// P(BB1->BB3) = DEFAULT_WEIGHT_WEIGHT/(COLD_WEIGHT + DEFAULT_WEIGHT) = |
100 | /// 0xfffff / (0xffff + 0xfffff) = 0.941(94.1%) |
101 | /// P(BB2->ColdBB) = COLD_WEIGHT/(COLD_WEIGHT + UNREACHABLE_WEIGHT) = 1(100%) |
102 | /// P(BB2->UnreachBB) = |
103 | /// UNREACHABLE_WEIGHT/(COLD_WEIGHT+UNREACHABLE_WEIGHT) = 0(0%) |
104 | /// |
105 | /// If no branch probabilities were calculated on this step then take the next |
106 | /// one. |
107 | /// |
108 | /// Third, apply different kinds of local heuristics for each individual |
109 | /// branch until first match. For example probability of a pointer to be null is |
110 | /// estimated as PH_TAKEN_WEIGHT/(PH_TAKEN_WEIGHT + PH_NONTAKEN_WEIGHT). If |
111 | /// no local heuristic has been matched then branch is left with no explicit |
112 | /// probability set and assumed to have default probability. |
113 | class BranchProbabilityInfo { |
114 | public: |
115 | BranchProbabilityInfo() = default; |
116 | |
117 | BranchProbabilityInfo(const Function &F, const LoopInfo &LI, |
118 | const TargetLibraryInfo *TLI = nullptr, |
119 | DominatorTree *DT = nullptr, |
120 | PostDominatorTree *PDT = nullptr) { |
121 | calculate(F, LI, TLI, DT, PDT); |
122 | } |
123 | |
124 | BranchProbabilityInfo(BranchProbabilityInfo &&Arg) |
125 | : Handles(std::move(Arg.Handles)), Probs(std::move(Arg.Probs)), |
126 | LastF(Arg.LastF), |
127 | EstimatedBlockWeight(std::move(Arg.EstimatedBlockWeight)) { |
128 | for (auto &Handle : Handles) |
129 | Handle.setBPI(this); |
130 | } |
131 | |
132 | BranchProbabilityInfo(const BranchProbabilityInfo &) = delete; |
133 | BranchProbabilityInfo &operator=(const BranchProbabilityInfo &) = delete; |
134 | |
135 | BranchProbabilityInfo &operator=(BranchProbabilityInfo &&RHS) { |
136 | releaseMemory(); |
137 | Handles = std::move(RHS.Handles); |
138 | Probs = std::move(RHS.Probs); |
139 | EstimatedBlockWeight = std::move(RHS.EstimatedBlockWeight); |
140 | for (auto &Handle : Handles) |
141 | Handle.setBPI(this); |
142 | return *this; |
143 | } |
144 | |
145 | bool invalidate(Function &, const PreservedAnalyses &PA, |
146 | FunctionAnalysisManager::Invalidator &); |
147 | |
148 | void releaseMemory(); |
149 | |
150 | void print(raw_ostream &OS) const; |
151 | |
152 | /// Get an edge's probability, relative to other out-edges of the Src. |
153 | /// |
154 | /// This routine provides access to the fractional probability between zero |
155 | /// (0%) and one (100%) of this edge executing, relative to other edges |
156 | /// leaving the 'Src' block. The returned probability is never zero, and can |
157 | /// only be one if the source block has only one successor. |
158 | BranchProbability getEdgeProbability(const BasicBlock *Src, |
159 | unsigned IndexInSuccessors) const; |
160 | |
161 | /// Get the probability of going from Src to Dst. |
162 | /// |
163 | /// It returns the sum of all probabilities for edges from Src to Dst. |
164 | BranchProbability getEdgeProbability(const BasicBlock *Src, |
165 | const BasicBlock *Dst) const; |
166 | |
167 | BranchProbability getEdgeProbability(const BasicBlock *Src, |
168 | const_succ_iterator Dst) const; |
169 | |
170 | /// Test if an edge is hot relative to other out-edges of the Src. |
171 | /// |
172 | /// Check whether this edge out of the source block is 'hot'. We define hot |
173 | /// as having a relative probability >= 80%. |
174 | bool isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const; |
175 | |
176 | /// Print an edge's probability. |
177 | /// |
178 | /// Retrieves an edge's probability similarly to \see getEdgeProbability, but |
179 | /// then prints that probability to the provided stream. That stream is then |
180 | /// returned. |
181 | raw_ostream &printEdgeProbability(raw_ostream &OS, const BasicBlock *Src, |
182 | const BasicBlock *Dst) const; |
183 | |
184 | public: |
185 | /// Set the raw probabilities for all edges from the given block. |
186 | /// |
187 | /// This allows a pass to explicitly set edge probabilities for a block. It |
188 | /// can be used when updating the CFG to update the branch probability |
189 | /// information. |
190 | void setEdgeProbability(const BasicBlock *Src, |
191 | const SmallVectorImpl<BranchProbability> &Probs); |
192 | |
193 | /// Copy outgoing edge probabilities from \p Src to \p Dst. |
194 | /// |
195 | /// This allows to keep probabilities unset for the destination if they were |
196 | /// unset for source. |
197 | void copyEdgeProbabilities(BasicBlock *Src, BasicBlock *Dst); |
198 | |
199 | /// Swap outgoing edges probabilities for \p Src with branch terminator |
200 | void swapSuccEdgesProbabilities(const BasicBlock *Src); |
201 | |
202 | static BranchProbability getBranchProbStackProtector(bool IsLikely) { |
203 | static const BranchProbability LikelyProb((1u << 20) - 1, 1u << 20); |
204 | return IsLikely ? LikelyProb : LikelyProb.getCompl(); |
205 | } |
206 | |
207 | void calculate(const Function &F, const LoopInfo &LI, |
208 | const TargetLibraryInfo *TLI, DominatorTree *DT, |
209 | PostDominatorTree *PDT); |
210 | |
211 | /// Forget analysis results for the given basic block. |
212 | void eraseBlock(const BasicBlock *BB); |
213 | |
214 | // Data structure to track SCCs for handling irreducible loops. |
215 | class SccInfo { |
216 | // Enum of types to classify basic blocks in SCC. Basic block belonging to |
217 | // SCC is 'Inner' until it is either 'Header' or 'Exiting'. Note that a |
218 | // basic block can be 'Header' and 'Exiting' at the same time. |
219 | enum SccBlockType { |
220 | Inner = 0x0, |
221 | = 0x1, |
222 | Exiting = 0x2, |
223 | }; |
224 | // Map of basic blocks to SCC IDs they belong to. If basic block doesn't |
225 | // belong to any SCC it is not in the map. |
226 | using SccMap = DenseMap<const BasicBlock *, int>; |
227 | // Each basic block in SCC is attributed with one or several types from |
228 | // SccBlockType. Map value has uint32_t type (instead of SccBlockType) |
229 | // since basic block may be for example "Header" and "Exiting" at the same |
230 | // time and we need to be able to keep more than one value from |
231 | // SccBlockType. |
232 | using SccBlockTypeMap = DenseMap<const BasicBlock *, uint32_t>; |
233 | // Vector containing classification of basic blocks for all SCCs where i'th |
234 | // vector element corresponds to SCC with ID equal to i. |
235 | using SccBlockTypeMaps = std::vector<SccBlockTypeMap>; |
236 | |
237 | SccMap SccNums; |
238 | SccBlockTypeMaps SccBlocks; |
239 | |
240 | public: |
241 | explicit SccInfo(const Function &F); |
242 | |
243 | /// If \p BB belongs to some SCC then ID of that SCC is returned, otherwise |
244 | /// -1 is returned. If \p BB belongs to more than one SCC at the same time |
245 | /// result is undefined. |
246 | int getSCCNum(const BasicBlock *BB) const; |
247 | /// Returns true if \p BB is a 'header' block in SCC with \p SccNum ID, |
248 | /// false otherwise. |
249 | bool (const BasicBlock *BB, int SccNum) const { |
250 | return getSccBlockType(BB, SccNum) & Header; |
251 | } |
252 | /// Returns true if \p BB is an 'exiting' block in SCC with \p SccNum ID, |
253 | /// false otherwise. |
254 | bool isSCCExitingBlock(const BasicBlock *BB, int SccNum) const { |
255 | return getSccBlockType(BB, SccNum) & Exiting; |
256 | } |
257 | /// Fills in \p Enters vector with all such blocks that don't belong to |
258 | /// SCC with \p SccNum ID but there is an edge to a block belonging to the |
259 | /// SCC. |
260 | void getSccEnterBlocks(int SccNum, |
261 | SmallVectorImpl<BasicBlock *> &Enters) const; |
262 | /// Fills in \p Exits vector with all such blocks that don't belong to |
263 | /// SCC with \p SccNum ID but there is an edge from a block belonging to the |
264 | /// SCC. |
265 | void getSccExitBlocks(int SccNum, |
266 | SmallVectorImpl<BasicBlock *> &Exits) const; |
267 | |
268 | private: |
269 | /// Returns \p BB's type according to classification given by SccBlockType |
270 | /// enum. Please note that \p BB must belong to SSC with \p SccNum ID. |
271 | uint32_t getSccBlockType(const BasicBlock *BB, int SccNum) const; |
272 | /// Calculates \p BB's type and stores it in internal data structures for |
273 | /// future use. Please note that \p BB must belong to SSC with \p SccNum ID. |
274 | void calculateSccBlockType(const BasicBlock *BB, int SccNum); |
275 | }; |
276 | |
277 | private: |
278 | // We need to store CallbackVH's in order to correctly handle basic block |
279 | // removal. |
280 | class BasicBlockCallbackVH final : public CallbackVH { |
281 | BranchProbabilityInfo *BPI; |
282 | |
283 | void deleted() override { |
284 | assert(BPI != nullptr); |
285 | BPI->eraseBlock(BB: cast<BasicBlock>(Val: getValPtr())); |
286 | } |
287 | |
288 | public: |
289 | void setBPI(BranchProbabilityInfo *BPI) { this->BPI = BPI; } |
290 | |
291 | BasicBlockCallbackVH(const Value *V, BranchProbabilityInfo *BPI = nullptr) |
292 | : CallbackVH(const_cast<Value *>(V)), BPI(BPI) {} |
293 | }; |
294 | |
295 | /// Pair of Loop and SCC ID number. Used to unify handling of normal and |
296 | /// SCC based loop representations. |
297 | using LoopData = std::pair<Loop *, int>; |
298 | /// Helper class to keep basic block along with its loop data information. |
299 | class LoopBlock { |
300 | public: |
301 | explicit LoopBlock(const BasicBlock *BB, const LoopInfo &LI, |
302 | const SccInfo &SccI); |
303 | |
304 | const BasicBlock *getBlock() const { return BB; } |
305 | BasicBlock *getBlock() { return const_cast<BasicBlock *>(BB); } |
306 | LoopData getLoopData() const { return LD; } |
307 | Loop *getLoop() const { return LD.first; } |
308 | int getSccNum() const { return LD.second; } |
309 | |
310 | bool belongsToLoop() const { return getLoop() || getSccNum() != -1; } |
311 | bool belongsToSameLoop(const LoopBlock &LB) const { |
312 | return (LB.getLoop() && getLoop() == LB.getLoop()) || |
313 | (LB.getSccNum() != -1 && getSccNum() == LB.getSccNum()); |
314 | } |
315 | |
316 | private: |
317 | const BasicBlock *const BB = nullptr; |
318 | LoopData LD = {nullptr, -1}; |
319 | }; |
320 | |
321 | // Pair of LoopBlocks representing an edge from first to second block. |
322 | using LoopEdge = std::pair<const LoopBlock &, const LoopBlock &>; |
323 | |
324 | DenseSet<BasicBlockCallbackVH, DenseMapInfo<Value*>> Handles; |
325 | |
326 | // Since we allow duplicate edges from one basic block to another, we use |
327 | // a pair (PredBlock and an index in the successors) to specify an edge. |
328 | using Edge = std::pair<const BasicBlock *, unsigned>; |
329 | |
330 | DenseMap<Edge, BranchProbability> Probs; |
331 | |
332 | /// Track the last function we run over for printing. |
333 | const Function *LastF = nullptr; |
334 | |
335 | const LoopInfo *LI = nullptr; |
336 | |
337 | /// Keeps information about all SCCs in a function. |
338 | std::unique_ptr<const SccInfo> SccI; |
339 | |
340 | /// Keeps mapping of a basic block to its estimated weight. |
341 | SmallDenseMap<const BasicBlock *, uint32_t> EstimatedBlockWeight; |
342 | |
343 | /// Keeps mapping of a loop to estimated weight to enter the loop. |
344 | SmallDenseMap<LoopData, uint32_t> EstimatedLoopWeight; |
345 | |
346 | /// Helper to construct LoopBlock for \p BB. |
347 | LoopBlock getLoopBlock(const BasicBlock *BB) const { |
348 | return LoopBlock(BB, *LI, *SccI.get()); |
349 | } |
350 | |
351 | /// Returns true if destination block belongs to some loop and source block is |
352 | /// either doesn't belong to any loop or belongs to a loop which is not inner |
353 | /// relative to the destination block. |
354 | bool isLoopEnteringEdge(const LoopEdge &Edge) const; |
355 | /// Returns true if source block belongs to some loop and destination block is |
356 | /// either doesn't belong to any loop or belongs to a loop which is not inner |
357 | /// relative to the source block. |
358 | bool isLoopExitingEdge(const LoopEdge &Edge) const; |
359 | /// Returns true if \p Edge is either enters to or exits from some loop, false |
360 | /// in all other cases. |
361 | bool isLoopEnteringExitingEdge(const LoopEdge &Edge) const; |
362 | /// Returns true if source and destination blocks belongs to the same loop and |
363 | /// destination block is loop header. |
364 | bool isLoopBackEdge(const LoopEdge &Edge) const; |
365 | // Fills in \p Enters vector with all "enter" blocks to a loop \LB belongs to. |
366 | void getLoopEnterBlocks(const LoopBlock &LB, |
367 | SmallVectorImpl<BasicBlock *> &Enters) const; |
368 | // Fills in \p Exits vector with all "exit" blocks from a loop \LB belongs to. |
369 | void getLoopExitBlocks(const LoopBlock &LB, |
370 | SmallVectorImpl<BasicBlock *> &Exits) const; |
371 | |
372 | /// Returns estimated weight for \p BB. std::nullopt if \p BB has no estimated |
373 | /// weight. |
374 | std::optional<uint32_t> getEstimatedBlockWeight(const BasicBlock *BB) const; |
375 | |
376 | /// Returns estimated weight to enter \p L. In other words it is weight of |
377 | /// loop's header block not scaled by trip count. Returns std::nullopt if \p L |
378 | /// has no no estimated weight. |
379 | std::optional<uint32_t> getEstimatedLoopWeight(const LoopData &L) const; |
380 | |
381 | /// Return estimated weight for \p Edge. Returns std::nullopt if estimated |
382 | /// weight is unknown. |
383 | std::optional<uint32_t> getEstimatedEdgeWeight(const LoopEdge &Edge) const; |
384 | |
385 | /// Iterates over all edges leading from \p SrcBB to \p Successors and |
386 | /// returns maximum of all estimated weights. If at least one edge has unknown |
387 | /// estimated weight std::nullopt is returned. |
388 | template <class IterT> |
389 | std::optional<uint32_t> |
390 | getMaxEstimatedEdgeWeight(const LoopBlock &SrcBB, |
391 | iterator_range<IterT> Successors) const; |
392 | |
393 | /// If \p LoopBB has no estimated weight then set it to \p BBWeight and |
394 | /// return true. Otherwise \p BB's weight remains unchanged and false is |
395 | /// returned. In addition all blocks/loops that might need their weight to be |
396 | /// re-estimated are put into BlockWorkList/LoopWorkList. |
397 | bool updateEstimatedBlockWeight(LoopBlock &LoopBB, uint32_t BBWeight, |
398 | SmallVectorImpl<BasicBlock *> &BlockWorkList, |
399 | SmallVectorImpl<LoopBlock> &LoopWorkList); |
400 | |
401 | /// Starting from \p LoopBB (including \p LoopBB itself) propagate \p BBWeight |
402 | /// up the domination tree. |
403 | void propagateEstimatedBlockWeight(const LoopBlock &LoopBB, DominatorTree *DT, |
404 | PostDominatorTree *PDT, uint32_t BBWeight, |
405 | SmallVectorImpl<BasicBlock *> &WorkList, |
406 | SmallVectorImpl<LoopBlock> &LoopWorkList); |
407 | |
408 | /// Returns block's weight encoded in the IR. |
409 | std::optional<uint32_t> getInitialEstimatedBlockWeight(const BasicBlock *BB); |
410 | |
411 | // Computes estimated weights for all blocks in \p F. |
412 | void computeEestimateBlockWeight(const Function &F, DominatorTree *DT, |
413 | PostDominatorTree *PDT); |
414 | |
415 | /// Based on computed weights by \p computeEstimatedBlockWeight set |
416 | /// probabilities on branches. |
417 | bool calcEstimatedHeuristics(const BasicBlock *BB); |
418 | bool calcMetadataWeights(const BasicBlock *BB); |
419 | bool calcPointerHeuristics(const BasicBlock *BB); |
420 | bool calcZeroHeuristics(const BasicBlock *BB, const TargetLibraryInfo *TLI); |
421 | bool calcFloatingPointHeuristics(const BasicBlock *BB); |
422 | }; |
423 | |
424 | /// Analysis pass which computes \c BranchProbabilityInfo. |
425 | class BranchProbabilityAnalysis |
426 | : public AnalysisInfoMixin<BranchProbabilityAnalysis> { |
427 | friend AnalysisInfoMixin<BranchProbabilityAnalysis>; |
428 | |
429 | static AnalysisKey Key; |
430 | |
431 | public: |
432 | /// Provide the result type for this analysis pass. |
433 | using Result = BranchProbabilityInfo; |
434 | |
435 | /// Run the analysis pass over a function and produce BPI. |
436 | BranchProbabilityInfo run(Function &F, FunctionAnalysisManager &AM); |
437 | }; |
438 | |
439 | /// Printer pass for the \c BranchProbabilityAnalysis results. |
440 | class BranchProbabilityPrinterPass |
441 | : public PassInfoMixin<BranchProbabilityPrinterPass> { |
442 | raw_ostream &OS; |
443 | |
444 | public: |
445 | explicit BranchProbabilityPrinterPass(raw_ostream &OS) : OS(OS) {} |
446 | |
447 | PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); |
448 | |
449 | static bool isRequired() { return true; } |
450 | }; |
451 | |
452 | /// Legacy analysis pass which computes \c BranchProbabilityInfo. |
453 | class BranchProbabilityInfoWrapperPass : public FunctionPass { |
454 | BranchProbabilityInfo BPI; |
455 | |
456 | public: |
457 | static char ID; |
458 | |
459 | BranchProbabilityInfoWrapperPass(); |
460 | |
461 | BranchProbabilityInfo &getBPI() { return BPI; } |
462 | const BranchProbabilityInfo &getBPI() const { return BPI; } |
463 | |
464 | void getAnalysisUsage(AnalysisUsage &AU) const override; |
465 | bool runOnFunction(Function &F) override; |
466 | void releaseMemory() override; |
467 | void print(raw_ostream &OS, const Module *M = nullptr) const override; |
468 | }; |
469 | |
470 | } // end namespace llvm |
471 | |
472 | #endif // LLVM_ANALYSIS_BRANCHPROBABILITYINFO_H |
473 | |