LLVM  17.0.0git
CallGraph.h
Go to the documentation of this file.
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 
59 namespace llvm {
60 
61 template <class GraphType> struct GraphTraits;
62 class CallGraphNode;
63 class Function;
64 class Module;
65 class 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.
72 class 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 
89 public:
90  explicit CallGraph(Module &M);
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,
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 
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.
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.
149 
150  /// Similar to operator[], but this will insert a new CallGraphNode for
151  /// \c F if one does not already exist.
153 
154  /// Populate \p CGN based on the calls inside the associated function.
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.
167 public:
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<std::optional<WeakTrackingVH>, CallGraphNode *>;
179 
180 public:
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 
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.
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.
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.
243  CalledFunctions.emplace_back(Call ? std::optional<WeakTrackingVH>(Call)
244  : std::optional<WeakTrackingVH>(),
245  M);
246  M->AddRef();
247  }
248 
250  I->second->DropRef();
251  *I = CalledFunctions.back();
252  CalledFunctions.pop_back();
253  }
254 
255  /// Removes the edge in the node for the specified call site.
256  ///
257  /// Note that this method takes linear time, so it should be used sparingly.
258  void removeCallEdgeFor(CallBase &Call);
259 
260  /// Removes all call edges from this node to the specified callee
261  /// function.
262  ///
263  /// This takes more time to execute than removeCallEdgeTo, so it should not
264  /// be used unless necessary.
265  void removeAnyCallEdgeTo(CallGraphNode *Callee);
266 
267  /// Removes one edge associated with a null callsite from this node to
268  /// the specified callee function.
270 
271  /// Replaces the edge in the node for the specified call site with a
272  /// new one.
273  ///
274  /// Note that this method takes linear time, so it should be used sparingly.
275  void replaceCallEdge(CallBase &Call, CallBase &NewCall,
276  CallGraphNode *NewNode);
277 
278 private:
279  friend class CallGraph;
280 
281  CallGraph *CG;
282  Function *F;
283 
284  std::vector<CallRecord> CalledFunctions;
285 
286  /// The number of times that this CallGraphNode occurs in the
287  /// CalledFunctions array of this or other CallGraphNodes.
288  unsigned NumReferences = 0;
289 
290  void DropRef() { --NumReferences; }
291  void AddRef() { ++NumReferences; }
292 
293  /// A special function that should only be used by the CallGraph class.
294  void allReferencesDropped() { NumReferences = 0; }
295 };
296 
297 /// An analysis pass to compute the \c CallGraph for a \c Module.
298 ///
299 /// This class implements the concept of an analysis pass used by the \c
300 /// ModuleAnalysisManager to run an analysis over a module and cache the
301 /// resulting data.
302 class CallGraphAnalysis : public AnalysisInfoMixin<CallGraphAnalysis> {
304 
305  static AnalysisKey Key;
306 
307 public:
308  /// A formulaic type to inform clients of the result type.
309  using Result = CallGraph;
310 
311  /// Compute the \c CallGraph for the module \c M.
312  ///
313  /// The real work here is done in the \c CallGraph constructor.
315 };
316 
317 /// Printer pass for the \c CallGraphAnalysis results.
318 class CallGraphPrinterPass : public PassInfoMixin<CallGraphPrinterPass> {
319  raw_ostream &OS;
320 
321 public:
322  explicit CallGraphPrinterPass(raw_ostream &OS) : OS(OS) {}
323 
325 };
326 
327 /// Printer pass for the summarized \c CallGraphAnalysis results.
329  : public PassInfoMixin<CallGraphSCCsPrinterPass> {
330  raw_ostream &OS;
331 
332 public:
333  explicit CallGraphSCCsPrinterPass(raw_ostream &OS) : OS(OS) {}
334 
336 };
337 
338 /// The \c ModulePass which wraps up a \c CallGraph and the logic to
339 /// build it.
340 ///
341 /// This class exposes both the interface to the call graph container and the
342 /// module pass which runs over a module of IR and produces the call graph. The
343 /// call graph interface is entirelly a wrapper around a \c CallGraph object
344 /// which is stored internally for each module.
346  std::unique_ptr<CallGraph> G;
347 
348 public:
349  static char ID; // Class identification, replacement for typeinfo
350 
352  ~CallGraphWrapperPass() override;
353 
354  /// The internal \c CallGraph around which the rest of this interface
355  /// is wrapped.
356  const CallGraph &getCallGraph() const { return *G; }
357  CallGraph &getCallGraph() { return *G; }
358 
361 
362  /// Returns the module the call graph corresponds to.
363  Module &getModule() const { return G->getModule(); }
364 
365  inline iterator begin() { return G->begin(); }
366  inline iterator end() { return G->end(); }
367  inline const_iterator begin() const { return G->begin(); }
368  inline const_iterator end() const { return G->end(); }
369 
370  /// Returns the call graph node for the provided function.
371  inline const CallGraphNode *operator[](const Function *F) const {
372  return (*G)[F];
373  }
374 
375  /// Returns the call graph node for the provided function.
376  inline CallGraphNode *operator[](const Function *F) { return (*G)[F]; }
377 
378  /// Returns the \c CallGraphNode which is used to represent
379  /// undetermined calls into the callgraph.
381  return G->getExternalCallingNode();
382  }
383 
385  return G->getCallsExternalNode();
386  }
387 
388  //===---------------------------------------------------------------------
389  // Functions to keep a call graph up to date with a function that has been
390  // modified.
391  //
392 
393  /// Unlink the function from this module, returning it.
394  ///
395  /// Because this removes the function from the module, the call graph node is
396  /// destroyed. This is only valid if the function does not call any other
397  /// functions (ie, there are no edges in it's CGN). The easiest way to do
398  /// this is to dropAllReferences before calling this.
400  return G->removeFunctionFromModule(CGN);
401  }
402 
403  /// Similar to operator[], but this will insert a new CallGraphNode for
404  /// \c F if one does not already exist.
406  return G->getOrInsertFunction(F);
407  }
408 
409  //===---------------------------------------------------------------------
410  // Implementation of the ModulePass interface needed here.
411  //
412 
413  void getAnalysisUsage(AnalysisUsage &AU) const override;
414  bool runOnModule(Module &M) override;
415  void releaseMemory() override;
416 
417  void print(raw_ostream &o, const Module *) const override;
418  void dump() const;
419 };
420 
421 //===----------------------------------------------------------------------===//
422 // GraphTraits specializations for call graphs so that they can be treated as
423 // graphs by the generic graph algorithms.
424 //
425 
426 // Provide graph traits for traversing call graphs using standard graph
427 // traversals.
428 template <> struct GraphTraits<CallGraphNode *> {
431 
432  static NodeRef getEntryNode(CallGraphNode *CGN) { return CGN; }
433  static CallGraphNode *CGNGetValue(CGNPairTy P) { return P.second; }
434 
435  using ChildIteratorType =
436  mapped_iterator<CallGraphNode::iterator, decltype(&CGNGetValue)>;
437 
439  return ChildIteratorType(N->begin(), &CGNGetValue);
440  }
441 
443  return ChildIteratorType(N->end(), &CGNGetValue);
444  }
445 };
446 
447 template <> struct GraphTraits<const CallGraphNode *> {
448  using NodeRef = const CallGraphNode *;
451 
452  static NodeRef getEntryNode(const CallGraphNode *CGN) { return CGN; }
453  static const CallGraphNode *CGNGetValue(CGNPairTy P) { return P.second; }
454 
455  using ChildIteratorType =
458 
460  return ChildIteratorType(N->begin(), &CGNGetValue);
461  }
462 
464  return ChildIteratorType(N->end(), &CGNGetValue);
465  }
466 
468  return N->begin();
469  }
470  static ChildEdgeIteratorType child_edge_end(NodeRef N) { return N->end(); }
471 
472  static NodeRef edge_dest(EdgeRef E) { return E.second; }
473 };
474 
475 template <>
477  using PairTy =
478  std::pair<const Function *const, std::unique_ptr<CallGraphNode>>;
479 
481  return CGN->getExternalCallingNode(); // Start at the external node!
482  }
483 
485  return P.second.get();
486  }
487 
488  // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
489  using nodes_iterator =
490  mapped_iterator<CallGraph::iterator, decltype(&CGGetValuePtr)>;
491 
493  return nodes_iterator(CG->begin(), &CGGetValuePtr);
494  }
495 
497  return nodes_iterator(CG->end(), &CGGetValuePtr);
498  }
499 };
500 
501 template <>
503  const CallGraphNode *> {
504  using PairTy =
505  std::pair<const Function *const, std::unique_ptr<CallGraphNode>>;
506 
507  static NodeRef getEntryNode(const CallGraph *CGN) {
508  return CGN->getExternalCallingNode(); // Start at the external node!
509  }
510 
511  static const CallGraphNode *CGGetValuePtr(const PairTy &P) {
512  return P.second.get();
513  }
514 
515  // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
516  using nodes_iterator =
517  mapped_iterator<CallGraph::const_iterator, decltype(&CGGetValuePtr)>;
518 
520  return nodes_iterator(CG->begin(), &CGGetValuePtr);
521  }
522 
523  static nodes_iterator nodes_end(const CallGraph *CG) {
524  return nodes_iterator(CG->end(), &CGGetValuePtr);
525  }
526 };
527 
528 } // end namespace llvm
529 
530 #endif // LLVM_ANALYSIS_CALLGRAPH_H
llvm::CallGraphNode::removeAnyCallEdgeTo
void removeAnyCallEdgeTo(CallGraphNode *Callee)
Removes all call edges from this node to the specified callee function.
Definition: CallGraph.cpp:229
i
i
Definition: README.txt:29
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
llvm::CallGraphNode::end
const_iterator end() const
Definition: CallGraph.h:202
llvm::CallGraphNode::operator=
CallGraphNode & operator=(const CallGraphNode &)=delete
llvm::CallGraphNode::CalledFunctionsVector
std::vector< CallRecord > CalledFunctionsVector
Definition: CallGraph.h:181
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::CallGraph::end
const_iterator end() const
Definition: CallGraph.h:109
llvm::CallGraphWrapperPass::~CallGraphWrapperPass
~CallGraphWrapperPass() override
llvm::GraphTraits< CallGraphNode * >::child_begin
static ChildIteratorType child_begin(NodeRef N)
Definition: CallGraph.h:438
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
llvm::CallGraphNode::iterator
std::vector< CallRecord >::iterator iterator
Definition: CallGraph.h:193
llvm::CallGraph::getExternalCallingNode
CallGraphNode * getExternalCallingNode() const
Returns the CallGraphNode which is used to represent undetermined calls into the callgraph.
Definition: CallGraph.h:127
llvm::CallGraphNode::~CallGraphNode
~CallGraphNode()
Definition: CallGraph.h:189
llvm::CallGraphAnalysis
An analysis pass to compute the CallGraph for a Module.
Definition: CallGraph.h:302
llvm::CallGraphWrapperPass::end
const_iterator end() const
Definition: CallGraph.h:368
llvm::ModulePass
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
Definition: Pass.h:248
llvm::PassInfoMixin
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:371
llvm::Function
Definition: Function.h:59
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
Pass.h
llvm::CallGraphNode::CallGraphNode
CallGraphNode(CallGraph *CG, Function *F)
Creates a node for the specified function.
Definition: CallGraph.h:184
llvm::CallGraphWrapperPass::getCallGraph
const CallGraph & getCallGraph() const
The internal CallGraph around which the rest of this interface is wrapped.
Definition: CallGraph.h:356
llvm::GraphTraits< const CallGraphNode * >::getEntryNode
static NodeRef getEntryNode(const CallGraphNode *CGN)
Definition: CallGraph.h:452
llvm::GraphTraits< const CallGraphNode * >::CGNGetValue
static const CallGraphNode * CGNGetValue(CGNPairTy P)
Definition: CallGraph.h:453
llvm::CallGraphNode::removeCallEdgeFor
void removeCallEdgeFor(CallBase &Call)
Removes the edge in the node for the specified call site.
Definition: CallGraph.cpp:209
llvm::GraphTraits< CallGraphNode * >::child_end
static ChildIteratorType child_end(NodeRef N)
Definition: CallGraph.h:442
llvm::CallGraph::begin
const_iterator begin() const
Definition: CallGraph.h:108
llvm::CallGraph
The basic data container for the call graph of a Module of IR.
Definition: CallGraph.h:72
llvm::CallGraph::dump
void dump() const
Definition: CallGraph.cpp:138
llvm::CallGraphSCCsPrinterPass::CallGraphSCCsPrinterPass
CallGraphSCCsPrinterPass(raw_ostream &OS)
Definition: CallGraph.h:333
llvm::CallGraphWrapperPass::removeFunctionFromModule
Function * removeFunctionFromModule(CallGraphNode *CGN)
Unlink the function from this module, returning it.
Definition: CallGraph.h:399
llvm::CallGraph::~CallGraph
~CallGraph()
Definition: CallGraph.cpp:54
llvm::mapped_iterator
Definition: STLExtras.h:404
llvm::CallGraphNode::removeCallEdge
void removeCallEdge(iterator I)
Definition: CallGraph.h:249
llvm::GraphTraits< CallGraphNode * >::getEntryNode
static NodeRef getEntryNode(CallGraphNode *CGN)
Definition: CallGraph.h:432
llvm::CallGraphSCCsPrinterPass::run
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
Definition: CallGraph.cpp:312
llvm::GraphTraits< const CallGraph * >::nodes_begin
static nodes_iterator nodes_begin(const CallGraph *CG)
Definition: CallGraph.h:519
llvm::CallGraphNode::addCalledFunction
void addCalledFunction(CallBase *Call, CallGraphNode *M)
Adds a function to the list of functions called by this one.
Definition: CallGraph.h:242
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::CallGraph::invalidate
bool invalidate(Module &, const PreservedAnalyses &PA, ModuleAnalysisManager::Invalidator &)
Definition: CallGraph.cpp:67
llvm::CallGraphPrinterPass::run
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
Definition: CallGraph.cpp:306
llvm::CallGraph::getOrInsertFunction
CallGraphNode * getOrInsertFunction(const Function *F)
Similar to operator[], but this will insert a new CallGraphNode for F if one does not already exist.
Definition: CallGraph.cpp:170
Arg
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Definition: AMDGPULibCalls.cpp:187
llvm::CallGraphWrapperPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: CallGraph.cpp:354
llvm::CallGraphNode::end
iterator end()
Definition: CallGraph.h:200
llvm::CallGraph::iterator
FunctionMapTy::iterator iterator
Definition: CallGraph.h:97
llvm::CallGraphNode::getNumReferences
unsigned getNumReferences() const
Returns the number of other CallGraphNodes in this CallGraph that reference this node in their callee...
Definition: CallGraph.h:208
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::CallGraphWrapperPass::end
iterator end()
Definition: CallGraph.h:366
llvm::CallGraph::end
iterator end()
Definition: CallGraph.h:107
llvm::GraphTraits< CallGraphNode * >::CGNPairTy
CallGraphNode::CallRecord CGNPairTy
Definition: CallGraph.h:430
Intrinsics.h
InstrTypes.h
llvm::GraphTraits< const CallGraphNode * >::CGNPairTy
CallGraphNode::CallRecord CGNPairTy
Definition: CallGraph.h:449
llvm::CallGraphNode::dump
void dump() const
Print out this call graph node.
Definition: CallGraph.cpp:203
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::CallGraphWrapperPass::iterator
CallGraph::iterator iterator
Definition: CallGraph.h:359
llvm::CallGraphWrapperPass::getExternalCallingNode
CallGraphNode * getExternalCallingNode() const
Returns the CallGraphNode which is used to represent undetermined calls into the callgraph.
Definition: CallGraph.h:380
llvm::CallGraphSCCsPrinterPass
Printer pass for the summarized CallGraphAnalysis results.
Definition: CallGraph.h:328
llvm::GraphTraits< CallGraph * >::nodes_end
static nodes_iterator nodes_end(CallGraph *CG)
Definition: CallGraph.h:496
llvm::CallGraphWrapperPass::getCallGraph
CallGraph & getCallGraph()
Definition: CallGraph.h:357
llvm::GraphTraits< const CallGraph * >::CGGetValuePtr
static const CallGraphNode * CGGetValuePtr(const PairTy &P)
Definition: CallGraph.h:511
llvm::CallGraph::const_iterator
FunctionMapTy::const_iterator const_iterator
Definition: CallGraph.h:98
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
llvm::CallGraphPrinterPass::CallGraphPrinterPass
CallGraphPrinterPass(raw_ostream &OS)
Definition: CallGraph.h:322
llvm::CallGraphNode
A node in the call graph for a module.
Definition: CallGraph.h:166
llvm::GraphTraits< const CallGraph * >::PairTy
std::pair< const Function *const, std::unique_ptr< CallGraphNode > > PairTy
Definition: CallGraph.h:505
llvm::AnalysisManager::Invalidator
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:661
llvm::GraphTraits< CallGraph * >::getEntryNode
static NodeRef getEntryNode(CallGraph *CGN)
Definition: CallGraph.h:480
llvm::CallGraphNode::begin
const_iterator begin() const
Definition: CallGraph.h:201
llvm::CallGraphPrinterPass
Printer pass for the CallGraphAnalysis results.
Definition: CallGraph.h:318
llvm::CallGraph::ReplaceExternalCallEdge
void ReplaceExternalCallEdge(CallGraphNode *Old, CallGraphNode *New)
Old node has been deleted, and New is to be used in its place, update the ExternalCallingNode.
Definition: CallGraph.cpp:141
llvm::CallGraphWrapperPass::print
void print(raw_ostream &o, const Module *) const override
print - Print out the internal state of the pass.
Definition: CallGraph.cpp:371
llvm::GraphTraits< const CallGraphNode * >::child_end
static ChildIteratorType child_end(NodeRef N)
Definition: CallGraph.h:463
llvm::CallGraph::print
void print(raw_ostream &OS) const
Definition: CallGraph.cpp:115
llvm::CallGraph::populateCallGraphNode
void populateCallGraphNode(CallGraphNode *CGN)
Populate CGN based on the calls inside the associated function.
Definition: CallGraph.cpp:89
llvm::CallGraphNode::empty
bool empty() const
Definition: CallGraph.h:203
llvm::CallGraphNode::removeAllCalledFunctions
void removeAllCalledFunctions()
Removes all edges from this CallGraphNode to any functions it calls.
Definition: CallGraph.h:227
const
aarch64 promote const
Definition: AArch64PromoteConstant.cpp:232
llvm::GraphTraits< CallGraphNode * >::CGNGetValue
static CallGraphNode * CGNGetValue(CGNPairTy P)
Definition: CallGraph.h:433
llvm::AnalysisKey
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:69
llvm::CallGraphWrapperPass
The ModulePass which wraps up a CallGraph and the logic to build it.
Definition: CallGraph.h:345
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::CallGraphWrapperPass::begin
iterator begin()
Definition: CallGraph.h:365
llvm::GraphTraits< const CallGraphNode * >::child_begin
static ChildIteratorType child_begin(NodeRef N)
Definition: CallGraph.h:459
llvm::GraphTraits< const CallGraph * >::getEntryNode
static NodeRef getEntryNode(const CallGraph *CGN)
Definition: CallGraph.h:507
G
#define G(x, y, z)
Definition: MD5.cpp:56
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:853
llvm::CallGraph::removeFunctionFromModule
Function * removeFunctionFromModule(CallGraphNode *CGN)
Unlink the function from this module, returning it.
Definition: CallGraph.cpp:157
llvm::CallGraphWrapperPass::runOnModule
bool runOnModule(Module &M) override
runOnModule - Virtual method overriden by subclasses to process the module being operated on.
Definition: CallGraph.cpp:358
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
llvm::CallGraphWrapperPass::ID
static char ID
Definition: CallGraph.h:349
llvm::AnalysisInfoMixin
A CRTP mix-in that provides informational APIs needed for analysis passes.
Definition: PassManager.h:394
llvm::CallGraphWrapperPass::const_iterator
CallGraph::const_iterator const_iterator
Definition: CallGraph.h:360
llvm::CallGraphNode::const_iterator
std::vector< CallRecord >::const_iterator const_iterator
Definition: CallGraph.h:194
llvm::GraphTraits< const CallGraphNode * >::child_edge_begin
static ChildEdgeIteratorType child_edge_begin(NodeRef N)
Definition: CallGraph.h:467
llvm::CallGraph::operator[]
const CallGraphNode * operator[](const Function *F) const
Returns the call graph node for the provided function.
Definition: CallGraph.h:112
llvm::CallGraph::addToCallGraph
void addToCallGraph(Function *F)
Add a function to the call graph, and link the node to all of the functions that it calls.
Definition: CallGraph.cpp:75
Module
Machine Check Debug Module
Definition: MachineCheckDebugify.cpp:122
ValueHandle.h
llvm::CallGraphNode::getFunction
Function * getFunction() const
Returns the function that this call graph node represents.
Definition: CallGraph.h:197
llvm::CallGraphWrapperPass::CallGraphWrapperPass
CallGraphWrapperPass()
Definition: CallGraph.cpp:348
llvm::CallGraphNode::removeOneAbstractEdgeTo
void removeOneAbstractEdgeTo(CallGraphNode *Callee)
Removes one edge associated with a null callsite from this node to the specified callee function.
Definition: CallGraph.cpp:241
llvm::CallGraph::CallGraph
CallGraph(Module &M)
Definition: CallGraph.cpp:32
llvm::CallGraphWrapperPass::operator[]
CallGraphNode * operator[](const Function *F)
Returns the call graph node for the provided function.
Definition: CallGraph.h:376
llvm::GraphTraits< const CallGraphNode * >::child_edge_end
static ChildEdgeIteratorType child_edge_end(NodeRef N)
Definition: CallGraph.h:470
llvm::GraphTraits< const CallGraphNode * >::edge_dest
static NodeRef edge_dest(EdgeRef E)
Definition: CallGraph.h:472
llvm::CallGraphWrapperPass::operator[]
const CallGraphNode * operator[](const Function *F) const
Returns the call graph node for the provided function.
Definition: CallGraph.h:371
llvm::GraphTraits< const CallGraph * >::nodes_end
static nodes_iterator nodes_end(const CallGraph *CG)
Definition: CallGraph.h:523
PassManager.h
llvm::CallGraph::operator[]
CallGraphNode * operator[](const Function *F)
Returns the call graph node for the provided function.
Definition: CallGraph.h:119
llvm::CallGraph::getModule
Module & getModule() const
Returns the module the call graph corresponds to.
Definition: CallGraph.h:101
llvm::GraphTraits< CallGraph * >::CGGetValuePtr
static CallGraphNode * CGGetValuePtr(const PairTy &P)
Definition: CallGraph.h:484
llvm::GraphTraits< CallGraphNode * >
Definition: CallGraph.h:428
llvm::GraphTraits< const CallGraphNode * >::ChildEdgeIteratorType
CallGraphNode::const_iterator ChildEdgeIteratorType
Definition: CallGraph.h:457
llvm::CallGraphNode::CallRecord
std::pair< std::optional< WeakTrackingVH >, CallGraphNode * > CallRecord
A pair of the calling instruction (a call or invoke) and the call graph node being called.
Definition: CallGraph.h:178
llvm::CallGraphNode::print
void print(raw_ostream &OS) const
Definition: CallGraph.cpp:184
N
#define N
llvm::GraphTraits< const CallGraphNode * >::EdgeRef
const CallGraphNode::CallRecord & EdgeRef
Definition: CallGraph.h:450
llvm::CallGraphNode::size
unsigned size() const
Definition: CallGraph.h:204
llvm::CallBase
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1184
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
llvm::CallGraphWrapperPass::getModule
Module & getModule() const
Returns the module the call graph corresponds to.
Definition: CallGraph.h:363
llvm::CallGraphWrapperPass::getCallsExternalNode
CallGraphNode * getCallsExternalNode() const
Definition: CallGraph.h:384
llvm::GraphTraits
Definition: GraphTraits.h:37
llvm::CallGraphAnalysis::run
CallGraph run(Module &M, ModuleAnalysisManager &)
Compute the CallGraph for the module M.
Definition: CallGraph.h:314
llvm::CallGraphWrapperPass::dump
void dump() const
Definition: CallGraph.cpp:383
llvm::CallGraph::getCallsExternalNode
CallGraphNode * getCallsExternalNode() const
Definition: CallGraph.h:129
llvm::CallGraph::begin
iterator begin()
Definition: CallGraph.h:106
llvm::GraphTraits< CallGraph * >::PairTy
std::pair< const Function *const, std::unique_ptr< CallGraphNode > > PairTy
Definition: CallGraph.h:478
llvm::CallGraphNode::operator[]
CallGraphNode * operator[](unsigned i) const
Returns the i'th called function.
Definition: CallGraph.h:211
llvm::CallGraphWrapperPass::releaseMemory
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
llvm::CallGraphNode::stealCalledFunctionsFrom
void stealCalledFunctionsFrom(CallGraphNode *N)
Moves all the callee information from N to this node.
Definition: CallGraph.h:235
llvm::codeview::PublicSymFlags::Function
@ Function
llvm::CallGraphWrapperPass::begin
const_iterator begin() const
Definition: CallGraph.h:367
llvm::CallGraphNode::begin
iterator begin()
Definition: CallGraph.h:199
llvm::CallGraphNode::replaceCallEdge
void replaceCallEdge(CallBase &Call, CallBase &NewCall, CallGraphNode *NewNode)
Replaces the edge in the node for the specified call site with a new one.
Definition: CallGraph.cpp:257
llvm::CallGraphWrapperPass::getOrInsertFunction
CallGraphNode * getOrInsertFunction(const Function *F)
Similar to operator[], but this will insert a new CallGraphNode for F if one does not already exist.
Definition: CallGraph.h:405
llvm::GraphTraits< CallGraph * >::nodes_begin
static nodes_iterator nodes_begin(CallGraph *CG)
Definition: CallGraph.h:492