[LazyCallGraph] Handle spurious ref edges when deleting a dead function

Spurious ref edges are ref edges that still exist in the call graph even
though the corresponding IR reference no longer exists. This can cause
issues when deleting a dead function which has a spurious ref edge
pointed at it because currently we expect the dead function's RefSCC to
be trivial.

In the case that the dead function's RefSCC is not trivial, remove all
ref edges from other nodes in the RefSCC to it.

Removing a ref edge can result in splitting RefSCCs. There's actually no
reason to revisit those RefSCCs because currently we only run passes on
SCCs, and we've already added all SCCs in the RefSCC to the worklist.
(as opposed to removing the ref edge in
updateCGAndAnalysisManagerForPass() which can modify the call graph of
SCCs we have not visited yet). We also don't expect that RefSCC
refinement will allow us to glean any more information for optimization
use. Also, doing so would drastically increase the complexity of
LazyCallGraph::removeDeadFunction(), requiring us to return a list of
invalidated RefSCCs and new RefSCCs to add to the worklist.

Fixes #56503

Reviewed By: asbirlea

Differential Revision: https://reviews.llvm.org/D133907

1 files changed, 158 insertions, 1 deletions

diff --git a/llvm/unittests/Analysis/LazyCallGraphTest.cpp b/llvm/unittests/Analysis/LazyCallGraphTest.cpp
index d6e73f3a..ee3c254 100644
--- a/llvm/unittests/Analysis/LazyCallGraphTest.cpp
+++ b/llvm/unittests/Analysis/LazyCallGraphTest.cpp
@@ -2092,7 +2092,7 @@ TEST(LazyCallGraphTest, ReplaceNodeFunction) {
   EXPECT_EQ(&DN, &(*BN)[DN].getNode());
 }
 
-TEST(LazyCallGraphTest, RemoveFunctionWithSpurriousRef) {
+TEST(LazyCallGraphTest, RemoveFunctionWithSpuriousRef) {
   LLVMContext Context;
   // A graph with a couple of RefSCCs.
   std::unique_ptr<Module> M =
@@ -2173,6 +2173,163 @@ TEST(LazyCallGraphTest, RemoveFunctionWithSpurriousRef) {
   EXPECT_EQ(CG.postorder_ref_scc_end(), I);
 }
 
+TEST(LazyCallGraphTest, RemoveFunctionWithSpuriousRefRecursive) {
+  LLVMContext Context;
+  std::unique_ptr<Module> M =
+      parseAssembly(Context, "define void @a(ptr %p) {\n"
+                             "  store ptr @b, ptr %p\n"
+                             "  ret void\n"
+                             "}\n"
+                             "define void @b(ptr %p) {\n"
+                             "  store ptr @c, ptr %p\n"
+                             "  ret void\n"
+                             "}\n"
+                             "define void @c(ptr %p) {\n"
+                             "  ret void\n"
+                             "}\n");
+  LazyCallGraph CG = buildCG(*M);
+
+  LazyCallGraph::Node &AN = CG.get(lookupFunction(*M, "a"));
+  LazyCallGraph::Node &BN = CG.get(lookupFunction(*M, "b"));
+  LazyCallGraph::Node &CN = CG.get(lookupFunction(*M, "c"));
+  AN.populate();
+  BN.populate();
+  CN.populate();
+  // Insert spurious ref edge.
+  CG.insertEdge(CN, AN, LazyCallGraph::Edge::Ref);
+
+  // Force the graph to be fully expanded.
+  CG.buildRefSCCs();
+  auto I = CG.postorder_ref_scc_begin();
+  LazyCallGraph::RefSCC &RC = *I++;
+  EXPECT_EQ(CG.postorder_ref_scc_end(), I);
+
+  ASSERT_EQ(RC.size(), 3);
+
+  EXPECT_EQ(&RC, CG.lookupRefSCC(AN));
+  EXPECT_EQ(&RC, CG.lookupRefSCC(BN));
+  EXPECT_EQ(&RC, CG.lookupRefSCC(CN));
+
+  // Now delete 'a'. There are no uses of this function but there are
+  // spurious references.
+  CG.removeDeadFunction(AN.getFunction());
+
+  // The only observable change should be that the RefSCC is gone from the
+  // postorder sequence.
+  I = CG.postorder_ref_scc_begin();
+  EXPECT_EQ(CG.lookupRefSCC(CN), &*I++);
+  EXPECT_EQ(CG.lookupRefSCC(BN), &*I++);
+  EXPECT_EQ(CG.postorder_ref_scc_end(), I);
+}
+
+TEST(LazyCallGraphTest, RemoveFunctionWithSpuriousRefRecursive2) {
+  LLVMContext Context;
+  std::unique_ptr<Module> M =
+      parseAssembly(Context, "define void @a(ptr %p) {\n"
+                             "  store ptr @b, ptr %p\n"
+                             "  ret void\n"
+                             "}\n"
+                             "define void @b(ptr %p) {\n"
+                             "  store ptr @c, ptr %p\n"
+                             "  ret void\n"
+                             "}\n"
+                             "define void @c(ptr %p) {\n"
+                             "  store ptr @b, ptr %p\n"
+                             "  store ptr @d, ptr %p\n"
+                             "  ret void\n"
+                             "}\n"
+                             "define void @d(ptr %p) {\n"
+                             "  ret void\n"
+                             "}\n");
+  LazyCallGraph CG = buildCG(*M);
+
+  LazyCallGraph::Node &AN = CG.get(lookupFunction(*M, "a"));
+  LazyCallGraph::Node &BN = CG.get(lookupFunction(*M, "b"));
+  LazyCallGraph::Node &CN = CG.get(lookupFunction(*M, "c"));
+  LazyCallGraph::Node &DN = CG.get(lookupFunction(*M, "d"));
+  AN.populate();
+  BN.populate();
+  CN.populate();
+  DN.populate();
+  // Insert spurious ref edge.
+  CG.insertEdge(DN, AN, LazyCallGraph::Edge::Ref);
+
+  // Force the graph to be fully expanded.
+  CG.buildRefSCCs();
+  auto I = CG.postorder_ref_scc_begin();
+  LazyCallGraph::RefSCC &RC = *I++;
+  EXPECT_EQ(CG.postorder_ref_scc_end(), I);
+
+  ASSERT_EQ(4, RC.size());
+
+  EXPECT_EQ(&RC, CG.lookupRefSCC(AN));
+  EXPECT_EQ(&RC, CG.lookupRefSCC(BN));
+  EXPECT_EQ(&RC, CG.lookupRefSCC(CN));
+  EXPECT_EQ(&RC, CG.lookupRefSCC(DN));
+
+  // Now delete 'a'. There are no uses of this function but there are
+  // spurious references.
+  CG.removeDeadFunction(AN.getFunction());
+
+  // The only observable change should be that the RefSCC is gone from the
+  // postorder sequence.
+  I = CG.postorder_ref_scc_begin();
+  EXPECT_EQ(CG.lookupRefSCC(DN), &*I++);
+  EXPECT_EQ(CG.lookupRefSCC(CN), &*I);
+  EXPECT_EQ(CG.lookupRefSCC(BN), &*I++);
+  EXPECT_EQ(CG.postorder_ref_scc_end(), I);
+}
+
+TEST(LazyCallGraphTest, RemoveFunctionWithSpuriousRefRecursive3) {
+  LLVMContext Context;
+  std::unique_ptr<Module> M =
+      parseAssembly(Context, "define void @a(ptr %p) {\n"
+                             "  store ptr @b, ptr %p\n"
+                             "  ret void\n"
+                             "}\n"
+                             "define void @b(ptr %p) {\n"
+                             "  store ptr @c, ptr %p\n"
+                             "  ret void\n"
+                             "}\n"
+                             "define void @c(ptr %p) {\n"
+                             "  ret void\n"
+                             "}\n");
+  LazyCallGraph CG = buildCG(*M);
+
+  LazyCallGraph::Node &AN = CG.get(lookupFunction(*M, "a"));
+  LazyCallGraph::Node &BN = CG.get(lookupFunction(*M, "b"));
+  LazyCallGraph::Node &CN = CG.get(lookupFunction(*M, "c"));
+  AN.populate();
+  BN.populate();
+  CN.populate();
+  // Insert spurious ref edges.
+  CG.insertEdge(CN, AN, LazyCallGraph::Edge::Ref);
+  CG.insertEdge(BN, AN, LazyCallGraph::Edge::Ref);
+
+  // Force the graph to be fully expanded.
+  CG.buildRefSCCs();
+  auto I = CG.postorder_ref_scc_begin();
+  LazyCallGraph::RefSCC &RC = *I++;
+  EXPECT_EQ(CG.postorder_ref_scc_end(), I);
+
+  ASSERT_EQ(RC.size(), 3);
+
+  EXPECT_EQ(&RC, CG.lookupRefSCC(AN));
+  EXPECT_EQ(&RC, CG.lookupRefSCC(BN));
+  EXPECT_EQ(&RC, CG.lookupRefSCC(CN));
+
+  // Now delete 'a'. There are no uses of this function but there are
+  // spurious references.
+  CG.removeDeadFunction(AN.getFunction());
+
+  // The only observable change should be that the RefSCC is gone from the
+  // postorder sequence.
+  I = CG.postorder_ref_scc_begin();
+  EXPECT_EQ(CG.lookupRefSCC(CN), &*I++);
+  EXPECT_EQ(CG.lookupRefSCC(BN), &*I++);
+  EXPECT_EQ(CG.postorder_ref_scc_end(), I);
+}
+
 TEST(LazyCallGraphTest, AddSplitFunction1) {
   LLVMContext Context;
   std::unique_ptr<Module> M = parseAssembly(Context, "define void @f() {\n"