CallGraph.h revision 7e70829632f82de15db187845666aaca6e04b792
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 virtual const char *getPassName() const { return "Call Graph Construction"; } 119 120 // run - Compute the call graph for the specified module. 121 virtual bool run(Module &M); 122 123 // getAnalysisUsage - This obviously provides a call graph 124 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 125 AU.setPreservesAll(); 126 AU.addProvided(ID); 127 } 128 129 // releaseMemory - Data structures can be large, so free memory aggressively. 130 virtual void releaseMemory() { 131 destroy(); 132 } 133 134private: 135 //===--------------------------------------------------------------------- 136 // Implementation of CallGraph construction 137 // 138 139 // getNodeFor - Return the node for the specified function or create one if it 140 // does not already exist. 141 // 142 CallGraphNode *getNodeFor(Function *F); 143 144 // addToCallGraph - Add a function to the call graph, and link the node to all 145 // of the methods that it calls. 146 // 147 void addToCallGraph(Function *F); 148 149 // destroy - Release memory for the call graph 150 void destroy(); 151}; 152 153 154//===----------------------------------------------------------------------===// 155// CallGraphNode class definition 156// 157class CallGraphNode { 158 Function *Meth; 159 std::vector<CallGraphNode*> CalledMethods; 160 161 CallGraphNode(const CallGraphNode &); // Do not implement 162public: 163 //===--------------------------------------------------------------------- 164 // Accessor methods... 165 // 166 167 typedef std::vector<CallGraphNode*>::iterator iterator; 168 typedef std::vector<CallGraphNode*>::const_iterator const_iterator; 169 170 // getMethod - Return the method that this call graph node represents... 171 Function *getMethod() const { return Meth; } 172 173 inline iterator begin() { return CalledMethods.begin(); } 174 inline iterator end() { return CalledMethods.end(); } 175 inline const_iterator begin() const { return CalledMethods.begin(); } 176 inline const_iterator end() const { return CalledMethods.end(); } 177 inline unsigned size() const { return CalledMethods.size(); } 178 179 // Subscripting operator - Return the i'th called method... 180 // 181 inline CallGraphNode *operator[](unsigned i) const { return CalledMethods[i];} 182 183 184 //===--------------------------------------------------------------------- 185 // Methods to keep a call graph up to date with a method that has been 186 // modified 187 // 188 189 void removeAllCalledMethods() { 190 CalledMethods.clear(); 191 } 192 193private: // Stuff to construct the node, used by CallGraph 194 friend class CallGraph; 195 196 // CallGraphNode ctor - Create a node for the specified method... 197 inline CallGraphNode(Function *F) : Meth(F) {} 198 199 // addCalledMethod add a method to the list of methods called by this one 200 void addCalledMethod(CallGraphNode *M) { 201 CalledMethods.push_back(M); 202 } 203}; 204 205 206 207//===----------------------------------------------------------------------===// 208// GraphTraits specializations for call graphs so that they can be treated as 209// graphs by the generic graph algorithms... 210// 211 212// Provide graph traits for tranversing call graphs using standard graph 213// traversals. 214template <> struct GraphTraits<CallGraphNode*> { 215 typedef CallGraphNode NodeType; 216 typedef NodeType::iterator ChildIteratorType; 217 218 static NodeType *getEntryNode(CallGraphNode *CGN) { return CGN; } 219 static inline ChildIteratorType child_begin(NodeType *N) { return N->begin();} 220 static inline ChildIteratorType child_end (NodeType *N) { return N->end(); } 221}; 222 223template <> struct GraphTraits<const CallGraphNode*> { 224 typedef const CallGraphNode NodeType; 225 typedef NodeType::const_iterator ChildIteratorType; 226 227 static NodeType *getEntryNode(const CallGraphNode *CGN) { return CGN; } 228 static inline ChildIteratorType child_begin(NodeType *N) { return N->begin();} 229 static inline ChildIteratorType child_end (NodeType *N) { return N->end(); } 230}; 231 232 233template<> struct GraphTraits<CallGraph*> : 234 public GraphTraits<CallGraphNode*> { 235 static NodeType *getEntryNode(CallGraph *CGN) { 236 return CGN->getRoot(); 237 } 238}; 239template<> struct GraphTraits<const CallGraph*> : 240 public GraphTraits<const CallGraphNode*> { 241 static NodeType *getEntryNode(const CallGraph *CGN) { 242 return CGN->getRoot(); 243 } 244}; 245 246 247//===----------------------------------------------------------------------===// 248// Printing support for Call Graphs 249// 250 251// Stuff for printing out a callgraph... 252 253void WriteToOutput(const CallGraph &, std::ostream &o); 254inline std::ostream &operator <<(std::ostream &o, const CallGraph &CG) { 255 WriteToOutput(CG, o); return o; 256} 257 258void WriteToOutput(const CallGraphNode *, std::ostream &o); 259inline std::ostream &operator <<(std::ostream &o, const CallGraphNode *CGN) { 260 WriteToOutput(CGN, o); return o; 261} 262 263#endif 264