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