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

    <tr>
        <th>Summary</th>
        <td>
            [SimplifyCFG] Infinite loop of transformations on branch on widenable condition
        </td>
    </tr>

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

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

    <tr>
      <th>Reporter</th>
      <td>
          d-makogon
      </td>
    </tr>
</table>

<pre>
    I was investigating an xfailed test `llvm/test/Transforms/SimplifyCFG/pr52290.ll`. Running SimplifyCFG on it results in assert crash:
```
opt: llvm/lib/Transforms/Scalar/SimplifyCFGPass.cpp:240: bool iterativelySimplifyCFG(llvm::Function&, const llvm::TargetTransformInfo&, llvm::DomTreeUpdater*, const llvm::SimplifyCFGOptions&): Assertion `IterCnt++ < 1000 && "Iterative simplification didn't converge!"' failed.
```
Here is the IR:
```llvm
define i32 @test(float %arg) gc "statepoint-example" personality i32* ()* @blam {
bb:
  %tmp = call i1 @llvm.experimental.widenable.condition()
  br i1 %tmp, label %bb2, label %bb1

bb1:                                              ; preds = %bb
  br i1 undef, label %bb7, label %bb5

bb2:                                              ; preds = %bb
  %tmp3 = getelementptr inbounds i8, i8 addrspace(1)* undef, i64 16
  br i1 undef, label %bb6, label %bb4

bb4:                                              ; preds = %bb2
  call void @snork() [ "deopt"() ]
  unreachable

bb5:                                              ; preds = %bb1
  ret i32 0

bb6:                                              ; preds = %bb2
  br label %bb7

bb7:                                              ; preds = %bb6, %bb1
  %tmp8 = call i32 (...) @llvm.experimental.deoptimize.i32(i32 10) [ "deopt"() ]
  ret i32 %tmp8
}
```
SimplifyCFG applies some certain set of transformations, and then applying another one reverts the IR to the state before those first transformations. It continues until the assert fails.

Here are the transformations applied step by step:
1. We simplify the unconditional branch in `bb6`:
```llvm
define i32 @test(float %arg) gc "statepoint-example" personality i32* ()* @blam {
bb:
  %tmp = call i1 @llvm.experimental.widenable.condition()
  br i1 %tmp, label %bb2, label %bb1

bb1:                                              ; preds = %bb
  br i1 undef, label %bb7, label %bb5

bb2:                                              ; preds = %bb
  %tmp3 = getelementptr inbounds i8, i8 addrspace(1)* undef, i64 16
  br i1 undef, label %bb7, label %bb4

bb4:                                              ; preds = %bb2
  call void @snork() [ "deopt"() ]
  unreachable

bb5:                                              ; preds = %bb1
  ret i32 0

bb7:                                              ; preds = %bb2, %bb1
  %tmp8 = call i32 (...) @llvm.experimental.deoptimize.i32(i32 10) [ "deopt"() ]
  ret i32 %tmp8
}
```
2. Then update the `bb2` to branch to `bb1` on true condition (this is done by `tryWidenCondBranchToCondBranch` in `SimplifyCFG.cpp`):
```llvm
define i32 @test(float %arg) gc "statepoint-example" personality i32* ()* @blam {
bb:
  %tmp = call i1 @llvm.experimental.widenable.condition()
  br i1 %tmp, label %bb2, label %bb1

bb1:                                              ; preds = %bb2, %bb
  br i1 undef, label %bb7, label %bb5

bb2:                                              ; preds = %bb
  %tmp3 = getelementptr inbounds i8, i8 addrspace(1)* undef, i64 16
  br i1 undef, label %bb1, label %bb4

bb4:                                              ; preds = %bb2
  call void @snork() [ "deopt"() ]
  unreachable

bb5:                                              ; preds = %bb1
  ret i32 0

bb7:                                              ; preds = %bb1
  %tmp8 = call i32 (...) @llvm.experimental.deoptimize.i32(i32 10) [ "deopt"() ]
  ret i32 %tmp8
}
```
3. Then (when trying to optimize conditional branch in `bb1`) decide that `bb2` should branch to `bb7` on true condition (through a new `bb7.critedge` block):
```llvm
define i32 @test(float %arg) gc "statepoint-example" personality i32* ()* @blam {
bb:
  %tmp = call i1 @llvm.experimental.widenable.condition()
  br i1 %tmp, label %bb2, label %bb1

bb1:                                              ; preds = %bb
  br i1 undef, label %bb7, label %bb5

bb2:                                              ; preds = %bb
  %tmp3 = getelementptr inbounds i8, i8 addrspace(1)* undef, i64 16
  br i1 undef, label %bb7.critedge, label %bb4

bb4:                                              ; preds = %bb2
  call void @snork() [ "deopt"() ]
  unreachable

bb5:                                              ; preds = %bb1
  ret i32 0

bb7.critedge:                                     ; preds = %bb2
  br label %bb7

bb7:                                              ; preds = %bb7.critedge, %bb1
  %tmp8 = call i32 (...) @llvm.experimental.deoptimize.i32(i32 10) [ "deopt"() ]
  ret i32 %tmp8
}
```
Then repeat the same thing starting from step 1 over and over again.

Step 3 is done because SimplifyCFG looks at branch condition in `bb1` which is `undef` and tries to find a "known value" for it in its predecessors. I think it supposes that if we came to `bb1` from `bb2`, which also has a branch on `undef`, then it can assume `undef` in `bb1` is true too, so it changes the `br` in `bb2` to branch to `bb7` on taken path.

Disabling step 2 transformation from here solves the issue and the infinite loop is gone.

Does anyone have ideas on how to resolve this? Maybe we should consider disabling the conditional br to conditional br widening?



</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJztWd2PozYQ_2vIi3UITEKyD3nY3Wjbfaha3W11zwaG4MaxkW2SS__6zhjyQW57d5X2Wp2aVbSA8cz85oPfGFOY6rB8ZnvhmNQ7cF6uhZd6zYRmn2ohFVTM4zCL8kSp3TbiT3SJhxcrtKuN3Tq8-CC3rZL14fHpJ7xq7YzzuyRWCqVi9r7TmlReTGJGM-mZBdcpT6aZcA6sZ6UVromy-yhZRck9ig-_cGlaj7fYgEPJ4jMYpVDCjvH8hprjsm1Rkk8Tki-MUWgdLHq6A3UYgV8E7Qggu3_qdOml0RHPI_7ISqMxDufbL8KuwZ_sP-vaDDPPc1Zm-2IBfm8rgfYifv-aogv7v7Zk0AU9d4T1PoQFxygBz6jjUWPwH_DHouyRpUmSsDA7xwN_PjrFXK9TliIIV7JCN-aebO8AcUc8xfk4xPokx68G_GewwKRjvgH2_P7ztAQfwlAFtdQ4N-MsmiZ9iSxqZQRWDp9hpNAfti4JpPMYi9ZI7d_BJ4EwEQxnLVhntFDSH0gLhgrnLigKdDZNCiW2LJo_9OaK4gSGkQG_bTEeK4b5x9SmJEDYYviEeuUWtBcq3ssKtCgUxBiFSvapDSYGRYUNskFdyKMoQNF1UfCr63SIxIAmpVz9o78oe2CthcoF3EHnGEanMaZXVudX17MxCv6WKPowZOEG1jkooDC2HsHpwiA6fGwXhEcumKgq61pRYiYX6ZCzE36ZT1maf925_Op6OnZu-hbO8SOMUCg7IysqFaeN3fSlwKLZAxVpBUQ29IQMo6ujZKctiLKhOhoDnL0FwPRoxoIPT1MyNpK_aRQwGaPqGpmav4WpkNSxZ31hLS6eVyINvojjOIT6tUc3pENu5Z8QB3JYkEyafFPCjpEc7A5OzlevMt5ljxItnoJjzmyBlUjDAvuUQ22mZv5I-2Ig7EfsmBURpQ5yh76HGhyw2OwAUSDv-iOVMm_CWeBCVgBqAhwwDlgtLXaHK_0xew7cja25Q0QdnqigYGibROIuvsxfoG4RtMK1tsGzCs1Dy4pDOJ4INY3Zx1MDOQR5bIRHxhQKq0bosqGmjWGjFOfJrTXcWsN3bA3Xzt1awyut4U34mv9gfM1j9kKc24UVdiCrQEoc_xPJDlyFZ2E4pWFcD3vbATs96uSNb3Cdi7-KyBopESd6e_hIvPCI8x6CnhdzPidNPQVe9IzwopEn_eL9xojfkRHPhfo_58b0xo3_Ejf-GIyYDYyIavZ0RBajtSgy4BEA-8JiLu3Zi1VQIgEgnwp_QaiuMZ2qrkl1_gVStaZbN0wwDfthclxa6aFaA0kVypSbG1ve1o_fef14LrobWX6dLM_R-kZr_-0ewzi7PxBVB5620AJSWdgNEFuiXKJrZDIb9uFra7b9e3rKzA5s2GboT9ZC6tE7_wealp1XsVCKzsFo310Zs8H3f3_k8DNdX3YAtm8kNQVHQ_0DhYNhg8PSjggyP3JyhbyOQdhos9dsJ1QX2LY2lrb2JW3wu5AqKME5Y2kTI3i3ofuua1vjSBe1GFmzPfaO4P_lUj14f-o_lN4emVDOsEagJ0dH-h3yI1aaGfZi0FIpwteFbgsjb0b-0h43dS9vDImichJshF6DO71U2Euxv3nBOPVCsUHrrfDNKEMr6fCh7hOMueJXOzO9vw1t3TijdoNtieDhuL2EADD0WO6UypaArzHXYyMGBYU-UA00YociFWCoUH1j9oTUQtBOyXBR9sR-EYcCKAFDf6cPFChjWXWCS5bHywZSdDUSuiDORp2XePr_E1imeZ4sMp7k2aRaZtVddicmXnoFS3yuLr_CzFbseeTm5ztu5M459af-e4Y06axaNt63jvo5f8LfWvqmK7BFh89Hw1ckPLxrrfkDSvqqFWJNn5Jmc87TSbPE6p3yKS8yKJIkm2d1kSzysqwB5rO76V0yCeTmyAOs_qJbEy3MVhO55AnnySJdpNN0yrP4rp6nZV7nMyHqeZLOkHpgK6SKAwEZu57YZQCDOhzxknTenW9iBcu1hhAq0i863xi7rN5txcZgCUwC8mWA_Re-uLGb">