[v2,1/2] x86: Optimize strlen-evex.S
Commit Message
No bug. This commit optimizes strlen-evex.S. The
optimizations are mostly small things but they add up to roughly
10-30% performance improvement for strlen. The results for strnlen are
bit more ambiguous. test-strlen, test-strnlen, test-wcslen, and
test-wcsnlen are all passing.
Signed-off-by: Noah Goldstein <goldstein.w.n@gmail.com>
---
sysdeps/x86_64/multiarch/strlen-evex.S | 588 ++++++++++++++-----------
1 file changed, 324 insertions(+), 264 deletions(-)
Comments
On Sat, Apr 17, 2021 at 3:03 PM Noah Goldstein <goldstein.w.n@gmail.com> wrote:
>
> No bug. This commit optimizes strlen-evex.S. The
> optimizations are mostly small things but they add up to roughly
> 10-30% performance improvement for strlen. The results for strnlen are
> bit more ambiguous. test-strlen, test-strnlen, test-wcslen, and
> test-wcsnlen are all passing.
>
> Signed-off-by: Noah Goldstein <goldstein.w.n@gmail.com>
> ---
> sysdeps/x86_64/multiarch/strlen-evex.S | 588 ++++++++++++++-----------
> 1 file changed, 324 insertions(+), 264 deletions(-)
>
> diff --git a/sysdeps/x86_64/multiarch/strlen-evex.S b/sysdeps/x86_64/multiarch/strlen-evex.S
> index 0583819078..c1c88d84e5 100644
> --- a/sysdeps/x86_64/multiarch/strlen-evex.S
> +++ b/sysdeps/x86_64/multiarch/strlen-evex.S
> @@ -29,11 +29,13 @@
> # ifdef USE_AS_WCSLEN
> # define VPCMP vpcmpd
> # define VPMINU vpminud
> -# define SHIFT_REG r9d
> +# define SHIFT_REG ecx
> +# define CHAR_SIZE 4
> # else
> # define VPCMP vpcmpb
> # define VPMINU vpminub
> -# define SHIFT_REG ecx
> +# define SHIFT_REG edx
> +# define CHAR_SIZE 1
> # endif
>
> # define XMMZERO xmm16
> @@ -46,132 +48,172 @@
> # define YMM6 ymm22
>
> # define VEC_SIZE 32
> +# define PAGE_SIZE 4096
> +# define LOG_PAGE_SIZE 12
> +# define CHAR_PER_VEC (VEC_SIZE / CHAR_SIZE)
>
> .section .text.evex,"ax",@progbits
> ENTRY (STRLEN)
> # ifdef USE_AS_STRNLEN
> - /* Check for zero length. */
> + /* Check zero length. */
> test %RSI_LP, %RSI_LP
> jz L(zero)
> -# ifdef USE_AS_WCSLEN
> - shl $2, %RSI_LP
> -# elif defined __ILP32__
> +# ifdef __ILP32__
> /* Clear the upper 32 bits. */
> +# ifdef USE_AS_WCSLEN
> + andl $((1 << (32 - 4)) - 1), %esi
Remove this.
> +# else
> movl %esi, %esi
This clears the upper 32 bits.
> +# endif
> # endif
> mov %RSI_LP, %R8_LP
> # endif
> - movl %edi, %ecx
> - movq %rdi, %rdx
> + movl %edi, %eax
> vpxorq %XMMZERO, %XMMZERO, %XMMZERO
> -
> + /* Shift left eax to clear all bits not relevant to page cross
> + check. This saves 2 bytes of code as opposed to using andl with
> + PAGE_SIZE - 1. Then compare with PAGE_SIZE - VEC_SIZE shifted
> + left by the same amount (an imm32 either way). */
> + sall $(32 - LOG_PAGE_SIZE), %eax
> /* Check if we may cross page boundary with one vector load. */
> - andl $(2 * VEC_SIZE - 1), %ecx
> - cmpl $VEC_SIZE, %ecx
> - ja L(cros_page_boundary)
> + cmpl $((PAGE_SIZE - VEC_SIZE) << (32 - LOG_PAGE_SIZE)), %eax
> + ja L(cross_page_boundary)
>
> /* Check the first VEC_SIZE bytes. Each bit in K0 represents a
> null byte. */
> VPCMP $0, (%rdi), %YMMZERO, %k0
> kmovd %k0, %eax
> - testl %eax, %eax
> -
> # ifdef USE_AS_STRNLEN
> - jnz L(first_vec_x0_check)
> - /* Adjust length and check the end of data. */
> - subq $VEC_SIZE, %rsi
> - jbe L(max)
> -# else
> - jnz L(first_vec_x0)
> + /* If length < CHAR_PER_VEC handle special. */
> + cmpq $CHAR_PER_VEC, %rsi
> + jbe L(first_vec_x0)
> # endif
> -
> - /* Align data for aligned loads in the loop. */
> - addq $VEC_SIZE, %rdi
> - andl $(VEC_SIZE - 1), %ecx
> - andq $-VEC_SIZE, %rdi
> -
> + testl %eax, %eax
> + jz L(aligned_more)
> + tzcntl %eax, %eax
> + ret
> # ifdef USE_AS_STRNLEN
> - /* Adjust length. */
> - addq %rcx, %rsi
Add .p2align 4 here.
> +L(zero):
> + xorl %eax, %eax
> + ret
>
> - subq $(VEC_SIZE * 4), %rsi
> - jbe L(last_4x_vec_or_less)
> + .p2align 4
> +L(first_vec_x0):
> + /* Set bit for max len so that tzcnt will return min of max len
> + and position of first match. */
> + btsq %rsi, %rax
> + tzcntl %eax, %eax
> + ret
> # endif
> - jmp L(more_4x_vec)
>
> .p2align 4
> -L(cros_page_boundary):
> - andl $(VEC_SIZE - 1), %ecx
> - andq $-VEC_SIZE, %rdi
> -
> -# ifdef USE_AS_WCSLEN
> - /* NB: Divide shift count by 4 since each bit in K0 represent 4
> - bytes. */
> - movl %ecx, %SHIFT_REG
> - sarl $2, %SHIFT_REG
> +L(first_vec_x1):
> + tzcntl %eax, %eax
> + /* Safe to use 32 bit instructions as these are only called for
> + size = [1, 159]. */
> +# ifdef USE_AS_STRNLEN
> + /* Use ecx which was computed earlier to compute correct value.
> + */
Please align '*'.
> + leal -(CHAR_PER_VEC * 4 + 1)(%rcx, %rax), %eax
> +# else
> + subl %edx, %edi
> +# ifdef USE_AS_WCSLEN
> + /* NB: Divide bytes by 4 to get the wchar_t count. */
> + sarl $2, %edi
> +# endif
> + leal CHAR_PER_VEC(%rdi, %rax), %eax
> # endif
> - VPCMP $0, (%rdi), %YMMZERO, %k0
> - kmovd %k0, %eax
> + ret
>
> - /* Remove the leading bytes. */
> - sarxl %SHIFT_REG, %eax, %eax
> - testl %eax, %eax
> - jz L(aligned_more)
> + .p2align 4
> +L(first_vec_x2):
> tzcntl %eax, %eax
> -# ifdef USE_AS_WCSLEN
> - /* NB: Multiply wchar_t count by 4 to get the number of bytes. */
> - sall $2, %eax
> -# endif
> + /* Safe to use 32 bit instructions as these are only called for
> + size = [1, 159]. */
> # ifdef USE_AS_STRNLEN
> - /* Check the end of data. */
> - cmpq %rax, %rsi
> - jbe L(max)
> -# endif
> - addq %rdi, %rax
> - addq %rcx, %rax
> - subq %rdx, %rax
> -# ifdef USE_AS_WCSLEN
> - shrq $2, %rax
> + /* Use ecx which was computed earlier to compute correct value.
> + */
> + leal -(CHAR_PER_VEC * 3 + 1)(%rcx, %rax), %eax
> +# else
> + subl %edx, %edi
> +# ifdef USE_AS_WCSLEN
> + /* NB: Divide bytes by 4 to get the wchar_t count. */
> + sarl $2, %edi
> +# endif
> + leal (CHAR_PER_VEC * 2)(%rdi, %rax), %eax
> # endif
> ret
>
> .p2align 4
> -L(aligned_more):
> +L(first_vec_x3):
> + tzcntl %eax, %eax
> + /* Safe to use 32 bit instructions as these are only called for
> + size = [1, 159]. */
> # ifdef USE_AS_STRNLEN
> - /* "rcx" is less than VEC_SIZE. Calculate "rdx + rcx - VEC_SIZE"
> - with "rdx - (VEC_SIZE - rcx)" instead of "(rdx + rcx) - VEC_SIZE"
> - to void possible addition overflow. */
> - negq %rcx
> - addq $VEC_SIZE, %rcx
> -
> - /* Check the end of data. */
> - subq %rcx, %rsi
> - jbe L(max)
> + /* Use ecx which was computed earlier to compute correct value.
> + */
> + leal -(CHAR_PER_VEC * 2 + 1)(%rcx, %rax), %eax
> +# else
> + subl %edx, %edi
> +# ifdef USE_AS_WCSLEN
> + /* NB: Divide bytes by 4 to get the wchar_t count. */
> + sarl $2, %edi
> +# endif
> + leal (CHAR_PER_VEC * 3)(%rdi, %rax), %eax
> # endif
> + ret
>
> - addq $VEC_SIZE, %rdi
> -
> + .p2align 4
> +L(first_vec_x4):
> + tzcntl %eax, %eax
> + /* Safe to use 32 bit instructions as these are only called for
> + size = [1, 159]. */
> # ifdef USE_AS_STRNLEN
> - subq $(VEC_SIZE * 4), %rsi
> - jbe L(last_4x_vec_or_less)
> + /* Use ecx which was computed earlier to compute correct value.
> + */
> + leal -(CHAR_PER_VEC + 1)(%rcx, %rax), %eax
> +# else
> + subl %edx, %edi
> +# ifdef USE_AS_WCSLEN
> + /* NB: Divide bytes by 4 to get the wchar_t count. */
> + sarl $2, %edi
> +# endif
> + leal (CHAR_PER_VEC * 4)(%rdi, %rax), %eax
> # endif
> + ret
>
> -L(more_4x_vec):
> + .p2align 5
Why 5, not 4.
> +L(aligned_more):
> + movq %rdi, %rdx
> + /* Align data to VEC_SIZE. */
> + andq $-(VEC_SIZE), %rdi
> +L(cross_page_continue):
> /* Check the first 4 * VEC_SIZE. Only one VEC_SIZE at a time
> since data is only aligned to VEC_SIZE. */
> - VPCMP $0, (%rdi), %YMMZERO, %k0
> - kmovd %k0, %eax
> - testl %eax, %eax
> - jnz L(first_vec_x0)
> -
> +# ifdef USE_AS_STRNLEN
> + /* + CHAR_SIZE because it simplies the logic in
> + last_4x_vec_or_less. */
> + leaq (VEC_SIZE * 5 + CHAR_SIZE)(%rdi), %rcx
> + subq %rdx, %rcx
> +# ifdef USE_AS_WCSLEN
> + /* NB: Divide bytes by 4 to get the wchar_t count. */
> + sarl $2, %ecx
> +# endif
> +# endif
> + /* Load first VEC regardless. */
> VPCMP $0, VEC_SIZE(%rdi), %YMMZERO, %k0
> +# ifdef USE_AS_STRNLEN
> + /* Adjust length. If near end handle specially. */
> + subq %rcx, %rsi
> + jb L(last_4x_vec_or_less)
> +# endif
> kmovd %k0, %eax
> testl %eax, %eax
> jnz L(first_vec_x1)
>
> VPCMP $0, (VEC_SIZE * 2)(%rdi), %YMMZERO, %k0
> kmovd %k0, %eax
> - testl %eax, %eax
> + test %eax, %eax
> jnz L(first_vec_x2)
>
> VPCMP $0, (VEC_SIZE * 3)(%rdi), %YMMZERO, %k0
> @@ -179,258 +221,276 @@ L(more_4x_vec):
> testl %eax, %eax
> jnz L(first_vec_x3)
>
> - addq $(VEC_SIZE * 4), %rdi
> -
> -# ifdef USE_AS_STRNLEN
> - subq $(VEC_SIZE * 4), %rsi
> - jbe L(last_4x_vec_or_less)
> -# endif
> -
> - /* Align data to 4 * VEC_SIZE. */
> - movq %rdi, %rcx
> - andl $(4 * VEC_SIZE - 1), %ecx
> - andq $-(4 * VEC_SIZE), %rdi
> + VPCMP $0, (VEC_SIZE * 4)(%rdi), %YMMZERO, %k0
> + kmovd %k0, %eax
> + testl %eax, %eax
> + jnz L(first_vec_x4)
>
> + addq $VEC_SIZE, %rdi
> # ifdef USE_AS_STRNLEN
> - /* Adjust length. */
> + /* Check if at last VEC_SIZE * 4 length. */
> + cmpq $(CHAR_PER_VEC * 4 - 1), %rsi
> + jbe L(last_4x_vec_or_less_load)
> + movl %edi, %ecx
> + andl $(VEC_SIZE * 4 - 1), %ecx
> +# ifdef USE_AS_WCSLEN
> + /* NB: Divide bytes by 4 to get the wchar_t count. */
> + sarl $2, %ecx
> +# endif
> + /* Readjust length. */
> addq %rcx, %rsi
> # endif
> + /* Align data to VEC_SIZE * 4. */
> + andq $-(VEC_SIZE * 4), %rdi
>
> + /* Compare 4 * VEC at a time forward. */
> .p2align 4
> L(loop_4x_vec):
> - /* Compare 4 * VEC at a time forward. */
> - VMOVA (%rdi), %YMM1
> - VMOVA VEC_SIZE(%rdi), %YMM2
> - VMOVA (VEC_SIZE * 2)(%rdi), %YMM3
> - VMOVA (VEC_SIZE * 3)(%rdi), %YMM4
> -
> - VPMINU %YMM1, %YMM2, %YMM5
> - VPMINU %YMM3, %YMM4, %YMM6
> + /* Load first VEC regardless. */
> + VMOVA (VEC_SIZE * 4)(%rdi), %YMM1
> +# ifdef USE_AS_STRNLEN
> + /* Break if at end of length. */
> + subq $(CHAR_PER_VEC * 4), %rsi
> + jb L(last_4x_vec_or_less_cmpeq)
> +# endif
> + /* Save some code size by microfusing VPMINU with the load. Since
> + the matches in ymm2/ymm4 can only be returned if there where no
> + matches in ymm1/ymm3 respectively there is no issue with overlap.
> + */
> + VPMINU (VEC_SIZE * 5)(%rdi), %YMM1, %YMM2
> + VMOVA (VEC_SIZE * 6)(%rdi), %YMM3
> + VPMINU (VEC_SIZE * 7)(%rdi), %YMM3, %YMM4
> +
> + VPCMP $0, %YMM2, %YMMZERO, %k0
> + VPCMP $0, %YMM4, %YMMZERO, %k1
> + subq $-(VEC_SIZE * 4), %rdi
> + kortestd %k0, %k1
> + jz L(loop_4x_vec)
> +
> + /* Check if end was in first half. */
> + kmovd %k0, %eax
> + subq %rdx, %rdi
> +# ifdef USE_AS_WCSLEN
> + shrq $2, %rdi
> +# endif
> + testl %eax, %eax
> + jz L(second_vec_return)
>
> - VPMINU %YMM5, %YMM6, %YMM5
> - VPCMP $0, %YMM5, %YMMZERO, %k0
> - ktestd %k0, %k0
> - jnz L(4x_vec_end)
> + VPCMP $0, %YMM1, %YMMZERO, %k2
> + kmovd %k2, %edx
> + /* Combine VEC1 matches (edx) with VEC2 matches (eax). */
> +# ifdef USE_AS_WCSLEN
> + sall $CHAR_PER_VEC, %eax
> + orl %edx, %eax
> + tzcntl %eax, %eax
> +# else
> + salq $CHAR_PER_VEC, %rax
> + orq %rdx, %rax
> + tzcntq %rax, %rax
> +# endif
> + addq %rdi, %rax
> + ret
>
> - addq $(VEC_SIZE * 4), %rdi
>
> -# ifndef USE_AS_STRNLEN
> - jmp L(loop_4x_vec)
> -# else
> - subq $(VEC_SIZE * 4), %rsi
> - ja L(loop_4x_vec)
> +# ifdef USE_AS_STRNLEN
>
> +L(last_4x_vec_or_less_load):
> + /* Depending on entry adjust rdi / prepare first VEC in YMM1. */
> + VMOVA (VEC_SIZE * 4)(%rdi), %YMM1
> +L(last_4x_vec_or_less_cmpeq):
> + VPCMP $0, %YMM1, %YMMZERO, %k0
> + addq $(VEC_SIZE * 3), %rdi
> L(last_4x_vec_or_less):
> - /* Less than 4 * VEC and aligned to VEC_SIZE. */
> - addl $(VEC_SIZE * 2), %esi
> - jle L(last_2x_vec)
> -
> - VPCMP $0, (%rdi), %YMMZERO, %k0
> kmovd %k0, %eax
> + /* If remaining length > VEC_SIZE * 2. This works if esi is off by
> + VEC_SIZE * 4. */
> + testl $(CHAR_PER_VEC * 2), %esi
> + jnz L(last_4x_vec)
> +
> + /* length may have been negative or positive by an offset of
> + CHAR_PER_VEC * 4 depending on where this was called from. This
> + fixes that. */
> + andl $(CHAR_PER_VEC * 4 - 1), %esi
> testl %eax, %eax
> - jnz L(first_vec_x0)
> + jnz L(last_vec_x1_check)
>
> - VPCMP $0, VEC_SIZE(%rdi), %YMMZERO, %k0
> - kmovd %k0, %eax
> - testl %eax, %eax
> - jnz L(first_vec_x1)
> + /* Check the end of data. */
> + subl $CHAR_PER_VEC, %esi
> + jb L(max)
>
> VPCMP $0, (VEC_SIZE * 2)(%rdi), %YMMZERO, %k0
> kmovd %k0, %eax
> - testl %eax, %eax
> - jnz L(first_vec_x2_check)
> - subl $VEC_SIZE, %esi
> - jle L(max)
> + tzcntl %eax, %eax
> + /* Check the end of data. */
> + cmpl %eax, %esi
> + jb L(max)
>
> - VPCMP $0, (VEC_SIZE * 3)(%rdi), %YMMZERO, %k0
> - kmovd %k0, %eax
> - testl %eax, %eax
> - jnz L(first_vec_x3_check)
> + subq %rdx, %rdi
> +# ifdef USE_AS_WCSLEN
> + /* NB: Divide bytes by 4 to get the wchar_t count. */
> + sarq $2, %rdi
> +# endif
> + leaq (CHAR_PER_VEC * 2)(%rdi, %rax), %rax
> + ret
> +L(max):
> movq %r8, %rax
> + ret
> +# endif
> +
> + /* Placed here in strnlen so that the jcc L(last_4x_vec_or_less)
> + in the 4x VEC loop can use 2 byte encoding. */
> + .p2align 4
> +L(second_vec_return):
> + VPCMP $0, %YMM3, %YMMZERO, %k0
> + /* Combine YMM3 matches (k0) with YMM4 matches (k1). */
> +# ifdef USE_AS_WCSLEN
> + kunpckbw %k0, %k1, %k0
> + kmovd %k0, %eax
> + tzcntl %eax, %eax
> +# else
> + kunpckdq %k0, %k1, %k0
> + kmovq %k0, %rax
> + tzcntq %rax, %rax
> +# endif
> + leaq (CHAR_PER_VEC * 2)(%rdi, %rax), %rax
> + ret
> +
> +
> +# ifdef USE_AS_STRNLEN
> +L(last_vec_x1_check):
> + tzcntl %eax, %eax
> + /* Check the end of data. */
> + cmpl %eax, %esi
> + jb L(max)
> + subq %rdx, %rdi
> # ifdef USE_AS_WCSLEN
> - shrq $2, %rax
> + /* NB: Divide bytes by 4 to get the wchar_t count. */
> + sarq $2, %rdi
> # endif
> + leaq (CHAR_PER_VEC)(%rdi, %rax), %rax
> ret
>
> .p2align 4
> -L(last_2x_vec):
> - addl $(VEC_SIZE * 2), %esi
> +L(last_4x_vec):
> + /* Test first 2x VEC normally. */
> + testl %eax, %eax
> + jnz L(last_vec_x1)
>
> - VPCMP $0, (%rdi), %YMMZERO, %k0
> + VPCMP $0, (VEC_SIZE * 2)(%rdi), %YMMZERO, %k0
> kmovd %k0, %eax
> testl %eax, %eax
> - jnz L(first_vec_x0_check)
> - subl $VEC_SIZE, %esi
> - jle L(max)
> + jnz L(last_vec_x2)
>
> - VPCMP $0, VEC_SIZE(%rdi), %YMMZERO, %k0
> + /* Normalize length. */
> + andl $(CHAR_PER_VEC * 4 - 1), %esi
> + VPCMP $0, (VEC_SIZE * 3)(%rdi), %YMMZERO, %k0
> kmovd %k0, %eax
> testl %eax, %eax
> - jnz L(first_vec_x1_check)
> - movq %r8, %rax
> -# ifdef USE_AS_WCSLEN
> - shrq $2, %rax
> -# endif
> - ret
> + jnz L(last_vec_x3)
>
> - .p2align 4
> -L(first_vec_x0_check):
> + /* Check the end of data. */
> + subl $(CHAR_PER_VEC * 3), %esi
> + jb L(max)
> +
> + VPCMP $0, (VEC_SIZE * 4)(%rdi), %YMMZERO, %k0
> + kmovd %k0, %eax
> tzcntl %eax, %eax
> -# ifdef USE_AS_WCSLEN
> - /* NB: Multiply wchar_t count by 4 to get the number of bytes. */
> - sall $2, %eax
> -# endif
> /* Check the end of data. */
> - cmpq %rax, %rsi
> - jbe L(max)
> - addq %rdi, %rax
> - subq %rdx, %rax
> + cmpl %eax, %esi
> + jb L(max_end)
> +
> + subq %rdx, %rdi
> # ifdef USE_AS_WCSLEN
> - shrq $2, %rax
> + /* NB: Divide bytes by 4 to get the wchar_t count. */
> + sarq $2, %rdi
> # endif
> + leaq (CHAR_PER_VEC * 4)(%rdi, %rax), %rax
> ret
>
> .p2align 4
> -L(first_vec_x1_check):
> +L(last_vec_x1):
> tzcntl %eax, %eax
> + subq %rdx, %rdi
> # ifdef USE_AS_WCSLEN
> - /* NB: Multiply wchar_t count by 4 to get the number of bytes. */
> - sall $2, %eax
> -# endif
> - /* Check the end of data. */
> - cmpq %rax, %rsi
> - jbe L(max)
> - addq $VEC_SIZE, %rax
> - addq %rdi, %rax
> - subq %rdx, %rax
> -# ifdef USE_AS_WCSLEN
> - shrq $2, %rax
> + /* NB: Divide bytes by 4 to get the wchar_t count. */
> + sarq $2, %rdi
> # endif
> + leaq (CHAR_PER_VEC)(%rdi, %rax), %rax
> ret
>
> .p2align 4
> -L(first_vec_x2_check):
> +L(last_vec_x2):
> tzcntl %eax, %eax
> + subq %rdx, %rdi
> # ifdef USE_AS_WCSLEN
> - /* NB: Multiply wchar_t count by 4 to get the number of bytes. */
> - sall $2, %eax
> -# endif
> - /* Check the end of data. */
> - cmpq %rax, %rsi
> - jbe L(max)
> - addq $(VEC_SIZE * 2), %rax
> - addq %rdi, %rax
> - subq %rdx, %rax
> -# ifdef USE_AS_WCSLEN
> - shrq $2, %rax
> + /* NB: Divide bytes by 4 to get the wchar_t count. */
> + sarq $2, %rdi
> # endif
> + leaq (CHAR_PER_VEC * 2)(%rdi, %rax), %rax
> ret
>
> .p2align 4
> -L(first_vec_x3_check):
> +L(last_vec_x3):
> tzcntl %eax, %eax
> -# ifdef USE_AS_WCSLEN
> - /* NB: Multiply wchar_t count by 4 to get the number of bytes. */
> - sall $2, %eax
> -# endif
> + subl $(CHAR_PER_VEC * 2), %esi
> /* Check the end of data. */
> - cmpq %rax, %rsi
> - jbe L(max)
> - addq $(VEC_SIZE * 3), %rax
> - addq %rdi, %rax
> - subq %rdx, %rax
> + cmpl %eax, %esi
> + jb L(max_end)
> + subq %rdx, %rdi
> # ifdef USE_AS_WCSLEN
> - shrq $2, %rax
> + /* NB: Divide bytes by 4 to get the wchar_t count. */
> + sarq $2, %rdi
> # endif
> + leaq (CHAR_PER_VEC * 3)(%rdi, %rax), %rax
> ret
> -
> - .p2align 4
> -L(max):
> +L(max_end):
> movq %r8, %rax
> -# ifdef USE_AS_WCSLEN
> - shrq $2, %rax
> -# endif
> - ret
> -
> - .p2align 4
> -L(zero):
> - xorl %eax, %eax
> ret
> # endif
>
> + /* Cold case for crossing page with first load. */
> .p2align 4
> -L(first_vec_x0):
> - tzcntl %eax, %eax
> -# ifdef USE_AS_WCSLEN
> - /* NB: Multiply wchar_t count by 4 to get the number of bytes. */
> - sall $2, %eax
> -# endif
> - addq %rdi, %rax
> - subq %rdx, %rax
> +L(cross_page_boundary):
> + movq %rdi, %rdx
> + /* Align data to VEC_SIZE. */
> + andq $-VEC_SIZE, %rdi
> + VPCMP $0, (%rdi), %YMMZERO, %k0
> + kmovd %k0, %eax
> + /* Remove the leading bytes. */
> # ifdef USE_AS_WCSLEN
> - shrq $2, %rax
> + /* NB: Divide shift count by 4 since each bit in K0 represent 4
> + bytes. */
> + movl %edx, %ecx
> + shrl $2, %ecx
> + andl $(CHAR_PER_VEC - 1), %ecx
> # endif
> - ret
> -
> - .p2align 4
> -L(first_vec_x1):
> + /* SHIFT_REG is ecx for USE_AS_WCSLEN and edx otherwise. */
> + sarxl %SHIFT_REG, %eax, %eax
> + testl %eax, %eax
> +# ifndef USE_AS_STRNLEN
> + jz L(cross_page_continue)
> tzcntl %eax, %eax
> -# ifdef USE_AS_WCSLEN
> - /* NB: Multiply wchar_t count by 4 to get the number of bytes. */
> - sall $2, %eax
> -# endif
> - addq $VEC_SIZE, %rax
> - addq %rdi, %rax
> - subq %rdx, %rax
> -# ifdef USE_AS_WCSLEN
> - shrq $2, %rax
> -# endif
> ret
> -
> - .p2align 4
> -L(first_vec_x2):
> - tzcntl %eax, %eax
> -# ifdef USE_AS_WCSLEN
> - /* NB: Multiply wchar_t count by 4 to get the number of bytes. */
> - sall $2, %eax
> -# endif
> - addq $(VEC_SIZE * 2), %rax
> - addq %rdi, %rax
> - subq %rdx, %rax
> -# ifdef USE_AS_WCSLEN
> - shrq $2, %rax
> -# endif
> +# else
> + jnz L(cross_page_less_vec)
> +# ifndef USE_AS_WCSLEN
> + movl %edx, %ecx
> + andl $(CHAR_PER_VEC - 1), %ecx
> +# endif
> + movl $CHAR_PER_VEC, %eax
> + subl %ecx, %eax
> + /* Check the end of data. */
> + cmpq %rax, %rsi
> + ja L(cross_page_continue)
> + movl %esi, %eax
> ret
> -
> - .p2align 4
> -L(4x_vec_end):
> - VPCMP $0, %YMM1, %YMMZERO, %k0
> - kmovd %k0, %eax
> - testl %eax, %eax
> - jnz L(first_vec_x0)
> - VPCMP $0, %YMM2, %YMMZERO, %k1
> - kmovd %k1, %eax
> - testl %eax, %eax
> - jnz L(first_vec_x1)
> - VPCMP $0, %YMM3, %YMMZERO, %k2
> - kmovd %k2, %eax
> - testl %eax, %eax
> - jnz L(first_vec_x2)
> - VPCMP $0, %YMM4, %YMMZERO, %k3
> - kmovd %k3, %eax
> -L(first_vec_x3):
> +L(cross_page_less_vec):
> tzcntl %eax, %eax
> -# ifdef USE_AS_WCSLEN
> - /* NB: Multiply wchar_t count by 4 to get the number of bytes. */
> - sall $2, %eax
> -# endif
> - addq $(VEC_SIZE * 3), %rax
> - addq %rdi, %rax
> - subq %rdx, %rax
> -# ifdef USE_AS_WCSLEN
> - shrq $2, %rax
> -# endif
> + /* Select min of length and position of first null. */
> + cmpq %rax, %rsi
> + cmovb %esi, %eax
> ret
> +# endif
>
> END (STRLEN)
> #endif
> --
> 2.29.2
>
--
H.J.
On Mon, Apr 19, 2021 at 9:34 AM H.J. Lu <hjl.tools@gmail.com> wrote:
>
> On Sat, Apr 17, 2021 at 3:03 PM Noah Goldstein <goldstein.w.n@gmail.com> wrote:
> >
> > No bug. This commit optimizes strlen-evex.S. The
> > optimizations are mostly small things but they add up to roughly
> > 10-30% performance improvement for strlen. The results for strnlen are
> > bit more ambiguous. test-strlen, test-strnlen, test-wcslen, and
> > test-wcsnlen are all passing.
> >
> > Signed-off-by: Noah Goldstein <goldstein.w.n@gmail.com>
> > ---
> > sysdeps/x86_64/multiarch/strlen-evex.S | 588 ++++++++++++++-----------
> > 1 file changed, 324 insertions(+), 264 deletions(-)
> >
> > diff --git a/sysdeps/x86_64/multiarch/strlen-evex.S b/sysdeps/x86_64/multiarch/strlen-evex.S
> > index 0583819078..c1c88d84e5 100644
> > --- a/sysdeps/x86_64/multiarch/strlen-evex.S
> > +++ b/sysdeps/x86_64/multiarch/strlen-evex.S
> > @@ -29,11 +29,13 @@
> > # ifdef USE_AS_WCSLEN
> > # define VPCMP vpcmpd
> > # define VPMINU vpminud
> > -# define SHIFT_REG r9d
> > +# define SHIFT_REG ecx
> > +# define CHAR_SIZE 4
> > # else
> > # define VPCMP vpcmpb
> > # define VPMINU vpminub
> > -# define SHIFT_REG ecx
> > +# define SHIFT_REG edx
> > +# define CHAR_SIZE 1
> > # endif
> >
> > # define XMMZERO xmm16
> > @@ -46,132 +48,172 @@
> > # define YMM6 ymm22
> >
> > # define VEC_SIZE 32
> > +# define PAGE_SIZE 4096
> > +# define LOG_PAGE_SIZE 12
> > +# define CHAR_PER_VEC (VEC_SIZE / CHAR_SIZE)
> >
> > .section .text.evex,"ax",@progbits
> > ENTRY (STRLEN)
> > # ifdef USE_AS_STRNLEN
> > - /* Check for zero length. */
> > + /* Check zero length. */
> > test %RSI_LP, %RSI_LP
> > jz L(zero)
> > -# ifdef USE_AS_WCSLEN
> > - shl $2, %RSI_LP
> > -# elif defined __ILP32__
> > +# ifdef __ILP32__
> > /* Clear the upper 32 bits. */
> > +# ifdef USE_AS_WCSLEN
> > + andl $((1 << (32 - 4)) - 1), %esi
>
> Remove this.
Done. Note that removing this will make it so that in wcsnlen on x32
length = [2^28, 2^32) will have different behavior than
before / than wcsnlen-avx2. (Before the shift would set length to 0).
>
> > +# else
> > movl %esi, %esi
>
> This clears the upper 32 bits.
>
> > +# endif
> > # endif
> > mov %RSI_LP, %R8_LP
> > # endif
> > - movl %edi, %ecx
> > - movq %rdi, %rdx
> > + movl %edi, %eax
> > vpxorq %XMMZERO, %XMMZERO, %XMMZERO
> > -
> > + /* Shift left eax to clear all bits not relevant to page cross
> > + check. This saves 2 bytes of code as opposed to using andl with
> > + PAGE_SIZE - 1. Then compare with PAGE_SIZE - VEC_SIZE shifted
> > + left by the same amount (an imm32 either way). */
> > + sall $(32 - LOG_PAGE_SIZE), %eax
> > /* Check if we may cross page boundary with one vector load. */
> > - andl $(2 * VEC_SIZE - 1), %ecx
> > - cmpl $VEC_SIZE, %ecx
> > - ja L(cros_page_boundary)
> > + cmpl $((PAGE_SIZE - VEC_SIZE) << (32 - LOG_PAGE_SIZE)), %eax
> > + ja L(cross_page_boundary)
> >
> > /* Check the first VEC_SIZE bytes. Each bit in K0 represents a
> > null byte. */
> > VPCMP $0, (%rdi), %YMMZERO, %k0
> > kmovd %k0, %eax
> > - testl %eax, %eax
> > -
> > # ifdef USE_AS_STRNLEN
> > - jnz L(first_vec_x0_check)
> > - /* Adjust length and check the end of data. */
> > - subq $VEC_SIZE, %rsi
> > - jbe L(max)
> > -# else
> > - jnz L(first_vec_x0)
> > + /* If length < CHAR_PER_VEC handle special. */
> > + cmpq $CHAR_PER_VEC, %rsi
> > + jbe L(first_vec_x0)
> > # endif
> > -
> > - /* Align data for aligned loads in the loop. */
> > - addq $VEC_SIZE, %rdi
> > - andl $(VEC_SIZE - 1), %ecx
> > - andq $-VEC_SIZE, %rdi
> > -
> > + testl %eax, %eax
> > + jz L(aligned_more)
> > + tzcntl %eax, %eax
> > + ret
> > # ifdef USE_AS_STRNLEN
> > - /* Adjust length. */
> > - addq %rcx, %rsi
>
> Add .p2align 4 here.
Unnecessary with current patch. The target never crosses a 16 byte
block so is in the same FE decode block. Adding 16 byte align adds 16
bytes to overall code size. In the case that the code changes and the
zero case does cross a 16 byte boundary it will be 1 extra uop for the
zero length case but not much else (and only the extra uop if its
cold, i.e zero length in a loop with have no extra delay). Generally
don't think the a cold call to the zero case needs that extra
optimization so saving 16 bytes everywhere else wins out.
>
> > +L(zero):
> > + xorl %eax, %eax
> > + ret
> >
> > - subq $(VEC_SIZE * 4), %rsi
> > - jbe L(last_4x_vec_or_less)
> > + .p2align 4
> > +L(first_vec_x0):
> > + /* Set bit for max len so that tzcnt will return min of max len
> > + and position of first match. */
> > + btsq %rsi, %rax
> > + tzcntl %eax, %eax
> > + ret
> > # endif
> > - jmp L(more_4x_vec)
> >
> > .p2align 4
> > -L(cros_page_boundary):
> > - andl $(VEC_SIZE - 1), %ecx
> > - andq $-VEC_SIZE, %rdi
> > -
> > -# ifdef USE_AS_WCSLEN
> > - /* NB: Divide shift count by 4 since each bit in K0 represent 4
> > - bytes. */
> > - movl %ecx, %SHIFT_REG
> > - sarl $2, %SHIFT_REG
> > +L(first_vec_x1):
> > + tzcntl %eax, %eax
> > + /* Safe to use 32 bit instructions as these are only called for
> > + size = [1, 159]. */
> > +# ifdef USE_AS_STRNLEN
> > + /* Use ecx which was computed earlier to compute correct value.
> > + */
>
> Please align '*'.
Done. Same for avx2.
>
> > + leal -(CHAR_PER_VEC * 4 + 1)(%rcx, %rax), %eax
> > +# else
> > + subl %edx, %edi
> > +# ifdef USE_AS_WCSLEN
> > + /* NB: Divide bytes by 4 to get the wchar_t count. */
> > + sarl $2, %edi
> > +# endif
> > + leal CHAR_PER_VEC(%rdi, %rax), %eax
> > # endif
> > - VPCMP $0, (%rdi), %YMMZERO, %k0
> > - kmovd %k0, %eax
> > + ret
> >
> > - /* Remove the leading bytes. */
> > - sarxl %SHIFT_REG, %eax, %eax
> > - testl %eax, %eax
> > - jz L(aligned_more)
> > + .p2align 4
> > +L(first_vec_x2):
> > tzcntl %eax, %eax
> > -# ifdef USE_AS_WCSLEN
> > - /* NB: Multiply wchar_t count by 4 to get the number of bytes. */
> > - sall $2, %eax
> > -# endif
> > + /* Safe to use 32 bit instructions as these are only called for
> > + size = [1, 159]. */
> > # ifdef USE_AS_STRNLEN
> > - /* Check the end of data. */
> > - cmpq %rax, %rsi
> > - jbe L(max)
> > -# endif
> > - addq %rdi, %rax
> > - addq %rcx, %rax
> > - subq %rdx, %rax
> > -# ifdef USE_AS_WCSLEN
> > - shrq $2, %rax
> > + /* Use ecx which was computed earlier to compute correct value.
> > + */
> > + leal -(CHAR_PER_VEC * 3 + 1)(%rcx, %rax), %eax
> > +# else
> > + subl %edx, %edi
> > +# ifdef USE_AS_WCSLEN
> > + /* NB: Divide bytes by 4 to get the wchar_t count. */
> > + sarl $2, %edi
> > +# endif
> > + leal (CHAR_PER_VEC * 2)(%rdi, %rax), %eax
> > # endif
> > ret
> >
> > .p2align 4
> > -L(aligned_more):
> > +L(first_vec_x3):
> > + tzcntl %eax, %eax
> > + /* Safe to use 32 bit instructions as these are only called for
> > + size = [1, 159]. */
> > # ifdef USE_AS_STRNLEN
> > - /* "rcx" is less than VEC_SIZE. Calculate "rdx + rcx - VEC_SIZE"
> > - with "rdx - (VEC_SIZE - rcx)" instead of "(rdx + rcx) - VEC_SIZE"
> > - to void possible addition overflow. */
> > - negq %rcx
> > - addq $VEC_SIZE, %rcx
> > -
> > - /* Check the end of data. */
> > - subq %rcx, %rsi
> > - jbe L(max)
> > + /* Use ecx which was computed earlier to compute correct value.
> > + */
> > + leal -(CHAR_PER_VEC * 2 + 1)(%rcx, %rax), %eax
> > +# else
> > + subl %edx, %edi
> > +# ifdef USE_AS_WCSLEN
> > + /* NB: Divide bytes by 4 to get the wchar_t count. */
> > + sarl $2, %edi
> > +# endif
> > + leal (CHAR_PER_VEC * 3)(%rdi, %rax), %eax
> > # endif
> > + ret
> >
> > - addq $VEC_SIZE, %rdi
> > -
> > + .p2align 4
> > +L(first_vec_x4):
> > + tzcntl %eax, %eax
> > + /* Safe to use 32 bit instructions as these are only called for
> > + size = [1, 159]. */
> > # ifdef USE_AS_STRNLEN
> > - subq $(VEC_SIZE * 4), %rsi
> > - jbe L(last_4x_vec_or_less)
> > + /* Use ecx which was computed earlier to compute correct value.
> > + */
> > + leal -(CHAR_PER_VEC + 1)(%rcx, %rax), %eax
> > +# else
> > + subl %edx, %edi
> > +# ifdef USE_AS_WCSLEN
> > + /* NB: Divide bytes by 4 to get the wchar_t count. */
> > + sarl $2, %edi
> > +# endif
> > + leal (CHAR_PER_VEC * 4)(%rdi, %rax), %eax
> > # endif
> > + ret
> >
> > -L(more_4x_vec):
> > + .p2align 5
>
> Why 5, not 4.
ENTRY() aligns to 16. In tests on some CPUs (particularly Skylake) was
seeing high variance depending on how entry with aligned % 32. This
fixed that and has no negative impact on the CPUs that didn't see the
high variance. I think it also makes sense as this block feeds into
the 4x loop and the LSD / Uop Cache both care about 32 byte alignment
rather than 16 byte alignment. Aligning to 32 here allows for more
control over the 4x loop in relation to the LSD / Uop Cache without
having to .p2align 5 the loop entry and potentially wasting an entire
extra decode block on nops.
>
> > +L(aligned_more):
> > + movq %rdi, %rdx
> > + /* Align data to VEC_SIZE. */
> > + andq $-(VEC_SIZE), %rdi
> > +L(cross_page_continue):
> > /* Check the first 4 * VEC_SIZE. Only one VEC_SIZE at a time
> > since data is only aligned to VEC_SIZE. */
> > - VPCMP $0, (%rdi), %YMMZERO, %k0
> > - kmovd %k0, %eax
> > - testl %eax, %eax
> > - jnz L(first_vec_x0)
> > -
> > +# ifdef USE_AS_STRNLEN
> > + /* + CHAR_SIZE because it simplies the logic in
> > + last_4x_vec_or_less. */
> > + leaq (VEC_SIZE * 5 + CHAR_SIZE)(%rdi), %rcx
> > + subq %rdx, %rcx
> > +# ifdef USE_AS_WCSLEN
> > + /* NB: Divide bytes by 4 to get the wchar_t count. */
> > + sarl $2, %ecx
> > +# endif
> > +# endif
> > + /* Load first VEC regardless. */
> > VPCMP $0, VEC_SIZE(%rdi), %YMMZERO, %k0
> > +# ifdef USE_AS_STRNLEN
> > + /* Adjust length. If near end handle specially. */
> > + subq %rcx, %rsi
> > + jb L(last_4x_vec_or_less)
> > +# endif
> > kmovd %k0, %eax
> > testl %eax, %eax
> > jnz L(first_vec_x1)
> >
> > VPCMP $0, (VEC_SIZE * 2)(%rdi), %YMMZERO, %k0
> > kmovd %k0, %eax
> > - testl %eax, %eax
> > + test %eax, %eax
> > jnz L(first_vec_x2)
> >
> > VPCMP $0, (VEC_SIZE * 3)(%rdi), %YMMZERO, %k0
> > @@ -179,258 +221,276 @@ L(more_4x_vec):
> > testl %eax, %eax
> > jnz L(first_vec_x3)
> >
> > - addq $(VEC_SIZE * 4), %rdi
> > -
> > -# ifdef USE_AS_STRNLEN
> > - subq $(VEC_SIZE * 4), %rsi
> > - jbe L(last_4x_vec_or_less)
> > -# endif
> > -
> > - /* Align data to 4 * VEC_SIZE. */
> > - movq %rdi, %rcx
> > - andl $(4 * VEC_SIZE - 1), %ecx
> > - andq $-(4 * VEC_SIZE), %rdi
> > + VPCMP $0, (VEC_SIZE * 4)(%rdi), %YMMZERO, %k0
> > + kmovd %k0, %eax
> > + testl %eax, %eax
> > + jnz L(first_vec_x4)
> >
> > + addq $VEC_SIZE, %rdi
> > # ifdef USE_AS_STRNLEN
> > - /* Adjust length. */
> > + /* Check if at last VEC_SIZE * 4 length. */
> > + cmpq $(CHAR_PER_VEC * 4 - 1), %rsi
> > + jbe L(last_4x_vec_or_less_load)
> > + movl %edi, %ecx
> > + andl $(VEC_SIZE * 4 - 1), %ecx
> > +# ifdef USE_AS_WCSLEN
> > + /* NB: Divide bytes by 4 to get the wchar_t count. */
> > + sarl $2, %ecx
> > +# endif
> > + /* Readjust length. */
> > addq %rcx, %rsi
> > # endif
> > + /* Align data to VEC_SIZE * 4. */
> > + andq $-(VEC_SIZE * 4), %rdi
> >
> > + /* Compare 4 * VEC at a time forward. */
> > .p2align 4
> > L(loop_4x_vec):
> > - /* Compare 4 * VEC at a time forward. */
> > - VMOVA (%rdi), %YMM1
> > - VMOVA VEC_SIZE(%rdi), %YMM2
> > - VMOVA (VEC_SIZE * 2)(%rdi), %YMM3
> > - VMOVA (VEC_SIZE * 3)(%rdi), %YMM4
> > -
> > - VPMINU %YMM1, %YMM2, %YMM5
> > - VPMINU %YMM3, %YMM4, %YMM6
> > + /* Load first VEC regardless. */
> > + VMOVA (VEC_SIZE * 4)(%rdi), %YMM1
> > +# ifdef USE_AS_STRNLEN
> > + /* Break if at end of length. */
> > + subq $(CHAR_PER_VEC * 4), %rsi
> > + jb L(last_4x_vec_or_less_cmpeq)
> > +# endif
> > + /* Save some code size by microfusing VPMINU with the load. Since
> > + the matches in ymm2/ymm4 can only be returned if there where no
> > + matches in ymm1/ymm3 respectively there is no issue with overlap.
> > + */
> > + VPMINU (VEC_SIZE * 5)(%rdi), %YMM1, %YMM2
> > + VMOVA (VEC_SIZE * 6)(%rdi), %YMM3
> > + VPMINU (VEC_SIZE * 7)(%rdi), %YMM3, %YMM4
> > +
> > + VPCMP $0, %YMM2, %YMMZERO, %k0
> > + VPCMP $0, %YMM4, %YMMZERO, %k1
> > + subq $-(VEC_SIZE * 4), %rdi
> > + kortestd %k0, %k1
> > + jz L(loop_4x_vec)
> > +
> > + /* Check if end was in first half. */
> > + kmovd %k0, %eax
> > + subq %rdx, %rdi
> > +# ifdef USE_AS_WCSLEN
> > + shrq $2, %rdi
> > +# endif
> > + testl %eax, %eax
> > + jz L(second_vec_return)
> >
> > - VPMINU %YMM5, %YMM6, %YMM5
> > - VPCMP $0, %YMM5, %YMMZERO, %k0
> > - ktestd %k0, %k0
> > - jnz L(4x_vec_end)
> > + VPCMP $0, %YMM1, %YMMZERO, %k2
> > + kmovd %k2, %edx
> > + /* Combine VEC1 matches (edx) with VEC2 matches (eax). */
> > +# ifdef USE_AS_WCSLEN
> > + sall $CHAR_PER_VEC, %eax
> > + orl %edx, %eax
> > + tzcntl %eax, %eax
> > +# else
> > + salq $CHAR_PER_VEC, %rax
> > + orq %rdx, %rax
> > + tzcntq %rax, %rax
> > +# endif
> > + addq %rdi, %rax
> > + ret
> >
> > - addq $(VEC_SIZE * 4), %rdi
> >
> > -# ifndef USE_AS_STRNLEN
> > - jmp L(loop_4x_vec)
> > -# else
> > - subq $(VEC_SIZE * 4), %rsi
> > - ja L(loop_4x_vec)
> > +# ifdef USE_AS_STRNLEN
> >
> > +L(last_4x_vec_or_less_load):
> > + /* Depending on entry adjust rdi / prepare first VEC in YMM1. */
> > + VMOVA (VEC_SIZE * 4)(%rdi), %YMM1
> > +L(last_4x_vec_or_less_cmpeq):
> > + VPCMP $0, %YMM1, %YMMZERO, %k0
> > + addq $(VEC_SIZE * 3), %rdi
> > L(last_4x_vec_or_less):
> > - /* Less than 4 * VEC and aligned to VEC_SIZE. */
> > - addl $(VEC_SIZE * 2), %esi
> > - jle L(last_2x_vec)
> > -
> > - VPCMP $0, (%rdi), %YMMZERO, %k0
> > kmovd %k0, %eax
> > + /* If remaining length > VEC_SIZE * 2. This works if esi is off by
> > + VEC_SIZE * 4. */
> > + testl $(CHAR_PER_VEC * 2), %esi
> > + jnz L(last_4x_vec)
> > +
> > + /* length may have been negative or positive by an offset of
> > + CHAR_PER_VEC * 4 depending on where this was called from. This
> > + fixes that. */
> > + andl $(CHAR_PER_VEC * 4 - 1), %esi
> > testl %eax, %eax
> > - jnz L(first_vec_x0)
> > + jnz L(last_vec_x1_check)
> >
> > - VPCMP $0, VEC_SIZE(%rdi), %YMMZERO, %k0
> > - kmovd %k0, %eax
> > - testl %eax, %eax
> > - jnz L(first_vec_x1)
> > + /* Check the end of data. */
> > + subl $CHAR_PER_VEC, %esi
> > + jb L(max)
> >
> > VPCMP $0, (VEC_SIZE * 2)(%rdi), %YMMZERO, %k0
> > kmovd %k0, %eax
> > - testl %eax, %eax
> > - jnz L(first_vec_x2_check)
> > - subl $VEC_SIZE, %esi
> > - jle L(max)
> > + tzcntl %eax, %eax
> > + /* Check the end of data. */
> > + cmpl %eax, %esi
> > + jb L(max)
> >
> > - VPCMP $0, (VEC_SIZE * 3)(%rdi), %YMMZERO, %k0
> > - kmovd %k0, %eax
> > - testl %eax, %eax
> > - jnz L(first_vec_x3_check)
> > + subq %rdx, %rdi
> > +# ifdef USE_AS_WCSLEN
> > + /* NB: Divide bytes by 4 to get the wchar_t count. */
> > + sarq $2, %rdi
> > +# endif
> > + leaq (CHAR_PER_VEC * 2)(%rdi, %rax), %rax
> > + ret
> > +L(max):
> > movq %r8, %rax
> > + ret
> > +# endif
> > +
> > + /* Placed here in strnlen so that the jcc L(last_4x_vec_or_less)
> > + in the 4x VEC loop can use 2 byte encoding. */
> > + .p2align 4
> > +L(second_vec_return):
> > + VPCMP $0, %YMM3, %YMMZERO, %k0
> > + /* Combine YMM3 matches (k0) with YMM4 matches (k1). */
> > +# ifdef USE_AS_WCSLEN
> > + kunpckbw %k0, %k1, %k0
> > + kmovd %k0, %eax
> > + tzcntl %eax, %eax
> > +# else
> > + kunpckdq %k0, %k1, %k0
> > + kmovq %k0, %rax
> > + tzcntq %rax, %rax
> > +# endif
> > + leaq (CHAR_PER_VEC * 2)(%rdi, %rax), %rax
> > + ret
> > +
> > +
> > +# ifdef USE_AS_STRNLEN
> > +L(last_vec_x1_check):
> > + tzcntl %eax, %eax
> > + /* Check the end of data. */
> > + cmpl %eax, %esi
> > + jb L(max)
> > + subq %rdx, %rdi
> > # ifdef USE_AS_WCSLEN
> > - shrq $2, %rax
> > + /* NB: Divide bytes by 4 to get the wchar_t count. */
> > + sarq $2, %rdi
> > # endif
> > + leaq (CHAR_PER_VEC)(%rdi, %rax), %rax
> > ret
> >
> > .p2align 4
> > -L(last_2x_vec):
> > - addl $(VEC_SIZE * 2), %esi
> > +L(last_4x_vec):
> > + /* Test first 2x VEC normally. */
> > + testl %eax, %eax
> > + jnz L(last_vec_x1)
> >
> > - VPCMP $0, (%rdi), %YMMZERO, %k0
> > + VPCMP $0, (VEC_SIZE * 2)(%rdi), %YMMZERO, %k0
> > kmovd %k0, %eax
> > testl %eax, %eax
> > - jnz L(first_vec_x0_check)
> > - subl $VEC_SIZE, %esi
> > - jle L(max)
> > + jnz L(last_vec_x2)
> >
> > - VPCMP $0, VEC_SIZE(%rdi), %YMMZERO, %k0
> > + /* Normalize length. */
> > + andl $(CHAR_PER_VEC * 4 - 1), %esi
> > + VPCMP $0, (VEC_SIZE * 3)(%rdi), %YMMZERO, %k0
> > kmovd %k0, %eax
> > testl %eax, %eax
> > - jnz L(first_vec_x1_check)
> > - movq %r8, %rax
> > -# ifdef USE_AS_WCSLEN
> > - shrq $2, %rax
> > -# endif
> > - ret
> > + jnz L(last_vec_x3)
> >
> > - .p2align 4
> > -L(first_vec_x0_check):
> > + /* Check the end of data. */
> > + subl $(CHAR_PER_VEC * 3), %esi
> > + jb L(max)
> > +
> > + VPCMP $0, (VEC_SIZE * 4)(%rdi), %YMMZERO, %k0
> > + kmovd %k0, %eax
> > tzcntl %eax, %eax
> > -# ifdef USE_AS_WCSLEN
> > - /* NB: Multiply wchar_t count by 4 to get the number of bytes. */
> > - sall $2, %eax
> > -# endif
> > /* Check the end of data. */
> > - cmpq %rax, %rsi
> > - jbe L(max)
> > - addq %rdi, %rax
> > - subq %rdx, %rax
> > + cmpl %eax, %esi
> > + jb L(max_end)
> > +
> > + subq %rdx, %rdi
> > # ifdef USE_AS_WCSLEN
> > - shrq $2, %rax
> > + /* NB: Divide bytes by 4 to get the wchar_t count. */
> > + sarq $2, %rdi
> > # endif
> > + leaq (CHAR_PER_VEC * 4)(%rdi, %rax), %rax
> > ret
> >
> > .p2align 4
> > -L(first_vec_x1_check):
> > +L(last_vec_x1):
> > tzcntl %eax, %eax
> > + subq %rdx, %rdi
> > # ifdef USE_AS_WCSLEN
> > - /* NB: Multiply wchar_t count by 4 to get the number of bytes. */
> > - sall $2, %eax
> > -# endif
> > - /* Check the end of data. */
> > - cmpq %rax, %rsi
> > - jbe L(max)
> > - addq $VEC_SIZE, %rax
> > - addq %rdi, %rax
> > - subq %rdx, %rax
> > -# ifdef USE_AS_WCSLEN
> > - shrq $2, %rax
> > + /* NB: Divide bytes by 4 to get the wchar_t count. */
> > + sarq $2, %rdi
> > # endif
> > + leaq (CHAR_PER_VEC)(%rdi, %rax), %rax
> > ret
> >
> > .p2align 4
> > -L(first_vec_x2_check):
> > +L(last_vec_x2):
> > tzcntl %eax, %eax
> > + subq %rdx, %rdi
> > # ifdef USE_AS_WCSLEN
> > - /* NB: Multiply wchar_t count by 4 to get the number of bytes. */
> > - sall $2, %eax
> > -# endif
> > - /* Check the end of data. */
> > - cmpq %rax, %rsi
> > - jbe L(max)
> > - addq $(VEC_SIZE * 2), %rax
> > - addq %rdi, %rax
> > - subq %rdx, %rax
> > -# ifdef USE_AS_WCSLEN
> > - shrq $2, %rax
> > + /* NB: Divide bytes by 4 to get the wchar_t count. */
> > + sarq $2, %rdi
> > # endif
> > + leaq (CHAR_PER_VEC * 2)(%rdi, %rax), %rax
> > ret
> >
> > .p2align 4
> > -L(first_vec_x3_check):
> > +L(last_vec_x3):
> > tzcntl %eax, %eax
> > -# ifdef USE_AS_WCSLEN
> > - /* NB: Multiply wchar_t count by 4 to get the number of bytes. */
> > - sall $2, %eax
> > -# endif
> > + subl $(CHAR_PER_VEC * 2), %esi
> > /* Check the end of data. */
> > - cmpq %rax, %rsi
> > - jbe L(max)
> > - addq $(VEC_SIZE * 3), %rax
> > - addq %rdi, %rax
> > - subq %rdx, %rax
> > + cmpl %eax, %esi
> > + jb L(max_end)
> > + subq %rdx, %rdi
> > # ifdef USE_AS_WCSLEN
> > - shrq $2, %rax
> > + /* NB: Divide bytes by 4 to get the wchar_t count. */
> > + sarq $2, %rdi
> > # endif
> > + leaq (CHAR_PER_VEC * 3)(%rdi, %rax), %rax
> > ret
> > -
> > - .p2align 4
> > -L(max):
> > +L(max_end):
> > movq %r8, %rax
> > -# ifdef USE_AS_WCSLEN
> > - shrq $2, %rax
> > -# endif
> > - ret
> > -
> > - .p2align 4
> > -L(zero):
> > - xorl %eax, %eax
> > ret
> > # endif
> >
> > + /* Cold case for crossing page with first load. */
> > .p2align 4
> > -L(first_vec_x0):
> > - tzcntl %eax, %eax
> > -# ifdef USE_AS_WCSLEN
> > - /* NB: Multiply wchar_t count by 4 to get the number of bytes. */
> > - sall $2, %eax
> > -# endif
> > - addq %rdi, %rax
> > - subq %rdx, %rax
> > +L(cross_page_boundary):
> > + movq %rdi, %rdx
> > + /* Align data to VEC_SIZE. */
> > + andq $-VEC_SIZE, %rdi
> > + VPCMP $0, (%rdi), %YMMZERO, %k0
> > + kmovd %k0, %eax
> > + /* Remove the leading bytes. */
> > # ifdef USE_AS_WCSLEN
> > - shrq $2, %rax
> > + /* NB: Divide shift count by 4 since each bit in K0 represent 4
> > + bytes. */
> > + movl %edx, %ecx
> > + shrl $2, %ecx
> > + andl $(CHAR_PER_VEC - 1), %ecx
> > # endif
> > - ret
> > -
> > - .p2align 4
> > -L(first_vec_x1):
> > + /* SHIFT_REG is ecx for USE_AS_WCSLEN and edx otherwise. */
> > + sarxl %SHIFT_REG, %eax, %eax
> > + testl %eax, %eax
> > +# ifndef USE_AS_STRNLEN
> > + jz L(cross_page_continue)
> > tzcntl %eax, %eax
> > -# ifdef USE_AS_WCSLEN
> > - /* NB: Multiply wchar_t count by 4 to get the number of bytes. */
> > - sall $2, %eax
> > -# endif
> > - addq $VEC_SIZE, %rax
> > - addq %rdi, %rax
> > - subq %rdx, %rax
> > -# ifdef USE_AS_WCSLEN
> > - shrq $2, %rax
> > -# endif
> > ret
> > -
> > - .p2align 4
> > -L(first_vec_x2):
> > - tzcntl %eax, %eax
> > -# ifdef USE_AS_WCSLEN
> > - /* NB: Multiply wchar_t count by 4 to get the number of bytes. */
> > - sall $2, %eax
> > -# endif
> > - addq $(VEC_SIZE * 2), %rax
> > - addq %rdi, %rax
> > - subq %rdx, %rax
> > -# ifdef USE_AS_WCSLEN
> > - shrq $2, %rax
> > -# endif
> > +# else
> > + jnz L(cross_page_less_vec)
> > +# ifndef USE_AS_WCSLEN
> > + movl %edx, %ecx
> > + andl $(CHAR_PER_VEC - 1), %ecx
> > +# endif
> > + movl $CHAR_PER_VEC, %eax
> > + subl %ecx, %eax
> > + /* Check the end of data. */
> > + cmpq %rax, %rsi
> > + ja L(cross_page_continue)
> > + movl %esi, %eax
> > ret
> > -
> > - .p2align 4
> > -L(4x_vec_end):
> > - VPCMP $0, %YMM1, %YMMZERO, %k0
> > - kmovd %k0, %eax
> > - testl %eax, %eax
> > - jnz L(first_vec_x0)
> > - VPCMP $0, %YMM2, %YMMZERO, %k1
> > - kmovd %k1, %eax
> > - testl %eax, %eax
> > - jnz L(first_vec_x1)
> > - VPCMP $0, %YMM3, %YMMZERO, %k2
> > - kmovd %k2, %eax
> > - testl %eax, %eax
> > - jnz L(first_vec_x2)
> > - VPCMP $0, %YMM4, %YMMZERO, %k3
> > - kmovd %k3, %eax
> > -L(first_vec_x3):
> > +L(cross_page_less_vec):
> > tzcntl %eax, %eax
> > -# ifdef USE_AS_WCSLEN
> > - /* NB: Multiply wchar_t count by 4 to get the number of bytes. */
> > - sall $2, %eax
> > -# endif
> > - addq $(VEC_SIZE * 3), %rax
> > - addq %rdi, %rax
> > - subq %rdx, %rax
> > -# ifdef USE_AS_WCSLEN
> > - shrq $2, %rax
> > -# endif
> > + /* Select min of length and position of first null. */
> > + cmpq %rax, %rsi
> > + cmovb %esi, %eax
> > ret
> > +# endif
> >
> > END (STRLEN)
> > #endif
> > --
> > 2.29.2
> >
>
>
> --
> H.J.
@@ -29,11 +29,13 @@
# ifdef USE_AS_WCSLEN
# define VPCMP vpcmpd
# define VPMINU vpminud
-# define SHIFT_REG r9d
+# define SHIFT_REG ecx
+# define CHAR_SIZE 4
# else
# define VPCMP vpcmpb
# define VPMINU vpminub
-# define SHIFT_REG ecx
+# define SHIFT_REG edx
+# define CHAR_SIZE 1
# endif
# define XMMZERO xmm16
@@ -46,132 +48,172 @@
# define YMM6 ymm22
# define VEC_SIZE 32
+# define PAGE_SIZE 4096
+# define LOG_PAGE_SIZE 12
+# define CHAR_PER_VEC (VEC_SIZE / CHAR_SIZE)
.section .text.evex,"ax",@progbits
ENTRY (STRLEN)
# ifdef USE_AS_STRNLEN
- /* Check for zero length. */
+ /* Check zero length. */
test %RSI_LP, %RSI_LP
jz L(zero)
-# ifdef USE_AS_WCSLEN
- shl $2, %RSI_LP
-# elif defined __ILP32__
+# ifdef __ILP32__
/* Clear the upper 32 bits. */
+# ifdef USE_AS_WCSLEN
+ andl $((1 << (32 - 4)) - 1), %esi
+# else
movl %esi, %esi
+# endif
# endif
mov %RSI_LP, %R8_LP
# endif
- movl %edi, %ecx
- movq %rdi, %rdx
+ movl %edi, %eax
vpxorq %XMMZERO, %XMMZERO, %XMMZERO
-
+ /* Shift left eax to clear all bits not relevant to page cross
+ check. This saves 2 bytes of code as opposed to using andl with
+ PAGE_SIZE - 1. Then compare with PAGE_SIZE - VEC_SIZE shifted
+ left by the same amount (an imm32 either way). */
+ sall $(32 - LOG_PAGE_SIZE), %eax
/* Check if we may cross page boundary with one vector load. */
- andl $(2 * VEC_SIZE - 1), %ecx
- cmpl $VEC_SIZE, %ecx
- ja L(cros_page_boundary)
+ cmpl $((PAGE_SIZE - VEC_SIZE) << (32 - LOG_PAGE_SIZE)), %eax
+ ja L(cross_page_boundary)
/* Check the first VEC_SIZE bytes. Each bit in K0 represents a
null byte. */
VPCMP $0, (%rdi), %YMMZERO, %k0
kmovd %k0, %eax
- testl %eax, %eax
-
# ifdef USE_AS_STRNLEN
- jnz L(first_vec_x0_check)
- /* Adjust length and check the end of data. */
- subq $VEC_SIZE, %rsi
- jbe L(max)
-# else
- jnz L(first_vec_x0)
+ /* If length < CHAR_PER_VEC handle special. */
+ cmpq $CHAR_PER_VEC, %rsi
+ jbe L(first_vec_x0)
# endif
-
- /* Align data for aligned loads in the loop. */
- addq $VEC_SIZE, %rdi
- andl $(VEC_SIZE - 1), %ecx
- andq $-VEC_SIZE, %rdi
-
+ testl %eax, %eax
+ jz L(aligned_more)
+ tzcntl %eax, %eax
+ ret
# ifdef USE_AS_STRNLEN
- /* Adjust length. */
- addq %rcx, %rsi
+L(zero):
+ xorl %eax, %eax
+ ret
- subq $(VEC_SIZE * 4), %rsi
- jbe L(last_4x_vec_or_less)
+ .p2align 4
+L(first_vec_x0):
+ /* Set bit for max len so that tzcnt will return min of max len
+ and position of first match. */
+ btsq %rsi, %rax
+ tzcntl %eax, %eax
+ ret
# endif
- jmp L(more_4x_vec)
.p2align 4
-L(cros_page_boundary):
- andl $(VEC_SIZE - 1), %ecx
- andq $-VEC_SIZE, %rdi
-
-# ifdef USE_AS_WCSLEN
- /* NB: Divide shift count by 4 since each bit in K0 represent 4
- bytes. */
- movl %ecx, %SHIFT_REG
- sarl $2, %SHIFT_REG
+L(first_vec_x1):
+ tzcntl %eax, %eax
+ /* Safe to use 32 bit instructions as these are only called for
+ size = [1, 159]. */
+# ifdef USE_AS_STRNLEN
+ /* Use ecx which was computed earlier to compute correct value.
+ */
+ leal -(CHAR_PER_VEC * 4 + 1)(%rcx, %rax), %eax
+# else
+ subl %edx, %edi
+# ifdef USE_AS_WCSLEN
+ /* NB: Divide bytes by 4 to get the wchar_t count. */
+ sarl $2, %edi
+# endif
+ leal CHAR_PER_VEC(%rdi, %rax), %eax
# endif
- VPCMP $0, (%rdi), %YMMZERO, %k0
- kmovd %k0, %eax
+ ret
- /* Remove the leading bytes. */
- sarxl %SHIFT_REG, %eax, %eax
- testl %eax, %eax
- jz L(aligned_more)
+ .p2align 4
+L(first_vec_x2):
tzcntl %eax, %eax
-# ifdef USE_AS_WCSLEN
- /* NB: Multiply wchar_t count by 4 to get the number of bytes. */
- sall $2, %eax
-# endif
+ /* Safe to use 32 bit instructions as these are only called for
+ size = [1, 159]. */
# ifdef USE_AS_STRNLEN
- /* Check the end of data. */
- cmpq %rax, %rsi
- jbe L(max)
-# endif
- addq %rdi, %rax
- addq %rcx, %rax
- subq %rdx, %rax
-# ifdef USE_AS_WCSLEN
- shrq $2, %rax
+ /* Use ecx which was computed earlier to compute correct value.
+ */
+ leal -(CHAR_PER_VEC * 3 + 1)(%rcx, %rax), %eax
+# else
+ subl %edx, %edi
+# ifdef USE_AS_WCSLEN
+ /* NB: Divide bytes by 4 to get the wchar_t count. */
+ sarl $2, %edi
+# endif
+ leal (CHAR_PER_VEC * 2)(%rdi, %rax), %eax
# endif
ret
.p2align 4
-L(aligned_more):
+L(first_vec_x3):
+ tzcntl %eax, %eax
+ /* Safe to use 32 bit instructions as these are only called for
+ size = [1, 159]. */
# ifdef USE_AS_STRNLEN
- /* "rcx" is less than VEC_SIZE. Calculate "rdx + rcx - VEC_SIZE"
- with "rdx - (VEC_SIZE - rcx)" instead of "(rdx + rcx) - VEC_SIZE"
- to void possible addition overflow. */
- negq %rcx
- addq $VEC_SIZE, %rcx
-
- /* Check the end of data. */
- subq %rcx, %rsi
- jbe L(max)
+ /* Use ecx which was computed earlier to compute correct value.
+ */
+ leal -(CHAR_PER_VEC * 2 + 1)(%rcx, %rax), %eax
+# else
+ subl %edx, %edi
+# ifdef USE_AS_WCSLEN
+ /* NB: Divide bytes by 4 to get the wchar_t count. */
+ sarl $2, %edi
+# endif
+ leal (CHAR_PER_VEC * 3)(%rdi, %rax), %eax
# endif
+ ret
- addq $VEC_SIZE, %rdi
-
+ .p2align 4
+L(first_vec_x4):
+ tzcntl %eax, %eax
+ /* Safe to use 32 bit instructions as these are only called for
+ size = [1, 159]. */
# ifdef USE_AS_STRNLEN
- subq $(VEC_SIZE * 4), %rsi
- jbe L(last_4x_vec_or_less)
+ /* Use ecx which was computed earlier to compute correct value.
+ */
+ leal -(CHAR_PER_VEC + 1)(%rcx, %rax), %eax
+# else
+ subl %edx, %edi
+# ifdef USE_AS_WCSLEN
+ /* NB: Divide bytes by 4 to get the wchar_t count. */
+ sarl $2, %edi
+# endif
+ leal (CHAR_PER_VEC * 4)(%rdi, %rax), %eax
# endif
+ ret
-L(more_4x_vec):
+ .p2align 5
+L(aligned_more):
+ movq %rdi, %rdx
+ /* Align data to VEC_SIZE. */
+ andq $-(VEC_SIZE), %rdi
+L(cross_page_continue):
/* Check the first 4 * VEC_SIZE. Only one VEC_SIZE at a time
since data is only aligned to VEC_SIZE. */
- VPCMP $0, (%rdi), %YMMZERO, %k0
- kmovd %k0, %eax
- testl %eax, %eax
- jnz L(first_vec_x0)
-
+# ifdef USE_AS_STRNLEN
+ /* + CHAR_SIZE because it simplies the logic in
+ last_4x_vec_or_less. */
+ leaq (VEC_SIZE * 5 + CHAR_SIZE)(%rdi), %rcx
+ subq %rdx, %rcx
+# ifdef USE_AS_WCSLEN
+ /* NB: Divide bytes by 4 to get the wchar_t count. */
+ sarl $2, %ecx
+# endif
+# endif
+ /* Load first VEC regardless. */
VPCMP $0, VEC_SIZE(%rdi), %YMMZERO, %k0
+# ifdef USE_AS_STRNLEN
+ /* Adjust length. If near end handle specially. */
+ subq %rcx, %rsi
+ jb L(last_4x_vec_or_less)
+# endif
kmovd %k0, %eax
testl %eax, %eax
jnz L(first_vec_x1)
VPCMP $0, (VEC_SIZE * 2)(%rdi), %YMMZERO, %k0
kmovd %k0, %eax
- testl %eax, %eax
+ test %eax, %eax
jnz L(first_vec_x2)
VPCMP $0, (VEC_SIZE * 3)(%rdi), %YMMZERO, %k0
@@ -179,258 +221,276 @@ L(more_4x_vec):
testl %eax, %eax
jnz L(first_vec_x3)
- addq $(VEC_SIZE * 4), %rdi
-
-# ifdef USE_AS_STRNLEN
- subq $(VEC_SIZE * 4), %rsi
- jbe L(last_4x_vec_or_less)
-# endif
-
- /* Align data to 4 * VEC_SIZE. */
- movq %rdi, %rcx
- andl $(4 * VEC_SIZE - 1), %ecx
- andq $-(4 * VEC_SIZE), %rdi
+ VPCMP $0, (VEC_SIZE * 4)(%rdi), %YMMZERO, %k0
+ kmovd %k0, %eax
+ testl %eax, %eax
+ jnz L(first_vec_x4)
+ addq $VEC_SIZE, %rdi
# ifdef USE_AS_STRNLEN
- /* Adjust length. */
+ /* Check if at last VEC_SIZE * 4 length. */
+ cmpq $(CHAR_PER_VEC * 4 - 1), %rsi
+ jbe L(last_4x_vec_or_less_load)
+ movl %edi, %ecx
+ andl $(VEC_SIZE * 4 - 1), %ecx
+# ifdef USE_AS_WCSLEN
+ /* NB: Divide bytes by 4 to get the wchar_t count. */
+ sarl $2, %ecx
+# endif
+ /* Readjust length. */
addq %rcx, %rsi
# endif
+ /* Align data to VEC_SIZE * 4. */
+ andq $-(VEC_SIZE * 4), %rdi
+ /* Compare 4 * VEC at a time forward. */
.p2align 4
L(loop_4x_vec):
- /* Compare 4 * VEC at a time forward. */
- VMOVA (%rdi), %YMM1
- VMOVA VEC_SIZE(%rdi), %YMM2
- VMOVA (VEC_SIZE * 2)(%rdi), %YMM3
- VMOVA (VEC_SIZE * 3)(%rdi), %YMM4
-
- VPMINU %YMM1, %YMM2, %YMM5
- VPMINU %YMM3, %YMM4, %YMM6
+ /* Load first VEC regardless. */
+ VMOVA (VEC_SIZE * 4)(%rdi), %YMM1
+# ifdef USE_AS_STRNLEN
+ /* Break if at end of length. */
+ subq $(CHAR_PER_VEC * 4), %rsi
+ jb L(last_4x_vec_or_less_cmpeq)
+# endif
+ /* Save some code size by microfusing VPMINU with the load. Since
+ the matches in ymm2/ymm4 can only be returned if there where no
+ matches in ymm1/ymm3 respectively there is no issue with overlap.
+ */
+ VPMINU (VEC_SIZE * 5)(%rdi), %YMM1, %YMM2
+ VMOVA (VEC_SIZE * 6)(%rdi), %YMM3
+ VPMINU (VEC_SIZE * 7)(%rdi), %YMM3, %YMM4
+
+ VPCMP $0, %YMM2, %YMMZERO, %k0
+ VPCMP $0, %YMM4, %YMMZERO, %k1
+ subq $-(VEC_SIZE * 4), %rdi
+ kortestd %k0, %k1
+ jz L(loop_4x_vec)
+
+ /* Check if end was in first half. */
+ kmovd %k0, %eax
+ subq %rdx, %rdi
+# ifdef USE_AS_WCSLEN
+ shrq $2, %rdi
+# endif
+ testl %eax, %eax
+ jz L(second_vec_return)
- VPMINU %YMM5, %YMM6, %YMM5
- VPCMP $0, %YMM5, %YMMZERO, %k0
- ktestd %k0, %k0
- jnz L(4x_vec_end)
+ VPCMP $0, %YMM1, %YMMZERO, %k2
+ kmovd %k2, %edx
+ /* Combine VEC1 matches (edx) with VEC2 matches (eax). */
+# ifdef USE_AS_WCSLEN
+ sall $CHAR_PER_VEC, %eax
+ orl %edx, %eax
+ tzcntl %eax, %eax
+# else
+ salq $CHAR_PER_VEC, %rax
+ orq %rdx, %rax
+ tzcntq %rax, %rax
+# endif
+ addq %rdi, %rax
+ ret
- addq $(VEC_SIZE * 4), %rdi
-# ifndef USE_AS_STRNLEN
- jmp L(loop_4x_vec)
-# else
- subq $(VEC_SIZE * 4), %rsi
- ja L(loop_4x_vec)
+# ifdef USE_AS_STRNLEN
+L(last_4x_vec_or_less_load):
+ /* Depending on entry adjust rdi / prepare first VEC in YMM1. */
+ VMOVA (VEC_SIZE * 4)(%rdi), %YMM1
+L(last_4x_vec_or_less_cmpeq):
+ VPCMP $0, %YMM1, %YMMZERO, %k0
+ addq $(VEC_SIZE * 3), %rdi
L(last_4x_vec_or_less):
- /* Less than 4 * VEC and aligned to VEC_SIZE. */
- addl $(VEC_SIZE * 2), %esi
- jle L(last_2x_vec)
-
- VPCMP $0, (%rdi), %YMMZERO, %k0
kmovd %k0, %eax
+ /* If remaining length > VEC_SIZE * 2. This works if esi is off by
+ VEC_SIZE * 4. */
+ testl $(CHAR_PER_VEC * 2), %esi
+ jnz L(last_4x_vec)
+
+ /* length may have been negative or positive by an offset of
+ CHAR_PER_VEC * 4 depending on where this was called from. This
+ fixes that. */
+ andl $(CHAR_PER_VEC * 4 - 1), %esi
testl %eax, %eax
- jnz L(first_vec_x0)
+ jnz L(last_vec_x1_check)
- VPCMP $0, VEC_SIZE(%rdi), %YMMZERO, %k0
- kmovd %k0, %eax
- testl %eax, %eax
- jnz L(first_vec_x1)
+ /* Check the end of data. */
+ subl $CHAR_PER_VEC, %esi
+ jb L(max)
VPCMP $0, (VEC_SIZE * 2)(%rdi), %YMMZERO, %k0
kmovd %k0, %eax
- testl %eax, %eax
- jnz L(first_vec_x2_check)
- subl $VEC_SIZE, %esi
- jle L(max)
+ tzcntl %eax, %eax
+ /* Check the end of data. */
+ cmpl %eax, %esi
+ jb L(max)
- VPCMP $0, (VEC_SIZE * 3)(%rdi), %YMMZERO, %k0
- kmovd %k0, %eax
- testl %eax, %eax
- jnz L(first_vec_x3_check)
+ subq %rdx, %rdi
+# ifdef USE_AS_WCSLEN
+ /* NB: Divide bytes by 4 to get the wchar_t count. */
+ sarq $2, %rdi
+# endif
+ leaq (CHAR_PER_VEC * 2)(%rdi, %rax), %rax
+ ret
+L(max):
movq %r8, %rax
+ ret
+# endif
+
+ /* Placed here in strnlen so that the jcc L(last_4x_vec_or_less)
+ in the 4x VEC loop can use 2 byte encoding. */
+ .p2align 4
+L(second_vec_return):
+ VPCMP $0, %YMM3, %YMMZERO, %k0
+ /* Combine YMM3 matches (k0) with YMM4 matches (k1). */
+# ifdef USE_AS_WCSLEN
+ kunpckbw %k0, %k1, %k0
+ kmovd %k0, %eax
+ tzcntl %eax, %eax
+# else
+ kunpckdq %k0, %k1, %k0
+ kmovq %k0, %rax
+ tzcntq %rax, %rax
+# endif
+ leaq (CHAR_PER_VEC * 2)(%rdi, %rax), %rax
+ ret
+
+
+# ifdef USE_AS_STRNLEN
+L(last_vec_x1_check):
+ tzcntl %eax, %eax
+ /* Check the end of data. */
+ cmpl %eax, %esi
+ jb L(max)
+ subq %rdx, %rdi
# ifdef USE_AS_WCSLEN
- shrq $2, %rax
+ /* NB: Divide bytes by 4 to get the wchar_t count. */
+ sarq $2, %rdi
# endif
+ leaq (CHAR_PER_VEC)(%rdi, %rax), %rax
ret
.p2align 4
-L(last_2x_vec):
- addl $(VEC_SIZE * 2), %esi
+L(last_4x_vec):
+ /* Test first 2x VEC normally. */
+ testl %eax, %eax
+ jnz L(last_vec_x1)
- VPCMP $0, (%rdi), %YMMZERO, %k0
+ VPCMP $0, (VEC_SIZE * 2)(%rdi), %YMMZERO, %k0
kmovd %k0, %eax
testl %eax, %eax
- jnz L(first_vec_x0_check)
- subl $VEC_SIZE, %esi
- jle L(max)
+ jnz L(last_vec_x2)
- VPCMP $0, VEC_SIZE(%rdi), %YMMZERO, %k0
+ /* Normalize length. */
+ andl $(CHAR_PER_VEC * 4 - 1), %esi
+ VPCMP $0, (VEC_SIZE * 3)(%rdi), %YMMZERO, %k0
kmovd %k0, %eax
testl %eax, %eax
- jnz L(first_vec_x1_check)
- movq %r8, %rax
-# ifdef USE_AS_WCSLEN
- shrq $2, %rax
-# endif
- ret
+ jnz L(last_vec_x3)
- .p2align 4
-L(first_vec_x0_check):
+ /* Check the end of data. */
+ subl $(CHAR_PER_VEC * 3), %esi
+ jb L(max)
+
+ VPCMP $0, (VEC_SIZE * 4)(%rdi), %YMMZERO, %k0
+ kmovd %k0, %eax
tzcntl %eax, %eax
-# ifdef USE_AS_WCSLEN
- /* NB: Multiply wchar_t count by 4 to get the number of bytes. */
- sall $2, %eax
-# endif
/* Check the end of data. */
- cmpq %rax, %rsi
- jbe L(max)
- addq %rdi, %rax
- subq %rdx, %rax
+ cmpl %eax, %esi
+ jb L(max_end)
+
+ subq %rdx, %rdi
# ifdef USE_AS_WCSLEN
- shrq $2, %rax
+ /* NB: Divide bytes by 4 to get the wchar_t count. */
+ sarq $2, %rdi
# endif
+ leaq (CHAR_PER_VEC * 4)(%rdi, %rax), %rax
ret
.p2align 4
-L(first_vec_x1_check):
+L(last_vec_x1):
tzcntl %eax, %eax
+ subq %rdx, %rdi
# ifdef USE_AS_WCSLEN
- /* NB: Multiply wchar_t count by 4 to get the number of bytes. */
- sall $2, %eax
-# endif
- /* Check the end of data. */
- cmpq %rax, %rsi
- jbe L(max)
- addq $VEC_SIZE, %rax
- addq %rdi, %rax
- subq %rdx, %rax
-# ifdef USE_AS_WCSLEN
- shrq $2, %rax
+ /* NB: Divide bytes by 4 to get the wchar_t count. */
+ sarq $2, %rdi
# endif
+ leaq (CHAR_PER_VEC)(%rdi, %rax), %rax
ret
.p2align 4
-L(first_vec_x2_check):
+L(last_vec_x2):
tzcntl %eax, %eax
+ subq %rdx, %rdi
# ifdef USE_AS_WCSLEN
- /* NB: Multiply wchar_t count by 4 to get the number of bytes. */
- sall $2, %eax
-# endif
- /* Check the end of data. */
- cmpq %rax, %rsi
- jbe L(max)
- addq $(VEC_SIZE * 2), %rax
- addq %rdi, %rax
- subq %rdx, %rax
-# ifdef USE_AS_WCSLEN
- shrq $2, %rax
+ /* NB: Divide bytes by 4 to get the wchar_t count. */
+ sarq $2, %rdi
# endif
+ leaq (CHAR_PER_VEC * 2)(%rdi, %rax), %rax
ret
.p2align 4
-L(first_vec_x3_check):
+L(last_vec_x3):
tzcntl %eax, %eax
-# ifdef USE_AS_WCSLEN
- /* NB: Multiply wchar_t count by 4 to get the number of bytes. */
- sall $2, %eax
-# endif
+ subl $(CHAR_PER_VEC * 2), %esi
/* Check the end of data. */
- cmpq %rax, %rsi
- jbe L(max)
- addq $(VEC_SIZE * 3), %rax
- addq %rdi, %rax
- subq %rdx, %rax
+ cmpl %eax, %esi
+ jb L(max_end)
+ subq %rdx, %rdi
# ifdef USE_AS_WCSLEN
- shrq $2, %rax
+ /* NB: Divide bytes by 4 to get the wchar_t count. */
+ sarq $2, %rdi
# endif
+ leaq (CHAR_PER_VEC * 3)(%rdi, %rax), %rax
ret
-
- .p2align 4
-L(max):
+L(max_end):
movq %r8, %rax
-# ifdef USE_AS_WCSLEN
- shrq $2, %rax
-# endif
- ret
-
- .p2align 4
-L(zero):
- xorl %eax, %eax
ret
# endif
+ /* Cold case for crossing page with first load. */
.p2align 4
-L(first_vec_x0):
- tzcntl %eax, %eax
-# ifdef USE_AS_WCSLEN
- /* NB: Multiply wchar_t count by 4 to get the number of bytes. */
- sall $2, %eax
-# endif
- addq %rdi, %rax
- subq %rdx, %rax
+L(cross_page_boundary):
+ movq %rdi, %rdx
+ /* Align data to VEC_SIZE. */
+ andq $-VEC_SIZE, %rdi
+ VPCMP $0, (%rdi), %YMMZERO, %k0
+ kmovd %k0, %eax
+ /* Remove the leading bytes. */
# ifdef USE_AS_WCSLEN
- shrq $2, %rax
+ /* NB: Divide shift count by 4 since each bit in K0 represent 4
+ bytes. */
+ movl %edx, %ecx
+ shrl $2, %ecx
+ andl $(CHAR_PER_VEC - 1), %ecx
# endif
- ret
-
- .p2align 4
-L(first_vec_x1):
+ /* SHIFT_REG is ecx for USE_AS_WCSLEN and edx otherwise. */
+ sarxl %SHIFT_REG, %eax, %eax
+ testl %eax, %eax
+# ifndef USE_AS_STRNLEN
+ jz L(cross_page_continue)
tzcntl %eax, %eax
-# ifdef USE_AS_WCSLEN
- /* NB: Multiply wchar_t count by 4 to get the number of bytes. */
- sall $2, %eax
-# endif
- addq $VEC_SIZE, %rax
- addq %rdi, %rax
- subq %rdx, %rax
-# ifdef USE_AS_WCSLEN
- shrq $2, %rax
-# endif
ret
-
- .p2align 4
-L(first_vec_x2):
- tzcntl %eax, %eax
-# ifdef USE_AS_WCSLEN
- /* NB: Multiply wchar_t count by 4 to get the number of bytes. */
- sall $2, %eax
-# endif
- addq $(VEC_SIZE * 2), %rax
- addq %rdi, %rax
- subq %rdx, %rax
-# ifdef USE_AS_WCSLEN
- shrq $2, %rax
-# endif
+# else
+ jnz L(cross_page_less_vec)
+# ifndef USE_AS_WCSLEN
+ movl %edx, %ecx
+ andl $(CHAR_PER_VEC - 1), %ecx
+# endif
+ movl $CHAR_PER_VEC, %eax
+ subl %ecx, %eax
+ /* Check the end of data. */
+ cmpq %rax, %rsi
+ ja L(cross_page_continue)
+ movl %esi, %eax
ret
-
- .p2align 4
-L(4x_vec_end):
- VPCMP $0, %YMM1, %YMMZERO, %k0
- kmovd %k0, %eax
- testl %eax, %eax
- jnz L(first_vec_x0)
- VPCMP $0, %YMM2, %YMMZERO, %k1
- kmovd %k1, %eax
- testl %eax, %eax
- jnz L(first_vec_x1)
- VPCMP $0, %YMM3, %YMMZERO, %k2
- kmovd %k2, %eax
- testl %eax, %eax
- jnz L(first_vec_x2)
- VPCMP $0, %YMM4, %YMMZERO, %k3
- kmovd %k3, %eax
-L(first_vec_x3):
+L(cross_page_less_vec):
tzcntl %eax, %eax
-# ifdef USE_AS_WCSLEN
- /* NB: Multiply wchar_t count by 4 to get the number of bytes. */
- sall $2, %eax
-# endif
- addq $(VEC_SIZE * 3), %rax
- addq %rdi, %rax
- subq %rdx, %rax
-# ifdef USE_AS_WCSLEN
- shrq $2, %rax
-# endif
+ /* Select min of length and position of first null. */
+ cmpq %rax, %rsi
+ cmovb %esi, %eax
ret
+# endif
END (STRLEN)
#endif