[SLP]Need shrink the load vector after reordering.

[ABataev]

Summary

After merging the shuffles, we cannot rely on the previous shuffle
anymore and need to shrink the final shuffle, if it is required.

Reported in D92668

[anton-afanasyev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

4266–4274

This comment is obsolete after change.

[ABataev]

Removed outdated comment.

[anton-afanasyev]

LGTM

[rupprecht]

I can confirm this fixes the non-reduced test case we're seeing internally, thanks!

[mstorsjo]

This caused misoptimizations for armv7, where code that previously worked correctly now produce different results. (The code is clean under ubsan, so it shouldn't be relying on anything undefined.)

The issue appears with https://martin.st/temp/interplayvideo-preproc.c, compiled with clang -target armv7-linux-gnueabihf -O2.

The diff in generated code, before/after, looks like this:

        vmov.32 d16[0], lr
        vmov.32 d16[1], r2
 .LBB27_3:                               @ %if.end
                                         @   in Loop: Header=BB27_4 Depth=1
        vmov.32 r2, d16[1]
        add     r3, r3, #1
        vmov.32 r5, d16[0]
        cmp     r3, #8
+       vdup.32 d16, d16[0]
        vmov.16 d17[1], r2
        vmov.16 d18[0], r5
        vdup.16 d21, d17[1]
        vdup.16 d20, d18[0]
        vst1.16 {d20, d21}, [r1], r12
        beq     .LBB27_9
 .LBB27_4:                               @ %for.body
                                         @ =>This Inner Loop Header: Depth=1
        tst     r3, #3
        bne     .LBB27_3

If it loops back to .LBB27_3, the vector element d16[1] no longer has the value it was expected to have.

[ABataev]

In D93967#2486129, @mstorsjo wrote:

This caused misoptimizations for armv7, where code that previously worked correctly now produce different results. (The code is clean under ubsan, so it shouldn't be relying on anything undefined.)

The issue appears with https://martin.st/temp/interplayvideo-preproc.c, compiled with clang -target armv7-linux-gnueabihf -O2.

The diff in generated code, before/after, looks like this:

        vmov.32 d16[0], lr
        vmov.32 d16[1], r2
 .LBB27_3:                               @ %if.end
                                         @   in Loop: Header=BB27_4 Depth=1
        vmov.32 r2, d16[1]
        add     r3, r3, #1
        vmov.32 r5, d16[0]
        cmp     r3, #8
+       vdup.32 d16, d16[0]
        vmov.16 d17[1], r2
        vmov.16 d18[0], r5
        vdup.16 d21, d17[1]
        vdup.16 d20, d18[0]
        vst1.16 {d20, d21}, [r1], r12
        beq     .LBB27_9
 .LBB27_4:                               @ %for.body
                                         @ =>This Inner Loop Header: Depth=1
        tst     r3, #3
        bne     .LBB27_3

If it loops back to .LBB27_3, the vector element d16[1] no longer has the value it was expected to have.

Hi, thanks for the report, the patch is correct, the bug is in the existing code. Will fix it soon.

[ABataev]

Bug fixes

[ABataev]

Bug fix.

[echristo]

If you changed the existing patch it won't be clear that this is something that needs review. Can you make a new review with the bug fix?

Thanks!

-eric

[ABataev]

In D93967#2496809, @echristo wrote:

If you changed the existing patch it won't be clear that this is something that needs review. Can you make a new review with the bug fix?

Thanks!

-eric

Did it, thanks!

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

 }
 
 Value *BoUpSLP::vectorizeTree(ArrayRef<Value *> VL) {
   InstructionsState S = getSameOpcode(VL);
   if (S.getOpcode()) {
     if (TreeEntry *E = getTreeEntry(S.OpValue)) {
       if (E->isSame(VL)) {
         Value *V = vectorizeTree(E);
         if (VL.size() == E->Scalars.size() && !E->ReuseShuffleIndices.empty()) {
-          // We need to get the vectorized value but without shuffle.
-          if (auto *SV = dyn_cast<ShuffleVectorInst>(V)) {
-            V = SV->getOperand(0);
-          } else {
-            // Reshuffle to get only unique values.
-            SmallVector<int, 4> UniqueIdxs;
-            SmallSet<int, 4> UsedIdxs;
-            for (int Idx : E->ReuseShuffleIndices)
-              if (UsedIdxs.insert(Idx).second)
-                UniqueIdxs.emplace_back(Idx);
-            V = Builder.CreateShuffleVector(V, UniqueIdxs);
+          int Pos = 0;
+          for (int Idx : E->ReuseShuffleIndices) {
+              UniqueIdxs.emplace_back(Pos);
+            ++Pos;
           }
+          V = Builder.CreateShuffleVector(V, UniqueIdxs, "shrink.shuffle");
         }
         return V;
       }
     }
   }
 
   // Check that every instruction appears once in this bundle.
   SmallVector<int, 4> ReuseShuffleIndicies;

llvm/test/Transforms/SLPVectorizer/X86/shrink_after_reorder.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -slp-vectorizer -S -o - -mtriple=x86_64-unknown-linux-gnu -mcpu=haswell < %s | FileCheck %s
 
 define void @wombat(i32* %ptr, i32* %ptr1) {
 ; CHECK-LABEL: @wombat(
 ; CHECK-NEXT:  bb:
 ; CHECK-NEXT:    [[TMP7:%.*]] = getelementptr inbounds i32, i32* [[PTR:%.*]], i64 1
 ; CHECK-NEXT:    [[TMP8:%.*]] = getelementptr inbounds i32, i32* [[PTR]], i64 0
 ; CHECK-NEXT:    [[TMP0:%.*]] = bitcast i32* [[TMP8]] to <2 x i32>*
 ; CHECK-NEXT:    [[TMP1:%.*]] = load <2 x i32>, <2 x i32>* [[TMP0]], align 8
 ; CHECK-NEXT:    [[SHUFFLE:%.*]] = shufflevector <2 x i32> [[TMP1]], <2 x i32> poison, <4 x i32> <i32 1, i32 0, i32 1, i32 0>
 ; CHECK-NEXT:    [[TMP27:%.*]] = getelementptr inbounds i32, i32* [[PTR1:%.*]], i32 3
-; CHECK-NEXT:    [[TMP2:%.*]] = add nsw <2 x i32> [[TMP1]], <i32 -1, i32 -1>
+; CHECK-NEXT:    [[SHRINK_SHUFFLE:%.*]] = shufflevector <4 x i32> [[SHUFFLE]], <4 x i32> poison, <2 x i32> <i32 0, i32 1>
+; CHECK-NEXT:    [[TMP2:%.*]] = add nsw <2 x i32> [[SHRINK_SHUFFLE]], <i32 -1, i32 -1>
 ; CHECK-NEXT:    [[SHUFFLE1:%.*]] = shufflevector <2 x i32> [[TMP2]], <2 x i32> poison, <4 x i32> <i32 0, i32 1, i32 0, i32 1>
 ; CHECK-NEXT:    [[TMP34:%.*]] = getelementptr inbounds i32, i32* [[PTR1]], i32 4
 ; CHECK-NEXT:    [[TMP40:%.*]] = getelementptr inbounds i32, i32* [[PTR1]], i32 5
 ; CHECK-NEXT:    [[TMP3:%.*]] = icmp sgt <4 x i32> [[SHUFFLE]], undef
 ; CHECK-NEXT:    [[TMP4:%.*]] = select <4 x i1> [[TMP3]], <4 x i32> undef, <4 x i32> [[SHUFFLE1]]
 ; CHECK-NEXT:    [[TMP5:%.*]] = select <4 x i1> zeroinitializer, <4 x i32> zeroinitializer, <4 x i32> [[TMP4]]
 ; CHECK-NEXT:    [[TMP46:%.*]] = getelementptr inbounds i32, i32* [[PTR1]], i32 6
 ; CHECK-NEXT:    [[TMP6:%.*]] = bitcast i32* [[TMP27]] to <4 x i32>*
bb:
   ret void
 }
 
 define internal i32 @ipvideo_decode_block_opcode_0xD_16() {
 ; CHECK-LABEL: @ipvideo_decode_block_opcode_0xD_16(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 ; CHECK:       for.body:
-; CHECK-NEXT:    [[TMP0:%.*]] = phi <2 x i16> [ undef, [[ENTRY:%.*]] ], [ [[TMP0]], [[IF_END:%.*]] ]
+; CHECK-NEXT:    [[TMP0:%.*]] = phi <2 x i16> [ undef, [[ENTRY:%.*]] ], [ [[SHRINK_SHUFFLE:%.*]], [[IF_END:%.*]] ]
 ; CHECK-NEXT:    [[SHUFFLE:%.*]] = shufflevector <2 x i16> [[TMP0]], <2 x i16> poison, <8 x i32> <i32 0, i32 0, i32 0, i32 0, i32 1, i32 1, i32 1, i32 1>
 ; CHECK-NEXT:    br label [[IF_END]]
 ; CHECK:       if.end:
 ; CHECK-NEXT:    [[ARRAYIDX11_1:%.*]] = getelementptr inbounds i16, i16* undef, i32 1
 ; CHECK-NEXT:    [[ARRAYIDX11_2:%.*]] = getelementptr inbounds i16, i16* undef, i32 2
 ; CHECK-NEXT:    [[ARRAYIDX11_3:%.*]] = getelementptr inbounds i16, i16* undef, i32 3
 ; CHECK-NEXT:    [[ARRAYIDX11_4:%.*]] = getelementptr inbounds i16, i16* undef, i32 4
 ; CHECK-NEXT:    [[ARRAYIDX11_5:%.*]] = getelementptr inbounds i16, i16* undef, i32 5
 ; CHECK-NEXT:    [[ARRAYIDX11_6:%.*]] = getelementptr inbounds i16, i16* undef, i32 6
 ; CHECK-NEXT:    [[ARRAYIDX11_7:%.*]] = getelementptr inbounds i16, i16* undef, i32 7
 ; CHECK-NEXT:    store <8 x i16> [[SHUFFLE]], <8 x i16>* undef, align 2
+; CHECK-NEXT:    [[SHRINK_SHUFFLE]] = shufflevector <8 x i16> [[SHUFFLE]], <8 x i16> poison, <2 x i32> <i32 0, i32 4>
 ; CHECK-NEXT:    br label [[FOR_BODY]]
 ;
 entry:
   br label %for.body
 
 for.body:                                         ; preds = %if.end, %entry
   %P.sroa.7.0 = phi i16 [ undef, %entry ], [ %P.sroa.7.0, %if.end ]
   %P.sroa.0.0 = phi i16 [ undef, %entry ], [ %P.sroa.0.0, %if.end ]