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/IR/BasicBlock.h"
47 #include "llvm/IR/Constants.h"
48 #include "llvm/IR/Function.h"
49 #include "llvm/IR/Module.h"
50 #include "llvm/IR/PassManager.h"
51 #include "llvm/Support/Allocator.h"
52 #include "llvm/Support/raw_ostream.h"
57 class PreservedAnalyses;
60 /// A lazily constructed view of the call graph of a module.
62 /// With the edges of this graph, the motivating constraint that we are
63 /// attempting to maintain is that function-local optimization, CGSCC-local
64 /// optimizations, and optimizations transforming a pair of functions connected
65 /// by an edge in the graph, do not invalidate a bottom-up traversal of the SCC
66 /// DAG. That is, no optimizations will delete, remove, or add an edge such
67 /// that functions already visited in a bottom-up order of the SCC DAG are no
68 /// longer valid to have visited, or such that functions not yet visited in
69 /// a bottom-up order of the SCC DAG are not required to have already been
72 /// Within this constraint, the desire is to minimize the merge points of the
73 /// SCC DAG. The greater the fanout of the SCC DAG and the fewer merge points
74 /// in the SCC DAG, the more independence there is in optimizing within it.
75 /// There is a strong desire to enable parallelization of optimizations over
76 /// the call graph, and both limited fanout and merge points will (artificially
77 /// in some cases) limit the scaling of such an effort.
79 /// To this end, graph represents both direct and any potential resolution to
80 /// an indirect call edge. Another way to think about it is that it represents
81 /// both the direct call edges and any direct call edges that might be formed
82 /// through static optimizations. Specifically, it considers taking the address
83 /// of a function to be an edge in the call graph because this might be
84 /// forwarded to become a direct call by some subsequent function-local
85 /// optimization. The result is that the graph closely follows the use-def
86 /// edges for functions. Walking "up" the graph can be done by looking at all
87 /// of the uses of a function.
89 /// The roots of the call graph are the external functions and functions
90 /// escaped into global variables. Those functions can be called from outside
91 /// of the module or via unknowable means in the IR -- we may not be able to
92 /// form even a potential call edge from a function body which may dynamically
93 /// load the function and call it.
95 /// This analysis still requires updates to remain valid after optimizations
96 /// which could potentially change the set of potential callees. The
97 /// constraints it operates under only make the traversal order remain valid.
99 /// The entire analysis must be re-computed if full interprocedural
100 /// optimizations run at any point. For example, globalopt completely
101 /// invalidates the information in this analysis.
103 /// FIXME: This class is named LazyCallGraph in a lame attempt to distinguish
104 /// it from the existing CallGraph. At some point, it is expected that this
105 /// will be the only call graph and it will be renamed accordingly.
106 class LazyCallGraph {
112 class call_edge_iterator;
114 /// A class used to represent edges in the call graph.
116 /// The lazy call graph models both *call* edges and *reference* edges. Call
117 /// edges are much what you would expect, and exist when there is a 'call' or
118 /// 'invoke' instruction of some function. Reference edges are also tracked
119 /// along side these, and exist whenever any instruction (transitively
120 /// through its operands) references a function. All call edges are
121 /// inherently reference edges, and so the reference graph forms a superset
122 /// of the formal call graph.
124 /// Furthermore, edges also may point to raw \c Function objects when those
125 /// functions have not been scanned and incorporated into the graph (yet).
126 /// This is one of the primary ways in which the graph can be lazy. When
127 /// functions are scanned and fully incorporated into the graph, all of the
128 /// edges referencing them are updated to point to the graph \c Node objects
129 /// instead of to the raw \c Function objects. This class even provides
130 /// methods to trigger this scan on-demand by attempting to get the target
131 /// node of the graph and providing a reference back to the graph in order to
132 /// lazily build it if necessary.
134 /// All of these forms of edges are fundamentally represented as outgoing
135 /// edges. The edges are stored in the source node and point at the target
136 /// node. This allows the edge structure itself to be a very compact data
137 /// structure: essentially a tagged pointer.
140 /// The kind of edge in the graph.
141 enum Kind : bool { Ref = false, Call = true };
144 explicit Edge(Function &F, Kind K);
145 explicit Edge(Node &N, Kind K);
147 /// Test whether the edge is null.
149 /// This happens when an edge has been deleted. We leave the edge objects
150 /// around but clear them.
151 operator bool() const;
153 /// Returnss the \c Kind of the edge.
154 Kind getKind() const;
156 /// Test whether the edge represents a direct call to a function.
158 /// This requires that the edge is not null.
161 /// Get the function referenced by this edge.
163 /// This requires that the edge is not null, but will succeed whether we
164 /// have built a graph node for the function yet or not.
165 Function &getFunction() const;
167 /// Get the call graph node referenced by this edge if one exists.
169 /// This requires that the edge is not null. If we have built a graph node
170 /// for the function this edge points to, this will return that node,
171 /// otherwise it will return null.
172 Node *getNode() const;
174 /// Get the call graph node for this edge, building it if necessary.
176 /// This requires that the edge is not null. If we have not yet built
177 /// a graph node for the function this edge points to, this will first ask
178 /// the graph to build that node, inserting it into all the relevant
180 Node &getNode(LazyCallGraph &G);
183 friend class LazyCallGraph::Node;
184 friend class LazyCallGraph::RefSCC;
186 PointerIntPair<PointerUnion<Function *, Node *>, 1, Kind> Value;
188 void setKind(Kind K) { Value.setInt(K); }
191 typedef SmallVector<Edge, 4> EdgeVectorT;
192 typedef SmallVectorImpl<Edge> EdgeVectorImplT;
194 /// A node in the call graph.
196 /// This represents a single node. It's primary roles are to cache the list of
197 /// callees, de-duplicate and provide fast testing of whether a function is
198 /// a callee, and facilitate iteration of child nodes in the graph.
200 friend class LazyCallGraph;
201 friend class LazyCallGraph::SCC;
202 friend class LazyCallGraph::RefSCC;
207 // We provide for the DFS numbering and Tarjan walk lowlink numbers to be
208 // stored directly within the node. These are both '-1' when nodes are part
209 // of an SCC (or RefSCC), or '0' when not yet reached in a DFS walk.
213 mutable EdgeVectorT Edges;
214 DenseMap<Function *, int> EdgeIndexMap;
216 /// Basic constructor implements the scanning of F into Edges and
218 Node(LazyCallGraph &G, Function &F);
220 /// Internal helper to insert an edge to a function.
221 void insertEdgeInternal(Function &ChildF, Edge::Kind EK);
223 /// Internal helper to insert an edge to a node.
224 void insertEdgeInternal(Node &ChildN, Edge::Kind EK);
226 /// Internal helper to change an edge kind.
227 void setEdgeKind(Function &ChildF, Edge::Kind EK);
229 /// Internal helper to remove the edge to the given function.
230 void removeEdgeInternal(Function &ChildF);
234 EdgeIndexMap.clear();
237 /// Print the name of this node's function.
238 friend raw_ostream &operator<<(raw_ostream &OS, const Node &N) {
239 return OS << N.F.getName();
242 /// Dump the name of this node's function to stderr.
246 LazyCallGraph &getGraph() const { return *G; }
248 Function &getFunction() const { return F; }
250 edge_iterator begin() const {
251 return edge_iterator(Edges.begin(), Edges.end());
253 edge_iterator end() const { return edge_iterator(Edges.end(), Edges.end()); }
255 const Edge &operator[](int i) const { return Edges[i]; }
256 const Edge &operator[](Function &F) const {
257 assert(EdgeIndexMap.find(&F) != EdgeIndexMap.end() && "No such edge!");
258 return Edges[EdgeIndexMap.find(&F)->second];
260 const Edge &operator[](Node &N) const { return (*this)[N.getFunction()]; }
262 const Edge *lookup(Function &F) const {
263 auto EI = EdgeIndexMap.find(&F);
264 return EI != EdgeIndexMap.end() ? &Edges[EI->second] : nullptr;
267 call_edge_iterator call_begin() const {
268 return call_edge_iterator(Edges.begin(), Edges.end());
270 call_edge_iterator call_end() const {
271 return call_edge_iterator(Edges.end(), Edges.end());
274 iterator_range<call_edge_iterator> calls() const {
275 return make_range(call_begin(), call_end());
278 /// Equality is defined as address equality.
279 bool operator==(const Node &N) const { return this == &N; }
280 bool operator!=(const Node &N) const { return !operator==(N); }
283 /// A lazy iterator used for both the entry nodes and child nodes.
285 /// When this iterator is dereferenced, if not yet available, a function will
286 /// be scanned for "calls" or uses of functions and its child information
287 /// will be constructed. All of these results are accumulated and cached in
290 : public iterator_adaptor_base<edge_iterator, EdgeVectorImplT::iterator,
291 std::forward_iterator_tag> {
292 friend class LazyCallGraph;
293 friend class LazyCallGraph::Node;
295 EdgeVectorImplT::iterator E;
297 // Build the iterator for a specific position in the edge list.
298 edge_iterator(EdgeVectorImplT::iterator BaseI,
299 EdgeVectorImplT::iterator E)
300 : iterator_adaptor_base(BaseI), E(E) {
301 while (I != E && !*I)
308 using iterator_adaptor_base::operator++;
309 edge_iterator &operator++() {
312 } while (I != E && !*I);
317 /// A lazy iterator over specifically call edges.
319 /// This has the same iteration properties as the \c edge_iterator, but
320 /// restricts itself to edges which represent actual calls.
321 class call_edge_iterator
322 : public iterator_adaptor_base<call_edge_iterator,
323 EdgeVectorImplT::iterator,
324 std::forward_iterator_tag> {
325 friend class LazyCallGraph;
326 friend class LazyCallGraph::Node;
328 EdgeVectorImplT::iterator E;
330 /// Advance the iterator to the next valid, call edge.
331 void advanceToNextEdge() {
332 while (I != E && (!*I || !I->isCall()))
336 // Build the iterator for a specific position in the edge list.
337 call_edge_iterator(EdgeVectorImplT::iterator BaseI,
338 EdgeVectorImplT::iterator E)
339 : iterator_adaptor_base(BaseI), E(E) {
344 call_edge_iterator() {}
346 using iterator_adaptor_base::operator++;
347 call_edge_iterator &operator++() {
354 /// An SCC of the call graph.
356 /// This represents a Strongly Connected Component of the direct call graph
357 /// -- ignoring indirect calls and function references. It stores this as
358 /// a collection of call graph nodes. While the order of nodes in the SCC is
359 /// stable, it is not any particular order.
361 /// The SCCs are nested within a \c RefSCC, see below for details about that
362 /// outer structure. SCCs do not support mutation of the call graph, that
363 /// must be done through the containing \c RefSCC in order to fully reason
364 /// about the ordering and connections of the graph.
366 friend class LazyCallGraph;
367 friend class LazyCallGraph::Node;
370 SmallVector<Node *, 1> Nodes;
372 template <typename NodeRangeT>
373 SCC(RefSCC &OuterRefSCC, NodeRangeT &&Nodes)
374 : OuterRefSCC(&OuterRefSCC), Nodes(std::forward<NodeRangeT>(Nodes)) {}
377 OuterRefSCC = nullptr;
381 /// Print a short descrtiption useful for debugging or logging.
383 /// We print the function names in the SCC wrapped in '()'s and skipping
384 /// the middle functions if there are a large number.
386 // Note: this is defined inline to dodge issues with GCC's interpretation
387 // of enclosing namespaces for friend function declarations.
388 friend raw_ostream &operator<<(raw_ostream &OS, const SCC &C) {
391 for (LazyCallGraph::Node &N : C) {
394 // Elide the inner elements if there are too many.
396 OS << "..., " << *C.Nodes.back();
406 /// Dump a short description of this SCC to stderr.
410 /// Verify invariants about the SCC.
412 /// This will attempt to validate all of the basic invariants within an
413 /// SCC, but not that it is a strongly connected componet per-se. Primarily
414 /// useful while building and updating the graph to check that basic
415 /// properties are in place rather than having inexplicable crashes later.
420 typedef pointee_iterator<SmallVectorImpl<Node *>::const_iterator> iterator;
422 iterator begin() const { return Nodes.begin(); }
423 iterator end() const { return Nodes.end(); }
425 int size() const { return Nodes.size(); }
427 RefSCC &getOuterRefSCC() const { return *OuterRefSCC; }
429 /// Test if this SCC is a parent of \a C.
431 /// Note that this is linear in the number of edges departing the current
433 bool isParentOf(const SCC &C) const;
435 /// Test if this SCC is an ancestor of \a C.
437 /// Note that in the worst case this is linear in the number of edges
438 /// departing the current SCC and every SCC in the entire graph reachable
439 /// from this SCC. Thus this very well may walk every edge in the entire
440 /// call graph! Do not call this in a tight loop!
441 bool isAncestorOf(const SCC &C) const;
443 /// Test if this SCC is a child of \a C.
445 /// See the comments for \c isParentOf for detailed notes about the
446 /// complexity of this routine.
447 bool isChildOf(const SCC &C) const { return C.isParentOf(*this); }
449 /// Test if this SCC is a descendant of \a C.
451 /// See the comments for \c isParentOf for detailed notes about the
452 /// complexity of this routine.
453 bool isDescendantOf(const SCC &C) const { return C.isAncestorOf(*this); }
455 /// Provide a short name by printing this SCC to a std::string.
457 /// This copes with the fact that we don't have a name per-se for an SCC
458 /// while still making the use of this in debugging and logging useful.
459 std::string getName() const {
461 raw_string_ostream OS(Name);
468 /// A RefSCC of the call graph.
470 /// This models a Strongly Connected Component of function reference edges in
471 /// the call graph. As opposed to actual SCCs, these can be used to scope
472 /// subgraphs of the module which are independent from other subgraphs of the
473 /// module because they do not reference it in any way. This is also the unit
474 /// where we do mutation of the graph in order to restrict mutations to those
475 /// which don't violate this independence.
477 /// A RefSCC contains a DAG of actual SCCs. All the nodes within the RefSCC
478 /// are necessarily within some actual SCC that nests within it. Since
479 /// a direct call *is* a reference, there will always be at least one RefSCC
482 friend class LazyCallGraph;
483 friend class LazyCallGraph::Node;
486 SmallPtrSet<RefSCC *, 1> Parents;
488 /// A postorder list of the inner SCCs.
489 SmallVector<SCC *, 4> SCCs;
491 /// A map from SCC to index in the postorder list.
492 SmallDenseMap<SCC *, int, 4> SCCIndices;
494 /// Fast-path constructor. RefSCCs should instead be constructed by calling
495 /// formRefSCCFast on the graph itself.
496 RefSCC(LazyCallGraph &G);
504 /// Print a short description useful for debugging or logging.
506 /// We print the SCCs wrapped in '[]'s and skipping the middle SCCs if
507 /// there are a large number.
509 // Note: this is defined inline to dodge issues with GCC's interpretation
510 // of enclosing namespaces for friend function declarations.
511 friend raw_ostream &operator<<(raw_ostream &OS, const RefSCC &RC) {
514 for (LazyCallGraph::SCC &C : RC) {
517 // Elide the inner elements if there are too many.
519 OS << "..., " << *RC.SCCs.back();
529 /// Dump a short description of this RefSCC to stderr.
533 /// Verify invariants about the RefSCC and all its SCCs.
535 /// This will attempt to validate all of the invariants *within* the
536 /// RefSCC, but not that it is a strongly connected component of the larger
537 /// graph. This makes it useful even when partially through an update.
539 /// Invariants checked:
540 /// - SCCs and their indices match.
541 /// - The SCCs list is in fact in post-order.
545 /// Handle any necessary parent set updates after inserting a trivial ref
547 void handleTrivialEdgeInsertion(Node &SourceN, Node &TargetN);
550 typedef pointee_iterator<SmallVectorImpl<SCC *>::const_iterator> iterator;
551 typedef iterator_range<iterator> range;
552 typedef pointee_iterator<SmallPtrSetImpl<RefSCC *>::const_iterator>
555 iterator begin() const { return SCCs.begin(); }
556 iterator end() const { return SCCs.end(); }
558 ssize_t size() const { return SCCs.size(); }
560 SCC &operator[](int Idx) { return *SCCs[Idx]; }
562 iterator find(SCC &C) const {
563 return SCCs.begin() + SCCIndices.find(&C)->second;
566 parent_iterator parent_begin() const { return Parents.begin(); }
567 parent_iterator parent_end() const { return Parents.end(); }
569 iterator_range<parent_iterator> parents() const {
570 return make_range(parent_begin(), parent_end());
573 /// Test if this RefSCC is a parent of \a C.
574 bool isParentOf(const RefSCC &C) const { return C.isChildOf(*this); }
576 /// Test if this RefSCC is an ancestor of \a C.
577 bool isAncestorOf(const RefSCC &C) const { return C.isDescendantOf(*this); }
579 /// Test if this RefSCC is a child of \a C.
580 bool isChildOf(const RefSCC &C) const {
581 return Parents.count(const_cast<RefSCC *>(&C));
584 /// Test if this RefSCC is a descendant of \a C.
585 bool isDescendantOf(const RefSCC &C) const;
587 /// Provide a short name by printing this RefSCC to a std::string.
589 /// This copes with the fact that we don't have a name per-se for an RefSCC
590 /// while still making the use of this in debugging and logging useful.
591 std::string getName() const {
593 raw_string_ostream OS(Name);
600 /// \name Mutation API
602 /// These methods provide the core API for updating the call graph in the
603 /// presence of (potentially still in-flight) DFS-found RefSCCs and SCCs.
605 /// Note that these methods sometimes have complex runtimes, so be careful
606 /// how you call them.
608 /// Make an existing internal ref edge into a call edge.
610 /// This may form a larger cycle and thus collapse SCCs into TargetN's SCC.
611 /// If that happens, the deleted SCC pointers are returned. These SCCs are
612 /// not in a valid state any longer but the pointers will remain valid
613 /// until destruction of the parent graph instance for the purpose of
614 /// clearing cached information.
616 /// After this operation, both SourceN's SCC and TargetN's SCC may move
617 /// position within this RefSCC's postorder list. Any SCCs merged are
618 /// merged into the TargetN's SCC in order to preserve reachability analyses
619 /// which took place on that SCC.
620 SmallVector<SCC *, 1> switchInternalEdgeToCall(Node &SourceN,
623 /// Make an existing internal call edge between separate SCCs into a ref
626 /// If SourceN and TargetN in separate SCCs within this RefSCC, changing
627 /// the call edge between them to a ref edge is a trivial operation that
628 /// does not require any structural changes to the call graph.
629 void switchTrivialInternalEdgeToRef(Node &SourceN, Node &TargetN);
631 /// Make an existing internal call edge within a single SCC into a ref
634 /// Since SourceN and TargetN are part of a single SCC, this SCC may be
635 /// split up due to breaking a cycle in the call edges that formed it. If
636 /// that happens, then this routine will insert new SCCs into the postorder
637 /// list *before* the SCC of TargetN (previously the SCC of both). This
638 /// preserves postorder as the TargetN can reach all of the other nodes by
639 /// definition of previously being in a single SCC formed by the cycle from
640 /// SourceN to TargetN.
642 /// The newly added SCCs are added *immediately* and contiguously
643 /// prior to the TargetN SCC and return the range covering the new SCCs in
644 /// the RefSCC's postorder sequence. You can directly iterate the returned
645 /// range to observe all of the new SCCs in postorder.
647 /// Note that if SourceN and TargetN are in separate SCCs, the simpler
648 /// routine `switchTrivialInternalEdgeToRef` should be used instead.
649 iterator_range<iterator> switchInternalEdgeToRef(Node &SourceN,
652 /// Make an existing outgoing ref edge into a call edge.
654 /// Note that this is trivial as there are no cyclic impacts and there
655 /// remains a reference edge.
656 void switchOutgoingEdgeToCall(Node &SourceN, Node &TargetN);
658 /// Make an existing outgoing call edge into a ref edge.
660 /// This is trivial as there are no cyclic impacts and there remains
661 /// a reference edge.
662 void switchOutgoingEdgeToRef(Node &SourceN, Node &TargetN);
664 /// Insert a ref edge from one node in this RefSCC to another in this
667 /// This is always a trivial operation as it doesn't change any part of the
668 /// graph structure besides connecting the two nodes.
670 /// Note that we don't support directly inserting internal *call* edges
671 /// because that could change the graph structure and requires returning
672 /// information about what became invalid. As a consequence, the pattern
673 /// should be to first insert the necessary ref edge, and then to switch it
674 /// to a call edge if needed and handle any invalidation that results. See
675 /// the \c switchInternalEdgeToCall routine for details.
676 void insertInternalRefEdge(Node &SourceN, Node &TargetN);
678 /// Insert an edge whose parent is in this RefSCC and child is in some
681 /// There must be an existing path from the \p SourceN to the \p TargetN.
682 /// This operation is inexpensive and does not change the set of SCCs and
683 /// RefSCCs in the graph.
684 void insertOutgoingEdge(Node &SourceN, Node &TargetN, Edge::Kind EK);
686 /// Insert an edge whose source is in a descendant RefSCC and target is in
689 /// There must be an existing path from the target to the source in this
692 /// NB! This is has the potential to be a very expensive function. It
693 /// inherently forms a cycle in the prior RefSCC DAG and we have to merge
694 /// RefSCCs to resolve that cycle. But finding all of the RefSCCs which
695 /// participate in the cycle can in the worst case require traversing every
696 /// RefSCC in the graph. Every attempt is made to avoid that, but passes
697 /// must still exercise caution calling this routine repeatedly.
699 /// Also note that this can only insert ref edges. In order to insert
700 /// a call edge, first insert a ref edge and then switch it to a call edge.
701 /// These are intentionally kept as separate interfaces because each step
702 /// of the operation invalidates a different set of data structures.
704 /// This returns all the RefSCCs which were merged into the this RefSCC
705 /// (the target's). This allows callers to invalidate any cached
708 /// FIXME: We could possibly optimize this quite a bit for cases where the
709 /// caller and callee are very nearby in the graph. See comments in the
710 /// implementation for details, but that use case might impact users.
711 SmallVector<RefSCC *, 1> insertIncomingRefEdge(Node &SourceN,
714 /// Remove an edge whose source is in this RefSCC and target is *not*.
716 /// This removes an inter-RefSCC edge. All inter-RefSCC edges originating
717 /// from this SCC have been fully explored by any in-flight DFS graph
718 /// formation, so this is always safe to call once you have the source
721 /// This operation does not change the cyclic structure of the graph and so
722 /// is very inexpensive. It may change the connectivity graph of the SCCs
723 /// though, so be careful calling this while iterating over them.
724 void removeOutgoingEdge(Node &SourceN, Node &TargetN);
726 /// Remove a ref edge which is entirely within this RefSCC.
728 /// Both the \a SourceN and the \a TargetN must be within this RefSCC.
729 /// Removing such an edge may break cycles that form this RefSCC and thus
730 /// this operation may change the RefSCC graph significantly. In
731 /// particular, this operation will re-form new RefSCCs based on the
732 /// remaining connectivity of the graph. The following invariants are
733 /// guaranteed to hold after calling this method:
735 /// 1) This RefSCC is still a RefSCC in the graph.
736 /// 2) This RefSCC will be the parent of any new RefSCCs. Thus, this RefSCC
737 /// is preserved as the root of any new RefSCC DAG formed.
738 /// 3) No RefSCC other than this RefSCC has its member set changed (this is
739 /// inherent in the definition of removing such an edge).
740 /// 4) All of the parent links of the RefSCC graph will be updated to
741 /// reflect the new RefSCC structure.
742 /// 5) All RefSCCs formed out of this RefSCC, excluding this RefSCC, will
743 /// be returned in post-order.
744 /// 6) The order of the RefSCCs in the vector will be a valid postorder
745 /// traversal of the new RefSCCs.
747 /// These invariants are very important to ensure that we can build
748 /// optimization pipelines on top of the CGSCC pass manager which
749 /// intelligently update the RefSCC graph without invalidating other parts
750 /// of the RefSCC graph.
752 /// Note that we provide no routine to remove a *call* edge. Instead, you
753 /// must first switch it to a ref edge using \c switchInternalEdgeToRef.
754 /// This split API is intentional as each of these two steps can invalidate
755 /// a different aspect of the graph structure and needs to have the
756 /// invalidation handled independently.
758 /// The runtime complexity of this method is, in the worst case, O(V+E)
759 /// where V is the number of nodes in this RefSCC and E is the number of
760 /// edges leaving the nodes in this RefSCC. Note that E includes both edges
761 /// within this RefSCC and edges from this RefSCC to child RefSCCs. Some
762 /// effort has been made to minimize the overhead of common cases such as
763 /// self-edges and edge removals which result in a spanning tree with no
764 /// more cycles. There are also detailed comments within the implementation
765 /// on techniques which could substantially improve this routine's
767 SmallVector<RefSCC *, 1> removeInternalRefEdge(Node &SourceN,
770 /// A convenience wrapper around the above to handle trivial cases of
771 /// inserting a new call edge.
773 /// This is trivial whenever the target is in the same SCC as the source or
774 /// the edge is an outgoing edge to some descendant SCC. In these cases
775 /// there is no change to the cyclic structure of SCCs or RefSCCs.
777 /// To further make calling this convenient, it also handles inserting
778 /// already existing edges.
779 void insertTrivialCallEdge(Node &SourceN, Node &TargetN);
781 /// A convenience wrapper around the above to handle trivial cases of
782 /// inserting a new ref edge.
784 /// This is trivial whenever the target is in the same RefSCC as the source
785 /// or the edge is an outgoing edge to some descendant RefSCC. In these
786 /// cases there is no change to the cyclic structure of the RefSCCs.
788 /// To further make calling this convenient, it also handles inserting
789 /// already existing edges.
790 void insertTrivialRefEdge(Node &SourceN, Node &TargetN);
795 /// A post-order depth-first RefSCC iterator over the call graph.
797 /// This iterator triggers the Tarjan DFS-based formation of the RefSCC (and
798 /// SCC) DAG for the call graph, walking it lazily in depth-first post-order.
799 /// That is, it always visits RefSCCs for the target of a reference edge
800 /// prior to visiting the RefSCC for a source of the edge (when they are in
801 /// different RefSCCs).
803 /// When forming each RefSCC, the call edges within it are used to form SCCs
804 /// within it, so iterating this also controls the lazy formation of SCCs.
805 class postorder_ref_scc_iterator
806 : public iterator_facade_base<postorder_ref_scc_iterator,
807 std::forward_iterator_tag, RefSCC> {
808 friend class LazyCallGraph;
809 friend class LazyCallGraph::Node;
811 /// Nonce type to select the constructor for the end iterator.
817 /// Build the begin iterator for a node.
818 postorder_ref_scc_iterator(LazyCallGraph &G) : G(&G), RC(getRC(G, 0)) {}
820 /// Build the end iterator for a node. This is selected purely by overload.
821 postorder_ref_scc_iterator(LazyCallGraph &G, IsAtEndT /*Nonce*/)
822 : G(&G), RC(nullptr) {}
824 /// Get the post-order RefSCC at the given index of the postorder walk,
825 /// populating it if necessary.
826 static RefSCC *getRC(LazyCallGraph &G, int Index) {
827 if (Index == (int)G.PostOrderRefSCCs.size())
828 if (!G.buildNextRefSCCInPostOrder())
832 assert(Index < (int)G.PostOrderRefSCCs.size() &&
833 "Built the next post-order RefSCC without growing list!");
834 return G.PostOrderRefSCCs[Index];
838 bool operator==(const postorder_ref_scc_iterator &Arg) const {
839 return G == Arg.G && RC == Arg.RC;
842 reference operator*() const { return *RC; }
844 using iterator_facade_base::operator++;
845 postorder_ref_scc_iterator &operator++() {
846 assert(RC && "Cannot increment the end iterator!");
847 RC = getRC(*G, G->RefSCCIndices.find(RC)->second + 1);
852 /// Construct a graph for the given module.
854 /// This sets up the graph and computes all of the entry points of the graph.
855 /// No function definitions are scanned until their nodes in the graph are
856 /// requested during traversal.
857 LazyCallGraph(Module &M);
859 LazyCallGraph(LazyCallGraph &&G);
860 LazyCallGraph &operator=(LazyCallGraph &&RHS);
862 edge_iterator begin() {
863 return edge_iterator(EntryEdges.begin(), EntryEdges.end());
865 edge_iterator end() {
866 return edge_iterator(EntryEdges.end(), EntryEdges.end());
869 postorder_ref_scc_iterator postorder_ref_scc_begin() {
870 return postorder_ref_scc_iterator(*this);
872 postorder_ref_scc_iterator postorder_ref_scc_end() {
873 return postorder_ref_scc_iterator(*this,
874 postorder_ref_scc_iterator::IsAtEndT());
877 iterator_range<postorder_ref_scc_iterator> postorder_ref_sccs() {
878 return make_range(postorder_ref_scc_begin(), postorder_ref_scc_end());
881 /// Lookup a function in the graph which has already been scanned and added.
882 Node *lookup(const Function &F) const { return NodeMap.lookup(&F); }
884 /// Lookup a function's SCC in the graph.
886 /// \returns null if the function hasn't been assigned an SCC via the RefSCC
888 SCC *lookupSCC(Node &N) const { return SCCMap.lookup(&N); }
890 /// Lookup a function's RefSCC in the graph.
892 /// \returns null if the function hasn't been assigned a RefSCC via the
893 /// RefSCC iterator walk.
894 RefSCC *lookupRefSCC(Node &N) const {
895 if (SCC *C = lookupSCC(N))
896 return &C->getOuterRefSCC();
901 /// Get a graph node for a given function, scanning it to populate the graph
902 /// data as necessary.
903 Node &get(Function &F) {
904 Node *&N = NodeMap[&F];
908 return insertInto(F, N);
912 /// \name Pre-SCC Mutation API
914 /// These methods are only valid to call prior to forming any SCCs for this
915 /// call graph. They can be used to update the core node-graph during
916 /// a node-based inorder traversal that precedes any SCC-based traversal.
918 /// Once you begin manipulating a call graph's SCCs, most mutation of the
919 /// graph must be performed via a RefSCC method. There are some exceptions
922 /// Update the call graph after inserting a new edge.
923 void insertEdge(Node &Caller, Function &Callee, Edge::Kind EK);
925 /// Update the call graph after inserting a new edge.
926 void insertEdge(Function &Caller, Function &Callee, Edge::Kind EK) {
927 return insertEdge(get(Caller), Callee, EK);
930 /// Update the call graph after deleting an edge.
931 void removeEdge(Node &Caller, Function &Callee);
933 /// Update the call graph after deleting an edge.
934 void removeEdge(Function &Caller, Function &Callee) {
935 return removeEdge(get(Caller), Callee);
941 /// \name General Mutation API
943 /// There are a very limited set of mutations allowed on the graph as a whole
944 /// once SCCs have started to be formed. These routines have strict contracts
945 /// but may be called at any point.
947 /// Remove a dead function from the call graph (typically to delete it).
949 /// Note that the function must have an empty use list, and the call graph
950 /// must be up-to-date prior to calling this. That means it is by itself in
951 /// a maximal SCC which is by itself in a maximal RefSCC, etc. No structural
952 /// changes result from calling this routine other than potentially removing
953 /// entry points into the call graph.
955 /// If SCC formation has begun, this function must not be part of the current
956 /// DFS in order to call this safely. Typically, the function will have been
957 /// fully visited by the DFS prior to calling this routine.
958 void removeDeadFunction(Function &F);
963 /// \name Static helpers for code doing updates to the call graph.
965 /// These helpers are used to implement parts of the call graph but are also
966 /// useful to code doing updates or otherwise wanting to walk the IR in the
967 /// same patterns as when we build the call graph.
969 /// Recursively visits the defined functions whose address is reachable from
970 /// every constant in the \p Worklist.
972 /// Doesn't recurse through any constants already in the \p Visited set, and
973 /// updates that set with every constant visited.
975 /// For each defined function, calls \p Callback with that function.
976 template <typename CallbackT>
977 static void visitReferences(SmallVectorImpl<Constant *> &Worklist,
978 SmallPtrSetImpl<Constant *> &Visited,
979 CallbackT Callback) {
980 while (!Worklist.empty()) {
981 Constant *C = Worklist.pop_back_val();
983 if (Function *F = dyn_cast<Function>(C)) {
984 if (!F->isDeclaration())
989 if (BlockAddress *BA = dyn_cast<BlockAddress>(C)) {
990 // The blockaddress constant expression is a weird special case, we
991 // can't generically walk its operands the way we do for all other
993 if (Visited.insert(BA->getFunction()).second)
994 Worklist.push_back(BA->getFunction());
998 for (Value *Op : C->operand_values())
999 if (Visited.insert(cast<Constant>(Op)).second)
1000 Worklist.push_back(cast<Constant>(Op));
1007 typedef SmallVectorImpl<Node *>::reverse_iterator node_stack_iterator;
1008 typedef iterator_range<node_stack_iterator> node_stack_range;
1010 /// Allocator that holds all the call graph nodes.
1011 SpecificBumpPtrAllocator<Node> BPA;
1013 /// Maps function->node for fast lookup.
1014 DenseMap<const Function *, Node *> NodeMap;
1016 /// The entry nodes to the graph.
1018 /// These nodes are reachable through "external" means. Put another way, they
1019 /// escape at the module scope.
1020 EdgeVectorT EntryEdges;
1022 /// Map of the entry nodes in the graph to their indices in \c EntryEdges.
1023 DenseMap<Function *, int> EntryIndexMap;
1025 /// Allocator that holds all the call graph SCCs.
1026 SpecificBumpPtrAllocator<SCC> SCCBPA;
1028 /// Maps Function -> SCC for fast lookup.
1029 DenseMap<Node *, SCC *> SCCMap;
1031 /// Allocator that holds all the call graph RefSCCs.
1032 SpecificBumpPtrAllocator<RefSCC> RefSCCBPA;
1034 /// The post-order sequence of RefSCCs.
1036 /// This list is lazily formed the first time we walk the graph.
1037 SmallVector<RefSCC *, 16> PostOrderRefSCCs;
1039 /// A map from RefSCC to the index for it in the postorder sequence of
1041 DenseMap<RefSCC *, int> RefSCCIndices;
1043 /// The leaf RefSCCs of the graph.
1045 /// These are all of the RefSCCs which have no children.
1046 SmallVector<RefSCC *, 4> LeafRefSCCs;
1048 /// Stack of nodes in the DFS walk.
1049 SmallVector<std::pair<Node *, edge_iterator>, 4> DFSStack;
1051 /// Set of entry nodes not-yet-processed into RefSCCs.
1052 SmallVector<Function *, 4> RefSCCEntryNodes;
1054 /// Stack of nodes the DFS has walked but not yet put into a RefSCC.
1055 SmallVector<Node *, 4> PendingRefSCCStack;
1057 /// Counter for the next DFS number to assign.
1060 /// Helper to insert a new function, with an already looked-up entry in
1062 Node &insertInto(Function &F, Node *&MappedN);
1064 /// Helper to update pointers back to the graph object during moves.
1065 void updateGraphPtrs();
1067 /// Allocates an SCC and constructs it using the graph allocator.
1069 /// The arguments are forwarded to the constructor.
1070 template <typename... Ts> SCC *createSCC(Ts &&... Args) {
1071 return new (SCCBPA.Allocate()) SCC(std::forward<Ts>(Args)...);
1074 /// Allocates a RefSCC and constructs it using the graph allocator.
1076 /// The arguments are forwarded to the constructor.
1077 template <typename... Ts> RefSCC *createRefSCC(Ts &&... Args) {
1078 return new (RefSCCBPA.Allocate()) RefSCC(std::forward<Ts>(Args)...);
1081 /// Build the SCCs for a RefSCC out of a list of nodes.
1082 void buildSCCs(RefSCC &RC, node_stack_range Nodes);
1084 /// Connect a RefSCC into the larger graph.
1086 /// This walks the edges to connect the RefSCC to its children's parent set,
1087 /// and updates the root leaf list.
1088 void connectRefSCC(RefSCC &RC);
1090 /// Get the index of a RefSCC within the postorder traversal.
1092 /// Requires that this RefSCC is a valid one in the (perhaps partial)
1093 /// postorder traversed part of the graph.
1094 int getRefSCCIndex(RefSCC &RC) {
1095 auto IndexIt = RefSCCIndices.find(&RC);
1096 assert(IndexIt != RefSCCIndices.end() && "RefSCC doesn't have an index!");
1097 assert(PostOrderRefSCCs[IndexIt->second] == &RC &&
1098 "Index does not point back at RC!");
1099 return IndexIt->second;
1102 /// Builds the next node in the post-order RefSCC walk of the call graph and
1103 /// appends it to the \c PostOrderRefSCCs vector.
1105 /// Returns true if a new RefSCC was successfully constructed, and false if
1106 /// there are no more RefSCCs to build in the graph.
1107 bool buildNextRefSCCInPostOrder();
1110 inline LazyCallGraph::Edge::Edge() : Value() {}
1111 inline LazyCallGraph::Edge::Edge(Function &F, Kind K) : Value(&F, K) {}
1112 inline LazyCallGraph::Edge::Edge(Node &N, Kind K) : Value(&N, K) {}
1114 inline LazyCallGraph::Edge::operator bool() const {
1115 return !Value.getPointer().isNull();
1118 inline LazyCallGraph::Edge::Kind LazyCallGraph::Edge::getKind() const {
1119 assert(*this && "Queried a null edge!");
1120 return Value.getInt();
1123 inline bool LazyCallGraph::Edge::isCall() const {
1124 assert(*this && "Queried a null edge!");
1125 return getKind() == Call;
1128 inline Function &LazyCallGraph::Edge::getFunction() const {
1129 assert(*this && "Queried a null edge!");
1130 auto P = Value.getPointer();
1131 if (auto *F = P.dyn_cast<Function *>())
1134 return P.get<Node *>()->getFunction();
1137 inline LazyCallGraph::Node *LazyCallGraph::Edge::getNode() const {
1138 assert(*this && "Queried a null edge!");
1139 auto P = Value.getPointer();
1140 if (auto *N = P.dyn_cast<Node *>())
1146 inline LazyCallGraph::Node &LazyCallGraph::Edge::getNode(LazyCallGraph &G) {
1147 assert(*this && "Queried a null edge!");
1148 auto P = Value.getPointer();
1149 if (auto *N = P.dyn_cast<Node *>())
1152 Node &N = G.get(*P.get<Function *>());
1153 Value.setPointer(&N);
1157 // Provide GraphTraits specializations for call graphs.
1158 template <> struct GraphTraits<LazyCallGraph::Node *> {
1159 typedef LazyCallGraph::Node *NodeRef;
1160 typedef LazyCallGraph::edge_iterator ChildIteratorType;
1162 static NodeRef getEntryNode(NodeRef N) { return N; }
1163 static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
1164 static ChildIteratorType child_end(NodeRef N) { return N->end(); }
1166 template <> struct GraphTraits<LazyCallGraph *> {
1167 typedef LazyCallGraph::Node *NodeRef;
1168 typedef LazyCallGraph::edge_iterator ChildIteratorType;
1170 static NodeRef getEntryNode(NodeRef N) { return N; }
1171 static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
1172 static ChildIteratorType child_end(NodeRef N) { return N->end(); }
1175 /// An analysis pass which computes the call graph for a module.
1176 class LazyCallGraphAnalysis : public AnalysisInfoMixin<LazyCallGraphAnalysis> {
1177 friend AnalysisInfoMixin<LazyCallGraphAnalysis>;
1178 static AnalysisKey Key;
1181 /// Inform generic clients of the result type.
1182 typedef LazyCallGraph Result;
1184 /// Compute the \c LazyCallGraph for the module \c M.
1186 /// This just builds the set of entry points to the call graph. The rest is
1187 /// built lazily as it is walked.
1188 LazyCallGraph run(Module &M, ModuleAnalysisManager &) {
1189 return LazyCallGraph(M);
1193 /// A pass which prints the call graph to a \c raw_ostream.
1195 /// This is primarily useful for testing the analysis.
1196 class LazyCallGraphPrinterPass
1197 : public PassInfoMixin<LazyCallGraphPrinterPass> {
1201 explicit LazyCallGraphPrinterPass(raw_ostream &OS);
1203 PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);
1206 /// A pass which prints the call graph as a DOT file to a \c raw_ostream.
1208 /// This is primarily useful for visualization purposes.
1209 class LazyCallGraphDOTPrinterPass
1210 : public PassInfoMixin<LazyCallGraphDOTPrinterPass> {
1214 explicit LazyCallGraphDOTPrinterPass(raw_ostream &OS);
1216 PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);