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) { return NI == Arg.NI; }
 138     bool operator!=(const iterator &Arg) { 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   public:
 227     typedef SmallVectorImpl<Node *>::const_iterator iterator;
 228
 229     iterator begin() const { return Nodes.begin(); }
 230     iterator end() const { return Nodes.end(); }
 231   };
 232
 233   /// \brief A post-order depth-first SCC iterator over the call graph.
 234   ///
 235   /// This iterator triggers the Tarjan DFS-based formation of the SCC DAG for
 236   /// the call graph, walking it lazily in depth-first post-order. That is, it
 237   /// always visits SCCs for a callee prior to visiting the SCC for a caller
 238   /// (when they are in different SCCs).
 239   class postorder_scc_iterator
 240       : public std::iterator<std::forward_iterator_tag, SCC *, ptrdiff_t, SCC *,
 241                              SCC *> {
 242     friend class LazyCallGraph;
 243     friend class LazyCallGraph::Node;
 244     typedef std::iterator<std::forward_iterator_tag, SCC *, ptrdiff_t,
 245                           SCC *, SCC *> BaseT;
 246
 247     /// \brief Nonce type to select the constructor for the end iterator.
 248     struct IsAtEndT {};
 249
 250     LazyCallGraph *G;
 251     SCC *C;
 252
 253     // Build the begin iterator for a node.
 254     postorder_scc_iterator(LazyCallGraph &G) : G(&G) {
 255       C = G.getNextSCCInPostOrder();
 256     }
 257
 258     // Build the end iterator for a node. This is selected purely by overload.
 259     postorder_scc_iterator(LazyCallGraph &G, IsAtEndT /*Nonce*/)
 260         : G(&G), C(nullptr) {}
 261
 262   public:
 263     bool operator==(const postorder_scc_iterator &Arg) {
 264       return G == Arg.G && C == Arg.C;
 265     }
 266     bool operator!=(const postorder_scc_iterator &Arg) {
 267       return !operator==(Arg);
 268     }
 269
 270     reference operator*() const { return C; }
 271     pointer operator->() const { return operator*(); }
 272
 273     postorder_scc_iterator &operator++() {
 274       C = G->getNextSCCInPostOrder();
 275       return *this;
 276     }
 277     postorder_scc_iterator operator++(int) {
 278       postorder_scc_iterator prev = *this;
 279       ++*this;
 280       return prev;
 281     }
 282   };
 283
 284   /// \brief Construct a graph for the given module.
 285   ///
 286   /// This sets up the graph and computes all of the entry points of the graph.
 287   /// No function definitions are scanned until their nodes in the graph are
 288   /// requested during traversal.
 289   LazyCallGraph(Module &M);
 290
 291   LazyCallGraph(LazyCallGraph &&G);
 292   LazyCallGraph &operator=(LazyCallGraph &&RHS);
 293
 294   iterator begin() { return iterator(*this, EntryNodes); }
 295   iterator end() { return iterator(*this, EntryNodes, iterator::IsAtEndT()); }
 296
 297   postorder_scc_iterator postorder_scc_begin() {
 298     return postorder_scc_iterator(*this);
 299   }
 300   postorder_scc_iterator postorder_scc_end() {
 301     return postorder_scc_iterator(*this, postorder_scc_iterator::IsAtEndT());
 302   }
 303
 304   iterator_range<postorder_scc_iterator> postorder_sccs() {
 305     return iterator_range<postorder_scc_iterator>(postorder_scc_begin(),
 306                                                   postorder_scc_end());
 307   }
 308
 309   /// \brief Lookup a function in the graph which has already been scanned and
 310   /// added.
 311   Node *lookup(const Function &F) const { return NodeMap.lookup(&F); }
 312
 313   /// \brief Get a graph node for a given function, scanning it to populate the
 314   /// graph data as necessary.
 315   Node *get(Function &F) {
 316     Node *&N = NodeMap[&F];
 317     if (N)
 318       return N;
 319
 320     return insertInto(F, N);
 321   }
 322
 323 private:
 324   /// \brief Allocator that holds all the call graph nodes.
 325   SpecificBumpPtrAllocator<Node> BPA;
 326
 327   /// \brief Maps function->node for fast lookup.
 328   DenseMap<const Function *, Node *> NodeMap;
 329
 330   /// \brief The entry nodes to the graph.
 331   ///
 332   /// These nodes are reachable through "external" means. Put another way, they
 333   /// escape at the module scope.
 334   NodeVectorT EntryNodes;
 335
 336   /// \brief Map of the entry nodes in the graph to their indices in
 337   /// \c EntryNodes.
 338   DenseMap<Function *, size_t> EntryIndexMap;
 339
 340   /// \brief Allocator that holds all the call graph SCCs.
 341   SpecificBumpPtrAllocator<SCC> SCCBPA;
 342
 343   /// \brief Maps Function -> SCC for fast lookup.
 344   DenseMap<const Function *, SCC *> SCCMap;
 345
 346   /// \brief The leaf SCCs of the graph.
 347   ///
 348   /// These are all of the SCCs which have no children.
 349   SmallVector<SCC *, 4> LeafSCCs;
 350
 351   /// \brief Stack of nodes not-yet-processed into SCCs.
 352   SmallVector<std::pair<Node *, iterator>, 4> DFSStack;
 353
 354   /// \brief Set of entry nodes not-yet-processed into SCCs.
 355   SmallSetVector<Function *, 4> SCCEntryNodes;
 356
 357   /// \brief Counter for the next DFS number to assign.
 358   int NextDFSNumber;
 359
 360   /// \brief Helper to insert a new function, with an already looked-up entry in
 361   /// the NodeMap.
 362   Node *insertInto(Function &F, Node *&MappedN);
 363
 364   /// \brief Helper to update pointers back to the graph object during moves.
 365   void updateGraphPtrs();
 366
 367   /// \brief Retrieve the next node in the post-order SCC walk of the call graph.
 368   SCC *getNextSCCInPostOrder();
 369 };
 370
 371 // Provide GraphTraits specializations for call graphs.
 372 template <> struct GraphTraits<LazyCallGraph::Node *> {
 373   typedef LazyCallGraph::Node NodeType;
 374   typedef LazyCallGraph::iterator ChildIteratorType;
 375
 376   static NodeType *getEntryNode(NodeType *N) { return N; }
 377   static ChildIteratorType child_begin(NodeType *N) { return N->begin(); }
 378   static ChildIteratorType child_end(NodeType *N) { return N->end(); }
 379 };
 380 template <> struct GraphTraits<LazyCallGraph *> {
 381   typedef LazyCallGraph::Node NodeType;
 382   typedef LazyCallGraph::iterator ChildIteratorType;
 383
 384   static NodeType *getEntryNode(NodeType *N) { return N; }
 385   static ChildIteratorType child_begin(NodeType *N) { return N->begin(); }
 386   static ChildIteratorType child_end(NodeType *N) { return N->end(); }
 387 };
 388
 389 /// \brief An analysis pass which computes the call graph for a module.
 390 class LazyCallGraphAnalysis {
 391 public:
 392   /// \brief Inform generic clients of the result type.
 393   typedef LazyCallGraph Result;
 394
 395   static void *ID() { return (void *)&PassID; }
 396
 397   /// \brief Compute the \c LazyCallGraph for a the module \c M.
 398   ///
 399   /// This just builds the set of entry points to the call graph. The rest is
 400   /// built lazily as it is walked.
 401   LazyCallGraph run(Module *M) { return LazyCallGraph(*M); }
 402
 403 private:
 404   static char PassID;
 405 };
 406
 407 /// \brief A pass which prints the call graph to a \c raw_ostream.
 408 ///
 409 /// This is primarily useful for testing the analysis.
 410 class LazyCallGraphPrinterPass {
 411   raw_ostream &OS;
 412
 413 public:
 414   explicit LazyCallGraphPrinterPass(raw_ostream &OS);
 415
 416   PreservedAnalyses run(Module *M, ModuleAnalysisManager *AM);
 417
 418   static StringRef name() { return "LazyCallGraphPrinterPass"; }
 419 };
 420
 421 }
 422
 423 #endif