CallGraph.h revision f57b845547302d24ecb6a9e79d7bc386f761a6c9
1//===- CallGraph.h - Build a Module's call graph -----------------*- C++ -*--=// 2// 3// This interface is used to build and manipulate a call graph, which is a very 4// useful tool for interprocedural optimization. 5// 6// Every method in a module is represented as a node in the call graph. The 7// callgraph node keeps track of which methods the are called by the method 8// corresponding to the node. 9// 10// A call graph will contain nodes where the method that they correspond to is 11// null. This 'external' node is used to represent control flow that is not 12// represented (or analyzable) in the module. As such, the external node will 13// have edges to methods with the following properties: 14// 1. All methods in the module without internal linkage, since they could 15// be called by methods outside of the our analysis capability. 16// 2. All methods whose address is used for something more than a direct call, 17// for example being stored into a memory location. Since they may be 18// called by an unknown caller later, they must be tracked as such. 19// 20// Similarly, methods have a call edge to the external node iff: 21// 1. The method is external, reflecting the fact that they could call 22// anything without internal linkage or that has its address taken. 23// 2. The method contains an indirect method call. 24// 25// As an extension in the future, there may be multiple nodes with a null 26// method. These will be used when we can prove (through pointer analysis) that 27// an indirect call site can call only a specific set of methods. 28// 29// Because of these properties, the CallGraph captures a conservative superset 30// of all of the caller-callee relationships, which is useful for 31// transformations. 32// 33// The CallGraph class also attempts to figure out what the root of the 34// CallGraph is, which is currently does by looking for a method named 'main'. 35// If no method named 'main' is found, the external node is used as the entry 36// node, reflecting the fact that any method without internal linkage could 37// be called into (which is common for libraries). 38// 39//===----------------------------------------------------------------------===// 40 41#ifndef LLVM_ANALYSIS_CALLGRAPH_H 42#define LLVM_ANALYSIS_CALLGRAPH_H 43 44#include "Support/GraphTraits.h" 45#include "llvm/Pass.h" 46class Function; 47class Module; 48class CallGraphNode; 49 50//===----------------------------------------------------------------------===// 51// CallGraph class definition 52// 53class CallGraph : public Pass { 54 Module *Mod; // The module this call graph represents 55 56 typedef std::map<const Function *, CallGraphNode *> MethodMapTy; 57 MethodMapTy MethodMap; // Map from a method to its node 58 59 // Root is root of the call graph, or the external node if a 'main' function 60 // couldn't be found. ExternalNode is equivalent to (*this)[0]. 61 // 62 CallGraphNode *Root, *ExternalNode; 63public: 64 65 //===--------------------------------------------------------------------- 66 // Accessors... 67 // 68 typedef MethodMapTy::iterator iterator; 69 typedef MethodMapTy::const_iterator const_iterator; 70 71 inline CallGraphNode *getRoot() { return Root; } 72 inline const CallGraphNode *getRoot() const { return Root; } 73 inline iterator begin() { return MethodMap.begin(); } 74 inline iterator end() { return MethodMap.end(); } 75 inline const_iterator begin() const { return MethodMap.begin(); } 76 inline const_iterator end() const { return MethodMap.end(); } 77 78 79 // Subscripting operators, return the call graph node for the provided method 80 inline const CallGraphNode *operator[](const Function *F) const { 81 const_iterator I = MethodMap.find(F); 82 assert(I != MethodMap.end() && "Method not in callgraph!"); 83 return I->second; 84 } 85 inline CallGraphNode *operator[](const Function *F) { 86 const_iterator I = MethodMap.find(F); 87 assert(I != MethodMap.end() && "Method not in callgraph!"); 88 return I->second; 89 } 90 91 //===--------------------------------------------------------------------- 92 // Methods to keep a call graph up to date with a method that has been 93 // modified 94 // 95 void addMethodToModule(Function *Meth); 96 97 98 // removeMethodFromModule - Unlink the method from this module, returning it. 99 // Because this removes the method from the module, the call graph node is 100 // destroyed. This is only valid if the method does not call any other 101 // methods (ie, there are no edges in it's CGN). The easiest way to do this 102 // is to dropAllReferences before calling this. 103 // 104 Function *removeMethodFromModule(CallGraphNode *CGN); 105 Function *removeMethodFromModule(Function *Meth) { 106 return removeMethodFromModule((*this)[Meth]); 107 } 108 109 110 //===--------------------------------------------------------------------- 111 // Pass infrastructure interface glue code... 112 // 113 static AnalysisID ID; // We are an analysis, we must have an ID 114 115 CallGraph(AnalysisID AID) : Root(0) { assert(AID == ID); } 116 ~CallGraph() { destroy(); } 117 118 // run - Compute the call graph for the specified module. 119 virtual bool run(Module *TheModule); 120 121 // getAnalysisUsage - This obviously provides a call graph 122 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 123 AU.setPreservesAll(); 124 AU.addProvided(ID); 125 } 126 127 // releaseMemory - Data structures can be large, so free memory agressively. 128 virtual void releaseMemory() { 129 destroy(); 130 } 131 132private: 133 //===--------------------------------------------------------------------- 134 // Implementation of CallGraph construction 135 // 136 137 // getNodeFor - Return the node for the specified function or create one if it 138 // does not already exist. 139 // 140 CallGraphNode *getNodeFor(Function *F); 141 142 // addToCallGraph - Add a function to the call graph, and link the node to all 143 // of the methods that it calls. 144 // 145 void addToCallGraph(Function *F); 146 147 // destroy - Release memory for the call graph 148 void destroy(); 149}; 150 151 152//===----------------------------------------------------------------------===// 153// CallGraphNode class definition 154// 155class CallGraphNode { 156 Function *Meth; 157 std::vector<CallGraphNode*> CalledMethods; 158 159 CallGraphNode(const CallGraphNode &); // Do not implement 160public: 161 //===--------------------------------------------------------------------- 162 // Accessor methods... 163 // 164 165 typedef std::vector<CallGraphNode*>::iterator iterator; 166 typedef std::vector<CallGraphNode*>::const_iterator const_iterator; 167 168 // getMethod - Return the method that this call graph node represents... 169 Function *getMethod() const { return Meth; } 170 171 inline iterator begin() { return CalledMethods.begin(); } 172 inline iterator end() { return CalledMethods.end(); } 173 inline const_iterator begin() const { return CalledMethods.begin(); } 174 inline const_iterator end() const { return CalledMethods.end(); } 175 inline unsigned size() const { return CalledMethods.size(); } 176 177 // Subscripting operator - Return the i'th called method... 178 // 179 inline CallGraphNode *operator[](unsigned i) const { return CalledMethods[i];} 180 181 182 //===--------------------------------------------------------------------- 183 // Methods to keep a call graph up to date with a method that has been 184 // modified 185 // 186 187 void removeAllCalledMethods() { 188 CalledMethods.clear(); 189 } 190 191private: // Stuff to construct the node, used by CallGraph 192 friend class CallGraph; 193 194 // CallGraphNode ctor - Create a node for the specified method... 195 inline CallGraphNode(Function *F) : Meth(F) {} 196 197 // addCalledMethod add a method to the list of methods called by this one 198 void addCalledMethod(CallGraphNode *M) { 199 CalledMethods.push_back(M); 200 } 201}; 202 203 204 205//===----------------------------------------------------------------------===// 206// GraphTraits specializations for call graphs so that they can be treated as 207// graphs by the generic graph algorithms... 208// 209 210// Provide graph traits for tranversing call graphs using standard graph 211// traversals. 212template <> struct GraphTraits<CallGraphNode*> { 213 typedef CallGraphNode NodeType; 214 typedef NodeType::iterator ChildIteratorType; 215 216 static NodeType *getEntryNode(CallGraphNode *CGN) { return CGN; } 217 static inline ChildIteratorType child_begin(NodeType *N) { return N->begin();} 218 static inline ChildIteratorType child_end (NodeType *N) { return N->end(); } 219}; 220 221template <> struct GraphTraits<const CallGraphNode*> { 222 typedef const CallGraphNode NodeType; 223 typedef NodeType::const_iterator ChildIteratorType; 224 225 static NodeType *getEntryNode(const CallGraphNode *CGN) { return CGN; } 226 static inline ChildIteratorType child_begin(NodeType *N) { return N->begin();} 227 static inline ChildIteratorType child_end (NodeType *N) { return N->end(); } 228}; 229 230 231template<> struct GraphTraits<CallGraph*> : 232 public GraphTraits<CallGraphNode*> { 233 static NodeType *getEntryNode(CallGraph *CGN) { 234 return CGN->getRoot(); 235 } 236}; 237template<> struct GraphTraits<const CallGraph*> : 238 public GraphTraits<const CallGraphNode*> { 239 static NodeType *getEntryNode(const CallGraph *CGN) { 240 return CGN->getRoot(); 241 } 242}; 243 244 245//===----------------------------------------------------------------------===// 246// Printing support for Call Graphs 247// 248 249// Stuff for printing out a callgraph... 250 251void WriteToOutput(const CallGraph &, std::ostream &o); 252inline std::ostream &operator <<(std::ostream &o, const CallGraph &CG) { 253 WriteToOutput(CG, o); return o; 254} 255 256void WriteToOutput(const CallGraphNode *, std::ostream &o); 257inline std::ostream &operator <<(std::ostream &o, const CallGraphNode *CGN) { 258 WriteToOutput(CGN, o); return o; 259} 260 261#endif 262