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