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 { 00068 protected: 00069 Module *Mod; // The module this call graph represents 00070 00071 typedef std::map<const Function *, CallGraphNode *> FunctionMapTy; 00072 FunctionMapTy FunctionMap; // Map from a function to its node 00073 00074 public: 00075 //===--------------------------------------------------------------------- 00076 // Accessors... 00077 // 00078 typedef FunctionMapTy::iterator iterator; 00079 typedef FunctionMapTy::const_iterator const_iterator; 00080 00081 /// getModule - Return the module the call graph corresponds to. 00082 /// 00083 Module &getModule() const { return *Mod; } 00084 00085 inline iterator begin() { return FunctionMap.begin(); } 00086 inline iterator end() { return FunctionMap.end(); } 00087 inline const_iterator begin() const { return FunctionMap.begin(); } 00088 inline const_iterator end() const { return FunctionMap.end(); } 00089 00090 // Subscripting operators, return the call graph node for the provided 00091 // function 00092 inline const CallGraphNode *operator[](const Function *F) const { 00093 const_iterator I = FunctionMap.find(F); 00094 assert(I != FunctionMap.end() && "Function not in callgraph!"); 00095 return I->second; 00096 } 00097 inline CallGraphNode *operator[](const Function *F) { 00098 const_iterator I = FunctionMap.find(F); 00099 assert(I != FunctionMap.end() && "Function not in callgraph!"); 00100 return I->second; 00101 } 00102 00103 //Returns the CallGraphNode which is used to represent undetermined calls 00104 // into the callgraph. Override this if you want behavioural inheritance. 00105 virtual CallGraphNode* getExternalCallingNode() const { return 0; } 00106 00107 //Return the root/main method in the module, or some other root node, such 00108 // as the externalcallingnode. Overload these if you behavioural 00109 // inheritance. 00110 virtual CallGraphNode* getRoot() { return 0; } 00111 virtual const CallGraphNode* getRoot() const { return 0; } 00112 00113 //===--------------------------------------------------------------------- 00114 // Functions to keep a call graph up to date with a function that has been 00115 // modified. 00116 // 00117 00118 /// removeFunctionFromModule - Unlink the function from this module, returning 00119 /// it. Because this removes the function from the module, the call graph 00120 /// node is destroyed. This is only valid if the function does not call any 00121 /// other functions (ie, there are no edges in it's CGN). The easiest way to 00122 /// do this is to dropAllReferences before calling this. 00123 /// 00124 Function *removeFunctionFromModule(CallGraphNode *CGN); 00125 Function *removeFunctionFromModule(Function *F) { 00126 return removeFunctionFromModule((*this)[F]); 00127 } 00128 00129 /// changeFunction - This method changes the function associated with this 00130 /// CallGraphNode, for use by transformations that need to change the 00131 /// prototype of a Function (thus they must create a new Function and move the 00132 /// old code over). 00133 void changeFunction(Function *OldF, Function *NewF); 00134 00135 /// getOrInsertFunction - This method is identical to calling operator[], but 00136 /// it will insert a new CallGraphNode for the specified function if one does 00137 /// not already exist. 00138 CallGraphNode *getOrInsertFunction(const Function *F); 00139 00140 //===--------------------------------------------------------------------- 00141 // Pass infrastructure interface glue code... 00142 // 00143 protected: 00144 CallGraph() {} 00145 00146 public: 00147 virtual ~CallGraph() { destroy(); } 00148 00149 /// initialize - Call this method before calling other methods, 00150 /// re/initializes the state of the CallGraph. 00151 /// 00152 void initialize(Module &M); 00153 00154 virtual void print(std::ostream &o, const Module *M) const; 00155 void dump() const; 00156 00157 // stub - dummy function, just ignore it 00158 static void stub(); 00159 protected: 00160 00161 // destroy - Release memory for the call graph 00162 virtual void destroy(); 00163 }; 00164 00165 //===----------------------------------------------------------------------===// 00166 // CallGraphNode class definition 00167 // 00168 class CallGraphNode { 00169 Function *F; 00170 std::vector<CallGraphNode*> CalledFunctions; 00171 00172 CallGraphNode(const CallGraphNode &); // Do not implement 00173 public: 00174 //===--------------------------------------------------------------------- 00175 // Accessor methods... 00176 // 00177 00178 typedef std::vector<CallGraphNode*>::iterator iterator; 00179 typedef std::vector<CallGraphNode*>::const_iterator const_iterator; 00180 00181 // getFunction - Return the function that this call graph node represents... 00182 Function *getFunction() const { return F; } 00183 00184 inline iterator begin() { return CalledFunctions.begin(); } 00185 inline iterator end() { return CalledFunctions.end(); } 00186 inline const_iterator begin() const { return CalledFunctions.begin(); } 00187 inline const_iterator end() const { return CalledFunctions.end(); } 00188 inline unsigned size() const { return CalledFunctions.size(); } 00189 00190 // Subscripting operator - Return the i'th called function... 00191 // 00192 CallGraphNode *operator[](unsigned i) const { return CalledFunctions[i];} 00193 00194 /// dump - Print out this call graph node. 00195 /// 00196 void dump() const; 00197 void print(std::ostream &OS) const; 00198 00199 //===--------------------------------------------------------------------- 00200 // Methods to keep a call graph up to date with a function that has been 00201 // modified 00202 // 00203 00204 /// removeAllCalledFunctions - As the name implies, this removes all edges 00205 /// from this CallGraphNode to any functions it calls. 00206 void removeAllCalledFunctions() { 00207 CalledFunctions.clear(); 00208 } 00209 00210 /// addCalledFunction add a function to the list of functions called by this 00211 /// one. 00212 void addCalledFunction(CallGraphNode *M) { 00213 CalledFunctions.push_back(M); 00214 } 00215 00216 /// removeCallEdgeTo - This method removes a *single* edge to the specified 00217 /// callee function. Note that this method takes linear time, so it should be 00218 /// used sparingly. 00219 void removeCallEdgeTo(CallGraphNode *Callee); 00220 00221 /// removeAnyCallEdgeTo - This method removes any call edges from this node to 00222 /// the specified callee function. This takes more time to execute than 00223 /// removeCallEdgeTo, so it should not be used unless necessary. 00224 void removeAnyCallEdgeTo(CallGraphNode *Callee); 00225 00226 friend class CallGraph; 00227 00228 // CallGraphNode ctor - Create a node for the specified function... 00229 inline CallGraphNode(Function *f) : F(f) {} 00230 }; 00231 00232 //===----------------------------------------------------------------------===// 00233 // GraphTraits specializations for call graphs so that they can be treated as 00234 // graphs by the generic graph algorithms... 00235 // 00236 00237 // Provide graph traits for tranversing call graphs using standard graph 00238 // traversals. 00239 template <> struct GraphTraits<CallGraphNode*> { 00240 typedef CallGraphNode NodeType; 00241 typedef NodeType::iterator ChildIteratorType; 00242 00243 static NodeType *getEntryNode(CallGraphNode *CGN) { return CGN; } 00244 static inline ChildIteratorType child_begin(NodeType *N) { return N->begin();} 00245 static inline ChildIteratorType child_end (NodeType *N) { return N->end(); } 00246 }; 00247 00248 template <> struct GraphTraits<const CallGraphNode*> { 00249 typedef const CallGraphNode NodeType; 00250 typedef NodeType::const_iterator ChildIteratorType; 00251 00252 static NodeType *getEntryNode(const CallGraphNode *CGN) { return CGN; } 00253 static inline ChildIteratorType child_begin(NodeType *N) { return N->begin();} 00254 static inline ChildIteratorType child_end (NodeType *N) { return N->end(); } 00255 }; 00256 00257 template<> struct GraphTraits<CallGraph*> : public GraphTraits<CallGraphNode*> { 00258 static NodeType *getEntryNode(CallGraph *CGN) { 00259 return CGN->getExternalCallingNode(); // Start at the external node! 00260 } 00261 typedef std::pair<const Function*, CallGraphNode*> PairTy; 00262 typedef std::pointer_to_unary_function<PairTy, CallGraphNode&> DerefFun; 00263 00264 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph 00265 typedef mapped_iterator<CallGraph::iterator, DerefFun> nodes_iterator; 00266 static nodes_iterator nodes_begin(CallGraph *CG) { 00267 return map_iterator(CG->begin(), DerefFun(CGdereference)); 00268 } 00269 static nodes_iterator nodes_end (CallGraph *CG) { 00270 return map_iterator(CG->end(), DerefFun(CGdereference)); 00271 } 00272 00273 static CallGraphNode &CGdereference (std::pair<const Function*, 00274 CallGraphNode*> P) { 00275 return *P.second; 00276 } 00277 }; 00278 00279 template<> struct GraphTraits<const CallGraph*> : 00280 public GraphTraits<const CallGraphNode*> { 00281 static NodeType *getEntryNode(const CallGraph *CGN) { 00282 return CGN->getExternalCallingNode(); 00283 } 00284 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph 00285 typedef CallGraph::const_iterator nodes_iterator; 00286 static nodes_iterator nodes_begin(const CallGraph *CG) { return CG->begin(); } 00287 static nodes_iterator nodes_end (const CallGraph *CG) { return CG->end(); } 00288 }; 00289 00290 // Make sure that any clients of this file link in CallGraph.cpp 00291 static IncludeFile 00292 CALLGRAPH_INCLUDE_FILE((void*)&CallGraph::stub); 00293 00294 extern void BasicCallGraphStub(); 00295 static IncludeFile HDR_INCLUDE_CALLGRAPH_CPP((void*)&BasicCallGraphStub); 00296 00297 } // End llvm namespace 00298 00299 #endif