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 | |
33 | namespace llvm { |
34 | template <class GraphType> struct GraphTraits; |
35 | class CFGViewerPass : public PassInfoMixin<CFGViewerPass> { |
36 | public: |
37 | PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); |
38 | static bool isRequired() { return true; } |
39 | }; |
40 | |
41 | class CFGOnlyViewerPass : public PassInfoMixin<CFGOnlyViewerPass> { |
42 | public: |
43 | PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); |
44 | static bool isRequired() { return true; } |
45 | }; |
46 | |
47 | class CFGPrinterPass : public PassInfoMixin<CFGPrinterPass> { |
48 | public: |
49 | PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); |
50 | static bool isRequired() { return true; } |
51 | }; |
52 | |
53 | class CFGOnlyPrinterPass : public PassInfoMixin<CFGOnlyPrinterPass> { |
54 | public: |
55 | PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); |
56 | static bool isRequired() { return true; } |
57 | }; |
58 | |
59 | class DOTFuncInfo { |
60 | private: |
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 | |
69 | public: |
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 | |
105 | template <> |
106 | struct 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 | |
127 | template <typename BasicBlockT> |
128 | std::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 | |
139 | template <typename BasicBlockT> |
140 | std::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 | |
186 | template <> |
187 | struct 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 (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 | |