LLVM 19.0.0git
MachineBlockFrequencyInfo.cpp
Go to the documentation of this file.
1//===- MachineBlockFrequencyInfo.cpp - MBB 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/DenseMap.h"
15#include "llvm/ADT/iterator.h"
22#include "llvm/Pass.h"
25#include <optional>
26#include <string>
27
28using namespace llvm;
29
30#define DEBUG_TYPE "machine-block-freq"
31
32namespace llvm {
34 "view-machine-block-freq-propagation-dags", cl::Hidden,
35 cl::desc("Pop up a window to show a dag displaying how machine block "
36 "frequencies propagate through the CFG."),
37 cl::values(clEnumValN(GVDT_None, "none", "do not display graphs."),
38 clEnumValN(GVDT_Fraction, "fraction",
39 "display a graph using the "
40 "fractional block frequency representation."),
41 clEnumValN(GVDT_Integer, "integer",
42 "display a graph using the raw "
43 "integer fractional block frequency representation."),
44 clEnumValN(GVDT_Count, "count", "display a graph using the real "
45 "profile count if available.")));
46
47// Similar option above, but used to control BFI display only after MBP pass
49 "view-block-layout-with-bfi", cl::Hidden,
51 "Pop up a window to show a dag displaying MBP layout and associated "
52 "block frequencies of the CFG."),
53 cl::values(clEnumValN(GVDT_None, "none", "do not display graphs."),
54 clEnumValN(GVDT_Fraction, "fraction",
55 "display a graph using the "
56 "fractional block frequency representation."),
57 clEnumValN(GVDT_Integer, "integer",
58 "display a graph using the raw "
59 "integer fractional block frequency representation."),
60 clEnumValN(GVDT_Count, "count",
61 "display a graph using the real "
62 "profile count if available.")));
63
64// Command line option to specify the name of the function for CFG dump
65// Defined in Analysis/BlockFrequencyInfo.cpp: -view-bfi-func-name=
67
68// Command line option to specify hot frequency threshold.
69// Defined in Analysis/BlockFrequencyInfo.cpp: -view-hot-freq-perc=
71
73 "print-machine-bfi", cl::init(false), cl::Hidden,
74 cl::desc("Print the machine block frequency info."));
75
76// Command line option to specify the name of the function for block frequency
77// dump. Defined in Analysis/BlockFrequencyInfo.cpp.
79} // namespace llvm
80
84
86}
87
88namespace llvm {
89
91 using NodeRef = const MachineBasicBlock *;
94
96 return &G->getFunction()->front();
97 }
98
100 return N->succ_begin();
101 }
102
103 static ChildIteratorType child_end(const NodeRef N) { return N->succ_end(); }
104
106 return nodes_iterator(G->getFunction()->begin());
107 }
108
110 return nodes_iterator(G->getFunction()->end());
111 }
112};
113
117
118template <>
120 : public MBFIDOTGraphTraitsBase {
121 const MachineFunction *CurFunc = nullptr;
123
124 explicit DOTGraphTraits(bool isSimple = false)
126
127 std::string getNodeLabel(const MachineBasicBlock *Node,
128 const MachineBlockFrequencyInfo *Graph) {
129 int layout_order = -1;
130 // Attach additional ordering information if 'isSimple' is false.
131 if (!isSimple()) {
132 const MachineFunction *F = Node->getParent();
133 if (!CurFunc || F != CurFunc) {
134 if (CurFunc)
135 LayoutOrderMap.clear();
136
137 CurFunc = F;
138 int O = 0;
139 for (auto MBI = F->begin(); MBI != F->end(); ++MBI, ++O) {
140 LayoutOrderMap[&*MBI] = O;
141 }
142 }
143 layout_order = LayoutOrderMap[Node];
144 }
145 return MBFIDOTGraphTraitsBase::getNodeLabel(Node, Graph, getGVDT(),
146 layout_order);
147 }
148
149 std::string getNodeAttributes(const MachineBasicBlock *Node,
150 const MachineBlockFrequencyInfo *Graph) {
153 }
154
155 std::string getEdgeAttributes(const MachineBasicBlock *Node, EdgeIter EI,
156 const MachineBlockFrequencyInfo *MBFI) {
158 Node, EI, MBFI, MBFI->getMBPI(), ViewHotFreqPercent);
159 }
160};
161
162} // end namespace llvm
163
165 "Machine Block Frequency Analysis", true, true)
170
172
176}
177
182 calculate(F, MBPI, MLI);
183}
184
186
190 AU.setPreservesAll();
192}
193
196 const MachineLoopInfo &MLI) {
197 if (!MBFI)
198 MBFI.reset(new ImplType);
199 MBFI->calculate(F, MBPI, MLI);
201 (ViewBlockFreqFuncName.empty() ||
202 F.getName().equals(ViewBlockFreqFuncName))) {
203 view("MachineBlockFrequencyDAGS." + F.getName());
204 }
206 (PrintBFIFuncName.empty() || F.getName().equals(PrintBFIFuncName))) {
207 MBFI->print(dbgs());
208 }
209}
210
213 getAnalysis<MachineBranchProbabilityInfo>();
214 MachineLoopInfo &MLI = getAnalysis<MachineLoopInfo>();
215 calculate(F, MBPI, MLI);
216 return false;
217}
218
220
221/// Pop up a ghostview window with the current block frequency propagation
222/// rendered using dot.
224 // This code is only for debugging.
225 ViewGraph(const_cast<MachineBlockFrequencyInfo *>(this), Name, isSimple);
226}
227
230 return MBFI ? MBFI->getBlockFreq(MBB) : BlockFrequency(0);
231}
232
234 const MachineBasicBlock *MBB) const {
235 if (!MBFI)
236 return std::nullopt;
237
238 const Function &F = MBFI->getFunction()->getFunction();
239 return MBFI->getBlockProfileCount(F, MBB);
240}
241
242std::optional<uint64_t>
244 if (!MBFI)
245 return std::nullopt;
246
247 const Function &F = MBFI->getFunction()->getFunction();
248 return MBFI->getProfileCountFromFreq(F, Freq);
249}
250
252 const MachineBasicBlock *MBB) const {
253 assert(MBFI && "Expected analysis to be available");
254 return MBFI->isIrrLoopHeader(MBB);
255}
256
258 const MachineBasicBlock &NewPredecessor,
259 const MachineBasicBlock &NewSuccessor,
260 const MachineBranchProbabilityInfo &MBPI) {
261 assert(MBFI && "Expected analysis to be available");
262 auto NewSuccFreq = MBFI->getBlockFreq(&NewPredecessor) *
263 MBPI.getEdgeProbability(&NewPredecessor, &NewSuccessor);
264
265 MBFI->setBlockFreq(&NewSuccessor, NewSuccFreq);
266}
267
269 return MBFI ? MBFI->getFunction() : nullptr;
270}
271
273 return MBFI ? &MBFI->getBPI() : nullptr;
274}
275
277 return MBFI ? MBFI->getEntryFreq() : BlockFrequency(0);
278}
279
281 BlockFrequency Freq) {
282 return Printable([&MBFI, Freq](raw_ostream &OS) {
283 printBlockFreqImpl(OS, MBFI.getEntryFreq(), Freq);
284 });
285}
286
288 const MachineBasicBlock &MBB) {
289 return printBlockFreq(MBFI, MBFI.getBlockFreq(&MBB));
290}
MachineBasicBlock & MBB
COFF::MachineTypes Machine
Definition: COFFYAML.cpp:371
#define clEnumValN(ENUMVAL, FLAGNAME, DESC)
Definition: CommandLine.h:693
This file defines the DenseMap class.
std::string Name
#define F(x, y, z)
Definition: MD5.cpp:55
#define G(x, y, z)
Definition: MD5.cpp:56
static GVDAGType getGVDT()
Machine Block Frequency true
Machine Block Frequency Analysis
#define DEBUG_TYPE
#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
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
void setPreservesAll()
Set by analyses that do not transform their input at all.
Shared implementation for block frequency analysis.
std::vector< MachineBasicBlock * >::const_iterator const_succ_iterator
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
void view(const Twine &Name, bool isSimple=true) const
Pop up a ghostview window with the current block frequency propagation rendered using dot.
bool isIrrLoopHeader(const MachineBasicBlock *MBB) const
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
const MachineBranchProbabilityInfo * getMBPI() const
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
BlockFrequency getBlockFreq(const MachineBasicBlock *MBB) const
getblockFreq - Return block frequency.
void onEdgeSplit(const MachineBasicBlock &NewPredecessor, const MachineBasicBlock &NewSuccessor, const MachineBranchProbabilityInfo &MBPI)
incrementally calculate block frequencies when we split edges, to avoid full CFG traversal.
void calculate(const MachineFunction &F, const MachineBranchProbabilityInfo &MBPI, const MachineLoopInfo &MLI)
calculate - compute block frequency info for the given function.
bool runOnMachineFunction(MachineFunction &F) override
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
const MachineFunction * getFunction() const
std::optional< uint64_t > getProfileCountFromFreq(BlockFrequency Freq) const
BlockFrequency getEntryFreq() const
Divide a block's BlockFrequency::getFrequency() value by this value to obtain the entry block - relat...
std::optional< uint64_t > getBlockProfileCount(const MachineBasicBlock *MBB) const
BranchProbability getEdgeProbability(const MachineBasicBlock *Src, const MachineBasicBlock *Dst) const
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Simple wrapper around std::function<void(raw_ostream&)>.
Definition: Printable.h:38
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
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)
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."))
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."))
static cl::opt< bool > PrintMachineBlockFreq("print-machine-bfi", cl::init(false), cl::Hidden, cl::desc("Print the machine block frequency info."))
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
cl::opt< GVDAGType > ViewBlockLayoutWithBFI("view-block-layout-with-bfi", cl::Hidden, cl::desc("Pop up a window to show a dag displaying MBP layout and associated " "block frequencies of 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.")))
static cl::opt< GVDAGType > ViewMachineBlockFreqPropagationDAG("view-machine-block-freq-propagation-dags", cl::Hidden, cl::desc("Pop up a window to show a dag displaying how machine block " "frequencies propagate 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.")))
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
void initializeMachineBlockFrequencyInfoPass(PassRegistry &)
Printable printBlockFreq(const BlockFrequencyInfo &BFI, BlockFrequency Freq)
Print the block frequency Freq relative to the current functions entry frequency.
#define N
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 getEdgeAttributes(const MachineBasicBlock *Node, EdgeIter EI, const MachineBlockFrequencyInfo *MBFI)
std::string getNodeAttributes(const MachineBasicBlock *Node, const MachineBlockFrequencyInfo *Graph)
DenseMap< const MachineBasicBlock *, int > LayoutOrderMap
std::string getNodeLabel(const MachineBasicBlock *Node, const MachineBlockFrequencyInfo *Graph)
DOTGraphTraits - Template class that can be specialized to customize how graphs are converted to 'dot...
static ChildIteratorType child_begin(const NodeRef N)
static ChildIteratorType child_end(const NodeRef N)
static NodeRef getEntryNode(const MachineBlockFrequencyInfo *G)
static nodes_iterator nodes_begin(const MachineBlockFrequencyInfo *G)
MachineBasicBlock::const_succ_iterator ChildIteratorType
static nodes_iterator nodes_end(const MachineBlockFrequencyInfo *G)