1//===-- CFGPrinter.h - CFG printer external interface -----------*- 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 file defines a 'dot-cfg' analysis pass, which emits the
10// cfg.<fnname>.dot file for each function in the program, with a graph of the
11// CFG for that function.
12//
13// This file defines external functions that can be called to explicitly
14// instantiate the CFG printer.
15//
16//===----------------------------------------------------------------------===//
17
18#ifndef LLVM_ANALYSIS_CFGPRINTER_H
19#define LLVM_ANALYSIS_CFGPRINTER_H
20
21#include "llvm/Analysis/BlockFrequencyInfo.h"
22#include "llvm/Analysis/BranchProbabilityInfo.h"
23#include "llvm/Analysis/HeatUtils.h"
24#include "llvm/IR/CFG.h"
25#include "llvm/IR/Constants.h"
26#include "llvm/IR/Function.h"
27#include "llvm/IR/Instructions.h"
28#include "llvm/IR/PassManager.h"
29#include "llvm/IR/ProfDataUtils.h"
30#include "llvm/Support/DOTGraphTraits.h"
31#include "llvm/Support/FormatVariadic.h"
32
33namespace llvm {
34template <class GraphType> struct GraphTraits;
35class CFGViewerPass : public PassInfoMixin<CFGViewerPass> {
36public:
37 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
38 static bool isRequired() { return true; }
39};
40
41class CFGOnlyViewerPass : public PassInfoMixin<CFGOnlyViewerPass> {
42public:
43 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
44 static bool isRequired() { return true; }
45};
46
47class CFGPrinterPass : public PassInfoMixin<CFGPrinterPass> {
48public:
49 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
50 static bool isRequired() { return true; }
51};
52
53class CFGOnlyPrinterPass : public PassInfoMixin<CFGOnlyPrinterPass> {
54public:
55 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
56 static bool isRequired() { return true; }
57};
58
59class DOTFuncInfo {
60private:
61 const Function *F;
62 const BlockFrequencyInfo *BFI;
63 const BranchProbabilityInfo *BPI;
64 uint64_t MaxFreq;
65 bool ShowHeat;
66 bool EdgeWeights;
67 bool RawWeights;
68
69public:
70 DOTFuncInfo(const Function *F) : DOTFuncInfo(F, nullptr, nullptr, 0) {}
71
72 DOTFuncInfo(const Function *F, const BlockFrequencyInfo *BFI,
73 const BranchProbabilityInfo *BPI, uint64_t MaxFreq)
74 : F(F), BFI(BFI), BPI(BPI), MaxFreq(MaxFreq) {
75 ShowHeat = false;
76 EdgeWeights = !!BPI; // Print EdgeWeights when BPI is available.
77 RawWeights = !!BFI; // Print RawWeights when BFI is available.
78 }
79
80 const BlockFrequencyInfo *getBFI() const { return BFI; }
81
82 const BranchProbabilityInfo *getBPI() const { return BPI; }
83
84 const Function *getFunction() const { return this->F; }
85
86 uint64_t getMaxFreq() const { return MaxFreq; }
87
88 uint64_t getFreq(const BasicBlock *BB) const {
89 return BFI->getBlockFreq(BB).getFrequency();
90 }
91
92 void setHeatColors(bool ShowHeat) { this->ShowHeat = ShowHeat; }
93
94 bool showHeatColors() { return ShowHeat; }
95
96 void setRawEdgeWeights(bool RawWeights) { this->RawWeights = RawWeights; }
97
98 bool useRawEdgeWeights() { return RawWeights; }
99
100 void setEdgeWeights(bool EdgeWeights) { this->EdgeWeights = EdgeWeights; }
101
102 bool showEdgeWeights() { return EdgeWeights; }
103};
104
105template <>
106struct GraphTraits<DOTFuncInfo *> : public GraphTraits<const BasicBlock *> {
107 static NodeRef getEntryNode(DOTFuncInfo *CFGInfo) {
108 return &(CFGInfo->getFunction()->getEntryBlock());
109 }
110
111 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
112 using nodes_iterator = pointer_iterator<Function::const_iterator>;
113
114 static nodes_iterator nodes_begin(DOTFuncInfo *CFGInfo) {
115 return nodes_iterator(CFGInfo->getFunction()->begin());
116 }
117
118 static nodes_iterator nodes_end(DOTFuncInfo *CFGInfo) {
119 return nodes_iterator(CFGInfo->getFunction()->end());
120 }
121
122 static size_t size(DOTFuncInfo *CFGInfo) {
123 return CFGInfo->getFunction()->size();
124 }
125};
126
127template <typename BasicBlockT>
128std::string SimpleNodeLabelString(const BasicBlockT *Node) {
129 if (!Node->getName().empty())
130 return Node->getName().str();
131
132 std::string Str;
133 raw_string_ostream OS(Str);
134
135 Node->printAsOperand(OS, false);
136 return OS.str();
137}
138
139template <typename BasicBlockT>
140std::string CompleteNodeLabelString(
141 const BasicBlockT *Node,
142 function_ref<void(raw_string_ostream &, const BasicBlockT &)>
143 HandleBasicBlock,
144 function_ref<void(std::string &, unsigned &, unsigned)>
145 HandleComment) {
146
147 enum { MaxColumns = 80 };
148 std::string Str;
149 raw_string_ostream OS(Str);
150 HandleBasicBlock(OS, *Node);
151 std::string OutStr = OS.str();
152 // Remove "%" from BB name
153 if (OutStr[0] == '%') {
154 OutStr.erase(position: OutStr.begin());
155 }
156 // Place | after BB name to separate it into header
157 OutStr.insert(pos: OutStr.find_first_of(c: '\n') + 1, s: "\\|");
158
159 unsigned ColNum = 0;
160 unsigned LastSpace = 0;
161 for (unsigned i = 0; i != OutStr.length(); ++i) {
162 if (OutStr[i] == '\n') { // Left justify
163 OutStr[i] = '\\';
164 OutStr.insert(p: OutStr.begin() + i + 1, c: 'l');
165 ColNum = 0;
166 LastSpace = 0;
167 } else if (OutStr[i] == ';') { // Delete comments!
168 unsigned Idx = OutStr.find(c: '\n', pos: i + 1); // Find end of line
169 HandleComment(OutStr, i, Idx);
170 } else if (ColNum == MaxColumns) { // Wrap lines.
171 // Wrap very long names even though we can't find a space.
172 if (!LastSpace)
173 LastSpace = i;
174 OutStr.insert(pos: LastSpace, s: "\\l...");
175 ColNum = i - LastSpace;
176 LastSpace = 0;
177 i += 3; // The loop will advance 'i' again.
178 } else
179 ++ColNum;
180 if (OutStr[i] == ' ')
181 LastSpace = i;
182 }
183 return OutStr;
184}
185
186template <>
187struct DOTGraphTraits<DOTFuncInfo *> : public DefaultDOTGraphTraits {
188
189 // Cache for is hidden property
190 DenseMap<const BasicBlock *, bool> isOnDeoptOrUnreachablePath;
191
192 DOTGraphTraits(bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {}
193
194 static void eraseComment(std::string &OutStr, unsigned &I, unsigned Idx) {
195 OutStr.erase(first: OutStr.begin() + I, last: OutStr.begin() + Idx);
196 --I;
197 }
198
199 static std::string getGraphName(DOTFuncInfo *CFGInfo) {
200 return "CFG for '" + CFGInfo->getFunction()->getName().str() + "' function";
201 }
202
203 static std::string getSimpleNodeLabel(const BasicBlock *Node, DOTFuncInfo *) {
204 return SimpleNodeLabelString(Node);
205 }
206
207 static void printBasicBlock(raw_string_ostream &OS, const BasicBlock &Node) {
208 // Prepend label name
209 Node.printAsOperand(O&: OS, PrintType: false);
210 OS << ":\n";
211 for (auto J = Node.begin(), JE = Node.end(); J != JE; ++J) {
212 const Instruction *Inst = &*J;
213 OS << *Inst << "\n";
214 }
215 }
216
217 static std::string getCompleteNodeLabel(
218 const BasicBlock *Node, DOTFuncInfo *,
219 function_ref<void(raw_string_ostream &, const BasicBlock &)>
220 HandleBasicBlock = printBasicBlock,
221 function_ref<void(std::string &, unsigned &, unsigned)>
222 HandleComment = eraseComment) {
223 return CompleteNodeLabelString(Node, HandleBasicBlock, HandleComment);
224 }
225
226 std::string getNodeLabel(const BasicBlock *Node, DOTFuncInfo *CFGInfo) {
227
228 if (isSimple())
229 return getSimpleNodeLabel(Node, CFGInfo);
230 else
231 return getCompleteNodeLabel(Node, CFGInfo);
232 }
233
234 static std::string getEdgeSourceLabel(const BasicBlock *Node,
235 const_succ_iterator I) {
236 // Label source of conditional branches with "T" or "F"
237 if (const BranchInst *BI = dyn_cast<BranchInst>(Val: Node->getTerminator()))
238 if (BI->isConditional())
239 return (I == succ_begin(BB: Node)) ? "T" : "F";
240
241 // Label source of switch edges with the associated value.
242 if (const SwitchInst *SI = dyn_cast<SwitchInst>(Val: Node->getTerminator())) {
243 unsigned SuccNo = I.getSuccessorIndex();
244
245 if (SuccNo == 0)
246 return "def";
247
248 std::string Str;
249 raw_string_ostream OS(Str);
250 auto Case = *SwitchInst::ConstCaseIt::fromSuccessorIndex(SI, SuccessorIndex: SuccNo);
251 OS << Case.getCaseValue()->getValue();
252 return OS.str();
253 }
254 return "";
255 }
256
257 static std::string getBBName(const BasicBlock *Node) {
258 std::string NodeName = Node->getName().str();
259 if (NodeName.empty()) {
260 raw_string_ostream NodeOS(NodeName);
261 Node->printAsOperand(O&: NodeOS, PrintType: false);
262 NodeName = NodeOS.str();
263 // Removing %
264 NodeName.erase(position: NodeName.begin());
265 }
266 return NodeName;
267 }
268
269 /// Display the raw branch weights from PGO.
270 std::string getEdgeAttributes(const BasicBlock *Node, const_succ_iterator I,
271 DOTFuncInfo *CFGInfo) {
272 unsigned OpNo = I.getSuccessorIndex();
273 const Instruction *TI = Node->getTerminator();
274 BasicBlock *SuccBB = TI->getSuccessor(Idx: OpNo);
275 auto BranchProb = CFGInfo->getBPI()->getEdgeProbability(Src: Node, Dst: SuccBB);
276 double WeightPercent = ((double)BranchProb.getNumerator()) /
277 ((double)BranchProb.getDenominator());
278
279 std::string TTAttr =
280 formatv(Fmt: "tooltip=\"{0} -> {1}\\nProbability {2:P}\" ", Vals: getBBName(Node),
281 Vals: getBBName(Node: SuccBB), Vals&: WeightPercent);
282 if (!CFGInfo->showEdgeWeights())
283 return TTAttr;
284
285 if (TI->getNumSuccessors() == 1)
286 return TTAttr + "penwidth=2";
287
288 if (OpNo >= TI->getNumSuccessors())
289 return TTAttr;
290
291 double Width = 1 + WeightPercent;
292
293 if (!CFGInfo->useRawEdgeWeights())
294 return TTAttr +
295 formatv(Fmt: "label=\"{0:P}\" penwidth={1}", Vals&: WeightPercent, Vals&: Width)
296 .str();
297
298 // Prepend a 'W' to indicate that this is a weight rather than the actual
299 // profile count (due to scaling).
300
301 uint64_t Freq = CFGInfo->getFreq(BB: Node);
302 std::string Attrs =
303 TTAttr + formatv(Fmt: "label=\"W:{0}\" penwidth={1}",
304 Vals: (uint64_t)(Freq * WeightPercent), Vals&: Width)
305 .str();
306 if (Attrs.size())
307 return Attrs;
308
309 MDNode *WeightsNode = getBranchWeightMDNode(I: *TI);
310 if (!WeightsNode)
311 return TTAttr;
312
313 OpNo = I.getSuccessorIndex() + 1;
314 if (OpNo >= WeightsNode->getNumOperands())
315 return TTAttr;
316 ConstantInt *Weight =
317 mdconst::dyn_extract<ConstantInt>(MD: WeightsNode->getOperand(I: OpNo));
318 if (!Weight)
319 return TTAttr;
320 return (TTAttr + "label=\"W:" + std::to_string(val: Weight->getZExtValue()) +
321 "\" penwidth=" + std::to_string(val: Width));
322 }
323
324 std::string getNodeAttributes(const BasicBlock *Node, DOTFuncInfo *CFGInfo) {
325
326 if (!CFGInfo->showHeatColors())
327 return "";
328
329 uint64_t Freq = CFGInfo->getFreq(BB: Node);
330 std::string Color = getHeatColor(freq: Freq, maxFreq: CFGInfo->getMaxFreq());
331 std::string EdgeColor = (Freq <= (CFGInfo->getMaxFreq() / 2))
332 ? (getHeatColor(percent: 0))
333 : (getHeatColor(percent: 1));
334
335 std::string Attrs = "color=\"" + EdgeColor + "ff\", style=filled," +
336 " fillcolor=\"" + Color + "70\"" +
337 " fontname=\"Courier\"";
338 return Attrs;
339 }
340 bool isNodeHidden(const BasicBlock *Node, const DOTFuncInfo *CFGInfo);
341 void computeDeoptOrUnreachablePaths(const Function *F);
342};
343} // End llvm namespace
344
345#endif
346

source code of llvm/include/llvm/Analysis/CFGPrinter.h