contrib/llvm/lib/Analysis/LazyCallGraph.cpp

   1 //===- LazyCallGraph.cpp - Analysis of a Module's call graph --------------===//
   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
  10 #include "llvm/Analysis/LazyCallGraph.h"
  11 #include "llvm/ADT/ScopeExit.h"
  12 #include "llvm/ADT/Sequence.h"
  13 #include "llvm/ADT/STLExtras.h"
  14 #include "llvm/ADT/ScopeExit.h"
  15 #include "llvm/IR/CallSite.h"
  16 #include "llvm/IR/InstVisitor.h"
  17 #include "llvm/IR/Instructions.h"
  18 #include "llvm/IR/PassManager.h"
  19 #include "llvm/Support/Debug.h"
  20 #include "llvm/Support/GraphWriter.h"
  21 #include <utility>
  22
  23 using namespace llvm;
  24
  25 #define DEBUG_TYPE "lcg"
  26
  27 void LazyCallGraph::EdgeSequence::insertEdgeInternal(Node &TargetN,
  28                                                      Edge::Kind EK) {
  29   EdgeIndexMap.insert({&TargetN, Edges.size()});
  30   Edges.emplace_back(TargetN, EK);
  31 }
  32
  33 void LazyCallGraph::EdgeSequence::setEdgeKind(Node &TargetN, Edge::Kind EK) {
  34   Edges[EdgeIndexMap.find(&TargetN)->second].setKind(EK);
  35 }
  36
  37 bool LazyCallGraph::EdgeSequence::removeEdgeInternal(Node &TargetN) {
  38   auto IndexMapI = EdgeIndexMap.find(&TargetN);
  39   if (IndexMapI == EdgeIndexMap.end())
  40     return false;
  41
  42   Edges[IndexMapI->second] = Edge();
  43   EdgeIndexMap.erase(IndexMapI);
  44   return true;
  45 }
  46
  47 static void addEdge(SmallVectorImpl<LazyCallGraph::Edge> &Edges,
  48                     DenseMap<LazyCallGraph::Node *, int> &EdgeIndexMap,
  49                     LazyCallGraph::Node &N, LazyCallGraph::Edge::Kind EK) {
  50   if (!EdgeIndexMap.insert({&N, Edges.size()}).second)
  51     return;
  52
  53   DEBUG(dbgs() << "    Added callable function: " << N.getName() << "\n");
  54   Edges.emplace_back(LazyCallGraph::Edge(N, EK));
  55 }
  56
  57 LazyCallGraph::EdgeSequence &LazyCallGraph::Node::populateSlow() {
  58   assert(!Edges && "Must not have already populated the edges for this node!");
  59
  60   DEBUG(dbgs() << "  Adding functions called by '" << getName()
  61                << "' to the graph.\n");
  62
  63   Edges = EdgeSequence();
  64
  65   SmallVector<Constant *, 16> Worklist;
  66   SmallPtrSet<Function *, 4> Callees;
  67   SmallPtrSet<Constant *, 16> Visited;
  68
  69   // Find all the potential call graph edges in this function. We track both
  70   // actual call edges and indirect references to functions. The direct calls
  71   // are trivially added, but to accumulate the latter we walk the instructions
  72   // and add every operand which is a constant to the worklist to process
  73   // afterward.
  74   //
  75   // Note that we consider *any* function with a definition to be a viable
  76   // edge. Even if the function's definition is subject to replacement by
  77   // some other module (say, a weak definition) there may still be
  78   // optimizations which essentially speculate based on the definition and
  79   // a way to check that the specific definition is in fact the one being
  80   // used. For example, this could be done by moving the weak definition to
  81   // a strong (internal) definition and making the weak definition be an
  82   // alias. Then a test of the address of the weak function against the new
  83   // strong definition's address would be an effective way to determine the
  84   // safety of optimizing a direct call edge.
  85   for (BasicBlock &BB : *F)
  86     for (Instruction &I : BB) {
  87       if (auto CS = CallSite(&I))
  88         if (Function *Callee = CS.getCalledFunction())
  89           if (!Callee->isDeclaration())
  90             if (Callees.insert(Callee).second) {
  91               Visited.insert(Callee);
  92               addEdge(Edges->Edges, Edges->EdgeIndexMap, G->get(*Callee),
  93                       LazyCallGraph::Edge::Call);
  94             }
  95
  96       for (Value *Op : I.operand_values())
  97         if (Constant *C = dyn_cast<Constant>(Op))
  98           if (Visited.insert(C).second)
  99             Worklist.push_back(C);
 100     }
 101
 102   // We've collected all the constant (and thus potentially function or
 103   // function containing) operands to all of the instructions in the function.
 104   // Process them (recursively) collecting every function found.
 105   visitReferences(Worklist, Visited, [&](Function &F) {
 106     addEdge(Edges->Edges, Edges->EdgeIndexMap, G->get(F),
 107             LazyCallGraph::Edge::Ref);
 108   });
 109
 110   return *Edges;
 111 }
 112
 113 void LazyCallGraph::Node::replaceFunction(Function &NewF) {
 114   assert(F != &NewF && "Must not replace a function with itself!");
 115   F = &NewF;
 116 }
 117
 118 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 119 LLVM_DUMP_METHOD void LazyCallGraph::Node::dump() const {
 120   dbgs() << *this << '\n';
 121 }
 122 #endif
 123
 124 LazyCallGraph::LazyCallGraph(Module &M) {
 125   DEBUG(dbgs() << "Building CG for module: " << M.getModuleIdentifier()
 126                << "\n");
 127   for (Function &F : M)
 128     if (!F.isDeclaration() && !F.hasLocalLinkage()) {
 129       DEBUG(dbgs() << "  Adding '" << F.getName()
 130                    << "' to entry set of the graph.\n");
 131       addEdge(EntryEdges.Edges, EntryEdges.EdgeIndexMap, get(F), Edge::Ref);
 132     }
 133
 134   // Now add entry nodes for functions reachable via initializers to globals.
 135   SmallVector<Constant *, 16> Worklist;
 136   SmallPtrSet<Constant *, 16> Visited;
 137   for (GlobalVariable &GV : M.globals())
 138     if (GV.hasInitializer())
 139       if (Visited.insert(GV.getInitializer()).second)
 140         Worklist.push_back(GV.getInitializer());
 141
 142   DEBUG(dbgs() << "  Adding functions referenced by global initializers to the "
 143                   "entry set.\n");
 144   visitReferences(Worklist, Visited, [&](Function &F) {
 145     addEdge(EntryEdges.Edges, EntryEdges.EdgeIndexMap, get(F),
 146             LazyCallGraph::Edge::Ref);
 147   });
 148 }
 149
 150 LazyCallGraph::LazyCallGraph(LazyCallGraph &&G)
 151     : BPA(std::move(G.BPA)), NodeMap(std::move(G.NodeMap)),
 152       EntryEdges(std::move(G.EntryEdges)), SCCBPA(std::move(G.SCCBPA)),
 153       SCCMap(std::move(G.SCCMap)), LeafRefSCCs(std::move(G.LeafRefSCCs)) {
 154   updateGraphPtrs();
 155 }
 156
 157 LazyCallGraph &LazyCallGraph::operator=(LazyCallGraph &&G) {
 158   BPA = std::move(G.BPA);
 159   NodeMap = std::move(G.NodeMap);
 160   EntryEdges = std::move(G.EntryEdges);
 161   SCCBPA = std::move(G.SCCBPA);
 162   SCCMap = std::move(G.SCCMap);
 163   LeafRefSCCs = std::move(G.LeafRefSCCs);
 164   updateGraphPtrs();
 165   return *this;
 166 }
 167
 168 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 169 LLVM_DUMP_METHOD void LazyCallGraph::SCC::dump() const {
 170   dbgs() << *this << '\n';
 171 }
 172 #endif
 173
 174 #ifndef NDEBUG
 175 void LazyCallGraph::SCC::verify() {
 176   assert(OuterRefSCC && "Can't have a null RefSCC!");
 177   assert(!Nodes.empty() && "Can't have an empty SCC!");
 178
 179   for (Node *N : Nodes) {
 180     assert(N && "Can't have a null node!");
 181     assert(OuterRefSCC->G->lookupSCC(*N) == this &&
 182            "Node does not map to this SCC!");
 183     assert(N->DFSNumber == -1 &&
 184            "Must set DFS numbers to -1 when adding a node to an SCC!");
 185     assert(N->LowLink == -1 &&
 186            "Must set low link to -1 when adding a node to an SCC!");
 187     for (Edge &E : **N)
 188       assert(E.getNode() && "Can't have an unpopulated node!");
 189   }
 190 }
 191 #endif
 192
 193 bool LazyCallGraph::SCC::isParentOf(const SCC &C) const {
 194   if (this == &C)
 195     return false;
 196
 197   for (Node &N : *this)
 198     for (Edge &E : N->calls())
 199       if (OuterRefSCC->G->lookupSCC(E.getNode()) == &C)
 200         return true;
 201
 202   // No edges found.
 203   return false;
 204 }
 205
 206 bool LazyCallGraph::SCC::isAncestorOf(const SCC &TargetC) const {
 207   if (this == &TargetC)
 208     return false;
 209
 210   LazyCallGraph &G = *OuterRefSCC->G;
 211
 212   // Start with this SCC.
 213   SmallPtrSet<const SCC *, 16> Visited = {this};
 214   SmallVector<const SCC *, 16> Worklist = {this};
 215
 216   // Walk down the graph until we run out of edges or find a path to TargetC.
 217   do {
 218     const SCC &C = *Worklist.pop_back_val();
 219     for (Node &N : C)
 220       for (Edge &E : N->calls()) {
 221         SCC *CalleeC = G.lookupSCC(E.getNode());
 222         if (!CalleeC)
 223           continue;
 224
 225         // If the callee's SCC is the TargetC, we're done.
 226         if (CalleeC == &TargetC)
 227           return true;
 228
 229         // If this is the first time we've reached this SCC, put it on the
 230         // worklist to recurse through.
 231         if (Visited.insert(CalleeC).second)
 232           Worklist.push_back(CalleeC);
 233       }
 234   } while (!Worklist.empty());
 235
 236   // No paths found.
 237   return false;
 238 }
 239
 240 LazyCallGraph::RefSCC::RefSCC(LazyCallGraph &G) : G(&G) {}
 241
 242 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 243 LLVM_DUMP_METHOD void LazyCallGraph::RefSCC::dump() const {
 244   dbgs() << *this << '\n';
 245 }
 246 #endif
 247
 248 #ifndef NDEBUG
 249 void LazyCallGraph::RefSCC::verify() {
 250   assert(G && "Can't have a null graph!");
 251   assert(!SCCs.empty() && "Can't have an empty SCC!");
 252
 253   // Verify basic properties of the SCCs.
 254   SmallPtrSet<SCC *, 4> SCCSet;
 255   for (SCC *C : SCCs) {
 256     assert(C && "Can't have a null SCC!");
 257     C->verify();
 258     assert(&C->getOuterRefSCC() == this &&
 259            "SCC doesn't think it is inside this RefSCC!");
 260     bool Inserted = SCCSet.insert(C).second;
 261     assert(Inserted && "Found a duplicate SCC!");
 262     auto IndexIt = SCCIndices.find(C);
 263     assert(IndexIt != SCCIndices.end() &&
 264            "Found an SCC that doesn't have an index!");
 265   }
 266
 267   // Check that our indices map correctly.
 268   for (auto &SCCIndexPair : SCCIndices) {
 269     SCC *C = SCCIndexPair.first;
 270     int i = SCCIndexPair.second;
 271     assert(C && "Can't have a null SCC in the indices!");
 272     assert(SCCSet.count(C) && "Found an index for an SCC not in the RefSCC!");
 273     assert(SCCs[i] == C && "Index doesn't point to SCC!");
 274   }
 275
 276   // Check that the SCCs are in fact in post-order.
 277   for (int i = 0, Size = SCCs.size(); i < Size; ++i) {
 278     SCC &SourceSCC = *SCCs[i];
 279     for (Node &N : SourceSCC)
 280       for (Edge &E : *N) {
 281         if (!E.isCall())
 282           continue;
 283         SCC &TargetSCC = *G->lookupSCC(E.getNode());
 284         if (&TargetSCC.getOuterRefSCC() == this) {
 285           assert(SCCIndices.find(&TargetSCC)->second <= i &&
 286                  "Edge between SCCs violates post-order relationship.");
 287           continue;
 288         }
 289         assert(TargetSCC.getOuterRefSCC().Parents.count(this) &&
 290                "Edge to a RefSCC missing us in its parent set.");
 291       }
 292   }
 293
 294   // Check that our parents are actually parents.
 295   for (RefSCC *ParentRC : Parents) {
 296     assert(ParentRC != this && "Cannot be our own parent!");
 297     auto HasConnectingEdge = [&] {
 298       for (SCC &C : *ParentRC)
 299         for (Node &N : C)
 300           for (Edge &E : *N)
 301             if (G->lookupRefSCC(E.getNode()) == this)
 302               return true;
 303       return false;
 304     };
 305     assert(HasConnectingEdge() && "No edge connects the parent to us!");
 306   }
 307 }
 308 #endif
 309
 310 bool LazyCallGraph::RefSCC::isDescendantOf(const RefSCC &C) const {
 311   // Walk up the parents of this SCC and verify that we eventually find C.
 312   SmallVector<const RefSCC *, 4> AncestorWorklist;
 313   AncestorWorklist.push_back(this);
 314   do {
 315     const RefSCC *AncestorC = AncestorWorklist.pop_back_val();
 316     if (AncestorC->isChildOf(C))
 317       return true;
 318     for (const RefSCC *ParentC : AncestorC->Parents)
 319       AncestorWorklist.push_back(ParentC);
 320   } while (!AncestorWorklist.empty());
 321
 322   return false;
 323 }
 324
 325 /// Generic helper that updates a postorder sequence of SCCs for a potentially
 326 /// cycle-introducing edge insertion.
 327 ///
 328 /// A postorder sequence of SCCs of a directed graph has one fundamental
 329 /// property: all deges in the DAG of SCCs point "up" the sequence. That is,
 330 /// all edges in the SCC DAG point to prior SCCs in the sequence.
 331 ///
 332 /// This routine both updates a postorder sequence and uses that sequence to
 333 /// compute the set of SCCs connected into a cycle. It should only be called to
 334 /// insert a "downward" edge which will require changing the sequence to
 335 /// restore it to a postorder.
 336 ///
 337 /// When inserting an edge from an earlier SCC to a later SCC in some postorder
 338 /// sequence, all of the SCCs which may be impacted are in the closed range of
 339 /// those two within the postorder sequence. The algorithm used here to restore
 340 /// the state is as follows:
 341 ///
 342 /// 1) Starting from the source SCC, construct a set of SCCs which reach the
 343 ///    source SCC consisting of just the source SCC. Then scan toward the
 344 ///    target SCC in postorder and for each SCC, if it has an edge to an SCC
 345 ///    in the set, add it to the set. Otherwise, the source SCC is not
 346 ///    a successor, move it in the postorder sequence to immediately before
 347 ///    the source SCC, shifting the source SCC and all SCCs in the set one
 348 ///    position toward the target SCC. Stop scanning after processing the
 349 ///    target SCC.
 350 /// 2) If the source SCC is now past the target SCC in the postorder sequence,
 351 ///    and thus the new edge will flow toward the start, we are done.
 352 /// 3) Otherwise, starting from the target SCC, walk all edges which reach an
 353 ///    SCC between the source and the target, and add them to the set of
 354 ///    connected SCCs, then recurse through them. Once a complete set of the
 355 ///    SCCs the target connects to is known, hoist the remaining SCCs between
 356 ///    the source and the target to be above the target. Note that there is no
 357 ///    need to process the source SCC, it is already known to connect.
 358 /// 4) At this point, all of the SCCs in the closed range between the source
 359 ///    SCC and the target SCC in the postorder sequence are connected,
 360 ///    including the target SCC and the source SCC. Inserting the edge from
 361 ///    the source SCC to the target SCC will form a cycle out of precisely
 362 ///    these SCCs. Thus we can merge all of the SCCs in this closed range into
 363 ///    a single SCC.
 364 ///
 365 /// This process has various important properties:
 366 /// - Only mutates the SCCs when adding the edge actually changes the SCC
 367 ///   structure.
 368 /// - Never mutates SCCs which are unaffected by the change.
 369 /// - Updates the postorder sequence to correctly satisfy the postorder
 370 ///   constraint after the edge is inserted.
 371 /// - Only reorders SCCs in the closed postorder sequence from the source to
 372 ///   the target, so easy to bound how much has changed even in the ordering.
 373 /// - Big-O is the number of edges in the closed postorder range of SCCs from
 374 ///   source to target.
 375 ///
 376 /// This helper routine, in addition to updating the postorder sequence itself
 377 /// will also update a map from SCCs to indices within that sequecne.
 378 ///
 379 /// The sequence and the map must operate on pointers to the SCC type.
 380 ///
 381 /// Two callbacks must be provided. The first computes the subset of SCCs in
 382 /// the postorder closed range from the source to the target which connect to
 383 /// the source SCC via some (transitive) set of edges. The second computes the
 384 /// subset of the same range which the target SCC connects to via some
 385 /// (transitive) set of edges. Both callbacks should populate the set argument
 386 /// provided.
 387 template <typename SCCT, typename PostorderSequenceT, typename SCCIndexMapT,
 388           typename ComputeSourceConnectedSetCallableT,
 389           typename ComputeTargetConnectedSetCallableT>
 390 static iterator_range<typename PostorderSequenceT::iterator>
 391 updatePostorderSequenceForEdgeInsertion(
 392     SCCT &SourceSCC, SCCT &TargetSCC, PostorderSequenceT &SCCs,
 393     SCCIndexMapT &SCCIndices,
 394     ComputeSourceConnectedSetCallableT ComputeSourceConnectedSet,
 395     ComputeTargetConnectedSetCallableT ComputeTargetConnectedSet) {
 396   int SourceIdx = SCCIndices[&SourceSCC];
 397   int TargetIdx = SCCIndices[&TargetSCC];
 398   assert(SourceIdx < TargetIdx && "Cannot have equal indices here!");
 399
 400   SmallPtrSet<SCCT *, 4> ConnectedSet;
 401
 402   // Compute the SCCs which (transitively) reach the source.
 403   ComputeSourceConnectedSet(ConnectedSet);
 404
 405   // Partition the SCCs in this part of the port-order sequence so only SCCs
 406   // connecting to the source remain between it and the target. This is
 407   // a benign partition as it preserves postorder.
 408   auto SourceI = std::stable_partition(
 409       SCCs.begin() + SourceIdx, SCCs.begin() + TargetIdx + 1,
 410       [&ConnectedSet](SCCT *C) { return !ConnectedSet.count(C); });
 411   for (int i = SourceIdx, e = TargetIdx + 1; i < e; ++i)
 412     SCCIndices.find(SCCs[i])->second = i;
 413
 414   // If the target doesn't connect to the source, then we've corrected the
 415   // post-order and there are no cycles formed.
 416   if (!ConnectedSet.count(&TargetSCC)) {
 417     assert(SourceI > (SCCs.begin() + SourceIdx) &&
 418            "Must have moved the source to fix the post-order.");
 419     assert(*std::prev(SourceI) == &TargetSCC &&
 420            "Last SCC to move should have bene the target.");
 421
 422     // Return an empty range at the target SCC indicating there is nothing to
 423     // merge.
 424     return make_range(std::prev(SourceI), std::prev(SourceI));
 425   }
 426
 427   assert(SCCs[TargetIdx] == &TargetSCC &&
 428          "Should not have moved target if connected!");
 429   SourceIdx = SourceI - SCCs.begin();
 430   assert(SCCs[SourceIdx] == &SourceSCC &&
 431          "Bad updated index computation for the source SCC!");
 432
 433
 434   // See whether there are any remaining intervening SCCs between the source
 435   // and target. If so we need to make sure they all are reachable form the
 436   // target.
 437   if (SourceIdx + 1 < TargetIdx) {
 438     ConnectedSet.clear();
 439     ComputeTargetConnectedSet(ConnectedSet);
 440
 441     // Partition SCCs so that only SCCs reached from the target remain between
 442     // the source and the target. This preserves postorder.
 443     auto TargetI = std::stable_partition(
 444         SCCs.begin() + SourceIdx + 1, SCCs.begin() + TargetIdx + 1,
 445         [&ConnectedSet](SCCT *C) { return ConnectedSet.count(C); });
 446     for (int i = SourceIdx + 1, e = TargetIdx + 1; i < e; ++i)
 447       SCCIndices.find(SCCs[i])->second = i;
 448     TargetIdx = std::prev(TargetI) - SCCs.begin();
 449     assert(SCCs[TargetIdx] == &TargetSCC &&
 450            "Should always end with the target!");
 451   }
 452
 453   // At this point, we know that connecting source to target forms a cycle
 454   // because target connects back to source, and we know that all of the SCCs
 455   // between the source and target in the postorder sequence participate in that
 456   // cycle.
 457   return make_range(SCCs.begin() + SourceIdx, SCCs.begin() + TargetIdx);
 458 }
 459
 460 SmallVector<LazyCallGraph::SCC *, 1>
 461 LazyCallGraph::RefSCC::switchInternalEdgeToCall(Node &SourceN, Node &TargetN) {
 462   assert(!(*SourceN)[TargetN].isCall() && "Must start with a ref edge!");
 463   SmallVector<SCC *, 1> DeletedSCCs;
 464
 465 #ifndef NDEBUG
 466   // In a debug build, verify the RefSCC is valid to start with and when this
 467   // routine finishes.
 468   verify();
 469   auto VerifyOnExit = make_scope_exit([&]() { verify(); });
 470 #endif
 471
 472   SCC &SourceSCC = *G->lookupSCC(SourceN);
 473   SCC &TargetSCC = *G->lookupSCC(TargetN);
 474
 475   // If the two nodes are already part of the same SCC, we're also done as
 476   // we've just added more connectivity.
 477   if (&SourceSCC == &TargetSCC) {
 478     SourceN->setEdgeKind(TargetN, Edge::Call);
 479     return DeletedSCCs;
 480   }
 481
 482   // At this point we leverage the postorder list of SCCs to detect when the
 483   // insertion of an edge changes the SCC structure in any way.
 484   //
 485   // First and foremost, we can eliminate the need for any changes when the
 486   // edge is toward the beginning of the postorder sequence because all edges
 487   // flow in that direction already. Thus adding a new one cannot form a cycle.
 488   int SourceIdx = SCCIndices[&SourceSCC];
 489   int TargetIdx = SCCIndices[&TargetSCC];
 490   if (TargetIdx < SourceIdx) {
 491     SourceN->setEdgeKind(TargetN, Edge::Call);
 492     return DeletedSCCs;
 493   }
 494
 495   // Compute the SCCs which (transitively) reach the source.
 496   auto ComputeSourceConnectedSet = [&](SmallPtrSetImpl<SCC *> &ConnectedSet) {
 497 #ifndef NDEBUG
 498     // Check that the RefSCC is still valid before computing this as the
 499     // results will be nonsensical of we've broken its invariants.
 500     verify();
 501 #endif
 502     ConnectedSet.insert(&SourceSCC);
 503     auto IsConnected = [&](SCC &C) {
 504       for (Node &N : C)
 505         for (Edge &E : N->calls())
 506           if (ConnectedSet.count(G->lookupSCC(E.getNode())))
 507             return true;
 508
 509       return false;
 510     };
 511
 512     for (SCC *C :
 513          make_range(SCCs.begin() + SourceIdx + 1, SCCs.begin() + TargetIdx + 1))
 514       if (IsConnected(*C))
 515         ConnectedSet.insert(C);
 516   };
 517
 518   // Use a normal worklist to find which SCCs the target connects to. We still
 519   // bound the search based on the range in the postorder list we care about,
 520   // but because this is forward connectivity we just "recurse" through the
 521   // edges.
 522   auto ComputeTargetConnectedSet = [&](SmallPtrSetImpl<SCC *> &ConnectedSet) {
 523 #ifndef NDEBUG
 524     // Check that the RefSCC is still valid before computing this as the
 525     // results will be nonsensical of we've broken its invariants.
 526     verify();
 527 #endif
 528     ConnectedSet.insert(&TargetSCC);
 529     SmallVector<SCC *, 4> Worklist;
 530     Worklist.push_back(&TargetSCC);
 531     do {
 532       SCC &C = *Worklist.pop_back_val();
 533       for (Node &N : C)
 534         for (Edge &E : *N) {
 535           if (!E.isCall())
 536             continue;
 537           SCC &EdgeC = *G->lookupSCC(E.getNode());
 538           if (&EdgeC.getOuterRefSCC() != this)
 539             // Not in this RefSCC...
 540             continue;
 541           if (SCCIndices.find(&EdgeC)->second <= SourceIdx)
 542             // Not in the postorder sequence between source and target.
 543             continue;
 544
 545           if (ConnectedSet.insert(&EdgeC).second)
 546             Worklist.push_back(&EdgeC);
 547         }
 548     } while (!Worklist.empty());
 549   };
 550
 551   // Use a generic helper to update the postorder sequence of SCCs and return
 552   // a range of any SCCs connected into a cycle by inserting this edge. This
 553   // routine will also take care of updating the indices into the postorder
 554   // sequence.
 555   auto MergeRange = updatePostorderSequenceForEdgeInsertion(
 556       SourceSCC, TargetSCC, SCCs, SCCIndices, ComputeSourceConnectedSet,
 557       ComputeTargetConnectedSet);
 558
 559   // If the merge range is empty, then adding the edge didn't actually form any
 560   // new cycles. We're done.
 561   if (MergeRange.begin() == MergeRange.end()) {
 562     // Now that the SCC structure is finalized, flip the kind to call.
 563     SourceN->setEdgeKind(TargetN, Edge::Call);
 564     return DeletedSCCs;
 565   }
 566
 567 #ifndef NDEBUG
 568   // Before merging, check that the RefSCC remains valid after all the
 569   // postorder updates.
 570   verify();
 571 #endif
 572
 573   // Otherwise we need to merge all of the SCCs in the cycle into a single
 574   // result SCC.
 575   //
 576   // NB: We merge into the target because all of these functions were already
 577   // reachable from the target, meaning any SCC-wide properties deduced about it
 578   // other than the set of functions within it will not have changed.
 579   for (SCC *C : MergeRange) {
 580     assert(C != &TargetSCC &&
 581            "We merge *into* the target and shouldn't process it here!");
 582     SCCIndices.erase(C);
 583     TargetSCC.Nodes.append(C->Nodes.begin(), C->Nodes.end());
 584     for (Node *N : C->Nodes)
 585       G->SCCMap[N] = &TargetSCC;
 586     C->clear();
 587     DeletedSCCs.push_back(C);
 588   }
 589
 590   // Erase the merged SCCs from the list and update the indices of the
 591   // remaining SCCs.
 592   int IndexOffset = MergeRange.end() - MergeRange.begin();
 593   auto EraseEnd = SCCs.erase(MergeRange.begin(), MergeRange.end());
 594   for (SCC *C : make_range(EraseEnd, SCCs.end()))
 595     SCCIndices[C] -= IndexOffset;
 596
 597   // Now that the SCC structure is finalized, flip the kind to call.
 598   SourceN->setEdgeKind(TargetN, Edge::Call);
 599
 600   // And we're done!
 601   return DeletedSCCs;
 602 }
 603
 604 void LazyCallGraph::RefSCC::switchTrivialInternalEdgeToRef(Node &SourceN,
 605                                                            Node &TargetN) {
 606   assert((*SourceN)[TargetN].isCall() && "Must start with a call edge!");
 607
 608 #ifndef NDEBUG
 609   // In a debug build, verify the RefSCC is valid to start with and when this
 610   // routine finishes.
 611   verify();
 612   auto VerifyOnExit = make_scope_exit([&]() { verify(); });
 613 #endif
 614
 615   assert(G->lookupRefSCC(SourceN) == this &&
 616          "Source must be in this RefSCC.");
 617   assert(G->lookupRefSCC(TargetN) == this &&
 618          "Target must be in this RefSCC.");
 619   assert(G->lookupSCC(SourceN) != G->lookupSCC(TargetN) &&
 620          "Source and Target must be in separate SCCs for this to be trivial!");
 621
 622   // Set the edge kind.
 623   SourceN->setEdgeKind(TargetN, Edge::Ref);
 624 }
 625
 626 iterator_range<LazyCallGraph::RefSCC::iterator>
 627 LazyCallGraph::RefSCC::switchInternalEdgeToRef(Node &SourceN, Node &TargetN) {
 628   assert((*SourceN)[TargetN].isCall() && "Must start with a call edge!");
 629
 630 #ifndef NDEBUG
 631   // In a debug build, verify the RefSCC is valid to start with and when this
 632   // routine finishes.
 633   verify();
 634   auto VerifyOnExit = make_scope_exit([&]() { verify(); });
 635 #endif
 636
 637   assert(G->lookupRefSCC(SourceN) == this &&
 638          "Source must be in this RefSCC.");
 639   assert(G->lookupRefSCC(TargetN) == this &&
 640          "Target must be in this RefSCC.");
 641
 642   SCC &TargetSCC = *G->lookupSCC(TargetN);
 643   assert(G->lookupSCC(SourceN) == &TargetSCC && "Source and Target must be in "
 644                                                 "the same SCC to require the "
 645                                                 "full CG update.");
 646
 647   // Set the edge kind.
 648   SourceN->setEdgeKind(TargetN, Edge::Ref);
 649
 650   // Otherwise we are removing a call edge from a single SCC. This may break
 651   // the cycle. In order to compute the new set of SCCs, we need to do a small
 652   // DFS over the nodes within the SCC to form any sub-cycles that remain as
 653   // distinct SCCs and compute a postorder over the resulting SCCs.
 654   //
 655   // However, we specially handle the target node. The target node is known to
 656   // reach all other nodes in the original SCC by definition. This means that
 657   // we want the old SCC to be replaced with an SCC contaning that node as it
 658   // will be the root of whatever SCC DAG results from the DFS. Assumptions
 659   // about an SCC such as the set of functions called will continue to hold,
 660   // etc.
 661
 662   SCC &OldSCC = TargetSCC;
 663   SmallVector<std::pair<Node *, EdgeSequence::call_iterator>, 16> DFSStack;
 664   SmallVector<Node *, 16> PendingSCCStack;
 665   SmallVector<SCC *, 4> NewSCCs;
 666
 667   // Prepare the nodes for a fresh DFS.
 668   SmallVector<Node *, 16> Worklist;
 669   Worklist.swap(OldSCC.Nodes);
 670   for (Node *N : Worklist) {
 671     N->DFSNumber = N->LowLink = 0;
 672     G->SCCMap.erase(N);
 673   }
 674
 675   // Force the target node to be in the old SCC. This also enables us to take
 676   // a very significant short-cut in the standard Tarjan walk to re-form SCCs
 677   // below: whenever we build an edge that reaches the target node, we know
 678   // that the target node eventually connects back to all other nodes in our
 679   // walk. As a consequence, we can detect and handle participants in that
 680   // cycle without walking all the edges that form this connection, and instead
 681   // by relying on the fundamental guarantee coming into this operation (all
 682   // nodes are reachable from the target due to previously forming an SCC).
 683   TargetN.DFSNumber = TargetN.LowLink = -1;
 684   OldSCC.Nodes.push_back(&TargetN);
 685   G->SCCMap[&TargetN] = &OldSCC;
 686
 687   // Scan down the stack and DFS across the call edges.
 688   for (Node *RootN : Worklist) {
 689     assert(DFSStack.empty() &&
 690            "Cannot begin a new root with a non-empty DFS stack!");
 691     assert(PendingSCCStack.empty() &&
 692            "Cannot begin a new root with pending nodes for an SCC!");
 693
 694     // Skip any nodes we've already reached in the DFS.
 695     if (RootN->DFSNumber != 0) {
 696       assert(RootN->DFSNumber == -1 &&
 697              "Shouldn't have any mid-DFS root nodes!");
 698       continue;
 699     }
 700
 701     RootN->DFSNumber = RootN->LowLink = 1;
 702     int NextDFSNumber = 2;
 703
 704     DFSStack.push_back({RootN, (*RootN)->call_begin()});
 705     do {
 706       Node *N;
 707       EdgeSequence::call_iterator I;
 708       std::tie(N, I) = DFSStack.pop_back_val();
 709       auto E = (*N)->call_end();
 710       while (I != E) {
 711         Node &ChildN = I->getNode();
 712         if (ChildN.DFSNumber == 0) {
 713           // We haven't yet visited this child, so descend, pushing the current
 714           // node onto the stack.
 715           DFSStack.push_back({N, I});
 716
 717           assert(!G->SCCMap.count(&ChildN) &&
 718                  "Found a node with 0 DFS number but already in an SCC!");
 719           ChildN.DFSNumber = ChildN.LowLink = NextDFSNumber++;
 720           N = &ChildN;
 721           I = (*N)->call_begin();
 722           E = (*N)->call_end();
 723           continue;
 724         }
 725
 726         // Check for the child already being part of some component.
 727         if (ChildN.DFSNumber == -1) {
 728           if (G->lookupSCC(ChildN) == &OldSCC) {
 729             // If the child is part of the old SCC, we know that it can reach
 730             // every other node, so we have formed a cycle. Pull the entire DFS
 731             // and pending stacks into it. See the comment above about setting
 732             // up the old SCC for why we do this.
 733             int OldSize = OldSCC.size();
 734             OldSCC.Nodes.push_back(N);
 735             OldSCC.Nodes.append(PendingSCCStack.begin(), PendingSCCStack.end());
 736             PendingSCCStack.clear();
 737             while (!DFSStack.empty())
 738               OldSCC.Nodes.push_back(DFSStack.pop_back_val().first);
 739             for (Node &N : make_range(OldSCC.begin() + OldSize, OldSCC.end())) {
 740               N.DFSNumber = N.LowLink = -1;
 741               G->SCCMap[&N] = &OldSCC;
 742             }
 743             N = nullptr;
 744             break;
 745           }
 746
 747           // If the child has already been added to some child component, it
 748           // couldn't impact the low-link of this parent because it isn't
 749           // connected, and thus its low-link isn't relevant so skip it.
 750           ++I;
 751           continue;
 752         }
 753
 754         // Track the lowest linked child as the lowest link for this node.
 755         assert(ChildN.LowLink > 0 && "Must have a positive low-link number!");
 756         if (ChildN.LowLink < N->LowLink)
 757           N->LowLink = ChildN.LowLink;
 758
 759         // Move to the next edge.
 760         ++I;
 761       }
 762       if (!N)
 763         // Cleared the DFS early, start another round.
 764         break;
 765
 766       // We've finished processing N and its descendents, put it on our pending
 767       // SCC stack to eventually get merged into an SCC of nodes.
 768       PendingSCCStack.push_back(N);
 769
 770       // If this node is linked to some lower entry, continue walking up the
 771       // stack.
 772       if (N->LowLink != N->DFSNumber)
 773         continue;
 774
 775       // Otherwise, we've completed an SCC. Append it to our post order list of
 776       // SCCs.
 777       int RootDFSNumber = N->DFSNumber;
 778       // Find the range of the node stack by walking down until we pass the
 779       // root DFS number.
 780       auto SCCNodes = make_range(
 781           PendingSCCStack.rbegin(),
 782           find_if(reverse(PendingSCCStack), [RootDFSNumber](const Node *N) {
 783             return N->DFSNumber < RootDFSNumber;
 784           }));
 785
 786       // Form a new SCC out of these nodes and then clear them off our pending
 787       // stack.
 788       NewSCCs.push_back(G->createSCC(*this, SCCNodes));
 789       for (Node &N : *NewSCCs.back()) {
 790         N.DFSNumber = N.LowLink = -1;
 791         G->SCCMap[&N] = NewSCCs.back();
 792       }
 793       PendingSCCStack.erase(SCCNodes.end().base(), PendingSCCStack.end());
 794     } while (!DFSStack.empty());
 795   }
 796
 797   // Insert the remaining SCCs before the old one. The old SCC can reach all
 798   // other SCCs we form because it contains the target node of the removed edge
 799   // of the old SCC. This means that we will have edges into all of the new
 800   // SCCs, which means the old one must come last for postorder.
 801   int OldIdx = SCCIndices[&OldSCC];
 802   SCCs.insert(SCCs.begin() + OldIdx, NewSCCs.begin(), NewSCCs.end());
 803
 804   // Update the mapping from SCC* to index to use the new SCC*s, and remove the
 805   // old SCC from the mapping.
 806   for (int Idx = OldIdx, Size = SCCs.size(); Idx < Size; ++Idx)
 807     SCCIndices[SCCs[Idx]] = Idx;
 808
 809   return make_range(SCCs.begin() + OldIdx,
 810                     SCCs.begin() + OldIdx + NewSCCs.size());
 811 }
 812
 813 void LazyCallGraph::RefSCC::switchOutgoingEdgeToCall(Node &SourceN,
 814                                                      Node &TargetN) {
 815   assert(!(*SourceN)[TargetN].isCall() && "Must start with a ref edge!");
 816
 817   assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC.");
 818   assert(G->lookupRefSCC(TargetN) != this &&
 819          "Target must not be in this RefSCC.");
 820 #ifdef EXPENSIVE_CHECKS
 821   assert(G->lookupRefSCC(TargetN)->isDescendantOf(*this) &&
 822          "Target must be a descendant of the Source.");
 823 #endif
 824
 825   // Edges between RefSCCs are the same regardless of call or ref, so we can
 826   // just flip the edge here.
 827   SourceN->setEdgeKind(TargetN, Edge::Call);
 828
 829 #ifndef NDEBUG
 830   // Check that the RefSCC is still valid.
 831   verify();
 832 #endif
 833 }
 834
 835 void LazyCallGraph::RefSCC::switchOutgoingEdgeToRef(Node &SourceN,
 836                                                     Node &TargetN) {
 837   assert((*SourceN)[TargetN].isCall() && "Must start with a call edge!");
 838
 839   assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC.");
 840   assert(G->lookupRefSCC(TargetN) != this &&
 841          "Target must not be in this RefSCC.");
 842 #ifdef EXPENSIVE_CHECKS
 843   assert(G->lookupRefSCC(TargetN)->isDescendantOf(*this) &&
 844          "Target must be a descendant of the Source.");
 845 #endif
 846
 847   // Edges between RefSCCs are the same regardless of call or ref, so we can
 848   // just flip the edge here.
 849   SourceN->setEdgeKind(TargetN, Edge::Ref);
 850
 851 #ifndef NDEBUG
 852   // Check that the RefSCC is still valid.
 853   verify();
 854 #endif
 855 }
 856
 857 void LazyCallGraph::RefSCC::insertInternalRefEdge(Node &SourceN,
 858                                                   Node &TargetN) {
 859   assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC.");
 860   assert(G->lookupRefSCC(TargetN) == this && "Target must be in this RefSCC.");
 861
 862   SourceN->insertEdgeInternal(TargetN, Edge::Ref);
 863
 864 #ifndef NDEBUG
 865   // Check that the RefSCC is still valid.
 866   verify();
 867 #endif
 868 }
 869
 870 void LazyCallGraph::RefSCC::insertOutgoingEdge(Node &SourceN, Node &TargetN,
 871                                                Edge::Kind EK) {
 872   // First insert it into the caller.
 873   SourceN->insertEdgeInternal(TargetN, EK);
 874
 875   assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC.");
 876
 877   RefSCC &TargetC = *G->lookupRefSCC(TargetN);
 878   assert(&TargetC != this && "Target must not be in this RefSCC.");
 879 #ifdef EXPENSIVE_CHECKS
 880   assert(TargetC.isDescendantOf(*this) &&
 881          "Target must be a descendant of the Source.");
 882 #endif
 883
 884   // The only change required is to add this SCC to the parent set of the
 885   // callee.
 886   TargetC.Parents.insert(this);
 887
 888 #ifndef NDEBUG
 889   // Check that the RefSCC is still valid.
 890   verify();
 891 #endif
 892 }
 893
 894 SmallVector<LazyCallGraph::RefSCC *, 1>
 895 LazyCallGraph::RefSCC::insertIncomingRefEdge(Node &SourceN, Node &TargetN) {
 896   assert(G->lookupRefSCC(TargetN) == this && "Target must be in this RefSCC.");
 897   RefSCC &SourceC = *G->lookupRefSCC(SourceN);
 898   assert(&SourceC != this && "Source must not be in this RefSCC.");
 899 #ifdef EXPENSIVE_CHECKS
 900   assert(SourceC.isDescendantOf(*this) &&
 901          "Source must be a descendant of the Target.");
 902 #endif
 903
 904   SmallVector<RefSCC *, 1> DeletedRefSCCs;
 905
 906 #ifndef NDEBUG
 907   // In a debug build, verify the RefSCC is valid to start with and when this
 908   // routine finishes.
 909   verify();
 910   auto VerifyOnExit = make_scope_exit([&]() { verify(); });
 911 #endif
 912
 913   int SourceIdx = G->RefSCCIndices[&SourceC];
 914   int TargetIdx = G->RefSCCIndices[this];
 915   assert(SourceIdx < TargetIdx &&
 916          "Postorder list doesn't see edge as incoming!");
 917
 918   // Compute the RefSCCs which (transitively) reach the source. We do this by
 919   // working backwards from the source using the parent set in each RefSCC,
 920   // skipping any RefSCCs that don't fall in the postorder range. This has the
 921   // advantage of walking the sparser parent edge (in high fan-out graphs) but
 922   // more importantly this removes examining all forward edges in all RefSCCs
 923   // within the postorder range which aren't in fact connected. Only connected
 924   // RefSCCs (and their edges) are visited here.
 925   auto ComputeSourceConnectedSet = [&](SmallPtrSetImpl<RefSCC *> &Set) {
 926     Set.insert(&SourceC);
 927     SmallVector<RefSCC *, 4> Worklist;
 928     Worklist.push_back(&SourceC);
 929     do {
 930       RefSCC &RC = *Worklist.pop_back_val();
 931       for (RefSCC &ParentRC : RC.parents()) {
 932         // Skip any RefSCCs outside the range of source to target in the
 933         // postorder sequence.
 934         int ParentIdx = G->getRefSCCIndex(ParentRC);
 935         assert(ParentIdx > SourceIdx && "Parent cannot precede source in postorder!");
 936         if (ParentIdx > TargetIdx)
 937           continue;
 938         if (Set.insert(&ParentRC).second)
 939           // First edge connecting to this parent, add it to our worklist.
 940           Worklist.push_back(&ParentRC);
 941       }
 942     } while (!Worklist.empty());
 943   };
 944
 945   // Use a normal worklist to find which SCCs the target connects to. We still
 946   // bound the search based on the range in the postorder list we care about,
 947   // but because this is forward connectivity we just "recurse" through the
 948   // edges.
 949   auto ComputeTargetConnectedSet = [&](SmallPtrSetImpl<RefSCC *> &Set) {
 950     Set.insert(this);
 951     SmallVector<RefSCC *, 4> Worklist;
 952     Worklist.push_back(this);
 953     do {
 954       RefSCC &RC = *Worklist.pop_back_val();
 955       for (SCC &C : RC)
 956         for (Node &N : C)
 957           for (Edge &E : *N) {
 958             RefSCC &EdgeRC = *G->lookupRefSCC(E.getNode());
 959             if (G->getRefSCCIndex(EdgeRC) <= SourceIdx)
 960               // Not in the postorder sequence between source and target.
 961               continue;
 962
 963             if (Set.insert(&EdgeRC).second)
 964               Worklist.push_back(&EdgeRC);
 965           }
 966     } while (!Worklist.empty());
 967   };
 968
 969   // Use a generic helper to update the postorder sequence of RefSCCs and return
 970   // a range of any RefSCCs connected into a cycle by inserting this edge. This
 971   // routine will also take care of updating the indices into the postorder
 972   // sequence.
 973   iterator_range<SmallVectorImpl<RefSCC *>::iterator> MergeRange =
 974       updatePostorderSequenceForEdgeInsertion(
 975           SourceC, *this, G->PostOrderRefSCCs, G->RefSCCIndices,
 976           ComputeSourceConnectedSet, ComputeTargetConnectedSet);
 977
 978   // Build a set so we can do fast tests for whether a RefSCC will end up as
 979   // part of the merged RefSCC.
 980   SmallPtrSet<RefSCC *, 16> MergeSet(MergeRange.begin(), MergeRange.end());
 981
 982   // This RefSCC will always be part of that set, so just insert it here.
 983   MergeSet.insert(this);
 984
 985   // Now that we have identified all of the SCCs which need to be merged into
 986   // a connected set with the inserted edge, merge all of them into this SCC.
 987   SmallVector<SCC *, 16> MergedSCCs;
 988   int SCCIndex = 0;
 989   for (RefSCC *RC : MergeRange) {
 990     assert(RC != this && "We're merging into the target RefSCC, so it "
 991                          "shouldn't be in the range.");
 992
 993     // Merge the parents which aren't part of the merge into the our parents.
 994     for (RefSCC *ParentRC : RC->Parents)
 995       if (!MergeSet.count(ParentRC))
 996         Parents.insert(ParentRC);
 997     RC->Parents.clear();
 998
 999     // Walk the inner SCCs to update their up-pointer and walk all the edges to
1000     // update any parent sets.
1001     // FIXME: We should try to find a way to avoid this (rather expensive) edge
1002     // walk by updating the parent sets in some other manner.
1003     for (SCC &InnerC : *RC) {
1004       InnerC.OuterRefSCC = this;
1005       SCCIndices[&InnerC] = SCCIndex++;
1006       for (Node &N : InnerC) {
1007         G->SCCMap[&N] = &InnerC;
1008         for (Edge &E : *N) {
1009           RefSCC &ChildRC = *G->lookupRefSCC(E.getNode());
1010           if (MergeSet.count(&ChildRC))
1011             continue;
1012           ChildRC.Parents.erase(RC);
1013           ChildRC.Parents.insert(this);
1014         }
1015       }
1016     }
1017
1018     // Now merge in the SCCs. We can actually move here so try to reuse storage
1019     // the first time through.
1020     if (MergedSCCs.empty())
1021       MergedSCCs = std::move(RC->SCCs);
1022     else
1023       MergedSCCs.append(RC->SCCs.begin(), RC->SCCs.end());
1024     RC->SCCs.clear();
1025     DeletedRefSCCs.push_back(RC);
1026   }
1027
1028   // Append our original SCCs to the merged list and move it into place.
1029   for (SCC &InnerC : *this)
1030     SCCIndices[&InnerC] = SCCIndex++;
1031   MergedSCCs.append(SCCs.begin(), SCCs.end());
1032   SCCs = std::move(MergedSCCs);
1033
1034   // Remove the merged away RefSCCs from the post order sequence.
1035   for (RefSCC *RC : MergeRange)
1036     G->RefSCCIndices.erase(RC);
1037   int IndexOffset = MergeRange.end() - MergeRange.begin();
1038   auto EraseEnd =
1039       G->PostOrderRefSCCs.erase(MergeRange.begin(), MergeRange.end());
1040   for (RefSCC *RC : make_range(EraseEnd, G->PostOrderRefSCCs.end()))
1041     G->RefSCCIndices[RC] -= IndexOffset;
1042
1043   // At this point we have a merged RefSCC with a post-order SCCs list, just
1044   // connect the nodes to form the new edge.
1045   SourceN->insertEdgeInternal(TargetN, Edge::Ref);
1046
1047   // We return the list of SCCs which were merged so that callers can
1048   // invalidate any data they have associated with those SCCs. Note that these
1049   // SCCs are no longer in an interesting state (they are totally empty) but
1050   // the pointers will remain stable for the life of the graph itself.
1051   return DeletedRefSCCs;
1052 }
1053
1054 void LazyCallGraph::RefSCC::removeOutgoingEdge(Node &SourceN, Node &TargetN) {
1055   assert(G->lookupRefSCC(SourceN) == this &&
1056          "The source must be a member of this RefSCC.");
1057
1058   RefSCC &TargetRC = *G->lookupRefSCC(TargetN);
1059   assert(&TargetRC != this && "The target must not be a member of this RefSCC");
1060
1061   assert(!is_contained(G->LeafRefSCCs, this) &&
1062          "Cannot have a leaf RefSCC source.");
1063
1064 #ifndef NDEBUG
1065   // In a debug build, verify the RefSCC is valid to start with and when this
1066   // routine finishes.
1067   verify();
1068   auto VerifyOnExit = make_scope_exit([&]() { verify(); });
1069 #endif
1070
1071   // First remove it from the node.
1072   bool Removed = SourceN->removeEdgeInternal(TargetN);
1073   (void)Removed;
1074   assert(Removed && "Target not in the edge set for this caller?");
1075
1076   bool HasOtherEdgeToChildRC = false;
1077   bool HasOtherChildRC = false;
1078   for (SCC *InnerC : SCCs) {
1079     for (Node &N : *InnerC) {
1080       for (Edge &E : *N) {
1081         RefSCC &OtherChildRC = *G->lookupRefSCC(E.getNode());
1082         if (&OtherChildRC == &TargetRC) {
1083           HasOtherEdgeToChildRC = true;
1084           break;
1085         }
1086         if (&OtherChildRC != this)
1087           HasOtherChildRC = true;
1088       }
1089       if (HasOtherEdgeToChildRC)
1090         break;
1091     }
1092     if (HasOtherEdgeToChildRC)
1093       break;
1094   }
1095   // Because the SCCs form a DAG, deleting such an edge cannot change the set
1096   // of SCCs in the graph. However, it may cut an edge of the SCC DAG, making
1097   // the source SCC no longer connected to the target SCC. If so, we need to
1098   // update the target SCC's map of its parents.
1099   if (!HasOtherEdgeToChildRC) {
1100     bool Removed = TargetRC.Parents.erase(this);
1101     (void)Removed;
1102     assert(Removed &&
1103            "Did not find the source SCC in the target SCC's parent list!");
1104
1105     // It may orphan an SCC if it is the last edge reaching it, but that does
1106     // not violate any invariants of the graph.
1107     if (TargetRC.Parents.empty())
1108       DEBUG(dbgs() << "LCG: Update removing " << SourceN.getFunction().getName()
1109                    << " -> " << TargetN.getFunction().getName()
1110                    << " edge orphaned the callee's SCC!\n");
1111
1112     // It may make the Source SCC a leaf SCC.
1113     if (!HasOtherChildRC)
1114       G->LeafRefSCCs.push_back(this);
1115   }
1116 }
1117
1118 SmallVector<LazyCallGraph::RefSCC *, 1>
1119 LazyCallGraph::RefSCC::removeInternalRefEdge(Node &SourceN, Node &TargetN) {
1120   assert(!(*SourceN)[TargetN].isCall() &&
1121          "Cannot remove a call edge, it must first be made a ref edge");
1122
1123 #ifndef NDEBUG
1124   // In a debug build, verify the RefSCC is valid to start with and when this
1125   // routine finishes.
1126   verify();
1127   auto VerifyOnExit = make_scope_exit([&]() { verify(); });
1128 #endif
1129
1130   // First remove the actual edge.
1131   bool Removed = SourceN->removeEdgeInternal(TargetN);
1132   (void)Removed;
1133   assert(Removed && "Target not in the edge set for this caller?");
1134
1135   // We return a list of the resulting *new* RefSCCs in post-order.
1136   SmallVector<RefSCC *, 1> Result;
1137
1138   // Direct recursion doesn't impact the SCC graph at all.
1139   if (&SourceN == &TargetN)
1140     return Result;
1141
1142   // If this ref edge is within an SCC then there are sufficient other edges to
1143   // form a cycle without this edge so removing it is a no-op.
1144   SCC &SourceC = *G->lookupSCC(SourceN);
1145   SCC &TargetC = *G->lookupSCC(TargetN);
1146   if (&SourceC == &TargetC)
1147     return Result;
1148
1149   // We build somewhat synthetic new RefSCCs by providing a postorder mapping
1150   // for each inner SCC. We also store these associated with *nodes* rather
1151   // than SCCs because this saves a round-trip through the node->SCC map and in
1152   // the common case, SCCs are small. We will verify that we always give the
1153   // same number to every node in the SCC such that these are equivalent.
1154   const int RootPostOrderNumber = 0;
1155   int PostOrderNumber = RootPostOrderNumber + 1;
1156   SmallDenseMap<Node *, int> PostOrderMapping;
1157
1158   // Every node in the target SCC can already reach every node in this RefSCC
1159   // (by definition). It is the only node we know will stay inside this RefSCC.
1160   // Everything which transitively reaches Target will also remain in the
1161   // RefSCC. We handle this by pre-marking that the nodes in the target SCC map
1162   // back to the root post order number.
1163   //
1164   // This also enables us to take a very significant short-cut in the standard
1165   // Tarjan walk to re-form RefSCCs below: whenever we build an edge that
1166   // references the target node, we know that the target node eventually
1167   // references all other nodes in our walk. As a consequence, we can detect
1168   // and handle participants in that cycle without walking all the edges that
1169   // form the connections, and instead by relying on the fundamental guarantee
1170   // coming into this operation.
1171   for (Node &N : TargetC)
1172     PostOrderMapping[&N] = RootPostOrderNumber;
1173
1174   // Reset all the other nodes to prepare for a DFS over them, and add them to
1175   // our worklist.
1176   SmallVector<Node *, 8> Worklist;
1177   for (SCC *C : SCCs) {
1178     if (C == &TargetC)
1179       continue;
1180
1181     for (Node &N : *C)
1182       N.DFSNumber = N.LowLink = 0;
1183
1184     Worklist.append(C->Nodes.begin(), C->Nodes.end());
1185   }
1186
1187   auto MarkNodeForSCCNumber = [&PostOrderMapping](Node &N, int Number) {
1188     N.DFSNumber = N.LowLink = -1;
1189     PostOrderMapping[&N] = Number;
1190   };
1191
1192   SmallVector<std::pair<Node *, EdgeSequence::iterator>, 4> DFSStack;
1193   SmallVector<Node *, 4> PendingRefSCCStack;
1194   do {
1195     assert(DFSStack.empty() &&
1196            "Cannot begin a new root with a non-empty DFS stack!");
1197     assert(PendingRefSCCStack.empty() &&
1198            "Cannot begin a new root with pending nodes for an SCC!");
1199
1200     Node *RootN = Worklist.pop_back_val();
1201     // Skip any nodes we've already reached in the DFS.
1202     if (RootN->DFSNumber != 0) {
1203       assert(RootN->DFSNumber == -1 &&
1204              "Shouldn't have any mid-DFS root nodes!");
1205       continue;
1206     }
1207
1208     RootN->DFSNumber = RootN->LowLink = 1;
1209     int NextDFSNumber = 2;
1210
1211     DFSStack.push_back({RootN, (*RootN)->begin()});
1212     do {
1213       Node *N;
1214       EdgeSequence::iterator I;
1215       std::tie(N, I) = DFSStack.pop_back_val();
1216       auto E = (*N)->end();
1217
1218       assert(N->DFSNumber != 0 && "We should always assign a DFS number "
1219                                   "before processing a node.");
1220
1221       while (I != E) {
1222         Node &ChildN = I->getNode();
1223         if (ChildN.DFSNumber == 0) {
1224           // Mark that we should start at this child when next this node is the
1225           // top of the stack. We don't start at the next child to ensure this
1226           // child's lowlink is reflected.
1227           DFSStack.push_back({N, I});
1228
1229           // Continue, resetting to the child node.
1230           ChildN.LowLink = ChildN.DFSNumber = NextDFSNumber++;
1231           N = &ChildN;
1232           I = ChildN->begin();
1233           E = ChildN->end();
1234           continue;
1235         }
1236         if (ChildN.DFSNumber == -1) {
1237           // Check if this edge's target node connects to the deleted edge's
1238           // target node. If so, we know that every node connected will end up
1239           // in this RefSCC, so collapse the entire current stack into the root
1240           // slot in our SCC numbering. See above for the motivation of
1241           // optimizing the target connected nodes in this way.
1242           auto PostOrderI = PostOrderMapping.find(&ChildN);
1243           if (PostOrderI != PostOrderMapping.end() &&
1244               PostOrderI->second == RootPostOrderNumber) {
1245             MarkNodeForSCCNumber(*N, RootPostOrderNumber);
1246             while (!PendingRefSCCStack.empty())
1247               MarkNodeForSCCNumber(*PendingRefSCCStack.pop_back_val(),
1248                                    RootPostOrderNumber);
1249             while (!DFSStack.empty())
1250               MarkNodeForSCCNumber(*DFSStack.pop_back_val().first,
1251                                    RootPostOrderNumber);
1252             // Ensure we break all the way out of the enclosing loop.
1253             N = nullptr;
1254             break;
1255           }
1256
1257           // If this child isn't currently in this RefSCC, no need to process
1258           // it. However, we do need to remove this RefSCC from its RefSCC's
1259           // parent set.
1260           RefSCC &ChildRC = *G->lookupRefSCC(ChildN);
1261           ChildRC.Parents.erase(this);
1262           ++I;
1263           continue;
1264         }
1265
1266         // Track the lowest link of the children, if any are still in the stack.
1267         // Any child not on the stack will have a LowLink of -1.
1268         assert(ChildN.LowLink != 0 &&
1269                "Low-link must not be zero with a non-zero DFS number.");
1270         if (ChildN.LowLink >= 0 && ChildN.LowLink < N->LowLink)
1271           N->LowLink = ChildN.LowLink;
1272         ++I;
1273       }
1274       if (!N)
1275         // We short-circuited this node.
1276         break;
1277
1278       // We've finished processing N and its descendents, put it on our pending
1279       // stack to eventually get merged into a RefSCC.
1280       PendingRefSCCStack.push_back(N);
1281
1282       // If this node is linked to some lower entry, continue walking up the
1283       // stack.
1284       if (N->LowLink != N->DFSNumber) {
1285         assert(!DFSStack.empty() &&
1286                "We never found a viable root for a RefSCC to pop off!");
1287         continue;
1288       }
1289
1290       // Otherwise, form a new RefSCC from the top of the pending node stack.
1291       int RootDFSNumber = N->DFSNumber;
1292       // Find the range of the node stack by walking down until we pass the
1293       // root DFS number.
1294       auto RefSCCNodes = make_range(
1295           PendingRefSCCStack.rbegin(),
1296           find_if(reverse(PendingRefSCCStack), [RootDFSNumber](const Node *N) {
1297             return N->DFSNumber < RootDFSNumber;
1298           }));
1299
1300       // Mark the postorder number for these nodes and clear them off the
1301       // stack. We'll use the postorder number to pull them into RefSCCs at the
1302       // end. FIXME: Fuse with the loop above.
1303       int RefSCCNumber = PostOrderNumber++;
1304       for (Node *N : RefSCCNodes)
1305         MarkNodeForSCCNumber(*N, RefSCCNumber);
1306
1307       PendingRefSCCStack.erase(RefSCCNodes.end().base(),
1308                                PendingRefSCCStack.end());
1309     } while (!DFSStack.empty());
1310
1311     assert(DFSStack.empty() && "Didn't flush the entire DFS stack!");
1312     assert(PendingRefSCCStack.empty() && "Didn't flush all pending nodes!");
1313   } while (!Worklist.empty());
1314
1315   // We now have a post-order numbering for RefSCCs and a mapping from each
1316   // node in this RefSCC to its final RefSCC. We create each new RefSCC node
1317   // (re-using this RefSCC node for the root) and build a radix-sort style map
1318   // from postorder number to the RefSCC. We then append SCCs to each of these
1319   // RefSCCs in the order they occured in the original SCCs container.
1320   for (int i = 1; i < PostOrderNumber; ++i)
1321     Result.push_back(G->createRefSCC(*G));
1322
1323   // Insert the resulting postorder sequence into the global graph postorder
1324   // sequence before the current RefSCC in that sequence. The idea being that
1325   // this RefSCC is the target of the reference edge removed, and thus has
1326   // a direct or indirect edge to every other RefSCC formed and so must be at
1327   // the end of any postorder traversal.
1328   //
1329   // FIXME: It'd be nice to change the APIs so that we returned an iterator
1330   // range over the global postorder sequence and generally use that sequence
1331   // rather than building a separate result vector here.
1332   if (!Result.empty()) {
1333     int Idx = G->getRefSCCIndex(*this);
1334     G->PostOrderRefSCCs.insert(G->PostOrderRefSCCs.begin() + Idx,
1335                                Result.begin(), Result.end());
1336     for (int i : seq<int>(Idx, G->PostOrderRefSCCs.size()))
1337       G->RefSCCIndices[G->PostOrderRefSCCs[i]] = i;
1338     assert(G->PostOrderRefSCCs[G->getRefSCCIndex(*this)] == this &&
1339            "Failed to update this RefSCC's index after insertion!");
1340   }
1341
1342   for (SCC *C : SCCs) {
1343     auto PostOrderI = PostOrderMapping.find(&*C->begin());
1344     assert(PostOrderI != PostOrderMapping.end() &&
1345            "Cannot have missing mappings for nodes!");
1346     int SCCNumber = PostOrderI->second;
1347 #ifndef NDEBUG
1348     for (Node &N : *C)
1349       assert(PostOrderMapping.find(&N)->second == SCCNumber &&
1350              "Cannot have different numbers for nodes in the same SCC!");
1351 #endif
1352     if (SCCNumber == 0)
1353       // The root node is handled separately by removing the SCCs.
1354       continue;
1355
1356     RefSCC &RC = *Result[SCCNumber - 1];
1357     int SCCIndex = RC.SCCs.size();
1358     RC.SCCs.push_back(C);
1359     RC.SCCIndices[C] = SCCIndex;
1360     C->OuterRefSCC = &RC;
1361   }
1362
1363   // FIXME: We re-walk the edges in each RefSCC to establish whether it is
1364   // a leaf and connect it to the rest of the graph's parents lists. This is
1365   // really wasteful. We should instead do this during the DFS to avoid yet
1366   // another edge walk.
1367   for (RefSCC *RC : Result)
1368     G->connectRefSCC(*RC);
1369
1370   // Now erase all but the root's SCCs.
1371   SCCs.erase(remove_if(SCCs,
1372                        [&](SCC *C) {
1373                          return PostOrderMapping.lookup(&*C->begin()) !=
1374                                 RootPostOrderNumber;
1375                        }),
1376              SCCs.end());
1377   SCCIndices.clear();
1378   for (int i = 0, Size = SCCs.size(); i < Size; ++i)
1379     SCCIndices[SCCs[i]] = i;
1380
1381 #ifndef NDEBUG
1382   // Now we need to reconnect the current (root) SCC to the graph. We do this
1383   // manually because we can special case our leaf handling and detect errors.
1384   bool IsLeaf = true;
1385 #endif
1386   for (SCC *C : SCCs)
1387     for (Node &N : *C) {
1388       for (Edge &E : *N) {
1389         RefSCC &ChildRC = *G->lookupRefSCC(E.getNode());
1390         if (&ChildRC == this)
1391           continue;
1392         ChildRC.Parents.insert(this);
1393 #ifndef NDEBUG
1394         IsLeaf = false;
1395 #endif
1396       }
1397     }
1398 #ifndef NDEBUG
1399   if (!Result.empty())
1400     assert(!IsLeaf && "This SCC cannot be a leaf as we have split out new "
1401                       "SCCs by removing this edge.");
1402   if (none_of(G->LeafRefSCCs, [&](RefSCC *C) { return C == this; }))
1403     assert(!IsLeaf && "This SCC cannot be a leaf as it already had child "
1404                       "SCCs before we removed this edge.");
1405 #endif
1406   // And connect both this RefSCC and all the new ones to the correct parents.
1407   // The easiest way to do this is just to re-analyze the old parent set.
1408   SmallVector<RefSCC *, 4> OldParents(Parents.begin(), Parents.end());
1409   Parents.clear();
1410   for (RefSCC *ParentRC : OldParents)
1411     for (SCC &ParentC : *ParentRC)
1412       for (Node &ParentN : ParentC)
1413         for (Edge &E : *ParentN) {
1414           RefSCC &RC = *G->lookupRefSCC(E.getNode());
1415           if (&RC != ParentRC)
1416             RC.Parents.insert(ParentRC);
1417         }
1418
1419   // If this SCC stopped being a leaf through this edge removal, remove it from
1420   // the leaf SCC list. Note that this DTRT in the case where this was never
1421   // a leaf.
1422   // FIXME: As LeafRefSCCs could be very large, we might want to not walk the
1423   // entire list if this RefSCC wasn't a leaf before the edge removal.
1424   if (!Result.empty())
1425     G->LeafRefSCCs.erase(
1426         std::remove(G->LeafRefSCCs.begin(), G->LeafRefSCCs.end(), this),
1427         G->LeafRefSCCs.end());
1428
1429 #ifndef NDEBUG
1430   // Verify all of the new RefSCCs.
1431   for (RefSCC *RC : Result)
1432     RC->verify();
1433 #endif
1434
1435   // Return the new list of SCCs.
1436   return Result;
1437 }
1438
1439 void LazyCallGraph::RefSCC::handleTrivialEdgeInsertion(Node &SourceN,
1440                                                        Node &TargetN) {
1441   // The only trivial case that requires any graph updates is when we add new
1442   // ref edge and may connect different RefSCCs along that path. This is only
1443   // because of the parents set. Every other part of the graph remains constant
1444   // after this edge insertion.
1445   assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC.");
1446   RefSCC &TargetRC = *G->lookupRefSCC(TargetN);
1447   if (&TargetRC == this) {
1448
1449     return;
1450   }
1451
1452 #ifdef EXPENSIVE_CHECKS
1453   assert(TargetRC.isDescendantOf(*this) &&
1454          "Target must be a descendant of the Source.");
1455 #endif
1456   // The only change required is to add this RefSCC to the parent set of the
1457   // target. This is a set and so idempotent if the edge already existed.
1458   TargetRC.Parents.insert(this);
1459 }
1460
1461 void LazyCallGraph::RefSCC::insertTrivialCallEdge(Node &SourceN,
1462                                                   Node &TargetN) {
1463 #ifndef NDEBUG
1464   // Check that the RefSCC is still valid when we finish.
1465   auto ExitVerifier = make_scope_exit([this] { verify(); });
1466
1467 #ifdef EXPENSIVE_CHECKS
1468   // Check that we aren't breaking some invariants of the SCC graph. Note that
1469   // this is quadratic in the number of edges in the call graph!
1470   SCC &SourceC = *G->lookupSCC(SourceN);
1471   SCC &TargetC = *G->lookupSCC(TargetN);
1472   if (&SourceC != &TargetC)
1473     assert(SourceC.isAncestorOf(TargetC) &&
1474            "Call edge is not trivial in the SCC graph!");
1475 #endif // EXPENSIVE_CHECKS
1476 #endif // NDEBUG
1477
1478   // First insert it into the source or find the existing edge.
1479   auto InsertResult =
1480       SourceN->EdgeIndexMap.insert({&TargetN, SourceN->Edges.size()});
1481   if (!InsertResult.second) {
1482     // Already an edge, just update it.
1483     Edge &E = SourceN->Edges[InsertResult.first->second];
1484     if (E.isCall())
1485       return; // Nothing to do!
1486     E.setKind(Edge::Call);
1487   } else {
1488     // Create the new edge.
1489     SourceN->Edges.emplace_back(TargetN, Edge::Call);
1490   }
1491
1492   // Now that we have the edge, handle the graph fallout.
1493   handleTrivialEdgeInsertion(SourceN, TargetN);
1494 }
1495
1496 void LazyCallGraph::RefSCC::insertTrivialRefEdge(Node &SourceN, Node &TargetN) {
1497 #ifndef NDEBUG
1498   // Check that the RefSCC is still valid when we finish.
1499   auto ExitVerifier = make_scope_exit([this] { verify(); });
1500
1501 #ifdef EXPENSIVE_CHECKS
1502   // Check that we aren't breaking some invariants of the RefSCC graph.
1503   RefSCC &SourceRC = *G->lookupRefSCC(SourceN);
1504   RefSCC &TargetRC = *G->lookupRefSCC(TargetN);
1505   if (&SourceRC != &TargetRC)
1506     assert(SourceRC.isAncestorOf(TargetRC) &&
1507            "Ref edge is not trivial in the RefSCC graph!");
1508 #endif // EXPENSIVE_CHECKS
1509 #endif // NDEBUG
1510
1511   // First insert it into the source or find the existing edge.
1512   auto InsertResult =
1513       SourceN->EdgeIndexMap.insert({&TargetN, SourceN->Edges.size()});
1514   if (!InsertResult.second)
1515     // Already an edge, we're done.
1516     return;
1517
1518   // Create the new edge.
1519   SourceN->Edges.emplace_back(TargetN, Edge::Ref);
1520
1521   // Now that we have the edge, handle the graph fallout.
1522   handleTrivialEdgeInsertion(SourceN, TargetN);
1523 }
1524
1525 void LazyCallGraph::RefSCC::replaceNodeFunction(Node &N, Function &NewF) {
1526   Function &OldF = N.getFunction();
1527
1528 #ifndef NDEBUG
1529   // Check that the RefSCC is still valid when we finish.
1530   auto ExitVerifier = make_scope_exit([this] { verify(); });
1531
1532   assert(G->lookupRefSCC(N) == this &&
1533          "Cannot replace the function of a node outside this RefSCC.");
1534
1535   assert(G->NodeMap.find(&NewF) == G->NodeMap.end() &&
1536          "Must not have already walked the new function!'");
1537
1538   // It is important that this replacement not introduce graph changes so we
1539   // insist that the caller has already removed every use of the original
1540   // function and that all uses of the new function correspond to existing
1541   // edges in the graph. The common and expected way to use this is when
1542   // replacing the function itself in the IR without changing the call graph
1543   // shape and just updating the analysis based on that.
1544   assert(&OldF != &NewF && "Cannot replace a function with itself!");
1545   assert(OldF.use_empty() &&
1546          "Must have moved all uses from the old function to the new!");
1547 #endif
1548
1549   N.replaceFunction(NewF);
1550
1551   // Update various call graph maps.
1552   G->NodeMap.erase(&OldF);
1553   G->NodeMap[&NewF] = &N;
1554 }
1555
1556 void LazyCallGraph::insertEdge(Node &SourceN, Node &TargetN, Edge::Kind EK) {
1557   assert(SCCMap.empty() &&
1558          "This method cannot be called after SCCs have been formed!");
1559
1560   return SourceN->insertEdgeInternal(TargetN, EK);
1561 }
1562
1563 void LazyCallGraph::removeEdge(Node &SourceN, Node &TargetN) {
1564   assert(SCCMap.empty() &&
1565          "This method cannot be called after SCCs have been formed!");
1566
1567   bool Removed = SourceN->removeEdgeInternal(TargetN);
1568   (void)Removed;
1569   assert(Removed && "Target not in the edge set for this caller?");
1570 }
1571
1572 void LazyCallGraph::removeDeadFunction(Function &F) {
1573   // FIXME: This is unnecessarily restrictive. We should be able to remove
1574   // functions which recursively call themselves.
1575   assert(F.use_empty() &&
1576          "This routine should only be called on trivially dead functions!");
1577
1578   auto NI = NodeMap.find(&F);
1579   if (NI == NodeMap.end())
1580     // Not in the graph at all!
1581     return;
1582
1583   Node &N = *NI->second;
1584   NodeMap.erase(NI);
1585
1586   // Remove this from the entry edges if present.
1587   EntryEdges.removeEdgeInternal(N);
1588
1589   if (SCCMap.empty()) {
1590     // No SCCs have been formed, so removing this is fine and there is nothing
1591     // else necessary at this point but clearing out the node.
1592     N.clear();
1593     return;
1594   }
1595
1596   // Cannot remove a function which has yet to be visited in the DFS walk, so
1597   // if we have a node at all then we must have an SCC and RefSCC.
1598   auto CI = SCCMap.find(&N);
1599   assert(CI != SCCMap.end() &&
1600          "Tried to remove a node without an SCC after DFS walk started!");
1601   SCC &C = *CI->second;
1602   SCCMap.erase(CI);
1603   RefSCC &RC = C.getOuterRefSCC();
1604
1605   // This node must be the only member of its SCC as it has no callers, and
1606   // that SCC must be the only member of a RefSCC as it has no references.
1607   // Validate these properties first.
1608   assert(C.size() == 1 && "Dead functions must be in a singular SCC");
1609   assert(RC.size() == 1 && "Dead functions must be in a singular RefSCC");
1610
1611   // Clean up any remaining reference edges. Note that we walk an unordered set
1612   // here but are just removing and so the order doesn't matter.
1613   for (RefSCC &ParentRC : RC.parents())
1614     for (SCC &ParentC : ParentRC)
1615       for (Node &ParentN : ParentC)
1616         if (ParentN)
1617           ParentN->removeEdgeInternal(N);
1618
1619   // Now remove this RefSCC from any parents sets and the leaf list.
1620   for (Edge &E : *N)
1621     if (RefSCC *TargetRC = lookupRefSCC(E.getNode()))
1622       TargetRC->Parents.erase(&RC);
1623   // FIXME: This is a linear operation which could become hot and benefit from
1624   // an index map.
1625   auto LRI = find(LeafRefSCCs, &RC);
1626   if (LRI != LeafRefSCCs.end())
1627     LeafRefSCCs.erase(LRI);
1628
1629   auto RCIndexI = RefSCCIndices.find(&RC);
1630   int RCIndex = RCIndexI->second;
1631   PostOrderRefSCCs.erase(PostOrderRefSCCs.begin() + RCIndex);
1632   RefSCCIndices.erase(RCIndexI);
1633   for (int i = RCIndex, Size = PostOrderRefSCCs.size(); i < Size; ++i)
1634     RefSCCIndices[PostOrderRefSCCs[i]] = i;
1635
1636   // Finally clear out all the data structures from the node down through the
1637   // components.
1638   N.clear();
1639   C.clear();
1640   RC.clear();
1641
1642   // Nothing to delete as all the objects are allocated in stable bump pointer
1643   // allocators.
1644 }
1645
1646 LazyCallGraph::Node &LazyCallGraph::insertInto(Function &F, Node *&MappedN) {
1647   return *new (MappedN = BPA.Allocate()) Node(*this, F);
1648 }
1649
1650 void LazyCallGraph::updateGraphPtrs() {
1651   // Process all nodes updating the graph pointers.
1652   {
1653     SmallVector<Node *, 16> Worklist;
1654     for (Edge &E : EntryEdges)
1655       Worklist.push_back(&E.getNode());
1656
1657     while (!Worklist.empty()) {
1658       Node &N = *Worklist.pop_back_val();
1659       N.G = this;
1660       if (N)
1661         for (Edge &E : *N)
1662           Worklist.push_back(&E.getNode());
1663     }
1664   }
1665
1666   // Process all SCCs updating the graph pointers.
1667   {
1668     SmallVector<RefSCC *, 16> Worklist(LeafRefSCCs.begin(), LeafRefSCCs.end());
1669
1670     while (!Worklist.empty()) {
1671       RefSCC &C = *Worklist.pop_back_val();
1672       C.G = this;
1673       for (RefSCC &ParentC : C.parents())
1674         Worklist.push_back(&ParentC);
1675     }
1676   }
1677 }
1678
1679 template <typename RootsT, typename GetBeginT, typename GetEndT,
1680           typename GetNodeT, typename FormSCCCallbackT>
1681 void LazyCallGraph::buildGenericSCCs(RootsT &&Roots, GetBeginT &&GetBegin,
1682                                      GetEndT &&GetEnd, GetNodeT &&GetNode,
1683                                      FormSCCCallbackT &&FormSCC) {
1684   typedef decltype(GetBegin(std::declval<Node &>())) EdgeItT;
1685
1686   SmallVector<std::pair<Node *, EdgeItT>, 16> DFSStack;
1687   SmallVector<Node *, 16> PendingSCCStack;
1688
1689   // Scan down the stack and DFS across the call edges.
1690   for (Node *RootN : Roots) {
1691     assert(DFSStack.empty() &&
1692            "Cannot begin a new root with a non-empty DFS stack!");
1693     assert(PendingSCCStack.empty() &&
1694            "Cannot begin a new root with pending nodes for an SCC!");
1695
1696     // Skip any nodes we've already reached in the DFS.
1697     if (RootN->DFSNumber != 0) {
1698       assert(RootN->DFSNumber == -1 &&
1699              "Shouldn't have any mid-DFS root nodes!");
1700       continue;
1701     }
1702
1703     RootN->DFSNumber = RootN->LowLink = 1;
1704     int NextDFSNumber = 2;
1705
1706     DFSStack.push_back({RootN, GetBegin(*RootN)});
1707     do {
1708       Node *N;
1709       EdgeItT I;
1710       std::tie(N, I) = DFSStack.pop_back_val();
1711       auto E = GetEnd(*N);
1712       while (I != E) {
1713         Node &ChildN = GetNode(I);
1714         if (ChildN.DFSNumber == 0) {
1715           // We haven't yet visited this child, so descend, pushing the current
1716           // node onto the stack.
1717           DFSStack.push_back({N, I});
1718
1719           ChildN.DFSNumber = ChildN.LowLink = NextDFSNumber++;
1720           N = &ChildN;
1721           I = GetBegin(*N);
1722           E = GetEnd(*N);
1723           continue;
1724         }
1725
1726         // If the child has already been added to some child component, it
1727         // couldn't impact the low-link of this parent because it isn't
1728         // connected, and thus its low-link isn't relevant so skip it.
1729         if (ChildN.DFSNumber == -1) {
1730           ++I;
1731           continue;
1732         }
1733
1734         // Track the lowest linked child as the lowest link for this node.
1735         assert(ChildN.LowLink > 0 && "Must have a positive low-link number!");
1736         if (ChildN.LowLink < N->LowLink)
1737           N->LowLink = ChildN.LowLink;
1738
1739         // Move to the next edge.
1740         ++I;
1741       }
1742
1743       // We've finished processing N and its descendents, put it on our pending
1744       // SCC stack to eventually get merged into an SCC of nodes.
1745       PendingSCCStack.push_back(N);
1746
1747       // If this node is linked to some lower entry, continue walking up the
1748       // stack.
1749       if (N->LowLink != N->DFSNumber)
1750         continue;
1751
1752       // Otherwise, we've completed an SCC. Append it to our post order list of
1753       // SCCs.
1754       int RootDFSNumber = N->DFSNumber;
1755       // Find the range of the node stack by walking down until we pass the
1756       // root DFS number.
1757       auto SCCNodes = make_range(
1758           PendingSCCStack.rbegin(),
1759           find_if(reverse(PendingSCCStack), [RootDFSNumber](const Node *N) {
1760             return N->DFSNumber < RootDFSNumber;
1761           }));
1762       // Form a new SCC out of these nodes and then clear them off our pending
1763       // stack.
1764       FormSCC(SCCNodes);
1765       PendingSCCStack.erase(SCCNodes.end().base(), PendingSCCStack.end());
1766     } while (!DFSStack.empty());
1767   }
1768 }
1769
1770 /// Build the internal SCCs for a RefSCC from a sequence of nodes.
1771 ///
1772 /// Appends the SCCs to the provided vector and updates the map with their
1773 /// indices. Both the vector and map must be empty when passed into this
1774 /// routine.
1775 void LazyCallGraph::buildSCCs(RefSCC &RC, node_stack_range Nodes) {
1776   assert(RC.SCCs.empty() && "Already built SCCs!");
1777   assert(RC.SCCIndices.empty() && "Already mapped SCC indices!");
1778
1779   for (Node *N : Nodes) {
1780     assert(N->LowLink >= (*Nodes.begin())->LowLink &&
1781            "We cannot have a low link in an SCC lower than its root on the "
1782            "stack!");
1783
1784     // This node will go into the next RefSCC, clear out its DFS and low link
1785     // as we scan.
1786     N->DFSNumber = N->LowLink = 0;
1787   }
1788
1789   // Each RefSCC contains a DAG of the call SCCs. To build these, we do
1790   // a direct walk of the call edges using Tarjan's algorithm. We reuse the
1791   // internal storage as we won't need it for the outer graph's DFS any longer.
1792   buildGenericSCCs(
1793       Nodes, [](Node &N) { return N->call_begin(); },
1794       [](Node &N) { return N->call_end(); },
1795       [](EdgeSequence::call_iterator I) -> Node & { return I->getNode(); },
1796       [this, &RC](node_stack_range Nodes) {
1797         RC.SCCs.push_back(createSCC(RC, Nodes));
1798         for (Node &N : *RC.SCCs.back()) {
1799           N.DFSNumber = N.LowLink = -1;
1800           SCCMap[&N] = RC.SCCs.back();
1801         }
1802       });
1803
1804   // Wire up the SCC indices.
1805   for (int i = 0, Size = RC.SCCs.size(); i < Size; ++i)
1806     RC.SCCIndices[RC.SCCs[i]] = i;
1807 }
1808
1809 void LazyCallGraph::buildRefSCCs() {
1810   if (EntryEdges.empty() || !PostOrderRefSCCs.empty())
1811     // RefSCCs are either non-existent or already built!
1812     return;
1813
1814   assert(RefSCCIndices.empty() && "Already mapped RefSCC indices!");
1815
1816   SmallVector<Node *, 16> Roots;
1817   for (Edge &E : *this)
1818     Roots.push_back(&E.getNode());
1819
1820   // The roots will be popped of a stack, so use reverse to get a less
1821   // surprising order. This doesn't change any of the semantics anywhere.
1822   std::reverse(Roots.begin(), Roots.end());
1823
1824   buildGenericSCCs(
1825       Roots,
1826       [](Node &N) {
1827         // We need to populate each node as we begin to walk its edges.
1828         N.populate();
1829         return N->begin();
1830       },
1831       [](Node &N) { return N->end(); },
1832       [](EdgeSequence::iterator I) -> Node & { return I->getNode(); },
1833       [this](node_stack_range Nodes) {
1834         RefSCC *NewRC = createRefSCC(*this);
1835         buildSCCs(*NewRC, Nodes);
1836         connectRefSCC(*NewRC);
1837
1838         // Push the new node into the postorder list and remember its position
1839         // in the index map.
1840         bool Inserted =
1841             RefSCCIndices.insert({NewRC, PostOrderRefSCCs.size()}).second;
1842         (void)Inserted;
1843         assert(Inserted && "Cannot already have this RefSCC in the index map!");
1844         PostOrderRefSCCs.push_back(NewRC);
1845 #ifndef NDEBUG
1846         NewRC->verify();
1847 #endif
1848       });
1849 }
1850
1851 // FIXME: We should move callers of this to embed the parent linking and leaf
1852 // tracking into their DFS in order to remove a full walk of all edges.
1853 void LazyCallGraph::connectRefSCC(RefSCC &RC) {
1854   // Walk all edges in the RefSCC (this remains linear as we only do this once
1855   // when we build the RefSCC) to connect it to the parent sets of its
1856   // children.
1857   bool IsLeaf = true;
1858   for (SCC &C : RC)
1859     for (Node &N : C)
1860       for (Edge &E : *N) {
1861         RefSCC &ChildRC = *lookupRefSCC(E.getNode());
1862         if (&ChildRC == &RC)
1863           continue;
1864         ChildRC.Parents.insert(&RC);
1865         IsLeaf = false;
1866       }
1867
1868   // For the SCCs where we find no child SCCs, add them to the leaf list.
1869   if (IsLeaf)
1870     LeafRefSCCs.push_back(&RC);
1871 }
1872
1873 AnalysisKey LazyCallGraphAnalysis::Key;
1874
1875 LazyCallGraphPrinterPass::LazyCallGraphPrinterPass(raw_ostream &OS) : OS(OS) {}
1876
1877 static void printNode(raw_ostream &OS, LazyCallGraph::Node &N) {
1878   OS << "  Edges in function: " << N.getFunction().getName() << "\n";
1879   for (LazyCallGraph::Edge &E : N.populate())
1880     OS << "    " << (E.isCall() ? "call" : "ref ") << " -> "
1881        << E.getFunction().getName() << "\n";
1882
1883   OS << "\n";
1884 }
1885
1886 static void printSCC(raw_ostream &OS, LazyCallGraph::SCC &C) {
1887   ptrdiff_t Size = std::distance(C.begin(), C.end());
1888   OS << "    SCC with " << Size << " functions:\n";
1889
1890   for (LazyCallGraph::Node &N : C)
1891     OS << "      " << N.getFunction().getName() << "\n";
1892 }
1893
1894 static void printRefSCC(raw_ostream &OS, LazyCallGraph::RefSCC &C) {
1895   ptrdiff_t Size = std::distance(C.begin(), C.end());
1896   OS << "  RefSCC with " << Size << " call SCCs:\n";
1897
1898   for (LazyCallGraph::SCC &InnerC : C)
1899     printSCC(OS, InnerC);
1900
1901   OS << "\n";
1902 }
1903
1904 PreservedAnalyses LazyCallGraphPrinterPass::run(Module &M,
1905                                                 ModuleAnalysisManager &AM) {
1906   LazyCallGraph &G = AM.getResult<LazyCallGraphAnalysis>(M);
1907
1908   OS << "Printing the call graph for module: " << M.getModuleIdentifier()
1909      << "\n\n";
1910
1911   for (Function &F : M)
1912     printNode(OS, G.get(F));
1913
1914   G.buildRefSCCs();
1915   for (LazyCallGraph::RefSCC &C : G.postorder_ref_sccs())
1916     printRefSCC(OS, C);
1917
1918   return PreservedAnalyses::all();
1919 }
1920
1921 LazyCallGraphDOTPrinterPass::LazyCallGraphDOTPrinterPass(raw_ostream &OS)
1922     : OS(OS) {}
1923
1924 static void printNodeDOT(raw_ostream &OS, LazyCallGraph::Node &N) {
1925   std::string Name = "\"" + DOT::EscapeString(N.getFunction().getName()) + "\"";
1926
1927   for (LazyCallGraph::Edge &E : N.populate()) {
1928     OS << "  " << Name << " -> \""
1929        << DOT::EscapeString(E.getFunction().getName()) << "\"";
1930     if (!E.isCall()) // It is a ref edge.
1931       OS << " [style=dashed,label=\"ref\"]";
1932     OS << ";\n";
1933   }
1934
1935   OS << "\n";
1936 }
1937
1938 PreservedAnalyses LazyCallGraphDOTPrinterPass::run(Module &M,
1939                                                    ModuleAnalysisManager &AM) {
1940   LazyCallGraph &G = AM.getResult<LazyCallGraphAnalysis>(M);
1941
1942   OS << "digraph \"" << DOT::EscapeString(M.getModuleIdentifier()) << "\" {\n";
1943
1944   for (Function &F : M)
1945     printNodeDOT(OS, G.get(F));
1946
1947   OS << "}\n";
1948
1949   return PreservedAnalyses::all();
1950 }