[AArch64][CostModel]: Add costs for zero/sign extend.

[hassnaa-arm]

Summary

Add cost for extending to illegal scalable vector types.
Add testing file for the extend operations.

[hassnaa-arm]

Add testing file for the cost of zero/sign extend

[fhahn]

Could you please update the title to be more descriptive?

llvm/lib/Target/AArch64/AArch64TargetTransformInfo.cpp

2063

nit: -too wide-?

[hassnaa-arm]

fix comment typo

[hassnaa-arm]

Add more accurte costs.

[david-arm]

Thanks for this patch @hassnaa-arm! It's definitely an improvement on the existing cost model. However, I just have a few comments on the costs ...

llvm/lib/Target/AArch64/AArch64TargetTransformInfo.cpp

2066

For this example, something like

define <vscale x 16 x i16> @sve_ext_i8_i16(<vscale x 16 x i8> %a) {
  %r = zext <vscale x 16 x i8> %a to <vscale x 16 x i16>
  ret <vscale x 16 x i16> %r
}

would end up as

uunpklo z2.h, z0.b
uunpkhi z1.h, z0.b
mov     z0.d, z2.d
ret

So I think perhaps the comment above might be better written as something like

// zero/sign extend are implemented by multiple unpack operations,
// where each unpack operation has a cost of 2.

2067

I wonder if this cost should be even higher? Extending from nxv16i8 to nxv16i16 leads to 2 unpk instructions, where you have a cost of 4. However, going from nxv16i8 to nxv16i32 requires 6 unpk instructions, which I would expect to be 2*6=12. For example, I get:

sve_ext_i8_i32:
      uunpklo z1.h, z0.b
      uunpkhi z3.h, z0.b
      uunpklo z0.s, z1.h
      uunpkhi z1.s, z1.h
      uunpklo z2.s, z3.h
      uunpkhi z3.s, z3.h
      ret

The costs are probably even worse extending from nxv16i8 to nxv16i64!

2072

It would be good to complete the other extends from legal types here too, such as

{ ISD::ZERO_EXTEND, MVT::nxv8i32, MVT::nxv8i16, ?},
{ ISD::ZERO_EXTEND, MVT::nxv8i64, MVT::nxv8i16, ?},
{ ISD::ZERO_EXTEND, MVT::nxv4i64, MVT::nxv4i32, ?},

{ ISD::SIGN_EXTEND, MVT::nxv8i32, MVT::nxv8i16, ?},
{ ISD::SIGN_EXTEND, MVT::nxv8i64, MVT::nxv8i16, ?},
{ ISD::SIGN_EXTEND, MVT::nxv4i64, MVT::nxv4i32, ?},

[hassnaa-arm]

Recalculate costs. In the code generation testing file, use real variable instead of undef to get accurate costs.

[hassnaa-arm]

Remove changes included by mistake.

[dmgreen]

where each operation has a cost of 2

Why does each instruction have a cost of 2?

[hassnaa-arm]

In D142456#4079434, @dmgreen wrote:

where each operation has a cost of 2

Why does each instruction have a cost of 2?

Because that is mentioned here: https://developer.arm.com/documentation/pjdoc466751330-9685/latest/
in section 3.25 (SVE integer instructions)

[sdesmalen]

In D142456#4079499, @hassnaa-arm wrote:

In D142456#4079434, @dmgreen wrote:

where each operation has a cost of 2

Why does each instruction have a cost of 2?

Because that is mentioned here: https://developer.arm.com/documentation/pjdoc466751330-9685/latest/
in section 3.25 (SVE integer instructions)

Hi @hassnaa-arm, the cost-model shouldn't be hardcoding the number of cycles for one specific micro-architecture, because the cost-model should be accurate for other micro-architectures as well.
The cost requested here is the througput cost, not the latency. The throughput is closer to the number of instructions that is required for the operation.

[sdesmalen]

llvm/lib/Target/AArch64/AArch64TargetTransformInfo.cpp

2079

It's probably also worth adding cases for extending:

nxv8i16 -> nxv8i32
nxv8i16 -> nxv8i64
nxv4i32 -> nxv4i64

[dmgreen]

Yep - I would expect the throughput of most extend operations to be fairly cheap, at least it looks that way from the optimization guides I looked at. They are in line with other instructions, so would usually get a cost of 1.

There is always a chance that getting the cost "wrong" can result in better results. This change will probably make the vectorizer prefer lower vectorization factors or prefer neon over sve. That could result in better results in places, but it is usually better to get the costs more correct. We would need a good justification why they were set 2 x higher.

[hassnaa-arm]

In D142456#4079512, @sdesmalen wrote:

In D142456#4079499, @hassnaa-arm wrote:

In D142456#4079434, @dmgreen wrote:

where each operation has a cost of 2

Why does each instruction have a cost of 2?

Because that is mentioned here: https://developer.arm.com/documentation/pjdoc466751330-9685/latest/
in section 3.25 (SVE integer instructions)

Hi @hassnaa-arm, the cost-model shouldn't be hardcoding the number of cycles for one specific micro-architecture, because the cost-model should be accurate for other micro-architectures as well.
The cost requested here is the througput cost, not the latency. The throughput is closer to the number of instructions that is required for the operation.

The throughput of the unpack operation is 2.

[david-arm]

Hi @hassnaa-arm, so the confusing aspect here is that the throughput in the cost model is kind of the inverse of the throughput that's sometimes talked about in optimisation guides, which doesn't help. So in that optimisation guide you referenced earlier I believe that a high throughput is essentially a 'good thing', whereas in the vectoriser cost model a high value means the opposite. Suppose you took the inverse of the throughput (2), then it would be 1/2, but the cost has to be an integer so we can just round up to 1.

[dmgreen]

In D142456#4079959, @david-arm wrote:

Hi @hassnaa-arm, so the confusing aspect here is that the throughput in the cost model is kind of the inverse of the throughput that's sometimes talked about in optimisation guides, which doesn't help. So in that optimisation guide you referenced earlier I believe that a high throughput is essentially a 'good thing', whereas in the vectoriser cost model a high value means the opposite. Suppose you took the inverse of the throughput (2), then it would be 1/2, but the cost has to be an integer so we can just round up to 1.

Yeah - it's also relative to other instructions, so our baseline would be around 2 for any SVE operation on V1. Note that the V1 is a bit of an oddball in this regard - the SVE vector length is 256, but you can either execute 4 NEON instructions per cycle or 2 SVE instructions (they use the same vector pipelines, with SVE operations taking two pipelines. They end up with the same throughput in terms of bits). Really the reciprocal throughput cost of _all_ sve instructions should be twice what they are compared to neon instructions on V1. The end result would just be to double the cost so that VScaleForTuning (2 for V1) would divide them by 2 again. So it would be simpler (and more maintainable) to consider setting the VScaleForTuning to 1 for that core. Unfortunately when I tried that in the past the performance hit some snags, and it didn't solve the problem I was trying to fix.

That aside, in general the "Unpack and extend" instructions are usually cheap instructions in other optimization guides, in line with the costs of other instructions. Our generic cost should probably line up with that.

[hassnaa-arm]

Update the calculated costs.
Use a cost of 1 for each SVE instruction.

[david-arm]

llvm/lib/Target/AArch64/AArch64TargetTransformInfo.cpp

2066

I think perhaps this can just be a cost of 2 because there are only 2 unpacks needed? Same for the SIGN_EXTEND case.

2072

Hi @hassnaa-arm, I think this patch is still missing the other extends that @sdesmalen and I suggested?

[hassnaa-arm]

llvm/lib/Target/AArch64/AArch64TargetTransformInfo.cpp

2066

Needed instructions are 2 unpacks and 1 mov, that's why I made it 3.

[sdesmalen]

llvm/lib/Target/AArch64/AArch64TargetTransformInfo.cpp

2066

In this case the mov is inserted by the register allocator and isn't caused by lowering of the extend itself, so this should still have a cost of '2'.

[hassnaa-arm]

Recalculate the costs.

[sdesmalen]

LGTM with nit addressed

llvm/test/Analysis/CostModel/AArch64/sve-ext.ll

1

We have quite a few different files for the different kinds of extends, it might be nice to move them all to a single sve-cast.ll at some point (in a separate patch), similar to what was done for cast.ll

2

I don't think this is needed as there is no IR output (because of the -disable-output)

[hassnaa-arm]

This patch indirectly causes the vectoriser to choose a lower VF due to the high cost of extending nxv16i8 -> nxv16i16, and that caused a regression.
Dave was investigating that issue and he has created a patch for fixing it.
So, right now this patch should work well.
I will rebase it and run checks to make sure everything is okay.

[hassnaa-arm]

Updating by main branch.

llvm/lib/Target/AArch64/AArch64TargetTransformInfo.cpp

ConversionTbl[] = {
     { ISD::BITCAST, MVT::nxv2f16, MVT::nxv2i16, 0 },
     { ISD::BITCAST, MVT::nxv4f16, MVT::nxv4i16, 0 },
     { ISD::BITCAST, MVT::nxv2f32, MVT::nxv2i32, 0 },
 
     // Bitcasts from integer to float
     { ISD::BITCAST, MVT::nxv2i16, MVT::nxv2f16, 0 },
     { ISD::BITCAST, MVT::nxv4i16, MVT::nxv4f16, 0 },
     { ISD::BITCAST, MVT::nxv2i32, MVT::nxv2f32, 0 },
+
+    // Add cost for extending to illegal -too wide- scalable vectors.
+    // zero/sign extend are implemented by multiple unpack operations,
+    // where each operation has a cost of 1.
+    { ISD::ZERO_EXTEND, MVT::nxv16i16, MVT::nxv16i8, 2},
+    { ISD::ZERO_EXTEND, MVT::nxv16i32, MVT::nxv16i8, 6},
+    { ISD::ZERO_EXTEND, MVT::nxv16i64, MVT::nxv16i8, 14},
+    { ISD::ZERO_EXTEND, MVT::nxv8i32, MVT::nxv8i16, 2},
+    { ISD::ZERO_EXTEND, MVT::nxv8i64, MVT::nxv8i16, 6},
+    { ISD::ZERO_EXTEND, MVT::nxv4i64, MVT::nxv4i32, 2},
+
+    { ISD::SIGN_EXTEND, MVT::nxv16i16, MVT::nxv16i8, 2},
+    { ISD::SIGN_EXTEND, MVT::nxv16i32, MVT::nxv16i8, 6},
+    { ISD::SIGN_EXTEND, MVT::nxv16i64, MVT::nxv16i8, 14},
+    { ISD::SIGN_EXTEND, MVT::nxv8i32, MVT::nxv8i16, 2},
+    { ISD::SIGN_EXTEND, MVT::nxv8i64, MVT::nxv8i16, 6},
+    { ISD::SIGN_EXTEND, MVT::nxv4i64, MVT::nxv4i32, 2},
   };
 
   if (const auto *Entry = ConvertCostTableLookup(ConversionTbl, ISD,
                                                  DstTy.getSimpleVT(),
                                                  SrcTy.getSimpleVT()))
     return AdjustCost(Entry->Cost);
 
   static const TypeConversionCostTblEntry FP16Tbl[] = {
       {ISD::FP_TO_SINT, MVT::v4i8, MVT::v4f16, 1}, // fcvtzs

llvm/test/Analysis/CostModel/AArch64/cast.ll

 ; CHECK-NEXT:  Cost Model: Found an estimated cost of 1 for instruction: %v8 = sext <2 x i16> %loadv2i16 to <2 x i64>
 ; CHECK-NEXT:  Cost Model: Found an estimated cost of 1 for instruction: %v9 = zext <2 x i16> %loadv2i16 to <2 x i64>
 ; CHECK-NEXT:  Cost Model: Found an estimated cost of 1 for instruction: %v10 = sext <2 x i32> %loadv2i32 to <2 x i64>
 ; CHECK-NEXT:  Cost Model: Found an estimated cost of 1 for instruction: %v11 = zext <2 x i32> %loadv2i32 to <2 x i64>
 ; CHECK-NEXT:  Cost Model: Found an estimated cost of 2 for instruction: %v12 = sext <4 x i32> %loadv4i32 to <4 x i64>
 ; CHECK-NEXT:  Cost Model: Found an estimated cost of 2 for instruction: %v13 = zext <4 x i32> %loadv4i32 to <4 x i64>
 ; CHECK-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: %v14 = sext <vscale x 2 x i32> %loadnxv2i32 to <vscale x 2 x i64>
 ; CHECK-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: %v15 = zext <vscale x 2 x i32> %loadnxv2i32 to <vscale x 2 x i64>
-; CHECK-NEXT:  Cost Model: Found an estimated cost of 1 for instruction: %v16 = sext <vscale x 4 x i32> %loadnxv4i32 to <vscale x 4 x i64>
-; CHECK-NEXT:  Cost Model: Found an estimated cost of 1 for instruction: %v17 = zext <vscale x 4 x i32> %loadnxv4i32 to <vscale x 4 x i64>
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 2 for instruction: %v16 = sext <vscale x 4 x i32> %loadnxv4i32 to <vscale x 4 x i64>
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 2 for instruction: %v17 = zext <vscale x 4 x i32> %loadnxv4i32 to <vscale x 4 x i64>
 ; CHECK-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: ret i32 undef
 ;
   %loadi8 = load i8, ptr undef
   %loadi16 = load i16, ptr undef
   %loadi32 = load i32, ptr undef
   %loadv2i8 = load <2 x i8>, ptr undef
   %loadv4i8 = load <4 x i8>, ptr undef
   %loadv8i8 = load <8 x i8>, ptr undef

llvm/test/Analysis/CostModel/AArch64/sve-ext.ll

+; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py
+; RUN: opt -passes="print<cost-model>" 2>&1 -disable-output -mtriple aarch64-linux-gnu -mattr=+sve -S -o - < %s | FileCheck %s
+
+target triple = "aarch64-unknown-linux-gnu"
+
+define void @sve_ext() {
+; CHECK-LABEL: 'sve_ext'
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 2 for instruction: %zext_nxv16_i8_to_i16 = zext <vscale x 16 x i8> undef to <vscale x 16 x i16>
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 6 for instruction: %zext_nxv16_i8_to_i32 = zext <vscale x 16 x i8> undef to <vscale x 16 x i32>
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 14 for instruction: %zext_nxv16_i8_to_i64 = zext <vscale x 16 x i8> undef to <vscale x 16 x i64>
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 2 for instruction: %zext_nxv8_i16_to_i32 = zext <vscale x 8 x i16> undef to <vscale x 8 x i32>
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 6 for instruction: %zext_nxv8_i16_to_i64 = zext <vscale x 8 x i16> undef to <vscale x 8 x i64>
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 2 for instruction: %zext_nxv4_i32_to_i64 = zext <vscale x 4 x i32> undef to <vscale x 4 x i64>
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 2 for instruction: %sext_nxv16_i8_to_i16 = sext <vscale x 16 x i8> undef to <vscale x 16 x i16>
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 6 for instruction: %sext_nxv16_i8_to_i32 = sext <vscale x 16 x i8> undef to <vscale x 16 x i32>
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 14 for instruction: %sext_nxv16_i8_to_i64 = sext <vscale x 16 x i8> undef to <vscale x 16 x i64>
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 2 for instruction: %sext_nxv8_i16_to_i32 = sext <vscale x 8 x i16> undef to <vscale x 8 x i32>
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 6 for instruction: %sext_nxv8_i16_to_i64 = sext <vscale x 8 x i16> undef to <vscale x 8 x i64>
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 2 for instruction: %sext_nxv4_i32_to_i64 = sext <vscale x 4 x i32> undef to <vscale x 4 x i64>
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: ret void
+;
+  %zext_nxv16_i8_to_i16 = zext <vscale x 16 x i8> undef to <vscale x 16 x i16>
+  %zext_nxv16_i8_to_i32 = zext <vscale x 16 x i8> undef to <vscale x 16 x i32>
+  %zext_nxv16_i8_to_i64 = zext <vscale x 16 x i8> undef to <vscale x 16 x i64>
+  %zext_nxv8_i16_to_i32 = zext <vscale x 8 x i16> undef to <vscale x 8 x i32>
+  %zext_nxv8_i16_to_i64 = zext <vscale x 8 x i16> undef to <vscale x 8 x i64>
+  %zext_nxv4_i32_to_i64 = zext <vscale x 4 x i32> undef to <vscale x 4 x i64>
+
+  %sext_nxv16_i8_to_i16 = sext <vscale x 16 x i8> undef to <vscale x 16 x i16>
+  %sext_nxv16_i8_to_i32 = sext <vscale x 16 x i8> undef to <vscale x 16 x i32>
+  %sext_nxv16_i8_to_i64 = sext <vscale x 16 x i8> undef to <vscale x 16 x i64>
+  %sext_nxv8_i16_to_i32 = sext <vscale x 8 x i16> undef to <vscale x 8 x i32>
+  %sext_nxv8_i16_to_i64 = sext <vscale x 8 x i16> undef to <vscale x 8 x i64>
+  %sext_nxv4_i32_to_i64 = sext <vscale x 4 x i32> undef to <vscale x 4 x i64>
+
+  ret void
+}

llvm/test/Analysis/CostModel/AArch64/sve-widening-instruction.ll

;
   %in1.ext = zext <vscale x 4 x i16> %in2 to <vscale x 4 x i32>
   %in2.ext = zext <vscale x 4 x i16> %in2 to <vscale x 4 x i32>
   %in.add = add <vscale x 4 x i32> %in1.ext, %in2.ext
   ret <vscale x 4 x i32> %in.add
 }
 
 define <vscale x 8 x i32> @widening_nxv8i16(<vscale x 8 x i16> %in1, <vscale x 8 x i16> %in2) {
 ; CHECK-LABEL: 'widening_nxv8i16'
-; CHECK-NEXT:  Cost Model: Found an estimated cost of 3 for instruction: %in1.ext = zext <vscale x 8 x i16> %in2 to <vscale x 8 x i32>
-; CHECK-NEXT:  Cost Model: Found an estimated cost of 3 for instruction: %in2.ext = zext <vscale x 8 x i16> %in2 to <vscale x 8 x i32>
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 2 for instruction: %in1.ext = zext <vscale x 8 x i16> %in2 to <vscale x 8 x i32>
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 2 for instruction: %in2.ext = zext <vscale x 8 x i16> %in2 to <vscale x 8 x i32>
 ; CHECK-NEXT:  Cost Model: Found an estimated cost of 2 for instruction: %in.add = add <vscale x 8 x i32> %in1.ext, %in2.ext
 ; CHECK-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: ret <vscale x 8 x i32> %in.add
 ;
   %in1.ext = zext <vscale x 8 x i16> %in2 to <vscale x 8 x i32>
   %in2.ext = zext <vscale x 8 x i16> %in2 to <vscale x 8 x i32>
   %in.add = add <vscale x 8 x i32> %in1.ext, %in2.ext
   ret <vscale x 8 x i32> %in.add
 }