CallGraph.h revision facd752d3afaeca7dee46648f2a2ae209a94e5e9
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; 23 24namespace cfg { 25 26class CallGraph; 27class CallGraphNode { 28 Method *Meth; 29 std::vector<CallGraphNode*> CalledMethods; 30 31 CallGraphNode(const CallGraphNode &); // Do not implement 32public: 33 typedef std::vector<CallGraphNode*>::iterator iterator; 34 typedef std::vector<CallGraphNode*>::const_iterator const_iterator; 35 36 // getMethod - Return the method that this call graph node represents... 37 Method *getMethod() const { return Meth; } 38 39 inline iterator begin() { return CalledMethods.begin(); } 40 inline iterator end() { return CalledMethods.end(); } 41 inline const_iterator begin() const { return CalledMethods.begin(); } 42 inline const_iterator end() const { return CalledMethods.end(); } 43 inline unsigned size() const { return CalledMethods.size(); } 44 45 inline CallGraphNode *operator[](unsigned i) const { return CalledMethods[i];} 46 47 void removeAllCalledMethods() { 48 CalledMethods.clear(); 49 } 50 51private: // Stuff to construct the node, used by CallGraph 52 friend class CallGraph; 53 54 // CallGraphNode ctor - Create a node for the specified method... 55 inline CallGraphNode(Method *M) : Meth(M) {} 56 57 // addCalledMethod add a method to the list of methods called by this one 58 void addCalledMethod(CallGraphNode *M) { 59 CalledMethods.push_back(M); 60 } 61}; 62 63 64class CallGraph : public Pass { 65 Module *Mod; // The module this call graph represents 66 67 typedef std::map<const Method *, CallGraphNode *> MethodMapTy; 68 MethodMapTy MethodMap; // Map from a method to its node 69 70 CallGraphNode *Root; 71public: 72 static AnalysisID ID; // We are an analysis, we must have an ID 73 74 CallGraph(AnalysisID AID) : Root(0) { assert(AID == ID); } 75 ~CallGraph() { destroy(); } 76 77 typedef MethodMapTy::iterator iterator; 78 typedef MethodMapTy::const_iterator const_iterator; 79 80 inline CallGraphNode *getRoot() { return Root; } 81 inline const CallGraphNode *getRoot() const { return Root; } 82 inline iterator begin() { return MethodMap.begin(); } 83 inline iterator end() { return MethodMap.end(); } 84 inline const_iterator begin() const { return MethodMap.begin(); } 85 inline const_iterator end() const { return MethodMap.end(); } 86 87 inline const CallGraphNode *operator[](const Method *M) const { 88 const_iterator I = MethodMap.find(M); 89 assert(I != MethodMap.end() && "Method not in callgraph!"); 90 return I->second; 91 } 92 inline CallGraphNode *operator[](const Method *M) { 93 const_iterator I = MethodMap.find(M); 94 assert(I != MethodMap.end() && "Method not in callgraph!"); 95 return I->second; 96 } 97 98 // Methods to keep a call graph up to date with a method that has been 99 // modified 100 // 101 void addMethodToModule(Method *Meth); // TODO IMPLEMENT 102 103 104 // removeMethodFromModule - Unlink the method from this module, returning it. 105 // Because this removes the method from the module, the call graph node is 106 // destroyed. This is only valid if the method does not call any other 107 // methods (ie, there are no edges in it's CGN). The easiest way to do this 108 // is to dropAllReferences before calling this. 109 // 110 Method *removeMethodFromModule(CallGraphNode *CGN); 111 Method *removeMethodFromModule(Method *Meth) { 112 return removeMethodFromModule((*this)[Meth]); 113 } 114 115 // run - Compute the call graph for the specified module. 116 virtual bool run(Module *TheModule); 117 118 // getAnalysisUsageInfo - This obviously provides a call graph 119 virtual void getAnalysisUsageInfo(AnalysisSet &Required, 120 AnalysisSet &Destroyed, 121 AnalysisSet &Provided) { 122 Provided.push_back(ID); 123 } 124 125private: // Implementation of CallGraph construction 126 void destroy(); 127 128 // getNodeFor - Return the node for the specified method or create one if it 129 // does not already exist. 130 // 131 CallGraphNode *getNodeFor(Method *M); 132 133 // addToCallGraph - Add a method to the call graph, and link the node to all 134 // of the methods that it calls. 135 // 136 void addToCallGraph(Method *M); 137}; 138 139} // end namespace cfg 140 141 142 143 144// Provide graph traits for tranversing call graphs using standard graph 145// traversals. 146template <> struct GraphTraits<cfg::CallGraphNode*> { 147 typedef cfg::CallGraphNode NodeType; 148 typedef NodeType::iterator ChildIteratorType; 149 150 static NodeType *getEntryNode(cfg::CallGraphNode *CGN) { return CGN; } 151 static inline ChildIteratorType child_begin(NodeType *N) { return N->begin();} 152 static inline ChildIteratorType child_end (NodeType *N) { return N->end(); } 153}; 154 155template <> struct GraphTraits<const cfg::CallGraphNode*> { 156 typedef const cfg::CallGraphNode NodeType; 157 typedef NodeType::const_iterator ChildIteratorType; 158 159 static NodeType *getEntryNode(const cfg::CallGraphNode *CGN) { return CGN; } 160 static inline ChildIteratorType child_begin(NodeType *N) { return N->begin();} 161 static inline ChildIteratorType child_end (NodeType *N) { return N->end(); } 162}; 163 164 165template<> struct GraphTraits<cfg::CallGraph*> : 166 public GraphTraits<cfg::CallGraphNode*> { 167 static NodeType *getEntryNode(cfg::CallGraph *CGN) { 168 return CGN->getRoot(); 169 } 170}; 171template<> struct GraphTraits<const cfg::CallGraph*> : 172 public GraphTraits<const cfg::CallGraphNode*> { 173 static NodeType *getEntryNode(const cfg::CallGraph *CGN) { 174 return CGN->getRoot(); 175 } 176}; 177 178 179// Checks if a method contains any call instructions. 180// Note that this uses the call graph only if one is provided. 181// It does not build the call graph. 182// 183bool isLeafMethod(const Method* method, const cfg::CallGraph *callGraph = 0); 184 185#endif 186