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