LLVM  16.0.0git
LazyCallGraph.h
Go to the documentation of this file.
1 //===- LazyCallGraph.h - Analysis of 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 /// Implements a lazy call graph analysis and related passes for the new pass
11 /// manager.
12 ///
13 /// NB: This is *not* a traditional call graph! It is a graph which models both
14 /// the current calls and potential calls. As a consequence there are many
15 /// edges in this call graph that do not correspond to a 'call' or 'invoke'
16 /// instruction.
17 ///
18 /// The primary use cases of this graph analysis is to facilitate iterating
19 /// across the functions of a module in ways that ensure all callees are
20 /// visited prior to a caller (given any SCC constraints), or vice versa. As
21 /// such is it particularly well suited to organizing CGSCC optimizations such
22 /// as inlining, outlining, argument promotion, etc. That is its primary use
23 /// case and motivates the design. It may not be appropriate for other
24 /// purposes. The use graph of functions or some other conservative analysis of
25 /// call instructions may be interesting for optimizations and subsequent
26 /// analyses which don't work in the context of an overly specified
27 /// potential-call-edge graph.
28 ///
29 /// To understand the specific rules and nature of this call graph analysis,
30 /// see the documentation of the \c LazyCallGraph below.
31 ///
32 //===----------------------------------------------------------------------===//
33 
34 #ifndef LLVM_ANALYSIS_LAZYCALLGRAPH_H
35 #define LLVM_ANALYSIS_LAZYCALLGRAPH_H
36 
37 #include "llvm/ADT/ArrayRef.h"
38 #include "llvm/ADT/DenseMap.h"
39 #include "llvm/ADT/Optional.h"
41 #include "llvm/ADT/SetVector.h"
42 #include "llvm/ADT/SmallVector.h"
43 #include "llvm/ADT/StringRef.h"
44 #include "llvm/ADT/iterator.h"
47 #include "llvm/IR/PassManager.h"
48 #include "llvm/Support/Allocator.h"
50 #include <cassert>
51 #include <iterator>
52 #include <optional>
53 #include <string>
54 #include <utility>
55 
56 namespace llvm {
57 
58 class Constant;
59 class Function;
60 template <class GraphType> struct GraphTraits;
61 class Module;
62 class TargetLibraryInfo;
63 class Value;
64 
65 /// A lazily constructed view of the call graph of a module.
66 ///
67 /// With the edges of this graph, the motivating constraint that we are
68 /// attempting to maintain is that function-local optimization, CGSCC-local
69 /// optimizations, and optimizations transforming a pair of functions connected
70 /// by an edge in the graph, do not invalidate a bottom-up traversal of the SCC
71 /// DAG. That is, no optimizations will delete, remove, or add an edge such
72 /// that functions already visited in a bottom-up order of the SCC DAG are no
73 /// longer valid to have visited, or such that functions not yet visited in
74 /// a bottom-up order of the SCC DAG are not required to have already been
75 /// visited.
76 ///
77 /// Within this constraint, the desire is to minimize the merge points of the
78 /// SCC DAG. The greater the fanout of the SCC DAG and the fewer merge points
79 /// in the SCC DAG, the more independence there is in optimizing within it.
80 /// There is a strong desire to enable parallelization of optimizations over
81 /// the call graph, and both limited fanout and merge points will (artificially
82 /// in some cases) limit the scaling of such an effort.
83 ///
84 /// To this end, graph represents both direct and any potential resolution to
85 /// an indirect call edge. Another way to think about it is that it represents
86 /// both the direct call edges and any direct call edges that might be formed
87 /// through static optimizations. Specifically, it considers taking the address
88 /// of a function to be an edge in the call graph because this might be
89 /// forwarded to become a direct call by some subsequent function-local
90 /// optimization. The result is that the graph closely follows the use-def
91 /// edges for functions. Walking "up" the graph can be done by looking at all
92 /// of the uses of a function.
93 ///
94 /// The roots of the call graph are the external functions and functions
95 /// escaped into global variables. Those functions can be called from outside
96 /// of the module or via unknowable means in the IR -- we may not be able to
97 /// form even a potential call edge from a function body which may dynamically
98 /// load the function and call it.
99 ///
100 /// This analysis still requires updates to remain valid after optimizations
101 /// which could potentially change the set of potential callees. The
102 /// constraints it operates under only make the traversal order remain valid.
103 ///
104 /// The entire analysis must be re-computed if full interprocedural
105 /// optimizations run at any point. For example, globalopt completely
106 /// invalidates the information in this analysis.
107 ///
108 /// FIXME: This class is named LazyCallGraph in a lame attempt to distinguish
109 /// it from the existing CallGraph. At some point, it is expected that this
110 /// will be the only call graph and it will be renamed accordingly.
112 public:
113  class Node;
114  class EdgeSequence;
115  class SCC;
116  class RefSCC;
117 
118  /// A class used to represent edges in the call graph.
119  ///
120  /// The lazy call graph models both *call* edges and *reference* edges. Call
121  /// edges are much what you would expect, and exist when there is a 'call' or
122  /// 'invoke' instruction of some function. Reference edges are also tracked
123  /// along side these, and exist whenever any instruction (transitively
124  /// through its operands) references a function. All call edges are
125  /// inherently reference edges, and so the reference graph forms a superset
126  /// of the formal call graph.
127  ///
128  /// All of these forms of edges are fundamentally represented as outgoing
129  /// edges. The edges are stored in the source node and point at the target
130  /// node. This allows the edge structure itself to be a very compact data
131  /// structure: essentially a tagged pointer.
132  class Edge {
133  public:
134  /// The kind of edge in the graph.
135  enum Kind : bool { Ref = false, Call = true };
136 
137  Edge();
138  explicit Edge(Node &N, Kind K);
139 
140  /// Test whether the edge is null.
141  ///
142  /// This happens when an edge has been deleted. We leave the edge objects
143  /// around but clear them.
144  explicit operator bool() const;
145 
146  /// Returns the \c Kind of the edge.
147  Kind getKind() const;
148 
149  /// Test whether the edge represents a direct call to a function.
150  ///
151  /// This requires that the edge is not null.
152  bool isCall() const;
153 
154  /// Get the call graph node referenced by this edge.
155  ///
156  /// This requires that the edge is not null.
157  Node &getNode() const;
158 
159  /// Get the function referenced by this edge.
160  ///
161  /// This requires that the edge is not null.
162  Function &getFunction() const;
163 
164  private:
166  friend class LazyCallGraph::RefSCC;
167 
169 
170  void setKind(Kind K) { Value.setInt(K); }
171  };
172 
173  /// The edge sequence object.
174  ///
175  /// This typically exists entirely within the node but is exposed as
176  /// a separate type because a node doesn't initially have edges. An explicit
177  /// population step is required to produce this sequence at first and it is
178  /// then cached in the node. It is also used to represent edges entering the
179  /// graph from outside the module to model the graph's roots.
180  ///
181  /// The sequence itself both iterable and indexable. The indexes remain
182  /// stable even as the sequence mutates (including removal).
183  class EdgeSequence {
184  friend class LazyCallGraph;
185  friend class LazyCallGraph::Node;
186  friend class LazyCallGraph::RefSCC;
187 
190 
191  public:
192  /// An iterator used for the edges to both entry nodes and child nodes.
193  class iterator
194  : public iterator_adaptor_base<iterator, VectorImplT::iterator,
195  std::forward_iterator_tag> {
196  friend class LazyCallGraph;
197  friend class LazyCallGraph::Node;
198 
200 
201  // Build the iterator for a specific position in the edge list.
203  : iterator_adaptor_base(BaseI), E(E) {
204  while (I != E && !*I)
205  ++I;
206  }
207 
208  public:
209  iterator() = default;
210 
211  using iterator_adaptor_base::operator++;
213  do {
214  ++I;
215  } while (I != E && !*I);
216  return *this;
217  }
218  };
219 
220  /// An iterator over specifically call edges.
221  ///
222  /// This has the same iteration properties as the \c iterator, but
223  /// restricts itself to edges which represent actual calls.
225  : public iterator_adaptor_base<call_iterator, VectorImplT::iterator,
226  std::forward_iterator_tag> {
227  friend class LazyCallGraph;
228  friend class LazyCallGraph::Node;
229 
231 
232  /// Advance the iterator to the next valid, call edge.
233  void advanceToNextEdge() {
234  while (I != E && (!*I || !I->isCall()))
235  ++I;
236  }
237 
238  // Build the iterator for a specific position in the edge list.
240  : iterator_adaptor_base(BaseI), E(E) {
241  advanceToNextEdge();
242  }
243 
244  public:
245  call_iterator() = default;
246 
247  using iterator_adaptor_base::operator++;
249  ++I;
250  advanceToNextEdge();
251  return *this;
252  }
253  };
254 
255  iterator begin() { return iterator(Edges.begin(), Edges.end()); }
256  iterator end() { return iterator(Edges.end(), Edges.end()); }
257 
259  assert(EdgeIndexMap.find(&N) != EdgeIndexMap.end() && "No such edge!");
260  auto &E = Edges[EdgeIndexMap.find(&N)->second];
261  assert(E && "Dead or null edge!");
262  return E;
263  }
264 
266  auto EI = EdgeIndexMap.find(&N);
267  if (EI == EdgeIndexMap.end())
268  return nullptr;
269  auto &E = Edges[EI->second];
270  return E ? &E : nullptr;
271  }
272 
274  return call_iterator(Edges.begin(), Edges.end());
275  }
276  call_iterator call_end() { return call_iterator(Edges.end(), Edges.end()); }
277 
279  return make_range(call_begin(), call_end());
280  }
281 
282  bool empty() {
283  for (auto &E : Edges)
284  if (E)
285  return false;
286 
287  return true;
288  }
289 
290  private:
291  VectorT Edges;
292  DenseMap<Node *, int> EdgeIndexMap;
293 
294  EdgeSequence() = default;
295 
296  /// Internal helper to insert an edge to a node.
297  void insertEdgeInternal(Node &ChildN, Edge::Kind EK);
298 
299  /// Internal helper to change an edge kind.
300  void setEdgeKind(Node &ChildN, Edge::Kind EK);
301 
302  /// Internal helper to remove the edge to the given function.
303  bool removeEdgeInternal(Node &ChildN);
304  };
305 
306  /// A node in the call graph.
307  ///
308  /// This represents a single node. Its primary roles are to cache the list of
309  /// callees, de-duplicate and provide fast testing of whether a function is a
310  /// callee, and facilitate iteration of child nodes in the graph.
311  ///
312  /// The node works much like an optional in order to lazily populate the
313  /// edges of each node. Until populated, there are no edges. Once populated,
314  /// you can access the edges by dereferencing the node or using the `->`
315  /// operator as if the node was an `std::optional<EdgeSequence>`.
316  class Node {
317  friend class LazyCallGraph;
318  friend class LazyCallGraph::RefSCC;
319 
320  public:
321  LazyCallGraph &getGraph() const { return *G; }
322 
323  Function &getFunction() const { return *F; }
324 
325  StringRef getName() const { return F->getName(); }
326 
327  /// Equality is defined as address equality.
328  bool operator==(const Node &N) const { return this == &N; }
329  bool operator!=(const Node &N) const { return !operator==(N); }
330 
331  /// Tests whether the node has been populated with edges.
332  bool isPopulated() const { return Edges.has_value(); }
333 
334  /// Tests whether this is actually a dead node and no longer valid.
335  ///
336  /// Users rarely interact with nodes in this state and other methods are
337  /// invalid. This is used to model a node in an edge list where the
338  /// function has been completely removed.
339  bool isDead() const {
340  assert(!G == !F &&
341  "Both graph and function pointers should be null or non-null.");
342  return !G;
343  }
344 
345  // We allow accessing the edges by dereferencing or using the arrow
346  // operator, essentially wrapping the internal optional.
348  // Rip const off because the node itself isn't changing here.
349  return const_cast<EdgeSequence &>(*Edges);
350  }
351  EdgeSequence *operator->() const { return &**this; }
352 
353  /// Populate the edges of this node if necessary.
354  ///
355  /// The first time this is called it will populate the edges for this node
356  /// in the graph. It does this by scanning the underlying function, so once
357  /// this is done, any changes to that function must be explicitly reflected
358  /// in updates to the graph.
359  ///
360  /// \returns the populated \c EdgeSequence to simplify walking it.
361  ///
362  /// This will not update or re-scan anything if called repeatedly. Instead,
363  /// the edge sequence is cached and returned immediately on subsequent
364  /// calls.
366  if (Edges)
367  return *Edges;
368 
369  return populateSlow();
370  }
371 
372  private:
373  LazyCallGraph *G;
374  Function *F;
375 
376  // We provide for the DFS numbering and Tarjan walk lowlink numbers to be
377  // stored directly within the node. These are both '-1' when nodes are part
378  // of an SCC (or RefSCC), or '0' when not yet reached in a DFS walk.
379  int DFSNumber = 0;
380  int LowLink = 0;
381 
382  std::optional<EdgeSequence> Edges;
383 
384  /// Basic constructor implements the scanning of F into Edges and
385  /// EdgeIndexMap.
386  Node(LazyCallGraph &G, Function &F) : G(&G), F(&F) {}
387 
388  /// Implementation of the scan when populating.
389  EdgeSequence &populateSlow();
390 
391  /// Internal helper to directly replace the function with a new one.
392  ///
393  /// This is used to facilitate transformations which need to replace the
394  /// formal Function object but directly move the body and users from one to
395  /// the other.
396  void replaceFunction(Function &NewF);
397 
398  void clear() { Edges.reset(); }
399 
400  /// Print the name of this node's function.
401  friend raw_ostream &operator<<(raw_ostream &OS, const Node &N) {
402  return OS << N.F->getName();
403  }
404 
405  /// Dump the name of this node's function to stderr.
406  void dump() const;
407  };
408 
409  /// An SCC of the call graph.
410  ///
411  /// This represents a Strongly Connected Component of the direct call graph
412  /// -- ignoring indirect calls and function references. It stores this as
413  /// a collection of call graph nodes. While the order of nodes in the SCC is
414  /// stable, it is not any particular order.
415  ///
416  /// The SCCs are nested within a \c RefSCC, see below for details about that
417  /// outer structure. SCCs do not support mutation of the call graph, that
418  /// must be done through the containing \c RefSCC in order to fully reason
419  /// about the ordering and connections of the graph.
421  friend class LazyCallGraph;
422  friend class LazyCallGraph::Node;
423 
424  RefSCC *OuterRefSCC;
426 
427  template <typename NodeRangeT>
428  SCC(RefSCC &OuterRefSCC, NodeRangeT &&Nodes)
429  : OuterRefSCC(&OuterRefSCC), Nodes(std::forward<NodeRangeT>(Nodes)) {}
430 
431  void clear() {
432  OuterRefSCC = nullptr;
433  Nodes.clear();
434  }
435 
436  /// Print a short description useful for debugging or logging.
437  ///
438  /// We print the function names in the SCC wrapped in '()'s and skipping
439  /// the middle functions if there are a large number.
440  //
441  // Note: this is defined inline to dodge issues with GCC's interpretation
442  // of enclosing namespaces for friend function declarations.
443  friend raw_ostream &operator<<(raw_ostream &OS, const SCC &C) {
444  OS << '(';
445  int I = 0;
446  for (LazyCallGraph::Node &N : C) {
447  if (I > 0)
448  OS << ", ";
449  // Elide the inner elements if there are too many.
450  if (I > 8) {
451  OS << "..., " << *C.Nodes.back();
452  break;
453  }
454  OS << N;
455  ++I;
456  }
457  OS << ')';
458  return OS;
459  }
460 
461  /// Dump a short description of this SCC to stderr.
462  void dump() const;
463 
464 #if !defined(NDEBUG) || defined(EXPENSIVE_CHECKS)
465  /// Verify invariants about the SCC.
466  ///
467  /// This will attempt to validate all of the basic invariants within an
468  /// SCC, but not that it is a strongly connected component per se.
469  /// Primarily useful while building and updating the graph to check that
470  /// basic properties are in place rather than having inexplicable crashes
471  /// later.
472  void verify();
473 #endif
474 
475  public:
477 
478  iterator begin() const { return Nodes.begin(); }
479  iterator end() const { return Nodes.end(); }
480 
481  int size() const { return Nodes.size(); }
482 
483  RefSCC &getOuterRefSCC() const { return *OuterRefSCC; }
484 
485  /// Test if this SCC is a parent of \a C.
486  ///
487  /// Note that this is linear in the number of edges departing the current
488  /// SCC.
489  bool isParentOf(const SCC &C) const;
490 
491  /// Test if this SCC is an ancestor of \a C.
492  ///
493  /// Note that in the worst case this is linear in the number of edges
494  /// departing the current SCC and every SCC in the entire graph reachable
495  /// from this SCC. Thus this very well may walk every edge in the entire
496  /// call graph! Do not call this in a tight loop!
497  bool isAncestorOf(const SCC &C) const;
498 
499  /// Test if this SCC is a child of \a C.
500  ///
501  /// See the comments for \c isParentOf for detailed notes about the
502  /// complexity of this routine.
503  bool isChildOf(const SCC &C) const { return C.isParentOf(*this); }
504 
505  /// Test if this SCC is a descendant of \a C.
506  ///
507  /// See the comments for \c isParentOf for detailed notes about the
508  /// complexity of this routine.
509  bool isDescendantOf(const SCC &C) const { return C.isAncestorOf(*this); }
510 
511  /// Provide a short name by printing this SCC to a std::string.
512  ///
513  /// This copes with the fact that we don't have a name per se for an SCC
514  /// while still making the use of this in debugging and logging useful.
515  std::string getName() const {
516  std::string Name;
518  OS << *this;
519  OS.flush();
520  return Name;
521  }
522  };
523 
524  /// A RefSCC of the call graph.
525  ///
526  /// This models a Strongly Connected Component of function reference edges in
527  /// the call graph. As opposed to actual SCCs, these can be used to scope
528  /// subgraphs of the module which are independent from other subgraphs of the
529  /// module because they do not reference it in any way. This is also the unit
530  /// where we do mutation of the graph in order to restrict mutations to those
531  /// which don't violate this independence.
532  ///
533  /// A RefSCC contains a DAG of actual SCCs. All the nodes within the RefSCC
534  /// are necessarily within some actual SCC that nests within it. Since
535  /// a direct call *is* a reference, there will always be at least one RefSCC
536  /// around any SCC.
537  ///
538  /// Spurious ref edges, meaning ref edges that still exist in the call graph
539  /// even though the corresponding IR reference no longer exists, are allowed.
540  /// This is mostly to support argument promotion, which can modify a caller to
541  /// no longer pass a function. The only place that needs to specially handle
542  /// this is deleting a dead function/node, otherwise the dead ref edges are
543  /// automatically removed when visiting the function/node no longer containing
544  /// the ref edge.
545  class RefSCC {
546  friend class LazyCallGraph;
547  friend class LazyCallGraph::Node;
548 
549  LazyCallGraph *G;
550 
551  /// A postorder list of the inner SCCs.
553 
554  /// A map from SCC to index in the postorder list.
555  SmallDenseMap<SCC *, int, 4> SCCIndices;
556 
557  /// Fast-path constructor. RefSCCs should instead be constructed by calling
558  /// formRefSCCFast on the graph itself.
560 
561  void clear() {
562  SCCs.clear();
563  SCCIndices.clear();
564  }
565 
566  /// Print a short description useful for debugging or logging.
567  ///
568  /// We print the SCCs wrapped in '[]'s and skipping the middle SCCs if
569  /// there are a large number.
570  //
571  // Note: this is defined inline to dodge issues with GCC's interpretation
572  // of enclosing namespaces for friend function declarations.
573  friend raw_ostream &operator<<(raw_ostream &OS, const RefSCC &RC) {
574  OS << '[';
575  int I = 0;
576  for (LazyCallGraph::SCC &C : RC) {
577  if (I > 0)
578  OS << ", ";
579  // Elide the inner elements if there are too many.
580  if (I > 4) {
581  OS << "..., " << *RC.SCCs.back();
582  break;
583  }
584  OS << C;
585  ++I;
586  }
587  OS << ']';
588  return OS;
589  }
590 
591  /// Dump a short description of this RefSCC to stderr.
592  void dump() const;
593 
594 #if !defined(NDEBUG) || defined(EXPENSIVE_CHECKS)
595  /// Verify invariants about the RefSCC and all its SCCs.
596  ///
597  /// This will attempt to validate all of the invariants *within* the
598  /// RefSCC, but not that it is a strongly connected component of the larger
599  /// graph. This makes it useful even when partially through an update.
600  ///
601  /// Invariants checked:
602  /// - SCCs and their indices match.
603  /// - The SCCs list is in fact in post-order.
604  void verify();
605 #endif
606 
607  public:
610  using parent_iterator =
612 
613  iterator begin() const { return SCCs.begin(); }
614  iterator end() const { return SCCs.end(); }
615 
616  ssize_t size() const { return SCCs.size(); }
617 
618  SCC &operator[](int Idx) { return *SCCs[Idx]; }
619 
620  iterator find(SCC &C) const {
621  return SCCs.begin() + SCCIndices.find(&C)->second;
622  }
623 
624  /// Test if this RefSCC is a parent of \a RC.
625  ///
626  /// CAUTION: This method walks every edge in the \c RefSCC, it can be very
627  /// expensive.
628  bool isParentOf(const RefSCC &RC) const;
629 
630  /// Test if this RefSCC is an ancestor of \a RC.
631  ///
632  /// CAUTION: This method walks the directed graph of edges as far as
633  /// necessary to find a possible path to the argument. In the worst case
634  /// this may walk the entire graph and can be extremely expensive.
635  bool isAncestorOf(const RefSCC &RC) const;
636 
637  /// Test if this RefSCC is a child of \a RC.
638  ///
639  /// CAUTION: This method walks every edge in the argument \c RefSCC, it can
640  /// be very expensive.
641  bool isChildOf(const RefSCC &RC) const { return RC.isParentOf(*this); }
642 
643  /// Test if this RefSCC is a descendant of \a RC.
644  ///
645  /// CAUTION: This method walks the directed graph of edges as far as
646  /// necessary to find a possible path from the argument. In the worst case
647  /// this may walk the entire graph and can be extremely expensive.
648  bool isDescendantOf(const RefSCC &RC) const {
649  return RC.isAncestorOf(*this);
650  }
651 
652  /// Provide a short name by printing this RefSCC to a std::string.
653  ///
654  /// This copes with the fact that we don't have a name per se for an RefSCC
655  /// while still making the use of this in debugging and logging useful.
656  std::string getName() const {
657  std::string Name;
659  OS << *this;
660  OS.flush();
661  return Name;
662  }
663 
664  ///@{
665  /// \name Mutation API
666  ///
667  /// These methods provide the core API for updating the call graph in the
668  /// presence of (potentially still in-flight) DFS-found RefSCCs and SCCs.
669  ///
670  /// Note that these methods sometimes have complex runtimes, so be careful
671  /// how you call them.
672 
673  /// Make an existing internal ref edge into a call edge.
674  ///
675  /// This may form a larger cycle and thus collapse SCCs into TargetN's SCC.
676  /// If that happens, the optional callback \p MergedCB will be invoked (if
677  /// provided) on the SCCs being merged away prior to actually performing
678  /// the merge. Note that this will never include the target SCC as that
679  /// will be the SCC functions are merged into to resolve the cycle. Once
680  /// this function returns, these merged SCCs are not in a valid state but
681  /// the pointers will remain valid until destruction of the parent graph
682  /// instance for the purpose of clearing cached information. This function
683  /// also returns 'true' if a cycle was formed and some SCCs merged away as
684  /// a convenience.
685  ///
686  /// After this operation, both SourceN's SCC and TargetN's SCC may move
687  /// position within this RefSCC's postorder list. Any SCCs merged are
688  /// merged into the TargetN's SCC in order to preserve reachability analyses
689  /// which took place on that SCC.
691  Node &SourceN, Node &TargetN,
692  function_ref<void(ArrayRef<SCC *> MergedSCCs)> MergeCB = {});
693 
694  /// Make an existing internal call edge between separate SCCs into a ref
695  /// edge.
696  ///
697  /// If SourceN and TargetN in separate SCCs within this RefSCC, changing
698  /// the call edge between them to a ref edge is a trivial operation that
699  /// does not require any structural changes to the call graph.
700  void switchTrivialInternalEdgeToRef(Node &SourceN, Node &TargetN);
701 
702  /// Make an existing internal call edge within a single SCC into a ref
703  /// edge.
704  ///
705  /// Since SourceN and TargetN are part of a single SCC, this SCC may be
706  /// split up due to breaking a cycle in the call edges that formed it. If
707  /// that happens, then this routine will insert new SCCs into the postorder
708  /// list *before* the SCC of TargetN (previously the SCC of both). This
709  /// preserves postorder as the TargetN can reach all of the other nodes by
710  /// definition of previously being in a single SCC formed by the cycle from
711  /// SourceN to TargetN.
712  ///
713  /// The newly added SCCs are added *immediately* and contiguously
714  /// prior to the TargetN SCC and return the range covering the new SCCs in
715  /// the RefSCC's postorder sequence. You can directly iterate the returned
716  /// range to observe all of the new SCCs in postorder.
717  ///
718  /// Note that if SourceN and TargetN are in separate SCCs, the simpler
719  /// routine `switchTrivialInternalEdgeToRef` should be used instead.
721  Node &TargetN);
722 
723  /// Make an existing outgoing ref edge into a call edge.
724  ///
725  /// Note that this is trivial as there are no cyclic impacts and there
726  /// remains a reference edge.
727  void switchOutgoingEdgeToCall(Node &SourceN, Node &TargetN);
728 
729  /// Make an existing outgoing call edge into a ref edge.
730  ///
731  /// This is trivial as there are no cyclic impacts and there remains
732  /// a reference edge.
733  void switchOutgoingEdgeToRef(Node &SourceN, Node &TargetN);
734 
735  /// Insert a ref edge from one node in this RefSCC to another in this
736  /// RefSCC.
737  ///
738  /// This is always a trivial operation as it doesn't change any part of the
739  /// graph structure besides connecting the two nodes.
740  ///
741  /// Note that we don't support directly inserting internal *call* edges
742  /// because that could change the graph structure and requires returning
743  /// information about what became invalid. As a consequence, the pattern
744  /// should be to first insert the necessary ref edge, and then to switch it
745  /// to a call edge if needed and handle any invalidation that results. See
746  /// the \c switchInternalEdgeToCall routine for details.
747  void insertInternalRefEdge(Node &SourceN, Node &TargetN);
748 
749  /// Insert an edge whose parent is in this RefSCC and child is in some
750  /// child RefSCC.
751  ///
752  /// There must be an existing path from the \p SourceN to the \p TargetN.
753  /// This operation is inexpensive and does not change the set of SCCs and
754  /// RefSCCs in the graph.
755  void insertOutgoingEdge(Node &SourceN, Node &TargetN, Edge::Kind EK);
756 
757  /// Insert an edge whose source is in a descendant RefSCC and target is in
758  /// this RefSCC.
759  ///
760  /// There must be an existing path from the target to the source in this
761  /// case.
762  ///
763  /// NB! This is has the potential to be a very expensive function. It
764  /// inherently forms a cycle in the prior RefSCC DAG and we have to merge
765  /// RefSCCs to resolve that cycle. But finding all of the RefSCCs which
766  /// participate in the cycle can in the worst case require traversing every
767  /// RefSCC in the graph. Every attempt is made to avoid that, but passes
768  /// must still exercise caution calling this routine repeatedly.
769  ///
770  /// Also note that this can only insert ref edges. In order to insert
771  /// a call edge, first insert a ref edge and then switch it to a call edge.
772  /// These are intentionally kept as separate interfaces because each step
773  /// of the operation invalidates a different set of data structures.
774  ///
775  /// This returns all the RefSCCs which were merged into the this RefSCC
776  /// (the target's). This allows callers to invalidate any cached
777  /// information.
778  ///
779  /// FIXME: We could possibly optimize this quite a bit for cases where the
780  /// caller and callee are very nearby in the graph. See comments in the
781  /// implementation for details, but that use case might impact users.
783  Node &TargetN);
784 
785  /// Remove an edge whose source is in this RefSCC and target is *not*.
786  ///
787  /// This removes an inter-RefSCC edge. All inter-RefSCC edges originating
788  /// from this SCC have been fully explored by any in-flight DFS graph
789  /// formation, so this is always safe to call once you have the source
790  /// RefSCC.
791  ///
792  /// This operation does not change the cyclic structure of the graph and so
793  /// is very inexpensive. It may change the connectivity graph of the SCCs
794  /// though, so be careful calling this while iterating over them.
795  void removeOutgoingEdge(Node &SourceN, Node &TargetN);
796 
797  /// Remove a list of ref edges which are entirely within this RefSCC.
798  ///
799  /// Both the \a SourceN and all of the \a TargetNs must be within this
800  /// RefSCC. Removing these edges may break cycles that form this RefSCC and
801  /// thus this operation may change the RefSCC graph significantly. In
802  /// particular, this operation will re-form new RefSCCs based on the
803  /// remaining connectivity of the graph. The following invariants are
804  /// guaranteed to hold after calling this method:
805  ///
806  /// 1) If a ref-cycle remains after removal, it leaves this RefSCC intact
807  /// and in the graph. No new RefSCCs are built.
808  /// 2) Otherwise, this RefSCC will be dead after this call and no longer in
809  /// the graph or the postorder traversal of the call graph. Any iterator
810  /// pointing at this RefSCC will become invalid.
811  /// 3) All newly formed RefSCCs will be returned and the order of the
812  /// RefSCCs returned will be a valid postorder traversal of the new
813  /// RefSCCs.
814  /// 4) No RefSCC other than this RefSCC has its member set changed (this is
815  /// inherent in the definition of removing such an edge).
816  ///
817  /// These invariants are very important to ensure that we can build
818  /// optimization pipelines on top of the CGSCC pass manager which
819  /// intelligently update the RefSCC graph without invalidating other parts
820  /// of the RefSCC graph.
821  ///
822  /// Note that we provide no routine to remove a *call* edge. Instead, you
823  /// must first switch it to a ref edge using \c switchInternalEdgeToRef.
824  /// This split API is intentional as each of these two steps can invalidate
825  /// a different aspect of the graph structure and needs to have the
826  /// invalidation handled independently.
827  ///
828  /// The runtime complexity of this method is, in the worst case, O(V+E)
829  /// where V is the number of nodes in this RefSCC and E is the number of
830  /// edges leaving the nodes in this RefSCC. Note that E includes both edges
831  /// within this RefSCC and edges from this RefSCC to child RefSCCs. Some
832  /// effort has been made to minimize the overhead of common cases such as
833  /// self-edges and edge removals which result in a spanning tree with no
834  /// more cycles.
835  [[nodiscard]] SmallVector<RefSCC *, 1>
836  removeInternalRefEdge(Node &SourceN, ArrayRef<Node *> TargetNs);
837 
838  /// A convenience wrapper around the above to handle trivial cases of
839  /// inserting a new call edge.
840  ///
841  /// This is trivial whenever the target is in the same SCC as the source or
842  /// the edge is an outgoing edge to some descendant SCC. In these cases
843  /// there is no change to the cyclic structure of SCCs or RefSCCs.
844  ///
845  /// To further make calling this convenient, it also handles inserting
846  /// already existing edges.
847  void insertTrivialCallEdge(Node &SourceN, Node &TargetN);
848 
849  /// A convenience wrapper around the above to handle trivial cases of
850  /// inserting a new ref edge.
851  ///
852  /// This is trivial whenever the target is in the same RefSCC as the source
853  /// or the edge is an outgoing edge to some descendant RefSCC. In these
854  /// cases there is no change to the cyclic structure of the RefSCCs.
855  ///
856  /// To further make calling this convenient, it also handles inserting
857  /// already existing edges.
858  void insertTrivialRefEdge(Node &SourceN, Node &TargetN);
859 
860  /// Directly replace a node's function with a new function.
861  ///
862  /// This should be used when moving the body and users of a function to
863  /// a new formal function object but not otherwise changing the call graph
864  /// structure in any way.
865  ///
866  /// It requires that the old function in the provided node have zero uses
867  /// and the new function must have calls and references to it establishing
868  /// an equivalent graph.
869  void replaceNodeFunction(Node &N, Function &NewF);
870 
871  ///@}
872  };
873 
874  /// A post-order depth-first RefSCC iterator over the call graph.
875  ///
876  /// This iterator walks the cached post-order sequence of RefSCCs. However,
877  /// it trades stability for flexibility. It is restricted to a forward
878  /// iterator but will survive mutations which insert new RefSCCs and continue
879  /// to point to the same RefSCC even if it moves in the post-order sequence.
881  : public iterator_facade_base<postorder_ref_scc_iterator,
882  std::forward_iterator_tag, RefSCC> {
883  friend class LazyCallGraph;
884  friend class LazyCallGraph::Node;
885 
886  /// Nonce type to select the constructor for the end iterator.
887  struct IsAtEndT {};
888 
889  LazyCallGraph *G;
890  RefSCC *RC = nullptr;
891 
892  /// Build the begin iterator for a node.
893  postorder_ref_scc_iterator(LazyCallGraph &G) : G(&G), RC(getRC(G, 0)) {
894  incrementUntilNonEmptyRefSCC();
895  }
896 
897  /// Build the end iterator for a node. This is selected purely by overload.
898  postorder_ref_scc_iterator(LazyCallGraph &G, IsAtEndT /*Nonce*/) : G(&G) {}
899 
900  /// Get the post-order RefSCC at the given index of the postorder walk,
901  /// populating it if necessary.
902  static RefSCC *getRC(LazyCallGraph &G, int Index) {
903  if (Index == (int)G.PostOrderRefSCCs.size())
904  // We're at the end.
905  return nullptr;
906 
907  return G.PostOrderRefSCCs[Index];
908  }
909 
910  // Keep incrementing until RC is non-empty (or null).
911  void incrementUntilNonEmptyRefSCC() {
912  while (RC && RC->size() == 0)
913  increment();
914  }
915 
916  void increment() {
917  assert(RC && "Cannot increment the end iterator!");
918  RC = getRC(*G, G->RefSCCIndices.find(RC)->second + 1);
919  }
920 
921  public:
923  return G == Arg.G && RC == Arg.RC;
924  }
925 
926  reference operator*() const { return *RC; }
927 
928  using iterator_facade_base::operator++;
930  increment();
931  incrementUntilNonEmptyRefSCC();
932  return *this;
933  }
934  };
935 
936  /// Construct a graph for the given module.
937  ///
938  /// This sets up the graph and computes all of the entry points of the graph.
939  /// No function definitions are scanned until their nodes in the graph are
940  /// requested during traversal.
943 
946 
947  bool invalidate(Module &, const PreservedAnalyses &PA,
949 
950  EdgeSequence::iterator begin() { return EntryEdges.begin(); }
951  EdgeSequence::iterator end() { return EntryEdges.end(); }
952 
953  void buildRefSCCs();
954 
956  if (!EntryEdges.empty())
957  assert(!PostOrderRefSCCs.empty() &&
958  "Must form RefSCCs before iterating them!");
959  return postorder_ref_scc_iterator(*this);
960  }
962  if (!EntryEdges.empty())
963  assert(!PostOrderRefSCCs.empty() &&
964  "Must form RefSCCs before iterating them!");
965  return postorder_ref_scc_iterator(*this,
966  postorder_ref_scc_iterator::IsAtEndT());
967  }
968 
971  }
972 
973  /// Lookup a function in the graph which has already been scanned and added.
974  Node *lookup(const Function &F) const { return NodeMap.lookup(&F); }
975 
976  /// Lookup a function's SCC in the graph.
977  ///
978  /// \returns null if the function hasn't been assigned an SCC via the RefSCC
979  /// iterator walk.
980  SCC *lookupSCC(Node &N) const { return SCCMap.lookup(&N); }
981 
982  /// Lookup a function's RefSCC in the graph.
983  ///
984  /// \returns null if the function hasn't been assigned a RefSCC via the
985  /// RefSCC iterator walk.
987  if (SCC *C = lookupSCC(N))
988  return &C->getOuterRefSCC();
989 
990  return nullptr;
991  }
992 
993  /// Get a graph node for a given function, scanning it to populate the graph
994  /// data as necessary.
996  Node *&N = NodeMap[&F];
997  if (N)
998  return *N;
999 
1000  return insertInto(F, N);
1001  }
1002 
1003  /// Get the sequence of known and defined library functions.
1004  ///
1005  /// These functions, because they are known to LLVM, can have calls
1006  /// introduced out of thin air from arbitrary IR.
1008  return LibFunctions.getArrayRef();
1009  }
1010 
1011  /// Test whether a function is a known and defined library function tracked by
1012  /// the call graph.
1013  ///
1014  /// Because these functions are known to LLVM they are specially modeled in
1015  /// the call graph and even when all IR-level references have been removed
1016  /// remain active and reachable.
1017  bool isLibFunction(Function &F) const { return LibFunctions.count(&F); }
1018 
1019  ///@{
1020  /// \name Pre-SCC Mutation API
1021  ///
1022  /// These methods are only valid to call prior to forming any SCCs for this
1023  /// call graph. They can be used to update the core node-graph during
1024  /// a node-based inorder traversal that precedes any SCC-based traversal.
1025  ///
1026  /// Once you begin manipulating a call graph's SCCs, most mutation of the
1027  /// graph must be performed via a RefSCC method. There are some exceptions
1028  /// below.
1029 
1030  /// Update the call graph after inserting a new edge.
1031  void insertEdge(Node &SourceN, Node &TargetN, Edge::Kind EK);
1032 
1033  /// Update the call graph after inserting a new edge.
1035  return insertEdge(get(Source), get(Target), EK);
1036  }
1037 
1038  /// Update the call graph after deleting an edge.
1039  void removeEdge(Node &SourceN, Node &TargetN);
1040 
1041  /// Update the call graph after deleting an edge.
1043  return removeEdge(get(Source), get(Target));
1044  }
1045 
1046  ///@}
1047 
1048  ///@{
1049  /// \name General Mutation API
1050  ///
1051  /// There are a very limited set of mutations allowed on the graph as a whole
1052  /// once SCCs have started to be formed. These routines have strict contracts
1053  /// but may be called at any point.
1054 
1055  /// Remove a dead function from the call graph (typically to delete it).
1056  ///
1057  /// Note that the function must have an empty use list, and the call graph
1058  /// must be up-to-date prior to calling this. That means it is by itself in
1059  /// a maximal SCC which is by itself in a maximal RefSCC, etc. No structural
1060  /// changes result from calling this routine other than potentially removing
1061  /// entry points into the call graph.
1062  ///
1063  /// If SCC formation has begun, this function must not be part of the current
1064  /// DFS in order to call this safely. Typically, the function will have been
1065  /// fully visited by the DFS prior to calling this routine.
1066  void removeDeadFunction(Function &F);
1067 
1068  /// Add a new function split/outlined from an existing function.
1069  ///
1070  /// The new function may only reference other functions that the original
1071  /// function did.
1072  ///
1073  /// The original function must reference (either directly or indirectly) the
1074  /// new function.
1075  ///
1076  /// The new function may also reference the original function.
1077  /// It may end up in a parent SCC in the case that the original function's
1078  /// edge to the new function is a ref edge, and the edge back is a call edge.
1079  void addSplitFunction(Function &OriginalFunction, Function &NewFunction);
1080 
1081  /// Add new ref-recursive functions split/outlined from an existing function.
1082  ///
1083  /// The new functions may only reference other functions that the original
1084  /// function did. The new functions may reference (not call) the original
1085  /// function.
1086  ///
1087  /// The original function must reference (not call) all new functions.
1088  /// All new functions must reference (not call) each other.
1089  void addSplitRefRecursiveFunctions(Function &OriginalFunction,
1090  ArrayRef<Function *> NewFunctions);
1091 
1092  ///@}
1093 
1094  ///@{
1095  /// \name Static helpers for code doing updates to the call graph.
1096  ///
1097  /// These helpers are used to implement parts of the call graph but are also
1098  /// useful to code doing updates or otherwise wanting to walk the IR in the
1099  /// same patterns as when we build the call graph.
1100 
1101  /// Recursively visits the defined functions whose address is reachable from
1102  /// every constant in the \p Worklist.
1103  ///
1104  /// Doesn't recurse through any constants already in the \p Visited set, and
1105  /// updates that set with every constant visited.
1106  ///
1107  /// For each defined function, calls \p Callback with that function.
1108  static void visitReferences(SmallVectorImpl<Constant *> &Worklist,
1109  SmallPtrSetImpl<Constant *> &Visited,
1110  function_ref<void(Function &)> Callback);
1111 
1112  ///@}
1113 
1114 private:
1115  using node_stack_iterator = SmallVectorImpl<Node *>::reverse_iterator;
1116  using node_stack_range = iterator_range<node_stack_iterator>;
1117 
1118  /// Allocator that holds all the call graph nodes.
1120 
1121  /// Maps function->node for fast lookup.
1123 
1124  /// The entry edges into the graph.
1125  ///
1126  /// These edges are from "external" sources. Put another way, they
1127  /// escape at the module scope.
1128  EdgeSequence EntryEdges;
1129 
1130  /// Allocator that holds all the call graph SCCs.
1132 
1133  /// Maps Function -> SCC for fast lookup.
1134  DenseMap<Node *, SCC *> SCCMap;
1135 
1136  /// Allocator that holds all the call graph RefSCCs.
1138 
1139  /// The post-order sequence of RefSCCs.
1140  ///
1141  /// This list is lazily formed the first time we walk the graph.
1142  SmallVector<RefSCC *, 16> PostOrderRefSCCs;
1143 
1144  /// A map from RefSCC to the index for it in the postorder sequence of
1145  /// RefSCCs.
1146  DenseMap<RefSCC *, int> RefSCCIndices;
1147 
1148  /// Defined functions that are also known library functions which the
1149  /// optimizer can reason about and therefore might introduce calls to out of
1150  /// thin air.
1151  SmallSetVector<Function *, 4> LibFunctions;
1152 
1153  /// Helper to insert a new function, with an already looked-up entry in
1154  /// the NodeMap.
1155  Node &insertInto(Function &F, Node *&MappedN);
1156 
1157  /// Helper to initialize a new node created outside of creating SCCs and add
1158  /// it to the NodeMap if necessary. For example, useful when a function is
1159  /// split.
1160  Node &initNode(Function &F);
1161 
1162  /// Helper to update pointers back to the graph object during moves.
1163  void updateGraphPtrs();
1164 
1165  /// Allocates an SCC and constructs it using the graph allocator.
1166  ///
1167  /// The arguments are forwarded to the constructor.
1168  template <typename... Ts> SCC *createSCC(Ts &&...Args) {
1169  return new (SCCBPA.Allocate()) SCC(std::forward<Ts>(Args)...);
1170  }
1171 
1172  /// Allocates a RefSCC and constructs it using the graph allocator.
1173  ///
1174  /// The arguments are forwarded to the constructor.
1175  template <typename... Ts> RefSCC *createRefSCC(Ts &&...Args) {
1176  return new (RefSCCBPA.Allocate()) RefSCC(std::forward<Ts>(Args)...);
1177  }
1178 
1179  /// Common logic for building SCCs from a sequence of roots.
1180  ///
1181  /// This is a very generic implementation of the depth-first walk and SCC
1182  /// formation algorithm. It uses a generic sequence of roots and generic
1183  /// callbacks for each step. This is designed to be used to implement both
1184  /// the RefSCC formation and SCC formation with shared logic.
1185  ///
1186  /// Currently this is a relatively naive implementation of Tarjan's DFS
1187  /// algorithm to form the SCCs.
1188  ///
1189  /// FIXME: We should consider newer variants such as Nuutila.
1190  template <typename RootsT, typename GetBeginT, typename GetEndT,
1191  typename GetNodeT, typename FormSCCCallbackT>
1192  static void buildGenericSCCs(RootsT &&Roots, GetBeginT &&GetBegin,
1193  GetEndT &&GetEnd, GetNodeT &&GetNode,
1194  FormSCCCallbackT &&FormSCC);
1195 
1196  /// Build the SCCs for a RefSCC out of a list of nodes.
1197  void buildSCCs(RefSCC &RC, node_stack_range Nodes);
1198 
1199  /// Get the index of a RefSCC within the postorder traversal.
1200  ///
1201  /// Requires that this RefSCC is a valid one in the (perhaps partial)
1202  /// postorder traversed part of the graph.
1203  int getRefSCCIndex(RefSCC &RC) {
1204  auto IndexIt = RefSCCIndices.find(&RC);
1205  assert(IndexIt != RefSCCIndices.end() && "RefSCC doesn't have an index!");
1206  assert(PostOrderRefSCCs[IndexIt->second] == &RC &&
1207  "Index does not point back at RC!");
1208  return IndexIt->second;
1209  }
1210 };
1211 
1212 inline LazyCallGraph::Edge::Edge() = default;
1214 
1215 inline LazyCallGraph::Edge::operator bool() const {
1216  return Value.getPointer() && !Value.getPointer()->isDead();
1217 }
1218 
1220  assert(*this && "Queried a null edge!");
1221  return Value.getInt();
1222 }
1223 
1224 inline bool LazyCallGraph::Edge::isCall() const {
1225  assert(*this && "Queried a null edge!");
1226  return getKind() == Call;
1227 }
1228 
1230  assert(*this && "Queried a null edge!");
1231  return *Value.getPointer();
1232 }
1233 
1235  assert(*this && "Queried a null edge!");
1236  return getNode().getFunction();
1237 }
1238 
1239 // Provide GraphTraits specializations for call graphs.
1240 template <> struct GraphTraits<LazyCallGraph::Node *> {
1243 
1244  static NodeRef getEntryNode(NodeRef N) { return N; }
1245  static ChildIteratorType child_begin(NodeRef N) { return (*N)->begin(); }
1246  static ChildIteratorType child_end(NodeRef N) { return (*N)->end(); }
1247 };
1248 template <> struct GraphTraits<LazyCallGraph *> {
1251 
1252  static NodeRef getEntryNode(NodeRef N) { return N; }
1253  static ChildIteratorType child_begin(NodeRef N) { return (*N)->begin(); }
1254  static ChildIteratorType child_end(NodeRef N) { return (*N)->end(); }
1255 };
1256 
1257 /// An analysis pass which computes the call graph for a module.
1258 class LazyCallGraphAnalysis : public AnalysisInfoMixin<LazyCallGraphAnalysis> {
1260 
1261  static AnalysisKey Key;
1262 
1263 public:
1264  /// Inform generic clients of the result type.
1266 
1267  /// Compute the \c LazyCallGraph for the module \c M.
1268  ///
1269  /// This just builds the set of entry points to the call graph. The rest is
1270  /// built lazily as it is walked.
1274  auto GetTLI = [&FAM](Function &F) -> TargetLibraryInfo & {
1275  return FAM.getResult<TargetLibraryAnalysis>(F);
1276  };
1277  return LazyCallGraph(M, GetTLI);
1278  }
1279 };
1280 
1281 /// A pass which prints the call graph to a \c raw_ostream.
1282 ///
1283 /// This is primarily useful for testing the analysis.
1285  : public PassInfoMixin<LazyCallGraphPrinterPass> {
1286  raw_ostream &OS;
1287 
1288 public:
1289  explicit LazyCallGraphPrinterPass(raw_ostream &OS);
1290 
1292 };
1293 
1294 /// A pass which prints the call graph as a DOT file to a \c raw_ostream.
1295 ///
1296 /// This is primarily useful for visualization purposes.
1298  : public PassInfoMixin<LazyCallGraphDOTPrinterPass> {
1299  raw_ostream &OS;
1300 
1301 public:
1303 
1305 };
1306 
1307 } // end namespace llvm
1308 
1309 #endif // LLVM_ANALYSIS_LAZYCALLGRAPH_H
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
llvm::LazyCallGraph::postorder_ref_scc_iterator::operator==
bool operator==(const postorder_ref_scc_iterator &Arg) const
Definition: LazyCallGraph.h:922
llvm::LazyCallGraph::RefSCC::find
iterator find(SCC &C) const
Definition: LazyCallGraph.h:620
llvm::LazyCallGraph::Edge::Edge
Edge()
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::LazyCallGraph::buildRefSCCs
void buildRefSCCs()
Definition: LazyCallGraph.cpp:1922
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::make_range
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Definition: iterator_range.h:53
Optional.h
llvm::LazyCallGraph::LazyCallGraph
LazyCallGraph(Module &M, function_ref< TargetLibraryInfo &(Function &)> GetTLI)
Construct a graph for the given module.
Definition: LazyCallGraph.cpp:154
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:774
llvm::PassInfoMixin
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:371
llvm::Function
Definition: Function.h:60
StringRef.h
llvm::LazyCallGraph::insertEdge
void insertEdge(Node &SourceN, Node &TargetN, Edge::Kind EK)
Update the call graph after inserting a new edge.
Definition: LazyCallGraph.cpp:1478
llvm::raw_string_ostream
A raw_ostream that writes to an std::string.
Definition: raw_ostream.h:629
llvm::LazyCallGraph::RefSCC::size
ssize_t size() const
Definition: LazyCallGraph.h:616
llvm::LazyCallGraph::EdgeSequence::call_end
call_iterator call_end()
Definition: LazyCallGraph.h:276
llvm::Target
Target - Wrapper for Target specific information.
Definition: TargetRegistry.h:150
llvm::SmallVector< Edge, 4 >
llvm::LazyCallGraph::SCC::end
iterator end() const
Definition: LazyCallGraph.h:479
llvm::iterator_adaptor_base< iterator, VectorImplT::iterator, std::forward_iterator_tag >::I
VectorImplT::iterator I
Definition: iterator.h:241
Allocator.h
llvm::SmallDenseMap
Definition: DenseMap.h:880
llvm::LazyCallGraph::removeDeadFunction
void removeDeadFunction(Function &F)
Remove a dead function from the call graph (typically to delete it).
Definition: LazyCallGraph.cpp:1494
llvm::LazyCallGraph::Node::isPopulated
bool isPopulated() const
Tests whether the node has been populated with edges.
Definition: LazyCallGraph.h:332
FAM
FunctionAnalysisManager FAM
Definition: PassBuilderBindings.cpp:59
llvm::SpecificBumpPtrAllocator
A BumpPtrAllocator that allows only elements of a specific type to be allocated.
Definition: Allocator.h:382
llvm::LazyCallGraph::SCC::isDescendantOf
bool isDescendantOf(const SCC &C) const
Test if this SCC is a descendant of C.
Definition: LazyCallGraph.h:509
llvm::LazyCallGraph::Node::getFunction
Function & getFunction() const
Definition: LazyCallGraph.h:323
DenseMap.h
llvm::iterator_adaptor_base
CRTP base class for adapting an iterator to a different type.
Definition: iterator.h:235
llvm::LazyCallGraph::lookup
Node * lookup(const Function &F) const
Lookup a function in the graph which has already been scanned and added.
Definition: LazyCallGraph.h:974
llvm::GraphTraits< LazyCallGraph * >::child_end
static ChildIteratorType child_end(NodeRef N)
Definition: LazyCallGraph.h:1254
llvm::dump
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
Definition: SparseBitVector.h:877
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
llvm::LazyCallGraph::EdgeSequence::calls
iterator_range< call_iterator > calls()
Definition: LazyCallGraph.h:278
llvm::LazyCallGraph::postorder_ref_scc_begin
postorder_ref_scc_iterator postorder_ref_scc_begin()
Definition: LazyCallGraph.h:955
llvm::LazyCallGraph::EdgeSequence::begin
iterator begin()
Definition: LazyCallGraph.h:255
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::LazyCallGraph::invalidate
bool invalidate(Module &, const PreservedAnalyses &PA, ModuleAnalysisManager::Invalidator &)
Definition: LazyCallGraph.cpp:214
llvm::LazyCallGraph::RefSCC::isAncestorOf
bool isAncestorOf(const RefSCC &RC) const
Test if this RefSCC is an ancestor of RC.
Definition: LazyCallGraph.cpp:414
llvm::LazyCallGraph::EdgeSequence::operator[]
Edge & operator[](Node &N)
Definition: LazyCallGraph.h:258
PointerIntPair.h
clear
static void clear(coro::Shape &Shape)
Definition: Coroutines.cpp:149
llvm::LazyCallGraph::Edge::getNode
Node & getNode() const
Get the call graph node referenced by this edge.
Definition: LazyCallGraph.h:1229
Arg
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Definition: AMDGPULibCalls.cpp:187
llvm::LazyCallGraph::RefSCC::insertTrivialCallEdge
void insertTrivialCallEdge(Node &SourceN, Node &TargetN)
A convenience wrapper around the above to handle trivial cases of inserting a new call edge.
Definition: LazyCallGraph.cpp:1389
llvm::LazyCallGraph::SCC
An SCC of the call graph.
Definition: LazyCallGraph.h:420
llvm::LazyCallGraph::operator=
LazyCallGraph & operator=(LazyCallGraph &&RHS)
Definition: LazyCallGraph.cpp:222
llvm::ISD::Constant
@ Constant
Definition: ISDOpcodes.h:76
llvm::LazyCallGraphPrinterPass
A pass which prints the call graph to a raw_ostream.
Definition: LazyCallGraph.h:1284
llvm::LazyCallGraph::postorder_ref_scc_iterator::operator++
postorder_ref_scc_iterator & operator++()
Definition: LazyCallGraph.h:929
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::LazyCallGraph::end
EdgeSequence::iterator end()
Definition: LazyCallGraph.h:951
llvm::LazyCallGraph::Node::isDead
bool isDead() const
Tests whether this is actually a dead node and no longer valid.
Definition: LazyCallGraph.h:339
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::LazyCallGraph::EdgeSequence::end
iterator end()
Definition: LazyCallGraph.h:256
llvm::LazyCallGraph::RefSCC::isParentOf
bool isParentOf(const RefSCC &RC) const
Test if this RefSCC is a parent of RC.
Definition: LazyCallGraph.cpp:400
llvm::LazyCallGraph::RefSCC::insertTrivialRefEdge
void insertTrivialRefEdge(Node &SourceN, Node &TargetN)
A convenience wrapper around the above to handle trivial cases of inserting a new ref edge.
Definition: LazyCallGraph.cpp:1418
llvm::LazyCallGraph::removeEdge
void removeEdge(Function &Source, Function &Target)
Update the call graph after deleting an edge.
Definition: LazyCallGraph.h:1042
llvm::AMDGPU::PALMD::Key
Key
PAL metadata keys.
Definition: AMDGPUMetadata.h:486
TargetLibraryInfo.h
llvm::LazyCallGraph::RefSCC
A RefSCC of the call graph.
Definition: LazyCallGraph.h:545
llvm::LazyCallGraph::EdgeSequence::iterator
An iterator used for the edges to both entry nodes and child nodes.
Definition: LazyCallGraph.h:193
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::raw_ostream::flush
void flush()
Definition: raw_ostream.h:186
llvm::LazyCallGraph::EdgeSequence
The edge sequence object.
Definition: LazyCallGraph.h:183
llvm::LazyCallGraph::lookupSCC
SCC * lookupSCC(Node &N) const
Lookup a function's SCC in the graph.
Definition: LazyCallGraph.h:980
llvm::AnalysisManager::Invalidator
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:661
llvm::LazyCallGraph::insertEdge
void insertEdge(Function &Source, Function &Target, Edge::Kind EK)
Update the call graph after inserting a new edge.
Definition: LazyCallGraph.h:1034
llvm::LazyCallGraph::RefSCC::insertOutgoingEdge
void insertOutgoingEdge(Node &SourceN, Node &TargetN, Edge::Kind EK)
Insert an edge whose parent is in this RefSCC and child is in some child RefSCC.
Definition: LazyCallGraph.cpp:976
llvm::dxil::PointerTypeAnalysis::run
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
Definition: PointerTypeAnalysis.cpp:189
llvm::LazyCallGraph::postorder_ref_scc_iterator::LazyCallGraph
friend class LazyCallGraph
Definition: LazyCallGraph.h:883
llvm::iterator_facade_base< postorder_ref_scc_iterator, std::forward_iterator_tag, RefSCC >::reference
RefSCC & reference
Definition: iterator.h:86
llvm::LazyCallGraph::get
Node & get(Function &F)
Get a graph node for a given function, scanning it to populate the graph data as necessary.
Definition: LazyCallGraph.h:995
llvm::LazyCallGraph::Node::getName
StringRef getName() const
Definition: LazyCallGraph.h:325
llvm::LazyCallGraph::RefSCC::switchInternalEdgeToCall
bool switchInternalEdgeToCall(Node &SourceN, Node &TargetN, function_ref< void(ArrayRef< SCC * > MergedSCCs)> MergeCB={})
Make an existing internal ref edge into a call edge.
Definition: LazyCallGraph.cpp:576
llvm::function_ref
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLFunctionalExtras.h:36
G
const DataFlowGraph & G
Definition: RDFGraph.cpp:200
llvm::LazyCallGraphDOTPrinterPass
A pass which prints the call graph as a DOT file to a raw_ostream.
Definition: LazyCallGraph.h:1297
llvm::LazyCallGraph::SCC::getName
std::string getName() const
Provide a short name by printing this SCC to a std::string.
Definition: LazyCallGraph.h:515
llvm::LazyCallGraph::RefSCC::switchInternalEdgeToRef
iterator_range< iterator > switchInternalEdgeToRef(Node &SourceN, Node &TargetN)
Make an existing internal call edge within a single SCC into a ref edge.
Definition: LazyCallGraph.cpp:742
llvm::LazyCallGraph::Node::operator!=
bool operator!=(const Node &N) const
Definition: LazyCallGraph.h:329
llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, 4, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::clear
void clear()
Definition: DenseMap.h:110
Index
uint32_t Index
Definition: ELFObjHandler.cpp:83
llvm::LazyCallGraph::RefSCC::isDescendantOf
bool isDescendantOf(const RefSCC &RC) const
Test if this RefSCC is a descendant of RC.
Definition: LazyCallGraph.h:648
llvm::LazyCallGraph::addSplitFunction
void addSplitFunction(Function &OriginalFunction, Function &NewFunction)
Add a new function split/outlined from an existing function.
Definition: LazyCallGraph.cpp:1609
LLVM_EXTERNAL_VISIBILITY
#define LLVM_EXTERNAL_VISIBILITY
Definition: Compiler.h:127
llvm::LazyCallGraph::lookupRefSCC
RefSCC * lookupRefSCC(Node &N) const
Lookup a function's RefSCC in the graph.
Definition: LazyCallGraph.h:986
llvm::LazyCallGraph::RefSCC::getName
std::string getName() const
Provide a short name by printing this RefSCC to a std::string.
Definition: LazyCallGraph.h:656
llvm::LazyCallGraph::RefSCC::removeOutgoingEdge
void removeOutgoingEdge(Node &SourceN, Node &TargetN)
Remove an edge whose source is in this RefSCC and target is not.
Definition: LazyCallGraph.cpp:1137
llvm::DenseMap
Definition: DenseMap.h:714
llvm::LazyCallGraph::Node::getGraph
LazyCallGraph & getGraph() const
Definition: LazyCallGraph.h:321
llvm::GraphTraits< LazyCallGraph::Node * >::child_begin
static ChildIteratorType child_begin(NodeRef N)
Definition: LazyCallGraph.h:1245
llvm::AnalysisKey
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:69
iterator.h
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::LazyCallGraph::begin
EdgeSequence::iterator begin()
Definition: LazyCallGraph.h:950
llvm::LazyCallGraph::RefSCC::insertIncomingRefEdge
SmallVector< RefSCC *, 1 > insertIncomingRefEdge(Node &SourceN, Node &TargetN)
Insert an edge whose source is in a descendant RefSCC and target is in this RefSCC.
Definition: LazyCallGraph.cpp:996
llvm::iterator_facade_base
CRTP base class which implements the entire standard iterator facade in terms of a minimal subset of ...
Definition: iterator.h:80
ArrayRef.h
llvm::GraphTraits< LazyCallGraph::Node * >::child_end
static ChildIteratorType child_end(NodeRef N)
Definition: LazyCallGraph.h:1246
G
#define G(x, y, z)
Definition: MD5.cpp:56
llvm::LazyCallGraph::Edge::Kind
Kind
The kind of edge in the graph.
Definition: LazyCallGraph.h:135
llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, 4, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::find
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:150
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::LazyCallGraph::Edge::getFunction
Function & getFunction() const
Get the function referenced by this edge.
Definition: LazyCallGraph.h:1234
iterator_range.h
llvm::LazyCallGraph::EdgeSequence::lookup
Edge * lookup(Node &N)
Definition: LazyCallGraph.h:265
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:66
llvm::LazyCallGraph::postorder_ref_scc_iterator
A post-order depth-first RefSCC iterator over the call graph.
Definition: LazyCallGraph.h:880
llvm::AnalysisInfoMixin
A CRTP mix-in that provides informational APIs needed for analysis passes.
Definition: PassManager.h:394
llvm::LazyCallGraph::Node
A node in the call graph.
Definition: LazyCallGraph.h:316
llvm::AMDGPU::CPol::SCC
@ SCC
Definition: SIDefines.h:307
llvm::LazyCallGraph::Edge
A class used to represent edges in the call graph.
Definition: LazyCallGraph.h:132
llvm::Sched::Source
@ Source
Definition: TargetLowering.h:99
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::LazyCallGraph::EdgeSequence::call_iterator::call_iterator
call_iterator()=default
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
llvm::LazyCallGraph::RefSCC::removeInternalRefEdge
SmallVector< RefSCC *, 1 > removeInternalRefEdge(Node &SourceN, ArrayRef< Node * > TargetNs)
Remove a list of ref edges which are entirely within this RefSCC.
Definition: LazyCallGraph.cpp:1155
llvm::LazyCallGraph::SCC::size
int size() const
Definition: LazyCallGraph.h:481
llvm::LazyCallGraphAnalysis::run
LazyCallGraph run(Module &M, ModuleAnalysisManager &AM)
Compute the LazyCallGraph for the module M.
Definition: LazyCallGraph.h:1271
llvm::LazyCallGraph::RefSCC::begin
iterator begin() const
Definition: LazyCallGraph.h:613
llvm::LazyCallGraph::Edge::getKind
Kind getKind() const
Returns the Kind of the edge.
Definition: LazyCallGraph.h:1219
llvm::GraphTraits< LazyCallGraph::Node * >::getEntryNode
static NodeRef getEntryNode(NodeRef N)
Definition: LazyCallGraph.h:1244
llvm::LazyCallGraph::postorder_ref_scc_end
postorder_ref_scc_iterator postorder_ref_scc_end()
Definition: LazyCallGraph.h:961
Module
Machine Check Debug Module
Definition: MachineCheckDebugify.cpp:122
Node
Definition: ItaniumDemangle.h:156
llvm::LazyCallGraph::RefSCC::replaceNodeFunction
void replaceNodeFunction(Node &N, Function &NewF)
Directly replace a node's function with a new function.
Definition: LazyCallGraph.cpp:1442
llvm::LazyCallGraph::EdgeSequence::call_iterator::operator++
call_iterator & operator++()
Definition: LazyCallGraph.h:248
llvm::SpecificBumpPtrAllocator::Allocate
T * Allocate(size_t num=1)
Allocate space for an array of objects without constructing them.
Definition: Allocator.h:432
llvm::LazyCallGraph::postorder_ref_scc_iterator::operator*
reference operator*() const
Definition: LazyCallGraph.h:926
llvm::LazyCallGraph::getLibFunctions
ArrayRef< Function * > getLibFunctions() const
Get the sequence of known and defined library functions.
Definition: LazyCallGraph.h:1007
llvm::GraphProgram::Name
Name
Definition: GraphWriter.h:50
std
Definition: BitVector.h:851
llvm::LazyCallGraph::addSplitRefRecursiveFunctions
void addSplitRefRecursiveFunctions(Function &OriginalFunction, ArrayRef< Function * > NewFunctions)
Add new ref-recursive functions split/outlined from an existing function.
Definition: LazyCallGraph.cpp:1688
llvm::LazyCallGraph::Node::operator<<
friend raw_ostream & operator<<(raw_ostream &OS, const Node &N)
Print the name of this node's function.
Definition: LazyCallGraph.h:401
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::end
iterator end()
Definition: DenseMap.h:84
llvm::LazyCallGraph::RefSCC::operator<<
friend raw_ostream & operator<<(raw_ostream &OS, const RefSCC &RC)
Print a short description useful for debugging or logging.
Definition: LazyCallGraph.h:573
llvm::LazyCallGraph::Edge::isCall
bool isCall() const
Test whether the edge represents a direct call to a function.
Definition: LazyCallGraph.h:1224
llvm::LazyCallGraph::Node::populate
EdgeSequence & populate()
Populate the edges of this node if necessary.
Definition: LazyCallGraph.h:365
llvm::GraphTraits< LazyCallGraph * >::getEntryNode
static NodeRef getEntryNode(NodeRef N)
Definition: LazyCallGraph.h:1252
llvm::LazyCallGraphAnalysis
An analysis pass which computes the call graph for a module.
Definition: LazyCallGraph.h:1258
llvm::LazyCallGraph::isLibFunction
bool isLibFunction(Function &F) const
Test whether a function is a known and defined library function tracked by the call graph.
Definition: LazyCallGraph.h:1017
llvm::TargetStackID::Value
Value
Definition: TargetFrameLowering.h:27
PassManager.h
llvm::LazyCallGraph::SCC::begin
iterator begin() const
Definition: LazyCallGraph.h:478
llvm::TargetLibraryInfo
Provides information about what library functions are available for the current target.
Definition: TargetLibraryInfo.h:226
verify
ppc ctr loops verify
Definition: PPCCTRLoopsVerify.cpp:76
llvm::GraphTraits< LazyCallGraph * >::child_begin
static ChildIteratorType child_begin(NodeRef N)
Definition: LazyCallGraph.h:1253
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:614
llvm::LazyCallGraph::RefSCC::switchTrivialInternalEdgeToRef
void switchTrivialInternalEdgeToRef(Node &SourceN, Node &TargetN)
Make an existing internal call edge between separate SCCs into a ref edge.
Definition: LazyCallGraph.cpp:723
llvm::LazyCallGraph::RefSCC::operator[]
SCC & operator[](int Idx)
Definition: LazyCallGraph.h:618
llvm::LazyCallGraph::EdgeSequence::iterator::operator++
iterator & operator++()
Definition: LazyCallGraph.h:212
llvm::LazyCallGraph::EdgeSequence::empty
bool empty()
Definition: LazyCallGraph.h:282
llvm::LazyCallGraph::RefSCC::switchOutgoingEdgeToRef
void switchOutgoingEdgeToRef(Node &SourceN, Node &TargetN)
Make an existing outgoing call edge into a ref edge.
Definition: LazyCallGraph.cpp:943
llvm::PointerIntPair
PointerIntPair - This class implements a pair of a pointer and small integer.
Definition: PointerIntPair.h:46
SmallVector.h
llvm::LazyCallGraph::EdgeSequence::call_iterator
An iterator over specifically call edges.
Definition: LazyCallGraph.h:224
llvm::SmallVectorImpl::iterator
typename SuperClass::iterator iterator
Definition: SmallVector.h:581
N
#define N
llvm::LazyCallGraph::Node::operator*
EdgeSequence & operator*() const
Definition: LazyCallGraph.h:347
llvm::LazyCallGraph::RefSCC::switchOutgoingEdgeToCall
void switchOutgoingEdgeToCall(Node &SourceN, Node &TargetN)
Make an existing outgoing ref edge into a call edge.
Definition: LazyCallGraph.cpp:922
llvm::LazyCallGraph::SCC::getOuterRefSCC
RefSCC & getOuterRefSCC() const
Definition: LazyCallGraph.h:483
llvm::iterator_range
A range adaptor for a pair of iterators.
Definition: iterator_range.h:30
llvm::LazyCallGraph::postorder_ref_sccs
iterator_range< postorder_ref_scc_iterator > postorder_ref_sccs()
Definition: LazyCallGraph.h:969
llvm::LazyCallGraph::Node::operator==
bool operator==(const Node &N) const
Equality is defined as address equality.
Definition: LazyCallGraph.h:328
llvm::SmallVectorImpl< Edge >
llvm::SmallPtrSetImpl
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:344
llvm::LazyCallGraph::Edge::Ref
@ Ref
Definition: LazyCallGraph.h:135
llvm::SmallSetVector
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:307
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
llvm::InnerAnalysisManagerProxy
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
Definition: PassManager.h:931
llvm::LazyCallGraph::RefSCC::isChildOf
bool isChildOf(const RefSCC &RC) const
Test if this RefSCC is a child of RC.
Definition: LazyCallGraph.h:641
llvm::LazyCallGraph::Node::operator->
EdgeSequence * operator->() const
Definition: LazyCallGraph.h:351
llvm::GraphTraits
Definition: GraphTraits.h:37
llvm::pointee_iterator
An iterator type that allows iterating over the pointees via some other iterator.
Definition: iterator.h:320
llvm::LazyCallGraph::EdgeSequence::call_begin
call_iterator call_begin()
Definition: LazyCallGraph.h:273
llvm::AMDGPU::HSAMD::Kernel::Key::Args
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
Definition: AMDGPUMetadata.h:394
llvm::LazyCallGraph
A lazily constructed view of the call graph of a module.
Definition: LazyCallGraph.h:111
raw_ostream.h
llvm::LazyCallGraph::visitReferences
static void visitReferences(SmallVectorImpl< Constant * > &Worklist, SmallPtrSetImpl< Constant * > &Visited, function_ref< void(Function &)> Callback)
Recursively visits the defined functions whose address is reachable from every constant in the Workli...
Definition: LazyCallGraph.cpp:1960
llvm::LazyCallGraph::RefSCC::end
iterator end() const
Definition: LazyCallGraph.h:614
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::LazyCallGraph::SCC::isChildOf
bool isChildOf(const SCC &C) const
Test if this SCC is a child of C.
Definition: LazyCallGraph.h:503
llvm::TargetLibraryAnalysis
Analysis pass providing the TargetLibraryInfo.
Definition: TargetLibraryInfo.h:450
llvm::LazyCallGraph::Edge::Call
@ Call
Definition: LazyCallGraph.h:135
llvm::LazyCallGraph::RefSCC::insertInternalRefEdge
void insertInternalRefEdge(Node &SourceN, Node &TargetN)
Insert a ref edge from one node in this RefSCC to another in this RefSCC.
Definition: LazyCallGraph.cpp:964
llvm::codeview::PublicSymFlags::Function
@ Function
llvm::LazyCallGraph::removeEdge
void removeEdge(Node &SourceN, Node &TargetN)
Update the call graph after deleting an edge.
Definition: LazyCallGraph.cpp:1485
SetVector.h
llvm::LazyCallGraph::EdgeSequence::iterator::iterator
iterator()=default
llvm::LazyCallGraph::SCC::operator<<
friend raw_ostream & operator<<(raw_ostream &OS, const SCC &C)
Print a short description useful for debugging or logging.
Definition: LazyCallGraph.h:443