[v2,2/4] x86: Optimize {str|wcs}rchr-sse2
Checks
Context |
Check |
Description |
dj/TryBot-apply_patch |
success
|
Patch applied to master at the time it was sent
|
Commit Message
The new code unrolls the main loop slightly without adding too much
overhead and minimizes the comparisons for the search CHAR.
Geometric Mean of all benchmarks New / Old: 0.741
See email for all results.
Full xcheck passes on x86_64 with and without multiarch enabled.
---
sysdeps/x86_64/multiarch/strrchr-sse2.S | 2 +-
sysdeps/x86_64/multiarch/wcsrchr-sse2.S | 3 +-
sysdeps/x86_64/strrchr.S | 510 +++++++++++++++---------
sysdeps/x86_64/wcsrchr.S | 268 +------------
4 files changed, 339 insertions(+), 444 deletions(-)
Comments
On Thu, Apr 21, 2022 at 3:22 PM Noah Goldstein <goldstein.w.n@gmail.com> wrote:
>
> The new code unrolls the main loop slightly without adding too much
> overhead and minimizes the comparisons for the search CHAR.
>
> Geometric Mean of all benchmarks New / Old: 0.741
> See email for all results.
>
> Full xcheck passes on x86_64 with and without multiarch enabled.
> ---
> sysdeps/x86_64/multiarch/strrchr-sse2.S | 2 +-
> sysdeps/x86_64/multiarch/wcsrchr-sse2.S | 3 +-
> sysdeps/x86_64/strrchr.S | 510 +++++++++++++++---------
> sysdeps/x86_64/wcsrchr.S | 268 +------------
> 4 files changed, 339 insertions(+), 444 deletions(-)
>
> diff --git a/sysdeps/x86_64/multiarch/strrchr-sse2.S b/sysdeps/x86_64/multiarch/strrchr-sse2.S
> index db1b44c23c..866396e947 100644
> --- a/sysdeps/x86_64/multiarch/strrchr-sse2.S
> +++ b/sysdeps/x86_64/multiarch/strrchr-sse2.S
> @@ -17,7 +17,7 @@
> <https://www.gnu.org/licenses/>. */
>
> #if IS_IN (libc)
> -# define strrchr __strrchr_sse2
> +# define STRRCHR __strrchr_sse2
>
> # undef weak_alias
> # define weak_alias(strrchr, rindex)
> diff --git a/sysdeps/x86_64/multiarch/wcsrchr-sse2.S b/sysdeps/x86_64/multiarch/wcsrchr-sse2.S
> index 78d1ca6553..69d2f3cdb1 100644
> --- a/sysdeps/x86_64/multiarch/wcsrchr-sse2.S
> +++ b/sysdeps/x86_64/multiarch/wcsrchr-sse2.S
> @@ -17,7 +17,6 @@
> <https://www.gnu.org/licenses/>. */
>
> #if IS_IN (libc)
> -# define wcsrchr __wcsrchr_sse2
> +# define STRRCHR __wcsrchr_sse2
> #endif
> -
> #include "../wcsrchr.S"
> diff --git a/sysdeps/x86_64/strrchr.S b/sysdeps/x86_64/strrchr.S
> index 50d886713e..6efb25c880 100644
> --- a/sysdeps/x86_64/strrchr.S
> +++ b/sysdeps/x86_64/strrchr.S
> @@ -19,210 +19,360 @@
>
> #include <sysdep.h>
>
> +#ifndef STRRCHR
> +# define STRRCHR strrchr
> +#endif
> +
> +#ifdef USE_AS_WCSRCHR
> +# define PCMPEQ pcmpeqd
> +# define CHAR_SIZE 4
> +# define PMINU pminud
> +#else
> +# define PCMPEQ pcmpeqb
> +# define CHAR_SIZE 1
> +# define PMINU pminub
> +#endif
> +
> +#define PAGE_SIZE 4096
> +#define VEC_SIZE 16
> +
> .text
> -ENTRY (strrchr)
> - movd %esi, %xmm1
> +ENTRY(STRRCHR)
> + movd %esi, %xmm0
> movq %rdi, %rax
> - andl $4095, %eax
> - punpcklbw %xmm1, %xmm1
> - cmpq $4032, %rax
> - punpcklwd %xmm1, %xmm1
> - pshufd $0, %xmm1, %xmm1
> + andl $(PAGE_SIZE - 1), %eax
> +#ifndef USE_AS_WCSRCHR
> + punpcklbw %xmm0, %xmm0
> + punpcklwd %xmm0, %xmm0
> +#endif
> + pshufd $0, %xmm0, %xmm0
> + cmpl $(PAGE_SIZE - VEC_SIZE), %eax
> ja L(cross_page)
> - movdqu (%rdi), %xmm0
> +
> +L(cross_page_continue):
> + movups (%rdi), %xmm1
> pxor %xmm2, %xmm2
> - movdqa %xmm0, %xmm3
> - pcmpeqb %xmm1, %xmm0
> - pcmpeqb %xmm2, %xmm3
> - pmovmskb %xmm0, %ecx
> - pmovmskb %xmm3, %edx
> - testq %rdx, %rdx
> - je L(next_48_bytes)
> - leaq -1(%rdx), %rax
> - xorq %rdx, %rax
> - andq %rcx, %rax
> - je L(exit)
> - bsrq %rax, %rax
> + PCMPEQ %xmm1, %xmm2
> + pmovmskb %xmm2, %ecx
> + testl %ecx, %ecx
> + jz L(aligned_more)
> +
> + PCMPEQ %xmm0, %xmm1
> + pmovmskb %xmm1, %eax
> + leal -1(%rcx), %edx
> + xorl %edx, %ecx
> + andl %ecx, %eax
> + jz L(ret0)
> + bsrl %eax, %eax
> addq %rdi, %rax
> + /* We are off by 3 for wcsrchr if search CHAR is non-zero. If
> + search CHAR is zero we are correct. Either way `andq
> + -CHAR_SIZE, %rax` gets the correct result. */
> +#ifdef USE_AS_WCSRCHR
> + andq $-CHAR_SIZE, %rax
> +#endif
> +L(ret0):
> ret
>
> + /* Returns for first vec x1/x2 have hard coded backward search
> + path for earlier matches. */
> .p2align 4
> -L(next_48_bytes):
> - movdqu 16(%rdi), %xmm4
> - movdqa %xmm4, %xmm5
> - movdqu 32(%rdi), %xmm3
> - pcmpeqb %xmm1, %xmm4
> - pcmpeqb %xmm2, %xmm5
> - movdqu 48(%rdi), %xmm0
> - pmovmskb %xmm5, %edx
> - movdqa %xmm3, %xmm5
> - pcmpeqb %xmm1, %xmm3
> - pcmpeqb %xmm2, %xmm5
> - pcmpeqb %xmm0, %xmm2
> - salq $16, %rdx
> - pmovmskb %xmm3, %r8d
> - pmovmskb %xmm5, %eax
> - pmovmskb %xmm2, %esi
> - salq $32, %r8
> - salq $32, %rax
> - pcmpeqb %xmm1, %xmm0
> - orq %rdx, %rax
> - movq %rsi, %rdx
> - pmovmskb %xmm4, %esi
> - salq $48, %rdx
> - salq $16, %rsi
> - orq %r8, %rsi
> - orq %rcx, %rsi
> - pmovmskb %xmm0, %ecx
> - salq $48, %rcx
> - orq %rcx, %rsi
> - orq %rdx, %rax
> - je L(loop_header2)
> - leaq -1(%rax), %rcx
> - xorq %rax, %rcx
> - andq %rcx, %rsi
> - je L(exit)
> - bsrq %rsi, %rsi
> - leaq (%rdi,%rsi), %rax
> +L(first_vec_x0_test):
> + PCMPEQ %xmm0, %xmm1
> + pmovmskb %xmm1, %eax
> + testl %eax, %eax
> + jz L(ret0)
> + bsrl %eax, %eax
> + addq %r8, %rax
> +#ifdef USE_AS_WCSRCHR
> + andq $-CHAR_SIZE, %rax
> +#endif
> ret
>
> .p2align 4
> -L(loop_header2):
> - testq %rsi, %rsi
> - movq %rdi, %rcx
> - je L(no_c_found)
> -L(loop_header):
> - addq $64, %rdi
> - pxor %xmm7, %xmm7
> - andq $-64, %rdi
> - jmp L(loop_entry)
> +L(first_vec_x1):
> + PCMPEQ %xmm0, %xmm2
> + pmovmskb %xmm2, %eax
> + leal -1(%rcx), %edx
> + xorl %edx, %ecx
> + andl %ecx, %eax
> + jz L(first_vec_x0_test)
> + bsrl %eax, %eax
> + leaq (VEC_SIZE)(%rdi, %rax), %rax
> +#ifdef USE_AS_WCSRCHR
> + andq $-CHAR_SIZE, %rax
> +#endif
> + ret
>
> .p2align 4
> -L(loop64):
> - testq %rdx, %rdx
> - cmovne %rdx, %rsi
> - cmovne %rdi, %rcx
> - addq $64, %rdi
> -L(loop_entry):
> - movdqa 32(%rdi), %xmm3
> - pxor %xmm6, %xmm6
> - movdqa 48(%rdi), %xmm2
> - movdqa %xmm3, %xmm0
> - movdqa 16(%rdi), %xmm4
> - pminub %xmm2, %xmm0
> - movdqa (%rdi), %xmm5
> - pminub %xmm4, %xmm0
> - pminub %xmm5, %xmm0
> - pcmpeqb %xmm7, %xmm0
> - pmovmskb %xmm0, %eax
> - movdqa %xmm5, %xmm0
> - pcmpeqb %xmm1, %xmm0
> - pmovmskb %xmm0, %r9d
> - movdqa %xmm4, %xmm0
> - pcmpeqb %xmm1, %xmm0
> - pmovmskb %xmm0, %edx
> - movdqa %xmm3, %xmm0
> - pcmpeqb %xmm1, %xmm0
> - salq $16, %rdx
> - pmovmskb %xmm0, %r10d
> - movdqa %xmm2, %xmm0
> - pcmpeqb %xmm1, %xmm0
> - salq $32, %r10
> - orq %r10, %rdx
> - pmovmskb %xmm0, %r8d
> - orq %r9, %rdx
> - salq $48, %r8
> - orq %r8, %rdx
> +L(first_vec_x1_test):
> + PCMPEQ %xmm0, %xmm2
> + pmovmskb %xmm2, %eax
> testl %eax, %eax
> - je L(loop64)
> - pcmpeqb %xmm6, %xmm4
> - pcmpeqb %xmm6, %xmm3
> - pcmpeqb %xmm6, %xmm5
> - pmovmskb %xmm4, %eax
> - pmovmskb %xmm3, %r10d
> - pcmpeqb %xmm6, %xmm2
> - pmovmskb %xmm5, %r9d
> - salq $32, %r10
> - salq $16, %rax
> - pmovmskb %xmm2, %r8d
> - orq %r10, %rax
> - orq %r9, %rax
> - salq $48, %r8
> - orq %r8, %rax
> - leaq -1(%rax), %r8
> - xorq %rax, %r8
> - andq %r8, %rdx
> - cmovne %rdi, %rcx
> - cmovne %rdx, %rsi
> - bsrq %rsi, %rsi
> - leaq (%rcx,%rsi), %rax
> + jz L(first_vec_x0_test)
> + bsrl %eax, %eax
> + leaq (VEC_SIZE)(%rdi, %rax), %rax
> +#ifdef USE_AS_WCSRCHR
> + andq $-CHAR_SIZE, %rax
> +#endif
> + ret
> +
> + .p2align 4
> +L(first_vec_x2):
> + PCMPEQ %xmm0, %xmm3
> + pmovmskb %xmm3, %eax
> + leal -1(%rcx), %edx
> + xorl %edx, %ecx
> + andl %ecx, %eax
> + jz L(first_vec_x1_test)
> + bsrl %eax, %eax
> + leaq (VEC_SIZE * 2)(%rdi, %rax), %rax
> +#ifdef USE_AS_WCSRCHR
> + andq $-CHAR_SIZE, %rax
> +#endif
> + ret
> +
> + .p2align 4
> +L(aligned_more):
> + /* Save original pointer if match was in VEC 0. */
> + movq %rdi, %r8
> + andq $-VEC_SIZE, %rdi
> +
> + movaps VEC_SIZE(%rdi), %xmm2
> + pxor %xmm3, %xmm3
> + PCMPEQ %xmm2, %xmm3
> + pmovmskb %xmm3, %ecx
> + testl %ecx, %ecx
> + jnz L(first_vec_x1)
> +
> + movaps (VEC_SIZE * 2)(%rdi), %xmm3
> + pxor %xmm4, %xmm4
> + PCMPEQ %xmm3, %xmm4
> + pmovmskb %xmm4, %ecx
> + testl %ecx, %ecx
> + jnz L(first_vec_x2)
> +
> + addq $VEC_SIZE, %rdi
> + /* Save pointer again before realigning. */
> + movq %rdi, %rsi
> + andq $-(VEC_SIZE * 2), %rdi
> + .p2align 4
> +L(first_loop):
> + /* Do 2x VEC at a time. */
> + movaps (VEC_SIZE * 2)(%rdi), %xmm4
> + movaps (VEC_SIZE * 3)(%rdi), %xmm5
> + /* If SSE2 no pminud so wcsrchr needs seperate logic for
Did you mean "Since", instead of "If"?
> + detecting zero. Note if this is found to be a bottleneck it
> + may be worth adding an SSE4.1 wcsrchr implementation. */
> +#ifdef USE_AS_WCSRCHR
> + movaps %xmm5, %xmm6
> + pxor %xmm8, %xmm8
> +
> + PCMPEQ %xmm8, %xmm5
> + PCMPEQ %xmm4, %xmm8
> + por %xmm5, %xmm8
> +#else
> + movaps %xmm5, %xmm6
> + PMINU %xmm4, %xmm5
> +#endif
> +
> + movaps %xmm4, %xmm9
> + PCMPEQ %xmm0, %xmm4
> + PCMPEQ %xmm0, %xmm6
> + movaps %xmm6, %xmm7
> + por %xmm4, %xmm6
> +#ifndef USE_AS_WCSRCHR
> + pxor %xmm8, %xmm8
> + PCMPEQ %xmm5, %xmm8
> +#endif
> + pmovmskb %xmm8, %ecx
> + pmovmskb %xmm6, %eax
> +
> + addq $(VEC_SIZE * 2), %rdi
> + /* Use `addl` 1) so we can undo it with `subl` and 2) it can
> + macro-fuse with `jz`. */
> + addl %ecx, %eax
> + jz L(first_loop)
> +
> + /* Check if there is zero match. */
> + testl %ecx, %ecx
> + jz L(second_loop_match)
> +
> + /* Check if there was a match in last iteration. */
> + subl %ecx, %eax
> + jnz L(new_match)
> +
> +L(first_loop_old_match):
> + PCMPEQ %xmm0, %xmm2
> + PCMPEQ %xmm0, %xmm3
> + pmovmskb %xmm2, %ecx
> + pmovmskb %xmm3, %eax
> + addl %eax, %ecx
> + jz L(first_vec_x0_test)
> + /* NB: We could move this shift to before the branch and save a
> + bit of code size / performance on the fall through. The
> + branch leads to the null case which generally seems hotter
> + than char in first 3x VEC. */
> + sall $16, %eax
> + orl %ecx, %eax
> +
> + bsrl %eax, %eax
> + addq %rsi, %rax
> +#ifdef USE_AS_WCSRCHR
> + andq $-CHAR_SIZE, %rax
> +#endif
> + ret
> +
> + .p2align 4
> +L(new_match):
> + pxor %xmm6, %xmm6
> + PCMPEQ %xmm9, %xmm6
> + pmovmskb %xmm6, %eax
> + sall $16, %ecx
> + orl %eax, %ecx
> +
> + /* We can't reuse either of the old comparisons as since we mask
> + of zeros after first zero (instead of using the full
> + comparison) we can't gurantee no interference between match
> + after end of string and valid match. */
> + pmovmskb %xmm4, %eax
> + pmovmskb %xmm7, %edx
> + sall $16, %edx
> + orl %edx, %eax
> +
> + leal -1(%ecx), %edx
> + xorl %edx, %ecx
> + andl %ecx, %eax
> + jz L(first_loop_old_match)
> + bsrl %eax, %eax
> + addq %rdi, %rax
> +#ifdef USE_AS_WCSRCHR
> + andq $-CHAR_SIZE, %rax
> +#endif
> ret
>
> + /* Save minimum state for getting most recent match. We can
> + throw out all previous work. */
> .p2align 4
> -L(no_c_found):
> - movl $1, %esi
> - xorl %ecx, %ecx
> - jmp L(loop_header)
> +L(second_loop_match):
> + movq %rdi, %rsi
> + movaps %xmm4, %xmm2
> + movaps %xmm7, %xmm3
>
> .p2align 4
> -L(exit):
> - xorl %eax, %eax
> +L(second_loop):
> + movaps (VEC_SIZE * 2)(%rdi), %xmm4
> + movaps (VEC_SIZE * 3)(%rdi), %xmm5
> + /* If SSE2 no pminud so wcsrchr needs seperate logic for
Did you mean "Since", instead of "If"?
> + detecting zero. Note if this is found to be a bottleneck it
> + may be worth adding an SSE4.1 wcsrchr implementation. */
> +#ifdef USE_AS_WCSRCHR
> + movaps %xmm5, %xmm6
> + pxor %xmm8, %xmm8
> +
> + PCMPEQ %xmm8, %xmm5
> + PCMPEQ %xmm4, %xmm8
> + por %xmm5, %xmm8
> +#else
> + movaps %xmm5, %xmm6
> + PMINU %xmm4, %xmm5
> +#endif
> +
> + movaps %xmm4, %xmm9
> + PCMPEQ %xmm0, %xmm4
> + PCMPEQ %xmm0, %xmm6
> + movaps %xmm6, %xmm7
> + por %xmm4, %xmm6
> +#ifndef USE_AS_WCSRCHR
> + pxor %xmm8, %xmm8
> + PCMPEQ %xmm5, %xmm8
> +#endif
> +
> + pmovmskb %xmm8, %ecx
> + pmovmskb %xmm6, %eax
> +
> + addq $(VEC_SIZE * 2), %rdi
> + /* Either null term or new occurence of CHAR. */
> + addl %ecx, %eax
> + jz L(second_loop)
> +
> + /* No null term so much be new occurence of CHAR. */
> + testl %ecx, %ecx
> + jz L(second_loop_match)
> +
> +
> + subl %ecx, %eax
> + jnz L(second_loop_new_match)
> +
> +L(second_loop_old_match):
> + pmovmskb %xmm2, %ecx
> + pmovmskb %xmm3, %eax
> + sall $16, %eax
> + orl %ecx, %eax
> + bsrl %eax, %eax
> + addq %rsi, %rax
> +#ifdef USE_AS_WCSRCHR
> + andq $-CHAR_SIZE, %rax
> +#endif
> ret
>
> .p2align 4
> +L(second_loop_new_match):
> + pxor %xmm6, %xmm6
> + PCMPEQ %xmm9, %xmm6
> + pmovmskb %xmm6, %eax
> + sall $16, %ecx
> + orl %eax, %ecx
> +
> + /* We can't reuse either of the old comparisons as since we mask
> + of zeros after first zero (instead of using the full
> + comparison) we can't gurantee no interference between match
> + after end of string and valid match. */
> + pmovmskb %xmm4, %eax
> + pmovmskb %xmm7, %edx
> + sall $16, %edx
> + orl %edx, %eax
> +
> + leal -1(%ecx), %edx
> + xorl %edx, %ecx
> + andl %ecx, %eax
> + jz L(second_loop_old_match)
> + bsrl %eax, %eax
> + addq %rdi, %rax
> +#ifdef USE_AS_WCSRCHR
> + andq $-CHAR_SIZE, %rax
> +#endif
> + ret
> +
> + .p2align 4,, 4
> L(cross_page):
> - movq %rdi, %rax
> - pxor %xmm0, %xmm0
> - andq $-64, %rax
> - movdqu (%rax), %xmm5
> - movdqa %xmm5, %xmm6
> - movdqu 16(%rax), %xmm4
> - pcmpeqb %xmm1, %xmm5
> - pcmpeqb %xmm0, %xmm6
> - movdqu 32(%rax), %xmm3
> - pmovmskb %xmm6, %esi
> - movdqa %xmm4, %xmm6
> - movdqu 48(%rax), %xmm2
> - pcmpeqb %xmm1, %xmm4
> - pcmpeqb %xmm0, %xmm6
> - pmovmskb %xmm6, %edx
> - movdqa %xmm3, %xmm6
> - pcmpeqb %xmm1, %xmm3
> - pcmpeqb %xmm0, %xmm6
> - pcmpeqb %xmm2, %xmm0
> - salq $16, %rdx
> - pmovmskb %xmm3, %r9d
> - pmovmskb %xmm6, %r8d
> - pmovmskb %xmm0, %ecx
> - salq $32, %r9
> - salq $32, %r8
> - pcmpeqb %xmm1, %xmm2
> - orq %r8, %rdx
> - salq $48, %rcx
> - pmovmskb %xmm5, %r8d
> - orq %rsi, %rdx
> - pmovmskb %xmm4, %esi
> - orq %rcx, %rdx
> - pmovmskb %xmm2, %ecx
> - salq $16, %rsi
> - salq $48, %rcx
> - orq %r9, %rsi
> - orq %r8, %rsi
> - orq %rcx, %rsi
> + movq %rdi, %rsi
> + andq $-VEC_SIZE, %rsi
> + movaps (%rsi), %xmm1
> + pxor %xmm2, %xmm2
> + PCMPEQ %xmm1, %xmm2
> + pmovmskb %xmm2, %edx
> movl %edi, %ecx
> - subl %eax, %ecx
> - shrq %cl, %rdx
> - shrq %cl, %rsi
> - testq %rdx, %rdx
> - je L(loop_header2)
> - leaq -1(%rdx), %rax
> - xorq %rdx, %rax
> - andq %rax, %rsi
> - je L(exit)
> - bsrq %rsi, %rax
> + andl $(VEC_SIZE - 1), %ecx
> + sarl %cl, %edx
> + jz L(cross_page_continue)
> + PCMPEQ %xmm0, %xmm1
> + pmovmskb %xmm1, %eax
> + sarl %cl, %eax
> + leal -1(%rdx), %ecx
> + xorl %edx, %ecx
> + andl %ecx, %eax
> + jz L(ret1)
> + bsrl %eax, %eax
> addq %rdi, %rax
> +#ifdef USE_AS_WCSRCHR
> + andq $-CHAR_SIZE, %rax
> +#endif
> +L(ret1):
> ret
> -END (strrchr)
> +END(STRRCHR)
>
> -weak_alias (strrchr, rindex)
> -libc_hidden_builtin_def (strrchr)
> +#ifndef USE_AS_WCSRCHR
> + weak_alias (STRRCHR, rindex)
> + libc_hidden_builtin_def (STRRCHR)
> +#endif
> diff --git a/sysdeps/x86_64/wcsrchr.S b/sysdeps/x86_64/wcsrchr.S
> index 61552954de..2b80efc5ef 100644
> --- a/sysdeps/x86_64/wcsrchr.S
> +++ b/sysdeps/x86_64/wcsrchr.S
> @@ -1,4 +1,4 @@
> -/* wcsrchr with SSSE3
> +/* wcsrchr optimized with SSE2.
> Copyright (C) 2011-2022 Free Software Foundation, Inc.
> This file is part of the GNU C Library.
>
> @@ -16,266 +16,12 @@
> License along with the GNU C Library; if not, see
> <https://www.gnu.org/licenses/>. */
>
> -#include <sysdep.h>
>
> - .text
> -ENTRY (wcsrchr)
> +#define USE_AS_WCSRCHR 1
> +#define NO_PMINU 1
>
> - movd %rsi, %xmm1
> - mov %rdi, %rcx
> - punpckldq %xmm1, %xmm1
> - pxor %xmm2, %xmm2
> - punpckldq %xmm1, %xmm1
> - and $63, %rcx
> - cmp $48, %rcx
> - ja L(crosscache)
> +#ifndef STRRCHR
> +# define STRRCHR wcsrchr
> +#endif
>
> - movdqu (%rdi), %xmm0
> - pcmpeqd %xmm0, %xmm2
> - pcmpeqd %xmm1, %xmm0
> - pmovmskb %xmm2, %rcx
> - pmovmskb %xmm0, %rax
> - add $16, %rdi
> -
> - test %rax, %rax
> - jnz L(unaligned_match1)
> -
> - test %rcx, %rcx
> - jnz L(return_null)
> -
> - and $-16, %rdi
> - xor %r8, %r8
> - jmp L(loop)
> -
> - .p2align 4
> -L(unaligned_match1):
> - test %rcx, %rcx
> - jnz L(prolog_find_zero_1)
> -
> - mov %rax, %r8
> - mov %rdi, %rsi
> - and $-16, %rdi
> - jmp L(loop)
> -
> - .p2align 4
> -L(crosscache):
> - and $15, %rcx
> - and $-16, %rdi
> - pxor %xmm3, %xmm3
> - movdqa (%rdi), %xmm0
> - pcmpeqd %xmm0, %xmm3
> - pcmpeqd %xmm1, %xmm0
> - pmovmskb %xmm3, %rdx
> - pmovmskb %xmm0, %rax
> - shr %cl, %rdx
> - shr %cl, %rax
> - add $16, %rdi
> -
> - test %rax, %rax
> - jnz L(unaligned_match)
> -
> - test %rdx, %rdx
> - jnz L(return_null)
> -
> - xor %r8, %r8
> - jmp L(loop)
> -
> - .p2align 4
> -L(unaligned_match):
> - test %rdx, %rdx
> - jnz L(prolog_find_zero)
> -
> - mov %rax, %r8
> - lea (%rdi, %rcx), %rsi
> -
> -/* Loop start on aligned string. */
> - .p2align 4
> -L(loop):
> - movdqa (%rdi), %xmm0
> - pcmpeqd %xmm0, %xmm2
> - add $16, %rdi
> - pcmpeqd %xmm1, %xmm0
> - pmovmskb %xmm2, %rcx
> - pmovmskb %xmm0, %rax
> - or %rax, %rcx
> - jnz L(matches)
> -
> - movdqa (%rdi), %xmm3
> - pcmpeqd %xmm3, %xmm2
> - add $16, %rdi
> - pcmpeqd %xmm1, %xmm3
> - pmovmskb %xmm2, %rcx
> - pmovmskb %xmm3, %rax
> - or %rax, %rcx
> - jnz L(matches)
> -
> - movdqa (%rdi), %xmm4
> - pcmpeqd %xmm4, %xmm2
> - add $16, %rdi
> - pcmpeqd %xmm1, %xmm4
> - pmovmskb %xmm2, %rcx
> - pmovmskb %xmm4, %rax
> - or %rax, %rcx
> - jnz L(matches)
> -
> - movdqa (%rdi), %xmm5
> - pcmpeqd %xmm5, %xmm2
> - add $16, %rdi
> - pcmpeqd %xmm1, %xmm5
> - pmovmskb %xmm2, %rcx
> - pmovmskb %xmm5, %rax
> - or %rax, %rcx
> - jz L(loop)
> -
> - .p2align 4
> -L(matches):
> - test %rax, %rax
> - jnz L(match)
> -L(return_value):
> - test %r8, %r8
> - jz L(return_null)
> - mov %r8, %rax
> - mov %rsi, %rdi
> -
> - test $15 << 4, %ah
> - jnz L(match_fourth_wchar)
> - test %ah, %ah
> - jnz L(match_third_wchar)
> - test $15 << 4, %al
> - jnz L(match_second_wchar)
> - lea -16(%rdi), %rax
> - ret
> -
> - .p2align 4
> -L(match):
> - pmovmskb %xmm2, %rcx
> - test %rcx, %rcx
> - jnz L(find_zero)
> - mov %rax, %r8
> - mov %rdi, %rsi
> - jmp L(loop)
> -
> - .p2align 4
> -L(find_zero):
> - test $15, %cl
> - jnz L(find_zero_in_first_wchar)
> - test %cl, %cl
> - jnz L(find_zero_in_second_wchar)
> - test $15, %ch
> - jnz L(find_zero_in_third_wchar)
> -
> - and $1 << 13 - 1, %rax
> - jz L(return_value)
> -
> - test $15 << 4, %ah
> - jnz L(match_fourth_wchar)
> - test %ah, %ah
> - jnz L(match_third_wchar)
> - test $15 << 4, %al
> - jnz L(match_second_wchar)
> - lea -16(%rdi), %rax
> - ret
> -
> - .p2align 4
> -L(find_zero_in_first_wchar):
> - test $1, %rax
> - jz L(return_value)
> - lea -16(%rdi), %rax
> - ret
> -
> - .p2align 4
> -L(find_zero_in_second_wchar):
> - and $1 << 5 - 1, %rax
> - jz L(return_value)
> -
> - test $15 << 4, %al
> - jnz L(match_second_wchar)
> - lea -16(%rdi), %rax
> - ret
> -
> - .p2align 4
> -L(find_zero_in_third_wchar):
> - and $1 << 9 - 1, %rax
> - jz L(return_value)
> -
> - test %ah, %ah
> - jnz L(match_third_wchar)
> - test $15 << 4, %al
> - jnz L(match_second_wchar)
> - lea -16(%rdi), %rax
> - ret
> -
> - .p2align 4
> -L(prolog_find_zero):
> - add %rcx, %rdi
> - mov %rdx, %rcx
> -L(prolog_find_zero_1):
> - test $15, %cl
> - jnz L(prolog_find_zero_in_first_wchar)
> - test %cl, %cl
> - jnz L(prolog_find_zero_in_second_wchar)
> - test $15, %ch
> - jnz L(prolog_find_zero_in_third_wchar)
> -
> - and $1 << 13 - 1, %rax
> - jz L(return_null)
> -
> - test $15 << 4, %ah
> - jnz L(match_fourth_wchar)
> - test %ah, %ah
> - jnz L(match_third_wchar)
> - test $15 << 4, %al
> - jnz L(match_second_wchar)
> - lea -16(%rdi), %rax
> - ret
> -
> - .p2align 4
> -L(prolog_find_zero_in_first_wchar):
> - test $1, %rax
> - jz L(return_null)
> - lea -16(%rdi), %rax
> - ret
> -
> - .p2align 4
> -L(prolog_find_zero_in_second_wchar):
> - and $1 << 5 - 1, %rax
> - jz L(return_null)
> -
> - test $15 << 4, %al
> - jnz L(match_second_wchar)
> - lea -16(%rdi), %rax
> - ret
> -
> - .p2align 4
> -L(prolog_find_zero_in_third_wchar):
> - and $1 << 9 - 1, %rax
> - jz L(return_null)
> -
> - test %ah, %ah
> - jnz L(match_third_wchar)
> - test $15 << 4, %al
> - jnz L(match_second_wchar)
> - lea -16(%rdi), %rax
> - ret
> -
> - .p2align 4
> -L(match_second_wchar):
> - lea -12(%rdi), %rax
> - ret
> -
> - .p2align 4
> -L(match_third_wchar):
> - lea -8(%rdi), %rax
> - ret
> -
> - .p2align 4
> -L(match_fourth_wchar):
> - lea -4(%rdi), %rax
> - ret
> -
> - .p2align 4
> -L(return_null):
> - xor %rax, %rax
> - ret
> -
> -END (wcsrchr)
> +#include "../strrchr.S"
> --
> 2.25.1
>
On Thu, Apr 21, 2022 at 6:46 PM H.J. Lu <hjl.tools@gmail.com> wrote:
>
> On Thu, Apr 21, 2022 at 3:22 PM Noah Goldstein <goldstein.w.n@gmail.com> wrote:
> >
> > The new code unrolls the main loop slightly without adding too much
> > overhead and minimizes the comparisons for the search CHAR.
> >
> > Geometric Mean of all benchmarks New / Old: 0.741
> > See email for all results.
> >
> > Full xcheck passes on x86_64 with and without multiarch enabled.
> > ---
> > sysdeps/x86_64/multiarch/strrchr-sse2.S | 2 +-
> > sysdeps/x86_64/multiarch/wcsrchr-sse2.S | 3 +-
> > sysdeps/x86_64/strrchr.S | 510 +++++++++++++++---------
> > sysdeps/x86_64/wcsrchr.S | 268 +------------
> > 4 files changed, 339 insertions(+), 444 deletions(-)
> >
> > diff --git a/sysdeps/x86_64/multiarch/strrchr-sse2.S b/sysdeps/x86_64/multiarch/strrchr-sse2.S
> > index db1b44c23c..866396e947 100644
> > --- a/sysdeps/x86_64/multiarch/strrchr-sse2.S
> > +++ b/sysdeps/x86_64/multiarch/strrchr-sse2.S
> > @@ -17,7 +17,7 @@
> > <https://www.gnu.org/licenses/>. */
> >
> > #if IS_IN (libc)
> > -# define strrchr __strrchr_sse2
> > +# define STRRCHR __strrchr_sse2
> >
> > # undef weak_alias
> > # define weak_alias(strrchr, rindex)
> > diff --git a/sysdeps/x86_64/multiarch/wcsrchr-sse2.S b/sysdeps/x86_64/multiarch/wcsrchr-sse2.S
> > index 78d1ca6553..69d2f3cdb1 100644
> > --- a/sysdeps/x86_64/multiarch/wcsrchr-sse2.S
> > +++ b/sysdeps/x86_64/multiarch/wcsrchr-sse2.S
> > @@ -17,7 +17,6 @@
> > <https://www.gnu.org/licenses/>. */
> >
> > #if IS_IN (libc)
> > -# define wcsrchr __wcsrchr_sse2
> > +# define STRRCHR __wcsrchr_sse2
> > #endif
> > -
> > #include "../wcsrchr.S"
> > diff --git a/sysdeps/x86_64/strrchr.S b/sysdeps/x86_64/strrchr.S
> > index 50d886713e..6efb25c880 100644
> > --- a/sysdeps/x86_64/strrchr.S
> > +++ b/sysdeps/x86_64/strrchr.S
> > @@ -19,210 +19,360 @@
> >
> > #include <sysdep.h>
> >
> > +#ifndef STRRCHR
> > +# define STRRCHR strrchr
> > +#endif
> > +
> > +#ifdef USE_AS_WCSRCHR
> > +# define PCMPEQ pcmpeqd
> > +# define CHAR_SIZE 4
> > +# define PMINU pminud
> > +#else
> > +# define PCMPEQ pcmpeqb
> > +# define CHAR_SIZE 1
> > +# define PMINU pminub
> > +#endif
> > +
> > +#define PAGE_SIZE 4096
> > +#define VEC_SIZE 16
> > +
> > .text
> > -ENTRY (strrchr)
> > - movd %esi, %xmm1
> > +ENTRY(STRRCHR)
> > + movd %esi, %xmm0
> > movq %rdi, %rax
> > - andl $4095, %eax
> > - punpcklbw %xmm1, %xmm1
> > - cmpq $4032, %rax
> > - punpcklwd %xmm1, %xmm1
> > - pshufd $0, %xmm1, %xmm1
> > + andl $(PAGE_SIZE - 1), %eax
> > +#ifndef USE_AS_WCSRCHR
> > + punpcklbw %xmm0, %xmm0
> > + punpcklwd %xmm0, %xmm0
> > +#endif
> > + pshufd $0, %xmm0, %xmm0
> > + cmpl $(PAGE_SIZE - VEC_SIZE), %eax
> > ja L(cross_page)
> > - movdqu (%rdi), %xmm0
> > +
> > +L(cross_page_continue):
> > + movups (%rdi), %xmm1
> > pxor %xmm2, %xmm2
> > - movdqa %xmm0, %xmm3
> > - pcmpeqb %xmm1, %xmm0
> > - pcmpeqb %xmm2, %xmm3
> > - pmovmskb %xmm0, %ecx
> > - pmovmskb %xmm3, %edx
> > - testq %rdx, %rdx
> > - je L(next_48_bytes)
> > - leaq -1(%rdx), %rax
> > - xorq %rdx, %rax
> > - andq %rcx, %rax
> > - je L(exit)
> > - bsrq %rax, %rax
> > + PCMPEQ %xmm1, %xmm2
> > + pmovmskb %xmm2, %ecx
> > + testl %ecx, %ecx
> > + jz L(aligned_more)
> > +
> > + PCMPEQ %xmm0, %xmm1
> > + pmovmskb %xmm1, %eax
> > + leal -1(%rcx), %edx
> > + xorl %edx, %ecx
> > + andl %ecx, %eax
> > + jz L(ret0)
> > + bsrl %eax, %eax
> > addq %rdi, %rax
> > + /* We are off by 3 for wcsrchr if search CHAR is non-zero. If
> > + search CHAR is zero we are correct. Either way `andq
> > + -CHAR_SIZE, %rax` gets the correct result. */
> > +#ifdef USE_AS_WCSRCHR
> > + andq $-CHAR_SIZE, %rax
> > +#endif
> > +L(ret0):
> > ret
> >
> > + /* Returns for first vec x1/x2 have hard coded backward search
> > + path for earlier matches. */
> > .p2align 4
> > -L(next_48_bytes):
> > - movdqu 16(%rdi), %xmm4
> > - movdqa %xmm4, %xmm5
> > - movdqu 32(%rdi), %xmm3
> > - pcmpeqb %xmm1, %xmm4
> > - pcmpeqb %xmm2, %xmm5
> > - movdqu 48(%rdi), %xmm0
> > - pmovmskb %xmm5, %edx
> > - movdqa %xmm3, %xmm5
> > - pcmpeqb %xmm1, %xmm3
> > - pcmpeqb %xmm2, %xmm5
> > - pcmpeqb %xmm0, %xmm2
> > - salq $16, %rdx
> > - pmovmskb %xmm3, %r8d
> > - pmovmskb %xmm5, %eax
> > - pmovmskb %xmm2, %esi
> > - salq $32, %r8
> > - salq $32, %rax
> > - pcmpeqb %xmm1, %xmm0
> > - orq %rdx, %rax
> > - movq %rsi, %rdx
> > - pmovmskb %xmm4, %esi
> > - salq $48, %rdx
> > - salq $16, %rsi
> > - orq %r8, %rsi
> > - orq %rcx, %rsi
> > - pmovmskb %xmm0, %ecx
> > - salq $48, %rcx
> > - orq %rcx, %rsi
> > - orq %rdx, %rax
> > - je L(loop_header2)
> > - leaq -1(%rax), %rcx
> > - xorq %rax, %rcx
> > - andq %rcx, %rsi
> > - je L(exit)
> > - bsrq %rsi, %rsi
> > - leaq (%rdi,%rsi), %rax
> > +L(first_vec_x0_test):
> > + PCMPEQ %xmm0, %xmm1
> > + pmovmskb %xmm1, %eax
> > + testl %eax, %eax
> > + jz L(ret0)
> > + bsrl %eax, %eax
> > + addq %r8, %rax
> > +#ifdef USE_AS_WCSRCHR
> > + andq $-CHAR_SIZE, %rax
> > +#endif
> > ret
> >
> > .p2align 4
> > -L(loop_header2):
> > - testq %rsi, %rsi
> > - movq %rdi, %rcx
> > - je L(no_c_found)
> > -L(loop_header):
> > - addq $64, %rdi
> > - pxor %xmm7, %xmm7
> > - andq $-64, %rdi
> > - jmp L(loop_entry)
> > +L(first_vec_x1):
> > + PCMPEQ %xmm0, %xmm2
> > + pmovmskb %xmm2, %eax
> > + leal -1(%rcx), %edx
> > + xorl %edx, %ecx
> > + andl %ecx, %eax
> > + jz L(first_vec_x0_test)
> > + bsrl %eax, %eax
> > + leaq (VEC_SIZE)(%rdi, %rax), %rax
> > +#ifdef USE_AS_WCSRCHR
> > + andq $-CHAR_SIZE, %rax
> > +#endif
> > + ret
> >
> > .p2align 4
> > -L(loop64):
> > - testq %rdx, %rdx
> > - cmovne %rdx, %rsi
> > - cmovne %rdi, %rcx
> > - addq $64, %rdi
> > -L(loop_entry):
> > - movdqa 32(%rdi), %xmm3
> > - pxor %xmm6, %xmm6
> > - movdqa 48(%rdi), %xmm2
> > - movdqa %xmm3, %xmm0
> > - movdqa 16(%rdi), %xmm4
> > - pminub %xmm2, %xmm0
> > - movdqa (%rdi), %xmm5
> > - pminub %xmm4, %xmm0
> > - pminub %xmm5, %xmm0
> > - pcmpeqb %xmm7, %xmm0
> > - pmovmskb %xmm0, %eax
> > - movdqa %xmm5, %xmm0
> > - pcmpeqb %xmm1, %xmm0
> > - pmovmskb %xmm0, %r9d
> > - movdqa %xmm4, %xmm0
> > - pcmpeqb %xmm1, %xmm0
> > - pmovmskb %xmm0, %edx
> > - movdqa %xmm3, %xmm0
> > - pcmpeqb %xmm1, %xmm0
> > - salq $16, %rdx
> > - pmovmskb %xmm0, %r10d
> > - movdqa %xmm2, %xmm0
> > - pcmpeqb %xmm1, %xmm0
> > - salq $32, %r10
> > - orq %r10, %rdx
> > - pmovmskb %xmm0, %r8d
> > - orq %r9, %rdx
> > - salq $48, %r8
> > - orq %r8, %rdx
> > +L(first_vec_x1_test):
> > + PCMPEQ %xmm0, %xmm2
> > + pmovmskb %xmm2, %eax
> > testl %eax, %eax
> > - je L(loop64)
> > - pcmpeqb %xmm6, %xmm4
> > - pcmpeqb %xmm6, %xmm3
> > - pcmpeqb %xmm6, %xmm5
> > - pmovmskb %xmm4, %eax
> > - pmovmskb %xmm3, %r10d
> > - pcmpeqb %xmm6, %xmm2
> > - pmovmskb %xmm5, %r9d
> > - salq $32, %r10
> > - salq $16, %rax
> > - pmovmskb %xmm2, %r8d
> > - orq %r10, %rax
> > - orq %r9, %rax
> > - salq $48, %r8
> > - orq %r8, %rax
> > - leaq -1(%rax), %r8
> > - xorq %rax, %r8
> > - andq %r8, %rdx
> > - cmovne %rdi, %rcx
> > - cmovne %rdx, %rsi
> > - bsrq %rsi, %rsi
> > - leaq (%rcx,%rsi), %rax
> > + jz L(first_vec_x0_test)
> > + bsrl %eax, %eax
> > + leaq (VEC_SIZE)(%rdi, %rax), %rax
> > +#ifdef USE_AS_WCSRCHR
> > + andq $-CHAR_SIZE, %rax
> > +#endif
> > + ret
> > +
> > + .p2align 4
> > +L(first_vec_x2):
> > + PCMPEQ %xmm0, %xmm3
> > + pmovmskb %xmm3, %eax
> > + leal -1(%rcx), %edx
> > + xorl %edx, %ecx
> > + andl %ecx, %eax
> > + jz L(first_vec_x1_test)
> > + bsrl %eax, %eax
> > + leaq (VEC_SIZE * 2)(%rdi, %rax), %rax
> > +#ifdef USE_AS_WCSRCHR
> > + andq $-CHAR_SIZE, %rax
> > +#endif
> > + ret
> > +
> > + .p2align 4
> > +L(aligned_more):
> > + /* Save original pointer if match was in VEC 0. */
> > + movq %rdi, %r8
> > + andq $-VEC_SIZE, %rdi
> > +
> > + movaps VEC_SIZE(%rdi), %xmm2
> > + pxor %xmm3, %xmm3
> > + PCMPEQ %xmm2, %xmm3
> > + pmovmskb %xmm3, %ecx
> > + testl %ecx, %ecx
> > + jnz L(first_vec_x1)
> > +
> > + movaps (VEC_SIZE * 2)(%rdi), %xmm3
> > + pxor %xmm4, %xmm4
> > + PCMPEQ %xmm3, %xmm4
> > + pmovmskb %xmm4, %ecx
> > + testl %ecx, %ecx
> > + jnz L(first_vec_x2)
> > +
> > + addq $VEC_SIZE, %rdi
> > + /* Save pointer again before realigning. */
> > + movq %rdi, %rsi
> > + andq $-(VEC_SIZE * 2), %rdi
> > + .p2align 4
> > +L(first_loop):
> > + /* Do 2x VEC at a time. */
> > + movaps (VEC_SIZE * 2)(%rdi), %xmm4
> > + movaps (VEC_SIZE * 3)(%rdi), %xmm5
> > + /* If SSE2 no pminud so wcsrchr needs seperate logic for
> Did you mean "Since", instead of "If"?
Fixed in V3.
>
> > + detecting zero. Note if this is found to be a bottleneck it
> > + may be worth adding an SSE4.1 wcsrchr implementation. */
> > +#ifdef USE_AS_WCSRCHR
> > + movaps %xmm5, %xmm6
> > + pxor %xmm8, %xmm8
> > +
> > + PCMPEQ %xmm8, %xmm5
> > + PCMPEQ %xmm4, %xmm8
> > + por %xmm5, %xmm8
> > +#else
> > + movaps %xmm5, %xmm6
> > + PMINU %xmm4, %xmm5
> > +#endif
> > +
> > + movaps %xmm4, %xmm9
> > + PCMPEQ %xmm0, %xmm4
> > + PCMPEQ %xmm0, %xmm6
> > + movaps %xmm6, %xmm7
> > + por %xmm4, %xmm6
> > +#ifndef USE_AS_WCSRCHR
> > + pxor %xmm8, %xmm8
> > + PCMPEQ %xmm5, %xmm8
> > +#endif
> > + pmovmskb %xmm8, %ecx
> > + pmovmskb %xmm6, %eax
> > +
> > + addq $(VEC_SIZE * 2), %rdi
> > + /* Use `addl` 1) so we can undo it with `subl` and 2) it can
> > + macro-fuse with `jz`. */
> > + addl %ecx, %eax
> > + jz L(first_loop)
> > +
> > + /* Check if there is zero match. */
> > + testl %ecx, %ecx
> > + jz L(second_loop_match)
> > +
> > + /* Check if there was a match in last iteration. */
> > + subl %ecx, %eax
> > + jnz L(new_match)
> > +
> > +L(first_loop_old_match):
> > + PCMPEQ %xmm0, %xmm2
> > + PCMPEQ %xmm0, %xmm3
> > + pmovmskb %xmm2, %ecx
> > + pmovmskb %xmm3, %eax
> > + addl %eax, %ecx
> > + jz L(first_vec_x0_test)
> > + /* NB: We could move this shift to before the branch and save a
> > + bit of code size / performance on the fall through. The
> > + branch leads to the null case which generally seems hotter
> > + than char in first 3x VEC. */
> > + sall $16, %eax
> > + orl %ecx, %eax
> > +
> > + bsrl %eax, %eax
> > + addq %rsi, %rax
> > +#ifdef USE_AS_WCSRCHR
> > + andq $-CHAR_SIZE, %rax
> > +#endif
> > + ret
> > +
> > + .p2align 4
> > +L(new_match):
> > + pxor %xmm6, %xmm6
> > + PCMPEQ %xmm9, %xmm6
> > + pmovmskb %xmm6, %eax
> > + sall $16, %ecx
> > + orl %eax, %ecx
> > +
> > + /* We can't reuse either of the old comparisons as since we mask
> > + of zeros after first zero (instead of using the full
> > + comparison) we can't gurantee no interference between match
> > + after end of string and valid match. */
> > + pmovmskb %xmm4, %eax
> > + pmovmskb %xmm7, %edx
> > + sall $16, %edx
> > + orl %edx, %eax
> > +
> > + leal -1(%ecx), %edx
> > + xorl %edx, %ecx
> > + andl %ecx, %eax
> > + jz L(first_loop_old_match)
> > + bsrl %eax, %eax
> > + addq %rdi, %rax
> > +#ifdef USE_AS_WCSRCHR
> > + andq $-CHAR_SIZE, %rax
> > +#endif
> > ret
> >
> > + /* Save minimum state for getting most recent match. We can
> > + throw out all previous work. */
> > .p2align 4
> > -L(no_c_found):
> > - movl $1, %esi
> > - xorl %ecx, %ecx
> > - jmp L(loop_header)
> > +L(second_loop_match):
> > + movq %rdi, %rsi
> > + movaps %xmm4, %xmm2
> > + movaps %xmm7, %xmm3
> >
> > .p2align 4
> > -L(exit):
> > - xorl %eax, %eax
> > +L(second_loop):
> > + movaps (VEC_SIZE * 2)(%rdi), %xmm4
> > + movaps (VEC_SIZE * 3)(%rdi), %xmm5
> > + /* If SSE2 no pminud so wcsrchr needs seperate logic for
> Did you mean "Since", instead of "If"?
>
> > + detecting zero. Note if this is found to be a bottleneck it
> > + may be worth adding an SSE4.1 wcsrchr implementation. */
> > +#ifdef USE_AS_WCSRCHR
> > + movaps %xmm5, %xmm6
> > + pxor %xmm8, %xmm8
> > +
> > + PCMPEQ %xmm8, %xmm5
> > + PCMPEQ %xmm4, %xmm8
> > + por %xmm5, %xmm8
> > +#else
> > + movaps %xmm5, %xmm6
> > + PMINU %xmm4, %xmm5
> > +#endif
> > +
> > + movaps %xmm4, %xmm9
> > + PCMPEQ %xmm0, %xmm4
> > + PCMPEQ %xmm0, %xmm6
> > + movaps %xmm6, %xmm7
> > + por %xmm4, %xmm6
> > +#ifndef USE_AS_WCSRCHR
> > + pxor %xmm8, %xmm8
> > + PCMPEQ %xmm5, %xmm8
> > +#endif
> > +
> > + pmovmskb %xmm8, %ecx
> > + pmovmskb %xmm6, %eax
> > +
> > + addq $(VEC_SIZE * 2), %rdi
> > + /* Either null term or new occurence of CHAR. */
> > + addl %ecx, %eax
> > + jz L(second_loop)
> > +
> > + /* No null term so much be new occurence of CHAR. */
> > + testl %ecx, %ecx
> > + jz L(second_loop_match)
> > +
> > +
> > + subl %ecx, %eax
> > + jnz L(second_loop_new_match)
> > +
> > +L(second_loop_old_match):
> > + pmovmskb %xmm2, %ecx
> > + pmovmskb %xmm3, %eax
> > + sall $16, %eax
> > + orl %ecx, %eax
> > + bsrl %eax, %eax
> > + addq %rsi, %rax
> > +#ifdef USE_AS_WCSRCHR
> > + andq $-CHAR_SIZE, %rax
> > +#endif
> > ret
> >
> > .p2align 4
> > +L(second_loop_new_match):
> > + pxor %xmm6, %xmm6
> > + PCMPEQ %xmm9, %xmm6
> > + pmovmskb %xmm6, %eax
> > + sall $16, %ecx
> > + orl %eax, %ecx
> > +
> > + /* We can't reuse either of the old comparisons as since we mask
> > + of zeros after first zero (instead of using the full
> > + comparison) we can't gurantee no interference between match
> > + after end of string and valid match. */
> > + pmovmskb %xmm4, %eax
> > + pmovmskb %xmm7, %edx
> > + sall $16, %edx
> > + orl %edx, %eax
> > +
> > + leal -1(%ecx), %edx
> > + xorl %edx, %ecx
> > + andl %ecx, %eax
> > + jz L(second_loop_old_match)
> > + bsrl %eax, %eax
> > + addq %rdi, %rax
> > +#ifdef USE_AS_WCSRCHR
> > + andq $-CHAR_SIZE, %rax
> > +#endif
> > + ret
> > +
> > + .p2align 4,, 4
> > L(cross_page):
> > - movq %rdi, %rax
> > - pxor %xmm0, %xmm0
> > - andq $-64, %rax
> > - movdqu (%rax), %xmm5
> > - movdqa %xmm5, %xmm6
> > - movdqu 16(%rax), %xmm4
> > - pcmpeqb %xmm1, %xmm5
> > - pcmpeqb %xmm0, %xmm6
> > - movdqu 32(%rax), %xmm3
> > - pmovmskb %xmm6, %esi
> > - movdqa %xmm4, %xmm6
> > - movdqu 48(%rax), %xmm2
> > - pcmpeqb %xmm1, %xmm4
> > - pcmpeqb %xmm0, %xmm6
> > - pmovmskb %xmm6, %edx
> > - movdqa %xmm3, %xmm6
> > - pcmpeqb %xmm1, %xmm3
> > - pcmpeqb %xmm0, %xmm6
> > - pcmpeqb %xmm2, %xmm0
> > - salq $16, %rdx
> > - pmovmskb %xmm3, %r9d
> > - pmovmskb %xmm6, %r8d
> > - pmovmskb %xmm0, %ecx
> > - salq $32, %r9
> > - salq $32, %r8
> > - pcmpeqb %xmm1, %xmm2
> > - orq %r8, %rdx
> > - salq $48, %rcx
> > - pmovmskb %xmm5, %r8d
> > - orq %rsi, %rdx
> > - pmovmskb %xmm4, %esi
> > - orq %rcx, %rdx
> > - pmovmskb %xmm2, %ecx
> > - salq $16, %rsi
> > - salq $48, %rcx
> > - orq %r9, %rsi
> > - orq %r8, %rsi
> > - orq %rcx, %rsi
> > + movq %rdi, %rsi
> > + andq $-VEC_SIZE, %rsi
> > + movaps (%rsi), %xmm1
> > + pxor %xmm2, %xmm2
> > + PCMPEQ %xmm1, %xmm2
> > + pmovmskb %xmm2, %edx
> > movl %edi, %ecx
> > - subl %eax, %ecx
> > - shrq %cl, %rdx
> > - shrq %cl, %rsi
> > - testq %rdx, %rdx
> > - je L(loop_header2)
> > - leaq -1(%rdx), %rax
> > - xorq %rdx, %rax
> > - andq %rax, %rsi
> > - je L(exit)
> > - bsrq %rsi, %rax
> > + andl $(VEC_SIZE - 1), %ecx
> > + sarl %cl, %edx
> > + jz L(cross_page_continue)
> > + PCMPEQ %xmm0, %xmm1
> > + pmovmskb %xmm1, %eax
> > + sarl %cl, %eax
> > + leal -1(%rdx), %ecx
> > + xorl %edx, %ecx
> > + andl %ecx, %eax
> > + jz L(ret1)
> > + bsrl %eax, %eax
> > addq %rdi, %rax
> > +#ifdef USE_AS_WCSRCHR
> > + andq $-CHAR_SIZE, %rax
> > +#endif
> > +L(ret1):
> > ret
> > -END (strrchr)
> > +END(STRRCHR)
> >
> > -weak_alias (strrchr, rindex)
> > -libc_hidden_builtin_def (strrchr)
> > +#ifndef USE_AS_WCSRCHR
> > + weak_alias (STRRCHR, rindex)
> > + libc_hidden_builtin_def (STRRCHR)
> > +#endif
> > diff --git a/sysdeps/x86_64/wcsrchr.S b/sysdeps/x86_64/wcsrchr.S
> > index 61552954de..2b80efc5ef 100644
> > --- a/sysdeps/x86_64/wcsrchr.S
> > +++ b/sysdeps/x86_64/wcsrchr.S
> > @@ -1,4 +1,4 @@
> > -/* wcsrchr with SSSE3
> > +/* wcsrchr optimized with SSE2.
> > Copyright (C) 2011-2022 Free Software Foundation, Inc.
> > This file is part of the GNU C Library.
> >
> > @@ -16,266 +16,12 @@
> > License along with the GNU C Library; if not, see
> > <https://www.gnu.org/licenses/>. */
> >
> > -#include <sysdep.h>
> >
> > - .text
> > -ENTRY (wcsrchr)
> > +#define USE_AS_WCSRCHR 1
> > +#define NO_PMINU 1
> >
> > - movd %rsi, %xmm1
> > - mov %rdi, %rcx
> > - punpckldq %xmm1, %xmm1
> > - pxor %xmm2, %xmm2
> > - punpckldq %xmm1, %xmm1
> > - and $63, %rcx
> > - cmp $48, %rcx
> > - ja L(crosscache)
> > +#ifndef STRRCHR
> > +# define STRRCHR wcsrchr
> > +#endif
> >
> > - movdqu (%rdi), %xmm0
> > - pcmpeqd %xmm0, %xmm2
> > - pcmpeqd %xmm1, %xmm0
> > - pmovmskb %xmm2, %rcx
> > - pmovmskb %xmm0, %rax
> > - add $16, %rdi
> > -
> > - test %rax, %rax
> > - jnz L(unaligned_match1)
> > -
> > - test %rcx, %rcx
> > - jnz L(return_null)
> > -
> > - and $-16, %rdi
> > - xor %r8, %r8
> > - jmp L(loop)
> > -
> > - .p2align 4
> > -L(unaligned_match1):
> > - test %rcx, %rcx
> > - jnz L(prolog_find_zero_1)
> > -
> > - mov %rax, %r8
> > - mov %rdi, %rsi
> > - and $-16, %rdi
> > - jmp L(loop)
> > -
> > - .p2align 4
> > -L(crosscache):
> > - and $15, %rcx
> > - and $-16, %rdi
> > - pxor %xmm3, %xmm3
> > - movdqa (%rdi), %xmm0
> > - pcmpeqd %xmm0, %xmm3
> > - pcmpeqd %xmm1, %xmm0
> > - pmovmskb %xmm3, %rdx
> > - pmovmskb %xmm0, %rax
> > - shr %cl, %rdx
> > - shr %cl, %rax
> > - add $16, %rdi
> > -
> > - test %rax, %rax
> > - jnz L(unaligned_match)
> > -
> > - test %rdx, %rdx
> > - jnz L(return_null)
> > -
> > - xor %r8, %r8
> > - jmp L(loop)
> > -
> > - .p2align 4
> > -L(unaligned_match):
> > - test %rdx, %rdx
> > - jnz L(prolog_find_zero)
> > -
> > - mov %rax, %r8
> > - lea (%rdi, %rcx), %rsi
> > -
> > -/* Loop start on aligned string. */
> > - .p2align 4
> > -L(loop):
> > - movdqa (%rdi), %xmm0
> > - pcmpeqd %xmm0, %xmm2
> > - add $16, %rdi
> > - pcmpeqd %xmm1, %xmm0
> > - pmovmskb %xmm2, %rcx
> > - pmovmskb %xmm0, %rax
> > - or %rax, %rcx
> > - jnz L(matches)
> > -
> > - movdqa (%rdi), %xmm3
> > - pcmpeqd %xmm3, %xmm2
> > - add $16, %rdi
> > - pcmpeqd %xmm1, %xmm3
> > - pmovmskb %xmm2, %rcx
> > - pmovmskb %xmm3, %rax
> > - or %rax, %rcx
> > - jnz L(matches)
> > -
> > - movdqa (%rdi), %xmm4
> > - pcmpeqd %xmm4, %xmm2
> > - add $16, %rdi
> > - pcmpeqd %xmm1, %xmm4
> > - pmovmskb %xmm2, %rcx
> > - pmovmskb %xmm4, %rax
> > - or %rax, %rcx
> > - jnz L(matches)
> > -
> > - movdqa (%rdi), %xmm5
> > - pcmpeqd %xmm5, %xmm2
> > - add $16, %rdi
> > - pcmpeqd %xmm1, %xmm5
> > - pmovmskb %xmm2, %rcx
> > - pmovmskb %xmm5, %rax
> > - or %rax, %rcx
> > - jz L(loop)
> > -
> > - .p2align 4
> > -L(matches):
> > - test %rax, %rax
> > - jnz L(match)
> > -L(return_value):
> > - test %r8, %r8
> > - jz L(return_null)
> > - mov %r8, %rax
> > - mov %rsi, %rdi
> > -
> > - test $15 << 4, %ah
> > - jnz L(match_fourth_wchar)
> > - test %ah, %ah
> > - jnz L(match_third_wchar)
> > - test $15 << 4, %al
> > - jnz L(match_second_wchar)
> > - lea -16(%rdi), %rax
> > - ret
> > -
> > - .p2align 4
> > -L(match):
> > - pmovmskb %xmm2, %rcx
> > - test %rcx, %rcx
> > - jnz L(find_zero)
> > - mov %rax, %r8
> > - mov %rdi, %rsi
> > - jmp L(loop)
> > -
> > - .p2align 4
> > -L(find_zero):
> > - test $15, %cl
> > - jnz L(find_zero_in_first_wchar)
> > - test %cl, %cl
> > - jnz L(find_zero_in_second_wchar)
> > - test $15, %ch
> > - jnz L(find_zero_in_third_wchar)
> > -
> > - and $1 << 13 - 1, %rax
> > - jz L(return_value)
> > -
> > - test $15 << 4, %ah
> > - jnz L(match_fourth_wchar)
> > - test %ah, %ah
> > - jnz L(match_third_wchar)
> > - test $15 << 4, %al
> > - jnz L(match_second_wchar)
> > - lea -16(%rdi), %rax
> > - ret
> > -
> > - .p2align 4
> > -L(find_zero_in_first_wchar):
> > - test $1, %rax
> > - jz L(return_value)
> > - lea -16(%rdi), %rax
> > - ret
> > -
> > - .p2align 4
> > -L(find_zero_in_second_wchar):
> > - and $1 << 5 - 1, %rax
> > - jz L(return_value)
> > -
> > - test $15 << 4, %al
> > - jnz L(match_second_wchar)
> > - lea -16(%rdi), %rax
> > - ret
> > -
> > - .p2align 4
> > -L(find_zero_in_third_wchar):
> > - and $1 << 9 - 1, %rax
> > - jz L(return_value)
> > -
> > - test %ah, %ah
> > - jnz L(match_third_wchar)
> > - test $15 << 4, %al
> > - jnz L(match_second_wchar)
> > - lea -16(%rdi), %rax
> > - ret
> > -
> > - .p2align 4
> > -L(prolog_find_zero):
> > - add %rcx, %rdi
> > - mov %rdx, %rcx
> > -L(prolog_find_zero_1):
> > - test $15, %cl
> > - jnz L(prolog_find_zero_in_first_wchar)
> > - test %cl, %cl
> > - jnz L(prolog_find_zero_in_second_wchar)
> > - test $15, %ch
> > - jnz L(prolog_find_zero_in_third_wchar)
> > -
> > - and $1 << 13 - 1, %rax
> > - jz L(return_null)
> > -
> > - test $15 << 4, %ah
> > - jnz L(match_fourth_wchar)
> > - test %ah, %ah
> > - jnz L(match_third_wchar)
> > - test $15 << 4, %al
> > - jnz L(match_second_wchar)
> > - lea -16(%rdi), %rax
> > - ret
> > -
> > - .p2align 4
> > -L(prolog_find_zero_in_first_wchar):
> > - test $1, %rax
> > - jz L(return_null)
> > - lea -16(%rdi), %rax
> > - ret
> > -
> > - .p2align 4
> > -L(prolog_find_zero_in_second_wchar):
> > - and $1 << 5 - 1, %rax
> > - jz L(return_null)
> > -
> > - test $15 << 4, %al
> > - jnz L(match_second_wchar)
> > - lea -16(%rdi), %rax
> > - ret
> > -
> > - .p2align 4
> > -L(prolog_find_zero_in_third_wchar):
> > - and $1 << 9 - 1, %rax
> > - jz L(return_null)
> > -
> > - test %ah, %ah
> > - jnz L(match_third_wchar)
> > - test $15 << 4, %al
> > - jnz L(match_second_wchar)
> > - lea -16(%rdi), %rax
> > - ret
> > -
> > - .p2align 4
> > -L(match_second_wchar):
> > - lea -12(%rdi), %rax
> > - ret
> > -
> > - .p2align 4
> > -L(match_third_wchar):
> > - lea -8(%rdi), %rax
> > - ret
> > -
> > - .p2align 4
> > -L(match_fourth_wchar):
> > - lea -4(%rdi), %rax
> > - ret
> > -
> > - .p2align 4
> > -L(return_null):
> > - xor %rax, %rax
> > - ret
> > -
> > -END (wcsrchr)
> > +#include "../strrchr.S"
> > --
> > 2.25.1
> >
>
>
> --
> H.J.
@@ -17,7 +17,7 @@
<https://www.gnu.org/licenses/>. */
#if IS_IN (libc)
-# define strrchr __strrchr_sse2
+# define STRRCHR __strrchr_sse2
# undef weak_alias
# define weak_alias(strrchr, rindex)
@@ -17,7 +17,6 @@
<https://www.gnu.org/licenses/>. */
#if IS_IN (libc)
-# define wcsrchr __wcsrchr_sse2
+# define STRRCHR __wcsrchr_sse2
#endif
-
#include "../wcsrchr.S"
@@ -19,210 +19,360 @@
#include <sysdep.h>
+#ifndef STRRCHR
+# define STRRCHR strrchr
+#endif
+
+#ifdef USE_AS_WCSRCHR
+# define PCMPEQ pcmpeqd
+# define CHAR_SIZE 4
+# define PMINU pminud
+#else
+# define PCMPEQ pcmpeqb
+# define CHAR_SIZE 1
+# define PMINU pminub
+#endif
+
+#define PAGE_SIZE 4096
+#define VEC_SIZE 16
+
.text
-ENTRY (strrchr)
- movd %esi, %xmm1
+ENTRY(STRRCHR)
+ movd %esi, %xmm0
movq %rdi, %rax
- andl $4095, %eax
- punpcklbw %xmm1, %xmm1
- cmpq $4032, %rax
- punpcklwd %xmm1, %xmm1
- pshufd $0, %xmm1, %xmm1
+ andl $(PAGE_SIZE - 1), %eax
+#ifndef USE_AS_WCSRCHR
+ punpcklbw %xmm0, %xmm0
+ punpcklwd %xmm0, %xmm0
+#endif
+ pshufd $0, %xmm0, %xmm0
+ cmpl $(PAGE_SIZE - VEC_SIZE), %eax
ja L(cross_page)
- movdqu (%rdi), %xmm0
+
+L(cross_page_continue):
+ movups (%rdi), %xmm1
pxor %xmm2, %xmm2
- movdqa %xmm0, %xmm3
- pcmpeqb %xmm1, %xmm0
- pcmpeqb %xmm2, %xmm3
- pmovmskb %xmm0, %ecx
- pmovmskb %xmm3, %edx
- testq %rdx, %rdx
- je L(next_48_bytes)
- leaq -1(%rdx), %rax
- xorq %rdx, %rax
- andq %rcx, %rax
- je L(exit)
- bsrq %rax, %rax
+ PCMPEQ %xmm1, %xmm2
+ pmovmskb %xmm2, %ecx
+ testl %ecx, %ecx
+ jz L(aligned_more)
+
+ PCMPEQ %xmm0, %xmm1
+ pmovmskb %xmm1, %eax
+ leal -1(%rcx), %edx
+ xorl %edx, %ecx
+ andl %ecx, %eax
+ jz L(ret0)
+ bsrl %eax, %eax
addq %rdi, %rax
+ /* We are off by 3 for wcsrchr if search CHAR is non-zero. If
+ search CHAR is zero we are correct. Either way `andq
+ -CHAR_SIZE, %rax` gets the correct result. */
+#ifdef USE_AS_WCSRCHR
+ andq $-CHAR_SIZE, %rax
+#endif
+L(ret0):
ret
+ /* Returns for first vec x1/x2 have hard coded backward search
+ path for earlier matches. */
.p2align 4
-L(next_48_bytes):
- movdqu 16(%rdi), %xmm4
- movdqa %xmm4, %xmm5
- movdqu 32(%rdi), %xmm3
- pcmpeqb %xmm1, %xmm4
- pcmpeqb %xmm2, %xmm5
- movdqu 48(%rdi), %xmm0
- pmovmskb %xmm5, %edx
- movdqa %xmm3, %xmm5
- pcmpeqb %xmm1, %xmm3
- pcmpeqb %xmm2, %xmm5
- pcmpeqb %xmm0, %xmm2
- salq $16, %rdx
- pmovmskb %xmm3, %r8d
- pmovmskb %xmm5, %eax
- pmovmskb %xmm2, %esi
- salq $32, %r8
- salq $32, %rax
- pcmpeqb %xmm1, %xmm0
- orq %rdx, %rax
- movq %rsi, %rdx
- pmovmskb %xmm4, %esi
- salq $48, %rdx
- salq $16, %rsi
- orq %r8, %rsi
- orq %rcx, %rsi
- pmovmskb %xmm0, %ecx
- salq $48, %rcx
- orq %rcx, %rsi
- orq %rdx, %rax
- je L(loop_header2)
- leaq -1(%rax), %rcx
- xorq %rax, %rcx
- andq %rcx, %rsi
- je L(exit)
- bsrq %rsi, %rsi
- leaq (%rdi,%rsi), %rax
+L(first_vec_x0_test):
+ PCMPEQ %xmm0, %xmm1
+ pmovmskb %xmm1, %eax
+ testl %eax, %eax
+ jz L(ret0)
+ bsrl %eax, %eax
+ addq %r8, %rax
+#ifdef USE_AS_WCSRCHR
+ andq $-CHAR_SIZE, %rax
+#endif
ret
.p2align 4
-L(loop_header2):
- testq %rsi, %rsi
- movq %rdi, %rcx
- je L(no_c_found)
-L(loop_header):
- addq $64, %rdi
- pxor %xmm7, %xmm7
- andq $-64, %rdi
- jmp L(loop_entry)
+L(first_vec_x1):
+ PCMPEQ %xmm0, %xmm2
+ pmovmskb %xmm2, %eax
+ leal -1(%rcx), %edx
+ xorl %edx, %ecx
+ andl %ecx, %eax
+ jz L(first_vec_x0_test)
+ bsrl %eax, %eax
+ leaq (VEC_SIZE)(%rdi, %rax), %rax
+#ifdef USE_AS_WCSRCHR
+ andq $-CHAR_SIZE, %rax
+#endif
+ ret
.p2align 4
-L(loop64):
- testq %rdx, %rdx
- cmovne %rdx, %rsi
- cmovne %rdi, %rcx
- addq $64, %rdi
-L(loop_entry):
- movdqa 32(%rdi), %xmm3
- pxor %xmm6, %xmm6
- movdqa 48(%rdi), %xmm2
- movdqa %xmm3, %xmm0
- movdqa 16(%rdi), %xmm4
- pminub %xmm2, %xmm0
- movdqa (%rdi), %xmm5
- pminub %xmm4, %xmm0
- pminub %xmm5, %xmm0
- pcmpeqb %xmm7, %xmm0
- pmovmskb %xmm0, %eax
- movdqa %xmm5, %xmm0
- pcmpeqb %xmm1, %xmm0
- pmovmskb %xmm0, %r9d
- movdqa %xmm4, %xmm0
- pcmpeqb %xmm1, %xmm0
- pmovmskb %xmm0, %edx
- movdqa %xmm3, %xmm0
- pcmpeqb %xmm1, %xmm0
- salq $16, %rdx
- pmovmskb %xmm0, %r10d
- movdqa %xmm2, %xmm0
- pcmpeqb %xmm1, %xmm0
- salq $32, %r10
- orq %r10, %rdx
- pmovmskb %xmm0, %r8d
- orq %r9, %rdx
- salq $48, %r8
- orq %r8, %rdx
+L(first_vec_x1_test):
+ PCMPEQ %xmm0, %xmm2
+ pmovmskb %xmm2, %eax
testl %eax, %eax
- je L(loop64)
- pcmpeqb %xmm6, %xmm4
- pcmpeqb %xmm6, %xmm3
- pcmpeqb %xmm6, %xmm5
- pmovmskb %xmm4, %eax
- pmovmskb %xmm3, %r10d
- pcmpeqb %xmm6, %xmm2
- pmovmskb %xmm5, %r9d
- salq $32, %r10
- salq $16, %rax
- pmovmskb %xmm2, %r8d
- orq %r10, %rax
- orq %r9, %rax
- salq $48, %r8
- orq %r8, %rax
- leaq -1(%rax), %r8
- xorq %rax, %r8
- andq %r8, %rdx
- cmovne %rdi, %rcx
- cmovne %rdx, %rsi
- bsrq %rsi, %rsi
- leaq (%rcx,%rsi), %rax
+ jz L(first_vec_x0_test)
+ bsrl %eax, %eax
+ leaq (VEC_SIZE)(%rdi, %rax), %rax
+#ifdef USE_AS_WCSRCHR
+ andq $-CHAR_SIZE, %rax
+#endif
+ ret
+
+ .p2align 4
+L(first_vec_x2):
+ PCMPEQ %xmm0, %xmm3
+ pmovmskb %xmm3, %eax
+ leal -1(%rcx), %edx
+ xorl %edx, %ecx
+ andl %ecx, %eax
+ jz L(first_vec_x1_test)
+ bsrl %eax, %eax
+ leaq (VEC_SIZE * 2)(%rdi, %rax), %rax
+#ifdef USE_AS_WCSRCHR
+ andq $-CHAR_SIZE, %rax
+#endif
+ ret
+
+ .p2align 4
+L(aligned_more):
+ /* Save original pointer if match was in VEC 0. */
+ movq %rdi, %r8
+ andq $-VEC_SIZE, %rdi
+
+ movaps VEC_SIZE(%rdi), %xmm2
+ pxor %xmm3, %xmm3
+ PCMPEQ %xmm2, %xmm3
+ pmovmskb %xmm3, %ecx
+ testl %ecx, %ecx
+ jnz L(first_vec_x1)
+
+ movaps (VEC_SIZE * 2)(%rdi), %xmm3
+ pxor %xmm4, %xmm4
+ PCMPEQ %xmm3, %xmm4
+ pmovmskb %xmm4, %ecx
+ testl %ecx, %ecx
+ jnz L(first_vec_x2)
+
+ addq $VEC_SIZE, %rdi
+ /* Save pointer again before realigning. */
+ movq %rdi, %rsi
+ andq $-(VEC_SIZE * 2), %rdi
+ .p2align 4
+L(first_loop):
+ /* Do 2x VEC at a time. */
+ movaps (VEC_SIZE * 2)(%rdi), %xmm4
+ movaps (VEC_SIZE * 3)(%rdi), %xmm5
+ /* If SSE2 no pminud so wcsrchr needs seperate logic for
+ detecting zero. Note if this is found to be a bottleneck it
+ may be worth adding an SSE4.1 wcsrchr implementation. */
+#ifdef USE_AS_WCSRCHR
+ movaps %xmm5, %xmm6
+ pxor %xmm8, %xmm8
+
+ PCMPEQ %xmm8, %xmm5
+ PCMPEQ %xmm4, %xmm8
+ por %xmm5, %xmm8
+#else
+ movaps %xmm5, %xmm6
+ PMINU %xmm4, %xmm5
+#endif
+
+ movaps %xmm4, %xmm9
+ PCMPEQ %xmm0, %xmm4
+ PCMPEQ %xmm0, %xmm6
+ movaps %xmm6, %xmm7
+ por %xmm4, %xmm6
+#ifndef USE_AS_WCSRCHR
+ pxor %xmm8, %xmm8
+ PCMPEQ %xmm5, %xmm8
+#endif
+ pmovmskb %xmm8, %ecx
+ pmovmskb %xmm6, %eax
+
+ addq $(VEC_SIZE * 2), %rdi
+ /* Use `addl` 1) so we can undo it with `subl` and 2) it can
+ macro-fuse with `jz`. */
+ addl %ecx, %eax
+ jz L(first_loop)
+
+ /* Check if there is zero match. */
+ testl %ecx, %ecx
+ jz L(second_loop_match)
+
+ /* Check if there was a match in last iteration. */
+ subl %ecx, %eax
+ jnz L(new_match)
+
+L(first_loop_old_match):
+ PCMPEQ %xmm0, %xmm2
+ PCMPEQ %xmm0, %xmm3
+ pmovmskb %xmm2, %ecx
+ pmovmskb %xmm3, %eax
+ addl %eax, %ecx
+ jz L(first_vec_x0_test)
+ /* NB: We could move this shift to before the branch and save a
+ bit of code size / performance on the fall through. The
+ branch leads to the null case which generally seems hotter
+ than char in first 3x VEC. */
+ sall $16, %eax
+ orl %ecx, %eax
+
+ bsrl %eax, %eax
+ addq %rsi, %rax
+#ifdef USE_AS_WCSRCHR
+ andq $-CHAR_SIZE, %rax
+#endif
+ ret
+
+ .p2align 4
+L(new_match):
+ pxor %xmm6, %xmm6
+ PCMPEQ %xmm9, %xmm6
+ pmovmskb %xmm6, %eax
+ sall $16, %ecx
+ orl %eax, %ecx
+
+ /* We can't reuse either of the old comparisons as since we mask
+ of zeros after first zero (instead of using the full
+ comparison) we can't gurantee no interference between match
+ after end of string and valid match. */
+ pmovmskb %xmm4, %eax
+ pmovmskb %xmm7, %edx
+ sall $16, %edx
+ orl %edx, %eax
+
+ leal -1(%ecx), %edx
+ xorl %edx, %ecx
+ andl %ecx, %eax
+ jz L(first_loop_old_match)
+ bsrl %eax, %eax
+ addq %rdi, %rax
+#ifdef USE_AS_WCSRCHR
+ andq $-CHAR_SIZE, %rax
+#endif
ret
+ /* Save minimum state for getting most recent match. We can
+ throw out all previous work. */
.p2align 4
-L(no_c_found):
- movl $1, %esi
- xorl %ecx, %ecx
- jmp L(loop_header)
+L(second_loop_match):
+ movq %rdi, %rsi
+ movaps %xmm4, %xmm2
+ movaps %xmm7, %xmm3
.p2align 4
-L(exit):
- xorl %eax, %eax
+L(second_loop):
+ movaps (VEC_SIZE * 2)(%rdi), %xmm4
+ movaps (VEC_SIZE * 3)(%rdi), %xmm5
+ /* If SSE2 no pminud so wcsrchr needs seperate logic for
+ detecting zero. Note if this is found to be a bottleneck it
+ may be worth adding an SSE4.1 wcsrchr implementation. */
+#ifdef USE_AS_WCSRCHR
+ movaps %xmm5, %xmm6
+ pxor %xmm8, %xmm8
+
+ PCMPEQ %xmm8, %xmm5
+ PCMPEQ %xmm4, %xmm8
+ por %xmm5, %xmm8
+#else
+ movaps %xmm5, %xmm6
+ PMINU %xmm4, %xmm5
+#endif
+
+ movaps %xmm4, %xmm9
+ PCMPEQ %xmm0, %xmm4
+ PCMPEQ %xmm0, %xmm6
+ movaps %xmm6, %xmm7
+ por %xmm4, %xmm6
+#ifndef USE_AS_WCSRCHR
+ pxor %xmm8, %xmm8
+ PCMPEQ %xmm5, %xmm8
+#endif
+
+ pmovmskb %xmm8, %ecx
+ pmovmskb %xmm6, %eax
+
+ addq $(VEC_SIZE * 2), %rdi
+ /* Either null term or new occurence of CHAR. */
+ addl %ecx, %eax
+ jz L(second_loop)
+
+ /* No null term so much be new occurence of CHAR. */
+ testl %ecx, %ecx
+ jz L(second_loop_match)
+
+
+ subl %ecx, %eax
+ jnz L(second_loop_new_match)
+
+L(second_loop_old_match):
+ pmovmskb %xmm2, %ecx
+ pmovmskb %xmm3, %eax
+ sall $16, %eax
+ orl %ecx, %eax
+ bsrl %eax, %eax
+ addq %rsi, %rax
+#ifdef USE_AS_WCSRCHR
+ andq $-CHAR_SIZE, %rax
+#endif
ret
.p2align 4
+L(second_loop_new_match):
+ pxor %xmm6, %xmm6
+ PCMPEQ %xmm9, %xmm6
+ pmovmskb %xmm6, %eax
+ sall $16, %ecx
+ orl %eax, %ecx
+
+ /* We can't reuse either of the old comparisons as since we mask
+ of zeros after first zero (instead of using the full
+ comparison) we can't gurantee no interference between match
+ after end of string and valid match. */
+ pmovmskb %xmm4, %eax
+ pmovmskb %xmm7, %edx
+ sall $16, %edx
+ orl %edx, %eax
+
+ leal -1(%ecx), %edx
+ xorl %edx, %ecx
+ andl %ecx, %eax
+ jz L(second_loop_old_match)
+ bsrl %eax, %eax
+ addq %rdi, %rax
+#ifdef USE_AS_WCSRCHR
+ andq $-CHAR_SIZE, %rax
+#endif
+ ret
+
+ .p2align 4,, 4
L(cross_page):
- movq %rdi, %rax
- pxor %xmm0, %xmm0
- andq $-64, %rax
- movdqu (%rax), %xmm5
- movdqa %xmm5, %xmm6
- movdqu 16(%rax), %xmm4
- pcmpeqb %xmm1, %xmm5
- pcmpeqb %xmm0, %xmm6
- movdqu 32(%rax), %xmm3
- pmovmskb %xmm6, %esi
- movdqa %xmm4, %xmm6
- movdqu 48(%rax), %xmm2
- pcmpeqb %xmm1, %xmm4
- pcmpeqb %xmm0, %xmm6
- pmovmskb %xmm6, %edx
- movdqa %xmm3, %xmm6
- pcmpeqb %xmm1, %xmm3
- pcmpeqb %xmm0, %xmm6
- pcmpeqb %xmm2, %xmm0
- salq $16, %rdx
- pmovmskb %xmm3, %r9d
- pmovmskb %xmm6, %r8d
- pmovmskb %xmm0, %ecx
- salq $32, %r9
- salq $32, %r8
- pcmpeqb %xmm1, %xmm2
- orq %r8, %rdx
- salq $48, %rcx
- pmovmskb %xmm5, %r8d
- orq %rsi, %rdx
- pmovmskb %xmm4, %esi
- orq %rcx, %rdx
- pmovmskb %xmm2, %ecx
- salq $16, %rsi
- salq $48, %rcx
- orq %r9, %rsi
- orq %r8, %rsi
- orq %rcx, %rsi
+ movq %rdi, %rsi
+ andq $-VEC_SIZE, %rsi
+ movaps (%rsi), %xmm1
+ pxor %xmm2, %xmm2
+ PCMPEQ %xmm1, %xmm2
+ pmovmskb %xmm2, %edx
movl %edi, %ecx
- subl %eax, %ecx
- shrq %cl, %rdx
- shrq %cl, %rsi
- testq %rdx, %rdx
- je L(loop_header2)
- leaq -1(%rdx), %rax
- xorq %rdx, %rax
- andq %rax, %rsi
- je L(exit)
- bsrq %rsi, %rax
+ andl $(VEC_SIZE - 1), %ecx
+ sarl %cl, %edx
+ jz L(cross_page_continue)
+ PCMPEQ %xmm0, %xmm1
+ pmovmskb %xmm1, %eax
+ sarl %cl, %eax
+ leal -1(%rdx), %ecx
+ xorl %edx, %ecx
+ andl %ecx, %eax
+ jz L(ret1)
+ bsrl %eax, %eax
addq %rdi, %rax
+#ifdef USE_AS_WCSRCHR
+ andq $-CHAR_SIZE, %rax
+#endif
+L(ret1):
ret
-END (strrchr)
+END(STRRCHR)
-weak_alias (strrchr, rindex)
-libc_hidden_builtin_def (strrchr)
+#ifndef USE_AS_WCSRCHR
+ weak_alias (STRRCHR, rindex)
+ libc_hidden_builtin_def (STRRCHR)
+#endif
@@ -1,4 +1,4 @@
-/* wcsrchr with SSSE3
+/* wcsrchr optimized with SSE2.
Copyright (C) 2011-2022 Free Software Foundation, Inc.
This file is part of the GNU C Library.
@@ -16,266 +16,12 @@
License along with the GNU C Library; if not, see
<https://www.gnu.org/licenses/>. */
-#include <sysdep.h>
- .text
-ENTRY (wcsrchr)
+#define USE_AS_WCSRCHR 1
+#define NO_PMINU 1
- movd %rsi, %xmm1
- mov %rdi, %rcx
- punpckldq %xmm1, %xmm1
- pxor %xmm2, %xmm2
- punpckldq %xmm1, %xmm1
- and $63, %rcx
- cmp $48, %rcx
- ja L(crosscache)
+#ifndef STRRCHR
+# define STRRCHR wcsrchr
+#endif
- movdqu (%rdi), %xmm0
- pcmpeqd %xmm0, %xmm2
- pcmpeqd %xmm1, %xmm0
- pmovmskb %xmm2, %rcx
- pmovmskb %xmm0, %rax
- add $16, %rdi
-
- test %rax, %rax
- jnz L(unaligned_match1)
-
- test %rcx, %rcx
- jnz L(return_null)
-
- and $-16, %rdi
- xor %r8, %r8
- jmp L(loop)
-
- .p2align 4
-L(unaligned_match1):
- test %rcx, %rcx
- jnz L(prolog_find_zero_1)
-
- mov %rax, %r8
- mov %rdi, %rsi
- and $-16, %rdi
- jmp L(loop)
-
- .p2align 4
-L(crosscache):
- and $15, %rcx
- and $-16, %rdi
- pxor %xmm3, %xmm3
- movdqa (%rdi), %xmm0
- pcmpeqd %xmm0, %xmm3
- pcmpeqd %xmm1, %xmm0
- pmovmskb %xmm3, %rdx
- pmovmskb %xmm0, %rax
- shr %cl, %rdx
- shr %cl, %rax
- add $16, %rdi
-
- test %rax, %rax
- jnz L(unaligned_match)
-
- test %rdx, %rdx
- jnz L(return_null)
-
- xor %r8, %r8
- jmp L(loop)
-
- .p2align 4
-L(unaligned_match):
- test %rdx, %rdx
- jnz L(prolog_find_zero)
-
- mov %rax, %r8
- lea (%rdi, %rcx), %rsi
-
-/* Loop start on aligned string. */
- .p2align 4
-L(loop):
- movdqa (%rdi), %xmm0
- pcmpeqd %xmm0, %xmm2
- add $16, %rdi
- pcmpeqd %xmm1, %xmm0
- pmovmskb %xmm2, %rcx
- pmovmskb %xmm0, %rax
- or %rax, %rcx
- jnz L(matches)
-
- movdqa (%rdi), %xmm3
- pcmpeqd %xmm3, %xmm2
- add $16, %rdi
- pcmpeqd %xmm1, %xmm3
- pmovmskb %xmm2, %rcx
- pmovmskb %xmm3, %rax
- or %rax, %rcx
- jnz L(matches)
-
- movdqa (%rdi), %xmm4
- pcmpeqd %xmm4, %xmm2
- add $16, %rdi
- pcmpeqd %xmm1, %xmm4
- pmovmskb %xmm2, %rcx
- pmovmskb %xmm4, %rax
- or %rax, %rcx
- jnz L(matches)
-
- movdqa (%rdi), %xmm5
- pcmpeqd %xmm5, %xmm2
- add $16, %rdi
- pcmpeqd %xmm1, %xmm5
- pmovmskb %xmm2, %rcx
- pmovmskb %xmm5, %rax
- or %rax, %rcx
- jz L(loop)
-
- .p2align 4
-L(matches):
- test %rax, %rax
- jnz L(match)
-L(return_value):
- test %r8, %r8
- jz L(return_null)
- mov %r8, %rax
- mov %rsi, %rdi
-
- test $15 << 4, %ah
- jnz L(match_fourth_wchar)
- test %ah, %ah
- jnz L(match_third_wchar)
- test $15 << 4, %al
- jnz L(match_second_wchar)
- lea -16(%rdi), %rax
- ret
-
- .p2align 4
-L(match):
- pmovmskb %xmm2, %rcx
- test %rcx, %rcx
- jnz L(find_zero)
- mov %rax, %r8
- mov %rdi, %rsi
- jmp L(loop)
-
- .p2align 4
-L(find_zero):
- test $15, %cl
- jnz L(find_zero_in_first_wchar)
- test %cl, %cl
- jnz L(find_zero_in_second_wchar)
- test $15, %ch
- jnz L(find_zero_in_third_wchar)
-
- and $1 << 13 - 1, %rax
- jz L(return_value)
-
- test $15 << 4, %ah
- jnz L(match_fourth_wchar)
- test %ah, %ah
- jnz L(match_third_wchar)
- test $15 << 4, %al
- jnz L(match_second_wchar)
- lea -16(%rdi), %rax
- ret
-
- .p2align 4
-L(find_zero_in_first_wchar):
- test $1, %rax
- jz L(return_value)
- lea -16(%rdi), %rax
- ret
-
- .p2align 4
-L(find_zero_in_second_wchar):
- and $1 << 5 - 1, %rax
- jz L(return_value)
-
- test $15 << 4, %al
- jnz L(match_second_wchar)
- lea -16(%rdi), %rax
- ret
-
- .p2align 4
-L(find_zero_in_third_wchar):
- and $1 << 9 - 1, %rax
- jz L(return_value)
-
- test %ah, %ah
- jnz L(match_third_wchar)
- test $15 << 4, %al
- jnz L(match_second_wchar)
- lea -16(%rdi), %rax
- ret
-
- .p2align 4
-L(prolog_find_zero):
- add %rcx, %rdi
- mov %rdx, %rcx
-L(prolog_find_zero_1):
- test $15, %cl
- jnz L(prolog_find_zero_in_first_wchar)
- test %cl, %cl
- jnz L(prolog_find_zero_in_second_wchar)
- test $15, %ch
- jnz L(prolog_find_zero_in_third_wchar)
-
- and $1 << 13 - 1, %rax
- jz L(return_null)
-
- test $15 << 4, %ah
- jnz L(match_fourth_wchar)
- test %ah, %ah
- jnz L(match_third_wchar)
- test $15 << 4, %al
- jnz L(match_second_wchar)
- lea -16(%rdi), %rax
- ret
-
- .p2align 4
-L(prolog_find_zero_in_first_wchar):
- test $1, %rax
- jz L(return_null)
- lea -16(%rdi), %rax
- ret
-
- .p2align 4
-L(prolog_find_zero_in_second_wchar):
- and $1 << 5 - 1, %rax
- jz L(return_null)
-
- test $15 << 4, %al
- jnz L(match_second_wchar)
- lea -16(%rdi), %rax
- ret
-
- .p2align 4
-L(prolog_find_zero_in_third_wchar):
- and $1 << 9 - 1, %rax
- jz L(return_null)
-
- test %ah, %ah
- jnz L(match_third_wchar)
- test $15 << 4, %al
- jnz L(match_second_wchar)
- lea -16(%rdi), %rax
- ret
-
- .p2align 4
-L(match_second_wchar):
- lea -12(%rdi), %rax
- ret
-
- .p2align 4
-L(match_third_wchar):
- lea -8(%rdi), %rax
- ret
-
- .p2align 4
-L(match_fourth_wchar):
- lea -4(%rdi), %rax
- ret
-
- .p2align 4
-L(return_null):
- xor %rax, %rax
- ret
-
-END (wcsrchr)
+#include "../strrchr.S"