LLVM API Documentation
00001 //===- CallGraph.h - Build a Module's call graph ----------------*- C++ -*-===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This interface is used to build and manipulate a call graph, which is a very 00011 // useful tool for interprocedural optimization. 00012 // 00013 // Every function in a module is represented as a node in the call graph. The 00014 // callgraph node keeps track of which functions the are called by the function 00015 // corresponding to the node. 00016 // 00017 // A call graph may contain nodes where the function that they correspond to is 00018 // null. These 'external' nodes are used to represent control flow that is not 00019 // represented (or analyzable) in the module. In particular, this analysis 00020 // builds one external node such that: 00021 // 1. All functions in the module without internal linkage will have edges 00022 // from this external node, indicating that they could be called by 00023 // functions outside of the module. 00024 // 2. All functions whose address is used for something more than a direct 00025 // call, for example being stored into a memory location will also have an 00026 // edge from this external node. Since they may be called by an unknown 00027 // caller later, they must be tracked as such. 00028 // 00029 // There is a second external node added for calls that leave this module. 00030 // Functions have a call edge to the external node iff: 00031 // 1. The function is external, reflecting the fact that they could call 00032 // anything without internal linkage or that has its address taken. 00033 // 2. The function contains an indirect function call. 00034 // 00035 // As an extension in the future, there may be multiple nodes with a null 00036 // function. These will be used when we can prove (through pointer analysis) 00037 // that an indirect call site can call only a specific set of functions. 00038 // 00039 // Because of these properties, the CallGraph captures a conservative superset 00040 // of all of the caller-callee relationships, which is useful for 00041 // transformations. 00042 // 00043 // The CallGraph class also attempts to figure out what the root of the 00044 // CallGraph is, which it currently does by looking for a function named 'main'. 00045 // If no function named 'main' is found, the external node is used as the entry 00046 // node, reflecting the fact that any function without internal linkage could 00047 // be called into (which is common for libraries). 00048 // 00049 //===----------------------------------------------------------------------===// 00050 00051 #ifndef LLVM_ANALYSIS_CALLGRAPH_H 00052 #define LLVM_ANALYSIS_CALLGRAPH_H 00053 00054 #include "llvm/ADT/GraphTraits.h" 00055 #include "llvm/ADT/STLExtras.h" 00056 #include "llvm/Pass.h" 00057 00058 namespace llvm { 00059 00060 class Function; 00061 class Module; 00062 class CallGraphNode; 00063 00064 //===----------------------------------------------------------------------===// 00065 // CallGraph class definition 00066 // 00067 class CallGraph : public ModulePass { 00068 Module *Mod; // The module this call graph represents 00069 00070 typedef std::map<const Function *, CallGraphNode *> FunctionMapTy; 00071 FunctionMapTy FunctionMap; // Map from a function to its node 00072 00073 // Root is root of the call graph, or the external node if a 'main' function 00074 // couldn't be found. 00075 // 00076 CallGraphNode *Root; 00077 00078 // ExternalCallingNode - This node has edges to all external functions and 00079 // those internal functions that have their address taken. 00080 CallGraphNode *ExternalCallingNode; 00081 00082 // CallsExternalNode - This node has edges to it from all functions making 00083 // indirect calls or calling an external function. 00084 CallGraphNode *CallsExternalNode; 00085 00086 public: 00087 //===--------------------------------------------------------------------- 00088 // Accessors... 00089 // 00090 typedef FunctionMapTy::iterator iterator; 00091 typedef FunctionMapTy::const_iterator const_iterator; 00092 00093 CallGraphNode *getExternalCallingNode() const { return ExternalCallingNode; } 00094 CallGraphNode *getCallsExternalNode() const { return CallsExternalNode; } 00095 00096 // getRoot - Return the root of the call graph, which is either main, or if 00097 // main cannot be found, the external node. 00098 // 00099 CallGraphNode *getRoot() { return Root; } 00100 const CallGraphNode *getRoot() const { return Root; } 00101 00102 /// getModule - Return the module the call graph corresponds to. 00103 /// 00104 Module &getModule() const { return *Mod; } 00105 00106 inline iterator begin() { return FunctionMap.begin(); } 00107 inline iterator end() { return FunctionMap.end(); } 00108 inline const_iterator begin() const { return FunctionMap.begin(); } 00109 inline const_iterator end() const { return FunctionMap.end(); } 00110 00111 00112 // Subscripting operators, return the call graph node for the provided 00113 // function 00114 inline const CallGraphNode *operator[](const Function *F) const { 00115 const_iterator I = FunctionMap.find(F); 00116 assert(I != FunctionMap.end() && "Function not in callgraph!"); 00117 return I->second; 00118 } 00119 inline CallGraphNode *operator[](const Function *F) { 00120 const_iterator I = FunctionMap.find(F); 00121 assert(I != FunctionMap.end() && "Function not in callgraph!"); 00122 return I->second; 00123 } 00124 00125 //===--------------------------------------------------------------------- 00126 // Functions to keep a call graph up to date with a function that has been 00127 // modified. 00128 // 00129 00130 /// removeFunctionFromModule - Unlink the function from this module, returning 00131 /// it. Because this removes the function from the module, the call graph 00132 /// node is destroyed. This is only valid if the function does not call any 00133 /// other functions (ie, there are no edges in it's CGN). The easiest way to 00134 /// do this is to dropAllReferences before calling this. 00135 /// 00136 Function *removeFunctionFromModule(CallGraphNode *CGN); 00137 Function *removeFunctionFromModule(Function *F) { 00138 return removeFunctionFromModule((*this)[F]); 00139 } 00140 00141 /// changeFunction - This method changes the function associated with this 00142 /// CallGraphNode, for use by transformations that need to change the 00143 /// prototype of a Function (thus they must create a new Function and move the 00144 /// old code over). 00145 void changeFunction(Function *OldF, Function *NewF); 00146 00147 //===--------------------------------------------------------------------- 00148 // Pass infrastructure interface glue code... 00149 // 00150 CallGraph() : Root(0), CallsExternalNode(0) {} 00151 ~CallGraph() { destroy(); } 00152 00153 // runOnModule - Compute the call graph for the specified module. 00154 virtual bool runOnModule(Module &M); 00155 00156 // getAnalysisUsage - This obviously provides a call graph 00157 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00158 AU.setPreservesAll(); 00159 } 00160 00161 // releaseMemory - Data structures can be large, so free memory aggressively. 00162 virtual void releaseMemory() { 00163 destroy(); 00164 } 00165 00166 /// Print the types found in the module. If the optional Module parameter is 00167 /// passed in, then the types are printed symbolically if possible, using the 00168 /// symbol table from the module. 00169 /// 00170 void print(std::ostream &o, const Module *M) const; 00171 00172 /// dump - Print out this call graph. 00173 /// 00174 void dump() const; 00175 00176 // stub - dummy function, just ignore it 00177 static void stub(); 00178 private: 00179 //===--------------------------------------------------------------------- 00180 // Implementation of CallGraph construction 00181 // 00182 00183 // getNodeFor - Return the node for the specified function or create one if it 00184 // does not already exist. 00185 // 00186 CallGraphNode *getNodeFor(Function *F); 00187 00188 // addToCallGraph - Add a function to the call graph, and link the node to all 00189 // of the functions that it calls. 00190 // 00191 void addToCallGraph(Function *F); 00192 00193 // destroy - Release memory for the call graph 00194 void destroy(); 00195 }; 00196 00197 00198 //===----------------------------------------------------------------------===// 00199 // CallGraphNode class definition 00200 // 00201 class CallGraphNode { 00202 Function *F; 00203 std::vector<CallGraphNode*> CalledFunctions; 00204 00205 CallGraphNode(const CallGraphNode &); // Do not implement 00206 public: 00207 //===--------------------------------------------------------------------- 00208 // Accessor methods... 00209 // 00210 00211 typedef std::vector<CallGraphNode*>::iterator iterator; 00212 typedef std::vector<CallGraphNode*>::const_iterator const_iterator; 00213 00214 // getFunction - Return the function that this call graph node represents... 00215 Function *getFunction() const { return F; } 00216 00217 inline iterator begin() { return CalledFunctions.begin(); } 00218 inline iterator end() { return CalledFunctions.end(); } 00219 inline const_iterator begin() const { return CalledFunctions.begin(); } 00220 inline const_iterator end() const { return CalledFunctions.end(); } 00221 inline unsigned size() const { return CalledFunctions.size(); } 00222 00223 // Subscripting operator - Return the i'th called function... 00224 // 00225 CallGraphNode *operator[](unsigned i) const { return CalledFunctions[i];} 00226 00227 /// dump - Print out this call graph node. 00228 /// 00229 void dump() const; 00230 void print(std::ostream &OS) const; 00231 00232 //===--------------------------------------------------------------------- 00233 // Methods to keep a call graph up to date with a function that has been 00234 // modified 00235 // 00236 00237 /// removeAllCalledFunctions - As the name implies, this removes all edges 00238 /// from this CallGraphNode to any functions it calls. 00239 void removeAllCalledFunctions() { 00240 CalledFunctions.clear(); 00241 } 00242 00243 /// addCalledFunction add a function to the list of functions called by this 00244 /// one. 00245 void addCalledFunction(CallGraphNode *M) { 00246 CalledFunctions.push_back(M); 00247 } 00248 00249 /// removeCallEdgeTo - This method removes a *single* edge to the specified 00250 /// callee function. Note that this method takes linear time, so it should be 00251 /// used sparingly. 00252 void removeCallEdgeTo(CallGraphNode *Callee); 00253 00254 /// removeAnyCallEdgeTo - This method removes any call edges from this node to 00255 /// the specified callee function. This takes more time to execute than 00256 /// removeCallEdgeTo, so it should not be used unless necessary. 00257 void removeAnyCallEdgeTo(CallGraphNode *Callee); 00258 00259 private: // Stuff to construct the node, used by CallGraph 00260 friend class CallGraph; 00261 00262 // CallGraphNode ctor - Create a node for the specified function... 00263 inline CallGraphNode(Function *f) : F(f) {} 00264 }; 00265 00266 00267 00268 //===----------------------------------------------------------------------===// 00269 // GraphTraits specializations for call graphs so that they can be treated as 00270 // graphs by the generic graph algorithms... 00271 // 00272 00273 // Provide graph traits for tranversing call graphs using standard graph 00274 // traversals. 00275 template <> struct GraphTraits<CallGraphNode*> { 00276 typedef CallGraphNode NodeType; 00277 typedef NodeType::iterator ChildIteratorType; 00278 00279 static NodeType *getEntryNode(CallGraphNode *CGN) { return CGN; } 00280 static inline ChildIteratorType child_begin(NodeType *N) { return N->begin();} 00281 static inline ChildIteratorType child_end (NodeType *N) { return N->end(); } 00282 }; 00283 00284 template <> struct GraphTraits<const CallGraphNode*> { 00285 typedef const CallGraphNode NodeType; 00286 typedef NodeType::const_iterator ChildIteratorType; 00287 00288 static NodeType *getEntryNode(const CallGraphNode *CGN) { return CGN; } 00289 static inline ChildIteratorType child_begin(NodeType *N) { return N->begin();} 00290 static inline ChildIteratorType child_end (NodeType *N) { return N->end(); } 00291 }; 00292 00293 template<> struct GraphTraits<CallGraph*> : public GraphTraits<CallGraphNode*> { 00294 static NodeType *getEntryNode(CallGraph *CGN) { 00295 return CGN->getExternalCallingNode(); // Start at the external node! 00296 } 00297 typedef std::pair<const Function*, CallGraphNode*> PairTy; 00298 typedef std::pointer_to_unary_function<PairTy, CallGraphNode&> DerefFun; 00299 00300 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph 00301 typedef mapped_iterator<CallGraph::iterator, DerefFun> nodes_iterator; 00302 static nodes_iterator nodes_begin(CallGraph *CG) { 00303 return map_iterator(CG->begin(), DerefFun(CGdereference)); 00304 } 00305 static nodes_iterator nodes_end (CallGraph *CG) { 00306 return map_iterator(CG->end(), DerefFun(CGdereference)); 00307 } 00308 00309 static CallGraphNode &CGdereference (std::pair<const Function*, 00310 CallGraphNode*> P) { 00311 return *P.second; 00312 } 00313 }; 00314 template<> struct GraphTraits<const CallGraph*> : 00315 public GraphTraits<const CallGraphNode*> { 00316 static NodeType *getEntryNode(const CallGraph *CGN) { 00317 return CGN->getExternalCallingNode(); 00318 } 00319 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph 00320 typedef CallGraph::const_iterator nodes_iterator; 00321 static nodes_iterator nodes_begin(const CallGraph *CG) { return CG->begin(); } 00322 static nodes_iterator nodes_end (const CallGraph *CG) { return CG->end(); } 00323 }; 00324 00325 // Make sure that any clients of this file link in PostDominators.cpp 00326 static IncludeFile 00327 CALLGRAPH_INCLUDE_FILE((void*)&CallGraph::stub); 00328 00329 } // End llvm namespace 00330 00331 #endif