[LoopVectorize] Miscompile in epilogue loop

[d-makogon]

Repro: https://godbolt.org/z/vWK3Yx8c4

This IR does something similar to:

// 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:

%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:

%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 %arr. Then the array after the first vector iteration would look like this:

arr[0] = 1 * 3 = 3
arr[1] = 2 * 3 = 6
...
arr[15] = 16 * 3 = 48

So this vector body is correct.
However, as we don't know the exact amount of iterations, 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:

store <8 x i16> %27, <8 x i16>* %31, align 2

%27 is the following:

%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:

%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:

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.

[llvmbot]

@llvm/issue-subscribers-bug

[d-makogon]

@fhahn I see you had a lot of patches in vectorizer last months. Could you please take a look?

[fhahn]

Thanks, it looks like this is another instance that needs https://reviews.llvm.org/D92132