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

    <tr>
        <th>Summary</th>
        <td>
            SimplifyCFG speculation transformation is blocking vectorization in LoopVectorize
        </td>
    </tr>

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

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

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

<pre>
    After commit 47d831f2c90225a7d2 (https://github.com/llvm/llvm-project/pull/100514) I noticed a regression in a downstream benchmark, due to a loop no longer being vectorized. It seems like the changed cost of "llvm.umin" (from 2 to 1, given that the operation was legal for the target) impacted SimplifyCFG in a way that allowed a transform that simplified the control flow by speculating the umin together with a select statement. Unfortunately, that new code emitted by SimplifyCFG is for some reason not recognized by the loop vectorizer.

Here is an IR example cfg.ll to show what happens:
```
define i32 @foo(ptr %0, i32 %1) {
  br label %5

3: ; preds = %14
  %4 = phi i32 [ %15, %14 ]
  ret i32 %4

5: ; preds = %2, %14
  %6 = phi i64 [ 0, %2 ], [ %16, %14 ]
  %7 = phi i32 [ 128, %2 ], [ %15, %14 ]
  %8 = getelementptr inbounds i32, ptr %0, i64 %6
  %9 = load i32, ptr %8, align 4
  %10 = icmp sgt i32 %9, %1
  br i1 %10, label %11, label %14

11:                                               ; preds = %5
 %12 = trunc nuw nsw i64 %6 to i32
  %13 = tail call i32 @llvm.umin.i32(i32 %7, i32 %12)
  br label %14

14: ; preds = %5, %11
  %15 = phi i32 [ %13, %11 ], [ %7, %5 ]
  %16 = add nuw nsw i64 %6, 1
  %17 = icmp eq i64 %16, 128
  br i1 %17, label %3, label %5
}
```

If only running the vectorizer we get:
```
> opt -mtriple x86_64 -passes='loop-vectorize' cfg.ll -S -o - | grep umin
  %11 = call <4 x i32> @llvm.umin.v4i32(<4 x i32> %vec.phi, <4 x i32> %vec.ind)
  %12 = call <4 x i32> @llvm.umin.v4i32(<4 x i32> %vec.phi1, <4 x i32> %step.add)
  %rdx.minmax = call <4 x i32> @llvm.umin.v4i32(<4 x i32> %predphi, <4 x i32> %predphi4)
 %16 = call i32 @llvm.vector.reduce.umin.v4i32(<4 x i32> %rdx.minmax)
  %27 = tail call i32 @llvm.umin.i32(i32 %21, i32 %26)
```
But if first running simplifycfg there is no vectorization:
```
> build-all/bin/opt -mtriple x86_64 -passes='simplifycfg,loop-vectorize' cfg.ll -S -o - | grep umin
  %12 = tail call i32 @llvm.umin.i32(i32 %7, i32 %11)
```

The transform done by simplifycfg result in this IR:

```
define i32 @foo(ptr %0, i32 %1) {
  br label %5

3:                                                ; preds = %5
 %4 = phi i32 [ %13, %5 ]
  ret i32 %4

5: ; preds = %5, %2
  %6 = phi i64 [ 0, %2 ], [ %14, %5 ]
  %7 = phi i32 [ 128, %2 ], [ %13, %5 ]
  %8 = getelementptr inbounds i32, ptr %0, i64 %6
  %9 = load i32, ptr %8, align 4
  %10 = icmp sgt i32 %9, %1
  %11 = trunc nuw nsw i64 %6 to i32
  %12 = tail call i32 @llvm.umin.i32(i32 %7, i32 %11)
  %13 = select i1 %10, i32 %12, i32 %7
 %14 = add nuw nsw i64 %6, 1
  %15 = icmp eq i64 %14, 128
  br i1 %15, label %3, label %5
}
```
And loop-vectorize complains like this with `-debug`:
```
LV: Checking a loop in 'foo' from cfg.ll
LV: Loop hints: force=? width=0 interleave=0
LV: Found a loop: 
LV: Found an induction variable.
LV: PHI is not a poly recurrence.
LV: PHI is not a poly recurrence.
LV: Not vectorizing: Found an unidentified PHI   %7 = phi i32 [ 128, %2 ], [ %13, %5 ]
LV: Interleaving disabled by the pass manager
LV: Can't vectorize the instructions or CFG
LV: Not vectorizing: Cannot prove legality.
```

Is this some kind of limitation/bug in loop-vectorize? Or is it a phase ordering problem?

</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJzMWFtv6zYS_jX0y8CGRN2cBz8kcd0GKHYX7W5fF5Q4kthDkVqSsuP99QtStiw7Tk-Tc7BoEDiRh3P_OBcxa0WjEDckeyLZdsEG12qzKX_XPS5KzY-bx9qhgUp3nXCQFnydxDWtHiJKM1ZwCoSuW-d6S5JHQneE7hrh2qFcVbojdCfl_vxn2Rv9O1aO0F0_SEnoLo6iLE4JfYAXUNqJCjkwMNgYtFZoBUIBA64PyjqDrIMSVdV2zHwh9Bn4gOA0MJBa96A0SK0aNFCiUA3ssXLaiP8iX8GLA4vYWZDiC4JrEaqWqQY5VNo60DUQSr2Jq6ETitDgVG10B9RriL22RuxRgWuZCwJ0j4Y5b-OBWZDYMAm1NoHmmGnQebdE17PKIYdfRddLUR-fdz-OTh3YcRTGpNSH4LczTNlam24k2JFFIB8t1soZLaGW-gDlEWyP1SCZ8756urccnG7QtWjgIFwLDCxKrBxYxxx2qNwK_qVqbdygmEN59H4FXQoPUGmOgJ1w3t7yeG2yDc5Z3SEYZFYrny8wWOlG-Rh7Bm9FSMUUerMi0ZZEj-PnT2jQS2IKXn4BfGVdLxGqullJ6cNsW32AgzenZX2PKiBq5M-j02945FgLhSASCiSNaq0JXffOAKFZ5F0KBJrFPgOkeBqZAEoDkpUoPS2bG5aQ5BFI8gS9QW6BJNvAnp4ZCc3S8G3filF49hROZF5bOAok256PG3RnE9K5muyuGjrJmKnLL-ryNKiLTsdo0OT_P9mQ37WB0Kx4Y3JM1-9Jue8Jodk6SGnQoQwI8nEWqtSD4tYL9nxXsff20iyfiXgIIqRm_IYhWMOkaBTMnY-jwCCqrgfbTLF8OJs4y6eIRwZPmnIbx9ePV0mIY5-Fj_28ydkJPUE6DV86M6gK1HAAZQ9TEDyqvcsz35LxOBMSKiblGcRT8VmFEK1PPhdzOFNCH-5h-cbB9C7MpgTHc2uyu7BOprM3MClOhOwGJPGIV8b5mxB4jiuVxSW5-J_zsRHFHp9vcltcJTO5ejrf4mJ7t06Mny81aCWPYAalzsXyUqHggB7d75UakvwAunew7JwRvly9rvN_5ykse2YtWpJsCS180VtOIgktzkVt-SssNSyBFM_QGOxDkZ4HIw7BCEAgyXMKrwEuyQ_XkNinIyhujtBsj9Wqb0XIyj2aUHyGmQtav1VhfFejddivGL9RafjrqhOqY6_fptqj-T1fT7T0ovkCyje3bEzUyiAfKvyK0ovx107R4kPXmMaze0zzSdYN2J4GB6KGWhjrJriexoBjVQfoji1U6QnCYQj5I_iWg5B8ycLAVfrpZvdVQM90Evr8eXjTzxe7-L0gjZ__9GPWNC9xrTDMRLNYGbSDdH7Ycq2w8PLLJUb_t5niO_aZ-wNIcq8gf2z-ODcG-rnxI32nJXxo-rjrxl97-LhU7z_d-r_LbZhPEafpfj4EzWaF6aGY1cT0zzfq7G6jTt9t1NnnG_Wj4nBdZfy-2Usm1LSzCTsuNSSPlhzLofHc75S9n3_zUH9usfriS-hpQxQKCC3C1S4gbHdjHZvz_OwPtkI5v3z4nadCXxKTHRwEdy1JthEI5dBIZHtPutK488g8qQuX7S3N77R8qMLmuGdGsFLian7uHz-9jBXeAYNe-8EFq8EYVNUnD_5Nu6lbCNVcGTMowVG5cc30Er_L5R31vpzj5HPAhfWuTouibzfQMcUaNFdJY4rQ4mLwuK4LZZ0Zo2ZBG3je_fgVD5-Z8pHpjd7juJ4Ld1z90ZhoR5CFHfeLUBx0DVJ0wo0dlu7KofEYummHyQ7-bnwiRMhDyyyCNhyN97o3upTYkWQ3KlnwTcIfkge2wE1c0CRP83SdLNpNnVV5kXOMq4oyzOuioklUlFjTuMyTNFuIDY1oGq3jNE7TmMarJKbFQ53mdV6XUZrlJI2wY0KuQj3RplkIawfcxFEa0WQRrqINb3ko9et-oBJKSbZdmE14P1MOjfUFSVhnL2KccBI387cB06sHrS5NeHwUFkqpx2t3NaH4yPnL9ds5cIvByM2HXxwFq214dRTc2m_o_wIAAP__13E0CQ">