CallGraph.h revision c143c7573bfd0d55cf283cc2676dbd852f939c87
1//===- CallGraph.h - Build a Module's call graph ----------------*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// 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 may contain nodes where the function that they correspond to is 18// null. These 'external' nodes are used to represent control flow that is not 19// represented (or analyzable) in the module. In particular, this analysis 20// builds one external node such that: 21// 1. All functions in the module without internal linkage will have edges 22// from this external node, indicating that they could be called by 23// functions outside of the module. 24// 2. All functions whose address is used for something more than a direct 25// call, for example being stored into a memory location will also have an 26// edge from this external node. Since they may be called by an unknown 27// caller later, they must be tracked as such. 28// 29// There is a second external node added for calls that leave this module. 30// Functions have a call edge to the external node iff: 31// 1. The function is external, reflecting the fact that they could call 32// anything without internal linkage or that has its address taken. 33// 2. The function contains an indirect function call. 34// 35// As an extension in the future, there may be multiple nodes with a null 36// function. These will be used when we can prove (through pointer analysis) 37// that an indirect call site can call only a specific set of functions. 38// 39// Because of these properties, the CallGraph captures a conservative superset 40// of all of the caller-callee relationships, which is useful for 41// transformations. 42// 43// The CallGraph class also attempts to figure out what the root of the 44// CallGraph is, which it currently does by looking for a function named 'main'. 45// If no function named 'main' is found, the external node is used as the entry 46// node, reflecting the fact that any function without internal linkage could 47// be called into (which is common for libraries). 48// 49//===----------------------------------------------------------------------===// 50 51#ifndef LLVM_ANALYSIS_CALLGRAPH_H 52#define LLVM_ANALYSIS_CALLGRAPH_H 53 54#include "llvm/ADT/GraphTraits.h" 55#include "llvm/ADT/STLExtras.h" 56#include "llvm/IR/Function.h" 57#include "llvm/Pass.h" 58#include "llvm/Support/CallSite.h" 59#include "llvm/Support/IncludeFile.h" 60#include "llvm/Support/ValueHandle.h" 61#include <map> 62 63namespace llvm { 64 65class Function; 66class Module; 67class CallGraphNode; 68 69//===----------------------------------------------------------------------===// 70// CallGraph class definition 71// 72class CallGraph : public ModulePass { 73 Module *Mod; // The module this call graph represents 74 75 typedef std::map<const Function *, CallGraphNode *> FunctionMapTy; 76 FunctionMapTy FunctionMap; // Map from a function to its node 77 78 // Root is root of the call graph, or the external node if a 'main' function 79 // couldn't be found. 80 // 81 CallGraphNode *Root; 82 83 // ExternalCallingNode - This node has edges to all external functions and 84 // those internal functions that have their address taken. 85 CallGraphNode *ExternalCallingNode; 86 87 // CallsExternalNode - This node has edges to it from all functions making 88 // indirect calls or calling an external function. 89 CallGraphNode *CallsExternalNode; 90 91 /// Replace the function represented by this node by another. 92 /// This does not rescan the body of the function, so it is suitable when 93 /// splicing the body of one function to another while also updating all 94 /// callers from the old function to the new. 95 /// 96 void spliceFunction(const Function *From, const Function *To); 97 98 // Add a function to the call graph, and link the node to all of the functions 99 // that it calls. 100 void addToCallGraph(Function *F); 101 102public: 103 static char ID; // Class identification, replacement for typeinfo 104 //===--------------------------------------------------------------------- 105 // Accessors. 106 // 107 typedef FunctionMapTy::iterator iterator; 108 typedef FunctionMapTy::const_iterator const_iterator; 109 110 /// getModule - Return the module the call graph corresponds to. 111 /// 112 Module &getModule() const { return *Mod; } 113 114 inline iterator begin() { return FunctionMap.begin(); } 115 inline iterator end() { return FunctionMap.end(); } 116 inline const_iterator begin() const { return FunctionMap.begin(); } 117 inline const_iterator end() const { return FunctionMap.end(); } 118 119 // Subscripting operators, return the call graph node for the provided 120 // function 121 inline const CallGraphNode *operator[](const Function *F) const { 122 const_iterator I = FunctionMap.find(F); 123 assert(I != FunctionMap.end() && "Function not in callgraph!"); 124 return I->second; 125 } 126 inline CallGraphNode *operator[](const Function *F) { 127 const_iterator I = FunctionMap.find(F); 128 assert(I != FunctionMap.end() && "Function not in callgraph!"); 129 return I->second; 130 } 131 132 /// Returns the CallGraphNode which is used to represent undetermined calls 133 /// into the callgraph. 134 CallGraphNode *getExternalCallingNode() const { return ExternalCallingNode; } 135 CallGraphNode *getCallsExternalNode() const { return CallsExternalNode; } 136 137 /// Return the root/main method in the module, or some other root node, such 138 /// as the externalcallingnode. 139 CallGraphNode *getRoot() { return Root; } 140 const CallGraphNode *getRoot() const { return Root; } 141 142 //===--------------------------------------------------------------------- 143 // Functions to keep a call graph up to date with a function that has been 144 // modified. 145 // 146 147 /// removeFunctionFromModule - Unlink the function from this module, returning 148 /// it. Because this removes the function from the module, the call graph 149 /// node is destroyed. This is only valid if the function does not call any 150 /// other functions (ie, there are no edges in it's CGN). The easiest way to 151 /// do this is to dropAllReferences before calling this. 152 /// 153 Function *removeFunctionFromModule(CallGraphNode *CGN); 154 155 /// getOrInsertFunction - This method is identical to calling operator[], but 156 /// it will insert a new CallGraphNode for the specified function if one does 157 /// not already exist. 158 CallGraphNode *getOrInsertFunction(const Function *F); 159 160 CallGraph(); 161 virtual ~CallGraph() { releaseMemory(); } 162 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 163 virtual bool runOnModule(Module &M); 164 virtual void releaseMemory(); 165 166 void print(raw_ostream &o, const Module *) const; 167 void dump() const; 168}; 169 170//===----------------------------------------------------------------------===// 171// CallGraphNode class definition. 172// 173class CallGraphNode { 174 friend class CallGraph; 175 176 AssertingVH<Function> F; 177 178 // CallRecord - This is a pair of the calling instruction (a call or invoke) 179 // and the callgraph node being called. 180public: 181 typedef std::pair<WeakVH, CallGraphNode*> CallRecord; 182private: 183 std::vector<CallRecord> CalledFunctions; 184 185 /// NumReferences - This is the number of times that this CallGraphNode occurs 186 /// in the CalledFunctions array of this or other CallGraphNodes. 187 unsigned NumReferences; 188 189 CallGraphNode(const CallGraphNode &) LLVM_DELETED_FUNCTION; 190 void operator=(const CallGraphNode &) LLVM_DELETED_FUNCTION; 191 192 void DropRef() { --NumReferences; } 193 void AddRef() { ++NumReferences; } 194public: 195 typedef std::vector<CallRecord> CalledFunctionsVector; 196 197 198 // CallGraphNode ctor - Create a node for the specified function. 199 inline CallGraphNode(Function *f) : F(f), NumReferences(0) {} 200 ~CallGraphNode() { 201 assert(NumReferences == 0 && "Node deleted while references remain"); 202 } 203 204 //===--------------------------------------------------------------------- 205 // Accessor methods. 206 // 207 208 typedef std::vector<CallRecord>::iterator iterator; 209 typedef std::vector<CallRecord>::const_iterator const_iterator; 210 211 // getFunction - Return the function that this call graph node represents. 212 Function *getFunction() const { return F; } 213 214 inline iterator begin() { return CalledFunctions.begin(); } 215 inline iterator end() { return CalledFunctions.end(); } 216 inline const_iterator begin() const { return CalledFunctions.begin(); } 217 inline const_iterator end() const { return CalledFunctions.end(); } 218 inline bool empty() const { return CalledFunctions.empty(); } 219 inline unsigned size() const { return (unsigned)CalledFunctions.size(); } 220 221 /// getNumReferences - Return the number of other CallGraphNodes in this 222 /// CallGraph that reference this node in their callee list. 223 unsigned getNumReferences() const { return NumReferences; } 224 225 // Subscripting operator - Return the i'th called function. 226 // 227 CallGraphNode *operator[](unsigned i) const { 228 assert(i < CalledFunctions.size() && "Invalid index"); 229 return CalledFunctions[i].second; 230 } 231 232 /// dump - Print out this call graph node. 233 /// 234 void dump() const; 235 void print(raw_ostream &OS) const; 236 237 //===--------------------------------------------------------------------- 238 // Methods to keep a call graph up to date with a function that has been 239 // modified 240 // 241 242 /// removeAllCalledFunctions - As the name implies, this removes all edges 243 /// from this CallGraphNode to any functions it calls. 244 void removeAllCalledFunctions() { 245 while (!CalledFunctions.empty()) { 246 CalledFunctions.back().second->DropRef(); 247 CalledFunctions.pop_back(); 248 } 249 } 250 251 /// stealCalledFunctionsFrom - Move all the callee information from N to this 252 /// node. 253 void stealCalledFunctionsFrom(CallGraphNode *N) { 254 assert(CalledFunctions.empty() && 255 "Cannot steal callsite information if I already have some"); 256 std::swap(CalledFunctions, N->CalledFunctions); 257 } 258 259 260 /// addCalledFunction - Add a function to the list of functions called by this 261 /// one. 262 void addCalledFunction(CallSite CS, CallGraphNode *M) { 263 assert(!CS.getInstruction() || 264 !CS.getCalledFunction() || 265 !CS.getCalledFunction()->isIntrinsic()); 266 CalledFunctions.push_back(std::make_pair(CS.getInstruction(), M)); 267 M->AddRef(); 268 } 269 270 void removeCallEdge(iterator I) { 271 I->second->DropRef(); 272 *I = CalledFunctions.back(); 273 CalledFunctions.pop_back(); 274 } 275 276 277 /// removeCallEdgeFor - This method removes the edge in the node for the 278 /// specified call site. Note that this method takes linear time, so it 279 /// should be used sparingly. 280 void removeCallEdgeFor(CallSite CS); 281 282 /// removeAnyCallEdgeTo - This method removes all call edges from this node 283 /// to the specified callee function. This takes more time to execute than 284 /// removeCallEdgeTo, so it should not be used unless necessary. 285 void removeAnyCallEdgeTo(CallGraphNode *Callee); 286 287 /// removeOneAbstractEdgeTo - Remove one edge associated with a null callsite 288 /// from this node to the specified callee function. 289 void removeOneAbstractEdgeTo(CallGraphNode *Callee); 290 291 /// replaceCallEdge - This method replaces the edge in the node for the 292 /// specified call site with a new one. Note that this method takes linear 293 /// time, so it should be used sparingly. 294 void replaceCallEdge(CallSite CS, CallSite NewCS, CallGraphNode *NewNode); 295 296 /// allReferencesDropped - This is a special function that should only be 297 /// used by the CallGraph class. 298 void allReferencesDropped() { 299 NumReferences = 0; 300 } 301}; 302 303//===----------------------------------------------------------------------===// 304// GraphTraits specializations for call graphs so that they can be treated as 305// graphs by the generic graph algorithms. 306// 307 308// Provide graph traits for tranversing call graphs using standard graph 309// traversals. 310template <> struct GraphTraits<CallGraphNode*> { 311 typedef CallGraphNode NodeType; 312 313 typedef CallGraphNode::CallRecord CGNPairTy; 314 typedef std::pointer_to_unary_function<CGNPairTy, CallGraphNode*> CGNDerefFun; 315 316 static NodeType *getEntryNode(CallGraphNode *CGN) { return CGN; } 317 318 typedef mapped_iterator<NodeType::iterator, CGNDerefFun> ChildIteratorType; 319 320 static inline ChildIteratorType child_begin(NodeType *N) { 321 return map_iterator(N->begin(), CGNDerefFun(CGNDeref)); 322 } 323 static inline ChildIteratorType child_end (NodeType *N) { 324 return map_iterator(N->end(), CGNDerefFun(CGNDeref)); 325 } 326 327 static CallGraphNode *CGNDeref(CGNPairTy P) { 328 return P.second; 329 } 330 331}; 332 333template <> struct GraphTraits<const CallGraphNode*> { 334 typedef const CallGraphNode NodeType; 335 typedef NodeType::const_iterator ChildIteratorType; 336 337 static NodeType *getEntryNode(const CallGraphNode *CGN) { return CGN; } 338 static inline ChildIteratorType child_begin(NodeType *N) { return N->begin();} 339 static inline ChildIteratorType child_end (NodeType *N) { return N->end(); } 340}; 341 342template<> struct GraphTraits<CallGraph*> : public GraphTraits<CallGraphNode*> { 343 static NodeType *getEntryNode(CallGraph *CGN) { 344 return CGN->getExternalCallingNode(); // Start at the external node! 345 } 346 typedef std::pair<const Function*, CallGraphNode*> PairTy; 347 typedef std::pointer_to_unary_function<PairTy, CallGraphNode&> DerefFun; 348 349 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph 350 typedef mapped_iterator<CallGraph::iterator, DerefFun> nodes_iterator; 351 static nodes_iterator nodes_begin(CallGraph *CG) { 352 return map_iterator(CG->begin(), DerefFun(CGdereference)); 353 } 354 static nodes_iterator nodes_end (CallGraph *CG) { 355 return map_iterator(CG->end(), DerefFun(CGdereference)); 356 } 357 358 static CallGraphNode &CGdereference(PairTy P) { 359 return *P.second; 360 } 361}; 362 363template<> struct GraphTraits<const CallGraph*> : 364 public GraphTraits<const CallGraphNode*> { 365 static NodeType *getEntryNode(const CallGraph *CGN) { 366 return CGN->getExternalCallingNode(); 367 } 368 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph 369 typedef CallGraph::const_iterator nodes_iterator; 370 static nodes_iterator nodes_begin(const CallGraph *CG) { return CG->begin(); } 371 static nodes_iterator nodes_end (const CallGraph *CG) { return CG->end(); } 372}; 373 374} // End llvm namespace 375 376// Make sure that any clients of this file link in CallGraph.cpp 377FORCE_DEFINING_FILE_TO_BE_LINKED(CallGraph) 378 379#endif 380