[CostModel][AArch64] Improve the cost estimate of CTPOP intrinsic

[RosieSumpter]

Summary

Added a case for CTPOP to AArch64TTIImpl::getIntrinsicInstrCost so that
the cost estimate matches the codegen in
test/CodeGen/AArch64/arm64-vpopcnt.ll

[SjoerdMeijer]

llvm/lib/Target/AArch64/AArch64TargetTransformInfo.cpp

281

From a quick look, lookup tables here are more rare, while the it seems a lot more prevalent in the x86 implementations. But I quite like this little table here, it's accurate and easy to read, so have no problem with it.

289

Nit: you don't need the curly brackets for an if with 1 statement.

289

Do we have a test case where the table look up fails?

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

151

Does this really have a cost of only 2?

I guess it's 2 because LT.first * Entry->Cost = 2 * 1 = 2

So I am wondering if it is easier to expand the table with vector types, and if the lookup fails let it fall back to the generic function that will hopefully then assign a high cost for it.

[RosieSumpter]

llvm/lib/Target/AArch64/AArch64TargetTransformInfo.cpp

289

Good point, I'll expand the table then the large vector cases won't be found in the table.

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

151

I did try doing a check of the codegen for the large vector cases and they did seem to be double the cost, but I understand it is probably safer to expand the table so I'm happy to do that

[RosieSumpter]

Table now contains the vectors <= 128 bits

[RosieSumpter]

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

151

The costs for the large vectors are all now 4 as they fall through to a CustomCost of LT.first*2 in BasicTTIImpl.h. Is this what we want?

[dmgreen]

llvm/lib/Target/AArch64/AArch64TargetTransformInfo.cpp

280

It looks like this file doesn't contain all of the cases. As far as I understand, this is how it works:

• v8i8 and v8i16 are legal, so 1 instruction. Fantastic!
• v4i16 and v8i16 are converted to "v16i8 ctpop + addp". So cost 2
• v2i32 and v4i32 are converted to "v16i8 ctpop + addp + addp". So cost 3
• v1i64 and v2i64 are converted to "v16i8 ctpop + addp + addp + addp". So cost 4

Those are all good. For scalar, as opposed to vector, there is no good instruction though. The generation also looks pretty terrible at the moment.
So a i8 becomes "and 0xff; expensive-mov; v8i8 cnt; addlv; expensive-mov". The others looks equally expensive too. I would guess a cost of 5 would make sense?

Everything else would be legalized to one of those types. So you can probably use "auto LT = TLI->getTypeLegalizationCost(DL, RetTy);" and Use LT.first for the type in the table lookup, and return Entry->Cost * LT.second, to include the cost of legalization (how many different vectors there will be).

282

The table can also be easier to read if it's not formatted.
And maybe in a different order would help.

[CarolineConcatto]

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

64

nit: I don't know why ';' was added here in all functions, but I don't think you should use this patch to remove them.

[RosieSumpter]

llvm/lib/Target/AArch64/AArch64TargetTransformInfo.cpp

280

Thanks for the help with this, I've had another go at it. Only thing I'm not sure about now is that e.g. v2i16 is promoted to v2i32 so with LT.first * Entry->Cost it gets a cost of 3, but checking codegen it seems there are 5 instructions. Something like (2 * Entry->Cost - 1) would give the right numbers, but is this the correct thing to do?

[RosieSumpter]

• Corrected the scalar costs
• Adjusted the table
• Return LT.first * Entry->Cost or LT.first*Entry->Cost + 1 depending on whether vector integer type is promoted

[dmgreen]

Looks sensible to me, thanks

llvm/lib/Target/AArch64/AArch64TargetTransformInfo.cpp

293

I may be simpler to write it as this, without the if:

// Extra cost of +1 when illegal vector types are legalized by promoting
// the integer type.
int ExtraCost = MTy.getScalarSizeInBits() != RetTy->getScalarSizeInBits() ? 1 : 0;
return LT.first * Entry->Cost + ExtraCost;

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

64

If this is what the update script produces, I'm OK with the extra lines being removed. Either here or in a separate NFC patch.

llvm/lib/Target/AArch64/AArch64TargetTransformInfo.cpp

case Intrinsic::experimental_stepvector: {
     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::ctpop: {
+    static const CostTblEntry CtpopCostTbl[] = {
+        {ISD::CTPOP, MVT::v2i64, 4},
+        {ISD::CTPOP, MVT::v4i32, 3},
+        {ISD::CTPOP, MVT::v8i16, 2},
+        {ISD::CTPOP, MVT::v16i8, 1},
+        {ISD::CTPOP, MVT::i64,   4},
+        {ISD::CTPOP, MVT::v2i32, 3},
+        {ISD::CTPOP, MVT::v4i16, 2},
+        {ISD::CTPOP, MVT::v8i8,  1},
+        {ISD::CTPOP, MVT::i32,   5},
+    };
+    auto LT = TLI->getTypeLegalizationCost(DL, RetTy);
+    MVT MTy = LT.second;
+    if (const auto *Entry = CostTableLookup(CtpopCostTbl, ISD::CTPOP, MTy)) {
+      if (!MTy.isVector() ||
+          MTy.getScalarSizeInBits() == RetTy->getScalarSizeInBits())
+        return LT.first * Entry->Cost;
+      else
+        // Extra cost of +1 when illegal vector types are legalized by promoting
+        // the integer type.
+        return LT.first * Entry->Cost + 1;
+    }
+    break;
+  }
   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/ctpop.ll

 ; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py
 ; RUN: opt < %s -mtriple=aarch64 -cost-model -analyze | FileCheck %s
 
 ; Verify the cost of scalar ctpop instructions.
 
 define i64 @test_ctpop_i64(i64 %a) {
-;
 ; CHECK-LABEL: 'test_ctpop_i64'
-; CHECK-NEXT:  Cost Model: Found an estimated cost of 2 for instruction: %ctpop = call i64 @llvm.ctpop.i64(i64 %a)
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 4 for instruction: %ctpop = call i64 @llvm.ctpop.i64(i64 %a)
 ; CHECK-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: ret i64 %ctpop
-;
   %ctpop = call i64 @llvm.ctpop.i64(i64 %a)
   ret i64 %ctpop
 }
 
 define i32 @test_ctpop_i32(i32 %a) {
-;
 ; CHECK-LABEL: 'test_ctpop_i32'
-; CHECK-NEXT:  Cost Model: Found an estimated cost of 2 for instruction: %ctpop = call i32 @llvm.ctpop.i32(i32 %a)
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 5 for instruction: %ctpop = call i32 @llvm.ctpop.i32(i32 %a)
 ; CHECK-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: ret i32 %ctpop
-;
   %ctpop = call i32 @llvm.ctpop.i32(i32 %a)
   ret i32 %ctpop
 }
 
 define i16 @test_ctpop_i16(i16 %a) {
-;
 ; CHECK-LABEL: 'test_ctpop_i16'
-; CHECK-NEXT:  Cost Model: Found an estimated cost of 2 for instruction: %ctpop = call i16 @llvm.ctpop.i16(i16 %a)
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 5 for instruction: %ctpop = call i16 @llvm.ctpop.i16(i16 %a)
 ; CHECK-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: ret i16 %ctpop
-;
   %ctpop = call i16 @llvm.ctpop.i16(i16 %a)
   ret i16 %ctpop
 }
 
 define i8 @test_ctpop_i8(i8 %a) {
-;
 ; CHECK-LABEL: 'test_ctpop_i8'
-; CHECK-NEXT:  Cost Model: Found an estimated cost of 2 for instruction: %ctpop = call i8 @llvm.ctpop.i8(i8 %a)
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 5 for instruction: %ctpop = call i8 @llvm.ctpop.i8(i8 %a)
 ; CHECK-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: ret i8 %ctpop
-;
   %ctpop = call i8 @llvm.ctpop.i8(i8 %a)
   ret i8 %ctpop
 }
 
 declare i64 @llvm.ctpop.i64(i64)
 declare i32 @llvm.ctpop.i32(i32)
 declare i16 @llvm.ctpop.i16(i16)
 declare i8 @llvm.ctpop.i8(i8)
 
 ; Verify the cost of vector ctpop instructions.
 
 define <2 x i64> @test_ctpop_v2i64(<2 x i64> %a) {
-;
 ; CHECK-LABEL: 'test_ctpop_v2i64'
-; CHECK-NEXT:  Cost Model: Found an estimated cost of 2 for instruction: %ctpop = call <2 x i64> @llvm.ctpop.v2i64(<2 x i64> %a)
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 4 for instruction: %ctpop = call <2 x i64> @llvm.ctpop.v2i64(<2 x i64> %a)
 ; CHECK-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: ret <2 x i64> %ctpop
-;
   %ctpop = call <2 x i64> @llvm.ctpop.v2i64(<2 x i64> %a)
   ret <2 x i64> %ctpop
 }
 
 define <2 x i32> @test_ctpop_v2i32(<2 x i32> %a) {
-;
 ; CHECK-LABEL: 'test_ctpop_v2i32'
-; CHECK-NEXT:  Cost Model: Found an estimated cost of 2 for instruction: %ctpop = call <2 x i32> @llvm.ctpop.v2i32(<2 x i32> %a)
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 3 for instruction: %ctpop = call <2 x i32> @llvm.ctpop.v2i32(<2 x i32> %a)
 ; CHECK-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: ret <2 x i32> %ctpop
-;
   %ctpop = call <2 x i32> @llvm.ctpop.v2i32(<2 x i32> %a)
   ret <2 x i32> %ctpop
 }
 
 define <4 x i32> @test_ctpop_v4i32(<4 x i32> %a) {
-;
 ; CHECK-LABEL: 'test_ctpop_v4i32'
-; CHECK-NEXT:  Cost Model: Found an estimated cost of 2 for instruction: %ctpop = call <4 x i32> @llvm.ctpop.v4i32(<4 x i32> %a)
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 3 for instruction: %ctpop = call <4 x i32> @llvm.ctpop.v4i32(<4 x i32> %a)
 ; CHECK-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: ret <4 x i32> %ctpop
-;
   %ctpop = call <4 x i32> @llvm.ctpop.v4i32(<4 x i32> %a)
   ret <4 x i32> %ctpop
 }
 
 define <2 x i16> @test_ctpop_v2i16(<2 x i16> %a) {
-;
 ; CHECK-LABEL: 'test_ctpop_v2i16'
-; CHECK-NEXT:  Cost Model: Found an estimated cost of 2 for instruction: %ctpop = call <2 x i16> @llvm.ctpop.v2i16(<2 x i16> %a)
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 4 for instruction: %ctpop = call <2 x i16> @llvm.ctpop.v2i16(<2 x i16> %a)
 ; CHECK-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: ret <2 x i16> %ctpop
-;
   %ctpop = call <2 x i16> @llvm.ctpop.v2i16(<2 x i16> %a)
   ret <2 x i16> %ctpop
 }
 
 define <4 x i16> @test_ctpop_v4i16(<4 x i16> %a) {
-;
 ; CHECK-LABEL: 'test_ctpop_v4i16'
 ; CHECK-NEXT:  Cost Model: Found an estimated cost of 2 for instruction: %ctpop = call <4 x i16> @llvm.ctpop.v4i16(<4 x i16> %a)
 ; CHECK-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: ret <4 x i16> %ctpop
-;
   %ctpop = call <4 x i16> @llvm.ctpop.v4i16(<4 x i16> %a)
   ret <4 x i16> %ctpop
 }
 
 define <8 x i16> @test_ctpop_v8i16(<8 x i16> %a) {
-;
 ; CHECK-LABEL: 'test_ctpop_v8i16'
 ; CHECK-NEXT:  Cost Model: Found an estimated cost of 2 for instruction: %ctpop = call <8 x i16> @llvm.ctpop.v8i16(<8 x i16> %a)
 ; CHECK-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: ret <8 x i16> %ctpop
-;
   %ctpop = call <8 x i16> @llvm.ctpop.v8i16(<8 x i16> %a)
   ret <8 x i16> %ctpop
 }
 
 define <2 x i8> @test_ctpop_v2i8(<2 x i8> %a) {
-;
 ; CHECK-LABEL: 'test_ctpop_v2i8'
-; CHECK-NEXT:  Cost Model: Found an estimated cost of 2 for instruction: %ctpop = call <2 x i8> @llvm.ctpop.v2i8(<2 x i8> %a)
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 4 for instruction: %ctpop = call <2 x i8> @llvm.ctpop.v2i8(<2 x i8> %a)
 ; CHECK-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: ret <2 x i8> %ctpop
-;
   %ctpop = call <2 x i8> @llvm.ctpop.v2i8(<2 x i8> %a)
   ret <2 x i8> %ctpop
 }
 
 define <4 x i8> @test_ctpop_v4i8(<4 x i8> %a) {
-;
 ; CHECK-LABEL: 'test_ctpop_v4i8'
-; CHECK-NEXT:  Cost Model: Found an estimated cost of 2 for instruction: %ctpop = call <4 x i8> @llvm.ctpop.v4i8(<4 x i8> %a)
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 3 for instruction: %ctpop = call <4 x i8> @llvm.ctpop.v4i8(<4 x i8> %a)
 ; CHECK-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: ret <4 x i8> %ctpop
-;
   %ctpop = call <4 x i8> @llvm.ctpop.v4i8(<4 x i8> %a)
   ret <4 x i8> %ctpop
 }
 
 define <8 x i8> @test_ctpop_v8i8(<8 x i8> %a) {
-;
 ; CHECK-LABEL: 'test_ctpop_v8i8'
 ; CHECK-NEXT:  Cost Model: Found an estimated cost of 1 for instruction: %ctpop = call <8 x i8> @llvm.ctpop.v8i8(<8 x i8> %a)
 ; CHECK-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: ret <8 x i8> %ctpop
-;
   %ctpop = call <8 x i8> @llvm.ctpop.v8i8(<8 x i8> %a)
   ret <8 x i8> %ctpop
 }
 
 define <16 x i8> @test_ctpop_v16i8(<16 x i8> %a) {
-;
 ; CHECK-LABEL: 'test_ctpop_v16i8'
 ; CHECK-NEXT:  Cost Model: Found an estimated cost of 1 for instruction: %ctpop = call <16 x i8> @llvm.ctpop.v16i8(<16 x i8> %a)
 ; CHECK-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: ret <16 x i8> %ctpop
-;
   %ctpop = call <16 x i8> @llvm.ctpop.v16i8(<16 x i8> %a)
   ret <16 x i8> %ctpop
 }
 
 define <4 x i64> @test_ctpop_v4i64(<4 x i64> %a) {
-;
 ; CHECK-LABEL: 'test_ctpop_v4i64'
-; CHECK-NEXT:  Cost Model: Found an estimated cost of 4 for instruction: %ctpop = call <4 x i64> @llvm.ctpop.v4i64(<4 x i64> %a)
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 8 for instruction: %ctpop = call <4 x i64> @llvm.ctpop.v4i64(<4 x i64> %a)
 ; CHECK-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: ret <4 x i64> %ctpop
-;
   %ctpop = call <4 x i64> @llvm.ctpop.v4i64(<4 x i64> %a)
   ret <4 x i64> %ctpop
 }
 
 define <8 x i32> @test_ctpop_v8i32(<8 x i32> %a) {
-;
 ; CHECK-LABEL: 'test_ctpop_v8i32'
-; CHECK-NEXT:  Cost Model: Found an estimated cost of 4 for instruction: %ctpop = call <8 x i32> @llvm.ctpop.v8i32(<8 x i32> %a)
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 6 for instruction: %ctpop = call <8 x i32> @llvm.ctpop.v8i32(<8 x i32> %a)
 ; CHECK-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: ret <8 x i32> %ctpop
-;
   %ctpop = call <8 x i32> @llvm.ctpop.v8i32(<8 x i32> %a)
   ret <8 x i32> %ctpop
 }
 
 define <16 x i16> @test_ctpop_v16i16(<16 x i16> %a) {
-;
 ; CHECK-LABEL: 'test_ctpop_v16i16'
 ; CHECK-NEXT:  Cost Model: Found an estimated cost of 4 for instruction: %ctpop = call <16 x i16> @llvm.ctpop.v16i16(<16 x i16> %a)
 ; CHECK-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: ret <16 x i16> %ctpop
-;
   %ctpop = call <16 x i16> @llvm.ctpop.v16i16(<16 x i16> %a)
   ret <16 x i16> %ctpop
 }
 
 define <32 x i8> @test_ctpop_v32i8(<32 x i8> %a) {
 ; CHECK-LABEL: 'test_ctpop_v32i8'
-; CHECK-NEXT:  Cost Model: Found an estimated cost of 4 for instruction: %ctpop = call <32 x i8> @llvm.ctpop.v32i8(<32 x i8> %a)
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 2 for instruction: %ctpop = call <32 x i8> @llvm.ctpop.v32i8(<32 x i8> %a)
 ; CHECK-NEXT:  Cost Model: Found an estimated cost of 0 for instruction: ret <32 x i8> %ctpop
-;
   %ctpop = call <32 x i8> @llvm.ctpop.v32i8(<32 x i8> %a)
   ret <32 x i8> %ctpop
 }
 
 declare <2 x i64> @llvm.ctpop.v2i64(<2 x i64>)
 declare <2 x i32> @llvm.ctpop.v2i32(<2 x i32>)
 declare <4 x i32> @llvm.ctpop.v4i32(<4 x i32>)
 declare <2 x i16> @llvm.ctpop.v2i16(<2 x i16>)