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

    <tr>
        <th>Summary</th>
        <td>
            [SCCP] Missed optimization : better range for overflow operators with `nuw`/`nsw`
        </td>
    </tr>

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

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

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

<pre>
    Alive2 proof: https://alive2.llvm.org/ce/z/6AfwYo

### Motivating example 

```llvm
define i1 @src(i32 %a) {
entry:
  %cmp = icmp ne i32 %a, 0
  br i1 %cmp, label %then, label %else
then:
  %mul = mul nuw nsw i32 %a, 10000 ; Expected: [10000, UINT_MAX], Actual: Overdefined
 %add = add nsw i32 %mul, -5000   ; Expected: [5000, UINT_MAX], Actual: Overdefined
  %cond = icmp ult i32 %add, 4999
  ret i1 %cond
else:
  call void @dummy()
  ret i1 0
}
```
`%cond` can be optimized away:
```llvm
define i1 @tgt(i32 %a) {
entry:
 %cmp = icmp ne i32 %a, 0
  br i1 %cmp, label %then, label %else
then:
  ret i1 0
else:
  call void @dummy()
  ret i1 0
}
```

Not looking into SCCP yet, but I think such missed optimization is the same for other overflow operators like `sub` and `shl`.
NOTE: The overflow operators in original real-world ir can only be optimized at use, just like [this one](https://alive2.llvm.org/ce/z/g6_6fr). CVP/LVI also missed it, but I think it's easier to solve SCCP's one firstly, so post this issue.

### Real-world motivation

This snippet of IR is derived from [jemalloc/src/fxp.c@fxp_print](https://github.com/jemalloc/jemalloc/blob/f96010b7fa8ce5f83802144bdebf2bb7a6679649/src/fxp.c#L98) (after O3 pipeline).
The example above is a reduced version. If you're interested in the original suboptimal IR and optimal IR, see also:https://godbolt.org/z/hE3vza9Kc

**Let me know if you can confirm that it's an optimization opportunity, thanks.**
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJy8Vk1v4zYQ_TX0ZRBDpj4sHXxwkhUQdL-wTRfb04ISRxY3FEcgKTvOry9I23GcDdrtoQUEiRSHbzhv3owknFMbg7hi-TXLb2di8j3Z1bebfj9rSO5Xa622yGG0RB1L19B7PzqWrhmvGa9FXJ1rvR3mZDeM1y0yXj8xXhfrbvcnseSWJevjnaeHCz6QV1vhldkAPoph1AgXhkVyuALu4ZXEThkEtQCWJc62jJcq5cB4LhivgC2vD3ZovN2H48UZBIN2GIGlt6DCIGA877uB5GTX2IgdrcOCFg3qMPc9mosXqB0edsWlC1fDpKOr8DTTDozbXbhbJEmSAEuv4d3jiK1HGShl-XVcCBZ_3H28__5h_Y3lt2G6bv0kdDD6tEV7IEEeHQZQKaO_8Hzha5h02HyVB2_wlr_837uL5JCRZy4n7Z-jkzLsz6qqOplb9CdKyRxBIndnxlqhNWxJyZBUOQ3DnvGS8dcQxySx5e0reZynRydFAq0w0CDQ6NWgnlCC2ImzIP5JWX7jf1FZ_6OwLmn4bziM94_kQRM9hLpUxhP8fnPzGfbowzmbycMd-F6ZB3BT28OgnEN5Ylp4RQaUA98jODEgdGSBfI8WaIu207QDGtEKT9aBVg8IrEjc1ISsiaCrInG9ZkUyP57m0_27IMX7Ht9CUAbIqo0yQoNFoa92ZLUEZaMEyOj9Kx14mByGSH5Mzh8PkF_7Xjkgg7ECyl_ubpvie9FZxqs53Hz9zHj9_usdCO3oRIv6ibTwZukAhVNowRM40luMHMcFMgidss7rfdjqCEZyHuIBlXMTzt9upl_OwQ_Hvkrmpel9QHBGjSN6oA7uvoQ8SbRqixI6S0Mg4gcOQmtqGa9jf627x3HesizpHsfvo1XGv0XRRvl-auYtDYzXLyBeDBtNTYCrimSRNMtOlC3mXZmWCV9kWSOx6XjTLEVRLKsiq1755-n7qoyFyEvRebTwKYVRjaiVwcD_KUZ8_pSIhrYYQhRgUU4tStiidYrMHO462NPE-NJikDhadD5ky0TdPgvKTU1UjtCBraDO8zQmBzFmm6XrV3yQbEj7o1yCUvp36fZJVL-1l9kL13v0MCA8GNqBigeL2m3JdMoO4HvhT6oJkn5ZaDSOZP1klI9i8b0wD25-gJ3JVSqrtBIzXC2WSbFclFVezvoVllwuStFkHZeLpml50y5TUWZp1rUy6aqZWvGEZ8kiXSyKNM-zeYqFLLHIKtnmIi9zliU4CKWfa2IWlbkqk0VezWIrc_FXgnODu4NsGefhz8Kuwp6rZto4liVaOe_OKF55Hf9BYjXkt_DhjeYSmkGDPmjACrM5dpifO8NO-T50EzPt4rehDmMXxrPJ6tXfCDh-FQ6Pq9HSD2w943WMwjFexyj_CgAA___8-cRD">