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