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

    <tr>
        <th>Summary</th>
        <td>
            [LVI] Suboptimal evaluation order
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            llvm:optimizations,
            missed-optimization
      </td>
    </tr>

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

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

<pre>
    Consider this example:
```llvm
define i1 @test(i32 %x) {
  %a = add nuw nsw i32 %x, 1
  %b = add nuw nsw i32 %a, 1
  %c = add nuw nsw i32 %a, %b
  %d = icmp ugt i32 %c, 2
  ret i1 %d
}
```
The comparison can be folded to true, but `-passes=correlated-propagation` fails to do so. The relevant LVI log looks like this:
```
LVI Getting block end value %c = add nuw nsw i32 %a, %b at ''
PUSH:   %c = add nuw nsw i32 %a, %b in 
PUSH:   %a = add nuw nsw i32 %x, 1 in 
PUSH:   %b = add nuw nsw i32 %a, 1 in 
POP   %b = add nuw nsw i32 %a, 1 in  = constantrange<1, 0>
PUSH: i32 %x in 
POP i32 %x in  = overdefined
POP   %a = add nuw nsw i32 %x, 1 in  = constantrange<1, 0>
POP   %c = add nuw nsw i32 %a, %b in  = constantrange<2, 0>
  Result = constantrange<2, 0>
```
Notably, the values get pushed in the order `%c, %a, %b`, which means that `%b` gets evaluated before `%a`. But `%b` depends on `%a`, so it will use an overdefined value, rather than the more precise range we later compute.

We can get it to fold by slightly varying the input like this:
```llvm
define i1 @test(i32 %x) {
  %a = add nuw nsw i32 %x, 1
  %b = add nuw i32 %a, 1
  %c = add nuw nsw i32 %a, %b
  %d = icmp ugt i32 %c, 2 
  ret i1 %d
}
```

Removing the nsw flag makes CVP issue a query for `%a` earlier, avoiding the problem.
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJy8VV2PozYU_TXm5WoiYkIgDzzMTJp2pVU72m2nzxd8ATfGprZJNv31lU2iTab7kT60EgJhn3vul881Oic7TVSx_Inl2wQn3xtbabmXTVIbcaqejXZSkAXfSwf0CYdREcseWbpl6SNbp_Oj1GGYlwS1UhPIJbBV6sl5xkuZcWA8_8T4BljxNAMhLCGwbAsoBOjpCNod4TP2GZZXyPprSHyLbL6JDFRXYBHBshlGmDp_QTYByS8wSz7mw3NxTrvYvsl__v21J2jMMKKVzmhoUENN0BolSIA34O1EgbmePLB1-jCic-RYtm2MtaTQk3gYrRmxQy-NZusUWpTKBVthwJkFBBeWFB1Qe3j_-g6U6UAZs3eg5J5im_7Znvk3wH8k76XuoFam2QNpAQdUE91XN0APjBfhiYQvv338iWWPcGfZQWr4guF3zsBXrL5zHq6sfnm52yIiGqOdR-0t6o5Y9rwM2ynLfriN4hLkrafr1chmDmRnTYg38dyR913xXPjua8AXKfktJcAHcpPy92DfnLGfjcdanQLG9zQfLgcdeRgn15MIIYQNY8NQCWZntd3oMyw_w7GXTQ8DoXbge_RneNgOjA4o0AfVQE2tsXQGIFunC3iabgwEjaSFA6OvUMGLMyA9HKVSMDkC1NctmxMIMIu-j2MQ5wSG4G-01EhHEGsDR4KgYRtnwORpca5QfP9OcR6ESkgfBB3GAtQncEp2vVcnOKA9BWkGdqnHyX9L0f_3wP3Phy3862k7vz_QYA6XsgX_rcIOBtyTg-fXF5DOTQQIf05kT9Aae9V-ILRKkg0B4MFIceEZrakVDYtEVJnYZBtMqFoW6WpZluV6k_RVXnKxLotS5PlG0JK3dd0gX2bYZpum5UUiK57yVbpMebpZFavNol0WddmKsmnWZdnghq1SGlCqRejkwtguiZFWxbpI80RhTcrFa5nz2Ovs0YxeDvKveDU4xoMOGeeDdI7Ew_Vm2Mu3ia2C4UM9dY6tUiWdd5-deelVvPbfv75j-RY-TnWkQHVRlTR6VmkyWVX13o_xGPId47tO-n6qF40ZGN_F8OZPuL3-oMYzvovZOMZ3MaG_AwAA___4RW1M">