EIC code displayed by LXR master/​include/​llvm/​Analysis/​LazyCallGraph.h	Source navigation Diff markup Identifier search General search
	Version: master test Revert   Change

File indexing completed on 2026-05-10 08:43:14

 //===- LazyCallGraph.h - Analysis of a Module's call graph ------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 /// \file
 ///
 /// Implements a lazy call graph analysis and related passes for the new pass
 /// manager.
 ///
 /// NB: This is *not* a traditional call graph! It is a graph which models both
 /// the current calls and potential calls. As a consequence there are many
 /// edges in this call graph that do not correspond to a 'call' or 'invoke'
 /// instruction.
 ///
 /// The primary use cases of this graph analysis is to facilitate iterating
 /// across the functions of a module in ways that ensure all callees are
 /// visited prior to a caller (given any SCC constraints), or vice versa. As
 /// such is it particularly well suited to organizing CGSCC optimizations such
 /// as inlining, outlining, argument promotion, etc. That is its primary use
 /// case and motivates the design. It may not be appropriate for other
 /// purposes. The use graph of functions or some other conservative analysis of
 /// call instructions may be interesting for optimizations and subsequent
 /// analyses which don't work in the context of an overly specified
 /// potential-call-edge graph.
 ///
 /// To understand the specific rules and nature of this call graph analysis,
 /// see the documentation of the \c LazyCallGraph below.
 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ANALYSIS_LAZYCALLGRAPH_H
 #define LLVM_ANALYSIS_LAZYCALLGRAPH_H
 
 #include "llvm/ADT/Any.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/PointerIntPair.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/iterator.h"
 #include "llvm/ADT/iterator_range.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/raw_ostream.h"
 #include <cassert>
 #include <iterator>
 #include <optional>
 #include <string>
 #include <utility>
 
 namespace llvm {
 
 class Constant;
 template <class GraphType> struct GraphTraits;
 class Module;
 
 /// A lazily constructed view of the call graph of a module.
 ///
 /// With the edges of this graph, the motivating constraint that we are
 /// attempting to maintain is that function-local optimization, CGSCC-local
 /// optimizations, and optimizations transforming a pair of functions connected
 /// by an edge in the graph, do not invalidate a bottom-up traversal of the SCC
 /// DAG. That is, no optimizations will delete, remove, or add an edge such
 /// that functions already visited in a bottom-up order of the SCC DAG are no
 /// longer valid to have visited, or such that functions not yet visited in
 /// a bottom-up order of the SCC DAG are not required to have already been
 /// visited.
 ///
 /// Within this constraint, the desire is to minimize the merge points of the
 /// SCC DAG. The greater the fanout of the SCC DAG and the fewer merge points
 /// in the SCC DAG, the more independence there is in optimizing within it.
 /// There is a strong desire to enable parallelization of optimizations over
 /// the call graph, and both limited fanout and merge points will (artificially
 /// in some cases) limit the scaling of such an effort.
 ///
 /// To this end, graph represents both direct and any potential resolution to
 /// an indirect call edge. Another way to think about it is that it represents
 /// both the direct call edges and any direct call edges that might be formed
 /// through static optimizations. Specifically, it considers taking the address
 /// of a function to be an edge in the call graph because this might be
 /// forwarded to become a direct call by some subsequent function-local
 /// optimization. The result is that the graph closely follows the use-def
 /// edges for functions. Walking "up" the graph can be done by looking at all
 /// of the uses of a function.
 ///
 /// The roots of the call graph are the external functions and functions
 /// escaped into global variables. Those functions can be called from outside
 /// of the module or via unknowable means in the IR -- we may not be able to
 /// form even a potential call edge from a function body which may dynamically
 /// load the function and call it.
 ///
 /// This analysis still requires updates to remain valid after optimizations
 /// which could potentially change the set of potential callees. The
 /// constraints it operates under only make the traversal order remain valid.
 ///
 /// The entire analysis must be re-computed if full interprocedural
 /// optimizations run at any point. For example, globalopt completely
 /// invalidates the information in this analysis.
 ///
 /// FIXME: This class is named LazyCallGraph in a lame attempt to distinguish
 /// it from the existing CallGraph. At some point, it is expected that this
 /// will be the only call graph and it will be renamed accordingly.
 class LazyCallGraph {
 public:
   class Node;
   class EdgeSequence;
   class RefSCC;
 
   /// A class used to represent edges in the call graph.
   ///
   /// The lazy call graph models both *call* edges and *reference* edges. Call
   /// edges are much what you would expect, and exist when there is a 'call' or
   /// 'invoke' instruction of some function. Reference edges are also tracked
   /// along side these, and exist whenever any instruction (transitively
   /// through its operands) references a function. All call edges are
   /// inherently reference edges, and so the reference graph forms a superset
   /// of the formal call graph.
   ///
   /// All of these forms of edges are fundamentally represented as outgoing
   /// edges. The edges are stored in the source node and point at the target
   /// node. This allows the edge structure itself to be a very compact data
   /// structure: essentially a tagged pointer.
   class Edge {
   public:
     /// The kind of edge in the graph.
     enum Kind : bool { Ref = false, Call = true };
 
     Edge();
     explicit Edge(Node &N, Kind K);
 
     /// Test whether the edge is null.
     ///
     /// This happens when an edge has been deleted. We leave the edge objects
     /// around but clear them.
     explicit operator bool() const;
 
     /// Returns the \c Kind of the edge.
     Kind getKind() const;
 
     /// Test whether the edge represents a direct call to a function.
     ///
     /// This requires that the edge is not null.
     bool isCall() const;
 
     /// Get the call graph node referenced by this edge.
     ///
     /// This requires that the edge is not null.
     Node &getNode() const;
 
     /// Get the function referenced by this edge.
     ///
     /// This requires that the edge is not null.
     Function &getFunction() const;
 
   private:
     friend class LazyCallGraph::EdgeSequence;
     friend class LazyCallGraph::RefSCC;
 
     PointerIntPair<Node *, 1, Kind> Value;
 
     void setKind(Kind K) { Value.setInt(K); }
   };
 
   /// The edge sequence object.
   ///
   /// This typically exists entirely within the node but is exposed as
   /// a separate type because a node doesn't initially have edges. An explicit
   /// population step is required to produce this sequence at first and it is
   /// then cached in the node. It is also used to represent edges entering the
   /// graph from outside the module to model the graph's roots.
   ///
   /// The sequence itself both iterable and indexable. The indexes remain
   /// stable even as the sequence mutates (including removal).
   class EdgeSequence {
     friend class LazyCallGraph;
     friend class LazyCallGraph::Node;
     friend class LazyCallGraph::RefSCC;
 
     using VectorT = SmallVector<Edge, 4>;
     using VectorImplT = SmallVectorImpl<Edge>;
 
   public:
     /// An iterator used for the edges to both entry nodes and child nodes.
     class iterator
         : public iterator_adaptor_base<iterator, VectorImplT::iterator,
                                        std::forward_iterator_tag> {
       friend class LazyCallGraph;
       friend class LazyCallGraph::Node;
 
       VectorImplT::iterator E;
 
       // Build the iterator for a specific position in the edge list.
       iterator(VectorImplT::iterator BaseI, VectorImplT::iterator E)
           : iterator_adaptor_base(BaseI), E(E) {
         while (I != E && !*I)
           ++I;
       }
 
     public:
       iterator() = default;
 
       using iterator_adaptor_base::operator++;
       iterator &operator++() {
         do {
           ++I;
         } while (I != E && !*I);
         return *this;
       }
     };
 
     /// An iterator over specifically call edges.
     ///
     /// This has the same iteration properties as the \c iterator, but
     /// restricts itself to edges which represent actual calls.
     class call_iterator
         : public iterator_adaptor_base<call_iterator, VectorImplT::iterator,
                                        std::forward_iterator_tag> {
       friend class LazyCallGraph;
       friend class LazyCallGraph::Node;
 
       VectorImplT::iterator E;
 
       /// Advance the iterator to the next valid, call edge.
       void advanceToNextEdge() {
         while (I != E && (!*I || !I->isCall()))
           ++I;
       }
 
       // Build the iterator for a specific position in the edge list.
       call_iterator(VectorImplT::iterator BaseI, VectorImplT::iterator E)
           : iterator_adaptor_base(BaseI), E(E) {
         advanceToNextEdge();
       }
 
     public:
       call_iterator() = default;
 
       using iterator_adaptor_base::operator++;
       call_iterator &operator++() {
         ++I;
         advanceToNextEdge();
         return *this;
       }
     };
 
     iterator begin() { return iterator(Edges.begin(), Edges.end()); }
     iterator end() { return iterator(Edges.end(), Edges.end()); }
 
     Edge &operator[](Node &N) {
       assert(EdgeIndexMap.contains(&N) && "No such edge!");
       auto &E = Edges[EdgeIndexMap.find(&N)->second];
       assert(E && "Dead or null edge!");
       return E;
     }
 
     Edge *lookup(Node &N) {
       auto EI = EdgeIndexMap.find(&N);
       if (EI == EdgeIndexMap.end())
         return nullptr;
       auto &E = Edges[EI->second];
       return E ? &E : nullptr;
     }
 
     call_iterator call_begin() {
       return call_iterator(Edges.begin(), Edges.end());
     }
     call_iterator call_end() { return call_iterator(Edges.end(), Edges.end()); }
 
     iterator_range<call_iterator> calls() {
       return make_range(call_begin(), call_end());
     }
 
     bool empty() {
       for (auto &E : Edges)
         if (E)
           return false;
 
       return true;
     }
 
   private:
     VectorT Edges;
     DenseMap<Node *, int> EdgeIndexMap;
 
     EdgeSequence() = default;
 
     /// Internal helper to insert an edge to a node.
     void insertEdgeInternal(Node &ChildN, Edge::Kind EK);
 
     /// Internal helper to change an edge kind.
     void setEdgeKind(Node &ChildN, Edge::Kind EK);
 
     /// Internal helper to remove the edge to the given function.
     bool removeEdgeInternal(Node &ChildN);
   };
 
   /// A node in the call graph.
   ///
   /// This represents a single node. Its primary roles are to cache the list of
   /// callees, de-duplicate and provide fast testing of whether a function is a
   /// callee, and facilitate iteration of child nodes in the graph.
   ///
   /// The node works much like an optional in order to lazily populate the
   /// edges of each node. Until populated, there are no edges. Once populated,
   /// you can access the edges by dereferencing the node or using the `->`
   /// operator as if the node was an `std::optional<EdgeSequence>`.
   class Node {
     friend class LazyCallGraph;
     friend class LazyCallGraph::RefSCC;
 
   public:
     LazyCallGraph &getGraph() const { return *G; }
 
     Function &getFunction() const { return *F; }
 
     StringRef getName() const { return F->getName(); }
 
     /// Equality is defined as address equality.
     bool operator==(const Node &N) const { return this == &N; }
     bool operator!=(const Node &N) const { return !operator==(N); }
 
     /// Tests whether the node has been populated with edges.
     bool isPopulated() const { return Edges.has_value(); }
 
     /// Tests whether this is actually a dead node and no longer valid.
     ///
     /// Users rarely interact with nodes in this state and other methods are
     /// invalid. This is used to model a node in an edge list where the
     /// function has been completely removed.
     bool isDead() const {
       assert(!G == !F &&
              "Both graph and function pointers should be null or non-null.");
       return !G;
     }
 
     // We allow accessing the edges by dereferencing or using the arrow
     // operator, essentially wrapping the internal optional.
     EdgeSequence &operator*() const {
       // Rip const off because the node itself isn't changing here.
       return const_cast<EdgeSequence &>(*Edges);
     }
     EdgeSequence *operator->() const { return &**this; }
 
     /// Populate the edges of this node if necessary.
     ///
     /// The first time this is called it will populate the edges for this node
     /// in the graph. It does this by scanning the underlying function, so once
     /// this is done, any changes to that function must be explicitly reflected
     /// in updates to the graph.
     ///
     /// \returns the populated \c EdgeSequence to simplify walking it.
     ///
     /// This will not update or re-scan anything if called repeatedly. Instead,
     /// the edge sequence is cached and returned immediately on subsequent
     /// calls.
     EdgeSequence &populate() {
       if (Edges)
         return *Edges;
 
       return populateSlow();
     }
 
   private:
     LazyCallGraph *G;
     Function *F;
 
     // We provide for the DFS numbering and Tarjan walk lowlink numbers to be
     // stored directly within the node. These are both '-1' when nodes are part
     // of an SCC (or RefSCC), or '0' when not yet reached in a DFS walk.
     int DFSNumber = 0;
     int LowLink = 0;
 
     std::optional<EdgeSequence> Edges;
 
     /// Basic constructor implements the scanning of F into Edges and
     /// EdgeIndexMap.
     Node(LazyCallGraph &G, Function &F) : G(&G), F(&F) {}
 
     /// Implementation of the scan when populating.
     EdgeSequence &populateSlow();
 
     /// Internal helper to directly replace the function with a new one.
     ///
     /// This is used to facilitate transformations which need to replace the
     /// formal Function object but directly move the body and users from one to
     /// the other.
     void replaceFunction(Function &NewF);
 
     void clear() { Edges.reset(); }
 
     /// Print the name of this node's function.
     friend raw_ostream &operator<<(raw_ostream &OS, const Node &N) {
       return OS << N.F->getName();
     }
 
     /// Dump the name of this node's function to stderr.
     void dump() const;
   };
 
   /// An SCC of the call graph.
   ///
   /// This represents a Strongly Connected Component of the direct call graph
   /// -- ignoring indirect calls and function references. It stores this as
   /// a collection of call graph nodes. While the order of nodes in the SCC is
   /// stable, it is not any particular order.
   ///
   /// The SCCs are nested within a \c RefSCC, see below for details about that
   /// outer structure. SCCs do not support mutation of the call graph, that
   /// must be done through the containing \c RefSCC in order to fully reason
   /// about the ordering and connections of the graph.
   class LLVM_ABI SCC {
     friend class LazyCallGraph;
     friend class LazyCallGraph::Node;
 
     RefSCC *OuterRefSCC;
     SmallVector<Node *, 1> Nodes;
 
     template <typename NodeRangeT>
     SCC(RefSCC &OuterRefSCC, NodeRangeT &&Nodes)
         : OuterRefSCC(&OuterRefSCC), Nodes(std::forward<NodeRangeT>(Nodes)) {}
 
     void clear() {
       OuterRefSCC = nullptr;
       Nodes.clear();
     }
 
     /// Print a short description useful for debugging or logging.
     ///
     /// We print the function names in the SCC wrapped in '()'s and skipping
     /// the middle functions if there are a large number.
     //
     // Note: this is defined inline to dodge issues with GCC's interpretation
     // of enclosing namespaces for friend function declarations.
     friend raw_ostream &operator<<(raw_ostream &OS, const SCC &C) {
       OS << '(';
       int I = 0;
       for (LazyCallGraph::Node &N : C) {
         if (I > 0)
           OS << ", ";
         // Elide the inner elements if there are too many.
         if (I > 8) {
           OS << "..., " << *C.Nodes.back();
           break;
         }
         OS << N;
         ++I;
       }
       OS << ')';
       return OS;
     }
 
     /// Dump a short description of this SCC to stderr.
     void dump() const;
 
 #if !defined(NDEBUG) || defined(EXPENSIVE_CHECKS)
     /// Verify invariants about the SCC.
     ///
     /// This will attempt to validate all of the basic invariants within an
     /// SCC, but not that it is a strongly connected component per se.
     /// Primarily useful while building and updating the graph to check that
     /// basic properties are in place rather than having inexplicable crashes
     /// later.
     void verify();
 #endif
 
   public:
     using iterator = pointee_iterator<SmallVectorImpl<Node *>::const_iterator>;
 
     iterator begin() const { return Nodes.begin(); }
     iterator end() const { return Nodes.end(); }
 
     int size() const { return Nodes.size(); }
 
     RefSCC &getOuterRefSCC() const { return *OuterRefSCC; }
 
     /// Test if this SCC is a parent of \a C.
     ///
     /// Note that this is linear in the number of edges departing the current
     /// SCC.
     bool isParentOf(const SCC &C) const;
 
     /// Test if this SCC is an ancestor of \a C.
     ///
     /// Note that in the worst case this is linear in the number of edges
     /// departing the current SCC and every SCC in the entire graph reachable
     /// from this SCC. Thus this very well may walk every edge in the entire
     /// call graph! Do not call this in a tight loop!
     bool isAncestorOf(const SCC &C) const;
 
     /// Test if this SCC is a child of \a C.
     ///
     /// See the comments for \c isParentOf for detailed notes about the
     /// complexity of this routine.
     bool isChildOf(const SCC &C) const { return C.isParentOf(*this); }
 
     /// Test if this SCC is a descendant of \a C.
     ///
     /// See the comments for \c isParentOf for detailed notes about the
     /// complexity of this routine.
     bool isDescendantOf(const SCC &C) const { return C.isAncestorOf(*this); }
 
     /// Provide a short name by printing this SCC to a std::string.
     ///
     /// This copes with the fact that we don't have a name per se for an SCC
     /// while still making the use of this in debugging and logging useful.
     std::string getName() const {
       std::string Name;
       raw_string_ostream OS(Name);
       OS << *this;
       OS.flush();
       return Name;
     }
   };
 
   /// A RefSCC of the call graph.
   ///
   /// This models a Strongly Connected Component of function reference edges in
   /// the call graph. As opposed to actual SCCs, these can be used to scope
   /// subgraphs of the module which are independent from other subgraphs of the
   /// module because they do not reference it in any way. This is also the unit
   /// where we do mutation of the graph in order to restrict mutations to those
   /// which don't violate this independence.
   ///
   /// A RefSCC contains a DAG of actual SCCs. All the nodes within the RefSCC
   /// are necessarily within some actual SCC that nests within it. Since
   /// a direct call *is* a reference, there will always be at least one RefSCC
   /// around any SCC.
   ///
   /// Spurious ref edges, meaning ref edges that still exist in the call graph
   /// even though the corresponding IR reference no longer exists, are allowed.
   /// This is mostly to support argument promotion, which can modify a caller to
   /// no longer pass a function. The only place that needs to specially handle
   /// this is deleting a dead function/node, otherwise the dead ref edges are
   /// automatically removed when visiting the function/node no longer containing
   /// the ref edge.
   class RefSCC {
     friend class LazyCallGraph;
     friend class LazyCallGraph::Node;
 
     LazyCallGraph *G;
 
     /// A postorder list of the inner SCCs.
     SmallVector<SCC *, 4> SCCs;
 
     /// A map from SCC to index in the postorder list.
     SmallDenseMap<SCC *, int, 4> SCCIndices;
 
     /// Fast-path constructor. RefSCCs should instead be constructed by calling
     /// formRefSCCFast on the graph itself.
     RefSCC(LazyCallGraph &G);
 
     void clear() {
       SCCs.clear();
       SCCIndices.clear();
     }
 
     /// Print a short description useful for debugging or logging.
     ///
     /// We print the SCCs wrapped in '[]'s and skipping the middle SCCs if
     /// there are a large number.
     //
     // Note: this is defined inline to dodge issues with GCC's interpretation
     // of enclosing namespaces for friend function declarations.
     friend raw_ostream &operator<<(raw_ostream &OS, const RefSCC &RC) {
       OS << '[';
       int I = 0;
       for (LazyCallGraph::SCC &C : RC) {
         if (I > 0)
           OS << ", ";
         // Elide the inner elements if there are too many.
         if (I > 4) {
           OS << "..., " << *RC.SCCs.back();
           break;
         }
         OS << C;
         ++I;
       }
       OS << ']';
       return OS;
     }
 
     /// Dump a short description of this RefSCC to stderr.
     void dump() const;
 
 #if !defined(NDEBUG) || defined(EXPENSIVE_CHECKS)
     /// Verify invariants about the RefSCC and all its SCCs.
     ///
     /// This will attempt to validate all of the invariants *within* the
     /// RefSCC, but not that it is a strongly connected component of the larger
     /// graph. This makes it useful even when partially through an update.
     ///
     /// Invariants checked:
     /// - SCCs and their indices match.
     /// - The SCCs list is in fact in post-order.
     void verify();
 #endif
 
   public:
     using iterator = pointee_iterator<SmallVectorImpl<SCC *>::const_iterator>;
     using range = iterator_range<iterator>;
     using parent_iterator =
         pointee_iterator<SmallPtrSetImpl<RefSCC *>::const_iterator>;
 
     iterator begin() const { return SCCs.begin(); }
     iterator end() const { return SCCs.end(); }
 
     ssize_t size() const { return SCCs.size(); }
 
     SCC &operator[](int Idx) { return *SCCs[Idx]; }
 
     iterator find(SCC &C) const {
       return SCCs.begin() + SCCIndices.find(&C)->second;
     }
 
     /// Test if this RefSCC is a parent of \a RC.
     ///
     /// CAUTION: This method walks every edge in the \c RefSCC, it can be very
     /// expensive.
     bool isParentOf(const RefSCC &RC) const;
 
     /// Test if this RefSCC is an ancestor of \a RC.
     ///
     /// CAUTION: This method walks the directed graph of edges as far as
     /// necessary to find a possible path to the argument. In the worst case
     /// this may walk the entire graph and can be extremely expensive.
     bool isAncestorOf(const RefSCC &RC) const;
 
     /// Test if this RefSCC is a child of \a RC.
     ///
     /// CAUTION: This method walks every edge in the argument \c RefSCC, it can
     /// be very expensive.
     bool isChildOf(const RefSCC &RC) const { return RC.isParentOf(*this); }
 
     /// Test if this RefSCC is a descendant of \a RC.
     ///
     /// CAUTION: This method walks the directed graph of edges as far as
     /// necessary to find a possible path from the argument. In the worst case
     /// this may walk the entire graph and can be extremely expensive.
     bool isDescendantOf(const RefSCC &RC) const {
       return RC.isAncestorOf(*this);
     }
 
     /// Provide a short name by printing this RefSCC to a std::string.
     ///
     /// This copes with the fact that we don't have a name per se for an RefSCC
     /// while still making the use of this in debugging and logging useful.
     std::string getName() const {
       std::string Name;
       raw_string_ostream OS(Name);
       OS << *this;
       OS.flush();
       return Name;
     }
 
     ///@{
     /// \name Mutation API
     ///
     /// These methods provide the core API for updating the call graph in the
     /// presence of (potentially still in-flight) DFS-found RefSCCs and SCCs.
     ///
     /// Note that these methods sometimes have complex runtimes, so be careful
     /// how you call them.
 
     /// Make an existing internal ref edge into a call edge.
     ///
     /// This may form a larger cycle and thus collapse SCCs into TargetN's SCC.
     /// If that happens, the optional callback \p MergedCB will be invoked (if
     /// provided) on the SCCs being merged away prior to actually performing
     /// the merge. Note that this will never include the target SCC as that
     /// will be the SCC functions are merged into to resolve the cycle. Once
     /// this function returns, these merged SCCs are not in a valid state but
     /// the pointers will remain valid until destruction of the parent graph
     /// instance for the purpose of clearing cached information. This function
     /// also returns 'true' if a cycle was formed and some SCCs merged away as
     /// a convenience.
     ///
     /// After this operation, both SourceN's SCC and TargetN's SCC may move
     /// position within this RefSCC's postorder list. Any SCCs merged are
     /// merged into the TargetN's SCC in order to preserve reachability analyses
     /// which took place on that SCC.
     bool switchInternalEdgeToCall(
         Node &SourceN, Node &TargetN,
         function_ref<void(ArrayRef<SCC *> MergedSCCs)> MergeCB = {});
 
     /// Make an existing internal call edge between separate SCCs into a ref
     /// edge.
     ///
     /// If SourceN and TargetN in separate SCCs within this RefSCC, changing
     /// the call edge between them to a ref edge is a trivial operation that
     /// does not require any structural changes to the call graph.
     void switchTrivialInternalEdgeToRef(Node &SourceN, Node &TargetN);
 
     /// Make an existing internal call edge within a single SCC into a ref
     /// edge.
     ///
     /// Since SourceN and TargetN are part of a single SCC, this SCC may be
     /// split up due to breaking a cycle in the call edges that formed it. If
     /// that happens, then this routine will insert new SCCs into the postorder
     /// list *before* the SCC of TargetN (previously the SCC of both). This
     /// preserves postorder as the TargetN can reach all of the other nodes by
     /// definition of previously being in a single SCC formed by the cycle from
     /// SourceN to TargetN.
     ///
     /// The newly added SCCs are added *immediately* and contiguously
     /// prior to the TargetN SCC and return the range covering the new SCCs in
     /// the RefSCC's postorder sequence. You can directly iterate the returned
     /// range to observe all of the new SCCs in postorder.
     ///
     /// Note that if SourceN and TargetN are in separate SCCs, the simpler
     /// routine `switchTrivialInternalEdgeToRef` should be used instead.
     iterator_range<iterator> switchInternalEdgeToRef(Node &SourceN,
                                                      Node &TargetN);
 
     /// Make an existing outgoing ref edge into a call edge.
     ///
     /// Note that this is trivial as there are no cyclic impacts and there
     /// remains a reference edge.
     void switchOutgoingEdgeToCall(Node &SourceN, Node &TargetN);
 
     /// Make an existing outgoing call edge into a ref edge.
     ///
     /// This is trivial as there are no cyclic impacts and there remains
     /// a reference edge.
     void switchOutgoingEdgeToRef(Node &SourceN, Node &TargetN);
 
     /// Insert a ref edge from one node in this RefSCC to another in this
     /// RefSCC.
     ///
     /// This is always a trivial operation as it doesn't change any part of the
     /// graph structure besides connecting the two nodes.
     ///
     /// Note that we don't support directly inserting internal *call* edges
     /// because that could change the graph structure and requires returning
     /// information about what became invalid. As a consequence, the pattern
     /// should be to first insert the necessary ref edge, and then to switch it
     /// to a call edge if needed and handle any invalidation that results. See
     /// the \c switchInternalEdgeToCall routine for details.
     void insertInternalRefEdge(Node &SourceN, Node &TargetN);
 
     /// Insert an edge whose parent is in this RefSCC and child is in some
     /// child RefSCC.
     ///
     /// There must be an existing path from the \p SourceN to the \p TargetN.
     /// This operation is inexpensive and does not change the set of SCCs and
     /// RefSCCs in the graph.
     void insertOutgoingEdge(Node &SourceN, Node &TargetN, Edge::Kind EK);
 
     /// Insert an edge whose source is in a descendant RefSCC and target is in
     /// this RefSCC.
     ///
     /// There must be an existing path from the target to the source in this
     /// case.
     ///
     /// NB! This is has the potential to be a very expensive function. It
     /// inherently forms a cycle in the prior RefSCC DAG and we have to merge
     /// RefSCCs to resolve that cycle. But finding all of the RefSCCs which
     /// participate in the cycle can in the worst case require traversing every
     /// RefSCC in the graph. Every attempt is made to avoid that, but passes
     /// must still exercise caution calling this routine repeatedly.
     ///
     /// Also note that this can only insert ref edges. In order to insert
     /// a call edge, first insert a ref edge and then switch it to a call edge.
     /// These are intentionally kept as separate interfaces because each step
     /// of the operation invalidates a different set of data structures.
     ///
     /// This returns all the RefSCCs which were merged into the this RefSCC
     /// (the target's). This allows callers to invalidate any cached
     /// information.
     ///
     /// FIXME: We could possibly optimize this quite a bit for cases where the
     /// caller and callee are very nearby in the graph. See comments in the
     /// implementation for details, but that use case might impact users.
     SmallVector<RefSCC *, 1> insertIncomingRefEdge(Node &SourceN,
                                                    Node &TargetN);
 
     /// Remove an edge whose source is in this RefSCC and target is *not*.
     ///
     /// This removes an inter-RefSCC edge. All inter-RefSCC edges originating
     /// from this SCC have been fully explored by any in-flight DFS graph
     /// formation, so this is always safe to call once you have the source
     /// RefSCC.
     ///
     /// This operation does not change the cyclic structure of the graph and so
     /// is very inexpensive. It may change the connectivity graph of the SCCs
     /// though, so be careful calling this while iterating over them.
     void removeOutgoingEdge(Node &SourceN, Node &TargetN);
 
     /// Remove a list of ref edges which are entirely within this RefSCC.
     ///
     /// Both the \a SourceN and all of the \a TargetNs must be within this
     /// RefSCC. Removing these edges may break cycles that form this RefSCC and
     /// thus this operation may change the RefSCC graph significantly. In
     /// particular, this operation will re-form new RefSCCs based on the
     /// remaining connectivity of the graph. The following invariants are
     /// guaranteed to hold after calling this method:
     ///
     /// 1) If a ref-cycle remains after removal, it leaves this RefSCC intact
     ///    and in the graph. No new RefSCCs are built.
     /// 2) Otherwise, this RefSCC will be dead after this call and no longer in
     ///    the graph or the postorder traversal of the call graph. Any iterator
     ///    pointing at this RefSCC will become invalid.
     /// 3) All newly formed RefSCCs will be returned and the order of the
     ///    RefSCCs returned will be a valid postorder traversal of the new
     ///    RefSCCs.
     /// 4) No RefSCC other than this RefSCC has its member set changed (this is
     ///    inherent in the definition of removing such an edge).
     ///
     /// These invariants are very important to ensure that we can build
     /// optimization pipelines on top of the CGSCC pass manager which
     /// intelligently update the RefSCC graph without invalidating other parts
     /// of the RefSCC graph.
     ///
     /// Note that we provide no routine to remove a *call* edge. Instead, you
     /// must first switch it to a ref edge using \c switchInternalEdgeToRef.
     /// This split API is intentional as each of these two steps can invalidate
     /// a different aspect of the graph structure and needs to have the
     /// invalidation handled independently.
     ///
     /// The runtime complexity of this method is, in the worst case, O(V+E)
     /// where V is the number of nodes in this RefSCC and E is the number of
     /// edges leaving the nodes in this RefSCC. Note that E includes both edges
     /// within this RefSCC and edges from this RefSCC to child RefSCCs. Some
     /// effort has been made to minimize the overhead of common cases such as
     /// self-edges and edge removals which result in a spanning tree with no
     /// more cycles.
     [[nodiscard]] SmallVector<RefSCC *, 1>
     removeInternalRefEdges(ArrayRef<std::pair<Node *, Node *>> Edges);
 
     /// A convenience wrapper around the above to handle trivial cases of
     /// inserting a new call edge.
     ///
     /// This is trivial whenever the target is in the same SCC as the source or
     /// the edge is an outgoing edge to some descendant SCC. In these cases
     /// there is no change to the cyclic structure of SCCs or RefSCCs.
     ///
     /// To further make calling this convenient, it also handles inserting
     /// already existing edges.
     void insertTrivialCallEdge(Node &SourceN, Node &TargetN);
 
     /// A convenience wrapper around the above to handle trivial cases of
     /// inserting a new ref edge.
     ///
     /// This is trivial whenever the target is in the same RefSCC as the source
     /// or the edge is an outgoing edge to some descendant RefSCC. In these
     /// cases there is no change to the cyclic structure of the RefSCCs.
     ///
     /// To further make calling this convenient, it also handles inserting
     /// already existing edges.
     void insertTrivialRefEdge(Node &SourceN, Node &TargetN);
 
     /// Directly replace a node's function with a new function.
     ///
     /// This should be used when moving the body and users of a function to
     /// a new formal function object but not otherwise changing the call graph
     /// structure in any way.
     ///
     /// It requires that the old function in the provided node have zero uses
     /// and the new function must have calls and references to it establishing
     /// an equivalent graph.
     void replaceNodeFunction(Node &N, Function &NewF);
 
     ///@}
   };
 
   /// A post-order depth-first RefSCC iterator over the call graph.
   ///
   /// This iterator walks the cached post-order sequence of RefSCCs. However,
   /// it trades stability for flexibility. It is restricted to a forward
   /// iterator but will survive mutations which insert new RefSCCs and continue
   /// to point to the same RefSCC even if it moves in the post-order sequence.
   class postorder_ref_scc_iterator
       : public iterator_facade_base<postorder_ref_scc_iterator,
                                     std::forward_iterator_tag, RefSCC> {
     friend class LazyCallGraph;
     friend class LazyCallGraph::Node;
 
     /// Nonce type to select the constructor for the end iterator.
     struct IsAtEndT {};
 
     LazyCallGraph *G;
     RefSCC *RC = nullptr;
 
     /// Build the begin iterator for a node.
     postorder_ref_scc_iterator(LazyCallGraph &G) : G(&G), RC(getRC(G, 0)) {
       incrementUntilNonEmptyRefSCC();
     }
 
     /// Build the end iterator for a node. This is selected purely by overload.
     postorder_ref_scc_iterator(LazyCallGraph &G, IsAtEndT /*Nonce*/) : G(&G) {}
 
     /// Get the post-order RefSCC at the given index of the postorder walk,
     /// populating it if necessary.
     static RefSCC *getRC(LazyCallGraph &G, int Index) {
       if (Index == (int)G.PostOrderRefSCCs.size())
         // We're at the end.
         return nullptr;
 
       return G.PostOrderRefSCCs[Index];
     }
 
     // Keep incrementing until RC is non-empty (or null).
     void incrementUntilNonEmptyRefSCC() {
       while (RC && RC->size() == 0)
         increment();
     }
 
     void increment() {
       assert(RC && "Cannot increment the end iterator!");
       RC = getRC(*G, G->RefSCCIndices.find(RC)->second + 1);
     }
 
   public:
     bool operator==(const postorder_ref_scc_iterator &Arg) const {
       return G == Arg.G && RC == Arg.RC;
     }
 
     reference operator*() const { return *RC; }
 
     using iterator_facade_base::operator++;
     postorder_ref_scc_iterator &operator++() {
       increment();
       incrementUntilNonEmptyRefSCC();
       return *this;
     }
   };
 
   /// Construct a graph for the given module.
   ///
   /// This sets up the graph and computes all of the entry points of the graph.
   /// No function definitions are scanned until their nodes in the graph are
   /// requested during traversal.
   LazyCallGraph(Module &M,
                 function_ref<TargetLibraryInfo &(Function &)> GetTLI);
 
   LazyCallGraph(LazyCallGraph &&G);
   LazyCallGraph &operator=(LazyCallGraph &&RHS);
 
 #if !defined(NDEBUG) || defined(EXPENSIVE_CHECKS)
   /// Verify that every RefSCC is valid.
   void verify();
 #endif
 
   bool invalidate(Module &, const PreservedAnalyses &PA,
                   ModuleAnalysisManager::Invalidator &);
 
   EdgeSequence::iterator begin() { return EntryEdges.begin(); }
   EdgeSequence::iterator end() { return EntryEdges.end(); }
 
   void buildRefSCCs();
 
   postorder_ref_scc_iterator postorder_ref_scc_begin() {
     if (!EntryEdges.empty())
       assert(!PostOrderRefSCCs.empty() &&
              "Must form RefSCCs before iterating them!");
     return postorder_ref_scc_iterator(*this);
   }
   postorder_ref_scc_iterator postorder_ref_scc_end() {
     if (!EntryEdges.empty())
       assert(!PostOrderRefSCCs.empty() &&
              "Must form RefSCCs before iterating them!");
     return postorder_ref_scc_iterator(*this,
                                       postorder_ref_scc_iterator::IsAtEndT());
   }
 
   iterator_range<postorder_ref_scc_iterator> postorder_ref_sccs() {
     return make_range(postorder_ref_scc_begin(), postorder_ref_scc_end());
   }
 
   /// Lookup a function in the graph which has already been scanned and added.
   Node *lookup(const Function &F) const { return NodeMap.lookup(&F); }
 
   /// Lookup a function's SCC in the graph.
   ///
   /// \returns null if the function hasn't been assigned an SCC via the RefSCC
   /// iterator walk.
   SCC *lookupSCC(Node &N) const { return SCCMap.lookup(&N); }
 
   /// Lookup a function's RefSCC in the graph.
   ///
   /// \returns null if the function hasn't been assigned a RefSCC via the
   /// RefSCC iterator walk.
   RefSCC *lookupRefSCC(Node &N) const {
     if (SCC *C = lookupSCC(N))
       return &C->getOuterRefSCC();
 
     return nullptr;
   }
 
   /// Get a graph node for a given function, scanning it to populate the graph
   /// data as necessary.
   Node &get(Function &F) {
     Node *&N = NodeMap[&F];
     if (N)
       return *N;
 
     return insertInto(F, N);
   }
 
   /// Get the sequence of known and defined library functions.
   ///
   /// These functions, because they are known to LLVM, can have calls
   /// introduced out of thin air from arbitrary IR.
   ArrayRef<Function *> getLibFunctions() const {
     return LibFunctions.getArrayRef();
   }
 
   /// Test whether a function is a known and defined library function tracked by
   /// the call graph.
   ///
   /// Because these functions are known to LLVM they are specially modeled in
   /// the call graph and even when all IR-level references have been removed
   /// remain active and reachable.
   bool isLibFunction(Function &F) const { return LibFunctions.count(&F); }
 
   ///@{
   /// \name Pre-SCC Mutation API
   ///
   /// These methods are only valid to call prior to forming any SCCs for this
   /// call graph. They can be used to update the core node-graph during
   /// a node-based inorder traversal that precedes any SCC-based traversal.
   ///
   /// Once you begin manipulating a call graph's SCCs, most mutation of the
   /// graph must be performed via a RefSCC method. There are some exceptions
   /// below.
 
   /// Update the call graph after inserting a new edge.
   void insertEdge(Node &SourceN, Node &TargetN, Edge::Kind EK);
 
   /// Update the call graph after inserting a new edge.
   void insertEdge(Function &Source, Function &Target, Edge::Kind EK) {
     return insertEdge(get(Source), get(Target), EK);
   }
 
   /// Update the call graph after deleting an edge.
   void removeEdge(Node &SourceN, Node &TargetN);
 
   /// Update the call graph after deleting an edge.
   void removeEdge(Function &Source, Function &Target) {
     return removeEdge(get(Source), get(Target));
   }
 
   ///@}
 
   ///@{
   /// \name General Mutation API
   ///
   /// There are a very limited set of mutations allowed on the graph as a whole
   /// once SCCs have started to be formed. These routines have strict contracts
   /// but may be called at any point.
 
   /// Remove dead functions from the call graph.
   ///
   /// These functions should have already been passed to markDeadFunction().
   /// This is done as a batch to prevent compile time blowup as a result of
   /// handling a single function at a time.
   void removeDeadFunctions(ArrayRef<Function *> DeadFs);
 
   /// Mark a function as dead to be removed later by removeDeadFunctions().
   ///
   /// The function body should have no incoming or outgoing call or ref edges.
   /// For example, a function with a single "unreachable" instruction.
   void markDeadFunction(Function &F);
 
   /// Add a new function split/outlined from an existing function.
   ///
   /// The new function may only reference other functions that the original
   /// function did.
   ///
   /// The original function must reference (either directly or indirectly) the
   /// new function.
   ///
   /// The new function may also reference the original function.
   /// It may end up in a parent SCC in the case that the original function's
   /// edge to the new function is a ref edge, and the edge back is a call edge.
   void addSplitFunction(Function &OriginalFunction, Function &NewFunction);
 
   /// Add new ref-recursive functions split/outlined from an existing function.
   ///
   /// The new functions may only reference other functions that the original
   /// function did. The new functions may reference (not call) the original
   /// function.
   ///
   /// The original function must reference (not call) all new functions.
   /// All new functions must reference (not call) each other.
   void addSplitRefRecursiveFunctions(Function &OriginalFunction,
                                      ArrayRef<Function *> NewFunctions);
 
   ///@}
 
   ///@{
   /// \name Static helpers for code doing updates to the call graph.
   ///
   /// These helpers are used to implement parts of the call graph but are also
   /// useful to code doing updates or otherwise wanting to walk the IR in the
   /// same patterns as when we build the call graph.
 
   /// Recursively visits the defined functions whose address is reachable from
   /// every constant in the \p Worklist.
   ///
   /// Doesn't recurse through any constants already in the \p Visited set, and
   /// updates that set with every constant visited.
   ///
   /// For each defined function, calls \p Callback with that function.
   static void visitReferences(SmallVectorImpl<Constant *> &Worklist,
                               SmallPtrSetImpl<Constant *> &Visited,
                               function_ref<void(Function &)> Callback);
 
   ///@}
 
 private:
   using node_stack_iterator = SmallVectorImpl<Node *>::reverse_iterator;
   using node_stack_range = iterator_range<node_stack_iterator>;
 
   /// Allocator that holds all the call graph nodes.
   SpecificBumpPtrAllocator<Node> BPA;
 
   /// Maps function->node for fast lookup.
   DenseMap<const Function *, Node *> NodeMap;
 
   /// The entry edges into the graph.
   ///
   /// These edges are from "external" sources. Put another way, they
   /// escape at the module scope.
   EdgeSequence EntryEdges;
 
   /// Allocator that holds all the call graph SCCs.
   SpecificBumpPtrAllocator<SCC> SCCBPA;
 
   /// Maps Function -> SCC for fast lookup.
   DenseMap<Node *, SCC *> SCCMap;
 
   /// Allocator that holds all the call graph RefSCCs.
   SpecificBumpPtrAllocator<RefSCC> RefSCCBPA;
 
   /// The post-order sequence of RefSCCs.
   ///
   /// This list is lazily formed the first time we walk the graph.
   SmallVector<RefSCC *, 16> PostOrderRefSCCs;
 
   /// A map from RefSCC to the index for it in the postorder sequence of
   /// RefSCCs.
   DenseMap<RefSCC *, int> RefSCCIndices;
 
   /// Defined functions that are also known library functions which the
   /// optimizer can reason about and therefore might introduce calls to out of
   /// thin air.
   SmallSetVector<Function *, 4> LibFunctions;
 
   /// Helper to insert a new function, with an already looked-up entry in
   /// the NodeMap.
   Node &insertInto(Function &F, Node *&MappedN);
 
   /// Helper to initialize a new node created outside of creating SCCs and add
   /// it to the NodeMap if necessary. For example, useful when a function is
   /// split.
   Node &initNode(Function &F);
 
   /// Helper to update pointers back to the graph object during moves.
   void updateGraphPtrs();
 
   /// Allocates an SCC and constructs it using the graph allocator.
   ///
   /// The arguments are forwarded to the constructor.
   template <typename... Ts> SCC *createSCC(Ts &&...Args) {
     return new (SCCBPA.Allocate()) SCC(std::forward<Ts>(Args)...);
   }
 
   /// Allocates a RefSCC and constructs it using the graph allocator.
   ///
   /// The arguments are forwarded to the constructor.
   template <typename... Ts> RefSCC *createRefSCC(Ts &&...Args) {
     return new (RefSCCBPA.Allocate()) RefSCC(std::forward<Ts>(Args)...);
   }
 
   /// Common logic for building SCCs from a sequence of roots.
   ///
   /// This is a very generic implementation of the depth-first walk and SCC
   /// formation algorithm. It uses a generic sequence of roots and generic
   /// callbacks for each step. This is designed to be used to implement both
   /// the RefSCC formation and SCC formation with shared logic.
   ///
   /// Currently this is a relatively naive implementation of Tarjan's DFS
   /// algorithm to form the SCCs.
   ///
   /// FIXME: We should consider newer variants such as Nuutila.
   template <typename RootsT, typename GetBeginT, typename GetEndT,
             typename GetNodeT, typename FormSCCCallbackT>
   static void buildGenericSCCs(RootsT &&Roots, GetBeginT &&GetBegin,
                                GetEndT &&GetEnd, GetNodeT &&GetNode,
                                FormSCCCallbackT &&FormSCC);
 
   /// Build the SCCs for a RefSCC out of a list of nodes.
   void buildSCCs(RefSCC &RC, node_stack_range Nodes);
 
   /// Get the index of a RefSCC within the postorder traversal.
   ///
   /// Requires that this RefSCC is a valid one in the (perhaps partial)
   /// postorder traversed part of the graph.
   int getRefSCCIndex(RefSCC &RC) {
     auto IndexIt = RefSCCIndices.find(&RC);
     assert(IndexIt != RefSCCIndices.end() && "RefSCC doesn't have an index!");
     assert(PostOrderRefSCCs[IndexIt->second] == &RC &&
            "Index does not point back at RC!");
     return IndexIt->second;
   }
 };
 
 inline LazyCallGraph::Edge::Edge() = default;
 inline LazyCallGraph::Edge::Edge(Node &N, Kind K) : Value(&N, K) {}
 
 inline LazyCallGraph::Edge::operator bool() const {
   return Value.getPointer() && !Value.getPointer()->isDead();
 }
 
 inline LazyCallGraph::Edge::Kind LazyCallGraph::Edge::getKind() const {
   assert(*this && "Queried a null edge!");
   return Value.getInt();
 }
 
 inline bool LazyCallGraph::Edge::isCall() const {
   assert(*this && "Queried a null edge!");
   return getKind() == Call;
 }
 
 inline LazyCallGraph::Node &LazyCallGraph::Edge::getNode() const {
   assert(*this && "Queried a null edge!");
   return *Value.getPointer();
 }
 
 inline Function &LazyCallGraph::Edge::getFunction() const {
   assert(*this && "Queried a null edge!");
   return getNode().getFunction();
 }
 
 // Provide GraphTraits specializations for call graphs.
 template <> struct GraphTraits<LazyCallGraph::Node *> {
   using NodeRef = LazyCallGraph::Node *;
   using ChildIteratorType = LazyCallGraph::EdgeSequence::iterator;
 
   static NodeRef getEntryNode(NodeRef N) { return N; }
   static ChildIteratorType child_begin(NodeRef N) { return (*N)->begin(); }
   static ChildIteratorType child_end(NodeRef N) { return (*N)->end(); }
 };
 template <> struct GraphTraits<LazyCallGraph *> {
   using NodeRef = LazyCallGraph::Node *;
   using ChildIteratorType = LazyCallGraph::EdgeSequence::iterator;
 
   static NodeRef getEntryNode(NodeRef N) { return N; }
   static ChildIteratorType child_begin(NodeRef N) { return (*N)->begin(); }
   static ChildIteratorType child_end(NodeRef N) { return (*N)->end(); }
 };
 
 /// An analysis pass which computes the call graph for a module.
 class LazyCallGraphAnalysis : public AnalysisInfoMixin<LazyCallGraphAnalysis> {
   friend AnalysisInfoMixin<LazyCallGraphAnalysis>;
 
   static AnalysisKey Key;
 
 public:
   /// Inform generic clients of the result type.
   using Result = LazyCallGraph;
 
   /// Compute the \c LazyCallGraph for the module \c M.
   ///
   /// This just builds the set of entry points to the call graph. The rest is
   /// built lazily as it is walked.
   LazyCallGraph run(Module &M, ModuleAnalysisManager &AM) {
     FunctionAnalysisManager &FAM =
         AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
     auto GetTLI = [&FAM](Function &F) -> TargetLibraryInfo & {
       return FAM.getResult<TargetLibraryAnalysis>(F);
     };
     return LazyCallGraph(M, GetTLI);
   }
 };
 
 /// A pass which prints the call graph to a \c raw_ostream.
 ///
 /// This is primarily useful for testing the analysis.
 class LazyCallGraphPrinterPass
     : public PassInfoMixin<LazyCallGraphPrinterPass> {
   raw_ostream &OS;
 
 public:
   explicit LazyCallGraphPrinterPass(raw_ostream &OS);
 
   PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);
 
   static bool isRequired() { return true; }
 };
 
 /// A pass which prints the call graph as a DOT file to a \c raw_ostream.
 ///
 /// This is primarily useful for visualization purposes.
 class LazyCallGraphDOTPrinterPass
     : public PassInfoMixin<LazyCallGraphDOTPrinterPass> {
   raw_ostream &OS;
 
 public:
   explicit LazyCallGraphDOTPrinterPass(raw_ostream &OS);
 
   PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);
 
   static bool isRequired() { return true; }
 };
 
 extern template struct LLVM_TEMPLATE_ABI
     Any::TypeId<const LazyCallGraph::SCC *>;
 } // end namespace llvm
 
 #endif // LLVM_ANALYSIS_LAZYCALLGRAPH_H

This page was automatically generated by the 2.3.7 LXR engine. The LXR team