CallGraph.h revision bf4bf53dfd447614a2f4178791a1f6cbd76d8137
1//===- llvm/Analysis/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// This call graph represents a dynamic method invocation as a null method node. 7// A call graph may only have up to one null method node that represents all of 8// the dynamic method invocations. 9// 10// Additionally, the 'root' node of a call graph represents the "entry point" 11// node of the graph, which has an edge to every external method in the graph. 12// This node has a null method pointer. 13// 14//===----------------------------------------------------------------------===// 15 16#ifndef LLVM_ANALYSIS_CALLGRAPH_H 17#define LLVM_ANALYSIS_CALLGRAPH_H 18 19#include "Support/GraphTraits.h" 20#include "llvm/Pass.h" 21class Method; 22class Module; 23class CallGraph; 24 25//===----------------------------------------------------------------------===// 26// CallGraphNode class definition 27// 28class CallGraphNode { 29 Method *Meth; 30 std::vector<CallGraphNode*> CalledMethods; 31 32 CallGraphNode(const CallGraphNode &); // Do not implement 33public: 34 typedef std::vector<CallGraphNode*>::iterator iterator; 35 typedef std::vector<CallGraphNode*>::const_iterator const_iterator; 36 37 // getMethod - Return the method that this call graph node represents... 38 Method *getMethod() const { return Meth; } 39 40 inline iterator begin() { return CalledMethods.begin(); } 41 inline iterator end() { return CalledMethods.end(); } 42 inline const_iterator begin() const { return CalledMethods.begin(); } 43 inline const_iterator end() const { return CalledMethods.end(); } 44 inline unsigned size() const { return CalledMethods.size(); } 45 46 inline CallGraphNode *operator[](unsigned i) const { return CalledMethods[i];} 47 48 void removeAllCalledMethods() { 49 CalledMethods.clear(); 50 } 51 52private: // Stuff to construct the node, used by CallGraph 53 friend class CallGraph; 54 55 // CallGraphNode ctor - Create a node for the specified method... 56 inline CallGraphNode(Method *M) : Meth(M) {} 57 58 // addCalledMethod add a method to the list of methods called by this one 59 void addCalledMethod(CallGraphNode *M) { 60 CalledMethods.push_back(M); 61 } 62}; 63 64 65//===----------------------------------------------------------------------===// 66// CallGraph class definition 67// 68class CallGraph : public Pass { 69 Module *Mod; // The module this call graph represents 70 71 typedef std::map<const Method *, CallGraphNode *> MethodMapTy; 72 MethodMapTy MethodMap; // Map from a method to its node 73 74 CallGraphNode *Root; 75public: 76 static AnalysisID ID; // We are an analysis, we must have an ID 77 78 CallGraph(AnalysisID AID) : Root(0) { assert(AID == ID); } 79 ~CallGraph() { destroy(); } 80 81 typedef MethodMapTy::iterator iterator; 82 typedef MethodMapTy::const_iterator const_iterator; 83 84 inline CallGraphNode *getRoot() { return Root; } 85 inline const CallGraphNode *getRoot() const { return Root; } 86 inline iterator begin() { return MethodMap.begin(); } 87 inline iterator end() { return MethodMap.end(); } 88 inline const_iterator begin() const { return MethodMap.begin(); } 89 inline const_iterator end() const { return MethodMap.end(); } 90 91 inline const CallGraphNode *operator[](const Method *M) const { 92 const_iterator I = MethodMap.find(M); 93 assert(I != MethodMap.end() && "Method not in callgraph!"); 94 return I->second; 95 } 96 inline CallGraphNode *operator[](const Method *M) { 97 const_iterator I = MethodMap.find(M); 98 assert(I != MethodMap.end() && "Method not in callgraph!"); 99 return I->second; 100 } 101 102 // Methods to keep a call graph up to date with a method that has been 103 // modified 104 // 105 void addMethodToModule(Method *Meth); // TODO IMPLEMENT 106 107 108 // removeMethodFromModule - Unlink the method from this module, returning it. 109 // Because this removes the method from the module, the call graph node is 110 // destroyed. This is only valid if the method does not call any other 111 // methods (ie, there are no edges in it's CGN). The easiest way to do this 112 // is to dropAllReferences before calling this. 113 // 114 Method *removeMethodFromModule(CallGraphNode *CGN); 115 Method *removeMethodFromModule(Method *Meth) { 116 return removeMethodFromModule((*this)[Meth]); 117 } 118 119 // run - Compute the call graph for the specified module. 120 virtual bool run(Module *TheModule); 121 122 // getAnalysisUsageInfo - This obviously provides a call graph 123 virtual void getAnalysisUsageInfo(AnalysisSet &Required, 124 AnalysisSet &Destroyed, 125 AnalysisSet &Provided) { 126 Provided.push_back(ID); 127 } 128 129 // releaseMemory - Data structures can be large, so free memory agressively. 130 virtual void releaseMemory() { 131 destroy(); 132 } 133 134private: // Implementation of CallGraph construction 135 void destroy(); 136 137 // getNodeFor - Return the node for the specified method or create one if it 138 // does not already exist. 139 // 140 CallGraphNode *getNodeFor(Method *M); 141 142 // addToCallGraph - Add a method to the call graph, and link the node to all 143 // of the methods that it calls. 144 // 145 void addToCallGraph(Method *M); 146}; 147 148 149//===----------------------------------------------------------------------===// 150// GraphTraits specializations for call graphs so that they can be treated as 151// graphs by the generic graph algorithms... 152// 153 154// Provide graph traits for tranversing call graphs using standard graph 155// traversals. 156template <> struct GraphTraits<CallGraphNode*> { 157 typedef CallGraphNode NodeType; 158 typedef NodeType::iterator ChildIteratorType; 159 160 static NodeType *getEntryNode(CallGraphNode *CGN) { return CGN; } 161 static inline ChildIteratorType child_begin(NodeType *N) { return N->begin();} 162 static inline ChildIteratorType child_end (NodeType *N) { return N->end(); } 163}; 164 165template <> struct GraphTraits<const CallGraphNode*> { 166 typedef const CallGraphNode NodeType; 167 typedef NodeType::const_iterator ChildIteratorType; 168 169 static NodeType *getEntryNode(const CallGraphNode *CGN) { return CGN; } 170 static inline ChildIteratorType child_begin(NodeType *N) { return N->begin();} 171 static inline ChildIteratorType child_end (NodeType *N) { return N->end(); } 172}; 173 174 175template<> struct GraphTraits<CallGraph*> : 176 public GraphTraits<CallGraphNode*> { 177 static NodeType *getEntryNode(CallGraph *CGN) { 178 return CGN->getRoot(); 179 } 180}; 181template<> struct GraphTraits<const CallGraph*> : 182 public GraphTraits<const CallGraphNode*> { 183 static NodeType *getEntryNode(const CallGraph *CGN) { 184 return CGN->getRoot(); 185 } 186}; 187 188 189//===----------------------------------------------------------------------===// 190// Printing support for Call Graphs 191// 192 193// Stuff for printing out a callgraph... 194 195void WriteToOutput(const CallGraph &, std::ostream &o); 196inline std::ostream &operator <<(std::ostream &o, const CallGraph &CG) { 197 WriteToOutput(CG, o); return o; 198} 199 200void WriteToOutput(const CallGraphNode *, std::ostream &o); 201inline std::ostream &operator <<(std::ostream &o, const CallGraphNode *CGN) { 202 WriteToOutput(CGN, o); return o; 203} 204 205#endif 206