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