1 |
//===- CallGraph.h - Build a Module's call graph ----------------*- C++ -*-===// |
2 |
// |
3 |
// The LLVM Compiler Infrastructure |
4 |
// |
5 |
// This file is distributed under the University of Illinois Open Source |
6 |
// License. See LICENSE.TXT for details. |
7 |
// |
8 |
//===----------------------------------------------------------------------===// |
9 |
// |
10 |
// This interface is used to build and manipulate a call graph, which is a very |
11 |
// useful tool for interprocedural optimization. |
12 |
// |
13 |
// Every function in a module is represented as a node in the call graph. The |
14 |
// callgraph node keeps track of which functions the are called by the function |
15 |
// corresponding to the node. |
16 |
// |
17 |
// A call graph may contain nodes where the function that they correspond to is |
18 |
// null. These 'external' nodes are used to represent control flow that is not |
19 |
// represented (or analyzable) in the module. In particular, this analysis |
20 |
// builds one external node such that: |
21 |
// 1. All functions in the module without internal linkage will have edges |
22 |
// from this external node, indicating that they could be called by |
23 |
// functions outside of the module. |
24 |
// 2. All functions whose address is used for something more than a direct |
25 |
// call, for example being stored into a memory location will also have an |
26 |
// edge from this external node. Since they may be called by an unknown |
27 |
// caller later, they must be tracked as such. |
28 |
// |
29 |
// There is a second external node added for calls that leave this module. |
30 |
// Functions have a call edge to the external node iff: |
31 |
// 1. The function is external, reflecting the fact that they could call |
32 |
// anything without internal linkage or that has its address taken. |
33 |
// 2. The function contains an indirect function call. |
34 |
// |
35 |
// As an extension in the future, there may be multiple nodes with a null |
36 |
// function. These will be used when we can prove (through pointer analysis) |
37 |
// that an indirect call site can call only a specific set of functions. |
38 |
// |
39 |
// Because of these properties, the CallGraph captures a conservative superset |
40 |
// of all of the caller-callee relationships, which is useful for |
41 |
// transformations. |
42 |
// |
43 |
// The CallGraph class also attempts to figure out what the root of the |
44 |
// CallGraph is, which it currently does by looking for a function named 'main'. |
45 |
// If no function named 'main' is found, the external node is used as the entry |
46 |
// node, reflecting the fact that any function without internal linkage could |
47 |
// be called into (which is common for libraries). |
48 |
// |
49 |
//===----------------------------------------------------------------------===// |
50 |
|
51 |
#ifndef LLVM_ANALYSIS_CALLGRAPH_H |
52 |
#define LLVM_ANALYSIS_CALLGRAPH_H |
53 |
|
54 |
#include "llvm/ADT/GraphTraits.h" |
55 |
#include "llvm/ADT/STLExtras.h" |
56 |
#include "llvm/IR/Function.h" |
57 |
#include "llvm/Pass.h" |
58 |
#include "llvm/Support/CallSite.h" |
59 |
#include "llvm/Support/IncludeFile.h" |
60 |
#include "llvm/Support/ValueHandle.h" |
61 |
#include <map> |
62 |
|
63 |
namespace llvm { |
64 |
|
65 |
class Function; |
66 |
class Module; |
67 |
class CallGraphNode; |
68 |
|
69 |
//===----------------------------------------------------------------------===// |
70 |
// CallGraph class definition |
71 |
// |
72 |
class CallGraph : public ModulePass { |
73 |
Module *Mod; // The module this call graph represents |
74 |
|
75 |
typedef std::map<const Function *, CallGraphNode *> FunctionMapTy; |
76 |
FunctionMapTy FunctionMap; // Map from a function to its node |
77 |
|
78 |
// Root is root of the call graph, or the external node if a 'main' function |
79 |
// couldn't be found. |
80 |
// |
81 |
CallGraphNode *Root; |
82 |
|
83 |
// ExternalCallingNode - This node has edges to all external functions and |
84 |
// those internal functions that have their address taken. |
85 |
CallGraphNode *ExternalCallingNode; |
86 |
|
87 |
// CallsExternalNode - This node has edges to it from all functions making |
88 |
// indirect calls or calling an external function. |
89 |
CallGraphNode *CallsExternalNode; |
90 |
|
91 |
/// Replace the function represented by this node by another. |
92 |
/// This does not rescan the body of the function, so it is suitable when |
93 |
/// splicing the body of one function to another while also updating all |
94 |
/// callers from the old function to the new. |
95 |
/// |
96 |
void spliceFunction(const Function *From, const Function *To); |
97 |
|
98 |
// Add a function to the call graph, and link the node to all of the functions |
99 |
// that it calls. |
100 |
void addToCallGraph(Function *F); |
101 |
|
102 |
public: |
103 |
static char ID; // Class identification, replacement for typeinfo |
104 |
//===--------------------------------------------------------------------- |
105 |
// Accessors. |
106 |
// |
107 |
typedef FunctionMapTy::iterator iterator; |
108 |
typedef FunctionMapTy::const_iterator const_iterator; |
109 |
|
110 |
/// getModule - Return the module the call graph corresponds to. |
111 |
/// |
112 |
Module &getModule() const { return *Mod; } |
113 |
|
114 |
inline iterator begin() { return FunctionMap.begin(); } |
115 |
inline iterator end() { return FunctionMap.end(); } |
116 |
inline const_iterator begin() const { return FunctionMap.begin(); } |
117 |
inline const_iterator end() const { return FunctionMap.end(); } |
118 |
|
119 |
// Subscripting operators, return the call graph node for the provided |
120 |
// function |
121 |
inline const CallGraphNode *operator[](const Function *F) const { |
122 |
const_iterator I = FunctionMap.find(F); |
123 |
assert(I != FunctionMap.end() && "Function not in callgraph!"); |
124 |
return I->second; |
125 |
} |
126 |
inline CallGraphNode *operator[](const Function *F) { |
127 |
const_iterator I = FunctionMap.find(F); |
128 |
assert(I != FunctionMap.end() && "Function not in callgraph!"); |
129 |
return I->second; |
130 |
} |
131 |
|
132 |
/// Returns the CallGraphNode which is used to represent undetermined calls |
133 |
/// into the callgraph. |
134 |
CallGraphNode *getExternalCallingNode() const { return ExternalCallingNode; } |
135 |
CallGraphNode *getCallsExternalNode() const { return CallsExternalNode; } |
136 |
|
137 |
/// Return the root/main method in the module, or some other root node, such |
138 |
/// as the externalcallingnode. |
139 |
CallGraphNode *getRoot() { return Root; } |
140 |
const CallGraphNode *getRoot() const { return Root; } |
141 |
|
142 |
//===--------------------------------------------------------------------- |
143 |
// Functions to keep a call graph up to date with a function that has been |
144 |
// modified. |
145 |
// |
146 |
|
147 |
/// removeFunctionFromModule - Unlink the function from this module, returning |
148 |
/// it. Because this removes the function from the module, the call graph |
149 |
/// node is destroyed. This is only valid if the function does not call any |
150 |
/// other functions (ie, there are no edges in it's CGN). The easiest way to |
151 |
/// do this is to dropAllReferences before calling this. |
152 |
/// |
153 |
Function *removeFunctionFromModule(CallGraphNode *CGN); |
154 |
|
155 |
/// getOrInsertFunction - This method is identical to calling operator[], but |
156 |
/// it will insert a new CallGraphNode for the specified function if one does |
157 |
/// not already exist. |
158 |
CallGraphNode *getOrInsertFunction(const Function *F); |
159 |
|
160 |
CallGraph(); |
161 |
virtual ~CallGraph() { releaseMemory(); } |
162 |
virtual void getAnalysisUsage(AnalysisUsage &AU) const; |
163 |
virtual bool runOnModule(Module &M); |
164 |
virtual void releaseMemory(); |
165 |
|
166 |
void print(raw_ostream &o, const Module *) const; |
167 |
void dump() const; |
168 |
}; |
169 |
|
170 |
//===----------------------------------------------------------------------===// |
171 |
// CallGraphNode class definition. |
172 |
// |
173 |
class CallGraphNode { |
174 |
friend class CallGraph; |
175 |
|
176 |
AssertingVH<Function> F; |
177 |
|
178 |
// CallRecord - This is a pair of the calling instruction (a call or invoke) |
179 |
// and the callgraph node being called. |
180 |
public: |
181 |
typedef std::pair<WeakVH, CallGraphNode*> CallRecord; |
182 |
private: |
183 |
std::vector<CallRecord> CalledFunctions; |
184 |
|
185 |
/// NumReferences - This is the number of times that this CallGraphNode occurs |
186 |
/// in the CalledFunctions array of this or other CallGraphNodes. |
187 |
unsigned NumReferences; |
188 |
|
189 |
CallGraphNode(const CallGraphNode &) LLVM_DELETED_FUNCTION; |
190 |
void operator=(const CallGraphNode &) LLVM_DELETED_FUNCTION; |
191 |
|
192 |
void DropRef() { --NumReferences; } |
193 |
void AddRef() { ++NumReferences; } |
194 |
public: |
195 |
typedef std::vector<CallRecord> CalledFunctionsVector; |
196 |
|
197 |
|
198 |
// CallGraphNode ctor - Create a node for the specified function. |
199 |
inline CallGraphNode(Function *f) : F(f), NumReferences(0) {} |
200 |
~CallGraphNode() { |
201 |
assert(NumReferences == 0 && "Node deleted while references remain"); |
202 |
} |
203 |
|
204 |
//===--------------------------------------------------------------------- |
205 |
// Accessor methods. |
206 |
// |
207 |
|
208 |
typedef std::vector<CallRecord>::iterator iterator; |
209 |
typedef std::vector<CallRecord>::const_iterator const_iterator; |
210 |
|
211 |
// getFunction - Return the function that this call graph node represents. |
212 |
Function *getFunction() const { return F; } |
213 |
|
214 |
inline iterator begin() { return CalledFunctions.begin(); } |
215 |
inline iterator end() { return CalledFunctions.end(); } |
216 |
inline const_iterator begin() const { return CalledFunctions.begin(); } |
217 |
inline const_iterator end() const { return CalledFunctions.end(); } |
218 |
inline bool empty() const { return CalledFunctions.empty(); } |
219 |
inline unsigned size() const { return (unsigned)CalledFunctions.size(); } |
220 |
|
221 |
/// getNumReferences - Return the number of other CallGraphNodes in this |
222 |
/// CallGraph that reference this node in their callee list. |
223 |
unsigned getNumReferences() const { return NumReferences; } |
224 |
|
225 |
// Subscripting operator - Return the i'th called function. |
226 |
// |
227 |
CallGraphNode *operator[](unsigned i) const { |
228 |
assert(i < CalledFunctions.size() && "Invalid index"); |
229 |
return CalledFunctions[i].second; |
230 |
} |
231 |
|
232 |
/// dump - Print out this call graph node. |
233 |
/// |
234 |
void dump() const; |
235 |
void print(raw_ostream &OS) const; |
236 |
|
237 |
//===--------------------------------------------------------------------- |
238 |
// Methods to keep a call graph up to date with a function that has been |
239 |
// modified |
240 |
// |
241 |
|
242 |
/// removeAllCalledFunctions - As the name implies, this removes all edges |
243 |
/// from this CallGraphNode to any functions it calls. |
244 |
void removeAllCalledFunctions() { |
245 |
while (!CalledFunctions.empty()) { |
246 |
CalledFunctions.back().second->DropRef(); |
247 |
CalledFunctions.pop_back(); |
248 |
} |
249 |
} |
250 |
|
251 |
/// stealCalledFunctionsFrom - Move all the callee information from N to this |
252 |
/// node. |
253 |
void stealCalledFunctionsFrom(CallGraphNode *N) { |
254 |
assert(CalledFunctions.empty() && |
255 |
"Cannot steal callsite information if I already have some"); |
256 |
std::swap(CalledFunctions, N->CalledFunctions); |
257 |
} |
258 |
|
259 |
|
260 |
/// addCalledFunction - Add a function to the list of functions called by this |
261 |
/// one. |
262 |
void addCalledFunction(CallSite CS, CallGraphNode *M) { |
263 |
assert(!CS.getInstruction() || |
264 |
!CS.getCalledFunction() || |
265 |
!CS.getCalledFunction()->isIntrinsic()); |
266 |
CalledFunctions.push_back(std::make_pair(CS.getInstruction(), M)); |
267 |
M->AddRef(); |
268 |
} |
269 |
|
270 |
void removeCallEdge(iterator I) { |
271 |
I->second->DropRef(); |
272 |
*I = CalledFunctions.back(); |
273 |
CalledFunctions.pop_back(); |
274 |
} |
275 |
|
276 |
|
277 |
/// removeCallEdgeFor - This method removes the edge in the node for the |
278 |
/// specified call site. Note that this method takes linear time, so it |
279 |
/// should be used sparingly. |
280 |
void removeCallEdgeFor(CallSite CS); |
281 |
|
282 |
/// removeAnyCallEdgeTo - This method removes all call edges from this node |
283 |
/// to the specified callee function. This takes more time to execute than |
284 |
/// removeCallEdgeTo, so it should not be used unless necessary. |
285 |
void removeAnyCallEdgeTo(CallGraphNode *Callee); |
286 |
|
287 |
/// removeOneAbstractEdgeTo - Remove one edge associated with a null callsite |
288 |
/// from this node to the specified callee function. |
289 |
void removeOneAbstractEdgeTo(CallGraphNode *Callee); |
290 |
|
291 |
/// replaceCallEdge - This method replaces the edge in the node for the |
292 |
/// specified call site with a new one. Note that this method takes linear |
293 |
/// time, so it should be used sparingly. |
294 |
void replaceCallEdge(CallSite CS, CallSite NewCS, CallGraphNode *NewNode); |
295 |
|
296 |
/// allReferencesDropped - This is a special function that should only be |
297 |
/// used by the CallGraph class. |
298 |
void allReferencesDropped() { |
299 |
NumReferences = 0; |
300 |
} |
301 |
}; |
302 |
|
303 |
//===----------------------------------------------------------------------===// |
304 |
// GraphTraits specializations for call graphs so that they can be treated as |
305 |
// graphs by the generic graph algorithms. |
306 |
// |
307 |
|
308 |
// Provide graph traits for tranversing call graphs using standard graph |
309 |
// traversals. |
310 |
template <> struct GraphTraits<CallGraphNode*> { |
311 |
typedef CallGraphNode NodeType; |
312 |
|
313 |
typedef CallGraphNode::CallRecord CGNPairTy; |
314 |
typedef std::pointer_to_unary_function<CGNPairTy, CallGraphNode*> CGNDerefFun; |
315 |
|
316 |
static NodeType *getEntryNode(CallGraphNode *CGN) { return CGN; } |
317 |
|
318 |
typedef mapped_iterator<NodeType::iterator, CGNDerefFun> ChildIteratorType; |
319 |
|
320 |
static inline ChildIteratorType child_begin(NodeType *N) { |
321 |
return map_iterator(N->begin(), CGNDerefFun(CGNDeref)); |
322 |
} |
323 |
static inline ChildIteratorType child_end (NodeType *N) { |
324 |
return map_iterator(N->end(), CGNDerefFun(CGNDeref)); |
325 |
} |
326 |
|
327 |
static CallGraphNode *CGNDeref(CGNPairTy P) { |
328 |
return P.second; |
329 |
} |
330 |
|
331 |
}; |
332 |
|
333 |
template <> struct GraphTraits<const CallGraphNode*> { |
334 |
typedef const CallGraphNode NodeType; |
335 |
typedef NodeType::const_iterator ChildIteratorType; |
336 |
|
337 |
static NodeType *getEntryNode(const CallGraphNode *CGN) { return CGN; } |
338 |
static inline ChildIteratorType child_begin(NodeType *N) { return N->begin();} |
339 |
static inline ChildIteratorType child_end (NodeType *N) { return N->end(); } |
340 |
}; |
341 |
|
342 |
template<> struct GraphTraits<CallGraph*> : public GraphTraits<CallGraphNode*> { |
343 |
static NodeType *getEntryNode(CallGraph *CGN) { |
344 |
return CGN->getExternalCallingNode(); // Start at the external node! |
345 |
} |
346 |
typedef std::pair<const Function*, CallGraphNode*> PairTy; |
347 |
typedef std::pointer_to_unary_function<PairTy, CallGraphNode&> DerefFun; |
348 |
|
349 |
// nodes_iterator/begin/end - Allow iteration over all nodes in the graph |
350 |
typedef mapped_iterator<CallGraph::iterator, DerefFun> nodes_iterator; |
351 |
static nodes_iterator nodes_begin(CallGraph *CG) { |
352 |
return map_iterator(CG->begin(), DerefFun(CGdereference)); |
353 |
} |
354 |
static nodes_iterator nodes_end (CallGraph *CG) { |
355 |
return map_iterator(CG->end(), DerefFun(CGdereference)); |
356 |
} |
357 |
|
358 |
static CallGraphNode &CGdereference(PairTy P) { |
359 |
return *P.second; |
360 |
} |
361 |
}; |
362 |
|
363 |
template<> struct GraphTraits<const CallGraph*> : |
364 |
public GraphTraits<const CallGraphNode*> { |
365 |
static NodeType *getEntryNode(const CallGraph *CGN) { |
366 |
return CGN->getExternalCallingNode(); |
367 |
} |
368 |
// nodes_iterator/begin/end - Allow iteration over all nodes in the graph |
369 |
typedef CallGraph::const_iterator nodes_iterator; |
370 |
static nodes_iterator nodes_begin(const CallGraph *CG) { return CG->begin(); } |
371 |
static nodes_iterator nodes_end (const CallGraph *CG) { return CG->end(); } |
372 |
}; |
373 |
|
374 |
} // End llvm namespace |
375 |
|
376 |
// Make sure that any clients of this file link in CallGraph.cpp |
377 |
FORCE_DEFINING_FILE_TO_BE_LINKED(CallGraph) |
378 |
|
379 |
#endif |