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     SmallPtrSet<Function *, 4> CalleeSet;
 191
 192     /// \brief Basic constructor implements the scanning of F into Callees and
 193     /// CalleeSet.
 194     Node(LazyCallGraph &G, Function &F);
 195
 196     /// \brief Constructor used when copying a node from one graph to another.
 197     Node(LazyCallGraph &G, const Node &OtherN);
 198
 199   public:
 200     typedef LazyCallGraph::iterator iterator;
 201
 202     Function &getFunction() const {
 203       return F;
 204     };
 205
 206     iterator begin() const { return iterator(*G, Callees); }
 207     iterator end() const { return iterator(*G, Callees, iterator::IsAtEndT()); }
 208
 209     /// Equality is defined as address equality.
 210     bool operator==(const Node &N) const { return this == &N; }
 211     bool operator!=(const Node &N) const { return !operator==(N); }
 212   };
 213
 214   /// \brief An SCC of the call graph.
 215   ///
 216   /// This represents a Strongly Connected Component of the call graph as
 217   /// a collection of call graph nodes. While the order of nodes in the SCC is
 218   /// stable, it is not any particular order.
 219   class SCC {
 220     friend class LazyCallGraph;
 221     friend class LazyCallGraph::Node;
 222
 223     SmallSetVector<SCC *, 1> ParentSCCs;
 224     SmallVector<Node *, 1> Nodes;
 225     SmallPtrSet<Function *, 1> NodeSet;
 226
 227     SCC() {}
 228
 229   public:
 230     typedef SmallVectorImpl<Node *>::const_iterator iterator;
 231
 232     iterator begin() const { return Nodes.begin(); }
 233     iterator end() const { return Nodes.end(); }
 234   };
 235
 236   /// \brief A post-order depth-first SCC iterator over the call graph.
 237   ///
 238   /// This iterator triggers the Tarjan DFS-based formation of the SCC DAG for
 239   /// the call graph, walking it lazily in depth-first post-order. That is, it
 240   /// always visits SCCs for a callee prior to visiting the SCC for a caller
 241   /// (when they are in different SCCs).
 242   class postorder_scc_iterator
 243       : public std::iterator<std::forward_iterator_tag, SCC *, ptrdiff_t, SCC *,
 244                              SCC *> {
 245     friend class LazyCallGraph;
 246     friend class LazyCallGraph::Node;
 247     typedef std::iterator<std::forward_iterator_tag, SCC *, ptrdiff_t,
 248                           SCC *, SCC *> BaseT;
 249
 250     /// \brief Nonce type to select the constructor for the end iterator.
 251     struct IsAtEndT {};
 252
 253     LazyCallGraph *G;
 254     SCC *C;
 255
 256     // Build the begin iterator for a node.
 257     postorder_scc_iterator(LazyCallGraph &G) : G(&G) {
 258       C = G.getNextSCCInPostOrder();
 259     }
 260
 261     // Build the end iterator for a node. This is selected purely by overload.
 262     postorder_scc_iterator(LazyCallGraph &G, IsAtEndT /*Nonce*/)
 263         : G(&G), C(nullptr) {}
 264
 265   public:
 266     bool operator==(const postorder_scc_iterator &Arg) {
 267       return G == Arg.G && C == Arg.C;
 268     }
 269     bool operator!=(const postorder_scc_iterator &Arg) {
 270       return !operator==(Arg);
 271     }
 272
 273     reference operator*() const { return C; }
 274     pointer operator->() const { return operator*(); }
 275
 276     postorder_scc_iterator &operator++() {
 277       C = G->getNextSCCInPostOrder();
 278       return *this;
 279     }
 280     postorder_scc_iterator operator++(int) {
 281       postorder_scc_iterator prev = *this;
 282       ++*this;
 283       return prev;
 284     }
 285   };
 286
 287   /// \brief Construct a graph for the given module.
 288   ///
 289   /// This sets up the graph and computes all of the entry points of the graph.
 290   /// No function definitions are scanned until their nodes in the graph are
 291   /// requested during traversal.
 292   LazyCallGraph(Module &M);
 293
 294   /// \brief Copy constructor.
 295   ///
 296   /// This does a deep copy of the graph. It does no verification that the
 297   /// graph remains valid for the module. It is also relatively expensive.
 298   LazyCallGraph(const LazyCallGraph &G);
 299
 300   /// \brief Move constructor.
 301   ///
 302   /// This is a deep move. It leaves G in an undefined but destroyable state.
 303   /// Any other operation on G is likely to fail.
 304   LazyCallGraph(LazyCallGraph &&G);
 305
 306   /// \brief Copy and move assignment.
 307   LazyCallGraph &operator=(LazyCallGraph RHS) {
 308     std::swap(*this, RHS);
 309     return *this;
 310   }
 311
 312   iterator begin() { return iterator(*this, EntryNodes); }
 313   iterator end() { return iterator(*this, EntryNodes, iterator::IsAtEndT()); }
 314
 315   postorder_scc_iterator postorder_scc_begin() {
 316     return postorder_scc_iterator(*this);
 317   }
 318   postorder_scc_iterator postorder_scc_end() {
 319     return postorder_scc_iterator(*this, postorder_scc_iterator::IsAtEndT());
 320   }
 321
 322   iterator_range<postorder_scc_iterator> postorder_sccs() {
 323     return iterator_range<postorder_scc_iterator>(postorder_scc_begin(),
 324                                                   postorder_scc_end());
 325   }
 326
 327   /// \brief Lookup a function in the graph which has already been scanned and
 328   /// added.
 329   Node *lookup(const Function &F) const { return NodeMap.lookup(&F); }
 330
 331   /// \brief Get a graph node for a given function, scanning it to populate the
 332   /// graph data as necessary.
 333   Node *get(Function &F) {
 334     Node *&N = NodeMap[&F];
 335     if (N)
 336       return N;
 337
 338     return insertInto(F, N);
 339   }
 340
 341 private:
 342   /// \brief Allocator that holds all the call graph nodes.
 343   SpecificBumpPtrAllocator<Node> BPA;
 344
 345   /// \brief Maps function->node for fast lookup.
 346   DenseMap<const Function *, Node *> NodeMap;
 347
 348   /// \brief The entry nodes to the graph.
 349   ///
 350   /// These nodes are reachable through "external" means. Put another way, they
 351   /// escape at the module scope.
 352   NodeVectorT EntryNodes;
 353
 354   /// \brief Set of the entry nodes to the graph.
 355   SmallPtrSet<Function *, 4> EntryNodeSet;
 356
 357   /// \brief Allocator that holds all the call graph SCCs.
 358   SpecificBumpPtrAllocator<SCC> SCCBPA;
 359
 360   /// \brief Maps Function -> SCC for fast lookup.
 361   DenseMap<const Function *, SCC *> SCCMap;
 362
 363   /// \brief The leaf SCCs of the graph.
 364   ///
 365   /// These are all of the SCCs which have no children.
 366   SmallVector<SCC *, 4> LeafSCCs;
 367
 368   /// \brief Stack of nodes not-yet-processed into SCCs.
 369   SmallVector<std::pair<Node *, iterator>, 4> DFSStack;
 370
 371   /// \brief Set of entry nodes not-yet-processed into SCCs.
 372   SmallSetVector<Function *, 4> SCCEntryNodes;
 373
 374   /// \brief Counter for the next DFS number to assign.
 375   int NextDFSNumber;
 376
 377   /// \brief Helper to insert a new function, with an already looked-up entry in
 378   /// the NodeMap.
 379   Node *insertInto(Function &F, Node *&MappedN);
 380
 381   /// \brief Helper to copy a node from another graph into this one.
 382   Node *copyInto(const Node &OtherN);
 383
 384   /// \brief Retrieve the next node in the post-order SCC walk of the call graph.
 385   SCC *getNextSCCInPostOrder();
 386 };
 387
 388 // Provide GraphTraits specializations for call graphs.
 389 template <> struct GraphTraits<LazyCallGraph::Node *> {
 390   typedef LazyCallGraph::Node NodeType;
 391   typedef LazyCallGraph::iterator ChildIteratorType;
 392
 393   static NodeType *getEntryNode(NodeType *N) { return N; }
 394   static ChildIteratorType child_begin(NodeType *N) { return N->begin(); }
 395   static ChildIteratorType child_end(NodeType *N) { return N->end(); }
 396 };
 397 template <> struct GraphTraits<LazyCallGraph *> {
 398   typedef LazyCallGraph::Node NodeType;
 399   typedef LazyCallGraph::iterator ChildIteratorType;
 400
 401   static NodeType *getEntryNode(NodeType *N) { return N; }
 402   static ChildIteratorType child_begin(NodeType *N) { return N->begin(); }
 403   static ChildIteratorType child_end(NodeType *N) { return N->end(); }
 404 };
 405
 406 /// \brief An analysis pass which computes the call graph for a module.
 407 class LazyCallGraphAnalysis {
 408 public:
 409   /// \brief Inform generic clients of the result type.
 410   typedef LazyCallGraph Result;
 411
 412   static void *ID() { return (void *)&PassID; }
 413
 414   /// \brief Compute the \c LazyCallGraph for a the module \c M.
 415   ///
 416   /// This just builds the set of entry points to the call graph. The rest is
 417   /// built lazily as it is walked.
 418   LazyCallGraph run(Module *M) { return LazyCallGraph(*M); }
 419
 420 private:
 421   static char PassID;
 422 };
 423
 424 /// \brief A pass which prints the call graph to a \c raw_ostream.
 425 ///
 426 /// This is primarily useful for testing the analysis.
 427 class LazyCallGraphPrinterPass {
 428   raw_ostream &OS;
 429
 430 public:
 431   explicit LazyCallGraphPrinterPass(raw_ostream &OS);
 432
 433   PreservedAnalyses run(Module *M, ModuleAnalysisManager *AM);
 434
 435   static StringRef name() { return "LazyCallGraphPrinterPass"; }
 436 };
 437
 438 }
 439
 440 #endif