[AArch64] Improve cost of vector division by constant

[zatrazz]

Summary

With custom lowering for vector MULLH{S,U} [1], it is now profitable to
vectorize a divide by constant loop for the custom types (v16i8, v8i16,
and v4i32). The cost if based on TargetLowering::Build{S,U}DIV which
uses a multiply by constant plus adjustment to express a divide by
constant.

Both {u,s}mull{2} are expressed as Instruction::Mul and shifts by
Instruction::AShr.

[1] With custom lowering for vector MULLH{S,U}, it is now profitable to
vectorize a divide by constant loop for the custom types (v16i8, v8i16,
and v4i32). The cost if based on TargetLowering::Build{S,U}DIV which
uses a multiply by constant plus adjustment to express a divide by
constant.

Both {u,s}mull{2} are expressed as Instruction::Mul and shifts by
Instruction::AShr.

[rengolin]

Do we have similar cost tests for x86, Arm and others? It would be nice to make sure the change to BasicTTIImplBase didn't break other targets' costs.

[zatrazz]

In D46010#1077903, @rengolin wrote:

Do we have similar cost tests for x86, Arm and others? It would be nice to make sure the change to BasicTTIImplBase didn't break other targets' costs.

I should not change other architectures than AArch64 because 'isArithmeticDivFast' is a new method (only used by this patch). I initially added this logic on AArch64TargetTransformInfo.cpp, but since the division by constant is a platform agnostic transformation I though it would make sense to check the same check on a platform agnostic manner.

[zatrazz]

Ping now that https://reviews.llvm.org/D46009 has been committed.

[rengolin]

In D46010#1078477, @zatrazz wrote:

I should not change other architectures than AArch64 because 'isArithmeticDivFast' is a new method (only used by this patch).

This still looks very AArch64-y to me. Those two ISD nodes are specific to the case you're working on. I'm sure there are a lot more "divs" than that. :)

but since the division by constant is a platform agnostic transformation I though it would make sense to check the same check on a platform agnostic manner.

It is platform agnostic if you cover all cases that a platform agnostic constant divide function should. Right now, it's specific to this one issue in this one arch.

Alternatively, a simple static function here would be more appropriate. We can expand later if it proves to be more than just this case/arch.

I would mention that this is relying on the code generator to pick this exact pattern and hope nothing goes wrong between cost analysis and generation, but this is not new, so not for this patch. :)

--renato

[zatrazz]

In D46010#1087835, @rengolin wrote:

In D46010#1078477, @zatrazz wrote:

I should not change other architectures than AArch64 because 'isArithmeticDivFast' is a new method (only used by this patch).

This still looks very AArch64-y to me. Those two ISD nodes are specific to the case you're working on. I'm sure there are a lot more "divs" than that. :)

but since the division by constant is a platform agnostic transformation I though it would make sense to check the same check on a platform agnostic manner.

It is platform agnostic if you cover all cases that a platform agnostic constant divide function should. Right now, it's specific to this one issue in this one arch.

The divide-by-constant is lowered in a platform agnostic way at TargetLowering::BuildUDIV and TargetLowering::BuildSDIV (lib/CodeGen/SelectionDAG/TargetLowering.cpp). You can see that if target can lower either ISD::MULHS or ISD::SMUL_LOHI the multiply by inverse plus adjustment algorithm will be used. AArch64 is the case where it currently lowers ISD::MULHS.

What I am not sure if I need to handle the TargetTransformInfo::OP_PowerOf2 case, since DAGCombiner::visitSDIV will apply this transformation prior BuildSDIV/BuildUDIV.

Alternatively, a simple static function here would be more appropriate. We can expand later if it proves to be more than just this case/arch.

I would mention that this is relying on the code generator to pick this exact pattern and hope nothing goes wrong between cost analysis and generation, but this is not new, so not for this patch. :)

Yes, ideally this kind of cost analysis would be better *after* the BuildUDIV/BuildSDIV expansion.

[zatrazz]

But I do agree that there is not much gain in making the division by constant cost logic generic. I changed by moving the logic on aarch64 target cost class.

lib/Target/AArch64/AArch64TargetTransformInfo.cpp

477

And this new line shouldn't be here, I will remove it.

[rengolin]

LGTM with the line removed. :)

Thanks!

[evandro]

I tired this patch on Exynos and the performance of SPEC CPU2000 was virtually neutral, even if slightly negative overall in the integer score. Perhaps the defaults costs are too optimistic about the relative difference between multiply and add?

[zatrazz]

In D46010#1088258, @evandro wrote:

I tired this patch on Exynos and the performance of SPEC CPU2000 was virtually neutral, even if slightly negative overall in the integer score. Perhaps the defaults costs are too optimistic about the relative difference between multiply and add?

Any idea if the overall result is due the patch itself of system jitter/noise? Does any component outliers significantly?

[zatrazz]

In fact I couldn't find any code generation different with and without this patch on speccpu2000. Most likely the performance difference is expected runtime variance from speccpu2000 (I do see a lot in some components).

lib/Target/AArch64/AArch64TargetTransformInfo.cpp

if (Index != -1U) {
     if (Index == 0)
       return 0;
   }
 
   // All other insert/extracts cost this much.
   return ST->getVectorInsertExtractBaseCost();
 }
 
+
 int AArch64TTIImpl::getArithmeticInstrCost(
     unsigned Opcode, Type *Ty, TTI::OperandValueKind Opd1Info,
     TTI::OperandValueKind Opd2Info, TTI::OperandValueProperties Opd1PropInfo,
     TTI::OperandValueProperties Opd2PropInfo, ArrayRef<const Value *> Args) {
   // Legalize the type.
   std::pair<int, MVT> LT = TLI->getTypeLegalizationCost(DL, Ty);
 
   // If the instruction is a widening instruction (e.g., uaddl, saddw, etc.),
if (Opd2Info == TargetTransformInfo::OK_UniformConstantValue &&
                                      TargetTransformInfo::OP_None);
       Cost += getArithmeticInstrCost(Instruction::AShr, Ty, Opd1Info, Opd2Info,
                                      TargetTransformInfo::OP_None,
                                      TargetTransformInfo::OP_None);
       return Cost;
     }
     LLVM_FALLTHROUGH;
   case ISD::UDIV:
+    if (Opd2Info == TargetTransformInfo::OK_UniformConstantValue) {
+      auto VT = TLI->getValueType(DL, Ty);
+      if (TLI->isOperationLegalOrCustom(ISD::MULHU, VT)) {
+        // Vector signed division by constant are expanded to the
+        // sequence MULHS + ADD/SUB + SRA + SRL + ADD, and unsigned division
+        // to MULHS + SUB + SRL + ADD + SRL.
+        int MulCost = getArithmeticInstrCost(Instruction::Mul, Ty, Opd1Info,
+                                             Opd2Info,
+                                             TargetTransformInfo::OP_None,
+                                             TargetTransformInfo::OP_None);
+        int AddCost = getArithmeticInstrCost(Instruction::Add, Ty, Opd1Info,
+                                             Opd2Info,
+                                             TargetTransformInfo::OP_None,
+                                             TargetTransformInfo::OP_None);
+        int ShrCost = getArithmeticInstrCost(Instruction::AShr, Ty, Opd1Info,
+                                             Opd2Info,
+                                             TargetTransformInfo::OP_None,
+                                             TargetTransformInfo::OP_None);
+        return MulCost * 2 + AddCost * 2 + ShrCost * 2 + 1;
+      }
+    }
+
     Cost += BaseT::getArithmeticInstrCost(Opcode, Ty, Opd1Info, Opd2Info,
                                           Opd1PropInfo, Opd2PropInfo);
     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,

test/Analysis/CostModel/AArch64/div_cte.ll

+; RUN: opt -cost-model -analyze -mtriple=aarch64-linux-gnu -mattr=+neon < %s | FileCheck %s
+
+; Verify the cost of integer division by constant.
+
+define <16 x i8> @sdiv8xi16(<16 x i8> %x) {
+; CHECK-LABEL: 'Cost Model Analysis' for function 'sdiv8xi16':
+; CHECK: Found an estimated cost of 9 for instruction: %div = sdiv <16 x i8> %x, <i8 9, i8 9, i8 9, i8 9, i8 9, i8 9, i8 9, i8 9, i8 9, i8 9, i8 9, i8 9, i8 9, i8 9, i8 9, i8 9>
+  %div = sdiv <16 x i8> %x, <i8 9, i8 9, i8 9, i8 9, i8 9, i8 9, i8 9, i8 9, i8 9, i8 9, i8 9, i8 9, i8 9, i8 9, i8 9, i8 9>
+  ret <16 x i8> %div
+}
+
+define <8 x i16> @sdiv16xi8(<8 x i16> %x) {
+; CHECK-LABEL: 'Cost Model Analysis' for function 'sdiv16xi8':
+; CHECK: Found an estimated cost of 9 for instruction: %div = sdiv <8 x i16> %x, <i16 9, i16 9, i16 9, i16 9, i16 9, i16 9, i16 9, i16 9>
+  %div = sdiv <8 x i16> %x, <i16 9, i16 9, i16 9, i16 9, i16 9, i16 9, i16 9, i16 9>
+  ret <8 x i16> %div
+}
+
+define <4 x i32> @sdiv32xi4(<4 x i32> %x) {
+; CHECK-LABEL: 'Cost Model Analysis' for function 'sdiv32xi4':
+; CHECK: Found an estimated cost of 9 for instruction: %div = sdiv <4 x i32> %x, <i32 9, i32 9, i32 9, i32 9>
+  %div = sdiv <4 x i32> %x, <i32 9, i32 9, i32 9, i32 9>
+  ret <4 x i32> %div
+}
+
+define <16 x i8> @udiv8xi16(<16 x i8> %x) {
+; CHECK-LABEL: 'Cost Model Analysis' for function 'udiv8xi16':
+; CHECK: Found an estimated cost of 9 for instruction: %div = udiv <16 x i8> %x, <i8 9, i8 9, i8 9, i8 9, i8 9, i8 9, i8 9, i8 9, i8 9, i8 9, i8 9, i8 9, i8 9, i8 9, i8 9, i8 9>
+  %div = udiv <16 x i8> %x, <i8 9, i8 9, i8 9, i8 9, i8 9, i8 9, i8 9, i8 9, i8 9, i8 9, i8 9, i8 9, i8 9, i8 9, i8 9, i8 9>
+  ret <16 x i8> %div
+}
+
+define <8 x i16> @udiv16xi8(<8 x i16> %x) {
+; CHECK-LABEL: 'Cost Model Analysis' for function 'udiv16xi8':
+; CHECK: Found an estimated cost of 9 for instruction:   %div = udiv <8 x i16> %x, <i16 9, i16 9, i16 9, i16 9, i16 9, i16 9, i16 9, i16 9>
+  %div = udiv <8 x i16> %x, <i16 9, i16 9, i16 9, i16 9, i16 9, i16 9, i16 9, i16 9>
+  ret <8 x i16> %div
+}
+
+define <4 x i32> @udiv32xi4(<4 x i32> %x) {
+; CHECK-LABEL: Printing analysis 'Cost Model Analysis' for function 'udiv32xi4':
+; CHECK: Found an estimated cost of 9 for instruction:   %div = udiv <4 x i32> %x, <i32 9, i32 9, i32 9, i32 9>
+  %div = udiv <4 x i32> %x, <i32 9, i32 9, i32 9, i32 9>
+  ret <4 x i32> %div
+}