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/STLExtras.h"
  12 #include "llvm/IR/CallSite.h"
  13 #include "llvm/IR/InstVisitor.h"
  14 #include "llvm/IR/Instructions.h"
  15 #include "llvm/IR/PassManager.h"
  16 #include "llvm/Support/Debug.h"
  17 #include "llvm/Support/GraphWriter.h"
  18
  19 using namespace llvm;
  20
  21 #define DEBUG_TYPE "lcg"
  22
  23 static void addEdge(SmallVectorImpl<LazyCallGraph::Edge> &Edges,
  24                     DenseMap<Function *, int> &EdgeIndexMap, Function &F,
  25                     LazyCallGraph::Edge::Kind EK) {
  26   // Note that we consider *any* function with a definition to be a viable
  27   // edge. Even if the function's definition is subject to replacement by
  28   // some other module (say, a weak definition) there may still be
  29   // optimizations which essentially speculate based on the definition and
  30   // a way to check that the specific definition is in fact the one being
  31   // used. For example, this could be done by moving the weak definition to
  32   // a strong (internal) definition and making the weak definition be an
  33   // alias. Then a test of the address of the weak function against the new
  34   // strong definition's address would be an effective way to determine the
  35   // safety of optimizing a direct call edge.
  36   if (!F.isDeclaration() &&
  37       EdgeIndexMap.insert({&F, Edges.size()}).second) {
  38     DEBUG(dbgs() << "    Added callable function: " << F.getName() << "\n");
  39     Edges.emplace_back(LazyCallGraph::Edge(F, EK));
  40   }
  41 }
  42
  43 static void findReferences(SmallVectorImpl<Constant *> &Worklist,
  44                            SmallPtrSetImpl<Constant *> &Visited,
  45                            SmallVectorImpl<LazyCallGraph::Edge> &Edges,
  46                            DenseMap<Function *, int> &EdgeIndexMap) {
  47   while (!Worklist.empty()) {
  48     Constant *C = Worklist.pop_back_val();
  49
  50     if (Function *F = dyn_cast<Function>(C)) {
  51       addEdge(Edges, EdgeIndexMap, *F, LazyCallGraph::Edge::Ref);
  52       continue;
  53     }
  54
  55     for (Value *Op : C->operand_values())
  56       if (Visited.insert(cast<Constant>(Op)).second)
  57         Worklist.push_back(cast<Constant>(Op));
  58   }
  59 }
  60
  61 LazyCallGraph::Node::Node(LazyCallGraph &G, Function &F)
  62     : G(&G), F(F), DFSNumber(0), LowLink(0) {
  63   DEBUG(dbgs() << "  Adding functions called by '" << F.getName()
  64                << "' to the graph.\n");
  65
  66   SmallVector<Constant *, 16> Worklist;
  67   SmallPtrSet<Function *, 4> Callees;
  68   SmallPtrSet<Constant *, 16> Visited;
  69
  70   // Find all the potential call graph edges in this function. We track both
  71   // actual call edges and indirect references to functions. The direct calls
  72   // are trivially added, but to accumulate the latter we walk the instructions
  73   // and add every operand which is a constant to the worklist to process
  74   // afterward.
  75   for (BasicBlock &BB : F)
  76     for (Instruction &I : BB) {
  77       if (auto CS = CallSite(&I))
  78         if (Function *Callee = CS.getCalledFunction())
  79           if (Callees.insert(Callee).second) {
  80             Visited.insert(Callee);
  81             addEdge(Edges, EdgeIndexMap, *Callee, LazyCallGraph::Edge::Call);
  82           }
  83
  84       for (Value *Op : I.operand_values())
  85         if (Constant *C = dyn_cast<Constant>(Op))
  86           if (Visited.insert(C).second)
  87             Worklist.push_back(C);
  88     }
  89
  90   // We've collected all the constant (and thus potentially function or
  91   // function containing) operands to all of the instructions in the function.
  92   // Process them (recursively) collecting every function found.
  93   findReferences(Worklist, Visited, Edges, EdgeIndexMap);
  94 }
  95
  96 void LazyCallGraph::Node::insertEdgeInternal(Function &Target, Edge::Kind EK) {
  97   if (Node *N = G->lookup(Target))
  98     return insertEdgeInternal(*N, EK);
  99
 100   EdgeIndexMap.insert({&Target, Edges.size()});
 101   Edges.emplace_back(Target, EK);
 102 }
 103
 104 void LazyCallGraph::Node::insertEdgeInternal(Node &TargetN, Edge::Kind EK) {
 105   EdgeIndexMap.insert({&TargetN.getFunction(), Edges.size()});
 106   Edges.emplace_back(TargetN, EK);
 107 }
 108
 109 void LazyCallGraph::Node::setEdgeKind(Function &TargetF, Edge::Kind EK) {
 110   Edges[EdgeIndexMap.find(&TargetF)->second].setKind(EK);
 111 }
 112
 113 void LazyCallGraph::Node::removeEdgeInternal(Function &Target) {
 114   auto IndexMapI = EdgeIndexMap.find(&Target);
 115   assert(IndexMapI != EdgeIndexMap.end() &&
 116          "Target not in the edge set for this caller?");
 117
 118   Edges[IndexMapI->second] = Edge();
 119   EdgeIndexMap.erase(IndexMapI);
 120 }
 121
 122 void LazyCallGraph::Node::dump() const {
 123   dbgs() << *this << '\n';
 124 }
 125
 126 LazyCallGraph::LazyCallGraph(Module &M) : NextDFSNumber(0) {
 127   DEBUG(dbgs() << "Building CG for module: " << M.getModuleIdentifier()
 128                << "\n");
 129   for (Function &F : M)
 130     if (!F.isDeclaration() && !F.hasLocalLinkage())
 131       if (EntryIndexMap.insert({&F, EntryEdges.size()}).second) {
 132         DEBUG(dbgs() << "  Adding '" << F.getName()
 133                      << "' to entry set of the graph.\n");
 134         EntryEdges.emplace_back(F, Edge::Ref);
 135       }
 136
 137   // Now add entry nodes for functions reachable via initializers to globals.
 138   SmallVector<Constant *, 16> Worklist;
 139   SmallPtrSet<Constant *, 16> Visited;
 140   for (GlobalVariable &GV : M.globals())
 141     if (GV.hasInitializer())
 142       if (Visited.insert(GV.getInitializer()).second)
 143         Worklist.push_back(GV.getInitializer());
 144
 145   DEBUG(dbgs() << "  Adding functions referenced by global initializers to the "
 146                   "entry set.\n");
 147   findReferences(Worklist, Visited, EntryEdges, EntryIndexMap);
 148
 149   for (const Edge &E : EntryEdges)
 150     RefSCCEntryNodes.push_back(&E.getFunction());
 151 }
 152
 153 LazyCallGraph::LazyCallGraph(LazyCallGraph &&G)
 154     : BPA(std::move(G.BPA)), NodeMap(std::move(G.NodeMap)),
 155       EntryEdges(std::move(G.EntryEdges)),
 156       EntryIndexMap(std::move(G.EntryIndexMap)), SCCBPA(std::move(G.SCCBPA)),
 157       SCCMap(std::move(G.SCCMap)), LeafRefSCCs(std::move(G.LeafRefSCCs)),
 158       DFSStack(std::move(G.DFSStack)),
 159       RefSCCEntryNodes(std::move(G.RefSCCEntryNodes)),
 160       NextDFSNumber(G.NextDFSNumber) {
 161   updateGraphPtrs();
 162 }
 163
 164 LazyCallGraph &LazyCallGraph::operator=(LazyCallGraph &&G) {
 165   BPA = std::move(G.BPA);
 166   NodeMap = std::move(G.NodeMap);
 167   EntryEdges = std::move(G.EntryEdges);
 168   EntryIndexMap = std::move(G.EntryIndexMap);
 169   SCCBPA = std::move(G.SCCBPA);
 170   SCCMap = std::move(G.SCCMap);
 171   LeafRefSCCs = std::move(G.LeafRefSCCs);
 172   DFSStack = std::move(G.DFSStack);
 173   RefSCCEntryNodes = std::move(G.RefSCCEntryNodes);
 174   NextDFSNumber = G.NextDFSNumber;
 175   updateGraphPtrs();
 176   return *this;
 177 }
 178
 179 void LazyCallGraph::SCC::dump() const {
 180   dbgs() << *this << '\n';
 181 }
 182
 183 #ifndef NDEBUG
 184 void LazyCallGraph::SCC::verify() {
 185   assert(OuterRefSCC && "Can't have a null RefSCC!");
 186   assert(!Nodes.empty() && "Can't have an empty SCC!");
 187
 188   for (Node *N : Nodes) {
 189     assert(N && "Can't have a null node!");
 190     assert(OuterRefSCC->G->lookupSCC(*N) == this &&
 191            "Node does not map to this SCC!");
 192     assert(N->DFSNumber == -1 &&
 193            "Must set DFS numbers to -1 when adding a node to an SCC!");
 194     assert(N->LowLink == -1 &&
 195            "Must set low link to -1 when adding a node to an SCC!");
 196     for (Edge &E : *N)
 197       assert(E.getNode() && "Can't have an edge to a raw function!");
 198   }
 199 }
 200 #endif
 201
 202 LazyCallGraph::RefSCC::RefSCC(LazyCallGraph &G) : G(&G) {}
 203
 204 void LazyCallGraph::RefSCC::dump() const {
 205   dbgs() << *this << '\n';
 206 }
 207
 208 #ifndef NDEBUG
 209 void LazyCallGraph::RefSCC::verify() {
 210   assert(G && "Can't have a null graph!");
 211   assert(!SCCs.empty() && "Can't have an empty SCC!");
 212
 213   // Verify basic properties of the SCCs.
 214   for (SCC *C : SCCs) {
 215     assert(C && "Can't have a null SCC!");
 216     C->verify();
 217     assert(&C->getOuterRefSCC() == this &&
 218            "SCC doesn't think it is inside this RefSCC!");
 219   }
 220
 221   // Check that our indices map correctly.
 222   for (auto &SCCIndexPair : SCCIndices) {
 223     SCC *C = SCCIndexPair.first;
 224     int i = SCCIndexPair.second;
 225     assert(C && "Can't have a null SCC in the indices!");
 226     assert(SCCs[i] == C && "Index doesn't point to SCC!");
 227   }
 228
 229   // Check that the SCCs are in fact in post-order.
 230   for (int i = 0, Size = SCCs.size(); i < Size; ++i) {
 231     SCC &SourceSCC = *SCCs[i];
 232     for (Node &N : SourceSCC)
 233       for (Edge &E : N) {
 234         if (!E.isCall())
 235           continue;
 236         SCC &TargetSCC = *G->lookupSCC(*E.getNode());
 237         if (&TargetSCC.getOuterRefSCC() == this) {
 238           assert(SCCIndices.find(&TargetSCC)->second <= i &&
 239                  "Edge between SCCs violates post-order relationship.");
 240           continue;
 241         }
 242         assert(TargetSCC.getOuterRefSCC().Parents.count(this) &&
 243                "Edge to a RefSCC missing us in its parent set.");
 244       }
 245   }
 246 }
 247 #endif
 248
 249 bool LazyCallGraph::RefSCC::isDescendantOf(const RefSCC &C) const {
 250   // Walk up the parents of this SCC and verify that we eventually find C.
 251   SmallVector<const RefSCC *, 4> AncestorWorklist;
 252   AncestorWorklist.push_back(this);
 253   do {
 254     const RefSCC *AncestorC = AncestorWorklist.pop_back_val();
 255     if (AncestorC->isChildOf(C))
 256       return true;
 257     for (const RefSCC *ParentC : AncestorC->Parents)
 258       AncestorWorklist.push_back(ParentC);
 259   } while (!AncestorWorklist.empty());
 260
 261   return false;
 262 }
 263
 264 SmallVector<LazyCallGraph::SCC *, 1>
 265 LazyCallGraph::RefSCC::switchInternalEdgeToCall(Node &SourceN, Node &TargetN) {
 266   assert(!SourceN[TargetN].isCall() && "Must start with a ref edge!");
 267
 268   SmallVector<SCC *, 1> DeletedSCCs;
 269
 270   SCC &SourceSCC = *G->lookupSCC(SourceN);
 271   SCC &TargetSCC = *G->lookupSCC(TargetN);
 272
 273   // If the two nodes are already part of the same SCC, we're also done as
 274   // we've just added more connectivity.
 275   if (&SourceSCC == &TargetSCC) {
 276     SourceN.setEdgeKind(TargetN.getFunction(), Edge::Call);
 277 #ifndef NDEBUG
 278     // Check that the RefSCC is still valid.
 279     verify();
 280 #endif
 281     return DeletedSCCs;
 282   }
 283
 284   // At this point we leverage the postorder list of SCCs to detect when the
 285   // insertion of an edge changes the SCC structure in any way.
 286   //
 287   // First and foremost, we can eliminate the need for any changes when the
 288   // edge is toward the beginning of the postorder sequence because all edges
 289   // flow in that direction already. Thus adding a new one cannot form a cycle.
 290   int SourceIdx = SCCIndices[&SourceSCC];
 291   int TargetIdx = SCCIndices[&TargetSCC];
 292   if (TargetIdx < SourceIdx) {
 293     SourceN.setEdgeKind(TargetN.getFunction(), Edge::Call);
 294 #ifndef NDEBUG
 295     // Check that the RefSCC is still valid.
 296     verify();
 297 #endif
 298     return DeletedSCCs;
 299   }
 300
 301   // When we do have an edge from an earlier SCC to a later SCC in the
 302   // postorder sequence, all of the SCCs which may be impacted are in the
 303   // closed range of those two within the postorder sequence. The algorithm to
 304   // restore the state is as follows:
 305   //
 306   // 1) Starting from the source SCC, construct a set of SCCs which reach the
 307   //    source SCC consisting of just the source SCC. Then scan toward the
 308   //    target SCC in postorder and for each SCC, if it has an edge to an SCC
 309   //    in the set, add it to the set. Otherwise, the source SCC is not
 310   //    a successor, move it in the postorder sequence to immediately before
 311   //    the source SCC, shifting the source SCC and all SCCs in the set one
 312   //    position toward the target SCC. Stop scanning after processing the
 313   //    target SCC.
 314   // 2) If the source SCC is now past the target SCC in the postorder sequence,
 315   //    and thus the new edge will flow toward the start, we are done.
 316   // 3) Otherwise, starting from the target SCC, walk all edges which reach an
 317   //    SCC between the source and the target, and add them to the set of
 318   //    connected SCCs, then recurse through them. Once a complete set of the
 319   //    SCCs the target connects to is known, hoist the remaining SCCs between
 320   //    the source and the target to be above the target. Note that there is no
 321   //    need to process the source SCC, it is already known to connect.
 322   // 4) At this point, all of the SCCs in the closed range between the source
 323   //    SCC and the target SCC in the postorder sequence are connected,
 324   //    including the target SCC and the source SCC. Inserting the edge from
 325   //    the source SCC to the target SCC will form a cycle out of precisely
 326   //    these SCCs. Thus we can merge all of the SCCs in this closed range into
 327   //    a single SCC.
 328   //
 329   // This process has various important properties:
 330   // - Only mutates the SCCs when adding the edge actually changes the SCC
 331   //   structure.
 332   // - Never mutates SCCs which are unaffected by the change.
 333   // - Updates the postorder sequence to correctly satisfy the postorder
 334   //   constraint after the edge is inserted.
 335   // - Only reorders SCCs in the closed postorder sequence from the source to
 336   //   the target, so easy to bound how much has changed even in the ordering.
 337   // - Big-O is the number of edges in the closed postorder range of SCCs from
 338   //   source to target.
 339
 340   assert(SourceIdx < TargetIdx && "Cannot have equal indices here!");
 341   SmallPtrSet<SCC *, 4> ConnectedSet;
 342
 343   // Compute the SCCs which (transitively) reach the source.
 344   ConnectedSet.insert(&SourceSCC);
 345   auto IsConnected = [&](SCC &C) {
 346     for (Node &N : C)
 347       for (Edge &E : N.calls()) {
 348         assert(E.getNode() && "Must have formed a node within an SCC!");
 349         if (ConnectedSet.count(G->lookupSCC(*E.getNode())))
 350           return true;
 351       }
 352
 353     return false;
 354   };
 355
 356   for (SCC *C :
 357        make_range(SCCs.begin() + SourceIdx + 1, SCCs.begin() + TargetIdx + 1))
 358     if (IsConnected(*C))
 359       ConnectedSet.insert(C);
 360
 361   // Partition the SCCs in this part of the port-order sequence so only SCCs
 362   // connecting to the source remain between it and the target. This is
 363   // a benign partition as it preserves postorder.
 364   auto SourceI = std::stable_partition(
 365       SCCs.begin() + SourceIdx, SCCs.begin() + TargetIdx + 1,
 366       [&ConnectedSet](SCC *C) { return !ConnectedSet.count(C); });
 367   for (int i = SourceIdx, e = TargetIdx + 1; i < e; ++i)
 368     SCCIndices.find(SCCs[i])->second = i;
 369
 370   // If the target doesn't connect to the source, then we've corrected the
 371   // post-order and there are no cycles formed.
 372   if (!ConnectedSet.count(&TargetSCC)) {
 373     assert(SourceI > (SCCs.begin() + SourceIdx) &&
 374            "Must have moved the source to fix the post-order.");
 375     assert(*std::prev(SourceI) == &TargetSCC &&
 376            "Last SCC to move should have bene the target.");
 377     SourceN.setEdgeKind(TargetN.getFunction(), Edge::Call);
 378 #ifndef NDEBUG
 379     verify();
 380 #endif
 381     return DeletedSCCs;
 382   }
 383
 384   assert(SCCs[TargetIdx] == &TargetSCC &&
 385          "Should not have moved target if connected!");
 386   SourceIdx = SourceI - SCCs.begin();
 387
 388 #ifndef NDEBUG
 389   // Check that the RefSCC is still valid.
 390   verify();
 391 #endif
 392
 393   // See whether there are any remaining intervening SCCs between the source
 394   // and target. If so we need to make sure they all are reachable form the
 395   // target.
 396   if (SourceIdx + 1 < TargetIdx) {
 397     // Use a normal worklist to find which SCCs the target connects to. We still
 398     // bound the search based on the range in the postorder list we care about,
 399     // but because this is forward connectivity we just "recurse" through the
 400     // edges.
 401     ConnectedSet.clear();
 402     ConnectedSet.insert(&TargetSCC);
 403     SmallVector<SCC *, 4> Worklist;
 404     Worklist.push_back(&TargetSCC);
 405     do {
 406       SCC &C = *Worklist.pop_back_val();
 407       for (Node &N : C)
 408         for (Edge &E : N) {
 409           assert(E.getNode() && "Must have formed a node within an SCC!");
 410           if (!E.isCall())
 411             continue;
 412           SCC &EdgeC = *G->lookupSCC(*E.getNode());
 413           if (&EdgeC.getOuterRefSCC() != this)
 414             // Not in this RefSCC...
 415             continue;
 416           if (SCCIndices.find(&EdgeC)->second <= SourceIdx)
 417             // Not in the postorder sequence between source and target.
 418             continue;
 419
 420           if (ConnectedSet.insert(&EdgeC).second)
 421             Worklist.push_back(&EdgeC);
 422         }
 423     } while (!Worklist.empty());
 424
 425     // Partition SCCs so that only SCCs reached from the target remain between
 426     // the source and the target. This preserves postorder.
 427     auto TargetI = std::stable_partition(
 428         SCCs.begin() + SourceIdx + 1, SCCs.begin() + TargetIdx + 1,
 429         [&ConnectedSet](SCC *C) { return ConnectedSet.count(C); });
 430     for (int i = SourceIdx + 1, e = TargetIdx + 1; i < e; ++i)
 431       SCCIndices.find(SCCs[i])->second = i;
 432     TargetIdx = std::prev(TargetI) - SCCs.begin();
 433     assert(SCCs[TargetIdx] == &TargetSCC &&
 434            "Should always end with the target!");
 435
 436 #ifndef NDEBUG
 437     // Check that the RefSCC is still valid.
 438     verify();
 439 #endif
 440   }
 441
 442   // At this point, we know that connecting source to target forms a cycle
 443   // because target connects back to source, and we know that all of the SCCs
 444   // between the source and target in the postorder sequence participate in that
 445   // cycle. This means that we need to merge all of these SCCs into a single
 446   // result SCC.
 447   //
 448   // NB: We merge into the target because all of these functions were already
 449   // reachable from the target, meaning any SCC-wide properties deduced about it
 450   // other than the set of functions within it will not have changed.
 451   auto MergeRange =
 452       make_range(SCCs.begin() + SourceIdx, SCCs.begin() + TargetIdx);
 453   for (SCC *C : MergeRange) {
 454     assert(C != &TargetSCC &&
 455            "We merge *into* the target and shouldn't process it here!");
 456     SCCIndices.erase(C);
 457     TargetSCC.Nodes.append(C->Nodes.begin(), C->Nodes.end());
 458     for (Node *N : C->Nodes)
 459       G->SCCMap[N] = &TargetSCC;
 460     C->clear();
 461     DeletedSCCs.push_back(C);
 462   }
 463
 464   // Erase the merged SCCs from the list and update the indices of the
 465   // remaining SCCs.
 466   int IndexOffset = MergeRange.end() - MergeRange.begin();
 467   auto EraseEnd = SCCs.erase(MergeRange.begin(), MergeRange.end());
 468   for (SCC *C : make_range(EraseEnd, SCCs.end()))
 469     SCCIndices[C] -= IndexOffset;
 470
 471   // Now that the SCC structure is finalized, flip the kind to call.
 472   SourceN.setEdgeKind(TargetN.getFunction(), Edge::Call);
 473
 474 #ifndef NDEBUG
 475   // And we're done! Verify in debug builds that the RefSCC is coherent.
 476   verify();
 477 #endif
 478   return DeletedSCCs;
 479 }
 480
 481 void LazyCallGraph::RefSCC::switchInternalEdgeToRef(Node &SourceN,
 482                                                     Node &TargetN) {
 483   assert(SourceN[TargetN].isCall() && "Must start with a call edge!");
 484
 485   SCC &SourceSCC = *G->lookupSCC(SourceN);
 486   SCC &TargetSCC = *G->lookupSCC(TargetN);
 487
 488   assert(&SourceSCC.getOuterRefSCC() == this &&
 489          "Source must be in this RefSCC.");
 490   assert(&TargetSCC.getOuterRefSCC() == this &&
 491          "Target must be in this RefSCC.");
 492
 493   // Set the edge kind.
 494   SourceN.setEdgeKind(TargetN.getFunction(), Edge::Ref);
 495
 496   // If this call edge is just connecting two separate SCCs within this RefSCC,
 497   // there is nothing to do.
 498   if (&SourceSCC != &TargetSCC) {
 499 #ifndef NDEBUG
 500     // Check that the RefSCC is still valid.
 501     verify();
 502 #endif
 503     return;
 504   }
 505
 506   // Otherwise we are removing a call edge from a single SCC. This may break
 507   // the cycle. In order to compute the new set of SCCs, we need to do a small
 508   // DFS over the nodes within the SCC to form any sub-cycles that remain as
 509   // distinct SCCs and compute a postorder over the resulting SCCs.
 510   //
 511   // However, we specially handle the target node. The target node is known to
 512   // reach all other nodes in the original SCC by definition. This means that
 513   // we want the old SCC to be replaced with an SCC contaning that node as it
 514   // will be the root of whatever SCC DAG results from the DFS. Assumptions
 515   // about an SCC such as the set of functions called will continue to hold,
 516   // etc.
 517
 518   SCC &OldSCC = TargetSCC;
 519   SmallVector<std::pair<Node *, call_edge_iterator>, 16> DFSStack;
 520   SmallVector<Node *, 16> PendingSCCStack;
 521   SmallVector<SCC *, 4> NewSCCs;
 522
 523   // Prepare the nodes for a fresh DFS.
 524   SmallVector<Node *, 16> Worklist;
 525   Worklist.swap(OldSCC.Nodes);
 526   for (Node *N : Worklist) {
 527     N->DFSNumber = N->LowLink = 0;
 528     G->SCCMap.erase(N);
 529   }
 530
 531   // Force the target node to be in the old SCC. This also enables us to take
 532   // a very significant short-cut in the standard Tarjan walk to re-form SCCs
 533   // below: whenever we build an edge that reaches the target node, we know
 534   // that the target node eventually connects back to all other nodes in our
 535   // walk. As a consequence, we can detect and handle participants in that
 536   // cycle without walking all the edges that form this connection, and instead
 537   // by relying on the fundamental guarantee coming into this operation (all
 538   // nodes are reachable from the target due to previously forming an SCC).
 539   TargetN.DFSNumber = TargetN.LowLink = -1;
 540   OldSCC.Nodes.push_back(&TargetN);
 541   G->SCCMap[&TargetN] = &OldSCC;
 542
 543   // Scan down the stack and DFS across the call edges.
 544   for (Node *RootN : Worklist) {
 545     assert(DFSStack.empty() &&
 546            "Cannot begin a new root with a non-empty DFS stack!");
 547     assert(PendingSCCStack.empty() &&
 548            "Cannot begin a new root with pending nodes for an SCC!");
 549
 550     // Skip any nodes we've already reached in the DFS.
 551     if (RootN->DFSNumber != 0) {
 552       assert(RootN->DFSNumber == -1 &&
 553              "Shouldn't have any mid-DFS root nodes!");
 554       continue;
 555     }
 556
 557     RootN->DFSNumber = RootN->LowLink = 1;
 558     int NextDFSNumber = 2;
 559
 560     DFSStack.push_back({RootN, RootN->call_begin()});
 561     do {
 562       Node *N;
 563       call_edge_iterator I;
 564       std::tie(N, I) = DFSStack.pop_back_val();
 565       auto E = N->call_end();
 566       while (I != E) {
 567         Node &ChildN = *I->getNode();
 568         if (ChildN.DFSNumber == 0) {
 569           // We haven't yet visited this child, so descend, pushing the current
 570           // node onto the stack.
 571           DFSStack.push_back({N, I});
 572
 573           assert(!G->SCCMap.count(&ChildN) &&
 574                  "Found a node with 0 DFS number but already in an SCC!");
 575           ChildN.DFSNumber = ChildN.LowLink = NextDFSNumber++;
 576           N = &ChildN;
 577           I = N->call_begin();
 578           E = N->call_end();
 579           continue;
 580         }
 581
 582         // Check for the child already being part of some component.
 583         if (ChildN.DFSNumber == -1) {
 584           if (G->lookupSCC(ChildN) == &OldSCC) {
 585             // If the child is part of the old SCC, we know that it can reach
 586             // every other node, so we have formed a cycle. Pull the entire DFS
 587             // and pending stacks into it. See the comment above about setting
 588             // up the old SCC for why we do this.
 589             int OldSize = OldSCC.size();
 590             OldSCC.Nodes.push_back(N);
 591             OldSCC.Nodes.append(PendingSCCStack.begin(), PendingSCCStack.end());
 592             PendingSCCStack.clear();
 593             while (!DFSStack.empty())
 594               OldSCC.Nodes.push_back(DFSStack.pop_back_val().first);
 595             for (Node &N : make_range(OldSCC.begin() + OldSize, OldSCC.end())) {
 596               N.DFSNumber = N.LowLink = -1;
 597               G->SCCMap[&N] = &OldSCC;
 598             }
 599             N = nullptr;
 600             break;
 601           }
 602
 603           // If the child has already been added to some child component, it
 604           // couldn't impact the low-link of this parent because it isn't
 605           // connected, and thus its low-link isn't relevant so skip it.
 606           ++I;
 607           continue;
 608         }
 609
 610         // Track the lowest linked child as the lowest link for this node.
 611         assert(ChildN.LowLink > 0 && "Must have a positive low-link number!");
 612         if (ChildN.LowLink < N->LowLink)
 613           N->LowLink = ChildN.LowLink;
 614
 615         // Move to the next edge.
 616         ++I;
 617       }
 618       if (!N)
 619         // Cleared the DFS early, start another round.
 620         break;
 621
 622       // We've finished processing N and its descendents, put it on our pending
 623       // SCC stack to eventually get merged into an SCC of nodes.
 624       PendingSCCStack.push_back(N);
 625
 626       // If this node is linked to some lower entry, continue walking up the
 627       // stack.
 628       if (N->LowLink != N->DFSNumber)
 629         continue;
 630
 631       // Otherwise, we've completed an SCC. Append it to our post order list of
 632       // SCCs.
 633       int RootDFSNumber = N->DFSNumber;
 634       // Find the range of the node stack by walking down until we pass the
 635       // root DFS number.
 636       auto SCCNodes = make_range(
 637           PendingSCCStack.rbegin(),
 638           std::find_if(PendingSCCStack.rbegin(), PendingSCCStack.rend(),
 639                        [RootDFSNumber](Node *N) {
 640                          return N->DFSNumber < RootDFSNumber;
 641                        }));
 642
 643       // Form a new SCC out of these nodes and then clear them off our pending
 644       // stack.
 645       NewSCCs.push_back(G->createSCC(*this, SCCNodes));
 646       for (Node &N : *NewSCCs.back()) {
 647         N.DFSNumber = N.LowLink = -1;
 648         G->SCCMap[&N] = NewSCCs.back();
 649       }
 650       PendingSCCStack.erase(SCCNodes.end().base(), PendingSCCStack.end());
 651     } while (!DFSStack.empty());
 652   }
 653
 654   // Insert the remaining SCCs before the old one. The old SCC can reach all
 655   // other SCCs we form because it contains the target node of the removed edge
 656   // of the old SCC. This means that we will have edges into all of the new
 657   // SCCs, which means the old one must come last for postorder.
 658   int OldIdx = SCCIndices[&OldSCC];
 659   SCCs.insert(SCCs.begin() + OldIdx, NewSCCs.begin(), NewSCCs.end());
 660
 661   // Update the mapping from SCC* to index to use the new SCC*s, and remove the
 662   // old SCC from the mapping.
 663   for (int Idx = OldIdx, Size = SCCs.size(); Idx < Size; ++Idx)
 664     SCCIndices[SCCs[Idx]] = Idx;
 665
 666 #ifndef NDEBUG
 667   // We're done. Check the validity on our way out.
 668   verify();
 669 #endif
 670 }
 671
 672 void LazyCallGraph::RefSCC::switchOutgoingEdgeToCall(Node &SourceN,
 673                                                      Node &TargetN) {
 674   assert(!SourceN[TargetN].isCall() && "Must start with a ref edge!");
 675
 676   assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC.");
 677   assert(G->lookupRefSCC(TargetN) != this &&
 678          "Target must not be in this RefSCC.");
 679   assert(G->lookupRefSCC(TargetN)->isDescendantOf(*this) &&
 680          "Target must be a descendant of the Source.");
 681
 682   // Edges between RefSCCs are the same regardless of call or ref, so we can
 683   // just flip the edge here.
 684   SourceN.setEdgeKind(TargetN.getFunction(), Edge::Call);
 685
 686 #ifndef NDEBUG
 687   // Check that the RefSCC is still valid.
 688   verify();
 689 #endif
 690 }
 691
 692 void LazyCallGraph::RefSCC::switchOutgoingEdgeToRef(Node &SourceN,
 693                                                     Node &TargetN) {
 694   assert(SourceN[TargetN].isCall() && "Must start with a call edge!");
 695
 696   assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC.");
 697   assert(G->lookupRefSCC(TargetN) != this &&
 698          "Target must not be in this RefSCC.");
 699   assert(G->lookupRefSCC(TargetN)->isDescendantOf(*this) &&
 700          "Target must be a descendant of the Source.");
 701
 702   // Edges between RefSCCs are the same regardless of call or ref, so we can
 703   // just flip the edge here.
 704   SourceN.setEdgeKind(TargetN.getFunction(), Edge::Ref);
 705
 706 #ifndef NDEBUG
 707   // Check that the RefSCC is still valid.
 708   verify();
 709 #endif
 710 }
 711
 712 void LazyCallGraph::RefSCC::insertInternalRefEdge(Node &SourceN,
 713                                                   Node &TargetN) {
 714   assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC.");
 715   assert(G->lookupRefSCC(TargetN) == this && "Target must be in this RefSCC.");
 716
 717   SourceN.insertEdgeInternal(TargetN, Edge::Ref);
 718
 719 #ifndef NDEBUG
 720   // Check that the RefSCC is still valid.
 721   verify();
 722 #endif
 723 }
 724
 725 void LazyCallGraph::RefSCC::insertOutgoingEdge(Node &SourceN, Node &TargetN,
 726                                                Edge::Kind EK) {
 727   // First insert it into the caller.
 728   SourceN.insertEdgeInternal(TargetN, EK);
 729
 730   assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC.");
 731
 732   RefSCC &TargetC = *G->lookupRefSCC(TargetN);
 733   assert(&TargetC != this && "Target must not be in this RefSCC.");
 734   assert(TargetC.isDescendantOf(*this) &&
 735          "Target must be a descendant of the Source.");
 736
 737   // The only change required is to add this SCC to the parent set of the
 738   // callee.
 739   TargetC.Parents.insert(this);
 740
 741 #ifndef NDEBUG
 742   // Check that the RefSCC is still valid.
 743   verify();
 744 #endif
 745 }
 746
 747 SmallVector<LazyCallGraph::RefSCC *, 1>
 748 LazyCallGraph::RefSCC::insertIncomingRefEdge(Node &SourceN, Node &TargetN) {
 749   assert(G->lookupRefSCC(TargetN) == this && "Target must be in this SCC.");
 750
 751   // We store the RefSCCs found to be connected in postorder so that we can use
 752   // that when merging. We also return this to the caller to allow them to
 753   // invalidate information pertaining to these RefSCCs.
 754   SmallVector<RefSCC *, 1> Connected;
 755
 756   RefSCC &SourceC = *G->lookupRefSCC(SourceN);
 757   assert(&SourceC != this && "Source must not be in this SCC.");
 758   assert(SourceC.isDescendantOf(*this) &&
 759          "Source must be a descendant of the Target.");
 760
 761   // The algorithm we use for merging SCCs based on the cycle introduced here
 762   // is to walk the RefSCC inverted DAG formed by the parent sets. The inverse
 763   // graph has the same cycle properties as the actual DAG of the RefSCCs, and
 764   // when forming RefSCCs lazily by a DFS, the bottom of the graph won't exist
 765   // in many cases which should prune the search space.
 766   //
 767   // FIXME: We can get this pruning behavior even after the incremental RefSCC
 768   // formation by leaving behind (conservative) DFS numberings in the nodes,
 769   // and pruning the search with them. These would need to be cleverly updated
 770   // during the removal of intra-SCC edges, but could be preserved
 771   // conservatively.
 772   //
 773   // FIXME: This operation currently creates ordering stability problems
 774   // because we don't use stably ordered containers for the parent SCCs.
 775
 776   // The set of RefSCCs that are connected to the parent, and thus will
 777   // participate in the merged connected component.
 778   SmallPtrSet<RefSCC *, 8> ConnectedSet;
 779   ConnectedSet.insert(this);
 780
 781   // We build up a DFS stack of the parents chains.
 782   SmallVector<std::pair<RefSCC *, parent_iterator>, 8> DFSStack;
 783   SmallPtrSet<RefSCC *, 8> Visited;
 784   int ConnectedDepth = -1;
 785   DFSStack.push_back({&SourceC, SourceC.parent_begin()});
 786   do {
 787     auto DFSPair = DFSStack.pop_back_val();
 788     RefSCC *C = DFSPair.first;
 789     parent_iterator I = DFSPair.second;
 790     auto E = C->parent_end();
 791
 792     while (I != E) {
 793       RefSCC &Parent = *I++;
 794
 795       // If we have already processed this parent SCC, skip it, and remember
 796       // whether it was connected so we don't have to check the rest of the
 797       // stack. This also handles when we reach a child of the 'this' SCC (the
 798       // callee) which terminates the search.
 799       if (ConnectedSet.count(&Parent)) {
 800         assert(ConnectedDepth < (int)DFSStack.size() &&
 801                "Cannot have a connected depth greater than the DFS depth!");
 802         ConnectedDepth = DFSStack.size();
 803         continue;
 804       }
 805       if (Visited.count(&Parent))
 806         continue;
 807
 808       // We fully explore the depth-first space, adding nodes to the connected
 809       // set only as we pop them off, so "recurse" by rotating to the parent.
 810       DFSStack.push_back({C, I});
 811       C = &Parent;
 812       I = C->parent_begin();
 813       E = C->parent_end();
 814     }
 815
 816     // If we've found a connection anywhere below this point on the stack (and
 817     // thus up the parent graph from the caller), the current node needs to be
 818     // added to the connected set now that we've processed all of its parents.
 819     if ((int)DFSStack.size() == ConnectedDepth) {
 820       --ConnectedDepth; // We're finished with this connection.
 821       bool Inserted = ConnectedSet.insert(C).second;
 822       (void)Inserted;
 823       assert(Inserted && "Cannot insert a refSCC multiple times!");
 824       Connected.push_back(C);
 825     } else {
 826       // Otherwise remember that its parents don't ever connect.
 827       assert(ConnectedDepth < (int)DFSStack.size() &&
 828              "Cannot have a connected depth greater than the DFS depth!");
 829       Visited.insert(C);
 830     }
 831   } while (!DFSStack.empty());
 832
 833   // Now that we have identified all of the SCCs which need to be merged into
 834   // a connected set with the inserted edge, merge all of them into this SCC.
 835   // We walk the newly connected RefSCCs in the reverse postorder of the parent
 836   // DAG walk above and merge in each of their SCC postorder lists. This
 837   // ensures a merged postorder SCC list.
 838   SmallVector<SCC *, 16> MergedSCCs;
 839   int SCCIndex = 0;
 840   for (RefSCC *C : reverse(Connected)) {
 841     assert(C != this &&
 842            "This RefSCC should terminate the DFS without being reached.");
 843
 844     // Merge the parents which aren't part of the merge into the our parents.
 845     for (RefSCC *ParentC : C->Parents)
 846       if (!ConnectedSet.count(ParentC))
 847         Parents.insert(ParentC);
 848     C->Parents.clear();
 849
 850     // Walk the inner SCCs to update their up-pointer and walk all the edges to
 851     // update any parent sets.
 852     // FIXME: We should try to find a way to avoid this (rather expensive) edge
 853     // walk by updating the parent sets in some other manner.
 854     for (SCC &InnerC : *C) {
 855       InnerC.OuterRefSCC = this;
 856       SCCIndices[&InnerC] = SCCIndex++;
 857       for (Node &N : InnerC) {
 858         G->SCCMap[&N] = &InnerC;
 859         for (Edge &E : N) {
 860           assert(E.getNode() &&
 861                  "Cannot have a null node within a visited SCC!");
 862           RefSCC &ChildRC = *G->lookupRefSCC(*E.getNode());
 863           if (ConnectedSet.count(&ChildRC))
 864             continue;
 865           ChildRC.Parents.erase(C);
 866           ChildRC.Parents.insert(this);
 867         }
 868       }
 869     }
 870
 871     // Now merge in the SCCs. We can actually move here so try to reuse storage
 872     // the first time through.
 873     if (MergedSCCs.empty())
 874       MergedSCCs = std::move(C->SCCs);
 875     else
 876       MergedSCCs.append(C->SCCs.begin(), C->SCCs.end());
 877     C->SCCs.clear();
 878   }
 879
 880   // Finally append our original SCCs to the merged list and move it into
 881   // place.
 882   for (SCC &InnerC : *this)
 883     SCCIndices[&InnerC] = SCCIndex++;
 884   MergedSCCs.append(SCCs.begin(), SCCs.end());
 885   SCCs = std::move(MergedSCCs);
 886
 887   // At this point we have a merged RefSCC with a post-order SCCs list, just
 888   // connect the nodes to form the new edge.
 889   SourceN.insertEdgeInternal(TargetN, Edge::Ref);
 890
 891 #ifndef NDEBUG
 892   // Check that the RefSCC is still valid.
 893   verify();
 894 #endif
 895
 896   // We return the list of SCCs which were merged so that callers can
 897   // invalidate any data they have associated with those SCCs. Note that these
 898   // SCCs are no longer in an interesting state (they are totally empty) but
 899   // the pointers will remain stable for the life of the graph itself.
 900   return Connected;
 901 }
 902
 903 void LazyCallGraph::RefSCC::removeOutgoingEdge(Node &SourceN, Node &TargetN) {
 904   assert(G->lookupRefSCC(SourceN) == this &&
 905          "The source must be a member of this RefSCC.");
 906
 907   RefSCC &TargetRC = *G->lookupRefSCC(TargetN);
 908   assert(&TargetRC != this && "The target must not be a member of this RefSCC");
 909
 910   assert(std::find(G->LeafRefSCCs.begin(), G->LeafRefSCCs.end(), this) ==
 911              G->LeafRefSCCs.end() &&
 912          "Cannot have a leaf RefSCC source.");
 913
 914   // First remove it from the node.
 915   SourceN.removeEdgeInternal(TargetN.getFunction());
 916
 917   bool HasOtherEdgeToChildRC = false;
 918   bool HasOtherChildRC = false;
 919   for (SCC *InnerC : SCCs) {
 920     for (Node &N : *InnerC) {
 921       for (Edge &E : N) {
 922         assert(E.getNode() && "Cannot have a missing node in a visited SCC!");
 923         RefSCC &OtherChildRC = *G->lookupRefSCC(*E.getNode());
 924         if (&OtherChildRC == &TargetRC) {
 925           HasOtherEdgeToChildRC = true;
 926           break;
 927         }
 928         if (&OtherChildRC != this)
 929           HasOtherChildRC = true;
 930       }
 931       if (HasOtherEdgeToChildRC)
 932         break;
 933     }
 934     if (HasOtherEdgeToChildRC)
 935       break;
 936   }
 937   // Because the SCCs form a DAG, deleting such an edge cannot change the set
 938   // of SCCs in the graph. However, it may cut an edge of the SCC DAG, making
 939   // the source SCC no longer connected to the target SCC. If so, we need to
 940   // update the target SCC's map of its parents.
 941   if (!HasOtherEdgeToChildRC) {
 942     bool Removed = TargetRC.Parents.erase(this);
 943     (void)Removed;
 944     assert(Removed &&
 945            "Did not find the source SCC in the target SCC's parent list!");
 946
 947     // It may orphan an SCC if it is the last edge reaching it, but that does
 948     // not violate any invariants of the graph.
 949     if (TargetRC.Parents.empty())
 950       DEBUG(dbgs() << "LCG: Update removing " << SourceN.getFunction().getName()
 951                    << " -> " << TargetN.getFunction().getName()
 952                    << " edge orphaned the callee's SCC!\n");
 953
 954     // It may make the Source SCC a leaf SCC.
 955     if (!HasOtherChildRC)
 956       G->LeafRefSCCs.push_back(this);
 957   }
 958 }
 959
 960 SmallVector<LazyCallGraph::RefSCC *, 1>
 961 LazyCallGraph::RefSCC::removeInternalRefEdge(Node &SourceN, Node &TargetN) {
 962   assert(!SourceN[TargetN].isCall() &&
 963          "Cannot remove a call edge, it must first be made a ref edge");
 964
 965   // First remove the actual edge.
 966   SourceN.removeEdgeInternal(TargetN.getFunction());
 967
 968   // We return a list of the resulting *new* RefSCCs in post-order.
 969   SmallVector<RefSCC *, 1> Result;
 970
 971   // Direct recursion doesn't impact the SCC graph at all.
 972   if (&SourceN == &TargetN)
 973     return Result;
 974
 975   // We build somewhat synthetic new RefSCCs by providing a postorder mapping
 976   // for each inner SCC. We also store these associated with *nodes* rather
 977   // than SCCs because this saves a round-trip through the node->SCC map and in
 978   // the common case, SCCs are small. We will verify that we always give the
 979   // same number to every node in the SCC such that these are equivalent.
 980   const int RootPostOrderNumber = 0;
 981   int PostOrderNumber = RootPostOrderNumber + 1;
 982   SmallDenseMap<Node *, int> PostOrderMapping;
 983
 984   // Every node in the target SCC can already reach every node in this RefSCC
 985   // (by definition). It is the only node we know will stay inside this RefSCC.
 986   // Everything which transitively reaches Target will also remain in the
 987   // RefSCC. We handle this by pre-marking that the nodes in the target SCC map
 988   // back to the root post order number.
 989   //
 990   // This also enables us to take a very significant short-cut in the standard
 991   // Tarjan walk to re-form RefSCCs below: whenever we build an edge that
 992   // references the target node, we know that the target node eventually
 993   // references all other nodes in our walk. As a consequence, we can detect
 994   // and handle participants in that cycle without walking all the edges that
 995   // form the connections, and instead by relying on the fundamental guarantee
 996   // coming into this operation.
 997   SCC &TargetC = *G->lookupSCC(TargetN);
 998   for (Node &N : TargetC)
 999     PostOrderMapping[&N] = RootPostOrderNumber;
1000
1001   // Reset all the other nodes to prepare for a DFS over them, and add them to
1002   // our worklist.
1003   SmallVector<Node *, 8> Worklist;
1004   for (SCC *C : SCCs) {
1005     if (C == &TargetC)
1006       continue;
1007
1008     for (Node &N : *C)
1009       N.DFSNumber = N.LowLink = 0;
1010
1011     Worklist.append(C->Nodes.begin(), C->Nodes.end());
1012   }
1013
1014   auto MarkNodeForSCCNumber = [&PostOrderMapping](Node &N, int Number) {
1015     N.DFSNumber = N.LowLink = -1;
1016     PostOrderMapping[&N] = Number;
1017   };
1018
1019   SmallVector<std::pair<Node *, edge_iterator>, 4> DFSStack;
1020   SmallVector<Node *, 4> PendingRefSCCStack;
1021   do {
1022     assert(DFSStack.empty() &&
1023            "Cannot begin a new root with a non-empty DFS stack!");
1024     assert(PendingRefSCCStack.empty() &&
1025            "Cannot begin a new root with pending nodes for an SCC!");
1026
1027     Node *RootN = Worklist.pop_back_val();
1028     // Skip any nodes we've already reached in the DFS.
1029     if (RootN->DFSNumber != 0) {
1030       assert(RootN->DFSNumber == -1 &&
1031              "Shouldn't have any mid-DFS root nodes!");
1032       continue;
1033     }
1034
1035     RootN->DFSNumber = RootN->LowLink = 1;
1036     int NextDFSNumber = 2;
1037
1038     DFSStack.push_back({RootN, RootN->begin()});
1039     do {
1040       Node *N;
1041       edge_iterator I;
1042       std::tie(N, I) = DFSStack.pop_back_val();
1043       auto E = N->end();
1044
1045       assert(N->DFSNumber != 0 && "We should always assign a DFS number "
1046                                   "before processing a node.");
1047
1048       while (I != E) {
1049         Node &ChildN = I->getNode(*G);
1050         if (ChildN.DFSNumber == 0) {
1051           // Mark that we should start at this child when next this node is the
1052           // top of the stack. We don't start at the next child to ensure this
1053           // child's lowlink is reflected.
1054           DFSStack.push_back({N, I});
1055
1056           // Continue, resetting to the child node.
1057           ChildN.LowLink = ChildN.DFSNumber = NextDFSNumber++;
1058           N = &ChildN;
1059           I = ChildN.begin();
1060           E = ChildN.end();
1061           continue;
1062         }
1063         if (ChildN.DFSNumber == -1) {
1064           // Check if this edge's target node connects to the deleted edge's
1065           // target node. If so, we know that every node connected will end up
1066           // in this RefSCC, so collapse the entire current stack into the root
1067           // slot in our SCC numbering. See above for the motivation of
1068           // optimizing the target connected nodes in this way.
1069           auto PostOrderI = PostOrderMapping.find(&ChildN);
1070           if (PostOrderI != PostOrderMapping.end() &&
1071               PostOrderI->second == RootPostOrderNumber) {
1072             MarkNodeForSCCNumber(*N, RootPostOrderNumber);
1073             while (!PendingRefSCCStack.empty())
1074               MarkNodeForSCCNumber(*PendingRefSCCStack.pop_back_val(),
1075                                    RootPostOrderNumber);
1076             while (!DFSStack.empty())
1077               MarkNodeForSCCNumber(*DFSStack.pop_back_val().first,
1078                                    RootPostOrderNumber);
1079             // Ensure we break all the way out of the enclosing loop.
1080             N = nullptr;
1081             break;
1082           }
1083
1084           // If this child isn't currently in this RefSCC, no need to process
1085           // it.
1086           // However, we do need to remove this RefSCC from its RefSCC's parent
1087           // set.
1088           RefSCC &ChildRC = *G->lookupRefSCC(ChildN);
1089           ChildRC.Parents.erase(this);
1090           ++I;
1091           continue;
1092         }
1093
1094         // Track the lowest link of the children, if any are still in the stack.
1095         // Any child not on the stack will have a LowLink of -1.
1096         assert(ChildN.LowLink != 0 &&
1097                "Low-link must not be zero with a non-zero DFS number.");
1098         if (ChildN.LowLink >= 0 && ChildN.LowLink < N->LowLink)
1099           N->LowLink = ChildN.LowLink;
1100         ++I;
1101       }
1102       if (!N)
1103         // We short-circuited this node.
1104         break;
1105
1106       // We've finished processing N and its descendents, put it on our pending
1107       // stack to eventually get merged into a RefSCC.
1108       PendingRefSCCStack.push_back(N);
1109
1110       // If this node is linked to some lower entry, continue walking up the
1111       // stack.
1112       if (N->LowLink != N->DFSNumber) {
1113         assert(!DFSStack.empty() &&
1114                "We never found a viable root for a RefSCC to pop off!");
1115         continue;
1116       }
1117
1118       // Otherwise, form a new RefSCC from the top of the pending node stack.
1119       int RootDFSNumber = N->DFSNumber;
1120       // Find the range of the node stack by walking down until we pass the
1121       // root DFS number.
1122       auto RefSCCNodes = make_range(
1123           PendingRefSCCStack.rbegin(),
1124           std::find_if(PendingRefSCCStack.rbegin(), PendingRefSCCStack.rend(),
1125                        [RootDFSNumber](Node *N) {
1126                          return N->DFSNumber < RootDFSNumber;
1127                        }));
1128
1129       // Mark the postorder number for these nodes and clear them off the
1130       // stack. We'll use the postorder number to pull them into RefSCCs at the
1131       // end. FIXME: Fuse with the loop above.
1132       int RefSCCNumber = PostOrderNumber++;
1133       for (Node *N : RefSCCNodes)
1134         MarkNodeForSCCNumber(*N, RefSCCNumber);
1135
1136       PendingRefSCCStack.erase(RefSCCNodes.end().base(),
1137                                PendingRefSCCStack.end());
1138     } while (!DFSStack.empty());
1139
1140     assert(DFSStack.empty() && "Didn't flush the entire DFS stack!");
1141     assert(PendingRefSCCStack.empty() && "Didn't flush all pending nodes!");
1142   } while (!Worklist.empty());
1143
1144   // We now have a post-order numbering for RefSCCs and a mapping from each
1145   // node in this RefSCC to its final RefSCC. We create each new RefSCC node
1146   // (re-using this RefSCC node for the root) and build a radix-sort style map
1147   // from postorder number to the RefSCC. We then append SCCs to each of these
1148   // RefSCCs in the order they occured in the original SCCs container.
1149   for (int i = 1; i < PostOrderNumber; ++i)
1150     Result.push_back(G->createRefSCC(*G));
1151
1152   for (SCC *C : SCCs) {
1153     auto PostOrderI = PostOrderMapping.find(&*C->begin());
1154     assert(PostOrderI != PostOrderMapping.end() &&
1155            "Cannot have missing mappings for nodes!");
1156     int SCCNumber = PostOrderI->second;
1157 #ifndef NDEBUG
1158     for (Node &N : *C)
1159       assert(PostOrderMapping.find(&N)->second == SCCNumber &&
1160              "Cannot have different numbers for nodes in the same SCC!");
1161 #endif
1162     if (SCCNumber == 0)
1163       // The root node is handled separately by removing the SCCs.
1164       continue;
1165
1166     RefSCC &RC = *Result[SCCNumber - 1];
1167     int SCCIndex = RC.SCCs.size();
1168     RC.SCCs.push_back(C);
1169     SCCIndices[C] = SCCIndex;
1170     C->OuterRefSCC = &RC;
1171   }
1172
1173   // FIXME: We re-walk the edges in each RefSCC to establish whether it is
1174   // a leaf and connect it to the rest of the graph's parents lists. This is
1175   // really wasteful. We should instead do this during the DFS to avoid yet
1176   // another edge walk.
1177   for (RefSCC *RC : Result)
1178     G->connectRefSCC(*RC);
1179
1180   // Now erase all but the root's SCCs.
1181   SCCs.erase(std::remove_if(SCCs.begin(), SCCs.end(),
1182                             [&](SCC *C) {
1183                               return PostOrderMapping.lookup(&*C->begin()) !=
1184                                      RootPostOrderNumber;
1185                             }),
1186              SCCs.end());
1187
1188 #ifndef NDEBUG
1189   // Now we need to reconnect the current (root) SCC to the graph. We do this
1190   // manually because we can special case our leaf handling and detect errors.
1191   bool IsLeaf = true;
1192 #endif
1193   for (SCC *C : SCCs)
1194     for (Node &N : *C) {
1195       for (Edge &E : N) {
1196         assert(E.getNode() && "Cannot have a missing node in a visited SCC!");
1197         RefSCC &ChildRC = *G->lookupRefSCC(*E.getNode());
1198         if (&ChildRC == this)
1199           continue;
1200         ChildRC.Parents.insert(this);
1201 #ifndef NDEBUG
1202         IsLeaf = false;
1203 #endif
1204       }
1205     }
1206 #ifndef NDEBUG
1207   if (!Result.empty())
1208     assert(!IsLeaf && "This SCC cannot be a leaf as we have split out new "
1209                       "SCCs by removing this edge.");
1210   if (!std::any_of(G->LeafRefSCCs.begin(), G->LeafRefSCCs.end(),
1211                    [&](RefSCC *C) { return C == this; }))
1212     assert(!IsLeaf && "This SCC cannot be a leaf as it already had child "
1213                       "SCCs before we removed this edge.");
1214 #endif
1215   // If this SCC stopped being a leaf through this edge removal, remove it from
1216   // the leaf SCC list. Note that this DTRT in the case where this was never
1217   // a leaf.
1218   // FIXME: As LeafRefSCCs could be very large, we might want to not walk the
1219   // entire list if this RefSCC wasn't a leaf before the edge removal.
1220   if (!Result.empty())
1221     G->LeafRefSCCs.erase(
1222         std::remove(G->LeafRefSCCs.begin(), G->LeafRefSCCs.end(), this),
1223         G->LeafRefSCCs.end());
1224
1225   // Return the new list of SCCs.
1226   return Result;
1227 }
1228
1229 void LazyCallGraph::insertEdge(Node &SourceN, Function &Target, Edge::Kind EK) {
1230   assert(SCCMap.empty() && DFSStack.empty() &&
1231          "This method cannot be called after SCCs have been formed!");
1232
1233   return SourceN.insertEdgeInternal(Target, EK);
1234 }
1235
1236 void LazyCallGraph::removeEdge(Node &SourceN, Function &Target) {
1237   assert(SCCMap.empty() && DFSStack.empty() &&
1238          "This method cannot be called after SCCs have been formed!");
1239
1240   return SourceN.removeEdgeInternal(Target);
1241 }
1242
1243 LazyCallGraph::Node &LazyCallGraph::insertInto(Function &F, Node *&MappedN) {
1244   return *new (MappedN = BPA.Allocate()) Node(*this, F);
1245 }
1246
1247 void LazyCallGraph::updateGraphPtrs() {
1248   // Process all nodes updating the graph pointers.
1249   {
1250     SmallVector<Node *, 16> Worklist;
1251     for (Edge &E : EntryEdges)
1252       if (Node *EntryN = E.getNode())
1253         Worklist.push_back(EntryN);
1254
1255     while (!Worklist.empty()) {
1256       Node *N = Worklist.pop_back_val();
1257       N->G = this;
1258       for (Edge &E : N->Edges)
1259         if (Node *TargetN = E.getNode())
1260           Worklist.push_back(TargetN);
1261     }
1262   }
1263
1264   // Process all SCCs updating the graph pointers.
1265   {
1266     SmallVector<RefSCC *, 16> Worklist(LeafRefSCCs.begin(), LeafRefSCCs.end());
1267
1268     while (!Worklist.empty()) {
1269       RefSCC &C = *Worklist.pop_back_val();
1270       C.G = this;
1271       for (RefSCC &ParentC : C.parents())
1272         Worklist.push_back(&ParentC);
1273     }
1274   }
1275 }
1276
1277 /// Build the internal SCCs for a RefSCC from a sequence of nodes.
1278 ///
1279 /// Appends the SCCs to the provided vector and updates the map with their
1280 /// indices. Both the vector and map must be empty when passed into this
1281 /// routine.
1282 void LazyCallGraph::buildSCCs(RefSCC &RC, node_stack_range Nodes) {
1283   assert(RC.SCCs.empty() && "Already built SCCs!");
1284   assert(RC.SCCIndices.empty() && "Already mapped SCC indices!");
1285
1286   for (Node *N : Nodes) {
1287     assert(N->LowLink >= (*Nodes.begin())->LowLink &&
1288            "We cannot have a low link in an SCC lower than its root on the "
1289            "stack!");
1290
1291     // This node will go into the next RefSCC, clear out its DFS and low link
1292     // as we scan.
1293     N->DFSNumber = N->LowLink = 0;
1294   }
1295
1296   // Each RefSCC contains a DAG of the call SCCs. To build these, we do
1297   // a direct walk of the call edges using Tarjan's algorithm. We reuse the
1298   // internal storage as we won't need it for the outer graph's DFS any longer.
1299
1300   SmallVector<std::pair<Node *, call_edge_iterator>, 16> DFSStack;
1301   SmallVector<Node *, 16> PendingSCCStack;
1302
1303   // Scan down the stack and DFS across the call edges.
1304   for (Node *RootN : Nodes) {
1305     assert(DFSStack.empty() &&
1306            "Cannot begin a new root with a non-empty DFS stack!");
1307     assert(PendingSCCStack.empty() &&
1308            "Cannot begin a new root with pending nodes for an SCC!");
1309
1310     // Skip any nodes we've already reached in the DFS.
1311     if (RootN->DFSNumber != 0) {
1312       assert(RootN->DFSNumber == -1 &&
1313              "Shouldn't have any mid-DFS root nodes!");
1314       continue;
1315     }
1316
1317     RootN->DFSNumber = RootN->LowLink = 1;
1318     int NextDFSNumber = 2;
1319
1320     DFSStack.push_back({RootN, RootN->call_begin()});
1321     do {
1322       Node *N;
1323       call_edge_iterator I;
1324       std::tie(N, I) = DFSStack.pop_back_val();
1325       auto E = N->call_end();
1326       while (I != E) {
1327         Node &ChildN = *I->getNode();
1328         if (ChildN.DFSNumber == 0) {
1329           // We haven't yet visited this child, so descend, pushing the current
1330           // node onto the stack.
1331           DFSStack.push_back({N, I});
1332
1333           assert(!lookupSCC(ChildN) &&
1334                  "Found a node with 0 DFS number but already in an SCC!");
1335           ChildN.DFSNumber = ChildN.LowLink = NextDFSNumber++;
1336           N = &ChildN;
1337           I = N->call_begin();
1338           E = N->call_end();
1339           continue;
1340         }
1341
1342         // If the child has already been added to some child component, it
1343         // couldn't impact the low-link of this parent because it isn't
1344         // connected, and thus its low-link isn't relevant so skip it.
1345         if (ChildN.DFSNumber == -1) {
1346           ++I;
1347           continue;
1348         }
1349
1350         // Track the lowest linked child as the lowest link for this node.
1351         assert(ChildN.LowLink > 0 && "Must have a positive low-link number!");
1352         if (ChildN.LowLink < N->LowLink)
1353           N->LowLink = ChildN.LowLink;
1354
1355         // Move to the next edge.
1356         ++I;
1357       }
1358
1359       // We've finished processing N and its descendents, put it on our pending
1360       // SCC stack to eventually get merged into an SCC of nodes.
1361       PendingSCCStack.push_back(N);
1362
1363       // If this node is linked to some lower entry, continue walking up the
1364       // stack.
1365       if (N->LowLink != N->DFSNumber)
1366         continue;
1367
1368       // Otherwise, we've completed an SCC. Append it to our post order list of
1369       // SCCs.
1370       int RootDFSNumber = N->DFSNumber;
1371       // Find the range of the node stack by walking down until we pass the
1372       // root DFS number.
1373       auto SCCNodes = make_range(
1374           PendingSCCStack.rbegin(),
1375           std::find_if(PendingSCCStack.rbegin(), PendingSCCStack.rend(),
1376                        [RootDFSNumber](Node *N) {
1377                          return N->DFSNumber < RootDFSNumber;
1378                        }));
1379       // Form a new SCC out of these nodes and then clear them off our pending
1380       // stack.
1381       RC.SCCs.push_back(createSCC(RC, SCCNodes));
1382       for (Node &N : *RC.SCCs.back()) {
1383         N.DFSNumber = N.LowLink = -1;
1384         SCCMap[&N] = RC.SCCs.back();
1385       }
1386       PendingSCCStack.erase(SCCNodes.end().base(), PendingSCCStack.end());
1387     } while (!DFSStack.empty());
1388   }
1389
1390   // Wire up the SCC indices.
1391   for (int i = 0, Size = RC.SCCs.size(); i < Size; ++i)
1392     RC.SCCIndices[RC.SCCs[i]] = i;
1393 }
1394
1395 // FIXME: We should move callers of this to embed the parent linking and leaf
1396 // tracking into their DFS in order to remove a full walk of all edges.
1397 void LazyCallGraph::connectRefSCC(RefSCC &RC) {
1398   // Walk all edges in the RefSCC (this remains linear as we only do this once
1399   // when we build the RefSCC) to connect it to the parent sets of its
1400   // children.
1401   bool IsLeaf = true;
1402   for (SCC &C : RC)
1403     for (Node &N : C)
1404       for (Edge &E : N) {
1405         assert(E.getNode() &&
1406                "Cannot have a missing node in a visited part of the graph!");
1407         RefSCC &ChildRC = *lookupRefSCC(*E.getNode());
1408         if (&ChildRC == &RC)
1409           continue;
1410         ChildRC.Parents.insert(&RC);
1411         IsLeaf = false;
1412       }
1413
1414   // For the SCCs where we fine no child SCCs, add them to the leaf list.
1415   if (IsLeaf)
1416     LeafRefSCCs.push_back(&RC);
1417 }
1418
1419 LazyCallGraph::RefSCC *LazyCallGraph::getNextRefSCCInPostOrder() {
1420   if (DFSStack.empty()) {
1421     Node *N;
1422     do {
1423       // If we've handled all candidate entry nodes to the SCC forest, we're
1424       // done.
1425       if (RefSCCEntryNodes.empty())
1426         return nullptr;
1427
1428       N = &get(*RefSCCEntryNodes.pop_back_val());
1429     } while (N->DFSNumber != 0);
1430
1431     // Found a new root, begin the DFS here.
1432     N->LowLink = N->DFSNumber = 1;
1433     NextDFSNumber = 2;
1434     DFSStack.push_back({N, N->begin()});
1435   }
1436
1437   for (;;) {
1438     Node *N;
1439     edge_iterator I;
1440     std::tie(N, I) = DFSStack.pop_back_val();
1441
1442     assert(N->DFSNumber > 0 && "We should always assign a DFS number "
1443                                "before placing a node onto the stack.");
1444
1445     auto E = N->end();
1446     while (I != E) {
1447       Node &ChildN = I->getNode(*this);
1448       if (ChildN.DFSNumber == 0) {
1449         // We haven't yet visited this child, so descend, pushing the current
1450         // node onto the stack.
1451         DFSStack.push_back({N, N->begin()});
1452
1453         assert(!SCCMap.count(&ChildN) &&
1454                "Found a node with 0 DFS number but already in an SCC!");
1455         ChildN.LowLink = ChildN.DFSNumber = NextDFSNumber++;
1456         N = &ChildN;
1457         I = N->begin();
1458         E = N->end();
1459         continue;
1460       }
1461
1462       // If the child has already been added to some child component, it
1463       // couldn't impact the low-link of this parent because it isn't
1464       // connected, and thus its low-link isn't relevant so skip it.
1465       if (ChildN.DFSNumber == -1) {
1466         ++I;
1467         continue;
1468       }
1469
1470       // Track the lowest linked child as the lowest link for this node.
1471       assert(ChildN.LowLink > 0 && "Must have a positive low-link number!");
1472       if (ChildN.LowLink < N->LowLink)
1473         N->LowLink = ChildN.LowLink;
1474
1475       // Move to the next edge.
1476       ++I;
1477     }
1478
1479     // We've finished processing N and its descendents, put it on our pending
1480     // SCC stack to eventually get merged into an SCC of nodes.
1481     PendingRefSCCStack.push_back(N);
1482
1483     // If this node is linked to some lower entry, continue walking up the
1484     // stack.
1485     if (N->LowLink != N->DFSNumber) {
1486       assert(!DFSStack.empty() &&
1487              "We never found a viable root for an SCC to pop off!");
1488       continue;
1489     }
1490
1491     // Otherwise, form a new RefSCC from the top of the pending node stack.
1492     int RootDFSNumber = N->DFSNumber;
1493     // Find the range of the node stack by walking down until we pass the
1494     // root DFS number.
1495     auto RefSCCNodes = node_stack_range(
1496         PendingRefSCCStack.rbegin(),
1497         std::find_if(
1498             PendingRefSCCStack.rbegin(), PendingRefSCCStack.rend(),
1499             [RootDFSNumber](Node *N) { return N->DFSNumber < RootDFSNumber; }));
1500     // Form a new RefSCC out of these nodes and then clear them off our pending
1501     // stack.
1502     RefSCC *NewRC = createRefSCC(*this);
1503     buildSCCs(*NewRC, RefSCCNodes);
1504     connectRefSCC(*NewRC);
1505     PendingRefSCCStack.erase(RefSCCNodes.end().base(),
1506                              PendingRefSCCStack.end());
1507
1508     // We return the new node here. This essentially suspends the DFS walk
1509     // until another RefSCC is requested.
1510     return NewRC;
1511   }
1512 }
1513
1514 char LazyCallGraphAnalysis::PassID;
1515
1516 LazyCallGraphPrinterPass::LazyCallGraphPrinterPass(raw_ostream &OS) : OS(OS) {}
1517
1518 static void printNode(raw_ostream &OS, LazyCallGraph::Node &N) {
1519   OS << "  Edges in function: " << N.getFunction().getName() << "\n";
1520   for (const LazyCallGraph::Edge &E : N)
1521     OS << "    " << (E.isCall() ? "call" : "ref ") << " -> "
1522        << E.getFunction().getName() << "\n";
1523
1524   OS << "\n";
1525 }
1526
1527 static void printSCC(raw_ostream &OS, LazyCallGraph::SCC &C) {
1528   ptrdiff_t Size = std::distance(C.begin(), C.end());
1529   OS << "    SCC with " << Size << " functions:\n";
1530
1531   for (LazyCallGraph::Node &N : C)
1532     OS << "      " << N.getFunction().getName() << "\n";
1533 }
1534
1535 static void printRefSCC(raw_ostream &OS, LazyCallGraph::RefSCC &C) {
1536   ptrdiff_t Size = std::distance(C.begin(), C.end());
1537   OS << "  RefSCC with " << Size << " call SCCs:\n";
1538
1539   for (LazyCallGraph::SCC &InnerC : C)
1540     printSCC(OS, InnerC);
1541
1542   OS << "\n";
1543 }
1544
1545 PreservedAnalyses LazyCallGraphPrinterPass::run(Module &M,
1546                                                 ModuleAnalysisManager &AM) {
1547   LazyCallGraph &G = AM.getResult<LazyCallGraphAnalysis>(M);
1548
1549   OS << "Printing the call graph for module: " << M.getModuleIdentifier()
1550      << "\n\n";
1551
1552   for (Function &F : M)
1553     printNode(OS, G.get(F));
1554
1555   for (LazyCallGraph::RefSCC &C : G.postorder_ref_sccs())
1556     printRefSCC(OS, C);
1557
1558   return PreservedAnalyses::all();
1559 }
1560
1561 LazyCallGraphDOTPrinterPass::LazyCallGraphDOTPrinterPass(raw_ostream &OS)
1562     : OS(OS) {}
1563
1564 static void printNodeDOT(raw_ostream &OS, LazyCallGraph::Node &N) {
1565   std::string Name = "\"" + DOT::EscapeString(N.getFunction().getName()) + "\"";
1566
1567   for (const LazyCallGraph::Edge &E : N) {
1568     OS << "  " << Name << " -> \""
1569        << DOT::EscapeString(E.getFunction().getName()) << "\"";
1570     if (!E.isCall()) // It is a ref edge.
1571       OS << " [style=dashed,label=\"ref\"]";
1572     OS << ";\n";
1573   }
1574
1575   OS << "\n";
1576 }
1577
1578 PreservedAnalyses LazyCallGraphDOTPrinterPass::run(Module &M,
1579                                                    ModuleAnalysisManager &AM) {
1580   LazyCallGraph &G = AM.getResult<LazyCallGraphAnalysis>(M);
1581
1582   OS << "digraph \"" << DOT::EscapeString(M.getModuleIdentifier()) << "\" {\n";
1583
1584   for (Function &F : M)
1585     printNodeDOT(OS, G.get(F));
1586
1587   OS << "}\n";
1588
1589   return PreservedAnalyses::all();
1590 }