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

source code of llvm/include/llvm/Analysis/CallGraph.h