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/InitializePasses.h"
23 #include "llvm/Pass.h"
24 #include "llvm/Support/CommandLine.h"
25 #include "llvm/Support/FileSystem.h"
26 #include "llvm/Support/GraphWriter.h"
27 
28 using namespace llvm;
29 
30 static cl::opt<std::string>
31     CFGFuncName("cfg-func-name", cl::Hidden,
32                 cl::desc("The name of a function (or its substring)"
33                          " whose CFG is viewed/printed."));
34 
35 static cl::opt<std::string> CFGDotFilenamePrefix(
36     "cfg-dot-filename-prefix", cl::Hidden,
37     cl::desc("The prefix used for the CFG dot file names."));
38 
39 static cl::opt<bool> HideUnreachablePaths("cfg-hide-unreachable-paths",
40                                           cl::init(false));
41 
42 static cl::opt<bool> HideDeoptimizePaths("cfg-hide-deoptimize-paths",
43                                          cl::init(false));
44 
45 static cl::opt<double> HideColdPaths(
46     "cfg-hide-cold-paths", cl::init(0.0),
47     cl::desc("Hide blocks with relative frequency below the given value"));
48 
49 static cl::opt<bool> ShowHeatColors("cfg-heat-colors", cl::init(true),
50                                     cl::Hidden,
51                                     cl::desc("Show heat colors in CFG"));
52 
53 static cl::opt<bool> UseRawEdgeWeight("cfg-raw-weights", cl::init(false),
54                                       cl::Hidden,
55                                       cl::desc("Use raw weights for labels. "
56                                                "Use percentages as default."));
57 
58 static cl::opt<bool>
59     ShowEdgeWeight("cfg-weights", cl::init(false), cl::Hidden,
60                    cl::desc("Show edges labeled with weights"));
61 
62 static void writeCFGToDotFile(Function &F, BlockFrequencyInfo *BFI,
63                               BranchProbabilityInfo *BPI, uint64_t MaxFreq,
64                               bool CFGOnly = false) {
65   std::string Filename =
66       (CFGDotFilenamePrefix + "." + F.getName() + ".dot").str();
67   errs() << "Writing '" << Filename << "'...";
68 
69   std::error_code EC;
70   raw_fd_ostream File(Filename, EC, sys::fs::OF_Text);
71 
72   DOTFuncInfo CFGInfo(&F, BFI, BPI, MaxFreq);
73   CFGInfo.setHeatColors(ShowHeatColors);
74   CFGInfo.setEdgeWeights(ShowEdgeWeight);
75   CFGInfo.setRawEdgeWeights(UseRawEdgeWeight);
76 
77   if (!EC)
78     WriteGraph(File, &CFGInfo, CFGOnly);
79   else
80     errs() << "  error opening file for writing!";
81   errs() << "\n";
82 }
83 
84 static void viewCFG(Function &F, const BlockFrequencyInfo *BFI,
85                     const BranchProbabilityInfo *BPI, uint64_t MaxFreq,
86                     bool CFGOnly = false) {
87   DOTFuncInfo CFGInfo(&F, BFI, BPI, MaxFreq);
88   CFGInfo.setHeatColors(ShowHeatColors);
89   CFGInfo.setEdgeWeights(ShowEdgeWeight);
90   CFGInfo.setRawEdgeWeights(UseRawEdgeWeight);
91 
92   ViewGraph(&CFGInfo, "cfg." + F.getName(), CFGOnly);
93 }
94 
95 namespace {
96 struct CFGViewerLegacyPass : public FunctionPass {
97   static char ID; // Pass identifcation, replacement for typeid
98   CFGViewerLegacyPass() : FunctionPass(ID) {
99     initializeCFGViewerLegacyPassPass(*PassRegistry::getPassRegistry());
100   }
101 
102   bool runOnFunction(Function &F) override {
103     if (!CFGFuncName.empty() && !F.getName().contains(CFGFuncName))
104       return false;
105     auto *BPI = &getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
106     auto *BFI = &getAnalysis<BlockFrequencyInfoWrapperPass>().getBFI();
107     viewCFG(F, BFI, BPI, getMaxFreq(F, BFI));
108     return false;
109   }
110 
111   void print(raw_ostream &OS, const Module * = nullptr) const override {}
112 
113   void getAnalysisUsage(AnalysisUsage &AU) const override {
114     FunctionPass::getAnalysisUsage(AU);
115     AU.addRequired<BlockFrequencyInfoWrapperPass>();
116     AU.addRequired<BranchProbabilityInfoWrapperPass>();
117     AU.setPreservesAll();
118   }
119 };
120 } // namespace
121 
122 char CFGViewerLegacyPass::ID = 0;
123 INITIALIZE_PASS(CFGViewerLegacyPass, "view-cfg", "View CFG of function", false,
124                 true)
125 
126 PreservedAnalyses CFGViewerPass::run(Function &F, FunctionAnalysisManager &AM) {
127   if (!CFGFuncName.empty() && !F.getName().contains(CFGFuncName))
128     return PreservedAnalyses::all();
129   auto *BFI = &AM.getResult<BlockFrequencyAnalysis>(F);
130   auto *BPI = &AM.getResult<BranchProbabilityAnalysis>(F);
131   viewCFG(F, BFI, BPI, getMaxFreq(F, BFI));
132   return PreservedAnalyses::all();
133 }
134 
135 namespace {
136 struct CFGOnlyViewerLegacyPass : public FunctionPass {
137   static char ID; // Pass identifcation, replacement for typeid
138   CFGOnlyViewerLegacyPass() : FunctionPass(ID) {
139     initializeCFGOnlyViewerLegacyPassPass(*PassRegistry::getPassRegistry());
140   }
141 
142   bool runOnFunction(Function &F) override {
143     if (!CFGFuncName.empty() && !F.getName().contains(CFGFuncName))
144       return false;
145     auto *BPI = &getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
146     auto *BFI = &getAnalysis<BlockFrequencyInfoWrapperPass>().getBFI();
147     viewCFG(F, BFI, BPI, getMaxFreq(F, BFI), /*CFGOnly=*/true);
148     return false;
149   }
150 
151   void print(raw_ostream &OS, const Module * = nullptr) const override {}
152 
153   void getAnalysisUsage(AnalysisUsage &AU) const override {
154     FunctionPass::getAnalysisUsage(AU);
155     AU.addRequired<BlockFrequencyInfoWrapperPass>();
156     AU.addRequired<BranchProbabilityInfoWrapperPass>();
157     AU.setPreservesAll();
158   }
159 };
160 } // namespace
161 
162 char CFGOnlyViewerLegacyPass::ID = 0;
163 INITIALIZE_PASS(CFGOnlyViewerLegacyPass, "view-cfg-only",
164                 "View CFG of function (with no function bodies)", false, true)
165 
166 PreservedAnalyses CFGOnlyViewerPass::run(Function &F,
167                                          FunctionAnalysisManager &AM) {
168   if (!CFGFuncName.empty() && !F.getName().contains(CFGFuncName))
169     return PreservedAnalyses::all();
170   auto *BFI = &AM.getResult<BlockFrequencyAnalysis>(F);
171   auto *BPI = &AM.getResult<BranchProbabilityAnalysis>(F);
172   viewCFG(F, BFI, BPI, getMaxFreq(F, BFI), /*CFGOnly=*/true);
173   return PreservedAnalyses::all();
174 }
175 
176 namespace {
177 struct CFGPrinterLegacyPass : public FunctionPass {
178   static char ID; // Pass identification, replacement for typeid
179   CFGPrinterLegacyPass() : FunctionPass(ID) {
180     initializeCFGPrinterLegacyPassPass(*PassRegistry::getPassRegistry());
181   }
182 
183   bool runOnFunction(Function &F) override {
184     if (!CFGFuncName.empty() && !F.getName().contains(CFGFuncName))
185       return false;
186     auto *BPI = &getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
187     auto *BFI = &getAnalysis<BlockFrequencyInfoWrapperPass>().getBFI();
188     writeCFGToDotFile(F, BFI, BPI, getMaxFreq(F, BFI));
189     return false;
190   }
191 
192   void print(raw_ostream &OS, const Module * = nullptr) const override {}
193 
194   void getAnalysisUsage(AnalysisUsage &AU) const override {
195     FunctionPass::getAnalysisUsage(AU);
196     AU.addRequired<BlockFrequencyInfoWrapperPass>();
197     AU.addRequired<BranchProbabilityInfoWrapperPass>();
198     AU.setPreservesAll();
199   }
200 };
201 } // namespace
202 
203 char CFGPrinterLegacyPass::ID = 0;
204 INITIALIZE_PASS(CFGPrinterLegacyPass, "dot-cfg",
205                 "Print CFG of function to 'dot' file", false, true)
206 
207 PreservedAnalyses CFGPrinterPass::run(Function &F,
208                                       FunctionAnalysisManager &AM) {
209   if (!CFGFuncName.empty() && !F.getName().contains(CFGFuncName))
210     return PreservedAnalyses::all();
211   auto *BFI = &AM.getResult<BlockFrequencyAnalysis>(F);
212   auto *BPI = &AM.getResult<BranchProbabilityAnalysis>(F);
213   writeCFGToDotFile(F, BFI, BPI, getMaxFreq(F, BFI));
214   return PreservedAnalyses::all();
215 }
216 
217 namespace {
218 struct CFGOnlyPrinterLegacyPass : public FunctionPass {
219   static char ID; // Pass identification, replacement for typeid
220   CFGOnlyPrinterLegacyPass() : FunctionPass(ID) {
221     initializeCFGOnlyPrinterLegacyPassPass(*PassRegistry::getPassRegistry());
222   }
223 
224   bool runOnFunction(Function &F) override {
225     if (!CFGFuncName.empty() && !F.getName().contains(CFGFuncName))
226       return false;
227     auto *BPI = &getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
228     auto *BFI = &getAnalysis<BlockFrequencyInfoWrapperPass>().getBFI();
229     writeCFGToDotFile(F, BFI, BPI, getMaxFreq(F, BFI), /*CFGOnly=*/true);
230     return false;
231   }
232   void print(raw_ostream &OS, const Module * = nullptr) const override {}
233 
234   void getAnalysisUsage(AnalysisUsage &AU) const override {
235     FunctionPass::getAnalysisUsage(AU);
236     AU.addRequired<BlockFrequencyInfoWrapperPass>();
237     AU.addRequired<BranchProbabilityInfoWrapperPass>();
238     AU.setPreservesAll();
239   }
240 };
241 } // namespace
242 
243 char CFGOnlyPrinterLegacyPass::ID = 0;
244 INITIALIZE_PASS(CFGOnlyPrinterLegacyPass, "dot-cfg-only",
245                 "Print CFG of function to 'dot' file (with no function bodies)",
246                 false, true)
247 
248 PreservedAnalyses CFGOnlyPrinterPass::run(Function &F,
249                                           FunctionAnalysisManager &AM) {
250   if (!CFGFuncName.empty() && !F.getName().contains(CFGFuncName))
251     return PreservedAnalyses::all();
252   auto *BFI = &AM.getResult<BlockFrequencyAnalysis>(F);
253   auto *BPI = &AM.getResult<BranchProbabilityAnalysis>(F);
254   writeCFGToDotFile(F, BFI, BPI, getMaxFreq(F, BFI), /*CFGOnly=*/true);
255   return PreservedAnalyses::all();
256 }
257 
258 /// viewCFG - This function is meant for use from the debugger.  You can just
259 /// say 'call F->viewCFG()' and a ghostview window should pop up from the
260 /// program, displaying the CFG of the current function.  This depends on there
261 /// being a 'dot' and 'gv' program in your path.
262 ///
263 void Function::viewCFG() const { viewCFG(false, nullptr, nullptr); }
264 
265 void Function::viewCFG(bool ViewCFGOnly, const BlockFrequencyInfo *BFI,
266                        const BranchProbabilityInfo *BPI) const {
267   if (!CFGFuncName.empty() && !getName().contains(CFGFuncName))
268     return;
269   DOTFuncInfo CFGInfo(this, BFI, BPI, BFI ? getMaxFreq(*this, BFI) : 0);
270   ViewGraph(&CFGInfo, "cfg" + getName(), ViewCFGOnly);
271 }
272 
273 /// viewCFGOnly - This function is meant for use from the debugger.  It works
274 /// just like viewCFG, but it does not include the contents of basic blocks
275 /// into the nodes, just the label.  If you are only interested in the CFG
276 /// this can make the graph smaller.
277 ///
278 void Function::viewCFGOnly() const { viewCFGOnly(nullptr, nullptr); }
279 
280 void Function::viewCFGOnly(const BlockFrequencyInfo *BFI,
281                            const BranchProbabilityInfo *BPI) const {
282   viewCFG(true, BFI, BPI);
283 }
284 
285 FunctionPass *llvm::createCFGPrinterLegacyPassPass() {
286   return new CFGPrinterLegacyPass();
287 }
288 
289 FunctionPass *llvm::createCFGOnlyPrinterLegacyPassPass() {
290   return new CFGOnlyPrinterLegacyPass();
291 }
292 
293 /// Find all blocks on the paths which terminate with a deoptimize or
294 /// unreachable (i.e. all blocks which are post-dominated by a deoptimize
295 /// or unreachable). These paths are hidden if the corresponding cl::opts
296 /// are enabled.
297 void DOTGraphTraits<DOTFuncInfo *>::computeDeoptOrUnreachablePaths(
298     const Function *F) {
299   auto evaluateBB = [&](const BasicBlock *Node) {
300     if (succ_empty(Node)) {
301       const Instruction *TI = Node->getTerminator();
302       isOnDeoptOrUnreachablePath[Node] =
303           (HideUnreachablePaths && isa<UnreachableInst>(TI)) ||
304           (HideDeoptimizePaths && Node->getTerminatingDeoptimizeCall());
305       return;
306     }
307     isOnDeoptOrUnreachablePath[Node] =
308         llvm::all_of(successors(Node), [this](const BasicBlock *BB) {
309           return isOnDeoptOrUnreachablePath[BB];
310         });
311   };
312   /// The post order traversal iteration is done to know the status of
313   /// isOnDeoptOrUnreachablePath for all the successors on the current BB.
314   llvm::for_each(post_order(&F->getEntryBlock()), evaluateBB);
315 }
316 
317 bool DOTGraphTraits<DOTFuncInfo *>::isNodeHidden(const BasicBlock *Node,
318                                                  const DOTFuncInfo *CFGInfo) {
319   if (HideColdPaths.getNumOccurrences() > 0)
320     if (auto *BFI = CFGInfo->getBFI()) {
321       uint64_t NodeFreq = BFI->getBlockFreq(Node).getFrequency();
322       uint64_t EntryFreq = BFI->getEntryFreq();
323       // Hide blocks with relative frequency below HideColdPaths threshold.
324       if ((double)NodeFreq / EntryFreq < HideColdPaths)
325         return true;
326     }
327   if (HideUnreachablePaths || HideDeoptimizePaths) {
328     if (!isOnDeoptOrUnreachablePath.contains(Node))
329       computeDeoptOrUnreachablePaths(Node->getParent());
330     return isOnDeoptOrUnreachablePath[Node];
331   }
332   return false;
333 }
334