1 //===- CallGraph.cpp - Build a Module's call graph ------------------------===//
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
7 //===----------------------------------------------------------------------===//
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"
29 //===----------------------------------------------------------------------===//
30 // Implementations of the CallGraph class methods.
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.
38 if (!isDbgInfoIntrinsic(F.getIntrinsicID()))
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;
49 // Update parent CG for all call graph's nodes.
50 CallsExternalNode->CG = this;
51 for (auto &P : FunctionMap)
55 CallGraph::~CallGraph() {
56 // CallsExternalNode is not in the function map, delete it explicitly.
57 if (CallsExternalNode)
58 CallsExternalNode->allReferencesDropped();
60 // Reset all node's use counts to zero before deleting them to prevent an
61 // assertion from firing.
63 for (auto &I : FunctionMap)
64 I.second->allReferencesDropped();
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>());
77 void CallGraph::addToCallGraph(Function *F) {
78 CallGraphNode *Node = getOrInsertFunction(F);
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 ExternalCallingNode->addCalledFunction(nullptr, Node);
86 populateCallGraphNode(Node);
89 void CallGraph::populateCallGraphNode(CallGraphNode *Node) {
90 Function *F = Node->getFunction();
92 // If this function is not defined in this translation unit, it could call
94 if (F->isDeclaration() && !F->isIntrinsic())
95 Node->addCalledFunction(nullptr, CallsExternalNode.get());
97 // Look for calls by this function.
98 for (BasicBlock &BB : *F)
99 for (Instruction &I : BB) {
100 if (auto *Call = dyn_cast<CallBase>(&I)) {
101 const Function *Callee = Call->getCalledFunction();
102 if (!Callee || !Intrinsic::isLeaf(Callee->getIntrinsicID()))
103 // Indirect calls of intrinsics are not allowed so no need to check.
104 // We can be more precise here by using TargetArg returned by
105 // Intrinsic::isLeaf.
106 Node->addCalledFunction(Call, CallsExternalNode.get());
107 else if (!Callee->isIntrinsic())
108 Node->addCalledFunction(Call, getOrInsertFunction(Callee));
110 // Add reference to callback functions.
111 forEachCallbackFunction(*Call, [=](Function *CB) {
112 Node->addCalledFunction(nullptr, getOrInsertFunction(CB));
118 void CallGraph::print(raw_ostream &OS) const {
119 // Print in a deterministic order by sorting CallGraphNodes by name. We do
120 // this here to avoid slowing down the non-printing fast path.
122 SmallVector<CallGraphNode *, 16> Nodes;
123 Nodes.reserve(FunctionMap.size());
125 for (const auto &I : *this)
126 Nodes.push_back(I.second.get());
128 llvm::sort(Nodes, [](CallGraphNode *LHS, CallGraphNode *RHS) {
129 if (Function *LF = LHS->getFunction())
130 if (Function *RF = RHS->getFunction())
131 return LF->getName() < RF->getName();
133 return RHS->getFunction() != nullptr;
136 for (CallGraphNode *CN : Nodes)
140 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
141 LLVM_DUMP_METHOD void CallGraph::dump() const { print(dbgs()); }
144 void CallGraph::ReplaceExternalCallEdge(CallGraphNode *Old,
145 CallGraphNode *New) {
146 for (auto &CR : ExternalCallingNode->CalledFunctions)
147 if (CR.second == Old) {
148 CR.second->DropRef();
154 // removeFunctionFromModule - Unlink the function from this module, returning
155 // it. Because this removes the function from the module, the call graph node
156 // is destroyed. This is only valid if the function does not call any other
157 // functions (ie, there are no edges in it's CGN). The easiest way to do this
158 // is to dropAllReferences before calling this.
160 Function *CallGraph::removeFunctionFromModule(CallGraphNode *CGN) {
161 assert(CGN->empty() && "Cannot remove function from call "
162 "graph if it references other functions!");
163 Function *F = CGN->getFunction(); // Get the function for the call graph node
164 FunctionMap.erase(F); // Remove the call graph node from the map
166 M.getFunctionList().remove(F);
170 /// spliceFunction - Replace the function represented by this node by another.
171 /// This does not rescan the body of the function, so it is suitable when
172 /// splicing the body of the old function to the new while also updating all
173 /// callers from old to new.
174 void CallGraph::spliceFunction(const Function *From, const Function *To) {
175 assert(FunctionMap.count(From) && "No CallGraphNode for function!");
176 assert(!FunctionMap.count(To) &&
177 "Pointing CallGraphNode at a function that already exists");
178 FunctionMapTy::iterator I = FunctionMap.find(From);
179 I->second->F = const_cast<Function*>(To);
180 FunctionMap[To] = std::move(I->second);
181 FunctionMap.erase(I);
184 // getOrInsertFunction - This method is identical to calling operator[], but
185 // it will insert a new CallGraphNode for the specified function if one does
186 // not already exist.
187 CallGraphNode *CallGraph::getOrInsertFunction(const Function *F) {
188 auto &CGN = FunctionMap[F];
192 assert((!F || F->getParent() == &M) && "Function not in current module!");
193 CGN = std::make_unique<CallGraphNode>(this, const_cast<Function *>(F));
197 //===----------------------------------------------------------------------===//
198 // Implementations of the CallGraphNode class methods.
201 void CallGraphNode::print(raw_ostream &OS) const {
202 if (Function *F = getFunction())
203 OS << "Call graph node for function: '" << F->getName() << "'";
205 OS << "Call graph node <<null function>>";
207 OS << "<<" << this << ">> #uses=" << getNumReferences() << '\n';
209 for (const auto &I : *this) {
210 OS << " CS<" << I.first << "> calls ";
211 if (Function *FI = I.second->getFunction())
212 OS << "function '" << FI->getName() <<"'\n";
214 OS << "external node\n";
219 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
220 LLVM_DUMP_METHOD void CallGraphNode::dump() const { print(dbgs()); }
223 /// removeCallEdgeFor - This method removes the edge in the node for the
224 /// specified call site. Note that this method takes linear time, so it
225 /// should be used sparingly.
226 void CallGraphNode::removeCallEdgeFor(CallBase &Call) {
227 for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) {
228 assert(I != CalledFunctions.end() && "Cannot find callsite to remove!");
229 if (I->first && *I->first == &Call) {
230 I->second->DropRef();
231 *I = CalledFunctions.back();
232 CalledFunctions.pop_back();
234 // Remove all references to callback functions if there are any.
235 forEachCallbackFunction(Call, [=](Function *CB) {
236 removeOneAbstractEdgeTo(CG->getOrInsertFunction(CB));
243 // removeAnyCallEdgeTo - This method removes any call edges from this node to
244 // the specified callee function. This takes more time to execute than
245 // removeCallEdgeTo, so it should not be used unless necessary.
246 void CallGraphNode::removeAnyCallEdgeTo(CallGraphNode *Callee) {
247 for (unsigned i = 0, e = CalledFunctions.size(); i != e; ++i)
248 if (CalledFunctions[i].second == Callee) {
250 CalledFunctions[i] = CalledFunctions.back();
251 CalledFunctions.pop_back();
256 /// removeOneAbstractEdgeTo - Remove one edge associated with a null callsite
257 /// from this node to the specified callee function.
258 void CallGraphNode::removeOneAbstractEdgeTo(CallGraphNode *Callee) {
259 for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) {
260 assert(I != CalledFunctions.end() && "Cannot find callee to remove!");
262 if (CR.second == Callee && !CR.first) {
264 *I = CalledFunctions.back();
265 CalledFunctions.pop_back();
271 /// replaceCallEdge - This method replaces the edge in the node for the
272 /// specified call site with a new one. Note that this method takes linear
273 /// time, so it should be used sparingly.
274 void CallGraphNode::replaceCallEdge(CallBase &Call, CallBase &NewCall,
275 CallGraphNode *NewNode) {
276 for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) {
277 assert(I != CalledFunctions.end() && "Cannot find callsite to remove!");
278 if (I->first && *I->first == &Call) {
279 I->second->DropRef();
284 // Refresh callback references.
285 forEachCallbackFunction(Call, [=](Function *CB) {
286 removeOneAbstractEdgeTo(CG->getOrInsertFunction(CB));
288 forEachCallbackFunction(NewCall, [=](Function *CB) {
289 addCalledFunction(nullptr, CG->getOrInsertFunction(CB));
296 // Provide an explicit template instantiation for the static ID.
297 AnalysisKey CallGraphAnalysis::Key;
299 PreservedAnalyses CallGraphPrinterPass::run(Module &M,
300 ModuleAnalysisManager &AM) {
301 AM.getResult<CallGraphAnalysis>(M).print(OS);
302 return PreservedAnalyses::all();
305 //===----------------------------------------------------------------------===//
306 // Out-of-line definitions of CallGraphAnalysis class members.
309 //===----------------------------------------------------------------------===//
310 // Implementations of the CallGraphWrapperPass class methods.
313 CallGraphWrapperPass::CallGraphWrapperPass() : ModulePass(ID) {
314 initializeCallGraphWrapperPassPass(*PassRegistry::getPassRegistry());
317 CallGraphWrapperPass::~CallGraphWrapperPass() = default;
319 void CallGraphWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
320 AU.setPreservesAll();
323 bool CallGraphWrapperPass::runOnModule(Module &M) {
324 // All the real work is done in the constructor for the CallGraph.
325 G.reset(new CallGraph(M));
329 INITIALIZE_PASS(CallGraphWrapperPass, "basiccg", "CallGraph Construction",
332 char CallGraphWrapperPass::ID = 0;
334 void CallGraphWrapperPass::releaseMemory() { G.reset(); }
336 void CallGraphWrapperPass::print(raw_ostream &OS, const Module *) const {
338 OS << "No call graph has been built!\n";
346 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
348 void CallGraphWrapperPass::dump() const { print(dbgs(), nullptr); }
353 struct CallGraphPrinterLegacyPass : public ModulePass {
354 static char ID; // Pass ID, replacement for typeid
356 CallGraphPrinterLegacyPass() : ModulePass(ID) {
357 initializeCallGraphPrinterLegacyPassPass(*PassRegistry::getPassRegistry());
360 void getAnalysisUsage(AnalysisUsage &AU) const override {
361 AU.setPreservesAll();
362 AU.addRequiredTransitive<CallGraphWrapperPass>();
365 bool runOnModule(Module &M) override {
366 getAnalysis<CallGraphWrapperPass>().print(errs(), &M);
371 } // end anonymous namespace
373 char CallGraphPrinterLegacyPass::ID = 0;
375 INITIALIZE_PASS_BEGIN(CallGraphPrinterLegacyPass, "print-callgraph",
376 "Print a call graph", true, true)
377 INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass)
378 INITIALIZE_PASS_END(CallGraphPrinterLegacyPass, "print-callgraph",
379 "Print a call graph", true, true)