[X86][Costmodel] Load/store v2i16 VF=2 interleaving costs

[lebedev.ri]

Summary

@RKSimon please can you check that i'm got the idea right, and not missing any steps?

The only sched models that for cpu's that support avx2 but not avx512 are: haswell, broadwell, skylake, zen1-3

For load we have:
https://godbolt.org/z/M8vEKs5jY - for intels Block RThroughput: =2.0; for ryzens, Block RThroughput: <=1.0
So pick cost of 2.

For store we have:
https://godbolt.org/z/Kx1nKz7je - for intels Block RThroughput: =1.0; for ryzens, Block RThroughput: <=0.5
So pick cost of 1.

I'm directly using the shuffling asm the llc produced, without any manual fixups that may be needed to ensure sequential execution.

[RKSimon]

In your analysis, don't you need to account for the load/stores as well? Although in these cases they don't affect the numbers: https://llvm.godbolt.org/z/4xeEf619Y

[lebedev.ri]

llvm/lib/Target/X86/X86TargetTransformInfo.cpp

5062–5063

In your analysis, don't you need to account for the load/stores as well? Although in these cases they don't affect the numbers: https://llvm.godbolt.org/z/4xeEf619Y

I'm following this comment, only measuring the shuffle sequence, ignoring loads/stores.

[lebedev.ri]

And one more example: store VF16 stride 6:

• haswell 48 https://godbolt.org/z/jfb1rss8E
• broadwell 48 https://godbolt.org/z/v73sTPrax
• skylake 48 https://godbolt.org/z/fn8Y9334x
• zen1 20 https://godbolt.org/z/rnTvzYnTr (we seem to round 0.5 down?)
• zen2 20 https://godbolt.org/z/effcqPfaP (we seem to round 0.5 down?)
• zen3 20 https://godbolt.org/z/1fTjhf3To

Thus, 48.

Sidenote, i'm still unsure whether we should specify that Zen 3 has FeatureFastVariableShuffle.
Byte-wise variable shuffle is fast, but some are ucoded.

[lebedev.ri]

@RKSimon to be most specific: what i want here, is to agree on the algorithm, namely:

1. pick one IR sequence (from the codegen tests i've already added in llvm/test/CodeGen/X86/vector-interleaved-{load,store}-i16-stride-[2-6].ll)
2. annotate the [de]interleaving shuffle block with MCA macros
3. for each CPU (that has AVX2 but not AVX512) for which we have sched model:
   1. codegen the IR for given CPU
   2. do NO manual changes to the produced assembly whatsoever
   3. record Block RThroughput the MCA produces for that CPU/sched model
4. pick largest recorded Block RThroughput (rounding 0.999->1, 1.5->1, 1.50001->2) as the cost for the tuple

... so i can proceed to add the missing costs without nagging on you to double-check the findings.
At least that is what i would like to happen. If that is unfeasible, i can submit them as reviews..

[RKSimon]

In D103144#2783028, @lebedev.ri wrote:

Sidenote, i'm still unsure whether we should specify that Zen 3 has FeatureFastVariableShuffle.
Byte-wise variable shuffle is fast, but some are ucoded.

Yes, in hindsight this feature flag needs splitting into FeatureFastVariableCrossLaneShuffle + FeatureFastVariablePerLaneShuffle,

[lebedev.ri]

In D103144#2784735, @RKSimon wrote:

In D103144#2783028, @lebedev.ri wrote:

Sidenote, i'm still unsure whether we should specify that Zen 3 has FeatureFastVariableShuffle.
Byte-wise variable shuffle is fast, but some are ucoded.

Yes, in hindsight this feature flag needs splitting into FeatureFastVariableCrossLaneShuffle + FeatureFastVariablePerLaneShuffle,

Hmm. Let me look into that first then, right now :)

[lebedev.ri]

In D103144#2784747, @lebedev.ri wrote:

In D103144#2784735, @RKSimon wrote:

In D103144#2783028, @lebedev.ri wrote:

Sidenote, i'm still unsure whether we should specify that Zen 3 has FeatureFastVariableShuffle.
Byte-wise variable shuffle is fast, but some are ucoded.

Yes, in hindsight this feature flag needs splitting into FeatureFastVariableCrossLaneShuffle + FeatureFastVariablePerLaneShuffle,

Hmm. Let me look into that first then, right now :)

Done, D103274.

[RKSimon]

LGTM, and thanks for handling D103274

[lebedev.ri]

Thank you for taking a look!

In D103144#2787137, @RKSimon wrote:

LGTM, and thanks for handling D103274

Could you please specify, is LGTM for this specific change;
or about the algorithm, in which case i can proceed with
adding the other missing costs in
X86TTIImpl::getInterleavedMemoryOpCostAVX2()
without going throught this review?

[RKSimon]

The LGTM was for this patch.

The algorithm makes sense, although in the script I'm slowly writing for cost-tables vs llvm-mca comparisons, I'm always using ceil() for fractional values, this was mainly to keep with the 'worst case' approach of the cost tables.

[lebedev.ri]

Thank you.
The more i look at this, the more i think i'm not okay with the state of things there.
Clearly, the generic/worst-case costs are sacred, and are not easily changed,
but in the end, i think i actually care more about specific CPU[s].
So let's see if i can extend my scripts to knee-jerkingly improve situation for non-generic costs.

[lebedev.ri]

I've reconsidered.
If a patch spam is what it takes then i can surely do that.

llvm/lib/Target/X86/X86TargetTransformInfo.cpp

InstructionCost X86TTIImpl::getInterleavedMemoryOpCostAVX2(
   if (!ETy.isSimple())
     return BaseT::getInterleavedMemoryOpCost(Opcode, VecTy, Factor, Indices,
                                              Alignment, AddressSpace, CostKind);
 
   // TODO: Complete for other data-types and strides.
   // Each combination of Stride, element bit width and VF results in a different
   // sequence; The cost tables are therefore accessed with:
   // Factor (stride) and VectorType=VFxiN.
   // The Cost accounts only for the shuffle sequence;
   // The cost of the loads/stores is accounted for separately.
   //
   static const CostTblEntry AVX2InterleavedLoadTbl[] = {
+      {2, MVT::v2i16, 2}, // (load 4i16 and) deinterleave into 2 x 2i16
+
       {2, MVT::v4i64, 6}, // (load 8i64 and) deinterleave into 2 x 4i64
 
       {3, MVT::v2i8, 10},  // (load 6i8 and) deinterleave into 3 x 2i8
       {3, MVT::v4i8, 4},   // (load 12i8 and) deinterleave into 3 x 4i8
       {3, MVT::v8i8, 9},   // (load 24i8 and) deinterleave into 3 x 8i8
       {3, MVT::v16i8, 11}, // (load 48i8 and) deinterleave into 3 x 16i8
       {3, MVT::v32i8, 13}, // (load 96i8 and) deinterleave into 3 x 32i8
 
       {3, MVT::v8i32, 17}, // (load 24i32 and) deinterleave into 3 x 8i32
 
       {4, MVT::v2i8, 12},  // (load 8i8 and) deinterleave into 4 x 2i8
       {4, MVT::v4i8, 4},   // (load 16i8 and) deinterleave into 4 x 4i8
       {4, MVT::v8i8, 20},  // (load 32i8 and) deinterleave into 4 x 8i8
       {4, MVT::v16i8, 39}, // (load 64i8 and) deinterleave into 4 x 16i8
       {4, MVT::v32i8, 80}, // (load 128i8 and) deinterleave into 4 x 32i8
 
       {8, MVT::v8i32, 40} // (load 64i32 and) deinterleave into 8 x 8i32
   };
 
   static const CostTblEntry AVX2InterleavedStoreTbl[] = {
+      {2, MVT::v2i16, 1}, // interleave 2 x 2i16 into 4i16 (and store)
+
       {2, MVT::v4i64, 6}, // interleave 2 x 4i64 into 8i64 (and store)
 
       {3, MVT::v2i8, 7},   // interleave 3 x 2i8 into 6i8 (and store)
       {3, MVT::v4i8, 8},   // interleave 3 x 4i8 into 12i8 (and store)
       {3, MVT::v8i8, 11},  // interleave 3 x 8i8 into 24i8 (and store)
       {3, MVT::v16i8, 11}, // interleave 3 x 16i8 into 48i8 (and store)
       {3, MVT::v32i8, 13}, // interleave 3 x 32i8 into 96i8 (and store)
 

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

 ; RUN: opt -loop-vectorize -vectorizer-maximize-bandwidth -S -mattr=+avx2 --debug-only=loop-vectorize < %s 2>&1 | FileCheck %s
 ; 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 i16] zeroinitializer, align 128
 @B = global [1024 x i8] zeroinitializer, align 128
 
 ; CHECK: LV: Checking a loop in "test"
 ; CHECK: LV: Found an estimated cost of 1 for VF 1 For instruction:   %v0 = load i16, i16* %in0, align 2
-; CHECK: LV: Found an estimated cost of 9 for VF 2 For instruction:   %v0 = load i16, i16* %in0, align 2
+; CHECK: LV: Found an estimated cost of 3 for VF 2 For instruction:   %v0 = load i16, i16* %in0, align 2
 ; CHECK: LV: Found an estimated cost of 17 for VF 4 For instruction:   %v0 = load i16, i16* %in0, align 2
 ; CHECK: LV: Found an estimated cost of 41 for VF 8 For instruction:   %v0 = load i16, i16* %in0, align 2
 ; CHECK: LV: Found an estimated cost of 114 for VF 16 For instruction:   %v0 = load i16, i16* %in0, align 2
 ; CHECK: LV: Found an estimated cost of 228 for VF 32 For instruction:   %v0 = load i16, i16* %in0, align 2
 ; CHECK-NOT: LV: Found an estimated cost of {{[0-9]+}} for VF {{[0-9]+}} For instruction:   %v0 = load i16, i16* %in0, align 2
 
 define void @test() {
 entry:

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

 ; RUN: opt -loop-vectorize -vectorizer-maximize-bandwidth -S -mattr=+avx2 --debug-only=loop-vectorize < %s 2>&1 | FileCheck %s
 ; 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 i16] zeroinitializer, align 128
 
 ; CHECK: LV: Checking a loop in "test"
 ; CHECK: LV: Found an estimated cost of 1 for VF 1 For instruction:   store i16 %v1, i16* %out1, align 2
-; CHECK: LV: Found an estimated cost of 9 for VF 2 For instruction:   store i16 %v1, i16* %out1, align 2
+; CHECK: LV: Found an estimated cost of 2 for VF 2 For instruction:   store i16 %v1, i16* %out1, align 2
 ; CHECK: LV: Found an estimated cost of 17 for VF 4 For instruction:   store i16 %v1, i16* %out1, align 2
 ; CHECK: LV: Found an estimated cost of 49 for VF 8 For instruction:   store i16 %v1, i16* %out1, align 2
 ; CHECK: LV: Found an estimated cost of 114 for VF 16 For instruction:   store i16 %v1, i16* %out1, align 2
 ; CHECK: LV: Found an estimated cost of 228 for VF 32 For instruction:   store i16 %v1, i16* %out1, align 2
 ; CHECK-NOT: LV: Found an estimated cost of {{[0-9]+}} for VF {{[0-9]+}} For instruction:   store i16 %v1, i16* %out1, align 2
 
 define void @test() {
 entry: