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