[X86] Tune bypassing of slow division for Intel CPUs

[n.bozhenov]

Summary

64-bit integer division in Intel CPUs is extremely slow, much slower
than 32-bit division. On the other hand, 8-bit and 16-bit divisions
aren't any faster. The only important exception is Atom where DIV8
is fastest. Because of that, the patch

1. Enables bypassing of 64-bit division for Atom, Silvermont and all big cores.
2. Modifies 64-bit bypassing to use 32-bit division instead of 16-bit one. This doesn't make the shorter division slower but increases chances of taking it. Moreover, it's much more likely to prove at compile-time that a value fits 32 bits and doesn't require a run-time check (e.g. zext i32 to i64).

[n.bozhenov]

This patch is part of a larger patch set:

1. D28196
2. D28197
3. D28198
4. D28199
5. D28200

[jlebar]

I am confused about exactly which CPUs we do and don't want to do this transformation on, but I'll leave that up to people who know something about x86.

[spatel]

cc'ing Simon for AMD knowledge. Based on Agner's tables, it seems like some/most of the AMD uarch's do this in hardware? Ie, the *minimum* reported latency is often the same for 32-bit and 64-bit divides even thought the maximum may be substantially longer for 64-bit. This suggests that the divider unit has some shortcut paths when the operands are determined to fit into a smaller width.

That said, it probably shouldn't hold this patch up because we can always add the feature flag to more CPUs as needed.

[spatel]

Can you update the CHECK lines in both of the test files using utils/update_llc_test_checks.py as a preliminary step ahead of this patch (no review required)? This has 3 benefits:

1. We get tighter checks.
2. It's easier to update the test files for this and future transforms.
3. It's easier to see the diffs induced by this patch.

Note that you'll want to change the RUN lines in atom-bypass-slow-division-64.ll to include a triple ( -mtriple=x86_64-unknown-unknown ) rather than an arch, or you'll probably trigger bot failures.

test/CodeGen/X86/atom-bypass-slow-division-64.ll

6

Is there some reason to choose skylake here rather than sandybridge? If not, I'd prefer SNB because that's the oldest big core where the feature is applied?

test/CodeGen/X86/slow-div.ll

29–43

Add an 'optsize' test for the 64-bit divide too?

[RKSimon]

lib/Target/X86/X86.td

214

Is losing the idivq-to-divw option likely to cause any problems to existing users?

test/CodeGen/X86/atom-bypass-slow-division-64.ll

6

Drop the -march and move the triple in there instead.

[n.bozhenov]

Hi Sanjay,

In D28196#633259, @spatel wrote:

Can you update the CHECK lines in both of the test files using utils/update_llc_test_checks.py as a preliminary step ahead of this patch (no review required)? This has 3 benefits:

1. We get tighter checks.
2. It's easier to update the test files for this and future transforms.
3. It's easier to see the diffs induced by this patch.

Not sure what you mean exactly. Please take a look at D28469. Is it what you mean? Is any additional postprocessing needed after running update_llc_test_checks.py?

[spatel]

In D28196#639731, @n.bozhenov wrote:

Hi Sanjay,

In D28196#633259, @spatel wrote:

Can you update the CHECK lines in both of the test files using utils/update_llc_test_checks.py as a preliminary step ahead of this patch (no review required)? This has 3 benefits:

1. We get tighter checks.
2. It's easier to update the test files for this and future transforms.
3. It's easier to see the diffs induced by this patch.

Not sure what you mean exactly. Please take a look at D28469. Is it what you mean? Is any additional postprocessing needed after running update_llc_test_checks.py?

Yes, that's what I was suggesting in general. Once you have generated the baseline checks with the script, it is very simple to apply your code patch and then run the script again to update the checks.

Usually for small tests like this, we prefer to leave the auto-generated checks as-is (no hand edits), but if you think there is a lot of unnecessary checking with the script, you can remove those lines. Similarly, if the script does not capture some useful info (like loaded constant values), you can add those lines to the auto-generated checks.

[n.bozhenov]

lib/Target/X86/X86.td

214

Is losing the idivq-to-divw option likely to cause any problems to existing users?

Well, in theory it is possible for Atoms, because DIV16 is somewhat faster for them than DIV32. But still DIV64 is way way slower than DIV32, so this change is probably a win even for Atoms because obviously DIV32 can be taken more often than DIV16. For all other Intel architectures (including Silvermont) there's no sense in idivq-to-divw transformation.

test/CodeGen/X86/atom-bypass-slow-division-64.ll

6

Is there some reason to choose skylake here rather than sandybridge?

It doesn't make much difference because in D28197 I change this into -mattr=+idivq-to-divl

6

Drop the -march and move the triple in there instead.

Ok, I will. But what is the difference?

[RKSimon]

test/CodeGen/X86/atom-bypass-slow-division-64.ll

6

Drop the -march and move the triple in there instead.

Ok, I will. But what is the difference?

Triple sets the arch and the abi for you, so just avoids duplication.

[n.bozhenov]

Rebased atom-bypass-slow-division*.ll tests on D28469.

Didn't rebase slow-div.ll because in the next patch I would add several RUN lines into the test which produce similar but not exactly the same assembly. So, I decided to check here only whether the transformation is applied or not.

[n.bozhenov]

test/CodeGen/X86/slow-div.ll

29–43

Such a test is added in D28551 (see bypass-slow-division-tune.ll file)

[spatel]

In D28196#642439, @n.bozhenov wrote:

Rebased atom-bypass-slow-division*.ll tests on D28469.

Didn't rebase slow-div.ll because in the next patch I would add several RUN lines into the test which produce similar but not exactly the same assembly. So, I decided to check here only whether the transformation is applied or not.

Please correct me if I'm wrong, but this patch is now making 2 functional changes, but only testing for the 1st one:

1. Fix the definition of FeatureSlowDivide64 for existing CPUs (Bonnell/Silvermont)
2. Add the FeatureSlowDivide64 to SNB and later big cores

If that's correct, you should remove the 2nd code change from this patch and submit it as a follow-up to this patch with a corresponding test. Alternatively, you could bring the minimum test changes from the other test file back into this patch since that's a small difference. But we don't want to have a functional change with no testing. I know this is a patch series with appropriate testing at the end, but it's important to have the right tests in at every step just in case one or more of those steps needs to be reverted.

[n.bozhenov]

In D28196#642763, @spatel wrote:

In D28196#642439, @n.bozhenov wrote:

Rebased atom-bypass-slow-division*.ll tests on D28469.

Didn't rebase slow-div.ll because in the next patch I would add several RUN lines into the test which produce similar but not exactly the same assembly. So, I decided to check here only whether the transformation is applied or not.

Please correct me if I'm wrong, but this patch is now making 2 functional changes, but only testing for the 1st one:

1. Fix the definition of FeatureSlowDivide64 for existing CPUs (Bonnell/Silvermont)
2. Add the FeatureSlowDivide64 to SNB and later big cores

If that's correct, you should remove the 2nd code change from this patch and submit it as a follow-up to this patch with a corresponding test. Alternatively, you could bring the minimum test changes from the other test file back into this patch since that's a small difference. But we don't want to have a functional change with no testing. I know this is a patch series with appropriate testing at the end, but it's important to have the right tests in at every step just in case one or more of those steps needs to be reverted.

Does it look better now? I have added a Sandy Bridge test into atom-bypass-slow-division-64.ll

[spatel]

LGTM.

lib/Target/X86/X86.td

def FeatureMWAITX  : SubtargetFeature<"mwaitx", "HasMWAITX", "true",
                                       "Enable MONITORX/MWAITX timer functionality">;
 def FeatureMPX     : SubtargetFeature<"mpx", "HasMPX", "true",
                                       "Support MPX instructions">;
 def FeatureLEAForSP : SubtargetFeature<"lea-sp", "UseLeaForSP", "true",
                                      "Use LEA for adjusting the stack pointer">;
 def FeatureSlowDivide32 : SubtargetFeature<"idivl-to-divb",
                                      "HasSlowDivide32", "true",
                                      "Use 8-bit divide for positive values less than 256">;
-def FeatureSlowDivide64 : SubtargetFeature<"idivq-to-divw",
+def FeatureSlowDivide64 : SubtargetFeature<"idivq-to-divl",
                                      "HasSlowDivide64", "true",
-                                     "Use 16-bit divide for positive values less than 65536">;
+                                     "Use 32-bit divide for positive values less than 2^32">;
 def FeaturePadShortFunctions : SubtargetFeature<"pad-short-functions",
                                      "PadShortFunctions", "true",
                                      "Pad short functions">;
 def FeatureINVPCID : SubtargetFeature<"invpcid", "HasInvPCId", "true",
                                       "Invalidate Process-Context Identifier">;
 def FeatureVMFUNC  : SubtargetFeature<"vmfunc", "HasVMFUNC", "true",
                                       "VM Functions">;
 def FeatureSMAP    : SubtargetFeature<"smap", "HasSMAP", "true",

 def SNBFeatures : ProcessorFeatures<[], [
   FeatureX87,
   FeatureMMX,
   FeatureAVX,
   FeatureFXSR,
   FeatureCMPXCHG16B,
   FeaturePOPCNT,
   FeatureAES,
+  FeatureSlowDivide64,
   FeaturePCLMUL,
   FeatureXSAVE,
   FeatureXSAVEOPT,
   FeatureLAHFSAHF,
   FeatureFastScalarFSQRT
 ]>;
 
 class SandyBridgeProc<string Name> : ProcModel<Name, SandyBridgeModel,

lib/Target/X86/X86ISelLowering.cpp

if (Subtarget.isAtom())
     setSchedulingPreference(Sched::ILP);
   else if (Subtarget.is64Bit())
     setSchedulingPreference(Sched::ILP);
   else
     setSchedulingPreference(Sched::RegPressure);
   const X86RegisterInfo *RegInfo = Subtarget.getRegisterInfo();
   setStackPointerRegisterToSaveRestore(RegInfo->getStackRegister());
 
-  // Bypass expensive divides on Atom when compiling with O2.
+  // Bypass expensive divides and use cheaper ones.
   if (TM.getOptLevel() >= CodeGenOpt::Default) {
     if (Subtarget.hasSlowDivide32())
       addBypassSlowDiv(32, 8);
     if (Subtarget.hasSlowDivide64() && Subtarget.is64Bit())
-      addBypassSlowDiv(64, 16);
+      addBypassSlowDiv(64, 32);
   }
 
   if (Subtarget.isTargetKnownWindowsMSVC() ||
       Subtarget.isTargetWindowsItanium()) {
     // Setup Windows compiler runtime calls.
     setLibcallName(RTLIB::SDIV_I64, "_alldiv");
     setLibcallName(RTLIB::UDIV_I64, "_aulldiv");
     setLibcallName(RTLIB::SREM_I64, "_allrem");

lib/Target/X86/X86Subtarget.h

protected:
   /// True if hardware SQRTPS/VSQRTPS instructions are at least as fast
   /// (throughput) as RSQRTPS/VRSQRTPS followed by a Newton-Raphson iteration.
   bool HasFastVectorFSQRT;
 
   /// True if 8-bit divisions are significantly faster than
   /// 32-bit divisions and should be used when possible.
   bool HasSlowDivide32;
 
-  /// True if 16-bit divides are significantly faster than
+  /// True if 32-bit divides are significantly faster than
   /// 64-bit divisions and should be used when possible.
   bool HasSlowDivide64;
 
   /// True if LZCNT instruction is fast.
   bool HasFastLZCNT;
 
   /// True if the short functions should be padded to prevent
   /// a stall when returning too early.

test/CodeGen/X86/atom-bypass-slow-division-64.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc < %s -mcpu=atom -mtriple=x86_64-unknown-linux-gnu | FileCheck %s
 
 ; Additional tests for 64-bit divide bypass
 
 define i64 @Test_get_quotient(i64 %a, i64 %b) nounwind {
 ; CHECK-LABEL: Test_get_quotient:
 ; CHECK:       # BB#0:
 ; CHECK-NEXT:    movq %rdi, %rax
+; CHECK-NEXT:    movabsq $-4294967296, %rcx # imm = 0xFFFFFFFF00000000
 ; CHECK-NEXT:    orq %rsi, %rax
-; CHECK-NEXT:    testq $-65536, %rax # imm = 0xFFFF0000
+; CHECK-NEXT:    testq %rcx, %rax
 ; CHECK-NEXT:    je .LBB0_1
 ; CHECK-NEXT:  # BB#2:
 ; CHECK-NEXT:    movq %rdi, %rax
 ; CHECK-NEXT:    cqto
 ; CHECK-NEXT:    idivq %rsi
 ; CHECK-NEXT:    retq
 ; CHECK-NEXT:  .LBB0_1:
 ; CHECK-NEXT:    xorl %edx, %edx
 ; CHECK-NEXT:    movl %edi, %eax
-; CHECK-NEXT:    divw %si
-; CHECK-NEXT:    movzwl %ax, %eax
+; CHECK-NEXT:    divl %esi
+; CHECK-NEXT:    # kill: %EAX<def> %EAX<kill> %RAX<def>
 ; CHECK-NEXT:    retq
   %result = sdiv i64 %a, %b
   ret i64 %result
 }
 
 define i64 @Test_get_remainder(i64 %a, i64 %b) nounwind {
 ; CHECK-LABEL: Test_get_remainder:
 ; CHECK:       # BB#0:
 ; CHECK-NEXT:    movq %rdi, %rax
+; CHECK-NEXT:    movabsq $-4294967296, %rcx # imm = 0xFFFFFFFF00000000
 ; CHECK-NEXT:    orq %rsi, %rax
-; CHECK-NEXT:    testq $-65536, %rax # imm = 0xFFFF0000
+; CHECK-NEXT:    testq %rcx, %rax
 ; CHECK-NEXT:    je .LBB1_1
 ; CHECK-NEXT:  # BB#2:
 ; CHECK-NEXT:    movq %rdi, %rax
 ; CHECK-NEXT:    cqto
 ; CHECK-NEXT:    idivq %rsi
 ; CHECK-NEXT:    movq %rdx, %rax
 ; CHECK-NEXT:    retq
 ; CHECK-NEXT:  .LBB1_1:
 ; CHECK-NEXT:    xorl %edx, %edx
 ; CHECK-NEXT:    movl %edi, %eax
-; CHECK-NEXT:    divw %si
-; CHECK-NEXT:    movzwl %dx, %eax
+; CHECK-NEXT:    divl %esi
+; CHECK-NEXT:    # kill: %EDX<def> %EDX<kill> %RDX<def>
+; CHECK-NEXT:    movq %rdx, %rax
 ; CHECK-NEXT:    retq
   %result = srem i64 %a, %b
   ret i64 %result
 }
 
 define i64 @Test_get_quotient_and_remainder(i64 %a, i64 %b) nounwind {
 ; CHECK-LABEL: Test_get_quotient_and_remainder:
 ; CHECK:       # BB#0:
 ; CHECK-NEXT:    movq %rdi, %rax
+; CHECK-NEXT:    movabsq $-4294967296, %rcx # imm = 0xFFFFFFFF00000000
 ; CHECK-NEXT:    orq %rsi, %rax
-; CHECK-NEXT:    testq $-65536, %rax # imm = 0xFFFF0000
+; CHECK-NEXT:    testq %rcx, %rax
 ; CHECK-NEXT:    je .LBB2_1
 ; CHECK-NEXT:  # BB#2:
 ; CHECK-NEXT:    movq %rdi, %rax
 ; CHECK-NEXT:    cqto
 ; CHECK-NEXT:    idivq %rsi
 ; CHECK-NEXT:    addq %rdx, %rax
 ; CHECK-NEXT:    retq
 ; CHECK-NEXT:  .LBB2_1:
 ; CHECK-NEXT:    xorl %edx, %edx
 ; CHECK-NEXT:    movl %edi, %eax
-; CHECK-NEXT:    divw %si
-; CHECK-NEXT:    movzwl %ax, %eax
-; CHECK-NEXT:    movzwl %dx, %edx
+; CHECK-NEXT:    divl %esi
+; CHECK-NEXT:    # kill: %EAX<def> %EAX<kill> %RAX<def>
+; CHECK-NEXT:    # kill: %EDX<def> %EDX<kill> %RDX<def>
 ; CHECK-NEXT:    addq %rdx, %rax
 ; CHECK-NEXT:    retq
   %resultdiv = sdiv i64 %a, %b
   %resultrem = srem i64 %a, %b
   %result = add i64 %resultdiv, %resultrem
   ret i64 %result
 }

test/CodeGen/X86/slow-div.ll

 ; RUN: llc -mtriple=x86_64-unknown-linux-gnu -mattr=+idivl-to-divb < %s | FileCheck -check-prefix=DIV32 %s
-; RUN: llc -mtriple=x86_64-unknown-linux-gnu -mattr=+idivq-to-divw < %s | FileCheck -check-prefix=DIV64 %s
+; RUN: llc -mtriple=x86_64-unknown-linux-gnu -mattr=+idivq-to-divl < %s | FileCheck -check-prefix=DIV64 %s
 
 define i32 @div32(i32 %a, i32 %b) {
 entry:
 ; DIV32-LABEL: div32:
 ; DIV32: orl %{{.*}}, [[REG:%[a-z]+]]
 ; DIV32: testl $-256, [[REG]]
 ; DIV32: divb
 ; DIV64-LABEL: div32:
 ; DIV64-NOT: divb
   %div = sdiv i32 %a, %b
   ret i32 %div
 }
 
 define i64 @div64(i64 %a, i64 %b) {
 entry:
 ; DIV32-LABEL: div64:
-; DIV32-NOT: divw
+; DIV32-NOT: divl
 ; DIV64-LABEL: div64:
-; DIV64: orq %{{.*}}, [[REG:%[a-z]+]]
-; DIV64: testq   $-65536, [[REG]]
-; DIV64: divw
+; DIV64-DAG: movabsq $-4294967296, [[REGMSK:%[a-z]+]]
+; DIV64-DAG: orq %{{.*}}, [[REG:%[a-z]+]]
+; DIV64: testq [[REGMSK]], [[REG]]
+; DIV64: divl
   %div = sdiv i64 %a, %b
   ret i64 %div
 }
 
 ; Verify that no extra code is generated when optimizing for size.
 
 define i32 @div32_optsize(i32 %a, i32 %b) optsize {
 ; DIV32-LABEL: div32_optsize:
 ; DIV32-NOT: divb
   %div = sdiv i32 %a, %b
   ret i32 %div
 }
 
 define i32 @div32_minsize(i32 %a, i32 %b) minsize {
 ; DIV32-LABEL: div32_minsize:
 ; DIV32-NOT: divb
   %div = sdiv i32 %a, %b
   ret i32 %div
 }