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

source code of llvm/include/llvm/Analysis/LazyCallGraph.h