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