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