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

    <tr>
        <th>Summary</th>
        <td>
            [LoopVectorize] Miscompile in loop epilogue vectorized code
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            bug,
            miscompilation,
            vectorization
      </td>
    </tr>

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

    <tr>
      <th>Reporter</th>
      <td>
          d-makogon
      </td>
    </tr>
</table>

<pre>
    Repro: https://godbolt.org/z/vWK3Yx8c4

This IR does something similar to:
```cpp
// assume idx >= 1
void foo(int idx, int16_t* arr) {
 for (int i = idx; i < 93; i++)
       arr[i - 1] = (int16_t)(3 * i);
}
```

The loop vectorize pass decides to vectorize this loop.
The vector body code seems to be correct (VF = 16). On the first iteration it stores the value `%15` which is the following:
```llvm
%9 = trunc i64 %iv.start to i32
%.splatinsert = insertelement <16 x i32> poison, i32 %9, i32 0
%.splat = shufflevector <16 x i32> %.splatinsert, <16 x i32> poison, <16 x i32> zeroinitializer
%induction = add <16 x i32> %.splat, <i32 0, i32 1, i32 2, i32 3, i32 4, i32 5, i32 6, i32 7, i32 8, i32 9, i32 10, i32 11, i32 12, i32 13, i32 14, i32 15>
%vec.ind = %induction
%13 = mul <16 x i32> %vec.ind, <i32 196608, i32 196608, i32 196608, i32 196608, i32 196608, i32 196608, i32 196608, i32 196608, i32 196608, i32 196608, i32 196608, i32 196608, i32 196608, i32 196608, i32 196608, i32 196608>
%14 = lshr exact <16 x i32> %13, <i32 16, i32 16, i32 16, i32 16, i32 16, i32 16, i32 16, i32 16, i32 16, i32 16, i32 16, i32 16, i32 16, i32 16, i32 16, i32 16>
%15 = trunc <16 x i32> %14 to <16 x i16>
```
This is correct (`%13` and `%14` just perform multiplication by 3 in i16).
The store index is also correct: 
```llvm
%index = 0
%offset.idx = add i64 %iv.start, %index
%10 = trunc i64 %offset.idx to i32
%11 = add i32 %10, 0
%12 = add i32 %11, -1
%16 = zext i32 %12 to i64
%17 = getelementptr i16, i16* %arr, i64 %16
%18 = getelementptr i16, i16* %17, i32 0
%19 = bitcast i16* %18 to <16 x i16>*
```
If `%iv.start` is `1` then `%induction` is just `<1, 2, ..., 16>` and `%19` is equal to `0`. Then the array after the first vector iteration would look like this:
```cpp
arr[0] = 1 * 3 = 3
arr[1] = 2 * 3 = 6
...
arr[15] = 16 * 3 = 48
```
So this vector body is correct.
However, as we have array of length 92, after some 16-element iterations, we are trying vectorized 8-element loop epilogue.
And this is where the miscompile is.
Let's look at the `store` perfomed at the first iteration in `vec.epilog.vector.body`:
```llvm
store <8 x i16> %27, <8 x i16>* %31, align 2
```
`%27` is the following:
```llvm
%21 = trunc i64 %iv.start to i32
%.splatinsert8 = insertelement <8 x i32> poison, i32 %21, i32 0
%.splat9 = shufflevector <8 x i32> %.splatinsert8, <8 x i32> poison, <8 x i32> zeroinitializer
%induction10 = add <8 x i32> %.splat9, <i32 0, i32 1, i32 2, i32 3, i32 4, i32 5, i32 6, i32 7>
%vec.ind11 = %induction10
%25 = mul <8 x i32> %vec.ind11, <i32 196608, i32 196608, i32 196608, i32 196608, i32 196608, i32 196608, i32 196608, i32 196608>
%26 = lshr exact <8 x i32> %25, <i32 16, i32 16, i32 16, i32 16, i32 16, i32 16, i32 16, i32 16>
%27 = trunc <8 x i32> %26 to <8 x i16>
```
`%induction10`, whose elements are multiplied by 3 and actually get stored, **always** (no matter whether we entered the 16-element loop or not) is this: `<%iv.start, %iv.start + 1, ..., %iv.start + 15>`. **This is incorrect**. After `n` 16-element loop iterations it must be `<%iv.start * n * 16, %iv.start * n * 16 + 1, ..., %iv.start * n * 16 + 15>`. The indices are computed correctly:
```llvm
%offset.idx13 = add i64 %iv.start, %index7
%22 = trunc i64 %offset.idx13 to i32
%23 = add i32 %22, 0
%24 = add i32 %23, -1
%28 = zext i32 %24 to i64
%29 = getelementptr i16, i16* %arr, i64 %28
%30 = getelementptr i16, i16* %29, i32 0
%31 = bitcast i16* %30 to <8 x i16>*
```
Here `%index7` is the number of array elements processed by now by both loops.
Say we did one 16-element iterations and also one iteration in the vectorized epilogue.
The array would look like this:
```cpp
arr[0] = 1 * 3 = 3
arr[1] = 2 * 3 = 6
...
arr[15] = 16 * 3 = 48
arr[16] = 1 * 3 = 3
arr[17] = 2 * 3 = 6
...
arr[23] = 8 * 3 = 24
```.

opt 14.0.0 generates correct code - https://godbolt.org/z/73Wosh1jd (though it is different, it doesn't use `insertelement` and `shufflevector`, just computes values as scalars). Look at `vec.epilog.vector.body` block - `%index9` is added to each stored value in the epilogue which is number of array elements processed by vector loop.
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJzcWFtv47gV_jXMy0EEkbJk6cEPuWywi05RYHewiz4VtHRscUYWXZGKk_n1xSGpi2UnmSnaYtEgsCjx3Hh4Lh8pjVH7FnHD0nuWPt7I3ta621S3B_lV73V7s9XV6-ZXPHaaJXdQW3s0LLlj4omJp72utrqxke72TDx9Y-Lp-Y-_JH9_ycsVix9ZfOd_P9fKwC-_QqXRgNEHtLVq92DUQTWyA0uSA30W-__yeAxfnCKQxvQHBFW9AEt-YskjcD__rFUFO62ZyFVriYCJB1Ct5dk_LBN3ILuOiQLY-t4zwE53MFADSSKe5N69PECRuDET9-6_CEz-j2Sl9wpugbP00TF7SV5ZwUSeAClV9JIEjWz9uFjduXMQGq2P8Iyl1Z36hnCUxkCFparQgNWzGUueJOpoYvazQPsEpa4QDOLB8W0RSt11WFoy8_cnZzDPmCgi-FsLtkbYqc5YUBY7aZVuQVkwVnekl0TLpkcgg0XKU5bFcKpVWYPy0zvdNPqk2v3l_jXN82HYwLRwim3XtyWobAVMpOo5MlZ2lsxUiRhJI3NspFWtwc76zXFDbPCALX154Bm8OJbkJzhqZXTrNjwRJLYYxvFCopNl6n63azA4bCFroZwEvaltMfENO61aZZVs1DfsRtWqrfrSuZW0y6p6U2cQ6i0PS-DDQAyDZBishkE6DLJhsB4G-TAYfcIn0aNsPgrno3Q-iucpJduwnGcsI9VWIeyn1Y0EPHFzh765stDAPVspL7IsHs38P3qb-YyvnEsaU3eAL7K8CGHntrlTxp38k43mi0pnCX1lPSvK6vH7nPe8ALq-oMy8SIVak1CtkRRr_n1F7196Y-GI3U53Bwoyq46NKn3d2r5CAqp12kQxq46umoFqK3whVbIxetBH_ey9suWZaKVTNdG7nUEb-T7kc3pR0dxeBubJY_FlCZyJWhRBzifhvq751J3M4OKCwqX0LZ9IMkfyDV_sSCOcpmw1Ea0d0R6HCnu0nffhg3_cEZ9roQ-D3Tyb2PPvYefry6rMfU_YKltKakATcX4leMSyvfjXX3YhPkbfZzFtMstiTkNbYztQjMXKk7hYoqnkwTnOlcEoiujhdZ4HYBH48J-9bJyFWUyGRPCZlFA3lF0nX0HuLHaz1hqazdRhT7pvKurhX6FRX31Lfwf_eMgRD3CDO3jh62wypxgBiZhRhJ2idc1J01FaNiNe5Ved_Jv2qGMOM6acDYJ_1id8Rhcl0sAJoZbPg0f0Dhps97aGwnnZe4hgIPDsdujso4MM0ZyIGcF2rwQUR_xTQT4yOMyER9XofY_BjLu28sYqA6caSUKNcFCm1IejahCUCZSf0DKxNn4fpHV0LItdtaCtdmXmgNUwd4GTXGBRT_MmRN7GiNzjwuptQOQrEkse8jHAKfDFOnSBfB73NJO4CJWN2rcgriNJF6RiHYL0R7CZ4P8eOMuvo7P8HXAm-FvorLgOz_I30Vk-99UVdJb_ADgLtTnAs2s6i_8kPLsEVKHcn9s0bVA6B1X5NUzla___GlXNFiKyKyjn3FSR_jdAztyG9TkoWajPQlvJ34cki27B3QwVpFobhBDoxhWnAYFg5dEHdQtZ2l42zSu1RA89POAVd0zcyeYkX40fE9ZpNRykpWJ4qtHW9ETA1mKHlcvhWXl01U530Go6Z_okd30jNLErAGRIYibufbCG9nYxl_p2FwUzB1Sm2gEnuc8R3LnCzbLYNdGlcVMBp0PkgfrrFi-tcw2ndb9-J9-a-8DuJeG4CAJ9qq1UiX6bqPT3FquhYzWvH1TECZeF88wHIG89haB4D-XxZFlPRbJEcUKc4zyxuqBIFjhP5Bc4T6yWOE8UP47zRD6yJ_H3sIsrp--Ev4HzkvgyId-AeT9TIx8Tkxw-tbm2P2yxI4zhwcaYocdOl2iMT85Wn-ix1bZ2wTqggN_kK-VcpSrQ7RtwxOc1HRuI5AwB2PH2xWGTBRj5PGLCPz3kC0TZxyrX369TJANtPqMVq8Wyo_llmD5a4KsojmLYY0uuxul46C63bj-8glwnf2hT8y8V1Vhb635fU0VSBiq122GHrUtfZd19ZMvE2kJvXISdwZnZCeAMmYSO4E4QobgYf1NmCPyaUjayM-6S7VNAl-9BRdg2uvwKt_MIH04bsqqoFWhAWdahn4RLuRB-Q8xNF3PflxEBZLmrxJtqk1RFUsgb3PBsHedJxterm3qzjWUcp1isCrHCWHKZygoLHu8SLMQ2zW_URsRCcMFFXMRFwqM8zbNMlpJnu1Ruq4KtYjxI1URUYWmPbpQxPW7SYpUWN43cYmPczbMQ237PXPljQoyI3aXa-HnItfFr-njTbUj07bbfG7aKG2WsmZRZZRt3s_1J6-PvQ6ZSWP51diZoz88S85SmkLvpu2azCDpl634blfrAxJNrHv5xe-z0F9cxn9w6DRNPbqn_CgAA__8K63Pv">