Import LLVM 4.0.0 rc1 including clang and lld to help the current

development effort on OpenBSD/arm64.

1 files changed, 882 insertions, 50 deletions

diff --git a/gnu/llvm/unittests/Analysis/LazyCallGraphTest.cpp b/gnu/llvm/unittests/Analysis/LazyCallGraphTest.cpp
index 224a9458cc8..5bb9dec3449 100644
--- a/gnu/llvm/unittests/Analysis/LazyCallGraphTest.cpp
+++ b/gnu/llvm/unittests/Analysis/LazyCallGraphTest.cpp
@@ -9,6 +9,7 @@
 
 #include "llvm/Analysis/LazyCallGraph.h"
 #include "llvm/AsmParser/Parser.h"
+#include "llvm/IR/Instructions.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Module.h"
@@ -120,6 +121,101 @@ static const char DiamondOfTriangles[] =
      "  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);
@@ -220,6 +316,7 @@ TEST(LazyCallGraphTest, BasicGraphFormation) {
   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());
@@ -235,6 +332,7 @@ TEST(LazyCallGraphTest, BasicGraphFormation) {
   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());
@@ -252,6 +350,7 @@ TEST(LazyCallGraphTest, BasicGraphFormation) {
   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());
@@ -269,8 +368,10 @@ TEST(LazyCallGraphTest, BasicGraphFormation) {
   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) {
@@ -478,7 +579,7 @@ TEST(LazyCallGraphTest, OutgoingEdgeMutation) {
 
   // 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"));
@@ -493,13 +594,21 @@ TEST(LazyCallGraphTest, OutgoingEdgeMutation) {
   LazyCallGraph::RefSCC &CRC = *CG.lookupRefSCC(C);
   LazyCallGraph::RefSCC &DRC = *CG.lookupRefSCC(D);
   EXPECT_TRUE(ARC.isParentOf(BRC));
+  EXPECT_TRUE(AC.isParentOf(BC));
   EXPECT_TRUE(ARC.isParentOf(CRC));
+  EXPECT_TRUE(AC.isParentOf(CC));
   EXPECT_FALSE(ARC.isParentOf(DRC));
+  EXPECT_FALSE(AC.isParentOf(DC));
   EXPECT_TRUE(ARC.isAncestorOf(DRC));
+  EXPECT_TRUE(AC.isAncestorOf(DC));
   EXPECT_FALSE(DRC.isChildOf(ARC));
+  EXPECT_FALSE(DC.isChildOf(AC));
   EXPECT_TRUE(DRC.isDescendantOf(ARC));
+  EXPECT_TRUE(DC.isDescendantOf(AC));
   EXPECT_TRUE(DRC.isChildOf(BRC));
+  EXPECT_TRUE(DC.isChildOf(BC));
   EXPECT_TRUE(DRC.isChildOf(CRC));
+  EXPECT_TRUE(DC.isChildOf(CC));
 
   EXPECT_EQ(2, std::distance(A.begin(), A.end()));
   ARC.insertOutgoingEdge(A, D, LazyCallGraph::Edge::Call);
@@ -512,9 +621,13 @@ TEST(LazyCallGraphTest, OutgoingEdgeMutation) {
   // Only the parent and child tests sholud have changed. The rest of the graph
   // remains the same.
   EXPECT_TRUE(ARC.isParentOf(DRC));
+  EXPECT_TRUE(AC.isParentOf(DC));
   EXPECT_TRUE(ARC.isAncestorOf(DRC));
+  EXPECT_TRUE(AC.isAncestorOf(DC));
   EXPECT_TRUE(DRC.isChildOf(ARC));
+  EXPECT_TRUE(DC.isChildOf(AC));
   EXPECT_TRUE(DRC.isDescendantOf(ARC));
+  EXPECT_TRUE(DC.isDescendantOf(AC));
   EXPECT_EQ(&AC, CG.lookupSCC(A));
   EXPECT_EQ(&BC, CG.lookupSCC(B));
   EXPECT_EQ(&CC, CG.lookupSCC(C));
@@ -527,11 +640,15 @@ TEST(LazyCallGraphTest, OutgoingEdgeMutation) {
   ARC.switchOutgoingEdgeToRef(A, D);
   EXPECT_FALSE(NewE.isCall());
 
-  // Verify the graph remains the same.
+  // Verify the reference graph remains the same but the SCC graph is updated.
   EXPECT_TRUE(ARC.isParentOf(DRC));
+  EXPECT_FALSE(AC.isParentOf(DC));
   EXPECT_TRUE(ARC.isAncestorOf(DRC));
+  EXPECT_TRUE(AC.isAncestorOf(DC));
   EXPECT_TRUE(DRC.isChildOf(ARC));
+  EXPECT_FALSE(DC.isChildOf(AC));
   EXPECT_TRUE(DRC.isDescendantOf(ARC));
+  EXPECT_TRUE(DC.isDescendantOf(AC));
   EXPECT_EQ(&AC, CG.lookupSCC(A));
   EXPECT_EQ(&BC, CG.lookupSCC(B));
   EXPECT_EQ(&CC, CG.lookupSCC(C));
@@ -544,11 +661,15 @@ TEST(LazyCallGraphTest, OutgoingEdgeMutation) {
   ARC.switchOutgoingEdgeToCall(A, D);
   EXPECT_TRUE(NewE.isCall());
 
-  // Verify the graph remains the same.
+  // Verify the reference graph remains the same but the SCC graph is updated.
   EXPECT_TRUE(ARC.isParentOf(DRC));
+  EXPECT_TRUE(AC.isParentOf(DC));
   EXPECT_TRUE(ARC.isAncestorOf(DRC));
+  EXPECT_TRUE(AC.isAncestorOf(DC));
   EXPECT_TRUE(DRC.isChildOf(ARC));
+  EXPECT_TRUE(DC.isChildOf(AC));
   EXPECT_TRUE(DRC.isDescendantOf(ARC));
+  EXPECT_TRUE(DC.isDescendantOf(AC));
   EXPECT_EQ(&AC, CG.lookupSCC(A));
   EXPECT_EQ(&BC, CG.lookupSCC(B));
   EXPECT_EQ(&CC, CG.lookupSCC(C));
@@ -563,9 +684,13 @@ TEST(LazyCallGraphTest, OutgoingEdgeMutation) {
 
   // Now the parent and child tests fail again but the rest remains the same.
   EXPECT_FALSE(ARC.isParentOf(DRC));
+  EXPECT_FALSE(AC.isParentOf(DC));
   EXPECT_TRUE(ARC.isAncestorOf(DRC));
+  EXPECT_TRUE(AC.isAncestorOf(DC));
   EXPECT_FALSE(DRC.isChildOf(ARC));
+  EXPECT_FALSE(DC.isChildOf(AC));
   EXPECT_TRUE(DRC.isDescendantOf(ARC));
+  EXPECT_TRUE(DC.isDescendantOf(AC));
   EXPECT_EQ(&AC, CG.lookupSCC(A));
   EXPECT_EQ(&BC, CG.lookupSCC(B));
   EXPECT_EQ(&CC, CG.lookupSCC(C));
@@ -599,7 +724,7 @@ TEST(LazyCallGraphTest, IncomingEdgeInsertion) {
 
   // 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"));
@@ -668,6 +793,16 @@ TEST(LazyCallGraphTest, IncomingEdgeInsertion) {
   // 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) {
@@ -726,15 +861,574 @@ TEST(LazyCallGraphTest, IncomingEdgeInsertionMidTraversal) {
   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.
+  // 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 &BRC = *I;
+  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, InlineAndDeleteFunction) {
+  LLVMContext Context;
+  // We want to ensure we can delete nodes from relatively complex graphs and
+  // so use the diamond of triangles graph defined above.
+  //
+  // 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);
+
+  // 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()));
+
+  // 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(&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(&NewDRC, CG.lookupRefSCC(D1));
+  EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D3));
+  EXPECT_TRUE(CRC.isParentOf(NewDRC));
+
+  // Verify the post-order walk hasn't changed.
+  auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end();
+  ASSERT_NE(I, E);
+  EXPECT_EQ(&NewDRC, &*I) << "Actual RefSCC: " << *I;
+  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, 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(CRC));
+  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;
@@ -742,9 +1436,15 @@ TEST(LazyCallGraphTest, IncomingEdgeInsertionMidTraversal) {
   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) {
@@ -796,7 +1496,7 @@ TEST(LazyCallGraphTest, InternalEdgeMutation) {
   // Switch the call edge from 'b' to 'c' to a ref edge. This will break the
   // call cycle and cause us to form more SCCs. The RefSCC will remain the same
   // though.
-  RC.switchInternalEdgeToRef(B, C);
+  auto NewCs = RC.switchInternalEdgeToRef(B, C);
   EXPECT_EQ(&RC, CG.lookupRefSCC(A));
   EXPECT_EQ(&RC, CG.lookupRefSCC(B));
   EXPECT_EQ(&RC, CG.lookupRefSCC(C));
@@ -808,6 +1508,10 @@ TEST(LazyCallGraphTest, InternalEdgeMutation) {
   EXPECT_EQ(&*J++, CG.lookupSCC(A));
   EXPECT_EQ(&*J++, CG.lookupSCC(C));
   EXPECT_EQ(RC.end(), J);
+  // And the returned range must be the slice of this sequence containing new
+  // SCCs.
+  EXPECT_EQ(RC.begin(), NewCs.begin());
+  EXPECT_EQ(std::prev(RC.end()), NewCs.end());
 
   // Test turning the ref edge from A to C into a call edge. This will form an
   // SCC out of A and C. Since we previously had a call edge from C to A, the
@@ -855,9 +1559,9 @@ TEST(LazyCallGraphTest, InternalEdgeRemoval) {
   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"));
@@ -874,6 +1578,10 @@ TEST(LazyCallGraphTest, InternalEdgeRemoval) {
   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'.
@@ -881,9 +1589,97 @@ TEST(LazyCallGraphTest, InternalEdgeRemoval) {
   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, InternalNoOpEdgeRemoval) {
+  LLVMContext Context;
+  // A graph with a single cycle formed both from call and reference edges
+  // which makes the reference edges trivial to delete. The graph looks like:
+  //
+  // Reference edges: a -> b -> c -> a
+  //      Call edges: a -> c -> b -> a
+  std::unique_ptr<Module> M = parseAssembly(
+      Context, "define void @a(i8** %ptr) {\n"
+               "entry:\n"
+               "  call void @b(i8** %ptr)\n"
+               "  store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n"
+               "  ret void\n"
+               "}\n"
+               "define void @b(i8** %ptr) {\n"
+               "entry:\n"
+               "  store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n"
+               "  call void @c(i8** %ptr)\n"
+               "  ret void\n"
+               "}\n"
+               "define void @c(i8** %ptr) {\n"
+               "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.
+  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"));
+  LazyCallGraph::Node &BN = *CG.lookup(lookupFunction(*M, "b"));
+  LazyCallGraph::Node &CN = *CG.lookup(lookupFunction(*M, "c"));
+  EXPECT_EQ(&RC, CG.lookupRefSCC(AN));
+  EXPECT_EQ(&RC, CG.lookupRefSCC(BN));
+  EXPECT_EQ(&RC, CG.lookupRefSCC(CN));
+  EXPECT_EQ(&C, CG.lookupSCC(AN));
+  EXPECT_EQ(&C, CG.lookupSCC(BN));
+  EXPECT_EQ(&C, CG.lookupSCC(CN));
+
+  // Remove the edge from a -> c which doesn't change anything.
+  SmallVector<LazyCallGraph::RefSCC *, 1> NewRCs =
+      RC.removeInternalRefEdge(AN, CN);
+  EXPECT_EQ(0u, NewRCs.size());
+  EXPECT_EQ(&RC, CG.lookupRefSCC(AN));
+  EXPECT_EQ(&RC, CG.lookupRefSCC(BN));
+  EXPECT_EQ(&RC, CG.lookupRefSCC(CN));
+  EXPECT_EQ(&C, CG.lookupSCC(AN));
+  EXPECT_EQ(&C, CG.lookupSCC(BN));
+  EXPECT_EQ(&C, CG.lookupSCC(CN));
+  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 b -> a and c -> b; again this doesn't change
+  // anything.
+  NewRCs = RC.removeInternalRefEdge(BN, AN);
+  NewRCs = RC.removeInternalRefEdge(CN, BN);
+  EXPECT_EQ(0u, NewRCs.size());
+  EXPECT_EQ(&RC, CG.lookupRefSCC(AN));
+  EXPECT_EQ(&RC, CG.lookupRefSCC(BN));
+  EXPECT_EQ(&RC, CG.lookupRefSCC(CN));
+  EXPECT_EQ(&C, CG.lookupSCC(AN));
+  EXPECT_EQ(&C, CG.lookupSCC(BN));
+  EXPECT_EQ(&C, CG.lookupSCC(CN));
+  J = CG.postorder_ref_scc_begin();
+  EXPECT_EQ(I, J);
+  EXPECT_EQ(&RC, &*J);
+  EXPECT_EQ(E, std::next(J));
 }
 
 TEST(LazyCallGraphTest, InternalCallEdgeToRef) {
@@ -918,54 +1714,59 @@ TEST(LazyCallGraphTest, InternalCallEdgeToRef) {
   EXPECT_EQ(CG.postorder_ref_scc_end(), I);
 
   EXPECT_EQ(1, RC.size());
-  LazyCallGraph::SCC &CallC = *RC.begin();
+  LazyCallGraph::SCC &AC = *RC.begin();
 
-  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(&CallC, CG.lookupSCC(A));
-  EXPECT_EQ(&CallC, CG.lookupSCC(B));
-  EXPECT_EQ(&CallC, CG.lookupSCC(C));
+  LazyCallGraph::Node &AN = *CG.lookup(lookupFunction(*M, "a"));
+  LazyCallGraph::Node &BN = *CG.lookup(lookupFunction(*M, "b"));
+  LazyCallGraph::Node &CN = *CG.lookup(lookupFunction(*M, "c"));
+  EXPECT_EQ(&AC, CG.lookupSCC(AN));
+  EXPECT_EQ(&AC, CG.lookupSCC(BN));
+  EXPECT_EQ(&AC, CG.lookupSCC(CN));
 
   // Remove the call edge from b -> a to a ref edge, which should leave the
   // 3 functions still in a single connected component because of a -> b ->
   // c -> a.
-  RC.switchInternalEdgeToRef(B, A);
+  auto NewCs = RC.switchInternalEdgeToRef(BN, AN);
+  EXPECT_EQ(NewCs.begin(), NewCs.end());
   EXPECT_EQ(1, RC.size());
-  EXPECT_EQ(&CallC, CG.lookupSCC(A));
-  EXPECT_EQ(&CallC, CG.lookupSCC(B));
-  EXPECT_EQ(&CallC, CG.lookupSCC(C));
+  EXPECT_EQ(&AC, CG.lookupSCC(AN));
+  EXPECT_EQ(&AC, CG.lookupSCC(BN));
+  EXPECT_EQ(&AC, CG.lookupSCC(CN));
 
   // Remove the edge from c -> a, which should leave 'a' in the original SCC
   // and form a new SCC for 'b' and 'c'.
-  RC.switchInternalEdgeToRef(C, A);
+  NewCs = RC.switchInternalEdgeToRef(CN, AN);
+  EXPECT_EQ(1, std::distance(NewCs.begin(), NewCs.end()));
   EXPECT_EQ(2, RC.size());
-  EXPECT_EQ(&CallC, CG.lookupSCC(A));
-  LazyCallGraph::SCC &BCallC = *CG.lookupSCC(B);
-  EXPECT_NE(&BCallC, &CallC);
-  EXPECT_EQ(&BCallC, CG.lookupSCC(C));
-  auto J = RC.find(CallC);
-  EXPECT_EQ(&CallC, &*J);
+  EXPECT_EQ(&AC, CG.lookupSCC(AN));
+  LazyCallGraph::SCC &BC = *CG.lookupSCC(BN);
+  EXPECT_NE(&BC, &AC);
+  EXPECT_EQ(&BC, CG.lookupSCC(CN));
+  auto J = RC.find(AC);
+  EXPECT_EQ(&AC, &*J);
   --J;
-  EXPECT_EQ(&BCallC, &*J);
+  EXPECT_EQ(&BC, &*J);
   EXPECT_EQ(RC.begin(), J);
+  EXPECT_EQ(J, NewCs.begin());
 
   // Remove the edge from c -> b, which should leave 'b' in the original SCC
   // and form a new SCC for 'c'. It shouldn't change 'a's SCC.
-  RC.switchInternalEdgeToRef(C, B);
+  NewCs = RC.switchInternalEdgeToRef(CN, BN);
+  EXPECT_EQ(1, std::distance(NewCs.begin(), NewCs.end()));
   EXPECT_EQ(3, RC.size());
-  EXPECT_EQ(&CallC, CG.lookupSCC(A));
-  EXPECT_EQ(&BCallC, CG.lookupSCC(B));
-  LazyCallGraph::SCC &CCallC = *CG.lookupSCC(C);
-  EXPECT_NE(&CCallC, &CallC);
-  EXPECT_NE(&CCallC, &BCallC);
-  J = RC.find(CallC);
-  EXPECT_EQ(&CallC, &*J);
+  EXPECT_EQ(&AC, CG.lookupSCC(AN));
+  EXPECT_EQ(&BC, CG.lookupSCC(BN));
+  LazyCallGraph::SCC &CC = *CG.lookupSCC(CN);
+  EXPECT_NE(&CC, &AC);
+  EXPECT_NE(&CC, &BC);
+  J = RC.find(AC);
+  EXPECT_EQ(&AC, &*J);
   --J;
-  EXPECT_EQ(&BCallC, &*J);
+  EXPECT_EQ(&BC, &*J);
   --J;
-  EXPECT_EQ(&CCallC, &*J);
+  EXPECT_EQ(&CC, &*J);
   EXPECT_EQ(RC.begin(), J);
+  EXPECT_EQ(J, NewCs.begin());
 }
 
 TEST(LazyCallGraphTest, InternalRefEdgeToCall) {
@@ -1135,11 +1936,11 @@ TEST(LazyCallGraphTest, InternalRefEdgeToCallNoCycleInterleaved) {
 
   // Several call edges are initially present to force a particual post-order.
   // Remove them now, leaving an interleaved post-order pattern.
-  RC.switchInternalEdgeToRef(B3, C3);
-  RC.switchInternalEdgeToRef(C2, B3);
-  RC.switchInternalEdgeToRef(B2, C2);
-  RC.switchInternalEdgeToRef(C1, B2);
-  RC.switchInternalEdgeToRef(B1, C1);
+  RC.switchTrivialInternalEdgeToRef(B3, C3);
+  RC.switchTrivialInternalEdgeToRef(C2, B3);
+  RC.switchTrivialInternalEdgeToRef(B2, C2);
+  RC.switchTrivialInternalEdgeToRef(C1, B2);
+  RC.switchTrivialInternalEdgeToRef(B1, C1);
 
   // Check the initial post-order. We ensure this order with the extra edges
   // that are nuked above.
@@ -1262,8 +2063,8 @@ TEST(LazyCallGraphTest, InternalRefEdgeToCallBothPartitionAndMerge) {
   LazyCallGraph::SCC &GC = *CG.lookupSCC(G);
 
   // Remove the extra edges that were used to force a particular post-order.
-  RC.switchInternalEdgeToRef(C, D);
-  RC.switchInternalEdgeToRef(D, E);
+  RC.switchTrivialInternalEdgeToRef(C, D);
+  RC.switchTrivialInternalEdgeToRef(D, E);
 
   // Check the initial post-order. We ensure this order with the extra edges
   // that are nuked above.
@@ -1302,4 +2103,35 @@ TEST(LazyCallGraphTest, InternalRefEdgeToCallBothPartitionAndMerge) {
   EXPECT_EQ(&AC, &RC[4]);
 }
 
+// Test for IR containing constants using blockaddress constant expressions.
+// These are truly unique constructs: constant expressions with non-constant
+// operands.
+TEST(LazyCallGraphTest, HandleBlockAddress) {
+  LLVMContext Context;
+  std::unique_ptr<Module> M =
+      parseAssembly(Context, "define void @f() {\n"
+                             "entry:\n"
+                             "  ret void\n"
+                             "bb:\n"
+                             "  unreachable\n"
+                             "}\n"
+                             "define void @g(i8** %ptr) {\n"
+                             "entry:\n"
+                             "  store i8* blockaddress(@f, %bb), i8** %ptr\n"
+                             "  ret void\n"
+                             "}\n");
+  LazyCallGraph CG(*M);
+
+  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));
+}
+
 }