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

    <tr>
        <th>Summary</th>
        <td>
            Mul reassociation in instcombine does not maintain NSW (for example impacting alias analysis negatively when canonicalizing GEP)
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            llvm:instcombine
      </td>
    </tr>

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

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

<pre>
    Consider IR like this (also in godbolt here https://godbolt.org/z/rW8K8zfnc):

```
; RUN: opt -passes='aa-eval,instcombine,aa-eval' -print-all-alias-modref-info ....

target datalayout = "p:16:16:16:16"

define i16 @foo1(i16 %x) {
 %a = mul nsw nuw i16 %x, 2
    %b = mul nsw nuw i16 %a, 3
    ret i16 %b
}

define i16 @foo2(i16 %x) {
    %a = mul nsw nuw i16 %x, 3
    %b = mul nsw nuw i16 %a, 2
    ret i16 %b
}

define ptr @foo3(i16 noundef %x, ptr noundef %p) {
    %cmp = icmp sgt i16 %x, 0
    call void @llvm.assume(i1 %cmp)
    %a = mul nsw nuw i16 %x, 3
    %idxprom = sext i16 %a to i64
    %b = getelementptr inbounds i16, ptr %p, i64 %idxprom
 store i16 2, ptr %b
    store i16 1, ptr %p
    ret ptr %b
}
```

It seems a bit inconsistent that instcombine for foo1 is able to keep "nsw nuw" on the simplified mul
```
%b = mul nuw nsw i16 %x, 6
```
while for foo2 nsw is dropped
```
%b = mul nuw i16 %x, 6
```
and for foo3 both nuw and nsw is dropped on the mul
```
  %b.idx = mul i16 %x, 6
  %b = getelementptr inbounds i8, ptr %p, i16 %b.idx
```

The foo3 example also show that dropping "nsw" on the mul may impact alias analysis as it no longer is able to derive NoAlias after instcombine.


I think one problem here is that InstCombinerImpl::SimplifyAssociativeOrCommutative only deal with Add/Sub when using the maintainNoSignedWrap helper.

Here (https://alive2.llvm.org/ce/z/RqG2pz) is an alive2 proof showing that we at least should be able to keep nsw on the second mul when doing "(A mul B) mul C" ==> "A mul (B mul C)", as long as the associated Mul operations are both "nsw nuw":
```
define i8 @src(i8 %a, i8 %b, i8 %c) {
    %x = mul nsw nuw i8 %a, %b
    %y = mul nsw nuw i8 %x, %c
    ret i8 %y
}

define i8 @tgt(i8 %a, i8 %b, i8 %c) {
    %x = mul i8 %c, %b
    %y = mul nsw nuw i8 %x, %a
    ret i8 %y
}
```

Maybe there are more situations when "nsw" can be kept given that (B mul C) simplifies, e.g. when all involved values are known to be non-negative?

PS. When using the reassociate pass instead of instcombine the result is even worse, since it drops both "nuw nsw" even for foo1.
</pre>
<img width="1" height="1" alt="" src="http://email.email.llvm.org/o/eJykVltv2zoS_jX0y8CCRfkiP_jBcepusGi2aHaRZ0ocWWwoUktSdpxffzCifEvanhYHEGyJHM58c_uGwnu1M4grNrtjs_uR6EJt3ar4blscFVYeVxtrvJLo4OEbaPWCEGrlgfFcaG9BGdhZWVgdoEaHUIfQepatGd8yvh22Eut2jG_fGN-65_zf-VtlSsaXJDbpn_lkeCZrlt3Bt_89smwNtg0wboX36Fl2z_hCiDHuhWZ8o4wPpW0KZZDxzXl9AePWKRPGQuux0Er4cWOlw2qsTGUhSZIkWgzC7TCAFEFocbRdAJbdA-O8Zdk6nb__4Twek1gpg6DSObDppLI2ZTzvv_jslfElsMUdm6zpU_Qam06D8Qcw3QEuchsgfQBA38XPBAUJZoOgw3BaLwjL4v4niPiPEUVbvwaV_S4o_nug2uAGUNkAytjOSKzOFkniaq39ALhs2h6Johe_Czd4J4NcKbSGvVWSrGm9bxLhfddgb3TQQuX252FQ8rV1tunFPb6ezQsIFtR8-j5gOwyosUETyDNlCvLN06mTt9HLDR2-MkB6fLAuJpJfCReDictueqPqkoirA0Mirrtqsn4I4BEbDwIKFUCZkhrbBzQBQi1o5dxTUFkHVN6gPIhCI_n7gthSiwwxY5yDNRBqBK-aVqtKoaSgvjd9U03doY_5dbzn7w4caqXPCHgU9yCdbVuUf6f8V4qFkSe1GRQ21P0JWr21cXLroy8x1YmSr2ej7w3-RjXkH4ph6CFS_DFx_60xQsZX0bQaoSdeX9tDzFuPWpndkJurvBC-RhxBNa0oA_SECMIIffSUVw8qgLGgrdmhu061RKf2CI92HY9UgfYv9TGwKFUVjQPzApb63dlCYxMHgfIR3YPxYRNPuYem1UT62fopVsxx7b0tlQhqj_9xG9s0Xeg_wBp9BIlCw0GFGtZSMr596go41Gig8-Rv76JQJghlHu0TzTH57EQLNeoW3QDyX4SG8fx2Mgmt9siTni3idCpxGFHf_v-Zt29ERRQRA1GUvLNVH_ZoWwQ4IIgAGoUPtNFpCQXe9gtV1qlLsLSm75DohLRD0hjP1_3yHRmllw0lkWYePZ9IJgownt-dBJb9yQ2lkRJI_2RFDBFFCV86DbZFJ4KyxoNwGKv-poeHIXxVcqeRkhOdelcSjeZn7o-vxeW1_EDarx_p9XL-itMYnx1_Ivo6iJbXk6bfOf5o-vVQwy78A6hniT-FKH4F8baTv4hjQfcnqkjKRkOc7lXohgz1ZXHp4lIYqqcXbAPs1B5NrLqbIrhwryc8mOySqIZmojJ7q_coYS90h7ECXow9GCrPAsFYMza46zuOZdsI8utTAs-3TebwXFVA97GeClBIsNXN1IiyvtOBWgcJ8cE6T1c08MqUSIRDdOUvhRgHArnby58GTzKSq0wus6UY4SpdZIsJTxfz6aheLSTPUaYzWaXLii_m0_k0xwUvq2yWF4tsNlIrPuGzSZrO08mET6eJ5CJfFlWRZykvp7xg0wk2Qulz94-U9x2uUp6li9lIiwK17y_EnJMIy9Y3901OF2W3oq1x0e083TqUD_6iL6igcUX9dwmdsoZuy9fxkhY9GBvOLAaPT8-UX4rCie0jeVMq3vH3KXP6GDNeCmONKoVWbyT9-dNXxpejzunVu0u5CnVXJKVtGN_2_sW_cevsdywD49s-Hp7x7RCS_Yr_FQAA___rEqy7">