LLVM 19.0.0git
BlockFrequencyInfo.cpp
Go to the documentation of this file.
1//===- BlockFrequencyInfo.cpp - Block Frequency Analysis ------------------===//
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// Loops should be simplified before this analysis.
10//
11//===----------------------------------------------------------------------===//
12
14#include "llvm/ADT/APInt.h"
15#include "llvm/ADT/iterator.h"
19#include "llvm/IR/CFG.h"
20#include "llvm/IR/Function.h"
21#include "llvm/IR/PassManager.h"
23#include "llvm/Pass.h"
27#include <cassert>
28#include <optional>
29#include <string>
30
31using namespace llvm;
32
33#define DEBUG_TYPE "block-freq"
34
36 "view-block-freq-propagation-dags", cl::Hidden,
37 cl::desc("Pop up a window to show a dag displaying how block "
38 "frequencies propagation through the CFG."),
39 cl::values(clEnumValN(GVDT_None, "none", "do not display graphs."),
40 clEnumValN(GVDT_Fraction, "fraction",
41 "display a graph using the "
42 "fractional block frequency representation."),
43 clEnumValN(GVDT_Integer, "integer",
44 "display a graph using the raw "
45 "integer fractional block frequency representation."),
46 clEnumValN(GVDT_Count, "count", "display a graph using the real "
47 "profile count if available.")));
48
49namespace llvm {
51 ViewBlockFreqFuncName("view-bfi-func-name", cl::Hidden,
52 cl::desc("The option to specify "
53 "the name of the function "
54 "whose CFG will be displayed."));
55
57 ViewHotFreqPercent("view-hot-freq-percent", cl::init(10), cl::Hidden,
58 cl::desc("An integer in percent used to specify "
59 "the hot blocks/edges to be displayed "
60 "in red: a block or edge whose frequency "
61 "is no less than the max frequency of the "
62 "function multiplied by this percent."));
63
64// Command line option to turn on CFG dot or text dump after profile annotation.
66 "pgo-view-counts", cl::Hidden,
67 cl::desc("A boolean option to show CFG dag or text with "
68 "block profile counts and branch probabilities "
69 "right after PGO profile annotation step. The "
70 "profile counts are computed using branch "
71 "probabilities from the runtime profile data and "
72 "block frequency propagation algorithm. To view "
73 "the raw counts from the profile, use option "
74 "-pgo-view-raw-counts instead. To limit graph "
75 "display to only one function, use filtering option "
76 "-view-bfi-func-name."),
77 cl::values(clEnumValN(PGOVCT_None, "none", "do not show."),
78 clEnumValN(PGOVCT_Graph, "graph", "show a graph."),
79 clEnumValN(PGOVCT_Text, "text", "show in text.")));
80
81static cl::opt<bool> PrintBFI("print-bfi", cl::init(false), cl::Hidden,
82 cl::desc("Print the block frequency info."));
83
85 PrintBFIFuncName("print-bfi-func-name", cl::Hidden,
86 cl::desc("The option to specify the name of the function "
87 "whose block frequency info is printed."));
88} // namespace llvm
89
90namespace llvm {
91
94 return GVDT_Count;
96}
97
98template <>
100 using NodeRef = const BasicBlock *;
103
105 return &G->getFunction()->front();
106 }
107
109 return succ_begin(N);
110 }
111
112 static ChildIteratorType child_end(const NodeRef N) { return succ_end(N); }
113
115 return nodes_iterator(G->getFunction()->begin());
116 }
117
119 return nodes_iterator(G->getFunction()->end());
120 }
121};
122
125
126template <>
128 explicit DOTGraphTraits(bool isSimple = false)
130
131 std::string getNodeLabel(const BasicBlock *Node,
132 const BlockFrequencyInfo *Graph) {
133
134 return BFIDOTGTraitsBase::getNodeLabel(Node, Graph, getGVDT());
135 }
136
137 std::string getNodeAttributes(const BasicBlock *Node,
138 const BlockFrequencyInfo *Graph) {
139 return BFIDOTGTraitsBase::getNodeAttributes(Node, Graph,
141 }
142
143 std::string getEdgeAttributes(const BasicBlock *Node, EdgeIter EI,
144 const BlockFrequencyInfo *BFI) {
145 return BFIDOTGTraitsBase::getEdgeAttributes(Node, EI, BFI, BFI->getBPI(),
147 }
148};
149
150} // end namespace llvm
151
153
155 const BranchProbabilityInfo &BPI,
156 const LoopInfo &LI) {
157 calculate(F, BPI, LI);
158}
159
161 : BFI(std::move(Arg.BFI)) {}
162
165 BFI = std::move(RHS.BFI);
166 return *this;
167}
168
169// Explicitly define the default constructor otherwise it would be implicitly
170// defined at the first ODR-use which is the BFI member in the
171// LazyBlockFrequencyInfo header. The dtor needs the BlockFrequencyInfoImpl
172// template instantiated which is not available in the header.
174
177 // Check whether the analysis, all analyses on functions, or the function's
178 // CFG have been preserved.
179 auto PAC = PA.getChecker<BlockFrequencyAnalysis>();
180 return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
181 PAC.preservedSet<CFGAnalyses>());
182}
183
185 const BranchProbabilityInfo &BPI,
186 const LoopInfo &LI) {
187 if (!BFI)
188 BFI.reset(new ImplType);
189 BFI->calculate(F, BPI, LI);
191 (ViewBlockFreqFuncName.empty() || F.getName() == ViewBlockFreqFuncName)) {
192 view();
193 }
194 if (PrintBFI &&
195 (PrintBFIFuncName.empty() || F.getName() == PrintBFIFuncName)) {
196 print(dbgs());
197 }
198}
199
201 return BFI ? BFI->getBlockFreq(BB) : BlockFrequency(0);
202}
203
204std::optional<uint64_t>
206 bool AllowSynthetic) const {
207 if (!BFI)
208 return std::nullopt;
209
210 return BFI->getBlockProfileCount(*getFunction(), BB, AllowSynthetic);
211}
212
213std::optional<uint64_t>
215 if (!BFI)
216 return std::nullopt;
217 return BFI->getProfileCountFromFreq(*getFunction(), Freq);
218}
219
221 assert(BFI && "Expected analysis to be available");
222 return BFI->isIrrLoopHeader(BB);
223}
224
226 BlockFrequency Freq) {
227 assert(BFI && "Expected analysis to be available");
228 BFI->setBlockFreq(BB, Freq);
229}
230
232 const BasicBlock *ReferenceBB, BlockFrequency Freq,
233 SmallPtrSetImpl<BasicBlock *> &BlocksToScale) {
234 assert(BFI && "Expected analysis to be available");
235 // Use 128 bits APInt to avoid overflow.
236 APInt NewFreq(128, Freq.getFrequency());
237 APInt OldFreq(128, BFI->getBlockFreq(ReferenceBB).getFrequency());
238 APInt BBFreq(128, 0);
239 for (auto *BB : BlocksToScale) {
240 BBFreq = BFI->getBlockFreq(BB).getFrequency();
241 // Multiply first by NewFreq and then divide by OldFreq
242 // to minimize loss of precision.
243 BBFreq *= NewFreq;
244 // udiv is an expensive operation in the general case. If this ends up being
245 // a hot spot, one of the options proposed in
246 // https://reviews.llvm.org/D28535#650071 could be used to avoid this.
247 BBFreq = BBFreq.udiv(OldFreq);
248 BFI->setBlockFreq(BB, BlockFrequency(BBFreq.getLimitedValue()));
249 }
250 BFI->setBlockFreq(ReferenceBB, Freq);
251}
252
253/// Pop up a ghostview window with the current block frequency propagation
254/// rendered using dot.
256 ViewGraph(const_cast<BlockFrequencyInfo *>(this), title);
257}
258
260 return BFI ? BFI->getFunction() : nullptr;
261}
262
264 return BFI ? &BFI->getBPI() : nullptr;
265}
266
268 return BFI ? BFI->getEntryFreq() : BlockFrequency(0);
269}
270
272
274 if (BFI)
275 BFI->print(OS);
276}
277
279 if (BFI)
280 BFI->verifyMatch(*Other.BFI);
281}
282
284 BlockFrequency Freq) {
285 return Printable([&BFI, Freq](raw_ostream &OS) {
286 printRelativeBlockFreq(OS, BFI.getEntryFreq(), Freq);
287 });
288}
289
291 const BasicBlock &BB) {
292 return printBlockFreq(BFI, BFI.getBlockFreq(&BB));
293}
294
296 "Block Frequency Analysis", true, true)
300 "Block Frequency Analysis", true, true)
301
303
305 : FunctionPass(ID) {
307}
308
310
312 const Module *) const {
313 BFI.print(OS);
314}
315
319 AU.setPreservesAll();
320}
321
323
326 getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
327 LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
328 BFI.calculate(F, BPI, LI);
329 return false;
330}
331
332AnalysisKey BlockFrequencyAnalysis::Key;
335 auto &BP = AM.getResult<BranchProbabilityAnalysis>(F);
336 auto &LI = AM.getResult<LoopAnalysis>(F);
338 BFI.calculate(F, BP, LI);
339 return BFI;
340}
341
344 OS << "Printing analysis results of BFI for function "
345 << "'" << F.getName() << "':"
346 << "\n";
348 return PreservedAnalyses::all();
349}
This file implements a class to represent arbitrary precision integral constant values and operations...
basic Basic Alias true
static cl::opt< GVDAGType > ViewBlockFreqPropagationDAG("view-block-freq-propagation-dags", cl::Hidden, cl::desc("Pop up a window to show a dag displaying how block " "frequencies propagation through the CFG."), cl::values(clEnumValN(GVDT_None, "none", "do not display graphs."), clEnumValN(GVDT_Fraction, "fraction", "display a graph using the " "fractional block frequency representation."), clEnumValN(GVDT_Integer, "integer", "display a graph using the raw " "integer fractional block frequency representation."), clEnumValN(GVDT_Count, "count", "display a graph using the real " "profile count if available.")))
block freq
block Block Frequency Analysis
#define clEnumValN(ENUMVAL, FLAGNAME, DESC)
Definition: CommandLine.h:693
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
#define F(x, y, z)
Definition: MD5.cpp:55
#define G(x, y, z)
Definition: MD5.cpp:56
This header defines various interfaces for pass management in LLVM.
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:55
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:59
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:52
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static bool isSimple(Instruction *I)
raw_pwrite_stream & OS
unify loop Fixup each natural loop to have a single exit block
Value * RHS
Class for arbitrary precision integers.
Definition: APInt.h:77
This templated class represents "all analyses that operate over <a particular IR unit>" (e....
Definition: Analysis.h:47
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:360
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:321
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:473
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
void setPreservesAll()
Set by analyses that do not transform their input at all.
LLVM Basic Block Representation.
Definition: BasicBlock.h:60
Analysis pass which computes BlockFrequencyInfo.
Result run(Function &F, FunctionAnalysisManager &AM)
Run the analysis pass over a function and produce BFI.
Shared implementation for block frequency analysis.
Legacy analysis pass which computes BlockFrequencyInfo.
void print(raw_ostream &OS, const Module *M) const override
print - Print out the internal state of the pass.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
bool isIrrLoopHeader(const BasicBlock *BB)
Returns true if BB is an irreducible loop header block.
void calculate(const Function &F, const BranchProbabilityInfo &BPI, const LoopInfo &LI)
calculate - compute block frequency info for the given function.
std::optional< uint64_t > getProfileCountFromFreq(BlockFrequency Freq) const
Returns the estimated profile count of Freq.
void setBlockFreq(const BasicBlock *BB, BlockFrequency Freq)
const Function * getFunction() const
std::optional< uint64_t > getBlockProfileCount(const BasicBlock *BB, bool AllowSynthetic=false) const
Returns the estimated profile count of BB.
BlockFrequencyInfo & operator=(const BlockFrequencyInfo &)=delete
void view(StringRef="BlockFrequencyDAGs") const
Pop up a ghostview window with the current block frequency propagation rendered using dot.
void setBlockFreqAndScale(const BasicBlock *ReferenceBB, BlockFrequency Freq, SmallPtrSetImpl< BasicBlock * > &BlocksToScale)
Set the frequency of ReferenceBB to Freq and scale the frequencies of the blocks in BlocksToScale suc...
const BranchProbabilityInfo * getBPI() const
BlockFrequency getEntryFreq() const
BlockFrequency getBlockFreq(const BasicBlock *BB) const
getblockFreq - Return block frequency.
void print(raw_ostream &OS) const
bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &)
Handle invalidation explicitly.
void verifyMatch(BlockFrequencyInfo &Other) const
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
uint64_t getFrequency() const
Returns the frequency as a fixpoint number scaled by the entry frequency.
Analysis pass which computes BranchProbabilityInfo.
Legacy analysis pass which computes BranchProbabilityInfo.
Analysis providing branch probability information.
Represents analyses that only rely on functions' control flow.
Definition: Analysis.h:70
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:311
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:566
The legacy pass manager's analysis pass to compute loop information.
Definition: LoopInfo.h:593
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:109
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: Analysis.h:115
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
Definition: Analysis.h:264
Simple wrapper around std::function<void(raw_ostream&)>.
Definition: Printable.h:38
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:321
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
ValuesClass values(OptsTy... Options)
Helper to build a ValuesClass by forwarding a variable number of arguments as an initializer list to ...
Definition: CommandLine.h:718
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:450
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
static GVDAGType getGVDT()
cl::opt< std::string > PrintBFIFuncName("print-bfi-func-name", cl::Hidden, cl::desc("The option to specify the name of the function " "whose block frequency info is printed."))
static cl::opt< bool > PrintBFI("print-bfi", cl::init(false), cl::Hidden, cl::desc("Print the block frequency info."))
cl::opt< unsigned > ViewHotFreqPercent("view-hot-freq-percent", cl::init(10), cl::Hidden, cl::desc("An integer in percent used to specify " "the hot blocks/edges to be displayed " "in red: a block or edge whose frequency " "is no less than the max frequency of the " "function multiplied by this percent."))
Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr)
cl::opt< std::string > ViewBlockFreqFuncName("view-bfi-func-name", cl::Hidden, cl::desc("The option to specify " "the name of the function " "whose CFG will be displayed."))
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
void initializeBlockFrequencyInfoWrapperPassPass(PassRegistry &)
RNSuccIterator< NodeRef, BlockT, RegionT > succ_begin(NodeRef Node)
@ Other
Any other memory.
cl::opt< PGOViewCountsType > PGOViewCounts("pgo-view-counts", cl::Hidden, cl::desc("A boolean option to show CFG dag or text with " "block profile counts and branch probabilities " "right after PGO profile annotation step. The " "profile counts are computed using branch " "probabilities from the runtime profile data and " "block frequency propagation algorithm. To view " "the raw counts from the profile, use option " "-pgo-view-raw-counts instead. To limit graph " "display to only one function, use filtering option " "-view-bfi-func-name."), cl::values(clEnumValN(PGOVCT_None, "none", "do not show."), clEnumValN(PGOVCT_Graph, "graph", "show a graph."), clEnumValN(PGOVCT_Text, "text", "show in text.")))
RNSuccIterator< NodeRef, BlockT, RegionT > succ_end(NodeRef Node)
void ViewGraph(const GraphType &G, const Twine &Name, bool ShortNames=false, const Twine &Title="", GraphProgram::Name Program=GraphProgram::DOT)
ViewGraph - Emit a dot graph, run 'dot', run gv on the postscript file, then cleanup.
Definition: GraphWriter.h:427
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1849
void printRelativeBlockFreq(raw_ostream &OS, BlockFrequency EntryFreq, BlockFrequency Freq)
Printable printBlockFreq(const BlockFrequencyInfo &BFI, BlockFrequency Freq)
Print the block frequency Freq relative to the current functions entry frequency.
SuccIterator< const Instruction, const BasicBlock > const_succ_iterator
Definition: CFG.h:243
Implement std::hash so that hash_code can be used in STL containers.
Definition: BitVector.h:858
#define N
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: Analysis.h:26
std::string getNodeAttributes(NodeRef Node, const BlockFrequencyInfoT *Graph, unsigned HotPercentThreshold=0)
typename GTraits::ChildIteratorType EdgeIter
std::string getNodeLabel(NodeRef Node, const BlockFrequencyInfoT *Graph, GVDAGType GType, int layout_order=-1)
std::string getEdgeAttributes(NodeRef Node, EdgeIter EI, const BlockFrequencyInfoT *BFI, const BranchProbabilityInfoT *BPI, unsigned HotPercentThreshold=0)
std::string getNodeAttributes(const BasicBlock *Node, const BlockFrequencyInfo *Graph)
std::string getEdgeAttributes(const BasicBlock *Node, EdgeIter EI, const BlockFrequencyInfo *BFI)
std::string getNodeLabel(const BasicBlock *Node, const BlockFrequencyInfo *Graph)
DOTGraphTraits - Template class that can be specialized to customize how graphs are converted to 'dot...
static ChildIteratorType child_begin(const NodeRef N)
static NodeRef getEntryNode(const BlockFrequencyInfo *G)
static ChildIteratorType child_end(const NodeRef N)
static nodes_iterator nodes_end(const BlockFrequencyInfo *G)
static nodes_iterator nodes_begin(const BlockFrequencyInfo *G)