1 //===- CallGraph.cpp - Build a Module's call graph --------------------------=//
3 // This file implements call graph construction (from a module), and will
4 // eventually implement call graph serialization and deserialization for
7 // This call graph represents a dynamic method invocation as a null method node.
8 // A call graph may only have up to one null method node that represents all of
9 // the dynamic method invocations.
11 //===----------------------------------------------------------------------===//
13 #include "llvm/Analysis/CallGraph.h"
14 #include "llvm/Analysis/Writer.h"
15 #include "llvm/Module.h"
16 #include "llvm/Method.h"
17 #include "llvm/iOther.h"
18 #include "llvm/iTerminators.h"
19 #include "llvm/Support/InstIterator.h"// FIXME: CallGraph should use method uses
20 #include "Support/STLExtras.h"
23 AnalysisID cfg::CallGraph::ID(AnalysisID::create<cfg::CallGraph>());
24 //AnalysisID cfg::CallGraph::ID(AnalysisID::template AnalysisID<cfg::CallGraph>());
26 // getNodeFor - Return the node for the specified method or create one if it
27 // does not already exist.
29 cfg::CallGraphNode *cfg::CallGraph::getNodeFor(Method *M) {
30 iterator I = MethodMap.find(M);
31 if (I != MethodMap.end()) return I->second;
33 assert(M->getParent() == Mod && "Method not in current module!");
34 CallGraphNode *New = new CallGraphNode(M);
36 MethodMap.insert(std::make_pair(M, New));
40 // addToCallGraph - Add a method to the call graph, and link the node to all of
41 // the methods that it calls.
43 void cfg::CallGraph::addToCallGraph(Method *M) {
44 CallGraphNode *Node = getNodeFor(M);
46 // If this method has external linkage,
47 if (!M->hasInternalLinkage())
48 Root->addCalledMethod(Node);
50 for (inst_iterator I = inst_begin(M), E = inst_end(M); I != E; ++I) {
51 // Dynamic calls will cause Null nodes to be created
52 if (CallInst *CI = dyn_cast<CallInst>(*I))
53 Node->addCalledMethod(getNodeFor(CI->getCalledMethod()));
54 else if (InvokeInst *II = dyn_cast<InvokeInst>(*I))
55 Node->addCalledMethod(getNodeFor(II->getCalledMethod()));
59 bool cfg::CallGraph::run(Module *TheModule) {
64 // Create the root node of the module...
65 Root = new CallGraphNode(0);
67 // Add every method to the call graph...
68 for_each(Mod->begin(), Mod->end(), bind_obj(this,&CallGraph::addToCallGraph));
73 void cfg::CallGraph::destroy() {
74 for (MethodMapTy::iterator I = MethodMap.begin(), E = MethodMap.end();
82 void cfg::WriteToOutput(const CallGraphNode *CGN, std::ostream &o) {
84 o << "Call graph node for method: '" << CGN->getMethod()->getName() <<"'\n";
86 o << "Call graph node null method:\n";
88 for (unsigned i = 0; i < CGN->size(); ++i)
89 o << " Calls method '" << (*CGN)[i]->getMethod()->getName() << "'\n";
93 void cfg::WriteToOutput(const CallGraph &CG, std::ostream &o) {
94 WriteToOutput(CG.getRoot(), o);
95 for (CallGraph::const_iterator I = CG.begin(), E = CG.end(); I != E; ++I)
100 //===----------------------------------------------------------------------===//
101 // Implementations of public modification methods
104 // Methods to keep a call graph up to date with a method that has been
107 void cfg::CallGraph::addMethodToModule(Method *Meth) {
108 assert(0 && "not implemented");
112 // removeMethodFromModule - Unlink the method from this module, returning it.
113 // Because this removes the method from the module, the call graph node is
114 // destroyed. This is only valid if the method does not call any other
115 // methods (ie, there are no edges in it's CGN). The easiest way to do this
116 // is to dropAllReferences before calling this.
118 Method *cfg::CallGraph::removeMethodFromModule(CallGraphNode *CGN) {
119 assert(CGN->CalledMethods.empty() && "Cannot remove method from call graph"
120 " if it references other methods!");
121 Method *M = CGN->getMethod(); // Get the method for the call graph node
122 delete CGN; // Delete the call graph node for this method
123 MethodMap.erase(M); // Remove the call graph node from the map
125 Mod->getMethodList().remove(M);
131 // Checks if a method contains any call instructions.
132 // Note that this uses the call graph only if one is provided.
133 // It does not build the call graph.
135 bool IsLeafMethod(const Method* M, const cfg::CallGraph* CG) {
137 const cfg::CallGraphNode *cgn = (*CG)[M];
138 return (cgn->begin() == cgn->end());
141 for (const_inst_iterator I = inst_begin(M), E = inst_end(M); I != E; ++I)
142 if ((*I)->getOpcode() == Instruction::Call)