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