LCOV - code coverage report
Current view: top level - include/llvm/Analysis - LazyCallGraph.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 125 143 87.4 %
Date: 2018-10-20 13:21:21 Functions: 17 26 65.4 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.13