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