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     iterator(const iterator &Arg) : G(Arg.G), NI(Arg.NI) {}
 135     iterator(iterator &&Arg) : G(Arg.G), NI(std::move(Arg.NI)) {}
 136     iterator &operator=(iterator Arg) {
 137       std::swap(Arg, *this);
 138       return *this;
 139     }
 140
 141     bool operator==(const iterator &Arg) { return NI == Arg.NI; }
 142     bool operator!=(const iterator &Arg) { return !operator==(Arg); }
 143
 144     reference operator*() const {
 145       if (NI->is<Node *>())
 146         return NI->get<Node *>();
 147
 148       Function *F = NI->get<Function *>();
 149       Node *ChildN = G.get(*F);
 150       *NI = ChildN;
 151       return ChildN;
 152     }
 153     pointer operator->() const { return operator*(); }
 154
 155     iterator &operator++() {
 156       ++NI;
 157       return *this;
 158     }
 159     iterator operator++(int) {
 160       iterator prev = *this;
 161       ++*this;
 162       return prev;
 163     }
 164
 165     iterator &operator--() {
 166       --NI;
 167       return *this;
 168     }
 169     iterator operator--(int) {
 170       iterator next = *this;
 171       --*this;
 172       return next;
 173     }
 174   };
 175
 176   /// \brief Construct a graph for the given module.
 177   ///
 178   /// This sets up the graph and computes all of the entry points of the graph.
 179   /// No function definitions are scanned until their nodes in the graph are
 180   /// requested during traversal.
 181   LazyCallGraph(Module &M);
 182
 183   /// \brief Copy constructor.
 184   ///
 185   /// This does a deep copy of the graph. It does no verification that the
 186   /// graph remains valid for the module. It is also relatively expensive.
 187   LazyCallGraph(const LazyCallGraph &G);
 188
 189   /// \brief Move constructor.
 190   ///
 191   /// This is a deep move. It leaves G in an undefined but destroyable state.
 192   /// Any other operation on G is likely to fail.
 193   LazyCallGraph(LazyCallGraph &&G);
 194
 195   /// \brief Copy and move assignment.
 196   LazyCallGraph &operator=(LazyCallGraph RHS) {
 197     std::swap(*this, RHS);
 198     return *this;
 199   }
 200
 201   iterator begin() { return iterator(*this, EntryNodes); }
 202   iterator end() { return iterator(*this, EntryNodes, iterator::IsAtEndT()); }
 203
 204   /// \brief Lookup a function in the graph which has already been scanned and
 205   /// added.
 206   Node *lookup(const Function &F) const { return NodeMap.lookup(&F); }
 207
 208   /// \brief Get a graph node for a given function, scanning it to populate the
 209   /// graph data as necessary.
 210   Node *get(Function &F) {
 211     Node *&N = NodeMap[&F];
 212     if (N)
 213       return N;
 214
 215     return insertInto(F, N);
 216   }
 217
 218 private:
 219   Module &M;
 220
 221   /// \brief Allocator that holds all the call graph nodes.
 222   SpecificBumpPtrAllocator<Node> BPA;
 223
 224   /// \brief Maps function->node for fast lookup.
 225   DenseMap<const Function *, Node *> NodeMap;
 226
 227   /// \brief The entry nodes to the graph.
 228   ///
 229   /// These nodes are reachable through "external" means. Put another way, they
 230   /// escape at the module scope.
 231   NodeVectorT EntryNodes;
 232
 233   /// \brief Set of the entry nodes to the graph.
 234   SmallPtrSet<Function *, 4> EntryNodeSet;
 235
 236   /// \brief Helper to insert a new function, with an already looked-up entry in
 237   /// the NodeMap.
 238   Node *insertInto(Function &F, Node *&MappedN);
 239
 240   /// \brief Helper to copy a node from another graph into this one.
 241   Node *copyInto(const Node &OtherN);
 242
 243   /// \brief Helper to move a node from another graph into this one.
 244   Node *moveInto(Node &&OtherN);
 245 };
 246
 247 /// \brief A node in the call graph.
 248 ///
 249 /// This represents a single node. It's primary roles are to cache the list of
 250 /// callees, de-duplicate and provide fast testing of whether a function is
 251 /// a callee, and facilitate iteration of child nodes in the graph.
 252 class LazyCallGraph::Node {
 253   friend class LazyCallGraph;
 254
 255   LazyCallGraph &G;
 256   Function &F;
 257   mutable NodeVectorT Callees;
 258   SmallPtrSet<Function *, 4> CalleeSet;
 259
 260   /// \brief Basic constructor implements the scanning of F into Callees and
 261   /// CalleeSet.
 262   Node(LazyCallGraph &G, Function &F);
 263
 264   /// \brief Constructor used when copying a node from one graph to another.
 265   Node(LazyCallGraph &G, const Node &OtherN);
 266
 267   /// \brief Constructor used when moving a node from one graph to another.
 268   Node(LazyCallGraph &G, Node &&OtherN);
 269
 270 public:
 271   typedef LazyCallGraph::iterator iterator;
 272
 273   Function &getFunction() const {
 274     return F;
 275   };
 276
 277   iterator begin() const { return iterator(G, Callees); }
 278   iterator end() const { return iterator(G, Callees, iterator::IsAtEndT()); }
 279
 280   /// Equality is defined as address equality.
 281   bool operator==(const Node &N) const { return this == &N; }
 282   bool operator!=(const Node &N) const { return !operator==(N); }
 283 };
 284
 285 // Provide GraphTraits specializations for call graphs.
 286 template <> struct GraphTraits<LazyCallGraph::Node *> {
 287   typedef LazyCallGraph::Node NodeType;
 288   typedef LazyCallGraph::iterator ChildIteratorType;
 289
 290   static NodeType *getEntryNode(NodeType *N) { return N; }
 291   static ChildIteratorType child_begin(NodeType *N) { return N->begin(); }
 292   static ChildIteratorType child_end(NodeType *N) { return N->end(); }
 293 };
 294 template <> struct GraphTraits<LazyCallGraph *> {
 295   typedef LazyCallGraph::Node NodeType;
 296   typedef LazyCallGraph::iterator ChildIteratorType;
 297
 298   static NodeType *getEntryNode(NodeType *N) { return N; }
 299   static ChildIteratorType child_begin(NodeType *N) { return N->begin(); }
 300   static ChildIteratorType child_end(NodeType *N) { return N->end(); }
 301 };
 302
 303 /// \brief An analysis pass which computes the call graph for a module.
 304 class LazyCallGraphAnalysis {
 305 public:
 306   /// \brief Inform generic clients of the result type.
 307   typedef LazyCallGraph Result;
 308
 309   static void *ID() { return (void *)&PassID; }
 310
 311   /// \brief Compute the \c LazyCallGraph for a the module \c M.
 312   ///
 313   /// This just builds the set of entry points to the call graph. The rest is
 314   /// built lazily as it is walked.
 315   LazyCallGraph run(Module *M) { return LazyCallGraph(*M); }
 316
 317 private:
 318   static char PassID;
 319 };
 320
 321 /// \brief A pass which prints the call graph to a \c raw_ostream.
 322 ///
 323 /// This is primarily useful for testing the analysis.
 324 class LazyCallGraphPrinterPass {
 325   raw_ostream &OS;
 326
 327 public:
 328   explicit LazyCallGraphPrinterPass(raw_ostream &OS);
 329
 330   PreservedAnalyses run(Module *M, ModuleAnalysisManager *AM);
 331
 332   static StringRef name() { return "LazyCallGraphPrinterPass"; }
 333 };
 334
 335 }
 336
 337 #endif