Page MenuHomePhabricator

[SLP]Improve reordering for the nodes beeing used in alternate vectorization.
ClosedPublic

Authored by ABataev on Jan 6 2022, 6:43 AM.

Details

Summary

No need to include the order of the scalars beeing used as part of the
alternate vectorization into account when trying to reorder the whole
graph. Such elements better to reorder in the following phase because
the subtree still ends up in shuffle.

Part of D116688, fixes the regression in D116690.

Diff Detail

Event Timeline

ABataev created this revision.Jan 6 2022, 6:43 AM
ABataev requested review of this revision.Jan 6 2022, 6:43 AM
Herald added a project: Restricted Project. · View Herald TranscriptJan 6 2022, 6:43 AM
vporpo accepted this revision.Jan 6 2022, 10:23 AM

LGTM

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp
3053

Please explain in the comment why this is better.

This revision is now accepted and ready to land.Jan 6 2022, 10:23 AM

I have a question wrt this patch. Consider this test case:
define dso_local void @test(i32* noalias nocapture readonly %0, i32* noalias nocapture readonly %1, i32* noalias nocapture %2) {

%4 = getelementptr inbounds i32, i32* %1, i64 0
%5 = load i32, i32* %4, align 4
%6 = getelementptr inbounds i32, i32* %0, i64 0
%7 = load i32, i32* %6, align 4
%8 = getelementptr inbounds i32, i32* %1, i64 4
%9 = load i32, i32* %8, align 4
%10 = getelementptr inbounds i32, i32* %0, i64 4
%11 = load i32, i32* %10, align 4
%12 = getelementptr inbounds i32, i32* %1, i64 1
%13 = load i32, i32* %12, align 4
%14 = getelementptr inbounds i32, i32* %0, i64 1
%15 = load i32, i32* %14, align 4
%16 = getelementptr inbounds i32, i32* %1, i64 5
%17 = load i32, i32* %16, align 4
%18 = getelementptr inbounds i32, i32* %0, i64 5
%19 = load i32, i32* %18, align 4
%20 = getelementptr inbounds i32, i32* %1, i64 2
%21 = load i32, i32* %20, align 4
%22 = getelementptr inbounds i32, i32* %0, i64 2
%23 = load i32, i32* %22, align 4
%24 = getelementptr inbounds i32, i32* %1, i64 6
%25 = load i32, i32* %24, align 4
%26 = getelementptr inbounds i32, i32* %0, i64 6
%27 = load i32, i32* %26, align 4
%28 = getelementptr inbounds i32, i32* %1, i64 3
%29 = load i32, i32* %28, align 4
%30 = getelementptr inbounds i32, i32* %0, i64 3
%31 = load i32, i32* %30, align 4
%32 = getelementptr inbounds i32, i32* %1, i64 7
%33 = load i32, i32* %32, align 4
%34 = getelementptr inbounds i32, i32* %0, i64 7
%35 = load i32, i32* %34, align 4
%36 = sub i32 %33, %31
%37 = sub i32 %36, %35
%38 = add i32 %37, %29
%39 = sub i32 %25, %23
%40 = sub i32 %39, %27
%41 = add i32 %40, %21
%42 = sub i32 %17, %15
%43 = sub i32 %42, %19
%44 = add i32 %43, %13
%45 = sub i32 %9, %7
%46 = sub i32 %45, %11
%47 = add i32 %46, %5
%48 = getelementptr inbounds i32, i32* %2, i64 0
%49 = add i32 %41, %38
%50 = add i32 %49, %47
%51 = add i32 %50, %44
store i32 %51, i32* %48, align 4
%52 = getelementptr inbounds i32, i32* %2, i64 2
%53 = add i32 %47, %44
%54 = sub i32 %53, %38
%55 = sub i32 %54, %41
store i32 %55, i32* %52, align 4
%56 = getelementptr inbounds i32, i32* %2, i64 1
%57 = add i32 %47, %41
%58 = sub i32 %57, %44
%59 = sub i32 %58, %38
store i32 %59, i32* %56, align 4
%60 = getelementptr inbounds i32, i32* %2, i64 3
%61 = sub i32 %38, %44
%62 = sub i32 %61, %41
%63 = add i32 %62, %47
store i32 %63, i32* %60, align 4
ret void

}

opt -slp-vectorizer -dce -mtriple=x86_64-unknown-linux-gnu -mattr=+avx -S

After the patch SLP produced more shufflevector instructions then before:

%9 = load <4 x i32>, <4 x i32>* %8, align 4
%shuffle2 = shufflevector <4 x i32> %9, <4 x i32> poison, <4 x i32> <i32 2, i32 0, i32 1, i32 3>
%10 = bitcast i32* %5 to <4 x i32>*
%11 = load <4 x i32>, <4 x i32>* %10, align 4
%12 = bitcast i32* %6 to <4 x i32>*
%13 = load <4 x i32>, <4 x i32>* %12, align 4
%14 = bitcast i32* %7 to <4 x i32>*
%15 = load <4 x i32>, <4 x i32>* %14, align 4
%shuffle1 = shufflevector <4 x i32> %15, <4 x i32> poison, <4 x i32> <i32 2, i32 0, i32 1, i32 3>
%16 = sub <4 x i32> %13, %11
%shuffle = shufflevector <4 x i32> %16, <4 x i32> poison, <4 x i32> <i32 2, i32 0, i32 1, i32 3>
%17 = sub <4 x i32> %shuffle, %shuffle1
%18 = add <4 x i32> %17, %shuffle2

instcombine pass then optimizes these shuffles but the question is whether SLP should rely on that? Is it expected or considered as a regression in SLP vectorizer?

I have a question wrt this patch. Consider this test case:
define dso_local void @test(i32* noalias nocapture readonly %0, i32* noalias nocapture readonly %1, i32* noalias nocapture %2) {

%4 = getelementptr inbounds i32, i32* %1, i64 0
%5 = load i32, i32* %4, align 4
%6 = getelementptr inbounds i32, i32* %0, i64 0
%7 = load i32, i32* %6, align 4
%8 = getelementptr inbounds i32, i32* %1, i64 4
%9 = load i32, i32* %8, align 4
%10 = getelementptr inbounds i32, i32* %0, i64 4
%11 = load i32, i32* %10, align 4
%12 = getelementptr inbounds i32, i32* %1, i64 1
%13 = load i32, i32* %12, align 4
%14 = getelementptr inbounds i32, i32* %0, i64 1
%15 = load i32, i32* %14, align 4
%16 = getelementptr inbounds i32, i32* %1, i64 5
%17 = load i32, i32* %16, align 4
%18 = getelementptr inbounds i32, i32* %0, i64 5
%19 = load i32, i32* %18, align 4
%20 = getelementptr inbounds i32, i32* %1, i64 2
%21 = load i32, i32* %20, align 4
%22 = getelementptr inbounds i32, i32* %0, i64 2
%23 = load i32, i32* %22, align 4
%24 = getelementptr inbounds i32, i32* %1, i64 6
%25 = load i32, i32* %24, align 4
%26 = getelementptr inbounds i32, i32* %0, i64 6
%27 = load i32, i32* %26, align 4
%28 = getelementptr inbounds i32, i32* %1, i64 3
%29 = load i32, i32* %28, align 4
%30 = getelementptr inbounds i32, i32* %0, i64 3
%31 = load i32, i32* %30, align 4
%32 = getelementptr inbounds i32, i32* %1, i64 7
%33 = load i32, i32* %32, align 4
%34 = getelementptr inbounds i32, i32* %0, i64 7
%35 = load i32, i32* %34, align 4
%36 = sub i32 %33, %31
%37 = sub i32 %36, %35
%38 = add i32 %37, %29
%39 = sub i32 %25, %23
%40 = sub i32 %39, %27
%41 = add i32 %40, %21
%42 = sub i32 %17, %15
%43 = sub i32 %42, %19
%44 = add i32 %43, %13
%45 = sub i32 %9, %7
%46 = sub i32 %45, %11
%47 = add i32 %46, %5
%48 = getelementptr inbounds i32, i32* %2, i64 0
%49 = add i32 %41, %38
%50 = add i32 %49, %47
%51 = add i32 %50, %44
store i32 %51, i32* %48, align 4
%52 = getelementptr inbounds i32, i32* %2, i64 2
%53 = add i32 %47, %44
%54 = sub i32 %53, %38
%55 = sub i32 %54, %41
store i32 %55, i32* %52, align 4
%56 = getelementptr inbounds i32, i32* %2, i64 1
%57 = add i32 %47, %41
%58 = sub i32 %57, %44
%59 = sub i32 %58, %38
store i32 %59, i32* %56, align 4
%60 = getelementptr inbounds i32, i32* %2, i64 3
%61 = sub i32 %38, %44
%62 = sub i32 %61, %41
%63 = add i32 %62, %47
store i32 %63, i32* %60, align 4
ret void

}

opt -slp-vectorizer -dce -mtriple=x86_64-unknown-linux-gnu -mattr=+avx -S

After the patch SLP produced more shufflevector instructions then before:

%9 = load <4 x i32>, <4 x i32>* %8, align 4
%shuffle2 = shufflevector <4 x i32> %9, <4 x i32> poison, <4 x i32> <i32 2, i32 0, i32 1, i32 3>
%10 = bitcast i32* %5 to <4 x i32>*
%11 = load <4 x i32>, <4 x i32>* %10, align 4
%12 = bitcast i32* %6 to <4 x i32>*
%13 = load <4 x i32>, <4 x i32>* %12, align 4
%14 = bitcast i32* %7 to <4 x i32>*
%15 = load <4 x i32>, <4 x i32>* %14, align 4
%shuffle1 = shufflevector <4 x i32> %15, <4 x i32> poison, <4 x i32> <i32 2, i32 0, i32 1, i32 3>
%16 = sub <4 x i32> %13, %11
%shuffle = shufflevector <4 x i32> %16, <4 x i32> poison, <4 x i32> <i32 2, i32 0, i32 1, i32 3>
%17 = sub <4 x i32> %shuffle, %shuffle1
%18 = add <4 x i32> %17, %shuffle2

instcombine pass then optimizes these shuffles but the question is whether SLP should rely on that? Is it expected or considered as a regression in SLP vectorizer?

No, it is a regression, need to investigate it.

I believe https://reviews.llvm.org/D120492 supposed to fix the issue I reported earlier, but that did not happen. The test I've sent earlier is a simplified one. I just slightly modified it to show misbehaving of the reordering.

This is okay:
define void @test(i32* %arg, i32* %arg1, i32* %arg2) {
bb:

%i3 = load i32, i32* %arg, align 4
%s3 = add i32 %i3, %i3
%i4 = getelementptr inbounds i32, i32* %arg, i64 4
%i5 = load i32, i32* %i4, align 4
%s5 = add i32 %i5, %i5
%i8 = getelementptr inbounds i32, i32* %arg, i64 1
%i9 = load i32, i32* %i8, align 4
%s9 = add i32 %i9, %i9
%i10 = getelementptr inbounds i32, i32* %arg, i64 5
%i11 = load i32, i32* %i10, align 4
%s11 = add i32 %i11, %i11
%i14 = getelementptr inbounds i32, i32* %arg, i64 2
%i15 = load i32, i32* %i14, align 4
%s15 = add i32 %i15, %i15
%i16 = getelementptr inbounds i32, i32* %arg, i64 6
%i17 = load i32, i32* %i16, align 4
%s17 = add i32 %i17, %i17
%i20 = getelementptr inbounds i32, i32* %arg, i64 3
%i21 = load i32, i32* %i20, align 4
%s21 = add i32 %i21, %i21
%i22 = getelementptr inbounds i32, i32* %arg, i64 7
%i23 = load i32, i32* %i22, align 4
%s23 = add i32 %i23, %i23

%i1 = load i32, i32* %arg1, align 4
%i6 = getelementptr inbounds i32, i32* %arg1, i64 1
%i7 = load i32, i32* %i6, align 4
%i12 = getelementptr inbounds i32, i32* %arg1, i64 2
%i13 = load i32, i32* %i12, align 4
%i18 = getelementptr inbounds i32, i32* %arg1, i64 3
%i19 = load i32, i32* %i18, align 4

%i24 = sub i32 0, %s21
%i25 = sub i32 %i24, %s23
%i26 = add i32 %i25, %i19
%i27 = sub i32 undef, %s15
%i28 = sub i32 %i27, %s17
%i29 = add i32 %i28, %i13
%i30 = sub i32 0, %s9
%i31 = sub i32 %i30, %s11
%i32 = add i32 %i31, %i7
%i33 = sub i32 0, %s3
%i34 = sub i32 %i33, %s5
%i35 = add i32 %i34, %i1
%i36 = add i32 %i29, 1
%i37 = add i32 %i36, 0
%i38 = add i32 %i37, 0
store i32 %i38, i32* %arg2, align 4
%i39 = getelementptr inbounds i32, i32* %arg2, i64 2
%i40 = add i32 0, %i32
%i41 = sub i32 %i40, 0
%i42 = sub i32 %i41, 0
store i32 %i42, i32* %i39, align 4
%i43 = getelementptr inbounds i32, i32* %arg2, i64 1
%i44 = add i32 %i35, 0
%i45 = sub i32 %i44, 0
%i46 = sub i32 %i45, 0
store i32 %i46, i32* %i43, align 4
%i47 = getelementptr inbounds i32, i32* %arg2, i64 3
%i48 = sub i32 %i26, 0
%i49 = sub i32 %i48, 0
%i50 = add i32 %i49, 0
store i32 %i50, i32* %i47, align 4
ret void

}

merely because of this if statement:

if (UserTE->UserTreeIndices.size() != 1)
  break;

effectively returning to behavior prior to the patch.

But this test still produce all these extra shuffles:
define void @test(i32* %arg, i32* %arg1, i32* %arg2) {
bb:

%i3 = load i32, i32* %arg, align 4
%s3 = add i32 %i3, 6
%i4 = getelementptr inbounds i32, i32* %arg, i64 4
%i5 = load i32, i32* %i4, align 4
%s5 = add i32 %i5, 6
%i8 = getelementptr inbounds i32, i32* %arg, i64 1
%i9 = load i32, i32* %i8, align 4
%s9 = add i32 %i9, 6
%i10 = getelementptr inbounds i32, i32* %arg, i64 5
%i11 = load i32, i32* %i10, align 4
%s11 = add i32 %i11, 6
%i14 = getelementptr inbounds i32, i32* %arg, i64 2
%i15 = load i32, i32* %i14, align 4
%s15 = add i32 %i15, 6
%i16 = getelementptr inbounds i32, i32* %arg, i64 6
%i17 = load i32, i32* %i16, align 4
%s17 = add i32 %i17, 6
%i20 = getelementptr inbounds i32, i32* %arg, i64 3
%i21 = load i32, i32* %i20, align 4
%s21 = add i32 %i21, 6
%i22 = getelementptr inbounds i32, i32* %arg, i64 7
%i23 = load i32, i32* %i22, align 4
%s23 = add i32 %i23, 6

%i1 = load i32, i32* %arg1, align 4
%i6 = getelementptr inbounds i32, i32* %arg1, i64 1
%i7 = load i32, i32* %i6, align 4
%i12 = getelementptr inbounds i32, i32* %arg1, i64 2
%i13 = load i32, i32* %i12, align 4
%i18 = getelementptr inbounds i32, i32* %arg1, i64 3
%i19 = load i32, i32* %i18, align 4

%i24 = sub i32 0, %s21
%i25 = sub i32 %i24, %s23
%i26 = add i32 %i25, %i19
%i27 = sub i32 undef, %s15
%i28 = sub i32 %i27, %s17
%i29 = add i32 %i28, %i13
%i30 = sub i32 0, %s9
%i31 = sub i32 %i30, %s11
%i32 = add i32 %i31, %i7
%i33 = sub i32 0, %s3
%i34 = sub i32 %i33, %s5
%i35 = add i32 %i34, %i1
%i36 = add i32 %i29, 1
%i37 = add i32 %i36, 0
%i38 = add i32 %i37, 0
store i32 %i38, i32* %arg2, align 4
%i39 = getelementptr inbounds i32, i32* %arg2, i64 2
%i40 = add i32 0, %i32
%i41 = sub i32 %i40, 0
%i42 = sub i32 %i41, 0
store i32 %i42, i32* %i39, align 4
%i43 = getelementptr inbounds i32, i32* %arg2, i64 1
%i44 = add i32 %i35, 0
%i45 = sub i32 %i44, 0
%i46 = sub i32 %i45, 0
store i32 %i46, i32* %i43, align 4
%i47 = getelementptr inbounds i32, i32* %arg2, i64 3
%i48 = sub i32 %i26, 0
%i49 = sub i32 %i48, 0
%i50 = add i32 %i49, 0
store i32 %i50, i32* %i47, align 4
ret void

}

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp
3069

this condition is always false because if UserTE->UserTreeIndices.size() != 1 we exit loop at 3067

Herald added a project: Restricted Project. · View Herald TranscriptApr 1 2022, 3:18 PM
vdmitrie added inline comments.Apr 1 2022, 4:53 PM
llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp
3236–3241

Problem is seems to be here when VL is all constants. Operands are still can be reordered with no extra cost.