[SLP] Fix "gathering" of vector values

[anton-afanasyev]

Summary

For rare exceptional case vector tree node (insertelements for now only)
is marked as NeedToGather, this case is processed by patch. Follow-up
of D98714 to fix bug reported here https://reviews.llvm.org/D98714#2764135.

[xbolva00]

Add testcase?

[anton-afanasyev]

Add testcase (command crashed before)

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

3693–3695

Not sure we should return 0 here, maybe better to return some max cost, like INT_MAX?

4597–4599

Is this correct? Need to return the last insertelement instruction in the sequence

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

45–80

Why the check lines are removed?

[anton-afanasyev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

3693–3695

There is no difference for now (the only one is compile time). We could also just prohibit marking NeedToGather for vector node (it could be done while checking for ephemeral values only).

But I've done it this way since it looks more transparent and also we could use zero cost for the future cases when/if such NeedToGather vector node is not the only member of tree and whole tree vectorization is beneficial.

4597–4599

Sure, fixed!

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

45–80

Fixed

[anton-afanasyev]

Address comments

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

3693–3695

I think it is better to use TTI::TCC_Expensive to mark it explicitly as an expensive operation. Or even invalid cost, if possible.

[anton-afanasyev]

Address comment

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

3693–3695

Ok, used Invalid cost.
Deleted gathering code, since gathering isn't supposed now.

[ABataev]

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

148–155

Why are the instructions reordered if no vectorization should happen?

[anton-afanasyev]

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

148–155

Vectorization of inserts is prohibited now, yes, but compiler still "vectorizes" small trees of size 1 with any valid cost due to options -slp-threshold=-10000 -slp-min-tree-size=0. This is not related to this patch itself.

[ABataev]

LG

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

InstructionCost BoUpSLP::getEntryCost(const TreeEntry *E) {
   if (E->State == TreeEntry::NeedToGather) {
     if (allConstant(VL))
       return 0;
     if (isSplat(VL)) {
       return ReuseShuffleCost +
              TTI->getShuffleCost(TargetTransformInfo::SK_Broadcast, VecTy, None,
                                  0);
     }
+    // No cost for "gathering" already vector value
+    if (isa<FixedVectorType>(VL[0]->getType()))
+      return 0;
     if (E->getOpcode() == Instruction::ExtractElement &&
         allSameType(VL) && allSameBlock(VL)) {
       SmallVector<int> Mask;
       Optional<TargetTransformInfo::ShuffleKind> ShuffleKind =
           isShuffle(VL, Mask);
       if (ShuffleKind.hasValue()) {
         InstructionCost Cost =
             computeExtractCost(VL, VecTy, *ShuffleKind, Mask, *TTI);
void BoUpSLP::setInsertPointAfterBundle(const TreeEntry *E) {
   // debug location to Front.
   Builder.SetInsertPoint(BB, ++LastInst->getIterator());
   Builder.SetCurrentDebugLocation(Front->getDebugLoc());
 }
 
 Value *BoUpSLP::gather(ArrayRef<Value *> VL) {
   Value *Val0 =
       isa<StoreInst>(VL[0]) ? cast<StoreInst>(VL[0])->getValueOperand() : VL[0];
+  // "Gathering" of vector values is already done
+  if (isa<FixedVectorType>(Val0->getType()))
+    return Val0;
   FixedVectorType *VecTy = FixedVectorType::get(Val0->getType(), VL.size());
   Value *Vec = PoisonValue::get(VecTy);
   unsigned InsIndex = 0;
   for (Value *Val : VL) {
     Vec = Builder.CreateInsertElement(Vec, Val, Builder.getInt32(InsIndex++));
     auto *InsElt = dyn_cast<InsertElementInst>(Vec);
     if (!InsElt)
       continue;

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

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -slp-vectorizer -slp-threshold=-10000 < %s | FileCheck %s
 ; RUN: opt -S -slp-vectorizer -slp-threshold=0 < %s | FileCheck %s
+; RUN: opt -S -slp-vectorizer -slp-threshold=-10000 -slp-min-tree-size=0 < %s | FileCheck %s
 
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-n8:16:32:64-S128"
 target triple = "x86_64-apple-macosx10.8.0"
 
 define <4 x float> @simple_select(<4 x float> %a, <4 x float> %b, <4 x i32> %c) #0 {
 ; CHECK-LABEL: @simple_select(
 ; CHECK-NEXT:    [[TMP1:%.*]] = icmp ne <4 x i32> [[C:%.*]], zeroinitializer
 ; CHECK-NEXT:    [[TMP2:%.*]] = select <4 x i1> [[TMP1]], <4 x float> [[A:%.*]], <4 x float> [[B:%.*]]
;
   %rd = insertelement <4 x float> %rc, float %s3, i32 3
   ret <4 x float> %rd
 }
 
 declare void @llvm.assume(i1) nounwind
 
 ; This entire tree is ephemeral, don't vectorize any of it.
 define <4 x float> @simple_select_eph(<4 x float> %a, <4 x float> %b, <4 x i32> %c) #0 {
-; CHECK-LABEL: @simple_select_eph(
-; CHECK-NEXT:    [[C0:%.*]] = extractelement <4 x i32> [[C:%.*]], i32 0
-; CHECK-NEXT:    [[C1:%.*]] = extractelement <4 x i32> [[C]], i32 1
-; CHECK-NEXT:    [[C2:%.*]] = extractelement <4 x i32> [[C]], i32 2
-; CHECK-NEXT:    [[C3:%.*]] = extractelement <4 x i32> [[C]], i32 3
-; CHECK-NEXT:    [[A0:%.*]] = extractelement <4 x float> [[A:%.*]], i32 0
-; CHECK-NEXT:    [[A1:%.*]] = extractelement <4 x float> [[A]], i32 1
-; CHECK-NEXT:    [[A2:%.*]] = extractelement <4 x float> [[A]], i32 2
-; CHECK-NEXT:    [[A3:%.*]] = extractelement <4 x float> [[A]], i32 3
-; CHECK-NEXT:    [[B0:%.*]] = extractelement <4 x float> [[B:%.*]], i32 0
-; CHECK-NEXT:    [[B1:%.*]] = extractelement <4 x float> [[B]], i32 1
-; CHECK-NEXT:    [[B2:%.*]] = extractelement <4 x float> [[B]], i32 2
-; CHECK-NEXT:    [[B3:%.*]] = extractelement <4 x float> [[B]], i32 3
-; CHECK-NEXT:    [[CMP0:%.*]] = icmp ne i32 [[C0]], 0
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp ne i32 [[C1]], 0
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp ne i32 [[C2]], 0
-; CHECK-NEXT:    [[CMP3:%.*]] = icmp ne i32 [[C3]], 0
-; CHECK-NEXT:    [[S0:%.*]] = select i1 [[CMP0]], float [[A0]], float [[B0]]
-; CHECK-NEXT:    [[S1:%.*]] = select i1 [[CMP1]], float [[A1]], float [[B1]]
-; CHECK-NEXT:    [[S2:%.*]] = select i1 [[CMP2]], float [[A2]], float [[B2]]
-; CHECK-NEXT:    [[S3:%.*]] = select i1 [[CMP3]], float [[A3]], float [[B3]]
-; CHECK-NEXT:    [[RA:%.*]] = insertelement <4 x float> poison, float [[S0]], i32 0
-; CHECK-NEXT:    [[RB:%.*]] = insertelement <4 x float> [[RA]], float [[S1]], i32 1
-; CHECK-NEXT:    [[RC:%.*]] = insertelement <4 x float> [[RB]], float [[S2]], i32 2
-; CHECK-NEXT:    [[RD:%.*]] = insertelement <4 x float> [[RC]], float [[S3]], i32 3
-; CHECK-NEXT:    [[Q0:%.*]] = extractelement <4 x float> [[RD]], i32 0
-; CHECK-NEXT:    [[Q1:%.*]] = extractelement <4 x float> [[RD]], i32 1
-; CHECK-NEXT:    [[Q2:%.*]] = extractelement <4 x float> [[RD]], i32 2
-; CHECK-NEXT:    [[Q3:%.*]] = extractelement <4 x float> [[RD]], i32 3
-; CHECK-NEXT:    [[Q4:%.*]] = fadd float [[Q0]], [[Q1]]
-; CHECK-NEXT:    [[Q5:%.*]] = fadd float [[Q2]], [[Q3]]
-; CHECK-NEXT:    [[Q6:%.*]] = fadd float [[Q4]], [[Q5]]
-; CHECK-NEXT:    [[QI:%.*]] = fcmp olt float [[Q6]], [[Q5]]
-; CHECK-NEXT:    call void @llvm.assume(i1 [[QI]])
-; CHECK-NEXT:    ret <4 x float> undef
-;
   %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
   %a3 = extractelement <4 x float> %a, i32 3
;
   %b1 = extractelement <4 x float> %b, i32 1
   %b2 = extractelement <4 x float> %b, i32 2
   %b3 = extractelement <4 x float> %b, i32 3
   %cmp0 = icmp ne i32 %c0, 0
   %cmp1 = icmp ne i32 %c1, 0
   %cmp2 = icmp ne i32 %c2, 0
   %cmp3 = icmp ne i32 %c3, 0
   %s0 = select i1 %cmp0, float %a0, float %b0
   %s1 = select i1 %cmp1, float %a1, float %b1
   %s2 = select i1 %cmp2, float %a2, float %b2
   %s3 = select i1 %cmp3, float %a3, float %b3
   %ra = insertelement <4 x float> poison, float %s0, i32 0
   %rb = insertelement <4 x float> %ra, float %s1, i32 1
   %rc = insertelement <4 x float> %rb, float %s2, i32 2
   %rd = insertelement <4 x float> %rc, float %s3, i32 3
   call void @v4f32_user(<4 x float> %rd) #0
   ret <4 x float> %rd
 }
 
 ; Unused insertelement
 define <4 x float> @simple_select_no_users(<4 x float> %a, <4 x float> %b, <4 x i32> %c) #0 {
 ; CHECK-LABEL: @simple_select_no_users(
 ; CHECK-NEXT:    [[C0:%.*]] = extractelement <4 x i32> [[C:%.*]], i32 0
 ; CHECK-NEXT:    [[C1:%.*]] = extractelement <4 x i32> [[C]], i32 1
;
   %10 = extractelement <2 x float> %8, i32 1
   %rb = insertelement <4 x float> %ra, float %10, i32 1
   ret <4 x float> %rb
 }
 
 ; Make sure that vectorization happens even if insertelements operations
 ; must be rescheduled. The case here is from compiling Julia.
 define <4 x float> @reschedule_extract(<4 x float> %a, <4 x float> %b) {
-; CHECK-LABEL: @reschedule_extract(
-; CHECK-NEXT:    [[TMP1:%.*]] = fadd <4 x float> [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    ret <4 x float> [[TMP1]]
-;
   %a0 = extractelement <4 x float> %a, i32 0
   %b0 = extractelement <4 x float> %b, i32 0
   %c0 = fadd float %a0, %b0
   %v0 = insertelement <4 x float> poison, float %c0, i32 0
   %a1 = extractelement <4 x float> %a, i32 1
   %b1 = extractelement <4 x float> %b, i32 1
   %c1 = fadd float %a1, %b1
   %v1 = insertelement <4 x float> %v0, float %c1, i32 1
   %a2 = extractelement <4 x float> %a, i32 2
   %b2 = extractelement <4 x float> %b, i32 2
   %c2 = fadd float %a2, %b2
   %v2 = insertelement <4 x float> %v1, float %c2, i32 2
   %a3 = extractelement <4 x float> %a, i32 3
   %b3 = extractelement <4 x float> %b, i32 3
   %c3 = fadd float %a3, %b3
   %v3 = insertelement <4 x float> %v2, float %c3, i32 3
   ret <4 x float> %v3
 }
 
 ; Check that cost model for vectorization takes credit for
 ; instructions that are erased.
 define <4 x float> @take_credit(<4 x float> %a, <4 x float> %b) {
-; CHECK-LABEL: @take_credit(
-; CHECK-NEXT:    [[TMP1:%.*]] = fadd <4 x float> [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    ret <4 x float> [[TMP1]]
-;
   %a0 = extractelement <4 x float> %a, i32 0
   %b0 = extractelement <4 x float> %b, i32 0
   %c0 = fadd float %a0, %b0
   %a1 = extractelement <4 x float> %a, i32 1
   %b1 = extractelement <4 x float> %b, i32 1
   %c1 = fadd float %a1, %b1
   %a2 = extractelement <4 x float> %a, i32 2
   %b2 = extractelement <4 x float> %b, i32 2
;
   %t6 = fmul double %t2, 1.000000e+00
   %i3 = insertelement <4 x double> %i2, double %t6, i32 1
   %t7 = fmul double %t3, 1.000000e+00
   %i4 = insertelement <4 x double> %i3, double %t7, i32 0
   ret <4 x double> %i4
 }
 
 define <8 x float> @_vadd256(<8 x float> %a, <8 x float> %b) local_unnamed_addr #0 {
-; CHECK-LABEL: @_vadd256(
-; CHECK-NEXT:    [[TMP1:%.*]] = fadd <8 x float> [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    ret <8 x float> [[TMP1]]
-;
   %vecext = extractelement <8 x float> %a, i32 0
   %vecext1 = extractelement <8 x float> %b, i32 0
   %add = fadd float %vecext, %vecext1
   %vecext2 = extractelement <8 x float> %a, i32 1
   %vecext3 = extractelement <8 x float> %b, i32 1
   %add4 = fadd float %vecext2, %vecext3
   %vecext5 = extractelement <8 x float> %a, i32 2
   %vecext6 = extractelement <8 x float> %b, i32 2