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

    <tr>
        <th>Summary</th>
        <td>
            Reassociation pass incorrectly uses an existing vector with poison elements as replacement in (sub A B) -> (add A, -B)
        </td>
    </tr>

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

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

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

<pre>
    There appears to be a miscompilation bug in the reassociation pass when reassociating vector values that have poisoned elements.

Minimal IR Repro:
```llvm
; Function Attrs: argmemonly mustprogress nofree norecurse nosync nounwind readonly willreturn
define dso_local <4 x i32> @do_stuff(<4 x i32> %0) local_unnamed_addr #0 {
entry:
  %sub.i = sub <4 x i32> <i32 poison, i32 poison, i32 0, i32 0>, %0
  %add.i = sub <4 x i32> <i32 1, i32 1, i32 1, i32 1>, %0
  %shuffle.i14 = shufflevector <4 x i32> %sub.i, <4 x i32> %0, <4 x i32> <i32 2, i32 6, i32 3, i32 7>
  %add.i15 = add <4 x i32> %add.i, %shuffle.i14
  ret <4 x i32> %add.i15
}
```

when compiled with `opt -passes=reassociate`, will produce:
```llvm
define dso_local <4 x i32> @do_stuff(<4 x i32> %0) local_unnamed_addr {
  %sub.i = sub <4 x i32> <i32 poison, i32 poison, i32 0, i32 0>, %0
  %add.i = add <4 x i32> %sub.i, <i32 1, i32 1, i32 1, i32 1>   ;  <---- Problematic line
  %shuffle.i14 = shufflevector <4 x i32> %sub.i, <4 x i32> %0, <4 x i32> <i32 2, i32 6, i32 3, i32 7>
  %add.i15 = add <4 x i32> %add.i, %shuffle.i14
  ret <4 x i32> %add.i15
}
```

The main issue is that in the resulting IR, `%sub.i` is used to compute `%add.i` as a negation of `%0`. However, this isn't correct as it introduces extra poison values that were not originally in `%add.i`, and these will make there way to the final return value . The poison values already present in `%sub,i` are not observed, since the shuffle removes them.

Specifically, `NegateValue` in Reassociate.cpp has this loop:

https://github.com/llvm/llvm-project/blob/c3c930d573656a825523b7112891bd97eec7b64f/llvm/lib/Transforms/Scalar/Reassociate.cpp#L878-L882

which identifies `%sub.i` as an existing negation, even though it contains poison elements where the previous result did not.

I noticed this on latest trunk (fb45f3c9486f5d9e3003db95386432562b23577c), but it appears to repro as far back as 9.0.

Here is the minimal repro being fed through alive-tv, which also catches the incorrect optimisation: https://alive2.llvm.org/ce/z/iiYDkZ

Original C++ repro ( [Godbolt link](https://godbolt.org/z/jvcvo5eaW) ):

```cpp
#include <immintrin.h>

__m128i do_stuff(__m128i Input) {
        static const int ConstantVals[] = {0, 1, 0, 1};
        __m128i Constant = _mm_load_si128((const __m128i*)&ConstantVals[0]);

        __m128i Zero = {};
        __m128i NegatedInput = _mm_sub_epi32(Zero, Input);
        __m128i ConstantMinusInput = _mm_add_epi32(NegatedInput, Constant);
        __m128i InterleavedNegInput = _mm_unpackhi_epi32(NegatedInput, Input);
        __m128i Result = _mm_add_epi32(InterleavedNegInput, ConstantMinusInput);
        return Result;
}
```

Will produce this for X86 assembly:

Clang 8.0.1:
```asm
.LCPI0_0:
        .long   0                       # 0x0
        .long   1                       # 0x1
        .long   0                       # 0x0
        .long   1                       # 0x1
do_stuff(long long __vector(2)):
        pxor    xmm1, xmm1
        psubd   xmm1, xmm0
        movdqa  xmm2, xmmword ptr [rip + .LCPI0_0] # xmm2 = [0,1,0,1]
        psubd   xmm2, xmm0
        punpckhdq       xmm1, xmm0      # xmm1 = xmm1[2],xmm0[2],xmm1[3],xmm0[3]
        paddd   xmm1, xmm2
        movdqa  xmm0, xmm1
        ret
```

9.0 - trunk:
```asm
.LCPI0_0:
        .zero   4
        .zero   4
        .long   0                               # 0x0
        .long   1                               # 0x1
do_stuff(long long __vector(2)):
        pxor    xmm1, xmm1
        psubd   xmm1, xmm0
        punpckhdq       xmm1, xmm0              # xmm1 = xmm1[2],xmm0[2],xmm1[3],xmm0[3]
        psubd   xmm1, xmm0
        paddd   xmm1, xmmword ptr [rip + .LCPI0_0]
        movdqa  xmm0, xmm1
        ret
```

When passing <0, 0, 0, 0> to the function, the 8.0.1 assembly will correctly return <0, 1, 0, 1>. However, the 9.0+ assembly will return <0, 0, 0, 1> instead.

In the C++ case, InstCombine changes some elements of `%sub.i` to be poison since they are unused by the unpack/shuffle. However, the Reassociate pass then uses these poison elements when it shouldn't, and that ends up propogating to an incorrect return value.

For more context: this code was found a by a fuzzer to test codegen, it was not manually written
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJztWF1z6jYa_jVwowljbAzmgot8nLSZOd3tpJ09u71hZFuATmzJtWRIzq_f55VssAlJ2p1upxfNEJAt6f3S834p1fnL6uedqAXjVSV4bZjVLMUTK6XJdFnJglupFUubLZOK2Z1gteDG6Ez6iQoP7LATqv9ebdleZFbXbM-LRoDqjlu243vBKi2NViJnohClUNZMRsHdKLj23z9IJUtesIdH9iiqWo-idmI0D_ynKPZl-yq6YfeNypwY19bWBqsZr7elKLUqXljZGAsa21pARKU3tRD4qUXW1IZG5kVl-GnUQaqcxM_dtoMsilrYplaeTy42UgmWG70udAbhRtHtjD0zGYWj6BMbzYJcr41tNptRmJzNhXEwCpfM7Vs3SvFS5Gue5zWmooCNFjeeBwxRvxyVZbTRNOlEgtcdw-icZ3SLUWvLUXjLXj8Fp0H0icZOlhN5CPER-WlH4tLgIlGzgxUKMZHTmSftn1ssvLKNU9GRuWC1V2-9UGEnwrwbRN1gQUKdaTiNnSAYv2biFrRa9CTvSAADb-yZxi0CF3dn6Oxj2TmF9yHA_SDtjmGFriy7IqcRgOvdyWcE7YYshD4G1OZNJt5D__8JlR0g_1wIXjyePjp-AxwZaCIi0Oor_LEfa50ixCAaZayAqf6G6WWYIvyzkiO2S2MagW8frI_B3jSFC-gPj04GQmlrkXlAqxsDdCNrENIbK9oVXmis4AbJRImtzxZ6086TFBP2vT7A6jURtjvQkgbgWVjQqhGmLW2WJIr1_mCYeLY1b2E2yC0HymFKW6ZruZWKFwjkUGEoDPHhCPVQDAnAeVrJnwQ9Y_eBv5AepPWGKDCfBDwbNmFkqCFnXlDSeIG7gp6yJ4awD3h5_Tu5UiPqvchJBiNV5rh2yAOrUu-dLqIcJMSfKpHJjcxIodb-_yBjin-RCO4IFFLlMYpMsqpCojXenoXW1SmIuO-dtRUlylF4j88WUQlnibPDgwsu_ucKEegrTgCPaaGhzH0WZcsoyONFNI_nPAnjOIzSxXQaJstpmi8XQmSLdD7b9OhI2vdzzZXZ6Lo0ePgJenAc9_2ZxEiGn5NFcvU5ScJhCJXZjskcxoURYJ8z-BG4FEAhjYNoBzMyFHBFCNbNdkcYyrSyALnpTrCrPqh0qf1Z4BT3UjemxTzLZU4nNziOB3ojM0I82ReEUB8JY5mtG_UEz0s26SzewFazZL6J86WIgiDK02UcJfNZFMbzMA2jeLHIEIBJzLSxJF6v-qqp7iHNNrxmKc-eaLycBAM5viehnavCeduayW9MBVli4ySsnfa8kHtxZfcuuziD8sLAX7nNdh5ywFDncUhPEqWfNyPKqSFcHKlwQgc80fWWYCHw9Q3_Uv7n7umXvoz_bD2R3Y7CG3xaAWEjNopvvtN5qmFlhOanUXyHt2fI9PMtG-LwdZ_tdSz4F8pdZL4hsI_BjfDk34QRFCuaXLioXJYUSKSa7I4B2H-v1yVgLFkvYXavHhRimuPXJcZRsDTWJRVAyrjgxG5pxJWFTxqoBnVcNMceF3JcmmpHCMXRiVLHpiPgtq3LEimd52sjMTlyH8-rXT4Krx165md8A2fHZY_BGZtfBNnfS_aGJD645E7vozTwt7WoKLuECdEgVTrLvKcOqvnGDEkhFB9J9XkRyW7bG1QflBV1IdBE5Ng5JNuoCp6yk2_Sfk_cR-_vl0S8wLMv6UnBM9Jt6vCUTxPvJuIvvcrPhxeETfbvZM6oWizT4uUM8bcFh6snCA3T15UiN22hOPl8--NDsA563YX_mxQa2xkL2OU_uA8LnoPLm6bvbpr-2Zx6ruu2ua_12ld0eBk6h1m-skH1DBPj77ksnZe63-EKgD8frjgTFJk7_5W7FWG74qDrnFW2pkBXy4pR9DueA0UHyE7LvTPGLkwQdf8b370pQnhZhAr4B_zzX9vnvrAna9Fbx9FNxzehixe3jlz_ieaiwVz0WiZ4yZlZwjfNElw2LZzkHXdAymNXPq_-T-j-RsGOsdlve_0BQoeg-51IHW7-CyD2Y7j0Rf5DYfOxbK-B9YE3_bGw-0JdO_XnVEahbAiOybv9QoPVdQnt5ZNvX4SPxMdg7fuLtq7CY5sSOpL9oiD6dNYKCSr4SM0hsTMSwYAEKhFj0Y4M61XfxXUVWMaN8NnQ2FtdpnSDkO2QRVAHGl2KU1l8bNSOtba_GGzL52MH8-IanEa5LjB9cdx8MkbF1nWr58r1qn9_f2jJ6CBh2tbsQpGuqEw2qOeL3PWIp14O3Z9QORrRirJnpbf-AhLyojc4Vbb9bm5go3s4VKmhBfUIaDCp7HXpN9M5dYWUhxtw4qQfx6l_QwxxGKDCnxZthb_zsG41dXslV43rQQ-1tFaosVhN5_NwGU7jZD7OV1G-jJZ8bKUtxOrx9YXqUWyQcHbptzntPYW7UTq3FKf2pSp45p5dRxomdHtzzW6ojr3yFwQJ3TRck9BX9Hrc1MXqd3eG7sKA2rp4MU-i8W7Fp7NFLtI0RxckBJ-lAU_iRZ6GYZpNeZiOC56KwqyoRg5DJQ7-zgFjuPFYrsIgDIPldDpNouVsPlkuFptFksVRMM2mgm9Gs0CUXBbH_mNcr5xIabM1mCxgH3OaJB_eKiFWviQf8wbtYL26EeorXGXsWK-c6P8F_Oyrew">