[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

7 ↗

(On Diff #137467)

Show the actual numbers instead of a regex?

[evandro]

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

7 ↗

(On Diff #137467)

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.
+      // Conservatively assume OP_None.
+      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 a 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/vdiv.ll

+; RUN: opt < %s -O3 -debug-only=loop-vectorize 2> %t; FileCheck %s --input-file %t 
+
+; CHECK: LV: Scalar loop            costs: {{[0-9]}}.
+; CHECK: LV: Vector loop of width 2 costs: {{[0-9]+}}.
+; CHECK: LV: Vector loop of width 4 costs: {{[0-9]+}}.
+; CHECK: LV: Selecting VF: 1.
+
+target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
+target triple = "aarch64--linux-gnu"
+
+define void @scale(i32* noalias nocapture %p, i32* noalias nocapture readonly %scale, i32 %width) #0 {
+entry:
+  %cmp = icmp ugt i32 %width, 3
+  %rem = and i32 %width, 3
+  %cmp1 = icmp eq i32 %rem, 0
+  %or.cond17 = and i1 %cmp, %cmp1
+  br i1 %or.cond17, label %for.body.preheader, label %for.end
+
+for.body.preheader:                               ; preds = %entry
+  %wide.trip.count = zext i32 %width to i64
+  br label %for.body
+
+for.body:                                         ; preds = %for.body, %for.body.preheader
+  %indvars.iv = phi i64 [ 0, %for.body.preheader ], [ %indvars.iv.next, %for.body ]
+  %arrayidx = getelementptr inbounds i32, i32* %p, i64 %indvars.iv
+  %0 = load i32, i32* %arrayidx, align 4, !tbaa !2
+  %arrayidx4 = getelementptr inbounds i32, i32* %scale, i64 %indvars.iv
+  %1 = load i32, i32* %arrayidx4, align 4, !tbaa !2
+  %div = sdiv i32 %0, %1
+  store i32 %div, i32* %arrayidx, align 4, !tbaa !2
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond = icmp eq i64 %indvars.iv.next, %wide.trip.count
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:                                          ; preds = %for.body, %entry
+  ret void
+}
+
+attributes #0 = { norecurse nounwind }
+
+!2 = !{!3, !3, i64 0}
+!3 = !{!"int", !4, i64 0}
+!4 = !{!"omnipotent char", !5, i64 0}
+!5 = !{!"Simple C/C++ TBAA"}