Failure removing dead function due to RefSCC cycle

[danielframpton]

I saw a crash when compiling rust code. When I enabled LLVM assertions I saw the following assert fire:

llvm/lib/Analysis/LazyCallGraph.cpp:1538: void llvm::LazyCallGraph::removeDeadFunction(llvm::Function&): Assertion `RC.size() == 1 && "Dead functions must be in a singular RefSCC"' failed.

From looking further, the code appears to trigger the following sequence of events:

1. There is a ref cycle between a set of functions.
2. The cycle is broken via ArgumentPromotion (due to an unused function pointer parameter being dropped and thus dropping that ref edge).
3. Inlining causes a function to become dead, but it is not the only member of a RefSCC because we did not eagerly re-process nodes when we implicitly dropped the ref edge.

From this I was able to construct the following example to trigger the assertion under opt --passes=argpromotion,inline

define internal void @"A"() #0 {
  call void @"E"(i8* bitcast (void ()* @"C" to i8*))
  ret void
}

define internal void @"B"(i8* %0) #1 {
  ret void
}

define internal void @"C"() #1 {
  call void @"B"(i8* bitcast (void ()* @"A" to i8*))
  ret void
}

define void @"D"() {
  call void @"A"()
  ret void
}

declare void @"E"(i8* %0);

attributes #0 = { alwaysinline }
attributes #1 = { noinline }

With the following backtrace:

 #7 0x00007ff76bedc8d6 llvm::LazyCallGraph::removeDeadFunction(class llvm::Function &) E:\llvm-project\llvm\lib\Analysis\LazyCallGraph.cpp:1540:0
 #8 0x00007ff76d3a64f5 llvm::InlinerPass::run(class llvm::LazyCallGraph::SCC &, class llvm::AnalysisManager<class llvm::LazyCallGraph::SCC, class llvm::LazyCallGraph &> &, class llvm::LazyCallGraph &, struct llvm::CGSCCUpdateResult &) E:\llvm-project\llvm\lib\Transforms\IPO\Inliner.cpp:1090:0
 #9 0x00007ff76d3b8d8d llvm::detail::PassModel<class llvm::LazyCallGraph::SCC, class llvm::InlinerPass, class llvm::PreservedAnalyses, class llvm::AnalysisManager<class llvm::LazyCallGraph::SCC, class llvm::LazyCallGraph &>, class llvm::LazyCallGraph &, struct llvm::CGSCCUpdateResult &>::run(class llvm::LazyCallGraph::SCC &, class llvm::AnalysisManager<class llvm::LazyCallGraph::SCC, class llvm::LazyCallGraph &> &, class llvm::LazyCallGraph &, struct llvm::CGSCCUpdateResult &) E:\llvm-project\llvm\include\llvm\IR\PassManagerInternal.h:88:0
#10 0x00007ff76b97ca32 llvm::PassManager<class llvm::LazyCallGraph::SCC, class llvm::AnalysisManager<class llvm::LazyCallGraph::SCC, class llvm::LazyCallGraph &>, class llvm::LazyCallGraph &, struct llvm::CGSCCUpdateResult &>::run(class llvm::LazyCallGraph::SCC &, class llvm::AnalysisManager<class llvm::LazyCallGraph::SCC, class llvm::LazyCallGraph &> &, class llvm::LazyCallGraph &, struct llvm::CGSCCUpdateResult &) E:\llvm-project\llvm\lib\Analysis\CGSCCPassManager.cpp:90:0
#11 0x00007ff76d3b8c3d llvm::detail::PassModel<class llvm::LazyCallGraph::SCC, class llvm::PassManager<class llvm::LazyCallGraph::SCC, class llvm::AnalysisManager<class llvm::LazyCallGraph::SCC, class llvm::LazyCallGraph &>, class llvm::LazyCallGraph &, struct llvm::CGSCCUpdateResult &>, class llvm::PreservedAnalyses, class llvm::AnalysisManager<class llvm::LazyCallGraph::SCC, class llvm::LazyCallGraph &>, class llvm::LazyCallGraph &, struct llvm::CGSCCUpdateResult &>::run(class llvm::LazyCallGraph::SCC &, class llvm::AnalysisManager<class llvm::LazyCallGraph::SCC, class llvm::LazyCallGraph &> &, class llvm::LazyCallGraph &, struct llvm::CGSCCUpdateResult &) E:\llvm-project\llvm\include\llvm\IR\PassManagerInternal.h:88:0
#12 0x00007ff76b97d930 llvm::ModuleToPostOrderCGSCCPassAdaptor::run(class llvm::Module &, class llvm::AnalysisManager<class llvm::Module> &) E:\llvm-project\llvm\lib\Analysis\CGSCCPassManager.cpp:283:0
#13 0x00007ff76d3b8bc9 llvm::detail::PassModel<class llvm::Module, class llvm::ModuleToPostOrderCGSCCPassAdaptor, class llvm::PreservedAnalyses, class llvm::AnalysisManager<class llvm::Module>>::run(class llvm::Module &, class llvm::AnalysisManager<class llvm::Module> &) E:\llvm-project\llvm\include\llvm\IR\PassManagerInternal.h:88:0
#14 0x00007ff768d7109e llvm::PassManager<class llvm::Module, class llvm::AnalysisManager<class llvm::Module>>::run(class llvm::Module &, class llvm::AnalysisManager<class llvm::Module> &) E:\llvm-project\llvm\include\llvm\IR\PassManager.h:522:0
#15 0x00007ff768d2c884 llvm::runPassPipeline(class llvm::StringRef, class llvm::Module &, class llvm::TargetMachine *, class llvm::TargetLibraryInfoImpl *, class llvm::ToolOutputFile *, class llvm::ToolOutputFile *, class llvm::ToolOutputFile *, class llvm::StringRef, class llvm::ArrayRef<class llvm::StringRef>, class llvm::ArrayRef<class llvm::PassPlugin>, enum llvm::opt_tool::OutputKind, enum llvm::opt_tool::VerifierKind, bool, bool, bool, bool, bool, bool) E:\llvm-project\llvm\tools\opt\NewPMDriver.cpp:525:0
#16 0x00007ff768d844c4 main E:\llvm-project\llvm\tools\opt\opt.cpp:810:0

I also verified that adding code to explicitly break the cycles when we hit the case of deleting such a function appears to work for both this example and the original Rust code, but this might not be the best solution (although other work to try and avoid getting into this situation may affect throughput). Happy to put out a review if this is the right direction or to validate other possible fixes with my repro case.

diff --git a/llvm/lib/Analysis/LazyCallGraph.cpp b/llvm/lib/Analysis/LazyCallGraph.cpp
index 20a905e04a9d..e796b02ebccd 100644
--- a/llvm/lib/Analysis/LazyCallGraph.cpp
+++ b/llvm/lib/Analysis/LazyCallGraph.cpp
@@ -1530,14 +1530,36 @@ void LazyCallGraph::removeDeadFunction(Function &F) {
   assert(CI != SCCMap.end() &&
          "Tried to remove a node without an SCC after DFS walk started!");
   SCC &C = *CI->second;
+  RefSCC *RC = &C.getOuterRefSCC();
+
+  // Remove internal edges within the RefSCC to handle cycles
+  auto RemovedInternalEdge = [&](){
+    for (auto& OtherC : *RC) {
+      for (auto& OtherN : OtherC) {
+        if (OtherN->lookup(N)) {
+          // We found an internal edge to the function
+          RC->removeInternalRefEdge(OtherN, ArrayRef<Node *>{&N});
+
+          // We may have split the RefSCC
+          RC = &C.getOuterRefSCC();
+          return true;
+        }
+      }
+    }
+    return false;
+  };
+  // Continue removing edges until we don't progress (will assert below) or
+  // have a RefSCC with only one member
+  while (RC->size() != 1 && RemovedInternalEdge());
+
+  // Erase the SCC from the map.
   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
@@ -1546,8 +1568,8 @@ void LazyCallGraph::removeDeadFunction(Function &F) {
   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.

[nikic]

cc @aeubanks

[aeubanks]

@alinas
It looks like the issue is that the CGSCC infrastructure assumes that only references from the current SCC can be modified, but argument promotion is modifying references from callers which becomes an issue later on since that wasn't kept track of.

[danielframpton]

From reading some of the commit logs here, it seemed like the choice to not perform updates around ref edges was deliberate (e.g., this change) which was why for my workaround I tried to handle the case when deleting the function rather than triggering updates as part of argument promotion.

But yes, understanding if we should be doing something to break the cycle when we perform argument promotion is a key question. I also don't know if there are other optimizations (in addition to argument promotion) that may cause ref edges to become dead as well.

[aeubanks]

I didn't know dead ref edges were allowed to be kept around, that's good to know and we should document that better in comments.

Argument promotion should be the only CGSCC pass that modifies callers, which is how dead ref edges appear.

Your patch looks mostly good, but we need to handle the result of removeInternalRefEdge(). For example, if we have F1 -> F2 -> F3 -> F1 where all edges are ref edges and F2 -> F3 is spurious, we visit F1 and somehow remove F1 -> F2 and delete F2, then the graph will be F3 -> F1 and F3 will become its own RefSCC. Without the handling above we'll skip visiting F3 as the new RefSCC will never have been added to RCWorklist.

Feel free to put up a patch and add me as a reviewer.

[aeubanks]

sent out https://reviews.llvm.org/D133907 since we hit this after https://reviews.llvm.org/D128830