[PM/LCG] Remove the lazy RefSCC formation from the LazyCallGraph during iteration.

[chandlerc]

Summary

This behavior turns out to be incompatible with ArgPromotion, which can
delete reference edges in distant ancestors of the current SCC. These
reference edges being removed can cause many problems, but the worst
case is when they are part of the lazy in-flight DFS walk forming the
RefSCCs. When this happens we have no really good ways of updating
everything.

However, the lazy formation of RefSCCs isn't really the most important
part of the laziness here -- that has to do with walking the functions
themselves -- and isn't essential to maintain. Originally, there were
incremental update algorithms that relied on updates happening
predominantly near the most recent RefSCC formed, but those have been
replaced with ones that have much tighter general case bounds at this
point. So we can simplify the entire analysis by having a single
up-front step that builds all of the RefSCCs in a direct Tarjan walk. We
can even easily replace this with other or better algorithms at will and
with much less confusion now that there is no iterator-based incremental
logic involved. This removes a substantial amount of complexity from LCG
and also gives us an easy way to implement ArgPromote -- we already
support removing edges and doing incremental graph updates. In fact,
updates for removing edges are among the most simple cases.

Another advantage of moving in this direction is that it simplifies
testing the system substantially as we no longer have to worry about
observing and mutating the graph half-way through the RefSCC formation.

We still need a somewhat special iterator for RefSCCs because we want
the iterator to remain stable in the face of graph updates. However,
this now merely involves relative indexing to the current RefSCC's
position in the sequence which isn't too hard.

I've used this in a prototype of a more thorough port of ArgPromotion and it
seems to be working well. That part needs a bit more work though to fully
handle the updates and this seems usefully separable.

Depends on D29277.

[chandlerc]

Update to base on plain master where it can be submitted and remove discussion
of ArgPromote. Also updated to fix a scaling issue by putting some very
expensive asserts behind the appropriate macro guard.

After some experiments I'm going to port ArgPromote in a different way than
anticipated which makes this patch not *strictly* necessary, but a huge
improvement anyways.

[davide]

I personally like this solution as it strips away a lot of complexity. Some comments while I do some testing on this patch.

include/llvm/Analysis/LazyCallGraph.h

1082–1086

I think this API deserves a comment, also for consistency with everything else in the file.

lib/Analysis/LazyCallGraph.cpp

1691–1692

Commented code?

1786

s/bulit/built/

1795–1796

Comment on why you need this reverse, maybe?

1808–1809

"Push the new node into the postorder list " ...
I would also add the fact you're inserting in the indices map (or move this comment down, up to you).

[• dberlin]

lib/Analysis/LazyCallGraph.cpp

1690

Just to note, you don't actually have to push the stack here.

This will push every node onto the stack.
it's possible to push only the root nodes onto the stack.

This is more memory efficient, and about 25% faster.

This is nuutila's variant, which is easy to implement:

http://www.cse.tkk.fi/~enu/ps/ipl-scc.ps
or
http://www.cse.tkk.fi/~enu/ps/tko-b94-scc.ps
or
the tarjan scc part of https://reviews.llvm.org/D28934

(For the papers, you want algorithm 1, not 2)

[davide]

I think there's still a bug/infinite loop somewhere as this doesn't terminate on some large inputs I have. I'll investigate and let you know (assuming it's unrelated from the issue Danny pointed out)

[davide]

lib/Analysis/LazyCallGraph.cpp

1690

My understanding of Nuutila is that it's faster if the graph is sparse, and when I spoke and proposed this to Chandler he mentioned the graph maybe not-that-sparse (for some definition of). I never found the SCC computation being a bottleneck (even for large programs), but I like Nuutila's variant so I wouldn't be opposed to that (and I think it's worth a try)

[• dberlin]

lib/Analysis/LazyCallGraph.cpp

1690

It's either faster or the same in every case, and given it's switching like two lines, IMHO, i'd do it, but ¯\_(ツ)_/¯

The real speed is unrelated to whether it's a sparse or not. What it's really related to is what happens on trees/dags.

Tarjan's algorithm pushes always
Nuutila's variant only pushes if it's actually a cycle.
So nodes that are parts of trees/dags, will not end up on the stack.

[davide]

lib/Analysis/LazyCallGraph.cpp

1690

STGM =)

[davide]

Also, some of the assertions still on by default are waay to slow for large bitcode files (and LTO), O(N^2) to O(N^4) depending on the sparseness of the graph
With https://reviews.llvm.org/P7969 disables the offending assertions in release mode (and enables them only under LLVM_EXPENSIVE_CHECKS)

[davide]

(this was the reason why it was taking forever to build, FWIW)

[chandlerc]

Thanks, comments hopefully addressed and new patch incoming.

include/llvm/Analysis/LazyCallGraph.h

1082–1086

Sorry, I had meant to go back through all these comments after I got this stuff working and add the ones missing and clean up the ones that were no longer accurate. Only some got done. I've commented more effectively now (i hope) but please tell me if they could be improved further.

lib/Analysis/LazyCallGraph.cpp

1690

FWIW, if the Nuutila variant can be implement cleanly and shows a performance improvement for some graphs (both of which I assume are true) then of course we should switch. =]

That said, I don't want to switch in *this* patch because my intent here is to very minimally relocate existing code.

I've added this as a FIXME to the missing comment on the routine though. =]

1691–1692

An assert that I wasn't sure could be implemented generically. Indeed, it can't. That said, we have lots of other asserts and tests that should catch any issue like this, I just forgot to clean it up. Thanks for spotting1

1795–1796

I've commented. I'm a bit torn. Not sure we should do reverse at all really, but if I don't do reverse, all of the iterations in the tests go in the opposite order and it seemed a lot of churn for no benefit. I think the reason is that we operate on this as a stack and so reversed gives the most unsurprising semantics.

That said, if you disagree I can remove this completely and just update the tests.

[chandlerc]

Rebase and address review comments.

[chandlerc]

In D29381#667331, @davide wrote:

Also, some of the assertions still on by default are waay to slow for large bitcode files (and LTO), O(N^2) to O(N^4) depending on the sparseness of the graph
With https://reviews.llvm.org/P7969 disables the offending assertions in release mode (and enables them only under LLVM_EXPENSIVE_CHECKS)

Sorry I missed these the first time around, yes, all of the descendent / ancestor stuff should be behind expensive checks clearly. I thought I had gotten them all but had searched for only one. =] Updated patch coming up which should match what you pasted as well.

[chandlerc]

And this time with all the crazy super-linear assertions disabled outside of
"expensive checks" mode.

[chandlerc]

Another update to actually remove all the support variables for maintaining an
in-flight DFS walk from the class. Somehow forgot to remove these, they're all
dead now.

In entertaining news, if you look carefully you'll spot places where this patch
actually fixes bugs due to failing to correctly manage all these variables. Yay
for a simpler approach!

[davide]

This LGTM now. Thanks for your patience, Chandler!

include/llvm/Analysis/CGSCCPassManager.h

PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM) {
     // iterating off the worklists.
     SmallPtrSet<LazyCallGraph::RefSCC *, 4> InvalidRefSCCSet;
     SmallPtrSet<LazyCallGraph::SCC *, 4> InvalidSCCSet;
 
     CGSCCUpdateResult UR = {RCWorklist,    CWorklist, InvalidRefSCCSet,
                             InvalidSCCSet, nullptr,   nullptr};
 
     PreservedAnalyses PA = PreservedAnalyses::all();
+    CG.buildRefSCCs();
     for (auto RCI = CG.postorder_ref_scc_begin(),
               RCE = CG.postorder_ref_scc_end();
          RCI != RCE;) {
       assert(RCWorklist.empty() &&
              "Should always start with an empty RefSCC worklist");
       // The postorder_ref_sccs range we are walking is lazily constructed, so
       // we only push the first one onto the worklist. The worklist allows us
       // to capture *new* RefSCCs created during transformations.

include/llvm/Analysis/LazyCallGraph.h

public:
     /// already existing edges.
     void insertTrivialRefEdge(Node &SourceN, Node &TargetN);
 
     ///@}
   };
 
   /// A post-order depth-first RefSCC iterator over the call graph.
   ///
-  /// This iterator triggers the Tarjan DFS-based formation of the RefSCC (and
-  /// SCC) DAG for the call graph, walking it lazily in depth-first post-order.
-  /// That is, it always visits RefSCCs for the target of a reference edge
-  /// prior to visiting the RefSCC for a source of the edge (when they are in
-  /// different RefSCCs).
-  ///
-  /// When forming each RefSCC, the call edges within it are used to form SCCs
-  /// within it, so iterating this also controls the lazy formation of SCCs.
+  /// This iterator walks the cached post-order sequence of RefSCCs. However,
+  /// it trades stability for flexibility. It is restricted to a forward
+  /// iterator but will survive mutations which insert new RefSCCs and continue
+  /// to point to the same RefSCC even if it moves in the post-order sequence.
   class postorder_ref_scc_iterator
       : public iterator_facade_base<postorder_ref_scc_iterator,
                                     std::forward_iterator_tag, RefSCC> {
     friend class LazyCallGraph;
     friend class LazyCallGraph::Node;
 
     /// Nonce type to select the constructor for the end iterator.
     struct IsAtEndT {};
 
     LazyCallGraph *G;
     RefSCC *RC;
 
     /// Build the begin iterator for a node.
     postorder_ref_scc_iterator(LazyCallGraph &G) : G(&G), RC(getRC(G, 0)) {}
 
     /// Build the end iterator for a node. This is selected purely by overload.
     postorder_ref_scc_iterator(LazyCallGraph &G, IsAtEndT /*Nonce*/)
         : G(&G), RC(nullptr) {}
 
     /// Get the post-order RefSCC at the given index of the postorder walk,
     /// populating it if necessary.
     static RefSCC *getRC(LazyCallGraph &G, int Index) {
       if (Index == (int)G.PostOrderRefSCCs.size())
-        if (!G.buildNextRefSCCInPostOrder())
-          // We're at the end.
-          return nullptr;
 
-      assert(Index < (int)G.PostOrderRefSCCs.size() &&
-             "Built the next post-order RefSCC without growing list!");
       return G.PostOrderRefSCCs[Index];
     }
 
   public:
     bool operator==(const postorder_ref_scc_iterator &Arg) const {
       return G == Arg.G && RC == Arg.RC;
     }
 
#endif
 
   edge_iterator begin() {
     return edge_iterator(EntryEdges.begin(), EntryEdges.end());
   }
   edge_iterator end() {
     return edge_iterator(EntryEdges.end(), EntryEdges.end());
   }
 
+  void buildRefSCCs();
+
   postorder_ref_scc_iterator postorder_ref_scc_begin() {
+    if (!EntryEdges.empty())
+      assert(!PostOrderRefSCCs.empty() &&
+             "Must form RefSCCs before iterating them!");
     return postorder_ref_scc_iterator(*this);
   }
   postorder_ref_scc_iterator postorder_ref_scc_end() {
+    if (!EntryEdges.empty())
+      assert(!PostOrderRefSCCs.empty() &&
+             "Must form RefSCCs before iterating them!");
     return postorder_ref_scc_iterator(*this,
                                       postorder_ref_scc_iterator::IsAtEndT());
   }
 
   iterator_range<postorder_ref_scc_iterator> postorder_ref_sccs() {
     return make_range(postorder_ref_scc_begin(), postorder_ref_scc_end());
   }
 
private:
 
   /// Allocates a RefSCC and constructs it using the graph allocator.
   ///
   /// The arguments are forwarded to the constructor.
   template <typename... Ts> RefSCC *createRefSCC(Ts &&... Args) {
     return new (RefSCCBPA.Allocate()) RefSCC(std::forward<Ts>(Args)...);
   }
 
+  /// Common logic for building SCCs from a sequence of roots.
+  ///
+  /// This is a very generic implementation of the depth-first walk and SCC
+  /// formation algorithm. It uses a generic sequence of roots and generic
+  /// callbacks for each step. This is designed to be used to implement both
+  /// the RefSCC formation and SCC formation with shared logic.
+  ///
+  /// Currently this is a relatively naive implementation of Tarjan's DFS
+  /// algorithm to form the SCCs.
+  ///
+  /// FIXME: We should consider newer variants such as Nuutila.
+  template <typename RootsT, typename GetBeginT, typename GetEndT,
+            typename GetNodeT, typename FormSCCCallbackT>
+  static void buildGenericSCCs(RootsT &&Roots, GetBeginT &&GetBegin,
+                               GetEndT &&GetEnd, GetNodeT &&GetNode,
+                               FormSCCCallbackT &&FormSCC);
+
   /// Build the SCCs for a RefSCC out of a list of nodes.
   void buildSCCs(RefSCC &RC, node_stack_range Nodes);
 
   /// Connect a RefSCC into the larger graph.
   ///
   /// This walks the edges to connect the RefSCC to its children's parent set,
   /// and updates the root leaf list.
   void connectRefSCC(RefSCC &RC);
 
   /// Get the index of a RefSCC within the postorder traversal.
   ///
   /// Requires that this RefSCC is a valid one in the (perhaps partial)
   /// postorder traversed part of the graph.
   int getRefSCCIndex(RefSCC &RC) {
     auto IndexIt = RefSCCIndices.find(&RC);
     assert(IndexIt != RefSCCIndices.end() && "RefSCC doesn't have an index!");
     assert(PostOrderRefSCCs[IndexIt->second] == &RC &&
            "Index does not point back at RC!");
     return IndexIt->second;
   }
-
-  /// Builds the next node in the post-order RefSCC walk of the call graph and
-  /// appends it to the \c PostOrderRefSCCs vector.
-  ///
-  /// Returns true if a new RefSCC was successfully constructed, and false if
-  /// there are no more RefSCCs to build in the graph.
-  bool buildNextRefSCCInPostOrder();
 };
 
 inline LazyCallGraph::Edge::Edge() : Value() {}
 inline LazyCallGraph::Edge::Edge(Function &F, Kind K) : Value(&F, K) {}
 inline LazyCallGraph::Edge::Edge(Node &N, Kind K) : Value(&N, K) {}
 
 inline LazyCallGraph::Edge::operator bool() const {
   return !Value.getPointer().isNull();

lib/Analysis/CGSCCPassManager.cpp

bool CGSCCAnalysisManagerModuleProxy::Result::invalidate(
   }
 
   // Directly check if the relevant set is preserved so we can short circuit
   // invalidating SCCs below.
   bool AreSCCAnalysesPreserved =
       PA.allAnalysesInSetPreserved<AllAnalysesOn<LazyCallGraph::SCC>>();
 
   // Ok, we have a graph, so we can propagate the invalidation down into it.
+  G->buildRefSCCs();
   for (auto &RC : G->postorder_ref_sccs())
     for (auto &C : RC) {
       Optional<PreservedAnalyses> InnerPA;
 
       // Check to see whether the preserved set needs to be adjusted based on
       // module-level analysis invalidation triggering deferred invalidation
       // for this SCC.
       if (auto *OuterProxy =

lib/Analysis/LazyCallGraph.cpp

 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/ScopeExit.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/InstVisitor.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/GraphWriter.h"
+#include <utility>
 
 using namespace llvm;
 
 #define DEBUG_TYPE "lcg"
 
 static void addEdge(SmallVectorImpl<LazyCallGraph::Edge> &Edges,
                     DenseMap<Function *, int> &EdgeIndexMap, Function &F,
                     LazyCallGraph::Edge::Kind EK) {
if (GV.hasInitializer())
       if (Visited.insert(GV.getInitializer()).second)
         Worklist.push_back(GV.getInitializer());
 
   DEBUG(dbgs() << "  Adding functions referenced by global initializers to the "
                   "entry set.\n");
   visitReferences(Worklist, Visited, [&](Function &F) {
     addEdge(EntryEdges, EntryIndexMap, F, LazyCallGraph::Edge::Ref);
   });
-
-  for (const Edge &E : EntryEdges)
-    RefSCCEntryNodes.push_back(&E.getFunction());
 }
 
 LazyCallGraph::LazyCallGraph(LazyCallGraph &&G)
     : BPA(std::move(G.BPA)), NodeMap(std::move(G.NodeMap)),
       EntryEdges(std::move(G.EntryEdges)),
       EntryIndexMap(std::move(G.EntryIndexMap)), SCCBPA(std::move(G.SCCBPA)),
       SCCMap(std::move(G.SCCMap)), LeafRefSCCs(std::move(G.LeafRefSCCs)),
       DFSStack(std::move(G.DFSStack)),
-      RefSCCEntryNodes(std::move(G.RefSCCEntryNodes)),
       NextDFSNumber(G.NextDFSNumber) {
   updateGraphPtrs();
 }
 
 LazyCallGraph &LazyCallGraph::operator=(LazyCallGraph &&G) {
   BPA = std::move(G.BPA);
   NodeMap = std::move(G.NodeMap);
   EntryEdges = std::move(G.EntryEdges);
   EntryIndexMap = std::move(G.EntryIndexMap);
   SCCBPA = std::move(G.SCCBPA);
   SCCMap = std::move(G.SCCMap);
   LeafRefSCCs = std::move(G.LeafRefSCCs);
   DFSStack = std::move(G.DFSStack);
-  RefSCCEntryNodes = std::move(G.RefSCCEntryNodes);
   NextDFSNumber = G.NextDFSNumber;
   updateGraphPtrs();
   return *this;
 }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 LLVM_DUMP_METHOD void LazyCallGraph::SCC::dump() const {
   dbgs() << *this << '\n';

 }
 
 void LazyCallGraph::RefSCC::insertTrivialCallEdge(Node &SourceN,
                                                   Node &TargetN) {
 #ifndef NDEBUG
   // Check that the RefSCC is still valid when we finish.
   auto ExitVerifier = make_scope_exit([this] { verify(); });
 
-  // Check that we aren't breaking some invariants of the SCC graph.
+#ifdef EXPENSIVE_CHECKS
+  // Check that we aren't breaking some invariants of the SCC graph. Note that
+  // this is quadratic in the number of edges in the call graph!
   SCC &SourceC = *G->lookupSCC(SourceN);
   SCC &TargetC = *G->lookupSCC(TargetN);
   if (&SourceC != &TargetC)
     assert(SourceC.isAncestorOf(TargetC) &&
            "Call edge is not trivial in the SCC graph!");
-#endif
+#endif // EXPENSIVE_CHECKS
+#endif // NDEBUG
+
   // First insert it into the source or find the existing edge.
   auto InsertResult = SourceN.EdgeIndexMap.insert(
       {&TargetN.getFunction(), SourceN.Edges.size()});
   if (!InsertResult.second) {
     // Already an edge, just update it.
     Edge &E = SourceN.Edges[InsertResult.first->second];
     if (E.isCall())
       return; // Nothing to do!
     E.setKind(Edge::Call);
   } else {
     // Create the new edge.
     SourceN.Edges.emplace_back(TargetN, Edge::Call);
   }
 
   // Now that we have the edge, handle the graph fallout.
   handleTrivialEdgeInsertion(SourceN, TargetN);
 }
 
 void LazyCallGraph::RefSCC::insertTrivialRefEdge(Node &SourceN, Node &TargetN) {
 #ifndef NDEBUG
   // Check that the RefSCC is still valid when we finish.
   auto ExitVerifier = make_scope_exit([this] { verify(); });
 
+#ifdef EXPENSIVE_CHECKS
   // Check that we aren't breaking some invariants of the RefSCC graph.
   RefSCC &SourceRC = *G->lookupRefSCC(SourceN);
   RefSCC &TargetRC = *G->lookupRefSCC(TargetN);
   if (&SourceRC != &TargetRC)
     assert(SourceRC.isAncestorOf(TargetRC) &&
            "Ref edge is not trivial in the RefSCC graph!");
-#endif
+#endif // EXPENSIVE_CHECKS
+#endif // NDEBUG
+
   // First insert it into the source or find the existing edge.
   auto InsertResult = SourceN.EdgeIndexMap.insert(
       {&TargetN.getFunction(), SourceN.Edges.size()});
   if (!InsertResult.second)
     // Already an edge, we're done.
     return;
 
   // Create the new edge.
assert(F.use_empty() &&
          "This routine should only be called on trivially dead functions!");
 
   auto EII = EntryIndexMap.find(&F);
   if (EII != EntryIndexMap.end()) {
     EntryEdges[EII->second] = Edge();
     EntryIndexMap.erase(EII);
   }
 
-  // It's safe to just remove un-visited functions from the RefSCC entry list.
-  // FIXME: This is a linear operation which could become hot and benefit from
-  // an index map.
-  auto RENI = find(RefSCCEntryNodes, &F);
-  if (RENI != RefSCCEntryNodes.end())
-    RefSCCEntryNodes.erase(RENI);
-
   auto NI = NodeMap.find(&F);
   if (NI == NodeMap.end())
     // Not in the graph at all!
     return;
 
   Node &N = *NI->second;
   NodeMap.erase(NI);
 
while (!Worklist.empty()) {
       RefSCC &C = *Worklist.pop_back_val();
       C.G = this;
       for (RefSCC &ParentC : C.parents())
         Worklist.push_back(&ParentC);
     }
   }
 }
 
-/// Build the internal SCCs for a RefSCC from a sequence of nodes.
-///
-/// Appends the SCCs to the provided vector and updates the map with their
-/// indices. Both the vector and map must be empty when passed into this
-/// routine.
-void LazyCallGraph::buildSCCs(RefSCC &RC, node_stack_range Nodes) {
-  assert(RC.SCCs.empty() && "Already built SCCs!");
-  assert(RC.SCCIndices.empty() && "Already mapped SCC indices!");
-
-  for (Node *N : Nodes) {
-    assert(N->LowLink >= (*Nodes.begin())->LowLink &&
-           "We cannot have a low link in an SCC lower than its root on the "
-           "stack!");
-
-    // This node will go into the next RefSCC, clear out its DFS and low link
-    // as we scan.
-    N->DFSNumber = N->LowLink = 0;
-  }
-
-  // Each RefSCC contains a DAG of the call SCCs. To build these, we do
-  // a direct walk of the call edges using Tarjan's algorithm. We reuse the
-  // internal storage as we won't need it for the outer graph's DFS any longer.
+template <typename RootsT, typename GetBeginT, typename GetEndT,
+          typename GetNodeT, typename FormSCCCallbackT>
+void LazyCallGraph::buildGenericSCCs(RootsT &&Roots, GetBeginT &&GetBegin,
+                                     GetEndT &&GetEnd, GetNodeT &&GetNode,
+                                     FormSCCCallbackT &&FormSCC) {
+  typedef decltype(GetBegin(std::declval<Node &>())) EdgeItT;
 
-  SmallVector<std::pair<Node *, call_edge_iterator>, 16> DFSStack;
+  SmallVector<std::pair<Node *, EdgeItT>, 16> DFSStack;
   SmallVector<Node *, 16> PendingSCCStack;
 
   // Scan down the stack and DFS across the call edges.
-  for (Node *RootN : Nodes) {
+  for (Node *RootN : Roots) {
     assert(DFSStack.empty() &&
            "Cannot begin a new root with a non-empty DFS stack!");
     assert(PendingSCCStack.empty() &&
            "Cannot begin a new root with pending nodes for an SCC!");
 
     // Skip any nodes we've already reached in the DFS.
     if (RootN->DFSNumber != 0) {
       assert(RootN->DFSNumber == -1 &&
              "Shouldn't have any mid-DFS root nodes!");
       continue;
     }
 
     RootN->DFSNumber = RootN->LowLink = 1;
     int NextDFSNumber = 2;
 
-    DFSStack.push_back({RootN, RootN->call_begin()});
+    DFSStack.push_back({RootN, GetBegin(*RootN)});
     do {
       Node *N;
-      call_edge_iterator I;
+      EdgeItT I;
       std::tie(N, I) = DFSStack.pop_back_val();
-      auto E = N->call_end();
+      auto E = GetEnd(*N);
       while (I != E) {
-        Node &ChildN = *I->getNode();
+        Node &ChildN = GetNode(I);
         if (ChildN.DFSNumber == 0) {
           // We haven't yet visited this child, so descend, pushing the current
           // node onto the stack.
           DFSStack.push_back({N, I});
 
-          assert(!lookupSCC(ChildN) &&
-                 "Found a node with 0 DFS number but already in an SCC!");
           ChildN.DFSNumber = ChildN.LowLink = NextDFSNumber++;
           N = &ChildN;
-          I = N->call_begin();
-          E = N->call_end();
+          I = GetBegin(*N);
+          E = GetEnd(*N);
           continue;
         }
 
         // If the child has already been added to some child component, it
         // couldn't impact the low-link of this parent because it isn't
         // connected, and thus its low-link isn't relevant so skip it.
         if (ChildN.DFSNumber == -1) {
           ++I;
do {
       // root DFS number.
       auto SCCNodes = make_range(
           PendingSCCStack.rbegin(),
           find_if(reverse(PendingSCCStack), [RootDFSNumber](const Node *N) {
             return N->DFSNumber < RootDFSNumber;
           }));
       // Form a new SCC out of these nodes and then clear them off our pending
       // stack.
-      RC.SCCs.push_back(createSCC(RC, SCCNodes));
+      FormSCC(SCCNodes);
+      PendingSCCStack.erase(SCCNodes.end().base(), PendingSCCStack.end());
+    } while (!DFSStack.empty());
+  }
+}
+
+/// Build the internal SCCs for a RefSCC from a sequence of nodes.
+///
+/// Appends the SCCs to the provided vector and updates the map with their
+/// indices. Both the vector and map must be empty when passed into this
+/// routine.
+void LazyCallGraph::buildSCCs(RefSCC &RC, node_stack_range Nodes) {
+  assert(RC.SCCs.empty() && "Already built SCCs!");
+  assert(RC.SCCIndices.empty() && "Already mapped SCC indices!");
+
+  for (Node *N : Nodes) {
+    assert(N->LowLink >= (*Nodes.begin())->LowLink &&
+           "We cannot have a low link in an SCC lower than its root on the "
+           "stack!");
+
+    // This node will go into the next RefSCC, clear out its DFS and low link
+    // as we scan.
+    N->DFSNumber = N->LowLink = 0;
+  }
+
+  // Each RefSCC contains a DAG of the call SCCs. To build these, we do
+  // a direct walk of the call edges using Tarjan's algorithm. We reuse the
+  // internal storage as we won't need it for the outer graph's DFS any longer.
+  buildGenericSCCs(Nodes, [](Node &N) { return N.call_begin(); },
+                   [](Node &N) { return N.call_end(); },
+                   [](call_edge_iterator I) -> Node & {
+                     // For SCCs, all the nodes should already be formed.
+                     return *I->getNode();
+                   },
+                   [this, &RC](node_stack_range Nodes) {
+                     RC.SCCs.push_back(createSCC(RC, Nodes));
                      for (Node &N : *RC.SCCs.back()) {
                        N.DFSNumber = N.LowLink = -1;
                        SCCMap[&N] = RC.SCCs.back();
                      }
-      PendingSCCStack.erase(SCCNodes.end().base(), PendingSCCStack.end());
-    } while (!DFSStack.empty());
-  }
+                   });
 
   // Wire up the SCC indices.
   for (int i = 0, Size = RC.SCCs.size(); i < Size; ++i)
     RC.SCCIndices[RC.SCCs[i]] = i;
 }
 
+void LazyCallGraph::buildRefSCCs() {
+  if (EntryEdges.empty() || !PostOrderRefSCCs.empty())
+    // RefSCCs are either non-existent or already built!
+    return;
+
+  assert(RefSCCIndices.empty() && "Already mapped RefSCC indices!");
+
+  SmallVector<Node *, 16> Roots;
+  for (Edge &E : *this)
+    Roots.push_back(&E.getNode(*this));
+
+  // The roots will be popped of a stack, so use reverse to get a less
+  // surprising order. This doesn't change any of the semantics anywhere.
+  std::reverse(Roots.begin(), Roots.end());
+
+  buildGenericSCCs(
+      Roots, [](Node &N) { return N.begin(); }, [](Node &N) { return N.end(); },
+      [this](edge_iterator I) -> Node & {
+        // Form the node if we haven't yet.
+        return I->getNode(*this);
+      },
+      [this](node_stack_range Nodes) {
+        RefSCC *NewRC = createRefSCC(*this);
+        buildSCCs(*NewRC, Nodes);
+        connectRefSCC(*NewRC);
+
+        // Push the new node into the postorder list and remember its position
+        // in the index map.
+        bool Inserted =
+            RefSCCIndices.insert({NewRC, PostOrderRefSCCs.size()}).second;
+        (void)Inserted;
+        assert(Inserted && "Cannot already have this RefSCC in the index map!");
+        PostOrderRefSCCs.push_back(NewRC);
+        NewRC->verify();
+      });
+}
+
 // FIXME: We should move callers of this to embed the parent linking and leaf
 // tracking into their DFS in order to remove a full walk of all edges.
 void LazyCallGraph::connectRefSCC(RefSCC &RC) {
   // Walk all edges in the RefSCC (this remains linear as we only do this once
   // when we build the RefSCC) to connect it to the parent sets of its
   // children.
   bool IsLeaf = true;
   for (SCC &C : RC)
     for (Node &N : C)
       for (Edge &E : N) {
         assert(E.getNode() &&
                "Cannot have a missing node in a visited part of the graph!");
         RefSCC &ChildRC = *lookupRefSCC(*E.getNode());
         if (&ChildRC == &RC)
           continue;
         ChildRC.Parents.insert(&RC);
         IsLeaf = false;
       }
 
   // For the SCCs where we find no child SCCs, add them to the leaf list.
   if (IsLeaf)
     LeafRefSCCs.push_back(&RC);
 }
 
-bool LazyCallGraph::buildNextRefSCCInPostOrder() {
-  if (DFSStack.empty()) {
-    Node *N;
-    do {
-      // If we've handled all candidate entry nodes to the SCC forest, we're
-      // done.
-      if (RefSCCEntryNodes.empty())
-        return false;
-
-      N = &get(*RefSCCEntryNodes.pop_back_val());
-    } while (N->DFSNumber != 0);
-
-    // Found a new root, begin the DFS here.
-    N->LowLink = N->DFSNumber = 1;
-    NextDFSNumber = 2;
-    DFSStack.push_back({N, N->begin()});
-  }
-
-  for (;;) {
-    Node *N;
-    edge_iterator I;
-    std::tie(N, I) = DFSStack.pop_back_val();
-
-    assert(N->DFSNumber > 0 && "We should always assign a DFS number "
-                               "before placing a node onto the stack.");
-
-    auto E = N->end();
-    while (I != E) {
-      Node &ChildN = I->getNode(*this);
-      if (ChildN.DFSNumber == 0) {
-        // We haven't yet visited this child, so descend, pushing the current
-        // node onto the stack.
-        DFSStack.push_back({N, N->begin()});
-
-        assert(!SCCMap.count(&ChildN) &&
-               "Found a node with 0 DFS number but already in an SCC!");
-        ChildN.LowLink = ChildN.DFSNumber = NextDFSNumber++;
-        N = &ChildN;
-        I = N->begin();
-        E = N->end();
-        continue;
-      }
-
-      // If the child has already been added to some child component, it
-      // couldn't impact the low-link of this parent because it isn't
-      // connected, and thus its low-link isn't relevant so skip it.
-      if (ChildN.DFSNumber == -1) {
-        ++I;
-        continue;
-      }
-
-      // Track the lowest linked child as the lowest link for this node.
-      assert(ChildN.LowLink > 0 && "Must have a positive low-link number!");
-      if (ChildN.LowLink < N->LowLink)
-        N->LowLink = ChildN.LowLink;
-
-      // Move to the next edge.
-      ++I;
-    }
-
-    // We've finished processing N and its descendents, put it on our pending
-    // SCC stack to eventually get merged into an SCC of nodes.
-    PendingRefSCCStack.push_back(N);
-
-    // If this node is linked to some lower entry, continue walking up the
-    // stack.
-    if (N->LowLink != N->DFSNumber) {
-      assert(!DFSStack.empty() &&
-             "We never found a viable root for an SCC to pop off!");
-      continue;
-    }
-
-    // Otherwise, form a new RefSCC from the top of the pending node stack.
-    int RootDFSNumber = N->DFSNumber;
-    // Find the range of the node stack by walking down until we pass the
-    // root DFS number.
-    auto RefSCCNodes = node_stack_range(
-        PendingRefSCCStack.rbegin(),
-        find_if(reverse(PendingRefSCCStack), [RootDFSNumber](const Node *N) {
-          return N->DFSNumber < RootDFSNumber;
-        }));
-    // Form a new RefSCC out of these nodes and then clear them off our pending
-    // stack.
-    RefSCC *NewRC = createRefSCC(*this);
-    buildSCCs(*NewRC, RefSCCNodes);
-    connectRefSCC(*NewRC);
-    PendingRefSCCStack.erase(RefSCCNodes.end().base(),
-                             PendingRefSCCStack.end());
-
-    // Push the new node into the postorder list and return true indicating we
-    // successfully grew the postorder sequence by one.
-    bool Inserted =
-        RefSCCIndices.insert({NewRC, PostOrderRefSCCs.size()}).second;
-    (void)Inserted;
-    assert(Inserted && "Cannot already have this RefSCC in the index map!");
-    PostOrderRefSCCs.push_back(NewRC);
-    return true;
-  }
-}
-
 AnalysisKey LazyCallGraphAnalysis::Key;
 
 LazyCallGraphPrinterPass::LazyCallGraphPrinterPass(raw_ostream &OS) : OS(OS) {}
 
 static void printNode(raw_ostream &OS, LazyCallGraph::Node &N) {
   OS << "  Edges in function: " << N.getFunction().getName() << "\n";
   for (const LazyCallGraph::Edge &E : N)
     OS << "    " << (E.isCall() ? "call" : "ref ") << " -> "
PreservedAnalyses LazyCallGraphPrinterPass::run(Module &M,
   LazyCallGraph &G = AM.getResult<LazyCallGraphAnalysis>(M);
 
   OS << "Printing the call graph for module: " << M.getModuleIdentifier()
      << "\n\n";
 
   for (Function &F : M)
     printNode(OS, G.get(F));
 
+  G.buildRefSCCs();
   for (LazyCallGraph::RefSCC &C : G.postorder_ref_sccs())
     printRefSCC(OS, C);
 
   return PreservedAnalyses::all();
 }
 
 LazyCallGraphDOTPrinterPass::LazyCallGraphDOTPrinterPass(raw_ostream &OS)
     : OS(OS) {}

unittests/Analysis/LazyCallGraphTest.cpp

TEST(LazyCallGraphTest, BasicGraphFormation) {
   EXPECT_EQ(D1.end(), std::next(D1.begin()));
   EXPECT_EQ("d2", D1.begin()->getFunction().getName());
   EXPECT_EQ(D2.end(), std::next(D2.begin()));
   EXPECT_EQ("d3", D2.begin()->getFunction().getName());
   EXPECT_EQ(D3.end(), std::next(D3.begin()));
   EXPECT_EQ("d1", D3.begin()->getFunction().getName());
 
   // Now lets look at the RefSCCs and SCCs.
+  CG.buildRefSCCs();
   auto J = CG.postorder_ref_scc_begin();
 
   LazyCallGraph::RefSCC &D = *J++;
   ASSERT_EQ(1, D.size());
   for (LazyCallGraph::Node &N : *D.begin())
     Nodes.push_back(N.getFunction().getName());
   std::sort(Nodes.begin(), Nodes.end());
   EXPECT_EQ(3u, Nodes.size());
TEST(LazyCallGraphTest, InnerSCCFormation) {
   CG.insertEdge(lookupFunction(*M, "d1"), lookupFunction(*M, "a1"),
                 LazyCallGraph::Edge::Ref);
 
   // Build vectors and sort them for the rest of the assertions to make them
   // independent of order.
   std::vector<std::string> Nodes;
 
   // We should build a single RefSCC for the entire graph.
+  CG.buildRefSCCs();
   auto I = CG.postorder_ref_scc_begin();
   LazyCallGraph::RefSCC &RC = *I++;
   EXPECT_EQ(CG.postorder_ref_scc_end(), I);
 
   // Now walk the four SCCs which should be in post-order.
   auto J = RC.begin();
   LazyCallGraph::SCC &D = *J++;
   for (LazyCallGraph::Node &N : D)
std::unique_ptr<Module> M = parseAssembly(Context, "define void @f1() {\n"
                                                      "define void @f5() {\n"
                                                      "entry:\n"
                                                      "  call void @f1()\n"
                                                      "  ret void\n"
                                                      "}\n");
   LazyCallGraph CG(*M);
 
   // Force the graph to be fully expanded.
+  CG.buildRefSCCs();
   auto I = CG.postorder_ref_scc_begin();
   LazyCallGraph::RefSCC &RC = *I++;
   EXPECT_EQ(CG.postorder_ref_scc_end(), I);
 
   LazyCallGraph::Node &N1 = *CG.lookup(lookupFunction(*M, "f1"));
   LazyCallGraph::Node &N2 = *CG.lookup(lookupFunction(*M, "f2"));
   LazyCallGraph::Node &N3 = *CG.lookup(lookupFunction(*M, "f3"));
   LazyCallGraph::Node &N4 = *CG.lookup(lookupFunction(*M, "f4"));
std::unique_ptr<Module> M = parseAssembly(Context, "define void @a() {\n"
                                                      "}\n"
                                                      "define void @d() {\n"
                                                      "entry:\n"
                                                      "  ret void\n"
                                                      "}\n");
   LazyCallGraph CG(*M);
 
   // Force the graph to be fully expanded.
+  CG.buildRefSCCs();
   for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs())
     dbgs() << "Formed RefSCC: " << RC << "\n";
 
   LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a"));
   LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b"));
   LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c"));
   LazyCallGraph::Node &D = *CG.lookup(lookupFunction(*M, "d"));
   LazyCallGraph::SCC &AC = *CG.lookupSCC(A);
TEST(LazyCallGraphTest, IncomingEdgeInsertion) {
   //        a1        |
   //       /  \       |
   //      a3--a2      |
   //
   std::unique_ptr<Module> M = parseAssembly(Context, DiamondOfTriangles);
   LazyCallGraph CG(*M);
 
   // Force the graph to be fully expanded.
+  CG.buildRefSCCs();
   for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs())
     dbgs() << "Formed RefSCC: " << RC << "\n";
 
   LazyCallGraph::Node &A1 = *CG.lookup(lookupFunction(*M, "a1"));
   LazyCallGraph::Node &A2 = *CG.lookup(lookupFunction(*M, "a2"));
   LazyCallGraph::Node &A3 = *CG.lookup(lookupFunction(*M, "a3"));
   LazyCallGraph::Node &B1 = *CG.lookup(lookupFunction(*M, "b1"));
   LazyCallGraph::Node &B2 = *CG.lookup(lookupFunction(*M, "b2"));
TEST(LazyCallGraphTest, IncomingEdgeInsertion) {
   EXPECT_EQ(&CRC, &*I) << "Actual RefSCC: " << *I;
   ASSERT_NE(++I, E);
   EXPECT_EQ(&BRC, &*I) << "Actual RefSCC: " << *I;
   ASSERT_NE(++I, E);
   EXPECT_EQ(&ARC, &*I) << "Actual RefSCC: " << *I;
   EXPECT_EQ(++I, E);
 }
 
-TEST(LazyCallGraphTest, IncomingEdgeInsertionMidTraversal) {
-  LLVMContext Context;
-  // This is the same fundamental test as the previous, but we perform it
-  // having only partially walked the RefSCCs of the graph.
-  std::unique_ptr<Module> M = parseAssembly(Context, DiamondOfTriangles);
-  LazyCallGraph CG(*M);
-
-  // Walk the RefSCCs until we find the one containing 'c1'.
-  auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end();
-  ASSERT_NE(I, E);
-  LazyCallGraph::RefSCC &DRC = *I;
-  ASSERT_NE(&DRC, nullptr);
-  ++I;
-  ASSERT_NE(I, E);
-  LazyCallGraph::RefSCC &CRC = *I;
-  ASSERT_NE(&CRC, nullptr);
-
-  ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "a1")));
-  ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "a2")));
-  ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "a3")));
-  ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "b1")));
-  ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "b2")));
-  ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "b3")));
-  LazyCallGraph::Node &C1 = *CG.lookup(lookupFunction(*M, "c1"));
-  LazyCallGraph::Node &C2 = *CG.lookup(lookupFunction(*M, "c2"));
-  LazyCallGraph::Node &C3 = *CG.lookup(lookupFunction(*M, "c3"));
-  LazyCallGraph::Node &D1 = *CG.lookup(lookupFunction(*M, "d1"));
-  LazyCallGraph::Node &D2 = *CG.lookup(lookupFunction(*M, "d2"));
-  LazyCallGraph::Node &D3 = *CG.lookup(lookupFunction(*M, "d3"));
-  ASSERT_EQ(&CRC, CG.lookupRefSCC(C1));
-  ASSERT_EQ(&CRC, CG.lookupRefSCC(C2));
-  ASSERT_EQ(&CRC, CG.lookupRefSCC(C3));
-  ASSERT_EQ(&DRC, CG.lookupRefSCC(D1));
-  ASSERT_EQ(&DRC, CG.lookupRefSCC(D2));
-  ASSERT_EQ(&DRC, CG.lookupRefSCC(D3));
-  ASSERT_EQ(1, std::distance(D2.begin(), D2.end()));
-
-  auto MergedRCs = CRC.insertIncomingRefEdge(D2, C2);
-  // Make sure we connected the nodes.
-  for (LazyCallGraph::Edge E : D2) {
-    if (E.getNode() == &D3)
-      continue;
-    EXPECT_EQ(&C2, E.getNode());
-  }
-  // And marked the D ref-SCC as no longer valid.
-  EXPECT_EQ(1u, MergedRCs.size());
-  EXPECT_EQ(&DRC, MergedRCs[0]);
-
-  // Make sure we have the correct nodes in the RefSCCs.
-  EXPECT_EQ(&CRC, CG.lookupRefSCC(C1));
-  EXPECT_EQ(&CRC, CG.lookupRefSCC(C2));
-  EXPECT_EQ(&CRC, CG.lookupRefSCC(C3));
-  EXPECT_EQ(&CRC, CG.lookupRefSCC(D1));
-  EXPECT_EQ(&CRC, CG.lookupRefSCC(D2));
-  EXPECT_EQ(&CRC, CG.lookupRefSCC(D3));
-
-  // Verify that the post-order walk reflects the updated but still incomplete
-  // structure.
-  auto J = CG.postorder_ref_scc_begin();
-  EXPECT_NE(J, E);
-  EXPECT_EQ(&CRC, &*J) << "Actual RefSCC: " << *J;
-  EXPECT_EQ(I, J);
-
-  // Check that we can form the last two RefSCCs now, and even that we can do
-  // it with alternating iterators.
-  ++J;
-  EXPECT_NE(J, E);
-  LazyCallGraph::RefSCC &BRC = *J;
-  EXPECT_NE(&BRC, nullptr);
-  EXPECT_EQ(&BRC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "b1"))));
-  EXPECT_EQ(&BRC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "b2"))));
-  EXPECT_EQ(&BRC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "b3"))));
-  EXPECT_TRUE(BRC.isParentOf(CRC));
-  ++I;
-  EXPECT_EQ(J, I);
-  EXPECT_EQ(&BRC, &*I) << "Actual RefSCC: " << *I;
-
-  // Increment I this time to form the new RefSCC, flopping back to the first
-  // iterator.
-  ++I;
-  EXPECT_NE(I, E);
-  LazyCallGraph::RefSCC &ARC = *I;
-  EXPECT_NE(&ARC, nullptr);
-  EXPECT_EQ(&ARC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "a1"))));
-  EXPECT_EQ(&ARC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "a2"))));
-  EXPECT_EQ(&ARC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "a3"))));
-  EXPECT_TRUE(ARC.isParentOf(CRC));
-  ++J;
-  EXPECT_EQ(I, J);
-  EXPECT_EQ(&ARC, &*J) << "Actual RefSCC: " << *J;
-  ++I;
-  EXPECT_EQ(E, I);
-  ++J;
-  EXPECT_EQ(E, J);
-}
-
 TEST(LazyCallGraphTest, IncomingEdgeInsertionRefGraph) {
   LLVMContext Context;
   // Another variation of the above test but with all the edges switched to
   // references rather than calls.
   std::unique_ptr<Module> M =
       parseAssembly(Context, DiamondOfTrianglesRefGraph);
   LazyCallGraph CG(*M);
 
   // Force the graph to be fully expanded.
+  CG.buildRefSCCs();
   for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs())
     dbgs() << "Formed RefSCC: " << RC << "\n";
 
   LazyCallGraph::Node &A1 = *CG.lookup(lookupFunction(*M, "a1"));
   LazyCallGraph::Node &A2 = *CG.lookup(lookupFunction(*M, "a2"));
   LazyCallGraph::Node &A3 = *CG.lookup(lookupFunction(*M, "a3"));
   LazyCallGraph::Node &B1 = *CG.lookup(lookupFunction(*M, "b1"));
   LazyCallGraph::Node &B2 = *CG.lookup(lookupFunction(*M, "b2"));
std::unique_ptr<Module> M = parseAssembly(Context, "define void @a() {\n"
                                                      "}\n"
                                                      "define void @d() {\n"
                                                      "entry:\n"
                                                      "  ret void\n"
                                                      "}\n");
   LazyCallGraph CG(*M);
 
   // Force the graph to be fully expanded.
+  CG.buildRefSCCs();
   for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs())
     dbgs() << "Formed RefSCC: " << RC << "\n";
 
   LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a"));
   LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b"));
   LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c"));
   LazyCallGraph::Node &D = *CG.lookup(lookupFunction(*M, "d"));
   LazyCallGraph::SCC &AC = *CG.lookupSCC(A);
std::unique_ptr<Module> M =
                              "}\n"
                              "define void @d() {\n"
                              "entry:\n"
                              "  ret void\n"
                              "}\n");
   LazyCallGraph CG(*M);
 
   // Force the graph to be fully expanded.
+  CG.buildRefSCCs();
   for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs())
     dbgs() << "Formed RefSCC: " << RC << "\n";
 
   LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a"));
   LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b"));
   LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c"));
   LazyCallGraph::Node &D = *CG.lookup(lookupFunction(*M, "d"));
   LazyCallGraph::RefSCC &ARC = *CG.lookupRefSCC(A);
TEST(LazyCallGraphTest, InlineAndDeleteFunction) {
   //        a1        |
   //       /  \       |
   //      a3--a2      |
   //
   std::unique_ptr<Module> M = parseAssembly(Context, DiamondOfTriangles);
   LazyCallGraph CG(*M);
 
   // Force the graph to be fully expanded.
+  CG.buildRefSCCs();
   for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs())
     dbgs() << "Formed RefSCC: " << RC << "\n";
 
   LazyCallGraph::Node &A1 = *CG.lookup(lookupFunction(*M, "a1"));
   LazyCallGraph::Node &A2 = *CG.lookup(lookupFunction(*M, "a2"));
   LazyCallGraph::Node &A3 = *CG.lookup(lookupFunction(*M, "a3"));
   LazyCallGraph::Node &B1 = *CG.lookup(lookupFunction(*M, "b1"));
   LazyCallGraph::Node &B2 = *CG.lookup(lookupFunction(*M, "b2"));
TEST(LazyCallGraphTest, InlineAndDeleteFunction) {
   EXPECT_EQ(&CRC, &*I) << "Actual RefSCC: " << *I;
   ASSERT_NE(++I, E);
   EXPECT_EQ(&BRC, &*I) << "Actual RefSCC: " << *I;
   ASSERT_NE(++I, E);
   EXPECT_EQ(&ARC, &*I) << "Actual RefSCC: " << *I;
   EXPECT_EQ(++I, E);
 }
 
-TEST(LazyCallGraphTest, InlineAndDeleteFunctionMidTraversal) {
-  LLVMContext Context;
-  // This is the same fundamental test as the previous, but we perform it
-  // having only partially walked the RefSCCs of the graph.
-  //
-  // The ascii diagram is repeated here for easy reference.
-  //
-  //         d1       |
-  //        /  \      |
-  //       d3--d2     |
-  //      /     \     |
-  //     b1     c1    |
-  //   /  \    /  \   |
-  //  b3--b2  c3--c2  |
-  //       \  /       |
-  //        a1        |
-  //       /  \       |
-  //      a3--a2      |
-  //
-  std::unique_ptr<Module> M = parseAssembly(Context, DiamondOfTriangles);
-  LazyCallGraph CG(*M);
-
-  // Walk the RefSCCs until we find the one containing 'c1'.
-  auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end();
-  ASSERT_NE(I, E);
-  LazyCallGraph::RefSCC &DRC = *I;
-  ASSERT_NE(&DRC, nullptr);
-  ++I;
-  ASSERT_NE(I, E);
-  LazyCallGraph::RefSCC &CRC = *I;
-  ASSERT_NE(&CRC, nullptr);
-
-  ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "a1")));
-  ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "a2")));
-  ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "a3")));
-  ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "b1")));
-  ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "b2")));
-  ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "b3")));
-  LazyCallGraph::Node &C1 = *CG.lookup(lookupFunction(*M, "c1"));
-  LazyCallGraph::Node &C2 = *CG.lookup(lookupFunction(*M, "c2"));
-  LazyCallGraph::Node &C3 = *CG.lookup(lookupFunction(*M, "c3"));
-  LazyCallGraph::Node &D1 = *CG.lookup(lookupFunction(*M, "d1"));
-  LazyCallGraph::Node &D2 = *CG.lookup(lookupFunction(*M, "d2"));
-  LazyCallGraph::Node &D3 = *CG.lookup(lookupFunction(*M, "d3"));
-  ASSERT_EQ(&CRC, CG.lookupRefSCC(C1));
-  ASSERT_EQ(&CRC, CG.lookupRefSCC(C2));
-  ASSERT_EQ(&CRC, CG.lookupRefSCC(C3));
-  ASSERT_EQ(&DRC, CG.lookupRefSCC(D1));
-  ASSERT_EQ(&DRC, CG.lookupRefSCC(D2));
-  ASSERT_EQ(&DRC, CG.lookupRefSCC(D3));
-  ASSERT_EQ(1, std::distance(D2.begin(), D2.end()));
-
-  // Delete d2 from the graph, as if it had been inlined.
-  //
-  //         d1         |
-  //        / /         |
-  //       d3--.        |
-  //      /     \       |
-  //     b1     c1      |
-  //   /  \    /  \     |
-  //  b3--b2  c3--c2    |
-  //       \  /         |
-  //        a1          |
-  //       /  \         |
-  //      a3--a2        |
-
-  Function &D2F = D2.getFunction();
-  CallInst *C1Call = nullptr, *D1Call = nullptr;
-  for (User *U : D2F.users()) {
-    CallInst *CI = dyn_cast<CallInst>(U);
-    ASSERT_TRUE(CI) << "Expected a call: " << *U;
-    if (CI->getParent()->getParent() == &C1.getFunction()) {
-      ASSERT_EQ(nullptr, C1Call) << "Found too many C1 calls: " << *CI;
-      C1Call = CI;
-    } else if (CI->getParent()->getParent() == &D1.getFunction()) {
-      ASSERT_EQ(nullptr, D1Call) << "Found too many D1 calls: " << *CI;
-      D1Call = CI;
-    } else {
-      FAIL() << "Found an unexpected call instruction: " << *CI;
-    }
-  }
-  ASSERT_NE(C1Call, nullptr);
-  ASSERT_NE(D1Call, nullptr);
-  ASSERT_EQ(&D2F, C1Call->getCalledFunction());
-  ASSERT_EQ(&D2F, D1Call->getCalledFunction());
-  C1Call->setCalledFunction(&D3.getFunction());
-  D1Call->setCalledFunction(&D3.getFunction());
-  ASSERT_EQ(0u, D2F.getNumUses());
-
-  // Insert new edges first.
-  CRC.insertTrivialCallEdge(C1, D3);
-  DRC.insertTrivialCallEdge(D1, D3);
-
-  // Then remove the old ones.
-  LazyCallGraph::SCC &DC = *CG.lookupSCC(D2);
-  auto NewCs = DRC.switchInternalEdgeToRef(D1, D2);
-  EXPECT_EQ(&DC, CG.lookupSCC(D2));
-  EXPECT_EQ(NewCs.end(), std::next(NewCs.begin()));
-  LazyCallGraph::SCC &NewDC = *NewCs.begin();
-  EXPECT_EQ(&NewDC, CG.lookupSCC(D1));
-  EXPECT_EQ(&NewDC, CG.lookupSCC(D3));
-  auto NewRCs = DRC.removeInternalRefEdge(D1, D2);
-  EXPECT_EQ(&DRC, CG.lookupRefSCC(D2));
-  EXPECT_EQ(NewRCs.end(), std::next(NewRCs.begin()));
-  LazyCallGraph::RefSCC &NewDRC = **NewRCs.begin();
-  EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D1));
-  EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D3));
-  EXPECT_FALSE(NewDRC.isParentOf(DRC));
-  EXPECT_TRUE(CRC.isParentOf(DRC));
-  EXPECT_TRUE(CRC.isParentOf(NewDRC));
-  EXPECT_TRUE(DRC.isParentOf(NewDRC));
-  CRC.removeOutgoingEdge(C1, D2);
-  EXPECT_FALSE(CRC.isParentOf(DRC));
-  EXPECT_TRUE(CRC.isParentOf(NewDRC));
-  EXPECT_TRUE(DRC.isParentOf(NewDRC));
-
-  // Now that we've updated the call graph, D2 is dead, so remove it.
-  CG.removeDeadFunction(D2F);
-
-  // Check that the graph still looks the same.
-  EXPECT_EQ(&CRC, CG.lookupRefSCC(C1));
-  EXPECT_EQ(&CRC, CG.lookupRefSCC(C2));
-  EXPECT_EQ(&CRC, CG.lookupRefSCC(C3));
-  EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D1));
-  EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D3));
-  EXPECT_TRUE(CRC.isParentOf(NewDRC));
-
-  // Verify that the post-order walk reflects the updated but still incomplete
-  // structure.
-  auto J = CG.postorder_ref_scc_begin();
-  EXPECT_NE(J, E);
-  EXPECT_EQ(&NewDRC, &*J) << "Actual RefSCC: " << *J;
-  ++J;
-  EXPECT_NE(J, E);
-  EXPECT_EQ(&CRC, &*J) << "Actual RefSCC: " << *J;
-  EXPECT_EQ(I, J);
-
-  // Check that we can form the last two RefSCCs now, and even that we can do
-  // it with alternating iterators.
-  ++J;
-  EXPECT_NE(J, E);
-  LazyCallGraph::RefSCC &BRC = *J;
-  EXPECT_NE(&BRC, nullptr);
-  EXPECT_EQ(&BRC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "b1"))));
-  EXPECT_EQ(&BRC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "b2"))));
-  EXPECT_EQ(&BRC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "b3"))));
-  EXPECT_TRUE(BRC.isParentOf(NewDRC));
-  ++I;
-  EXPECT_EQ(J, I);
-  EXPECT_EQ(&BRC, &*I) << "Actual RefSCC: " << *I;
-
-  // Increment I this time to form the new RefSCC, flopping back to the first
-  // iterator.
-  ++I;
-  EXPECT_NE(I, E);
-  LazyCallGraph::RefSCC &ARC = *I;
-  EXPECT_NE(&ARC, nullptr);
-  EXPECT_EQ(&ARC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "a1"))));
-  EXPECT_EQ(&ARC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "a2"))));
-  EXPECT_EQ(&ARC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "a3"))));
-  EXPECT_TRUE(ARC.isParentOf(BRC));
-  EXPECT_TRUE(ARC.isParentOf(CRC));
-  ++J;
-  EXPECT_EQ(I, J);
-  EXPECT_EQ(&ARC, &*J) << "Actual RefSCC: " << *J;
-  ++I;
-  EXPECT_EQ(E, I);
-  ++J;
-  EXPECT_EQ(E, J);
-}
-
 TEST(LazyCallGraphTest, InternalEdgeMutation) {
   LLVMContext Context;
   std::unique_ptr<Module> M = parseAssembly(Context, "define void @a() {\n"
                                                      "entry:\n"
                                                      "  call void @b()\n"
                                                      "  ret void\n"
                                                      "}\n"
                                                      "define void @b() {\n"
                                                      "entry:\n"
                                                      "  call void @c()\n"
                                                      "  ret void\n"
                                                      "}\n"
                                                      "define void @c() {\n"
                                                      "entry:\n"
                                                      "  call void @a()\n"
                                                      "  ret void\n"
                                                      "}\n");
   LazyCallGraph CG(*M);
 
   // Force the graph to be fully expanded.
+  CG.buildRefSCCs();
   auto I = CG.postorder_ref_scc_begin();
   LazyCallGraph::RefSCC &RC = *I++;
   EXPECT_EQ(CG.postorder_ref_scc_end(), I);
 
   LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a"));
   LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b"));
   LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c"));
   EXPECT_EQ(&RC, CG.lookupRefSCC(A));
std::unique_ptr<Module> M = parseAssembly(
                "  store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n"
                "  store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n"
                "  store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n"
                "  ret void\n"
                "}\n");
   LazyCallGraph CG(*M);
 
   // Force the graph to be fully expanded.
+  CG.buildRefSCCs();
   auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end();
   LazyCallGraph::RefSCC &RC = *I;
   EXPECT_EQ(E, std::next(I));
 
   LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a"));
   LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b"));
   LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c"));
   EXPECT_EQ(&RC, CG.lookupRefSCC(A));
std::unique_ptr<Module> M = parseAssembly(
                "entry:\n"
                "  call void @a(i8** %ptr)\n"
                "  store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n"
                "  ret void\n"
                "}\n");
   LazyCallGraph CG(*M);
 
   // Force the graph to be fully expanded.
+  CG.buildRefSCCs();
   auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end();
   LazyCallGraph::RefSCC &RC = *I;
   EXPECT_EQ(E, std::next(I));
 
   LazyCallGraph::SCC &C = *RC.begin();
   EXPECT_EQ(RC.end(), std::next(RC.begin()));
 
   LazyCallGraph::Node &AN = *CG.lookup(lookupFunction(*M, "a"));
std::unique_ptr<Module> M = parseAssembly(Context, "define void @a() {\n"
                                                      "  call void @a()\n"
                                                      "  call void @b()\n"
                                                      "  call void @c()\n"
                                                      "  ret void\n"
                                                      "}\n");
   LazyCallGraph CG(*M);
 
   // Force the graph to be fully expanded.
+  CG.buildRefSCCs();
   auto I = CG.postorder_ref_scc_begin();
   LazyCallGraph::RefSCC &RC = *I++;
   EXPECT_EQ(CG.postorder_ref_scc_end(), I);
 
   EXPECT_EQ(1, RC.size());
   LazyCallGraph::SCC &AC = *RC.begin();
 
   LazyCallGraph::Node &AN = *CG.lookup(lookupFunction(*M, "a"));
std::unique_ptr<Module> M =
                              "define void @d() {\n"
                              "entry:\n"
                              "  store void()* @a, void()** undef\n"
                              "  ret void\n"
                              "}\n");
   LazyCallGraph CG(*M);
 
   // Force the graph to be fully expanded.
+  CG.buildRefSCCs();
   auto I = CG.postorder_ref_scc_begin();
   LazyCallGraph::RefSCC &RC = *I++;
   EXPECT_EQ(CG.postorder_ref_scc_end(), I);
 
   LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a"));
   LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b"));
   LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c"));
   LazyCallGraph::Node &D = *CG.lookup(lookupFunction(*M, "d"));
std::unique_ptr<Module> M =
                              "define void @d() {\n"
                              "entry:\n"
                              "  store void()* @a, void()** undef\n"
                              "  ret void\n"
                              "}\n");
   LazyCallGraph CG(*M);
 
   // Force the graph to be fully expanded.
+  CG.buildRefSCCs();
   auto I = CG.postorder_ref_scc_begin();
   LazyCallGraph::RefSCC &RC = *I++;
   EXPECT_EQ(CG.postorder_ref_scc_end(), I);
 
   LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a"));
   LazyCallGraph::Node &B1 = *CG.lookup(lookupFunction(*M, "b1"));
   LazyCallGraph::Node &B2 = *CG.lookup(lookupFunction(*M, "b2"));
   LazyCallGraph::Node &B3 = *CG.lookup(lookupFunction(*M, "b3"));
std::unique_ptr<Module> M =
                              "define void @g() {\n"
                              "entry:\n"
                              "  store void()* @a, void()** undef\n"
                              "  ret void\n"
                              "}\n");
   LazyCallGraph CG(*M);
 
   // Force the graph to be fully expanded.
+  CG.buildRefSCCs();
   auto I = CG.postorder_ref_scc_begin();
   LazyCallGraph::RefSCC &RC = *I++;
   EXPECT_EQ(CG.postorder_ref_scc_end(), I);
 
   LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a"));
   LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b"));
   LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c"));
   LazyCallGraph::Node &D = *CG.lookup(lookupFunction(*M, "d"));
std::unique_ptr<Module> M =
                              "}\n"
                              "define void @g(i8** %ptr) {\n"
                              "entry:\n"
                              "  store i8* blockaddress(@f, %bb), i8** %ptr\n"
                              "  ret void\n"
                              "}\n");
   LazyCallGraph CG(*M);
 
+  CG.buildRefSCCs();
   auto I = CG.postorder_ref_scc_begin();
   LazyCallGraph::RefSCC &FRC = *I++;
   LazyCallGraph::RefSCC &GRC = *I++;
   EXPECT_EQ(CG.postorder_ref_scc_end(), I);
 
   LazyCallGraph::Node &F = *CG.lookup(lookupFunction(*M, "f"));
   LazyCallGraph::Node &G = *CG.lookup(lookupFunction(*M, "g"));
   EXPECT_EQ(&FRC, CG.lookupRefSCC(F));
   EXPECT_EQ(&GRC, CG.lookupRefSCC(G));
   EXPECT_TRUE(GRC.isParentOf(FRC));
 }
 
 }