1 //===- CallGraph.cpp - Build a Module's 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 #include "llvm/Analysis/CallGraph.h"
10 #include "llvm/ADT/STLExtras.h"
11 #include "llvm/ADT/SmallVector.h"
12 #include "llvm/Config/llvm-config.h"
13 #include "llvm/IR/AbstractCallSite.h"
14 #include "llvm/IR/Function.h"
15 #include "llvm/IR/IntrinsicInst.h"
16 #include "llvm/IR/Intrinsics.h"
17 #include "llvm/IR/Module.h"
18 #include "llvm/IR/PassManager.h"
19 #include "llvm/InitializePasses.h"
20 #include "llvm/Pass.h"
21 #include "llvm/Support/Compiler.h"
22 #include "llvm/Support/Debug.h"
23 #include "llvm/Support/raw_ostream.h"
24 #include <algorithm>
25 #include <cassert>
26
27 using namespace llvm;
28
29 //===----------------------------------------------------------------------===//
30 // Implementations of the CallGraph class methods.
31 //
32
CallGraph(Module & M)33 CallGraph::CallGraph(Module &M)
34 : M(M), ExternalCallingNode(getOrInsertFunction(nullptr)),
35 CallsExternalNode(std::make_unique<CallGraphNode>(this, nullptr)) {
36 // Add every interesting function to the call graph.
37 for (Function &F : M)
38 if (!isDbgInfoIntrinsic(F.getIntrinsicID()))
39 addToCallGraph(&F);
40 }
41
CallGraph(CallGraph && Arg)42 CallGraph::CallGraph(CallGraph &&Arg)
43 : M(Arg.M), FunctionMap(std::move(Arg.FunctionMap)),
44 ExternalCallingNode(Arg.ExternalCallingNode),
45 CallsExternalNode(std::move(Arg.CallsExternalNode)) {
46 Arg.FunctionMap.clear();
47 Arg.ExternalCallingNode = nullptr;
48
49 // Update parent CG for all call graph's nodes.
50 CallsExternalNode->CG = this;
51 for (auto &P : FunctionMap)
52 P.second->CG = this;
53 }
54
~CallGraph()55 CallGraph::~CallGraph() {
56 // CallsExternalNode is not in the function map, delete it explicitly.
57 if (CallsExternalNode)
58 CallsExternalNode->allReferencesDropped();
59
60 // Reset all node's use counts to zero before deleting them to prevent an
61 // assertion from firing.
62 #ifndef NDEBUG
63 for (auto &I : FunctionMap)
64 I.second->allReferencesDropped();
65 #endif
66 }
67
invalidate(Module &,const PreservedAnalyses & PA,ModuleAnalysisManager::Invalidator &)68 bool CallGraph::invalidate(Module &, const PreservedAnalyses &PA,
69 ModuleAnalysisManager::Invalidator &) {
70 // Check whether the analysis, all analyses on functions, or the function's
71 // CFG have been preserved.
72 auto PAC = PA.getChecker<CallGraphAnalysis>();
73 return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Module>>() ||
74 PAC.preservedSet<CFGAnalyses>());
75 }
76
addToCallGraph(Function * F)77 void CallGraph::addToCallGraph(Function *F) {
78 CallGraphNode *Node = getOrInsertFunction(F);
79
80 // If this function has external linkage or has its address taken and
81 // it is not a callback, then anything could call it.
82 if (!F->hasLocalLinkage() ||
83 F->hasAddressTaken(nullptr, /*IgnoreCallbackUses=*/true,
84 /* IgnoreAssumeLikeCalls */ true,
85 /* IgnoreLLVMUsed */ false))
86 ExternalCallingNode->addCalledFunction(nullptr, Node);
87
88 populateCallGraphNode(Node);
89 }
90
populateCallGraphNode(CallGraphNode * Node)91 void CallGraph::populateCallGraphNode(CallGraphNode *Node) {
92 Function *F = Node->getFunction();
93
94 // If this function is not defined in this translation unit, it could call
95 // anything.
96 if (F->isDeclaration() && !F->isIntrinsic())
97 Node->addCalledFunction(nullptr, CallsExternalNode.get());
98
99 // Look for calls by this function.
100 for (BasicBlock &BB : *F)
101 for (Instruction &I : BB) {
102 if (auto *Call = dyn_cast<CallBase>(&I)) {
103 const Function *Callee = Call->getCalledFunction();
104 if (!Callee || !Intrinsic::isLeaf(Callee->getIntrinsicID()))
105 // Indirect calls of intrinsics are not allowed so no need to check.
106 // We can be more precise here by using TargetArg returned by
107 // Intrinsic::isLeaf.
108 Node->addCalledFunction(Call, CallsExternalNode.get());
109 else if (!Callee->isIntrinsic())
110 Node->addCalledFunction(Call, getOrInsertFunction(Callee));
111
112 // Add reference to callback functions.
113 forEachCallbackFunction(*Call, [=](Function *CB) {
114 Node->addCalledFunction(nullptr, getOrInsertFunction(CB));
115 });
116 }
117 }
118 }
119
print(raw_ostream & OS) const120 void CallGraph::print(raw_ostream &OS) const {
121 // Print in a deterministic order by sorting CallGraphNodes by name. We do
122 // this here to avoid slowing down the non-printing fast path.
123
124 SmallVector<CallGraphNode *, 16> Nodes;
125 Nodes.reserve(FunctionMap.size());
126
127 for (const auto &I : *this)
128 Nodes.push_back(I.second.get());
129
130 llvm::sort(Nodes, [](CallGraphNode *LHS, CallGraphNode *RHS) {
131 if (Function *LF = LHS->getFunction())
132 if (Function *RF = RHS->getFunction())
133 return LF->getName() < RF->getName();
134
135 return RHS->getFunction() != nullptr;
136 });
137
138 for (CallGraphNode *CN : Nodes)
139 CN->print(OS);
140 }
141
142 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
dump() const143 LLVM_DUMP_METHOD void CallGraph::dump() const { print(dbgs()); }
144 #endif
145
ReplaceExternalCallEdge(CallGraphNode * Old,CallGraphNode * New)146 void CallGraph::ReplaceExternalCallEdge(CallGraphNode *Old,
147 CallGraphNode *New) {
148 for (auto &CR : ExternalCallingNode->CalledFunctions)
149 if (CR.second == Old) {
150 CR.second->DropRef();
151 CR.second = New;
152 CR.second->AddRef();
153 }
154 }
155
156 // removeFunctionFromModule - Unlink the function from this module, returning
157 // it. Because this removes the function from the module, the call graph node
158 // is destroyed. This is only valid if the function does not call any other
159 // functions (ie, there are no edges in it's CGN). The easiest way to do this
160 // is to dropAllReferences before calling this.
161 //
removeFunctionFromModule(CallGraphNode * CGN)162 Function *CallGraph::removeFunctionFromModule(CallGraphNode *CGN) {
163 assert(CGN->empty() && "Cannot remove function from call "
164 "graph if it references other functions!");
165 Function *F = CGN->getFunction(); // Get the function for the call graph node
166 FunctionMap.erase(F); // Remove the call graph node from the map
167
168 M.getFunctionList().remove(F);
169 return F;
170 }
171
172 // getOrInsertFunction - This method is identical to calling operator[], but
173 // it will insert a new CallGraphNode for the specified function if one does
174 // not already exist.
getOrInsertFunction(const Function * F)175 CallGraphNode *CallGraph::getOrInsertFunction(const Function *F) {
176 auto &CGN = FunctionMap[F];
177 if (CGN)
178 return CGN.get();
179
180 assert((!F || F->getParent() == &M) && "Function not in current module!");
181 CGN = std::make_unique<CallGraphNode>(this, const_cast<Function *>(F));
182 return CGN.get();
183 }
184
185 //===----------------------------------------------------------------------===//
186 // Implementations of the CallGraphNode class methods.
187 //
188
print(raw_ostream & OS) const189 void CallGraphNode::print(raw_ostream &OS) const {
190 if (Function *F = getFunction())
191 OS << "Call graph node for function: '" << F->getName() << "'";
192 else
193 OS << "Call graph node <<null function>>";
194
195 OS << "<<" << this << ">> #uses=" << getNumReferences() << '\n';
196
197 for (const auto &I : *this) {
198 OS << " CS<" << I.first << "> calls ";
199 if (Function *FI = I.second->getFunction())
200 OS << "function '" << FI->getName() <<"'\n";
201 else
202 OS << "external node\n";
203 }
204 OS << '\n';
205 }
206
207 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
dump() const208 LLVM_DUMP_METHOD void CallGraphNode::dump() const { print(dbgs()); }
209 #endif
210
211 /// removeCallEdgeFor - This method removes the edge in the node for the
212 /// specified call site. Note that this method takes linear time, so it
213 /// should be used sparingly.
removeCallEdgeFor(CallBase & Call)214 void CallGraphNode::removeCallEdgeFor(CallBase &Call) {
215 for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) {
216 assert(I != CalledFunctions.end() && "Cannot find callsite to remove!");
217 if (I->first && *I->first == &Call) {
218 I->second->DropRef();
219 *I = CalledFunctions.back();
220 CalledFunctions.pop_back();
221
222 // Remove all references to callback functions if there are any.
223 forEachCallbackFunction(Call, [=](Function *CB) {
224 removeOneAbstractEdgeTo(CG->getOrInsertFunction(CB));
225 });
226 return;
227 }
228 }
229 }
230
231 // removeAnyCallEdgeTo - This method removes any call edges from this node to
232 // the specified callee function. This takes more time to execute than
233 // removeCallEdgeTo, so it should not be used unless necessary.
removeAnyCallEdgeTo(CallGraphNode * Callee)234 void CallGraphNode::removeAnyCallEdgeTo(CallGraphNode *Callee) {
235 for (unsigned i = 0, e = CalledFunctions.size(); i != e; ++i)
236 if (CalledFunctions[i].second == Callee) {
237 Callee->DropRef();
238 CalledFunctions[i] = CalledFunctions.back();
239 CalledFunctions.pop_back();
240 --i; --e;
241 }
242 }
243
244 /// removeOneAbstractEdgeTo - Remove one edge associated with a null callsite
245 /// from this node to the specified callee function.
removeOneAbstractEdgeTo(CallGraphNode * Callee)246 void CallGraphNode::removeOneAbstractEdgeTo(CallGraphNode *Callee) {
247 for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) {
248 assert(I != CalledFunctions.end() && "Cannot find callee to remove!");
249 CallRecord &CR = *I;
250 if (CR.second == Callee && !CR.first) {
251 Callee->DropRef();
252 *I = CalledFunctions.back();
253 CalledFunctions.pop_back();
254 return;
255 }
256 }
257 }
258
259 /// replaceCallEdge - This method replaces the edge in the node for the
260 /// specified call site with a new one. Note that this method takes linear
261 /// time, so it should be used sparingly.
replaceCallEdge(CallBase & Call,CallBase & NewCall,CallGraphNode * NewNode)262 void CallGraphNode::replaceCallEdge(CallBase &Call, CallBase &NewCall,
263 CallGraphNode *NewNode) {
264 for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) {
265 assert(I != CalledFunctions.end() && "Cannot find callsite to remove!");
266 if (I->first && *I->first == &Call) {
267 I->second->DropRef();
268 I->first = &NewCall;
269 I->second = NewNode;
270 NewNode->AddRef();
271
272 // Refresh callback references. Do not resize CalledFunctions if the
273 // number of callbacks is the same for new and old call sites.
274 SmallVector<CallGraphNode *, 4u> OldCBs;
275 SmallVector<CallGraphNode *, 4u> NewCBs;
276 forEachCallbackFunction(Call, [this, &OldCBs](Function *CB) {
277 OldCBs.push_back(CG->getOrInsertFunction(CB));
278 });
279 forEachCallbackFunction(NewCall, [this, &NewCBs](Function *CB) {
280 NewCBs.push_back(CG->getOrInsertFunction(CB));
281 });
282 if (OldCBs.size() == NewCBs.size()) {
283 for (unsigned N = 0; N < OldCBs.size(); ++N) {
284 CallGraphNode *OldNode = OldCBs[N];
285 CallGraphNode *NewNode = NewCBs[N];
286 for (auto J = CalledFunctions.begin();; ++J) {
287 assert(J != CalledFunctions.end() &&
288 "Cannot find callsite to update!");
289 if (!J->first && J->second == OldNode) {
290 J->second = NewNode;
291 OldNode->DropRef();
292 NewNode->AddRef();
293 break;
294 }
295 }
296 }
297 } else {
298 for (auto *CGN : OldCBs)
299 removeOneAbstractEdgeTo(CGN);
300 for (auto *CGN : NewCBs)
301 addCalledFunction(nullptr, CGN);
302 }
303 return;
304 }
305 }
306 }
307
308 // Provide an explicit template instantiation for the static ID.
309 AnalysisKey CallGraphAnalysis::Key;
310
run(Module & M,ModuleAnalysisManager & AM)311 PreservedAnalyses CallGraphPrinterPass::run(Module &M,
312 ModuleAnalysisManager &AM) {
313 AM.getResult<CallGraphAnalysis>(M).print(OS);
314 return PreservedAnalyses::all();
315 }
316
317 //===----------------------------------------------------------------------===//
318 // Out-of-line definitions of CallGraphAnalysis class members.
319 //
320
321 //===----------------------------------------------------------------------===//
322 // Implementations of the CallGraphWrapperPass class methods.
323 //
324
CallGraphWrapperPass()325 CallGraphWrapperPass::CallGraphWrapperPass() : ModulePass(ID) {
326 initializeCallGraphWrapperPassPass(*PassRegistry::getPassRegistry());
327 }
328
329 CallGraphWrapperPass::~CallGraphWrapperPass() = default;
330
getAnalysisUsage(AnalysisUsage & AU) const331 void CallGraphWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
332 AU.setPreservesAll();
333 }
334
runOnModule(Module & M)335 bool CallGraphWrapperPass::runOnModule(Module &M) {
336 // All the real work is done in the constructor for the CallGraph.
337 G.reset(new CallGraph(M));
338 return false;
339 }
340
341 INITIALIZE_PASS(CallGraphWrapperPass, "basiccg", "CallGraph Construction",
342 false, true)
343
344 char CallGraphWrapperPass::ID = 0;
345
releaseMemory()346 void CallGraphWrapperPass::releaseMemory() { G.reset(); }
347
print(raw_ostream & OS,const Module *) const348 void CallGraphWrapperPass::print(raw_ostream &OS, const Module *) const {
349 if (!G) {
350 OS << "No call graph has been built!\n";
351 return;
352 }
353
354 // Just delegate.
355 G->print(OS);
356 }
357
358 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
359 LLVM_DUMP_METHOD
dump() const360 void CallGraphWrapperPass::dump() const { print(dbgs(), nullptr); }
361 #endif
362
363 namespace {
364
365 struct CallGraphPrinterLegacyPass : public ModulePass {
366 static char ID; // Pass ID, replacement for typeid
367
CallGraphPrinterLegacyPass__anon57befa8c0611::CallGraphPrinterLegacyPass368 CallGraphPrinterLegacyPass() : ModulePass(ID) {
369 initializeCallGraphPrinterLegacyPassPass(*PassRegistry::getPassRegistry());
370 }
371
getAnalysisUsage__anon57befa8c0611::CallGraphPrinterLegacyPass372 void getAnalysisUsage(AnalysisUsage &AU) const override {
373 AU.setPreservesAll();
374 AU.addRequiredTransitive<CallGraphWrapperPass>();
375 }
376
runOnModule__anon57befa8c0611::CallGraphPrinterLegacyPass377 bool runOnModule(Module &M) override {
378 getAnalysis<CallGraphWrapperPass>().print(errs(), &M);
379 return false;
380 }
381 };
382
383 } // end anonymous namespace
384
385 char CallGraphPrinterLegacyPass::ID = 0;
386
387 INITIALIZE_PASS_BEGIN(CallGraphPrinterLegacyPass, "print-callgraph",
388 "Print a call graph", true, true)
389 INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass)
390 INITIALIZE_PASS_END(CallGraphPrinterLegacyPass, "print-callgraph",
391 "Print a call graph", true, true)
392