1//===- CFGPrinter.cpp - DOT printer for the control flow graph ------------===//
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// `<prefix>.<fnname>.dot` file for each function in the program, with a graph
11// of the CFG for that function. The default value for `<prefix>` is `cfg` but
12// can be customized as needed.
13//
14// The other main feature of this file is that it implements the
15// Function::viewCFG method, which is useful for debugging passes which operate
16// on the CFG.
17//
18//===----------------------------------------------------------------------===//
19
20#include "llvm/Analysis/CFGPrinter.h"
21#include "llvm/ADT/PostOrderIterator.h"
22#include "llvm/IR/ModuleSlotTracker.h"
23#include "llvm/Support/CommandLine.h"
24#include "llvm/Support/FileSystem.h"
25#include "llvm/Support/GraphWriter.h"
26
27using namespace llvm;
28
29static cl::opt<std::string>
30 CFGFuncName("cfg-func-name", cl::Hidden,
31 cl::desc("The name of a function (or its substring)"
32 " whose CFG is viewed/printed."));
33
34static cl::opt<std::string> CFGDotFilenamePrefix(
35 "cfg-dot-filename-prefix", cl::Hidden,
36 cl::desc("The prefix used for the CFG dot file names."));
37
38static cl::opt<bool> HideUnreachablePaths("cfg-hide-unreachable-paths",
39 cl::init(Val: false));
40
41static cl::opt<bool> HideDeoptimizePaths("cfg-hide-deoptimize-paths",
42 cl::init(Val: false));
43
44static cl::opt<double> HideColdPaths(
45 "cfg-hide-cold-paths", cl::init(Val: 0.0),
46 cl::desc("Hide blocks with relative frequency below the given value"));
47
48static cl::opt<bool> ShowHeatColors("cfg-heat-colors", cl::init(Val: true),
49 cl::Hidden,
50 cl::desc("Show heat colors in CFG"));
51
52static cl::opt<bool> UseRawEdgeWeight("cfg-raw-weights", cl::init(Val: false),
53 cl::Hidden,
54 cl::desc("Use raw weights for labels. "
55 "Use percentages as default."));
56
57static cl::opt<bool>
58 ShowEdgeWeight("cfg-weights", cl::init(Val: false), cl::Hidden,
59 cl::desc("Show edges labeled with weights"));
60
61static void writeCFGToDotFile(Function &F, BlockFrequencyInfo *BFI,
62 BranchProbabilityInfo *BPI, uint64_t MaxFreq,
63 bool CFGOnly = false) {
64 std::string Filename =
65 (CFGDotFilenamePrefix + "." + F.getName() + ".dot").str();
66 errs() << "Writing '" << Filename << "'...";
67
68 std::error_code EC;
69 raw_fd_ostream File(Filename, EC, sys::fs::OF_Text);
70
71 DOTFuncInfo CFGInfo(&F, BFI, BPI, MaxFreq);
72 CFGInfo.setHeatColors(ShowHeatColors);
73 CFGInfo.setEdgeWeights(ShowEdgeWeight);
74 CFGInfo.setRawEdgeWeights(UseRawEdgeWeight);
75
76 if (!EC)
77 WriteGraph(O&: File, G: &CFGInfo, ShortNames: CFGOnly);
78 else
79 errs() << " error opening file for writing!";
80 errs() << "\n";
81}
82
83static void viewCFG(Function &F, const BlockFrequencyInfo *BFI,
84 const BranchProbabilityInfo *BPI, uint64_t MaxFreq,
85 bool CFGOnly = false) {
86 DOTFuncInfo CFGInfo(&F, BFI, BPI, MaxFreq);
87 CFGInfo.setHeatColors(ShowHeatColors);
88 CFGInfo.setEdgeWeights(ShowEdgeWeight);
89 CFGInfo.setRawEdgeWeights(UseRawEdgeWeight);
90
91 ViewGraph(G: &CFGInfo, Name: "cfg." + F.getName(), ShortNames: CFGOnly);
92}
93
94DOTFuncInfo::DOTFuncInfo(const Function *F, const BlockFrequencyInfo *BFI,
95 const BranchProbabilityInfo *BPI, uint64_t MaxFreq,
96 std::optional<NodeIdFormatterTy> NodeIdFormatter)
97 : F(F), BFI(BFI), BPI(BPI), MaxFreq(MaxFreq),
98 NodeIdFormatter(NodeIdFormatter) {
99 ShowHeat = false;
100 EdgeWeights = !!BPI; // Print EdgeWeights when BPI is available.
101 RawWeights = !!BFI; // Print RawWeights when BFI is available.
102}
103
104DOTFuncInfo::~DOTFuncInfo() = default;
105
106ModuleSlotTracker *DOTFuncInfo::getModuleSlotTracker() {
107 if (!MSTStorage)
108 MSTStorage = std::make_unique<ModuleSlotTracker>(args: F->getParent());
109 return &*MSTStorage;
110}
111
112PreservedAnalyses CFGViewerPass::run(Function &F, FunctionAnalysisManager &AM) {
113 if (!CFGFuncName.empty() && !F.getName().contains(Other: CFGFuncName))
114 return PreservedAnalyses::all();
115 auto *BFI = &AM.getResult<BlockFrequencyAnalysis>(IR&: F);
116 auto *BPI = &AM.getResult<BranchProbabilityAnalysis>(IR&: F);
117 viewCFG(F, BFI, BPI, MaxFreq: getMaxFreq(F, BFI));
118 return PreservedAnalyses::all();
119}
120
121PreservedAnalyses CFGOnlyViewerPass::run(Function &F,
122 FunctionAnalysisManager &AM) {
123 if (!CFGFuncName.empty() && !F.getName().contains(Other: CFGFuncName))
124 return PreservedAnalyses::all();
125 auto *BFI = &AM.getResult<BlockFrequencyAnalysis>(IR&: F);
126 auto *BPI = &AM.getResult<BranchProbabilityAnalysis>(IR&: F);
127 viewCFG(F, BFI, BPI, MaxFreq: getMaxFreq(F, BFI), /*CFGOnly=*/true);
128 return PreservedAnalyses::all();
129}
130
131PreservedAnalyses CFGPrinterPass::run(Function &F,
132 FunctionAnalysisManager &AM) {
133 if (!CFGFuncName.empty() && !F.getName().contains(Other: CFGFuncName))
134 return PreservedAnalyses::all();
135 auto *BFI = &AM.getResult<BlockFrequencyAnalysis>(IR&: F);
136 auto *BPI = &AM.getResult<BranchProbabilityAnalysis>(IR&: F);
137 writeCFGToDotFile(F, BFI, BPI, MaxFreq: getMaxFreq(F, BFI));
138 return PreservedAnalyses::all();
139}
140
141PreservedAnalyses CFGOnlyPrinterPass::run(Function &F,
142 FunctionAnalysisManager &AM) {
143 if (!CFGFuncName.empty() && !F.getName().contains(Other: CFGFuncName))
144 return PreservedAnalyses::all();
145 auto *BFI = &AM.getResult<BlockFrequencyAnalysis>(IR&: F);
146 auto *BPI = &AM.getResult<BranchProbabilityAnalysis>(IR&: F);
147 writeCFGToDotFile(F, BFI, BPI, MaxFreq: getMaxFreq(F, BFI), /*CFGOnly=*/true);
148 return PreservedAnalyses::all();
149}
150
151/// viewCFG - This function is meant for use from the debugger. You can just
152/// say 'call F->viewCFG()' and a ghostview window should pop up from the
153/// program, displaying the CFG of the current function. This depends on there
154/// being a 'dot' and 'gv' program in your path.
155///
156void Function::viewCFG() const { viewCFG(ViewCFGOnly: false, BFI: nullptr, BPI: nullptr); }
157
158void Function::viewCFG(const char *OutputFileName) const {
159 viewCFG(ViewCFGOnly: false, BFI: nullptr, BPI: nullptr, OutputFileName);
160}
161
162void Function::viewCFG(bool ViewCFGOnly, const BlockFrequencyInfo *BFI,
163 const BranchProbabilityInfo *BPI,
164 const char *OutputFileName) const {
165 if (!CFGFuncName.empty() && !getName().contains(Other: CFGFuncName))
166 return;
167 DOTFuncInfo CFGInfo(this, BFI, BPI, BFI ? getMaxFreq(F: *this, BFI) : 0);
168 ViewGraph(G: &CFGInfo, Name: OutputFileName ? OutputFileName : "cfg" + getName(),
169 ShortNames: ViewCFGOnly);
170}
171
172/// viewCFGOnly - This function is meant for use from the debugger. It works
173/// just like viewCFG, but it does not include the contents of basic blocks
174/// into the nodes, just the label. If you are only interested in the CFG
175/// this can make the graph smaller.
176///
177void Function::viewCFGOnly() const { viewCFGOnly(BFI: nullptr, BPI: nullptr); }
178
179void Function::viewCFGOnly(const char *OutputFileName) const {
180 viewCFG(ViewCFGOnly: true, BFI: nullptr, BPI: nullptr, OutputFileName);
181}
182
183void Function::viewCFGOnly(const BlockFrequencyInfo *BFI,
184 const BranchProbabilityInfo *BPI) const {
185 viewCFG(ViewCFGOnly: true, BFI, BPI);
186}
187
188/// Find all blocks on the paths which terminate with a deoptimize or
189/// unreachable (i.e. all blocks which are post-dominated by a deoptimize
190/// or unreachable). These paths are hidden if the corresponding cl::opts
191/// are enabled.
192void DOTGraphTraits<DOTFuncInfo *>::computeDeoptOrUnreachablePaths(
193 const Function *F) {
194 auto evaluateBB = [&](const BasicBlock *Node) {
195 if (succ_empty(BB: Node)) {
196 const Instruction *TI = Node->getTerminator();
197 isOnDeoptOrUnreachablePath[Node] =
198 (HideUnreachablePaths && isa<UnreachableInst>(Val: TI)) ||
199 (HideDeoptimizePaths && Node->getTerminatingDeoptimizeCall());
200 return;
201 }
202 isOnDeoptOrUnreachablePath[Node] =
203 llvm::all_of(Range: successors(BB: Node), P: [this](const BasicBlock *BB) {
204 return isOnDeoptOrUnreachablePath[BB];
205 });
206 };
207 /// The post order traversal iteration is done to know the status of
208 /// isOnDeoptOrUnreachablePath for all the successors on the current BB.
209 llvm::for_each(Range: post_order(G: &F->getEntryBlock()), F: evaluateBB);
210}
211
212bool DOTGraphTraits<DOTFuncInfo *>::isNodeHidden(const BasicBlock *Node,
213 const DOTFuncInfo *CFGInfo) {
214 if (HideColdPaths.getNumOccurrences() > 0)
215 if (auto *BFI = CFGInfo->getBFI()) {
216 BlockFrequency NodeFreq = BFI->getBlockFreq(BB: Node);
217 BlockFrequency EntryFreq = BFI->getEntryFreq();
218 // Hide blocks with relative frequency below HideColdPaths threshold.
219 if ((double)NodeFreq.getFrequency() / EntryFreq.getFrequency() <
220 HideColdPaths)
221 return true;
222 }
223 if (HideUnreachablePaths || HideDeoptimizePaths) {
224 if (!isOnDeoptOrUnreachablePath.contains(Val: Node))
225 computeDeoptOrUnreachablePaths(F: Node->getParent());
226 return isOnDeoptOrUnreachablePath[Node];
227 }
228 return false;
229}
230
231std::string DOTGraphTraits<DOTFuncInfo *>::getCompleteNodeLabel(
232 const BasicBlock *Node, DOTFuncInfo *CFGInfo,
233 function_ref<void(raw_string_ostream &, const BasicBlock &)>
234 HandleBasicBlock,
235 function_ref<void(std::string &, unsigned &, unsigned)> HandleComment) {
236 if (HandleBasicBlock)
237 return CompleteNodeLabelString(Node, HandleBasicBlock, HandleComment);
238
239 // Default basic block printing
240 std::optional<ModuleSlotTracker> MSTStorage;
241 ModuleSlotTracker *MST = nullptr;
242
243 if (CFGInfo) {
244 MST = CFGInfo->getModuleSlotTracker();
245 } else {
246 MSTStorage.emplace(args: Node->getModule());
247 MST = &*MSTStorage;
248 }
249
250 return CompleteNodeLabelString(
251 Node,
252 HandleBasicBlock: function_ref<void(raw_string_ostream &, const BasicBlock &)>(
253 [MST](raw_string_ostream &OS, const BasicBlock &Node) -> void {
254 // Prepend label name
255 Node.printAsOperand(O&: OS, PrintType: false, MST&: *MST);
256 OS << ":\n";
257
258 for (const Instruction &Inst : Node) {
259 Inst.print(O&: OS, MST&: *MST, /* IsForDebug */ false);
260 OS << '\n';
261 }
262 }),
263 HandleComment);
264}
265