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