diff mbox series

[v1,1/2] x86: Optimize L(less_vec) case in memcmp-evex-movbe.S

Message ID 20211225032257.2887327-1-goldstein.w.n@gmail.com
State New
Headers show
Series [v1,1/2] x86: Optimize L(less_vec) case in memcmp-evex-movbe.S | expand

Commit Message

Noah Goldstein Dec. 25, 2021, 3:22 a.m. UTC 
No bug.
Optimizations are twofold.

1) Replace page cross and 0/1 checks with masked load instructions in
   L(less_vec). In applications this reduces branch-misses in the
   hot [0, 32] case.
2) Change controlflow so that L(less_vec) case gets the fall through.

Change 2) helps copies in the [0, 32] size range but comes at the cost
of copies in the [33, 64] size range.  From profiles of GCC and
Python3, 94%+ and 99%+ of calls are in the [0, 32] range so this
appears to the the right tradeoff.
---
 sysdeps/x86_64/multiarch/memcmp-evex-movbe.S | 249 +++++--------------
 1 file changed, 56 insertions(+), 193 deletions(-)

Comments

Noah Goldstein Dec. 25, 2021, 3:24 a.m. UTC | #1 
On Fri, Dec 24, 2021 at 9:23 PM Noah Goldstein <goldstein.w.n@gmail.com> wrote:
>
> No bug.
> Optimizations are twofold.
>
> 1) Replace page cross and 0/1 checks with masked load instructions in
>    L(less_vec). In applications this reduces branch-misses in the
>    hot [0, 32] case.
> 2) Change controlflow so that L(less_vec) case gets the fall through.
>
> Change 2) helps copies in the [0, 32] size range but comes at the cost
> of copies in the [33, 64] size range.  From profiles of GCC and
> Python3, 94%+ and 99%+ of calls are in the [0, 32] range so this
> appears to the the right tradeoff.
> ---
>  sysdeps/x86_64/multiarch/memcmp-evex-movbe.S | 249 +++++--------------
>  1 file changed, 56 insertions(+), 193 deletions(-)
>
> diff --git a/sysdeps/x86_64/multiarch/memcmp-evex-movbe.S b/sysdeps/x86_64/multiarch/memcmp-evex-movbe.S
> index 640f6757fa..d2899e7c70 100644
> --- a/sysdeps/x86_64/multiarch/memcmp-evex-movbe.S
> +++ b/sysdeps/x86_64/multiarch/memcmp-evex-movbe.S
> @@ -62,15 +62,18 @@ Latency:
>  # define VMOVU         vmovdqu64
>
>  # ifdef USE_AS_WMEMCMP
> +#  define VMOVU_MASK   vmovdqu32
>  #  define CHAR_SIZE    4
>  #  define VPCMP        vpcmpd
>  #  define VPTEST       vptestmd
>  # else
> +#  define VMOVU_MASK   vmovdqu8
>  #  define CHAR_SIZE    1
>  #  define VPCMP        vpcmpub
>  #  define VPTEST       vptestmb
>  # endif
>
> +
>  # define VEC_SIZE      32
>  # define PAGE_SIZE     4096
>  # define CHAR_PER_VEC  (VEC_SIZE / CHAR_SIZE)
> @@ -102,12 +105,48 @@ ENTRY_P2ALIGN (MEMCMP, 6)
>         movl    %edx, %edx
>  # endif
>         cmp     $CHAR_PER_VEC, %RDX_LP
> -       jb      L(less_vec)
> +       /* Fall through for [0, VEC_SIZE] as its the hottest.  */
> +       ja      L(more_1x_vec)
> +
> +       /* Create mask for CHAR's we want to compare. This allows us to
> +          avoid having to include page cross logic.  */
> +       movl    $-1, %ecx
> +       bzhil   %edx, %ecx, %ecx
> +       kmovd   %ecx, %k2
> +
> +       /* Safe to load full ymm with mask.  */
> +       VMOVU_MASK (%rsi), %YMM2{%k2}
> +       VPCMP   $4,(%rdi), %YMM2, %k1{%k2}
> +       kmovd   %k1, %eax
> +       testl   %eax, %eax
> +       jnz     L(return_vec_0)
> +       ret
>
> +       .p2align 4
> +L(return_vec_0):
> +       tzcntl  %eax, %eax
> +# ifdef USE_AS_WMEMCMP
> +       movl    (%rdi, %rax, CHAR_SIZE), %ecx
> +       xorl    %edx, %edx
> +       cmpl    (%rsi, %rax, CHAR_SIZE), %ecx
> +       /* NB: no partial register stall here because xorl zero idiom
> +          above.  */
> +       setg    %dl
> +       leal    -1(%rdx, %rdx), %eax
> +# else
> +       movzbl  (%rsi, %rax), %ecx
> +       movzbl  (%rdi, %rax), %eax
> +       subl    %ecx, %eax
> +# endif
> +       ret
> +
> +
> +       .p2align 4
> +L(more_1x_vec):
>         /* From VEC to 2 * VEC.  No branch when size == VEC_SIZE.  */
>         VMOVU   (%rsi), %YMM1
>         /* Use compare not equals to directly check for mismatch.  */
> -       VPCMP   $4, (%rdi), %YMM1, %k1
> +       VPCMP   $4,(%rdi), %YMM1, %k1
>         kmovd   %k1, %eax
>         /* NB: eax must be destination register if going to
>            L(return_vec_[0,2]). For L(return_vec_3) destination register
> @@ -131,13 +170,13 @@ ENTRY_P2ALIGN (MEMCMP, 6)
>
>         /* Check third and fourth VEC no matter what.  */
>         VMOVU   (VEC_SIZE * 2)(%rsi), %YMM3
> -       VPCMP   $4, (VEC_SIZE * 2)(%rdi), %YMM3, %k1
> +       VPCMP   $4,(VEC_SIZE * 2)(%rdi), %YMM3, %k1
>         kmovd   %k1, %eax
>         testl   %eax, %eax
>         jnz     L(return_vec_2)
>
>         VMOVU   (VEC_SIZE * 3)(%rsi), %YMM4
> -       VPCMP   $4, (VEC_SIZE * 3)(%rdi), %YMM4, %k1
> +       VPCMP   $4,(VEC_SIZE * 3)(%rdi), %YMM4, %k1
>         kmovd   %k1, %ecx
>         testl   %ecx, %ecx
>         jnz     L(return_vec_3)
> @@ -169,7 +208,7 @@ ENTRY_P2ALIGN (MEMCMP, 6)
>         VMOVU   (VEC_SIZE * 3)(%rsi), %YMM4
>         /* Ternary logic to xor (VEC_SIZE * 3)(%rdi) with YMM4 while
>            oring with YMM1. Result is stored in YMM4.  */
> -       vpternlogd $0xde, (VEC_SIZE * 3)(%rdi), %YMM1, %YMM4
> +       vpternlogd $0xde,(VEC_SIZE * 3)(%rdi), %YMM1, %YMM4
>
>         /* Or together YMM2, YMM3, and YMM4 into YMM4.  */
>         vpternlogd $0xfe, %YMM2, %YMM3, %YMM4
> @@ -184,7 +223,8 @@ ENTRY_P2ALIGN (MEMCMP, 6)
>         /* NB: eax must be zero to reach here.  */
>         ret
>
> -       .p2align 4
> +
> +       .p2align 4,, 8
>  L(8x_end_return_vec_0_1_2_3):
>         movq    %rdx, %rdi
>  L(8x_return_vec_0_1_2_3):
> @@ -222,23 +262,6 @@ L(return_vec_3):
>  # endif
>         ret
>
> -       .p2align 4
> -L(return_vec_0):
> -       tzcntl  %eax, %eax
> -# ifdef USE_AS_WMEMCMP
> -       movl    (%rdi, %rax, CHAR_SIZE), %ecx
> -       xorl    %edx, %edx
> -       cmpl    (%rsi, %rax, CHAR_SIZE), %ecx
> -       /* NB: no partial register stall here because xorl zero idiom
> -          above.  */
> -       setg    %dl
> -       leal    -1(%rdx, %rdx), %eax
> -# else
> -       movzbl  (%rsi, %rax), %ecx
> -       movzbl  (%rdi, %rax), %eax
> -       subl    %ecx, %eax
> -# endif
> -       ret
>
>         .p2align 4
>  L(return_vec_1):
> @@ -297,7 +320,7 @@ L(loop_4x_vec):
>         VMOVU   (VEC_SIZE * 2)(%rsi, %rdi), %YMM3
>         vpxorq  (VEC_SIZE * 2)(%rdi), %YMM3, %YMM3
>         VMOVU   (VEC_SIZE * 3)(%rsi, %rdi), %YMM4
> -       vpternlogd $0xde, (VEC_SIZE * 3)(%rdi), %YMM1, %YMM4
> +       vpternlogd $0xde,(VEC_SIZE * 3)(%rdi), %YMM1, %YMM4
>         vpternlogd $0xfe, %YMM2, %YMM3, %YMM4
>         VPTEST  %YMM4, %YMM4, %k1
>         kmovd   %k1, %ecx
> @@ -324,7 +347,7 @@ L(loop_4x_vec):
>         VMOVU   VEC_SIZE(%rsi, %rdx), %YMM2
>         vpxorq  VEC_SIZE(%rdx), %YMM2, %YMM2
>         VMOVU   (VEC_SIZE * 3)(%rsi, %rdx), %YMM4
> -       vpternlogd $0xde, (VEC_SIZE * 3)(%rdx), %YMM1, %YMM4
> +       vpternlogd $0xde,(VEC_SIZE * 3)(%rdx), %YMM1, %YMM4
>         vpternlogd $0xfe, %YMM2, %YMM3, %YMM4
>         VPTEST  %YMM4, %YMM4, %k1
>         kmovd   %k1, %ecx
> @@ -336,14 +359,14 @@ L(loop_4x_vec):
>         /* Only entry is from L(more_8x_vec).  */
>         .p2align 4,, 10
>  L(8x_last_2x_vec):
> -       VPCMP   $4, (VEC_SIZE * 2)(%rdx), %YMM3, %k1
> +       VPCMP   $4,(VEC_SIZE * 2)(%rdx), %YMM3, %k1
>         kmovd   %k1, %eax
>         testl   %eax, %eax
>         jnz     L(8x_return_vec_2)
>         /* Naturally aligned to 16 bytes.  */
>  L(8x_last_1x_vec):
>         VMOVU   (VEC_SIZE * 3)(%rsi, %rdx), %YMM1
> -       VPCMP   $4, (VEC_SIZE * 3)(%rdx), %YMM1, %k1
> +       VPCMP   $4,(VEC_SIZE * 3)(%rdx), %YMM1, %k1
>         kmovd   %k1, %eax
>         testl   %eax, %eax
>         jnz     L(8x_return_vec_3)
> @@ -392,7 +415,9 @@ L(last_1x_vec):
>         jnz     L(return_vec_0_end)
>         ret
>
> -       .p2align 4,, 10
> +
> +       /* Don't align. Takes 2-fetch blocks either way and aligning
> +          will cause code to spill into another cacheline.  */
>  L(return_vec_1_end):
>         /* Use bsf to save code size. This is necessary to have
>            L(one_or_less) fit in aligning bytes between.  */
> @@ -411,31 +436,8 @@ L(return_vec_1_end):
>  # endif
>         ret
>
> -       /* NB: L(one_or_less) fits in alignment padding between
> -          L(return_vec_1_end) and L(return_vec_0_end).  */
> -# ifdef USE_AS_WMEMCMP
> -L(one_or_less):
> -       jb      L(zero)
> -       movl    (%rdi), %ecx
> -       xorl    %edx, %edx
> -       cmpl    (%rsi), %ecx
> -       je      L(zero)
> -       setg    %dl
> -       leal    -1(%rdx, %rdx), %eax
> -       ret
> -# else
> -L(one_or_less):
> -       jb      L(zero)
> -       movzbl  (%rsi), %ecx
> -       movzbl  (%rdi), %eax
> -       subl    %ecx, %eax
> -       ret
> -# endif
> -L(zero):
> -       xorl    %eax, %eax
> -       ret
> -
> -       .p2align 4
> +       /* Don't align. Takes 2-fetch blocks either way and aligning
> +          will cause code to spill into another cacheline.  */
>  L(return_vec_0_end):
>         tzcntl  %eax, %eax
>         addl    %edx, %eax
> @@ -451,146 +453,7 @@ L(return_vec_0_end):
>         subl    %ecx, %eax
>  # endif
>         ret
> +       /* 1-byte until next cache line.  */
>
> -       .p2align 4
> -L(less_vec):
> -       /* Check if one or less CHAR. This is necessary for size == 0
> -          but is also faster for size == CHAR_SIZE.  */
> -       cmpl    $1, %edx
> -       jbe     L(one_or_less)
> -
> -       /* Check if loading one VEC from either s1 or s2 could cause a
> -          page cross. This can have false positives but is by far the
> -          fastest method.  */
> -       movl    %edi, %eax
> -       orl     %esi, %eax
> -       andl    $(PAGE_SIZE - 1), %eax
> -       cmpl    $(PAGE_SIZE - VEC_SIZE), %eax
> -       jg      L(page_cross_less_vec)
> -
> -       /* No page cross possible.  */
> -       VMOVU   (%rsi), %YMM2
> -       VPCMP   $4, (%rdi), %YMM2, %k1
> -       kmovd   %k1, %eax
> -       /* Check if any matches where in bounds. Intentionally not
> -          storing result in eax to limit dependency chain if it goes to
> -          L(return_vec_0_lv).  */
> -       bzhil   %edx, %eax, %edx
> -       jnz     L(return_vec_0_lv)
> -       xorl    %eax, %eax
> -       ret
> -
> -       /* Essentially duplicate of L(return_vec_0). Ends up not costing
> -          any code as shrinks L(less_vec) by allowing 2-byte encoding of
> -          the jump and ends up fitting in aligning bytes. As well fits on
> -          same cache line as L(less_vec) so also saves a line from having
> -          to be fetched on cold calls to memcmp.  */
> -       .p2align 4,, 4
> -L(return_vec_0_lv):
> -       tzcntl  %eax, %eax
> -# ifdef USE_AS_WMEMCMP
> -       movl    (%rdi, %rax, CHAR_SIZE), %ecx
> -       xorl    %edx, %edx
> -       cmpl    (%rsi, %rax, CHAR_SIZE), %ecx
> -       /* NB: no partial register stall here because xorl zero idiom
> -          above.  */
> -       setg    %dl
> -       leal    -1(%rdx, %rdx), %eax
> -# else
> -       movzbl  (%rsi, %rax), %ecx
> -       movzbl  (%rdi, %rax), %eax
> -       subl    %ecx, %eax
> -# endif
> -       ret
> -
> -       .p2align 4
> -L(page_cross_less_vec):
> -       /* if USE_AS_WMEMCMP it can only be 0, 4, 8, 12, 16, 20, 24, 28
> -          bytes.  */
> -       cmpl    $(16 / CHAR_SIZE), %edx
> -       jae     L(between_16_31)
> -# ifndef USE_AS_WMEMCMP
> -       cmpl    $8, %edx
> -       jae     L(between_8_15)
> -       cmpl    $4, %edx
> -       jb      L(between_2_3)
> -
> -       /* Load as big endian with overlapping movbe to avoid branches.
> -        */
> -       movbe   (%rdi), %eax
> -       movbe   (%rsi), %ecx
> -       shlq    $32, %rax
> -       shlq    $32, %rcx
> -       movbe   -4(%rdi, %rdx), %edi
> -       movbe   -4(%rsi, %rdx), %esi
> -       orq     %rdi, %rax
> -       orq     %rsi, %rcx
> -       subq    %rcx, %rax
> -       /* edx is guranteed to be positive int32 in range [4, 7].  */
> -       cmovne  %edx, %eax
> -       /* ecx is -1 if rcx > rax. Otherwise 0.  */
> -       sbbl    %ecx, %ecx
> -       /* If rcx > rax, then ecx is 0 and eax is positive. If rcx ==
> -          rax then eax and ecx are zero. If rax < rax then ecx is -1 so
> -          eax doesn't matter.  */
> -       orl     %ecx, %eax
> -       ret
> -
> -       .p2align 4,, 8
> -L(between_8_15):
> -# endif
> -       /* If USE_AS_WMEMCMP fall through into 8-15 byte case.  */
> -       vmovq   (%rdi), %xmm1
> -       vmovq   (%rsi), %xmm2
> -       VPCMP   $4, %xmm1, %xmm2, %k1
> -       kmovd   %k1, %eax
> -       testl   %eax, %eax
> -       jnz     L(return_vec_0_lv)
> -       /* Use overlapping loads to avoid branches.  */
> -       vmovq   -8(%rdi, %rdx, CHAR_SIZE), %xmm1
> -       vmovq   -8(%rsi, %rdx, CHAR_SIZE), %xmm2
> -       VPCMP   $4, %xmm1, %xmm2, %k1
> -       addl    $(CHAR_PER_VEC - (8 / CHAR_SIZE)), %edx
> -       kmovd   %k1, %eax
> -       testl   %eax, %eax
> -       jnz     L(return_vec_0_end)
> -       ret
> -
> -       .p2align 4,, 8
> -L(between_16_31):
> -       /* From 16 to 31 bytes.  No branch when size == 16.  */
> -
> -       /* Use movups to save code size.  */
> -       vmovdqu (%rsi), %xmm2
> -       VPCMP   $4, (%rdi), %xmm2, %k1
> -       kmovd   %k1, %eax
> -       testl   %eax, %eax
> -       jnz     L(return_vec_0_lv)
> -       /* Use overlapping loads to avoid branches.  */
> -       vmovdqu -16(%rsi, %rdx, CHAR_SIZE), %xmm2
> -       VPCMP   $4, -16(%rdi, %rdx, CHAR_SIZE), %xmm2, %k1
> -       addl    $(CHAR_PER_VEC - (16 / CHAR_SIZE)), %edx
> -       kmovd   %k1, %eax
> -       testl   %eax, %eax
> -       jnz     L(return_vec_0_end)
> -       ret
> -
> -# ifndef USE_AS_WMEMCMP
> -L(between_2_3):
> -       /* Load as big endian to avoid branches.  */
> -       movzwl  (%rdi), %eax
> -       movzwl  (%rsi), %ecx
> -       shll    $8, %eax
> -       shll    $8, %ecx
> -       bswap   %eax
> -       bswap   %ecx
> -       movzbl  -1(%rdi, %rdx), %edi
> -       movzbl  -1(%rsi, %rdx), %esi
> -       orl     %edi, %eax
> -       orl     %esi, %ecx
> -       /* Subtraction is okay because the upper 8 bits are zero.  */
> -       subl    %ecx, %eax
> -       ret
> -# endif
>  END (MEMCMP)
>  #endif
> --
> 2.25.1
>

Numbers attached here.



Numbers collected on Tigerlake:
https://ark.intel.com/content/www/us/en/ark/products/208921/intel-core-i7-1165g7-processor-12m-cache-up-to-4-70-ghz-with-ipu.html

Numbers geomean of N = 20 runs.

Times reported as (new T) / (old T).

Some notes, there signficant improvement in the [0, 32] sized
case. Roughly 33-37% improvement for the page cross case (including false
positives) and 17-20% for the normal case.

On the other hand there are fairly significant slowdowns in the [33,
64] sized cases. For memcmpeq these regressions are roughly 5-20%. For
memcmp these regressions are around 10-15%.

In general I believe this a workwhile tradeoff.

As stated in the commit message, a profile of GCC compiling itself or
Python3 running the pyperf benchmark suite indicates that 94%+ or 99%+
of memcmp calls respectively fall into the [0, 32] size range.

Since the speedup in the [0, 32] case is greater than the regression
in the [33, 64] case and the [0, 32] case covers the vast majority of
cases, I think we can expect this change to benefit applications.

If people think otherwise, I have patches that show no regressions but
more modest speedups for the [0, 32] case (0-5% normal and 15-20% for
page cross case)
H.J. Lu Dec. 26, 2021, 5:04 p.m. UTC | #2 
On Fri, Dec 24, 2021 at 7:23 PM Noah Goldstein <goldstein.w.n@gmail.com> wrote:
>
> No bug.
> Optimizations are twofold.
>
> 1) Replace page cross and 0/1 checks with masked load instructions in
>    L(less_vec). In applications this reduces branch-misses in the
>    hot [0, 32] case.
> 2) Change controlflow so that L(less_vec) case gets the fall through.
>
> Change 2) helps copies in the [0, 32] size range but comes at the cost
> of copies in the [33, 64] size range.  From profiles of GCC and
> Python3, 94%+ and 99%+ of calls are in the [0, 32] range so this
> appears to the the right tradeoff.
> ---
>  sysdeps/x86_64/multiarch/memcmp-evex-movbe.S | 249 +++++--------------
>  1 file changed, 56 insertions(+), 193 deletions(-)
>
> diff --git a/sysdeps/x86_64/multiarch/memcmp-evex-movbe.S b/sysdeps/x86_64/multiarch/memcmp-evex-movbe.S
> index 640f6757fa..d2899e7c70 100644
> --- a/sysdeps/x86_64/multiarch/memcmp-evex-movbe.S
> +++ b/sysdeps/x86_64/multiarch/memcmp-evex-movbe.S
> @@ -62,15 +62,18 @@ Latency:
>  # define VMOVU         vmovdqu64
>
>  # ifdef USE_AS_WMEMCMP
> +#  define VMOVU_MASK   vmovdqu32
>  #  define CHAR_SIZE    4
>  #  define VPCMP        vpcmpd
>  #  define VPTEST       vptestmd
>  # else
> +#  define VMOVU_MASK   vmovdqu8
>  #  define CHAR_SIZE    1
>  #  define VPCMP        vpcmpub
>  #  define VPTEST       vptestmb
>  # endif
>
> +
>  # define VEC_SIZE      32
>  # define PAGE_SIZE     4096
>  # define CHAR_PER_VEC  (VEC_SIZE / CHAR_SIZE)
> @@ -102,12 +105,48 @@ ENTRY_P2ALIGN (MEMCMP, 6)
>         movl    %edx, %edx
>  # endif
>         cmp     $CHAR_PER_VEC, %RDX_LP
> -       jb      L(less_vec)
> +       /* Fall through for [0, VEC_SIZE] as its the hottest.  */
> +       ja      L(more_1x_vec)
> +
> +       /* Create mask for CHAR's we want to compare. This allows us to
> +          avoid having to include page cross logic.  */
> +       movl    $-1, %ecx
> +       bzhil   %edx, %ecx, %ecx
> +       kmovd   %ecx, %k2
> +
> +       /* Safe to load full ymm with mask.  */
> +       VMOVU_MASK (%rsi), %YMM2{%k2}
> +       VPCMP   $4,(%rdi), %YMM2, %k1{%k2}
> +       kmovd   %k1, %eax
> +       testl   %eax, %eax
> +       jnz     L(return_vec_0)
> +       ret
>
> +       .p2align 4
> +L(return_vec_0):
> +       tzcntl  %eax, %eax
> +# ifdef USE_AS_WMEMCMP
> +       movl    (%rdi, %rax, CHAR_SIZE), %ecx
> +       xorl    %edx, %edx
> +       cmpl    (%rsi, %rax, CHAR_SIZE), %ecx
> +       /* NB: no partial register stall here because xorl zero idiom
> +          above.  */
> +       setg    %dl
> +       leal    -1(%rdx, %rdx), %eax
> +# else
> +       movzbl  (%rsi, %rax), %ecx
> +       movzbl  (%rdi, %rax), %eax
> +       subl    %ecx, %eax
> +# endif
> +       ret
> +
> +
> +       .p2align 4
> +L(more_1x_vec):
>         /* From VEC to 2 * VEC.  No branch when size == VEC_SIZE.  */
>         VMOVU   (%rsi), %YMM1
>         /* Use compare not equals to directly check for mismatch.  */
> -       VPCMP   $4, (%rdi), %YMM1, %k1
> +       VPCMP   $4,(%rdi), %YMM1, %k1
>         kmovd   %k1, %eax
>         /* NB: eax must be destination register if going to
>            L(return_vec_[0,2]). For L(return_vec_3) destination register
> @@ -131,13 +170,13 @@ ENTRY_P2ALIGN (MEMCMP, 6)
>
>         /* Check third and fourth VEC no matter what.  */
>         VMOVU   (VEC_SIZE * 2)(%rsi), %YMM3
> -       VPCMP   $4, (VEC_SIZE * 2)(%rdi), %YMM3, %k1
> +       VPCMP   $4,(VEC_SIZE * 2)(%rdi), %YMM3, %k1
>         kmovd   %k1, %eax
>         testl   %eax, %eax
>         jnz     L(return_vec_2)
>
>         VMOVU   (VEC_SIZE * 3)(%rsi), %YMM4
> -       VPCMP   $4, (VEC_SIZE * 3)(%rdi), %YMM4, %k1
> +       VPCMP   $4,(VEC_SIZE * 3)(%rdi), %YMM4, %k1
>         kmovd   %k1, %ecx
>         testl   %ecx, %ecx
>         jnz     L(return_vec_3)
> @@ -169,7 +208,7 @@ ENTRY_P2ALIGN (MEMCMP, 6)
>         VMOVU   (VEC_SIZE * 3)(%rsi), %YMM4
>         /* Ternary logic to xor (VEC_SIZE * 3)(%rdi) with YMM4 while
>            oring with YMM1. Result is stored in YMM4.  */
> -       vpternlogd $0xde, (VEC_SIZE * 3)(%rdi), %YMM1, %YMM4
> +       vpternlogd $0xde,(VEC_SIZE * 3)(%rdi), %YMM1, %YMM4
>
>         /* Or together YMM2, YMM3, and YMM4 into YMM4.  */
>         vpternlogd $0xfe, %YMM2, %YMM3, %YMM4
> @@ -184,7 +223,8 @@ ENTRY_P2ALIGN (MEMCMP, 6)
>         /* NB: eax must be zero to reach here.  */
>         ret
>
> -       .p2align 4
> +
> +       .p2align 4,, 8
>  L(8x_end_return_vec_0_1_2_3):
>         movq    %rdx, %rdi
>  L(8x_return_vec_0_1_2_3):
> @@ -222,23 +262,6 @@ L(return_vec_3):
>  # endif
>         ret
>
> -       .p2align 4
> -L(return_vec_0):
> -       tzcntl  %eax, %eax
> -# ifdef USE_AS_WMEMCMP
> -       movl    (%rdi, %rax, CHAR_SIZE), %ecx
> -       xorl    %edx, %edx
> -       cmpl    (%rsi, %rax, CHAR_SIZE), %ecx
> -       /* NB: no partial register stall here because xorl zero idiom
> -          above.  */
> -       setg    %dl
> -       leal    -1(%rdx, %rdx), %eax
> -# else
> -       movzbl  (%rsi, %rax), %ecx
> -       movzbl  (%rdi, %rax), %eax
> -       subl    %ecx, %eax
> -# endif
> -       ret
>
>         .p2align 4
>  L(return_vec_1):
> @@ -297,7 +320,7 @@ L(loop_4x_vec):
>         VMOVU   (VEC_SIZE * 2)(%rsi, %rdi), %YMM3
>         vpxorq  (VEC_SIZE * 2)(%rdi), %YMM3, %YMM3
>         VMOVU   (VEC_SIZE * 3)(%rsi, %rdi), %YMM4
> -       vpternlogd $0xde, (VEC_SIZE * 3)(%rdi), %YMM1, %YMM4
> +       vpternlogd $0xde,(VEC_SIZE * 3)(%rdi), %YMM1, %YMM4
>         vpternlogd $0xfe, %YMM2, %YMM3, %YMM4
>         VPTEST  %YMM4, %YMM4, %k1
>         kmovd   %k1, %ecx
> @@ -324,7 +347,7 @@ L(loop_4x_vec):
>         VMOVU   VEC_SIZE(%rsi, %rdx), %YMM2
>         vpxorq  VEC_SIZE(%rdx), %YMM2, %YMM2
>         VMOVU   (VEC_SIZE * 3)(%rsi, %rdx), %YMM4
> -       vpternlogd $0xde, (VEC_SIZE * 3)(%rdx), %YMM1, %YMM4
> +       vpternlogd $0xde,(VEC_SIZE * 3)(%rdx), %YMM1, %YMM4
>         vpternlogd $0xfe, %YMM2, %YMM3, %YMM4
>         VPTEST  %YMM4, %YMM4, %k1
>         kmovd   %k1, %ecx
> @@ -336,14 +359,14 @@ L(loop_4x_vec):
>         /* Only entry is from L(more_8x_vec).  */
>         .p2align 4,, 10
>  L(8x_last_2x_vec):
> -       VPCMP   $4, (VEC_SIZE * 2)(%rdx), %YMM3, %k1
> +       VPCMP   $4,(VEC_SIZE * 2)(%rdx), %YMM3, %k1
>         kmovd   %k1, %eax
>         testl   %eax, %eax
>         jnz     L(8x_return_vec_2)
>         /* Naturally aligned to 16 bytes.  */
>  L(8x_last_1x_vec):
>         VMOVU   (VEC_SIZE * 3)(%rsi, %rdx), %YMM1
> -       VPCMP   $4, (VEC_SIZE * 3)(%rdx), %YMM1, %k1
> +       VPCMP   $4,(VEC_SIZE * 3)(%rdx), %YMM1, %k1
>         kmovd   %k1, %eax
>         testl   %eax, %eax
>         jnz     L(8x_return_vec_3)
> @@ -392,7 +415,9 @@ L(last_1x_vec):
>         jnz     L(return_vec_0_end)
>         ret
>
> -       .p2align 4,, 10
> +
> +       /* Don't align. Takes 2-fetch blocks either way and aligning
> +          will cause code to spill into another cacheline.  */
>  L(return_vec_1_end):
>         /* Use bsf to save code size. This is necessary to have
>            L(one_or_less) fit in aligning bytes between.  */
> @@ -411,31 +436,8 @@ L(return_vec_1_end):
>  # endif
>         ret
>
> -       /* NB: L(one_or_less) fits in alignment padding between
> -          L(return_vec_1_end) and L(return_vec_0_end).  */
> -# ifdef USE_AS_WMEMCMP
> -L(one_or_less):
> -       jb      L(zero)
> -       movl    (%rdi), %ecx
> -       xorl    %edx, %edx
> -       cmpl    (%rsi), %ecx
> -       je      L(zero)
> -       setg    %dl
> -       leal    -1(%rdx, %rdx), %eax
> -       ret
> -# else
> -L(one_or_less):
> -       jb      L(zero)
> -       movzbl  (%rsi), %ecx
> -       movzbl  (%rdi), %eax
> -       subl    %ecx, %eax
> -       ret
> -# endif
> -L(zero):
> -       xorl    %eax, %eax
> -       ret
> -
> -       .p2align 4
> +       /* Don't align. Takes 2-fetch blocks either way and aligning
> +          will cause code to spill into another cacheline.  */
>  L(return_vec_0_end):
>         tzcntl  %eax, %eax
>         addl    %edx, %eax
> @@ -451,146 +453,7 @@ L(return_vec_0_end):
>         subl    %ecx, %eax
>  # endif
>         ret
> +       /* 1-byte until next cache line.  */
>
> -       .p2align 4
> -L(less_vec):
> -       /* Check if one or less CHAR. This is necessary for size == 0
> -          but is also faster for size == CHAR_SIZE.  */
> -       cmpl    $1, %edx
> -       jbe     L(one_or_less)
> -
> -       /* Check if loading one VEC from either s1 or s2 could cause a
> -          page cross. This can have false positives but is by far the
> -          fastest method.  */
> -       movl    %edi, %eax
> -       orl     %esi, %eax
> -       andl    $(PAGE_SIZE - 1), %eax
> -       cmpl    $(PAGE_SIZE - VEC_SIZE), %eax
> -       jg      L(page_cross_less_vec)
> -
> -       /* No page cross possible.  */
> -       VMOVU   (%rsi), %YMM2
> -       VPCMP   $4, (%rdi), %YMM2, %k1
> -       kmovd   %k1, %eax
> -       /* Check if any matches where in bounds. Intentionally not
> -          storing result in eax to limit dependency chain if it goes to
> -          L(return_vec_0_lv).  */
> -       bzhil   %edx, %eax, %edx
> -       jnz     L(return_vec_0_lv)
> -       xorl    %eax, %eax
> -       ret
> -
> -       /* Essentially duplicate of L(return_vec_0). Ends up not costing
> -          any code as shrinks L(less_vec) by allowing 2-byte encoding of
> -          the jump and ends up fitting in aligning bytes. As well fits on
> -          same cache line as L(less_vec) so also saves a line from having
> -          to be fetched on cold calls to memcmp.  */
> -       .p2align 4,, 4
> -L(return_vec_0_lv):
> -       tzcntl  %eax, %eax
> -# ifdef USE_AS_WMEMCMP
> -       movl    (%rdi, %rax, CHAR_SIZE), %ecx
> -       xorl    %edx, %edx
> -       cmpl    (%rsi, %rax, CHAR_SIZE), %ecx
> -       /* NB: no partial register stall here because xorl zero idiom
> -          above.  */
> -       setg    %dl
> -       leal    -1(%rdx, %rdx), %eax
> -# else
> -       movzbl  (%rsi, %rax), %ecx
> -       movzbl  (%rdi, %rax), %eax
> -       subl    %ecx, %eax
> -# endif
> -       ret
> -
> -       .p2align 4
> -L(page_cross_less_vec):
> -       /* if USE_AS_WMEMCMP it can only be 0, 4, 8, 12, 16, 20, 24, 28
> -          bytes.  */
> -       cmpl    $(16 / CHAR_SIZE), %edx
> -       jae     L(between_16_31)
> -# ifndef USE_AS_WMEMCMP
> -       cmpl    $8, %edx
> -       jae     L(between_8_15)
> -       cmpl    $4, %edx
> -       jb      L(between_2_3)
> -
> -       /* Load as big endian with overlapping movbe to avoid branches.
> -        */
> -       movbe   (%rdi), %eax
> -       movbe   (%rsi), %ecx
> -       shlq    $32, %rax
> -       shlq    $32, %rcx
> -       movbe   -4(%rdi, %rdx), %edi
> -       movbe   -4(%rsi, %rdx), %esi
> -       orq     %rdi, %rax
> -       orq     %rsi, %rcx
> -       subq    %rcx, %rax
> -       /* edx is guranteed to be positive int32 in range [4, 7].  */
> -       cmovne  %edx, %eax
> -       /* ecx is -1 if rcx > rax. Otherwise 0.  */
> -       sbbl    %ecx, %ecx
> -       /* If rcx > rax, then ecx is 0 and eax is positive. If rcx ==
> -          rax then eax and ecx are zero. If rax < rax then ecx is -1 so
> -          eax doesn't matter.  */
> -       orl     %ecx, %eax
> -       ret
> -
> -       .p2align 4,, 8
> -L(between_8_15):
> -# endif
> -       /* If USE_AS_WMEMCMP fall through into 8-15 byte case.  */
> -       vmovq   (%rdi), %xmm1
> -       vmovq   (%rsi), %xmm2
> -       VPCMP   $4, %xmm1, %xmm2, %k1
> -       kmovd   %k1, %eax
> -       testl   %eax, %eax
> -       jnz     L(return_vec_0_lv)
> -       /* Use overlapping loads to avoid branches.  */
> -       vmovq   -8(%rdi, %rdx, CHAR_SIZE), %xmm1
> -       vmovq   -8(%rsi, %rdx, CHAR_SIZE), %xmm2
> -       VPCMP   $4, %xmm1, %xmm2, %k1
> -       addl    $(CHAR_PER_VEC - (8 / CHAR_SIZE)), %edx
> -       kmovd   %k1, %eax
> -       testl   %eax, %eax
> -       jnz     L(return_vec_0_end)
> -       ret
> -
> -       .p2align 4,, 8
> -L(between_16_31):
> -       /* From 16 to 31 bytes.  No branch when size == 16.  */
> -
> -       /* Use movups to save code size.  */
> -       vmovdqu (%rsi), %xmm2
> -       VPCMP   $4, (%rdi), %xmm2, %k1
> -       kmovd   %k1, %eax
> -       testl   %eax, %eax
> -       jnz     L(return_vec_0_lv)
> -       /* Use overlapping loads to avoid branches.  */
> -       vmovdqu -16(%rsi, %rdx, CHAR_SIZE), %xmm2
> -       VPCMP   $4, -16(%rdi, %rdx, CHAR_SIZE), %xmm2, %k1
> -       addl    $(CHAR_PER_VEC - (16 / CHAR_SIZE)), %edx
> -       kmovd   %k1, %eax
> -       testl   %eax, %eax
> -       jnz     L(return_vec_0_end)
> -       ret
> -
> -# ifndef USE_AS_WMEMCMP
> -L(between_2_3):
> -       /* Load as big endian to avoid branches.  */
> -       movzwl  (%rdi), %eax
> -       movzwl  (%rsi), %ecx
> -       shll    $8, %eax
> -       shll    $8, %ecx
> -       bswap   %eax
> -       bswap   %ecx
> -       movzbl  -1(%rdi, %rdx), %edi
> -       movzbl  -1(%rsi, %rdx), %esi
> -       orl     %edi, %eax
> -       orl     %esi, %ecx
> -       /* Subtraction is okay because the upper 8 bits are zero.  */
> -       subl    %ecx, %eax
> -       ret
> -# endif
>  END (MEMCMP)
>  #endif
> --
> 2.25.1
>

LGTM.

Reviewed-by: H.J. Lu <hjl.tools@gmail.com>

Thanks.
Noah Goldstein Dec. 27, 2021, 10:08 a.m. UTC | #3 
On Sun, Dec 26, 2021 at 11:05 AM H.J. Lu <hjl.tools@gmail.com> wrote:
>
> On Fri, Dec 24, 2021 at 7:23 PM Noah Goldstein <goldstein.w.n@gmail.com> wrote:
> >
> > No bug.
> > Optimizations are twofold.
> >
> > 1) Replace page cross and 0/1 checks with masked load instructions in
> >    L(less_vec). In applications this reduces branch-misses in the
> >    hot [0, 32] case.
> > 2) Change controlflow so that L(less_vec) case gets the fall through.
> >
> > Change 2) helps copies in the [0, 32] size range but comes at the cost
> > of copies in the [33, 64] size range.  From profiles of GCC and
> > Python3, 94%+ and 99%+ of calls are in the [0, 32] range so this
> > appears to the the right tradeoff.
> > ---
> >  sysdeps/x86_64/multiarch/memcmp-evex-movbe.S | 249 +++++--------------
> >  1 file changed, 56 insertions(+), 193 deletions(-)
> >
> > diff --git a/sysdeps/x86_64/multiarch/memcmp-evex-movbe.S b/sysdeps/x86_64/multiarch/memcmp-evex-movbe.S
> > index 640f6757fa..d2899e7c70 100644
> > --- a/sysdeps/x86_64/multiarch/memcmp-evex-movbe.S
> > +++ b/sysdeps/x86_64/multiarch/memcmp-evex-movbe.S
> > @@ -62,15 +62,18 @@ Latency:
> >  # define VMOVU         vmovdqu64
> >
> >  # ifdef USE_AS_WMEMCMP
> > +#  define VMOVU_MASK   vmovdqu32
> >  #  define CHAR_SIZE    4
> >  #  define VPCMP        vpcmpd
> >  #  define VPTEST       vptestmd
> >  # else
> > +#  define VMOVU_MASK   vmovdqu8
> >  #  define CHAR_SIZE    1
> >  #  define VPCMP        vpcmpub
> >  #  define VPTEST       vptestmb
> >  # endif
> >
> > +
> >  # define VEC_SIZE      32
> >  # define PAGE_SIZE     4096
> >  # define CHAR_PER_VEC  (VEC_SIZE / CHAR_SIZE)
> > @@ -102,12 +105,48 @@ ENTRY_P2ALIGN (MEMCMP, 6)
> >         movl    %edx, %edx
> >  # endif
> >         cmp     $CHAR_PER_VEC, %RDX_LP
> > -       jb      L(less_vec)
> > +       /* Fall through for [0, VEC_SIZE] as its the hottest.  */
> > +       ja      L(more_1x_vec)
> > +
> > +       /* Create mask for CHAR's we want to compare. This allows us to
> > +          avoid having to include page cross logic.  */
> > +       movl    $-1, %ecx
> > +       bzhil   %edx, %ecx, %ecx
> > +       kmovd   %ecx, %k2
> > +
> > +       /* Safe to load full ymm with mask.  */
> > +       VMOVU_MASK (%rsi), %YMM2{%k2}
> > +       VPCMP   $4,(%rdi), %YMM2, %k1{%k2}
> > +       kmovd   %k1, %eax
> > +       testl   %eax, %eax
> > +       jnz     L(return_vec_0)
> > +       ret
> >
> > +       .p2align 4
> > +L(return_vec_0):
> > +       tzcntl  %eax, %eax
> > +# ifdef USE_AS_WMEMCMP
> > +       movl    (%rdi, %rax, CHAR_SIZE), %ecx
> > +       xorl    %edx, %edx
> > +       cmpl    (%rsi, %rax, CHAR_SIZE), %ecx
> > +       /* NB: no partial register stall here because xorl zero idiom
> > +          above.  */
> > +       setg    %dl
> > +       leal    -1(%rdx, %rdx), %eax
> > +# else
> > +       movzbl  (%rsi, %rax), %ecx
> > +       movzbl  (%rdi, %rax), %eax
> > +       subl    %ecx, %eax
> > +# endif
> > +       ret
> > +
> > +
> > +       .p2align 4
> > +L(more_1x_vec):
> >         /* From VEC to 2 * VEC.  No branch when size == VEC_SIZE.  */
> >         VMOVU   (%rsi), %YMM1
> >         /* Use compare not equals to directly check for mismatch.  */
> > -       VPCMP   $4, (%rdi), %YMM1, %k1
> > +       VPCMP   $4,(%rdi), %YMM1, %k1
> >         kmovd   %k1, %eax
> >         /* NB: eax must be destination register if going to
> >            L(return_vec_[0,2]). For L(return_vec_3) destination register
> > @@ -131,13 +170,13 @@ ENTRY_P2ALIGN (MEMCMP, 6)
> >
> >         /* Check third and fourth VEC no matter what.  */
> >         VMOVU   (VEC_SIZE * 2)(%rsi), %YMM3
> > -       VPCMP   $4, (VEC_SIZE * 2)(%rdi), %YMM3, %k1
> > +       VPCMP   $4,(VEC_SIZE * 2)(%rdi), %YMM3, %k1
> >         kmovd   %k1, %eax
> >         testl   %eax, %eax
> >         jnz     L(return_vec_2)
> >
> >         VMOVU   (VEC_SIZE * 3)(%rsi), %YMM4
> > -       VPCMP   $4, (VEC_SIZE * 3)(%rdi), %YMM4, %k1
> > +       VPCMP   $4,(VEC_SIZE * 3)(%rdi), %YMM4, %k1
> >         kmovd   %k1, %ecx
> >         testl   %ecx, %ecx
> >         jnz     L(return_vec_3)
> > @@ -169,7 +208,7 @@ ENTRY_P2ALIGN (MEMCMP, 6)
> >         VMOVU   (VEC_SIZE * 3)(%rsi), %YMM4
> >         /* Ternary logic to xor (VEC_SIZE * 3)(%rdi) with YMM4 while
> >            oring with YMM1. Result is stored in YMM4.  */
> > -       vpternlogd $0xde, (VEC_SIZE * 3)(%rdi), %YMM1, %YMM4
> > +       vpternlogd $0xde,(VEC_SIZE * 3)(%rdi), %YMM1, %YMM4
> >
> >         /* Or together YMM2, YMM3, and YMM4 into YMM4.  */
> >         vpternlogd $0xfe, %YMM2, %YMM3, %YMM4
> > @@ -184,7 +223,8 @@ ENTRY_P2ALIGN (MEMCMP, 6)
> >         /* NB: eax must be zero to reach here.  */
> >         ret
> >
> > -       .p2align 4
> > +
> > +       .p2align 4,, 8
> >  L(8x_end_return_vec_0_1_2_3):
> >         movq    %rdx, %rdi
> >  L(8x_return_vec_0_1_2_3):
> > @@ -222,23 +262,6 @@ L(return_vec_3):
> >  # endif
> >         ret
> >
> > -       .p2align 4
> > -L(return_vec_0):
> > -       tzcntl  %eax, %eax
> > -# ifdef USE_AS_WMEMCMP
> > -       movl    (%rdi, %rax, CHAR_SIZE), %ecx
> > -       xorl    %edx, %edx
> > -       cmpl    (%rsi, %rax, CHAR_SIZE), %ecx
> > -       /* NB: no partial register stall here because xorl zero idiom
> > -          above.  */
> > -       setg    %dl
> > -       leal    -1(%rdx, %rdx), %eax
> > -# else
> > -       movzbl  (%rsi, %rax), %ecx
> > -       movzbl  (%rdi, %rax), %eax
> > -       subl    %ecx, %eax
> > -# endif
> > -       ret
> >
> >         .p2align 4
> >  L(return_vec_1):
> > @@ -297,7 +320,7 @@ L(loop_4x_vec):
> >         VMOVU   (VEC_SIZE * 2)(%rsi, %rdi), %YMM3
> >         vpxorq  (VEC_SIZE * 2)(%rdi), %YMM3, %YMM3
> >         VMOVU   (VEC_SIZE * 3)(%rsi, %rdi), %YMM4
> > -       vpternlogd $0xde, (VEC_SIZE * 3)(%rdi), %YMM1, %YMM4
> > +       vpternlogd $0xde,(VEC_SIZE * 3)(%rdi), %YMM1, %YMM4
> >         vpternlogd $0xfe, %YMM2, %YMM3, %YMM4
> >         VPTEST  %YMM4, %YMM4, %k1
> >         kmovd   %k1, %ecx
> > @@ -324,7 +347,7 @@ L(loop_4x_vec):
> >         VMOVU   VEC_SIZE(%rsi, %rdx), %YMM2
> >         vpxorq  VEC_SIZE(%rdx), %YMM2, %YMM2
> >         VMOVU   (VEC_SIZE * 3)(%rsi, %rdx), %YMM4
> > -       vpternlogd $0xde, (VEC_SIZE * 3)(%rdx), %YMM1, %YMM4
> > +       vpternlogd $0xde,(VEC_SIZE * 3)(%rdx), %YMM1, %YMM4
> >         vpternlogd $0xfe, %YMM2, %YMM3, %YMM4
> >         VPTEST  %YMM4, %YMM4, %k1
> >         kmovd   %k1, %ecx
> > @@ -336,14 +359,14 @@ L(loop_4x_vec):
> >         /* Only entry is from L(more_8x_vec).  */
> >         .p2align 4,, 10
> >  L(8x_last_2x_vec):
> > -       VPCMP   $4, (VEC_SIZE * 2)(%rdx), %YMM3, %k1
> > +       VPCMP   $4,(VEC_SIZE * 2)(%rdx), %YMM3, %k1
> >         kmovd   %k1, %eax
> >         testl   %eax, %eax
> >         jnz     L(8x_return_vec_2)
> >         /* Naturally aligned to 16 bytes.  */
> >  L(8x_last_1x_vec):
> >         VMOVU   (VEC_SIZE * 3)(%rsi, %rdx), %YMM1
> > -       VPCMP   $4, (VEC_SIZE * 3)(%rdx), %YMM1, %k1
> > +       VPCMP   $4,(VEC_SIZE * 3)(%rdx), %YMM1, %k1
> >         kmovd   %k1, %eax
> >         testl   %eax, %eax
> >         jnz     L(8x_return_vec_3)
> > @@ -392,7 +415,9 @@ L(last_1x_vec):
> >         jnz     L(return_vec_0_end)
> >         ret
> >
> > -       .p2align 4,, 10
> > +
> > +       /* Don't align. Takes 2-fetch blocks either way and aligning
> > +          will cause code to spill into another cacheline.  */
> >  L(return_vec_1_end):
> >         /* Use bsf to save code size. This is necessary to have
> >            L(one_or_less) fit in aligning bytes between.  */
> > @@ -411,31 +436,8 @@ L(return_vec_1_end):
> >  # endif
> >         ret
> >
> > -       /* NB: L(one_or_less) fits in alignment padding between
> > -          L(return_vec_1_end) and L(return_vec_0_end).  */
> > -# ifdef USE_AS_WMEMCMP
> > -L(one_or_less):
> > -       jb      L(zero)
> > -       movl    (%rdi), %ecx
> > -       xorl    %edx, %edx
> > -       cmpl    (%rsi), %ecx
> > -       je      L(zero)
> > -       setg    %dl
> > -       leal    -1(%rdx, %rdx), %eax
> > -       ret
> > -# else
> > -L(one_or_less):
> > -       jb      L(zero)
> > -       movzbl  (%rsi), %ecx
> > -       movzbl  (%rdi), %eax
> > -       subl    %ecx, %eax
> > -       ret
> > -# endif
> > -L(zero):
> > -       xorl    %eax, %eax
> > -       ret
> > -
> > -       .p2align 4
> > +       /* Don't align. Takes 2-fetch blocks either way and aligning
> > +          will cause code to spill into another cacheline.  */
> >  L(return_vec_0_end):
> >         tzcntl  %eax, %eax
> >         addl    %edx, %eax
> > @@ -451,146 +453,7 @@ L(return_vec_0_end):
> >         subl    %ecx, %eax
> >  # endif
> >         ret
> > +       /* 1-byte until next cache line.  */
> >
> > -       .p2align 4
> > -L(less_vec):
> > -       /* Check if one or less CHAR. This is necessary for size == 0
> > -          but is also faster for size == CHAR_SIZE.  */
> > -       cmpl    $1, %edx
> > -       jbe     L(one_or_less)
> > -
> > -       /* Check if loading one VEC from either s1 or s2 could cause a
> > -          page cross. This can have false positives but is by far the
> > -          fastest method.  */
> > -       movl    %edi, %eax
> > -       orl     %esi, %eax
> > -       andl    $(PAGE_SIZE - 1), %eax
> > -       cmpl    $(PAGE_SIZE - VEC_SIZE), %eax
> > -       jg      L(page_cross_less_vec)
> > -
> > -       /* No page cross possible.  */
> > -       VMOVU   (%rsi), %YMM2
> > -       VPCMP   $4, (%rdi), %YMM2, %k1
> > -       kmovd   %k1, %eax
> > -       /* Check if any matches where in bounds. Intentionally not
> > -          storing result in eax to limit dependency chain if it goes to
> > -          L(return_vec_0_lv).  */
> > -       bzhil   %edx, %eax, %edx
> > -       jnz     L(return_vec_0_lv)
> > -       xorl    %eax, %eax
> > -       ret
> > -
> > -       /* Essentially duplicate of L(return_vec_0). Ends up not costing
> > -          any code as shrinks L(less_vec) by allowing 2-byte encoding of
> > -          the jump and ends up fitting in aligning bytes. As well fits on
> > -          same cache line as L(less_vec) so also saves a line from having
> > -          to be fetched on cold calls to memcmp.  */
> > -       .p2align 4,, 4
> > -L(return_vec_0_lv):
> > -       tzcntl  %eax, %eax
> > -# ifdef USE_AS_WMEMCMP
> > -       movl    (%rdi, %rax, CHAR_SIZE), %ecx
> > -       xorl    %edx, %edx
> > -       cmpl    (%rsi, %rax, CHAR_SIZE), %ecx
> > -       /* NB: no partial register stall here because xorl zero idiom
> > -          above.  */
> > -       setg    %dl
> > -       leal    -1(%rdx, %rdx), %eax
> > -# else
> > -       movzbl  (%rsi, %rax), %ecx
> > -       movzbl  (%rdi, %rax), %eax
> > -       subl    %ecx, %eax
> > -# endif
> > -       ret
> > -
> > -       .p2align 4
> > -L(page_cross_less_vec):
> > -       /* if USE_AS_WMEMCMP it can only be 0, 4, 8, 12, 16, 20, 24, 28
> > -          bytes.  */
> > -       cmpl    $(16 / CHAR_SIZE), %edx
> > -       jae     L(between_16_31)
> > -# ifndef USE_AS_WMEMCMP
> > -       cmpl    $8, %edx
> > -       jae     L(between_8_15)
> > -       cmpl    $4, %edx
> > -       jb      L(between_2_3)
> > -
> > -       /* Load as big endian with overlapping movbe to avoid branches.
> > -        */
> > -       movbe   (%rdi), %eax
> > -       movbe   (%rsi), %ecx
> > -       shlq    $32, %rax
> > -       shlq    $32, %rcx
> > -       movbe   -4(%rdi, %rdx), %edi
> > -       movbe   -4(%rsi, %rdx), %esi
> > -       orq     %rdi, %rax
> > -       orq     %rsi, %rcx
> > -       subq    %rcx, %rax
> > -       /* edx is guranteed to be positive int32 in range [4, 7].  */
> > -       cmovne  %edx, %eax
> > -       /* ecx is -1 if rcx > rax. Otherwise 0.  */
> > -       sbbl    %ecx, %ecx
> > -       /* If rcx > rax, then ecx is 0 and eax is positive. If rcx ==
> > -          rax then eax and ecx are zero. If rax < rax then ecx is -1 so
> > -          eax doesn't matter.  */
> > -       orl     %ecx, %eax
> > -       ret
> > -
> > -       .p2align 4,, 8
> > -L(between_8_15):
> > -# endif
> > -       /* If USE_AS_WMEMCMP fall through into 8-15 byte case.  */
> > -       vmovq   (%rdi), %xmm1
> > -       vmovq   (%rsi), %xmm2
> > -       VPCMP   $4, %xmm1, %xmm2, %k1
> > -       kmovd   %k1, %eax
> > -       testl   %eax, %eax
> > -       jnz     L(return_vec_0_lv)
> > -       /* Use overlapping loads to avoid branches.  */
> > -       vmovq   -8(%rdi, %rdx, CHAR_SIZE), %xmm1
> > -       vmovq   -8(%rsi, %rdx, CHAR_SIZE), %xmm2
> > -       VPCMP   $4, %xmm1, %xmm2, %k1
> > -       addl    $(CHAR_PER_VEC - (8 / CHAR_SIZE)), %edx
> > -       kmovd   %k1, %eax
> > -       testl   %eax, %eax
> > -       jnz     L(return_vec_0_end)
> > -       ret
> > -
> > -       .p2align 4,, 8
> > -L(between_16_31):
> > -       /* From 16 to 31 bytes.  No branch when size == 16.  */
> > -
> > -       /* Use movups to save code size.  */
> > -       vmovdqu (%rsi), %xmm2
> > -       VPCMP   $4, (%rdi), %xmm2, %k1
> > -       kmovd   %k1, %eax
> > -       testl   %eax, %eax
> > -       jnz     L(return_vec_0_lv)
> > -       /* Use overlapping loads to avoid branches.  */
> > -       vmovdqu -16(%rsi, %rdx, CHAR_SIZE), %xmm2
> > -       VPCMP   $4, -16(%rdi, %rdx, CHAR_SIZE), %xmm2, %k1
> > -       addl    $(CHAR_PER_VEC - (16 / CHAR_SIZE)), %edx
> > -       kmovd   %k1, %eax
> > -       testl   %eax, %eax
> > -       jnz     L(return_vec_0_end)
> > -       ret
> > -
> > -# ifndef USE_AS_WMEMCMP
> > -L(between_2_3):
> > -       /* Load as big endian to avoid branches.  */
> > -       movzwl  (%rdi), %eax
> > -       movzwl  (%rsi), %ecx
> > -       shll    $8, %eax
> > -       shll    $8, %ecx
> > -       bswap   %eax
> > -       bswap   %ecx
> > -       movzbl  -1(%rdi, %rdx), %edi
> > -       movzbl  -1(%rsi, %rdx), %esi
> > -       orl     %edi, %eax
> > -       orl     %esi, %ecx
> > -       /* Subtraction is okay because the upper 8 bits are zero.  */
> > -       subl    %ecx, %eax
> > -       ret
> > -# endif
> >  END (MEMCMP)
> >  #endif
> > --
> > 2.25.1
> >
>
> LGTM.
>
> Reviewed-by: H.J. Lu <hjl.tools@gmail.com>
>
> Thanks.

Thanks pushed.
>
> --
> H.J.
Sunil Pandey April 23, 2022, 1:53 a.m. UTC | #4 
On Mon, Dec 27, 2021 at 2:08 AM Noah Goldstein via Libc-alpha
<libc-alpha@sourceware.org> wrote:
>
> On Sun, Dec 26, 2021 at 11:05 AM H.J. Lu <hjl.tools@gmail.com> wrote:
> >
> > On Fri, Dec 24, 2021 at 7:23 PM Noah Goldstein <goldstein.w.n@gmail.com> wrote:
> > >
> > > No bug.
> > > Optimizations are twofold.
> > >
> > > 1) Replace page cross and 0/1 checks with masked load instructions in
> > >    L(less_vec). In applications this reduces branch-misses in the
> > >    hot [0, 32] case.
> > > 2) Change controlflow so that L(less_vec) case gets the fall through.
> > >
> > > Change 2) helps copies in the [0, 32] size range but comes at the cost
> > > of copies in the [33, 64] size range.  From profiles of GCC and
> > > Python3, 94%+ and 99%+ of calls are in the [0, 32] range so this
> > > appears to the the right tradeoff.
> > > ---
> > >  sysdeps/x86_64/multiarch/memcmp-evex-movbe.S | 249 +++++--------------
> > >  1 file changed, 56 insertions(+), 193 deletions(-)
> > >
> > > diff --git a/sysdeps/x86_64/multiarch/memcmp-evex-movbe.S b/sysdeps/x86_64/multiarch/memcmp-evex-movbe.S
> > > index 640f6757fa..d2899e7c70 100644
> > > --- a/sysdeps/x86_64/multiarch/memcmp-evex-movbe.S
> > > +++ b/sysdeps/x86_64/multiarch/memcmp-evex-movbe.S
> > > @@ -62,15 +62,18 @@ Latency:
> > >  # define VMOVU         vmovdqu64
> > >
> > >  # ifdef USE_AS_WMEMCMP
> > > +#  define VMOVU_MASK   vmovdqu32
> > >  #  define CHAR_SIZE    4
> > >  #  define VPCMP        vpcmpd
> > >  #  define VPTEST       vptestmd
> > >  # else
> > > +#  define VMOVU_MASK   vmovdqu8
> > >  #  define CHAR_SIZE    1
> > >  #  define VPCMP        vpcmpub
> > >  #  define VPTEST       vptestmb
> > >  # endif
> > >
> > > +
> > >  # define VEC_SIZE      32
> > >  # define PAGE_SIZE     4096
> > >  # define CHAR_PER_VEC  (VEC_SIZE / CHAR_SIZE)
> > > @@ -102,12 +105,48 @@ ENTRY_P2ALIGN (MEMCMP, 6)
> > >         movl    %edx, %edx
> > >  # endif
> > >         cmp     $CHAR_PER_VEC, %RDX_LP
> > > -       jb      L(less_vec)
> > > +       /* Fall through for [0, VEC_SIZE] as its the hottest.  */
> > > +       ja      L(more_1x_vec)
> > > +
> > > +       /* Create mask for CHAR's we want to compare. This allows us to
> > > +          avoid having to include page cross logic.  */
> > > +       movl    $-1, %ecx
> > > +       bzhil   %edx, %ecx, %ecx
> > > +       kmovd   %ecx, %k2
> > > +
> > > +       /* Safe to load full ymm with mask.  */
> > > +       VMOVU_MASK (%rsi), %YMM2{%k2}
> > > +       VPCMP   $4,(%rdi), %YMM2, %k1{%k2}
> > > +       kmovd   %k1, %eax
> > > +       testl   %eax, %eax
> > > +       jnz     L(return_vec_0)
> > > +       ret
> > >
> > > +       .p2align 4
> > > +L(return_vec_0):
> > > +       tzcntl  %eax, %eax
> > > +# ifdef USE_AS_WMEMCMP
> > > +       movl    (%rdi, %rax, CHAR_SIZE), %ecx
> > > +       xorl    %edx, %edx
> > > +       cmpl    (%rsi, %rax, CHAR_SIZE), %ecx
> > > +       /* NB: no partial register stall here because xorl zero idiom
> > > +          above.  */
> > > +       setg    %dl
> > > +       leal    -1(%rdx, %rdx), %eax
> > > +# else
> > > +       movzbl  (%rsi, %rax), %ecx
> > > +       movzbl  (%rdi, %rax), %eax
> > > +       subl    %ecx, %eax
> > > +# endif
> > > +       ret
> > > +
> > > +
> > > +       .p2align 4
> > > +L(more_1x_vec):
> > >         /* From VEC to 2 * VEC.  No branch when size == VEC_SIZE.  */
> > >         VMOVU   (%rsi), %YMM1
> > >         /* Use compare not equals to directly check for mismatch.  */
> > > -       VPCMP   $4, (%rdi), %YMM1, %k1
> > > +       VPCMP   $4,(%rdi), %YMM1, %k1
> > >         kmovd   %k1, %eax
> > >         /* NB: eax must be destination register if going to
> > >            L(return_vec_[0,2]). For L(return_vec_3) destination register
> > > @@ -131,13 +170,13 @@ ENTRY_P2ALIGN (MEMCMP, 6)
> > >
> > >         /* Check third and fourth VEC no matter what.  */
> > >         VMOVU   (VEC_SIZE * 2)(%rsi), %YMM3
> > > -       VPCMP   $4, (VEC_SIZE * 2)(%rdi), %YMM3, %k1
> > > +       VPCMP   $4,(VEC_SIZE * 2)(%rdi), %YMM3, %k1
> > >         kmovd   %k1, %eax
> > >         testl   %eax, %eax
> > >         jnz     L(return_vec_2)
> > >
> > >         VMOVU   (VEC_SIZE * 3)(%rsi), %YMM4
> > > -       VPCMP   $4, (VEC_SIZE * 3)(%rdi), %YMM4, %k1
> > > +       VPCMP   $4,(VEC_SIZE * 3)(%rdi), %YMM4, %k1
> > >         kmovd   %k1, %ecx
> > >         testl   %ecx, %ecx
> > >         jnz     L(return_vec_3)
> > > @@ -169,7 +208,7 @@ ENTRY_P2ALIGN (MEMCMP, 6)
> > >         VMOVU   (VEC_SIZE * 3)(%rsi), %YMM4
> > >         /* Ternary logic to xor (VEC_SIZE * 3)(%rdi) with YMM4 while
> > >            oring with YMM1. Result is stored in YMM4.  */
> > > -       vpternlogd $0xde, (VEC_SIZE * 3)(%rdi), %YMM1, %YMM4
> > > +       vpternlogd $0xde,(VEC_SIZE * 3)(%rdi), %YMM1, %YMM4
> > >
> > >         /* Or together YMM2, YMM3, and YMM4 into YMM4.  */
> > >         vpternlogd $0xfe, %YMM2, %YMM3, %YMM4
> > > @@ -184,7 +223,8 @@ ENTRY_P2ALIGN (MEMCMP, 6)
> > >         /* NB: eax must be zero to reach here.  */
> > >         ret
> > >
> > > -       .p2align 4
> > > +
> > > +       .p2align 4,, 8
> > >  L(8x_end_return_vec_0_1_2_3):
> > >         movq    %rdx, %rdi
> > >  L(8x_return_vec_0_1_2_3):
> > > @@ -222,23 +262,6 @@ L(return_vec_3):
> > >  # endif
> > >         ret
> > >
> > > -       .p2align 4
> > > -L(return_vec_0):
> > > -       tzcntl  %eax, %eax
> > > -# ifdef USE_AS_WMEMCMP
> > > -       movl    (%rdi, %rax, CHAR_SIZE), %ecx
> > > -       xorl    %edx, %edx
> > > -       cmpl    (%rsi, %rax, CHAR_SIZE), %ecx
> > > -       /* NB: no partial register stall here because xorl zero idiom
> > > -          above.  */
> > > -       setg    %dl
> > > -       leal    -1(%rdx, %rdx), %eax
> > > -# else
> > > -       movzbl  (%rsi, %rax), %ecx
> > > -       movzbl  (%rdi, %rax), %eax
> > > -       subl    %ecx, %eax
> > > -# endif
> > > -       ret
> > >
> > >         .p2align 4
> > >  L(return_vec_1):
> > > @@ -297,7 +320,7 @@ L(loop_4x_vec):
> > >         VMOVU   (VEC_SIZE * 2)(%rsi, %rdi), %YMM3
> > >         vpxorq  (VEC_SIZE * 2)(%rdi), %YMM3, %YMM3
> > >         VMOVU   (VEC_SIZE * 3)(%rsi, %rdi), %YMM4
> > > -       vpternlogd $0xde, (VEC_SIZE * 3)(%rdi), %YMM1, %YMM4
> > > +       vpternlogd $0xde,(VEC_SIZE * 3)(%rdi), %YMM1, %YMM4
> > >         vpternlogd $0xfe, %YMM2, %YMM3, %YMM4
> > >         VPTEST  %YMM4, %YMM4, %k1
> > >         kmovd   %k1, %ecx
> > > @@ -324,7 +347,7 @@ L(loop_4x_vec):
> > >         VMOVU   VEC_SIZE(%rsi, %rdx), %YMM2
> > >         vpxorq  VEC_SIZE(%rdx), %YMM2, %YMM2
> > >         VMOVU   (VEC_SIZE * 3)(%rsi, %rdx), %YMM4
> > > -       vpternlogd $0xde, (VEC_SIZE * 3)(%rdx), %YMM1, %YMM4
> > > +       vpternlogd $0xde,(VEC_SIZE * 3)(%rdx), %YMM1, %YMM4
> > >         vpternlogd $0xfe, %YMM2, %YMM3, %YMM4
> > >         VPTEST  %YMM4, %YMM4, %k1
> > >         kmovd   %k1, %ecx
> > > @@ -336,14 +359,14 @@ L(loop_4x_vec):
> > >         /* Only entry is from L(more_8x_vec).  */
> > >         .p2align 4,, 10
> > >  L(8x_last_2x_vec):
> > > -       VPCMP   $4, (VEC_SIZE * 2)(%rdx), %YMM3, %k1
> > > +       VPCMP   $4,(VEC_SIZE * 2)(%rdx), %YMM3, %k1
> > >         kmovd   %k1, %eax
> > >         testl   %eax, %eax
> > >         jnz     L(8x_return_vec_2)
> > >         /* Naturally aligned to 16 bytes.  */
> > >  L(8x_last_1x_vec):
> > >         VMOVU   (VEC_SIZE * 3)(%rsi, %rdx), %YMM1
> > > -       VPCMP   $4, (VEC_SIZE * 3)(%rdx), %YMM1, %k1
> > > +       VPCMP   $4,(VEC_SIZE * 3)(%rdx), %YMM1, %k1
> > >         kmovd   %k1, %eax
> > >         testl   %eax, %eax
> > >         jnz     L(8x_return_vec_3)
> > > @@ -392,7 +415,9 @@ L(last_1x_vec):
> > >         jnz     L(return_vec_0_end)
> > >         ret
> > >
> > > -       .p2align 4,, 10
> > > +
> > > +       /* Don't align. Takes 2-fetch blocks either way and aligning
> > > +          will cause code to spill into another cacheline.  */
> > >  L(return_vec_1_end):
> > >         /* Use bsf to save code size. This is necessary to have
> > >            L(one_or_less) fit in aligning bytes between.  */
> > > @@ -411,31 +436,8 @@ L(return_vec_1_end):
> > >  # endif
> > >         ret
> > >
> > > -       /* NB: L(one_or_less) fits in alignment padding between
> > > -          L(return_vec_1_end) and L(return_vec_0_end).  */
> > > -# ifdef USE_AS_WMEMCMP
> > > -L(one_or_less):
> > > -       jb      L(zero)
> > > -       movl    (%rdi), %ecx
> > > -       xorl    %edx, %edx
> > > -       cmpl    (%rsi), %ecx
> > > -       je      L(zero)
> > > -       setg    %dl
> > > -       leal    -1(%rdx, %rdx), %eax
> > > -       ret
> > > -# else
> > > -L(one_or_less):
> > > -       jb      L(zero)
> > > -       movzbl  (%rsi), %ecx
> > > -       movzbl  (%rdi), %eax
> > > -       subl    %ecx, %eax
> > > -       ret
> > > -# endif
> > > -L(zero):
> > > -       xorl    %eax, %eax
> > > -       ret
> > > -
> > > -       .p2align 4
> > > +       /* Don't align. Takes 2-fetch blocks either way and aligning
> > > +          will cause code to spill into another cacheline.  */
> > >  L(return_vec_0_end):
> > >         tzcntl  %eax, %eax
> > >         addl    %edx, %eax
> > > @@ -451,146 +453,7 @@ L(return_vec_0_end):
> > >         subl    %ecx, %eax
> > >  # endif
> > >         ret
> > > +       /* 1-byte until next cache line.  */
> > >
> > > -       .p2align 4
> > > -L(less_vec):
> > > -       /* Check if one or less CHAR. This is necessary for size == 0
> > > -          but is also faster for size == CHAR_SIZE.  */
> > > -       cmpl    $1, %edx
> > > -       jbe     L(one_or_less)
> > > -
> > > -       /* Check if loading one VEC from either s1 or s2 could cause a
> > > -          page cross. This can have false positives but is by far the
> > > -          fastest method.  */
> > > -       movl    %edi, %eax
> > > -       orl     %esi, %eax
> > > -       andl    $(PAGE_SIZE - 1), %eax
> > > -       cmpl    $(PAGE_SIZE - VEC_SIZE), %eax
> > > -       jg      L(page_cross_less_vec)
> > > -
> > > -       /* No page cross possible.  */
> > > -       VMOVU   (%rsi), %YMM2
> > > -       VPCMP   $4, (%rdi), %YMM2, %k1
> > > -       kmovd   %k1, %eax
> > > -       /* Check if any matches where in bounds. Intentionally not
> > > -          storing result in eax to limit dependency chain if it goes to
> > > -          L(return_vec_0_lv).  */
> > > -       bzhil   %edx, %eax, %edx
> > > -       jnz     L(return_vec_0_lv)
> > > -       xorl    %eax, %eax
> > > -       ret
> > > -
> > > -       /* Essentially duplicate of L(return_vec_0). Ends up not costing
> > > -          any code as shrinks L(less_vec) by allowing 2-byte encoding of
> > > -          the jump and ends up fitting in aligning bytes. As well fits on
> > > -          same cache line as L(less_vec) so also saves a line from having
> > > -          to be fetched on cold calls to memcmp.  */
> > > -       .p2align 4,, 4
> > > -L(return_vec_0_lv):
> > > -       tzcntl  %eax, %eax
> > > -# ifdef USE_AS_WMEMCMP
> > > -       movl    (%rdi, %rax, CHAR_SIZE), %ecx
> > > -       xorl    %edx, %edx
> > > -       cmpl    (%rsi, %rax, CHAR_SIZE), %ecx
> > > -       /* NB: no partial register stall here because xorl zero idiom
> > > -          above.  */
> > > -       setg    %dl
> > > -       leal    -1(%rdx, %rdx), %eax
> > > -# else
> > > -       movzbl  (%rsi, %rax), %ecx
> > > -       movzbl  (%rdi, %rax), %eax
> > > -       subl    %ecx, %eax
> > > -# endif
> > > -       ret
> > > -
> > > -       .p2align 4
> > > -L(page_cross_less_vec):
> > > -       /* if USE_AS_WMEMCMP it can only be 0, 4, 8, 12, 16, 20, 24, 28
> > > -          bytes.  */
> > > -       cmpl    $(16 / CHAR_SIZE), %edx
> > > -       jae     L(between_16_31)
> > > -# ifndef USE_AS_WMEMCMP
> > > -       cmpl    $8, %edx
> > > -       jae     L(between_8_15)
> > > -       cmpl    $4, %edx
> > > -       jb      L(between_2_3)
> > > -
> > > -       /* Load as big endian with overlapping movbe to avoid branches.
> > > -        */
> > > -       movbe   (%rdi), %eax
> > > -       movbe   (%rsi), %ecx
> > > -       shlq    $32, %rax
> > > -       shlq    $32, %rcx
> > > -       movbe   -4(%rdi, %rdx), %edi
> > > -       movbe   -4(%rsi, %rdx), %esi
> > > -       orq     %rdi, %rax
> > > -       orq     %rsi, %rcx
> > > -       subq    %rcx, %rax
> > > -       /* edx is guranteed to be positive int32 in range [4, 7].  */
> > > -       cmovne  %edx, %eax
> > > -       /* ecx is -1 if rcx > rax. Otherwise 0.  */
> > > -       sbbl    %ecx, %ecx
> > > -       /* If rcx > rax, then ecx is 0 and eax is positive. If rcx ==
> > > -          rax then eax and ecx are zero. If rax < rax then ecx is -1 so
> > > -          eax doesn't matter.  */
> > > -       orl     %ecx, %eax
> > > -       ret
> > > -
> > > -       .p2align 4,, 8
> > > -L(between_8_15):
> > > -# endif
> > > -       /* If USE_AS_WMEMCMP fall through into 8-15 byte case.  */
> > > -       vmovq   (%rdi), %xmm1
> > > -       vmovq   (%rsi), %xmm2
> > > -       VPCMP   $4, %xmm1, %xmm2, %k1
> > > -       kmovd   %k1, %eax
> > > -       testl   %eax, %eax
> > > -       jnz     L(return_vec_0_lv)
> > > -       /* Use overlapping loads to avoid branches.  */
> > > -       vmovq   -8(%rdi, %rdx, CHAR_SIZE), %xmm1
> > > -       vmovq   -8(%rsi, %rdx, CHAR_SIZE), %xmm2
> > > -       VPCMP   $4, %xmm1, %xmm2, %k1
> > > -       addl    $(CHAR_PER_VEC - (8 / CHAR_SIZE)), %edx
> > > -       kmovd   %k1, %eax
> > > -       testl   %eax, %eax
> > > -       jnz     L(return_vec_0_end)
> > > -       ret
> > > -
> > > -       .p2align 4,, 8
> > > -L(between_16_31):
> > > -       /* From 16 to 31 bytes.  No branch when size == 16.  */
> > > -
> > > -       /* Use movups to save code size.  */
> > > -       vmovdqu (%rsi), %xmm2
> > > -       VPCMP   $4, (%rdi), %xmm2, %k1
> > > -       kmovd   %k1, %eax
> > > -       testl   %eax, %eax
> > > -       jnz     L(return_vec_0_lv)
> > > -       /* Use overlapping loads to avoid branches.  */
> > > -       vmovdqu -16(%rsi, %rdx, CHAR_SIZE), %xmm2
> > > -       VPCMP   $4, -16(%rdi, %rdx, CHAR_SIZE), %xmm2, %k1
> > > -       addl    $(CHAR_PER_VEC - (16 / CHAR_SIZE)), %edx
> > > -       kmovd   %k1, %eax
> > > -       testl   %eax, %eax
> > > -       jnz     L(return_vec_0_end)
> > > -       ret
> > > -
> > > -# ifndef USE_AS_WMEMCMP
> > > -L(between_2_3):
> > > -       /* Load as big endian to avoid branches.  */
> > > -       movzwl  (%rdi), %eax
> > > -       movzwl  (%rsi), %ecx
> > > -       shll    $8, %eax
> > > -       shll    $8, %ecx
> > > -       bswap   %eax
> > > -       bswap   %ecx
> > > -       movzbl  -1(%rdi, %rdx), %edi
> > > -       movzbl  -1(%rsi, %rdx), %esi
> > > -       orl     %edi, %eax
> > > -       orl     %esi, %ecx
> > > -       /* Subtraction is okay because the upper 8 bits are zero.  */
> > > -       subl    %ecx, %eax
> > > -       ret
> > > -# endif
> > >  END (MEMCMP)
> > >  #endif
> > > --
> > > 2.25.1
> > >
> >
> > LGTM.
> >
> > Reviewed-by: H.J. Lu <hjl.tools@gmail.com>
> >
> > Thanks.
>
> Thanks pushed.
> >
> > --
> > H.J.

I would like to backport this patch to release branches.
Any comments or objections?

--Sunil
diff mbox series

Patch

diff --git a/sysdeps/x86_64/multiarch/memcmp-evex-movbe.S b/sysdeps/x86_64/multiarch/memcmp-evex-movbe.S
index 640f6757fa..d2899e7c70 100644
--- a/sysdeps/x86_64/multiarch/memcmp-evex-movbe.S
+++ b/sysdeps/x86_64/multiarch/memcmp-evex-movbe.S
@@ -62,15 +62,18 @@  Latency:
 # define VMOVU		vmovdqu64
 
 # ifdef USE_AS_WMEMCMP
+#  define VMOVU_MASK	vmovdqu32
 #  define CHAR_SIZE	4
 #  define VPCMP	vpcmpd
 #  define VPTEST	vptestmd
 # else
+#  define VMOVU_MASK	vmovdqu8
 #  define CHAR_SIZE	1
 #  define VPCMP	vpcmpub
 #  define VPTEST	vptestmb
 # endif
 
+
 # define VEC_SIZE	32
 # define PAGE_SIZE	4096
 # define CHAR_PER_VEC	(VEC_SIZE / CHAR_SIZE)
@@ -102,12 +105,48 @@  ENTRY_P2ALIGN (MEMCMP, 6)
 	movl	%edx, %edx
 # endif
 	cmp	$CHAR_PER_VEC, %RDX_LP
-	jb	L(less_vec)
+	/* Fall through for [0, VEC_SIZE] as its the hottest.  */
+	ja	L(more_1x_vec)
+
+	/* Create mask for CHAR's we want to compare. This allows us to
+	   avoid having to include page cross logic.  */
+	movl	$-1, %ecx
+	bzhil	%edx, %ecx, %ecx
+	kmovd	%ecx, %k2
+
+	/* Safe to load full ymm with mask.  */
+	VMOVU_MASK (%rsi), %YMM2{%k2}
+	VPCMP	$4,(%rdi), %YMM2, %k1{%k2}
+	kmovd	%k1, %eax
+	testl	%eax, %eax
+	jnz	L(return_vec_0)
+	ret
 
+	.p2align 4
+L(return_vec_0):
+	tzcntl	%eax, %eax
+# ifdef USE_AS_WMEMCMP
+	movl	(%rdi, %rax, CHAR_SIZE), %ecx
+	xorl	%edx, %edx
+	cmpl	(%rsi, %rax, CHAR_SIZE), %ecx
+	/* NB: no partial register stall here because xorl zero idiom
+	   above.  */
+	setg	%dl
+	leal	-1(%rdx, %rdx), %eax
+# else
+	movzbl	(%rsi, %rax), %ecx
+	movzbl	(%rdi, %rax), %eax
+	subl	%ecx, %eax
+# endif
+	ret
+
+
+	.p2align 4
+L(more_1x_vec):
 	/* From VEC to 2 * VEC.  No branch when size == VEC_SIZE.  */
 	VMOVU	(%rsi), %YMM1
 	/* Use compare not equals to directly check for mismatch.  */
-	VPCMP	$4, (%rdi), %YMM1, %k1
+	VPCMP	$4,(%rdi), %YMM1, %k1
 	kmovd	%k1, %eax
 	/* NB: eax must be destination register if going to
 	   L(return_vec_[0,2]). For L(return_vec_3) destination register
@@ -131,13 +170,13 @@  ENTRY_P2ALIGN (MEMCMP, 6)
 
 	/* Check third and fourth VEC no matter what.  */
 	VMOVU	(VEC_SIZE * 2)(%rsi), %YMM3
-	VPCMP	$4, (VEC_SIZE * 2)(%rdi), %YMM3, %k1
+	VPCMP	$4,(VEC_SIZE * 2)(%rdi), %YMM3, %k1
 	kmovd	%k1, %eax
 	testl	%eax, %eax
 	jnz	L(return_vec_2)
 
 	VMOVU	(VEC_SIZE * 3)(%rsi), %YMM4
-	VPCMP	$4, (VEC_SIZE * 3)(%rdi), %YMM4, %k1
+	VPCMP	$4,(VEC_SIZE * 3)(%rdi), %YMM4, %k1
 	kmovd	%k1, %ecx
 	testl	%ecx, %ecx
 	jnz	L(return_vec_3)
@@ -169,7 +208,7 @@  ENTRY_P2ALIGN (MEMCMP, 6)
 	VMOVU	(VEC_SIZE * 3)(%rsi), %YMM4
 	/* Ternary logic to xor (VEC_SIZE * 3)(%rdi) with YMM4 while
 	   oring with YMM1. Result is stored in YMM4.  */
-	vpternlogd $0xde, (VEC_SIZE * 3)(%rdi), %YMM1, %YMM4
+	vpternlogd $0xde,(VEC_SIZE * 3)(%rdi), %YMM1, %YMM4
 
 	/* Or together YMM2, YMM3, and YMM4 into YMM4.  */
 	vpternlogd $0xfe, %YMM2, %YMM3, %YMM4
@@ -184,7 +223,8 @@  ENTRY_P2ALIGN (MEMCMP, 6)
 	/* NB: eax must be zero to reach here.  */
 	ret
 
-	.p2align 4
+
+	.p2align 4,, 8
 L(8x_end_return_vec_0_1_2_3):
 	movq	%rdx, %rdi
 L(8x_return_vec_0_1_2_3):
@@ -222,23 +262,6 @@  L(return_vec_3):
 # endif
 	ret
 
-	.p2align 4
-L(return_vec_0):
-	tzcntl	%eax, %eax
-# ifdef USE_AS_WMEMCMP
-	movl	(%rdi, %rax, CHAR_SIZE), %ecx
-	xorl	%edx, %edx
-	cmpl	(%rsi, %rax, CHAR_SIZE), %ecx
-	/* NB: no partial register stall here because xorl zero idiom
-	   above.  */
-	setg	%dl
-	leal	-1(%rdx, %rdx), %eax
-# else
-	movzbl	(%rsi, %rax), %ecx
-	movzbl	(%rdi, %rax), %eax
-	subl	%ecx, %eax
-# endif
-	ret
 
 	.p2align 4
 L(return_vec_1):
@@ -297,7 +320,7 @@  L(loop_4x_vec):
 	VMOVU	(VEC_SIZE * 2)(%rsi, %rdi), %YMM3
 	vpxorq	(VEC_SIZE * 2)(%rdi), %YMM3, %YMM3
 	VMOVU	(VEC_SIZE * 3)(%rsi, %rdi), %YMM4
-	vpternlogd $0xde, (VEC_SIZE * 3)(%rdi), %YMM1, %YMM4
+	vpternlogd $0xde,(VEC_SIZE * 3)(%rdi), %YMM1, %YMM4
 	vpternlogd $0xfe, %YMM2, %YMM3, %YMM4
 	VPTEST	%YMM4, %YMM4, %k1
 	kmovd	%k1, %ecx
@@ -324,7 +347,7 @@  L(loop_4x_vec):
 	VMOVU	VEC_SIZE(%rsi, %rdx), %YMM2
 	vpxorq	VEC_SIZE(%rdx), %YMM2, %YMM2
 	VMOVU	(VEC_SIZE * 3)(%rsi, %rdx), %YMM4
-	vpternlogd $0xde, (VEC_SIZE * 3)(%rdx), %YMM1, %YMM4
+	vpternlogd $0xde,(VEC_SIZE * 3)(%rdx), %YMM1, %YMM4
 	vpternlogd $0xfe, %YMM2, %YMM3, %YMM4
 	VPTEST	%YMM4, %YMM4, %k1
 	kmovd	%k1, %ecx
@@ -336,14 +359,14 @@  L(loop_4x_vec):
 	/* Only entry is from L(more_8x_vec).  */
 	.p2align 4,, 10
 L(8x_last_2x_vec):
-	VPCMP	$4, (VEC_SIZE * 2)(%rdx), %YMM3, %k1
+	VPCMP	$4,(VEC_SIZE * 2)(%rdx), %YMM3, %k1
 	kmovd	%k1, %eax
 	testl	%eax, %eax
 	jnz	L(8x_return_vec_2)
 	/* Naturally aligned to 16 bytes.  */
 L(8x_last_1x_vec):
 	VMOVU	(VEC_SIZE * 3)(%rsi, %rdx), %YMM1
-	VPCMP	$4, (VEC_SIZE * 3)(%rdx), %YMM1, %k1
+	VPCMP	$4,(VEC_SIZE * 3)(%rdx), %YMM1, %k1
 	kmovd	%k1, %eax
 	testl	%eax, %eax
 	jnz	L(8x_return_vec_3)
@@ -392,7 +415,9 @@  L(last_1x_vec):
 	jnz	L(return_vec_0_end)
 	ret
 
-	.p2align 4,, 10
+
+	/* Don't align. Takes 2-fetch blocks either way and aligning
+	   will cause code to spill into another cacheline.  */
 L(return_vec_1_end):
 	/* Use bsf to save code size. This is necessary to have
 	   L(one_or_less) fit in aligning bytes between.  */
@@ -411,31 +436,8 @@  L(return_vec_1_end):
 # endif
 	ret
 
-	/* NB: L(one_or_less) fits in alignment padding between
-	   L(return_vec_1_end) and L(return_vec_0_end).  */
-# ifdef USE_AS_WMEMCMP
-L(one_or_less):
-	jb	L(zero)
-	movl	(%rdi), %ecx
-	xorl	%edx, %edx
-	cmpl	(%rsi), %ecx
-	je	L(zero)
-	setg	%dl
-	leal	-1(%rdx, %rdx), %eax
-	ret
-# else
-L(one_or_less):
-	jb	L(zero)
-	movzbl	(%rsi), %ecx
-	movzbl	(%rdi), %eax
-	subl	%ecx, %eax
-	ret
-# endif
-L(zero):
-	xorl	%eax, %eax
-	ret
-
-	.p2align 4
+	/* Don't align. Takes 2-fetch blocks either way and aligning
+	   will cause code to spill into another cacheline.  */
 L(return_vec_0_end):
 	tzcntl	%eax, %eax
 	addl	%edx, %eax
@@ -451,146 +453,7 @@  L(return_vec_0_end):
 	subl	%ecx, %eax
 # endif
 	ret
+	/* 1-byte until next cache line.  */
 
-	.p2align 4
-L(less_vec):
-	/* Check if one or less CHAR. This is necessary for size == 0
-	   but is also faster for size == CHAR_SIZE.  */
-	cmpl	$1, %edx
-	jbe	L(one_or_less)
-
-	/* Check if loading one VEC from either s1 or s2 could cause a
-	   page cross. This can have false positives but is by far the
-	   fastest method.  */
-	movl	%edi, %eax
-	orl	%esi, %eax
-	andl	$(PAGE_SIZE - 1), %eax
-	cmpl	$(PAGE_SIZE - VEC_SIZE), %eax
-	jg	L(page_cross_less_vec)
-
-	/* No page cross possible.  */
-	VMOVU	(%rsi), %YMM2
-	VPCMP	$4, (%rdi), %YMM2, %k1
-	kmovd	%k1, %eax
-	/* Check if any matches where in bounds. Intentionally not
-	   storing result in eax to limit dependency chain if it goes to
-	   L(return_vec_0_lv).  */
-	bzhil	%edx, %eax, %edx
-	jnz	L(return_vec_0_lv)
-	xorl	%eax, %eax
-	ret
-
-	/* Essentially duplicate of L(return_vec_0). Ends up not costing
-	   any code as shrinks L(less_vec) by allowing 2-byte encoding of
-	   the jump and ends up fitting in aligning bytes. As well fits on
-	   same cache line as L(less_vec) so also saves a line from having
-	   to be fetched on cold calls to memcmp.  */
-	.p2align 4,, 4
-L(return_vec_0_lv):
-	tzcntl	%eax, %eax
-# ifdef USE_AS_WMEMCMP
-	movl	(%rdi, %rax, CHAR_SIZE), %ecx
-	xorl	%edx, %edx
-	cmpl	(%rsi, %rax, CHAR_SIZE), %ecx
-	/* NB: no partial register stall here because xorl zero idiom
-	   above.  */
-	setg	%dl
-	leal	-1(%rdx, %rdx), %eax
-# else
-	movzbl	(%rsi, %rax), %ecx
-	movzbl	(%rdi, %rax), %eax
-	subl	%ecx, %eax
-# endif
-	ret
-
-	.p2align 4
-L(page_cross_less_vec):
-	/* if USE_AS_WMEMCMP it can only be 0, 4, 8, 12, 16, 20, 24, 28
-	   bytes.  */
-	cmpl	$(16 / CHAR_SIZE), %edx
-	jae	L(between_16_31)
-# ifndef USE_AS_WMEMCMP
-	cmpl	$8, %edx
-	jae	L(between_8_15)
-	cmpl	$4, %edx
-	jb	L(between_2_3)
-
-	/* Load as big endian with overlapping movbe to avoid branches.
-	 */
-	movbe	(%rdi), %eax
-	movbe	(%rsi), %ecx
-	shlq	$32, %rax
-	shlq	$32, %rcx
-	movbe	-4(%rdi, %rdx), %edi
-	movbe	-4(%rsi, %rdx), %esi
-	orq	%rdi, %rax
-	orq	%rsi, %rcx
-	subq	%rcx, %rax
-	/* edx is guranteed to be positive int32 in range [4, 7].  */
-	cmovne	%edx, %eax
-	/* ecx is -1 if rcx > rax. Otherwise 0.  */
-	sbbl	%ecx, %ecx
-	/* If rcx > rax, then ecx is 0 and eax is positive. If rcx ==
-	   rax then eax and ecx are zero. If rax < rax then ecx is -1 so
-	   eax doesn't matter.  */
-	orl	%ecx, %eax
-	ret
-
-	.p2align 4,, 8
-L(between_8_15):
-# endif
-	/* If USE_AS_WMEMCMP fall through into 8-15 byte case.  */
-	vmovq	(%rdi), %xmm1
-	vmovq	(%rsi), %xmm2
-	VPCMP	$4, %xmm1, %xmm2, %k1
-	kmovd	%k1, %eax
-	testl	%eax, %eax
-	jnz	L(return_vec_0_lv)
-	/* Use overlapping loads to avoid branches.  */
-	vmovq	-8(%rdi, %rdx, CHAR_SIZE), %xmm1
-	vmovq	-8(%rsi, %rdx, CHAR_SIZE), %xmm2
-	VPCMP	$4, %xmm1, %xmm2, %k1
-	addl	$(CHAR_PER_VEC - (8 / CHAR_SIZE)), %edx
-	kmovd	%k1, %eax
-	testl	%eax, %eax
-	jnz	L(return_vec_0_end)
-	ret
-
-	.p2align 4,, 8
-L(between_16_31):
-	/* From 16 to 31 bytes.  No branch when size == 16.  */
-
-	/* Use movups to save code size.  */
-	vmovdqu	(%rsi), %xmm2
-	VPCMP	$4, (%rdi), %xmm2, %k1
-	kmovd	%k1, %eax
-	testl	%eax, %eax
-	jnz	L(return_vec_0_lv)
-	/* Use overlapping loads to avoid branches.  */
-	vmovdqu	-16(%rsi, %rdx, CHAR_SIZE), %xmm2
-	VPCMP	$4, -16(%rdi, %rdx, CHAR_SIZE), %xmm2, %k1
-	addl	$(CHAR_PER_VEC - (16 / CHAR_SIZE)), %edx
-	kmovd	%k1, %eax
-	testl	%eax, %eax
-	jnz	L(return_vec_0_end)
-	ret
-
-# ifndef USE_AS_WMEMCMP
-L(between_2_3):
-	/* Load as big endian to avoid branches.  */
-	movzwl	(%rdi), %eax
-	movzwl	(%rsi), %ecx
-	shll	$8, %eax
-	shll	$8, %ecx
-	bswap	%eax
-	bswap	%ecx
-	movzbl	-1(%rdi, %rdx), %edi
-	movzbl	-1(%rsi, %rdx), %esi
-	orl	%edi, %eax
-	orl	%esi, %ecx
-	/* Subtraction is okay because the upper 8 bits are zero.  */
-	subl	%ecx, %eax
-	ret
-# endif
 END (MEMCMP)
 #endif