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/SmallPtrSet.h"
  42 #include "llvm/ADT/SmallVector.h"
  43 #include "llvm/IR/BasicBlock.h"
  44 #include "llvm/IR/Function.h"
  45 #include "llvm/IR/Module.h"
  46 #include "llvm/Support/Allocator.h"
  47 #include <iterator>
  48
  49 namespace llvm {
  50 class ModuleAnalysisManager;
  51 class PreservedAnalyses;
  52 class raw_ostream;
  53
  54 /// \brief A lazily constructed view of the call graph of a module.
  55 ///
  56 /// With the edges of this graph, the motivating constraint that we are
  57 /// attempting to maintain is that function-local optimization, CGSCC-local
  58 /// optimizations, and optimizations transforming a pair of functions connected
  59 /// by an edge in the graph, do not invalidate a bottom-up traversal of the SCC
  60 /// DAG. That is, no optimizations will delete, remove, or add an edge such
  61 /// that functions already visited in a bottom-up order of the SCC DAG are no
  62 /// longer valid to have visited, or such that functions not yet visited in
  63 /// a bottom-up order of the SCC DAG are not required to have already been
  64 /// visited.
  65 ///
  66 /// Within this constraint, the desire is to minimize the merge points of the
  67 /// SCC DAG. The greater the fanout of the SCC DAG and the fewer merge points
  68 /// in the SCC DAG, the more independence there is in optimizing within it.
  69 /// There is a strong desire to enable parallelization of optimizations over
  70 /// the call graph, and both limited fanout and merge points will (artificially
  71 /// in some cases) limit the scaling of such an effort.
  72 ///
  73 /// To this end, graph represents both direct and any potential resolution to
  74 /// an indirect call edge. Another way to think about it is that it represents
  75 /// both the direct call edges and any direct call edges that might be formed
  76 /// through static optimizations. Specifically, it considers taking the address
  77 /// of a function to be an edge in the call graph because this might be
  78 /// forwarded to become a direct call by some subsequent function-local
  79 /// optimization. The result is that the graph closely follows the use-def
  80 /// edges for functions. Walking "up" the graph can be done by looking at all
  81 /// of the uses of a function.
  82 ///
  83 /// The roots of the call graph are the external functions and functions
  84 /// escaped into global variables. Those functions can be called from outside
  85 /// of the module or via unknowable means in the IR -- we may not be able to
  86 /// form even a potential call edge from a function body which may dynamically
  87 /// load the function and call it.
  88 ///
  89 /// This analysis still requires updates to remain valid after optimizations
  90 /// which could potentially change the set of potential callees. The
  91 /// constraints it operates under only make the traversal order remain valid.
  92 ///
  93 /// The entire analysis must be re-computed if full interprocedural
  94 /// optimizations run at any point. For example, globalopt completely
  95 /// invalidates the information in this analysis.
  96 ///
  97 /// FIXME: This class is named LazyCallGraph in a lame attempt to distinguish
  98 /// it from the existing CallGraph. At some point, it is expected that this
  99 /// will be the only call graph and it will be renamed accordingly.
 100 class LazyCallGraph {
 101 public:
 102   class Node;
 103   typedef SmallVector<PointerUnion<Function *, Node *>, 4> NodeVectorT;
 104   typedef SmallVectorImpl<PointerUnion<Function *, Node *>> NodeVectorImplT;
 105
 106   /// \brief A lazy iterator used for both the entry nodes and child nodes.
 107   ///
 108   /// When this iterator is dereferenced, if not yet available, a function will
 109   /// be scanned for "calls" or uses of functions and its child information
 110   /// will be constructed. All of these results are accumulated and cached in
 111   /// the graph.
 112   class iterator : public std::iterator<std::bidirectional_iterator_tag, Node *,
 113                                         ptrdiff_t, Node *, Node *> {
 114     friend class LazyCallGraph;
 115     friend class LazyCallGraph::Node;
 116     typedef std::iterator<std::bidirectional_iterator_tag, Node *, ptrdiff_t,
 117                           Node *, Node *> BaseT;
 118
 119     /// \brief Nonce type to select the constructor for the end iterator.
 120     struct IsAtEndT {};
 121
 122     LazyCallGraph *G;
 123     NodeVectorImplT::iterator NI;
 124
 125     // Build the begin iterator for a node.
 126     explicit iterator(LazyCallGraph &G, NodeVectorImplT &Nodes)
 127         : G(&G), NI(Nodes.begin()) {}
 128
 129     // Build the end iterator for a node. This is selected purely by overload.
 130     iterator(LazyCallGraph &G, NodeVectorImplT &Nodes, IsAtEndT /*Nonce*/)
 131         : G(&G), NI(Nodes.end()) {}
 132
 133   public:
 134     bool operator==(const iterator &Arg) { return NI == Arg.NI; }
 135     bool operator!=(const iterator &Arg) { return !operator==(Arg); }
 136
 137     reference operator*() const {
 138       if (NI->is<Node *>())
 139         return NI->get<Node *>();
 140
 141       Function *F = NI->get<Function *>();
 142       Node *ChildN = G->get(*F);
 143       *NI = ChildN;
 144       return ChildN;
 145     }
 146     pointer operator->() const { return operator*(); }
 147
 148     iterator &operator++() {
 149       ++NI;
 150       return *this;
 151     }
 152     iterator operator++(int) {
 153       iterator prev = *this;
 154       ++*this;
 155       return prev;
 156     }
 157
 158     iterator &operator--() {
 159       --NI;
 160       return *this;
 161     }
 162     iterator operator--(int) {
 163       iterator next = *this;
 164       --*this;
 165       return next;
 166     }
 167   };
 168
 169   /// \brief A node in the call graph.
 170   ///
 171   /// This represents a single node. It's primary roles are to cache the list of
 172   /// callees, de-duplicate and provide fast testing of whether a function is
 173   /// a callee, and facilitate iteration of child nodes in the graph.
 174   class Node {
 175     friend class LazyCallGraph;
 176
 177     LazyCallGraph *G;
 178     Function &F;
 179     mutable NodeVectorT Callees;
 180     SmallPtrSet<Function *, 4> CalleeSet;
 181
 182     /// \brief Basic constructor implements the scanning of F into Callees and
 183     /// CalleeSet.
 184     Node(LazyCallGraph &G, Function &F);
 185
 186     /// \brief Constructor used when copying a node from one graph to another.
 187     Node(LazyCallGraph &G, const Node &OtherN);
 188
 189   public:
 190     typedef LazyCallGraph::iterator iterator;
 191
 192     Function &getFunction() const {
 193       return F;
 194     };
 195
 196     iterator begin() const { return iterator(*G, Callees); }
 197     iterator end() const { return iterator(*G, Callees, iterator::IsAtEndT()); }
 198
 199     /// Equality is defined as address equality.
 200     bool operator==(const Node &N) const { return this == &N; }
 201     bool operator!=(const Node &N) const { return !operator==(N); }
 202   };
 203
 204   /// \brief Construct a graph for the given module.
 205   ///
 206   /// This sets up the graph and computes all of the entry points of the graph.
 207   /// No function definitions are scanned until their nodes in the graph are
 208   /// requested during traversal.
 209   LazyCallGraph(Module &M);
 210
 211   /// \brief Copy constructor.
 212   ///
 213   /// This does a deep copy of the graph. It does no verification that the
 214   /// graph remains valid for the module. It is also relatively expensive.
 215   LazyCallGraph(const LazyCallGraph &G);
 216
 217   /// \brief Move constructor.
 218   ///
 219   /// This is a deep move. It leaves G in an undefined but destroyable state.
 220   /// Any other operation on G is likely to fail.
 221   LazyCallGraph(LazyCallGraph &&G);
 222
 223   /// \brief Copy and move assignment.
 224   LazyCallGraph &operator=(LazyCallGraph RHS) {
 225     std::swap(*this, RHS);
 226     return *this;
 227   }
 228
 229   iterator begin() { return iterator(*this, EntryNodes); }
 230   iterator end() { return iterator(*this, EntryNodes, iterator::IsAtEndT()); }
 231
 232   /// \brief Lookup a function in the graph which has already been scanned and
 233   /// added.
 234   Node *lookup(const Function &F) const { return NodeMap.lookup(&F); }
 235
 236   /// \brief Get a graph node for a given function, scanning it to populate the
 237   /// graph data as necessary.
 238   Node *get(Function &F) {
 239     Node *&N = NodeMap[&F];
 240     if (N)
 241       return N;
 242
 243     return insertInto(F, N);
 244   }
 245
 246 private:
 247   /// \brief Allocator that holds all the call graph nodes.
 248   SpecificBumpPtrAllocator<Node> BPA;
 249
 250   /// \brief Maps function->node for fast lookup.
 251   DenseMap<const Function *, Node *> NodeMap;
 252
 253   /// \brief The entry nodes to the graph.
 254   ///
 255   /// These nodes are reachable through "external" means. Put another way, they
 256   /// escape at the module scope.
 257   NodeVectorT EntryNodes;
 258
 259   /// \brief Set of the entry nodes to the graph.
 260   SmallPtrSet<Function *, 4> EntryNodeSet;
 261
 262   /// \brief Helper to insert a new function, with an already looked-up entry in
 263   /// the NodeMap.
 264   Node *insertInto(Function &F, Node *&MappedN);
 265
 266   /// \brief Helper to copy a node from another graph into this one.
 267   Node *copyInto(const Node &OtherN);
 268 };
 269
 270 // Provide GraphTraits specializations for call graphs.
 271 template <> struct GraphTraits<LazyCallGraph::Node *> {
 272   typedef LazyCallGraph::Node NodeType;
 273   typedef LazyCallGraph::iterator ChildIteratorType;
 274
 275   static NodeType *getEntryNode(NodeType *N) { return N; }
 276   static ChildIteratorType child_begin(NodeType *N) { return N->begin(); }
 277   static ChildIteratorType child_end(NodeType *N) { return N->end(); }
 278 };
 279 template <> struct GraphTraits<LazyCallGraph *> {
 280   typedef LazyCallGraph::Node NodeType;
 281   typedef LazyCallGraph::iterator ChildIteratorType;
 282
 283   static NodeType *getEntryNode(NodeType *N) { return N; }
 284   static ChildIteratorType child_begin(NodeType *N) { return N->begin(); }
 285   static ChildIteratorType child_end(NodeType *N) { return N->end(); }
 286 };
 287
 288 /// \brief An analysis pass which computes the call graph for a module.
 289 class LazyCallGraphAnalysis {
 290 public:
 291   /// \brief Inform generic clients of the result type.
 292   typedef LazyCallGraph Result;
 293
 294   static void *ID() { return (void *)&PassID; }
 295
 296   /// \brief Compute the \c LazyCallGraph for a the module \c M.
 297   ///
 298   /// This just builds the set of entry points to the call graph. The rest is
 299   /// built lazily as it is walked.
 300   LazyCallGraph run(Module *M) { return LazyCallGraph(*M); }
 301
 302 private:
 303   static char PassID;
 304 };
 305
 306 /// \brief A pass which prints the call graph to a \c raw_ostream.
 307 ///
 308 /// This is primarily useful for testing the analysis.
 309 class LazyCallGraphPrinterPass {
 310   raw_ostream &OS;
 311
 312 public:
 313   explicit LazyCallGraphPrinterPass(raw_ostream &OS);
 314
 315   PreservedAnalyses run(Module *M, ModuleAnalysisManager *AM);
 316
 317   static StringRef name() { return "LazyCallGraphPrinterPass"; }
 318 };
 319
 320 }
 321
 322 #endif