blob: 7d5d2d2e4496994251fb5260631af876bf01e9e9 [file] [log] [blame]
Chris Lattnerd852cc32002-03-06 18:00:49 +00001//===- CallGraph.cpp - Build a Module's call graph ------------------------===//
Misha Brukman01808ca2005-04-21 21:13:18 +00002//
John Criswell482202a2003-10-20 19:43:21 +00003// The LLVM Compiler Infrastructure
4//
Chris Lattnerf3ebc3f2007-12-29 20:36:04 +00005// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
Misha Brukman01808ca2005-04-21 21:13:18 +00007//
John Criswell482202a2003-10-20 19:43:21 +00008//===----------------------------------------------------------------------===//
Chris Lattnerbbf3ae82001-09-28 00:08:15 +00009
10#include "llvm/Analysis/CallGraph.h"
Eugene Zelenko48666a62017-07-24 23:16:33 +000011#include "llvm/ADT/STLExtras.h"
12#include "llvm/ADT/SmallVector.h"
Nico Weber432a3882018-04-30 14:59:11 +000013#include "llvm/Config/llvm-config.h"
Chandler Carruth219b89b2014-03-04 11:01:28 +000014#include "llvm/IR/CallSite.h"
Chandler Carruth9fb823b2013-01-02 11:36:10 +000015#include "llvm/IR/Module.h"
Eugene Zelenko48666a62017-07-24 23:16:33 +000016#include "llvm/IR/Function.h"
17#include "llvm/IR/Intrinsics.h"
18#include "llvm/IR/PassManager.h"
19#include "llvm/Pass.h"
20#include "llvm/Support/Compiler.h"
David Greeneba44b3e2009-12-23 20:03:58 +000021#include "llvm/Support/Debug.h"
Chris Lattner13626022009-08-23 06:03:38 +000022#include "llvm/Support/raw_ostream.h"
Eugene Zelenko48666a62017-07-24 23:16:33 +000023#include <algorithm>
24#include <cassert>
25
Chris Lattner8b6db182004-04-12 05:36:32 +000026using namespace llvm;
Brian Gaeke960707c2003-11-11 22:41:34 +000027
Chandler Carruth6378cf52013-11-26 04:19:30 +000028//===----------------------------------------------------------------------===//
29// Implementations of the CallGraph class methods.
30//
31
32CallGraph::CallGraph(Module &M)
Peter Collingbournef3e9f122017-05-11 23:59:05 +000033 : M(M), ExternalCallingNode(getOrInsertFunction(nullptr)),
David Blaikiea5d7de92015-08-05 20:55:50 +000034 CallsExternalNode(llvm::make_unique<CallGraphNode>(nullptr)) {
Chandler Carruth6378cf52013-11-26 04:19:30 +000035 // Add every function to the call graph.
Yaron Keren26ceb082015-06-12 05:15:27 +000036 for (Function &F : M)
37 addToCallGraph(&F);
Chandler Carruth6378cf52013-11-26 04:19:30 +000038}
39
Chandler Carruth5efd5302015-08-16 06:35:19 +000040CallGraph::CallGraph(CallGraph &&Arg)
Peter Collingbournef3e9f122017-05-11 23:59:05 +000041 : M(Arg.M), FunctionMap(std::move(Arg.FunctionMap)),
Chandler Carruth5efd5302015-08-16 06:35:19 +000042 ExternalCallingNode(Arg.ExternalCallingNode),
43 CallsExternalNode(std::move(Arg.CallsExternalNode)) {
44 Arg.FunctionMap.clear();
Chandler Carruth5efd5302015-08-16 06:35:19 +000045 Arg.ExternalCallingNode = nullptr;
46}
47
Chandler Carruth6378cf52013-11-26 04:19:30 +000048CallGraph::~CallGraph() {
49 // CallsExternalNode is not in the function map, delete it explicitly.
David Blaikiea5d7de92015-08-05 20:55:50 +000050 if (CallsExternalNode)
51 CallsExternalNode->allReferencesDropped();
Chandler Carruth6378cf52013-11-26 04:19:30 +000052
53// Reset all node's use counts to zero before deleting them to prevent an
54// assertion from firing.
55#ifndef NDEBUG
Yaron Keren26ceb082015-06-12 05:15:27 +000056 for (auto &I : FunctionMap)
57 I.second->allReferencesDropped();
Chandler Carruth6378cf52013-11-26 04:19:30 +000058#endif
Chris Lattnerbbf3ae82001-09-28 00:08:15 +000059}
60
Rafael Espindola6554e5a2013-10-31 03:03:55 +000061void CallGraph::addToCallGraph(Function *F) {
62 CallGraphNode *Node = getOrInsertFunction(F);
63
Peter Collingbournef3e9f122017-05-11 23:59:05 +000064 // If this function has external linkage or has its address taken, anything
65 // could call it.
66 if (!F->hasLocalLinkage() || F->hasAddressTaken())
Rafael Espindola6554e5a2013-10-31 03:03:55 +000067 ExternalCallingNode->addCalledFunction(CallSite(), Node);
68
69 // If this function is not defined in this translation unit, it could call
70 // anything.
71 if (F->isDeclaration() && !F->isIntrinsic())
David Blaikiea5d7de92015-08-05 20:55:50 +000072 Node->addCalledFunction(CallSite(), CallsExternalNode.get());
Rafael Espindola6554e5a2013-10-31 03:03:55 +000073
74 // Look for calls by this function.
Benjamin Krameraa209152016-06-26 17:27:42 +000075 for (BasicBlock &BB : *F)
76 for (Instruction &I : BB) {
77 if (auto CS = CallSite(&I)) {
Rafael Espindola6554e5a2013-10-31 03:03:55 +000078 const Function *Callee = CS.getCalledFunction();
Sanjoy Dasc65d43e2015-06-18 19:28:26 +000079 if (!Callee || !Intrinsic::isLeaf(Callee->getIntrinsicID()))
Rafael Espindola6554e5a2013-10-31 03:03:55 +000080 // Indirect calls of intrinsics are not allowed so no need to check.
Sanjoy Dasc65d43e2015-06-18 19:28:26 +000081 // We can be more precise here by using TargetArg returned by
82 // Intrinsic::isLeaf.
David Blaikiea5d7de92015-08-05 20:55:50 +000083 Node->addCalledFunction(CS, CallsExternalNode.get());
Rafael Espindola6554e5a2013-10-31 03:03:55 +000084 else if (!Callee->isIntrinsic())
85 Node->addCalledFunction(CS, getOrInsertFunction(Callee));
86 }
87 }
88}
89
Chandler Carruth6378cf52013-11-26 04:19:30 +000090void CallGraph::print(raw_ostream &OS) const {
Sanjoy Das18c9dd32015-06-19 23:20:31 +000091 // Print in a deterministic order by sorting CallGraphNodes by name. We do
92 // this here to avoid slowing down the non-printing fast path.
93
94 SmallVector<CallGraphNode *, 16> Nodes;
95 Nodes.reserve(FunctionMap.size());
96
Benjamin Krameraa209152016-06-26 17:27:42 +000097 for (const auto &I : *this)
98 Nodes.push_back(I.second.get());
Sanjoy Das18c9dd32015-06-19 23:20:31 +000099
Mandeep Singh Grang97bcade2018-04-01 01:46:51 +0000100 llvm::sort(Nodes.begin(), Nodes.end(),
101 [](CallGraphNode *LHS, CallGraphNode *RHS) {
Sanjoy Das18c9dd32015-06-19 23:20:31 +0000102 if (Function *LF = LHS->getFunction())
103 if (Function *RF = RHS->getFunction())
104 return LF->getName() < RF->getName();
105
106 return RHS->getFunction() != nullptr;
107 });
108
109 for (CallGraphNode *CN : Nodes)
110 CN->print(OS);
Chris Lattner6b5411022004-08-08 03:27:49 +0000111}
112
Aaron Ballman615eb472017-10-15 14:32:27 +0000113#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
Matthias Braun8c209aa2017-01-28 02:02:38 +0000114LLVM_DUMP_METHOD void CallGraph::dump() const { print(dbgs()); }
115#endif
Chris Lattner03946cd2001-11-26 18:51:25 +0000116
Chris Lattner79b0c7d2002-07-18 04:43:16 +0000117// removeFunctionFromModule - Unlink the function from this module, returning
118// it. Because this removes the function from the module, the call graph node
119// is destroyed. This is only valid if the function does not call any other
120// functions (ie, there are no edges in it's CGN). The easiest way to do this
Chris Lattner03946cd2001-11-26 18:51:25 +0000121// is to dropAllReferences before calling this.
122//
Chris Lattner79b0c7d2002-07-18 04:43:16 +0000123Function *CallGraph::removeFunctionFromModule(CallGraphNode *CGN) {
Chris Lattner4275cf22009-08-31 02:24:20 +0000124 assert(CGN->empty() && "Cannot remove function from call "
Chris Lattner79b0c7d2002-07-18 04:43:16 +0000125 "graph if it references other functions!");
Chris Lattner6f5e18d2003-08-31 20:36:52 +0000126 Function *F = CGN->getFunction(); // Get the function for the call graph node
Chris Lattner6f5e18d2003-08-31 20:36:52 +0000127 FunctionMap.erase(F); // Remove the call graph node from the map
Chris Lattner03946cd2001-11-26 18:51:25 +0000128
Chandler Carruth6378cf52013-11-26 04:19:30 +0000129 M.getFunctionList().remove(F);
Chris Lattner6f5e18d2003-08-31 20:36:52 +0000130 return F;
Chris Lattner03946cd2001-11-26 18:51:25 +0000131}
132
Nick Lewycky0f87ca72011-01-03 03:19:35 +0000133/// spliceFunction - Replace the function represented by this node by another.
134/// This does not rescan the body of the function, so it is suitable when
135/// splicing the body of the old function to the new while also updating all
136/// callers from old to new.
Nick Lewycky0f87ca72011-01-03 03:19:35 +0000137void CallGraph::spliceFunction(const Function *From, const Function *To) {
138 assert(FunctionMap.count(From) && "No CallGraphNode for function!");
139 assert(!FunctionMap.count(To) &&
140 "Pointing CallGraphNode at a function that already exists");
141 FunctionMapTy::iterator I = FunctionMap.find(From);
142 I->second->F = const_cast<Function*>(To);
David Blaikiea5d7de92015-08-05 20:55:50 +0000143 FunctionMap[To] = std::move(I->second);
Nick Lewycky0f87ca72011-01-03 03:19:35 +0000144 FunctionMap.erase(I);
145}
146
Chris Lattner00ca8d22006-01-14 20:03:00 +0000147// getOrInsertFunction - This method is identical to calling operator[], but
148// it will insert a new CallGraphNode for the specified function if one does
149// not already exist.
150CallGraphNode *CallGraph::getOrInsertFunction(const Function *F) {
David Blaikiea5d7de92015-08-05 20:55:50 +0000151 auto &CGN = FunctionMap[F];
Chandler Carruth6378cf52013-11-26 04:19:30 +0000152 if (CGN)
David Blaikiea5d7de92015-08-05 20:55:50 +0000153 return CGN.get();
Chandler Carruth6378cf52013-11-26 04:19:30 +0000154
155 assert((!F || F->getParent() == &M) && "Function not in current module!");
David Blaikiea5d7de92015-08-05 20:55:50 +0000156 CGN = llvm::make_unique<CallGraphNode>(const_cast<Function *>(F));
157 return CGN.get();
Chris Lattner00ca8d22006-01-14 20:03:00 +0000158}
159
Chandler Carruth6378cf52013-11-26 04:19:30 +0000160//===----------------------------------------------------------------------===//
161// Implementations of the CallGraphNode class methods.
162//
163
Chris Lattner13626022009-08-23 06:03:38 +0000164void CallGraphNode::print(raw_ostream &OS) const {
Chris Lattnerbe1987772005-12-22 06:07:52 +0000165 if (Function *F = getFunction())
Chris Lattner081375b2009-08-31 03:15:49 +0000166 OS << "Call graph node for function: '" << F->getName() << "'";
Chris Lattnerbe1987772005-12-22 06:07:52 +0000167 else
Chris Lattner081375b2009-08-31 03:15:49 +0000168 OS << "Call graph node <<null function>>";
169
Chris Lattner8c562542010-04-23 18:23:40 +0000170 OS << "<<" << this << ">> #uses=" << getNumReferences() << '\n';
Chris Lattnerbe1987772005-12-22 06:07:52 +0000171
Benjamin Krameraa209152016-06-26 17:27:42 +0000172 for (const auto &I : *this) {
173 OS << " CS<" << I.first << "> calls ";
174 if (Function *FI = I.second->getFunction())
Chris Lattner8c562542010-04-23 18:23:40 +0000175 OS << "function '" << FI->getName() <<"'\n";
176 else
177 OS << "external node\n";
178 }
179 OS << '\n';
Chris Lattnerbe1987772005-12-22 06:07:52 +0000180}
181
Aaron Ballman615eb472017-10-15 14:32:27 +0000182#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
Matthias Braun8c209aa2017-01-28 02:02:38 +0000183LLVM_DUMP_METHOD void CallGraphNode::dump() const { print(dbgs()); }
184#endif
Chris Lattnerbe1987772005-12-22 06:07:52 +0000185
Chris Lattnercc9709c2008-04-13 19:41:25 +0000186/// removeCallEdgeFor - This method removes the edge in the node for the
187/// specified call site. Note that this method takes linear time, so it
188/// should be used sparingly.
189void CallGraphNode::removeCallEdgeFor(CallSite CS) {
Chris Lattnereedcd842009-08-31 07:23:46 +0000190 for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) {
191 assert(I != CalledFunctions.end() && "Cannot find callsite to remove!");
Chris Lattner063d0652009-09-01 06:31:31 +0000192 if (I->first == CS.getInstruction()) {
Chris Lattnereedcd842009-08-31 07:23:46 +0000193 I->second->DropRef();
194 *I = CalledFunctions.back();
195 CalledFunctions.pop_back();
196 return;
197 }
Chris Lattnercc9709c2008-04-13 19:41:25 +0000198 }
199}
200
Chris Lattner824a2182004-09-18 21:34:34 +0000201// removeAnyCallEdgeTo - This method removes any call edges from this node to
202// the specified callee function. This takes more time to execute than
203// removeCallEdgeTo, so it should not be used unless necessary.
204void CallGraphNode::removeAnyCallEdgeTo(CallGraphNode *Callee) {
Chris Lattnerd6d99df2004-09-19 19:01:06 +0000205 for (unsigned i = 0, e = CalledFunctions.size(); i != e; ++i)
Chris Lattner5de3b8b2006-07-12 18:29:36 +0000206 if (CalledFunctions[i].second == Callee) {
Chris Lattner081375b2009-08-31 03:15:49 +0000207 Callee->DropRef();
Chris Lattnerd6d99df2004-09-19 19:01:06 +0000208 CalledFunctions[i] = CalledFunctions.back();
209 CalledFunctions.pop_back();
210 --i; --e;
Chris Lattner824a2182004-09-18 21:34:34 +0000211 }
212}
Reid Spencerbe535662006-06-07 22:00:26 +0000213
Duncan Sands3a813a52008-10-03 07:36:09 +0000214/// removeOneAbstractEdgeTo - Remove one edge associated with a null callsite
215/// from this node to the specified callee function.
216void CallGraphNode::removeOneAbstractEdgeTo(CallGraphNode *Callee) {
Gabor Greif20b722f2009-01-17 19:46:01 +0000217 for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) {
218 assert(I != CalledFunctions.end() && "Cannot find callee to remove!");
219 CallRecord &CR = *I;
Craig Topper353eda42014-04-24 06:44:33 +0000220 if (CR.second == Callee && CR.first == nullptr) {
Chris Lattner081375b2009-08-31 03:15:49 +0000221 Callee->DropRef();
222 *I = CalledFunctions.back();
223 CalledFunctions.pop_back();
Duncan Sands3a813a52008-10-03 07:36:09 +0000224 return;
225 }
226 }
227}
228
Chris Lattnere0987212009-09-15 05:40:35 +0000229/// replaceCallEdge - This method replaces the edge in the node for the
230/// specified call site with a new one. Note that this method takes linear
231/// time, so it should be used sparingly.
232void CallGraphNode::replaceCallEdge(CallSite CS,
233 CallSite NewCS, CallGraphNode *NewNode){
234 for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) {
235 assert(I != CalledFunctions.end() && "Cannot find callsite to remove!");
236 if (I->first == CS.getInstruction()) {
237 I->second->DropRef();
238 I->first = NewCS.getInstruction();
239 I->second = NewNode;
240 NewNode->AddRef();
241 return;
242 }
243 }
244}
245
Chandler Carruthcf3f4f22016-03-10 14:33:10 +0000246// Provide an explicit template instantiation for the static ID.
Chandler Carruthdab4eae2016-11-23 17:53:26 +0000247AnalysisKey CallGraphAnalysis::Key;
Chandler Carruthcf3f4f22016-03-10 14:33:10 +0000248
Chandler Carruth4c660f72016-03-10 11:24:11 +0000249PreservedAnalyses CallGraphPrinterPass::run(Module &M,
Sean Silvafd03ac62016-08-09 00:28:38 +0000250 ModuleAnalysisManager &AM) {
Chandler Carruthb47f8012016-03-11 11:05:24 +0000251 AM.getResult<CallGraphAnalysis>(M).print(OS);
Chandler Carruth4c660f72016-03-10 11:24:11 +0000252 return PreservedAnalyses::all();
253}
254
Chandler Carruth6378cf52013-11-26 04:19:30 +0000255//===----------------------------------------------------------------------===//
Chandler Carruth5efd5302015-08-16 06:35:19 +0000256// Out-of-line definitions of CallGraphAnalysis class members.
257//
258
Chandler Carruth5efd5302015-08-16 06:35:19 +0000259//===----------------------------------------------------------------------===//
Chandler Carruth6378cf52013-11-26 04:19:30 +0000260// Implementations of the CallGraphWrapperPass class methods.
261//
262
263CallGraphWrapperPass::CallGraphWrapperPass() : ModulePass(ID) {
264 initializeCallGraphWrapperPassPass(*PassRegistry::getPassRegistry());
265}
266
Eugene Zelenko48666a62017-07-24 23:16:33 +0000267CallGraphWrapperPass::~CallGraphWrapperPass() = default;
Chandler Carruth6378cf52013-11-26 04:19:30 +0000268
269void CallGraphWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
270 AU.setPreservesAll();
271}
272
273bool CallGraphWrapperPass::runOnModule(Module &M) {
274 // All the real work is done in the constructor for the CallGraph.
275 G.reset(new CallGraph(M));
276 return false;
277}
278
279INITIALIZE_PASS(CallGraphWrapperPass, "basiccg", "CallGraph Construction",
280 false, true)
281
282char CallGraphWrapperPass::ID = 0;
283
David Blaikieb61064e2014-07-19 01:05:11 +0000284void CallGraphWrapperPass::releaseMemory() { G.reset(); }
Chandler Carruth6378cf52013-11-26 04:19:30 +0000285
286void CallGraphWrapperPass::print(raw_ostream &OS, const Module *) const {
287 if (!G) {
288 OS << "No call graph has been built!\n";
289 return;
290 }
291
292 // Just delegate.
293 G->print(OS);
294}
295
Aaron Ballman615eb472017-10-15 14:32:27 +0000296#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
Davide Italiano6f93df82015-11-23 02:58:42 +0000297LLVM_DUMP_METHOD
Craig Toppere73658d2014-04-28 04:05:08 +0000298void CallGraphWrapperPass::dump() const { print(dbgs(), nullptr); }
Matthias Braun8c209aa2017-01-28 02:02:38 +0000299#endif
Chandler Carruth1ecd7402016-03-10 11:08:44 +0000300
301namespace {
Eugene Zelenko48666a62017-07-24 23:16:33 +0000302
Chandler Carruth1ecd7402016-03-10 11:08:44 +0000303struct CallGraphPrinterLegacyPass : public ModulePass {
304 static char ID; // Pass ID, replacement for typeid
Eugene Zelenko48666a62017-07-24 23:16:33 +0000305
Chandler Carruth1ecd7402016-03-10 11:08:44 +0000306 CallGraphPrinterLegacyPass() : ModulePass(ID) {
307 initializeCallGraphPrinterLegacyPassPass(*PassRegistry::getPassRegistry());
308 }
309
310 void getAnalysisUsage(AnalysisUsage &AU) const override {
311 AU.setPreservesAll();
312 AU.addRequiredTransitive<CallGraphWrapperPass>();
313 }
Eugene Zelenko48666a62017-07-24 23:16:33 +0000314
Chandler Carruth1ecd7402016-03-10 11:08:44 +0000315 bool runOnModule(Module &M) override {
316 getAnalysis<CallGraphWrapperPass>().print(errs(), &M);
317 return false;
318 }
319};
Eugene Zelenko48666a62017-07-24 23:16:33 +0000320
321} // end anonymous namespace
Chandler Carruth1ecd7402016-03-10 11:08:44 +0000322
323char CallGraphPrinterLegacyPass::ID = 0;
324
325INITIALIZE_PASS_BEGIN(CallGraphPrinterLegacyPass, "print-callgraph",
326 "Print a call graph", true, true)
327INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass)
328INITIALIZE_PASS_END(CallGraphPrinterLegacyPass, "print-callgraph",
329 "Print a call graph", true, true)