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 std::iterator<std::bidirectional_iterator_tag, Node> {
 117     friend class LazyCallGraph;
 118     friend class LazyCallGraph::Node;
 119
 120     /// \brief Nonce type to select the constructor for the end iterator.
 121     struct IsAtEndT {};
 122
 123     LazyCallGraph *G;
 124     NodeVectorImplT::iterator NI;
 125
 126     // Build the begin iterator for a node.
 127     explicit iterator(LazyCallGraph &G, NodeVectorImplT &Nodes)
 128         : G(&G), NI(Nodes.begin()) {}
 129
 130     // Build the end iterator for a node. This is selected purely by overload.
 131     iterator(LazyCallGraph &G, NodeVectorImplT &Nodes, IsAtEndT /*Nonce*/)
 132         : G(&G), NI(Nodes.end()) {}
 133
 134   public:
 135     bool operator==(const iterator &Arg) const { return NI == Arg.NI; }
 136     bool operator!=(const iterator &Arg) const { return !operator==(Arg); }
 137
 138     reference operator*() const {
 139       if (NI->is<Node *>())
 140         return *NI->get<Node *>();
 141
 142       Function *F = NI->get<Function *>();
 143       Node &ChildN = G->get(*F);
 144       *NI = &ChildN;
 145       return ChildN;
 146     }
 147     pointer operator->() const { return &operator*(); }
 148
 149     iterator &operator++() {
 150       ++NI;
 151       return *this;
 152     }
 153     iterator operator++(int) {
 154       iterator prev = *this;
 155       ++*this;
 156       return prev;
 157     }
 158
 159     iterator &operator--() {
 160       --NI;
 161       return *this;
 162     }
 163     iterator operator--(int) {
 164       iterator next = *this;
 165       --*this;
 166       return next;
 167     }
 168   };
 169
 170   /// \brief A node in the call graph.
 171   ///
 172   /// This represents a single node. It's primary roles are to cache the list of
 173   /// callees, de-duplicate and provide fast testing of whether a function is
 174   /// a callee, and facilitate iteration of child nodes in the graph.
 175   class Node {
 176     friend class LazyCallGraph;
 177     friend class LazyCallGraph::SCC;
 178
 179     LazyCallGraph *G;
 180     Function &F;
 181
 182     // We provide for the DFS numbering and Tarjan walk lowlink numbers to be
 183     // stored directly within the node.
 184     int DFSNumber;
 185     int LowLink;
 186
 187     mutable NodeVectorT Callees;
 188     DenseMap<Function *, size_t> CalleeIndexMap;
 189
 190     /// \brief Basic constructor implements the scanning of F into Callees and
 191     /// CalleeIndexMap.
 192     Node(LazyCallGraph &G, Function &F);
 193
 194   public:
 195     typedef LazyCallGraph::iterator iterator;
 196
 197     Function &getFunction() const {
 198       return F;
 199     };
 200
 201     iterator begin() const { return iterator(*G, Callees); }
 202     iterator end() const { return iterator(*G, Callees, iterator::IsAtEndT()); }
 203
 204     /// Equality is defined as address equality.
 205     bool operator==(const Node &N) const { return this == &N; }
 206     bool operator!=(const Node &N) const { return !operator==(N); }
 207   };
 208
 209   /// \brief An SCC of the call graph.
 210   ///
 211   /// This represents a Strongly Connected Component of the call graph as
 212   /// a collection of call graph nodes. While the order of nodes in the SCC is
 213   /// stable, it is not any particular order.
 214   class SCC {
 215     friend class LazyCallGraph;
 216     friend class LazyCallGraph::Node;
 217
 218     SmallPtrSet<SCC *, 1> ParentSCCs;
 219     SmallVector<Node *, 1> Nodes;
 220
 221     SCC() {}
 222
 223     void insert(LazyCallGraph &G, Node &N);
 224
 225     void removeEdge(LazyCallGraph &G, Function &Caller, Function &Callee,
 226                     SCC &CalleeC);
 227
 228     SmallVector<LazyCallGraph::SCC *, 1>
 229     removeInternalEdge(LazyCallGraph &G, Node &Caller, Node &Callee);
 230
 231   public:
 232     typedef SmallVectorImpl<Node *>::const_iterator iterator;
 233     typedef pointee_iterator<SmallPtrSet<SCC *, 1>::const_iterator> parent_iterator;
 234
 235     iterator begin() const { return Nodes.begin(); }
 236     iterator end() const { return Nodes.end(); }
 237
 238     parent_iterator parent_begin() const { return ParentSCCs.begin(); }
 239     parent_iterator parent_end() const { return ParentSCCs.end(); }
 240
 241     iterator_range<parent_iterator> parents() const {
 242       return iterator_range<parent_iterator>(parent_begin(), parent_end());
 243     }
 244   };
 245
 246   /// \brief A post-order depth-first SCC iterator over the call graph.
 247   ///
 248   /// This iterator triggers the Tarjan DFS-based formation of the SCC DAG for
 249   /// the call graph, walking it lazily in depth-first post-order. That is, it
 250   /// always visits SCCs for a callee prior to visiting the SCC for a caller
 251   /// (when they are in different SCCs).
 252   class postorder_scc_iterator
 253       : public std::iterator<std::forward_iterator_tag, SCC> {
 254     friend class LazyCallGraph;
 255     friend class LazyCallGraph::Node;
 256
 257     /// \brief Nonce type to select the constructor for the end iterator.
 258     struct IsAtEndT {};
 259
 260     LazyCallGraph *G;
 261     SCC *C;
 262
 263     // Build the begin iterator for a node.
 264     postorder_scc_iterator(LazyCallGraph &G) : G(&G) {
 265       C = G.getNextSCCInPostOrder();
 266     }
 267
 268     // Build the end iterator for a node. This is selected purely by overload.
 269     postorder_scc_iterator(LazyCallGraph &G, IsAtEndT /*Nonce*/)
 270         : G(&G), C(nullptr) {}
 271
 272   public:
 273     bool operator==(const postorder_scc_iterator &Arg) const {
 274       return G == Arg.G && C == Arg.C;
 275     }
 276     bool operator!=(const postorder_scc_iterator &Arg) const {
 277       return !operator==(Arg);
 278     }
 279
 280     reference operator*() const { return *C; }
 281     pointer operator->() const { return &operator*(); }
 282
 283     postorder_scc_iterator &operator++() {
 284       C = G->getNextSCCInPostOrder();
 285       return *this;
 286     }
 287     postorder_scc_iterator operator++(int) {
 288       postorder_scc_iterator prev = *this;
 289       ++*this;
 290       return prev;
 291     }
 292   };
 293
 294   /// \brief Construct a graph for the given module.
 295   ///
 296   /// This sets up the graph and computes all of the entry points of the graph.
 297   /// No function definitions are scanned until their nodes in the graph are
 298   /// requested during traversal.
 299   LazyCallGraph(Module &M);
 300
 301   LazyCallGraph(LazyCallGraph &&G);
 302   LazyCallGraph &operator=(LazyCallGraph &&RHS);
 303
 304   iterator begin() { return iterator(*this, EntryNodes); }
 305   iterator end() { return iterator(*this, EntryNodes, iterator::IsAtEndT()); }
 306
 307   postorder_scc_iterator postorder_scc_begin() {
 308     return postorder_scc_iterator(*this);
 309   }
 310   postorder_scc_iterator postorder_scc_end() {
 311     return postorder_scc_iterator(*this, postorder_scc_iterator::IsAtEndT());
 312   }
 313
 314   iterator_range<postorder_scc_iterator> postorder_sccs() {
 315     return iterator_range<postorder_scc_iterator>(postorder_scc_begin(),
 316                                                   postorder_scc_end());
 317   }
 318
 319   /// \brief Lookup a function in the graph which has already been scanned and
 320   /// added.
 321   Node *lookup(const Function &F) const { return NodeMap.lookup(&F); }
 322
 323   /// \brief Lookup a function's SCC in the graph.
 324   ///
 325   /// \returns null if the function hasn't been assigned an SCC via the SCC
 326   /// iterator walk.
 327   SCC *lookupSCC(Node &N) const { return SCCMap.lookup(&N); }
 328
 329   /// \brief Get a graph node for a given function, scanning it to populate the
 330   /// graph data as necessary.
 331   Node &get(Function &F) {
 332     Node *&N = NodeMap[&F];
 333     if (N)
 334       return *N;
 335
 336     return insertInto(F, N);
 337   }
 338
 339   /// \brief Update the call graph after deleting an edge.
 340   void removeEdge(Node &Caller, Function &Callee);
 341
 342   /// \brief Update the call graph after deleting an edge.
 343   void removeEdge(Function &Caller, Function &Callee) {
 344     return removeEdge(get(Caller), Callee);
 345   }
 346
 347 private:
 348   /// \brief Allocator that holds all the call graph nodes.
 349   SpecificBumpPtrAllocator<Node> BPA;
 350
 351   /// \brief Maps function->node for fast lookup.
 352   DenseMap<const Function *, Node *> NodeMap;
 353
 354   /// \brief The entry nodes to the graph.
 355   ///
 356   /// These nodes are reachable through "external" means. Put another way, they
 357   /// escape at the module scope.
 358   NodeVectorT EntryNodes;
 359
 360   /// \brief Map of the entry nodes in the graph to their indices in
 361   /// \c EntryNodes.
 362   DenseMap<Function *, size_t> EntryIndexMap;
 363
 364   /// \brief Allocator that holds all the call graph SCCs.
 365   SpecificBumpPtrAllocator<SCC> SCCBPA;
 366
 367   /// \brief Maps Function -> SCC for fast lookup.
 368   DenseMap<Node *, SCC *> SCCMap;
 369
 370   /// \brief The leaf SCCs of the graph.
 371   ///
 372   /// These are all of the SCCs which have no children.
 373   SmallVector<SCC *, 4> LeafSCCs;
 374
 375   /// \brief Stack of nodes in the DFS walk.
 376   SmallVector<std::pair<Node *, iterator>, 4> DFSStack;
 377
 378   /// \brief Set of entry nodes not-yet-processed into SCCs.
 379   SmallSetVector<Function *, 4> SCCEntryNodes;
 380
 381   /// \brief Stack of nodes the DFS has walked but not yet put into a SCC.
 382   SmallVector<Node *, 4> PendingSCCStack;
 383
 384   /// \brief Counter for the next DFS number to assign.
 385   int NextDFSNumber;
 386
 387   /// \brief Helper to insert a new function, with an already looked-up entry in
 388   /// the NodeMap.
 389   Node &insertInto(Function &F, Node *&MappedN);
 390
 391   /// \brief Helper to update pointers back to the graph object during moves.
 392   void updateGraphPtrs();
 393
 394   /// \brief Helper to form a new SCC out of the top of a DFSStack-like
 395   /// structure.
 396   SCC *formSCC(Node *RootN, SmallVectorImpl<Node *> &NodeStack);
 397
 398   /// \brief Retrieve the next node in the post-order SCC walk of the call graph.
 399   SCC *getNextSCCInPostOrder();
 400 };
 401
 402 // Provide GraphTraits specializations for call graphs.
 403 template <> struct GraphTraits<LazyCallGraph::Node *> {
 404   typedef LazyCallGraph::Node NodeType;
 405   typedef LazyCallGraph::iterator ChildIteratorType;
 406
 407   static NodeType *getEntryNode(NodeType *N) { return N; }
 408   static ChildIteratorType child_begin(NodeType *N) { return N->begin(); }
 409   static ChildIteratorType child_end(NodeType *N) { return N->end(); }
 410 };
 411 template <> struct GraphTraits<LazyCallGraph *> {
 412   typedef LazyCallGraph::Node NodeType;
 413   typedef LazyCallGraph::iterator ChildIteratorType;
 414
 415   static NodeType *getEntryNode(NodeType *N) { return N; }
 416   static ChildIteratorType child_begin(NodeType *N) { return N->begin(); }
 417   static ChildIteratorType child_end(NodeType *N) { return N->end(); }
 418 };
 419
 420 /// \brief An analysis pass which computes the call graph for a module.
 421 class LazyCallGraphAnalysis {
 422 public:
 423   /// \brief Inform generic clients of the result type.
 424   typedef LazyCallGraph Result;
 425
 426   static void *ID() { return (void *)&PassID; }
 427
 428   /// \brief Compute the \c LazyCallGraph for a the module \c M.
 429   ///
 430   /// This just builds the set of entry points to the call graph. The rest is
 431   /// built lazily as it is walked.
 432   LazyCallGraph run(Module *M) { return LazyCallGraph(*M); }
 433
 434 private:
 435   static char PassID;
 436 };
 437
 438 /// \brief A pass which prints the call graph to a \c raw_ostream.
 439 ///
 440 /// This is primarily useful for testing the analysis.
 441 class LazyCallGraphPrinterPass {
 442   raw_ostream &OS;
 443
 444 public:
 445   explicit LazyCallGraphPrinterPass(raw_ostream &OS);
 446
 447   PreservedAnalyses run(Module *M, ModuleAnalysisManager *AM);
 448
 449   static StringRef name() { return "LazyCallGraphPrinterPass"; }
 450 };
 451
 452 }
 453
 454 #endif