[SLP]Need to 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.

The previous patch in D93967 was reverted because the original code had a bug. This patch fixes it.

[echristo]

Is the summary correct? The patch that this is fixing isn't reverted...

It's not clear what this is fixing and why it's fixing it.

Thanks!

-eric

[ABataev]

In D94972#2507235, @echristo wrote:

Is the summary correct? The patch that this is fixing isn't reverted...

It's not clear what this is fixing and why it's fixing it.

Thanks!

-eric

Here is the reverting commit https://reviews.llvm.org/rGbcbdeafa9cb3469a7bf367c17f32d913076a4d55

Before D92668, we could reuse the argument of the shuffle as the instruction and in most cases, we did this. And it masked the issue that exists in the code for the case when there is no shuffle after vectorization of the node. After D92668 we could not reuse the argument of the shuffle anymore and should resize the vectorized instructions always if required. But originally we did it incorrectly. If some of the scalars are duplicated in the vectorization tree entry, we do not vectorize them but instead generate a mask for the reuses. But if there are several users of the same entry, they may have different vectorization factors. This is especially important for PHI nodes. In this case, we need to adapt the resulting instruction for the user vectorization factor and have to reshuffle it again to take only unique elements of the vector. Before this patch, the compiler incorrectly returned reduced vector instruction with the same elements, not with the unique ones.

block:
%phi = phi <2 x > { .., %entry} {%shuffle, %block}
%2 = shuffle <2 x > %phi, %poison, <4 x > <0, 0, 1, 1>
... (use %2)
%shuffle = shuffle <2 x> %2, poison, <2 x> {0, 2} <----------------- Currently the compiler emits {0, 1} here but insteasd it should be {0, 2}, otherwise %2 instruction becomes incorrect after the first iteration
br %block

[echristo]

I think this would be more clear as a combined patch rather than 3 separate and some reverted patches. Would it make more sense to revert the chain and put them all back together in a single review?

[ABataev]

In D94972#2507344, @echristo wrote:

I think this would be more clear as a combined patch rather than 3 separate and some reverted patches. Would it make more sense to revert the chain and put them all back together in a single review?

There is no chain, actually. And the patch, that caused the problem, is not directly related.
D92668 just improves the cost model by squashing multiple shuffles. This one fixes the issue in the code that existed even before D92668 and D92668 just revealed it.

[echristo]

Hard to tell because there aren't any comments around any of the code that changed in either patch. Can you fix that in a separate change and actually document what everything is doing? :)

For this patch can you add a comment that explains what we're doing here as well. It's unclear.

[ABataev]

In D94972#2507385, @echristo wrote:

Hard to tell because there aren't any comments around any of the code that changed in either patch. Can you fix that in a separate change and actually document what everything is doing? :)

This is a separate patch with the fix only. :) There are no more patches required to fix the issue, just this one. Or do you mean something else?

For this patch can you add a comment that explains what we're doing here as well. It's unclear.

Sure.

[echristo]

In D94972#2507400, @ABataev wrote:

In D94972#2507385, @echristo wrote:

Hard to tell because there aren't any comments around any of the code that changed in either patch. Can you fix that in a separate change and actually document what everything is doing? :)

This is a separate patch with the fix only. :) There are no more patches required to fix the issue, just this one. Or do you mean something else?

The previous patch.. and yeah, I know it's not your fault some of this could be better documented and thanks for fixing it up :)

For this patch can you add a comment that explains what we're doing here as well. It's unclear.

Sure.

Thanks!

-eric

[echristo]

Hmm?

[ABataev]

In D94972#2507666, @echristo wrote:

Hmm?

I just reverted the original patch for shuffles and going to merge this patch and the patch for shuffles. Going to post it soon.

[echristo]

Awesome. 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 ]