diff --git a/llvm/include/llvm/Analysis/LazyCallGraph.h b/llvm/include/llvm/Analysis/LazyCallGraph.h --- a/llvm/include/llvm/Analysis/LazyCallGraph.h +++ b/llvm/include/llvm/Analysis/LazyCallGraph.h @@ -533,6 +533,14 @@ /// are necessarily within some actual SCC that nests within it. Since /// a direct call *is* a reference, there will always be at least one RefSCC /// around any SCC. + /// + /// Spurious ref edges, meaning ref edges that still exist in the call graph + /// even though the corresponding IR reference no longer exists, are allowed. + /// This is mostly to support argument promotion, which can modify a caller to + /// no longer pass a function. The only place that needs to specially handle + /// this is deleting a dead function/node, otherwise the dead ref edges are + /// automatically removed when visiting the function/node no longer containing + /// the ref edge. class RefSCC { friend class LazyCallGraph; friend class LazyCallGraph::Node; @@ -823,8 +831,8 @@ /// effort has been made to minimize the overhead of common cases such as /// self-edges and edge removals which result in a spanning tree with no /// more cycles. - SmallVector removeInternalRefEdge(Node &SourceN, - ArrayRef TargetNs); + [[nodiscard]] SmallVector + removeInternalRefEdge(Node &SourceN, ArrayRef TargetNs); /// A convenience wrapper around the above to handle trivial cases of /// inserting a new call edge. diff --git a/llvm/lib/Analysis/LazyCallGraph.cpp b/llvm/lib/Analysis/LazyCallGraph.cpp --- a/llvm/lib/Analysis/LazyCallGraph.cpp +++ b/llvm/lib/Analysis/LazyCallGraph.cpp @@ -1508,10 +1508,6 @@ return; Node &N = *NI->second; - NodeMap.erase(NI); - - // Remove this from the entry edges if present. - EntryEdges.removeEdgeInternal(N); // Cannot remove a function which has yet to be visited in the DFS walk, so // if we have a node at all then we must have an SCC and RefSCC. @@ -1519,14 +1515,38 @@ assert(CI != SCCMap.end() && "Tried to remove a node without an SCC after DFS walk started!"); SCC &C = *CI->second; + RefSCC *RC = &C.getOuterRefSCC(); + + // In extremely rare cases, we can delete a dead function which is still in a + // non-trivial RefSCC. This can happen due to spurious ref edges sticking + // around after an IR function reference is removed. + if (RC->size() != 1) { + SmallVector NodesInRC; + for (SCC &OtherC : *RC) { + for (Node &OtherN : OtherC) + NodesInRC.push_back(&OtherN); + } + for (Node *OtherN : NodesInRC) { + if ((*OtherN)->lookup(N)) { + auto NewRefSCCs = + RC->removeInternalRefEdge(*OtherN, ArrayRef(&N)); + // If we've split into multiple RefSCCs, RC is now invalid and the + // RefSCC containing C will be different. + if (!NewRefSCCs.empty()) + RC = &C.getOuterRefSCC(); + } + } + } + + NodeMap.erase(NI); + EntryEdges.removeEdgeInternal(N); SCCMap.erase(CI); - RefSCC &RC = C.getOuterRefSCC(); // This node must be the only member of its SCC as it has no callers, and // that SCC must be the only member of a RefSCC as it has no references. // Validate these properties first. assert(C.size() == 1 && "Dead functions must be in a singular SCC"); - assert(RC.size() == 1 && "Dead functions must be in a singular RefSCC"); + assert(RC->size() == 1 && "Dead functions must be in a singular RefSCC"); // Finally clear out all the data structures from the node down through the // components. postorder_ref_scc_iterator will skip empty RefSCCs, so no need @@ -1535,8 +1555,8 @@ N.G = nullptr; N.F = nullptr; C.clear(); - RC.clear(); - RC.G = nullptr; + RC->clear(); + RC->G = nullptr; // Nothing to delete as all the objects are allocated in stable bump pointer // allocators. diff --git a/llvm/test/Analysis/LazyCallGraph/remove-dead-function-spurious-ref-edge.ll b/llvm/test/Analysis/LazyCallGraph/remove-dead-function-spurious-ref-edge.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Analysis/LazyCallGraph/remove-dead-function-spurious-ref-edge.ll @@ -0,0 +1,36 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt -passes=argpromotion,inline -S %s | FileCheck %s + +; argpromo removes @b's parameter (removing @c's reference to @a without updating the ref edge in the call graph), then the inliner inlines @a into @d and attempts to remove @a. + +define internal void @a() alwaysinline { + call void @e(ptr @c) + ret void +} + +define internal void @b(ptr) noinline { +; CHECK-LABEL: @b( +; CHECK-NEXT: ret void +; + ret void +} + +define internal void @c() noinline { +; CHECK-LABEL: @c( +; CHECK-NEXT: call void @b() +; CHECK-NEXT: ret void +; + call void @b(ptr @a) + ret void +} + +define void @d() { +; CHECK-LABEL: @d( +; CHECK-NEXT: call void @e(ptr @c) +; CHECK-NEXT: ret void +; + call void @a() + ret void +} + +declare void @e(ptr); diff --git a/llvm/unittests/Analysis/LazyCallGraphTest.cpp b/llvm/unittests/Analysis/LazyCallGraphTest.cpp --- a/llvm/unittests/Analysis/LazyCallGraphTest.cpp +++ b/llvm/unittests/Analysis/LazyCallGraphTest.cpp @@ -2092,7 +2092,7 @@ EXPECT_EQ(&DN, &(*BN)[DN].getNode()); } -TEST(LazyCallGraphTest, RemoveFunctionWithSpurriousRef) { +TEST(LazyCallGraphTest, RemoveFunctionWithSpuriousRef) { LLVMContext Context; // A graph with a couple of RefSCCs. std::unique_ptr M = @@ -2173,6 +2173,163 @@ EXPECT_EQ(CG.postorder_ref_scc_end(), I); } +TEST(LazyCallGraphTest, RemoveFunctionWithSpuriousRefRecursive) { + LLVMContext Context; + std::unique_ptr 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 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 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 M = parseAssembly(Context, "define void @f() {\n"