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/IR/BasicBlock.h"
17#include "llvm/IR/CFG.h"
18#include "llvm/IR/PassManager.h"
19#include "llvm/Pass.h"
20#include "llvm/Support/BranchProbability.h"
21#include "llvm/Support/Compiler.h"
22#include <cassert>
23#include <cstdint>
24#include <memory>
25#include <utility>
26
27namespace llvm {
28
29class Function;
30class Loop;
31class LoopInfo;
32class raw_ostream;
33class DominatorTree;
34class PostDominatorTree;
35class TargetLibraryInfo;
36class Value;
37
38/// Analysis providing branch probability information.
39///
40/// This is a function analysis which provides information on the relative
41/// probabilities of each "edge" in the function's CFG where such an edge is
42/// defined by a pair (PredBlock and an index in the successors). The
43/// probability of an edge from one block is always relative to the
44/// probabilities of other edges from the block. The probabilites of all edges
45/// from a block sum to exactly one (100%).
46/// We use a pair (PredBlock and an index in the successors) to uniquely
47/// identify an edge, since we can have multiple edges from Src to Dst.
48/// As an example, we can have a switch which jumps to Dst with value 0 and
49/// value 10.
50///
51/// Process of computing branch probabilities can be logically viewed as three
52/// step process:
53///
54/// First, if there is a profile information associated with the branch then
55/// it is trivially translated to branch probabilities. There is one exception
56/// from this rule though. Probabilities for edges leading to "unreachable"
57/// blocks (blocks with the estimated weight not greater than
58/// UNREACHABLE_WEIGHT) are evaluated according to static estimation and
59/// override profile information. If no branch probabilities were calculated
60/// on this step then take the next one.
61///
62/// Second, estimate absolute execution weights for each block based on
63/// statically known information. Roots of such information are "cold",
64/// "unreachable", "noreturn" and "unwind" blocks. Those blocks get their
65/// weights set to BlockExecWeight::COLD, BlockExecWeight::UNREACHABLE,
66/// BlockExecWeight::NORETURN and BlockExecWeight::UNWIND respectively. Then the
67/// weights are propagated to the other blocks up the domination line. In
68/// addition, if all successors have estimated weights set then maximum of these
69/// weights assigned to the block itself (while this is not ideal heuristic in
70/// theory it's simple and works reasonably well in most cases) and the process
71/// repeats. Once the process of weights propagation converges branch
72/// probabilities are set for all such branches that have at least one successor
73/// with the weight set. Default execution weight (BlockExecWeight::DEFAULT) is
74/// used for any successors which doesn't have its weight set. For loop back
75/// branches we use their weights scaled by loop trip count equal to
76/// 'LBH_TAKEN_WEIGHT/LBH_NOTTAKEN_WEIGHT'.
77///
78/// Here is a simple example demonstrating how the described algorithm works.
79///
80/// BB1
81/// / \
82/// v v
83/// BB2 BB3
84/// / \
85/// v v
86/// ColdBB UnreachBB
87///
88/// Initially, ColdBB is associated with COLD_WEIGHT and UnreachBB with
89/// UNREACHABLE_WEIGHT. COLD_WEIGHT is set to BB2 as maximum between its
90/// successors. BB1 and BB3 has no explicit estimated weights and assumed to
91/// have DEFAULT_WEIGHT. Based on assigned weights branches will have the
92/// following probabilities:
93/// P(BB1->BB2) = COLD_WEIGHT/(COLD_WEIGHT + DEFAULT_WEIGHT) =
94/// 0xffff / (0xffff + 0xfffff) = 0.0588(5.9%)
95/// P(BB1->BB3) = DEFAULT_WEIGHT_WEIGHT/(COLD_WEIGHT + DEFAULT_WEIGHT) =
96/// 0xfffff / (0xffff + 0xfffff) = 0.941(94.1%)
97/// P(BB2->ColdBB) = COLD_WEIGHT/(COLD_WEIGHT + UNREACHABLE_WEIGHT) = 1(100%)
98/// P(BB2->UnreachBB) =
99/// UNREACHABLE_WEIGHT/(COLD_WEIGHT+UNREACHABLE_WEIGHT) = 0(0%)
100///
101/// If no branch probabilities were calculated on this step then take the next
102/// one.
103///
104/// Third, apply different kinds of local heuristics for each individual
105/// branch until first match. For example probability of a pointer to be null is
106/// estimated as PH_TAKEN_WEIGHT/(PH_TAKEN_WEIGHT + PH_NONTAKEN_WEIGHT). If
107/// no local heuristic has been matched then branch is left with no explicit
108/// probability set and assumed to have default probability.
109class BranchProbabilityInfo {
110public:
111 BranchProbabilityInfo() = default;
112
113 BranchProbabilityInfo(const Function &F, const LoopInfo &LI,
114 const TargetLibraryInfo *TLI = nullptr,
115 DominatorTree *DT = nullptr,
116 PostDominatorTree *PDT = nullptr) {
117 calculate(F, LI, TLI, DT, PDT);
118 }
119
120 LLVM_ABI bool invalidate(Function &, const PreservedAnalyses &PA,
121 FunctionAnalysisManager::Invalidator &);
122
123 LLVM_ABI void print(raw_ostream &OS) const;
124
125 /// Get an edge's probability, relative to other out-edges of the Src.
126 ///
127 /// This routine provides access to the fractional probability between zero
128 /// (0%) and one (100%) of this edge executing, relative to other edges
129 /// leaving the 'Src' block. The returned probability is never zero, and can
130 /// only be one if the source block has only one successor.
131 LLVM_ABI BranchProbability
132 getEdgeProbability(const BasicBlock *Src, unsigned IndexInSuccessors) const;
133
134 /// Get the probability of going from Src to Dst.
135 ///
136 /// It returns the sum of all probabilities for edges from Src to Dst.
137 LLVM_ABI BranchProbability getEdgeProbability(const BasicBlock *Src,
138 const BasicBlock *Dst) const;
139
140 LLVM_ABI BranchProbability getEdgeProbability(const BasicBlock *Src,
141 const_succ_iterator Dst) const;
142
143 /// Test if an edge is hot relative to other out-edges of the Src.
144 ///
145 /// Check whether this edge out of the source block is 'hot'. We define hot
146 /// as having a relative probability > 80%.
147 LLVM_ABI bool isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const;
148
149 /// Print an edge's probability.
150 ///
151 /// Retrieves an edge's probability similarly to \see getEdgeProbability, but
152 /// then prints that probability to the provided stream. That stream is then
153 /// returned.
154 LLVM_ABI raw_ostream &printEdgeProbability(raw_ostream &OS,
155 const BasicBlock *Src,
156 const BasicBlock *Dst) const;
157
158 /// Set the raw probabilities for all edges from the given block.
159 ///
160 /// This allows a pass to explicitly set edge probabilities for a block. It
161 /// can be used when updating the CFG to update the branch probability
162 /// information.
163 LLVM_ABI void
164 setEdgeProbability(const BasicBlock *Src,
165 const SmallVectorImpl<BranchProbability> &Probs);
166
167 /// Copy outgoing edge probabilities from \p Src to \p Dst.
168 ///
169 /// This allows to keep probabilities unset for the destination if they were
170 /// unset for source.
171 LLVM_ABI void copyEdgeProbabilities(BasicBlock *Src, BasicBlock *Dst);
172
173 /// Swap outgoing edges probabilities for \p Src with branch terminator
174 LLVM_ABI void swapSuccEdgesProbabilities(const BasicBlock *Src);
175
176 static BranchProbability getBranchProbStackProtector(bool IsLikely) {
177 static const BranchProbability LikelyProb((1u << 20) - 1, 1u << 20);
178 return IsLikely ? LikelyProb : LikelyProb.getCompl();
179 }
180
181 LLVM_ABI void calculate(const Function &F, const LoopInfo &LI,
182 const TargetLibraryInfo *TLI, DominatorTree *DT,
183 PostDominatorTree *PDT);
184
185 /// Forget analysis results for the given basic block.
186 LLVM_ABI void eraseBlock(const BasicBlock *BB);
187
188private:
189 MutableArrayRef<BranchProbability> allocEdges(const BasicBlock *BB);
190 ArrayRef<BranchProbability> getEdges(const BasicBlock *BB) const;
191
192 // Storage for branch probabilities.
193 SmallVector<BranchProbability> Probs;
194 // Map from block number to first edge.
195 SmallVector<unsigned> EdgeStarts;
196
197 /// Track the last function we run over for printing.
198 const Function *LastF = nullptr;
199 unsigned BlockNumberEpoch;
200};
201
202/// Analysis pass which computes \c BranchProbabilityInfo.
203class BranchProbabilityAnalysis
204 : public AnalysisInfoMixin<BranchProbabilityAnalysis> {
205 friend AnalysisInfoMixin<BranchProbabilityAnalysis>;
206
207 LLVM_ABI static AnalysisKey Key;
208
209public:
210 /// Provide the result type for this analysis pass.
211 using Result = BranchProbabilityInfo;
212
213 /// Run the analysis pass over a function and produce BPI.
214 LLVM_ABI BranchProbabilityInfo run(Function &F, FunctionAnalysisManager &AM);
215};
216
217/// Printer pass for the \c BranchProbabilityAnalysis results.
218class BranchProbabilityPrinterPass
219 : public PassInfoMixin<BranchProbabilityPrinterPass> {
220 raw_ostream &OS;
221
222public:
223 explicit BranchProbabilityPrinterPass(raw_ostream &OS) : OS(OS) {}
224
225 LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
226
227 static bool isRequired() { return true; }
228};
229
230/// Legacy analysis pass which computes \c BranchProbabilityInfo.
231class LLVM_ABI BranchProbabilityInfoWrapperPass : public FunctionPass {
232 BranchProbabilityInfo BPI;
233
234public:
235 static char ID;
236
237 BranchProbabilityInfoWrapperPass();
238
239 BranchProbabilityInfo &getBPI() { return BPI; }
240 const BranchProbabilityInfo &getBPI() const { return BPI; }
241
242 void getAnalysisUsage(AnalysisUsage &AU) const override;
243 bool runOnFunction(Function &F) override;
244 void print(raw_ostream &OS, const Module *M = nullptr) const override;
245};
246
247} // end namespace llvm
248
249#endif // LLVM_ANALYSIS_BRANCHPROBABILITYINFO_H
250