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 "llvm/ADT/DenseMap.h"
18 #include "llvm/ADT/SmallSet.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/InitializePasses.h"
24 #include "llvm/Support/CommandLine.h"
25 #include "llvm/Support/DOTGraphTraits.h"
26 #include "llvm/Support/GraphWriter.h"
27
28 using namespace llvm;
29
30 namespace llvm {
31 template <class GraphType> struct GraphTraits;
32 }
33
34 // This option shows static (relative) call counts.
35 // FIXME:
36 // Need to show real counts when profile data is available
37 static cl::opt<bool> ShowHeatColors("callgraph-heat-colors", cl::init(false),
38 cl::Hidden,
39 cl::desc("Show heat colors in call-graph"));
40
41 static cl::opt<bool>
42 ShowEdgeWeight("callgraph-show-weights", cl::init(false), cl::Hidden,
43 cl::desc("Show edges labeled with weights"));
44
45 static cl::opt<bool>
46 CallMultiGraph("callgraph-multigraph", cl::init(false), cl::Hidden,
47 cl::desc("Show call-multigraph (do not remove parallel edges)"));
48
49 static cl::opt<std::string> CallGraphDotFilenamePrefix(
50 "callgraph-dot-filename-prefix", cl::Hidden,
51 cl::desc("The prefix used for the CallGraph dot file names."));
52
53 namespace llvm {
54
55 class CallGraphDOTInfo {
56 private:
57 Module *M;
58 CallGraph *CG;
59 DenseMap<const Function *, uint64_t> Freq;
60 uint64_t MaxFreq;
61
62 public:
63 std::function<BlockFrequencyInfo *(Function &)> LookupBFI;
64
CallGraphDOTInfo(Module * M,CallGraph * CG,function_ref<BlockFrequencyInfo * (Function &)> LookupBFI)65 CallGraphDOTInfo(Module *M, CallGraph *CG,
66 function_ref<BlockFrequencyInfo *(Function &)> LookupBFI)
67 : M(M), CG(CG), LookupBFI(LookupBFI) {
68 MaxFreq = 0;
69
70 for (Function &F : M->getFunctionList()) {
71 uint64_t localSumFreq = 0;
72 SmallSet<Function *, 16> Callers;
73 for (User *U : F.users())
74 if (isa<CallInst>(U))
75 Callers.insert(cast<Instruction>(U)->getFunction());
76 for (Function *Caller : Callers)
77 localSumFreq += getNumOfCalls(*Caller, F);
78 if (localSumFreq >= MaxFreq)
79 MaxFreq = localSumFreq;
80 Freq[&F] = localSumFreq;
81 }
82 if (!CallMultiGraph)
83 removeParallelEdges();
84 }
85
getModule() const86 Module *getModule() const { return M; }
87
getCallGraph() const88 CallGraph *getCallGraph() const { return CG; }
89
getFreq(const Function * F)90 uint64_t getFreq(const Function *F) { return Freq[F]; }
91
getMaxFreq()92 uint64_t getMaxFreq() { return MaxFreq; }
93
94 private:
removeParallelEdges()95 void removeParallelEdges() {
96 for (auto &I : (*CG)) {
97 CallGraphNode *Node = I.second.get();
98
99 bool FoundParallelEdge = true;
100 while (FoundParallelEdge) {
101 SmallSet<Function *, 16> Visited;
102 FoundParallelEdge = false;
103 for (auto CI = Node->begin(), CE = Node->end(); CI != CE; CI++) {
104 if (!(Visited.insert(CI->second->getFunction())).second) {
105 FoundParallelEdge = true;
106 Node->removeCallEdge(CI);
107 break;
108 }
109 }
110 }
111 }
112 }
113 };
114
115 template <>
116 struct GraphTraits<CallGraphDOTInfo *>
117 : public GraphTraits<const CallGraphNode *> {
getEntryNodellvm::GraphTraits118 static NodeRef getEntryNode(CallGraphDOTInfo *CGInfo) {
119 // Start at the external node!
120 return CGInfo->getCallGraph()->getExternalCallingNode();
121 }
122
123 typedef std::pair<const Function *const, std::unique_ptr<CallGraphNode>>
124 PairTy;
CGGetValuePtrllvm::GraphTraits125 static const CallGraphNode *CGGetValuePtr(const PairTy &P) {
126 return P.second.get();
127 }
128
129 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
130 typedef mapped_iterator<CallGraph::const_iterator, decltype(&CGGetValuePtr)>
131 nodes_iterator;
132
nodes_beginllvm::GraphTraits133 static nodes_iterator nodes_begin(CallGraphDOTInfo *CGInfo) {
134 return nodes_iterator(CGInfo->getCallGraph()->begin(), &CGGetValuePtr);
135 }
nodes_endllvm::GraphTraits136 static nodes_iterator nodes_end(CallGraphDOTInfo *CGInfo) {
137 return nodes_iterator(CGInfo->getCallGraph()->end(), &CGGetValuePtr);
138 }
139 };
140
141 template <>
142 struct DOTGraphTraits<CallGraphDOTInfo *> : public DefaultDOTGraphTraits {
143
DOTGraphTraitsllvm::DOTGraphTraits144 DOTGraphTraits(bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {}
145
getGraphNamellvm::DOTGraphTraits146 static std::string getGraphName(CallGraphDOTInfo *CGInfo) {
147 return "Call graph: " +
148 std::string(CGInfo->getModule()->getModuleIdentifier());
149 }
150
isNodeHiddenllvm::DOTGraphTraits151 static bool isNodeHidden(const CallGraphNode *Node,
152 const CallGraphDOTInfo *CGInfo) {
153 if (CallMultiGraph || Node->getFunction())
154 return false;
155 return true;
156 }
157
getNodeLabelllvm::DOTGraphTraits158 std::string getNodeLabel(const CallGraphNode *Node,
159 CallGraphDOTInfo *CGInfo) {
160 if (Node == CGInfo->getCallGraph()->getExternalCallingNode())
161 return "external caller";
162 if (Node == CGInfo->getCallGraph()->getCallsExternalNode())
163 return "external callee";
164
165 if (Function *Func = Node->getFunction())
166 return std::string(Func->getName());
167 return "external node";
168 }
CGGetValuePtrllvm::DOTGraphTraits169 static const CallGraphNode *CGGetValuePtr(CallGraphNode::CallRecord P) {
170 return P.second;
171 }
172
173 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
174 typedef mapped_iterator<CallGraphNode::const_iterator,
175 decltype(&CGGetValuePtr)>
176 nodes_iterator;
177
getEdgeAttributesllvm::DOTGraphTraits178 std::string getEdgeAttributes(const CallGraphNode *Node, nodes_iterator I,
179 CallGraphDOTInfo *CGInfo) {
180 if (!ShowEdgeWeight)
181 return "";
182
183 Function *Caller = Node->getFunction();
184 if (Caller == nullptr || Caller->isDeclaration())
185 return "";
186
187 Function *Callee = (*I)->getFunction();
188 if (Callee == nullptr)
189 return "";
190
191 uint64_t Counter = getNumOfCalls(*Caller, *Callee);
192 double Width =
193 1 + 2 * (double(Counter) / CGInfo->getMaxFreq());
194 std::string Attrs = "label=\"" + std::to_string(Counter) +
195 "\" penwidth=" + std::to_string(Width);
196 return Attrs;
197 }
198
getNodeAttributesllvm::DOTGraphTraits199 std::string getNodeAttributes(const CallGraphNode *Node,
200 CallGraphDOTInfo *CGInfo) {
201 Function *F = Node->getFunction();
202 if (F == nullptr)
203 return "";
204 std::string attrs;
205 if (ShowHeatColors) {
206 uint64_t freq = CGInfo->getFreq(F);
207 std::string color = getHeatColor(freq, CGInfo->getMaxFreq());
208 std::string edgeColor = (freq <= (CGInfo->getMaxFreq() / 2))
209 ? getHeatColor(0)
210 : getHeatColor(1);
211 attrs = "color=\"" + edgeColor + "ff\", style=filled, fillcolor=\"" +
212 color + "80\"";
213 }
214 return attrs;
215 }
216 };
217
218 } // end llvm namespace
219
220 namespace {
doCallGraphDOTPrinting(Module & M,function_ref<BlockFrequencyInfo * (Function &)> LookupBFI)221 void doCallGraphDOTPrinting(
222 Module &M, function_ref<BlockFrequencyInfo *(Function &)> LookupBFI) {
223 std::string Filename;
224 if (!CallGraphDotFilenamePrefix.empty())
225 Filename = (CallGraphDotFilenamePrefix + ".callgraph.dot");
226 else
227 Filename = (std::string(M.getModuleIdentifier()) + ".callgraph.dot");
228 errs() << "Writing '" << Filename << "'...";
229
230 std::error_code EC;
231 raw_fd_ostream File(Filename, EC, sys::fs::OF_Text);
232
233 CallGraph CG(M);
234 CallGraphDOTInfo CFGInfo(&M, &CG, LookupBFI);
235
236 if (!EC)
237 WriteGraph(File, &CFGInfo);
238 else
239 errs() << " error opening file for writing!";
240 errs() << "\n";
241 }
242
viewCallGraph(Module & M,function_ref<BlockFrequencyInfo * (Function &)> LookupBFI)243 void viewCallGraph(Module &M,
244 function_ref<BlockFrequencyInfo *(Function &)> LookupBFI) {
245 CallGraph CG(M);
246 CallGraphDOTInfo CFGInfo(&M, &CG, LookupBFI);
247
248 std::string Title =
249 DOTGraphTraits<CallGraphDOTInfo *>::getGraphName(&CFGInfo);
250 ViewGraph(&CFGInfo, "callgraph", true, Title);
251 }
252 } // namespace
253
254 namespace llvm {
run(Module & M,ModuleAnalysisManager & AM)255 PreservedAnalyses CallGraphDOTPrinterPass::run(Module &M,
256 ModuleAnalysisManager &AM) {
257 FunctionAnalysisManager &FAM =
258 AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
259
260 auto LookupBFI = [&FAM](Function &F) {
261 return &FAM.getResult<BlockFrequencyAnalysis>(F);
262 };
263
264 doCallGraphDOTPrinting(M, LookupBFI);
265
266 return PreservedAnalyses::all();
267 }
268
run(Module & M,ModuleAnalysisManager & AM)269 PreservedAnalyses CallGraphViewerPass::run(Module &M,
270 ModuleAnalysisManager &AM) {
271
272 FunctionAnalysisManager &FAM =
273 AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
274
275 auto LookupBFI = [&FAM](Function &F) {
276 return &FAM.getResult<BlockFrequencyAnalysis>(F);
277 };
278
279 viewCallGraph(M, LookupBFI);
280
281 return PreservedAnalyses::all();
282 }
283 } // namespace llvm
284
285 namespace {
286 // Viewer
287 class CallGraphViewer : public ModulePass {
288 public:
289 static char ID;
CallGraphViewer()290 CallGraphViewer() : ModulePass(ID) {}
291
292 void getAnalysisUsage(AnalysisUsage &AU) const override;
293 bool runOnModule(Module &M) override;
294 };
295
getAnalysisUsage(AnalysisUsage & AU) const296 void CallGraphViewer::getAnalysisUsage(AnalysisUsage &AU) const {
297 ModulePass::getAnalysisUsage(AU);
298 AU.addRequired<BlockFrequencyInfoWrapperPass>();
299 AU.setPreservesAll();
300 }
301
runOnModule(Module & M)302 bool CallGraphViewer::runOnModule(Module &M) {
303 auto LookupBFI = [this](Function &F) {
304 return &this->getAnalysis<BlockFrequencyInfoWrapperPass>(F).getBFI();
305 };
306
307 viewCallGraph(M, LookupBFI);
308
309 return false;
310 }
311
312 // DOT Printer
313
314 class CallGraphDOTPrinter : public ModulePass {
315 public:
316 static char ID;
CallGraphDOTPrinter()317 CallGraphDOTPrinter() : ModulePass(ID) {}
318
319 void getAnalysisUsage(AnalysisUsage &AU) const override;
320 bool runOnModule(Module &M) override;
321 };
322
getAnalysisUsage(AnalysisUsage & AU) const323 void CallGraphDOTPrinter::getAnalysisUsage(AnalysisUsage &AU) const {
324 ModulePass::getAnalysisUsage(AU);
325 AU.addRequired<BlockFrequencyInfoWrapperPass>();
326 AU.setPreservesAll();
327 }
328
runOnModule(Module & M)329 bool CallGraphDOTPrinter::runOnModule(Module &M) {
330 auto LookupBFI = [this](Function &F) {
331 return &this->getAnalysis<BlockFrequencyInfoWrapperPass>(F).getBFI();
332 };
333
334 doCallGraphDOTPrinting(M, LookupBFI);
335
336 return false;
337 }
338
339 } // end anonymous namespace
340
341 char CallGraphViewer::ID = 0;
342 INITIALIZE_PASS(CallGraphViewer, "view-callgraph", "View call graph", false,
343 false)
344
345 char CallGraphDOTPrinter::ID = 0;
346 INITIALIZE_PASS(CallGraphDOTPrinter, "dot-callgraph",
347 "Print call graph to 'dot' file", false, false)
348
349 // Create methods available outside of this file, to use them
350 // "include/llvm/LinkAllPasses.h". Otherwise the pass would be deleted by
351 // the link time optimization.
352
createCallGraphViewerPass()353 ModulePass *llvm::createCallGraphViewerPass() { return new CallGraphViewer(); }
354
createCallGraphDOTPrinterPass()355 ModulePass *llvm::createCallGraphDOTPrinterPass() {
356 return new CallGraphDOTPrinter();
357 }
358