[X86][LV] i64 divrem loops should prefer tail folding
- Dominant language
- LLVM
- Stars
- 40.5k
- Forks
- 18.7k
- PR merge metrics
- PR metrics pending
Description
https://godbolt.org/z/9TT47ar3s
```c
#include
uint64_t foo(uint64_t *restrict a, uint64_t *restrict b, int n) {
uint64_t x = 0;
for (int i = 0; i < n; i++) {
x += a[i] / b[i];
}
return x;
}
```
current codegen:
```asm
.LCPI0_0:
.quad 0x3ff0000000000000
foo:
test edx, edx
jle .LBB0_1
mov r8d, edx
cmp edx, 4
jae .LBB0_4
xor r9d, r9d
xor ecx, ecx
jmp .LBB0_13
.LBB0_1:
xor ecx, ecx
mov rax, rcx
ret
.LBB0_4:
cmp edx, 32
jae .LBB0_6
xor r9d, r9d
xor ecx, ecx
jmp .LBB0_10
.LBB0_6:
vbroadcastsd zmm1, qword ptr [rip + .LCPI0_0]
mov eax, 6661
mov r9d, r8d
and r9d, 2147483616
vpxor xmm0, xmm0, xmm0
xor ecx, ecx
vpxor xmm2, xmm2, xmm2
vpxor xmm3, xmm3, xmm3
vpxor xmm4, xmm4, xmm4
bextr eax, r8d, eax
shl rax, 8
.LBB0_7:
vmovdqu64 zmm10, zmmword ptr [rsi + rcx]
vmovdqu64 zmm7, zmmword ptr [rdi + rcx]
vmovdqu64 zmm12, zmmword ptr [rsi + rcx + 64]
vmovdqu64 zmm8, zmmword ptr [rdi + rcx + 64]
vmovdqu64 zmm6, zmmword ptr [rsi + rcx + 128]
vmovdqu64 zmm9, zmmword ptr [rdi + rcx + 128]
vmovdqu64 zmm5, zmmword ptr [rdi + rcx + 192]
vcvtuqq2pd zmm11, zmm10, {ru-sae}
vcvtuqq2pd zmm13, zmm7, {rd-sae}
vdivpd zmm11, zmm1, zmm11, {rd-sae}
vmulpd zmm13, zmm13, zmm11, {rd-sae}
vcvtpd2uqq zmm13, zmm13, {rd-sae}
vpmullq zmm14, zmm13, zmm10
vpsubq zmm7, zmm7, zmm14
vcvtuqq2pd zmm14, zmm7, {rd-sae}
vmulpd zmm11, zmm14, zmm11, {rd-sae}
vcvtuqq2pd zmm14, zmm12, {ru-sae}
vcvtpd2uqq zmm11, zmm11, {rd-sae}
vdivpd zmm16, zmm1, zmm14, {rd-sae}
vpmullq zmm15, zmm11, zmm10
vpaddq zmm11, zmm13, zmm11
vpsubq zmm7, zmm7, zmm15
vcvtuqq2pd zmm15, zmm8, {rd-sae}
vpcmpnltuq k0, zmm7, zmm10
vmovdqu64 zmm7, zmmword ptr [rsi + rcx + 192]
add rcx, 256
vpmovm2q zmm13, k0
vpsubq zmm11, zmm11, zmm13
vcvtuqq2pd zmm13, zmm6, {ru-sae}
vpaddq zmm0, zmm11, zmm0
vmulpd zmm14, zmm15, zmm16, {rd-sae}
vcvtpd2uqq zmm14, zmm14, {rd-sae}
vpmullq zmm15, zmm14, zmm12
vpsubq zmm8, zmm8, zmm15
vcvtuqq2pd zmm15, zmm8, {rd-sae}
vmulpd zmm10, zmm15, zmm16, {rd-sae}
vcvtpd2uqq zmm10, zmm10, {rd-sae}
vpaddq zmm11, zmm14, zmm10
vdivpd zmm14, zmm1, zmm13, {rd-sae}
vpmullq zmm10, zmm10, zmm12
vpsubq zmm8, zmm8, zmm10
vcvtuqq2pd zmm10, zmm9, {rd-sae}
vpcmpnltuq k0, zmm8, zmm12
vpmovm2q zmm8, k0
vpsubq zmm8, zmm11, zmm8
vcvtuqq2pd zmm11, zmm7, {ru-sae}
vpaddq zmm2, zmm8, zmm2
vmulpd zmm10, zmm10, zmm14, {rd-sae}
vcvtpd2uqq zmm10, zmm10, {rd-sae}
vpmullq zmm13, zmm10, zmm6
vpsubq zmm9, zmm9, zmm13
vcvtuqq2pd zmm13, zmm9, {rd-sae}
vmulpd zmm8, zmm13, zmm14, {rd-sae}
vcvtpd2uqq zmm8, zmm8, {rd-sae}
vpaddq zmm10, zmm10, zmm8
vpmullq zmm8, zmm8, zmm6
vpsubq zmm8, zmm9, zmm8
vpcmpnltuq k0, zmm8, zmm6
vcvtuqq2pd zmm8, zmm5, {rd-sae}
vpmovm2q zmm6, k0
vpsubq zmm6, zmm10, zmm6
vpaddq zmm3, zmm6, zmm3
vdivpd zmm6, zmm1, zmm11, {rd-sae}
vmulpd zmm8, zmm8, zmm6, {rd-sae}
vcvtpd2uqq zmm8, zmm8, {rd-sae}
vpmullq zmm9, zmm8, zmm7
vpsubq zmm5, zmm5, zmm9
vcvtuqq2pd zmm9, zmm5, {rd-sae}
vmulpd zmm6, zmm9, zmm6, {rd-sae}
vcvtpd2uqq zmm6, zmm6, {rd-sae}
vpaddq zmm8, zmm8, zmm6
vpmullq zmm6, zmm6, zmm7
vpsubq zmm5, zmm5, zmm6
vpcmpnltuq k0, zmm5, zmm7
vpmovm2q zmm5, k0
vpsubq zmm5, zmm8, zmm5
vpaddq zmm4, zmm5, zmm4
cmp rax, rcx
jne .LBB0_7
vpaddq zmm0, zmm2, zmm0
vpaddq zmm0, zmm3, zmm0
vpaddq zmm0, zmm4, zmm0
vextracti64x4 ymm1, zmm0, 1
vpaddq zmm0, zmm0, zmm1
vextracti128 xmm1, ymm0, 1
vpaddq xmm0, xmm0, xmm1
vpshufd xmm1, xmm0, 238
vpaddq xmm0, xmm0, xmm1
vmovq rcx, xmm0
cmp r9d, r8d
je .LBB0_17
test r8b, 28
je .LBB0_13
.LBB0_10:
vbroadcastsd zmm1, qword ptr [rip + .LCPI0_0]
mov rax, r9
mov r9d, r8d
and r9d, 2147483644
vmovq xmm0, rcx
.LBB0_11:
vmovdqu ymm2, ymmword ptr [rsi + 8*rax]
vmovdqu ymm4, ymmword ptr [rdi + 8*rax]
add rax, 4
vcvtuqq2pd zmm3, zmm2, {ru-sae}
vcvtuqq2pd zmm5, zmm4, {rd-sae}
vdivpd zmm3, zmm1, zmm3, {rd-sae}
vmulpd zmm5, zmm5, zmm3, {rd-sae}
vcvtpd2uqq zmm5, zmm5, {rd-sae}
vpmullq ymm6, ymm5, ymm2
vpsubq ymm4, ymm4, ymm6
vcvtuqq2pd zmm6, zmm4, {rd-sae}
vmulpd zmm3, zmm6, zmm3, {rd-sae}
vcvtpd2uqq zmm3, zmm3, {rd-sae}
vpaddq ymm5, ymm5, ymm3
vpmullq ymm3, ymm3, ymm2
vpsubq ymm3, ymm4, ymm3
vpcmpnltuq k0, ymm3, ymm2
vpmovm2q ymm2, k0
vpsubq ymm2, ymm5, ymm2
vpaddq ymm0, ymm2, ymm0
cmp r9, rax
jne .LBB0_11
vextracti128 xmm1, ymm0, 1
vpaddq xmm0, xmm0, xmm1
vpshufd xmm1, xmm0, 238
vpaddq xmm0, xmm0, xmm1
vmovq rcx, xmm0
cmp r9d, r8d
jne .LBB0_13
jmp .LBB0_17
.LBB0_15:
xor edx, edx
div r10
add rcx, rax
inc r9
cmp r8, r9
je .LBB0_17
.LBB0_13:
mov rax, qword ptr [rdi + 8*r9]
mov r10, qword ptr [rsi + 8*r9]
mov rdx, rax
or rdx, r10
shr rdx, 32
jne .LBB0_15
xor edx, edx
div r10d
add rcx, rax
inc r9
cmp r8, r9
jne .LBB0_13
.LBB0_17:
mov rax, rcx
vzeroupper
ret
```
This is very not ideal:
X86's i64 divrem is a long reciprocal approximation sequence based on embedded rounding which is a 512-only feature, so the overhead of v2i64/v4i64 is as high as v8i64, and the throughput of the critical path (vdivpd + 2*vpmullq) is very poor, so vector interleave and epilogue will only significantly increase code size without improving throughput.
But even v2i64 is much faster than scalar, so scalar epilogues should be avoided whenever possible.
with -mllvm -tail-folding-policy=prefer-fold-tail -mllvm -prefer-predicated-reduction-select can get ideal codegen:
```asm
.LCPI0_0:
.quad 0
.quad 1
.quad 2
.quad 3
.quad 4
.quad 5
.quad 6
.quad 7
.LCPI0_1:
.quad 0x3ff0000000000000
.LCPI0_2:
.quad 8
foo:
test edx, edx
jle .LBB0_1
vbroadcastsd zmm3, qword ptr [rip + .LCPI0_1]
vmovdqa64 zmm2, zmmword ptr [rip + .LCPI0_0]
vpbroadcastq zmm4, qword ptr [rip + .LCPI0_2]
mov eax, edx
add edx, 7
dec rax
vpxor xmm1, xmm1, xmm1
shr edx, 3
vpbroadcastq zmm0, rax
xor eax, eax
shl rdx, 6
.LBB0_3:
vpcmpleuq k1, zmm2, zmm0
vpaddq zmm2, zmm2, zmm4
vmovdqu64 zmm5 {k1} {z}, zmmword ptr [rsi + rax]
vmovdqu64 zmm7 {k1} {z}, zmmword ptr [rdi + rax]
add rax, 64
vcvtuqq2pd zmm6, zmm5, {ru-sae}
vcvtuqq2pd zmm8, zmm7, {rd-sae}
vdivpd zmm6, zmm3, zmm6, {rd-sae}
vmulpd zmm8, zmm8, zmm6, {rd-sae}
vcvtpd2uqq zmm8, zmm8, {rd-sae}
vpmullq zmm9, zmm8, zmm5
vpsubq zmm7, zmm7, zmm9
vcvtuqq2pd zmm9, zmm7, {rd-sae}
vmulpd zmm6, zmm9, zmm6, {rd-sae}
vcvtpd2uqq zmm6, zmm6, {rd-sae}
vpaddq zmm8, zmm8, zmm6
vpmullq zmm6, zmm6, zmm5
vpsubq zmm6, zmm7, zmm6
vpcmpnltuq k0, zmm6, zmm5
vpmovm2q zmm5, k0
vpsubq zmm5, zmm8, zmm5
vpaddq zmm1 {k1}, zmm1, zmm5
cmp rdx, rax
jne .LBB0_3
vextracti64x4 ymm0, zmm1, 1
vpaddq zmm0, zmm1, zmm0
vextracti128 xmm1, ymm0, 1
vpaddq xmm0, xmm0, xmm1
vpshufd xmm1, xmm0, 238
vpaddq xmm0, xmm0, xmm1
vmovq rax, xmm0
vzeroupper
ret
.LBB0_1:
xor eax, eax
ret
```
Contributor guide
Assessment
This issue has not been assessed yet.