LLVM 18.0.0git
Go to the documentation of this file.
1//===- BlockFrequencyInfo.cpp - Block Frequency Analysis ------------------===//
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
9// Loops should be simplified before this analysis.
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>
31using namespace llvm;
33#define DEBUG_TYPE "block-freq"
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.")));
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."));
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."));
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.")));
82 "print-bfi", cl::init(false), cl::Hidden,
83 cl::desc("Print the block frequency info."));
86 "print-bfi-func-name", cl::Hidden,
87 cl::desc("The option to specify the name of the function "
88 "whose block frequency info is printed."));
89} // namespace llvm
91namespace llvm {
95 return GVDT_Count;
99template <>
101 using NodeRef = const BasicBlock *;
106 return &G->getFunction()->front();
107 }
110 return succ_begin(N);
111 }
113 static ChildIteratorType child_end(const NodeRef N) { return succ_end(N); }
116 return nodes_iterator(G->getFunction()->begin());
117 }
120 return nodes_iterator(G->getFunction()->end());
121 }
127template <>
129 explicit DOTGraphTraits(bool isSimple = false)
132 std::string getNodeLabel(const BasicBlock *Node,
133 const BlockFrequencyInfo *Graph) {
135 return BFIDOTGTraitsBase::getNodeLabel(Node, Graph, getGVDT());
136 }
138 std::string getNodeAttributes(const BasicBlock *Node,
139 const BlockFrequencyInfo *Graph) {
140 return BFIDOTGTraitsBase::getNodeAttributes(Node, Graph,
142 }
144 std::string getEdgeAttributes(const BasicBlock *Node, EdgeIter EI,
145 const BlockFrequencyInfo *BFI) {
146 return BFIDOTGTraitsBase::getEdgeAttributes(Node, EI, BFI, BFI->getBPI(),
148 }
151} // end namespace llvm
156 const BranchProbabilityInfo &BPI,
157 const LoopInfo &LI) {
158 calculate(F, BPI, LI);
162 : BFI(std::move(Arg.BFI)) {}
166 BFI = std::move(RHS.BFI);
167 return *this;
170// Explicitly define the default constructor otherwise it would be implicitly
171// defined at the first ODR-use which is the BFI member in the
172// LazyBlockFrequencyInfo header. The dtor needs the BlockFrequencyInfoImpl
173// template instantiated which is not available in the header.
178 // Check whether the analysis, all analyses on functions, or the function's
179 // CFG have been preserved.
180 auto PAC = PA.getChecker<BlockFrequencyAnalysis>();
181 return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
182 PAC.preservedSet<CFGAnalyses>());
186 const BranchProbabilityInfo &BPI,
187 const LoopInfo &LI) {
188 if (!BFI)
189 BFI.reset(new ImplType);
190 BFI->calculate(F, BPI, LI);
192 (ViewBlockFreqFuncName.empty() ||
193 F.getName().equals(ViewBlockFreqFuncName))) {
194 view();
195 }
196 if (PrintBlockFreq &&
197 (PrintBlockFreqFuncName.empty() ||
198 F.getName().equals(PrintBlockFreqFuncName))) {
199 print(dbgs());
200 }
204 return BFI ? BFI->getBlockFreq(BB) : 0;
209 bool AllowSynthetic) const {
210 if (!BFI)
211 return std::nullopt;
213 return BFI->getBlockProfileCount(*getFunction(), BB, AllowSynthetic);
218 if (!BFI)
219 return std::nullopt;
220 return BFI->getProfileCountFromFreq(*getFunction(), Freq);
224 assert(BFI && "Expected analysis to be available");
225 return BFI->isIrrLoopHeader(BB);
229 assert(BFI && "Expected analysis to be available");
230 BFI->setBlockFreq(BB, Freq);
234 const BasicBlock *ReferenceBB, uint64_t Freq,
235 SmallPtrSetImpl<BasicBlock *> &BlocksToScale) {
236 assert(BFI && "Expected analysis to be available");
237 // Use 128 bits APInt to avoid overflow.
238 APInt NewFreq(128, Freq);
239 APInt OldFreq(128, BFI->getBlockFreq(ReferenceBB).getFrequency());
240 APInt BBFreq(128, 0);
241 for (auto *BB : BlocksToScale) {
242 BBFreq = BFI->getBlockFreq(BB).getFrequency();
243 // Multiply first by NewFreq and then divide by OldFreq
244 // to minimize loss of precision.
245 BBFreq *= NewFreq;
246 // udiv is an expensive operation in the general case. If this ends up being
247 // a hot spot, one of the options proposed in
248 // https://reviews.llvm.org/D28535#650071 could be used to avoid this.
249 BBFreq = BBFreq.udiv(OldFreq);
250 BFI->setBlockFreq(BB, BBFreq.getLimitedValue());
251 }
252 BFI->setBlockFreq(ReferenceBB, Freq);
255/// Pop up a ghostview window with the current block frequency propagation
256/// rendered using dot.
258 ViewGraph(const_cast<BlockFrequencyInfo *>(this), title);
262 return BFI ? BFI->getFunction() : nullptr;
266 return BFI ? &BFI->getBPI() : nullptr;
270printBlockFreq(raw_ostream &OS, const BlockFrequency Freq) const {
271 return BFI ? BFI->printBlockFreq(OS, Freq) : OS;
276 const BasicBlock *BB) const {
277 return BFI ? BFI->printBlockFreq(OS, BB) : OS;
281 return BFI ? BFI->getEntryFreq() : 0;
287 if (BFI)
288 BFI->print(OS);
292 if (BFI)
293 BFI->verifyMatch(*Other.BFI);
297 "Block Frequency Analysis", true, true)
301 "Block Frequency Analysis", true, true)
306 : FunctionPass(ID) {
313 const Module *) const {
314 BFI.print(OS);
320 AU.setPreservesAll();
327 getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
328 LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
329 BFI.calculate(F, BPI, LI);
330 return false;
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;
345 OS << "Printing analysis results of BFI for function "
346 << "'" << F.getName() << "':"
347 << "\n";
349 return PreservedAnalyses::all();
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
Definition: CommandLine.h:680
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.
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
APInt udiv(const APInt &RHS) const
Unsigned division operation.
Definition: APInt.cpp:1579
uint64_t getLimitedValue(uint64_t Limit=UINT64_MAX) const
If this value is smaller than the specified limit, return it, otherwise return the limit value.
Definition: APInt.h:453
This templated class represents "all analyses that operate over <a particular IR unit>" (e....
Definition: PassManager.h:90
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:661
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:620
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:774
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:56
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.
raw_ostream & printBlockFreq(raw_ostream &OS, const BlockFrequency Freq) const
const Function * getFunction() const
void setBlockFreq(const BasicBlock *BB, uint64_t Freq)
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 setBlockFreqAndScale(const BasicBlock *ReferenceBB, uint64_t Freq, SmallPtrSetImpl< BasicBlock * > &BlocksToScale)
Set the frequency of ReferenceBB to Freq and scale the frequencies of the blocks in BlocksToScale suc...
void view(StringRef="BlockFrequencyDAGs") const
Pop up a ghostview window with the current block frequency propagation rendered using dot.
std::optional< uint64_t > getProfileCountFromFreq(uint64_t Freq) const
Returns the estimated profile count of Freq.
const BranchProbabilityInfo * getBPI() 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)
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: PassManager.h:113
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:569
The legacy pass manager's analysis pass to compute loop information.
Definition: LoopInfo.h:594
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: PassManager.h:152
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
Definition: PassManager.h:310
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:345
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:705
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:445
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:102
static GVDAGType getGVDT()
static cl::opt< bool > PrintBlockFreq("print-bfi", cl::init(false), cl::Hidden, cl::desc("Print the block frequency info."))
cl::opt< std::string > PrintBlockFreqFuncName("print-bfi-func-name", cl::Hidden, cl::desc("The option to specify the name of the function " "whose block frequency info is printed."))
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."))
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."))
Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr)
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:1854
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: PassManager.h:69
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)