[AArch64] Adjust the cost of integer vector division

[evandro]

Summary

Since there is no legal instruction for integer vector division, factor in the cost of singling out each element to be used with the scalar division instruction.

[evandro]

This patch results in some image processing benchmarks to improve by over 1% on big Cortex and Exynos cores.

[mssimpso]

Makes sense to me. I tested this patch on Falkor and didn't notice any significant performance differences on the benchmarks I ran. Can we add a test case, though? Maybe in test/Analysis/CostModel?

[evandro]

Added a test case.

[mssimpso]

For the test case, why not just run "-cost-model -analyze" like we do for the other tests instead of running the vectorizer? Am I missing something?

[evandro]

The test case has scalar types and it seems more interesting to see the cost rising proportionally with the vector factor.

[mssimpso]

In D43974#1030467, @evandro wrote:

The test case has scalar types and it seems more interesting to see the cost rising proportionally with the vector factor.

You can't really see the costs of the divisions increasing, though. Why not follow the example in bswap.ll with something like:

define <2 x i32> @sdiv_v2i32(<2 x i32> %a, <2 x i32> %b) {
; CHECK: Found an estimated cost of 8 for instruction:   %tmp = sdiv <2 x i32> %a, %b
  %tmp = sdiv <2 x i32> %a, %b
  ret <2 x i32> %tmp
}

define <4 x i32> @sdiv_v4i32(<4 x i32> %a, <4 x i32> %b) {
; CHECK: Found an estimated cost of 22 for instruction:   %tmp = sdiv <4 x i32> %a, %b
  %tmp = sdiv <4 x i32> %a, %b
  ret <4 x i32> %tmp
}

...

[evandro]

That's a sensible alternative.

[evandro]

Updated the test case.

[mssimpso]

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

8

Show the actual numbers instead of a regex?

[evandro]

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

8

I was afraid you were going to say that... 🙂

[mssimpso]

LGTM, thanks!

llvm/lib/Target/AArch64/AArch64TargetTransformInfo.cpp

int AArch64TTIImpl::getArithmeticInstrCost(
   // widening overhead here, we attach the total cost of the combined operation
   // to the widening instruction.
   int Cost = 0;
   if (isWideningInstruction(Ty, Opcode, Args))
     Cost += ST->getWideningBaseCost();
 
   int ISD = TLI->InstructionOpcodeToISD(Opcode);
 
-  if (ISD == ISD::SDIV &&
-      Opd2Info == TargetTransformInfo::OK_UniformConstantValue &&
+  switch (ISD) {
+  default:
+    return Cost + BaseT::getArithmeticInstrCost(Opcode, Ty, Opd1Info, Opd2Info,
+                                                Opd1PropInfo, Opd2PropInfo);
+  case ISD::SDIV:
+    if (Opd2Info == TargetTransformInfo::OK_UniformConstantValue &&
         Opd2PropInfo == TargetTransformInfo::OP_PowerOf2) {
       // On AArch64, scalar signed division by constants power-of-two are
       // normally expanded to the sequence ADD + CMP + SELECT + SRA.
       // The OperandValue properties many not be same as that of previous
       // operation; conservatively assume OP_None.
       Cost += getArithmeticInstrCost(Instruction::Add, Ty, Opd1Info, Opd2Info,
                                      TargetTransformInfo::OP_None,
                                      TargetTransformInfo::OP_None);
       Cost += getArithmeticInstrCost(Instruction::Sub, Ty, Opd1Info, Opd2Info,
                                      TargetTransformInfo::OP_None,
                                      TargetTransformInfo::OP_None);
       Cost += getArithmeticInstrCost(Instruction::Select, Ty, Opd1Info, Opd2Info,
                                      TargetTransformInfo::OP_None,
                                      TargetTransformInfo::OP_None);
       Cost += getArithmeticInstrCost(Instruction::AShr, Ty, Opd1Info, Opd2Info,
                                      TargetTransformInfo::OP_None,
                                      TargetTransformInfo::OP_None);
       return Cost;
     }
-
-  switch (ISD) {
-  default:
-    return Cost + BaseT::getArithmeticInstrCost(Opcode, Ty, Opd1Info, Opd2Info,
-                                                Opd1PropInfo, Opd2PropInfo);
+    LLVM_FALLTHROUGH;
+  case ISD::UDIV:
+    Cost += BaseT::getArithmeticInstrCost(Opcode, Ty, Opd1Info, Opd2Info,
+    if (Ty->isVectorTy()) {
+      // On AArch64, vector divisions are not supported natively and are
+      // expanded into scalar divisions of each pair of elements.
+      Cost += getArithmeticInstrCost(Instruction::ExtractElement, Ty, Opd1Info,
+                                     Opd2Info, Opd1PropInfo, Opd2PropInfo);
+      Cost += getArithmeticInstrCost(Instruction::InsertElement, Ty, Opd1Info,
+                                     Opd2Info, Opd1PropInfo, Opd2PropInfo);
+      // TODO: if one of the arguments is scalar, then it's not necessary to
+      // double the cost of handling the vector elements.
+      Cost += Cost;
+    }
+    return Cost;
+
   case ISD::ADD:
   case ISD::MUL:
   case ISD::XOR:
   case ISD::OR:
   case ISD::AND:
     // These nodes are marked as 'custom' for combining purposes only.
     // We know that they are legal. See LowerAdd in ISelLowering.
     return (Cost + 1) * LT.first;

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

+; RUN: opt -cost-model -analyze -mtriple=aarch64--linux-gnu < %s | FileCheck %s
+
+; Verify the cost of integer division instructions.
+
+define i32 @sdivs1i32(i32 %a, i32 %b) {
+; CHECK-LABEL: 'Cost Model Analysis' for function 'sdivs1i32':
+; CHECK: Found an estimated cost of 1 for instruction: %c = sdiv i32 %a, %b
+  %c = sdiv i32 %a, %b
+  ret i32 %c
+}
+
+define i64 @sdivs1i64(i64 %a, i64 %b) {
+; CHECK-LABEL: 'Cost Model Analysis' for function 'sdivs1i64':
+; CHECK: Found an estimated cost of 1 for instruction: %c = sdiv i64 %a, %b
+  %c = sdiv i64 %a, %b
+  ret i64 %c
+}
+
+define <2 x i32> @sdivv2i32(<2 x i32> %a, <2 x i32> %b) {
+; CHECK-LABEL: 'Cost Model Analysis' for function 'sdivv2i32':
+; CHECK: Found an estimated cost of 24 for instruction: %c = sdiv <2 x i32> %a, %b
+  %c = sdiv <2 x i32> %a, %b
+  ret <2 x i32> %c
+}
+
+define <2 x i64> @sdivv2i64(<2 x i64> %a, <2 x i64> %b) {
+; CHECK-LABEL: 'Cost Model Analysis' for function 'sdivv2i64':
+; CHECK: Found an estimated cost of 24 for instruction: %c = sdiv <2 x i64> %a, %b
+  %c = sdiv <2 x i64> %a, %b
+  ret <2 x i64> %c
+}
+
+define <4 x i32> @sdivv4i32(<4 x i32> %a, <4 x i32> %b) {
+; CHECK-LABEL: 'Cost Model Analysis' for function 'sdivv4i32':
+; CHECK: Found an estimated cost of 52 for instruction: %c = sdiv <4 x i32> %a, %b
+  %c = sdiv <4 x i32> %a, %b
+  ret <4 x i32> %c
+}