blob: a826177d6bdeb3d5cf38a1bf52b39a1320f01c82 [file] [log] [blame]
Dan Gohmanf17a25c2007-07-18 16:29:46 +00001//===- CallGraph.cpp - Build a Module's call graph ------------------------===//
2//
3// The LLVM Compiler Infrastructure
4//
Chris Lattner081ce942007-12-29 20:36:04 +00005// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
Dan Gohmanf17a25c2007-07-18 16:29:46 +00007//
8//===----------------------------------------------------------------------===//
9//
10// This file implements the CallGraph class and provides the BasicCallGraph
11// default implementation.
12//
13//===----------------------------------------------------------------------===//
14
15#include "llvm/Analysis/CallGraph.h"
16#include "llvm/Module.h"
17#include "llvm/Instructions.h"
Dale Johannesenb618d082009-03-19 18:03:56 +000018#include "llvm/IntrinsicInst.h"
Dan Gohmanf17a25c2007-07-18 16:29:46 +000019#include "llvm/Support/CallSite.h"
David Greene6e554392009-12-23 20:03:58 +000020#include "llvm/Support/Debug.h"
Chris Lattner397f4562009-08-23 06:03:38 +000021#include "llvm/Support/raw_ostream.h"
Dan Gohmanf17a25c2007-07-18 16:29:46 +000022using namespace llvm;
23
Dan Gohmanf17a25c2007-07-18 16:29:46 +000024namespace {
25
26//===----------------------------------------------------------------------===//
27// BasicCallGraph class definition
28//
Nick Lewycky492d06e2009-10-25 06:33:48 +000029class BasicCallGraph : public CallGraph, public ModulePass {
Dan Gohmanf17a25c2007-07-18 16:29:46 +000030 // Root is root of the call graph, or the external node if a 'main' function
31 // couldn't be found.
32 //
33 CallGraphNode *Root;
34
35 // ExternalCallingNode - This node has edges to all external functions and
36 // those internal functions that have their address taken.
37 CallGraphNode *ExternalCallingNode;
38
39 // CallsExternalNode - This node has edges to it from all functions making
40 // indirect calls or calling an external function.
41 CallGraphNode *CallsExternalNode;
42
43public:
44 static char ID; // Class identification, replacement for typeinfo
Dan Gohman26f8c272008-09-04 17:05:41 +000045 BasicCallGraph() : ModulePass(&ID), Root(0),
Dan Gohmanf17a25c2007-07-18 16:29:46 +000046 ExternalCallingNode(0), CallsExternalNode(0) {}
47
48 // runOnModule - Compute the call graph for the specified module.
49 virtual bool runOnModule(Module &M) {
50 CallGraph::initialize(M);
51
52 ExternalCallingNode = getOrInsertFunction(0);
53 CallsExternalNode = new CallGraphNode(0);
54 Root = 0;
55
Chris Lattnerfd707922009-08-31 03:15:49 +000056 // Add every function to the call graph.
Dan Gohmanf17a25c2007-07-18 16:29:46 +000057 for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
58 addToCallGraph(I);
59
60 // If we didn't find a main function, use the external call graph node
61 if (Root == 0) Root = ExternalCallingNode;
62
63 return false;
64 }
65
66 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
67 AU.setPreservesAll();
68 }
69
Chris Lattner397f4562009-08-23 06:03:38 +000070 virtual void print(raw_ostream &OS, const Module *) const {
71 OS << "CallGraph Root is: ";
Dan Gohmanf17a25c2007-07-18 16:29:46 +000072 if (Function *F = getRoot()->getFunction())
Chris Lattner397f4562009-08-23 06:03:38 +000073 OS << F->getName() << "\n";
74 else {
75 OS << "<<null function: 0x" << getRoot() << ">>\n";
76 }
Dan Gohmanf17a25c2007-07-18 16:29:46 +000077
Chris Lattner397f4562009-08-23 06:03:38 +000078 CallGraph::print(OS, 0);
Dan Gohmanf17a25c2007-07-18 16:29:46 +000079 }
80
81 virtual void releaseMemory() {
82 destroy();
83 }
84
Dan Gohmanf17a25c2007-07-18 16:29:46 +000085 CallGraphNode* getExternalCallingNode() const { return ExternalCallingNode; }
86 CallGraphNode* getCallsExternalNode() const { return CallsExternalNode; }
87
88 // getRoot - Return the root of the call graph, which is either main, or if
89 // main cannot be found, the external node.
90 //
91 CallGraphNode *getRoot() { return Root; }
92 const CallGraphNode *getRoot() const { return Root; }
93
94private:
95 //===---------------------------------------------------------------------
96 // Implementation of CallGraph construction
97 //
98
99 // addToCallGraph - Add a function to the call graph, and link the node to all
100 // of the functions that it calls.
101 //
102 void addToCallGraph(Function *F) {
103 CallGraphNode *Node = getOrInsertFunction(F);
104
105 // If this function has external linkage, anything could call it.
Rafael Espindolaa168fc92009-01-15 20:18:42 +0000106 if (!F->hasLocalLinkage()) {
Dan Gohmanf17a25c2007-07-18 16:29:46 +0000107 ExternalCallingNode->addCalledFunction(CallSite(), Node);
108
109 // Found the entry point?
110 if (F->getName() == "main") {
111 if (Root) // Found multiple external mains? Don't pick one.
112 Root = ExternalCallingNode;
113 else
114 Root = Node; // Found a main, keep track of it!
115 }
116 }
117
Duncan Sands3ebfa912008-09-09 19:56:34 +0000118 // Loop over all of the users of the function, looking for non-call uses.
119 for (Value::use_iterator I = F->use_begin(), E = F->use_end(); I != E; ++I)
Gabor Greif6be9a1b2009-01-22 21:35:57 +0000120 if ((!isa<CallInst>(I) && !isa<InvokeInst>(I))
121 || !CallSite(cast<Instruction>(I)).isCallee(I)) {
Duncan Sands3ebfa912008-09-09 19:56:34 +0000122 // Not a call, or being used as a parameter rather than as the callee.
123 ExternalCallingNode->addCalledFunction(CallSite(), Node);
124 break;
125 }
126
Dan Gohmanf17a25c2007-07-18 16:29:46 +0000127 // If this function is not defined in this translation unit, it could call
128 // anything.
Duncan Sands79d28872007-12-03 20:06:50 +0000129 if (F->isDeclaration() && !F->isIntrinsic())
Dan Gohmanf17a25c2007-07-18 16:29:46 +0000130 Node->addCalledFunction(CallSite(), CallsExternalNode);
131
Duncan Sands8f7eaea2008-09-09 12:40:47 +0000132 // Look for calls by this function.
Dan Gohmanf17a25c2007-07-18 16:29:46 +0000133 for (Function::iterator BB = F->begin(), BBE = F->end(); BB != BBE; ++BB)
134 for (BasicBlock::iterator II = BB->begin(), IE = BB->end();
135 II != IE; ++II) {
Duncan Sands8f7eaea2008-09-09 12:40:47 +0000136 CallSite CS = CallSite::get(II);
Dale Johannesenb618d082009-03-19 18:03:56 +0000137 if (CS.getInstruction() && !isa<DbgInfoIntrinsic>(II)) {
Duncan Sands8f7eaea2008-09-09 12:40:47 +0000138 const Function *Callee = CS.getCalledFunction();
139 if (Callee)
140 Node->addCalledFunction(CS, getOrInsertFunction(Callee));
141 else
142 Node->addCalledFunction(CS, CallsExternalNode);
143 }
Dan Gohmanf17a25c2007-07-18 16:29:46 +0000144 }
145 }
146
147 //
148 // destroy - Release memory for the call graph
149 virtual void destroy() {
150 /// CallsExternalNode is not in the function map, delete it explicitly.
151 delete CallsExternalNode;
152 CallsExternalNode = 0;
153 CallGraph::destroy();
154 }
155};
156
Dan Gohmanf17a25c2007-07-18 16:29:46 +0000157} //End anonymous namespace
158
Dan Gohman089efff2008-05-13 00:00:25 +0000159static RegisterAnalysisGroup<CallGraph> X("Call Graph");
160static RegisterPass<BasicCallGraph>
161Y("basiccg", "Basic CallGraph Construction", false, true);
162static RegisterAnalysisGroup<CallGraph, true> Z(Y);
163
Dan Gohmanf17a25c2007-07-18 16:29:46 +0000164char CallGraph::ID = 0;
165char BasicCallGraph::ID = 0;
166
167void CallGraph::initialize(Module &M) {
168 Mod = &M;
169}
170
171void CallGraph::destroy() {
Chris Lattnerfd707922009-08-31 03:15:49 +0000172 if (FunctionMap.empty()) return;
173
174 for (FunctionMapTy::iterator I = FunctionMap.begin(), E = FunctionMap.end();
175 I != E; ++I)
176 delete I->second;
177 FunctionMap.clear();
Dan Gohmanf17a25c2007-07-18 16:29:46 +0000178}
179
Chris Lattner397f4562009-08-23 06:03:38 +0000180void CallGraph::print(raw_ostream &OS, Module*) const {
Dan Gohmanf17a25c2007-07-18 16:29:46 +0000181 for (CallGraph::const_iterator I = begin(), E = end(); I != E; ++I)
182 I->second->print(OS);
183}
Chris Lattnerba263e52009-08-30 22:24:32 +0000184void CallGraph::dump() const {
David Greene6e554392009-12-23 20:03:58 +0000185 print(dbgs(), 0);
Chris Lattnerba263e52009-08-30 22:24:32 +0000186}
Dan Gohmanf17a25c2007-07-18 16:29:46 +0000187
Dan Gohmanf17a25c2007-07-18 16:29:46 +0000188//===----------------------------------------------------------------------===//
189// Implementations of public modification methods
190//
191
192// removeFunctionFromModule - Unlink the function from this module, returning
193// it. Because this removes the function from the module, the call graph node
194// is destroyed. This is only valid if the function does not call any other
195// functions (ie, there are no edges in it's CGN). The easiest way to do this
196// is to dropAllReferences before calling this.
197//
198Function *CallGraph::removeFunctionFromModule(CallGraphNode *CGN) {
Chris Lattner7d7776f2009-08-31 02:24:20 +0000199 assert(CGN->empty() && "Cannot remove function from call "
Dan Gohmanf17a25c2007-07-18 16:29:46 +0000200 "graph if it references other functions!");
201 Function *F = CGN->getFunction(); // Get the function for the call graph node
202 delete CGN; // Delete the call graph node for this func
203 FunctionMap.erase(F); // Remove the call graph node from the map
204
205 Mod->getFunctionList().remove(F);
206 return F;
207}
208
Dan Gohmanf17a25c2007-07-18 16:29:46 +0000209// getOrInsertFunction - This method is identical to calling operator[], but
210// it will insert a new CallGraphNode for the specified function if one does
211// not already exist.
212CallGraphNode *CallGraph::getOrInsertFunction(const Function *F) {
213 CallGraphNode *&CGN = FunctionMap[F];
214 if (CGN) return CGN;
215
216 assert((!F || F->getParent() == Mod) && "Function not in current module!");
217 return CGN = new CallGraphNode(const_cast<Function*>(F));
218}
219
Chris Lattner397f4562009-08-23 06:03:38 +0000220void CallGraphNode::print(raw_ostream &OS) const {
Dan Gohmanf17a25c2007-07-18 16:29:46 +0000221 if (Function *F = getFunction())
Chris Lattnerfd707922009-08-31 03:15:49 +0000222 OS << "Call graph node for function: '" << F->getName() << "'";
Dan Gohmanf17a25c2007-07-18 16:29:46 +0000223 else
Chris Lattnerfd707922009-08-31 03:15:49 +0000224 OS << "Call graph node <<null function>>";
225
226 OS << "<<0x" << this << ">> #uses=" << getNumReferences() << '\n';
Dan Gohmanf17a25c2007-07-18 16:29:46 +0000227
Duncan Sandsafeb3e82008-09-08 16:04:03 +0000228 for (const_iterator I = begin(), E = end(); I != E; ++I)
Gabor Greifbd78fa82009-01-14 17:09:04 +0000229 if (Function *FI = I->second->getFunction())
Chris Lattner397f4562009-08-23 06:03:38 +0000230 OS << " Calls function '" << FI->getName() <<"'\n";
Duncan Sandsafeb3e82008-09-08 16:04:03 +0000231 else
232 OS << " Calls external node\n";
Dan Gohmanf17a25c2007-07-18 16:29:46 +0000233 OS << "\n";
234}
235
David Greene6e554392009-12-23 20:03:58 +0000236void CallGraphNode::dump() const { print(dbgs()); }
Dan Gohmanf17a25c2007-07-18 16:29:46 +0000237
Chris Lattner9125c402008-04-13 19:41:25 +0000238/// removeCallEdgeFor - This method removes the edge in the node for the
239/// specified call site. Note that this method takes linear time, so it
240/// should be used sparingly.
241void CallGraphNode::removeCallEdgeFor(CallSite CS) {
Chris Lattner298ea102009-08-31 07:23:46 +0000242 for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) {
243 assert(I != CalledFunctions.end() && "Cannot find callsite to remove!");
Chris Lattnera59b5de2009-09-01 06:31:31 +0000244 if (I->first == CS.getInstruction()) {
Chris Lattner298ea102009-08-31 07:23:46 +0000245 I->second->DropRef();
246 *I = CalledFunctions.back();
247 CalledFunctions.pop_back();
248 return;
249 }
Chris Lattner9125c402008-04-13 19:41:25 +0000250 }
251}
252
253
Dan Gohmanf17a25c2007-07-18 16:29:46 +0000254// removeAnyCallEdgeTo - This method removes any call edges from this node to
255// the specified callee function. This takes more time to execute than
256// removeCallEdgeTo, so it should not be used unless necessary.
257void CallGraphNode::removeAnyCallEdgeTo(CallGraphNode *Callee) {
258 for (unsigned i = 0, e = CalledFunctions.size(); i != e; ++i)
259 if (CalledFunctions[i].second == Callee) {
Chris Lattnerfd707922009-08-31 03:15:49 +0000260 Callee->DropRef();
Dan Gohmanf17a25c2007-07-18 16:29:46 +0000261 CalledFunctions[i] = CalledFunctions.back();
262 CalledFunctions.pop_back();
263 --i; --e;
264 }
265}
266
Duncan Sands349bf2e2008-10-03 07:36:09 +0000267/// removeOneAbstractEdgeTo - Remove one edge associated with a null callsite
268/// from this node to the specified callee function.
269void CallGraphNode::removeOneAbstractEdgeTo(CallGraphNode *Callee) {
Gabor Greifa3ef1552009-01-17 19:46:01 +0000270 for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) {
271 assert(I != CalledFunctions.end() && "Cannot find callee to remove!");
272 CallRecord &CR = *I;
Chris Lattnera59b5de2009-09-01 06:31:31 +0000273 if (CR.second == Callee && CR.first == 0) {
Chris Lattnerfd707922009-08-31 03:15:49 +0000274 Callee->DropRef();
275 *I = CalledFunctions.back();
276 CalledFunctions.pop_back();
Duncan Sands349bf2e2008-10-03 07:36:09 +0000277 return;
278 }
279 }
280}
281
Chris Lattner69177fb2009-09-15 05:40:35 +0000282/// replaceCallEdge - This method replaces the edge in the node for the
283/// specified call site with a new one. Note that this method takes linear
284/// time, so it should be used sparingly.
285void CallGraphNode::replaceCallEdge(CallSite CS,
286 CallSite NewCS, CallGraphNode *NewNode){
287 for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) {
288 assert(I != CalledFunctions.end() && "Cannot find callsite to remove!");
289 if (I->first == CS.getInstruction()) {
290 I->second->DropRef();
291 I->first = NewCS.getInstruction();
292 I->second = NewNode;
293 NewNode->AddRef();
294 return;
295 }
296 }
297}
298
Dan Gohmanf17a25c2007-07-18 16:29:46 +0000299// Enuse that users of CallGraph.h also link with this file
300DEFINING_FILE_FOR(CallGraph)