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