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