CallGraph.cpp revision 697954c15da58bd8b186dbafdedd8b06db770201 
1//===- CallGraph.cpp - Build a Module's call graph --------------------------=//
2//
3// This file implements call graph construction (from a module), and will
4// eventually implement call graph serialization and deserialization for
5// annotation support.
6//
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.
10//
11//===----------------------------------------------------------------------===//
12
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 "Support/STLExtras.h"
20#include <algorithm>
21
22// getNodeFor - Return the node for the specified method or create one if it
23// does not already exist.
24//
25cfg::CallGraphNode *cfg::CallGraph::getNodeFor(Method *M) {
26  iterator I = MethodMap.find(M);
27  if (I != MethodMap.end()) return I->second;
28
29  assert(M->getParent() == Mod && "Method not in current module!");
30  CallGraphNode *New = new CallGraphNode(M);
31
32  MethodMap.insert(std::make_pair(M, New));
33  return New;
34}
35
36// addToCallGraph - Add a method to the call graph, and link the node to all of
37// the methods that it calls.
38//
39void cfg::CallGraph::addToCallGraph(Method *M) {
40  CallGraphNode *Node = getNodeFor(M);
41
42  // If this method has external linkage,
43  if (!M->hasInternalLinkage())
44    Root->addCalledMethod(Node);
45
46  for (Method::inst_iterator I = M->inst_begin(), E = M->inst_end();
47       I != E; ++I) {
48    // Dynamic calls will cause Null nodes to be created
49    if (CallInst *CI = dyn_cast<CallInst>(*I))
50      Node->addCalledMethod(getNodeFor(CI->getCalledMethod()));
51    else if (InvokeInst *II = dyn_cast<InvokeInst>(*I))
52      Node->addCalledMethod(getNodeFor(II->getCalledMethod()));
53  }
54}
55
56cfg::CallGraph::CallGraph(Module *TheModule) {
57  Mod = TheModule;
58
59  // Create the root node of the module...
60  Root = new CallGraphNode(0);
61
62  // Add every method to the call graph...
63  for_each(Mod->begin(), Mod->end(), bind_obj(this,&CallGraph::addToCallGraph));
64}
65
66cfg::CallGraph::~CallGraph() {
67  for (MethodMapTy::iterator I = MethodMap.begin(), E = MethodMap.end();
68       I != E; ++I) {
69    delete I->second;
70  }
71}
72
73
74void cfg::WriteToOutput(const CallGraphNode *CGN, std::ostream &o) {
75  if (CGN->getMethod())
76    o << "Call graph node for method: '" << CGN->getMethod()->getName() <<"'\n";
77  else
78    o << "Call graph node null method:\n";
79
80  for (unsigned i = 0; i < CGN->size(); ++i)
81    o << "  Calls method '" << (*CGN)[i]->getMethod()->getName() << "'\n";
82  o << "\n";
83}
84
85void cfg::WriteToOutput(const CallGraph &CG, std::ostream &o) {
86  WriteToOutput(CG.getRoot(), o);
87  for (CallGraph::const_iterator I = CG.begin(), E = CG.end(); I != E; ++I)
88    o << I->second;
89}
90
91
92//===----------------------------------------------------------------------===//
93// Implementations of public modification methods
94//
95
96// Methods to keep a call graph up to date with a method that has been
97// modified
98//
99void cfg::CallGraph::addMethodToModule(Method *Meth) {
100  assert(0 && "not implemented");
101  abort();
102}
103
104// removeMethodFromModule - Unlink the method from this module, returning it.
105// Because this removes the method from the module, the call graph node is
106// destroyed.  This is only valid if the method does not call any other
107// methods (ie, there are no edges in it's CGN).  The easiest way to do this
108// is to dropAllReferences before calling this.
109//
110Method *cfg::CallGraph::removeMethodFromModule(CallGraphNode *CGN) {
111  assert(CGN->CalledMethods.empty() && "Cannot remove method from call graph"
112	 " if it references other methods!");
113  Method *M = CGN->getMethod();  // Get the method for the call graph node
114  delete CGN;                    // Delete the call graph node for this method
115  MethodMap.erase(M);            // Remove the call graph node from the map
116
117  Mod->getMethodList().remove(M);
118  return M;
119}
120
121
122//
123// Checks if a method contains any call instructions.
124// Note that this uses the call graph only if one is provided.
125// It does not build the call graph.
126//
127bool IsLeafMethod(const Method* M, const cfg::CallGraph* CG) {
128  if (CG) {
129    const cfg::CallGraphNode *cgn = (*CG)[M];
130    return (cgn->begin() == cgn->end());
131  }
132
133  for (Method::const_inst_iterator I = M->inst_begin(), E = M->inst_end();
134       I != E; ++I)
135    if ((*I)->getOpcode() == Instruction::Call)
136      return false;
137  return true;
138}
139
140
141