[SLP]Try to emit canonical shuffle with undef operand.

[ABataev]

Summary

In the canonical form of the shuffle the poison/undef operand is the
second operand, the patch tries to emit canonical form for partial
vectorization of the buildvector sequence.
Also, this patch starts emitting freeze instruction for shuffles with undef indices if the second shuffle operan is undef, not poison. It is an initial step to D93818, where undef mask element are treated as returning poison value.

[ABataev]

Rebase

[ABataev]

Ping!

[vdmitrie]

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

15

I'm not sure I understand well why freeze is generated here. I likely missed something but the LangRef says:
"If the shuffle mask is undefined, the result vector is undefined. If the shuffle mask selects an undefined element from one of the input vectors, the resulting element is undefined. An undefined element in the mask vector specifies that the resulting element is undefined. An undefined element in the mask vector prevents a poisoned vector element from propagating."
So here the first two lanes of VECINS_I_5_I1 are taken from TMP6, all the rest is undef. The for TMP6 the first two lanes taken from TMP5, all the rest of TM5 is undef, TMP5 is a bitcast of TMP4, both lines of which are normal values. It means that all lanes of VECINS_I_5_I1 are either normal values or undef. So why freeze is here?

It would be nice if you extend patch description with some information about what is deemed to be a canonical form of a shuffle.

[ABataev]

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

15

It is going to be changed soon to be poisoned instead of undefined.

[vdmitrie]

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

15

Ah, okay. Hence there must be a discussion about that somewhere. Can you please point out to the discussion?

Since this is yet anticipated change the patch description should definitely be more detailed.

[ABataev]

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

15

https://reviews.llvm.org/D93818

[ABataev]

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

15

Done

[vdmitrie]

Thank you, Alexey. Looks good.

[dyung]

Hi @ABataev, we have an internal test where this seemed to cause the codegen for a horizontal add test to get worse (I think) after your change. I have filed the issue as #58177, can you take a look?

[ABataev]

In D134377#3838960, @dyung wrote:

Hi @ABataev, we have an internal test where this seemed to cause the codegen for a horizontal add test to get worse (I think) after your change. I have filed the issue as #58177, can you take a look?

Looks like need to add the analysis of freeze instructions to the shuffles emission/cost estimation function, will do it later today.

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

case Instruction::InsertElement: {
           GatherShuffleSeq.insert(I);
           CSEBlocks.insert(I->getParent());
         }
       }
 
       SmallVector<int> InsertMask(NumElts, UndefMaskElem);
       for (unsigned I = 0; I < NumElts; I++) {
         if (Mask[I] != UndefMaskElem)
-          InsertMask[Offset + I] = NumElts + I;
+          InsertMask[Offset + I] = I;
       }
-      if (Offset != 0 ||
-          !isUndefVector(FirstInsert->getOperand(0), InsertMask)) {
+      bool IsFirstUndef = isUndefVector(FirstInsert->getOperand(0), InsertMask);
+      if ((!IsIdentity || Offset != 0 || !IsFirstUndef) &&
+          NumElts != NumScalars) {
+        if (IsFirstUndef) {
+          if (!ShuffleVectorInst::isIdentityMask(InsertMask)) {
+            V = Builder.CreateShuffleVector(
+                V, InsertMask, cast<Instruction>(E->Scalars.back())->getName());
+            if (auto *I = dyn_cast<Instruction>(V)) {
+              GatherShuffleSeq.insert(I);
+              CSEBlocks.insert(I->getParent());
+            }
+            // Create freeze for undef values.
+            if (!isa<PoisonValue>(FirstInsert->getOperand(0)))
+              V = Builder.CreateFreeze(V);
+          }
+        } else {
           for (unsigned I = 0; I < NumElts; I++) {
             if (InsertMask[I] == UndefMaskElem)
               InsertMask[I] = I;
+            else
+              InsertMask[I] += NumElts;
           }
-
           V = Builder.CreateShuffleVector(
               FirstInsert->getOperand(0), V, InsertMask,
               cast<Instruction>(E->Scalars.back())->getName());
           if (auto *I = dyn_cast<Instruction>(V)) {
             GatherShuffleSeq.insert(I);
             CSEBlocks.insert(I->getParent());
           }
         }
+      }
 
       ++NumVectorInstructions;
       E->VectorizedValue = V;
       return V;
     }
     case Instruction::ZExt:
     case Instruction::SExt:
     case Instruction::FPToUI:

llvm/test/Transforms/SLPVectorizer/X86/PR35865-inseltpoison.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -slp-vectorizer < %s -S -o - -mtriple=x86_64-apple-macosx10.10.0 -mcpu=core2 | FileCheck %s
 
 define void @_Z10fooConvertPDv4_xS0_S0_PKS_() {
 ; CHECK-LABEL: @_Z10fooConvertPDv4_xS0_S0_PKS_(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TMP0:%.*]] = extractelement <16 x half> undef, i32 4
 ; CHECK-NEXT:    [[TMP1:%.*]] = extractelement <16 x half> undef, i32 5
 ; CHECK-NEXT:    [[TMP2:%.*]] = insertelement <2 x half> poison, half [[TMP0]], i32 0
 ; CHECK-NEXT:    [[TMP3:%.*]] = insertelement <2 x half> [[TMP2]], half [[TMP1]], i32 1
 ; CHECK-NEXT:    [[TMP4:%.*]] = fpext <2 x half> [[TMP3]] to <2 x float>
 ; CHECK-NEXT:    [[TMP5:%.*]] = bitcast <2 x float> [[TMP4]] to <2 x i32>
 ; CHECK-NEXT:    [[TMP6:%.*]] = shufflevector <2 x i32> [[TMP5]], <2 x i32> poison, <8 x i32> <i32 0, i32 1, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef>
-; CHECK-NEXT:    [[VECINS_I_5_I1:%.*]] = shufflevector <8 x i32> poison, <8 x i32> [[TMP6]], <8 x i32> <i32 0, i32 1, i32 2, i32 3, i32 8, i32 9, i32 6, i32 7>
+; CHECK-NEXT:    [[VECINS_I_5_I1:%.*]] = shufflevector <8 x i32> [[TMP6]], <8 x i32> poison, <8 x i32> <i32 undef, i32 undef, i32 undef, i32 undef, i32 0, i32 1, i32 undef, i32 undef>
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %0 = extractelement <16 x half> undef, i32 4
   %conv.i.4.i = fpext half %0 to float
   %1 = bitcast float %conv.i.4.i to i32
   %vecins.i.4.i = insertelement <8 x i32> poison, i32 %1, i32 4
   %2 = extractelement <16 x half> undef, i32 5
   %conv.i.5.i = fpext half %2 to float
   %3 = bitcast float %conv.i.5.i to i32
   %vecins.i.5.i = insertelement <8 x i32> %vecins.i.4.i, i32 %3, i32 5
   ret void
 }

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

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -slp-vectorizer < %s -S -o - -mtriple=x86_64-apple-macosx10.10.0 -mcpu=core2 | FileCheck %s
 
 define void @_Z10fooConvertPDv4_xS0_S0_PKS_() {
 ; CHECK-LABEL: @_Z10fooConvertPDv4_xS0_S0_PKS_(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TMP0:%.*]] = extractelement <16 x half> undef, i32 4
 ; CHECK-NEXT:    [[TMP1:%.*]] = extractelement <16 x half> undef, i32 5
 ; CHECK-NEXT:    [[TMP2:%.*]] = insertelement <2 x half> poison, half [[TMP0]], i32 0
 ; CHECK-NEXT:    [[TMP3:%.*]] = insertelement <2 x half> [[TMP2]], half [[TMP1]], i32 1
 ; CHECK-NEXT:    [[TMP4:%.*]] = fpext <2 x half> [[TMP3]] to <2 x float>
 ; CHECK-NEXT:    [[TMP5:%.*]] = bitcast <2 x float> [[TMP4]] to <2 x i32>
 ; CHECK-NEXT:    [[TMP6:%.*]] = shufflevector <2 x i32> [[TMP5]], <2 x i32> poison, <8 x i32> <i32 0, i32 1, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef>
-; CHECK-NEXT:    [[VECINS_I_5_I1:%.*]] = shufflevector <8 x i32> undef, <8 x i32> [[TMP6]], <8 x i32> <i32 0, i32 1, i32 2, i32 3, i32 8, i32 9, i32 6, i32 7>
+; CHECK-NEXT:    [[VECINS_I_5_I1:%.*]] = shufflevector <8 x i32> [[TMP6]], <8 x i32> poison, <8 x i32> <i32 undef, i32 undef, i32 undef, i32 undef, i32 0, i32 1, i32 undef, i32 undef>
+; CHECK-NEXT:    [[TMP7:%.*]] = freeze <8 x i32> [[VECINS_I_5_I1]]
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %0 = extractelement <16 x half> undef, i32 4
   %conv.i.4.i = fpext half %0 to float
   %1 = bitcast float %conv.i.4.i to i32
   %vecins.i.4.i = insertelement <8 x i32> undef, i32 %1, i32 4
   %2 = extractelement <16 x half> undef, i32 5
   %conv.i.5.i = fpext half %2 to float
   %3 = bitcast float %conv.i.5.i to i32
   %vecins.i.5.i = insertelement <8 x i32> %vecins.i.4.i, i32 %3, i32 5
   ret void
 }

llvm/test/Transforms/SLPVectorizer/X86/insert-element-build-vector-inseltpoison.ll

 ; CHECK-NEXT:    [[TMP11:%.*]] = icmp ne <2 x i32> [[TMP10]], zeroinitializer
 ; CHECK-NEXT:    [[TMP12:%.*]] = insertelement <2 x float> poison, float [[A2]], i32 0
 ; CHECK-NEXT:    [[TMP13:%.*]] = insertelement <2 x float> [[TMP12]], float [[A3]], i32 1
 ; CHECK-NEXT:    [[TMP14:%.*]] = insertelement <2 x float> poison, float [[B2]], i32 0
 ; CHECK-NEXT:    [[TMP15:%.*]] = insertelement <2 x float> [[TMP14]], float [[B3]], i32 1
 ; CHECK-NEXT:    [[TMP16:%.*]] = select <2 x i1> [[TMP11]], <2 x float> [[TMP13]], <2 x float> [[TMP15]]
 ; CHECK-NEXT:    [[TMP17:%.*]] = shufflevector <2 x float> [[TMP8]], <2 x float> poison, <4 x i32> <i32 0, i32 1, i32 undef, i32 undef>
 ; CHECK-NEXT:    [[TMP18:%.*]] = shufflevector <2 x float> [[TMP16]], <2 x float> poison, <4 x i32> <i32 0, i32 1, i32 undef, i32 undef>
-; CHECK-NEXT:    [[RD1:%.*]] = shufflevector <4 x float> poison, <4 x float> [[TMP18]], <4 x i32> <i32 0, i32 1, i32 4, i32 5>
+; CHECK-NEXT:    [[RD1:%.*]] = shufflevector <4 x float> [[TMP18]], <4 x float> poison, <4 x i32> <i32 undef, i32 undef, i32 0, i32 1>
 ; CHECK-NEXT:    ret <4 x float> [[RD1]]
 ;
   %c0 = extractelement <4 x i32> %c, i32 0
   %c1 = extractelement <4 x i32> %c, i32 1
   %c2 = extractelement <4 x i32> %c, i32 2
   %c3 = extractelement <4 x i32> %c, i32 3
   %a0 = extractelement <4 x float> %a, i32 0
   %a1 = extractelement <4 x float> %a, i32 1

llvm/test/Transforms/SLPVectorizer/X86/insert-element-build-vector.ll

 ; CHECK-NEXT:    [[TMP11:%.*]] = icmp ne <2 x i32> [[TMP10]], zeroinitializer
 ; CHECK-NEXT:    [[TMP12:%.*]] = insertelement <2 x float> poison, float [[A2]], i32 0
 ; CHECK-NEXT:    [[TMP13:%.*]] = insertelement <2 x float> [[TMP12]], float [[A3]], i32 1
 ; CHECK-NEXT:    [[TMP14:%.*]] = insertelement <2 x float> poison, float [[B2]], i32 0
 ; CHECK-NEXT:    [[TMP15:%.*]] = insertelement <2 x float> [[TMP14]], float [[B3]], i32 1
 ; CHECK-NEXT:    [[TMP16:%.*]] = select <2 x i1> [[TMP11]], <2 x float> [[TMP13]], <2 x float> [[TMP15]]
 ; CHECK-NEXT:    [[TMP17:%.*]] = shufflevector <2 x float> [[TMP8]], <2 x float> poison, <4 x i32> <i32 0, i32 1, i32 undef, i32 undef>
 ; CHECK-NEXT:    [[TMP18:%.*]] = shufflevector <2 x float> [[TMP16]], <2 x float> poison, <4 x i32> <i32 0, i32 1, i32 undef, i32 undef>
-; CHECK-NEXT:    [[RD1:%.*]] = shufflevector <4 x float> undef, <4 x float> [[TMP18]], <4 x i32> <i32 0, i32 1, i32 4, i32 5>
-; CHECK-NEXT:    ret <4 x float> [[RD1]]
+; CHECK-NEXT:    [[RD1:%.*]] = shufflevector <4 x float> [[TMP18]], <4 x float> poison, <4 x i32> <i32 undef, i32 undef, i32 0, i32 1>
+; CHECK-NEXT:    [[TMP19:%.*]] = freeze <4 x float> [[RD1]]
+; CHECK-NEXT:    ret <4 x float> [[TMP19]]
 ;
   %c0 = extractelement <4 x i32> %c, i32 0
   %c1 = extractelement <4 x i32> %c, i32 1
   %c2 = extractelement <4 x i32> %c, i32 2
   %c3 = extractelement <4 x i32> %c, i32 3
   %a0 = extractelement <4 x float> %a, i32 0
   %a1 = extractelement <4 x float> %a, i32 1
   %a2 = extractelement <4 x float> %a, i32 2