LLVM  16.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<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  assert(!Call || !Call->getCalledFunction() ||
244  !Call->getCalledFunction()->isIntrinsic() ||
245  !Intrinsic::isLeaf(Call->getCalledFunction()->getIntrinsicID()));
246  CalledFunctions.emplace_back(
248  M->AddRef();
249  }
250 
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.
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 
280 private:
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.
304 class CallGraphAnalysis : public AnalysisInfoMixin<CallGraphAnalysis> {
306 
307  static AnalysisKey Key;
308 
309 public:
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.
317 };
318 
319 /// Printer pass for the \c CallGraphAnalysis results.
320 class CallGraphPrinterPass : public PassInfoMixin<CallGraphPrinterPass> {
321  raw_ostream &OS;
322 
323 public:
324  explicit CallGraphPrinterPass(raw_ostream &OS) : OS(OS) {}
325 
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.
337  std::unique_ptr<CallGraph> G;
338 
339 public:
340  static char ID; // Class identification, replacement for typeinfo
341 
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 
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.
372  return G->getExternalCallingNode();
373  }
374 
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.
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.
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.
419 template <> struct GraphTraits<CallGraphNode *> {
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 
430  return ChildIteratorType(N->begin(), &CGNGetValue);
431  }
432 
434  return ChildIteratorType(N->end(), &CGNGetValue);
435  }
436 };
437 
438 template <> struct GraphTraits<const CallGraphNode *> {
439  using NodeRef = const CallGraphNode *;
442 
443  static NodeRef getEntryNode(const CallGraphNode *CGN) { return CGN; }
444  static const CallGraphNode *CGNGetValue(CGNPairTy P) { return P.second; }
445 
446  using ChildIteratorType =
449 
451  return ChildIteratorType(N->begin(), &CGNGetValue);
452  }
453 
455  return ChildIteratorType(N->end(), &CGNGetValue);
456  }
457 
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 
466 template <>
468  using PairTy =
469  std::pair<const Function *const, std::unique_ptr<CallGraphNode>>;
470 
472  return CGN->getExternalCallingNode(); // Start at the external node!
473  }
474 
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 
484  return nodes_iterator(CG->begin(), &CGGetValuePtr);
485  }
486 
488  return nodes_iterator(CG->end(), &CGGetValuePtr);
489  }
490 };
491 
492 template <>
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 
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
llvm::CallGraphNode::removeAnyCallEdgeTo
void removeAnyCallEdgeTo(CallGraphNode *Callee)
Removes all call edges from this node to the specified callee function.
Definition: CallGraph.cpp:232
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:429
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:304
llvm::CallGraphWrapperPass::end
const_iterator end() const
Definition: CallGraph.h:359
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:60
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::CallGraphNode::CallRecord
std::pair< 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::CallGraphWrapperPass::getCallGraph
const CallGraph & getCallGraph() const
The internal CallGraph around which the rest of this interface is wrapped.
Definition: CallGraph.h:347
llvm::GraphTraits< const CallGraphNode * >::getEntryNode
static NodeRef getEntryNode(const CallGraphNode *CGN)
Definition: CallGraph.h:443
llvm::GraphTraits< const CallGraphNode * >::CGNGetValue
static const CallGraphNode * CGNGetValue(CGNPairTy P)
Definition: CallGraph.h:444
llvm::CallGraphNode::removeCallEdgeFor
void removeCallEdgeFor(CallBase &Call)
Removes the edge in the node for the specified call site.
Definition: CallGraph.cpp:212
llvm::GraphTraits< CallGraphNode * >::child_end
static ChildIteratorType child_end(NodeRef N)
Definition: CallGraph.h:433
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:141
llvm::CallGraphWrapperPass::removeFunctionFromModule
Function * removeFunctionFromModule(CallGraphNode *CGN)
Unlink the function from this module, returning it.
Definition: CallGraph.h:390
llvm::CallGraph::~CallGraph
~CallGraph()
Definition: CallGraph.cpp:54
llvm::Optional
Definition: APInt.h:33
llvm::mapped_iterator
Definition: STLExtras.h:286
llvm::CallGraphNode::removeCallEdge
void removeCallEdge(iterator I)
Definition: CallGraph.h:251
llvm::GraphTraits< CallGraphNode * >::getEntryNode
static NodeRef getEntryNode(CallGraphNode *CGN)
Definition: CallGraph.h:423
llvm::GraphTraits< const CallGraph * >::nodes_begin
static nodes_iterator nodes_begin(const CallGraph *CG)
Definition: CallGraph.h:510
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:309
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:173
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:329
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:357
llvm::CallGraph::end
iterator end()
Definition: CallGraph.h:107
llvm::GraphTraits< CallGraphNode * >::CGNPairTy
CallGraphNode::CallRecord CGNPairTy
Definition: CallGraph.h:421
Intrinsics.h
InstrTypes.h
llvm::GraphTraits< const CallGraphNode * >::CGNPairTy
CallGraphNode::CallRecord CGNPairTy
Definition: CallGraph.h:440
llvm::CallGraphNode::dump
void dump() const
Print out this call graph node.
Definition: CallGraph.cpp:206
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::CallGraphWrapperPass::iterator
CallGraph::iterator iterator
Definition: CallGraph.h:350
llvm::CallGraphWrapperPass::getExternalCallingNode
CallGraphNode * getExternalCallingNode() const
Returns the CallGraphNode which is used to represent undetermined calls into the callgraph.
Definition: CallGraph.h:371
llvm::GraphTraits< CallGraph * >::nodes_end
static nodes_iterator nodes_end(CallGraph *CG)
Definition: CallGraph.h:487
llvm::CallGraphWrapperPass::getCallGraph
CallGraph & getCallGraph()
Definition: CallGraph.h:348
llvm::GraphTraits< const CallGraph * >::CGGetValuePtr
static const CallGraphNode * CGGetValuePtr(const PairTy &P)
Definition: CallGraph.h:502
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:324
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:496
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:471
llvm::CallGraphNode::begin
const_iterator begin() const
Definition: CallGraph.h:201
llvm::CallGraphPrinterPass
Printer pass for the CallGraphAnalysis results.
Definition: CallGraph.h:320
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:144
llvm::CallGraphWrapperPass::print
void print(raw_ostream &o, const Module *) const override
print - Print out the internal state of the pass.
Definition: CallGraph.cpp:346
llvm::GraphTraits< const CallGraphNode * >::child_end
static ChildIteratorType child_end(NodeRef N)
Definition: CallGraph.h:454
llvm::CallGraph::print
void print(raw_ostream &OS) const
Definition: CallGraph.cpp:118
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:424
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:336
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::CallGraphWrapperPass::begin
iterator begin()
Definition: CallGraph.h:356
llvm::GraphTraits< const CallGraphNode * >::child_begin
static ChildIteratorType child_begin(NodeRef N)
Definition: CallGraph.h:450
llvm::GraphTraits< const CallGraph * >::getEntryNode
static NodeRef getEntryNode(const CallGraph *CGN)
Definition: CallGraph.h:498
G
#define G(x, y, z)
Definition: MD5.cpp:56
llvm::Intrinsic::isLeaf
bool isLeaf(ID id)
Returns true if the intrinsic is a leaf, i.e.
Definition: Function.cpp:1404
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:160
llvm::CallGraphWrapperPass::runOnModule
bool runOnModule(Module &M) override
runOnModule - Virtual method overriden by subclasses to process the module being operated on.
Definition: CallGraph.cpp:333
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:340
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:351
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:458
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:323
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:244
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:367
llvm::GraphTraits< const CallGraphNode * >::child_edge_end
static ChildEdgeIteratorType child_edge_end(NodeRef N)
Definition: CallGraph.h:461
llvm::GraphTraits< const CallGraphNode * >::edge_dest
static NodeRef edge_dest(EdgeRef E)
Definition: CallGraph.h:463
llvm::CallGraphWrapperPass::operator[]
const CallGraphNode * operator[](const Function *F) const
Returns the call graph node for the provided function.
Definition: CallGraph.h:362
llvm::GraphTraits< const CallGraph * >::nodes_end
static nodes_iterator nodes_end(const CallGraph *CG)
Definition: CallGraph.h:514
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:475
llvm::GraphTraits< CallGraphNode * >
Definition: CallGraph.h:419
llvm::GraphTraits< const CallGraphNode * >::ChildEdgeIteratorType
CallGraphNode::const_iterator ChildEdgeIteratorType
Definition: CallGraph.h:448
llvm::CallGraphNode::print
void print(raw_ostream &OS) const
Definition: CallGraph.cpp:187
N
#define N
llvm::GraphTraits< const CallGraphNode * >::EdgeRef
const CallGraphNode::CallRecord & EdgeRef
Definition: CallGraph.h:441
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:1174
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:354
llvm::CallGraphWrapperPass::getCallsExternalNode
CallGraphNode * getCallsExternalNode() const
Definition: CallGraph.h:375
llvm::GraphTraits
Definition: GraphTraits.h:37
llvm::CallGraphAnalysis::run
CallGraph run(Module &M, ModuleAnalysisManager &)
Compute the CallGraph for the module M.
Definition: CallGraph.h:316
llvm::CallGraphWrapperPass::dump
void dump() const
Definition: CallGraph.cpp:358
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:469
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:358
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:260
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:396
llvm::GraphTraits< CallGraph * >::nodes_begin
static nodes_iterator nodes_begin(CallGraph *CG)
Definition: CallGraph.h:483