[SLP] Double UserCost compensation for vector store of aggregate

[anton-afanasyev]

Summary

For the case of vector storing of aggregate built before by findBuildAggregate() we adjust total cost to consider that vector is already prepared.

This patch fixes llvm.org/PR40522

[ABataev]

I think the better approach would be to pass the list of InsertUses as a buildTree function UserIgnoreLst argument. You just need to correctly generate ExtractElement instructions for these InsertElements because currently the compiler just crashes trying to remove instructions used as operands for the original InsertElements. Thoughts?

[anton-afanasyev]

In D96791#2565982, @ABataev wrote:

I think the better approach would be to pass the list of InsertUses as a buildTree function UserIgnoreLst argument. You just need to correctly generate ExtractElement instructions for these InsertElements because currently the compiler just crashes trying to remove instructions used as operands for the original InsertElements. Thoughts?

Thanks, I'm to try this approach.

[RKSimon]

Please can you cleanup pr40522.ll (remove the metatdata etc.)? Also, PR40522 notes missing fp2int vectorization - please can you add those?

typedef int int4 __attribute__((__vector_size__(16)));

void fp2int_vec1(float a, float b, float c, float d, int *p) {
  int4 result = (int4) { (int) a, (int) b, (int) c, (int) d };
  *p++ = result[0];
  *p++ = result[1];
  *p++ = result[2];
  *p++ = result[3];
}

void fp2int_vec2(float a, float b, float c, float d, int4 *p) {
  int4 result = (int4) { (int) a, (int) b, (int) c, (int) d };
  *p = result;
}

[anton-afanasyev]

Cleaned pr40522.ll

[anton-afanasyev]

I can add fp2int sample, but it is not touched by this patch. Actually, its tree built is not vectorized by marking as "tiny" (R.isTreeTinyAndNotFullyVectorizable() function), its size is 2 (since fp2int is unary operation, whereas add is binary one). Though it could be fixed by checking that stores are using its result and therefore tree size could be increased. But this looks too hacky, isn't it?

In D96791#2571041, @RKSimon wrote:

Please can you cleanup pr40522.ll (remove the metatdata etc.)? Also, PR40522 notes missing fp2int vectorization - please can you add those?

[RKSimon]

OK - adding the fp2int tests to the same test file makes sense to me as they call came from the same bug, even if we don't yet have a fix

[anton-afanasyev]

Added fp2int scalar and vector test cases

[RKSimon]

@ABataev Any comments?

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

6298

Can we use an llvm::any_of pattern instead here?

[anton-afanasyev]

I'm trying another approach here, so abandoned this for a while.

[anton-afanasyev]

Here is another fix approach: https://reviews.llvm.org/D98714

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

for (unsigned I = NextInst; I < MaxInst; ++I) {
         // shuffle.
         InstructionCost UserCost = 0;
         for (unsigned Lane = 0; Lane < OpsWidth; Lane++) {
           auto *IE = cast<InsertElementInst>(InsertUses[I + Lane]);
           if (auto *CI = dyn_cast<ConstantInt>(IE->getOperand(2)))
             UserCost += TTI->getVectorInstrCost(
                 Instruction::InsertElement, IE->getType(), CI->getZExtValue());
         }
+
+        // Double UserCost in case vector is used by StoreInst:
+        // the first cost to compensate ExtractCost (see above)
+        // and the second one to consider that vector is already
+        // prepared for vector store eliminating its redundant building
+        // with insert instructions.
+        for (User *U: InsertUses[I + OpsWidth - 1]->users())
+          if (isa<StoreInst>(U)) {
+              UserCost *= 2;
+              break;
+          }
+
         LLVM_DEBUG(dbgs() << "SLP: Compensate cost of users by: " << UserCost
                           << ".\n");
         Cost -= UserCost;
       }
 
       MinCost = std::min(MinCost, Cost);
 
       if (Cost < -SLPCostThreshold) {

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

entry:
   %incdec.ptr10 = getelementptr inbounds i32, i32* %p, i64 3
   store i32 %add3, i32* %incdec.ptr8, align 4, !tbaa !2
   store i32 %add5, i32* %incdec.ptr10, align 4, !tbaa !2
   ret void
 }
 
 define void @test2_vec(i32 %0, i32 %1, i32 %2, i32 %3, <4 x i32>* nocapture %4) {
 ; CHECK-LABEL: @test2_vec(
-; CHECK-NEXT:    [[TMP6:%.*]] = add nsw i32 [[TMP0:%.*]], 1
-; CHECK-NEXT:    [[TMP7:%.*]] = insertelement <4 x i32> undef, i32 [[TMP6]], i32 0
-; CHECK-NEXT:    [[TMP8:%.*]] = add nsw i32 [[TMP1:%.*]], 1
-; CHECK-NEXT:    [[TMP9:%.*]] = insertelement <4 x i32> [[TMP7]], i32 [[TMP8]], i32 1
-; CHECK-NEXT:    [[TMP10:%.*]] = add nsw i32 [[TMP2:%.*]], 1
-; CHECK-NEXT:    [[TMP11:%.*]] = insertelement <4 x i32> [[TMP9]], i32 [[TMP10]], i32 2
-; CHECK-NEXT:    [[TMP12:%.*]] = add nsw i32 [[TMP3:%.*]], 1
-; CHECK-NEXT:    [[TMP13:%.*]] = insertelement <4 x i32> [[TMP11]], i32 [[TMP12]], i32 3
-; CHECK-NEXT:    store <4 x i32> [[TMP13]], <4 x i32>* [[TMP4:%.*]], align 16, [[TBAA0]]
+; CHECK-NEXT:    [[TMP6:%.*]] = insertelement <4 x i32> poison, i32 [[TMP0:%.*]], i32 0
+; CHECK-NEXT:    [[TMP7:%.*]] = insertelement <4 x i32> [[TMP6]], i32 [[TMP1:%.*]], i32 1
+; CHECK-NEXT:    [[TMP8:%.*]] = insertelement <4 x i32> [[TMP7]], i32 [[TMP2:%.*]], i32 2
+; CHECK-NEXT:    [[TMP9:%.*]] = insertelement <4 x i32> [[TMP8]], i32 [[TMP3:%.*]], i32 3
+; CHECK-NEXT:    [[TMP10:%.*]] = add nsw <4 x i32> [[TMP9]], <i32 1, i32 1, i32 1, i32 1>
+; CHECK-NEXT:    store <4 x i32> [[TMP10]], <4 x i32>* [[TMP4:%.*]], align 16, [[TBAA0]]
 ; CHECK-NEXT:    ret void
 ;
   %6 = add nsw i32 %0, 1
   %7 = insertelement <4 x i32> undef, i32 %6, i32 0
   %8 = add nsw i32 %1, 1
   %9 = insertelement <4 x i32> %7, i32 %8, i32 1
   %10 = add nsw i32 %2, 1
   %11 = insertelement <4 x i32> %9, i32 %10, i32 2