[AArch64] Add cost tests for bitreverse

[Rin]

Summary

This patch includes cost tests for bit reverse as well as some adjustments to the cost model.

[dmgreen]

llvm/lib/Target/AArch64/AArch64TargetTransformInfo.cpp

259

I think that these types should have a slightly higher cost than just 1 (or 1*LT.first, the legalization cost).

It's common in these cost functions to have a table of operand and type, giving a cost to each. That way they can be controlled a little better. Like the getShuffleCost at the end of this file. Would it be worth adding something similar here?

(We could also maybe optimize the v4i32 case better using a vrev32. But it's probably best to use the current cost over what we expect it could be later).

[Rin]

Add adequate costs for bitreverse operations

[dmgreen]

llvm/lib/Target/AArch64/AArch64TargetTransformInfo.cpp

295

Can we change it to only call getTypeLegalizationCost once.

llvm/test/Analysis/CostModel/AArch64/bitreverse-cost-model.ll

8 ↗

(On Diff #350250)

I see this doesn't give a cost of 2. I think it is trying to use the legal type that i8 will be converted to (i32) for the costs.

Maybe.. can we add something that says "if the original element type is not the same as the legal element type, add 1"?

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

2

I'm not sure why this testcase was added when there was already one in review adding the same thing. It seems strange. Especially as it missed half of the important cases.

Can you combine the two tests into one? Making sure we have the tests from both. Less boilerplate in them would be good too.

[CarolineConcatto]

Hey @Rin,
I don't think you need bitreverse-cost-model.ll, you can use only bitreverse.ll.
Why some costs are not being changed in bitreverse.ll?

llvm/test/Analysis/CostModel/AArch64/bitreverse-cost-model.ll

2 ↗

(On Diff #350250)

Do you need to use

-cost-kind=code-size -mtriple=aarch64-none-eabi

?

I believe you can have the same command as bitreverse.ll, no?

nit:
s/%s --check-prefix=SIZE/ %s /

[Rin]

In D102755#2807464, @CarolineConcatto wrote:

Hey @Rin,
I don't think you need bitreverse-cost-model.ll, you can use only bitreverse.ll.
Why some costs are not being changed in bitreverse.ll?

Hi Carol, yeah, you're right, I'll remove it. And I'm working on making the costs adequate as well, which will require adjustments in bitreverse.ll

[Rin]

Address review comments

[CarolineConcatto]

llvm/lib/Target/AArch64/AArch64TargetTransformInfo.cpp

295

nit:
s/(LegalisationCost.second)/LegalisationCost.second/

298

Is the '+1' added because the ICA.getID() is informing the type is MVT::i32?
If so, then should we remove these types from the table

{Intrinsic::bitreverse, MVT::i8, 2},
{Intrinsic::bitreverse, MVT::i16, 2}

?
If not(the problem is not with the wrong type being selected on the table) can you add an explanation why the table does not solve the problem?

[Rin]

llvm/lib/Target/AArch64/AArch64TargetTransformInfo.cpp

298

Is the '+1' added because the ICA.getID() is informing the type is MVT::i32?

If so, then should we remove these types from the table

Yes, that's a good point. I'll remove them.

I think David mentioned the reason why the table does not sole the problem. Because it's trying to use the legal type that i8 will be converted to (i32) for the costs. Which is why I added that if. I'll add a comment in the code to highlight that.

[Rin]

Remove unused typed from cost model table

[Rin]

Address nit comment

[dmgreen]

Costs look good, as far as I can tell.

llvm/lib/Target/AArch64/AArch64TargetTransformInfo.cpp

299

Should this be if (Entry) return LegalisationCost.first * Entry->Cost; now?

[Rin]

Address review comment

[Rin]

llvm/lib/Target/AArch64/AArch64TargetTransformInfo.cpp

299

Yeah, you're right, I have changed it.

[dmgreen]

Thanks. LGTM

llvm/lib/Target/AArch64/AArch64TargetTransformInfo.cpp

unsigned Instrs =
         LT.second.getScalarSizeInBits() == RetTy->getScalarSizeInBits() ? 1 : 4;
     if (any_of(ValidSatTys, [&LT](MVT M) { return M == LT.second; }))
       return LT.first * Instrs;
     break;
   }
   case Intrinsic::abs: {
     static const auto ValidAbsTys = {MVT::v8i8,  MVT::v16i8, MVT::v4i16,
                                      MVT::v8i16, MVT::v2i32, MVT::v4i32,
                                      MVT::v2i64};
     auto LT = TLI->getTypeLegalizationCost(DL, RetTy);
     if (any_of(ValidAbsTys, [&LT](MVT M) { return M == LT.second; }))
       return LT.first;
     break;
   }
   case Intrinsic::experimental_stepvector: {
     InstructionCost Cost = 1; // Cost of the `index' instruction
     auto LT = TLI->getTypeLegalizationCost(DL, RetTy);
     // Legalisation of illegal vectors involves an `index' instruction plus
     // (LT.first - 1) vector adds.
     if (LT.first > 1) {
       Type *LegalVTy = EVT(LT.second).getTypeForEVT(RetTy->getContext());
       InstructionCost AddCost =
           getArithmeticInstrCost(Instruction::Add, LegalVTy, CostKind);
       Cost += AddCost * (LT.first - 1);
     }
     return Cost;
   }
+  case Intrinsic::bitreverse: {
+    static const CostTblEntry BitreverseTbl[] = {
+        {Intrinsic::bitreverse, MVT::i32, 1},
+        {Intrinsic::bitreverse, MVT::i64, 1},
+        {Intrinsic::bitreverse, MVT::v8i8, 1},
+        {Intrinsic::bitreverse, MVT::v16i8, 1},
+        {Intrinsic::bitreverse, MVT::v4i16, 2},
+        {Intrinsic::bitreverse, MVT::v8i16, 2},
+        {Intrinsic::bitreverse, MVT::v2i32, 2},
+        {Intrinsic::bitreverse, MVT::v4i32, 2},
+        {Intrinsic::bitreverse, MVT::v1i64, 2},
+        {Intrinsic::bitreverse, MVT::v2i64, 2},
+    };
+    const auto LegalisationCost = TLI->getTypeLegalizationCost(DL, RetTy);
+    const auto *Entry =
+        CostTableLookup(BitreverseTbl, ICA.getID(), LegalisationCost.second);
+    // Cost Model is using the legal type(i32) that i8 and i16 will be converted
+    // to +1 so that we match the actual lowering cost
+    if (TLI->getValueType(DL, RetTy, true) == MVT::i8 ||
+        TLI->getValueType(DL, RetTy, true) == MVT::i16)
+      return LegalisationCost.first * Entry->Cost + 1;
+    if (Entry)
+      return LegalisationCost.first * Entry->Cost;
+  }
   default:
     break;
   }
   return BaseT::getIntrinsicInstrCost(ICA, CostKind);
 }
 
 /// The function will remove redundant reinterprets casting in the presence
 /// of the control flow

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

 ; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py
 ; RUN: opt < %s -mtriple=aarch64-unknown-linux-gnu -cost-model -analyze | FileCheck %s
 
 ; Verify the cost of scalar bitreverse instructions.
 
 declare  i8 @llvm.bitreverse.i8(i8)
 declare i16 @llvm.bitreverse.i16(i16)
 declare i32 @llvm.bitreverse.i32(i32)
 declare i64 @llvm.bitreverse.i64(i64)
 

 ; CHECK-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: ret i32 %bitreverse
 ;
   %bitreverse = call i32 @llvm.bitreverse.i32(i32 %a)
   ret i32 %bitreverse
 }
 
 define i16 @var_bitreverse_i16(i16 %a) {
 ; CHECK-LABEL: 'var_bitreverse_i16'
-; CHECK-NEXT:  Cost Model: Found an estimated cost of 1 for instruction: %bitreverse = call i16 @llvm.bitreverse.i16(i16 %a)
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 2 for instruction: %bitreverse = call i16 @llvm.bitreverse.i16(i16 %a)
 ; CHECK-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: ret i16 %bitreverse
 ;
   %bitreverse = call i16 @llvm.bitreverse.i16(i16 %a)
   ret i16 %bitreverse
 }
 
 define i8 @var_bitreverse_i8(i8 %a) {
 ; CHECK-LABEL: 'var_bitreverse_i8'
-; CHECK-NEXT:  Cost Model: Found an estimated cost of 1 for instruction: %bitreverse = call i8 @llvm.bitreverse.i8(i8 %a)
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 2 for instruction: %bitreverse = call i8 @llvm.bitreverse.i8(i8 %a)
 ; CHECK-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: ret i8 %bitreverse
 ;
   %bitreverse = call i8 @llvm.bitreverse.i8(i8 %a)
   ret i8 %bitreverse
 }
 
 ; Verify the cost of vector bitreverse instructions.
 
+declare <1 x i64> @llvm.bitreverse.v1i64(<1 x i64>)
+declare <2 x i32> @llvm.bitreverse.v2i32(<2 x i32>)
+declare <4 x i16> @llvm.bitreverse.v4i16(<4 x i16>)
+declare <8 x i8> @llvm.bitreverse.v8i8(<8 x i8>)
+
 declare <2 x i64> @llvm.bitreverse.v2i64(<2 x i64>)
 declare <4 x i32> @llvm.bitreverse.v4i32(<4 x i32>)
 declare <8 x i16> @llvm.bitreverse.v8i16(<8 x i16>)
 declare <16 x i8> @llvm.bitreverse.v16i8(<16 x i8>)
 
 declare <4 x i64> @llvm.bitreverse.v4i64(<4 x i64>)
 declare <8 x i32> @llvm.bitreverse.v8i32(<8 x i32>)
 declare <16 x i16> @llvm.bitreverse.v16i16(<16 x i16>)
 declare <32 x i8> @llvm.bitreverse.v32i8(<32 x i8>)
 
+define <1 x i64> @var_bitreverse_v1i64(<1 x i64> %a) {
+; CHECK-LABEL: 'var_bitreverse_v1i64'
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 2 for instruction: %bitreverse = call <1 x i64> @llvm.bitreverse.v1i64(<1 x i64> %a)
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: ret <1 x i64> %bitreverse
+;
+  %bitreverse = call <1 x i64> @llvm.bitreverse.v1i64(<1 x i64> %a)
+  ret <1 x i64> %bitreverse
+}
+
 define <2 x i64> @var_bitreverse_v2i64(<2 x i64> %a) {
 ; CHECK-LABEL: 'var_bitreverse_v2i64'
 ; CHECK-NEXT:  Cost Model: Found an estimated cost of 2 for instruction: %bitreverse = call <2 x i64> @llvm.bitreverse.v2i64(<2 x i64> %a)
 ; CHECK-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: ret <2 x i64> %bitreverse
 ;
   %bitreverse = call <2 x i64> @llvm.bitreverse.v2i64(<2 x i64> %a)
   ret <2 x i64> %bitreverse
 }
 
 define <4 x i64> @var_bitreverse_v4i64(<4 x i64> %a) {
 ; CHECK-LABEL: 'var_bitreverse_v4i64'
 ; CHECK-NEXT:  Cost Model: Found an estimated cost of 4 for instruction: %bitreverse = call <4 x i64> @llvm.bitreverse.v4i64(<4 x i64> %a)
 ; CHECK-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: ret <4 x i64> %bitreverse
 ;
   %bitreverse = call <4 x i64> @llvm.bitreverse.v4i64(<4 x i64> %a)
   ret <4 x i64> %bitreverse
 }
 
+define <2 x i32> @var_bitreverse_v2i32(<2 x i32> %a) {
+; CHECK-LABEL: 'var_bitreverse_v2i32'
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 2 for instruction: %bitreverse = call <2 x i32> @llvm.bitreverse.v2i32(<2 x i32> %a)
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: ret <2 x i32> %bitreverse
+;
+  %bitreverse = call <2 x i32> @llvm.bitreverse.v2i32(<2 x i32> %a)
+  ret <2 x i32> %bitreverse
+}
+
 define <4 x i32> @var_bitreverse_v4i32(<4 x i32> %a) {
 ; CHECK-LABEL: 'var_bitreverse_v4i32'
 ; CHECK-NEXT:  Cost Model: Found an estimated cost of 2 for instruction: %bitreverse = call <4 x i32> @llvm.bitreverse.v4i32(<4 x i32> %a)
 ; CHECK-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: ret <4 x i32> %bitreverse
 ;
   %bitreverse = call <4 x i32> @llvm.bitreverse.v4i32(<4 x i32> %a)
   ret <4 x i32> %bitreverse
 }
 
 define <8 x i32> @var_bitreverse_v8i32(<8 x i32> %a) {
 ; CHECK-LABEL: 'var_bitreverse_v8i32'
 ; CHECK-NEXT:  Cost Model: Found an estimated cost of 4 for instruction: %bitreverse = call <8 x i32> @llvm.bitreverse.v8i32(<8 x i32> %a)
 ; CHECK-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: ret <8 x i32> %bitreverse
 ;
   %bitreverse = call <8 x i32> @llvm.bitreverse.v8i32(<8 x i32> %a)
   ret <8 x i32> %bitreverse
 }
 
+define <4 x i16> @var_bitreverse_v4i16(<4 x i16> %a) {
+; CHECK-LABEL: 'var_bitreverse_v4i16'
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 2 for instruction: %bitreverse = call <4 x i16> @llvm.bitreverse.v4i16(<4 x i16> %a)
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: ret <4 x i16> %bitreverse
+;
+  %bitreverse = call <4 x i16> @llvm.bitreverse.v4i16(<4 x i16> %a)
+  ret <4 x i16> %bitreverse
+}
+
 define <8 x i16> @var_bitreverse_v8i16(<8 x i16> %a) {
 ; CHECK-LABEL: 'var_bitreverse_v8i16'
-; CHECK-NEXT:  Cost Model: Found an estimated cost of 50 for instruction: %bitreverse = call <8 x i16> @llvm.bitreverse.v8i16(<8 x i16> %a)
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 2 for instruction: %bitreverse = call <8 x i16> @llvm.bitreverse.v8i16(<8 x i16> %a)
 ; CHECK-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: ret <8 x i16> %bitreverse
 ;
   %bitreverse = call <8 x i16> @llvm.bitreverse.v8i16(<8 x i16> %a)
   ret <8 x i16> %bitreverse
 }
 
 define <16 x i16> @var_bitreverse_v16i16(<16 x i16> %a) {
 ; CHECK-LABEL: 'var_bitreverse_v16i16'
-; CHECK-NEXT:  Cost Model: Found an estimated cost of 100 for instruction: %bitreverse = call <16 x i16> @llvm.bitreverse.v16i16(<16 x i16> %a)
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 4 for instruction: %bitreverse = call <16 x i16> @llvm.bitreverse.v16i16(<16 x i16> %a)
 ; CHECK-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: ret <16 x i16> %bitreverse
 ;
   %bitreverse = call <16 x i16> @llvm.bitreverse.v16i16(<16 x i16> %a)
   ret <16 x i16> %bitreverse
 }
 
+define <8 x i8> @var_bitreverse_v8i8(<8 x i8> %a) {
+; CHECK-LABEL: 'var_bitreverse_v8i8'
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 1 for instruction: %bitreverse = call <8 x i8> @llvm.bitreverse.v8i8(<8 x i8> %a)
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: ret <8 x i8> %bitreverse
+;
+  %bitreverse = call <8 x i8> @llvm.bitreverse.v8i8(<8 x i8> %a)
+  ret <8 x i8> %bitreverse
+}
+
 define <16 x i8> @var_bitreverse_v16i8(<16 x i8> %a) {
 ; CHECK-LABEL: 'var_bitreverse_v16i8'
 ; CHECK-NEXT:  Cost Model: Found an estimated cost of 1 for instruction: %bitreverse = call <16 x i8> @llvm.bitreverse.v16i8(<16 x i8> %a)
 ; CHECK-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: ret <16 x i8> %bitreverse
 ;
   %bitreverse = call <16 x i8> @llvm.bitreverse.v16i8(<16 x i8> %a)
   ret <16 x i8> %bitreverse
 }
 
 define <32 x i8> @var_bitreverse_v32i8(<32 x i8> %a) {
 ; CHECK-LABEL: 'var_bitreverse_v32i8'
-; CHECK-NEXT:  Cost Model: Found an estimated cost of 4 for instruction: %bitreverse = call <32 x i8> @llvm.bitreverse.v32i8(<32 x i8> %a)
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 2 for instruction: %bitreverse = call <32 x i8> @llvm.bitreverse.v32i8(<32 x i8> %a)
 ; CHECK-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: ret <32 x i8> %bitreverse
 ;
   %bitreverse = call <32 x i8> @llvm.bitreverse.v32i8(<32 x i8> %a)
   ret <32 x i8> %bitreverse
 }