1 //===- LazyCallGraph.h - Analysis of a Module's call graph ------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
11 /// Implements a lazy call graph analysis and related passes for the new pass
14 /// NB: This is *not* a traditional call graph! It is a graph which models both
15 /// the current calls and potential calls. As a consequence there are many
16 /// edges in this call graph that do not correspond to a 'call' or 'invoke'
19 /// The primary use cases of this graph analysis is to facilitate iterating
20 /// across the functions of a module in ways that ensure all callees are
21 /// visited prior to a caller (given any SCC constraints), or vice versa. As
22 /// such is it particularly well suited to organizing CGSCC optimizations such
23 /// as inlining, outlining, argument promotion, etc. That is its primary use
24 /// case and motivates the design. It may not be appropriate for other
25 /// purposes. The use graph of functions or some other conservative analysis of
26 /// call instructions may be interesting for optimizations and subsequent
27 /// analyses which don't work in the context of an overly specified
28 /// potential-call-edge graph.
30 /// To understand the specific rules and nature of this call graph analysis,
31 /// see the documentation of the \c LazyCallGraph below.
33 //===----------------------------------------------------------------------===//
35 #ifndef LLVM_ANALYSIS_LAZYCALLGRAPH_H
36 #define LLVM_ANALYSIS_LAZYCALLGRAPH_H
38 #include "llvm/ADT/DenseMap.h"
39 #include "llvm/ADT/PointerUnion.h"
40 #include "llvm/ADT/STLExtras.h"
41 #include "llvm/ADT/SetVector.h"
42 #include "llvm/ADT/SmallPtrSet.h"
43 #include "llvm/ADT/SmallVector.h"
44 #include "llvm/ADT/iterator.h"
45 #include "llvm/ADT/iterator_range.h"
46 #include "llvm/Analysis/TargetLibraryInfo.h"
47 #include "llvm/IR/BasicBlock.h"
48 #include "llvm/IR/Constants.h"
49 #include "llvm/IR/Function.h"
50 #include "llvm/IR/Module.h"
51 #include "llvm/IR/PassManager.h"
52 #include "llvm/Support/Allocator.h"
53 #include "llvm/Support/raw_ostream.h"
58 class PreservedAnalyses;
61 /// A lazily constructed view of the call graph of a module.
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
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.
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.
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.
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.
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.
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.
107 class LazyCallGraph {
114 class call_edge_iterator;
116 /// A class used to represent edges in the call graph.
118 /// The lazy call graph models both *call* edges and *reference* edges. Call
119 /// edges are much what you would expect, and exist when there is a 'call' or
120 /// 'invoke' instruction of some function. Reference edges are also tracked
121 /// along side these, and exist whenever any instruction (transitively
122 /// through its operands) references a function. All call edges are
123 /// inherently reference edges, and so the reference graph forms a superset
124 /// of the formal call graph.
126 /// All of these forms of edges are fundamentally represented as outgoing
127 /// edges. The edges are stored in the source node and point at the target
128 /// node. This allows the edge structure itself to be a very compact data
129 /// structure: essentially a tagged pointer.
132 /// The kind of edge in the graph.
133 enum Kind : bool { Ref = false, Call = true };
136 explicit Edge(Node &N, Kind K);
138 /// Test whether the edge is null.
140 /// This happens when an edge has been deleted. We leave the edge objects
141 /// around but clear them.
142 explicit operator bool() const;
144 /// Returnss the \c Kind of the edge.
145 Kind getKind() const;
147 /// Test whether the edge represents a direct call to a function.
149 /// This requires that the edge is not null.
152 /// Get the call graph node referenced by this edge.
154 /// This requires that the edge is not null.
155 Node &getNode() const;
157 /// Get the function referenced by this edge.
159 /// This requires that the edge is not null.
160 Function &getFunction() const;
163 friend class LazyCallGraph::EdgeSequence;
164 friend class LazyCallGraph::RefSCC;
166 PointerIntPair<Node *, 1, Kind> Value;
168 void setKind(Kind K) { Value.setInt(K); }
171 /// The edge sequence object.
173 /// This typically exists entirely within the node but is exposed as
174 /// a separate type because a node doesn't initially have edges. An explicit
175 /// population step is required to produce this sequence at first and it is
176 /// then cached in the node. It is also used to represent edges entering the
177 /// graph from outside the module to model the graph's roots.
179 /// The sequence itself both iterable and indexable. The indexes remain
180 /// stable even as the sequence mutates (including removal).
182 friend class LazyCallGraph;
183 friend class LazyCallGraph::Node;
184 friend class LazyCallGraph::RefSCC;
186 typedef SmallVector<Edge, 4> VectorT;
187 typedef SmallVectorImpl<Edge> VectorImplT;
190 /// An iterator used for the edges to both entry nodes and child nodes.
192 : public iterator_adaptor_base<iterator, VectorImplT::iterator,
193 std::forward_iterator_tag> {
194 friend class LazyCallGraph;
195 friend class LazyCallGraph::Node;
197 VectorImplT::iterator E;
199 // Build the iterator for a specific position in the edge list.
200 iterator(VectorImplT::iterator BaseI, VectorImplT::iterator E)
201 : iterator_adaptor_base(BaseI), E(E) {
202 while (I != E && !*I)
209 using iterator_adaptor_base::operator++;
210 iterator &operator++() {
213 } while (I != E && !*I);
218 /// An iterator over specifically call edges.
220 /// This has the same iteration properties as the \c iterator, but
221 /// restricts itself to edges which represent actual calls.
223 : public iterator_adaptor_base<call_iterator, VectorImplT::iterator,
224 std::forward_iterator_tag> {
225 friend class LazyCallGraph;
226 friend class LazyCallGraph::Node;
228 VectorImplT::iterator E;
230 /// Advance the iterator to the next valid, call edge.
231 void advanceToNextEdge() {
232 while (I != E && (!*I || !I->isCall()))
236 // Build the iterator for a specific position in the edge list.
237 call_iterator(VectorImplT::iterator BaseI, VectorImplT::iterator E)
238 : iterator_adaptor_base(BaseI), E(E) {
245 using iterator_adaptor_base::operator++;
246 call_iterator &operator++() {
253 iterator begin() { return iterator(Edges.begin(), Edges.end()); }
254 iterator end() { return iterator(Edges.end(), Edges.end()); }
256 Edge &operator[](int i) { return Edges[i]; }
257 Edge &operator[](Node &N) {
258 assert(EdgeIndexMap.find(&N) != EdgeIndexMap.end() && "No such edge!");
259 return Edges[EdgeIndexMap.find(&N)->second];
261 Edge *lookup(Node &N) {
262 auto EI = EdgeIndexMap.find(&N);
263 return EI != EdgeIndexMap.end() ? &Edges[EI->second] : nullptr;
266 call_iterator call_begin() {
267 return call_iterator(Edges.begin(), Edges.end());
269 call_iterator call_end() { return call_iterator(Edges.end(), Edges.end()); }
271 iterator_range<call_iterator> calls() {
272 return make_range(call_begin(), call_end());
276 for (auto &E : Edges)
285 DenseMap<Node *, int> EdgeIndexMap;
287 EdgeSequence() = default;
289 /// Internal helper to insert an edge to a node.
290 void insertEdgeInternal(Node &ChildN, Edge::Kind EK);
292 /// Internal helper to change an edge kind.
293 void setEdgeKind(Node &ChildN, Edge::Kind EK);
295 /// Internal helper to remove the edge to the given function.
296 bool removeEdgeInternal(Node &ChildN);
298 /// Internal helper to replace an edge key with a new one.
300 /// This should be used when the function for a particular node in the
301 /// graph gets replaced and we are updating all of the edges to that node
302 /// to use the new function as the key.
303 void replaceEdgeKey(Function &OldTarget, Function &NewTarget);
306 /// A node in the call graph.
308 /// This represents a single node. It's primary roles are to cache the list of
309 /// callees, de-duplicate and provide fast testing of whether a function is
310 /// a callee, and facilitate iteration of child nodes in the graph.
312 /// The node works much like an optional in order to lazily populate the
313 /// edges of each node. Until populated, there are no edges. Once populated,
314 /// you can access the edges by dereferencing the node or using the `->`
315 /// operator as if the node was an `Optional<EdgeSequence>`.
317 friend class LazyCallGraph;
318 friend class LazyCallGraph::RefSCC;
321 LazyCallGraph &getGraph() const { return *G; }
323 Function &getFunction() const { return *F; }
325 StringRef getName() const { return F->getName(); }
327 /// Equality is defined as address equality.
328 bool operator==(const Node &N) const { return this == &N; }
329 bool operator!=(const Node &N) const { return !operator==(N); }
331 /// Tests whether the node has been populated with edges.
332 operator bool() const { return Edges.hasValue(); }
334 // We allow accessing the edges by dereferencing or using the arrow
335 // operator, essentially wrapping the internal optional.
336 EdgeSequence &operator*() const {
337 // Rip const off because the node itself isn't changing here.
338 return const_cast<EdgeSequence &>(*Edges);
340 EdgeSequence *operator->() const { return &**this; }
342 /// Populate the edges of this node if necessary.
344 /// The first time this is called it will populate the edges for this node
345 /// in the graph. It does this by scanning the underlying function, so once
346 /// this is done, any changes to that function must be explicitly reflected
347 /// in updates to the graph.
349 /// \returns the populated \c EdgeSequence to simplify walking it.
351 /// This will not update or re-scan anything if called repeatedly. Instead,
352 /// the edge sequence is cached and returned immediately on subsequent
354 EdgeSequence &populate() {
358 return populateSlow();
365 // We provide for the DFS numbering and Tarjan walk lowlink numbers to be
366 // stored directly within the node. These are both '-1' when nodes are part
367 // of an SCC (or RefSCC), or '0' when not yet reached in a DFS walk.
371 Optional<EdgeSequence> Edges;
373 /// Basic constructor implements the scanning of F into Edges and
375 Node(LazyCallGraph &G, Function &F)
376 : G(&G), F(&F), DFSNumber(0), LowLink(0) {}
378 /// Implementation of the scan when populating.
379 EdgeSequence &populateSlow();
381 /// Internal helper to directly replace the function with a new one.
383 /// This is used to facilitate tranfsormations which need to replace the
384 /// formal Function object but directly move the body and users from one to
386 void replaceFunction(Function &NewF);
388 void clear() { Edges.reset(); }
390 /// Print the name of this node's function.
391 friend raw_ostream &operator<<(raw_ostream &OS, const Node &N) {
392 return OS << N.F->getName();
395 /// Dump the name of this node's function to stderr.
399 /// An SCC of the call graph.
401 /// This represents a Strongly Connected Component of the direct call graph
402 /// -- ignoring indirect calls and function references. It stores this as
403 /// a collection of call graph nodes. While the order of nodes in the SCC is
404 /// stable, it is not any particular order.
406 /// The SCCs are nested within a \c RefSCC, see below for details about that
407 /// outer structure. SCCs do not support mutation of the call graph, that
408 /// must be done through the containing \c RefSCC in order to fully reason
409 /// about the ordering and connections of the graph.
411 friend class LazyCallGraph;
412 friend class LazyCallGraph::Node;
415 SmallVector<Node *, 1> Nodes;
417 template <typename NodeRangeT>
418 SCC(RefSCC &OuterRefSCC, NodeRangeT &&Nodes)
419 : OuterRefSCC(&OuterRefSCC), Nodes(std::forward<NodeRangeT>(Nodes)) {}
422 OuterRefSCC = nullptr;
426 /// Print a short descrtiption useful for debugging or logging.
428 /// We print the function names in the SCC wrapped in '()'s and skipping
429 /// the middle functions if there are a large number.
431 // Note: this is defined inline to dodge issues with GCC's interpretation
432 // of enclosing namespaces for friend function declarations.
433 friend raw_ostream &operator<<(raw_ostream &OS, const SCC &C) {
436 for (LazyCallGraph::Node &N : C) {
439 // Elide the inner elements if there are too many.
441 OS << "..., " << *C.Nodes.back();
451 /// Dump a short description of this SCC to stderr.
455 /// Verify invariants about the SCC.
457 /// This will attempt to validate all of the basic invariants within an
458 /// SCC, but not that it is a strongly connected componet per-se. Primarily
459 /// useful while building and updating the graph to check that basic
460 /// properties are in place rather than having inexplicable crashes later.
465 typedef pointee_iterator<SmallVectorImpl<Node *>::const_iterator> iterator;
467 iterator begin() const { return Nodes.begin(); }
468 iterator end() const { return Nodes.end(); }
470 int size() const { return Nodes.size(); }
472 RefSCC &getOuterRefSCC() const { return *OuterRefSCC; }
474 /// Test if this SCC is a parent of \a C.
476 /// Note that this is linear in the number of edges departing the current
478 bool isParentOf(const SCC &C) const;
480 /// Test if this SCC is an ancestor of \a C.
482 /// Note that in the worst case this is linear in the number of edges
483 /// departing the current SCC and every SCC in the entire graph reachable
484 /// from this SCC. Thus this very well may walk every edge in the entire
485 /// call graph! Do not call this in a tight loop!
486 bool isAncestorOf(const SCC &C) const;
488 /// Test if this SCC is a child of \a C.
490 /// See the comments for \c isParentOf for detailed notes about the
491 /// complexity of this routine.
492 bool isChildOf(const SCC &C) const { return C.isParentOf(*this); }
494 /// Test if this SCC is a descendant of \a C.
496 /// See the comments for \c isParentOf for detailed notes about the
497 /// complexity of this routine.
498 bool isDescendantOf(const SCC &C) const { return C.isAncestorOf(*this); }
500 /// Provide a short name by printing this SCC to a std::string.
502 /// This copes with the fact that we don't have a name per-se for an SCC
503 /// while still making the use of this in debugging and logging useful.
504 std::string getName() const {
506 raw_string_ostream OS(Name);
513 /// A RefSCC of the call graph.
515 /// This models a Strongly Connected Component of function reference edges in
516 /// the call graph. As opposed to actual SCCs, these can be used to scope
517 /// subgraphs of the module which are independent from other subgraphs of the
518 /// module because they do not reference it in any way. This is also the unit
519 /// where we do mutation of the graph in order to restrict mutations to those
520 /// which don't violate this independence.
522 /// A RefSCC contains a DAG of actual SCCs. All the nodes within the RefSCC
523 /// are necessarily within some actual SCC that nests within it. Since
524 /// a direct call *is* a reference, there will always be at least one RefSCC
527 friend class LazyCallGraph;
528 friend class LazyCallGraph::Node;
531 SmallPtrSet<RefSCC *, 1> Parents;
533 /// A postorder list of the inner SCCs.
534 SmallVector<SCC *, 4> SCCs;
536 /// A map from SCC to index in the postorder list.
537 SmallDenseMap<SCC *, int, 4> SCCIndices;
539 /// Fast-path constructor. RefSCCs should instead be constructed by calling
540 /// formRefSCCFast on the graph itself.
541 RefSCC(LazyCallGraph &G);
549 /// Print a short description useful for debugging or logging.
551 /// We print the SCCs wrapped in '[]'s and skipping the middle SCCs if
552 /// there are a large number.
554 // Note: this is defined inline to dodge issues with GCC's interpretation
555 // of enclosing namespaces for friend function declarations.
556 friend raw_ostream &operator<<(raw_ostream &OS, const RefSCC &RC) {
559 for (LazyCallGraph::SCC &C : RC) {
562 // Elide the inner elements if there are too many.
564 OS << "..., " << *RC.SCCs.back();
574 /// Dump a short description of this RefSCC to stderr.
578 /// Verify invariants about the RefSCC and all its SCCs.
580 /// This will attempt to validate all of the invariants *within* the
581 /// RefSCC, but not that it is a strongly connected component of the larger
582 /// graph. This makes it useful even when partially through an update.
584 /// Invariants checked:
585 /// - SCCs and their indices match.
586 /// - The SCCs list is in fact in post-order.
590 /// Handle any necessary parent set updates after inserting a trivial ref
592 void handleTrivialEdgeInsertion(Node &SourceN, Node &TargetN);
595 typedef pointee_iterator<SmallVectorImpl<SCC *>::const_iterator> iterator;
596 typedef iterator_range<iterator> range;
597 typedef pointee_iterator<SmallPtrSetImpl<RefSCC *>::const_iterator>
600 iterator begin() const { return SCCs.begin(); }
601 iterator end() const { return SCCs.end(); }
603 ssize_t size() const { return SCCs.size(); }
605 SCC &operator[](int Idx) { return *SCCs[Idx]; }
607 iterator find(SCC &C) const {
608 return SCCs.begin() + SCCIndices.find(&C)->second;
611 parent_iterator parent_begin() const { return Parents.begin(); }
612 parent_iterator parent_end() const { return Parents.end(); }
614 iterator_range<parent_iterator> parents() const {
615 return make_range(parent_begin(), parent_end());
618 /// Test if this RefSCC is a parent of \a C.
619 bool isParentOf(const RefSCC &C) const { return C.isChildOf(*this); }
621 /// Test if this RefSCC is an ancestor of \a C.
622 bool isAncestorOf(const RefSCC &C) const { return C.isDescendantOf(*this); }
624 /// Test if this RefSCC is a child of \a C.
625 bool isChildOf(const RefSCC &C) const {
626 return Parents.count(const_cast<RefSCC *>(&C));
629 /// Test if this RefSCC is a descendant of \a C.
630 bool isDescendantOf(const RefSCC &C) const;
632 /// Provide a short name by printing this RefSCC to a std::string.
634 /// This copes with the fact that we don't have a name per-se for an RefSCC
635 /// while still making the use of this in debugging and logging useful.
636 std::string getName() const {
638 raw_string_ostream OS(Name);
645 /// \name Mutation API
647 /// These methods provide the core API for updating the call graph in the
648 /// presence of (potentially still in-flight) DFS-found RefSCCs and SCCs.
650 /// Note that these methods sometimes have complex runtimes, so be careful
651 /// how you call them.
653 /// Make an existing internal ref edge into a call edge.
655 /// This may form a larger cycle and thus collapse SCCs into TargetN's SCC.
656 /// If that happens, the optional callback \p MergedCB will be invoked (if
657 /// provided) on the SCCs being merged away prior to actually performing
658 /// the merge. Note that this will never include the target SCC as that
659 /// will be the SCC functions are merged into to resolve the cycle. Once
660 /// this function returns, these merged SCCs are not in a valid state but
661 /// the pointers will remain valid until destruction of the parent graph
662 /// instance for the purpose of clearing cached information. This function
663 /// also returns 'true' if a cycle was formed and some SCCs merged away as
666 /// After this operation, both SourceN's SCC and TargetN's SCC may move
667 /// position within this RefSCC's postorder list. Any SCCs merged are
668 /// merged into the TargetN's SCC in order to preserve reachability analyses
669 /// which took place on that SCC.
670 bool switchInternalEdgeToCall(
671 Node &SourceN, Node &TargetN,
672 function_ref<void(ArrayRef<SCC *> MergedSCCs)> MergeCB = {});
674 /// Make an existing internal call edge between separate SCCs into a ref
677 /// If SourceN and TargetN in separate SCCs within this RefSCC, changing
678 /// the call edge between them to a ref edge is a trivial operation that
679 /// does not require any structural changes to the call graph.
680 void switchTrivialInternalEdgeToRef(Node &SourceN, Node &TargetN);
682 /// Make an existing internal call edge within a single SCC into a ref
685 /// Since SourceN and TargetN are part of a single SCC, this SCC may be
686 /// split up due to breaking a cycle in the call edges that formed it. If
687 /// that happens, then this routine will insert new SCCs into the postorder
688 /// list *before* the SCC of TargetN (previously the SCC of both). This
689 /// preserves postorder as the TargetN can reach all of the other nodes by
690 /// definition of previously being in a single SCC formed by the cycle from
691 /// SourceN to TargetN.
693 /// The newly added SCCs are added *immediately* and contiguously
694 /// prior to the TargetN SCC and return the range covering the new SCCs in
695 /// the RefSCC's postorder sequence. You can directly iterate the returned
696 /// range to observe all of the new SCCs in postorder.
698 /// Note that if SourceN and TargetN are in separate SCCs, the simpler
699 /// routine `switchTrivialInternalEdgeToRef` should be used instead.
700 iterator_range<iterator> switchInternalEdgeToRef(Node &SourceN,
703 /// Make an existing outgoing ref edge into a call edge.
705 /// Note that this is trivial as there are no cyclic impacts and there
706 /// remains a reference edge.
707 void switchOutgoingEdgeToCall(Node &SourceN, Node &TargetN);
709 /// Make an existing outgoing call edge into a ref edge.
711 /// This is trivial as there are no cyclic impacts and there remains
712 /// a reference edge.
713 void switchOutgoingEdgeToRef(Node &SourceN, Node &TargetN);
715 /// Insert a ref edge from one node in this RefSCC to another in this
718 /// This is always a trivial operation as it doesn't change any part of the
719 /// graph structure besides connecting the two nodes.
721 /// Note that we don't support directly inserting internal *call* edges
722 /// because that could change the graph structure and requires returning
723 /// information about what became invalid. As a consequence, the pattern
724 /// should be to first insert the necessary ref edge, and then to switch it
725 /// to a call edge if needed and handle any invalidation that results. See
726 /// the \c switchInternalEdgeToCall routine for details.
727 void insertInternalRefEdge(Node &SourceN, Node &TargetN);
729 /// Insert an edge whose parent is in this RefSCC and child is in some
732 /// There must be an existing path from the \p SourceN to the \p TargetN.
733 /// This operation is inexpensive and does not change the set of SCCs and
734 /// RefSCCs in the graph.
735 void insertOutgoingEdge(Node &SourceN, Node &TargetN, Edge::Kind EK);
737 /// Insert an edge whose source is in a descendant RefSCC and target is in
740 /// There must be an existing path from the target to the source in this
743 /// NB! This is has the potential to be a very expensive function. It
744 /// inherently forms a cycle in the prior RefSCC DAG and we have to merge
745 /// RefSCCs to resolve that cycle. But finding all of the RefSCCs which
746 /// participate in the cycle can in the worst case require traversing every
747 /// RefSCC in the graph. Every attempt is made to avoid that, but passes
748 /// must still exercise caution calling this routine repeatedly.
750 /// Also note that this can only insert ref edges. In order to insert
751 /// a call edge, first insert a ref edge and then switch it to a call edge.
752 /// These are intentionally kept as separate interfaces because each step
753 /// of the operation invalidates a different set of data structures.
755 /// This returns all the RefSCCs which were merged into the this RefSCC
756 /// (the target's). This allows callers to invalidate any cached
759 /// FIXME: We could possibly optimize this quite a bit for cases where the
760 /// caller and callee are very nearby in the graph. See comments in the
761 /// implementation for details, but that use case might impact users.
762 SmallVector<RefSCC *, 1> insertIncomingRefEdge(Node &SourceN,
765 /// Remove an edge whose source is in this RefSCC and target is *not*.
767 /// This removes an inter-RefSCC edge. All inter-RefSCC edges originating
768 /// from this SCC have been fully explored by any in-flight DFS graph
769 /// formation, so this is always safe to call once you have the source
772 /// This operation does not change the cyclic structure of the graph and so
773 /// is very inexpensive. It may change the connectivity graph of the SCCs
774 /// though, so be careful calling this while iterating over them.
775 void removeOutgoingEdge(Node &SourceN, Node &TargetN);
777 /// Remove a ref edge which is entirely within this RefSCC.
779 /// Both the \a SourceN and the \a TargetN must be within this RefSCC.
780 /// Removing such an edge may break cycles that form this RefSCC and thus
781 /// this operation may change the RefSCC graph significantly. In
782 /// particular, this operation will re-form new RefSCCs based on the
783 /// remaining connectivity of the graph. The following invariants are
784 /// guaranteed to hold after calling this method:
786 /// 1) This RefSCC is still a RefSCC in the graph.
787 /// 2) This RefSCC will be the parent of any new RefSCCs. Thus, this RefSCC
788 /// is preserved as the root of any new RefSCC DAG formed.
789 /// 3) No RefSCC other than this RefSCC has its member set changed (this is
790 /// inherent in the definition of removing such an edge).
791 /// 4) All of the parent links of the RefSCC graph will be updated to
792 /// reflect the new RefSCC structure.
793 /// 5) All RefSCCs formed out of this RefSCC, excluding this RefSCC, will
794 /// be returned in post-order.
795 /// 6) The order of the RefSCCs in the vector will be a valid postorder
796 /// traversal of the new RefSCCs.
798 /// These invariants are very important to ensure that we can build
799 /// optimization pipelines on top of the CGSCC pass manager which
800 /// intelligently update the RefSCC graph without invalidating other parts
801 /// of the RefSCC graph.
803 /// Note that we provide no routine to remove a *call* edge. Instead, you
804 /// must first switch it to a ref edge using \c switchInternalEdgeToRef.
805 /// This split API is intentional as each of these two steps can invalidate
806 /// a different aspect of the graph structure and needs to have the
807 /// invalidation handled independently.
809 /// The runtime complexity of this method is, in the worst case, O(V+E)
810 /// where V is the number of nodes in this RefSCC and E is the number of
811 /// edges leaving the nodes in this RefSCC. Note that E includes both edges
812 /// within this RefSCC and edges from this RefSCC to child RefSCCs. Some
813 /// effort has been made to minimize the overhead of common cases such as
814 /// self-edges and edge removals which result in a spanning tree with no
815 /// more cycles. There are also detailed comments within the implementation
816 /// on techniques which could substantially improve this routine's
818 SmallVector<RefSCC *, 1> removeInternalRefEdge(Node &SourceN,
821 /// A convenience wrapper around the above to handle trivial cases of
822 /// inserting a new call edge.
824 /// This is trivial whenever the target is in the same SCC as the source or
825 /// the edge is an outgoing edge to some descendant SCC. In these cases
826 /// there is no change to the cyclic structure of SCCs or RefSCCs.
828 /// To further make calling this convenient, it also handles inserting
829 /// already existing edges.
830 void insertTrivialCallEdge(Node &SourceN, Node &TargetN);
832 /// A convenience wrapper around the above to handle trivial cases of
833 /// inserting a new ref edge.
835 /// This is trivial whenever the target is in the same RefSCC as the source
836 /// or the edge is an outgoing edge to some descendant RefSCC. In these
837 /// cases there is no change to the cyclic structure of the RefSCCs.
839 /// To further make calling this convenient, it also handles inserting
840 /// already existing edges.
841 void insertTrivialRefEdge(Node &SourceN, Node &TargetN);
843 /// Directly replace a node's function with a new function.
845 /// This should be used when moving the body and users of a function to
846 /// a new formal function object but not otherwise changing the call graph
847 /// structure in any way.
849 /// It requires that the old function in the provided node have zero uses
850 /// and the new function must have calls and references to it establishing
851 /// an equivalent graph.
852 void replaceNodeFunction(Node &N, Function &NewF);
857 /// A post-order depth-first RefSCC iterator over the call graph.
859 /// This iterator walks the cached post-order sequence of RefSCCs. However,
860 /// it trades stability for flexibility. It is restricted to a forward
861 /// iterator but will survive mutations which insert new RefSCCs and continue
862 /// to point to the same RefSCC even if it moves in the post-order sequence.
863 class postorder_ref_scc_iterator
864 : public iterator_facade_base<postorder_ref_scc_iterator,
865 std::forward_iterator_tag, RefSCC> {
866 friend class LazyCallGraph;
867 friend class LazyCallGraph::Node;
869 /// Nonce type to select the constructor for the end iterator.
875 /// Build the begin iterator for a node.
876 postorder_ref_scc_iterator(LazyCallGraph &G) : G(&G), RC(getRC(G, 0)) {}
878 /// Build the end iterator for a node. This is selected purely by overload.
879 postorder_ref_scc_iterator(LazyCallGraph &G, IsAtEndT /*Nonce*/)
880 : G(&G), RC(nullptr) {}
882 /// Get the post-order RefSCC at the given index of the postorder walk,
883 /// populating it if necessary.
884 static RefSCC *getRC(LazyCallGraph &G, int Index) {
885 if (Index == (int)G.PostOrderRefSCCs.size())
889 return G.PostOrderRefSCCs[Index];
893 bool operator==(const postorder_ref_scc_iterator &Arg) const {
894 return G == Arg.G && RC == Arg.RC;
897 reference operator*() const { return *RC; }
899 using iterator_facade_base::operator++;
900 postorder_ref_scc_iterator &operator++() {
901 assert(RC && "Cannot increment the end iterator!");
902 RC = getRC(*G, G->RefSCCIndices.find(RC)->second + 1);
907 /// Construct a graph for the given module.
909 /// This sets up the graph and computes all of the entry points of the graph.
910 /// No function definitions are scanned until their nodes in the graph are
911 /// requested during traversal.
912 LazyCallGraph(Module &M, TargetLibraryInfo &TLI);
914 LazyCallGraph(LazyCallGraph &&G);
915 LazyCallGraph &operator=(LazyCallGraph &&RHS);
917 EdgeSequence::iterator begin() { return EntryEdges.begin(); }
918 EdgeSequence::iterator end() { return EntryEdges.end(); }
922 postorder_ref_scc_iterator postorder_ref_scc_begin() {
923 if (!EntryEdges.empty())
924 assert(!PostOrderRefSCCs.empty() &&
925 "Must form RefSCCs before iterating them!");
926 return postorder_ref_scc_iterator(*this);
928 postorder_ref_scc_iterator postorder_ref_scc_end() {
929 if (!EntryEdges.empty())
930 assert(!PostOrderRefSCCs.empty() &&
931 "Must form RefSCCs before iterating them!");
932 return postorder_ref_scc_iterator(*this,
933 postorder_ref_scc_iterator::IsAtEndT());
936 iterator_range<postorder_ref_scc_iterator> postorder_ref_sccs() {
937 return make_range(postorder_ref_scc_begin(), postorder_ref_scc_end());
940 /// Lookup a function in the graph which has already been scanned and added.
941 Node *lookup(const Function &F) const { return NodeMap.lookup(&F); }
943 /// Lookup a function's SCC in the graph.
945 /// \returns null if the function hasn't been assigned an SCC via the RefSCC
947 SCC *lookupSCC(Node &N) const { return SCCMap.lookup(&N); }
949 /// Lookup a function's RefSCC in the graph.
951 /// \returns null if the function hasn't been assigned a RefSCC via the
952 /// RefSCC iterator walk.
953 RefSCC *lookupRefSCC(Node &N) const {
954 if (SCC *C = lookupSCC(N))
955 return &C->getOuterRefSCC();
960 /// Get a graph node for a given function, scanning it to populate the graph
961 /// data as necessary.
962 Node &get(Function &F) {
963 Node *&N = NodeMap[&F];
967 return insertInto(F, N);
970 /// Get the sequence of known and defined library functions.
972 /// These functions, because they are known to LLVM, can have calls
973 /// introduced out of thin air from arbitrary IR.
974 ArrayRef<Function *> getLibFunctions() const {
975 return LibFunctions.getArrayRef();
978 /// Test whether a function is a known and defined library function tracked by
981 /// Because these functions are known to LLVM they are specially modeled in
982 /// the call graph and even when all IR-level references have been removed
983 /// remain active and reachable.
984 bool isLibFunction(Function &F) const { return LibFunctions.count(&F); }
987 /// \name Pre-SCC Mutation API
989 /// These methods are only valid to call prior to forming any SCCs for this
990 /// call graph. They can be used to update the core node-graph during
991 /// a node-based inorder traversal that precedes any SCC-based traversal.
993 /// Once you begin manipulating a call graph's SCCs, most mutation of the
994 /// graph must be performed via a RefSCC method. There are some exceptions
997 /// Update the call graph after inserting a new edge.
998 void insertEdge(Node &SourceN, Node &TargetN, Edge::Kind EK);
1000 /// Update the call graph after inserting a new edge.
1001 void insertEdge(Function &Source, Function &Target, Edge::Kind EK) {
1002 return insertEdge(get(Source), get(Target), EK);
1005 /// Update the call graph after deleting an edge.
1006 void removeEdge(Node &SourceN, Node &TargetN);
1008 /// Update the call graph after deleting an edge.
1009 void removeEdge(Function &Source, Function &Target) {
1010 return removeEdge(get(Source), get(Target));
1016 /// \name General Mutation API
1018 /// There are a very limited set of mutations allowed on the graph as a whole
1019 /// once SCCs have started to be formed. These routines have strict contracts
1020 /// but may be called at any point.
1022 /// Remove a dead function from the call graph (typically to delete it).
1024 /// Note that the function must have an empty use list, and the call graph
1025 /// must be up-to-date prior to calling this. That means it is by itself in
1026 /// a maximal SCC which is by itself in a maximal RefSCC, etc. No structural
1027 /// changes result from calling this routine other than potentially removing
1028 /// entry points into the call graph.
1030 /// If SCC formation has begun, this function must not be part of the current
1031 /// DFS in order to call this safely. Typically, the function will have been
1032 /// fully visited by the DFS prior to calling this routine.
1033 void removeDeadFunction(Function &F);
1038 /// \name Static helpers for code doing updates to the call graph.
1040 /// These helpers are used to implement parts of the call graph but are also
1041 /// useful to code doing updates or otherwise wanting to walk the IR in the
1042 /// same patterns as when we build the call graph.
1044 /// Recursively visits the defined functions whose address is reachable from
1045 /// every constant in the \p Worklist.
1047 /// Doesn't recurse through any constants already in the \p Visited set, and
1048 /// updates that set with every constant visited.
1050 /// For each defined function, calls \p Callback with that function.
1051 template <typename CallbackT>
1052 static void visitReferences(SmallVectorImpl<Constant *> &Worklist,
1053 SmallPtrSetImpl<Constant *> &Visited,
1054 CallbackT Callback) {
1055 while (!Worklist.empty()) {
1056 Constant *C = Worklist.pop_back_val();
1058 if (Function *F = dyn_cast<Function>(C)) {
1059 if (!F->isDeclaration())
1064 if (BlockAddress *BA = dyn_cast<BlockAddress>(C)) {
1065 // The blockaddress constant expression is a weird special case, we
1066 // can't generically walk its operands the way we do for all other
1068 if (Visited.insert(BA->getFunction()).second)
1069 Worklist.push_back(BA->getFunction());
1073 for (Value *Op : C->operand_values())
1074 if (Visited.insert(cast<Constant>(Op)).second)
1075 Worklist.push_back(cast<Constant>(Op));
1082 typedef SmallVectorImpl<Node *>::reverse_iterator node_stack_iterator;
1083 typedef iterator_range<node_stack_iterator> node_stack_range;
1085 /// Allocator that holds all the call graph nodes.
1086 SpecificBumpPtrAllocator<Node> BPA;
1088 /// Maps function->node for fast lookup.
1089 DenseMap<const Function *, Node *> NodeMap;
1091 /// The entry edges into the graph.
1093 /// These edges are from "external" sources. Put another way, they
1094 /// escape at the module scope.
1095 EdgeSequence EntryEdges;
1097 /// Allocator that holds all the call graph SCCs.
1098 SpecificBumpPtrAllocator<SCC> SCCBPA;
1100 /// Maps Function -> SCC for fast lookup.
1101 DenseMap<Node *, SCC *> SCCMap;
1103 /// Allocator that holds all the call graph RefSCCs.
1104 SpecificBumpPtrAllocator<RefSCC> RefSCCBPA;
1106 /// The post-order sequence of RefSCCs.
1108 /// This list is lazily formed the first time we walk the graph.
1109 SmallVector<RefSCC *, 16> PostOrderRefSCCs;
1111 /// A map from RefSCC to the index for it in the postorder sequence of
1113 DenseMap<RefSCC *, int> RefSCCIndices;
1115 /// The leaf RefSCCs of the graph.
1117 /// These are all of the RefSCCs which have no children.
1118 SmallVector<RefSCC *, 4> LeafRefSCCs;
1120 /// Defined functions that are also known library functions which the
1121 /// optimizer can reason about and therefore might introduce calls to out of
1123 SmallSetVector<Function *, 4> LibFunctions;
1125 /// Helper to insert a new function, with an already looked-up entry in
1127 Node &insertInto(Function &F, Node *&MappedN);
1129 /// Helper to update pointers back to the graph object during moves.
1130 void updateGraphPtrs();
1132 /// Allocates an SCC and constructs it using the graph allocator.
1134 /// The arguments are forwarded to the constructor.
1135 template <typename... Ts> SCC *createSCC(Ts &&... Args) {
1136 return new (SCCBPA.Allocate()) SCC(std::forward<Ts>(Args)...);
1139 /// Allocates a RefSCC and constructs it using the graph allocator.
1141 /// The arguments are forwarded to the constructor.
1142 template <typename... Ts> RefSCC *createRefSCC(Ts &&... Args) {
1143 return new (RefSCCBPA.Allocate()) RefSCC(std::forward<Ts>(Args)...);
1146 /// Common logic for building SCCs from a sequence of roots.
1148 /// This is a very generic implementation of the depth-first walk and SCC
1149 /// formation algorithm. It uses a generic sequence of roots and generic
1150 /// callbacks for each step. This is designed to be used to implement both
1151 /// the RefSCC formation and SCC formation with shared logic.
1153 /// Currently this is a relatively naive implementation of Tarjan's DFS
1154 /// algorithm to form the SCCs.
1156 /// FIXME: We should consider newer variants such as Nuutila.
1157 template <typename RootsT, typename GetBeginT, typename GetEndT,
1158 typename GetNodeT, typename FormSCCCallbackT>
1159 static void buildGenericSCCs(RootsT &&Roots, GetBeginT &&GetBegin,
1160 GetEndT &&GetEnd, GetNodeT &&GetNode,
1161 FormSCCCallbackT &&FormSCC);
1163 /// Build the SCCs for a RefSCC out of a list of nodes.
1164 void buildSCCs(RefSCC &RC, node_stack_range Nodes);
1166 /// Connect a RefSCC into the larger graph.
1168 /// This walks the edges to connect the RefSCC to its children's parent set,
1169 /// and updates the root leaf list.
1170 void connectRefSCC(RefSCC &RC);
1172 /// Get the index of a RefSCC within the postorder traversal.
1174 /// Requires that this RefSCC is a valid one in the (perhaps partial)
1175 /// postorder traversed part of the graph.
1176 int getRefSCCIndex(RefSCC &RC) {
1177 auto IndexIt = RefSCCIndices.find(&RC);
1178 assert(IndexIt != RefSCCIndices.end() && "RefSCC doesn't have an index!");
1179 assert(PostOrderRefSCCs[IndexIt->second] == &RC &&
1180 "Index does not point back at RC!");
1181 return IndexIt->second;
1185 inline LazyCallGraph::Edge::Edge() : Value() {}
1186 inline LazyCallGraph::Edge::Edge(Node &N, Kind K) : Value(&N, K) {}
1188 inline LazyCallGraph::Edge::operator bool() const { return Value.getPointer(); }
1190 inline LazyCallGraph::Edge::Kind LazyCallGraph::Edge::getKind() const {
1191 assert(*this && "Queried a null edge!");
1192 return Value.getInt();
1195 inline bool LazyCallGraph::Edge::isCall() const {
1196 assert(*this && "Queried a null edge!");
1197 return getKind() == Call;
1200 inline LazyCallGraph::Node &LazyCallGraph::Edge::getNode() const {
1201 assert(*this && "Queried a null edge!");
1202 return *Value.getPointer();
1205 inline Function &LazyCallGraph::Edge::getFunction() const {
1206 assert(*this && "Queried a null edge!");
1207 return getNode().getFunction();
1210 // Provide GraphTraits specializations for call graphs.
1211 template <> struct GraphTraits<LazyCallGraph::Node *> {
1212 typedef LazyCallGraph::Node *NodeRef;
1213 typedef LazyCallGraph::EdgeSequence::iterator ChildIteratorType;
1215 static NodeRef getEntryNode(NodeRef N) { return N; }
1216 static ChildIteratorType child_begin(NodeRef N) { return (*N)->begin(); }
1217 static ChildIteratorType child_end(NodeRef N) { return (*N)->end(); }
1219 template <> struct GraphTraits<LazyCallGraph *> {
1220 typedef LazyCallGraph::Node *NodeRef;
1221 typedef LazyCallGraph::EdgeSequence::iterator ChildIteratorType;
1223 static NodeRef getEntryNode(NodeRef N) { return N; }
1224 static ChildIteratorType child_begin(NodeRef N) { return (*N)->begin(); }
1225 static ChildIteratorType child_end(NodeRef N) { return (*N)->end(); }
1228 /// An analysis pass which computes the call graph for a module.
1229 class LazyCallGraphAnalysis : public AnalysisInfoMixin<LazyCallGraphAnalysis> {
1230 friend AnalysisInfoMixin<LazyCallGraphAnalysis>;
1231 static AnalysisKey Key;
1234 /// Inform generic clients of the result type.
1235 typedef LazyCallGraph Result;
1237 /// Compute the \c LazyCallGraph for the module \c M.
1239 /// This just builds the set of entry points to the call graph. The rest is
1240 /// built lazily as it is walked.
1241 LazyCallGraph run(Module &M, ModuleAnalysisManager &AM) {
1242 return LazyCallGraph(M, AM.getResult<TargetLibraryAnalysis>(M));
1246 /// A pass which prints the call graph to a \c raw_ostream.
1248 /// This is primarily useful for testing the analysis.
1249 class LazyCallGraphPrinterPass
1250 : public PassInfoMixin<LazyCallGraphPrinterPass> {
1254 explicit LazyCallGraphPrinterPass(raw_ostream &OS);
1256 PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);
1259 /// A pass which prints the call graph as a DOT file to a \c raw_ostream.
1261 /// This is primarily useful for visualization purposes.
1262 class LazyCallGraphDOTPrinterPass
1263 : public PassInfoMixin<LazyCallGraphDOTPrinterPass> {
1267 explicit LazyCallGraphDOTPrinterPass(raw_ostream &OS);
1269 PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);