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