[v4,2/2] x86: Optimize strchr-evex.S

Message ID 20210423195625.2871522-2-goldstein.w.n@gmail.com
State Committed
Commit 7f3e7c262cab4e2401e4331a6ef29c428de02044
Headers
Series [v4,1/2] x86: Optimize strchr-avx2.S |

Commit Message

Noah Goldstein April 23, 2021, 7:56 p.m. UTC
  No bug. This commit optimizes strchr-evex.S. The optimizations are
mostly small things such as save an ALU in the alignment process,
saving a few instructions in the loop return. The one significant
change is saving 2 instructions in the 4x loop. test-strchr,
test-strchrnul, test-wcschr, and test-wcschrnul are all passing.

Signed-off-by: Noah Goldstein <goldstein.w.n@gmail.com>
---
 sysdeps/x86_64/multiarch/strchr-evex.S | 392 ++++++++++++++-----------
 1 file changed, 218 insertions(+), 174 deletions(-)
  

Comments

Sunil Pandey April 27, 2022, 11:54 p.m. UTC | #1
On Fri, Apr 23, 2021 at 2:57 PM Noah Goldstein via Libc-alpha
<libc-alpha@sourceware.org> wrote:
>
> No bug. This commit optimizes strchr-evex.S. The optimizations are
> mostly small things such as save an ALU in the alignment process,
> saving a few instructions in the loop return. The one significant
> change is saving 2 instructions in the 4x loop. test-strchr,
> test-strchrnul, test-wcschr, and test-wcschrnul are all passing.
>
> Signed-off-by: Noah Goldstein <goldstein.w.n@gmail.com>
> ---
>  sysdeps/x86_64/multiarch/strchr-evex.S | 392 ++++++++++++++-----------
>  1 file changed, 218 insertions(+), 174 deletions(-)
>
> diff --git a/sysdeps/x86_64/multiarch/strchr-evex.S b/sysdeps/x86_64/multiarch/strchr-evex.S
> index ddc86a7058..7f9d4ee48d 100644
> --- a/sysdeps/x86_64/multiarch/strchr-evex.S
> +++ b/sysdeps/x86_64/multiarch/strchr-evex.S
> @@ -32,13 +32,15 @@
>  #  define VPCMP                vpcmpd
>  #  define VPMINU       vpminud
>  #  define CHAR_REG     esi
> -#  define SHIFT_REG    r8d
> +#  define SHIFT_REG    ecx
> +#  define CHAR_SIZE    4
>  # else
>  #  define VPBROADCAST  vpbroadcastb
>  #  define VPCMP                vpcmpb
>  #  define VPMINU       vpminub
>  #  define CHAR_REG     sil
> -#  define SHIFT_REG    ecx
> +#  define SHIFT_REG    edx
> +#  define CHAR_SIZE    1
>  # endif
>
>  # define XMMZERO       xmm16
> @@ -56,23 +58,20 @@
>
>  # define VEC_SIZE 32
>  # define PAGE_SIZE 4096
> +# define CHAR_PER_VEC (VEC_SIZE / CHAR_SIZE)
>
>         .section .text.evex,"ax",@progbits
>  ENTRY (STRCHR)
> -       movl    %edi, %ecx
> -# ifndef USE_AS_STRCHRNUL
> -       xorl    %edx, %edx
> -# endif
> -
>         /* Broadcast CHAR to YMM0.      */
> -       VPBROADCAST %esi, %YMM0
> -
> +       VPBROADCAST     %esi, %YMM0
> +       movl    %edi, %eax
> +       andl    $(PAGE_SIZE - 1), %eax
>         vpxorq  %XMMZERO, %XMMZERO, %XMMZERO
>
> -       /* Check if we cross page boundary with one vector load.  */
> -       andl    $(PAGE_SIZE - 1), %ecx
> -       cmpl    $(PAGE_SIZE - VEC_SIZE), %ecx
> -       ja  L(cross_page_boundary)
> +       /* Check if we cross page boundary with one vector load.
> +          Otherwise it is safe to use an unaligned load.  */
> +       cmpl    $(PAGE_SIZE - VEC_SIZE), %eax
> +       ja      L(cross_page_boundary)
>
>         /* Check the first VEC_SIZE bytes. Search for both CHAR and the
>            null bytes.  */
> @@ -83,251 +82,296 @@ ENTRY (STRCHR)
>         VPMINU  %YMM2, %YMM1, %YMM2
>         /* Each bit in K0 represents a CHAR or a null byte in YMM1.  */
>         VPCMP   $0, %YMMZERO, %YMM2, %k0
> -       ktestd  %k0, %k0
> -       jz      L(more_vecs)
>         kmovd   %k0, %eax
> +       testl   %eax, %eax
> +       jz      L(aligned_more)
>         tzcntl  %eax, %eax
> -       /* Found CHAR or the null byte.  */
>  # ifdef USE_AS_WCSCHR
> -       /* NB: Multiply wchar_t count by 4 to get the number of bytes.  */
> -       leaq    (%rdi, %rax, 4), %rax
> +       /* NB: Multiply wchar_t count by 4 to get the number of bytes.
> +        */
> +       leaq    (%rdi, %rax, CHAR_SIZE), %rax
>  # else
>         addq    %rdi, %rax
>  # endif
>  # ifndef USE_AS_STRCHRNUL
> -       cmp (%rax), %CHAR_REG
> -       cmovne  %rdx, %rax
> +       /* Found CHAR or the null byte.  */
> +       cmp     (%rax), %CHAR_REG
> +       jne     L(zero)
>  # endif
>         ret
>
> -       .p2align 4
> -L(more_vecs):
> -       /* Align data for aligned loads in the loop.  */
> -       andq    $-VEC_SIZE, %rdi
> -L(aligned_more):
> -
> -       /* Check the next 4 * VEC_SIZE.  Only one VEC_SIZE at a time
> -          since data is only aligned to VEC_SIZE.      */
> -       VMOVA   VEC_SIZE(%rdi), %YMM1
> -       addq    $VEC_SIZE, %rdi
> -
> -       /* Leaves only CHARS matching esi as 0.  */
> -       vpxorq  %YMM1, %YMM0, %YMM2
> -       VPMINU  %YMM2, %YMM1, %YMM2
> -       /* Each bit in K0 represents a CHAR or a null byte in YMM1.  */
> -       VPCMP   $0, %YMMZERO, %YMM2, %k0
> -       kmovd   %k0, %eax
> -       testl   %eax, %eax
> -       jnz     L(first_vec_x0)
> -
> -       VMOVA   VEC_SIZE(%rdi), %YMM1
> -       /* Leaves only CHARS matching esi as 0.  */
> -       vpxorq  %YMM1, %YMM0, %YMM2
> -       VPMINU  %YMM2, %YMM1, %YMM2
> -       /* Each bit in K0 represents a CHAR or a null byte in YMM1.  */
> -       VPCMP   $0, %YMMZERO, %YMM2, %k0
> -       kmovd   %k0, %eax
> -       testl   %eax, %eax
> -       jnz     L(first_vec_x1)
> -
> -       VMOVA   (VEC_SIZE * 2)(%rdi), %YMM1
> -       /* Leaves only CHARS matching esi as 0.  */
> -       vpxorq  %YMM1, %YMM0, %YMM2
> -       VPMINU  %YMM2, %YMM1, %YMM2
> -       /* Each bit in K0 represents a CHAR or a null byte in YMM1.  */
> -       VPCMP   $0, %YMMZERO, %YMM2, %k0
> -       kmovd   %k0, %eax
> -       testl   %eax, %eax
> -       jnz     L(first_vec_x2)
> -
> -       VMOVA   (VEC_SIZE * 3)(%rdi), %YMM1
> -       /* Leaves only CHARS matching esi as 0.  */
> -       vpxorq  %YMM1, %YMM0, %YMM2
> -       VPMINU  %YMM2, %YMM1, %YMM2
> -       /* Each bit in K0 represents a CHAR or a null byte in YMM1.  */
> -       VPCMP   $0, %YMMZERO, %YMM2, %k0
> -       ktestd  %k0, %k0
> -       jz      L(prep_loop_4x)
> -
> -       kmovd   %k0, %eax
> +       /* .p2align 5 helps keep performance more consistent if ENTRY()
> +          alignment % 32 was either 16 or 0. As well this makes the
> +          alignment % 32 of the loop_4x_vec fixed which makes tuning it
> +          easier.  */
> +       .p2align 5
> +L(first_vec_x3):
>         tzcntl  %eax, %eax
> +# ifndef USE_AS_STRCHRNUL
>         /* Found CHAR or the null byte.  */
> -# ifdef USE_AS_WCSCHR
> -       /* NB: Multiply wchar_t count by 4 to get the number of bytes.  */
> -       leaq    (VEC_SIZE * 3)(%rdi, %rax, 4), %rax
> -# else
> -       leaq    (VEC_SIZE * 3)(%rdi, %rax), %rax
> +       cmp     (VEC_SIZE * 3)(%rdi, %rax, CHAR_SIZE), %CHAR_REG
> +       jne     L(zero)
>  # endif
> +       /* NB: Multiply sizeof char type (1 or 4) to get the number of
> +          bytes.  */
> +       leaq    (VEC_SIZE * 3)(%rdi, %rax, CHAR_SIZE), %rax
> +       ret
> +
>  # ifndef USE_AS_STRCHRNUL
> -       cmp (%rax), %CHAR_REG
> -       cmovne  %rdx, %rax
> -# endif
> +L(zero):
> +       xorl    %eax, %eax
>         ret
> +# endif
>
>         .p2align 4
> -L(first_vec_x0):
> +L(first_vec_x4):
> +# ifndef USE_AS_STRCHRNUL
> +       /* Check to see if first match was CHAR (k0) or null (k1).  */
> +       kmovd   %k0, %eax
>         tzcntl  %eax, %eax
> -       /* Found CHAR or the null byte.  */
> -# ifdef USE_AS_WCSCHR
> -       /* NB: Multiply wchar_t count by 4 to get the number of bytes.  */
> -       leaq    (%rdi, %rax, 4), %rax
> +       kmovd   %k1, %ecx
> +       /* bzhil will not be 0 if first match was null.  */
> +       bzhil   %eax, %ecx, %ecx
> +       jne     L(zero)
>  # else
> -       addq    %rdi, %rax
> -# endif
> -# ifndef USE_AS_STRCHRNUL
> -       cmp (%rax), %CHAR_REG
> -       cmovne  %rdx, %rax
> +       /* Combine CHAR and null matches.  */
> +       kord    %k0, %k1, %k0
> +       kmovd   %k0, %eax
> +       tzcntl  %eax, %eax
>  # endif
> +       /* NB: Multiply sizeof char type (1 or 4) to get the number of
> +          bytes.  */
> +       leaq    (VEC_SIZE * 4)(%rdi, %rax, CHAR_SIZE), %rax
>         ret
>
>         .p2align 4
>  L(first_vec_x1):
>         tzcntl  %eax, %eax
> -       /* Found CHAR or the null byte.  */
> -# ifdef USE_AS_WCSCHR
> -       /* NB: Multiply wchar_t count by 4 to get the number of bytes.  */
> -       leaq    VEC_SIZE(%rdi, %rax, 4), %rax
> -# else
> -       leaq    VEC_SIZE(%rdi, %rax), %rax
> -# endif
>  # ifndef USE_AS_STRCHRNUL
> -       cmp (%rax), %CHAR_REG
> -       cmovne  %rdx, %rax
> +       /* Found CHAR or the null byte.  */
> +       cmp     (VEC_SIZE)(%rdi, %rax, CHAR_SIZE), %CHAR_REG
> +       jne     L(zero)
> +
>  # endif
> +       /* NB: Multiply sizeof char type (1 or 4) to get the number of
> +          bytes.  */
> +       leaq    (VEC_SIZE)(%rdi, %rax, CHAR_SIZE), %rax
>         ret
>
>         .p2align 4
>  L(first_vec_x2):
> +# ifndef USE_AS_STRCHRNUL
> +       /* Check to see if first match was CHAR (k0) or null (k1).  */
> +       kmovd   %k0, %eax
>         tzcntl  %eax, %eax
> -       /* Found CHAR or the null byte.  */
> -# ifdef USE_AS_WCSCHR
> -       /* NB: Multiply wchar_t count by 4 to get the number of bytes.  */
> -       leaq    (VEC_SIZE * 2)(%rdi, %rax, 4), %rax
> +       kmovd   %k1, %ecx
> +       /* bzhil will not be 0 if first match was null.  */
> +       bzhil   %eax, %ecx, %ecx
> +       jne     L(zero)
>  # else
> -       leaq    (VEC_SIZE * 2)(%rdi, %rax), %rax
> -# endif
> -# ifndef USE_AS_STRCHRNUL
> -       cmp (%rax), %CHAR_REG
> -       cmovne  %rdx, %rax
> +       /* Combine CHAR and null matches.  */
> +       kord    %k0, %k1, %k0
> +       kmovd   %k0, %eax
> +       tzcntl  %eax, %eax
>  # endif
> +       /* NB: Multiply sizeof char type (1 or 4) to get the number of
> +          bytes.  */
> +       leaq    (VEC_SIZE * 2)(%rdi, %rax, CHAR_SIZE), %rax
>         ret
>
> -L(prep_loop_4x):
> -       /* Align data to 4 * VEC_SIZE.  */
> +       .p2align 4
> +L(aligned_more):
> +       /* Align data to VEC_SIZE.  */
> +       andq    $-VEC_SIZE, %rdi
> +L(cross_page_continue):
> +       /* Check the next 4 * VEC_SIZE. Only one VEC_SIZE at a time since
> +          data is only aligned to VEC_SIZE. Use two alternating methods
> +          for checking VEC to balance latency and port contention.  */
> +
> +       /* This method has higher latency but has better port
> +          distribution.  */
> +       VMOVA   (VEC_SIZE)(%rdi), %YMM1
> +       /* Leaves only CHARS matching esi as 0.  */
> +       vpxorq  %YMM1, %YMM0, %YMM2
> +       VPMINU  %YMM2, %YMM1, %YMM2
> +       /* Each bit in K0 represents a CHAR or a null byte in YMM1.  */
> +       VPCMP   $0, %YMMZERO, %YMM2, %k0
> +       kmovd   %k0, %eax
> +       testl   %eax, %eax
> +       jnz     L(first_vec_x1)
> +
> +       /* This method has higher latency but has better port
> +          distribution.  */
> +       VMOVA   (VEC_SIZE * 2)(%rdi), %YMM1
> +       /* Each bit in K0 represents a CHAR in YMM1.  */
> +       VPCMP   $0, %YMM1, %YMM0, %k0
> +       /* Each bit in K1 represents a CHAR in YMM1.  */
> +       VPCMP   $0, %YMM1, %YMMZERO, %k1
> +       kortestd        %k0, %k1
> +       jnz     L(first_vec_x2)
> +
> +       VMOVA   (VEC_SIZE * 3)(%rdi), %YMM1
> +       /* Leaves only CHARS matching esi as 0.  */
> +       vpxorq  %YMM1, %YMM0, %YMM2
> +       VPMINU  %YMM2, %YMM1, %YMM2
> +       /* Each bit in K0 represents a CHAR or a null byte in YMM1.  */
> +       VPCMP   $0, %YMMZERO, %YMM2, %k0
> +       kmovd   %k0, %eax
> +       testl   %eax, %eax
> +       jnz     L(first_vec_x3)
> +
> +       VMOVA   (VEC_SIZE * 4)(%rdi), %YMM1
> +       /* Each bit in K0 represents a CHAR in YMM1.  */
> +       VPCMP   $0, %YMM1, %YMM0, %k0
> +       /* Each bit in K1 represents a CHAR in YMM1.  */
> +       VPCMP   $0, %YMM1, %YMMZERO, %k1
> +       kortestd        %k0, %k1
> +       jnz     L(first_vec_x4)
> +
> +       /* Align data to VEC_SIZE * 4 for the loop.  */
> +       addq    $VEC_SIZE, %rdi
>         andq    $-(VEC_SIZE * 4), %rdi
>
>         .p2align 4
>  L(loop_4x_vec):
> -       /* Compare 4 * VEC at a time forward.  */
> +       /* Check 4x VEC at a time. No penalty to imm32 offset with evex
> +          encoding.  */
>         VMOVA   (VEC_SIZE * 4)(%rdi), %YMM1
>         VMOVA   (VEC_SIZE * 5)(%rdi), %YMM2
>         VMOVA   (VEC_SIZE * 6)(%rdi), %YMM3
>         VMOVA   (VEC_SIZE * 7)(%rdi), %YMM4
>
> -       /* Leaves only CHARS matching esi as 0.  */
> +       /* For YMM1 and YMM3 use xor to set the CHARs matching esi to
> +          zero.  */
>         vpxorq  %YMM1, %YMM0, %YMM5
> -       vpxorq  %YMM2, %YMM0, %YMM6
> +       /* For YMM2 and YMM4 cmp not equals to CHAR and store result in
> +          k register. Its possible to save either 1 or 2 instructions
> +          using cmp no equals method for either YMM1 or YMM1 and YMM3
> +          respectively but bottleneck on p5 makes it not worth it.  */
> +       VPCMP   $4, %YMM0, %YMM2, %k2
>         vpxorq  %YMM3, %YMM0, %YMM7
> -       vpxorq  %YMM4, %YMM0, %YMM8
> -
> -       VPMINU  %YMM5, %YMM1, %YMM5
> -       VPMINU  %YMM6, %YMM2, %YMM6
> -       VPMINU  %YMM7, %YMM3, %YMM7
> -       VPMINU  %YMM8, %YMM4, %YMM8
> -
> -       VPMINU  %YMM5, %YMM6, %YMM1
> -       VPMINU  %YMM7, %YMM8, %YMM2
> -
> -       VPMINU  %YMM1, %YMM2, %YMM1
> -
> -       /* Each bit in K0 represents a CHAR or a null byte.  */
> -       VPCMP   $0, %YMMZERO, %YMM1, %k0
> -
> -       addq    $(VEC_SIZE * 4), %rdi
> -
> -       ktestd  %k0, %k0
> +       VPCMP   $4, %YMM0, %YMM4, %k4
> +
> +       /* Use min to select all zeros from either xor or end of string).
> +        */
> +       VPMINU  %YMM1, %YMM5, %YMM1
> +       VPMINU  %YMM3, %YMM7, %YMM3
> +
> +       /* Use min + zeromask to select for zeros. Since k2 and k4 will
> +          have 0 as positions that matched with CHAR which will set
> +          zero in the corresponding destination bytes in YMM2 / YMM4.
> +        */
> +       VPMINU  %YMM1, %YMM2, %YMM2{%k2}{z}
> +       VPMINU  %YMM3, %YMM4, %YMM4
> +       VPMINU  %YMM2, %YMM4, %YMM4{%k4}{z}
> +
> +       VPCMP   $0, %YMMZERO, %YMM4, %k1
> +       kmovd   %k1, %ecx
> +       subq    $-(VEC_SIZE * 4), %rdi
> +       testl   %ecx, %ecx
>         jz      L(loop_4x_vec)
>
> -       /* Each bit in K0 represents a CHAR or a null byte in YMM1.  */
> -       VPCMP   $0, %YMMZERO, %YMM5, %k0
> +       VPCMP   $0, %YMMZERO, %YMM1, %k0
>         kmovd   %k0, %eax
>         testl   %eax, %eax
> -       jnz     L(first_vec_x0)
> +       jnz     L(last_vec_x1)
>
> -       /* Each bit in K1 represents a CHAR or a null byte in YMM2.  */
> -       VPCMP   $0, %YMMZERO, %YMM6, %k1
> -       kmovd   %k1, %eax
> +       VPCMP   $0, %YMMZERO, %YMM2, %k0
> +       kmovd   %k0, %eax
>         testl   %eax, %eax
> -       jnz     L(first_vec_x1)
> -
> -       /* Each bit in K2 represents a CHAR or a null byte in YMM3.  */
> -       VPCMP   $0, %YMMZERO, %YMM7, %k2
> -       /* Each bit in K3 represents a CHAR or a null byte in YMM4.  */
> -       VPCMP   $0, %YMMZERO, %YMM8, %k3
> +       jnz     L(last_vec_x2)
>
> +       VPCMP   $0, %YMMZERO, %YMM3, %k0
> +       kmovd   %k0, %eax
> +       /* Combine YMM3 matches (eax) with YMM4 matches (ecx).  */
>  # ifdef USE_AS_WCSCHR
> -       /* NB: Each bit in K2/K3 represents 4-byte element.  */
> -       kshiftlw $8, %k3, %k1
> +       sall    $8, %ecx
> +       orl     %ecx, %eax
> +       tzcntl  %eax, %eax
>  # else
> -       kshiftlq $32, %k3, %k1
> +       salq    $32, %rcx
> +       orq     %rcx, %rax
> +       tzcntq  %rax, %rax
>  # endif
> +# ifndef USE_AS_STRCHRNUL
> +       /* Check if match was CHAR or null.  */
> +       cmp     (VEC_SIZE * 2)(%rdi, %rax, CHAR_SIZE), %CHAR_REG
> +       jne     L(zero_end)
> +# endif
> +       /* NB: Multiply sizeof char type (1 or 4) to get the number of
> +          bytes.  */
> +       leaq    (VEC_SIZE * 2)(%rdi, %rax, CHAR_SIZE), %rax
> +       ret
>
> -       /* Each bit in K1 represents a NULL or a mismatch.  */
> -       korq    %k1, %k2, %k1
> -       kmovq   %k1, %rax
> +# ifndef USE_AS_STRCHRNUL
> +L(zero_end):
> +       xorl    %eax, %eax
> +       ret
> +# endif
>
> -       tzcntq  %rax, %rax
> -# ifdef USE_AS_WCSCHR
> -       /* NB: Multiply wchar_t count by 4 to get the number of bytes.  */
> -       leaq    (VEC_SIZE * 2)(%rdi, %rax, 4), %rax
> -# else
> -       leaq    (VEC_SIZE * 2)(%rdi, %rax), %rax
> +       .p2align 4
> +L(last_vec_x1):
> +       tzcntl  %eax, %eax
> +# ifndef USE_AS_STRCHRNUL
> +       /* Check if match was null.  */
> +       cmp     (%rdi, %rax, CHAR_SIZE), %CHAR_REG
> +       jne     L(zero_end)
>  # endif
> +       /* NB: Multiply sizeof char type (1 or 4) to get the number of
> +          bytes.  */
> +       leaq    (%rdi, %rax, CHAR_SIZE), %rax
> +       ret
> +
> +       .p2align 4
> +L(last_vec_x2):
> +       tzcntl  %eax, %eax
>  # ifndef USE_AS_STRCHRNUL
> -       cmp (%rax), %CHAR_REG
> -       cmovne  %rdx, %rax
> +       /* Check if match was null.  */
> +       cmp     (VEC_SIZE)(%rdi, %rax, CHAR_SIZE), %CHAR_REG
> +       jne     L(zero_end)
>  # endif
> +       /* NB: Multiply sizeof char type (1 or 4) to get the number of
> +          bytes.  */
> +       leaq    (VEC_SIZE)(%rdi, %rax, CHAR_SIZE), %rax
>         ret
>
>         /* Cold case for crossing page with first load.  */
>         .p2align 4
>  L(cross_page_boundary):
> +       movq    %rdi, %rdx
> +       /* Align rdi.  */
>         andq    $-VEC_SIZE, %rdi
> -       andl    $(VEC_SIZE - 1), %ecx
> -
>         VMOVA   (%rdi), %YMM1
> -
>         /* Leaves only CHARS matching esi as 0.  */
>         vpxorq  %YMM1, %YMM0, %YMM2
>         VPMINU  %YMM2, %YMM1, %YMM2
>         /* Each bit in K0 represents a CHAR or a null byte in YMM1.  */
>         VPCMP   $0, %YMMZERO, %YMM2, %k0
>         kmovd   %k0, %eax
> -       testl   %eax, %eax
> -
> +       /* Remove the leading bits.      */
>  # ifdef USE_AS_WCSCHR
> +       movl    %edx, %SHIFT_REG
>         /* NB: Divide shift count by 4 since each bit in K1 represent 4
>            bytes.  */
> -       movl    %ecx, %SHIFT_REG
> -       sarl    $2, %SHIFT_REG
> +       sarl    $2, %SHIFT_REG
> +       andl    $(CHAR_PER_VEC - 1), %SHIFT_REG
>  # endif
> -
> -       /* Remove the leading bits.      */
>         sarxl   %SHIFT_REG, %eax, %eax
> +       /* If eax is zero continue.  */
>         testl   %eax, %eax
> -
> -       jz      L(aligned_more)
> +       jz      L(cross_page_continue)
>         tzcntl  %eax, %eax
> -       addq    %rcx, %rdi
> +# ifndef USE_AS_STRCHRNUL
> +       /* Check to see if match was CHAR or null.  */
> +       cmp     (%rdx, %rax, CHAR_SIZE), %CHAR_REG
> +       jne     L(zero_end)
> +# endif
>  # ifdef USE_AS_WCSCHR
> -       /* NB: Multiply wchar_t count by 4 to get the number of bytes.  */
> -       leaq    (%rdi, %rax, 4), %rax
> +       /* NB: Multiply wchar_t count by 4 to get the number of
> +          bytes.  */
> +       leaq    (%rdx, %rax, CHAR_SIZE), %rax
>  # else
> -       addq    %rdi, %rax
> -# endif
> -# ifndef USE_AS_STRCHRNUL
> -       cmp (%rax), %CHAR_REG
> -       cmovne  %rdx, %rax
> +       addq    %rdx, %rax
>  # endif
>         ret
>
> --
> 2.29.2
>

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

--Sunil
  

Patch

diff --git a/sysdeps/x86_64/multiarch/strchr-evex.S b/sysdeps/x86_64/multiarch/strchr-evex.S
index ddc86a7058..7f9d4ee48d 100644
--- a/sysdeps/x86_64/multiarch/strchr-evex.S
+++ b/sysdeps/x86_64/multiarch/strchr-evex.S
@@ -32,13 +32,15 @@ 
 #  define VPCMP		vpcmpd
 #  define VPMINU	vpminud
 #  define CHAR_REG	esi
-#  define SHIFT_REG	r8d
+#  define SHIFT_REG	ecx
+#  define CHAR_SIZE	4
 # else
 #  define VPBROADCAST	vpbroadcastb
 #  define VPCMP		vpcmpb
 #  define VPMINU	vpminub
 #  define CHAR_REG	sil
-#  define SHIFT_REG	ecx
+#  define SHIFT_REG	edx
+#  define CHAR_SIZE	1
 # endif
 
 # define XMMZERO	xmm16
@@ -56,23 +58,20 @@ 
 
 # define VEC_SIZE 32
 # define PAGE_SIZE 4096
+# define CHAR_PER_VEC (VEC_SIZE / CHAR_SIZE)
 
 	.section .text.evex,"ax",@progbits
 ENTRY (STRCHR)
-	movl	%edi, %ecx
-# ifndef USE_AS_STRCHRNUL
-	xorl	%edx, %edx
-# endif
-
 	/* Broadcast CHAR to YMM0.	*/
-	VPBROADCAST %esi, %YMM0
-
+	VPBROADCAST	%esi, %YMM0
+	movl	%edi, %eax
+	andl	$(PAGE_SIZE - 1), %eax
 	vpxorq	%XMMZERO, %XMMZERO, %XMMZERO
 
-	/* Check if we cross page boundary with one vector load.  */
-	andl	$(PAGE_SIZE - 1), %ecx
-	cmpl	$(PAGE_SIZE - VEC_SIZE), %ecx
-	ja  L(cross_page_boundary)
+	/* Check if we cross page boundary with one vector load.
+	   Otherwise it is safe to use an unaligned load.  */
+	cmpl	$(PAGE_SIZE - VEC_SIZE), %eax
+	ja	L(cross_page_boundary)
 
 	/* Check the first VEC_SIZE bytes. Search for both CHAR and the
 	   null bytes.  */
@@ -83,251 +82,296 @@  ENTRY (STRCHR)
 	VPMINU	%YMM2, %YMM1, %YMM2
 	/* Each bit in K0 represents a CHAR or a null byte in YMM1.  */
 	VPCMP	$0, %YMMZERO, %YMM2, %k0
-	ktestd	%k0, %k0
-	jz	L(more_vecs)
 	kmovd	%k0, %eax
+	testl	%eax, %eax
+	jz	L(aligned_more)
 	tzcntl	%eax, %eax
-	/* Found CHAR or the null byte.	 */
 # ifdef USE_AS_WCSCHR
-	/* NB: Multiply wchar_t count by 4 to get the number of bytes.  */
-	leaq	(%rdi, %rax, 4), %rax
+	/* NB: Multiply wchar_t count by 4 to get the number of bytes.
+	 */
+	leaq	(%rdi, %rax, CHAR_SIZE), %rax
 # else
 	addq	%rdi, %rax
 # endif
 # ifndef USE_AS_STRCHRNUL
-	cmp (%rax), %CHAR_REG
-	cmovne	%rdx, %rax
+	/* Found CHAR or the null byte.	 */
+	cmp	(%rax), %CHAR_REG
+	jne	L(zero)
 # endif
 	ret
 
-	.p2align 4
-L(more_vecs):
-	/* Align data for aligned loads in the loop.  */
-	andq	$-VEC_SIZE, %rdi
-L(aligned_more):
-
-	/* Check the next 4 * VEC_SIZE.	 Only one VEC_SIZE at a time
-	   since data is only aligned to VEC_SIZE.	*/
-	VMOVA	VEC_SIZE(%rdi), %YMM1
-	addq	$VEC_SIZE, %rdi
-
-	/* Leaves only CHARS matching esi as 0.  */
-	vpxorq	%YMM1, %YMM0, %YMM2
-	VPMINU	%YMM2, %YMM1, %YMM2
-	/* Each bit in K0 represents a CHAR or a null byte in YMM1.  */
-	VPCMP	$0, %YMMZERO, %YMM2, %k0
-	kmovd	%k0, %eax
-	testl	%eax, %eax
-	jnz	L(first_vec_x0)
-
-	VMOVA	VEC_SIZE(%rdi), %YMM1
-	/* Leaves only CHARS matching esi as 0.  */
-	vpxorq	%YMM1, %YMM0, %YMM2
-	VPMINU	%YMM2, %YMM1, %YMM2
-	/* Each bit in K0 represents a CHAR or a null byte in YMM1.  */
-	VPCMP	$0, %YMMZERO, %YMM2, %k0
-	kmovd	%k0, %eax
-	testl	%eax, %eax
-	jnz	L(first_vec_x1)
-
-	VMOVA	(VEC_SIZE * 2)(%rdi), %YMM1
-	/* Leaves only CHARS matching esi as 0.  */
-	vpxorq	%YMM1, %YMM0, %YMM2
-	VPMINU	%YMM2, %YMM1, %YMM2
-	/* Each bit in K0 represents a CHAR or a null byte in YMM1.  */
-	VPCMP	$0, %YMMZERO, %YMM2, %k0
-	kmovd	%k0, %eax
-	testl	%eax, %eax
-	jnz	L(first_vec_x2)
-
-	VMOVA	(VEC_SIZE * 3)(%rdi), %YMM1
-	/* Leaves only CHARS matching esi as 0.  */
-	vpxorq	%YMM1, %YMM0, %YMM2
-	VPMINU	%YMM2, %YMM1, %YMM2
-	/* Each bit in K0 represents a CHAR or a null byte in YMM1.  */
-	VPCMP	$0, %YMMZERO, %YMM2, %k0
-	ktestd	%k0, %k0
-	jz	L(prep_loop_4x)
-
-	kmovd	%k0, %eax
+	/* .p2align 5 helps keep performance more consistent if ENTRY()
+	   alignment % 32 was either 16 or 0. As well this makes the
+	   alignment % 32 of the loop_4x_vec fixed which makes tuning it
+	   easier.  */
+	.p2align 5
+L(first_vec_x3):
 	tzcntl	%eax, %eax
+# ifndef USE_AS_STRCHRNUL
 	/* Found CHAR or the null byte.	 */
-# ifdef USE_AS_WCSCHR
-	/* NB: Multiply wchar_t count by 4 to get the number of bytes.  */
-	leaq	(VEC_SIZE * 3)(%rdi, %rax, 4), %rax
-# else
-	leaq	(VEC_SIZE * 3)(%rdi, %rax), %rax
+	cmp	(VEC_SIZE * 3)(%rdi, %rax, CHAR_SIZE), %CHAR_REG
+	jne	L(zero)
 # endif
+	/* NB: Multiply sizeof char type (1 or 4) to get the number of
+	   bytes.  */
+	leaq	(VEC_SIZE * 3)(%rdi, %rax, CHAR_SIZE), %rax
+	ret
+
 # ifndef USE_AS_STRCHRNUL
-	cmp (%rax), %CHAR_REG
-	cmovne	%rdx, %rax
-# endif
+L(zero):
+	xorl	%eax, %eax
 	ret
+# endif
 
 	.p2align 4
-L(first_vec_x0):
+L(first_vec_x4):
+# ifndef USE_AS_STRCHRNUL
+	/* Check to see if first match was CHAR (k0) or null (k1).  */
+	kmovd	%k0, %eax
 	tzcntl	%eax, %eax
-	/* Found CHAR or the null byte.	 */
-# ifdef USE_AS_WCSCHR
-	/* NB: Multiply wchar_t count by 4 to get the number of bytes.  */
-	leaq	(%rdi, %rax, 4), %rax
+	kmovd	%k1, %ecx
+	/* bzhil will not be 0 if first match was null.  */
+	bzhil	%eax, %ecx, %ecx
+	jne	L(zero)
 # else
-	addq	%rdi, %rax
-# endif
-# ifndef USE_AS_STRCHRNUL
-	cmp (%rax), %CHAR_REG
-	cmovne	%rdx, %rax
+	/* Combine CHAR and null matches.  */
+	kord	%k0, %k1, %k0
+	kmovd	%k0, %eax
+	tzcntl	%eax, %eax
 # endif
+	/* NB: Multiply sizeof char type (1 or 4) to get the number of
+	   bytes.  */
+	leaq	(VEC_SIZE * 4)(%rdi, %rax, CHAR_SIZE), %rax
 	ret
 
 	.p2align 4
 L(first_vec_x1):
 	tzcntl	%eax, %eax
-	/* Found CHAR or the null byte.	 */
-# ifdef USE_AS_WCSCHR
-	/* NB: Multiply wchar_t count by 4 to get the number of bytes.  */
-	leaq	VEC_SIZE(%rdi, %rax, 4), %rax
-# else
-	leaq	VEC_SIZE(%rdi, %rax), %rax
-# endif
 # ifndef USE_AS_STRCHRNUL
-	cmp (%rax), %CHAR_REG
-	cmovne	%rdx, %rax
+	/* Found CHAR or the null byte.	 */
+	cmp	(VEC_SIZE)(%rdi, %rax, CHAR_SIZE), %CHAR_REG
+	jne	L(zero)
+
 # endif
+	/* NB: Multiply sizeof char type (1 or 4) to get the number of
+	   bytes.  */
+	leaq	(VEC_SIZE)(%rdi, %rax, CHAR_SIZE), %rax
 	ret
 
 	.p2align 4
 L(first_vec_x2):
+# ifndef USE_AS_STRCHRNUL
+	/* Check to see if first match was CHAR (k0) or null (k1).  */
+	kmovd	%k0, %eax
 	tzcntl	%eax, %eax
-	/* Found CHAR or the null byte.	 */
-# ifdef USE_AS_WCSCHR
-	/* NB: Multiply wchar_t count by 4 to get the number of bytes.  */
-	leaq	(VEC_SIZE * 2)(%rdi, %rax, 4), %rax
+	kmovd	%k1, %ecx
+	/* bzhil will not be 0 if first match was null.  */
+	bzhil	%eax, %ecx, %ecx
+	jne	L(zero)
 # else
-	leaq	(VEC_SIZE * 2)(%rdi, %rax), %rax
-# endif
-# ifndef USE_AS_STRCHRNUL
-	cmp (%rax), %CHAR_REG
-	cmovne	%rdx, %rax
+	/* Combine CHAR and null matches.  */
+	kord	%k0, %k1, %k0
+	kmovd	%k0, %eax
+	tzcntl	%eax, %eax
 # endif
+	/* NB: Multiply sizeof char type (1 or 4) to get the number of
+	   bytes.  */
+	leaq	(VEC_SIZE * 2)(%rdi, %rax, CHAR_SIZE), %rax
 	ret
 
-L(prep_loop_4x):
-	/* Align data to 4 * VEC_SIZE.	*/
+	.p2align 4
+L(aligned_more):
+	/* Align data to VEC_SIZE.  */
+	andq	$-VEC_SIZE, %rdi
+L(cross_page_continue):
+	/* Check the next 4 * VEC_SIZE. Only one VEC_SIZE at a time since
+	   data is only aligned to VEC_SIZE. Use two alternating methods
+	   for checking VEC to balance latency and port contention.  */
+
+	/* This method has higher latency but has better port
+	   distribution.  */
+	VMOVA	(VEC_SIZE)(%rdi), %YMM1
+	/* Leaves only CHARS matching esi as 0.  */
+	vpxorq	%YMM1, %YMM0, %YMM2
+	VPMINU	%YMM2, %YMM1, %YMM2
+	/* Each bit in K0 represents a CHAR or a null byte in YMM1.  */
+	VPCMP	$0, %YMMZERO, %YMM2, %k0
+	kmovd	%k0, %eax
+	testl	%eax, %eax
+	jnz	L(first_vec_x1)
+
+	/* This method has higher latency but has better port
+	   distribution.  */
+	VMOVA	(VEC_SIZE * 2)(%rdi), %YMM1
+	/* Each bit in K0 represents a CHAR in YMM1.  */
+	VPCMP	$0, %YMM1, %YMM0, %k0
+	/* Each bit in K1 represents a CHAR in YMM1.  */
+	VPCMP	$0, %YMM1, %YMMZERO, %k1
+	kortestd	%k0, %k1
+	jnz	L(first_vec_x2)
+
+	VMOVA	(VEC_SIZE * 3)(%rdi), %YMM1
+	/* Leaves only CHARS matching esi as 0.  */
+	vpxorq	%YMM1, %YMM0, %YMM2
+	VPMINU	%YMM2, %YMM1, %YMM2
+	/* Each bit in K0 represents a CHAR or a null byte in YMM1.  */
+	VPCMP	$0, %YMMZERO, %YMM2, %k0
+	kmovd	%k0, %eax
+	testl	%eax, %eax
+	jnz	L(first_vec_x3)
+
+	VMOVA	(VEC_SIZE * 4)(%rdi), %YMM1
+	/* Each bit in K0 represents a CHAR in YMM1.  */
+	VPCMP	$0, %YMM1, %YMM0, %k0
+	/* Each bit in K1 represents a CHAR in YMM1.  */
+	VPCMP	$0, %YMM1, %YMMZERO, %k1
+	kortestd	%k0, %k1
+	jnz	L(first_vec_x4)
+
+	/* Align data to VEC_SIZE * 4 for the loop.  */
+	addq	$VEC_SIZE, %rdi
 	andq	$-(VEC_SIZE * 4), %rdi
 
 	.p2align 4
 L(loop_4x_vec):
-	/* Compare 4 * VEC at a time forward.  */
+	/* Check 4x VEC at a time. No penalty to imm32 offset with evex
+	   encoding.  */
 	VMOVA	(VEC_SIZE * 4)(%rdi), %YMM1
 	VMOVA	(VEC_SIZE * 5)(%rdi), %YMM2
 	VMOVA	(VEC_SIZE * 6)(%rdi), %YMM3
 	VMOVA	(VEC_SIZE * 7)(%rdi), %YMM4
 
-	/* Leaves only CHARS matching esi as 0.  */
+	/* For YMM1 and YMM3 use xor to set the CHARs matching esi to
+	   zero.  */
 	vpxorq	%YMM1, %YMM0, %YMM5
-	vpxorq	%YMM2, %YMM0, %YMM6
+	/* For YMM2 and YMM4 cmp not equals to CHAR and store result in
+	   k register. Its possible to save either 1 or 2 instructions
+	   using cmp no equals method for either YMM1 or YMM1 and YMM3
+	   respectively but bottleneck on p5 makes it not worth it.  */
+	VPCMP	$4, %YMM0, %YMM2, %k2
 	vpxorq	%YMM3, %YMM0, %YMM7
-	vpxorq	%YMM4, %YMM0, %YMM8
-
-	VPMINU	%YMM5, %YMM1, %YMM5
-	VPMINU	%YMM6, %YMM2, %YMM6
-	VPMINU	%YMM7, %YMM3, %YMM7
-	VPMINU	%YMM8, %YMM4, %YMM8
-
-	VPMINU	%YMM5, %YMM6, %YMM1
-	VPMINU	%YMM7, %YMM8, %YMM2
-
-	VPMINU	%YMM1, %YMM2, %YMM1
-
-	/* Each bit in K0 represents a CHAR or a null byte.  */
-	VPCMP	$0, %YMMZERO, %YMM1, %k0
-
-	addq	$(VEC_SIZE * 4), %rdi
-
-	ktestd	%k0, %k0
+	VPCMP	$4, %YMM0, %YMM4, %k4
+
+	/* Use min to select all zeros from either xor or end of string).
+	 */
+	VPMINU	%YMM1, %YMM5, %YMM1
+	VPMINU	%YMM3, %YMM7, %YMM3
+
+	/* Use min + zeromask to select for zeros. Since k2 and k4 will
+	   have 0 as positions that matched with CHAR which will set
+	   zero in the corresponding destination bytes in YMM2 / YMM4.
+	 */
+	VPMINU	%YMM1, %YMM2, %YMM2{%k2}{z}
+	VPMINU	%YMM3, %YMM4, %YMM4
+	VPMINU	%YMM2, %YMM4, %YMM4{%k4}{z}
+
+	VPCMP	$0, %YMMZERO, %YMM4, %k1
+	kmovd	%k1, %ecx
+	subq	$-(VEC_SIZE * 4), %rdi
+	testl	%ecx, %ecx
 	jz	L(loop_4x_vec)
 
-	/* Each bit in K0 represents a CHAR or a null byte in YMM1.  */
-	VPCMP	$0, %YMMZERO, %YMM5, %k0
+	VPCMP	$0, %YMMZERO, %YMM1, %k0
 	kmovd	%k0, %eax
 	testl	%eax, %eax
-	jnz	L(first_vec_x0)
+	jnz	L(last_vec_x1)
 
-	/* Each bit in K1 represents a CHAR or a null byte in YMM2.  */
-	VPCMP	$0, %YMMZERO, %YMM6, %k1
-	kmovd	%k1, %eax
+	VPCMP	$0, %YMMZERO, %YMM2, %k0
+	kmovd	%k0, %eax
 	testl	%eax, %eax
-	jnz	L(first_vec_x1)
-
-	/* Each bit in K2 represents a CHAR or a null byte in YMM3.  */
-	VPCMP	$0, %YMMZERO, %YMM7, %k2
-	/* Each bit in K3 represents a CHAR or a null byte in YMM4.  */
-	VPCMP	$0, %YMMZERO, %YMM8, %k3
+	jnz	L(last_vec_x2)
 
+	VPCMP	$0, %YMMZERO, %YMM3, %k0
+	kmovd	%k0, %eax
+	/* Combine YMM3 matches (eax) with YMM4 matches (ecx).  */
 # ifdef USE_AS_WCSCHR
-	/* NB: Each bit in K2/K3 represents 4-byte element.  */
-	kshiftlw $8, %k3, %k1
+	sall	$8, %ecx
+	orl	%ecx, %eax
+	tzcntl	%eax, %eax
 # else
-	kshiftlq $32, %k3, %k1
+	salq	$32, %rcx
+	orq	%rcx, %rax
+	tzcntq	%rax, %rax
 # endif
+# ifndef USE_AS_STRCHRNUL
+	/* Check if match was CHAR or null.  */
+	cmp	(VEC_SIZE * 2)(%rdi, %rax, CHAR_SIZE), %CHAR_REG
+	jne	L(zero_end)
+# endif
+	/* NB: Multiply sizeof char type (1 or 4) to get the number of
+	   bytes.  */
+	leaq	(VEC_SIZE * 2)(%rdi, %rax, CHAR_SIZE), %rax
+	ret
 
-	/* Each bit in K1 represents a NULL or a mismatch.  */
-	korq	%k1, %k2, %k1
-	kmovq	%k1, %rax
+# ifndef USE_AS_STRCHRNUL
+L(zero_end):
+	xorl	%eax, %eax
+	ret
+# endif
 
-	tzcntq  %rax, %rax
-# ifdef USE_AS_WCSCHR
-	/* NB: Multiply wchar_t count by 4 to get the number of bytes.  */
-	leaq	(VEC_SIZE * 2)(%rdi, %rax, 4), %rax
-# else
-	leaq	(VEC_SIZE * 2)(%rdi, %rax), %rax
+	.p2align 4
+L(last_vec_x1):
+	tzcntl	%eax, %eax
+# ifndef USE_AS_STRCHRNUL
+	/* Check if match was null.  */
+	cmp	(%rdi, %rax, CHAR_SIZE), %CHAR_REG
+	jne	L(zero_end)
 # endif
+	/* NB: Multiply sizeof char type (1 or 4) to get the number of
+	   bytes.  */
+	leaq	(%rdi, %rax, CHAR_SIZE), %rax
+	ret
+
+	.p2align 4
+L(last_vec_x2):
+	tzcntl	%eax, %eax
 # ifndef USE_AS_STRCHRNUL
-	cmp (%rax), %CHAR_REG
-	cmovne	%rdx, %rax
+	/* Check if match was null.  */
+	cmp	(VEC_SIZE)(%rdi, %rax, CHAR_SIZE), %CHAR_REG
+	jne	L(zero_end)
 # endif
+	/* NB: Multiply sizeof char type (1 or 4) to get the number of
+	   bytes.  */
+	leaq	(VEC_SIZE)(%rdi, %rax, CHAR_SIZE), %rax
 	ret
 
 	/* Cold case for crossing page with first load.	 */
 	.p2align 4
 L(cross_page_boundary):
+	movq	%rdi, %rdx
+	/* Align rdi.  */
 	andq	$-VEC_SIZE, %rdi
-	andl	$(VEC_SIZE - 1), %ecx
-
 	VMOVA	(%rdi), %YMM1
-
 	/* Leaves only CHARS matching esi as 0.  */
 	vpxorq	%YMM1, %YMM0, %YMM2
 	VPMINU	%YMM2, %YMM1, %YMM2
 	/* Each bit in K0 represents a CHAR or a null byte in YMM1.  */
 	VPCMP	$0, %YMMZERO, %YMM2, %k0
 	kmovd	%k0, %eax
-	testl	%eax, %eax
-
+	/* Remove the leading bits.	 */
 # ifdef USE_AS_WCSCHR
+	movl	%edx, %SHIFT_REG
 	/* NB: Divide shift count by 4 since each bit in K1 represent 4
 	   bytes.  */
-	movl	%ecx, %SHIFT_REG
-	sarl    $2, %SHIFT_REG
+	sarl	$2, %SHIFT_REG
+	andl	$(CHAR_PER_VEC - 1), %SHIFT_REG
 # endif
-
-	/* Remove the leading bits.	 */
 	sarxl	%SHIFT_REG, %eax, %eax
+	/* If eax is zero continue.  */
 	testl	%eax, %eax
-
-	jz	L(aligned_more)
+	jz	L(cross_page_continue)
 	tzcntl	%eax, %eax
-	addq	%rcx, %rdi
+# ifndef USE_AS_STRCHRNUL
+	/* Check to see if match was CHAR or null.  */
+	cmp	(%rdx, %rax, CHAR_SIZE), %CHAR_REG
+	jne	L(zero_end)
+# endif
 # ifdef USE_AS_WCSCHR
-	/* NB: Multiply wchar_t count by 4 to get the number of bytes.  */
-	leaq	(%rdi, %rax, 4), %rax
+	/* NB: Multiply wchar_t count by 4 to get the number of
+	   bytes.  */
+	leaq	(%rdx, %rax, CHAR_SIZE), %rax
 # else
-	addq	%rdi, %rax
-# endif
-# ifndef USE_AS_STRCHRNUL
-	cmp (%rax), %CHAR_REG
-	cmovne	%rdx, %rax
+	addq	%rdx, %rax
 # endif
 	ret