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