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
26using namespace llvm;
27
28//===----------------------------------------------------------------------===//
29// Implementations of the CallGraph class methods.
30//
31
32CallGraph::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
41CallGraph::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
54CallGraph::~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
67bool 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
75void 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
89void 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
115void 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)
138LLVM_DUMP_METHOD void CallGraph::dump() const { print(dbgs()); }
139#endif
140
141void 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//
157Function *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.
170CallGraphNode *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
184void 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)
203LLVM_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.
209void 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.
229void 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.
241void 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.
257void 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.
304AnalysisKey CallGraphAnalysis::Key;
305
306PreservedAnalyses CallGraphPrinterPass::run(Module &M,
307 ModuleAnalysisManager &AM) {
308 AM.getResult<CallGraphAnalysis>(IR&: M).print(OS);
309 return PreservedAnalyses::all();
310}
311
312PreservedAnalyses 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
346CallGraphWrapperPass::CallGraphWrapperPass() : ModulePass(ID) {
347 initializeCallGraphWrapperPassPass(*PassRegistry::getPassRegistry());
348}
349
350CallGraphWrapperPass::~CallGraphWrapperPass() = default;
351
352void CallGraphWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
353 AU.setPreservesAll();
354}
355
356bool 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
362INITIALIZE_PASS(CallGraphWrapperPass, "basiccg", "CallGraph Construction",
363 false, true)
364
365char CallGraphWrapperPass::ID = 0;
366
367void CallGraphWrapperPass::releaseMemory() { G.reset(); }
368
369void 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)
380LLVM_DUMP_METHOD
381void CallGraphWrapperPass::dump() const { print(dbgs(), nullptr); }
382#endif
383