LLVM  10.0.0svn
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 
10 #include "llvm/ADT/STLExtras.h"
11 #include "llvm/ADT/SmallVector.h"
12 #include "llvm/Config/llvm-config.h"
13 #include "llvm/IR/Module.h"
14 #include "llvm/IR/Function.h"
15 #include "llvm/IR/Intrinsics.h"
16 #include "llvm/IR/PassManager.h"
17 #include "llvm/Pass.h"
18 #include "llvm/Support/Compiler.h"
19 #include "llvm/Support/Debug.h"
21 #include <algorithm>
22 #include <cassert>
23 
24 using namespace llvm;
25 
26 //===----------------------------------------------------------------------===//
27 // Implementations of the CallGraph class methods.
28 //
29 
31  : M(M), ExternalCallingNode(getOrInsertFunction(nullptr)),
32  CallsExternalNode(std::make_unique<CallGraphNode>(nullptr)) {
33  // Add every function to the call graph.
34  for (Function &F : M)
35  addToCallGraph(&F);
36 }
37 
39  : M(Arg.M), FunctionMap(std::move(Arg.FunctionMap)),
40  ExternalCallingNode(Arg.ExternalCallingNode),
41  CallsExternalNode(std::move(Arg.CallsExternalNode)) {
42  Arg.FunctionMap.clear();
43  Arg.ExternalCallingNode = nullptr;
44 }
45 
47  // CallsExternalNode is not in the function map, delete it explicitly.
48  if (CallsExternalNode)
49  CallsExternalNode->allReferencesDropped();
50 
51 // Reset all node's use counts to zero before deleting them to prevent an
52 // assertion from firing.
53 #ifndef NDEBUG
54  for (auto &I : FunctionMap)
55  I.second->allReferencesDropped();
56 #endif
57 }
58 
59 void CallGraph::addToCallGraph(Function *F) {
61 
62  // If this function has external linkage or has its address taken, anything
63  // could call it.
64  if (!F->hasLocalLinkage() || F->hasAddressTaken())
65  ExternalCallingNode->addCalledFunction(nullptr, Node);
66 
67  // If this function is not defined in this translation unit, it could call
68  // anything.
69  if (F->isDeclaration() && !F->isIntrinsic())
70  Node->addCalledFunction(nullptr, CallsExternalNode.get());
71 
72  // Look for calls by this function.
73  for (BasicBlock &BB : *F)
74  for (Instruction &I : BB) {
75  if (auto *Call = dyn_cast<CallBase>(&I)) {
76  const Function *Callee = Call->getCalledFunction();
77  if (!Callee || !Intrinsic::isLeaf(Callee->getIntrinsicID()))
78  // Indirect calls of intrinsics are not allowed so no need to check.
79  // We can be more precise here by using TargetArg returned by
80  // Intrinsic::isLeaf.
81  Node->addCalledFunction(Call, CallsExternalNode.get());
82  else if (!Callee->isIntrinsic())
83  Node->addCalledFunction(Call, getOrInsertFunction(Callee));
84  }
85  }
86 }
87 
88 void CallGraph::print(raw_ostream &OS) const {
89  // Print in a deterministic order by sorting CallGraphNodes by name. We do
90  // this here to avoid slowing down the non-printing fast path.
91 
93  Nodes.reserve(FunctionMap.size());
94 
95  for (const auto &I : *this)
96  Nodes.push_back(I.second.get());
97 
98  llvm::sort(Nodes, [](CallGraphNode *LHS, CallGraphNode *RHS) {
99  if (Function *LF = LHS->getFunction())
100  if (Function *RF = RHS->getFunction())
101  return LF->getName() < RF->getName();
102 
103  return RHS->getFunction() != nullptr;
104  });
105 
106  for (CallGraphNode *CN : Nodes)
107  CN->print(OS);
108 }
109 
110 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
112 #endif
113 
114 // removeFunctionFromModule - Unlink the function from this module, returning
115 // it. Because this removes the function from the module, the call graph node
116 // is destroyed. This is only valid if the function does not call any other
117 // functions (ie, there are no edges in it's CGN). The easiest way to do this
118 // is to dropAllReferences before calling this.
119 //
121  assert(CGN->empty() && "Cannot remove function from call "
122  "graph if it references other functions!");
123  Function *F = CGN->getFunction(); // Get the function for the call graph node
124  FunctionMap.erase(F); // Remove the call graph node from the map
125 
126  M.getFunctionList().remove(F);
127  return F;
128 }
129 
130 /// spliceFunction - Replace the function represented by this node by another.
131 /// This does not rescan the body of the function, so it is suitable when
132 /// splicing the body of the old function to the new while also updating all
133 /// callers from old to new.
134 void CallGraph::spliceFunction(const Function *From, const Function *To) {
135  assert(FunctionMap.count(From) && "No CallGraphNode for function!");
136  assert(!FunctionMap.count(To) &&
137  "Pointing CallGraphNode at a function that already exists");
138  FunctionMapTy::iterator I = FunctionMap.find(From);
139  I->second->F = const_cast<Function*>(To);
140  FunctionMap[To] = std::move(I->second);
141  FunctionMap.erase(I);
142 }
143 
144 // getOrInsertFunction - This method is identical to calling operator[], but
145 // it will insert a new CallGraphNode for the specified function if one does
146 // not already exist.
148  auto &CGN = FunctionMap[F];
149  if (CGN)
150  return CGN.get();
151 
152  assert((!F || F->getParent() == &M) && "Function not in current module!");
153  CGN = std::make_unique<CallGraphNode>(const_cast<Function *>(F));
154  return CGN.get();
155 }
156 
157 //===----------------------------------------------------------------------===//
158 // Implementations of the CallGraphNode class methods.
159 //
160 
162  if (Function *F = getFunction())
163  OS << "Call graph node for function: '" << F->getName() << "'";
164  else
165  OS << "Call graph node <<null function>>";
166 
167  OS << "<<" << this << ">> #uses=" << getNumReferences() << '\n';
168 
169  for (const auto &I : *this) {
170  OS << " CS<" << I.first << "> calls ";
171  if (Function *FI = I.second->getFunction())
172  OS << "function '" << FI->getName() <<"'\n";
173  else
174  OS << "external node\n";
175  }
176  OS << '\n';
177 }
178 
179 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
181 #endif
182 
183 /// removeCallEdgeFor - This method removes the edge in the node for the
184 /// specified call site. Note that this method takes linear time, so it
185 /// should be used sparingly.
187  for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) {
188  assert(I != CalledFunctions.end() && "Cannot find callsite to remove!");
189  if (I->first == &Call) {
190  I->second->DropRef();
191  *I = CalledFunctions.back();
192  CalledFunctions.pop_back();
193  return;
194  }
195  }
196 }
197 
198 // removeAnyCallEdgeTo - This method removes any call edges from this node to
199 // the specified callee function. This takes more time to execute than
200 // removeCallEdgeTo, so it should not be used unless necessary.
202  for (unsigned i = 0, e = CalledFunctions.size(); i != e; ++i)
203  if (CalledFunctions[i].second == Callee) {
204  Callee->DropRef();
205  CalledFunctions[i] = CalledFunctions.back();
206  CalledFunctions.pop_back();
207  --i; --e;
208  }
209 }
210 
211 /// removeOneAbstractEdgeTo - Remove one edge associated with a null callsite
212 /// from this node to the specified callee function.
214  for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) {
215  assert(I != CalledFunctions.end() && "Cannot find callee to remove!");
216  CallRecord &CR = *I;
217  if (CR.second == Callee && CR.first == nullptr) {
218  Callee->DropRef();
219  *I = CalledFunctions.back();
220  CalledFunctions.pop_back();
221  return;
222  }
223  }
224 }
225 
226 /// replaceCallEdge - This method replaces the edge in the node for the
227 /// specified call site with a new one. Note that this method takes linear
228 /// time, so it should be used sparingly.
230  CallGraphNode *NewNode) {
231  for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) {
232  assert(I != CalledFunctions.end() && "Cannot find callsite to remove!");
233  if (I->first == &Call) {
234  I->second->DropRef();
235  I->first = &NewCall;
236  I->second = NewNode;
237  NewNode->AddRef();
238  return;
239  }
240  }
241 }
242 
243 // Provide an explicit template instantiation for the static ID.
244 AnalysisKey CallGraphAnalysis::Key;
245 
247  ModuleAnalysisManager &AM) {
248  AM.getResult<CallGraphAnalysis>(M).print(OS);
249  return PreservedAnalyses::all();
250 }
251 
252 //===----------------------------------------------------------------------===//
253 // Out-of-line definitions of CallGraphAnalysis class members.
254 //
255 
256 //===----------------------------------------------------------------------===//
257 // Implementations of the CallGraphWrapperPass class methods.
258 //
259 
262 }
263 
265 
267  AU.setPreservesAll();
268 }
269 
271  // All the real work is done in the constructor for the CallGraph.
272  G.reset(new CallGraph(M));
273  return false;
274 }
275 
276 INITIALIZE_PASS(CallGraphWrapperPass, "basiccg", "CallGraph Construction",
277  false, true)
278 
279 char CallGraphWrapperPass::ID = 0;
280 
281 void CallGraphWrapperPass::releaseMemory() { G.reset(); }
282 
284  if (!G) {
285  OS << "No call graph has been built!\n";
286  return;
287  }
288 
289  // Just delegate.
290  G->print(OS);
291 }
292 
293 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
295 void CallGraphWrapperPass::dump() const { print(dbgs(), nullptr); }
296 #endif
297 
298 namespace {
299 
300 struct CallGraphPrinterLegacyPass : public ModulePass {
301  static char ID; // Pass ID, replacement for typeid
302 
303  CallGraphPrinterLegacyPass() : ModulePass(ID) {
305  }
306 
307  void getAnalysisUsage(AnalysisUsage &AU) const override {
308  AU.setPreservesAll();
310  }
311 
312  bool runOnModule(Module &M) override {
313  getAnalysis<CallGraphWrapperPass>().print(errs(), &M);
314  return false;
315  }
316 };
317 
318 } // end anonymous namespace
319 
321 
322 INITIALIZE_PASS_BEGIN(CallGraphPrinterLegacyPass, "print-callgraph",
323  "Print a call graph", true, true)
325 INITIALIZE_PASS_END(CallGraphPrinterLegacyPass, "print-callgraph",
326  "Print a call graph", true, true)
bool isIntrinsic() const
isIntrinsic - Returns true if the function&#39;s name starts with "llvm.".
Definition: Function.h:198
raw_ostream & errs()
This returns a reference to a raw_ostream for standard error.
bool hasLocalLinkage() const
Definition: GlobalValue.h:445
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:776
This class represents lattice values for constants.
Definition: AllocatorList.h:23
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds...
Definition: Compiler.h:484
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:65
unsigned second
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1100
F(f)
bool runOnModule(Module &M) override
runOnModule - Virtual method overriden by subclasses to process the module being operated on...
Definition: CallGraph.cpp:270
void reserve(size_type N)
Definition: SmallVector.h:369
A node in the call graph for a module.
Definition: CallGraph.h:164
void removeOneAbstractEdgeTo(CallGraphNode *Callee)
Removes one edge associated with a null callsite from this node to the specified callee function...
Definition: CallGraph.cpp:213
print callgraph
Definition: CallGraph.cpp:325
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
Definition: BitVector.h:937
void print(raw_ostream &OS) const
Definition: CallGraph.cpp:161
ModulePass(char &pid)
Definition: Pass.h:226
Function * removeFunctionFromModule(CallGraphNode *CGN)
Unlink the function from this module, returning it.
Definition: CallGraph.cpp:120
void dump() const
Print out this call graph node.
Definition: CallGraph.cpp:180
This file provides interfaces used to build and manipulate a call graph, which is a very useful tool ...
static Function * getFunction(Constant *C)
Definition: Evaluator.cpp:258
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
void initializeCallGraphPrinterLegacyPassPass(PassRegistry &)
void removeAnyCallEdgeTo(CallGraphNode *Callee)
Removes all call edges from this node to the specified callee function.
Definition: CallGraph.cpp:201
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
The ModulePass which wraps up a CallGraph and the logic to build it.
Definition: CallGraph.h:324
bool isLeaf(ID id)
Returns true if the intrinsic is a leaf, i.e.
Definition: Function.cpp:1076
const FunctionListType & getFunctionList() const
Get the Module&#39;s list of functions (constant).
Definition: Module.h:533
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
void initializeCallGraphWrapperPassPass(PassRegistry &)
Represent the analysis usage information of a pass.
void removeCallEdgeFor(CallBase &Call)
Removes the edge in the node for the specified call site.
Definition: CallGraph.cpp:186
CallGraph(Module &M)
Definition: CallGraph.cpp:30
constexpr double e
Definition: MathExtras.h:57
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:159
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:33
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1095
Function * getFunction() const
Returns the function that this call graph node represents.
Definition: CallGraph.h:187
BlockVerifier::State From
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
Module.h This file contains the declarations for the Module class.
bool empty() const
Definition: CallGraph.h:193
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
Definition: CallGraph.cpp:246
Intrinsic::ID getIntrinsicID() const LLVM_READONLY
getIntrinsicID - This method returns the ID number of the specified function, or Intrinsic::not_intri...
Definition: Function.h:193
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
amdgpu Simplify well known AMD library false FunctionCallee Callee
INITIALIZE_PASS_BEGIN(CallGraphPrinterLegacyPass, "print-callgraph", "Print a call graph", true, true) INITIALIZE_PASS_END(CallGraphPrinterLegacyPass
void setPreservesAll()
Set by analyses that do not transform their input at all.
An analysis pass to compute the CallGraph for a Module.
Definition: CallGraph.h:292
pointer remove(iterator &IT)
Definition: ilist.h:249
The basic data container for the call graph of a Module of IR.
Definition: CallGraph.h:73
print Print a call true
Definition: CallGraph.cpp:325
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:229
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:214
std::pair< WeakTrackingVH, CallGraphNode * > CallRecord
A pair of the calling instruction (a call or invoke) and the call graph node being called...
Definition: CallGraph.h:168
#define I(x, y, z)
Definition: MD5.cpp:58
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
Definition: Pass.h:224
AnalysisUsage & addRequiredTransitive()
bool isDeclaration() const
Return true if the primary definition of this global value is outside of the current translation unit...
Definition: Globals.cpp:231
bool hasAddressTaken(const User **=nullptr) const
hasAddressTaken - returns true if there are any uses of this function other than direct calls or invo...
Definition: Function.cpp:1420
print Print a call graph
Definition: CallGraph.cpp:325
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:575
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:147
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
A container for analyses that lazily runs them and caches their results.
void dump() const
Definition: CallGraph.cpp:111
This header defines various interfaces for pass management in LLVM.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: CallGraph.cpp:266
void print(raw_ostream &o, const Module *) const override
print - Print out the internal state of the pass.
Definition: CallGraph.cpp:283
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:70
void print(raw_ostream &OS) const
Definition: CallGraph.cpp:88
void addCalledFunction(CallBase *Call, CallGraphNode *M)
Adds a function to the list of functions called by this one.
Definition: CallGraph.h:232