CallGraph.h revision 697954c15da58bd8b186dbafdedd8b06db770201
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 <map> 21#include <vector> 22class Method; 23class Module; 24 25namespace cfg { 26 27class CallGraph; 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 65class CallGraph { 66 Module *Mod; // The module this call graph represents 67 68 typedef std::map<const Method *, CallGraphNode *> MethodMapTy; 69 MethodMapTy MethodMap; // Map from a method to its node 70 71 CallGraphNode *Root; 72public: 73 CallGraph(Module *TheModule); 74 ~CallGraph(); 75 76 typedef MethodMapTy::iterator iterator; 77 typedef MethodMapTy::const_iterator const_iterator; 78 79 inline CallGraphNode *getRoot() { return Root; } 80 inline const CallGraphNode *getRoot() const { return Root; } 81 inline iterator begin() { return MethodMap.begin(); } 82 inline iterator end() { return MethodMap.end(); } 83 inline const_iterator begin() const { return MethodMap.begin(); } 84 inline const_iterator end() const { return MethodMap.end(); } 85 86 inline const CallGraphNode *operator[](const Method *M) const { 87 const_iterator I = MethodMap.find(M); 88 assert(I != MethodMap.end() && "Method not in callgraph!"); 89 return I->second; 90 } 91 inline CallGraphNode *operator[](const Method *M) { 92 const_iterator I = MethodMap.find(M); 93 assert(I != MethodMap.end() && "Method not in callgraph!"); 94 return I->second; 95 } 96 97 // Methods to keep a call graph up to date with a method that has been 98 // modified 99 // 100 void addMethodToModule(Method *Meth); // TODO IMPLEMENT 101 102 103 // removeMethodFromModule - Unlink the method from this module, returning it. 104 // Because this removes the method from the module, the call graph node is 105 // destroyed. This is only valid if the method does not call any other 106 // methods (ie, there are no edges in it's CGN). The easiest way to do this 107 // is to dropAllReferences before calling this. 108 // 109 Method *removeMethodFromModule(CallGraphNode *CGN); 110 Method *removeMethodFromModule(Method *Meth) { 111 return removeMethodFromModule((*this)[Meth]); 112 } 113 114private: // Implementation of CallGraph construction 115 116 // getNodeFor - Return the node for the specified method or create one if it 117 // does not already exist. 118 // 119 CallGraphNode *getNodeFor(Method *M); 120 121 // addToCallGraph - Add a method to the call graph, and link the node to all 122 // of the methods that it calls. 123 // 124 void addToCallGraph(Method *M); 125}; 126 127} // end namespace cfg 128 129 130 131 132// Provide graph traits for tranversing call graphs using standard graph 133// traversals. 134template <> struct GraphTraits<cfg::CallGraphNode*> { 135 typedef cfg::CallGraphNode NodeType; 136 typedef NodeType::iterator ChildIteratorType; 137 138 static NodeType *getEntryNode(cfg::CallGraphNode *CGN) { return CGN; } 139 static inline ChildIteratorType child_begin(NodeType *N) { return N->begin();} 140 static inline ChildIteratorType child_end (NodeType *N) { return N->end(); } 141}; 142 143template <> struct GraphTraits<const cfg::CallGraphNode*> { 144 typedef const cfg::CallGraphNode NodeType; 145 typedef NodeType::const_iterator ChildIteratorType; 146 147 static NodeType *getEntryNode(const cfg::CallGraphNode *CGN) { return CGN; } 148 static inline ChildIteratorType child_begin(NodeType *N) { return N->begin();} 149 static inline ChildIteratorType child_end (NodeType *N) { return N->end(); } 150}; 151 152 153template<> struct GraphTraits<cfg::CallGraph*> : 154 public GraphTraits<cfg::CallGraphNode*> { 155 static NodeType *getEntryNode(cfg::CallGraph *CGN) { 156 return CGN->getRoot(); 157 } 158}; 159template<> struct GraphTraits<const cfg::CallGraph*> : 160 public GraphTraits<const cfg::CallGraphNode*> { 161 static NodeType *getEntryNode(const cfg::CallGraph *CGN) { 162 return CGN->getRoot(); 163 } 164}; 165 166 167// Checks if a method contains any call instructions. 168// Note that this uses the call graph only if one is provided. 169// It does not build the call graph. 170// 171bool isLeafMethod(const Method* method, const cfg::CallGraph *callGraph = 0); 172 173#endif 174