1//===- CallPrinter.cpp - DOT printer for call 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 '-dot-callgraph', which emit a callgraph.<fnname>.dot
10// containing the call graph of a module.
11//
12// There is also a pass available to directly call dotty ('-view-callgraph').
13//
14//===----------------------------------------------------------------------===//
15
16#include "llvm/Analysis/CallPrinter.h"
17#include "AnalysisOptions.h"
18#include "llvm/ADT/DenseMap.h"
19#include "llvm/Analysis/BlockFrequencyInfo.h"
20#include "llvm/Analysis/CallGraph.h"
21#include "llvm/Analysis/HeatUtils.h"
22#include "llvm/IR/Instructions.h"
23#include "llvm/IR/Module.h"
24#include "llvm/InitializePasses.h"
25#include "llvm/Support/DOTGraphTraits.h"
26#include "llvm/Support/GraphWriter.h"
27
28using namespace llvm;
29
30namespace llvm {
31template <class GraphType> struct GraphTraits;
32} // namespace llvm
33
34namespace llvm {
35
36class CallGraphDOTInfo {
37private:
38 const AnalysisOptions &Opts;
39 Module *M;
40 CallGraph *CG;
41 DenseMap<const Function *, uint64_t> Freq;
42 uint64_t MaxFreq;
43
44public:
45 std::function<BlockFrequencyInfo *(Function &)> LookupBFI;
46
47 CallGraphDOTInfo(Module *M, CallGraph *CG,
48 function_ref<BlockFrequencyInfo *(Function &)> LookupBFI)
49 : Opts(getAnalysisOptions(M: *M)), M(M), CG(CG), LookupBFI(LookupBFI) {
50 MaxFreq = 0;
51
52 for (Function &F : M->getFunctionList()) {
53 uint64_t localSumFreq = 0;
54 SmallPtrSet<Function *, 16> Callers;
55 for (User *U : F.users())
56 if (isa<CallInst>(Val: U))
57 Callers.insert(Ptr: cast<Instruction>(Val: U)->getFunction());
58 for (Function *Caller : Callers)
59 localSumFreq += getNumOfCalls(CallerFunction: *Caller, CalledFunction: F);
60 if (localSumFreq >= MaxFreq)
61 MaxFreq = localSumFreq;
62 Freq[&F] = localSumFreq;
63 }
64 if (!Opts.callgraph_multigraph)
65 removeParallelEdges();
66 }
67
68 const AnalysisOptions &getOpts() const { return Opts; }
69
70 Module *getModule() const { return M; }
71
72 CallGraph *getCallGraph() const { return CG; }
73
74 uint64_t getFreq(const Function *F) { return Freq[F]; }
75
76 uint64_t getMaxFreq() { return MaxFreq; }
77
78private:
79 void removeParallelEdges() {
80 for (auto &I : (*CG)) {
81 CallGraphNode *Node = I.second.get();
82
83 bool FoundParallelEdge = true;
84 while (FoundParallelEdge) {
85 SmallPtrSet<Function *, 16> Visited;
86 FoundParallelEdge = false;
87 for (auto CI = Node->begin(), CE = Node->end(); CI != CE; CI++) {
88 if (!(Visited.insert(Ptr: CI->second->getFunction())).second) {
89 FoundParallelEdge = true;
90 Node->removeCallEdge(I: CI);
91 break;
92 }
93 }
94 }
95 }
96 }
97};
98
99template <>
100struct GraphTraits<CallGraphDOTInfo *>
101 : public GraphTraits<const CallGraphNode *> {
102 static NodeRef getEntryNode(CallGraphDOTInfo *CGInfo) {
103 // Start at the external node!
104 return CGInfo->getCallGraph()->getExternalCallingNode();
105 }
106
107 typedef std::pair<const Function *const, std::unique_ptr<CallGraphNode>>
108 PairTy;
109 static const CallGraphNode *CGGetValuePtr(const PairTy &P) {
110 return P.second.get();
111 }
112
113 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
114 typedef mapped_iterator<CallGraph::const_iterator, decltype(&CGGetValuePtr)>
115 nodes_iterator;
116
117 static nodes_iterator nodes_begin(CallGraphDOTInfo *CGInfo) {
118 return nodes_iterator(CGInfo->getCallGraph()->begin(), &CGGetValuePtr);
119 }
120 static nodes_iterator nodes_end(CallGraphDOTInfo *CGInfo) {
121 return nodes_iterator(CGInfo->getCallGraph()->end(), &CGGetValuePtr);
122 }
123};
124
125template <>
126struct DOTGraphTraits<CallGraphDOTInfo *> : public DefaultDOTGraphTraits {
127
128 DOTGraphTraits(bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {}
129
130 static std::string getGraphName(CallGraphDOTInfo *CGInfo) {
131 return "Call graph: " +
132 std::string(CGInfo->getModule()->getModuleIdentifier());
133 }
134
135 static bool isNodeHidden(const CallGraphNode *Node,
136 const CallGraphDOTInfo *CGInfo) {
137 if (CGInfo->getOpts().callgraph_multigraph || Node->getFunction())
138 return false;
139 return true;
140 }
141
142 std::string getNodeLabel(const CallGraphNode *Node,
143 CallGraphDOTInfo *CGInfo) {
144 if (Node == CGInfo->getCallGraph()->getExternalCallingNode())
145 return "external caller";
146 if (Node == CGInfo->getCallGraph()->getCallsExternalNode())
147 return "external callee";
148
149 if (Function *Func = Node->getFunction())
150 return std::string(Func->getName());
151 return "external node";
152 }
153 static const CallGraphNode *CGGetValuePtr(CallGraphNode::CallRecord P) {
154 return P.second;
155 }
156
157 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
158 typedef mapped_iterator<CallGraphNode::const_iterator,
159 decltype(&CGGetValuePtr)>
160 nodes_iterator;
161
162 std::string getEdgeAttributes(const CallGraphNode *Node, nodes_iterator I,
163 CallGraphDOTInfo *CGInfo) {
164 if (!CGInfo->getOpts().callgraph_show_weights)
165 return "";
166
167 Function *Caller = Node->getFunction();
168 if (Caller == nullptr || Caller->isDeclaration())
169 return "";
170
171 Function *Callee = (*I)->getFunction();
172 if (Callee == nullptr)
173 return "";
174
175 uint64_t Counter = getNumOfCalls(CallerFunction: *Caller, CalledFunction: *Callee);
176 double Width =
177 1 + 2 * (double(Counter) / CGInfo->getMaxFreq());
178 std::string Attrs = "label=\"" + std::to_string(val: Counter) +
179 "\" penwidth=" + std::to_string(val: Width);
180 return Attrs;
181 }
182
183 std::string getNodeAttributes(const CallGraphNode *Node,
184 CallGraphDOTInfo *CGInfo) {
185 Function *F = Node->getFunction();
186 if (F == nullptr)
187 return "";
188 std::string attrs;
189 if (CGInfo->getOpts().callgraph_heat_colors) {
190 uint64_t freq = CGInfo->getFreq(F);
191 std::string color = getHeatColor(Freq: freq, MaxFreq: CGInfo->getMaxFreq());
192 std::string edgeColor = (freq <= (CGInfo->getMaxFreq() / 2))
193 ? getHeatColor(Percent: 0)
194 : getHeatColor(Percent: 1);
195 attrs = "color=\"" + edgeColor + "ff\", style=filled, fillcolor=\"" +
196 color + "80\"";
197 }
198 return attrs;
199 }
200};
201
202} // namespace llvm
203
204namespace {
205void doCallGraphDOTPrinting(
206 Module &M, function_ref<BlockFrequencyInfo *(Function &)> LookupBFI) {
207 StringRef Prefix = getAnalysisOptions(M).callgraph_dot_filename_prefix;
208 std::string Filename;
209 if (!Prefix.empty())
210 Filename = (Prefix + ".callgraph.dot").str();
211 else
212 Filename = (std::string(M.getModuleIdentifier()) + ".callgraph.dot");
213 errs() << "Writing '" << Filename << "'...";
214
215 std::error_code EC;
216 raw_fd_ostream File(Filename, EC, sys::fs::OF_Text);
217
218 CallGraph CG(M);
219 CallGraphDOTInfo CFGInfo(&M, &CG, LookupBFI);
220
221 if (!EC)
222 WriteGraph(O&: File, G: &CFGInfo);
223 else
224 errs() << " error opening file for writing!";
225 errs() << "\n";
226}
227
228void viewCallGraph(Module &M,
229 function_ref<BlockFrequencyInfo *(Function &)> LookupBFI) {
230 CallGraph CG(M);
231 CallGraphDOTInfo CFGInfo(&M, &CG, LookupBFI);
232
233 std::string Title =
234 DOTGraphTraits<CallGraphDOTInfo *>::getGraphName(CGInfo: &CFGInfo);
235 ViewGraph(G: &CFGInfo, Name: "callgraph", ShortNames: true, Title);
236}
237} // namespace
238
239namespace llvm {
240PreservedAnalyses CallGraphDOTPrinterPass::run(Module &M,
241 ModuleAnalysisManager &AM) {
242 FunctionAnalysisManager &FAM =
243 AM.getResult<FunctionAnalysisManagerModuleProxy>(IR&: M).getManager();
244
245 auto LookupBFI = [&FAM](Function &F) {
246 return &FAM.getResult<BlockFrequencyAnalysis>(IR&: F);
247 };
248
249 doCallGraphDOTPrinting(M, LookupBFI);
250
251 return PreservedAnalyses::all();
252}
253
254PreservedAnalyses CallGraphViewerPass::run(Module &M,
255 ModuleAnalysisManager &AM) {
256
257 FunctionAnalysisManager &FAM =
258 AM.getResult<FunctionAnalysisManagerModuleProxy>(IR&: M).getManager();
259
260 auto LookupBFI = [&FAM](Function &F) {
261 return &FAM.getResult<BlockFrequencyAnalysis>(IR&: F);
262 };
263
264 viewCallGraph(M, LookupBFI);
265
266 return PreservedAnalyses::all();
267}
268} // namespace llvm
269
270namespace {
271// Viewer
272class CallGraphViewer : public ModulePass {
273public:
274 static char ID;
275 CallGraphViewer() : ModulePass(ID) {}
276
277 void getAnalysisUsage(AnalysisUsage &AU) const override;
278 bool runOnModule(Module &M) override;
279};
280
281void CallGraphViewer::getAnalysisUsage(AnalysisUsage &AU) const {
282 ModulePass::getAnalysisUsage(AU);
283 AU.addRequired<BlockFrequencyInfoWrapperPass>();
284 AU.setPreservesAll();
285}
286
287bool CallGraphViewer::runOnModule(Module &M) {
288 auto LookupBFI = [this](Function &F) {
289 return &this->getAnalysis<BlockFrequencyInfoWrapperPass>(F).getBFI();
290 };
291
292 viewCallGraph(M, LookupBFI);
293
294 return false;
295}
296
297// DOT Printer
298
299class CallGraphDOTPrinter : public ModulePass {
300public:
301 static char ID;
302 CallGraphDOTPrinter() : ModulePass(ID) {}
303
304 void getAnalysisUsage(AnalysisUsage &AU) const override;
305 bool runOnModule(Module &M) override;
306};
307
308void CallGraphDOTPrinter::getAnalysisUsage(AnalysisUsage &AU) const {
309 ModulePass::getAnalysisUsage(AU);
310 AU.addRequired<BlockFrequencyInfoWrapperPass>();
311 AU.setPreservesAll();
312}
313
314bool CallGraphDOTPrinter::runOnModule(Module &M) {
315 auto LookupBFI = [this](Function &F) {
316 return &this->getAnalysis<BlockFrequencyInfoWrapperPass>(F).getBFI();
317 };
318
319 doCallGraphDOTPrinting(M, LookupBFI);
320
321 return false;
322}
323
324} // end anonymous namespace
325
326char CallGraphViewer::ID = 0;
327INITIALIZE_PASS(CallGraphViewer, "view-callgraph", "View call graph", false,
328 false)
329
330char CallGraphDOTPrinter::ID = 0;
331INITIALIZE_PASS(CallGraphDOTPrinter, "dot-callgraph",
332 "Print call graph to 'dot' file", false, false)
333
334// Create methods available outside of this file, to use them
335// "include/llvm/LinkAllPasses.h". Otherwise the pass would be deleted by
336// the link time optimization.
337
338ModulePass *llvm::createCallGraphViewerPass() { return new CallGraphViewer(); }
339
340ModulePass *llvm::createCallGraphDOTPrinterPass() {
341 return new CallGraphDOTPrinter();
342}
343