[TTI] BasicTTI::getInterleavedMemoryOpCost(): use getScalarizationOverhead()

[RKSimon]

Summary

getScalarizationOverhead() results in a somewhat better cost estimation
than counting the insertion/extraction costs directly.
Notably, this is still overestimating the costs.

[lebedev.ri]

(note that i haven't update all the affected tests, only the checkline blocks where there is at least one change have been updated)

[RKSimon]

I've done my own version and I have all the tests updated - would you mind if I commandeered this with my version?

[lebedev.ri]

In D110713#3030304, @RKSimon wrote:

I've done my own version and I have all the tests updated - would you mind if I commandeered this with my version?

Sure, go ahead!

[RKSimon]

Update all tests and just getScalarizationOverhead wrapper when all elements are demanded

[lebedev.ri]

LG, it's a bit of an improvement in modelling precision, but not much.
Thank you!

llvm/include/llvm/CodeGen/BasicTTIImpl.h

1261–1262

Please can you name the bool params?

[RKSimon]

cheers - it seems to be enough to cause an actual test change so is at least going in the right direction. A better step would be to get this converted to shuffle costs, but we have really poor handling of length changing shuffles

llvm/include/llvm/CodeGen/BasicTTIImpl.h

1261–1262

yes I'll add them

llvm/include/llvm/CodeGen/BasicTTIImpl.h

if (Opcode == Instruction::Load) {
       // The interleave cost is similar to extract sub vectors' elements
       // from the wide vector, and insert them into sub vectors.
       //
       // E.g. An interleaved load of factor 2 (with one member of index 0):
       //      %vec = load <8 x i32>, <8 x i32>* %ptr
       //      %v0 = shuffle %vec, undef, <0, 2, 4, 6>         ; Index 0
       // The cost is estimated as extract elements at 0, 2, 4, 6 from the
       // <8 x i32> vector and insert them into a <4 x i32> vector.
+      APInt ExtractedElts(NumElts, 0);
       for (unsigned Index : Indices) {
         assert(Index < Factor && "Invalid index for interleaved memory op");
 
         // Extract elements from loaded vector for each sub vector.
         for (unsigned Elm = 0; Elm < NumSubElts; Elm++)
-          Cost += thisT()->getVectorInstrCost(Instruction::ExtractElement, VT,
-                                              Index + Elm * Factor);
+          ExtractedElts.setBit(Index + Elm * Factor);
       }
+      Cost += thisT()->getScalarizationOverhead(
+          VT, ExtractedElts, /*Insert=*/false, /*Extract=*/true);
 
-      InstructionCost InsSubCost = 0;
+      APInt InsertedElts(NumSubElts, 0);
       for (unsigned Elm = 0; Elm < NumSubElts; Elm++)
-        InsSubCost +=
-            thisT()->getVectorInstrCost(Instruction::InsertElement, SubVT, Elm);
-
-      Cost += Indices.size() * InsSubCost;
+        InsertedElts.setBit(Elm);
+      Cost += Indices.size() *
+              thisT()->getScalarizationOverhead(
+                  SubVT, InsertedElts, /*Insert=*/true, /*Extract=*/false);
     } else {
       // The interleave cost is extract elements from sub vectors, and
       // insert them into the wide vector.
       //
       // E.g. An interleaved store of factor 3 with 2 members at indices 0,1:
       // (using VF=4):
       //    %v0_v1 = shuffle %v0, %v1, <0,4,undef,1,5,undef,2,6,undef,3,7,undef>
       //    %gaps.mask = <true, true, false, true, true, false,
       //                  true, true, false, true, true, false>
       //    call llvm.masked.store <12 x i32> %v0_v1, <12 x i32>* %ptr,
       //                           i32 Align, <12 x i1> %gaps.mask
       // The cost is estimated as extract all elements (of actual members,
       // excluding gaps) from both <4 x i32> vectors and insert into the <12 x
       // i32> vector.
-      InstructionCost ExtSubCost = 0;
+      APInt ExtractedElts(NumSubElts, 0);
       for (unsigned Elm = 0; Elm < NumSubElts; Elm++)
-        ExtSubCost += thisT()->getVectorInstrCost(Instruction::ExtractElement,
-                                                  SubVT, Elm);
-      Cost += ExtSubCost * Indices.size();
+        ExtractedElts.setBit(Elm);
+      Cost += Indices.size() *
+              thisT()->getScalarizationOverhead(
+                  SubVT, ExtractedElts, /*Insert=*/false, /*Extract=*/true);
 
+      APInt InsertedElts(NumElts, 0);
       for (unsigned Index : Indices) {
         assert(Index < Factor && "Invalid index for interleaved memory op");
 
-        // Insert elements from loaded vector for each sub vector.
+        // Extract elements from loaded vector for each sub vector.
         for (unsigned Elm = 0; Elm < NumSubElts; Elm++)
-          Cost += thisT()->getVectorInstrCost(Instruction::InsertElement, VT,
-                                              Index + Elm * Factor);
+          InsertedElts.setBit(Index + Elm * Factor);
       }
+      Cost += thisT()->getScalarizationOverhead(
+          VT, InsertedElts, /*Insert=*/true, /*Extract=*/false);
     }
 
     if (!UseMaskForCond)
       return Cost;
 
     Type *I8Type = Type::getInt8Ty(VT->getContext());
     auto *MaskVT = FixedVectorType::get(I8Type, NumElts);
     SubVT = FixedVectorType::get(I8Type, NumSubElts);

llvm/test/Analysis/CostModel/X86/interleaved-load-i16-stride-5.ll

 ; AVX1: LV: Found an estimated cost of 50 for VF 4 For instruction:   %v0 = load i16, i16* %in0, align 2
 ; AVX1: LV: Found an estimated cost of 99 for VF 8 For instruction:   %v0 = load i16, i16* %in0, align 2
 ; AVX1: LV: Found an estimated cost of 285 for VF 16 For instruction:   %v0 = load i16, i16* %in0, align 2
 ;
 ; AVX2: LV: Found an estimated cost of 1 for VF 1 For instruction:   %v0 = load i16, i16* %in0, align 2
 ; AVX2: LV: Found an estimated cost of 26 for VF 2 For instruction:   %v0 = load i16, i16* %in0, align 2
 ; AVX2: LV: Found an estimated cost of 50 for VF 4 For instruction:   %v0 = load i16, i16* %in0, align 2
 ; AVX2: LV: Found an estimated cost of 99 for VF 8 For instruction:   %v0 = load i16, i16* %in0, align 2
-; AVX2: LV: Found an estimated cost of 285 for VF 16 For instruction:   %v0 = load i16, i16* %in0, align 2
+; AVX2: LV: Found an estimated cost of 215 for VF 16 For instruction:   %v0 = load i16, i16* %in0, align 2
 ;
 ; AVX512: LV: Found an estimated cost of 1 for VF 1 For instruction:   %v0 = load i16, i16* %in0, align 2
 ; AVX512: LV: Found an estimated cost of 11 for VF 2 For instruction:   %v0 = load i16, i16* %in0, align 2
 ; AVX512: LV: Found an estimated cost of 11 for VF 4 For instruction:   %v0 = load i16, i16* %in0, align 2
 ; AVX512: LV: Found an estimated cost of 14 for VF 8 For instruction:   %v0 = load i16, i16* %in0, align 2
 ; AVX512: LV: Found an estimated cost of 28 for VF 16 For instruction:   %v0 = load i16, i16* %in0, align 2
 ; AVX512: LV: Found an estimated cost of 55 for VF 32 For instruction:   %v0 = load i16, i16* %in0, align 2
 ; AVX512: LV: Found an estimated cost of 235 for VF 64 For instruction:   %v0 = load i16, i16* %in0, align 2

llvm/test/Analysis/CostModel/X86/interleaved-load-i8-stride-2.ll

 ; RUN: opt -loop-vectorize -vectorizer-maximize-bandwidth -S -mattr=+sse2 --debug-only=loop-vectorize < %s 2>&1 | FileCheck %s --check-prefixes=CHECK,SSE2
 ; RUN: opt -loop-vectorize -vectorizer-maximize-bandwidth -S -mattr=+avx  --debug-only=loop-vectorize < %s 2>&1 | FileCheck %s --check-prefixes=CHECK,AVX1
 ; RUN: opt -loop-vectorize -vectorizer-maximize-bandwidth -S -mattr=+avx2 --debug-only=loop-vectorize < %s 2>&1 | FileCheck %s --check-prefixes=CHECK,AVX2
 ; RUN: opt -loop-vectorize -vectorizer-maximize-bandwidth -S -mattr=+avx512bw,+avx512vl --debug-only=loop-vectorize < %s 2>&1 | FileCheck %s --check-prefixes=CHECK,AVX512
 ; REQUIRES: asserts
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 @A = global [1024 x i8] zeroinitializer, align 128
 @B = global [1024 x i8] zeroinitializer, align 128
 
 ; CHECK: LV: Checking a loop in "test"
 ;
 ; SSE2: LV: Found an estimated cost of 1 for VF 1 For instruction:   %v0 = load i8, i8* %in0, align 1
-; SSE2: LV: Found an estimated cost of 20 for VF 2 For instruction:   %v0 = load i8, i8* %in0, align 1
-; SSE2: LV: Found an estimated cost of 56 for VF 4 For instruction:   %v0 = load i8, i8* %in0, align 1
-; SSE2: LV: Found an estimated cost of 160 for VF 8 For instruction:   %v0 = load i8, i8* %in0, align 1
-; SSE2: LV: Found an estimated cost of 478 for VF 16 For instruction:   %v0 = load i8, i8* %in0, align 1
+; SSE2: LV: Found an estimated cost of 14 for VF 2 For instruction:   %v0 = load i8, i8* %in0, align 1
+; SSE2: LV: Found an estimated cost of 30 for VF 4 For instruction:   %v0 = load i8, i8* %in0, align 1
+; SSE2: LV: Found an estimated cost of 62 for VF 8 For instruction:   %v0 = load i8, i8* %in0, align 1
+; SSE2: LV: Found an estimated cost of 126 for VF 16 For instruction:   %v0 = load i8, i8* %in0, align 1
 ;
 ; AVX1: LV: Found an estimated cost of 1 for VF 1 For instruction:   %v0 = load i8, i8* %in0, align 1
 ; AVX1: LV: Found an estimated cost of 9 for VF 2 For instruction:   %v0 = load i8, i8* %in0, align 1
 ; AVX1: LV: Found an estimated cost of 17 for VF 4 For instruction:   %v0 = load i8, i8* %in0, align 1
 ; AVX1: LV: Found an estimated cost of 33 for VF 8 For instruction:   %v0 = load i8, i8* %in0, align 1
 ; AVX1: LV: Found an estimated cost of 81 for VF 16 For instruction:   %v0 = load i8, i8* %in0, align 1
-; AVX1: LV: Found an estimated cost of 226 for VF 32 For instruction:   %v0 = load i8, i8* %in0, align 1
+; AVX1: LV: Found an estimated cost of 166 for VF 32 For instruction:   %v0 = load i8, i8* %in0, align 1
 ;
 ; AVX2: LV: Found an estimated cost of 1 for VF 1 For instruction:   %v0 = load i8, i8* %in0, align 1
 ; AVX2: LV: Found an estimated cost of 3 for VF 2 For instruction:   %v0 = load i8, i8* %in0, align 1
 ; AVX2: LV: Found an estimated cost of 3 for VF 4 For instruction:   %v0 = load i8, i8* %in0, align 1
 ; AVX2: LV: Found an estimated cost of 3 for VF 8 For instruction:   %v0 = load i8, i8* %in0, align 1
 ; AVX2: LV: Found an estimated cost of 5 for VF 16 For instruction:   %v0 = load i8, i8* %in0, align 1
 ; AVX2: LV: Found an estimated cost of 8 for VF 32 For instruction:   %v0 = load i8, i8* %in0, align 1
 ;

llvm/test/Analysis/CostModel/X86/interleaved-store-i8-stride-2.ll

 ; RUN: opt -loop-vectorize -vectorizer-maximize-bandwidth -S -mattr=+sse2 --debug-only=loop-vectorize < %s 2>&1 | FileCheck %s --check-prefixes=CHECK,SSE2
 ; RUN: opt -loop-vectorize -vectorizer-maximize-bandwidth -S -mattr=+avx  --debug-only=loop-vectorize < %s 2>&1 | FileCheck %s --check-prefixes=CHECK,AVX1
 ; RUN: opt -loop-vectorize -vectorizer-maximize-bandwidth -S -mattr=+avx2 --debug-only=loop-vectorize < %s 2>&1 | FileCheck %s --check-prefixes=CHECK,AVX2
 ; RUN: opt -loop-vectorize -vectorizer-maximize-bandwidth -S -mattr=+avx512bw,+avx512vl --debug-only=loop-vectorize < %s 2>&1 | FileCheck %s --check-prefixes=CHECK,AVX512
 ; REQUIRES: asserts
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 @A = global [1024 x i8] zeroinitializer, align 128
 @B = global [1024 x i8] zeroinitializer, align 128
 
 ; CHECK: LV: Checking a loop in "test"
 ;
 ; SSE2: LV: Found an estimated cost of 1 for VF 1 For instruction:   store i8 %v1, i8* %out1, align 1
-; SSE2: LV: Found an estimated cost of 27 for VF 2 For instruction:   store i8 %v1, i8* %out1, align 1
-; SSE2: LV: Found an estimated cost of 79 for VF 4 For instruction:   store i8 %v1, i8* %out1, align 1
-; SSE2: LV: Found an estimated cost of 238 for VF 8 For instruction:   store i8 %v1, i8* %out1, align 1
-; SSE2: LV: Found an estimated cost of 478 for VF 16 For instruction:   store i8 %v1, i8* %out1, align 1
+; SSE2: LV: Found an estimated cost of 14 for VF 2 For instruction:   store i8 %v1, i8* %out1, align 1
+; SSE2: LV: Found an estimated cost of 30 for VF 4 For instruction:   store i8 %v1, i8* %out1, align 1
+; SSE2: LV: Found an estimated cost of 62 for VF 8 For instruction:   store i8 %v1, i8* %out1, align 1
+; SSE2: LV: Found an estimated cost of 126 for VF 16 For instruction:   store i8 %v1, i8* %out1, align 1
 ;
 ; AVX1: LV: Found an estimated cost of 1 for VF 1 For instruction:   store i8 %v1, i8* %out1, align 1
 ; AVX1: LV: Found an estimated cost of 9 for VF 2 For instruction:   store i8 %v1, i8* %out1, align 1
 ; AVX1: LV: Found an estimated cost of 17 for VF 4 For instruction:   store i8 %v1, i8* %out1, align 1
 ; AVX1: LV: Found an estimated cost of 33 for VF 8 For instruction:   store i8 %v1, i8* %out1, align 1
-; AVX1: LV: Found an estimated cost of 97 for VF 16 For instruction:   store i8 %v1, i8* %out1, align 1
-; AVX1: LV: Found an estimated cost of 226 for VF 32 For instruction:   store i8 %v1, i8* %out1, align 1
-
+; AVX1: LV: Found an estimated cost of 67 for VF 16 For instruction:   store i8 %v1, i8* %out1, align 1
+; AVX1: LV: Found an estimated cost of 166 for VF 32 For instruction:   store i8 %v1, i8* %out1, align 1
+;
 ; AVX2: LV: Found an estimated cost of 1 for VF 1 For instruction:   store i8 %v1, i8* %out1, align 1
 ; AVX2: LV: Found an estimated cost of 2 for VF 2 For instruction:   store i8 %v1, i8* %out1, align 1
 ; AVX2: LV: Found an estimated cost of 2 for VF 4 For instruction:   store i8 %v1, i8* %out1, align 1
 ; AVX2: LV: Found an estimated cost of 2 for VF 8 For instruction:   store i8 %v1, i8* %out1, align 1
 ; AVX2: LV: Found an estimated cost of 4 for VF 16 For instruction:   store i8 %v1, i8* %out1, align 1
 ; AVX2: LV: Found an estimated cost of 6 for VF 32 For instruction:   store i8 %v1, i8* %out1, align 1
 ;
 ; AVX512: LV: Found an estimated cost of 1 for VF 1 For instruction:   store i8 %v1, i8* %out1, align 1