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 <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.has_value(); }
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  ///
537  /// Spurious ref edges, meaning ref edges that still exist in the call graph
538  /// even though the corresponding IR reference no longer exists, are allowed.
539  /// This is mostly to support argument promotion, which can modify a caller to
540  /// no longer pass a function. The only place that needs to specially handle
541  /// this is deleting a dead function/node, otherwise the dead ref edges are
542  /// automatically removed when visiting the function/node no longer containing
543  /// the ref edge.
544  class RefSCC {
545  friend class LazyCallGraph;
546  friend class LazyCallGraph::Node;
547 
548  LazyCallGraph *G;
549 
550  /// A postorder list of the inner SCCs.
552 
553  /// A map from SCC to index in the postorder list.
554  SmallDenseMap<SCC *, int, 4> SCCIndices;
555 
556  /// Fast-path constructor. RefSCCs should instead be constructed by calling
557  /// formRefSCCFast on the graph itself.
559 
560  void clear() {
561  SCCs.clear();
562  SCCIndices.clear();
563  }
564 
565  /// Print a short description useful for debugging or logging.
566  ///
567  /// We print the SCCs wrapped in '[]'s and skipping the middle SCCs if
568  /// there are a large number.
569  //
570  // Note: this is defined inline to dodge issues with GCC's interpretation
571  // of enclosing namespaces for friend function declarations.
572  friend raw_ostream &operator<<(raw_ostream &OS, const RefSCC &RC) {
573  OS << '[';
574  int I = 0;
575  for (LazyCallGraph::SCC &C : RC) {
576  if (I > 0)
577  OS << ", ";
578  // Elide the inner elements if there are too many.
579  if (I > 4) {
580  OS << "..., " << *RC.SCCs.back();
581  break;
582  }
583  OS << C;
584  ++I;
585  }
586  OS << ']';
587  return OS;
588  }
589 
590  /// Dump a short description of this RefSCC to stderr.
591  void dump() const;
592 
593 #if !defined(NDEBUG) || defined(EXPENSIVE_CHECKS)
594  /// Verify invariants about the RefSCC and all its SCCs.
595  ///
596  /// This will attempt to validate all of the invariants *within* the
597  /// RefSCC, but not that it is a strongly connected component of the larger
598  /// graph. This makes it useful even when partially through an update.
599  ///
600  /// Invariants checked:
601  /// - SCCs and their indices match.
602  /// - The SCCs list is in fact in post-order.
603  void verify();
604 #endif
605 
606  public:
609  using parent_iterator =
611 
612  iterator begin() const { return SCCs.begin(); }
613  iterator end() const { return SCCs.end(); }
614 
615  ssize_t size() const { return SCCs.size(); }
616 
617  SCC &operator[](int Idx) { return *SCCs[Idx]; }
618 
619  iterator find(SCC &C) const {
620  return SCCs.begin() + SCCIndices.find(&C)->second;
621  }
622 
623  /// Test if this RefSCC is a parent of \a RC.
624  ///
625  /// CAUTION: This method walks every edge in the \c RefSCC, it can be very
626  /// expensive.
627  bool isParentOf(const RefSCC &RC) const;
628 
629  /// Test if this RefSCC is an ancestor of \a RC.
630  ///
631  /// CAUTION: This method walks the directed graph of edges as far as
632  /// necessary to find a possible path to the argument. In the worst case
633  /// this may walk the entire graph and can be extremely expensive.
634  bool isAncestorOf(const RefSCC &RC) const;
635 
636  /// Test if this RefSCC is a child of \a RC.
637  ///
638  /// CAUTION: This method walks every edge in the argument \c RefSCC, it can
639  /// be very expensive.
640  bool isChildOf(const RefSCC &RC) const { return RC.isParentOf(*this); }
641 
642  /// Test if this RefSCC is a descendant of \a RC.
643  ///
644  /// CAUTION: This method walks the directed graph of edges as far as
645  /// necessary to find a possible path from the argument. In the worst case
646  /// this may walk the entire graph and can be extremely expensive.
647  bool isDescendantOf(const RefSCC &RC) const {
648  return RC.isAncestorOf(*this);
649  }
650 
651  /// Provide a short name by printing this RefSCC to a std::string.
652  ///
653  /// This copes with the fact that we don't have a name per se for an RefSCC
654  /// while still making the use of this in debugging and logging useful.
655  std::string getName() const {
656  std::string Name;
658  OS << *this;
659  OS.flush();
660  return Name;
661  }
662 
663  ///@{
664  /// \name Mutation API
665  ///
666  /// These methods provide the core API for updating the call graph in the
667  /// presence of (potentially still in-flight) DFS-found RefSCCs and SCCs.
668  ///
669  /// Note that these methods sometimes have complex runtimes, so be careful
670  /// how you call them.
671 
672  /// Make an existing internal ref edge into a call edge.
673  ///
674  /// This may form a larger cycle and thus collapse SCCs into TargetN's SCC.
675  /// If that happens, the optional callback \p MergedCB will be invoked (if
676  /// provided) on the SCCs being merged away prior to actually performing
677  /// the merge. Note that this will never include the target SCC as that
678  /// will be the SCC functions are merged into to resolve the cycle. Once
679  /// this function returns, these merged SCCs are not in a valid state but
680  /// the pointers will remain valid until destruction of the parent graph
681  /// instance for the purpose of clearing cached information. This function
682  /// also returns 'true' if a cycle was formed and some SCCs merged away as
683  /// a convenience.
684  ///
685  /// After this operation, both SourceN's SCC and TargetN's SCC may move
686  /// position within this RefSCC's postorder list. Any SCCs merged are
687  /// merged into the TargetN's SCC in order to preserve reachability analyses
688  /// which took place on that SCC.
690  Node &SourceN, Node &TargetN,
691  function_ref<void(ArrayRef<SCC *> MergedSCCs)> MergeCB = {});
692 
693  /// Make an existing internal call edge between separate SCCs into a ref
694  /// edge.
695  ///
696  /// If SourceN and TargetN in separate SCCs within this RefSCC, changing
697  /// the call edge between them to a ref edge is a trivial operation that
698  /// does not require any structural changes to the call graph.
699  void switchTrivialInternalEdgeToRef(Node &SourceN, Node &TargetN);
700 
701  /// Make an existing internal call edge within a single SCC into a ref
702  /// edge.
703  ///
704  /// Since SourceN and TargetN are part of a single SCC, this SCC may be
705  /// split up due to breaking a cycle in the call edges that formed it. If
706  /// that happens, then this routine will insert new SCCs into the postorder
707  /// list *before* the SCC of TargetN (previously the SCC of both). This
708  /// preserves postorder as the TargetN can reach all of the other nodes by
709  /// definition of previously being in a single SCC formed by the cycle from
710  /// SourceN to TargetN.
711  ///
712  /// The newly added SCCs are added *immediately* and contiguously
713  /// prior to the TargetN SCC and return the range covering the new SCCs in
714  /// the RefSCC's postorder sequence. You can directly iterate the returned
715  /// range to observe all of the new SCCs in postorder.
716  ///
717  /// Note that if SourceN and TargetN are in separate SCCs, the simpler
718  /// routine `switchTrivialInternalEdgeToRef` should be used instead.
720  Node &TargetN);
721 
722  /// Make an existing outgoing ref edge into a call edge.
723  ///
724  /// Note that this is trivial as there are no cyclic impacts and there
725  /// remains a reference edge.
726  void switchOutgoingEdgeToCall(Node &SourceN, Node &TargetN);
727 
728  /// Make an existing outgoing call edge into a ref edge.
729  ///
730  /// This is trivial as there are no cyclic impacts and there remains
731  /// a reference edge.
732  void switchOutgoingEdgeToRef(Node &SourceN, Node &TargetN);
733 
734  /// Insert a ref edge from one node in this RefSCC to another in this
735  /// RefSCC.
736  ///
737  /// This is always a trivial operation as it doesn't change any part of the
738  /// graph structure besides connecting the two nodes.
739  ///
740  /// Note that we don't support directly inserting internal *call* edges
741  /// because that could change the graph structure and requires returning
742  /// information about what became invalid. As a consequence, the pattern
743  /// should be to first insert the necessary ref edge, and then to switch it
744  /// to a call edge if needed and handle any invalidation that results. See
745  /// the \c switchInternalEdgeToCall routine for details.
746  void insertInternalRefEdge(Node &SourceN, Node &TargetN);
747 
748  /// Insert an edge whose parent is in this RefSCC and child is in some
749  /// child RefSCC.
750  ///
751  /// There must be an existing path from the \p SourceN to the \p TargetN.
752  /// This operation is inexpensive and does not change the set of SCCs and
753  /// RefSCCs in the graph.
754  void insertOutgoingEdge(Node &SourceN, Node &TargetN, Edge::Kind EK);
755 
756  /// Insert an edge whose source is in a descendant RefSCC and target is in
757  /// this RefSCC.
758  ///
759  /// There must be an existing path from the target to the source in this
760  /// case.
761  ///
762  /// NB! This is has the potential to be a very expensive function. It
763  /// inherently forms a cycle in the prior RefSCC DAG and we have to merge
764  /// RefSCCs to resolve that cycle. But finding all of the RefSCCs which
765  /// participate in the cycle can in the worst case require traversing every
766  /// RefSCC in the graph. Every attempt is made to avoid that, but passes
767  /// must still exercise caution calling this routine repeatedly.
768  ///
769  /// Also note that this can only insert ref edges. In order to insert
770  /// a call edge, first insert a ref edge and then switch it to a call edge.
771  /// These are intentionally kept as separate interfaces because each step
772  /// of the operation invalidates a different set of data structures.
773  ///
774  /// This returns all the RefSCCs which were merged into the this RefSCC
775  /// (the target's). This allows callers to invalidate any cached
776  /// information.
777  ///
778  /// FIXME: We could possibly optimize this quite a bit for cases where the
779  /// caller and callee are very nearby in the graph. See comments in the
780  /// implementation for details, but that use case might impact users.
782  Node &TargetN);
783 
784  /// Remove an edge whose source is in this RefSCC and target is *not*.
785  ///
786  /// This removes an inter-RefSCC edge. All inter-RefSCC edges originating
787  /// from this SCC have been fully explored by any in-flight DFS graph
788  /// formation, so this is always safe to call once you have the source
789  /// RefSCC.
790  ///
791  /// This operation does not change the cyclic structure of the graph and so
792  /// is very inexpensive. It may change the connectivity graph of the SCCs
793  /// though, so be careful calling this while iterating over them.
794  void removeOutgoingEdge(Node &SourceN, Node &TargetN);
795 
796  /// Remove a list of ref edges which are entirely within this RefSCC.
797  ///
798  /// Both the \a SourceN and all of the \a TargetNs must be within this
799  /// RefSCC. Removing these edges may break cycles that form this RefSCC and
800  /// thus this operation may change the RefSCC graph significantly. In
801  /// particular, this operation will re-form new RefSCCs based on the
802  /// remaining connectivity of the graph. The following invariants are
803  /// guaranteed to hold after calling this method:
804  ///
805  /// 1) If a ref-cycle remains after removal, it leaves this RefSCC intact
806  /// and in the graph. No new RefSCCs are built.
807  /// 2) Otherwise, this RefSCC will be dead after this call and no longer in
808  /// the graph or the postorder traversal of the call graph. Any iterator
809  /// pointing at this RefSCC will become invalid.
810  /// 3) All newly formed RefSCCs will be returned and the order of the
811  /// RefSCCs returned will be a valid postorder traversal of the new
812  /// RefSCCs.
813  /// 4) No RefSCC other than this RefSCC has its member set changed (this is
814  /// inherent in the definition of removing such an edge).
815  ///
816  /// These invariants are very important to ensure that we can build
817  /// optimization pipelines on top of the CGSCC pass manager which
818  /// intelligently update the RefSCC graph without invalidating other parts
819  /// of the RefSCC graph.
820  ///
821  /// Note that we provide no routine to remove a *call* edge. Instead, you
822  /// must first switch it to a ref edge using \c switchInternalEdgeToRef.
823  /// This split API is intentional as each of these two steps can invalidate
824  /// a different aspect of the graph structure and needs to have the
825  /// invalidation handled independently.
826  ///
827  /// The runtime complexity of this method is, in the worst case, O(V+E)
828  /// where V is the number of nodes in this RefSCC and E is the number of
829  /// edges leaving the nodes in this RefSCC. Note that E includes both edges
830  /// within this RefSCC and edges from this RefSCC to child RefSCCs. Some
831  /// effort has been made to minimize the overhead of common cases such as
832  /// self-edges and edge removals which result in a spanning tree with no
833  /// more cycles.
834  [[nodiscard]] SmallVector<RefSCC *, 1>
835  removeInternalRefEdge(Node &SourceN, ArrayRef<Node *> TargetNs);
836 
837  /// A convenience wrapper around the above to handle trivial cases of
838  /// inserting a new call edge.
839  ///
840  /// This is trivial whenever the target is in the same SCC as the source or
841  /// the edge is an outgoing edge to some descendant SCC. In these cases
842  /// there is no change to the cyclic structure of SCCs or RefSCCs.
843  ///
844  /// To further make calling this convenient, it also handles inserting
845  /// already existing edges.
846  void insertTrivialCallEdge(Node &SourceN, Node &TargetN);
847 
848  /// A convenience wrapper around the above to handle trivial cases of
849  /// inserting a new ref edge.
850  ///
851  /// This is trivial whenever the target is in the same RefSCC as the source
852  /// or the edge is an outgoing edge to some descendant RefSCC. In these
853  /// cases there is no change to the cyclic structure of the RefSCCs.
854  ///
855  /// To further make calling this convenient, it also handles inserting
856  /// already existing edges.
857  void insertTrivialRefEdge(Node &SourceN, Node &TargetN);
858 
859  /// Directly replace a node's function with a new function.
860  ///
861  /// This should be used when moving the body and users of a function to
862  /// a new formal function object but not otherwise changing the call graph
863  /// structure in any way.
864  ///
865  /// It requires that the old function in the provided node have zero uses
866  /// and the new function must have calls and references to it establishing
867  /// an equivalent graph.
868  void replaceNodeFunction(Node &N, Function &NewF);
869 
870  ///@}
871  };
872 
873  /// A post-order depth-first RefSCC iterator over the call graph.
874  ///
875  /// This iterator walks the cached post-order sequence of RefSCCs. However,
876  /// it trades stability for flexibility. It is restricted to a forward
877  /// iterator but will survive mutations which insert new RefSCCs and continue
878  /// to point to the same RefSCC even if it moves in the post-order sequence.
880  : public iterator_facade_base<postorder_ref_scc_iterator,
881  std::forward_iterator_tag, RefSCC> {
882  friend class LazyCallGraph;
883  friend class LazyCallGraph::Node;
884 
885  /// Nonce type to select the constructor for the end iterator.
886  struct IsAtEndT {};
887 
888  LazyCallGraph *G;
889  RefSCC *RC = nullptr;
890 
891  /// Build the begin iterator for a node.
892  postorder_ref_scc_iterator(LazyCallGraph &G) : G(&G), RC(getRC(G, 0)) {
893  incrementUntilNonEmptyRefSCC();
894  }
895 
896  /// Build the end iterator for a node. This is selected purely by overload.
897  postorder_ref_scc_iterator(LazyCallGraph &G, IsAtEndT /*Nonce*/) : G(&G) {}
898 
899  /// Get the post-order RefSCC at the given index of the postorder walk,
900  /// populating it if necessary.
901  static RefSCC *getRC(LazyCallGraph &G, int Index) {
902  if (Index == (int)G.PostOrderRefSCCs.size())
903  // We're at the end.
904  return nullptr;
905 
906  return G.PostOrderRefSCCs[Index];
907  }
908 
909  // Keep incrementing until RC is non-empty (or null).
910  void incrementUntilNonEmptyRefSCC() {
911  while (RC && RC->size() == 0)
912  increment();
913  }
914 
915  void increment() {
916  assert(RC && "Cannot increment the end iterator!");
917  RC = getRC(*G, G->RefSCCIndices.find(RC)->second + 1);
918  }
919 
920  public:
922  return G == Arg.G && RC == Arg.RC;
923  }
924 
925  reference operator*() const { return *RC; }
926 
927  using iterator_facade_base::operator++;
929  increment();
930  incrementUntilNonEmptyRefSCC();
931  return *this;
932  }
933  };
934 
935  /// Construct a graph for the given module.
936  ///
937  /// This sets up the graph and computes all of the entry points of the graph.
938  /// No function definitions are scanned until their nodes in the graph are
939  /// requested during traversal.
942 
945 
946  bool invalidate(Module &, const PreservedAnalyses &PA,
948 
949  EdgeSequence::iterator begin() { return EntryEdges.begin(); }
950  EdgeSequence::iterator end() { return EntryEdges.end(); }
951 
952  void buildRefSCCs();
953 
955  if (!EntryEdges.empty())
956  assert(!PostOrderRefSCCs.empty() &&
957  "Must form RefSCCs before iterating them!");
958  return postorder_ref_scc_iterator(*this);
959  }
961  if (!EntryEdges.empty())
962  assert(!PostOrderRefSCCs.empty() &&
963  "Must form RefSCCs before iterating them!");
964  return postorder_ref_scc_iterator(*this,
965  postorder_ref_scc_iterator::IsAtEndT());
966  }
967 
970  }
971 
972  /// Lookup a function in the graph which has already been scanned and added.
973  Node *lookup(const Function &F) const { return NodeMap.lookup(&F); }
974 
975  /// Lookup a function's SCC in the graph.
976  ///
977  /// \returns null if the function hasn't been assigned an SCC via the RefSCC
978  /// iterator walk.
979  SCC *lookupSCC(Node &N) const { return SCCMap.lookup(&N); }
980 
981  /// Lookup a function's RefSCC in the graph.
982  ///
983  /// \returns null if the function hasn't been assigned a RefSCC via the
984  /// RefSCC iterator walk.
986  if (SCC *C = lookupSCC(N))
987  return &C->getOuterRefSCC();
988 
989  return nullptr;
990  }
991 
992  /// Get a graph node for a given function, scanning it to populate the graph
993  /// data as necessary.
995  Node *&N = NodeMap[&F];
996  if (N)
997  return *N;
998 
999  return insertInto(F, N);
1000  }
1001 
1002  /// Get the sequence of known and defined library functions.
1003  ///
1004  /// These functions, because they are known to LLVM, can have calls
1005  /// introduced out of thin air from arbitrary IR.
1007  return LibFunctions.getArrayRef();
1008  }
1009 
1010  /// Test whether a function is a known and defined library function tracked by
1011  /// the call graph.
1012  ///
1013  /// Because these functions are known to LLVM they are specially modeled in
1014  /// the call graph and even when all IR-level references have been removed
1015  /// remain active and reachable.
1016  bool isLibFunction(Function &F) const { return LibFunctions.count(&F); }
1017 
1018  ///@{
1019  /// \name Pre-SCC Mutation API
1020  ///
1021  /// These methods are only valid to call prior to forming any SCCs for this
1022  /// call graph. They can be used to update the core node-graph during
1023  /// a node-based inorder traversal that precedes any SCC-based traversal.
1024  ///
1025  /// Once you begin manipulating a call graph's SCCs, most mutation of the
1026  /// graph must be performed via a RefSCC method. There are some exceptions
1027  /// below.
1028 
1029  /// Update the call graph after inserting a new edge.
1030  void insertEdge(Node &SourceN, Node &TargetN, Edge::Kind EK);
1031 
1032  /// Update the call graph after inserting a new edge.
1034  return insertEdge(get(Source), get(Target), EK);
1035  }
1036 
1037  /// Update the call graph after deleting an edge.
1038  void removeEdge(Node &SourceN, Node &TargetN);
1039 
1040  /// Update the call graph after deleting an edge.
1042  return removeEdge(get(Source), get(Target));
1043  }
1044 
1045  ///@}
1046 
1047  ///@{
1048  /// \name General Mutation API
1049  ///
1050  /// There are a very limited set of mutations allowed on the graph as a whole
1051  /// once SCCs have started to be formed. These routines have strict contracts
1052  /// but may be called at any point.
1053 
1054  /// Remove a dead function from the call graph (typically to delete it).
1055  ///
1056  /// Note that the function must have an empty use list, and the call graph
1057  /// must be up-to-date prior to calling this. That means it is by itself in
1058  /// a maximal SCC which is by itself in a maximal RefSCC, etc. No structural
1059  /// changes result from calling this routine other than potentially removing
1060  /// entry points into the call graph.
1061  ///
1062  /// If SCC formation has begun, this function must not be part of the current
1063  /// DFS in order to call this safely. Typically, the function will have been
1064  /// fully visited by the DFS prior to calling this routine.
1065  void removeDeadFunction(Function &F);
1066 
1067  /// Add a new function split/outlined from an existing function.
1068  ///
1069  /// The new function may only reference other functions that the original
1070  /// function did.
1071  ///
1072  /// The original function must reference (either directly or indirectly) the
1073  /// new function.
1074  ///
1075  /// The new function may also reference the original function.
1076  /// It may end up in a parent SCC in the case that the original function's
1077  /// edge to the new function is a ref edge, and the edge back is a call edge.
1078  void addSplitFunction(Function &OriginalFunction, Function &NewFunction);
1079 
1080  /// Add new ref-recursive functions split/outlined from an existing function.
1081  ///
1082  /// The new functions may only reference other functions that the original
1083  /// function did. The new functions may reference (not call) the original
1084  /// function.
1085  ///
1086  /// The original function must reference (not call) all new functions.
1087  /// All new functions must reference (not call) each other.
1088  void addSplitRefRecursiveFunctions(Function &OriginalFunction,
1089  ArrayRef<Function *> NewFunctions);
1090 
1091  ///@}
1092 
1093  ///@{
1094  /// \name Static helpers for code doing updates to the call graph.
1095  ///
1096  /// These helpers are used to implement parts of the call graph but are also
1097  /// useful to code doing updates or otherwise wanting to walk the IR in the
1098  /// same patterns as when we build the call graph.
1099 
1100  /// Recursively visits the defined functions whose address is reachable from
1101  /// every constant in the \p Worklist.
1102  ///
1103  /// Doesn't recurse through any constants already in the \p Visited set, and
1104  /// updates that set with every constant visited.
1105  ///
1106  /// For each defined function, calls \p Callback with that function.
1107  static void visitReferences(SmallVectorImpl<Constant *> &Worklist,
1108  SmallPtrSetImpl<Constant *> &Visited,
1109  function_ref<void(Function &)> Callback);
1110 
1111  ///@}
1112 
1113 private:
1114  using node_stack_iterator = SmallVectorImpl<Node *>::reverse_iterator;
1115  using node_stack_range = iterator_range<node_stack_iterator>;
1116 
1117  /// Allocator that holds all the call graph nodes.
1119 
1120  /// Maps function->node for fast lookup.
1122 
1123  /// The entry edges into the graph.
1124  ///
1125  /// These edges are from "external" sources. Put another way, they
1126  /// escape at the module scope.
1127  EdgeSequence EntryEdges;
1128 
1129  /// Allocator that holds all the call graph SCCs.
1131 
1132  /// Maps Function -> SCC for fast lookup.
1133  DenseMap<Node *, SCC *> SCCMap;
1134 
1135  /// Allocator that holds all the call graph RefSCCs.
1137 
1138  /// The post-order sequence of RefSCCs.
1139  ///
1140  /// This list is lazily formed the first time we walk the graph.
1141  SmallVector<RefSCC *, 16> PostOrderRefSCCs;
1142 
1143  /// A map from RefSCC to the index for it in the postorder sequence of
1144  /// RefSCCs.
1145  DenseMap<RefSCC *, int> RefSCCIndices;
1146 
1147  /// Defined functions that are also known library functions which the
1148  /// optimizer can reason about and therefore might introduce calls to out of
1149  /// thin air.
1150  SmallSetVector<Function *, 4> LibFunctions;
1151 
1152  /// Helper to insert a new function, with an already looked-up entry in
1153  /// the NodeMap.
1154  Node &insertInto(Function &F, Node *&MappedN);
1155 
1156  /// Helper to initialize a new node created outside of creating SCCs and add
1157  /// it to the NodeMap if necessary. For example, useful when a function is
1158  /// split.
1159  Node &initNode(Function &F);
1160 
1161  /// Helper to update pointers back to the graph object during moves.
1162  void updateGraphPtrs();
1163 
1164  /// Allocates an SCC and constructs it using the graph allocator.
1165  ///
1166  /// The arguments are forwarded to the constructor.
1167  template <typename... Ts> SCC *createSCC(Ts &&...Args) {
1168  return new (SCCBPA.Allocate()) SCC(std::forward<Ts>(Args)...);
1169  }
1170 
1171  /// Allocates a RefSCC and constructs it using the graph allocator.
1172  ///
1173  /// The arguments are forwarded to the constructor.
1174  template <typename... Ts> RefSCC *createRefSCC(Ts &&...Args) {
1175  return new (RefSCCBPA.Allocate()) RefSCC(std::forward<Ts>(Args)...);
1176  }
1177 
1178  /// Common logic for building SCCs from a sequence of roots.
1179  ///
1180  /// This is a very generic implementation of the depth-first walk and SCC
1181  /// formation algorithm. It uses a generic sequence of roots and generic
1182  /// callbacks for each step. This is designed to be used to implement both
1183  /// the RefSCC formation and SCC formation with shared logic.
1184  ///
1185  /// Currently this is a relatively naive implementation of Tarjan's DFS
1186  /// algorithm to form the SCCs.
1187  ///
1188  /// FIXME: We should consider newer variants such as Nuutila.
1189  template <typename RootsT, typename GetBeginT, typename GetEndT,
1190  typename GetNodeT, typename FormSCCCallbackT>
1191  static void buildGenericSCCs(RootsT &&Roots, GetBeginT &&GetBegin,
1192  GetEndT &&GetEnd, GetNodeT &&GetNode,
1193  FormSCCCallbackT &&FormSCC);
1194 
1195  /// Build the SCCs for a RefSCC out of a list of nodes.
1196  void buildSCCs(RefSCC &RC, node_stack_range Nodes);
1197 
1198  /// Get the index of a RefSCC within the postorder traversal.
1199  ///
1200  /// Requires that this RefSCC is a valid one in the (perhaps partial)
1201  /// postorder traversed part of the graph.
1202  int getRefSCCIndex(RefSCC &RC) {
1203  auto IndexIt = RefSCCIndices.find(&RC);
1204  assert(IndexIt != RefSCCIndices.end() && "RefSCC doesn't have an index!");
1205  assert(PostOrderRefSCCs[IndexIt->second] == &RC &&
1206  "Index does not point back at RC!");
1207  return IndexIt->second;
1208  }
1209 };
1210 
1211 inline LazyCallGraph::Edge::Edge() = default;
1213 
1214 inline LazyCallGraph::Edge::operator bool() const {
1215  return Value.getPointer() && !Value.getPointer()->isDead();
1216 }
1217 
1219  assert(*this && "Queried a null edge!");
1220  return Value.getInt();
1221 }
1222 
1223 inline bool LazyCallGraph::Edge::isCall() const {
1224  assert(*this && "Queried a null edge!");
1225  return getKind() == Call;
1226 }
1227 
1229  assert(*this && "Queried a null edge!");
1230  return *Value.getPointer();
1231 }
1232 
1234  assert(*this && "Queried a null edge!");
1235  return getNode().getFunction();
1236 }
1237 
1238 // Provide GraphTraits specializations for call graphs.
1239 template <> struct GraphTraits<LazyCallGraph::Node *> {
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 template <> struct GraphTraits<LazyCallGraph *> {
1250 
1251  static NodeRef getEntryNode(NodeRef N) { return N; }
1252  static ChildIteratorType child_begin(NodeRef N) { return (*N)->begin(); }
1253  static ChildIteratorType child_end(NodeRef N) { return (*N)->end(); }
1254 };
1255 
1256 /// An analysis pass which computes the call graph for a module.
1257 class LazyCallGraphAnalysis : public AnalysisInfoMixin<LazyCallGraphAnalysis> {
1259 
1260  static AnalysisKey Key;
1261 
1262 public:
1263  /// Inform generic clients of the result type.
1265 
1266  /// Compute the \c LazyCallGraph for the module \c M.
1267  ///
1268  /// This just builds the set of entry points to the call graph. The rest is
1269  /// built lazily as it is walked.
1273  auto GetTLI = [&FAM](Function &F) -> TargetLibraryInfo & {
1274  return FAM.getResult<TargetLibraryAnalysis>(F);
1275  };
1276  return LazyCallGraph(M, GetTLI);
1277  }
1278 };
1279 
1280 /// A pass which prints the call graph to a \c raw_ostream.
1281 ///
1282 /// This is primarily useful for testing the analysis.
1284  : public PassInfoMixin<LazyCallGraphPrinterPass> {
1285  raw_ostream &OS;
1286 
1287 public:
1288  explicit LazyCallGraphPrinterPass(raw_ostream &OS);
1289 
1291 };
1292 
1293 /// A pass which prints the call graph as a DOT file to a \c raw_ostream.
1294 ///
1295 /// This is primarily useful for visualization purposes.
1297  : public PassInfoMixin<LazyCallGraphDOTPrinterPass> {
1298  raw_ostream &OS;
1299 
1300 public:
1302 
1304 };
1305 
1306 } // end namespace llvm
1307 
1308 #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:921
llvm::LazyCallGraph::RefSCC::find
iterator find(SCC &C) const
Definition: LazyCallGraph.h:619
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:628
llvm::LazyCallGraph::RefSCC::size
ssize_t size() const
Definition: LazyCallGraph.h:615
llvm::LazyCallGraph::EdgeSequence::call_end
call_iterator call_end()
Definition: LazyCallGraph.h:275
llvm::Target
Target - Wrapper for Target specific information.
Definition: TargetRegistry.h:145
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: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: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:382
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:973
llvm::Optional
Definition: APInt.h:33
llvm::GraphTraits< LazyCallGraph * >::child_end
static ChildIteratorType child_end(NodeRef N)
Definition: LazyCallGraph.h:1253
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:954
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: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: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:1228
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:419
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:1283
llvm::LazyCallGraph::postorder_ref_scc_iterator::operator++
postorder_ref_scc_iterator & operator++()
Definition: LazyCallGraph.h:928
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::LazyCallGraph::end
EdgeSequence::iterator end()
Definition: LazyCallGraph.h:950
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: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:1041
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:544
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:52
llvm::raw_ostream::flush
void flush()
Definition: raw_ostream.h:185
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:979
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:1033
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:882
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:994
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: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:1296
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:742
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:110
Index
uint32_t Index
Definition: ELFObjHandler.cpp:82
llvm::LazyCallGraph::RefSCC::isDescendantOf
bool isDescendantOf(const RefSCC &RC) const
Test if this RefSCC is a descendant of RC.
Definition: LazyCallGraph.h:647
llvm::Optional::reset
void reset()
Definition: Optional.h:309
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:985
llvm::LazyCallGraph::RefSCC::getName
std::string getName() const
Provide a short name by printing this RefSCC to a std::string.
Definition: LazyCallGraph.h:655
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:320
llvm::GraphTraits< LazyCallGraph::Node * >::child_begin
static ChildIteratorType child_begin(NodeRef N)
Definition: LazyCallGraph.h:1244
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:949
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:1245
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: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:1233
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:879
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:307
llvm::LazyCallGraph::Edge
A class used to represent edges in the call graph.
Definition: LazyCallGraph.h:131
llvm::Sched::Source
@ Source
Definition: TargetLowering.h:98
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:480
llvm::LazyCallGraphAnalysis::run
LazyCallGraph run(Module &M, ModuleAnalysisManager &AM)
Compute the LazyCallGraph for the module M.
Definition: LazyCallGraph.h:1270
llvm::LazyCallGraph::RefSCC::begin
iterator begin() const
Definition: LazyCallGraph.h:612
llvm::LazyCallGraph::Edge::getKind
Kind getKind() const
Returns the Kind of the edge.
Definition: LazyCallGraph.h:1218
llvm::GraphTraits< LazyCallGraph::Node * >::getEntryNode
static NodeRef getEntryNode(NodeRef N)
Definition: LazyCallGraph.h:1243
llvm::LazyCallGraph::postorder_ref_scc_end
postorder_ref_scc_iterator postorder_ref_scc_end()
Definition: LazyCallGraph.h:960
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:1442
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:432
llvm::LazyCallGraph::postorder_ref_scc_iterator::operator*
reference operator*() const
Definition: LazyCallGraph.h:925
llvm::LazyCallGraph::getLibFunctions
ArrayRef< Function * > getLibFunctions() const
Get the sequence of known and defined library functions.
Definition: LazyCallGraph.h:1006
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: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:572
llvm::LazyCallGraph::Edge::isCall
bool isCall() const
Test whether the edge represents a direct call to a function.
Definition: LazyCallGraph.h:1223
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:1251
llvm::LazyCallGraphAnalysis
An analysis pass which computes the call graph for a module.
Definition: LazyCallGraph.h:1257
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:1016
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:225
verify
ppc ctr loops verify
Definition: PPCCTRLoopsVerify.cpp:76
llvm::GraphTraits< LazyCallGraph * >::child_begin
static ChildIteratorType child_begin(NodeRef N)
Definition: LazyCallGraph.h:1252
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:596
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:617
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: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:223
llvm::SmallVectorImpl::iterator
typename SuperClass::iterator iterator
Definition: SmallVector.h:563
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:922
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:968
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:931
llvm::LazyCallGraph::RefSCC::isChildOf
bool isChildOf(const RefSCC &RC) const
Test if this RefSCC is a child of RC.
Definition: LazyCallGraph.h:640
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:1960
llvm::LazyCallGraph::RefSCC::end
iterator end() const
Definition: LazyCallGraph.h:613
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:449
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: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:442