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

    <tr>
        <th>Summary</th>
        <td>
            [fix-irreducible] FixIrreducible unnecessarily destroys child loops causing assertion error
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            new issue
      </td>
    </tr>

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

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

<pre>
    ## Version

I've tested on [llvmorg-13.0.1-rc3](https://github.com/llvm/llvm-project/tree/llvmorg-13.0.1-rc3), and latest [main](https://github.com/llvm/llvm-project/tree/f3ad7ea03a8da9afb910501538905a63901aa0db). The issue exists in both version, and should have existed since FixIrreducible pass was introduced in 11.0.

## Steps to reproduce

Build LLVM with Debug (not Release) profile. And feed compiled `opt` with following IR, `./opt -fix-irreducible irreducible.ll -S`:

```llvm
; ModuleID = 'irreducible.ll'
source_filename = "irreducible.c"
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-pc-linux-gnu"

define dso_local void @foo(i1 %a) {
entry:
  br i1 %a, label %block1, label %block2
block1:
  br i1 %a, label %block1, label %block2
block2:
  br label %body
body:
  br i1 %a, label %latch, label %inner_body
inner_body:
  br label %body
latch:
  br i1 %a, label %block1, label %block2
}
```

An assertion error will be triggered.

```
opt: /home/sun/Projects/llvm-project.15/llvm/lib/Transforms/Utils/FixIrreducible.cpp:298: bool makeReducible(llvm::LoopInfo &, llvm::DominatorTree &, Graph &&) [Graph = llvm::Loop &]: Assertion `LI.isLoopHeader(Headers.front())' failed.
PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace.
Stack dump:
0.      Program arguments: ./opt -fix-irreducible irreducible.ll -S
 #0 0x0000560ae1fd5437 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) /home/sun/Projects/llvm-project.15/llvm/lib/Support/Unix/Signals.inc:565:11
 #1 0x0000560ae1fd564b PrintStackTraceSignalHandler(void*) /home/sun/Projects/llvm-project.15/llvm/lib/Support/Unix/Signals.inc:632:1
 #2 0x0000560ae1fd3a03 llvm::sys::RunSignalHandlers() /home/sun/Projects/llvm-project.15/llvm/lib/Support/Signals.cpp:103:5
 #3 0x0000560ae1fd5e71 SignalHandler(int) /home/sun/Projects/llvm-project.15/llvm/lib/Support/Unix/Signals.inc:0:3
 #4 0x00007fdff4e7b560 __restore_rt libc_sigaction.c:0:0
 #5 0x00007fdff4ec834c __pthread_kill_implementation pthread_kill.c:0:0
 #6 0x00007fdff4e7b4b8 gsignal (/usr/lib/libc.so.6+0x424b8)
 #7 0x00007fdff4e65534 abort (/usr/lib/libc.so.6+0x2c534)
 #8 0x00007fdff4e6545c _nl_load_domain.cold loadmsgcat.c:0:0
 #9 0x00007fdff4e74116 (/usr/lib/libc.so.6+0x3b116)
#10 0x0000560ae209080a bool makeReducible<llvm::Loop&>(llvm::LoopInfo&, llvm::DominatorTree&, llvm::Loop&) /home/sun/Projects/llvm-project.15/llvm/lib/Transforms/Utils/FixIrreducible.cpp:299:7
#11 0x0000560ae208f9e9 FixIrreducibleImpl(llvm::Function&, llvm::LoopInfo&, llvm::DominatorTree&) /home/sun/Projects/llvm-project.15/llvm/lib/Transforms/Utils/FixIrreducible.cpp:326:16
#12 0x0000560ae208f750 llvm::FixIrreduciblePass::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) /home/sun/Projects/llvm-project.15/llvm/lib/Transforms/Utils/FixIrreducible.cpp:345:7
#13 0x0000560ae24fde67 llvm::detail::PassModel<llvm::Function, llvm::FixIrreduciblePass, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Function> >::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) /home/sun/Projects/llvm-project.15/llvm/include/llvm/IR/PassManagerInternal.h:88:17
#14 0x0000560ae12badac llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function> >::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) /home/sun/Projects/llvm-project.15/llvm/include/llvm/IR/PassManager.h:522:16
#15 0x0000560ade79d337 llvm::detail::PassModel<llvm::Function, llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function> >, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Function> >::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) /home/sun/Projects/llvm-project.15/llvm/include/llvm/IR/PassManagerInternal.h:88:17
#16 0x0000560ae12b99a1 llvm::ModuleToFunctionPassAdaptor::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) /home/sun/Projects/llvm-project.15/llvm/lib/IR/PassManager.cpp:127:14
#17 0x0000560ade79ce77 llvm::detail::PassModel<llvm::Module, llvm::ModuleToFunctionPassAdaptor, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Module> >::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) /home/sun/Projects/llvm-project.15/llvm/include/llvm/IR/PassManagerInternal.h:88:17
#18 0x0000560ae12b9f6c llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module> >::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) /home/sun/Projects/llvm-project.15/llvm/include/llvm/IR/PassManager.h:522:16
#19 0x0000560addfeccd4 llvm::runPassPipeline(llvm::StringRef, llvm::Module&, llvm::TargetMachine*, llvm::TargetLibraryInfoImpl*, llvm::ToolOutputFile*, llvm::ToolOutputFile*, llvm::ToolOutputFile*, llvm::StringRef, llvm::ArrayRef<llvm::StringRef>, llvm::ArrayRef<llvm::PassPlugin>, llvm::opt_tool::OutputKind, llvm::opt_tool::VerifierKind, bool, bool, bool, bool, bool) /home/sun/Projects/llvm-project.15/llvm/tools/opt/NewPMDriver.cpp:496:3
#20 0x0000560ade025763 main /home/sun/Projects/llvm-project.15/llvm/tools/opt/opt.cpp:820:12
#21 0x00007fdff4e66310 __libc_start_call_main libc-start.c:0:0
#22 0x00007fdff4e663c1 __libc_start_main@GLIBC_2.2.5 (/usr/lib/libc.so.6+0x2d3c1)
#23 0x0000560addfe6005 _start (./opt+0x11cb005)
[1]    277524 IOT instruction (core dumped)  ./opt -fix-irreducible irreducible.ll -S
```

## Explanation

The following code snippet is used to destroy the old loops that share the same headers with that of the new loop generated by FixIrreducible. However, some child loops of `Child` where also, unnecessarily, destroyed.

https://github.com/llvm/llvm-project/blob/f3ad7ea03a8da9afb910501538905a63901aa0db/llvm/lib/Transforms/Utils/FixIrreducible.cpp#L140-L145

This results some loops missing in LoopInfo, and may trigger the assertion failure below, as the loop has already been discarded. Even if this assertion is not triggered, `opt` has already been in a wrong state, which may furthermore cause other errors.

https://github.com/llvm/llvm-project/blob/f3ad7ea03a8da9afb910501538905a63901aa0db/llvm/lib/Transforms/Utils/FixIrreducible.cpp#L298-L299

## Possible fix

```diff
diff --git a/llvm/lib/Transforms/Utils/FixIrreducible.cpp b/llvm/lib/Transforms/Utils/FixIrreducible.cpp
index 10f48fe827f4..8e44528fa154 100644
--- a/llvm/lib/Transforms/Utils/FixIrreducible.cpp
+++ b/llvm/lib/Transforms/Utils/FixIrreducible.cpp
@@ -137,10 +137,18 @@ static void reconnectChildLoops(LoopInfo &LI, Loop *ParentLoop, Loop *NewLoop,
     // not be necessary if we can retain such backedges.
     if (Headers.count(Child->getHeader())) {
       for (auto BB : Child->blocks()) {
+        if (LI.getLoopFor(BB) != Child)
+          continue;
         LI.changeLoopFor(BB, NewLoop);
         LLVM_DEBUG(dbgs() << "moved block from child: " << BB->getName()
                           << "\n");
       }
+      std::vector<Loop *> GrandChildLoops;
+      std::swap(GrandChildLoops, Child->getSubLoopsVector());
+      for (auto GrandChildLoop : GrandChildLoops) {
+        GrandChildLoop->setParentLoop(nullptr);
+        NewLoop->addChildLoop(GrandChildLoop);
+      }
       LI.destroy(Child);
       LLVM_DEBUG(dbgs() << "subsumed child loop (common header)\n");
       continue;
```

I can create a pull request with a unit test if you like.

</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJztGtly47jxa-QXlFi8jwc_SPZ4VhXPxjX2zqsKJEEJGYpgANC28vXpBimKpDTra3aTbEUl0yTYaPTdDbRSke8vZ64HX_KNScVFNbOvZ_aiva5mbvTIiGZKs5yIisyCZVk-7oTczB3Psi1nLjNvFlzP3Hirda1m3mLm3sB3w_W2Sa1M7OABp3T_5rUU_2CZhkctGetGJ_jcZOZeEVrlpKS4Ni67o7z62EKFR_OIUdujcU4TWqSJYwe2E3hxYgc09BLbodTOU1jeIg9bRrhSDSPsmSutCK9IKvSWPHZS6ghUW9GUOdnSxw4S5KR4lTFyw59XUrK8yXhaMlJTpcgTRURaChgFQMDpOMD1UOSdMu41qxXRgkhWt-BDoGXDYdHb229fyBPwT65Z2mwIyKYSmnxlJaMKOE4ITC14ySyyAFILBkuCnGoYyckstEWt4dpiKERZiidebcjqK_IGLyyQGYCQecGf53zAyuDeKksyvwdg1MeQCxgxX6ORdshbki_ASclW12TmwZ8bjTHBQAuqRCMztkbSK7pjHbQ7hM7guQXWVG6YJjnVtKR70egDOJvvgCo2r90IyfNcc8FHZ_yId6FvLnN-uClinOS48byK8SY8zIF39zA8XV9LXpc9qc9xuAbAOpuXvGqe55uq6Se015wVvGIkV2JdioyW5FFw0IpvF0KAIrkDaAKKSpxFy3YKA8vZ94ImJJWkB7sCV0lZiU8p4PvunA51y3evfwoad4zmCAhhpQPDuxfXAjfPtqMRXlVMro94Bs8vLdki-yh_s-h6YspD7S0qAv7MpIZQQJiUQoIbgS-kDA1hs2FgqdZZh2gf0fW8Bax5sxU7DE6qgZByc9fGLDWJYZYTDIIbhwh18yBppQohdwj7m-Yl_h-HHCura1jETdB-IXiJkuzod_b18B6szKAESXmLWyHqVVUIICk0MunfXIsdr6gW8gHC6OH1Z0nrbfsQGhsNlt0Q2P8Yq4GCwA00LHqRgSBuVxZXCPALozmTQE17o6xCigridmzyAHwjUlCMWZ1A724_Le4_EdWkO64JJRj6IEoKqTFevjk7mCiP0jPxHEJ32eSgRYj_maRqS1KafdeSZqxb_l7DAMmbXd3bGEbwBHS3kXRHIBw0O3BVJIK8IYa21gqx3yb2sw2fILQpc4o88L1oIFO1V-3NnYRUYqh5QPJG6pT0aS0UJD666zTGUaTJByzuvqlRxmhuFX_GAb6paKksEBmsGIQBhknnyIcz5SP0UzIhusXxC0i-NCaAQXDmLv5QSkMTxgeEuhNCPagRzgn8a1ON6FWtjf4USg8ktj7r2B6K9EiiN5UlixwyFd4frWKTRY80-R1NUZEXhc-iFIgj67WEgk1ItgZ3BKzZWvENzdDprQMO-4gjGOPIYs_PAEett2C6-fo7xNQ130FiRY-iJnQM351DGU7J8tOYbJThhBiN3TRK9jwjjZYSFjjJ0n72XYDGoNOji8bowiAAxmmK0eYlZG4GsCNk8RSZHwC7VQklAHCUCyxyIVhBbYcDO7XJqD7HYzLh0Xec8EVyvBSgenLQQUeRxrUTO7bpuUThXY1DOoYU79PZ_PH76ePk7QHbh8z2LbkwgWt0lIAzlkBcJCyZVO4rML8RqzdNZez5LDOvlMGfw66HesLStefXnfIbBfaA0DGWOyhxunSCJL5GBAtwsr3i6gutKBRBI8vpJ6Hp_Hky8IOxykeh1PWLnIXD9JozDcVGl2FBALBlYeV5PkacnxHd6P0dxEUmH1neioipdwmOoPD-21TS1UzHAdxC3hjhtWuuKs0kkGFhWR6b7dRAIf4ot7kpzWk2FNwRzyvU8JeWo5Ff4LoTpw4GAsxZlOSe9zMs-o8T_P8d41WOEU4cI0moM6C_PUx5EAdaEe8ipzXkmfOSaCe8SQ7dlJ8QsU9suat03Qiv_pHraGLNGYveZs0HNq9eKaufZY29rH5si_8hDXzQDuOpHRbhawL0OT38ReX3g8CcDE05L1iW5f6AbOAOcdzxmpW8Gm_g7zVslDdfWXHOjk8E8GDOIL_QbGvwLM69veWppHKPBWpb0k6hoO7_e6PrRt_w8gySD73-ATsLKekeR4caO8JOU8VZcCPCstnw6gRe1HqtgbD2qSXvb7zKfw_qG5O84Ewe4HA79PL_99kVrooAeBro3vzKnu6-XEv-2AdHPzGnzr1BufYoNtpuEIUewU3jT1gert2ysdsefR_XdSb71hD3jut1u7_XVOp1RmGnbijBwbkZnO5cEZN7gilzxphMo8e3P9-ulldr13Kt4OWNdg5Yhjtb15t4Xgi3pF0AsVkHrmGy42QpvD1OD5bOLLgm8HGjKHB9svr7A-GV0rLJ2sNLN86EZOYMkOWo_Def8509VO5aP5-e6xLCip704rAjdezSZJD2iKp4XTNNuCKNYjkef-YM6BR7c37ZniMI7CNtqSZqS2V7sKmwqbJtT1vb9o8BEIV5W7EnM41sWMUkxY5Wup9sii3yi3hij8xkTwWGRyD09MsBImDtCkdMg2nLYGFaKoHQTVWxjClFJS_3ONCRPDkwf_M5bloKtIzXd_net6N0vVvHt-dwCcbaASVA7dCUWrUCaUWx40qhvsAxjscDbetwR_eHZoGR-7GhgMfdDYgsZaBtA64MhNHKFh5oiUdgewBgFcm5yqjMQX7k0yM8c1QjUHPEBw_YGOw7E12Dr-v_nSAEWil5kgLIBo_RJoU_bXm2NSQXjQRa5A49IKNgd0Tgc9sFUf8rOnSTeH6Lx0Gn_ncnQGXou-DLZ1s4OS-KrokHd2Q-32Af4p3EkHdz0fXFcvZMHLvw44LFblT4lhUz3w_cuKBO4MMrO_S78no-n7-bzoOIlu33g2RDgIcvmTteBNYFyQRQdvcx6V6i7fGs7YtKlgmMG9oEFfQkPHwfNq1uV2imXcMJigLJKt2eLh5HIcN2Q4feIHxa4zQOkmLwa2PTHt3oCS28gsU1JjbVZG03iOUbdjB0gwJAB-2rTDSmfWVInUNRAsVX3-M69LQGbV3SfkB0iIU2EMWXS6iBF6THYBqTqp9-nIua6D4tEbcrC2s94PIGtzbxctkWJw425tqIfMyT_VwC-aTSvGqgUB5TRQhgzLa02rAx0ivSSzM5M-n225f19aflb58BPE83favEu4Ivdsh34hETCzJGCil2bQKZmaaoe4BbLjv5_UqxthmczP_4c1xiFlxV-O-UwGNz9yADpfO2_nsEI8MN9NXBaHBD8hlsOx-YnjcVfz9dPVGQSDydAOIamsN9k5rxb-1ivVmc4B0axRinMZCTZc6bxhgMaVBMD10krpqyrLU8SwM5aBonQjXVIzrh8-z0XtZHe-oy_sFHzijoZftRTaqaHf6ipS882sJst4OMt-38LfmxDZxY_NmabGUiQAbZUUOGJjXICeLBPxv8VZKpnCgUNBD-zc-UwAX3ooEK-PuhWXyRX3p54iX0QnNdsksoLicVIpaak58KjSqkQ3mkRhUWJl4sKyY_QrhoZHn5_g54ENhJcrG9tNOCJa7jZn7h2rnnpFlYFGHuRTROojRIL8wvJhRyA7LFetGgMC53fcEvXdt1bd8NMfd4oRXbduH5QZrnXuIFUDf5NoMqv7SQDkvIzYW8NCSlDSjat0v8wdXxJfDINxUzwkP84AxbIS9hn_MvXoMQXNsJLwwBl4aBfwPTWNll">