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     /// \brief Constructor used when moving a node from one graph to another.
 190     Node(LazyCallGraph &G, Node &&OtherN);
 191
 192   public:
 193     typedef LazyCallGraph::iterator iterator;
 194
 195     Function &getFunction() const {
 196       return F;
 197     };
 198
 199     iterator begin() const { return iterator(*G, Callees); }
 200     iterator end() const { return iterator(*G, Callees, iterator::IsAtEndT()); }
 201
 202     /// Equality is defined as address equality.
 203     bool operator==(const Node &N) const { return this == &N; }
 204     bool operator!=(const Node &N) const { return !operator==(N); }
 205   };
 206
 207   /// \brief Construct a graph for the given module.
 208   ///
 209   /// This sets up the graph and computes all of the entry points of the graph.
 210   /// No function definitions are scanned until their nodes in the graph are
 211   /// requested during traversal.
 212   LazyCallGraph(Module &M);
 213
 214   /// \brief Copy constructor.
 215   ///
 216   /// This does a deep copy of the graph. It does no verification that the
 217   /// graph remains valid for the module. It is also relatively expensive.
 218   LazyCallGraph(const LazyCallGraph &G);
 219
 220   /// \brief Move constructor.
 221   ///
 222   /// This is a deep move. It leaves G in an undefined but destroyable state.
 223   /// Any other operation on G is likely to fail.
 224   LazyCallGraph(LazyCallGraph &&G);
 225
 226   /// \brief Copy and move assignment.
 227   LazyCallGraph &operator=(LazyCallGraph RHS) {
 228     std::swap(*this, RHS);
 229     return *this;
 230   }
 231
 232   iterator begin() { return iterator(*this, EntryNodes); }
 233   iterator end() { return iterator(*this, EntryNodes, iterator::IsAtEndT()); }
 234
 235   /// \brief Lookup a function in the graph which has already been scanned and
 236   /// added.
 237   Node *lookup(const Function &F) const { return NodeMap.lookup(&F); }
 238
 239   /// \brief Get a graph node for a given function, scanning it to populate the
 240   /// graph data as necessary.
 241   Node *get(Function &F) {
 242     Node *&N = NodeMap[&F];
 243     if (N)
 244       return N;
 245
 246     return insertInto(F, N);
 247   }
 248
 249 private:
 250   /// \brief Allocator that holds all the call graph nodes.
 251   SpecificBumpPtrAllocator<Node> BPA;
 252
 253   /// \brief Maps function->node for fast lookup.
 254   DenseMap<const Function *, Node *> NodeMap;
 255
 256   /// \brief The entry nodes to the graph.
 257   ///
 258   /// These nodes are reachable through "external" means. Put another way, they
 259   /// escape at the module scope.
 260   NodeVectorT EntryNodes;
 261
 262   /// \brief Set of the entry nodes to the graph.
 263   SmallPtrSet<Function *, 4> EntryNodeSet;
 264
 265   /// \brief Helper to insert a new function, with an already looked-up entry in
 266   /// the NodeMap.
 267   Node *insertInto(Function &F, Node *&MappedN);
 268
 269   /// \brief Helper to copy a node from another graph into this one.
 270   Node *copyInto(const Node &OtherN);
 271 };
 272
 273 // Provide GraphTraits specializations for call graphs.
 274 template <> struct GraphTraits<LazyCallGraph::Node *> {
 275   typedef LazyCallGraph::Node NodeType;
 276   typedef LazyCallGraph::iterator ChildIteratorType;
 277
 278   static NodeType *getEntryNode(NodeType *N) { return N; }
 279   static ChildIteratorType child_begin(NodeType *N) { return N->begin(); }
 280   static ChildIteratorType child_end(NodeType *N) { return N->end(); }
 281 };
 282 template <> struct GraphTraits<LazyCallGraph *> {
 283   typedef LazyCallGraph::Node NodeType;
 284   typedef LazyCallGraph::iterator ChildIteratorType;
 285
 286   static NodeType *getEntryNode(NodeType *N) { return N; }
 287   static ChildIteratorType child_begin(NodeType *N) { return N->begin(); }
 288   static ChildIteratorType child_end(NodeType *N) { return N->end(); }
 289 };
 290
 291 /// \brief An analysis pass which computes the call graph for a module.
 292 class LazyCallGraphAnalysis {
 293 public:
 294   /// \brief Inform generic clients of the result type.
 295   typedef LazyCallGraph Result;
 296
 297   static void *ID() { return (void *)&PassID; }
 298
 299   /// \brief Compute the \c LazyCallGraph for a the module \c M.
 300   ///
 301   /// This just builds the set of entry points to the call graph. The rest is
 302   /// built lazily as it is walked.
 303   LazyCallGraph run(Module *M) { return LazyCallGraph(*M); }
 304
 305 private:
 306   static char PassID;
 307 };
 308
 309 /// \brief A pass which prints the call graph to a \c raw_ostream.
 310 ///
 311 /// This is primarily useful for testing the analysis.
 312 class LazyCallGraphPrinterPass {
 313   raw_ostream &OS;
 314
 315 public:
 316   explicit LazyCallGraphPrinterPass(raw_ostream &OS);
 317
 318   PreservedAnalyses run(Module *M, ModuleAnalysisManager *AM);
 319
 320   static StringRef name() { return "LazyCallGraphPrinterPass"; }
 321 };
 322
 323 }
 324
 325 #endif