1 //===- CallGraph.h - Build a Module's call graph ----------------*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 /// \file 9 /// 10 /// This file provides interfaces used to build and manipulate a call graph, 11 /// which is a very 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 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 18 /// is null. These 'external' nodes are used to represent control flow that is 19 /// not represented (or analyzable) in the module. In particular, this 20 /// analysis 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 26 /// an edge from this external node. Since they may be called by an 27 /// unknown 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 //===----------------------------------------------------------------------===// 44 45 #ifndef LLVM_ANALYSIS_CALLGRAPH_H 46 #define LLVM_ANALYSIS_CALLGRAPH_H 47 48 #include "llvm/ADT/GraphTraits.h" 49 #include "llvm/ADT/STLExtras.h" 50 #include "llvm/IR/Function.h" 51 #include "llvm/IR/InstrTypes.h" 52 #include "llvm/IR/Intrinsics.h" 53 #include "llvm/IR/PassManager.h" 54 #include "llvm/IR/ValueHandle.h" 55 #include "llvm/Pass.h" 56 #include <cassert> 57 #include <map> 58 #include <memory> 59 #include <utility> 60 #include <vector> 61 62 namespace llvm { 63 64 class CallGraphNode; 65 class Module; 66 class raw_ostream; 67 68 /// The basic data container for the call graph of a \c Module of IR. 69 /// 70 /// This class exposes both the interface to the call graph for a module of IR. 71 /// 72 /// The core call graph itself can also be updated to reflect changes to the IR. 73 class CallGraph { 74 Module &M; 75 76 using FunctionMapTy = 77 std::map<const Function *, std::unique_ptr<CallGraphNode>>; 78 79 /// A map from \c Function* to \c CallGraphNode*. 80 FunctionMapTy FunctionMap; 81 82 /// This node has edges to all external functions and those internal 83 /// functions that have their address taken. 84 CallGraphNode *ExternalCallingNode; 85 86 /// This node has edges to it from all functions making indirect calls 87 /// or calling an external function. 88 std::unique_ptr<CallGraphNode> CallsExternalNode; 89 90 /// Replace the function represented by this node by another. 91 /// 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 void spliceFunction(const Function *From, const Function *To); 96 97 public: 98 explicit CallGraph(Module &M); 99 CallGraph(CallGraph &&Arg); 100 ~CallGraph(); 101 102 void print(raw_ostream &OS) const; 103 void dump() const; 104 105 using iterator = FunctionMapTy::iterator; 106 using const_iterator = FunctionMapTy::const_iterator; 107 108 /// Returns the module the call graph corresponds to. getModule()109 Module &getModule() const { return M; } 110 111 bool invalidate(Module &, const PreservedAnalyses &PA, 112 ModuleAnalysisManager::Invalidator &); 113 begin()114 inline iterator begin() { return FunctionMap.begin(); } end()115 inline iterator end() { return FunctionMap.end(); } begin()116 inline const_iterator begin() const { return FunctionMap.begin(); } end()117 inline const_iterator end() const { return FunctionMap.end(); } 118 119 /// Returns the call graph node for the provided function. 120 inline const CallGraphNode *operator[](const Function *F) const { 121 const_iterator I = FunctionMap.find(F); 122 assert(I != FunctionMap.end() && "Function not in callgraph!"); 123 return I->second.get(); 124 } 125 126 /// Returns the call graph node for the provided function. 127 inline CallGraphNode *operator[](const Function *F) { 128 const_iterator I = FunctionMap.find(F); 129 assert(I != FunctionMap.end() && "Function not in callgraph!"); 130 return I->second.get(); 131 } 132 133 /// Returns the \c CallGraphNode which is used to represent 134 /// undetermined calls into the callgraph. getExternalCallingNode()135 CallGraphNode *getExternalCallingNode() const { return ExternalCallingNode; } 136 getCallsExternalNode()137 CallGraphNode *getCallsExternalNode() const { 138 return CallsExternalNode.get(); 139 } 140 141 /// Old node has been deleted, and New is to be used in its place, update the 142 /// ExternalCallingNode. 143 void ReplaceExternalCallEdge(CallGraphNode *Old, CallGraphNode *New); 144 145 //===--------------------------------------------------------------------- 146 // Functions to keep a call graph up to date with a function that has been 147 // modified. 148 // 149 150 /// Unlink the function from this module, returning it. 151 /// 152 /// Because this removes the function from the module, the call graph node is 153 /// destroyed. This is only valid if the function does not call any other 154 /// functions (ie, there are no edges in it's CGN). The easiest way to do 155 /// this is to dropAllReferences before calling this. 156 Function *removeFunctionFromModule(CallGraphNode *CGN); 157 158 /// Similar to operator[], but this will insert a new CallGraphNode for 159 /// \c F if one does not already exist. 160 CallGraphNode *getOrInsertFunction(const Function *F); 161 162 /// Populate \p CGN based on the calls inside the associated function. 163 void populateCallGraphNode(CallGraphNode *CGN); 164 165 /// Add a function to the call graph, and link the node to all of the 166 /// functions that it calls. 167 void addToCallGraph(Function *F); 168 }; 169 170 /// A node in the call graph for a module. 171 /// 172 /// Typically represents a function in the call graph. There are also special 173 /// "null" nodes used to represent theoretical entries in the call graph. 174 class CallGraphNode { 175 public: 176 /// A pair of the calling instruction (a call or invoke) 177 /// and the call graph node being called. 178 /// Call graph node may have two types of call records which represent an edge 179 /// in the call graph - reference or a call edge. Reference edges are not 180 /// associated with any call instruction and are created with the first field 181 /// set to `None`, while real call edges have instruction address in this 182 /// field. Therefore, all real call edges are expected to have a value in the 183 /// first field and it is not supposed to be `nullptr`. 184 /// Reference edges, for example, are used for connecting broker function 185 /// caller to the callback function for callback call sites. 186 using CallRecord = std::pair<Optional<WeakTrackingVH>, CallGraphNode *>; 187 188 public: 189 using CalledFunctionsVector = std::vector<CallRecord>; 190 191 /// Creates a node for the specified function. CallGraphNode(CallGraph * CG,Function * F)192 inline CallGraphNode(CallGraph *CG, Function *F) : CG(CG), F(F) {} 193 194 CallGraphNode(const CallGraphNode &) = delete; 195 CallGraphNode &operator=(const CallGraphNode &) = delete; 196 ~CallGraphNode()197 ~CallGraphNode() { 198 assert(NumReferences == 0 && "Node deleted while references remain"); 199 } 200 201 using iterator = std::vector<CallRecord>::iterator; 202 using const_iterator = std::vector<CallRecord>::const_iterator; 203 204 /// Returns the function that this call graph node represents. getFunction()205 Function *getFunction() const { return F; } 206 begin()207 inline iterator begin() { return CalledFunctions.begin(); } end()208 inline iterator end() { return CalledFunctions.end(); } begin()209 inline const_iterator begin() const { return CalledFunctions.begin(); } end()210 inline const_iterator end() const { return CalledFunctions.end(); } empty()211 inline bool empty() const { return CalledFunctions.empty(); } size()212 inline unsigned size() const { return (unsigned)CalledFunctions.size(); } 213 214 /// Returns the number of other CallGraphNodes in this CallGraph that 215 /// reference this node in their callee list. getNumReferences()216 unsigned getNumReferences() const { return NumReferences; } 217 218 /// Returns the i'th called function. 219 CallGraphNode *operator[](unsigned i) const { 220 assert(i < CalledFunctions.size() && "Invalid index"); 221 return CalledFunctions[i].second; 222 } 223 224 /// Print out this call graph node. 225 void dump() const; 226 void print(raw_ostream &OS) const; 227 228 //===--------------------------------------------------------------------- 229 // Methods to keep a call graph up to date with a function that has been 230 // modified 231 // 232 233 /// Removes all edges from this CallGraphNode to any functions it 234 /// calls. removeAllCalledFunctions()235 void removeAllCalledFunctions() { 236 while (!CalledFunctions.empty()) { 237 CalledFunctions.back().second->DropRef(); 238 CalledFunctions.pop_back(); 239 } 240 } 241 242 /// Moves all the callee information from N to this node. stealCalledFunctionsFrom(CallGraphNode * N)243 void stealCalledFunctionsFrom(CallGraphNode *N) { 244 assert(CalledFunctions.empty() && 245 "Cannot steal callsite information if I already have some"); 246 std::swap(CalledFunctions, N->CalledFunctions); 247 } 248 249 /// Adds a function to the list of functions called by this one. addCalledFunction(CallBase * Call,CallGraphNode * M)250 void addCalledFunction(CallBase *Call, CallGraphNode *M) { 251 assert(!Call || !Call->getCalledFunction() || 252 !Call->getCalledFunction()->isIntrinsic() || 253 !Intrinsic::isLeaf(Call->getCalledFunction()->getIntrinsicID())); 254 CalledFunctions.emplace_back( 255 Call ? Optional<WeakTrackingVH>(Call) : Optional<WeakTrackingVH>(), M); 256 M->AddRef(); 257 } 258 removeCallEdge(iterator I)259 void removeCallEdge(iterator I) { 260 I->second->DropRef(); 261 *I = CalledFunctions.back(); 262 CalledFunctions.pop_back(); 263 } 264 265 /// Removes the edge in the node for the specified call site. 266 /// 267 /// Note that this method takes linear time, so it should be used sparingly. 268 void removeCallEdgeFor(CallBase &Call); 269 270 /// Removes all call edges from this node to the specified callee 271 /// function. 272 /// 273 /// This takes more time to execute than removeCallEdgeTo, so it should not 274 /// be used unless necessary. 275 void removeAnyCallEdgeTo(CallGraphNode *Callee); 276 277 /// Removes one edge associated with a null callsite from this node to 278 /// the specified callee function. 279 void removeOneAbstractEdgeTo(CallGraphNode *Callee); 280 281 /// Replaces the edge in the node for the specified call site with a 282 /// new one. 283 /// 284 /// Note that this method takes linear time, so it should be used sparingly. 285 void replaceCallEdge(CallBase &Call, CallBase &NewCall, 286 CallGraphNode *NewNode); 287 288 private: 289 friend class CallGraph; 290 291 CallGraph *CG; 292 Function *F; 293 294 std::vector<CallRecord> CalledFunctions; 295 296 /// The number of times that this CallGraphNode occurs in the 297 /// CalledFunctions array of this or other CallGraphNodes. 298 unsigned NumReferences = 0; 299 DropRef()300 void DropRef() { --NumReferences; } AddRef()301 void AddRef() { ++NumReferences; } 302 303 /// A special function that should only be used by the CallGraph class. allReferencesDropped()304 void allReferencesDropped() { NumReferences = 0; } 305 }; 306 307 /// An analysis pass to compute the \c CallGraph for a \c Module. 308 /// 309 /// This class implements the concept of an analysis pass used by the \c 310 /// ModuleAnalysisManager to run an analysis over a module and cache the 311 /// resulting data. 312 class CallGraphAnalysis : public AnalysisInfoMixin<CallGraphAnalysis> { 313 friend AnalysisInfoMixin<CallGraphAnalysis>; 314 315 static AnalysisKey Key; 316 317 public: 318 /// A formulaic type to inform clients of the result type. 319 using Result = CallGraph; 320 321 /// Compute the \c CallGraph for the module \c M. 322 /// 323 /// The real work here is done in the \c CallGraph constructor. run(Module & M,ModuleAnalysisManager &)324 CallGraph run(Module &M, ModuleAnalysisManager &) { return CallGraph(M); } 325 }; 326 327 /// Printer pass for the \c CallGraphAnalysis results. 328 class CallGraphPrinterPass : public PassInfoMixin<CallGraphPrinterPass> { 329 raw_ostream &OS; 330 331 public: CallGraphPrinterPass(raw_ostream & OS)332 explicit CallGraphPrinterPass(raw_ostream &OS) : OS(OS) {} 333 334 PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM); 335 }; 336 337 /// The \c ModulePass which wraps up a \c CallGraph and the logic to 338 /// build it. 339 /// 340 /// This class exposes both the interface to the call graph container and the 341 /// module pass which runs over a module of IR and produces the call graph. The 342 /// call graph interface is entirelly a wrapper around a \c CallGraph object 343 /// which is stored internally for each module. 344 class CallGraphWrapperPass : public ModulePass { 345 std::unique_ptr<CallGraph> G; 346 347 public: 348 static char ID; // Class identification, replacement for typeinfo 349 350 CallGraphWrapperPass(); 351 ~CallGraphWrapperPass() override; 352 353 /// The internal \c CallGraph around which the rest of this interface 354 /// is wrapped. getCallGraph()355 const CallGraph &getCallGraph() const { return *G; } getCallGraph()356 CallGraph &getCallGraph() { return *G; } 357 358 using iterator = CallGraph::iterator; 359 using const_iterator = CallGraph::const_iterator; 360 361 /// Returns the module the call graph corresponds to. getModule()362 Module &getModule() const { return G->getModule(); } 363 begin()364 inline iterator begin() { return G->begin(); } end()365 inline iterator end() { return G->end(); } begin()366 inline const_iterator begin() const { return G->begin(); } end()367 inline const_iterator end() const { return G->end(); } 368 369 /// Returns the call graph node for the provided function. 370 inline const CallGraphNode *operator[](const Function *F) const { 371 return (*G)[F]; 372 } 373 374 /// Returns the call graph node for the provided function. 375 inline CallGraphNode *operator[](const Function *F) { return (*G)[F]; } 376 377 /// Returns the \c CallGraphNode which is used to represent 378 /// undetermined calls into the callgraph. getExternalCallingNode()379 CallGraphNode *getExternalCallingNode() const { 380 return G->getExternalCallingNode(); 381 } 382 getCallsExternalNode()383 CallGraphNode *getCallsExternalNode() const { 384 return G->getCallsExternalNode(); 385 } 386 387 //===--------------------------------------------------------------------- 388 // Functions to keep a call graph up to date with a function that has been 389 // modified. 390 // 391 392 /// Unlink the function from this module, returning it. 393 /// 394 /// Because this removes the function from the module, the call graph node is 395 /// destroyed. This is only valid if the function does not call any other 396 /// functions (ie, there are no edges in it's CGN). The easiest way to do 397 /// this is to dropAllReferences before calling this. removeFunctionFromModule(CallGraphNode * CGN)398 Function *removeFunctionFromModule(CallGraphNode *CGN) { 399 return G->removeFunctionFromModule(CGN); 400 } 401 402 /// Similar to operator[], but this will insert a new CallGraphNode for 403 /// \c F if one does not already exist. getOrInsertFunction(const Function * F)404 CallGraphNode *getOrInsertFunction(const Function *F) { 405 return G->getOrInsertFunction(F); 406 } 407 408 //===--------------------------------------------------------------------- 409 // Implementation of the ModulePass interface needed here. 410 // 411 412 void getAnalysisUsage(AnalysisUsage &AU) const override; 413 bool runOnModule(Module &M) override; 414 void releaseMemory() override; 415 416 void print(raw_ostream &o, const Module *) const override; 417 void dump() const; 418 }; 419 420 //===----------------------------------------------------------------------===// 421 // GraphTraits specializations for call graphs so that they can be treated as 422 // graphs by the generic graph algorithms. 423 // 424 425 // Provide graph traits for traversing call graphs using standard graph 426 // traversals. 427 template <> struct GraphTraits<CallGraphNode *> { 428 using NodeRef = CallGraphNode *; 429 using CGNPairTy = CallGraphNode::CallRecord; 430 431 static NodeRef getEntryNode(CallGraphNode *CGN) { return CGN; } 432 static CallGraphNode *CGNGetValue(CGNPairTy P) { return P.second; } 433 434 using ChildIteratorType = 435 mapped_iterator<CallGraphNode::iterator, decltype(&CGNGetValue)>; 436 437 static ChildIteratorType child_begin(NodeRef N) { 438 return ChildIteratorType(N->begin(), &CGNGetValue); 439 } 440 441 static ChildIteratorType child_end(NodeRef N) { 442 return ChildIteratorType(N->end(), &CGNGetValue); 443 } 444 }; 445 446 template <> struct GraphTraits<const CallGraphNode *> { 447 using NodeRef = const CallGraphNode *; 448 using CGNPairTy = CallGraphNode::CallRecord; 449 using EdgeRef = const CallGraphNode::CallRecord &; 450 451 static NodeRef getEntryNode(const CallGraphNode *CGN) { return CGN; } 452 static const CallGraphNode *CGNGetValue(CGNPairTy P) { return P.second; } 453 454 using ChildIteratorType = 455 mapped_iterator<CallGraphNode::const_iterator, decltype(&CGNGetValue)>; 456 using ChildEdgeIteratorType = CallGraphNode::const_iterator; 457 458 static ChildIteratorType child_begin(NodeRef N) { 459 return ChildIteratorType(N->begin(), &CGNGetValue); 460 } 461 462 static ChildIteratorType child_end(NodeRef N) { 463 return ChildIteratorType(N->end(), &CGNGetValue); 464 } 465 466 static ChildEdgeIteratorType child_edge_begin(NodeRef N) { 467 return N->begin(); 468 } 469 static ChildEdgeIteratorType child_edge_end(NodeRef N) { return N->end(); } 470 471 static NodeRef edge_dest(EdgeRef E) { return E.second; } 472 }; 473 474 template <> 475 struct GraphTraits<CallGraph *> : public GraphTraits<CallGraphNode *> { 476 using PairTy = 477 std::pair<const Function *const, std::unique_ptr<CallGraphNode>>; 478 479 static NodeRef getEntryNode(CallGraph *CGN) { 480 return CGN->getExternalCallingNode(); // Start at the external node! 481 } 482 483 static CallGraphNode *CGGetValuePtr(const PairTy &P) { 484 return P.second.get(); 485 } 486 487 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph 488 using nodes_iterator = 489 mapped_iterator<CallGraph::iterator, decltype(&CGGetValuePtr)>; 490 491 static nodes_iterator nodes_begin(CallGraph *CG) { 492 return nodes_iterator(CG->begin(), &CGGetValuePtr); 493 } 494 495 static nodes_iterator nodes_end(CallGraph *CG) { 496 return nodes_iterator(CG->end(), &CGGetValuePtr); 497 } 498 }; 499 500 template <> 501 struct GraphTraits<const CallGraph *> : public GraphTraits< 502 const CallGraphNode *> { 503 using PairTy = 504 std::pair<const Function *const, std::unique_ptr<CallGraphNode>>; 505 506 static NodeRef getEntryNode(const CallGraph *CGN) { 507 return CGN->getExternalCallingNode(); // Start at the external node! 508 } 509 510 static const CallGraphNode *CGGetValuePtr(const PairTy &P) { 511 return P.second.get(); 512 } 513 514 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph 515 using nodes_iterator = 516 mapped_iterator<CallGraph::const_iterator, decltype(&CGGetValuePtr)>; 517 518 static nodes_iterator nodes_begin(const CallGraph *CG) { 519 return nodes_iterator(CG->begin(), &CGGetValuePtr); 520 } 521 522 static nodes_iterator nodes_end(const CallGraph *CG) { 523 return nodes_iterator(CG->end(), &CGGetValuePtr); 524 } 525 }; 526 527 } // end namespace llvm 528 529 #endif // LLVM_ANALYSIS_CALLGRAPH_H 530