1 //===- LazyCallGraph.h - Analysis of a Module's call graph ------*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 /// \file 9 /// 10 /// Implements a lazy call graph analysis and related passes for the new pass 11 /// manager. 12 /// 13 /// NB: This is *not* a traditional call graph! It is a graph which models both 14 /// the current calls and potential calls. As a consequence there are many 15 /// edges in this call graph that do not correspond to a 'call' or 'invoke' 16 /// instruction. 17 /// 18 /// The primary use cases of this graph analysis is to facilitate iterating 19 /// across the functions of a module in ways that ensure all callees are 20 /// visited prior to a caller (given any SCC constraints), or vice versa. As 21 /// such is it particularly well suited to organizing CGSCC optimizations such 22 /// as inlining, outlining, argument promotion, etc. That is its primary use 23 /// case and motivates the design. It may not be appropriate for other 24 /// purposes. The use graph of functions or some other conservative analysis of 25 /// call instructions may be interesting for optimizations and subsequent 26 /// analyses which don't work in the context of an overly specified 27 /// potential-call-edge graph. 28 /// 29 /// To understand the specific rules and nature of this call graph analysis, 30 /// see the documentation of the \c LazyCallGraph below. 31 /// 32 //===----------------------------------------------------------------------===// 33 34 #ifndef LLVM_ANALYSIS_LAZYCALLGRAPH_H 35 #define LLVM_ANALYSIS_LAZYCALLGRAPH_H 36 37 #include "llvm/ADT/ArrayRef.h" 38 #include "llvm/ADT/DenseMap.h" 39 #include "llvm/ADT/Optional.h" 40 #include "llvm/ADT/PointerIntPair.h" 41 #include "llvm/ADT/SetVector.h" 42 #include "llvm/ADT/SmallVector.h" 43 #include "llvm/ADT/StringRef.h" 44 #include "llvm/ADT/iterator.h" 45 #include "llvm/ADT/iterator_range.h" 46 #include "llvm/Analysis/TargetLibraryInfo.h" 47 #include "llvm/IR/PassManager.h" 48 #include "llvm/Support/Allocator.h" 49 #include "llvm/Support/raw_ostream.h" 50 #include <cassert> 51 #include <iterator> 52 #include <string> 53 #include <utility> 54 55 namespace llvm { 56 57 class Constant; 58 class Function; 59 template <class GraphType> struct GraphTraits; 60 class Module; 61 class TargetLibraryInfo; 62 class Value; 63 64 /// A lazily constructed view of the call graph of a module. 65 /// 66 /// With the edges of this graph, the motivating constraint that we are 67 /// attempting to maintain is that function-local optimization, CGSCC-local 68 /// optimizations, and optimizations transforming a pair of functions connected 69 /// by an edge in the graph, do not invalidate a bottom-up traversal of the SCC 70 /// DAG. That is, no optimizations will delete, remove, or add an edge such 71 /// that functions already visited in a bottom-up order of the SCC DAG are no 72 /// longer valid to have visited, or such that functions not yet visited in 73 /// a bottom-up order of the SCC DAG are not required to have already been 74 /// visited. 75 /// 76 /// Within this constraint, the desire is to minimize the merge points of the 77 /// SCC DAG. The greater the fanout of the SCC DAG and the fewer merge points 78 /// in the SCC DAG, the more independence there is in optimizing within it. 79 /// There is a strong desire to enable parallelization of optimizations over 80 /// the call graph, and both limited fanout and merge points will (artificially 81 /// in some cases) limit the scaling of such an effort. 82 /// 83 /// To this end, graph represents both direct and any potential resolution to 84 /// an indirect call edge. Another way to think about it is that it represents 85 /// both the direct call edges and any direct call edges that might be formed 86 /// through static optimizations. Specifically, it considers taking the address 87 /// of a function to be an edge in the call graph because this might be 88 /// forwarded to become a direct call by some subsequent function-local 89 /// optimization. The result is that the graph closely follows the use-def 90 /// edges for functions. Walking "up" the graph can be done by looking at all 91 /// of the uses of a function. 92 /// 93 /// The roots of the call graph are the external functions and functions 94 /// escaped into global variables. Those functions can be called from outside 95 /// of the module or via unknowable means in the IR -- we may not be able to 96 /// form even a potential call edge from a function body which may dynamically 97 /// load the function and call it. 98 /// 99 /// This analysis still requires updates to remain valid after optimizations 100 /// which could potentially change the set of potential callees. The 101 /// constraints it operates under only make the traversal order remain valid. 102 /// 103 /// The entire analysis must be re-computed if full interprocedural 104 /// optimizations run at any point. For example, globalopt completely 105 /// invalidates the information in this analysis. 106 /// 107 /// FIXME: This class is named LazyCallGraph in a lame attempt to distinguish 108 /// it from the existing CallGraph. At some point, it is expected that this 109 /// will be the only call graph and it will be renamed accordingly. 110 class LazyCallGraph { 111 public: 112 class Node; 113 class EdgeSequence; 114 class SCC; 115 class RefSCC; 116 117 /// A class used to represent edges in the call graph. 118 /// 119 /// The lazy call graph models both *call* edges and *reference* edges. Call 120 /// edges are much what you would expect, and exist when there is a 'call' or 121 /// 'invoke' instruction of some function. Reference edges are also tracked 122 /// along side these, and exist whenever any instruction (transitively 123 /// through its operands) references a function. All call edges are 124 /// inherently reference edges, and so the reference graph forms a superset 125 /// of the formal call graph. 126 /// 127 /// All of these forms of edges are fundamentally represented as outgoing 128 /// edges. The edges are stored in the source node and point at the target 129 /// node. This allows the edge structure itself to be a very compact data 130 /// structure: essentially a tagged pointer. 131 class Edge { 132 public: 133 /// The kind of edge in the graph. 134 enum Kind : bool { Ref = false, Call = true }; 135 136 Edge(); 137 explicit Edge(Node &N, Kind K); 138 139 /// Test whether the edge is null. 140 /// 141 /// This happens when an edge has been deleted. We leave the edge objects 142 /// around but clear them. 143 explicit operator bool() const; 144 145 /// Returns the \c Kind of the edge. 146 Kind getKind() const; 147 148 /// Test whether the edge represents a direct call to a function. 149 /// 150 /// This requires that the edge is not null. 151 bool isCall() const; 152 153 /// Get the call graph node referenced by this edge. 154 /// 155 /// This requires that the edge is not null. 156 Node &getNode() const; 157 158 /// Get the function referenced by this edge. 159 /// 160 /// This requires that the edge is not null. 161 Function &getFunction() const; 162 163 private: 164 friend class LazyCallGraph::EdgeSequence; 165 friend class LazyCallGraph::RefSCC; 166 167 PointerIntPair<Node *, 1, Kind> Value; 168 169 void setKind(Kind K) { Value.setInt(K); } 170 }; 171 172 /// The edge sequence object. 173 /// 174 /// This typically exists entirely within the node but is exposed as 175 /// a separate type because a node doesn't initially have edges. An explicit 176 /// population step is required to produce this sequence at first and it is 177 /// then cached in the node. It is also used to represent edges entering the 178 /// graph from outside the module to model the graph's roots. 179 /// 180 /// The sequence itself both iterable and indexable. The indexes remain 181 /// stable even as the sequence mutates (including removal). 182 class EdgeSequence { 183 friend class LazyCallGraph; 184 friend class LazyCallGraph::Node; 185 friend class LazyCallGraph::RefSCC; 186 187 using VectorT = SmallVector<Edge, 4>; 188 using VectorImplT = SmallVectorImpl<Edge>; 189 190 public: 191 /// An iterator used for the edges to both entry nodes and child nodes. 192 class iterator 193 : public iterator_adaptor_base<iterator, VectorImplT::iterator, 194 std::forward_iterator_tag> { 195 friend class LazyCallGraph; 196 friend class LazyCallGraph::Node; 197 198 VectorImplT::iterator E; 199 200 // Build the iterator for a specific position in the edge list. 201 iterator(VectorImplT::iterator BaseI, VectorImplT::iterator E) 202 : iterator_adaptor_base(BaseI), E(E) { 203 while (I != E && !*I) 204 ++I; 205 } 206 207 public: 208 iterator() = default; 209 210 using iterator_adaptor_base::operator++; 211 iterator &operator++() { 212 do { 213 ++I; 214 } while (I != E && !*I); 215 return *this; 216 } 217 }; 218 219 /// An iterator over specifically call edges. 220 /// 221 /// This has the same iteration properties as the \c iterator, but 222 /// restricts itself to edges which represent actual calls. 223 class call_iterator 224 : public iterator_adaptor_base<call_iterator, VectorImplT::iterator, 225 std::forward_iterator_tag> { 226 friend class LazyCallGraph; 227 friend class LazyCallGraph::Node; 228 229 VectorImplT::iterator E; 230 231 /// Advance the iterator to the next valid, call edge. 232 void advanceToNextEdge() { 233 while (I != E && (!*I || !I->isCall())) 234 ++I; 235 } 236 237 // Build the iterator for a specific position in the edge list. 238 call_iterator(VectorImplT::iterator BaseI, VectorImplT::iterator E) 239 : iterator_adaptor_base(BaseI), E(E) { 240 advanceToNextEdge(); 241 } 242 243 public: 244 call_iterator() = default; 245 246 using iterator_adaptor_base::operator++; 247 call_iterator &operator++() { 248 ++I; 249 advanceToNextEdge(); 250 return *this; 251 } 252 }; 253 254 iterator begin() { return iterator(Edges.begin(), Edges.end()); } 255 iterator end() { return iterator(Edges.end(), Edges.end()); } 256 257 Edge &operator[](Node &N) { 258 assert(EdgeIndexMap.find(&N) != EdgeIndexMap.end() && "No such edge!"); 259 auto &E = Edges[EdgeIndexMap.find(&N)->second]; 260 assert(E && "Dead or null edge!"); 261 return E; 262 } 263 264 Edge *lookup(Node &N) { 265 auto EI = EdgeIndexMap.find(&N); 266 if (EI == EdgeIndexMap.end()) 267 return nullptr; 268 auto &E = Edges[EI->second]; 269 return E ? &E : nullptr; 270 } 271 272 call_iterator call_begin() { 273 return call_iterator(Edges.begin(), Edges.end()); 274 } 275 call_iterator call_end() { return call_iterator(Edges.end(), Edges.end()); } 276 277 iterator_range<call_iterator> calls() { 278 return make_range(call_begin(), call_end()); 279 } 280 281 bool empty() { 282 for (auto &E : Edges) 283 if (E) 284 return false; 285 286 return true; 287 } 288 289 private: 290 VectorT Edges; 291 DenseMap<Node *, int> EdgeIndexMap; 292 293 EdgeSequence() = default; 294 295 /// Internal helper to insert an edge to a node. 296 void insertEdgeInternal(Node &ChildN, Edge::Kind EK); 297 298 /// Internal helper to change an edge kind. 299 void setEdgeKind(Node &ChildN, Edge::Kind EK); 300 301 /// Internal helper to remove the edge to the given function. 302 bool removeEdgeInternal(Node &ChildN); 303 }; 304 305 /// A node in the call graph. 306 /// 307 /// This represents a single node. Its primary roles are to cache the list of 308 /// callees, de-duplicate and provide fast testing of whether a function is a 309 /// callee, and facilitate iteration of child nodes in the graph. 310 /// 311 /// The node works much like an optional in order to lazily populate the 312 /// edges of each node. Until populated, there are no edges. Once populated, 313 /// you can access the edges by dereferencing the node or using the `->` 314 /// operator as if the node was an `Optional<EdgeSequence>`. 315 class Node { 316 friend class LazyCallGraph; 317 friend class LazyCallGraph::RefSCC; 318 319 public: 320 LazyCallGraph &getGraph() const { return *G; } 321 322 Function &getFunction() const { return *F; } 323 324 StringRef getName() const { return F->getName(); } 325 326 /// Equality is defined as address equality. 327 bool operator==(const Node &N) const { return this == &N; } 328 bool operator!=(const Node &N) const { return !operator==(N); } 329 330 /// Tests whether the node has been populated with edges. 331 bool isPopulated() const { return Edges.has_value(); } 332 333 /// Tests whether this is actually a dead node and no longer valid. 334 /// 335 /// Users rarely interact with nodes in this state and other methods are 336 /// invalid. This is used to model a node in an edge list where the 337 /// function has been completely removed. 338 bool isDead() const { 339 assert(!G == !F && 340 "Both graph and function pointers should be null or non-null."); 341 return !G; 342 } 343 344 // We allow accessing the edges by dereferencing or using the arrow 345 // operator, essentially wrapping the internal optional. 346 EdgeSequence &operator*() const { 347 // Rip const off because the node itself isn't changing here. 348 return const_cast<EdgeSequence &>(*Edges); 349 } 350 EdgeSequence *operator->() const { return &**this; } 351 352 /// Populate the edges of this node if necessary. 353 /// 354 /// The first time this is called it will populate the edges for this node 355 /// in the graph. It does this by scanning the underlying function, so once 356 /// this is done, any changes to that function must be explicitly reflected 357 /// in updates to the graph. 358 /// 359 /// \returns the populated \c EdgeSequence to simplify walking it. 360 /// 361 /// This will not update or re-scan anything if called repeatedly. Instead, 362 /// the edge sequence is cached and returned immediately on subsequent 363 /// calls. 364 EdgeSequence &populate() { 365 if (Edges) 366 return *Edges; 367 368 return populateSlow(); 369 } 370 371 private: 372 LazyCallGraph *G; 373 Function *F; 374 375 // We provide for the DFS numbering and Tarjan walk lowlink numbers to be 376 // stored directly within the node. These are both '-1' when nodes are part 377 // of an SCC (or RefSCC), or '0' when not yet reached in a DFS walk. 378 int DFSNumber = 0; 379 int LowLink = 0; 380 381 Optional<EdgeSequence> Edges; 382 383 /// Basic constructor implements the scanning of F into Edges and 384 /// EdgeIndexMap. 385 Node(LazyCallGraph &G, Function &F) : G(&G), F(&F) {} 386 387 /// Implementation of the scan when populating. 388 EdgeSequence &populateSlow(); 389 390 /// Internal helper to directly replace the function with a new one. 391 /// 392 /// This is used to facilitate transformations which need to replace the 393 /// formal Function object but directly move the body and users from one to 394 /// the other. 395 void replaceFunction(Function &NewF); 396 397 void clear() { Edges.reset(); } 398 399 /// Print the name of this node's function. 400 friend raw_ostream &operator<<(raw_ostream &OS, const Node &N) { 401 return OS << N.F->getName(); 402 } 403 404 /// Dump the name of this node's function to stderr. 405 void dump() const; 406 }; 407 408 /// An SCC of the call graph. 409 /// 410 /// This represents a Strongly Connected Component of the direct call graph 411 /// -- ignoring indirect calls and function references. It stores this as 412 /// a collection of call graph nodes. While the order of nodes in the SCC is 413 /// stable, it is not any particular order. 414 /// 415 /// The SCCs are nested within a \c RefSCC, see below for details about that 416 /// outer structure. SCCs do not support mutation of the call graph, that 417 /// must be done through the containing \c RefSCC in order to fully reason 418 /// about the ordering and connections of the graph. 419 class LLVM_EXTERNAL_VISIBILITY SCC { 420 friend class LazyCallGraph; 421 friend class LazyCallGraph::Node; 422 423 RefSCC *OuterRefSCC; 424 SmallVector<Node *, 1> Nodes; 425 426 template <typename NodeRangeT> 427 SCC(RefSCC &OuterRefSCC, NodeRangeT &&Nodes) 428 : OuterRefSCC(&OuterRefSCC), Nodes(std::forward<NodeRangeT>(Nodes)) {} 429 430 void clear() { 431 OuterRefSCC = nullptr; 432 Nodes.clear(); 433 } 434 435 /// Print a short description useful for debugging or logging. 436 /// 437 /// We print the function names in the SCC wrapped in '()'s and skipping 438 /// the middle functions if there are a large number. 439 // 440 // Note: this is defined inline to dodge issues with GCC's interpretation 441 // of enclosing namespaces for friend function declarations. 442 friend raw_ostream &operator<<(raw_ostream &OS, const SCC &C) { 443 OS << '('; 444 int i = 0; 445 for (LazyCallGraph::Node &N : C) { 446 if (i > 0) 447 OS << ", "; 448 // Elide the inner elements if there are too many. 449 if (i > 8) { 450 OS << "..., " << *C.Nodes.back(); 451 break; 452 } 453 OS << N; 454 ++i; 455 } 456 OS << ')'; 457 return OS; 458 } 459 460 /// Dump a short description of this SCC to stderr. 461 void dump() const; 462 463 #if !defined(NDEBUG) || defined(EXPENSIVE_CHECKS) 464 /// Verify invariants about the SCC. 465 /// 466 /// This will attempt to validate all of the basic invariants within an 467 /// SCC, but not that it is a strongly connected component per se. 468 /// Primarily useful while building and updating the graph to check that 469 /// basic properties are in place rather than having inexplicable crashes 470 /// later. 471 void verify(); 472 #endif 473 474 public: 475 using iterator = pointee_iterator<SmallVectorImpl<Node *>::const_iterator>; 476 477 iterator begin() const { return Nodes.begin(); } 478 iterator end() const { return Nodes.end(); } 479 480 int size() const { return Nodes.size(); } 481 482 RefSCC &getOuterRefSCC() const { return *OuterRefSCC; } 483 484 /// Test if this SCC is a parent of \a C. 485 /// 486 /// Note that this is linear in the number of edges departing the current 487 /// SCC. 488 bool isParentOf(const SCC &C) const; 489 490 /// Test if this SCC is an ancestor of \a C. 491 /// 492 /// Note that in the worst case this is linear in the number of edges 493 /// departing the current SCC and every SCC in the entire graph reachable 494 /// from this SCC. Thus this very well may walk every edge in the entire 495 /// call graph! Do not call this in a tight loop! 496 bool isAncestorOf(const SCC &C) const; 497 498 /// Test if this SCC is a child of \a C. 499 /// 500 /// See the comments for \c isParentOf for detailed notes about the 501 /// complexity of this routine. 502 bool isChildOf(const SCC &C) const { return C.isParentOf(*this); } 503 504 /// Test if this SCC is a descendant of \a C. 505 /// 506 /// See the comments for \c isParentOf for detailed notes about the 507 /// complexity of this routine. 508 bool isDescendantOf(const SCC &C) const { return C.isAncestorOf(*this); } 509 510 /// Provide a short name by printing this SCC to a std::string. 511 /// 512 /// This copes with the fact that we don't have a name per se for an SCC 513 /// while still making the use of this in debugging and logging useful. 514 std::string getName() const { 515 std::string Name; 516 raw_string_ostream OS(Name); 517 OS << *this; 518 OS.flush(); 519 return Name; 520 } 521 }; 522 523 /// A RefSCC of the call graph. 524 /// 525 /// This models a Strongly Connected Component of function reference edges in 526 /// the call graph. As opposed to actual SCCs, these can be used to scope 527 /// subgraphs of the module which are independent from other subgraphs of the 528 /// module because they do not reference it in any way. This is also the unit 529 /// where we do mutation of the graph in order to restrict mutations to those 530 /// which don't violate this independence. 531 /// 532 /// A RefSCC contains a DAG of actual SCCs. All the nodes within the RefSCC 533 /// are necessarily within some actual SCC that nests within it. Since 534 /// a direct call *is* a reference, there will always be at least one RefSCC 535 /// around any SCC. 536 class RefSCC { 537 friend class LazyCallGraph; 538 friend class LazyCallGraph::Node; 539 540 LazyCallGraph *G; 541 542 /// A postorder list of the inner SCCs. 543 SmallVector<SCC *, 4> SCCs; 544 545 /// A map from SCC to index in the postorder list. 546 SmallDenseMap<SCC *, int, 4> SCCIndices; 547 548 /// Fast-path constructor. RefSCCs should instead be constructed by calling 549 /// formRefSCCFast on the graph itself. 550 RefSCC(LazyCallGraph &G); 551 552 void clear() { 553 SCCs.clear(); 554 SCCIndices.clear(); 555 } 556 557 /// Print a short description useful for debugging or logging. 558 /// 559 /// We print the SCCs wrapped in '[]'s and skipping the middle SCCs if 560 /// there are a large number. 561 // 562 // Note: this is defined inline to dodge issues with GCC's interpretation 563 // of enclosing namespaces for friend function declarations. 564 friend raw_ostream &operator<<(raw_ostream &OS, const RefSCC &RC) { 565 OS << '['; 566 int i = 0; 567 for (LazyCallGraph::SCC &C : RC) { 568 if (i > 0) 569 OS << ", "; 570 // Elide the inner elements if there are too many. 571 if (i > 4) { 572 OS << "..., " << *RC.SCCs.back(); 573 break; 574 } 575 OS << C; 576 ++i; 577 } 578 OS << ']'; 579 return OS; 580 } 581 582 /// Dump a short description of this RefSCC to stderr. 583 void dump() const; 584 585 #if !defined(NDEBUG) || defined(EXPENSIVE_CHECKS) 586 /// Verify invariants about the RefSCC and all its SCCs. 587 /// 588 /// This will attempt to validate all of the invariants *within* the 589 /// RefSCC, but not that it is a strongly connected component of the larger 590 /// graph. This makes it useful even when partially through an update. 591 /// 592 /// Invariants checked: 593 /// - SCCs and their indices match. 594 /// - The SCCs list is in fact in post-order. 595 void verify(); 596 #endif 597 598 public: 599 using iterator = pointee_iterator<SmallVectorImpl<SCC *>::const_iterator>; 600 using range = iterator_range<iterator>; 601 using parent_iterator = 602 pointee_iterator<SmallPtrSetImpl<RefSCC *>::const_iterator>; 603 604 iterator begin() const { return SCCs.begin(); } 605 iterator end() const { return SCCs.end(); } 606 607 ssize_t size() const { return SCCs.size(); } 608 609 SCC &operator[](int Idx) { return *SCCs[Idx]; } 610 611 iterator find(SCC &C) const { 612 return SCCs.begin() + SCCIndices.find(&C)->second; 613 } 614 615 /// Test if this RefSCC is a parent of \a RC. 616 /// 617 /// CAUTION: This method walks every edge in the \c RefSCC, it can be very 618 /// expensive. 619 bool isParentOf(const RefSCC &RC) const; 620 621 /// Test if this RefSCC is an ancestor of \a RC. 622 /// 623 /// CAUTION: This method walks the directed graph of edges as far as 624 /// necessary to find a possible path to the argument. In the worst case 625 /// this may walk the entire graph and can be extremely expensive. 626 bool isAncestorOf(const RefSCC &RC) const; 627 628 /// Test if this RefSCC is a child of \a RC. 629 /// 630 /// CAUTION: This method walks every edge in the argument \c RefSCC, it can 631 /// be very expensive. 632 bool isChildOf(const RefSCC &RC) const { return RC.isParentOf(*this); } 633 634 /// Test if this RefSCC is a descendant of \a RC. 635 /// 636 /// CAUTION: This method walks the directed graph of edges as far as 637 /// necessary to find a possible path from the argument. In the worst case 638 /// this may walk the entire graph and can be extremely expensive. 639 bool isDescendantOf(const RefSCC &RC) const { 640 return RC.isAncestorOf(*this); 641 } 642 643 /// Provide a short name by printing this RefSCC to a std::string. 644 /// 645 /// This copes with the fact that we don't have a name per se for an RefSCC 646 /// while still making the use of this in debugging and logging useful. 647 std::string getName() const { 648 std::string Name; 649 raw_string_ostream OS(Name); 650 OS << *this; 651 OS.flush(); 652 return Name; 653 } 654 655 ///@{ 656 /// \name Mutation API 657 /// 658 /// These methods provide the core API for updating the call graph in the 659 /// presence of (potentially still in-flight) DFS-found RefSCCs and SCCs. 660 /// 661 /// Note that these methods sometimes have complex runtimes, so be careful 662 /// how you call them. 663 664 /// Make an existing internal ref edge into a call edge. 665 /// 666 /// This may form a larger cycle and thus collapse SCCs into TargetN's SCC. 667 /// If that happens, the optional callback \p MergedCB will be invoked (if 668 /// provided) on the SCCs being merged away prior to actually performing 669 /// the merge. Note that this will never include the target SCC as that 670 /// will be the SCC functions are merged into to resolve the cycle. Once 671 /// this function returns, these merged SCCs are not in a valid state but 672 /// the pointers will remain valid until destruction of the parent graph 673 /// instance for the purpose of clearing cached information. This function 674 /// also returns 'true' if a cycle was formed and some SCCs merged away as 675 /// a convenience. 676 /// 677 /// After this operation, both SourceN's SCC and TargetN's SCC may move 678 /// position within this RefSCC's postorder list. Any SCCs merged are 679 /// merged into the TargetN's SCC in order to preserve reachability analyses 680 /// which took place on that SCC. 681 bool switchInternalEdgeToCall( 682 Node &SourceN, Node &TargetN, 683 function_ref<void(ArrayRef<SCC *> MergedSCCs)> MergeCB = {}); 684 685 /// Make an existing internal call edge between separate SCCs into a ref 686 /// edge. 687 /// 688 /// If SourceN and TargetN in separate SCCs within this RefSCC, changing 689 /// the call edge between them to a ref edge is a trivial operation that 690 /// does not require any structural changes to the call graph. 691 void switchTrivialInternalEdgeToRef(Node &SourceN, Node &TargetN); 692 693 /// Make an existing internal call edge within a single SCC into a ref 694 /// edge. 695 /// 696 /// Since SourceN and TargetN are part of a single SCC, this SCC may be 697 /// split up due to breaking a cycle in the call edges that formed it. If 698 /// that happens, then this routine will insert new SCCs into the postorder 699 /// list *before* the SCC of TargetN (previously the SCC of both). This 700 /// preserves postorder as the TargetN can reach all of the other nodes by 701 /// definition of previously being in a single SCC formed by the cycle from 702 /// SourceN to TargetN. 703 /// 704 /// The newly added SCCs are added *immediately* and contiguously 705 /// prior to the TargetN SCC and return the range covering the new SCCs in 706 /// the RefSCC's postorder sequence. You can directly iterate the returned 707 /// range to observe all of the new SCCs in postorder. 708 /// 709 /// Note that if SourceN and TargetN are in separate SCCs, the simpler 710 /// routine `switchTrivialInternalEdgeToRef` should be used instead. 711 iterator_range<iterator> switchInternalEdgeToRef(Node &SourceN, 712 Node &TargetN); 713 714 /// Make an existing outgoing ref edge into a call edge. 715 /// 716 /// Note that this is trivial as there are no cyclic impacts and there 717 /// remains a reference edge. 718 void switchOutgoingEdgeToCall(Node &SourceN, Node &TargetN); 719 720 /// Make an existing outgoing call edge into a ref edge. 721 /// 722 /// This is trivial as there are no cyclic impacts and there remains 723 /// a reference edge. 724 void switchOutgoingEdgeToRef(Node &SourceN, Node &TargetN); 725 726 /// Insert a ref edge from one node in this RefSCC to another in this 727 /// RefSCC. 728 /// 729 /// This is always a trivial operation as it doesn't change any part of the 730 /// graph structure besides connecting the two nodes. 731 /// 732 /// Note that we don't support directly inserting internal *call* edges 733 /// because that could change the graph structure and requires returning 734 /// information about what became invalid. As a consequence, the pattern 735 /// should be to first insert the necessary ref edge, and then to switch it 736 /// to a call edge if needed and handle any invalidation that results. See 737 /// the \c switchInternalEdgeToCall routine for details. 738 void insertInternalRefEdge(Node &SourceN, Node &TargetN); 739 740 /// Insert an edge whose parent is in this RefSCC and child is in some 741 /// child RefSCC. 742 /// 743 /// There must be an existing path from the \p SourceN to the \p TargetN. 744 /// This operation is inexpensive and does not change the set of SCCs and 745 /// RefSCCs in the graph. 746 void insertOutgoingEdge(Node &SourceN, Node &TargetN, Edge::Kind EK); 747 748 /// Insert an edge whose source is in a descendant RefSCC and target is in 749 /// this RefSCC. 750 /// 751 /// There must be an existing path from the target to the source in this 752 /// case. 753 /// 754 /// NB! This is has the potential to be a very expensive function. It 755 /// inherently forms a cycle in the prior RefSCC DAG and we have to merge 756 /// RefSCCs to resolve that cycle. But finding all of the RefSCCs which 757 /// participate in the cycle can in the worst case require traversing every 758 /// RefSCC in the graph. Every attempt is made to avoid that, but passes 759 /// must still exercise caution calling this routine repeatedly. 760 /// 761 /// Also note that this can only insert ref edges. In order to insert 762 /// a call edge, first insert a ref edge and then switch it to a call edge. 763 /// These are intentionally kept as separate interfaces because each step 764 /// of the operation invalidates a different set of data structures. 765 /// 766 /// This returns all the RefSCCs which were merged into the this RefSCC 767 /// (the target's). This allows callers to invalidate any cached 768 /// information. 769 /// 770 /// FIXME: We could possibly optimize this quite a bit for cases where the 771 /// caller and callee are very nearby in the graph. See comments in the 772 /// implementation for details, but that use case might impact users. 773 SmallVector<RefSCC *, 1> insertIncomingRefEdge(Node &SourceN, 774 Node &TargetN); 775 776 /// Remove an edge whose source is in this RefSCC and target is *not*. 777 /// 778 /// This removes an inter-RefSCC edge. All inter-RefSCC edges originating 779 /// from this SCC have been fully explored by any in-flight DFS graph 780 /// formation, so this is always safe to call once you have the source 781 /// RefSCC. 782 /// 783 /// This operation does not change the cyclic structure of the graph and so 784 /// is very inexpensive. It may change the connectivity graph of the SCCs 785 /// though, so be careful calling this while iterating over them. 786 void removeOutgoingEdge(Node &SourceN, Node &TargetN); 787 788 /// Remove a list of ref edges which are entirely within this RefSCC. 789 /// 790 /// Both the \a SourceN and all of the \a TargetNs must be within this 791 /// RefSCC. Removing these edges may break cycles that form this RefSCC and 792 /// thus this operation may change the RefSCC graph significantly. In 793 /// particular, this operation will re-form new RefSCCs based on the 794 /// remaining connectivity of the graph. The following invariants are 795 /// guaranteed to hold after calling this method: 796 /// 797 /// 1) If a ref-cycle remains after removal, it leaves this RefSCC intact 798 /// and in the graph. No new RefSCCs are built. 799 /// 2) Otherwise, this RefSCC will be dead after this call and no longer in 800 /// the graph or the postorder traversal of the call graph. Any iterator 801 /// pointing at this RefSCC will become invalid. 802 /// 3) All newly formed RefSCCs will be returned and the order of the 803 /// RefSCCs returned will be a valid postorder traversal of the new 804 /// RefSCCs. 805 /// 4) No RefSCC other than this RefSCC has its member set changed (this is 806 /// inherent in the definition of removing such an edge). 807 /// 808 /// These invariants are very important to ensure that we can build 809 /// optimization pipelines on top of the CGSCC pass manager which 810 /// intelligently update the RefSCC graph without invalidating other parts 811 /// of the RefSCC graph. 812 /// 813 /// Note that we provide no routine to remove a *call* edge. Instead, you 814 /// must first switch it to a ref edge using \c switchInternalEdgeToRef. 815 /// This split API is intentional as each of these two steps can invalidate 816 /// a different aspect of the graph structure and needs to have the 817 /// invalidation handled independently. 818 /// 819 /// The runtime complexity of this method is, in the worst case, O(V+E) 820 /// where V is the number of nodes in this RefSCC and E is the number of 821 /// edges leaving the nodes in this RefSCC. Note that E includes both edges 822 /// within this RefSCC and edges from this RefSCC to child RefSCCs. Some 823 /// effort has been made to minimize the overhead of common cases such as 824 /// self-edges and edge removals which result in a spanning tree with no 825 /// more cycles. 826 SmallVector<RefSCC *, 1> removeInternalRefEdge(Node &SourceN, 827 ArrayRef<Node *> TargetNs); 828 829 /// A convenience wrapper around the above to handle trivial cases of 830 /// inserting a new call edge. 831 /// 832 /// This is trivial whenever the target is in the same SCC as the source or 833 /// the edge is an outgoing edge to some descendant SCC. In these cases 834 /// there is no change to the cyclic structure of SCCs or RefSCCs. 835 /// 836 /// To further make calling this convenient, it also handles inserting 837 /// already existing edges. 838 void insertTrivialCallEdge(Node &SourceN, Node &TargetN); 839 840 /// A convenience wrapper around the above to handle trivial cases of 841 /// inserting a new ref edge. 842 /// 843 /// This is trivial whenever the target is in the same RefSCC as the source 844 /// or the edge is an outgoing edge to some descendant RefSCC. In these 845 /// cases there is no change to the cyclic structure of the RefSCCs. 846 /// 847 /// To further make calling this convenient, it also handles inserting 848 /// already existing edges. 849 void insertTrivialRefEdge(Node &SourceN, Node &TargetN); 850 851 /// Directly replace a node's function with a new function. 852 /// 853 /// This should be used when moving the body and users of a function to 854 /// a new formal function object but not otherwise changing the call graph 855 /// structure in any way. 856 /// 857 /// It requires that the old function in the provided node have zero uses 858 /// and the new function must have calls and references to it establishing 859 /// an equivalent graph. 860 void replaceNodeFunction(Node &N, Function &NewF); 861 862 ///@} 863 }; 864 865 /// A post-order depth-first RefSCC iterator over the call graph. 866 /// 867 /// This iterator walks the cached post-order sequence of RefSCCs. However, 868 /// it trades stability for flexibility. It is restricted to a forward 869 /// iterator but will survive mutations which insert new RefSCCs and continue 870 /// to point to the same RefSCC even if it moves in the post-order sequence. 871 class postorder_ref_scc_iterator 872 : public iterator_facade_base<postorder_ref_scc_iterator, 873 std::forward_iterator_tag, RefSCC> { 874 friend class LazyCallGraph; 875 friend class LazyCallGraph::Node; 876 877 /// Nonce type to select the constructor for the end iterator. 878 struct IsAtEndT {}; 879 880 LazyCallGraph *G; 881 RefSCC *RC = nullptr; 882 883 /// Build the begin iterator for a node. 884 postorder_ref_scc_iterator(LazyCallGraph &G) : G(&G), RC(getRC(G, 0)) { 885 incrementUntilNonEmptyRefSCC(); 886 } 887 888 /// Build the end iterator for a node. This is selected purely by overload. 889 postorder_ref_scc_iterator(LazyCallGraph &G, IsAtEndT /*Nonce*/) : G(&G) {} 890 891 /// Get the post-order RefSCC at the given index of the postorder walk, 892 /// populating it if necessary. 893 static RefSCC *getRC(LazyCallGraph &G, int Index) { 894 if (Index == (int)G.PostOrderRefSCCs.size()) 895 // We're at the end. 896 return nullptr; 897 898 return G.PostOrderRefSCCs[Index]; 899 } 900 901 // Keep incrementing until RC is non-empty (or null). 902 void incrementUntilNonEmptyRefSCC() { 903 while (RC && RC->size() == 0) 904 increment(); 905 } 906 907 void increment() { 908 assert(RC && "Cannot increment the end iterator!"); 909 RC = getRC(*G, G->RefSCCIndices.find(RC)->second + 1); 910 } 911 912 public: 913 bool operator==(const postorder_ref_scc_iterator &Arg) const { 914 return G == Arg.G && RC == Arg.RC; 915 } 916 917 reference operator*() const { return *RC; } 918 919 using iterator_facade_base::operator++; 920 postorder_ref_scc_iterator &operator++() { 921 increment(); 922 incrementUntilNonEmptyRefSCC(); 923 return *this; 924 } 925 }; 926 927 /// Construct a graph for the given module. 928 /// 929 /// This sets up the graph and computes all of the entry points of the graph. 930 /// No function definitions are scanned until their nodes in the graph are 931 /// requested during traversal. 932 LazyCallGraph(Module &M, 933 function_ref<TargetLibraryInfo &(Function &)> GetTLI); 934 935 LazyCallGraph(LazyCallGraph &&G); 936 LazyCallGraph &operator=(LazyCallGraph &&RHS); 937 938 bool invalidate(Module &, const PreservedAnalyses &PA, 939 ModuleAnalysisManager::Invalidator &); 940 941 EdgeSequence::iterator begin() { return EntryEdges.begin(); } 942 EdgeSequence::iterator end() { return EntryEdges.end(); } 943 944 void buildRefSCCs(); 945 946 postorder_ref_scc_iterator postorder_ref_scc_begin() { 947 if (!EntryEdges.empty()) 948 assert(!PostOrderRefSCCs.empty() && 949 "Must form RefSCCs before iterating them!"); 950 return postorder_ref_scc_iterator(*this); 951 } 952 postorder_ref_scc_iterator postorder_ref_scc_end() { 953 if (!EntryEdges.empty()) 954 assert(!PostOrderRefSCCs.empty() && 955 "Must form RefSCCs before iterating them!"); 956 return postorder_ref_scc_iterator(*this, 957 postorder_ref_scc_iterator::IsAtEndT()); 958 } 959 960 iterator_range<postorder_ref_scc_iterator> postorder_ref_sccs() { 961 return make_range(postorder_ref_scc_begin(), postorder_ref_scc_end()); 962 } 963 964 /// Lookup a function in the graph which has already been scanned and added. 965 Node *lookup(const Function &F) const { return NodeMap.lookup(&F); } 966 967 /// Lookup a function's SCC in the graph. 968 /// 969 /// \returns null if the function hasn't been assigned an SCC via the RefSCC 970 /// iterator walk. 971 SCC *lookupSCC(Node &N) const { return SCCMap.lookup(&N); } 972 973 /// Lookup a function's RefSCC in the graph. 974 /// 975 /// \returns null if the function hasn't been assigned a RefSCC via the 976 /// RefSCC iterator walk. 977 RefSCC *lookupRefSCC(Node &N) const { 978 if (SCC *C = lookupSCC(N)) 979 return &C->getOuterRefSCC(); 980 981 return nullptr; 982 } 983 984 /// Get a graph node for a given function, scanning it to populate the graph 985 /// data as necessary. 986 Node &get(Function &F) { 987 Node *&N = NodeMap[&F]; 988 if (N) 989 return *N; 990 991 return insertInto(F, N); 992 } 993 994 /// Get the sequence of known and defined library functions. 995 /// 996 /// These functions, because they are known to LLVM, can have calls 997 /// introduced out of thin air from arbitrary IR. 998 ArrayRef<Function *> getLibFunctions() const { 999 return LibFunctions.getArrayRef(); 1000 } 1001 1002 /// Test whether a function is a known and defined library function tracked by 1003 /// the call graph. 1004 /// 1005 /// Because these functions are known to LLVM they are specially modeled in 1006 /// the call graph and even when all IR-level references have been removed 1007 /// remain active and reachable. 1008 bool isLibFunction(Function &F) const { return LibFunctions.count(&F); } 1009 1010 ///@{ 1011 /// \name Pre-SCC Mutation API 1012 /// 1013 /// These methods are only valid to call prior to forming any SCCs for this 1014 /// call graph. They can be used to update the core node-graph during 1015 /// a node-based inorder traversal that precedes any SCC-based traversal. 1016 /// 1017 /// Once you begin manipulating a call graph's SCCs, most mutation of the 1018 /// graph must be performed via a RefSCC method. There are some exceptions 1019 /// below. 1020 1021 /// Update the call graph after inserting a new edge. 1022 void insertEdge(Node &SourceN, Node &TargetN, Edge::Kind EK); 1023 1024 /// Update the call graph after inserting a new edge. 1025 void insertEdge(Function &Source, Function &Target, Edge::Kind EK) { 1026 return insertEdge(get(Source), get(Target), EK); 1027 } 1028 1029 /// Update the call graph after deleting an edge. 1030 void removeEdge(Node &SourceN, Node &TargetN); 1031 1032 /// Update the call graph after deleting an edge. 1033 void removeEdge(Function &Source, Function &Target) { 1034 return removeEdge(get(Source), get(Target)); 1035 } 1036 1037 ///@} 1038 1039 ///@{ 1040 /// \name General Mutation API 1041 /// 1042 /// There are a very limited set of mutations allowed on the graph as a whole 1043 /// once SCCs have started to be formed. These routines have strict contracts 1044 /// but may be called at any point. 1045 1046 /// Remove a dead function from the call graph (typically to delete it). 1047 /// 1048 /// Note that the function must have an empty use list, and the call graph 1049 /// must be up-to-date prior to calling this. That means it is by itself in 1050 /// a maximal SCC which is by itself in a maximal RefSCC, etc. No structural 1051 /// changes result from calling this routine other than potentially removing 1052 /// entry points into the call graph. 1053 /// 1054 /// If SCC formation has begun, this function must not be part of the current 1055 /// DFS in order to call this safely. Typically, the function will have been 1056 /// fully visited by the DFS prior to calling this routine. 1057 void removeDeadFunction(Function &F); 1058 1059 /// Add a new function split/outlined from an existing function. 1060 /// 1061 /// The new function may only reference other functions that the original 1062 /// function did. 1063 /// 1064 /// The original function must reference (either directly or indirectly) the 1065 /// new function. 1066 /// 1067 /// The new function may also reference the original function. 1068 /// It may end up in a parent SCC in the case that the original function's 1069 /// edge to the new function is a ref edge, and the edge back is a call edge. 1070 void addSplitFunction(Function &OriginalFunction, Function &NewFunction); 1071 1072 /// Add new ref-recursive functions split/outlined from an existing function. 1073 /// 1074 /// The new functions may only reference other functions that the original 1075 /// function did. The new functions may reference (not call) the original 1076 /// function. 1077 /// 1078 /// The original function must reference (not call) all new functions. 1079 /// All new functions must reference (not call) each other. 1080 void addSplitRefRecursiveFunctions(Function &OriginalFunction, 1081 ArrayRef<Function *> NewFunctions); 1082 1083 ///@} 1084 1085 ///@{ 1086 /// \name Static helpers for code doing updates to the call graph. 1087 /// 1088 /// These helpers are used to implement parts of the call graph but are also 1089 /// useful to code doing updates or otherwise wanting to walk the IR in the 1090 /// same patterns as when we build the call graph. 1091 1092 /// Recursively visits the defined functions whose address is reachable from 1093 /// every constant in the \p Worklist. 1094 /// 1095 /// Doesn't recurse through any constants already in the \p Visited set, and 1096 /// updates that set with every constant visited. 1097 /// 1098 /// For each defined function, calls \p Callback with that function. 1099 static void visitReferences(SmallVectorImpl<Constant *> &Worklist, 1100 SmallPtrSetImpl<Constant *> &Visited, 1101 function_ref<void(Function &)> Callback); 1102 1103 ///@} 1104 1105 private: 1106 using node_stack_iterator = SmallVectorImpl<Node *>::reverse_iterator; 1107 using node_stack_range = iterator_range<node_stack_iterator>; 1108 1109 /// Allocator that holds all the call graph nodes. 1110 SpecificBumpPtrAllocator<Node> BPA; 1111 1112 /// Maps function->node for fast lookup. 1113 DenseMap<const Function *, Node *> NodeMap; 1114 1115 /// The entry edges into the graph. 1116 /// 1117 /// These edges are from "external" sources. Put another way, they 1118 /// escape at the module scope. 1119 EdgeSequence EntryEdges; 1120 1121 /// Allocator that holds all the call graph SCCs. 1122 SpecificBumpPtrAllocator<SCC> SCCBPA; 1123 1124 /// Maps Function -> SCC for fast lookup. 1125 DenseMap<Node *, SCC *> SCCMap; 1126 1127 /// Allocator that holds all the call graph RefSCCs. 1128 SpecificBumpPtrAllocator<RefSCC> RefSCCBPA; 1129 1130 /// The post-order sequence of RefSCCs. 1131 /// 1132 /// This list is lazily formed the first time we walk the graph. 1133 SmallVector<RefSCC *, 16> PostOrderRefSCCs; 1134 1135 /// A map from RefSCC to the index for it in the postorder sequence of 1136 /// RefSCCs. 1137 DenseMap<RefSCC *, int> RefSCCIndices; 1138 1139 /// Defined functions that are also known library functions which the 1140 /// optimizer can reason about and therefore might introduce calls to out of 1141 /// thin air. 1142 SmallSetVector<Function *, 4> LibFunctions; 1143 1144 /// Helper to insert a new function, with an already looked-up entry in 1145 /// the NodeMap. 1146 Node &insertInto(Function &F, Node *&MappedN); 1147 1148 /// Helper to initialize a new node created outside of creating SCCs and add 1149 /// it to the NodeMap if necessary. For example, useful when a function is 1150 /// split. 1151 Node &initNode(Function &F); 1152 1153 /// Helper to update pointers back to the graph object during moves. 1154 void updateGraphPtrs(); 1155 1156 /// Allocates an SCC and constructs it using the graph allocator. 1157 /// 1158 /// The arguments are forwarded to the constructor. 1159 template <typename... Ts> SCC *createSCC(Ts &&... Args) { 1160 return new (SCCBPA.Allocate()) SCC(std::forward<Ts>(Args)...); 1161 } 1162 1163 /// Allocates a RefSCC and constructs it using the graph allocator. 1164 /// 1165 /// The arguments are forwarded to the constructor. 1166 template <typename... Ts> RefSCC *createRefSCC(Ts &&... Args) { 1167 return new (RefSCCBPA.Allocate()) RefSCC(std::forward<Ts>(Args)...); 1168 } 1169 1170 /// Common logic for building SCCs from a sequence of roots. 1171 /// 1172 /// This is a very generic implementation of the depth-first walk and SCC 1173 /// formation algorithm. It uses a generic sequence of roots and generic 1174 /// callbacks for each step. This is designed to be used to implement both 1175 /// the RefSCC formation and SCC formation with shared logic. 1176 /// 1177 /// Currently this is a relatively naive implementation of Tarjan's DFS 1178 /// algorithm to form the SCCs. 1179 /// 1180 /// FIXME: We should consider newer variants such as Nuutila. 1181 template <typename RootsT, typename GetBeginT, typename GetEndT, 1182 typename GetNodeT, typename FormSCCCallbackT> 1183 static void buildGenericSCCs(RootsT &&Roots, GetBeginT &&GetBegin, 1184 GetEndT &&GetEnd, GetNodeT &&GetNode, 1185 FormSCCCallbackT &&FormSCC); 1186 1187 /// Build the SCCs for a RefSCC out of a list of nodes. 1188 void buildSCCs(RefSCC &RC, node_stack_range Nodes); 1189 1190 /// Get the index of a RefSCC within the postorder traversal. 1191 /// 1192 /// Requires that this RefSCC is a valid one in the (perhaps partial) 1193 /// postorder traversed part of the graph. 1194 int getRefSCCIndex(RefSCC &RC) { 1195 auto IndexIt = RefSCCIndices.find(&RC); 1196 assert(IndexIt != RefSCCIndices.end() && "RefSCC doesn't have an index!"); 1197 assert(PostOrderRefSCCs[IndexIt->second] == &RC && 1198 "Index does not point back at RC!"); 1199 return IndexIt->second; 1200 } 1201 }; 1202 1203 inline LazyCallGraph::Edge::Edge() = default; 1204 inline LazyCallGraph::Edge::Edge(Node &N, Kind K) : Value(&N, K) {} 1205 1206 inline LazyCallGraph::Edge::operator bool() const { 1207 return Value.getPointer() && !Value.getPointer()->isDead(); 1208 } 1209 1210 inline LazyCallGraph::Edge::Kind LazyCallGraph::Edge::getKind() const { 1211 assert(*this && "Queried a null edge!"); 1212 return Value.getInt(); 1213 } 1214 1215 inline bool LazyCallGraph::Edge::isCall() const { 1216 assert(*this && "Queried a null edge!"); 1217 return getKind() == Call; 1218 } 1219 1220 inline LazyCallGraph::Node &LazyCallGraph::Edge::getNode() const { 1221 assert(*this && "Queried a null edge!"); 1222 return *Value.getPointer(); 1223 } 1224 1225 inline Function &LazyCallGraph::Edge::getFunction() const { 1226 assert(*this && "Queried a null edge!"); 1227 return getNode().getFunction(); 1228 } 1229 1230 // Provide GraphTraits specializations for call graphs. 1231 template <> struct GraphTraits<LazyCallGraph::Node *> { 1232 using NodeRef = LazyCallGraph::Node *; 1233 using ChildIteratorType = LazyCallGraph::EdgeSequence::iterator; 1234 1235 static NodeRef getEntryNode(NodeRef N) { return N; } 1236 static ChildIteratorType child_begin(NodeRef N) { return (*N)->begin(); } 1237 static ChildIteratorType child_end(NodeRef N) { return (*N)->end(); } 1238 }; 1239 template <> struct GraphTraits<LazyCallGraph *> { 1240 using NodeRef = LazyCallGraph::Node *; 1241 using ChildIteratorType = LazyCallGraph::EdgeSequence::iterator; 1242 1243 static NodeRef getEntryNode(NodeRef N) { return N; } 1244 static ChildIteratorType child_begin(NodeRef N) { return (*N)->begin(); } 1245 static ChildIteratorType child_end(NodeRef N) { return (*N)->end(); } 1246 }; 1247 1248 /// An analysis pass which computes the call graph for a module. 1249 class LazyCallGraphAnalysis : public AnalysisInfoMixin<LazyCallGraphAnalysis> { 1250 friend AnalysisInfoMixin<LazyCallGraphAnalysis>; 1251 1252 static AnalysisKey Key; 1253 1254 public: 1255 /// Inform generic clients of the result type. 1256 using Result = LazyCallGraph; 1257 1258 /// Compute the \c LazyCallGraph for the module \c M. 1259 /// 1260 /// This just builds the set of entry points to the call graph. The rest is 1261 /// built lazily as it is walked. 1262 LazyCallGraph run(Module &M, ModuleAnalysisManager &AM) { 1263 FunctionAnalysisManager &FAM = 1264 AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager(); 1265 auto GetTLI = [&FAM](Function &F) -> TargetLibraryInfo & { 1266 return FAM.getResult<TargetLibraryAnalysis>(F); 1267 }; 1268 return LazyCallGraph(M, GetTLI); 1269 } 1270 }; 1271 1272 /// A pass which prints the call graph to a \c raw_ostream. 1273 /// 1274 /// This is primarily useful for testing the analysis. 1275 class LazyCallGraphPrinterPass 1276 : public PassInfoMixin<LazyCallGraphPrinterPass> { 1277 raw_ostream &OS; 1278 1279 public: 1280 explicit LazyCallGraphPrinterPass(raw_ostream &OS); 1281 1282 PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM); 1283 }; 1284 1285 /// A pass which prints the call graph as a DOT file to a \c raw_ostream. 1286 /// 1287 /// This is primarily useful for visualization purposes. 1288 class LazyCallGraphDOTPrinterPass 1289 : public PassInfoMixin<LazyCallGraphDOTPrinterPass> { 1290 raw_ostream &OS; 1291 1292 public: 1293 explicit LazyCallGraphDOTPrinterPass(raw_ostream &OS); 1294 1295 PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM); 1296 }; 1297 1298 } // end namespace llvm 1299 1300 #endif // LLVM_ANALYSIS_LAZYCALLGRAPH_H 1301