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() ||
192 F.getName().equals(ViewBlockFreqFuncName))) {
193 view();
194 }
195 if (PrintBFI &&
196 (PrintBFIFuncName.empty() || F.getName().equals(PrintBFIFuncName))) {
197 print(dbgs());
198 }
199}
200
202 return BFI ? BFI->getBlockFreq(BB) : BlockFrequency(0);
203}
204
205std::optional<uint64_t>
207 bool AllowSynthetic) const {
208 if (!BFI)
209 return std::nullopt;
210
211 return BFI->getBlockProfileCount(*getFunction(), BB, AllowSynthetic);
212}
213
214std::optional<uint64_t>
216 if (!BFI)
217 return std::nullopt;
218 return BFI->getProfileCountFromFreq(*getFunction(), Freq);
219}
220
222 assert(BFI && "Expected analysis to be available");
223 return BFI->isIrrLoopHeader(BB);
224}
225
227 BlockFrequency Freq) {
228 assert(BFI && "Expected analysis to be available");
229 BFI->setBlockFreq(BB, Freq);
230}
231
233 const BasicBlock *ReferenceBB, BlockFrequency Freq,
234 SmallPtrSetImpl<BasicBlock *> &BlocksToScale) {
235 assert(BFI && "Expected analysis to be available");
236 // Use 128 bits APInt to avoid overflow.
237 APInt NewFreq(128, Freq.getFrequency());
238 APInt OldFreq(128, BFI->getBlockFreq(ReferenceBB).getFrequency());
239 APInt BBFreq(128, 0);
240 for (auto *BB : BlocksToScale) {
241 BBFreq = BFI->getBlockFreq(BB).getFrequency();
242 // Multiply first by NewFreq and then divide by OldFreq
243 // to minimize loss of precision.
244 BBFreq *= NewFreq;
245 // udiv is an expensive operation in the general case. If this ends up being
246 // a hot spot, one of the options proposed in
247 // https://reviews.llvm.org/D28535#650071 could be used to avoid this.
248 BBFreq = BBFreq.udiv(OldFreq);
249 BFI->setBlockFreq(BB, BlockFrequency(BBFreq.getLimitedValue()));
250 }
251 BFI->setBlockFreq(ReferenceBB, Freq);
252}
253
254/// Pop up a ghostview window with the current block frequency propagation
255/// rendered using dot.
257 ViewGraph(const_cast<BlockFrequencyInfo *>(this), title);
258}
259
261 return BFI ? BFI->getFunction() : nullptr;
262}
263
265 return BFI ? &BFI->getBPI() : nullptr;
266}
267
269 return BFI ? BFI->getEntryFreq() : BlockFrequency(0);
270}
271
273
275 if (BFI)
276 BFI->print(OS);
277}
278
280 if (BFI)
281 BFI->verifyMatch(*Other.BFI);
282}
283
285 BlockFrequency Freq) {
286 return Printable([&BFI, Freq](raw_ostream &OS) {
287 printBlockFreqImpl(OS, BFI.getEntryFreq(), Freq);
288 });
289}
290
292 const BasicBlock &BB) {
293 return printBlockFreq(BFI, BFI.getBlockFreq(&BB));
294}
295
297 "Block Frequency Analysis", true, true)
301 "Block Frequency Analysis", true, true)
302
304
306 : FunctionPass(ID) {
308}
309
311
313 const Module *) const {
314 BFI.print(OS);
315}
316
320 AU.setPreservesAll();
321}
322
324
327 getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
328 LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
329 BFI.calculate(F, BPI, LI);
330 return false;
331}
332
333AnalysisKey BlockFrequencyAnalysis::Key;
336 auto &BP = AM.getResult<BranchProbabilityAnalysis>(F);
337 auto &LI = AM.getResult<LoopAnalysis>(F);
339 BFI.calculate(F, BP, LI);
340 return BFI;
341}
342
345 OS << "Printing analysis results of BFI for function "
346 << "'" << F.getName() << "':"
347 << "\n";
349 return PreservedAnalyses::all();
350}
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:76
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:387
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:348
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:500
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
void printBlockFreqImpl(raw_ostream &OS, BlockFrequency EntryFreq, BlockFrequency Freq)
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:102
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."))
Interval::succ_iterator succ_begin(Interval *I)
succ_begin/succ_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:99
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 &)
@ 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.")))
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:1858
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)