include/llvm/Analysis/LazyCallGraph.h

   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_LAZY_CALL_GRAPH
  36 #define LLVM_ANALYSIS_LAZY_CALL_GRAPH
  37
  38 #include "llvm/ADT/DenseMap.h"
  39 #include "llvm/ADT/PointerUnion.h"
  40 #include "llvm/ADT/STLExtras.h"
  41 #include "llvm/ADT/SetVector.h"
  42 #include "llvm/ADT/SmallPtrSet.h"
  43 #include "llvm/ADT/SmallVector.h"
  44 #include "llvm/ADT/iterator.h"
  45 #include "llvm/ADT/iterator_range.h"
  46 #include "llvm/IR/BasicBlock.h"
  47 #include "llvm/IR/Function.h"
  48 #include "llvm/IR/Module.h"
  49 #include "llvm/Support/Allocator.h"
  50 #include <iterator>
  51
  52 namespace llvm {
  53 class ModuleAnalysisManager;
  54 class PreservedAnalyses;
  55 class raw_ostream;
  56
  57 /// \brief A lazily constructed view of the call graph of a module.
  58 ///
  59 /// With the edges of this graph, the motivating constraint that we are
  60 /// attempting to maintain is that function-local optimization, CGSCC-local
  61 /// optimizations, and optimizations transforming a pair of functions connected
  62 /// by an edge in the graph, do not invalidate a bottom-up traversal of the SCC
  63 /// DAG. That is, no optimizations will delete, remove, or add an edge such
  64 /// that functions already visited in a bottom-up order of the SCC DAG are no
  65 /// longer valid to have visited, or such that functions not yet visited in
  66 /// a bottom-up order of the SCC DAG are not required to have already been
  67 /// visited.
  68 ///
  69 /// Within this constraint, the desire is to minimize the merge points of the
  70 /// SCC DAG. The greater the fanout of the SCC DAG and the fewer merge points
  71 /// in the SCC DAG, the more independence there is in optimizing within it.
  72 /// There is a strong desire to enable parallelization of optimizations over
  73 /// the call graph, and both limited fanout and merge points will (artificially
  74 /// in some cases) limit the scaling of such an effort.
  75 ///
  76 /// To this end, graph represents both direct and any potential resolution to
  77 /// an indirect call edge. Another way to think about it is that it represents
  78 /// both the direct call edges and any direct call edges that might be formed
  79 /// through static optimizations. Specifically, it considers taking the address
  80 /// of a function to be an edge in the call graph because this might be
  81 /// forwarded to become a direct call by some subsequent function-local
  82 /// optimization. The result is that the graph closely follows the use-def
  83 /// edges for functions. Walking "up" the graph can be done by looking at all
  84 /// of the uses of a function.
  85 ///
  86 /// The roots of the call graph are the external functions and functions
  87 /// escaped into global variables. Those functions can be called from outside
  88 /// of the module or via unknowable means in the IR -- we may not be able to
  89 /// form even a potential call edge from a function body which may dynamically
  90 /// load the function and call it.
  91 ///
  92 /// This analysis still requires updates to remain valid after optimizations
  93 /// which could potentially change the set of potential callees. The
  94 /// constraints it operates under only make the traversal order remain valid.
  95 ///
  96 /// The entire analysis must be re-computed if full interprocedural
  97 /// optimizations run at any point. For example, globalopt completely
  98 /// invalidates the information in this analysis.
  99 ///
 100 /// FIXME: This class is named LazyCallGraph in a lame attempt to distinguish
 101 /// it from the existing CallGraph. At some point, it is expected that this
 102 /// will be the only call graph and it will be renamed accordingly.
 103 class LazyCallGraph {
 104 public:
 105   class Node;
 106   class SCC;
 107   typedef SmallVector<PointerUnion<Function *, Node *>, 4> NodeVectorT;
 108   typedef SmallVectorImpl<PointerUnion<Function *, Node *>> NodeVectorImplT;
 109
 110   /// \brief A lazy iterator used for both the entry nodes and child nodes.
 111   ///
 112   /// When this iterator is dereferenced, if not yet available, a function will
 113   /// be scanned for "calls" or uses of functions and its child information
 114   /// will be constructed. All of these results are accumulated and cached in
 115   /// the graph.
 116   class iterator : public iterator_adaptor_base<
 117                        iterator, NodeVectorImplT::iterator, Node> {
 118     friend class LazyCallGraph;
 119     friend class LazyCallGraph::Node;
 120
 121     LazyCallGraph *G;
 122     NodeVectorImplT::iterator NI;
 123
 124     // Build the iterator for a specific position in a node list.
 125     iterator(LazyCallGraph &G, NodeVectorImplT::iterator NI)
 126         : iterator_adaptor_base(NI), G(&G) {}
 127
 128   public:
 129     iterator() {}
 130
 131     reference operator*() const {
 132       if (I->is<Node *>())
 133         return *I->get<Node *>();
 134
 135       Function *F = I->get<Function *>();
 136       Node &ChildN = G->get(*F);
 137       *I = &ChildN;
 138       return ChildN;
 139     }
 140   };
 141
 142   /// \brief A node in the call graph.
 143   ///
 144   /// This represents a single node. It's primary roles are to cache the list of
 145   /// callees, de-duplicate and provide fast testing of whether a function is
 146   /// a callee, and facilitate iteration of child nodes in the graph.
 147   class Node {
 148     friend class LazyCallGraph;
 149     friend class LazyCallGraph::SCC;
 150
 151     LazyCallGraph *G;
 152     Function &F;
 153
 154     // We provide for the DFS numbering and Tarjan walk lowlink numbers to be
 155     // stored directly within the node.
 156     int DFSNumber;
 157     int LowLink;
 158
 159     mutable NodeVectorT Callees;
 160     DenseMap<Function *, size_t> CalleeIndexMap;
 161
 162     /// \brief Basic constructor implements the scanning of F into Callees and
 163     /// CalleeIndexMap.
 164     Node(LazyCallGraph &G, Function &F);
 165
 166     /// \brief Internal helper to insert a callee.
 167     void insertEdgeInternal(Function &Callee);
 168
 169     /// \brief Internal helper to remove a callee from this node.
 170     void removeEdgeInternal(Function &Callee);
 171
 172   public:
 173     typedef LazyCallGraph::iterator iterator;
 174
 175     Function &getFunction() const {
 176       return F;
 177     };
 178
 179     iterator begin() const { return iterator(*G, Callees.begin()); }
 180     iterator end() const { return iterator(*G, Callees.end()); }
 181
 182     /// Equality is defined as address equality.
 183     bool operator==(const Node &N) const { return this == &N; }
 184     bool operator!=(const Node &N) const { return !operator==(N); }
 185   };
 186
 187   /// \brief An SCC of the call graph.
 188   ///
 189   /// This represents a Strongly Connected Component of the call graph as
 190   /// a collection of call graph nodes. While the order of nodes in the SCC is
 191   /// stable, it is not any particular order.
 192   class SCC {
 193     friend class LazyCallGraph;
 194     friend class LazyCallGraph::Node;
 195
 196     LazyCallGraph *G;
 197     SmallPtrSet<SCC *, 1> ParentSCCs;
 198     SmallVector<Node *, 1> Nodes;
 199
 200     SCC(LazyCallGraph &G) : G(&G) {}
 201
 202     void insert(Node &N);
 203
 204     void
 205     internalDFS(SmallVectorImpl<std::pair<Node *, Node::iterator>> &DFSStack,
 206                 SmallVectorImpl<Node *> &PendingSCCStack, Node *N,
 207                 SmallVectorImpl<SCC *> &ResultSCCs);
 208
 209   public:
 210     typedef SmallVectorImpl<Node *>::const_iterator iterator;
 211     typedef pointee_iterator<SmallPtrSet<SCC *, 1>::const_iterator> parent_iterator;
 212
 213     iterator begin() const { return Nodes.begin(); }
 214     iterator end() const { return Nodes.end(); }
 215
 216     parent_iterator parent_begin() const { return ParentSCCs.begin(); }
 217     parent_iterator parent_end() const { return ParentSCCs.end(); }
 218
 219     iterator_range<parent_iterator> parents() const {
 220       return iterator_range<parent_iterator>(parent_begin(), parent_end());
 221     }
 222
 223     ///@{
 224     /// \name Mutation API
 225     ///
 226     /// These methods provide the core API for updating the call graph in the
 227     /// presence of a (potentially still in-flight) DFS-found SCCs.
 228     ///
 229     /// Note that these methods sometimes have complex runtimes, so be careful
 230     /// how you call them.
 231
 232     /// \brief Remove an edge whose source is in this SCC and target is *not*.
 233     ///
 234     /// This removes an inter-SCC edge. All inter-SCC edges originating from
 235     /// this SCC have been fully explored by any in-flight DFS SCC formation,
 236     /// so this is always safe to call once you have the source SCC.
 237     ///
 238     /// This operation does not change the set of SCCs or the members of the
 239     /// SCCs and so is very inexpensive. It may change the connectivity graph
 240     /// of the SCCs though, so be careful calling this while iterating over
 241     /// them.
 242     void removeInterSCCEdge(Node &CallerN, Node &CalleeN);
 243
 244     /// \brief Remove an edge which is entirely within this SCC.
 245     ///
 246     /// Both the \a Caller and the \a Callee must be within this SCC. Removing
 247     /// such an edge make break cycles that form this SCC and thus this
 248     /// operation may change the SCC graph significantly. In particular, this
 249     /// operation will re-form new SCCs based on the remaining connectivity of
 250     /// the graph. The following invariants are guaranteed to hold after
 251     /// calling this method:
 252     ///
 253     /// 1) This SCC is still an SCC in the graph.
 254     /// 2) This SCC will be the parent of any new SCCs. Thus, this SCC is
 255     ///    preserved as the root of any new SCC directed graph formed.
 256     /// 3) No SCC other than this SCC has its member set changed (this is
 257     ///    inherent in the definiton of removing such an edge).
 258     /// 4) All of the parent links of the SCC graph will be updated to reflect
 259     ///    the new SCC structure.
 260     /// 5) All SCCs formed out of this SCC, excluding this SCC, will be
 261     ///    returned in a vector.
 262     /// 6) The order of the SCCs in the vector will be a valid postorder
 263     ///    traversal of the new SCCs.
 264     ///
 265     /// These invariants are very important to ensure that we can build
 266     /// optimization pipeliens on top of the CGSCC pass manager which
 267     /// intelligently update the SCC graph without invalidating other parts of
 268     /// the SCC graph.
 269     ///
 270     /// The runtime complexity of this method is, in the worst case, O(V+E)
 271     /// where V is the number of nodes in this SCC and E is the number of edges
 272     /// leaving the nodes in this SCC. Note that E includes both edges within
 273     /// this SCC and edges from this SCC to child SCCs. Some effort has been
 274     /// made to minimize the overhead of common cases such as self-edges and
 275     /// edge removals which result in a spanning tree with no more cycles.
 276     SmallVector<SCC *, 1> removeIntraSCCEdge(Node &CallerN, Node &CalleeN);
 277
 278     ///@}
 279   };
 280
 281   /// \brief A post-order depth-first SCC iterator over the call graph.
 282   ///
 283   /// This iterator triggers the Tarjan DFS-based formation of the SCC DAG for
 284   /// the call graph, walking it lazily in depth-first post-order. That is, it
 285   /// always visits SCCs for a callee prior to visiting the SCC for a caller
 286   /// (when they are in different SCCs).
 287   class postorder_scc_iterator
 288       : public iterator_facade_base<postorder_scc_iterator,
 289                                     std::forward_iterator_tag, SCC> {
 290     friend class LazyCallGraph;
 291     friend class LazyCallGraph::Node;
 292
 293     /// \brief Nonce type to select the constructor for the end iterator.
 294     struct IsAtEndT {};
 295
 296     LazyCallGraph *G;
 297     SCC *C;
 298
 299     // Build the begin iterator for a node.
 300     postorder_scc_iterator(LazyCallGraph &G) : G(&G) {
 301       C = G.getNextSCCInPostOrder();
 302     }
 303
 304     // Build the end iterator for a node. This is selected purely by overload.
 305     postorder_scc_iterator(LazyCallGraph &G, IsAtEndT /*Nonce*/)
 306         : G(&G), C(nullptr) {}
 307
 308   public:
 309     bool operator==(const postorder_scc_iterator &Arg) const {
 310       return G == Arg.G && C == Arg.C;
 311     }
 312
 313     reference operator*() const { return *C; }
 314
 315     using iterator_facade_base::operator++;
 316     postorder_scc_iterator &operator++() {
 317       C = G->getNextSCCInPostOrder();
 318       return *this;
 319     }
 320   };
 321
 322   /// \brief Construct a graph for the given module.
 323   ///
 324   /// This sets up the graph and computes all of the entry points of the graph.
 325   /// No function definitions are scanned until their nodes in the graph are
 326   /// requested during traversal.
 327   LazyCallGraph(Module &M);
 328
 329   LazyCallGraph(LazyCallGraph &&G);
 330   LazyCallGraph &operator=(LazyCallGraph &&RHS);
 331
 332   iterator begin() { return iterator(*this, EntryNodes.begin()); }
 333   iterator end() { return iterator(*this, EntryNodes.end()); }
 334
 335   postorder_scc_iterator postorder_scc_begin() {
 336     return postorder_scc_iterator(*this);
 337   }
 338   postorder_scc_iterator postorder_scc_end() {
 339     return postorder_scc_iterator(*this, postorder_scc_iterator::IsAtEndT());
 340   }
 341
 342   iterator_range<postorder_scc_iterator> postorder_sccs() {
 343     return iterator_range<postorder_scc_iterator>(postorder_scc_begin(),
 344                                                   postorder_scc_end());
 345   }
 346
 347   /// \brief Lookup a function in the graph which has already been scanned and
 348   /// added.
 349   Node *lookup(const Function &F) const { return NodeMap.lookup(&F); }
 350
 351   /// \brief Lookup a function's SCC in the graph.
 352   ///
 353   /// \returns null if the function hasn't been assigned an SCC via the SCC
 354   /// iterator walk.
 355   SCC *lookupSCC(Node &N) const { return SCCMap.lookup(&N); }
 356
 357   /// \brief Get a graph node for a given function, scanning it to populate the
 358   /// graph data as necessary.
 359   Node &get(Function &F) {
 360     Node *&N = NodeMap[&F];
 361     if (N)
 362       return *N;
 363
 364     return insertInto(F, N);
 365   }
 366
 367   ///@{
 368   /// \name Pre-SCC Mutation API
 369   ///
 370   /// These methods are only valid to call prior to forming any SCCs for this
 371   /// call graph. They can be used to update the core node-graph during
 372   /// a node-based inorder traversal that precedes any SCC-based traversal.
 373   ///
 374   /// Once you begin manipulating a call graph's SCCs, you must perform all
 375   /// mutation of the graph via the SCC methods.
 376
 377   /// \brief Update the call graph after inserting a new edge.
 378   void insertEdge(Node &Caller, Function &Callee);
 379
 380   /// \brief Update the call graph after inserting a new edge.
 381   void insertEdge(Function &Caller, Function &Callee) {
 382     return insertEdge(get(Caller), Callee);
 383   }
 384
 385   /// \brief Update the call graph after deleting an edge.
 386   void removeEdge(Node &Caller, Function &Callee);
 387
 388   /// \brief Update the call graph after deleting an edge.
 389   void removeEdge(Function &Caller, Function &Callee) {
 390     return removeEdge(get(Caller), Callee);
 391   }
 392
 393   ///@}
 394
 395 private:
 396   /// \brief Allocator that holds all the call graph nodes.
 397   SpecificBumpPtrAllocator<Node> BPA;
 398
 399   /// \brief Maps function->node for fast lookup.
 400   DenseMap<const Function *, Node *> NodeMap;
 401
 402   /// \brief The entry nodes to the graph.
 403   ///
 404   /// These nodes are reachable through "external" means. Put another way, they
 405   /// escape at the module scope.
 406   NodeVectorT EntryNodes;
 407
 408   /// \brief Map of the entry nodes in the graph to their indices in
 409   /// \c EntryNodes.
 410   DenseMap<Function *, size_t> EntryIndexMap;
 411
 412   /// \brief Allocator that holds all the call graph SCCs.
 413   SpecificBumpPtrAllocator<SCC> SCCBPA;
 414
 415   /// \brief Maps Function -> SCC for fast lookup.
 416   DenseMap<Node *, SCC *> SCCMap;
 417
 418   /// \brief The leaf SCCs of the graph.
 419   ///
 420   /// These are all of the SCCs which have no children.
 421   SmallVector<SCC *, 4> LeafSCCs;
 422
 423   /// \brief Stack of nodes in the DFS walk.
 424   SmallVector<std::pair<Node *, iterator>, 4> DFSStack;
 425
 426   /// \brief Set of entry nodes not-yet-processed into SCCs.
 427   SmallVector<Function *, 4> SCCEntryNodes;
 428
 429   /// \brief Stack of nodes the DFS has walked but not yet put into a SCC.
 430   SmallVector<Node *, 4> PendingSCCStack;
 431
 432   /// \brief Counter for the next DFS number to assign.
 433   int NextDFSNumber;
 434
 435   /// \brief Helper to insert a new function, with an already looked-up entry in
 436   /// the NodeMap.
 437   Node &insertInto(Function &F, Node *&MappedN);
 438
 439   /// \brief Helper to update pointers back to the graph object during moves.
 440   void updateGraphPtrs();
 441
 442   /// \brief Helper to form a new SCC out of the top of a DFSStack-like
 443   /// structure.
 444   SCC *formSCC(Node *RootN, SmallVectorImpl<Node *> &NodeStack);
 445
 446   /// \brief Retrieve the next node in the post-order SCC walk of the call graph.
 447   SCC *getNextSCCInPostOrder();
 448 };
 449
 450 // Provide GraphTraits specializations for call graphs.
 451 template <> struct GraphTraits<LazyCallGraph::Node *> {
 452   typedef LazyCallGraph::Node NodeType;
 453   typedef LazyCallGraph::iterator ChildIteratorType;
 454
 455   static NodeType *getEntryNode(NodeType *N) { return N; }
 456   static ChildIteratorType child_begin(NodeType *N) { return N->begin(); }
 457   static ChildIteratorType child_end(NodeType *N) { return N->end(); }
 458 };
 459 template <> struct GraphTraits<LazyCallGraph *> {
 460   typedef LazyCallGraph::Node NodeType;
 461   typedef LazyCallGraph::iterator ChildIteratorType;
 462
 463   static NodeType *getEntryNode(NodeType *N) { return N; }
 464   static ChildIteratorType child_begin(NodeType *N) { return N->begin(); }
 465   static ChildIteratorType child_end(NodeType *N) { return N->end(); }
 466 };
 467
 468 /// \brief An analysis pass which computes the call graph for a module.
 469 class LazyCallGraphAnalysis {
 470 public:
 471   /// \brief Inform generic clients of the result type.
 472   typedef LazyCallGraph Result;
 473
 474   static void *ID() { return (void *)&PassID; }
 475
 476   /// \brief Compute the \c LazyCallGraph for a the module \c M.
 477   ///
 478   /// This just builds the set of entry points to the call graph. The rest is
 479   /// built lazily as it is walked.
 480   LazyCallGraph run(Module *M) { return LazyCallGraph(*M); }
 481
 482 private:
 483   static char PassID;
 484 };
 485
 486 /// \brief A pass which prints the call graph to a \c raw_ostream.
 487 ///
 488 /// This is primarily useful for testing the analysis.
 489 class LazyCallGraphPrinterPass {
 490   raw_ostream &OS;
 491
 492 public:
 493   explicit LazyCallGraphPrinterPass(raw_ostream &OS);
 494
 495   PreservedAnalyses run(Module *M, ModuleAnalysisManager *AM);
 496
 497   static StringRef name() { return "LazyCallGraphPrinterPass"; }
 498 };
 499
 500 }
 501
 502 #endif