[LCG] Redesign the lazy post-order iteration mechanism for the LazyCallGraph to support repeated, stable iterations, even in the face of graph updates.

[chandlerc]

Summary

This is particularly important to allow the CGSCC pass manager to walk
the RefSCCs (and thus everything else) in a module more than once. Lots
of unittests and other tests were hard or impossible to write because
repeated CGSCC pass managers which didn't invalidate the LazyCallGraph
would conclude the module was empty after the first one. =[ Really,
really bad.

The interesting thing is that in many ways this simplifies the code. We
can now re-use the same code for handling reference edge insertion
updates of the RefSCC graph as we use for handling call edge insertion
updates of the SCC graph. Outside of adapting to the shared logic for
this (which isn't trivial, but is *much* simpler than the DFS it
replaces!), the new code involves putting newly created RefSCCs when
deleting a reference edge into the cached list in the correct way, and
to re-formulate the iterator to be stable and effective even in the face
of these kinds of updates.

I've updated the unittests for the LazyCallGraph to re-iterate the
postorder sequence and verify that this all works. We even check for
using alternating iterators to trigger the lazy formation of RefSCCs
after mutation has occured.

It's worth noting that there are a reasonable number of likely simplifications
we can make past this. It isn't clear that we need to keep the "LeafRefSCCs"
around any more. But I've not removed that mostly because I want this to be
a more isolated change.

[eraman]

lib/Analysis/LazyCallGraph.cpp

804 ↗

(On Diff #70285)

Nit: RefSCC in place of SCC in assert messages here and below.

830 ↗

(On Diff #70285)

Why are ref edges excluded here?

906 ↗

(On Diff #70285)

The node to SCC mapping doesn't change right?

[chandlerc]

Thanks so much for the review! See responses below.

lib/Analysis/LazyCallGraph.cpp

804 ↗

(On Diff #70285)

Great catch! Thanks, and fixed. I think I have several more of these that I'm gonna do a pass over this entire code to clean up afterward...

830 ↗

(On Diff #70285)

Yikes!

Because this code is based originally on the code for call edges, and I didn't update this.

I've updated the tests to actually check that this works in graphs composed of reference cycles rather than call cycles.

906 ↗

(On Diff #70285)

Correct, this should be a no-op. But I'd prefer to remove it in a separate commit as this was already here and I'm not changing the fact that it isn't needed. =] Good catch though.

Sadly, I can't really test for this as it is in fact a no-op. Even an assert doesn't really seem valuable here.

[chandlerc]

Updated with better assert strings, a big "DOH!" bug fix, and an important
added test case to cover that bug fix. Many thanks to Easwaran for the review
that found these issues.

[eraman]

lib/Analysis/LazyCallGraph.cpp

883 ↗

(On Diff #70666)

The comment is stale now since there is no DAG walk above anymore.

888 ↗

(On Diff #70666)

I don't think you should be reversing the MergeRange here. Consider this example where you have three RefSCCs R0, R1 and R2 with the numbers being index to the PostOrderRefSCCs. Assume R2 is this RefSCC and the edge being added is from R0 -> R2. Assume each Ri has one Si (call SCC). MergeRange is [R0, R1]. At the end of this loop, MergedSCCs will have [S1, S0] and outside the loop S2 gets added to MergedSCCs resulting in [S1, S0, S2]. I believe you want it to be [S0, S1, S2] to keep it in post order.

The unit test below doesn't test that call SCC's are in post-order. Ensuring verify on the merged RefSCC doesn't assert helps in general (but still won't catch this)

[chandlerc]

lib/Analysis/LazyCallGraph.cpp

888 ↗

(On Diff #70666)

Arrg, still more things that need a more complex test case to trigger.

I've added a couple more tests that exercise this and some other aspects of the code. They cause the verify below to catch this bug, as well as independently verifying the postorder result.

Thanks again!

[chandlerc]

Update with more tests and a fix nicely spotted by Easwaran during review.

[sanjoy]

Some comments inline.

include/llvm/Analysis/LazyCallGraph.h

920 ↗

(On Diff #70970)

Not sure what you mean by "Only RefSCCs which have been created while walking the graph" -- what else is there?

lib/Analysis/LazyCallGraph.cpp

892 ↗

(On Diff #70970)

copy_if ?

937 ↗

(On Diff #70970)

I know this isn't new, but does it make sense to erase the erased RefSCCs from RefSCCIndices too?

1221 ↗

(On Diff #70970)

How about adding an accessor to LCG like getIndexForRefSCC that verifies that the index into the postorder is correct?

1225 ↗

(On Diff #70970)

Use llvm::seq ?

1588 ↗

(On Diff #70970)

*sequence

827 ↗

(On Diff #70666)

Why can't you do a DFS on the parent edges starting from SourceC, and bound it by the range in the postorder list?

870 ↗

(On Diff #70666)

s/SCCs/RefSCCs/ right?

Also, I know this is "controversial", but I think using an explicit type for MergeRange here is actually going to be more readable.

874 ↗

(On Diff #70666)

Nice!

1215 ↗

(On Diff #70666)

s/sequnece/sequence/

[chandlerc]

Working others, but a quick comment below:

lib/Analysis/LazyCallGraph.cpp

827 ↗

(On Diff #70970)

I mean, I could. Do you think that would be simpler? It seems like it would be strictly more complicated than this, and still O(edges), so it didn't seem like it was worth pursuing. But I'm happy to try it out if you think it'd be an improvement.

[eraman]

lib/Analysis/LazyCallGraph.cpp

827 ↗

(On Diff #70970)

Isn't what Sanjoy proposing O(|edges in RefSCC DAG|) which is a tighter bound than O(|edges in the callgraph|) of the current implementation?

unittests/Analysis/LazyCallGraphTest.cpp

1082 ↗

(On Diff #70970)

Incorrect comment. No calls in this RefSCC.

[sanjoy]

lib/Analysis/LazyCallGraph.cpp

827 ↗

(On Diff #70970)

Do you think that would be simpler?

Not in a one-to-one comparison, but perhaps you could write it in a way that can be shared with ComputeTargetConnectedSet ?

+ What @eraman said.

[chandlerc]

Thanks for all the comments Sanjoy and Easwaran!

include/llvm/Analysis/LazyCallGraph.h

920 ↗

(On Diff #70970)

No idea. Removed.

lib/Analysis/LazyCallGraph.cpp

827 ↗

(On Diff #70970)

Sanjoy and I chatted about this on IRC and now I understand *much* better what your idea is here Sanjoy.

The idea is just to walk the parent edges to build connected sets. It's not the full complexity (in code) of Tarjan's, its just walking like this but with a nicer complexity bound.

However, thinking about this I think I've made this entire problem much more complex than is necessary. But the simplification I have in mind will impact both this code and the SCC caller, so I'd rather do that in a follow-up if its OK.

870–876 ↗

(On Diff #70970)

Done on the first count.

The type seems really long, opaque, and to add little value to me? It's: iterator_range<SmallVectorImpl<RefSCC *>::iterator>. That said, if it makes it easier to read, no problem. I've put it in here, and I can update the other caller.

To help me understand this better, what about seeing this type helps you read the code?

892 ↗

(On Diff #70970)

It's quite awkward to use. std::inserter doesn't help because the insert routine doesn't accept an iterator position (and even if it did, there is no meaningful iterator to provide).

We could use the range insert routine and a filtered iterator, but that seems also overkill.

1225 ↗

(On Diff #70970)

Hah, good idea!

[chandlerc]

Updates from codereview (and rebased).

[sanjoy]

lgtm modulo minor things here and there

include/llvm/Analysis/LazyCallGraph.h

975 ↗

(On Diff #71144)

Can we add an assert(PostOrderRefSCCs[IndexIt->second] == &RC) here?

lib/Analysis/LazyCallGraph.cpp

827 ↗

(On Diff #71144)

But the simplification I have in mind will impact both this code and the SCC caller, so I'd rather do that in a follow-up if its OK.

SGTM.

852–876 ↗

(On Diff #71144)

Okay, I agree that iterator_range<SmallVectorImpl<RefSCC *>::iterator> isn't great. :)

However, I had made my suggestion under the assumption that updatePostorderSequenceForEdgeInsertion returns an ArrayRef<RefSCC *>. Does changing updatePostorderSequenceForEdgeInsertion to return ArrayRef<RefSCC *> sound generally cleaner?

In any case, there's no reason to hold checking this on this specific point, it's very minor.

895 ↗

(On Diff #71144)

Not clear what "This RefSCC should terminate the DFS without being reached." means now.

900 ↗

(On Diff #71144)

Ok.

1222 ↗

(On Diff #71144)

There's one more ("sequnece").

unittests/Analysis/LazyCallGraphTest.cpp

142 ↗

(On Diff #71144)

Are the trailing \n 's needed? Seems like we should be able to replace them with spaces (which may look less distracting).

581 ↗

(On Diff #71144)

Writing to dbgs() seems fairly uncommon in unittests/ (I only see one other instance). I
can't see any obvious reason why this will be a problem, but perhaps there is a reason why it is usually avoided?

895 ↗

(On Diff #71144)

Can this sequence be a C macro or a C++ class with A1, A2 etc. as fields (in the latter case all of the lookup logic could be in a constructor or some helper function)? Right now this is repeated a few times.

1018 ↗

(On Diff #71144)

llvm::find (here and below)?

1082 ↗

(On Diff #71144)

@eraman 's comment has not been addressed.

[chandlerc]

Thanks all! Adjustments made, landed.

Easwaran, if you have more comments, don't hesitate to post them and I'll keep track here. I've still got a few things to clean up post-submit anyways.

lib/Analysis/LazyCallGraph.cpp

852–876 ↗

(On Diff #71144)

Doesn't really work ... we hand the range to erase, etc. We could hack it with addresses into the ArrayRef, but that seems pretty gross. Happy to keep tweaking the API though...

unittests/Analysis/LazyCallGraphTest.cpp

142 ↗

(On Diff #71144)

I think so. But can try some stuff with this whole file in a follow-up commit.

581 ↗

(On Diff #71144)

No idea, it made debugging this stuff easier and it seems harmless...

895 ↗

(On Diff #71144)

Yea, I'd like to refactor a bunch of this, probably in a follow-up. The repeated pattern got a lot more frequent somewhat organically.

1082 ↗

(On Diff #71144)

Doh, sorry I missed this. Thanks!

llvm/trunk/include/llvm/Analysis/LazyCallGraph.h

class 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 *C;
+    RefSCC *RC;
 
-    // Build the begin iterator for a node.
-    postorder_ref_scc_iterator(LazyCallGraph &G) : G(&G) {
-      C = G.getNextRefSCCInPostOrder();
-    }
+    /// 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.
+    /// Build the end iterator for a node. This is selected purely by overload.
     postorder_ref_scc_iterator(LazyCallGraph &G, IsAtEndT /*Nonce*/)
-        : G(&G), C(nullptr) {}
+        : 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 && C == Arg.C;
+      return G == Arg.G && RC == Arg.RC;
     }
 
-    reference operator*() const { return *C; }
+    reference operator*() const { return *RC; }
 
     using iterator_facade_base::operator++;
     postorder_ref_scc_iterator &operator++() {
-      C = G->getNextRefSCCInPostOrder();
+      assert(RC && "Cannot increment the end iterator!");
+      RC = getRC(*G, G->RefSCCIndices.find(RC)->second + 1);
       return *this;
     }
   };
 
   /// Construct a graph for the given module.
   ///
   /// This sets up the graph and computes all of the entry points of the graph.
   /// No function definitions are scanned until their nodes in the graph are
private:
   SpecificBumpPtrAllocator<SCC> SCCBPA;
 
   /// Maps Function -> SCC for fast lookup.
   DenseMap<Node *, SCC *> SCCMap;
 
   /// Allocator that holds all the call graph RefSCCs.
   SpecificBumpPtrAllocator<RefSCC> RefSCCBPA;
 
+  /// The post-order sequence of RefSCCs.
+  ///
+  /// This list is lazily formed the first time we walk the graph.
+  SmallVector<RefSCC *, 16> PostOrderRefSCCs;
+
+  /// A map from RefSCC to the index for it in the postorder sequence of
+  /// RefSCCs.
+  DenseMap<RefSCC *, int> RefSCCIndices;
+
   /// The leaf RefSCCs of the graph.
   ///
   /// These are all of the RefSCCs which have no children.
   SmallVector<RefSCC *, 4> LeafRefSCCs;
 
   /// Stack of nodes in the DFS walk.
   SmallVector<std::pair<Node *, edge_iterator>, 4> DFSStack;
 
private:
   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);
 
-  /// Retrieve the next node in the post-order RefSCC walk of the call graph.
-  RefSCC *getNextRefSCCInPostOrder();
+  /// 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();

llvm/trunk/lib/Analysis/LazyCallGraph.cpp

 //===- LazyCallGraph.cpp - Analysis of a Module's call graph --------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/LazyCallGraph.h"
 #include "llvm/ADT/ScopeExit.h"
+#include "llvm/ADT/Sequence.h"
 #include "llvm/ADT/STLExtras.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"
 

 #ifndef NDEBUG
   // Check that the RefSCC is still valid.
   verify();
 #endif
 }
 
 SmallVector<LazyCallGraph::RefSCC *, 1>
 LazyCallGraph::RefSCC::insertIncomingRefEdge(Node &SourceN, Node &TargetN) {
-  assert(G->lookupRefSCC(TargetN) == this && "Target must be in this SCC.");
+  assert(G->lookupRefSCC(TargetN) == this && "Target must be in this RefSCC.");
+  RefSCC &SourceC = *G->lookupRefSCC(SourceN);
+  assert(&SourceC != this && "Source must not be in this RefSCC.");
+  assert(SourceC.isDescendantOf(*this) &&
+         "Source must be a descendant of the Target.");
+
+  SmallVector<RefSCC *, 1> DeletedRefSCCs;
 
 #ifndef NDEBUG
   // In a debug build, verify the RefSCC is valid to start with and when this
   // routine finishes.
   verify();
   auto VerifyOnExit = make_scope_exit([&]() { verify(); });
 #endif
 
-  // We store the RefSCCs found to be connected in postorder so that we can use
-  // that when merging. We also return this to the caller to allow them to
-  // invalidate information pertaining to these RefSCCs.
-  SmallVector<RefSCC *, 1> Connected;
-
-  RefSCC &SourceC = *G->lookupRefSCC(SourceN);
-  assert(&SourceC != this && "Source must not be in this SCC.");
-  assert(SourceC.isDescendantOf(*this) &&
-         "Source must be a descendant of the Target.");
-
-  // The algorithm we use for merging SCCs based on the cycle introduced here
-  // is to walk the RefSCC inverted DAG formed by the parent sets. The inverse
-  // graph has the same cycle properties as the actual DAG of the RefSCCs, and
-  // when forming RefSCCs lazily by a DFS, the bottom of the graph won't exist
-  // in many cases which should prune the search space.
-  //
-  // FIXME: We can get this pruning behavior even after the incremental RefSCC
-  // formation by leaving behind (conservative) DFS numberings in the nodes,
-  // and pruning the search with them. These would need to be cleverly updated
-  // during the removal of intra-SCC edges, but could be preserved
-  // conservatively.
-  //
-  // FIXME: This operation currently creates ordering stability problems
-  // because we don't use stably ordered containers for the parent SCCs.
-
-  // The set of RefSCCs that are connected to the parent, and thus will
-  // participate in the merged connected component.
-  SmallPtrSet<RefSCC *, 8> ConnectedSet;
-  ConnectedSet.insert(this);
-
-  // We build up a DFS stack of the parents chains.
-  SmallVector<std::pair<RefSCC *, parent_iterator>, 8> DFSStack;
-  SmallPtrSet<RefSCC *, 8> Visited;
-  int ConnectedDepth = -1;
-  DFSStack.push_back({&SourceC, SourceC.parent_begin()});
+  int SourceIdx = G->RefSCCIndices[&SourceC];
+  int TargetIdx = G->RefSCCIndices[this];
+  assert(SourceIdx < TargetIdx &&
+         "Postorder list doesn't see edge as incoming!");
+
+  // Compute the RefSCCs which (transitively) reach the source. We do this by
+  // working backwards from the source using the parent set in each RefSCC,
+  // skipping any RefSCCs that don't fall in the postorder range. This has the
+  // advantage of walking the sparser parent edge (in high fan-out graphs) but
+  // more importantly this removes examining all forward edges in all RefSCCs
+  // within the postorder range which aren't in fact connected. Only connected
+  // RefSCCs (and their edges) are visited here.
+  auto ComputeSourceConnectedSet = [&](SmallPtrSetImpl<RefSCC *> &Set) {
+    Set.insert(&SourceC);
+    SmallVector<RefSCC *, 4> Worklist;
+    Worklist.push_back(&SourceC);
     do {
-    auto DFSPair = DFSStack.pop_back_val();
-    RefSCC *C = DFSPair.first;
-    parent_iterator I = DFSPair.second;
-    auto E = C->parent_end();
+      RefSCC &RC = *Worklist.pop_back_val();
+      for (RefSCC &ParentRC : RC.parents()) {
+        // Skip any RefSCCs outside the range of source to target in the
+        // postorder sequence.
+        int ParentIdx = G->getRefSCCIndex(ParentRC);
+        assert(ParentIdx > SourceIdx && "Parent cannot precede source in postorder!");
+        if (ParentIdx > TargetIdx)
+          continue;
+        if (Set.insert(&ParentRC).second)
+          // First edge connecting to this parent, add it to our worklist.
+          Worklist.push_back(&ParentRC);
+      }
+    } while (!Worklist.empty());
+  };
 
-    while (I != E) {
-      RefSCC &Parent = *I++;
+  // Use a normal worklist to find which SCCs the target connects to. We still
+  // bound the search based on the range in the postorder list we care about,
+  // but because this is forward connectivity we just "recurse" through the
+  // edges.
+  auto ComputeTargetConnectedSet = [&](SmallPtrSetImpl<RefSCC *> &Set) {
+    Set.insert(this);
+    SmallVector<RefSCC *, 4> Worklist;
+    Worklist.push_back(this);
+    do {
+      RefSCC &RC = *Worklist.pop_back_val();
+      for (SCC &C : RC)
+        for (Node &N : C)
+          for (Edge &E : N) {
+            assert(E.getNode() && "Must have formed a node!");
+            RefSCC &EdgeRC = *G->lookupRefSCC(*E.getNode());
+            if (G->getRefSCCIndex(EdgeRC) <= SourceIdx)
+              // Not in the postorder sequence between source and target.
+              continue;
 
-      // If we have already processed this parent SCC, skip it, and remember
-      // whether it was connected so we don't have to check the rest of the
-      // stack. This also handles when we reach a child of the 'this' SCC (the
-      // callee) which terminates the search.
-      if (ConnectedSet.count(&Parent)) {
-        assert(ConnectedDepth < (int)DFSStack.size() &&
-               "Cannot have a connected depth greater than the DFS depth!");
-        ConnectedDepth = DFSStack.size();
-        continue;
-      }
-      if (Visited.count(&Parent))
-        continue;
-
-      // We fully explore the depth-first space, adding nodes to the connected
-      // set only as we pop them off, so "recurse" by rotating to the parent.
-      DFSStack.push_back({C, I});
-      C = &Parent;
-      I = C->parent_begin();
-      E = C->parent_end();
-    }
-
-    // If we've found a connection anywhere below this point on the stack (and
-    // thus up the parent graph from the caller), the current node needs to be
-    // added to the connected set now that we've processed all of its parents.
-    if ((int)DFSStack.size() == ConnectedDepth) {
-      --ConnectedDepth; // We're finished with this connection.
-      bool Inserted = ConnectedSet.insert(C).second;
-      (void)Inserted;
-      assert(Inserted && "Cannot insert a refSCC multiple times!");
-      Connected.push_back(C);
-    } else {
-      // Otherwise remember that its parents don't ever connect.
-      assert(ConnectedDepth < (int)DFSStack.size() &&
-             "Cannot have a connected depth greater than the DFS depth!");
-      Visited.insert(C);
+            if (Set.insert(&EdgeRC).second)
+              Worklist.push_back(&EdgeRC);
           }
-  } while (!DFSStack.empty());
+    } while (!Worklist.empty());
+  };
+
+  // Use a generic helper to update the postorder sequence of RefSCCs and return
+  // a range of any RefSCCs connected into a cycle by inserting this edge. This
+  // routine will also take care of updating the indices into the postorder
+  // sequence.
+  iterator_range<SmallVectorImpl<RefSCC *>::iterator> MergeRange =
+      updatePostorderSequenceForEdgeInsertion(
+          SourceC, *this, G->PostOrderRefSCCs, G->RefSCCIndices,
+          ComputeSourceConnectedSet, ComputeTargetConnectedSet);
+
+  // Build a set so we can do fast tests for whether a merge is occuring.
+  SmallPtrSet<RefSCC *, 16> MergeSet(MergeRange.begin(), MergeRange.end());
 
   // Now that we have identified all of the SCCs which need to be merged into
   // a connected set with the inserted edge, merge all of them into this SCC.
-  // We walk the newly connected RefSCCs in the reverse postorder of the parent
-  // DAG walk above and merge in each of their SCC postorder lists. This
-  // ensures a merged postorder SCC list.
   SmallVector<SCC *, 16> MergedSCCs;
   int SCCIndex = 0;
-  for (RefSCC *C : reverse(Connected)) {
-    assert(C != this &&
-           "This RefSCC should terminate the DFS without being reached.");
+  for (RefSCC *RC : MergeRange) {
+    assert(RC != this && "We're merging into the target RefSCC, so it "
+                         "shouldn't be in the range.");
 
     // Merge the parents which aren't part of the merge into the our parents.
-    for (RefSCC *ParentC : C->Parents)
-      if (!ConnectedSet.count(ParentC))
-        Parents.insert(ParentC);
-    C->Parents.clear();
+    for (RefSCC *ParentRC : RC->Parents)
+      if (!MergeSet.count(ParentRC))
+        Parents.insert(ParentRC);
+    RC->Parents.clear();
 
     // Walk the inner SCCs to update their up-pointer and walk all the edges to
     // update any parent sets.
     // FIXME: We should try to find a way to avoid this (rather expensive) edge
     // walk by updating the parent sets in some other manner.
-    for (SCC &InnerC : *C) {
+    for (SCC &InnerC : *RC) {
       InnerC.OuterRefSCC = this;
       SCCIndices[&InnerC] = SCCIndex++;
       for (Node &N : InnerC) {
         G->SCCMap[&N] = &InnerC;
         for (Edge &E : N) {
           assert(E.getNode() &&
                  "Cannot have a null node within a visited SCC!");
           RefSCC &ChildRC = *G->lookupRefSCC(*E.getNode());
-          if (ConnectedSet.count(&ChildRC))
+          if (MergeSet.count(&ChildRC))
             continue;
-          ChildRC.Parents.erase(C);
+          ChildRC.Parents.erase(RC);
           ChildRC.Parents.insert(this);
         }
       }
     }
 
     // Now merge in the SCCs. We can actually move here so try to reuse storage
     // the first time through.
     if (MergedSCCs.empty())
-      MergedSCCs = std::move(C->SCCs);
+      MergedSCCs = std::move(RC->SCCs);
     else
-      MergedSCCs.append(C->SCCs.begin(), C->SCCs.end());
-    C->SCCs.clear();
+      MergedSCCs.append(RC->SCCs.begin(), RC->SCCs.end());
+    RC->SCCs.clear();
+    DeletedRefSCCs.push_back(RC);
   }
 
-  // Finally append our original SCCs to the merged list and move it into
-  // place.
+  // Append our original SCCs to the merged list and move it into place.
   for (SCC &InnerC : *this)
     SCCIndices[&InnerC] = SCCIndex++;
   MergedSCCs.append(SCCs.begin(), SCCs.end());
   SCCs = std::move(MergedSCCs);
 
+  // Remove the merged away RefSCCs from the post order sequence.
+  for (RefSCC *RC : MergeRange)
+    G->RefSCCIndices.erase(RC);
+  int IndexOffset = MergeRange.end() - MergeRange.begin();
+  auto EraseEnd =
+      G->PostOrderRefSCCs.erase(MergeRange.begin(), MergeRange.end());
+  for (RefSCC *RC : make_range(EraseEnd, G->PostOrderRefSCCs.end()))
+    G->RefSCCIndices[RC] -= IndexOffset;
+
   // At this point we have a merged RefSCC with a post-order SCCs list, just
   // connect the nodes to form the new edge.
   SourceN.insertEdgeInternal(TargetN, Edge::Ref);
 
   // We return the list of SCCs which were merged so that callers can
   // invalidate any data they have associated with those SCCs. Note that these
   // SCCs are no longer in an interesting state (they are totally empty) but
   // the pointers will remain stable for the life of the graph itself.
-  return Connected;
+  return DeletedRefSCCs;
 }
 
 void LazyCallGraph::RefSCC::removeOutgoingEdge(Node &SourceN, Node &TargetN) {
   assert(G->lookupRefSCC(SourceN) == this &&
          "The source must be a member of this RefSCC.");
 
   RefSCC &TargetRC = *G->lookupRefSCC(TargetN);
   assert(&TargetRC != this && "The target must not be a member of this RefSCC");
#endif
   // We now have a post-order numbering for RefSCCs and a mapping from each
   // node in this RefSCC to its final RefSCC. We create each new RefSCC node
   // (re-using this RefSCC node for the root) and build a radix-sort style map
   // from postorder number to the RefSCC. We then append SCCs to each of these
   // RefSCCs in the order they occured in the original SCCs container.
   for (int i = 1; i < PostOrderNumber; ++i)
     Result.push_back(G->createRefSCC(*G));
 
+  // Insert the resulting postorder sequence into the global graph postorder
+  // sequence before the current RefSCC in that sequence. The idea being that
+  // this RefSCC is the target of the reference edge removed, and thus has
+  // a direct or indirect edge to every other RefSCC formed and so must be at
+  // the end of any postorder traversal.
+  //
+  // FIXME: It'd be nice to change the APIs so that we returned an iterator
+  // range over the global postorder sequence and generally use that sequence
+  // rather than building a separate result vector here.
+  if (!Result.empty()) {
+    int Idx = G->getRefSCCIndex(*this);
+    G->PostOrderRefSCCs.insert(G->PostOrderRefSCCs.begin() + Idx,
+                               Result.begin(), Result.end());
+    for (int i : seq<int>(Idx, G->PostOrderRefSCCs.size()))
+      G->RefSCCIndices[G->PostOrderRefSCCs[i]] = i;
+    assert(G->PostOrderRefSCCs[G->getRefSCCIndex(*this)] == this &&
+           "Failed to update this RefSCC's index after insertion!");
+  }
+
   for (SCC *C : SCCs) {
     auto PostOrderI = PostOrderMapping.find(&*C->begin());
     assert(PostOrderI != PostOrderMapping.end() &&
            "Cannot have missing mappings for nodes!");
     int SCCNumber = PostOrderI->second;
 #ifndef NDEBUG
     for (Node &N : *C)
       assert(PostOrderMapping.find(&N)->second == SCCNumber &&
for (Node &N : C)
         IsLeaf = false;
       }
 
   // For the SCCs where we fine no child SCCs, add them to the leaf list.
   if (IsLeaf)
     LeafRefSCCs.push_back(&RC);
 }
 
-LazyCallGraph::RefSCC *LazyCallGraph::getNextRefSCCInPostOrder() {
+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 nullptr;
+        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 (;;) {
     // 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());
 
-    // We return the new node here. This essentially suspends the DFS walk
-    // until another RefSCC is requested.
-    return NewRC;
+    // 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;
   }
 }
 
 char LazyCallGraphAnalysis::PassID;
 
 LazyCallGraphPrinterPass::LazyCallGraphPrinterPass(raw_ostream &OS) : OS(OS) {}
 
 static void printNode(raw_ostream &OS, LazyCallGraph::Node &N) {

llvm/trunk/unittests/Analysis/LazyCallGraphTest.cpp

static const char DiamondOfTriangles[] =
      "  ret void\n"
      "}\n"
      "define void @d3() {\n"
      "entry:\n"
      "  call void @d1()\n"
      "  ret void\n"
      "}\n";
 
+/*
+   IR forming a reference graph with a diamond of triangle-shaped RefSCCs
+
+           d1
+          /  \
+         d3--d2
+        /     \
+       b1     c1
+     /  \    /  \
+    b3--b2  c3--c2
+         \  /
+          a1
+         /  \
+        a3--a2
+
+   All call edges go up between RefSCCs, and clockwise around the RefSCC.
+ */
+static const char DiamondOfTrianglesRefGraph[] =
+     "define void @a1() {\n"
+     "entry:\n"
+     "  %a = alloca void ()*\n"
+     "  store void ()* @a2, void ()** %a\n"
+     "  store void ()* @b2, void ()** %a\n"
+     "  store void ()* @c3, void ()** %a\n"
+     "  ret void\n"
+     "}\n"
+     "define void @a2() {\n"
+     "entry:\n"
+     "  %a = alloca void ()*\n"
+     "  store void ()* @a3, void ()** %a\n"
+     "  ret void\n"
+     "}\n"
+     "define void @a3() {\n"
+     "entry:\n"
+     "  %a = alloca void ()*\n"
+     "  store void ()* @a1, void ()** %a\n"
+     "  ret void\n"
+     "}\n"
+     "define void @b1() {\n"
+     "entry:\n"
+     "  %a = alloca void ()*\n"
+     "  store void ()* @b2, void ()** %a\n"
+     "  store void ()* @d3, void ()** %a\n"
+     "  ret void\n"
+     "}\n"
+     "define void @b2() {\n"
+     "entry:\n"
+     "  %a = alloca void ()*\n"
+     "  store void ()* @b3, void ()** %a\n"
+     "  ret void\n"
+     "}\n"
+     "define void @b3() {\n"
+     "entry:\n"
+     "  %a = alloca void ()*\n"
+     "  store void ()* @b1, void ()** %a\n"
+     "  ret void\n"
+     "}\n"
+     "define void @c1() {\n"
+     "entry:\n"
+     "  %a = alloca void ()*\n"
+     "  store void ()* @c2, void ()** %a\n"
+     "  store void ()* @d2, void ()** %a\n"
+     "  ret void\n"
+     "}\n"
+     "define void @c2() {\n"
+     "entry:\n"
+     "  %a = alloca void ()*\n"
+     "  store void ()* @c3, void ()** %a\n"
+     "  ret void\n"
+     "}\n"
+     "define void @c3() {\n"
+     "entry:\n"
+     "  %a = alloca void ()*\n"
+     "  store void ()* @c1, void ()** %a\n"
+     "  ret void\n"
+     "}\n"
+     "define void @d1() {\n"
+     "entry:\n"
+     "  %a = alloca void ()*\n"
+     "  store void ()* @d2, void ()** %a\n"
+     "  ret void\n"
+     "}\n"
+     "define void @d2() {\n"
+     "entry:\n"
+     "  %a = alloca void ()*\n"
+     "  store void ()* @d3, void ()** %a\n"
+     "  ret void\n"
+     "}\n"
+     "define void @d3() {\n"
+     "entry:\n"
+     "  %a = alloca void ()*\n"
+     "  store void ()* @d1, void ()** %a\n"
+     "  ret void\n"
+     "}\n";
+
 TEST(LazyCallGraphTest, BasicGraphFormation) {
   LLVMContext Context;
   std::unique_ptr<Module> M = parseAssembly(Context, DiamondOfTriangles);
   LazyCallGraph CG(*M);
 
   // The order of the entry nodes should be stable w.r.t. the source order of
   // the IR, and everything in our module is an entry node, so just directly
   // build variables for each node.
TEST(LazyCallGraphTest, BasicGraphFormation) {
   EXPECT_EQ("d1", Nodes[0]);
   EXPECT_EQ("d2", Nodes[1]);
   EXPECT_EQ("d3", Nodes[2]);
   Nodes.clear();
   EXPECT_FALSE(D.isParentOf(D));
   EXPECT_FALSE(D.isChildOf(D));
   EXPECT_FALSE(D.isAncestorOf(D));
   EXPECT_FALSE(D.isDescendantOf(D));
+  EXPECT_EQ(&D, &*CG.postorder_ref_scc_begin());
 
   LazyCallGraph::RefSCC &C = *J++;
   ASSERT_EQ(1, C.size());
   for (LazyCallGraph::Node &N : *C.begin())
     Nodes.push_back(N.getFunction().getName());
   std::sort(Nodes.begin(), Nodes.end());
   EXPECT_EQ(3u, Nodes.size());
   EXPECT_EQ("c1", Nodes[0]);
   EXPECT_EQ("c2", Nodes[1]);
   EXPECT_EQ("c3", Nodes[2]);
   Nodes.clear();
   EXPECT_TRUE(C.isParentOf(D));
   EXPECT_FALSE(C.isChildOf(D));
   EXPECT_TRUE(C.isAncestorOf(D));
   EXPECT_FALSE(C.isDescendantOf(D));
+  EXPECT_EQ(&C, &*std::next(CG.postorder_ref_scc_begin()));
 
   LazyCallGraph::RefSCC &B = *J++;
   ASSERT_EQ(1, B.size());
   for (LazyCallGraph::Node &N : *B.begin())
     Nodes.push_back(N.getFunction().getName());
   std::sort(Nodes.begin(), Nodes.end());
   EXPECT_EQ(3u, Nodes.size());
   EXPECT_EQ("b1", Nodes[0]);
   EXPECT_EQ("b2", Nodes[1]);
   EXPECT_EQ("b3", Nodes[2]);
   Nodes.clear();
   EXPECT_TRUE(B.isParentOf(D));
   EXPECT_FALSE(B.isChildOf(D));
   EXPECT_TRUE(B.isAncestorOf(D));
   EXPECT_FALSE(B.isDescendantOf(D));
   EXPECT_FALSE(B.isAncestorOf(C));
   EXPECT_FALSE(C.isAncestorOf(B));
+  EXPECT_EQ(&B, &*std::next(CG.postorder_ref_scc_begin(), 2));
 
   LazyCallGraph::RefSCC &A = *J++;
   ASSERT_EQ(1, A.size());
   for (LazyCallGraph::Node &N : *A.begin())
     Nodes.push_back(N.getFunction().getName());
   std::sort(Nodes.begin(), Nodes.end());
   EXPECT_EQ(3u, Nodes.size());
   EXPECT_EQ("a1", Nodes[0]);
   EXPECT_EQ("a2", Nodes[1]);
   EXPECT_EQ("a3", Nodes[2]);
   Nodes.clear();
   EXPECT_TRUE(A.isParentOf(B));
   EXPECT_TRUE(A.isParentOf(C));
   EXPECT_FALSE(A.isParentOf(D));
   EXPECT_TRUE(A.isAncestorOf(B));
   EXPECT_TRUE(A.isAncestorOf(C));
   EXPECT_TRUE(A.isAncestorOf(D));
+  EXPECT_EQ(&A, &*std::next(CG.postorder_ref_scc_begin(), 3));
 
   EXPECT_EQ(CG.postorder_ref_scc_end(), J);
+  EXPECT_EQ(J, std::next(CG.postorder_ref_scc_begin(), 4));
 }
 
 static Function &lookupFunction(Module &M, StringRef Name) {
   for (Function &F : M)
     if (F.getName() == Name)
       return F;
   report_fatal_error("Couldn't find function!");
 }
std::unique_ptr<Module> M = parseAssembly(Context, "define void @a() {\n"
                                                      "define void @d() {\n"
                                                      "entry:\n"
                                                      "  ret void\n"
                                                      "}\n");
   LazyCallGraph CG(*M);
 
   // Force the graph to be fully expanded.
   for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs())
-    (void)RC;
+    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);
   LazyCallGraph::SCC &BC = *CG.lookupSCC(B);
   LazyCallGraph::SCC &CC = *CG.lookupSCC(C);
TEST(LazyCallGraphTest, IncomingEdgeInsertion) {
   //       /  \       |
   //      a3--a2      |
   //
   std::unique_ptr<Module> M = parseAssembly(Context, DiamondOfTriangles);
   LazyCallGraph CG(*M);
 
   // Force the graph to be fully expanded.
   for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs())
-    (void)RC;
+    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"));
   LazyCallGraph::Node &B3 = *CG.lookup(lookupFunction(*M, "b3"));
   LazyCallGraph::Node &C1 = *CG.lookup(lookupFunction(*M, "c1"));
TEST(LazyCallGraphTest, IncomingEdgeInsertion) {
   EXPECT_EQ(&CRC, CG.lookupRefSCC(C3));
   EXPECT_EQ(&CRC, CG.lookupRefSCC(D1));
   EXPECT_EQ(&CRC, CG.lookupRefSCC(D2));
   EXPECT_EQ(&CRC, CG.lookupRefSCC(D3));
 
   // And that ancestry tests have been updated.
   EXPECT_TRUE(ARC.isParentOf(CRC));
   EXPECT_TRUE(BRC.isParentOf(CRC));
+
+  // And verify the post-order walk reflects the updated structure.
+  auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end();
+  ASSERT_NE(I, E);
+  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);
TEST(LazyCallGraphTest, IncomingEdgeInsertionMidTraversal) {
   // 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));
 
-  // Check that we can form the last two RefSCCs now in a coherent way.
-  ++I;
-  EXPECT_NE(I, E);
-  LazyCallGraph::RefSCC &BRC = *I;
+  // 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.
+  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"));
+  LazyCallGraph::Node &B3 = *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"));
+  LazyCallGraph::RefSCC &ARC = *CG.lookupRefSCC(A1);
+  LazyCallGraph::RefSCC &BRC = *CG.lookupRefSCC(B1);
+  LazyCallGraph::RefSCC &CRC = *CG.lookupRefSCC(C1);
+  LazyCallGraph::RefSCC &DRC = *CG.lookupRefSCC(D1);
+  ASSERT_EQ(&ARC, CG.lookupRefSCC(A2));
+  ASSERT_EQ(&ARC, CG.lookupRefSCC(A3));
+  ASSERT_EQ(&BRC, CG.lookupRefSCC(B2));
+  ASSERT_EQ(&BRC, CG.lookupRefSCC(B3));
+  ASSERT_EQ(&CRC, CG.lookupRefSCC(C2));
+  ASSERT_EQ(&CRC, CG.lookupRefSCC(C3));
+  ASSERT_EQ(&DRC, CG.lookupRefSCC(D2));
+  ASSERT_EQ(&DRC, CG.lookupRefSCC(D3));
+  ASSERT_EQ(1, std::distance(D2.begin(), D2.end()));
+
+  // Add an edge to make the graph:
+  //
+  //         d1         |
+  //        /  \        |
+  //       d3--d2---.   |
+  //      /     \    |  |
+  //     b1     c1   |  |
+  //   /  \    /  \ /   |
+  //  b3--b2  c3--c2    |
+  //       \  /         |
+  //        a1          |
+  //       /  \         |
+  //      a3--a2        |
+  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 SCC sets.
+  EXPECT_EQ(&ARC, CG.lookupRefSCC(A1));
+  EXPECT_EQ(&ARC, CG.lookupRefSCC(A2));
+  EXPECT_EQ(&ARC, CG.lookupRefSCC(A3));
+  EXPECT_EQ(&BRC, CG.lookupRefSCC(B1));
+  EXPECT_EQ(&BRC, CG.lookupRefSCC(B2));
+  EXPECT_EQ(&BRC, CG.lookupRefSCC(B3));
+  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));
+
+  // And that ancestry tests have been updated.
+  EXPECT_TRUE(ARC.isParentOf(CRC));
+  EXPECT_TRUE(BRC.isParentOf(CRC));
+
+  // And verify the post-order walk reflects the updated structure.
+  auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end();
+  ASSERT_NE(I, E);
+  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, IncomingEdgeInsertionLargeCallCycle) {
+  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 @d()\n"
+                                                     "  ret void\n"
+                                                     "}\n"
+                                                     "define void @d() {\n"
+                                                     "entry:\n"
+                                                     "  ret void\n"
+                                                     "}\n");
+  LazyCallGraph CG(*M);
+
+  // Force the graph to be fully expanded.
+  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);
+  LazyCallGraph::SCC &BC = *CG.lookupSCC(B);
+  LazyCallGraph::SCC &CC = *CG.lookupSCC(C);
+  LazyCallGraph::SCC &DC = *CG.lookupSCC(D);
+  LazyCallGraph::RefSCC &ARC = *CG.lookupRefSCC(A);
+  LazyCallGraph::RefSCC &BRC = *CG.lookupRefSCC(B);
+  LazyCallGraph::RefSCC &CRC = *CG.lookupRefSCC(C);
+  LazyCallGraph::RefSCC &DRC = *CG.lookupRefSCC(D);
+
+  // Connect the top to the bottom forming a large RefSCC made up mostly of calls.
+  auto MergedRCs = ARC.insertIncomingRefEdge(D, A);
+  // Make sure we connected the nodes.
+  EXPECT_NE(D.begin(), D.end());
+  EXPECT_EQ(&A, D.begin()->getNode());
+
+  // Check that we have the dead RCs, but ignore the order.
+  EXPECT_EQ(3u, MergedRCs.size());
+  EXPECT_NE(find(MergedRCs, &BRC), MergedRCs.end());
+  EXPECT_NE(find(MergedRCs, &CRC), MergedRCs.end());
+  EXPECT_NE(find(MergedRCs, &DRC), MergedRCs.end());
+
+  // Make sure the nodes point to the right place now.
+  EXPECT_EQ(&ARC, CG.lookupRefSCC(A));
+  EXPECT_EQ(&ARC, CG.lookupRefSCC(B));
+  EXPECT_EQ(&ARC, CG.lookupRefSCC(C));
+  EXPECT_EQ(&ARC, CG.lookupRefSCC(D));
+
+  // Check that the SCCs are in postorder.
+  EXPECT_EQ(4, ARC.size());
+  EXPECT_EQ(&DC, &ARC[0]);
+  EXPECT_EQ(&CC, &ARC[1]);
+  EXPECT_EQ(&BC, &ARC[2]);
+  EXPECT_EQ(&AC, &ARC[3]);
+
+  // And verify the post-order walk reflects the updated structure.
+  auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end();
+  ASSERT_NE(I, E);
+  EXPECT_EQ(&ARC, &*I) << "Actual RefSCC: " << *I;
+  EXPECT_EQ(++I, E);
+}
+
+TEST(LazyCallGraphTest, IncomingEdgeInsertionLargeRefCycle) {
+  LLVMContext Context;
+  std::unique_ptr<Module> M =
+      parseAssembly(Context, "define void @a() {\n"
+                             "entry:\n"
+                             "  %p = alloca void ()*\n"
+                             "  store void ()* @b, void ()** %p\n"
+                             "  ret void\n"
+                             "}\n"
+                             "define void @b() {\n"
+                             "entry:\n"
+                             "  %p = alloca void ()*\n"
+                             "  store void ()* @c, void ()** %p\n"
+                             "  ret void\n"
+                             "}\n"
+                             "define void @c() {\n"
+                             "entry:\n"
+                             "  %p = alloca void ()*\n"
+                             "  store void ()* @d, void ()** %p\n"
+                             "  ret void\n"
+                             "}\n"
+                             "define void @d() {\n"
+                             "entry:\n"
+                             "  ret void\n"
+                             "}\n");
+  LazyCallGraph CG(*M);
+
+  // Force the graph to be fully expanded.
+  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);
+  LazyCallGraph::RefSCC &BRC = *CG.lookupRefSCC(B);
+  LazyCallGraph::RefSCC &CRC = *CG.lookupRefSCC(C);
+  LazyCallGraph::RefSCC &DRC = *CG.lookupRefSCC(D);
+
+  // Connect the top to the bottom forming a large RefSCC made up just of
+  // references.
+  auto MergedRCs = ARC.insertIncomingRefEdge(D, A);
+  // Make sure we connected the nodes.
+  EXPECT_NE(D.begin(), D.end());
+  EXPECT_EQ(&A, D.begin()->getNode());
+
+  // Check that we have the dead RCs, but ignore the order.
+  EXPECT_EQ(3u, MergedRCs.size());
+  EXPECT_NE(find(MergedRCs, &BRC), MergedRCs.end());
+  EXPECT_NE(find(MergedRCs, &CRC), MergedRCs.end());
+  EXPECT_NE(find(MergedRCs, &DRC), MergedRCs.end());
+
+  // Make sure the nodes point to the right place now.
+  EXPECT_EQ(&ARC, CG.lookupRefSCC(A));
+  EXPECT_EQ(&ARC, CG.lookupRefSCC(B));
+  EXPECT_EQ(&ARC, CG.lookupRefSCC(C));
+  EXPECT_EQ(&ARC, CG.lookupRefSCC(D));
+
+  // And verify the post-order walk reflects the updated structure.
+  auto I = CG.postorder_ref_scc_begin(), End = CG.postorder_ref_scc_end();
+  ASSERT_NE(I, End);
+  EXPECT_EQ(&ARC, &*I) << "Actual RefSCC: " << *I;
+  EXPECT_EQ(++I, End);
 }
 
 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"
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.
-  auto I = CG.postorder_ref_scc_begin();
-  LazyCallGraph::RefSCC &RC = *I++;
-  EXPECT_EQ(CG.postorder_ref_scc_end(), I);
+  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));
   EXPECT_EQ(&RC, CG.lookupRefSCC(B));
   EXPECT_EQ(&RC, CG.lookupRefSCC(C));
 
   // Remove the edge from b -> a, which should leave the 3 functions still in
   // a single connected component because of a -> b -> c -> a.
   SmallVector<LazyCallGraph::RefSCC *, 1> NewRCs =
       RC.removeInternalRefEdge(B, A);
   EXPECT_EQ(0u, NewRCs.size());
   EXPECT_EQ(&RC, CG.lookupRefSCC(A));
   EXPECT_EQ(&RC, CG.lookupRefSCC(B));
   EXPECT_EQ(&RC, CG.lookupRefSCC(C));
+  auto J = CG.postorder_ref_scc_begin();
+  EXPECT_EQ(I, J);
+  EXPECT_EQ(&RC, &*J);
+  EXPECT_EQ(E, std::next(J));
 
   // Remove the edge from c -> a, which should leave 'a' in the original RefSCC
   // and form a new RefSCC for 'b' and 'c'.
   NewRCs = RC.removeInternalRefEdge(C, A);
   EXPECT_EQ(1u, NewRCs.size());
   EXPECT_EQ(&RC, CG.lookupRefSCC(A));
   EXPECT_EQ(1, std::distance(RC.begin(), RC.end()));
-  LazyCallGraph::RefSCC *RC2 = CG.lookupRefSCC(B);
-  EXPECT_EQ(RC2, CG.lookupRefSCC(C));
-  EXPECT_EQ(RC2, NewRCs[0]);
+  LazyCallGraph::RefSCC &RC2 = *CG.lookupRefSCC(B);
+  EXPECT_EQ(&RC2, CG.lookupRefSCC(C));
+  EXPECT_EQ(&RC2, NewRCs[0]);
+  J = CG.postorder_ref_scc_begin();
+  EXPECT_NE(I, J);
+  EXPECT_EQ(&RC2, &*J);
+  ++J;
+  EXPECT_EQ(I, J);
+  EXPECT_EQ(&RC, &*J);
+  ++I;
+  EXPECT_EQ(E, I);
+  ++J;
+  EXPECT_EQ(E, J);
 }
 
 TEST(LazyCallGraphTest, InternalCallEdgeToRef) {
   LLVMContext Context;
   // A nice fully connected (including self-edges) SCC (and RefSCC)
   std::unique_ptr<Module> M = parseAssembly(Context, "define void @a() {\n"
                                                      "entry:\n"
                                                      "  call void @a()\n"