CallGraph.h revision e669d83a21d7ebf01d3c9e37a20c7348b5a77c11
183165a5f71319b04beb561afb7c968493027bcbdreed@google.com//===- CallGraph.h - Build a Module's call graph ----------------*- C++ -*-===// 283165a5f71319b04beb561afb7c968493027bcbdreed@google.com// 383165a5f71319b04beb561afb7c968493027bcbdreed@google.com// The LLVM Compiler Infrastructure 483165a5f71319b04beb561afb7c968493027bcbdreed@google.com// 583165a5f71319b04beb561afb7c968493027bcbdreed@google.com// This file is distributed under the University of Illinois Open Source 683165a5f71319b04beb561afb7c968493027bcbdreed@google.com// License. See LICENSE.TXT for details. 783165a5f71319b04beb561afb7c968493027bcbdreed@google.com// 883165a5f71319b04beb561afb7c968493027bcbdreed@google.com//===----------------------------------------------------------------------===// 983165a5f71319b04beb561afb7c968493027bcbdreed@google.com// 1083165a5f71319b04beb561afb7c968493027bcbdreed@google.com// This interface is used to build and manipulate a call graph, which is a very 118f6884aab8aecd7657cf3f9cdbc682f0deca29c5tfarina@chromium.org// useful tool for interprocedural optimization. 1283165a5f71319b04beb561afb7c968493027bcbdreed@google.com// 1343c27586e8b02243c16649de1cd7d95dcea0a712reed@google.com// Every function in a module is represented as a node in the call graph. The 1443c27586e8b02243c16649de1cd7d95dcea0a712reed@google.com// callgraph node keeps track of which functions the are called by the function 1543c27586e8b02243c16649de1cd7d95dcea0a712reed@google.com// corresponding to the node. 1643c27586e8b02243c16649de1cd7d95dcea0a712reed@google.com// 1743c27586e8b02243c16649de1cd7d95dcea0a712reed@google.com// A call graph may contain nodes where the function that they correspond to is 18e1d94437585dad1c195d7cf095f8a5a8219d196askia.committer@gmail.com// null. These 'external' nodes are used to represent control flow that is not 1949f085dddff10473b6ebf832a974288300224e60bsalomon// represented (or analyzable) in the module. In particular, this analysis 2043c27586e8b02243c16649de1cd7d95dcea0a712reed@google.com// builds one external node such that: 2143c27586e8b02243c16649de1cd7d95dcea0a712reed@google.com// 1. All functions in the module without internal linkage will have edges 2243c27586e8b02243c16649de1cd7d95dcea0a712reed@google.com// from this external node, indicating that they could be called by 2343c27586e8b02243c16649de1cd7d95dcea0a712reed@google.com// functions outside of the module. 2443c27586e8b02243c16649de1cd7d95dcea0a712reed@google.com// 2. All functions whose address is used for something more than a direct 2543c27586e8b02243c16649de1cd7d95dcea0a712reed@google.com// call, for example being stored into a memory location will also have an 2643c27586e8b02243c16649de1cd7d95dcea0a712reed@google.com// edge from this external node. Since they may be called by an unknown 2743c27586e8b02243c16649de1cd7d95dcea0a712reed@google.com// caller later, they must be tracked as such. 2843c27586e8b02243c16649de1cd7d95dcea0a712reed@google.com// 2943c27586e8b02243c16649de1cd7d95dcea0a712reed@google.com// There is a second external node added for calls that leave this module. 3043c27586e8b02243c16649de1cd7d95dcea0a712reed@google.com// Functions have a call edge to the external node iff: 3143c27586e8b02243c16649de1cd7d95dcea0a712reed@google.com// 1. The function is external, reflecting the fact that they could call 3243c27586e8b02243c16649de1cd7d95dcea0a712reed@google.com// anything without internal linkage or that has its address taken. 3343c27586e8b02243c16649de1cd7d95dcea0a712reed@google.com// 2. The function contains an indirect function call. 3443c27586e8b02243c16649de1cd7d95dcea0a712reed@google.com// 3543c27586e8b02243c16649de1cd7d95dcea0a712reed@google.com// As an extension in the future, there may be multiple nodes with a null 36e1d94437585dad1c195d7cf095f8a5a8219d196askia.committer@gmail.com// function. These will be used when we can prove (through pointer analysis) 3743c27586e8b02243c16649de1cd7d95dcea0a712reed@google.com// that an indirect call site can call only a specific set of functions. 3843c27586e8b02243c16649de1cd7d95dcea0a712reed@google.com// 3943c27586e8b02243c16649de1cd7d95dcea0a712reed@google.com// Because of these properties, the CallGraph captures a conservative superset 4043c27586e8b02243c16649de1cd7d95dcea0a712reed@google.com// of all of the caller-callee relationships, which is useful for 4143c27586e8b02243c16649de1cd7d95dcea0a712reed@google.com// transformations. 4243c27586e8b02243c16649de1cd7d95dcea0a712reed@google.com// 4343c27586e8b02243c16649de1cd7d95dcea0a712reed@google.com// The CallGraph class also attempts to figure out what the root of the 4443c27586e8b02243c16649de1cd7d95dcea0a712reed@google.com// CallGraph is, which it currently does by looking for a function named 'main'. 4543c27586e8b02243c16649de1cd7d95dcea0a712reed@google.com// If no function named 'main' is found, the external node is used as the entry 4643c27586e8b02243c16649de1cd7d95dcea0a712reed@google.com// node, reflecting the fact that any function without internal linkage could 4743c27586e8b02243c16649de1cd7d95dcea0a712reed@google.com// be called into (which is common for libraries). 4843c27586e8b02243c16649de1cd7d95dcea0a712reed@google.com// 4943c27586e8b02243c16649de1cd7d95dcea0a712reed@google.com//===----------------------------------------------------------------------===// 5043c27586e8b02243c16649de1cd7d95dcea0a712reed@google.com 51d44d988127841cf9180bb7ba91b6eba8127af467reed@google.com#ifndef LLVM_ANALYSIS_CALLGRAPH_H 52d44d988127841cf9180bb7ba91b6eba8127af467reed@google.com#define LLVM_ANALYSIS_CALLGRAPH_H 53d44d988127841cf9180bb7ba91b6eba8127af467reed@google.com 54d44d988127841cf9180bb7ba91b6eba8127af467reed@google.com#include "llvm/Function.h" 55d44d988127841cf9180bb7ba91b6eba8127af467reed@google.com#include "llvm/Pass.h" 56c1a81ebec52bc5dff8c9461570e1212afe09506freed@google.com#include "llvm/ADT/GraphTraits.h" 57c1a81ebec52bc5dff8c9461570e1212afe09506freed@google.com#include "llvm/ADT/STLExtras.h" 58c1a81ebec52bc5dff8c9461570e1212afe09506freed@google.com#include "llvm/Support/CallSite.h" 59c1a81ebec52bc5dff8c9461570e1212afe09506freed@google.com#include "llvm/Support/ValueHandle.h" 60f91e3d4f54de9976b6538decadd977b19e49eaddskia.committer@gmail.com#include "llvm/Support/IncludeFile.h" 61c1a81ebec52bc5dff8c9461570e1212afe09506freed@google.com#include <map> 62c1a81ebec52bc5dff8c9461570e1212afe09506freed@google.com 63c1a81ebec52bc5dff8c9461570e1212afe09506freed@google.comnamespace llvm { 64c1a81ebec52bc5dff8c9461570e1212afe09506freed@google.com 65c1a81ebec52bc5dff8c9461570e1212afe09506freed@google.comclass Function; 66c1a81ebec52bc5dff8c9461570e1212afe09506freed@google.comclass Module; 67c1a81ebec52bc5dff8c9461570e1212afe09506freed@google.comclass CallGraphNode; 68c1a81ebec52bc5dff8c9461570e1212afe09506freed@google.com 69c1a81ebec52bc5dff8c9461570e1212afe09506freed@google.com//===----------------------------------------------------------------------===// 70c1a81ebec52bc5dff8c9461570e1212afe09506freed@google.com// CallGraph class definition 71c1a81ebec52bc5dff8c9461570e1212afe09506freed@google.com// 72c1a81ebec52bc5dff8c9461570e1212afe09506freed@google.comclass CallGraph { 73c1a81ebec52bc5dff8c9461570e1212afe09506freed@google.comprotected: 74c1a81ebec52bc5dff8c9461570e1212afe09506freed@google.com Module *Mod; // The module this call graph represents 75c1a81ebec52bc5dff8c9461570e1212afe09506freed@google.com 76c1a81ebec52bc5dff8c9461570e1212afe09506freed@google.com typedef std::map<const Function *, CallGraphNode *> FunctionMapTy; 77c1a81ebec52bc5dff8c9461570e1212afe09506freed@google.com FunctionMapTy FunctionMap; // Map from a function to its node 78d44d988127841cf9180bb7ba91b6eba8127af467reed@google.com 79d44d988127841cf9180bb7ba91b6eba8127af467reed@google.compublic: 80d44d988127841cf9180bb7ba91b6eba8127af467reed@google.com static char ID; // Class identification, replacement for typeinfo 8183165a5f71319b04beb561afb7c968493027bcbdreed@google.com //===--------------------------------------------------------------------- 8283165a5f71319b04beb561afb7c968493027bcbdreed@google.com // Accessors. 8383165a5f71319b04beb561afb7c968493027bcbdreed@google.com // 8483165a5f71319b04beb561afb7c968493027bcbdreed@google.com typedef FunctionMapTy::iterator iterator; 8583165a5f71319b04beb561afb7c968493027bcbdreed@google.com typedef FunctionMapTy::const_iterator const_iterator; 8683165a5f71319b04beb561afb7c968493027bcbdreed@google.com 8783165a5f71319b04beb561afb7c968493027bcbdreed@google.com /// getModule - Return the module the call graph corresponds to. 8883165a5f71319b04beb561afb7c968493027bcbdreed@google.com /// 897103344b64f3f0df88e76857c16edc8eedb58366bungeman@google.com Module &getModule() const { return *Mod; } 9083165a5f71319b04beb561afb7c968493027bcbdreed@google.com 917103344b64f3f0df88e76857c16edc8eedb58366bungeman@google.com inline iterator begin() { return FunctionMap.begin(); } 9283165a5f71319b04beb561afb7c968493027bcbdreed@google.com inline iterator end() { return FunctionMap.end(); } 9383165a5f71319b04beb561afb7c968493027bcbdreed@google.com inline const_iterator begin() const { return FunctionMap.begin(); } 9483165a5f71319b04beb561afb7c968493027bcbdreed@google.com inline const_iterator end() const { return FunctionMap.end(); } 9583165a5f71319b04beb561afb7c968493027bcbdreed@google.com 9683165a5f71319b04beb561afb7c968493027bcbdreed@google.com // Subscripting operators, return the call graph node for the provided 9783165a5f71319b04beb561afb7c968493027bcbdreed@google.com // function 9883165a5f71319b04beb561afb7c968493027bcbdreed@google.com inline const CallGraphNode *operator[](const Function *F) const { 9983165a5f71319b04beb561afb7c968493027bcbdreed@google.com const_iterator I = FunctionMap.find(F); 10083165a5f71319b04beb561afb7c968493027bcbdreed@google.com assert(I != FunctionMap.end() && "Function not in callgraph!"); 101eb02957a5ff4e7b639263b2071e5e2522c7bc4fareed@google.com return I->second; 10283165a5f71319b04beb561afb7c968493027bcbdreed@google.com } 10383165a5f71319b04beb561afb7c968493027bcbdreed@google.com inline CallGraphNode *operator[](const Function *F) { 104c1ccda3af8c462dc99d5893806baac3bd85fa5d3reed@google.com const_iterator I = FunctionMap.find(F); 10583165a5f71319b04beb561afb7c968493027bcbdreed@google.com assert(I != FunctionMap.end() && "Function not in callgraph!"); 10683165a5f71319b04beb561afb7c968493027bcbdreed@google.com return I->second; 10783165a5f71319b04beb561afb7c968493027bcbdreed@google.com } 10883165a5f71319b04beb561afb7c968493027bcbdreed@google.com 10983165a5f71319b04beb561afb7c968493027bcbdreed@google.com /// Returns the CallGraphNode which is used to represent undetermined calls 11083165a5f71319b04beb561afb7c968493027bcbdreed@google.com /// into the callgraph. Override this if you want behavioral inheritance. 11183165a5f71319b04beb561afb7c968493027bcbdreed@google.com virtual CallGraphNode* getExternalCallingNode() const { return 0; } 11283165a5f71319b04beb561afb7c968493027bcbdreed@google.com virtual CallGraphNode* getCallsExternalNode() const { return 0; } 11383165a5f71319b04beb561afb7c968493027bcbdreed@google.com 11466c9f9995ec581f578aa7de4f0defe7dd728fa7ereed@google.com /// Return the root/main method in the module, or some other root node, such 11583165a5f71319b04beb561afb7c968493027bcbdreed@google.com /// as the externalcallingnode. Overload these if you behavioral 116e4fafb146e85cdfcf9d5418597b6818aa0754adatfarina@chromium.org /// inheritance. 11783165a5f71319b04beb561afb7c968493027bcbdreed@google.com virtual CallGraphNode* getRoot() { return 0; } 118c1a81ebec52bc5dff8c9461570e1212afe09506freed@google.com virtual const CallGraphNode* getRoot() const { return 0; } 11943c27586e8b02243c16649de1cd7d95dcea0a712reed@google.com 12083165a5f71319b04beb561afb7c968493027bcbdreed@google.com //===--------------------------------------------------------------------- 121 // Functions to keep a call graph up to date with a function that has been 122 // modified. 123 // 124 125 /// removeFunctionFromModule - Unlink the function from this module, returning 126 /// it. Because this removes the function from the module, the call graph 127 /// node is destroyed. This is only valid if the function does not call any 128 /// other functions (ie, there are no edges in it's CGN). The easiest way to 129 /// do this is to dropAllReferences before calling this. 130 /// 131 Function *removeFunctionFromModule(CallGraphNode *CGN); 132 Function *removeFunctionFromModule(Function *F) { 133 return removeFunctionFromModule((*this)[F]); 134 } 135 136 /// getOrInsertFunction - This method is identical to calling operator[], but 137 /// it will insert a new CallGraphNode for the specified function if one does 138 /// not already exist. 139 CallGraphNode *getOrInsertFunction(const Function *F); 140 141 /// spliceFunction - Replace the function represented by this node by another. 142 /// This does not rescan the body of the function, so it is suitable when 143 /// splicing the body of one function to another while also updating all 144 /// callers from the old function to the new. 145 /// 146 void spliceFunction(const Function *From, const Function *To); 147 148 //===--------------------------------------------------------------------- 149 // Pass infrastructure interface glue code. 150 // 151protected: 152 CallGraph() {} 153 154public: 155 virtual ~CallGraph() { destroy(); } 156 157 /// initialize - Call this method before calling other methods, 158 /// re/initializes the state of the CallGraph. 159 /// 160 void initialize(Module &M); 161 162 void print(raw_ostream &o, Module *) const; 163 void dump() const; 164protected: 165 // destroy - Release memory for the call graph 166 virtual void destroy(); 167}; 168 169//===----------------------------------------------------------------------===// 170// CallGraphNode class definition. 171// 172class CallGraphNode { 173 friend class CallGraph; 174 175 AssertingVH<Function> F; 176 177 // CallRecord - This is a pair of the calling instruction (a call or invoke) 178 // and the callgraph node being called. 179public: 180 typedef std::pair<WeakVH, CallGraphNode*> CallRecord; 181private: 182 std::vector<CallRecord> CalledFunctions; 183 184 /// NumReferences - This is the number of times that this CallGraphNode occurs 185 /// in the CalledFunctions array of this or other CallGraphNodes. 186 unsigned NumReferences; 187 188 CallGraphNode(const CallGraphNode &); // DO NOT IMPLEMENT 189 void operator=(const CallGraphNode &); // DO NOT IMPLEMENT 190 191 void DropRef() { --NumReferences; } 192 void AddRef() { ++NumReferences; } 193public: 194 typedef std::vector<CallRecord> CalledFunctionsVector; 195 196 197 // CallGraphNode ctor - Create a node for the specified function. 198 inline CallGraphNode(Function *f) : F(f), NumReferences(0) {} 199 ~CallGraphNode() { 200 assert(NumReferences == 0 && "Node deleted while references remain"); 201 } 202 203 //===--------------------------------------------------------------------- 204 // Accessor methods. 205 // 206 207 typedef std::vector<CallRecord>::iterator iterator; 208 typedef std::vector<CallRecord>::const_iterator const_iterator; 209 210 // getFunction - Return the function that this call graph node represents. 211 Function *getFunction() const { return F; } 212 213 inline iterator begin() { return CalledFunctions.begin(); } 214 inline iterator end() { return CalledFunctions.end(); } 215 inline const_iterator begin() const { return CalledFunctions.begin(); } 216 inline const_iterator end() const { return CalledFunctions.end(); } 217 inline bool empty() const { return CalledFunctions.empty(); } 218 inline unsigned size() const { return (unsigned)CalledFunctions.size(); } 219 220 /// getNumReferences - Return the number of other CallGraphNodes in this 221 /// CallGraph that reference this node in their callee list. 222 unsigned getNumReferences() const { return NumReferences; } 223 224 // Subscripting operator - Return the i'th called function. 225 // 226 CallGraphNode *operator[](unsigned i) const { 227 assert(i < CalledFunctions.size() && "Invalid index"); 228 return CalledFunctions[i].second; 229 } 230 231 /// dump - Print out this call graph node. 232 /// 233 void dump() const; 234 void print(raw_ostream &OS) const; 235 236 //===--------------------------------------------------------------------- 237 // Methods to keep a call graph up to date with a function that has been 238 // modified 239 // 240 241 /// removeAllCalledFunctions - As the name implies, this removes all edges 242 /// from this CallGraphNode to any functions it calls. 243 void removeAllCalledFunctions() { 244 while (!CalledFunctions.empty()) { 245 CalledFunctions.back().second->DropRef(); 246 CalledFunctions.pop_back(); 247 } 248 } 249 250 /// stealCalledFunctionsFrom - Move all the callee information from N to this 251 /// node. 252 void stealCalledFunctionsFrom(CallGraphNode *N) { 253 assert(CalledFunctions.empty() && 254 "Cannot steal callsite information if I already have some"); 255 std::swap(CalledFunctions, N->CalledFunctions); 256 } 257 258 259 /// addCalledFunction - Add a function to the list of functions called by this 260 /// one. 261 void addCalledFunction(CallSite CS, CallGraphNode *M) { 262 assert(!CS.getInstruction() || 263 !CS.getCalledFunction() || 264 !CS.getCalledFunction()->isIntrinsic()); 265 CalledFunctions.push_back(std::make_pair(CS.getInstruction(), M)); 266 M->AddRef(); 267 } 268 269 void removeCallEdge(iterator I) { 270 I->second->DropRef(); 271 *I = CalledFunctions.back(); 272 CalledFunctions.pop_back(); 273 } 274 275 276 /// removeCallEdgeFor - This method removes the edge in the node for the 277 /// specified call site. Note that this method takes linear time, so it 278 /// should be used sparingly. 279 void removeCallEdgeFor(CallSite CS); 280 281 /// removeAnyCallEdgeTo - This method removes all call edges from this node 282 /// to the specified callee function. This takes more time to execute than 283 /// removeCallEdgeTo, so it should not be used unless necessary. 284 void removeAnyCallEdgeTo(CallGraphNode *Callee); 285 286 /// removeOneAbstractEdgeTo - Remove one edge associated with a null callsite 287 /// from this node to the specified callee function. 288 void removeOneAbstractEdgeTo(CallGraphNode *Callee); 289 290 /// replaceCallEdge - This method replaces the edge in the node for the 291 /// specified call site with a new one. Note that this method takes linear 292 /// time, so it should be used sparingly. 293 void replaceCallEdge(CallSite CS, CallSite NewCS, CallGraphNode *NewNode); 294 295 /// allReferencesDropped - This is a special function that should only be 296 /// used by the CallGraph class. 297 void allReferencesDropped() { 298 NumReferences = 0; 299 } 300}; 301 302//===----------------------------------------------------------------------===// 303// GraphTraits specializations for call graphs so that they can be treated as 304// graphs by the generic graph algorithms. 305// 306 307// Provide graph traits for tranversing call graphs using standard graph 308// traversals. 309template <> struct GraphTraits<CallGraphNode*> { 310 typedef CallGraphNode NodeType; 311 312 typedef CallGraphNode::CallRecord CGNPairTy; 313 typedef std::pointer_to_unary_function<CGNPairTy, CallGraphNode*> CGNDerefFun; 314 315 static NodeType *getEntryNode(CallGraphNode *CGN) { return CGN; } 316 317 typedef mapped_iterator<NodeType::iterator, CGNDerefFun> ChildIteratorType; 318 319 static inline ChildIteratorType child_begin(NodeType *N) { 320 return map_iterator(N->begin(), CGNDerefFun(CGNDeref)); 321 } 322 static inline ChildIteratorType child_end (NodeType *N) { 323 return map_iterator(N->end(), CGNDerefFun(CGNDeref)); 324 } 325 326 static CallGraphNode *CGNDeref(CGNPairTy P) { 327 return P.second; 328 } 329 330}; 331 332template <> struct GraphTraits<const CallGraphNode*> { 333 typedef const CallGraphNode NodeType; 334 typedef NodeType::const_iterator ChildIteratorType; 335 336 static NodeType *getEntryNode(const CallGraphNode *CGN) { return CGN; } 337 static inline ChildIteratorType child_begin(NodeType *N) { return N->begin();} 338 static inline ChildIteratorType child_end (NodeType *N) { return N->end(); } 339}; 340 341template<> struct GraphTraits<CallGraph*> : public GraphTraits<CallGraphNode*> { 342 static NodeType *getEntryNode(CallGraph *CGN) { 343 return CGN->getExternalCallingNode(); // Start at the external node! 344 } 345 typedef std::pair<const Function*, CallGraphNode*> PairTy; 346 typedef std::pointer_to_unary_function<PairTy, CallGraphNode&> DerefFun; 347 348 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph 349 typedef mapped_iterator<CallGraph::iterator, DerefFun> nodes_iterator; 350 static nodes_iterator nodes_begin(CallGraph *CG) { 351 return map_iterator(CG->begin(), DerefFun(CGdereference)); 352 } 353 static nodes_iterator nodes_end (CallGraph *CG) { 354 return map_iterator(CG->end(), DerefFun(CGdereference)); 355 } 356 357 static CallGraphNode &CGdereference(PairTy P) { 358 return *P.second; 359 } 360}; 361 362template<> struct GraphTraits<const CallGraph*> : 363 public GraphTraits<const CallGraphNode*> { 364 static NodeType *getEntryNode(const CallGraph *CGN) { 365 return CGN->getExternalCallingNode(); 366 } 367 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph 368 typedef CallGraph::const_iterator nodes_iterator; 369 static nodes_iterator nodes_begin(const CallGraph *CG) { return CG->begin(); } 370 static nodes_iterator nodes_end (const CallGraph *CG) { return CG->end(); } 371}; 372 373} // End llvm namespace 374 375// Make sure that any clients of this file link in CallGraph.cpp 376FORCE_DEFINING_FILE_TO_BE_LINKED(CallGraph) 377 378#endif 379