LazyCallGraph.h revision 36b56886974eae4f9c5ebc96befd3e7bfe5de338
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 49namespace llvm { 50class ModuleAnalysisManager; 51class PreservedAnalyses; 52class 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. 100class LazyCallGraph { 101public: 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 218private: 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. 252class 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 270public: 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. 286template <> 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}; 294template <> 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. 304class LazyCallGraphAnalysis { 305public: 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 317private: 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. 324class LazyCallGraphPrinterPass { 325 raw_ostream &OS; 326 327public: 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 338