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

Reply via email to