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