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