Fix SLP score for out of order contiguous loads

[alban.bridonneau]

Summary

SLP uses the distance between pointers to optimize
the getShallowScore. However the current code misses
the case where we are trying to vectorize for VF=4, and the distance
between pointers is 2. In that case the returned score
reflects the case of contiguous loads, when it's not actually
contiguous.

The attached unit tests have 5 loads, where the program order
is not the same as the offset order in the GEPs. So, the choice
of which 4 loads to bundle together matters. If we pick the
first 4, then we can vectorize with VF=4. If we pick the
last 4, then we can only vectorize with VF=2.

This patch makes a more conservative choice, to consider
all distances>1 to not be a case of contiguous load, and
give those cases a lower score.

[ABataev]

Try to simplify the tests.

[alban.bridonneau]

I have simplified the unit tests.
As far as this patch goes, both tests were checking the same
behaviour, so I have only kept one. The complex data structures
and unnecesary attributes have been removed, and the IR has been reordered
to make the patterns clearer. Let me know if further reduction
is needed.

[vporpo]

llvm/test/Transforms/SLPVectorizer/AArch64/tsc-s116.ll

18–24

This test should work fine without the loop and the entry and for.cond.cleanup blocks. Please remove these extra blocks and the loop-related code.

26–29

Do you think you could replace these offset calculations with constants? This would make the test a lot smaller.

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

1199 ↗

(On Diff #422172)

Actually, this code is part of non-power-of-2 vectorization support in SLP, the problem should disappear once it is fully landed.

[alban.bridonneau]

@vporpo I was just starting to look at removing the loop-related code. That's a good point, i keep thinking about SLP in the context of loops, but it shouldn't be just about loops. The various costs seem completely different, it might require some extra work to reproduce the exact case without the loop control code.

@ABataev , that's interesting. Is that a patch you are working on? I'd be curious to take a look if that's possible.

[ABataev]

@ABataev , that's interesting. Is that a patch you are working on? I'd be curious to take a look if that's possible.

D57059 but I did not update it for a while + D105986, which is part of the first one.

[alban.bridonneau]

Further reduction of the unit test

[alban.bridonneau]

@ABataev , I had a look at the various patches you pointed. That looks like a proper piece of work! Given how much change is going to happen, i don't think it is worth pushing the fix i am proposing today.

However, I'd like to make sure my test case will get fixed, if possible. I tried your original patch (rebased last July) on the unit test and that failed. Do you think you could incorporate this unit test in your work?

I have reduced the unit test further, there is no more loop control, and the gep indices have been cleaned up. The CHECK lines are also more targeted to say we are looking for a vectorization of 4 (it currently does 2). We can actually see much better now which is the root cause of my issue. The LHS operands of the fmul are what's deciding which is the first group of loads beeing evaluated, and that group does not have 4 contiguous loads.

[vporpo]

Thanks for updating the test, it looks much better now :)
I agree, I don't think that this needs to wait for the non-power-of-2 support, unless @ABataev has some objection.

llvm/test/Transforms/SLPVectorizer/AArch64/tsc-s116.ll

8–11

Please use the utils/update_test_checks.py script for generating the checks. It makes it easier to diff test failures when tests contain automatically generated checks.

[ABataev]

In D123516#3451025, @alban.bridonneau wrote:

@ABataev , I had a look at the various patches you pointed. That looks like a proper piece of work! Given how much change is going to happen, i don't think it is worth pushing the fix i am proposing today.

However, I'd like to make sure my test case will get fixed, if possible. I tried your original patch (rebased last July) on the unit test and that failed. Do you think you could incorporate this unit test in your work?

Sure, +1 here. You can add the test separately with the CHECKs for currently emitted code and a FIXME message how it is expected to be.
The more tests we have, the better. Iy would be much easier for me to tune the patch.

I have reduced the unit test further, there is no more loop control, and the gep indices have been cleaned up. The CHECK lines are also more targeted to say we are looking for a vectorization of 4 (it currently does 2). We can actually see much better now which is the root cause of my issue. The LHS operands of the fmul are what's deciding which is the first group of loads beeing evaluated, and that group does not have 4 contiguous loads.

I'll check it, thanks. Follow suggestions from @vporpo to commit the test.

[alban.bridonneau]

The CHECK lines are now autogenerated.

I also removed the code change, and instead added
a FIXME with details of what that unit test should
be checking.

[ABataev]

LG

llvm/test/Transforms/SLPVectorizer/AArch64/tsc-s116.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -slp-vectorizer -S -mtriple=aarch64-unknown-unknown | FileCheck %s
+
+; This test is reduced from the TSVC evaluation of vectorizers:
+; https://github.com/llvm/llvm-test-suite/commits/main/MultiSource/Benchmarks/TSVC/LoopRerolling-flt/tsc.c
+
+; FIXME
+; This test is currently getting vectorized with VF=2. We should be able
+; to vectorize it with VF=4. Specifically, we should be able to have 1 load of
+; <4 x float> instead of 2 loads of <2 x float>, and there should be no need
+; for shufflevectors.
+; The current issue comes from the Left-Hand-Side fmul operands.
+; These operands are coming from 4 loads which are not
+; contiguous. The score estimation needs to be corrected, so that these 4 loads
+; are not selected for vectorization. Instead we should vectorize with
+; contiguous loads, from %a plus offsets 0 to 3, or offsets 1 to 4.
+
+define void @s116_modified(float* %a) {
+; CHECK-LABEL: @s116_modified(
+; CHECK-NEXT:    [[GEP0:%.*]] = getelementptr inbounds float, float* [[A:%.*]], i64 0
+; CHECK-NEXT:    [[GEP1:%.*]] = getelementptr inbounds float, float* [[A]], i64 1
+; CHECK-NEXT:    [[GEP3:%.*]] = getelementptr inbounds float, float* [[A]], i64 3
+; CHECK-NEXT:    [[LD0:%.*]] = load float, float* [[GEP0]], align 4
+; CHECK-NEXT:    [[TMP1:%.*]] = bitcast float* [[GEP1]] to <2 x float>*
+; CHECK-NEXT:    [[TMP2:%.*]] = load <2 x float>, <2 x float>* [[TMP1]], align 4
+; CHECK-NEXT:    [[TMP3:%.*]] = bitcast float* [[GEP3]] to <2 x float>*
+; CHECK-NEXT:    [[TMP4:%.*]] = load <2 x float>, <2 x float>* [[TMP3]], align 4
+; CHECK-NEXT:    [[TMP5:%.*]] = insertelement <4 x float> poison, float [[LD0]], i32 0
+; CHECK-NEXT:    [[TMP6:%.*]] = extractelement <2 x float> [[TMP2]], i32 1
+; CHECK-NEXT:    [[TMP7:%.*]] = insertelement <4 x float> [[TMP5]], float [[TMP6]], i32 1
+; CHECK-NEXT:    [[TMP8:%.*]] = shufflevector <2 x float> [[TMP4]], <2 x float> poison, <4 x i32> <i32 0, i32 1, i32 undef, i32 undef>
+; CHECK-NEXT:    [[TMP9:%.*]] = shufflevector <4 x float> [[TMP7]], <4 x float> [[TMP8]], <4 x i32> <i32 0, i32 1, i32 4, i32 5>
+; CHECK-NEXT:    [[TMP10:%.*]] = extractelement <2 x float> [[TMP2]], i32 0
+; CHECK-NEXT:    [[TMP11:%.*]] = insertelement <4 x float> poison, float [[TMP10]], i32 0
+; CHECK-NEXT:    [[TMP12:%.*]] = shufflevector <2 x float> [[TMP2]], <2 x float> poison, <4 x i32> <i32 0, i32 1, i32 undef, i32 undef>
+; CHECK-NEXT:    [[TMP13:%.*]] = shufflevector <4 x float> [[TMP11]], <4 x float> [[TMP12]], <4 x i32> <i32 0, i32 4, i32 5, i32 3>
+; CHECK-NEXT:    [[TMP14:%.*]] = extractelement <2 x float> [[TMP4]], i32 0
+; CHECK-NEXT:    [[TMP15:%.*]] = insertelement <4 x float> [[TMP13]], float [[TMP14]], i32 3
+; CHECK-NEXT:    [[TMP16:%.*]] = fmul fast <4 x float> [[TMP9]], [[TMP15]]
+; CHECK-NEXT:    [[TMP17:%.*]] = bitcast float* [[GEP0]] to <4 x float>*
+; CHECK-NEXT:    store <4 x float> [[TMP16]], <4 x float>* [[TMP17]], align 4
+; CHECK-NEXT:    ret void
+;
+  %gep0 = getelementptr inbounds float, float* %a, i64 0
+  %gep1 = getelementptr inbounds float, float* %a, i64 1
+  %gep2 = getelementptr inbounds float, float* %a, i64 2
+  %gep3 = getelementptr inbounds float, float* %a, i64 3
+  %gep4 = getelementptr inbounds float, float* %a, i64 4
+  %ld0 = load float, float* %gep0
+  %ld1 = load float, float* %gep1
+  %ld2 = load float, float* %gep2
+  %ld3 = load float, float* %gep3
+  %ld4 = load float, float* %gep4
+  %mul0 = fmul fast float %ld0, %ld1
+  %mul1 = fmul fast float %ld2, %ld1
+  %mul2 = fmul fast float %ld3, %ld2
+  %mul3 = fmul fast float %ld4, %ld3
+  store float %mul0, float* %gep0
+  store float %mul1, float* %gep1
+  store float %mul2, float* %gep2
+  store float %mul3, float* %gep3
+  ret void
+}
+
+