1 //===- CallGraph.cpp - Build a Module's call graph ------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements the CallGraph class and provides the BasicCallGraph
11 // default implementation.
13 //===----------------------------------------------------------------------===//
15 #include "llvm/Analysis/CallGraph.h"
16 #include "llvm/Module.h"
17 #include "llvm/Instructions.h"
18 #include "llvm/IntrinsicInst.h"
19 #include "llvm/Support/CallSite.h"
20 #include "llvm/Support/raw_ostream.h"
25 //===----------------------------------------------------------------------===//
26 // BasicCallGraph class definition
28 class BasicCallGraph
: public CallGraph
, public ModulePass
{
29 // Root is root of the call graph, or the external node if a 'main' function
34 // ExternalCallingNode - This node has edges to all external functions and
35 // those internal functions that have their address taken.
36 CallGraphNode
*ExternalCallingNode
;
38 // CallsExternalNode - This node has edges to it from all functions making
39 // indirect calls or calling an external function.
40 CallGraphNode
*CallsExternalNode
;
43 static char ID
; // Class identification, replacement for typeinfo
44 BasicCallGraph() : ModulePass(&ID
), Root(0),
45 ExternalCallingNode(0), CallsExternalNode(0) {}
47 // runOnModule - Compute the call graph for the specified module.
48 virtual bool runOnModule(Module
&M
) {
49 CallGraph::initialize(M
);
51 ExternalCallingNode
= getOrInsertFunction(0);
52 CallsExternalNode
= new CallGraphNode(0);
55 // Add every function to the call graph.
56 for (Module::iterator I
= M
.begin(), E
= M
.end(); I
!= E
; ++I
)
59 // If we didn't find a main function, use the external call graph node
60 if (Root
== 0) Root
= ExternalCallingNode
;
65 virtual void getAnalysisUsage(AnalysisUsage
&AU
) const {
69 virtual void print(raw_ostream
&OS
, const Module
*) const {
70 OS
<< "CallGraph Root is: ";
71 if (Function
*F
= getRoot()->getFunction())
72 OS
<< F
->getName() << "\n";
74 OS
<< "<<null function: 0x" << getRoot() << ">>\n";
77 CallGraph::print(OS
, 0);
80 virtual void releaseMemory() {
84 CallGraphNode
* getExternalCallingNode() const { return ExternalCallingNode
; }
85 CallGraphNode
* getCallsExternalNode() const { return CallsExternalNode
; }
87 // getRoot - Return the root of the call graph, which is either main, or if
88 // main cannot be found, the external node.
90 CallGraphNode
*getRoot() { return Root
; }
91 const CallGraphNode
*getRoot() const { return Root
; }
94 //===---------------------------------------------------------------------
95 // Implementation of CallGraph construction
98 // addToCallGraph - Add a function to the call graph, and link the node to all
99 // of the functions that it calls.
101 void addToCallGraph(Function
*F
) {
102 CallGraphNode
*Node
= getOrInsertFunction(F
);
104 // If this function has external linkage, anything could call it.
105 if (!F
->hasLocalLinkage()) {
106 ExternalCallingNode
->addCalledFunction(CallSite(), Node
);
108 // Found the entry point?
109 if (F
->getName() == "main") {
110 if (Root
) // Found multiple external mains? Don't pick one.
111 Root
= ExternalCallingNode
;
113 Root
= Node
; // Found a main, keep track of it!
117 // Loop over all of the users of the function, looking for non-call uses.
118 for (Value::use_iterator I
= F
->use_begin(), E
= F
->use_end(); I
!= E
; ++I
)
119 if ((!isa
<CallInst
>(I
) && !isa
<InvokeInst
>(I
))
120 || !CallSite(cast
<Instruction
>(I
)).isCallee(I
)) {
121 // Not a call, or being used as a parameter rather than as the callee.
122 ExternalCallingNode
->addCalledFunction(CallSite(), Node
);
126 // If this function is not defined in this translation unit, it could call
128 if (F
->isDeclaration() && !F
->isIntrinsic())
129 Node
->addCalledFunction(CallSite(), CallsExternalNode
);
131 // Look for calls by this function.
132 for (Function::iterator BB
= F
->begin(), BBE
= F
->end(); BB
!= BBE
; ++BB
)
133 for (BasicBlock::iterator II
= BB
->begin(), IE
= BB
->end();
135 CallSite CS
= CallSite::get(II
);
136 if (CS
.getInstruction() && !isa
<DbgInfoIntrinsic
>(II
)) {
137 const Function
*Callee
= CS
.getCalledFunction();
139 Node
->addCalledFunction(CS
, getOrInsertFunction(Callee
));
141 Node
->addCalledFunction(CS
, CallsExternalNode
);
147 // destroy - Release memory for the call graph
148 virtual void destroy() {
149 /// CallsExternalNode is not in the function map, delete it explicitly.
150 delete CallsExternalNode
;
151 CallsExternalNode
= 0;
152 CallGraph::destroy();
156 } //End anonymous namespace
158 static RegisterAnalysisGroup
<CallGraph
> X("Call Graph");
159 static RegisterPass
<BasicCallGraph
>
160 Y("basiccg", "Basic CallGraph Construction", false, true);
161 static RegisterAnalysisGroup
<CallGraph
, true> Z(Y
);
163 char CallGraph::ID
= 0;
164 char BasicCallGraph::ID
= 0;
166 void CallGraph::initialize(Module
&M
) {
170 void CallGraph::destroy() {
171 if (FunctionMap
.empty()) return;
173 for (FunctionMapTy::iterator I
= FunctionMap
.begin(), E
= FunctionMap
.end();
179 void CallGraph::print(raw_ostream
&OS
, Module
*) const {
180 for (CallGraph::const_iterator I
= begin(), E
= end(); I
!= E
; ++I
)
181 I
->second
->print(OS
);
183 void CallGraph::dump() const {
187 //===----------------------------------------------------------------------===//
188 // Implementations of public modification methods
191 // removeFunctionFromModule - Unlink the function from this module, returning
192 // it. Because this removes the function from the module, the call graph node
193 // is destroyed. This is only valid if the function does not call any other
194 // functions (ie, there are no edges in it's CGN). The easiest way to do this
195 // is to dropAllReferences before calling this.
197 Function
*CallGraph::removeFunctionFromModule(CallGraphNode
*CGN
) {
198 assert(CGN
->empty() && "Cannot remove function from call "
199 "graph if it references other functions!");
200 Function
*F
= CGN
->getFunction(); // Get the function for the call graph node
201 delete CGN
; // Delete the call graph node for this func
202 FunctionMap
.erase(F
); // Remove the call graph node from the map
204 Mod
->getFunctionList().remove(F
);
208 // getOrInsertFunction - This method is identical to calling operator[], but
209 // it will insert a new CallGraphNode for the specified function if one does
210 // not already exist.
211 CallGraphNode
*CallGraph::getOrInsertFunction(const Function
*F
) {
212 CallGraphNode
*&CGN
= FunctionMap
[F
];
215 assert((!F
|| F
->getParent() == Mod
) && "Function not in current module!");
216 return CGN
= new CallGraphNode(const_cast<Function
*>(F
));
219 void CallGraphNode::print(raw_ostream
&OS
) const {
220 if (Function
*F
= getFunction())
221 OS
<< "Call graph node for function: '" << F
->getName() << "'";
223 OS
<< "Call graph node <<null function>>";
225 OS
<< "<<0x" << this << ">> #uses=" << getNumReferences() << '\n';
227 for (const_iterator I
= begin(), E
= end(); I
!= E
; ++I
)
228 if (Function
*FI
= I
->second
->getFunction())
229 OS
<< " Calls function '" << FI
->getName() <<"'\n";
231 OS
<< " Calls external node\n";
235 void CallGraphNode::dump() const { print(errs()); }
237 /// removeCallEdgeFor - This method removes the edge in the node for the
238 /// specified call site. Note that this method takes linear time, so it
239 /// should be used sparingly.
240 void CallGraphNode::removeCallEdgeFor(CallSite CS
) {
241 for (CalledFunctionsVector::iterator I
= CalledFunctions
.begin(); ; ++I
) {
242 assert(I
!= CalledFunctions
.end() && "Cannot find callsite to remove!");
243 if (I
->first
== CS
.getInstruction()) {
244 I
->second
->DropRef();
245 *I
= CalledFunctions
.back();
246 CalledFunctions
.pop_back();
253 // removeAnyCallEdgeTo - This method removes any call edges from this node to
254 // the specified callee function. This takes more time to execute than
255 // removeCallEdgeTo, so it should not be used unless necessary.
256 void CallGraphNode::removeAnyCallEdgeTo(CallGraphNode
*Callee
) {
257 for (unsigned i
= 0, e
= CalledFunctions
.size(); i
!= e
; ++i
)
258 if (CalledFunctions
[i
].second
== Callee
) {
260 CalledFunctions
[i
] = CalledFunctions
.back();
261 CalledFunctions
.pop_back();
266 /// removeOneAbstractEdgeTo - Remove one edge associated with a null callsite
267 /// from this node to the specified callee function.
268 void CallGraphNode::removeOneAbstractEdgeTo(CallGraphNode
*Callee
) {
269 for (CalledFunctionsVector::iterator I
= CalledFunctions
.begin(); ; ++I
) {
270 assert(I
!= CalledFunctions
.end() && "Cannot find callee to remove!");
272 if (CR
.second
== Callee
&& CR
.first
== 0) {
274 *I
= CalledFunctions
.back();
275 CalledFunctions
.pop_back();
281 /// replaceCallEdge - This method replaces the edge in the node for the
282 /// specified call site with a new one. Note that this method takes linear
283 /// time, so it should be used sparingly.
284 void CallGraphNode::replaceCallEdge(CallSite CS
,
285 CallSite NewCS
, CallGraphNode
*NewNode
){
286 for (CalledFunctionsVector::iterator I
= CalledFunctions
.begin(); ; ++I
) {
287 assert(I
!= CalledFunctions
.end() && "Cannot find callsite to remove!");
288 if (I
->first
== CS
.getInstruction()) {
289 I
->second
->DropRef();
290 I
->first
= NewCS
.getInstruction();
298 // Enuse that users of CallGraph.h also link with this file
299 DEFINING_FILE_FOR(CallGraph
)