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

    <tr>
        <th>Summary</th>
        <td>
            [x86] Backend hangs during `CodeGenPrepare` due to infinitely sinking `cmp` expression
        </td>
    </tr>

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

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

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

<pre>
    ## Description

The backend hangs with the following input during `CodeGenPrepare` when targeting `x86_64` / `i386`.

## Minimal Reproduction

https://godbolt.org/z/373K8TdhM

### Code

```ll
define i32 @f(i32 %0) {
BB:
  %P0 = alloca i32, i32 8
  %P1 = getelementptr i32, ptr %P0, i32 1
  %B0 = icmp eq i32 %0, 0
  br label %BB1

BB1:                                              ; preds = %BB1, %BB
  %P2 = getelementptr i1, ptr %P1, i1 %B0
  br i1 false, label %BB1, label %BB2

BB2:                                              ; preds = %BB1
  %P3 = select i1 %B0, ptr %P1, ptr %P2
  %L1 = load i32, ptr %P3
  ret i32 %L1
}
```

## Cause

`sinkCmpExpression` keeps adding code for every `CodeGenPrepare` iteration so the loop is never broken. 

https://github.com/llvm/llvm-project/blob/dacfdbcdd917ea424e367fd373ba4287563ee93b/llvm/lib/CodeGen/CodeGenPrepare.cpp#L1674-L1738

Dump of IR for each iteration of `CodeGenPrepare`:

```ll
; Original
define i32 @f() {
BB:
  %RP = alloca i32, i32 20, align 4
  %L = load i32, ptr %RP, align 4
  %G = getelementptr i32, ptr %RP, i32 1
  %C4 = icmp eq i32 %L, 0
  %G3 = getelementptr i32, ptr %G, i32 4
  br label %BB3

BB3:                                              ; preds = %BB3, %BB
  %G1 = getelementptr i1, ptr %G3, i1 %C4
  br i1 false, label %BB3, label %BB1

BB1:                                              ; preds = %BB3
  %S = select i1 %C4, ptr %G3, ptr %G1
  %L1 = load i32, ptr %S, align 4
  ret i32 %L1
}

; Iteration 1
define i32 @f() {
BB:
  %RP = alloca i32, i32 20, align 4
  %L = load i32, ptr %RP, align 4
  %G = getelementptr i32, ptr %RP, i32 1
  %G3 = getelementptr i32, ptr %G, i32 4
  br label %BB3

BB3:                                              ; preds = %BB3, %BB
  %0 = icmp eq i32 %L, 0
  %G1 = getelementptr i1, ptr %G3, i1 %0
  br i1 false, label %BB3, label %BB1

BB1:                                              ; preds = %BB3
  %1 = icmp eq i32 %L, 0
  %S1 = select i1 %1, i1 false, i1 %0
  %S = select i1 %1, ptr %G3, ptr %G1
  %L1 = load i32, ptr %S, align 4
  ret i32 %L1
}

; Iteration 2
define i32 @f() {
BB:
  %RP = alloca i32, i32 20, align 4
  %L = load i32, ptr %RP, align 4
  %G = getelementptr i32, ptr %RP, i32 1
  %G3 = getelementptr i32, ptr %G, i32 4
  br label %BB3

BB3:                                              ; preds = %BB3, %BB
  %0 = icmp eq i32 %L, 0
  %G1 = getelementptr i1, ptr %G3, i1 %0
  br i1 false, label %BB3, label %BB1

BB1:                                              ; preds = %BB3
  %1 = icmp eq i32 %L, 0
  %2 = icmp eq i32 %L, 0
  %S1 = select i1 %2, i1 false, i1 %1
  %S2 = select i1 %2, i1 false, i1 %0
  %S = select i1 %2, ptr %G3, ptr %G1
  %L1 = load i32, ptr %S, align 4
  ret i32 %L1
}

; Iteration 3
define i32 @f() {
BB:
  %RP = alloca i32, i32 20, align 4
  %L = load i32, ptr %RP, align 4
  %G = getelementptr i32, ptr %RP, i32 1
  %G3 = getelementptr i32, ptr %G, i32 4
  br label %BB3

BB3:                                              ; preds = %BB3, %BB
  %0 = icmp eq i32 %L, 0
  %G1 = getelementptr i1, ptr %G3, i1 %0
  br i1 false, label %BB3, label %BB1

BB1:                                              ; preds = %BB3
  %1 = icmp eq i32 %L, 0
  %2 = icmp eq i32 %L, 0
  %3 = icmp eq i32 %L, 0
  %S1 = select i1 %3, i1 false, i1 %2
  %S2 = select i1 %3, i1 false, i1 %1
  %S3 = select i1 %3, i1 false, i1 %0
  %S = select i1 %3, ptr %G3, ptr %G1
  %L1 = load i32, ptr %S, align 4
  ret i32 %L1
}

; Iteration 4
define i32 @f() {
BB:
  %RP = alloca i32, i32 20, align 4
  %L = load i32, ptr %RP, align 4
  %G = getelementptr i32, ptr %RP, i32 1
  %G3 = getelementptr i32, ptr %G, i32 4
  br label %BB3

BB3:                                              ; preds = %BB3, %BB
  %0 = icmp eq i32 %L, 0
  %G1 = getelementptr i1, ptr %G3, i1 %0
  br i1 false, label %BB3, label %BB1

BB1:                                              ; preds = %BB3
  %1 = icmp eq i32 %L, 0
  %2 = icmp eq i32 %L, 0
  %3 = icmp eq i32 %L, 0
  %4 = icmp eq i32 %L, 0
  %S1 = select i1 %4, i1 false, i1 %3
  %S2 = select i1 %4, i1 false, i1 %2
  %S3 = select i1 %4, i1 false, i1 %1
  %S4 = select i1 %4, i1 false, i1 %0
  %S = select i1 %4, ptr %G3, ptr %G1
  %L1 = load i32, ptr %S, align 4
  ret i32 %L1
}
```

</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJztWVFz2jgQ_jXmRVPGloxtHvxwwJV2js5lkr53ZGvBaoTts-wm6a-_lcFggwmkk8mkHTIO1kq7693Vfh8gokw8hRZleJEZ6LiQeSmz1LJnlv3X5vVrAiTi8T2kgiQ8XWnyIMuElDi9zJTKHmS6IjLNq5KIqjCC5dnTTMAc0psCcl4ATpCHBFJS8mIF5VbnMfC-ea5Zs-hHMyFZ4OFt2H76NrYvMpVrrsgt5EUmqvgwyKQsc20xVP-I1yoTUabKYVasUPqJ_8xn_wRfRfLl2Ldxb8LtrHj25lJqMyFgKVMgklFiufbSokE9pCPbomNi-ZON2mRiYqiHxKzeYG5sRjiWKebG2qLT2knQVnJqJSwMKFhDWuZl0eiaYe2nMXRahpONdxmvcwL_kX1EU2I3alFBFI9A1foTp52kERmqvOTPYhOSFyB0_eStT3xePWrnRPtyctop1YJ0Nom0wsWpJVcazHIn9K5Mu6nQ10mllQGr5zXGH5f7OA8TaATaMl1sNlRlXBzuI2vUCiibDVs0u-LPDrqvBwhTXunDVtUyvZ-u878fMR2tDTIQU_cAuSZcCIO2GPsb0VoQ-AHFUz9AZQkFN7giOqvRrbIsJ1KT1BjhzmRIAUPyDOqQFqpoGGdrFJT60dw-IGS_YxFRjFQW4U3weCmiWIix4wN3qQvM85cCQRqhFPgjjwGMWdTyI42wDXo_2oY_jPMci7NwPN_9sHB8FrSjnFWIj2xJPt9uSsDjpJUsLvSVY4fjE4RguuffQq5kyk9SxLPUcHtzghpo3WRcyVVK3HZXnWqq25t-g_lZWtlYHtLK1O2jlUWHVox7dtb_vHHv9tMR62KYvQaGWR8dzXsptg3gOdvT0dQ9T0fsiJ5en1lZK4O7YzbCMA_jbwTnIja66-mbZ3lp1_mfd_Bx_rDm_526uvft_xinL-r9C96J37r1nYvSvHOOEdJ8xNhlcZBjP66OS_P2sKJXWF1h9R5gRX8ZfLQffO2uuKMXm53BLH0HmGVXzF4x-_tglv0yslk_ROkZZJ8w6xBCz5fuE2ZnCIG9A0Jwr4RwJYQ_jRAuOxzoow23H8jsDG2cMKNnaOOEWYdt3IvNzrDNm38T754QDiB0PM9jY5dSdyBCJsZszAelLBWE1mjyGHjWaEYmnVP85w7rRQWkzIhMkbkkYuOJmDPGrTpuvdGB3XHjoCpU-OKzQKl1BRoHo2DEgkESgnBZbNsjzwncse8twXciFgmfx24Qx1QMalxpk5BFaQoPpHaBY0xuIENqU-rY1KHM8W13GMBSBKYkXHBmj8fIvbDmUg1NHOangUER1iFF1UrjopK61PtFjqmtUqjrZ_zzqkyyIvzEfz5h6MmgfnZYx_4_7s9ZlA">