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

    <tr>
        <th>Summary</th>
        <td>
            [FixIrreducible] Assertion `std::abs(NumInsertions) <= 1 && "Unbalanced operations!"' failed.
        </td>
    </tr>

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

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

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

<pre>
    This bug was found by Azul FuzzGen IR test generator.

https://godbolt.org/z/ocvT445Kx

Run opt with -passes=fix-irreducible:

```
; ModuleID = 'bugpoint-reduced-simplified.bc'
source_filename = "gen_001_fix-irreducible"
target triple = "x86_64-unknown-linux-gnu"

define void @function_0(i1 %val_i1_11) {
entry_1:
  br i1 %val_i1_11, label %bb_4, label %bb_2

bb_2:                                             ; preds = %bb_4, %entry_1
  br i1 undef, label %bb_4, label %bb_4

bb_4:                                             ; preds = %bb_2, %bb_2, %entry_1
  br label %bb_2
}
```

Stacktrace:
```
opt: /root/llvm-project/llvm/include/llvm/Support/CFGUpdate.h:87: void llvm::cfg::LegalizeUpdates(llvm::ArrayRef<llvm::cfg::Update<NodePtr> >, llvm::SmallVectorImpl<llvm::cfg::Update<NodePtr> >&, bool, bool) [with NodePtr = llvm::BasicBlock*]: Assertion `std::abs(NumInsertions) <= 1 && "Unbalanced operations!"' 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/compiler-explorer/clang-assertions-trunk/bin/opt -o /app/output.s -S -passes=fix-irreducible <source>
 #0 0x00005633ecf7fcaf PrintStackTraceSignalHandler(void*) Signals.cpp:0:0
 #1 0x00005633ecf7d6dc SignalHandler(int) Signals.cpp:0:0
 #2 0x00007fd85ba833c0 __restore_rt (/lib/x86_64-linux-gnu/libpthread.so.0+0x143c0)
 #3 0x00007fd85b55003b raise (/lib/x86_64-linux-gnu/libc.so.6+0x4303b)
 #4 0x00007fd85b52f859 abort (/lib/x86_64-linux-gnu/libc.so.6+0x22859)
 #5 0x00007fd85b52f729 (/lib/x86_64-linux-gnu/libc.so.6+0x22729)
 #6 0x00007fd85b541006 (/lib/x86_64-linux-gnu/libc.so.6+0x34006)
 #7 0x00005633ebd39359 void llvm::cfg::LegalizeUpdates<llvm::BasicBlock*>(llvm::ArrayRef<llvm::cfg::Update<llvm::BasicBlock*>>, llvm::SmallVectorImpl<llvm::cfg::Update<llvm::BasicBlock*>>&, bool, bool) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x2339359)
 #8 0x00005633ebe4933b llvm::GraphDiff<llvm::BasicBlock*, false>::GraphDiff(llvm::ArrayRef<llvm::cfg::Update<llvm::BasicBlock*>>, bool) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x244933b)
 #9 0x00005633ec64058f llvm::DominatorTreeBase<llvm::BasicBlock, false>::applyUpdates(llvm::ArrayRef<llvm::cfg::Update<llvm::BasicBlock*>>) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x2c4058f)
#10 0x00005633ebd310ab llvm::DomTreeUpdater::applyUpdates(llvm::ArrayRef<llvm::cfg::Update<llvm::BasicBlock*>>) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x23310ab)
#11 0x00005633ecfaebd6 llvm::CreateControlFlowHub(llvm::DomTreeUpdater*, llvm::SmallVectorImpl<llvm::BasicBlock*>&, llvm::SetVector<llvm::BasicBlock*, std::vector<llvm::BasicBlock*, std::allocator<llvm::BasicBlock*>>, llvm::DenseSet<llvm::BasicBlock*, llvm::DenseMapInfo<llvm::BasicBlock*, void>>> const&, llvm::SetVector<llvm::BasicBlock*, std::vector<llvm::BasicBlock*, std::allocator<llvm::BasicBlock*>>, llvm::DenseSet<llvm::BasicBlock*, llvm::DenseMapInfo<llvm::BasicBlock*, void>>> const&, llvm::StringRef) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x35aebd6)
#12 0x00005633ed015aca createNaturalLoopInternal(llvm::LoopInfo&, llvm::DominatorTree&, llvm::Loop*, llvm::SetVector<llvm::BasicBlock*, std::vector<llvm::BasicBlock*, std::allocator<llvm::BasicBlock*>>, llvm::DenseSet<llvm::BasicBlock*, llvm::DenseMapInfo<llvm::BasicBlock*, void>>>&, llvm::SetVector<llvm::BasicBlock*, std::vector<llvm::BasicBlock*, std::allocator<llvm::BasicBlock*>>, llvm::DenseSet<llvm::BasicBlock*, llvm::DenseMapInfo<llvm::BasicBlock*, void>>>&) FixIrreducible.cpp:0:0
#13 0x00005633ed018d81 bool makeReducible<llvm::Function*>(llvm::LoopInfo&, llvm::DominatorTree&, llvm::Function*&&) (.isra.286) FixIrreducible.cpp:0:0
#14 0x00005633ed01c061 FixIrreducibleImpl(llvm::Function&, llvm::LoopInfo&, llvm::DominatorTree&) FixIrreducible.cpp:0:0
#15 0x00005633ed01e325 llvm::FixIrreduciblePass::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x361e325)
#16 0x00005633ed2a9181 llvm::detail::PassModel<llvm::Function, llvm::FixIrreduciblePass, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Function>>::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x38a9181)
#17 0x00005633ec70315a llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function>>::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x2d0315a)
#18 0x00005633eaa779b1 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>&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x10779b1)
#19 0x00005633ec702b6a llvm::ModuleToFunctionPassAdaptor::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x2d02b6a)
#20 0x00005633eaa78311 llvm::detail::PassModel<llvm::Module, llvm::ModuleToFunctionPassAdaptor, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x1078311)
#21 0x00005633ec701494 llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x2d01494)
#22 0x00005633ea6b2b4a 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) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0xcb2b4a)
#23 0x00005633ea5efdc3 main (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0xbefdc3)
#24 0x00007fd85b5310b3 __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x240b3)
#25 0x00005633ea6a626a _start (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0xca626a)
Compiler returned: 139
``` 
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJztWl1z4rgS_TXOiwrKtmwDDzwQGGZTO5lNTbL7Skm2DLoRlkuW8_XrtyUTsAwhZIbZ2ru7qQQwUh91H51uS1aozJ7HdyteIVov0SOpUC7rIkP0GU1eaoHm9cvLZ1agq29Is0qjJSuYIlqqvufPPH_SvK60LisPT7xwDr9LmVEpdF-qJVy9wJ9MH-6iKP71qW30rS6QLDV65HqFeiWpKgYYs5w_9bhSLKtTTgUzqC0jL_E3v80lvkTXMqsFu5ohMEZeOIBASskL3bMYLOtVfF0KnnOW9WkKHRrTStYqZYucC1aQNdtYhxDgwveDRdeNMGzMNFFLppFWvBRbo6dhskiiXl3cF_Kx6Ale1E-9ZVFvrZrXjOW8YOhB8gx5kZ_XRaq5hPG8cMgDAIofiFjwYBEEXjhC3uCysWOFVs-LYEsFQlShPYMpEoQyYb6ldBF1v3A8sdcYgD7wY7gugZBqE_V2FPj46qHjHuiI5e_6FXX8is7hV7jxq_Vx38VD7Axmh3VmX281Se-1ImlLlW4_0LNxHySvpNTwJsTDulcq-T-Wvl7CGy9SUWds98VtXZZSmR7T-effy4xo1l8B0nBg4KxgbE8YFk_SfNl8-MKWRPAX1hhUoKJdp4lS5Pkb8I-nBywbC2j7KjN2o5WHPwF7n-zcbHvfrokQf4DjUl1BBn0QKTFgVEqxewdJx5c23Ted7YztQC9JxdNLIdN7L5x48czEPoGyoEyWICC50lnTk1AT7dd6fVVsmisLj6cG0WQGDJ-Y1Py9oESQAuoAFBtTupq-gUnNcIByAvmfbYrZzZdPk9tPqKrpmmtEbElUzEwM0hJ1ihyEUdN-Kte7WexMNq-q2szKHBGoqJs5R3rFUKpItUL0VU39lrxQVq_Lrbx8aBrdKLlUZI2g8tRrkHG1kZgRWzgHD0qIQfXYUymkYsp8BxEve-SVuqqnFdQmaKC8aAxRTxoIUpbmutZlrfsV6t2-XYgNuU3NNNPbZJEXYh_5Tz78xAnGLM0HeUpydKOg_tpw7kx8t3xZEPELsCCMe0OjZzPDMGNNU9VPSxO0b_-22EEHO0uyFHXBYKR3gcIN0CDPhjElQ4xTHy0WCu5owNgC5heAzARyCq-bat6q4qah1CvFSNavZB_q9aX_FESAAkPvhsHOMHHs-5giRXjFTsBPDXJikSMMhg5y5CKH-TAeIULlSZ63kMMQDB3kuIs8MHn0MUwwcTATFzMKfD_5GCaOwMTBHLS1QDM8wsDAqYWxXbncImMq1cer5hG0Hyui7wAfrqmW2B8pBs00YsupQ_rQIZ1FIwyC3vn4WZFyNeN5fsRzcDSHvLRFo2P0M4g_NymRjdkhZeRUpSTy42HeImUm17wwK-Q7xRh4-bbbXWagGIvnH7iXv0PO-UhJbcxbUkyl9jvpGfiEuqQYOhpX1f9ZuNhG44TbuTMRCDlphTuFO4VmUwlLTinmQj7-UlMnxA4fTZ6cVjT261fSMWa6MT2eldu11MNHOoNfMiXH-x-ogjMG6zRw7Pgonf7XpLwqcnncxq4lmhFh5ZnCNOr_GHmfEdi_FkuTY-fLExzbNHDyJGznSeYHMUkJrH5NdnwlulZEfJESYoIkgNWbkyJNAwTb9d0psHutxmw_n_69AvgvGTpcjNCcP13t9jX7OwYjXNwR7jAbBnZxgdbknn3bPZ1qDT7fPM85sK78TjG3Ee2OdpOufV4p0g-HJ4cTdcJJ_SToGNobTdvn3eAHUuzEYE7zLu54x3AYt1lwIG6gEDXfQxU6zeEJ1JbnilfXpCBLpg5P2lYe5yqHiY3DKYeJE2hIRgGoaudLxjThovlswryWGRNvSGx6nCCn_QY2ukw9sKwhglXfR8_rOvVvzvvQ0urw7mwe04EPkiNtfgzXx3z8B9MVZpYNhy5n20fIYDCi55DpT6P53yv2wLeT48zeqCP2kCZtsTfHJXfy1SczK5OMlPamfSjixuBD8W5MfoJWTTDtaEO_o9Wh2Zx9RKuv4U1P5OhcYttx9JbU_j7Eg8wMrw7xQUdmQTSKTkj2Q3T_U2gCfRoWHJqcHRBJaEijdjYCjmHqhpdM8II5gbU2afvi3Iv3zh5MXpN0ZXEmh1q_cKqIejaLt2a51-0FC9zf7GHAnIsDID_U_EY4B5_27Pp2y_vB7pZCUS95sdcf5mahzUNBe9W49ysvsmO9_mDKHBer137uE9e33s8mo9SKxFGRsx0hMcuzFMNOhBfnGpNaSGfMzpkDDnyK0WJhHtQvKk2UXrQcOPWsIAIQZ5TYzQ-ShHC3avDPxqcF3Y463SAhxXStCma2rijAo86BLrrIxjgb4RG50FwLNvbiS3eh7cWzv-h48qJWYvz954-G2-hiNSbxIM2GoxhHwxzHjCU-g3kP2ShkOE1TdmFPxCsTKYxfsEdkIYwv8eyCj0M_DH2o9EEQxj7u03BACY4IYwEJSOZ7kc9AEqJv_DD__XGhxtYlWi8raBS80tWuEeaNLwtmiTX4pNYrqcYFZH51T57JhR18bJ3_E2tPhx8">