LLVM 19.0.0git
CallGraph.cpp
Go to the documentation of this file.
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
11#include "llvm/ADT/STLExtras.h"
13#include "llvm/Config/llvm-config.h"
15#include "llvm/IR/Function.h"
17#include "llvm/IR/Module.h"
18#include "llvm/IR/PassManager.h"
20#include "llvm/Pass.h"
22#include "llvm/Support/Debug.h"
24#include <cassert>
25
26using namespace llvm;
27
28//===----------------------------------------------------------------------===//
29// Implementations of the CallGraph class methods.
30//
31
33 : M(M), ExternalCallingNode(getOrInsertFunction(nullptr)),
34 CallsExternalNode(std::make_unique<CallGraphNode>(this, nullptr)) {
35 // Add every interesting function to the call graph.
36 for (Function &F : M)
37 if (!isDbgInfoIntrinsic(F.getIntrinsicID()))
39}
40
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
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
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
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 */ false))
84 ExternalCallingNode->addCalledFunction(nullptr, Node);
85
87}
88
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(Attribute::NoCallback))
95 Node->addCalledFunction(nullptr, 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>(&I)) {
101 const Function *Callee = Call->getCalledFunction();
102 if (!Callee)
103 Node->addCalledFunction(Call, CallsExternalNode.get());
104 else if (!isDbgInfoIntrinsic(Callee->getIntrinsicID()))
105 Node->addCalledFunction(Call, getOrInsertFunction(Callee));
106
107 // Add reference to callback functions.
108 forEachCallbackFunction(*Call, [=](Function *CB) {
109 Node->addCalledFunction(nullptr, getOrInsertFunction(CB));
110 });
111 }
112 }
113}
114
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
120 Nodes.reserve(FunctionMap.size());
121
122 for (const auto &I : *this)
123 Nodes.push_back(I.second.get());
124
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)
139#endif
140
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//
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(F); // Remove the call graph node from the map
162
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.
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>(this, const_cast<Function *>(F));
177 return CGN.get();
178}
179
180//===----------------------------------------------------------------------===//
181// Implementations of the CallGraphNode class methods.
182//
183
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)
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.
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(Call, [=](Function *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.
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.
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.
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.
271 forEachCallbackFunction(Call, [this, &OldCBs](Function *CB) {
272 OldCBs.push_back(CG->getOrInsertFunction(CB));
273 });
274 forEachCallbackFunction(NewCall, [this, &NewCBs](Function *CB) {
275 NewCBs.push_back(CG->getOrInsertFunction(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)
295 for (auto *CGN : NewCBs)
296 addCalledFunction(nullptr, CGN);
297 }
298 return;
299 }
300 }
301}
302
303// Provide an explicit template instantiation for the static ID.
304AnalysisKey CallGraphAnalysis::Key;
305
309 return PreservedAnalyses::all();
310}
311
314 auto &CG = AM.getResult<CallGraphAnalysis>(M);
315 unsigned sccNum = 0;
316 OS << "SCCs for the program in PostOrder:";
317 for (scc_iterator<CallGraph *> SCCI = scc_begin(&CG); !SCCI.isAtEnd();
318 ++SCCI) {
319 const std::vector<CallGraphNode *> &nextSCC = *SCCI;
320 OS << "\nSCC #" << ++sccNum << ": ";
321 bool First = true;
322 for (std::vector<CallGraphNode *>::const_iterator I = nextSCC.begin(),
323 E = nextSCC.end();
324 I != E; ++I) {
325 if (First)
326 First = false;
327 else
328 OS << ", ";
329 OS << ((*I)->getFunction() ? (*I)->getFunction()->getName()
330 : "external node");
331 }
332
333 if (nextSCC.size() == 1 && SCCI.hasCycle())
334 OS << " (Has self-loop).";
335 }
336 OS << "\n";
337 return PreservedAnalyses::all();
338}
339
340//===----------------------------------------------------------------------===//
341// Out-of-line definitions of CallGraphAnalysis class members.
342//
343
344//===----------------------------------------------------------------------===//
345// Implementations of the CallGraphWrapperPass class methods.
346//
347
350}
351
353
355 AU.setPreservesAll();
356}
357
359 // All the real work is done in the constructor for the CallGraph.
360 G.reset(new CallGraph(M));
361 return false;
362}
363
364INITIALIZE_PASS(CallGraphWrapperPass, "basiccg", "CallGraph Construction",
365 false, true)
366
368
369void CallGraphWrapperPass::releaseMemory() { G.reset(); }
370
372 if (!G) {
373 OS << "No call graph has been built!\n";
374 return;
375 }
376
377 // Just delegate.
378 G->print(OS);
379}
380
381#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
383void CallGraphWrapperPass::dump() const { print(dbgs(), nullptr); }
384#endif
This file provides interfaces used to build and manipulate a call graph, which is a very useful tool ...
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:529
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
#define G(x, y, z)
Definition: MD5.cpp:56
Module.h This file contains the declarations for the Module class.
#define P(N)
if(VerifyEach)
This header defines various interfaces for pass management in LLVM.
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:38
This builds on the llvm/ADT/GraphTraits.h file to find the strongly connected components (SCCs) of a ...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file contains some templates that are useful if you are working with the STL at all.
raw_pwrite_stream & OS
This file defines the SmallVector class.
Value * RHS
Value * LHS
This templated class represents "all analyses that operate over <a particular IR unit>" (e....
Definition: Analysis.h:47
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:387
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:348
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:500
Represent the analysis usage information of a pass.
void setPreservesAll()
Set by analyses that do not transform their input at all.
LLVM Basic Block Representation.
Definition: BasicBlock.h:60
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1461
An analysis pass to compute the CallGraph for a Module.
Definition: CallGraph.h:302
A node in the call graph for a module.
Definition: CallGraph.h:166
void removeCallEdgeFor(CallBase &Call)
Removes the edge in the node for the specified call site.
Definition: CallGraph.cpp:209
void print(raw_ostream &OS) const
Definition: CallGraph.cpp:184
bool empty() const
Definition: CallGraph.h:203
void addCalledFunction(CallBase *Call, CallGraphNode *M)
Adds a function to the list of functions called by this one.
Definition: CallGraph.h:242
void replaceCallEdge(CallBase &Call, CallBase &NewCall, CallGraphNode *NewNode)
Replaces the edge in the node for the specified call site with a new one.
Definition: CallGraph.cpp:257
void dump() const
Print out this call graph node.
Definition: CallGraph.cpp:203
Function * getFunction() const
Returns the function that this call graph node represents.
Definition: CallGraph.h:197
void removeOneAbstractEdgeTo(CallGraphNode *Callee)
Removes one edge associated with a null callsite from this node to the specified callee function.
Definition: CallGraph.cpp:241
unsigned getNumReferences() const
Returns the number of other CallGraphNodes in this CallGraph that reference this node in their callee...
Definition: CallGraph.h:208
void removeAnyCallEdgeTo(CallGraphNode *Callee)
Removes all call edges from this node to the specified callee function.
Definition: CallGraph.cpp:229
std::pair< std::optional< WeakTrackingVH >, CallGraphNode * > CallRecord
A pair of the calling instruction (a call or invoke) and the call graph node being called.
Definition: CallGraph.h:178
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
Definition: CallGraph.cpp:306
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
Definition: CallGraph.cpp:312
The ModulePass which wraps up a CallGraph and the logic to build it.
Definition: CallGraph.h:349
bool runOnModule(Module &M) override
runOnModule - Virtual method overriden by subclasses to process the module being operated on.
Definition: CallGraph.cpp:358
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: CallGraph.cpp:354
void print(raw_ostream &o, const Module *) const override
print - Print out the internal state of the pass.
Definition: CallGraph.cpp:371
The basic data container for the call graph of a Module of IR.
Definition: CallGraph.h:72
Function * removeFunctionFromModule(CallGraphNode *CGN)
Unlink the function from this module, returning it.
Definition: CallGraph.cpp:157
void print(raw_ostream &OS) const
Definition: CallGraph.cpp:115
void dump() const
Definition: CallGraph.cpp:138
void populateCallGraphNode(CallGraphNode *CGN)
Populate CGN based on the calls inside the associated function.
Definition: CallGraph.cpp:89
void addToCallGraph(Function *F)
Add a function to the call graph, and link the node to all of the functions that it calls.
Definition: CallGraph.cpp:75
CallGraphNode * getOrInsertFunction(const Function *F)
Similar to operator[], but this will insert a new CallGraphNode for F if one does not already exist.
Definition: CallGraph.cpp:170
bool invalidate(Module &, const PreservedAnalyses &PA, ModuleAnalysisManager::Invalidator &)
Definition: CallGraph.cpp:67
CallGraph(Module &M)
Definition: CallGraph.cpp:32
void ReplaceExternalCallEdge(CallGraphNode *Old, CallGraphNode *New)
Old node has been deleted, and New is to be used in its place, update the ExternalCallingNode.
Definition: CallGraph.cpp:141
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
Definition: Pass.h:251
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
const FunctionListType & getFunctionList() const
Get the Module's list of functions (constant).
Definition: Module.h:605
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:109
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: Analysis.h:115
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
Definition: Analysis.h:264
size_t size() const
Definition: SmallVector.h:91
void reserve(size_type N)
Definition: SmallVector.h:676
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
pointer remove(iterator &IT)
Definition: ilist.h:188
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
Enumerate the SCCs of a directed graph in reverse topological order of the SCC DAG.
Definition: SCCIterator.h:49
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
scc_iterator< T > scc_begin(const T &G)
Construct the begin iterator for a deduced graph type T.
Definition: SCCIterator.h:233
Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr)
void initializeCallGraphWrapperPassPass(PassRegistry &)
static bool isDbgInfoIntrinsic(Intrinsic::ID ID)
Check if ID corresponds to a debug info intrinsic.
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1656
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
@ First
Helpers to iterate all locations in the MemoryEffectsBase class.
void forEachCallbackFunction(const CallBase &CB, UnaryFunction Func)
Apply function Func to each CB's callback function.
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1858
Implement std::hash so that hash_code can be used in STL containers.
Definition: BitVector.h:858
#define N
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: Analysis.h:26