<table border="1" cellspacing="0" cellpadding="8">
    <tr>
        <th>Issue</th>
        <td>
            <a href=https://github.com/llvm/llvm-project/issues/56503>56503</a>
        </td>
    </tr>

    <tr>
        <th>Summary</th>
        <td>
            Failure removing dead function due to RefSCC cycle
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
      </td>
    </tr>

    <tr>
      <th>Assignees</th>
      <td>
      </td>
    </tr>

    <tr>
      <th>Reporter</th>
      <td>
          danielframpton
      </td>
    </tr>
</table>

<pre>
    I saw a [crash when compiling rust code](https://github.com/rust-lang/rust/issues/99196). 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.
```
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJztGltX2zzy14QXneQ4dpzLAw8hQJezhXIo2z72yPY40aJYXlkm5fv1OyPZjmMcoC3dh2_LCblYc9Nc5RlHKnk6vWIF3zHOBuFZrHmxYbsNZCxW21xIka2ZLguDPxMYhOcDf74xJi8GwXLgX-JrLcymjEYIjT8Icih5tq6-44coihIK_LJYjBfTgb8Ysa9E_opBxiMJCfv48cs140UB2giVFcyJYzbAUiWl2pEIbpmlQgNx9s4HXv0-9aqX_SnlIwkiRYTvy4zLp0IQ94_8r6cVl_KD5vlmFOc5khmHwRw_2KMSCbOISDpYHoC6Sxq26hHOgSeXZRaTmKiHPcb-Im2QSC7r7TCU7G41KsRfgCi4ygbBOb7YmFnoKX74RJilFZGCbUnfETCRoVEK3H4puWZ3kH5erRB64M9YygWqbtSrAvd-qdWWSaUeSH1pqVGfeuCvrF7JloznOXBdMKOY0WK9Bt3ReQH_KSGLgamUwSNkpuiofkzbuUe6KGqBompIWfwUS0DhzQ7Aig-G8JvNVSL7FWoFj-iRVg-I8Sg4W-p1uUV-t7gF5ZToz5MSSFSesTIrC9jri-VKZAalz7nmW6BvEZD8iVa4xQRREtxZWbgLtGI23FhpIVkDuaQTKiChrjL0eQKKObKhbTWMkH0E6OjAEjQYKTMqDROGxM-UsepTmXxiW9hGKAbum1dmI0Six3aIjN5G4MBR5witYZhrFUNBVBJkacMPAcU2lyIWBmHqvRCLWvDRM3ObjaDw2XEUG0OLBI5R50aXsekYF75zpA5d6zdhiFpO8Bo6lcoNGw5zWkEHOOd6ndd2QRUIUhd0fK_jkAmkCMOslTAiXbwNJh768tL6s4sLP_DYYHbmcBjqXx6AXjhQgcBLFgkTc4wSvOBALA1accAUJ7Q3C21XFjVdjR5JOJWos_O25C-IetbmP_BDrxJ63Bb6Z4mvDvQwfkkPZz-ih-Wv6aHF9rwl4XHh9vZ8I5sYUxscNXOl5kFw1sbiBl0WQw9DxTkNplOUiXG545jurUeyhtMh9LiBzlQXsjePfsX61omdiMcPRvO4VYoOMYnRjHnfPfybpelsGkESz5PpTxQZ1A_mheelxlWPBbugy-GKACiL_BtiU_2kD6yC4aqpguGqvwqi3oNlS_R5W_Qk4NNJGrZEsBkS9C0KVgle9knas0NKhFbuFetC10Je84zS4iBYvY1eH60DSMswuDjG9zksAlUZcw-1-oCs_pUn3MAdFKU0P6D-e82zIlV6Swa4uv1E706DtQG8RccAi0MDRPNk3j6gJGCw_LvvZIVrrBrylzTWNmnP8q0GLAuPkDgrQS_Q77bge1svuPjjvS95r8hiWdKZv75wdYdv1t_cLq-qOjai_cznexemNOsdpL_FLOaB3_aoPZlfUtYfp_t7Od2zimXJtLylypntjEnuNu5mzDj4vRnz_9iB_xSIP7H66wXC7xSIZIEn-b1IGKGlhHt1qwrzSeOtaJMIlgnPjdIv2cYh_7wtHH6j1nfKWf48OFRB0E1aUbz4iaRVSduz09eV-PtiudHhK3H0v7XVr_nspG2weTLDkzu8uSYcN9PfVplWiSHezx9oMTzUoh_P55OWDLgzInErcrCtpee7_Iw39Nn6DtLjPn9MBfdcr8Fc83hj7_ypX3EM6KOINNdPV1mqrra5PAqslPxUmrw0l0IeJ_mOUC9uf6k1f6K158bd4_XXyhdQrUFkuRZZhQtZuW2tq9x8Myi8--W28E-RJa-CfgEtUgG6Bo5o5c2fr_gnsaF8jCzx_QZ2t9fnWjw2CTn0w0PPnB565nwyiSdsy0X2I3zwvaI_H7dPqX3NpSvGZaHYo9NC4hrTPEls_5ma9EYx-N50gSMN_MF18Kltvu8Ub4Tr78a8sO16LBRgbA-_jDftFnar6b9T-oGlSqMubYdLFE1T2HXMkZIWaHIu2V0zAaqa3hZ8K9YbY1vZEVj4CBCsULKsm_Zcmo0q1xumaPzgWNqO85PlwW3fD2PNyioyWiLChTAltzS2HCHTFGz_WhMp9Cw7RPoHbuWJiOEFpvCf5g-PAnZMpI4Kvmy73EqZCA1OBbhjxHrkUtB5p5IsV0UhqGWeiu-kV2r6bak1j8a2Wj1otnf72yJN2XC4RiNwmj29dQTFoh-BdrwwTuA78z2-8ELwJnyRjEYwW0wjz4cojhM29rzpZOKAh8Phj0lUh8KZe_2MgNTFnXhsOA4DD70FayYSqn4EU1YtW8O_tQfa7nledhrQ1cQCoVZXuD6m7i6eca55PgJKKVVLnSZtDUr1N_D9e22jTjHHF32IJjDW_NalMqKFDkhDpfPLz2zH5QMen7k2kBAzalXvu9NIs7oFWLkus79cXQ0xYxYQKxSm6WKjZuu5EMLc1dDT1QhjAbMn6HrYNz_ofvttAm78inSs5M1QgSZDzoExbZH_V4xwkxuMOVnnjhYlXuKio5PU558LJOPECs9Id3byS8LM2jIwm0Ao0JEEDTM_UTTRfpZuZwfWqlD6kW4sksPvx2IU2YjmwEmvNN4sc7x040YbvUiNpr5SD7-ktJMdqsumJOrw1y73nMTdivg5L6lVhIq9sPPDSiLKja0aekOeRCUcK-aMdHhDg4aj5nwuLOW-DUfbFlgATMuWvfK93Yf2WBpMqdFLdAl9APvBSH2te6X7uyKYYlXrUCTIoMd9VyrD5F-Ci0A7mbQOXOJlaaellAJmhmEiXmuakeKGdkLK-pGACKTake3xbuYZdau-ZgZrs7od0Co8_LkhbQtnt3GHrrkzdntk7_JKM7LviZV68PZKtF5oqtBkShIodUNbMnU-aucQm74I1Oa1NtVhK3NMK6u_ZvKacCXD_Ua4SXPzoEHP4FqYwuW-ggbcG04YdtoH2t4QYirp0rWHF8J5gWxjiwO6GlLQ9KhBMeoS_VLXaSSGmkMvyGlAjR6SCl2YUU8deI-HLeonLQ4U37B49wc6OvHZYtT1xHfl1dH1JZ310FxYHhDFFkCMM7IiWoBXbaNSk-5rx7VulKhdVh_P6GqXLj1JhBGXmWJEBy2jqBXxDY3-rYjjbwL9luM1ZqO6eBA5g21uniqZrbfhGRndJAOox8jNIWNCt3lzd8aYzt339z5i3Iw-2DjLSilzo9v1_mZ0eWxpNbJ67AQjxe9LK_2c3InBOkMfamv5CH7HIjeKjgdrKnz2VoEe_GiMrSK6vcHfGuiaijH8EvInPPjQETkqt3n90E2XcAWvdNF9NukkOQ2SRbDgJwbvZeD0kguJvrTP-0nbj1n1uE-VLeyR5aTU8vSFh8_qg2r7Hq31_Fk4Db3gZHOazAI_TMdJAHEQTpPUT-JgFvqTmR9OvTgOTiTHmlKc0sEnPD8Rp77n-95sHHj0GY7SYEqn7TSaJXE64TP0NcB7RDkixiOl1yf61MoQlesCF6Uo0PGbRYxtsUZPrunjIWij9GnCMwEy1XgDZlR2YqU-tSL_F9tZHb4">