CallGraph.h revision 36b56886974eae4f9c5ebc96befd3e7bfe5de338
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/// \file 10/// 11/// This file provides interfaces used to build and manipulate a call graph, 12/// which is a very useful tool for interprocedural optimization. 13/// 14/// Every function in a module is represented as a node in the call graph. The 15/// callgraph node keeps track of which functions are called by the function 16/// corresponding to the node. 17/// 18/// A call graph may contain nodes where the function that they correspond to 19/// is null. These 'external' nodes are used to represent control flow that is 20/// not represented (or analyzable) in the module. In particular, this 21/// analysis builds one external node such that: 22/// 1. All functions in the module without internal linkage will have edges 23/// from this external node, indicating that they could be called by 24/// functions outside of the module. 25/// 2. All functions whose address is used for something more than a direct 26/// call, for example being stored into a memory location will also have 27/// an edge from this external node. Since they may be called by an 28/// unknown caller later, they must be tracked as such. 29/// 30/// There is a second external node added for calls that leave this module. 31/// Functions have a call edge to the external node iff: 32/// 1. The function is external, reflecting the fact that they could call 33/// anything without internal linkage or that has its address taken. 34/// 2. The function contains an indirect function call. 35/// 36/// As an extension in the future, there may be multiple nodes with a null 37/// function. These will be used when we can prove (through pointer analysis) 38/// that an indirect call site can call only a specific set of functions. 39/// 40/// Because of these properties, the CallGraph captures a conservative superset 41/// of all of the caller-callee relationships, which is useful for 42/// transformations. 43/// 44/// The CallGraph class also attempts to figure out what the root of the 45/// CallGraph is, which it currently does by looking for a function named 46/// 'main'. If no function named 'main' is found, the external node is used as 47/// the entry node, reflecting the fact that any function without internal 48/// linkage could be called into (which is common for libraries). 49/// 50//===----------------------------------------------------------------------===// 51 52#ifndef LLVM_ANALYSIS_CALLGRAPH_H 53#define LLVM_ANALYSIS_CALLGRAPH_H 54 55#include "llvm/ADT/GraphTraits.h" 56#include "llvm/ADT/STLExtras.h" 57#include "llvm/IR/CallSite.h" 58#include "llvm/IR/Function.h" 59#include "llvm/IR/ValueHandle.h" 60#include "llvm/Pass.h" 61#include "llvm/Support/IncludeFile.h" 62#include <map> 63 64namespace llvm { 65 66class Function; 67class Module; 68class CallGraphNode; 69 70/// \brief The basic data container for the call graph of a \c Module of IR. 71/// 72/// This class exposes both the interface to the call graph for a module of IR. 73/// 74/// The core call graph itself can also be updated to reflect changes to the IR. 75class CallGraph { 76 Module &M; 77 78 typedef std::map<const Function *, CallGraphNode *> FunctionMapTy; 79 80 /// \brief A map from \c Function* to \c CallGraphNode*. 81 FunctionMapTy FunctionMap; 82 83 /// \brief Root is root of the call graph, or the external node if a 'main' 84 /// function couldn't be found. 85 CallGraphNode *Root; 86 87 /// \brief This node has edges to all external functions and those internal 88 /// functions that have their address taken. 89 CallGraphNode *ExternalCallingNode; 90 91 /// \brief This node has edges to it from all functions making indirect calls 92 /// or calling an external function. 93 CallGraphNode *CallsExternalNode; 94 95 /// \brief Replace the function represented by this node by another. 96 /// 97 /// This does not rescan the body of the function, so it is suitable when 98 /// splicing the body of one function to another while also updating all 99 /// callers from the old function to the new. 100 void spliceFunction(const Function *From, const Function *To); 101 102 /// \brief Add a function to the call graph, and link the node to all of the 103 /// functions that it calls. 104 void addToCallGraph(Function *F); 105 106public: 107 CallGraph(Module &M); 108 ~CallGraph(); 109 110 void print(raw_ostream &OS) const; 111 void dump() const; 112 113 typedef FunctionMapTy::iterator iterator; 114 typedef FunctionMapTy::const_iterator const_iterator; 115 116 /// \brief Returns the module the call graph corresponds to. 117 Module &getModule() const { return M; } 118 119 inline iterator begin() { return FunctionMap.begin(); } 120 inline iterator end() { return FunctionMap.end(); } 121 inline const_iterator begin() const { return FunctionMap.begin(); } 122 inline const_iterator end() const { return FunctionMap.end(); } 123 124 /// \brief Returns the call graph node for the provided function. 125 inline const CallGraphNode *operator[](const Function *F) const { 126 const_iterator I = FunctionMap.find(F); 127 assert(I != FunctionMap.end() && "Function not in callgraph!"); 128 return I->second; 129 } 130 131 /// \brief Returns the call graph node for the provided function. 132 inline CallGraphNode *operator[](const Function *F) { 133 const_iterator I = FunctionMap.find(F); 134 assert(I != FunctionMap.end() && "Function not in callgraph!"); 135 return I->second; 136 } 137 138 /// \brief Returns the \c CallGraphNode which is used to represent 139 /// undetermined calls into the callgraph. 140 CallGraphNode *getExternalCallingNode() const { return ExternalCallingNode; } 141 142 CallGraphNode *getCallsExternalNode() const { return CallsExternalNode; } 143 144 //===--------------------------------------------------------------------- 145 // Functions to keep a call graph up to date with a function that has been 146 // modified. 147 // 148 149 /// \brief Unlink the function from this module, returning it. 150 /// 151 /// Because this removes the function from the module, the call graph node is 152 /// destroyed. This is only valid if the function does not call any other 153 /// functions (ie, there are no edges in it's CGN). The easiest way to do 154 /// this is to dropAllReferences before calling this. 155 Function *removeFunctionFromModule(CallGraphNode *CGN); 156 157 /// \brief Similar to operator[], but this will insert a new CallGraphNode for 158 /// \c F if one does not already exist. 159 CallGraphNode *getOrInsertFunction(const Function *F); 160}; 161 162/// \brief A node in the call graph for a module. 163/// 164/// Typically represents a function in the call graph. There are also special 165/// "null" nodes used to represent theoretical entries in the call graph. 166class CallGraphNode { 167public: 168 /// \brief A pair of the calling instruction (a call or invoke) 169 /// and the call graph node being called. 170 typedef std::pair<WeakVH, CallGraphNode *> CallRecord; 171 172public: 173 typedef std::vector<CallRecord> CalledFunctionsVector; 174 175 /// \brief Creates a node for the specified function. 176 inline CallGraphNode(Function *F) : F(F), NumReferences(0) {} 177 178 ~CallGraphNode() { 179 assert(NumReferences == 0 && "Node deleted while references remain"); 180 } 181 182 typedef std::vector<CallRecord>::iterator iterator; 183 typedef std::vector<CallRecord>::const_iterator const_iterator; 184 185 /// \brief Returns the function that this call graph node represents. 186 Function *getFunction() const { return F; } 187 188 inline iterator begin() { return CalledFunctions.begin(); } 189 inline iterator end() { return CalledFunctions.end(); } 190 inline const_iterator begin() const { return CalledFunctions.begin(); } 191 inline const_iterator end() const { return CalledFunctions.end(); } 192 inline bool empty() const { return CalledFunctions.empty(); } 193 inline unsigned size() const { return (unsigned)CalledFunctions.size(); } 194 195 /// \brief Returns the number of other CallGraphNodes in this CallGraph that 196 /// reference this node in their callee list. 197 unsigned getNumReferences() const { return NumReferences; } 198 199 /// \brief Returns the i'th called function. 200 CallGraphNode *operator[](unsigned i) const { 201 assert(i < CalledFunctions.size() && "Invalid index"); 202 return CalledFunctions[i].second; 203 } 204 205 /// \brief Print out this call graph node. 206 void dump() const; 207 void print(raw_ostream &OS) const; 208 209 //===--------------------------------------------------------------------- 210 // Methods to keep a call graph up to date with a function that has been 211 // modified 212 // 213 214 /// \brief Removes all edges from this CallGraphNode to any functions it 215 /// calls. 216 void removeAllCalledFunctions() { 217 while (!CalledFunctions.empty()) { 218 CalledFunctions.back().second->DropRef(); 219 CalledFunctions.pop_back(); 220 } 221 } 222 223 /// \brief Moves all the callee information from N to this node. 224 void stealCalledFunctionsFrom(CallGraphNode *N) { 225 assert(CalledFunctions.empty() && 226 "Cannot steal callsite information if I already have some"); 227 std::swap(CalledFunctions, N->CalledFunctions); 228 } 229 230 /// \brief Adds a function to the list of functions called by this one. 231 void addCalledFunction(CallSite CS, CallGraphNode *M) { 232 assert(!CS.getInstruction() || !CS.getCalledFunction() || 233 !CS.getCalledFunction()->isIntrinsic()); 234 CalledFunctions.push_back(std::make_pair(CS.getInstruction(), M)); 235 M->AddRef(); 236 } 237 238 void removeCallEdge(iterator I) { 239 I->second->DropRef(); 240 *I = CalledFunctions.back(); 241 CalledFunctions.pop_back(); 242 } 243 244 /// \brief Removes the edge in the node for the specified call site. 245 /// 246 /// Note that this method takes linear time, so it should be used sparingly. 247 void removeCallEdgeFor(CallSite CS); 248 249 /// \brief Removes all call edges from this node to the specified callee 250 /// function. 251 /// 252 /// This takes more time to execute than removeCallEdgeTo, so it should not 253 /// be used unless necessary. 254 void removeAnyCallEdgeTo(CallGraphNode *Callee); 255 256 /// \brief Removes one edge associated with a null callsite from this node to 257 /// the specified callee function. 258 void removeOneAbstractEdgeTo(CallGraphNode *Callee); 259 260 /// \brief Replaces the edge in the node for the specified call site with a 261 /// new one. 262 /// 263 /// Note that this method takes linear time, so it should be used sparingly. 264 void replaceCallEdge(CallSite CS, CallSite NewCS, CallGraphNode *NewNode); 265 266private: 267 friend class CallGraph; 268 269 AssertingVH<Function> F; 270 271 std::vector<CallRecord> CalledFunctions; 272 273 /// \brief The number of times that this CallGraphNode occurs in the 274 /// CalledFunctions array of this or other CallGraphNodes. 275 unsigned NumReferences; 276 277 CallGraphNode(const CallGraphNode &) LLVM_DELETED_FUNCTION; 278 void operator=(const CallGraphNode &) LLVM_DELETED_FUNCTION; 279 280 void DropRef() { --NumReferences; } 281 void AddRef() { ++NumReferences; } 282 283 /// \brief A special function that should only be used by the CallGraph class. 284 void allReferencesDropped() { NumReferences = 0; } 285}; 286 287/// \brief An analysis pass to compute the \c CallGraph for a \c Module. 288/// 289/// This class implements the concept of an analysis pass used by the \c 290/// ModuleAnalysisManager to run an analysis over a module and cache the 291/// resulting data. 292class CallGraphAnalysis { 293public: 294 /// \brief A formulaic typedef to inform clients of the result type. 295 typedef CallGraph Result; 296 297 static void *ID() { return (void *)&PassID; } 298 299 /// \brief Compute the \c CallGraph for the module \c M. 300 /// 301 /// The real work here is done in the \c CallGraph constructor. 302 CallGraph run(Module *M) { return CallGraph(*M); } 303 304private: 305 static char PassID; 306}; 307 308/// \brief The \c ModulePass which wraps up a \c CallGraph and the logic to 309/// build it. 310/// 311/// This class exposes both the interface to the call graph container and the 312/// module pass which runs over a module of IR and produces the call graph. The 313/// call graph interface is entirelly a wrapper around a \c CallGraph object 314/// which is stored internally for each module. 315class CallGraphWrapperPass : public ModulePass { 316 std::unique_ptr<CallGraph> G; 317 318public: 319 static char ID; // Class identification, replacement for typeinfo 320 321 CallGraphWrapperPass(); 322 virtual ~CallGraphWrapperPass(); 323 324 /// \brief The internal \c CallGraph around which the rest of this interface 325 /// is wrapped. 326 const CallGraph &getCallGraph() const { return *G; } 327 CallGraph &getCallGraph() { return *G; } 328 329 typedef CallGraph::iterator iterator; 330 typedef CallGraph::const_iterator const_iterator; 331 332 /// \brief Returns the module the call graph corresponds to. 333 Module &getModule() const { return G->getModule(); } 334 335 inline iterator begin() { return G->begin(); } 336 inline iterator end() { return G->end(); } 337 inline const_iterator begin() const { return G->begin(); } 338 inline const_iterator end() const { return G->end(); } 339 340 /// \brief Returns the call graph node for the provided function. 341 inline const CallGraphNode *operator[](const Function *F) const { 342 return (*G)[F]; 343 } 344 345 /// \brief Returns the call graph node for the provided function. 346 inline CallGraphNode *operator[](const Function *F) { return (*G)[F]; } 347 348 /// \brief Returns the \c CallGraphNode which is used to represent 349 /// undetermined calls into the callgraph. 350 CallGraphNode *getExternalCallingNode() const { 351 return G->getExternalCallingNode(); 352 } 353 354 CallGraphNode *getCallsExternalNode() const { 355 return G->getCallsExternalNode(); 356 } 357 358 //===--------------------------------------------------------------------- 359 // Functions to keep a call graph up to date with a function that has been 360 // modified. 361 // 362 363 /// \brief Unlink the function from this module, returning it. 364 /// 365 /// Because this removes the function from the module, the call graph node is 366 /// destroyed. This is only valid if the function does not call any other 367 /// functions (ie, there are no edges in it's CGN). The easiest way to do 368 /// this is to dropAllReferences before calling this. 369 Function *removeFunctionFromModule(CallGraphNode *CGN) { 370 return G->removeFunctionFromModule(CGN); 371 } 372 373 /// \brief Similar to operator[], but this will insert a new CallGraphNode for 374 /// \c F if one does not already exist. 375 CallGraphNode *getOrInsertFunction(const Function *F) { 376 return G->getOrInsertFunction(F); 377 } 378 379 //===--------------------------------------------------------------------- 380 // Implementation of the ModulePass interface needed here. 381 // 382 383 void getAnalysisUsage(AnalysisUsage &AU) const override; 384 bool runOnModule(Module &M) override; 385 void releaseMemory() override; 386 387 void print(raw_ostream &o, const Module *) const override; 388 void dump() const; 389}; 390 391//===----------------------------------------------------------------------===// 392// GraphTraits specializations for call graphs so that they can be treated as 393// graphs by the generic graph algorithms. 394// 395 396// Provide graph traits for tranversing call graphs using standard graph 397// traversals. 398template <> struct GraphTraits<CallGraphNode *> { 399 typedef CallGraphNode NodeType; 400 401 typedef CallGraphNode::CallRecord CGNPairTy; 402 typedef std::pointer_to_unary_function<CGNPairTy, CallGraphNode *> 403 CGNDerefFun; 404 405 static NodeType *getEntryNode(CallGraphNode *CGN) { return CGN; } 406 407 typedef mapped_iterator<NodeType::iterator, CGNDerefFun> ChildIteratorType; 408 409 static inline ChildIteratorType child_begin(NodeType *N) { 410 return map_iterator(N->begin(), CGNDerefFun(CGNDeref)); 411 } 412 static inline ChildIteratorType child_end(NodeType *N) { 413 return map_iterator(N->end(), CGNDerefFun(CGNDeref)); 414 } 415 416 static CallGraphNode *CGNDeref(CGNPairTy P) { return P.second; } 417}; 418 419template <> struct GraphTraits<const CallGraphNode *> { 420 typedef const CallGraphNode NodeType; 421 typedef NodeType::const_iterator ChildIteratorType; 422 423 static NodeType *getEntryNode(const CallGraphNode *CGN) { return CGN; } 424 static inline ChildIteratorType child_begin(NodeType *N) { 425 return N->begin(); 426 } 427 static inline ChildIteratorType child_end(NodeType *N) { return N->end(); } 428}; 429 430template <> 431struct GraphTraits<CallGraph *> : public GraphTraits<CallGraphNode *> { 432 static NodeType *getEntryNode(CallGraph *CGN) { 433 return CGN->getExternalCallingNode(); // Start at the external node! 434 } 435 typedef std::pair<const Function *, CallGraphNode *> PairTy; 436 typedef std::pointer_to_unary_function<PairTy, CallGraphNode &> DerefFun; 437 438 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph 439 typedef mapped_iterator<CallGraph::iterator, DerefFun> nodes_iterator; 440 static nodes_iterator nodes_begin(CallGraph *CG) { 441 return map_iterator(CG->begin(), DerefFun(CGdereference)); 442 } 443 static nodes_iterator nodes_end(CallGraph *CG) { 444 return map_iterator(CG->end(), DerefFun(CGdereference)); 445 } 446 447 static CallGraphNode &CGdereference(PairTy P) { return *P.second; } 448}; 449 450template <> 451struct GraphTraits<const CallGraph *> : public GraphTraits< 452 const CallGraphNode *> { 453 static NodeType *getEntryNode(const CallGraph *CGN) { 454 return CGN->getExternalCallingNode(); 455 } 456 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph 457 typedef CallGraph::const_iterator nodes_iterator; 458 static nodes_iterator nodes_begin(const CallGraph *CG) { return CG->begin(); } 459 static nodes_iterator nodes_end(const CallGraph *CG) { return CG->end(); } 460}; 461 462} // End llvm namespace 463 464// Make sure that any clients of this file link in CallGraph.cpp 465FORCE_DEFINING_FILE_TO_BE_LINKED(CallGraph) 466 467#endif 468