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/Support/STLExtras.h"
16 #include "llvm/Module.h"
17 #include "llvm/Method.h"
18 #include "llvm/iOther.h"
19 #include "llvm/iTerminators.h"
24 // getNodeFor - Return the node for the specified method or create one if it
25 // does not already exist.
27 CallGraphNode *CallGraph::getNodeFor(Method *M) {
28 iterator I = MethodMap.find(M);
29 if (I != MethodMap.end()) return I->second;
31 assert(M->getParent() == Mod && "Method not in current module!");
32 CallGraphNode *New = new CallGraphNode(M);
34 MethodMap.insert(pair<const Method*, CallGraphNode*>(M, New));
38 // addToCallGraph - Add a method to the call graph, and link the node to all of
39 // the methods that it calls.
41 void CallGraph::addToCallGraph(Method *M) {
42 CallGraphNode *Node = getNodeFor(M);
44 for (Method::inst_iterator I = M->inst_begin(), E = M->inst_end();
46 // Dynamic calls will cause Null nodes to be created
47 if (CallInst *CI = dyn_cast<CallInst>(*I))
48 Node->addCalledMethod(getNodeFor(CI->getCalledMethod()));
49 else if (InvokeInst *II = dyn_cast<InvokeInst>(*I))
50 Node->addCalledMethod(getNodeFor(II->getCalledMethod()));
54 CallGraph::CallGraph(Module *TheModule) {
57 // Add every method to the call graph...
58 for_each(Mod->begin(), Mod->end(), bind_obj(this,&CallGraph::addToCallGraph));
62 void cfg::WriteToOutput(const CallGraphNode *CGN, ostream &o) {
63 o << "Call graph node for method: '" << CGN->getMethod()->getName() << "'\n";
64 for (unsigned i = 0; i < CGN->size(); ++i)
65 o << " Calls method '" << (*CGN)[i]->getMethod()->getName() << "'\n";
69 void cfg::WriteToOutput(const CallGraph &CG, ostream &o) {
70 for (CallGraph::const_iterator I = CG.begin(), E = CG.end(); I != E; ++I)
77 // Checks if a method contains any call instructions.
78 // Note that this uses the call graph only if one is provided.
79 // It does not build the call graph.
81 bool IsLeafMethod(const Method* M, const cfg::CallGraph* CG) {
83 const cfg::CallGraphNode *cgn = (*CG)[M];
84 return (cgn->begin() == cgn->end());
87 for (Method::inst_const_iterator I = M->inst_begin(), E = M->inst_end();
89 if ((*I)->getOpcode() == Instruction::Call)