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