| Issue |
241242
|
| Summary |
[X86][AVX512] use VBMI lookup table method for v64i8 division
|
| Labels |
backend:X86,
missed-optimization
|
| Assignees |
|
| Reporter |
Andarwinux
|
https://hugeonotation.github.io/pblog/2023/04/29/uint8_division_using_avx512.html
https://github.com/Avereniect/AVEL/blob/master/include/avel/impl/vectors/Vec64x8u.hpp#L1050-L1169
https://godbolt.org/z/PocGdaEKW
```c++
typedef uint8_t vec64x8u [[clang::ext_vector_type(64)]];
struct div_type {
vec64x8u quot;
vec64x8u rem;
};
static inline div_type div(vec64x8u x, vec64x8u y) {
// This approach fundamentally takes the same approach as Denom64x8u.
// Using a lookup table is fast enough to beat the long-division
// approach under the assumption that the table is already cached
//Special thanks to u/YumiYumiYumi
alignas(64) static constexpr std::uint8_t recip_hi_table_data[128] {
0x00, 0x80, 0x55, 0x40, 0x33, 0x2a, 0x24, 0x20,
0x1c, 0x19, 0x17, 0x15, 0x13, 0x12, 0x11, 0x10,
0x0f, 0x0e, 0x0d, 0x0c, 0x0c, 0x0b, 0x0b, 0x0a,
0x0a, 0x09, 0x09, 0x09, 0x08, 0x08, 0x08, 0x08,
0x07, 0x07, 0x07, 0x07, 0x06, 0x06, 0x06, 0x06,
0x06, 0x06, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
0x05, 0x05, 0x05, 0x04, 0x04, 0x04, 0x04, 0x04,
0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
0x03, 0x03, 0x03, 0x03, 0x03, 0x02, 0x02, 0x02,
0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02
};
alignas(64) static constexpr std::uint8_t recip_lo_table_data[256] {
0x00, 0x00, 0x56, 0x00, 0x34, 0xab, 0x93, 0x00,
0x72, 0x9a, 0x46, 0x56, 0xb2, 0x4a, 0x12, 0x00,
0x10, 0x39, 0x7a, 0xcd, 0x31, 0xa3, 0x22, 0xab,
0x3e, 0xd9, 0x7c, 0x25, 0xd4, 0x89, 0x43, 0x00,
0xc2, 0x88, 0x51, 0x1d, 0xec, 0xbd, 0x91, 0x67,
0x3f, 0x19, 0xf5, 0xd2, 0xb1, 0x91, 0x73, 0x56,
0x3a, 0x1f, 0x06, 0xed, 0xd5, 0xbe, 0xa8, 0x93,
0x7e, 0x6a, 0x57, 0x45, 0x33, 0x22, 0x11, 0x00,
0xf1, 0xe1, 0xd3, 0xc4, 0xb6, 0xa9, 0x9c, 0x8f,
0x82, 0x76, 0x6a, 0x5f, 0x54, 0x49, 0x3e, 0x34,
0x2a, 0x20, 0x16, 0x0d, 0x04, 0xfb, 0xf2, 0xe9,
0xe1, 0xd9, 0xd1, 0xc9, 0xc1, 0xba, 0xb2, 0xab,
0xa4, 0x9d, 0x96, 0x90, 0x89, 0x83, 0x7d, 0x77,
0x71, 0x6b, 0x65, 0x5f, 0x5a, 0x54, 0x4f, 0x4a,
0x44, 0x3f, 0x3a, 0x35, 0x31, 0x2c, 0x27, 0x23,
0x1e, 0x1a, 0x15, 0x11, 0x0d, 0x09, 0x05, 0x00,
0xfd, 0xf9, 0xf5, 0xf1, 0xed, 0xea, 0xe6, 0xe2,
0xdf, 0xdb, 0xd8, 0xd5, 0xd1, 0xce, 0xcb, 0xc8,
0xc4, 0xc1, 0xbe, 0xbb, 0xb8, 0xb5, 0xb3, 0xb0,
0xad, 0xaa, 0xa7, 0xa5, 0xa2, 0x9f, 0x9d, 0x9a,
0x98, 0x95, 0x93, 0x90, 0x8e, 0x8b, 0x89, 0x87,
0x84, 0x82, 0x80, 0x7e, 0x7b, 0x79, 0x77, 0x75,
0x73, 0x71, 0x6f, 0x6d, 0x6b, 0x69, 0x67, 0x65,
0x63, 0x61, 0x5f, 0x5d, 0x5b, 0x59, 0x58, 0x56,
0x54, 0x52, 0x51, 0x4f, 0x4d, 0x4b, 0x4a, 0x48,
0x47, 0x45, 0x43, 0x42, 0x40, 0x3f, 0x3d, 0x3c,
0x3a, 0x39, 0x37, 0x36, 0x34, 0x33, 0x31, 0x30,
0x2f, 0x2d, 0x2c, 0x2a, 0x29, 0x28, 0x26, 0x25,
0x24, 0x22, 0x21, 0x20, 0x1f, 0x1d, 0x1c, 0x1b,
0x1a, 0x19, 0x17, 0x16, 0x15, 0x14, 0x13, 0x12,
0x10, 0x0f, 0x0e, 0x0d, 0x0c, 0x0b, 0x0a, 0x09,
0x08, 0x07, 0x06, 0x05, 0x04, 0x03, 0x02, 0x00
};
__m512i recip_hi0 = _mm512_load_si512(recip_hi_table_data + 0);
__m512i recip_hi1 = _mm512_load_si512(recip_hi_table_data + 64);
__m512i recip_lo0 = _mm512_load_si512(recip_lo_table_data + 0);
__m512i recip_lo1 = _mm512_load_si512(recip_lo_table_data + 64);
__m512i recip_lo2 = _mm512_load_si512(recip_lo_table_data + 128);
__m512i recip_lo3 = _mm512_load_si512(recip_lo_table_data + 192);
__m512i byte_mask = _mm512_set1_epi16(0x00FF);
__m512i _one_ = _mm512_set1_epi8(1);
// Don't care about y == 0
__m512i z = _mm512_sub_epi8((y), one);
__mmask64 high_bit_mask = _mm512_movepi8_mask(z);
// Lookup low/high reciprocal halves
__m512i recip_hi = _mm512_mask_blend_epi8(
high_bit_mask,
_mm512_permutex2var_epi8(recip_hi0, z, recip_hi1),
one
);
__m512i recip_lo = _mm512_mask_blend_epi8(
high_bit_mask,
_mm512_permutex2var_epi8(recip_lo0, z, recip_lo1),
_mm512_permutex2var_epi8(recip_lo2, z, recip_lo3)
);
// Construct 16-bit reciprocal
__m512i zeros = _mm512_setzero_si512();
__m512i reciprocals_lo = _mm512_unpacklo_epi8(recip_lo, recip_hi);
__m512i reciprocals_hi = _mm512_unpackhi_epi8(recip_lo, recip_hi);
__m512i x_lo = _mm512_unpacklo_epi8((x), zeros);
__m512i x_hi = _mm512_unpackhi_epi8((x), zeros);
// Compute quotient
__m512i quotient_lo = _mm512_mulhi_epu16(x_lo, reciprocals_lo);
__m512i quotient_hi = _mm512_mulhi_epu16(x_hi, reciprocals_hi);
__m512i quotient = _mm512_packus_epi16(quotient_lo, quotient_hi);
// Handle division by 1
__mmask64 is_denom_one = _mm512_testn_epi8_mask(z, z);
quotient = _mm512_mask_blend_epi8(is_denom_one, quotient, (x));
// Construct remainder
__m512i y_lo = _mm512_unpacklo_epi8((y), zeros);
__m512i y_hi = _mm512_unpackhi_epi8((y), zeros);
__m512i tmp_lo = _mm512_mullo_epi16(quotient_lo, y_lo);
__m512i tmp_hi = _mm512_mullo_epi16(quotient_hi, y_hi);
__m512i r = _mm512_maskz_sub_epi8(_knot_mask64(is_denom_one), (x), _mm512_packus_epi16(tmp_lo, tmp_hi));
return {quotient, r};
}
vec64x8u div7_vbmi(vec64x8u x) {
return div(x,7).quot;
}
vec64x8u div7_native(vec64x8u x) {
return x / 7;
}
vec64x8u div_vbmi(vec64x8u x, vec64x8u y) {
return div(x,y).quot;
}
vec64x8u div_native(vec64x8u x, vec64x8u y) {
return x / y;
}
vec64x8u rem7_vbmi(vec64x8u x) {
return div(x,7).rem;
}
vec64x8u rem7_native(vec64x8u x) {
return x % 7;
}
vec64x8u rem_vbmi(vec64x8u x, vec64x8u y) {
return div(x,y).rem;
}
vec64x8u rem_native(vec64x8u x, vec64x8u y) {
return x % y;
}
```
```asm
div7_vbmi(unsigned char vector[64]):
vpxor xmm1, xmm1, xmm1
vpunpcklbw zmm2, zmm0, zmm1
vpunpckhbw zmm0, zmm0, zmm1
vmovdqa64 zmm1, zmmword ptr [rip + .LCPI0_0]
vpmulhuw zmm2, zmm2, zmm1
vpmulhuw zmm0, zmm0, zmm1
vpackuswb zmm0, zmm2, zmm0
ret
div7_native(unsigned char vector[64]):
vpxor xmm1, xmm1, xmm1
vpunpckhbw zmm2, zmm0, zmm1
vpbroadcastw zmm3, word ptr [rip + .LCPI1_0]
vpmullw zmm2, zmm2, zmm3
vpsrlw zmm2, zmm2, 8
vpunpcklbw zmm1, zmm0, zmm1
vpmullw zmm1, zmm1, zmm3
vpsrlw zmm1, zmm1, 8
vpackuswb zmm1, zmm1, zmm2
vpsubb zmm0, zmm0, zmm1
vgf2p8affineqb zmm0, zmm0, qword ptr [rip + .LCPI1_3]{1to8}, 0
vpaddb zmm0, zmm0, zmm1
vgf2p8affineqb zmm0, zmm0, qword ptr [rip + .LCPI1_4]{1to8}, 0
ret
div_vbmi(unsigned char vector[64], unsigned char vector[64]):
vpternlogd zmm2, zmm2, zmm2, 255
vpaddb zmm2, zmm1, zmm2
vpmovb2m k1, zmm2
vmovdqa64 zmm1, zmmword ptr [rip + .LCPI2_0]
vpermt2b zmm1, zmm2, zmmword ptr [rip + .LCPI2_1]
vpxor xmm3, xmm3, xmm3
vmovdqu8 zmm1 {k1}, zmmword ptr [rip + .LCPI2_2]
vmovdqa64 zmm4, zmmword ptr [rip + .LCPI2_3]
vpermt2b zmm4, zmm2, zmmword ptr [rip + .LCPI2_4]
vmovdqa64 zmm5, zmmword ptr [rip + .LCPI2_5]
vpermt2b zmm5, zmm2, zmmword ptr [rip + .LCPI2_6]
vmovdqu8 zmm4 {k1}, zmm5
vpunpcklbw zmm5, zmm4, zmm1
vpunpckhbw zmm1, zmm4, zmm1
vpunpcklbw zmm4, zmm0, zmm3
vpmulhuw zmm4, zmm4, zmm5
vpunpckhbw zmm3, zmm0, zmm3
vpmulhuw zmm1, zmm3, zmm1
vpackuswb zmm1, zmm4, zmm1
vptestnmb k1, zmm2, zmm2
vmovdqu8 zmm1 {k1}, zmm0
vmovdqa64 zmm0, zmm1
ret
div_native(unsigned char vector[64], unsigned char vector[64]):
vextracti64x4 ymm2, zmm1, 1
vpmovzxbd zmm3, xmm2
vcvtdq2ps zmm3, zmm3
vextracti64x4 ymm4, zmm0, 1
vpmovzxbd zmm5, xmm4
vcvtdq2ps zmm5, zmm5
vdivps zmm3, zmm5, zmm3
vcvttps2dq zmm3, zmm3
vpmovdb xmm3, zmm3
vextracti128 xmm2, ymm2, 1
vpmovzxbd zmm2, xmm2
vcvtdq2ps zmm2, zmm2
vextracti128 xmm4, ymm4, 1
vpmovzxbd zmm4, xmm4
vcvtdq2ps zmm4, zmm4
vdivps zmm2, zmm4, zmm2
vcvttps2dq zmm2, zmm2
vpmovdb xmm2, zmm2
vinserti128 ymm2, ymm3, xmm2, 1
vpmovzxbd zmm3, xmm1
vcvtdq2ps zmm3, zmm3
vpmovzxbd zmm4, xmm0
vcvtdq2ps zmm4, zmm4
vdivps zmm3, zmm4, zmm3
vcvttps2dq zmm3, zmm3
vpmovdb xmm3, zmm3
vextracti128 xmm1, ymm1, 1
vpmovzxbd zmm1, xmm1
vcvtdq2ps zmm1, zmm1
vextracti128 xmm0, ymm0, 1
vpmovzxbd zmm0, xmm0
vcvtdq2ps zmm0, zmm0
vdivps zmm0, zmm0, zmm1
vcvttps2dq zmm0, zmm0
vpmovdb xmm0, zmm0
vinserti128 ymm0, ymm3, xmm0, 1
vinserti64x4 zmm0, zmm0, ymm2, 1
ret
rem7_vbmi(unsigned char vector[64]):
vpxor xmm1, xmm1, xmm1
vpunpcklbw zmm2, zmm0, zmm1
vpunpckhbw zmm1, zmm0, zmm1
vmovdqa64 zmm3, zmmword ptr [rip + .LCPI4_0]
vpmulhuw zmm2, zmm2, zmm3
vpmulhuw zmm1, zmm1, zmm3
vpsllw zmm3, zmm2, 3
vpsubw zmm2, zmm3, zmm2
vpsllw zmm3, zmm1, 3
vpsubw zmm1, zmm3, zmm1
vpackuswb zmm1, zmm2, zmm1
vpsubb zmm0, zmm0, zmm1
ret
rem7_native(unsigned char vector[64]):
vpxor xmm1, xmm1, xmm1
vpunpckhbw zmm2, zmm0, zmm1
vpbroadcastw zmm3, word ptr [rip + .LCPI5_0]
vpmullw zmm2, zmm2, zmm3
vpsrlw zmm2, zmm2, 8
vpunpcklbw zmm1, zmm0, zmm1
vpmullw zmm1, zmm1, zmm3
vpsrlw zmm1, zmm1, 8
vpackuswb zmm1, zmm1, zmm2
vpsubb zmm2, zmm0, zmm1
vgf2p8affineqb zmm2, zmm2, qword ptr [rip + .LCPI5_4]{1to8}, 0
vpaddb zmm1, zmm2, zmm1
vgf2p8affineqb zmm2, zmm1, qword ptr [rip + .LCPI5_5]{1to8}, 0
vgf2p8affineqb zmm1, zmm1, qword ptr [rip + .LCPI5_6]{1to8}, 0
vpsubb zmm1, zmm1, zmm2
vpaddb zmm0, zmm0, zmm1
ret
rem_vbmi(unsigned char vector[64], unsigned char vector[64]):
vpternlogd zmm2, zmm2, zmm2, 255
vpaddb zmm2, zmm1, zmm2
vpmovb2m k1, zmm2
vpxor xmm3, xmm3, xmm3
vmovdqa64 zmm4, zmmword ptr [rip + .LCPI6_0]
vpermt2b zmm4, zmm2, zmmword ptr [rip + .LCPI6_1]
vmovdqa64 zmm5, zmmword ptr [rip + .LCPI6_3]
vpermt2b zmm5, zmm2, zmmword ptr [rip + .LCPI6_4]
vmovdqu8 zmm4 {k1}, zmmword ptr [rip + .LCPI6_2]
vmovdqa64 zmm6, zmmword ptr [rip + .LCPI6_5]
vpermt2b zmm6, zmm2, zmmword ptr [rip + .LCPI6_6]
vmovdqu8 zmm5 {k1}, zmm6
vpunpcklbw zmm6, zmm5, zmm4
vpunpckhbw zmm4, zmm5, zmm4
vpunpcklbw zmm5, zmm0, zmm3
vpmulhuw zmm5, zmm5, zmm6
vpunpckhbw zmm6, zmm0, zmm3
vpmulhuw zmm4, zmm6, zmm4
vptestmb k1, zmm2, zmm2
vpunpcklbw zmm2, zmm1, zmm3
vpmullw zmm2, zmm5, zmm2
vpunpckhbw zmm1, zmm1, zmm3
vpmullw zmm1, zmm4, zmm1
vpackuswb zmm1, zmm2, zmm1
vpsubb zmm0 {k1} {z}, zmm0, zmm1
ret
rem_native(unsigned char vector[64], unsigned char vector[64]):
vextracti64x4 ymm2, zmm1, 1
vpmovzxbd zmm3, xmm2
vcvtdq2ps zmm3, zmm3
vextracti64x4 ymm4, zmm0, 1
vpmovzxbd zmm5, xmm4
vcvtdq2ps zmm5, zmm5
vdivps zmm3, zmm5, zmm3
vcvttps2dq zmm3, zmm3
vpmovdb xmm3, zmm3
vextracti128 xmm2, ymm2, 1
vpmovzxbd zmm2, xmm2
vcvtdq2ps zmm2, zmm2
vextracti128 xmm4, ymm4, 1
vpmovzxbd zmm4, xmm4
vcvtdq2ps zmm4, zmm4
vdivps zmm2, zmm4, zmm2
vcvttps2dq zmm2, zmm2
vpmovdb xmm2, zmm2
vinserti128 ymm2, ymm3, xmm2, 1
vpmovzxbd zmm3, xmm1
vcvtdq2ps zmm3, zmm3
vpmovzxbd zmm4, xmm0
vcvtdq2ps zmm4, zmm4
vdivps zmm3, zmm4, zmm3
vcvttps2dq zmm3, zmm3
vpmovdb xmm3, zmm3
vextracti128 xmm4, ymm1, 1
vpmovzxbd zmm4, xmm4
vcvtdq2ps zmm4, zmm4
vextracti128 xmm5, ymm0, 1
vpmovzxbd zmm5, xmm5
vcvtdq2ps zmm5, zmm5
vdivps zmm4, zmm5, zmm4
vcvttps2dq zmm4, zmm4
vpmovdb xmm4, zmm4
vinserti128 ymm3, ymm3, xmm4, 1
vinserti64x4 zmm2, zmm3, ymm2, 1
vpandd zmm3, zmm1, dword ptr [rip + .LCPI7_2]{1to16}
vpmaddubsw zmm3, zmm2, zmm3
vpmullw zmm1, zmm2, zmm1
vmovdqa64 zmm2, zmmword ptr [rip + .LCPI7_1]
vpermi2b zmm2, zmm1, zmm3
vpsubb zmm0, zmm0, zmm2
ret
```
Surprisingly, this method even works better than DAG codegen for constant divisors.
_______________________________________________
llvm-bugs mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-bugs