git: 37728967ee5c - stable/14 - lib/libc/amd64/string/strcmp.S: add baseline implementation

From: Robert Clausecker <fuz_at_FreeBSD.org>
Date: Wed, 24 Jan 2024 19:44:28 UTC
The branch stable/14 has been updated by fuz:

URL: https://cgit.FreeBSD.org/src/commit/?id=37728967ee5c845f5af9d22377be10ffb62c90aa

commit 37728967ee5c845f5af9d22377be10ffb62c90aa
Author:     Robert Clausecker <fuz@FreeBSD.org>
AuthorDate: 2023-09-16 05:29:39 +0000
Commit:     Robert Clausecker <fuz@FreeBSD.org>
CommitDate: 2024-01-24 19:39:24 +0000

    lib/libc/amd64/string/strcmp.S: add baseline implementation
    
    This is the most complicated one so far.  The basic idea is to process
    the bulk of the string in aligned blocks of 16 bytes such that one
    string runs ahead and the other runs behind.  The string that runs ahead
    is checked for NUL bytes, the one that runs behind is compared with the
    corresponding chunk of the string that runs ahead.  This trades an extra
    load per iteration for the very complicated block-reassembly needed in
    the other implementations (bionic, glibc).  On the flip side, we need
    two code paths depending on the relative alignment of the two buffers.
    
    The initial part of the string is compared directly if it is known not
    to cross a page boundary.  Otherwise, a complex slow path to avoid
    crossing into unmapped memory commences.
    
    Performance-wise we beat bionic for misaligned strings (i.e. the strings
    do not share an alignment offset) and reach comparable performance for
    aligned strings.  glibc is a bit better as it has a special kernel for
    AVX-512, where this stuff is a bit easier to do.
    
    Sponsored by:   The FreeBSD Foundation
    Tested by:      developers@, exp-run
    Approved by:    mjg
    MFC after:      1 month
    MFC to:         stable/14
    PR:             275785
    Differential Revision:  https://reviews.freebsd.org/D41971
    
    (cherry picked from commit bca25680b91b3bea7faef615765806a04634eb23)
---
 lib/libc/amd64/string/strcmp.S | 299 ++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 292 insertions(+), 7 deletions(-)

diff --git a/lib/libc/amd64/string/strcmp.S b/lib/libc/amd64/string/strcmp.S
index 437db7eca43a..eb354bd2af82 100644
--- a/lib/libc/amd64/string/strcmp.S
+++ b/lib/libc/amd64/string/strcmp.S
@@ -1,14 +1,33 @@
-/*
- * Written by J.T. Conklin <jtc@acorntoolworks.com>
- * Public domain.
+/*-
+ * Copyright (c) 2023, The FreeBSD Foundation
+ *
+ * SPDX-License-Expression: BSD-2-Clause
+ *
+ * Portions of this software were developed by Robert Clausecker
+ * <fuz@FreeBSD.org> under sponsorship from the FreeBSD Foundation.
+ *
+ * Adapted from NetBSD's common/lib/libc/arch/x86_64/string/strcmp.S
+ * written by J.T. Conklin <jtc@acorntoolworks.com> that was originally
+ * dedicated to the public domain.
  */
 
 #include <machine/asm.h>
+#include <machine/param.h>
+
 #if 0
 	RCSID("$NetBSD: strcmp.S,v 1.3 2004/07/19 20:04:41 drochner Exp $")
 #endif
 
-ENTRY(strcmp)
+#include "amd64_archlevel.h"
+
+#define ALIGN_TEXT	.p2align 4, 0x90
+
+ARCHFUNCS(strcmp)
+	ARCHFUNC(strcmp, scalar)
+	ARCHFUNC(strcmp, baseline)
+ENDARCHFUNCS(strcmp)
+
+ARCHENTRY(strcmp, scalar)
 	/*
 	 * Align s1 to word boundary.
 	 * Consider unrolling loop?
@@ -39,7 +58,7 @@ ENTRY(strcmp)
 	movabsq	$0x8080808080808080,%r9
 	subq	$8,%rsi
 
-	.align	4
+	ALIGN_TEXT
 .Lword_loop:
 	movq	8(%rdi),%rax
 	addq	$8,%rdi
@@ -53,7 +72,7 @@ ENTRY(strcmp)
 	testq	%r9,%rdx
 	je	.Lword_loop
 
-	.align	4
+	ALIGN_TEXT
 .Lbyte_loop:
 	movb	(%rdi),%al
 	incq	%rdi
@@ -69,6 +88,272 @@ ENTRY(strcmp)
 	movzbq	%dl,%rdx
 	subq	%rdx,%rax
 	ret
-END(strcmp)
+ARCHEND(strcmp, scalar)
+
+ARCHENTRY(strcmp, baseline)
+	/* check if either string crosses a page in the head */
+	lea		15(%rdi), %r8d	# end of head
+	lea		15(%rsi), %r9d
+	mov		%edi, %eax
+	mov		%esi, %edx
+	xor		%edi, %r8d	# bits that changed between first and last byte
+	xor		%esi, %r9d
+	and		$~0xf, %rdi	# align heads to 16 bytes
+	and		$~0xf, %rsi
+	or		%r8d, %r9d	# in either RSI or RDI
+	and		$0xf, %eax	# offset from alignment
+	and		$0xf, %edx
+	pxor		%xmm1, %xmm1
+	test		$PAGE_SIZE, %r9d # did the page change?
+	jz		0f		# if not, take fast path
+
+	/* heads may cross page boundary, avoid unmapped loads */
+	movdqa		(%rdi), %xmm0	# load aligned heads
+	movdqa		(%rsi), %xmm2
+	mov		$-1, %r8d
+	mov		$-1, %r9d
+	mov		%eax, %ecx
+	shl		%cl, %r8d	# string head in XMM0
+	mov		%edx, %ecx
+	shl		%cl, %r9d	# string head in XMM2
+	movdqa		%xmm0, -40(%rsp) # stash copies of the heads on the stack
+	movdqa		%xmm2, -24(%rsp)
+	pcmpeqb		%xmm1, %xmm0
+	pcmpeqb		%xmm1, %xmm2
+	pmovmskb	%xmm0, %r10d
+	pmovmskb	%xmm2, %r11d
+	test		%r8d, %r10d	# NUL byte present in first string?
+	lea		-40(%rsp), %r8
+	cmovz		%rdi, %r8
+	test		%r9d, %r11d	# NUL byte present in second string?
+	lea		-24(%rsp), %r9
+	cmovz		%rsi, %r9
+	movdqu		(%r8, %rax, 1), %xmm0 # load true (or fake) heads
+	movdqu		(%r9, %rdx, 1), %xmm4
+	jmp		1f
+
+0:	movdqu		(%rdi, %rax, 1), %xmm0 # load true heads
+	movdqu		(%rsi, %rdx, 1), %xmm4
+1:	pxor		%xmm2, %xmm2
+	pcmpeqb		%xmm0, %xmm2	# NUL byte present?
+	pcmpeqb		%xmm0, %xmm4	# which bytes match?
+	pandn		%xmm4, %xmm2	# match and not NUL byte?
+	pmovmskb	%xmm2, %r9d
+	xor		$0xffff, %r9d	# mismatch or NUL byte?
+	jnz		.Lhead_mismatch
+
+	/* load head and second chunk */
+	movdqa		16(%rdi), %xmm2	# load second chunks
+	movdqa		16(%rsi), %xmm3
+	sub		%rdx, %rax	# is a&0xf >= b&0xf?
+	jb		.Lswapped	# if not, proceed with swapped operands
+
+	neg		%rax
+	movdqu		16(%rsi, %rax, 1), %xmm0
+	sub		%rdi, %rsi	# express RSI as distance from RDI
+	lea		(%rsi, %rax, 1), %rdx # point RDX to offset in second string
+	neg		%rax
+	pcmpeqb		%xmm3, %xmm1	# ... corresponding to RDI
+	pcmpeqb		%xmm2, %xmm0
+	pmovmskb	%xmm1, %r8d
+	pmovmskb	%xmm0, %r9d
+	add		$16, %rdi
+	test		%r8d, %r8d
+	jnz		.Lnul_found
+	xor		$0xffff, %r9d
+	jnz		.Lmismatch
+	add		$16, %rdi	# advance aligned pointers
+
+	/*
+	 * During the main loop, the layout of the two strings is something like:
+	 *
+	 *          v ------1------ v ------2------ v
+	 *     RDI:    AAAAAAAAAAAAABBBBBBBBBBBBBBBB...
+	 *     RSI: AAAAAAAAAAAAABBBBBBBBBBBBBBBBCCC...
+	 *
+	 * where v indicates the alignment boundaries and corresponding chunks
+	 * of the strings have the same letters.  Chunk A has been checked in
+	 * the previous iteration.  This iteration, we first check that string
+	 * RSI doesn't end within region 2, then we compare chunk B between the
+	 * two strings.  As RSI is known not to hold a NUL byte in regsions 1
+	 * and 2 at this point, this also ensures that RDI has not ended yet.
+	 */
+	ALIGN_TEXT
+0:	movdqu		(%rdi, %rdx, 1), %xmm0 # chunk of 2nd string corresponding to RDI?
+	pxor		%xmm1, %xmm1
+	pcmpeqb		(%rdi, %rsi, 1), %xmm1 # end of string in RSI?
+	pcmpeqb		(%rdi), %xmm0	# where do the chunks match?
+	pmovmskb	%xmm1, %r8d
+	pmovmskb	%xmm0, %r9d
+	test		%r8d, %r8d
+	jnz		.Lnul_found
+	xor		$0xffff, %r9d	# any mismatches?
+	jnz		.Lmismatch
+
+	/* main loop unrolled twice */
+	movdqu		16(%rdi, %rdx, 1), %xmm0 # chunk of 2nd string corresponding to RDI?
+	pxor		%xmm1, %xmm1
+	pcmpeqb		16(%rdi, %rsi, 1), %xmm1 # end of string in RSI?
+	pcmpeqb		16(%rdi), %xmm0	# where do the chunks match?
+	pmovmskb	%xmm1, %r8d
+	pmovmskb	%xmm0, %r9d
+	add		$32, %rdi
+	test		%r8d, %r8d
+	jnz		.Lnul_found2
+	xor		$0xffff, %r9d	# any mismatches?
+	jz		0b
+
+	sub		$16, %rdi	# roll back second increment
+
+	/* a mismatch has been found between RDX and RSI */
+.Lmismatch:
+	tzcnt		%r9d, %r9d	# where is the mismatch?
+	add		%rdi, %rdx	# turn RDX from offset to pointer
+	movzbl		(%rdx, %r9, 1), %ecx
+	movzbl		(%rdi, %r9, 1), %eax
+	sub		%ecx, %eax	# difference of the mismatching chars
+	ret
+
+	/* mismatch in true heads */
+.Lhead_mismatch:
+	tzcnt		%r9d, %r9d	# where is the mismatch?
+	add		%rax, %rdi	# return to true heads
+	add		%rdx, %rsi
+	movzbl		(%rdi, %r9, 1), %eax # mismatching characters
+	movzbl		(%rsi, %r9, 1), %ecx
+	sub		%ecx, %eax
+	ret
+
+.Lnul_found2:
+	sub		$16, %rdi	# roll back second increment
+
+	/* a NUL has been found in RSI */
+.Lnul_found:
+	mov		%eax, %ecx
+	mov		%r8d, %r10d
+	shl		%cl, %r8w	# adjust NUL mask to positions in RDI/RDX
+	xor		$0xffff, %r9d	# mask of mismatches
+	or		%r8d, %r9d	# NUL bytes also count as mismatches
+	jnz		.Lmismatch
+
+	/*
+	 * (RDI) == (RSI) and NUL is past the string.
+	 * Compare (RSI) with the corresponding part
+	 * of the other string until the NUL byte.
+	 */
+	movdqu		(%rdi, %rax, 1), %xmm0
+	pcmpeqb		(%rdi, %rsi, 1), %xmm0
+	add		%rdi, %rsi	# restore RSI pointer
+	add		%rax, %rdi	# point RDI to chunk corresponding to (RSI)
+	pmovmskb	%xmm0, %ecx	# mask of matches
+	not		%ecx		# mask of mismatches
+	or		%r10d, %ecx	# mask of mismatches or NUL bytes
+	tzcnt		%ecx, %ecx	# location of first mismatch
+	movzbl		(%rdi, %rcx, 1), %eax
+	movzbl		(%rsi, %rcx, 1), %ecx
+	sub		%ecx, %eax
+	ret
+
+	/*
+	 * If (a&0xf) < (b&0xf), we do the same thing but with swapped
+	 * operands.  I found that this performs slightly better than
+	 * using conditional moves to do the swap branchless.
+	 */
+.Lswapped:
+	movdqu		16(%rdi, %rax, 1), %xmm0
+	sub		%rsi, %rdi	# express RDI as distance from RSI
+	lea		(%rdi, %rax, 1), %rdx # point RDX to offset in RDI corresponding to RSI
+	neg		%rax		# make difference positive
+	pcmpeqb		%xmm2, %xmm1
+	pcmpeqb		%xmm3, %xmm0
+	pmovmskb	%xmm1, %r8d
+	pmovmskb	%xmm0, %r9d
+	add		$16, %rsi	# advance aligned pointers
+	test		%r8d, %r8d
+	jnz		.Lnul_founds
+	xor		$0xffff, %r9d
+	jnz		.Lmismatchs
+	add		$16, %rsi
+
+	/*
+	 * During the main loop, the layout of the two strings is something like:
+	 *
+	 *          v ------1------ v ------2------ v
+	 *     RDI:    AAAAAAAAAAAAABBBBBBBBBBBBBBBB...
+	 *     RSI: AAAAAAAAAAAAABBBBBBBBBBBBBBBBCCC...
+	 *
+	 * where v indicates the alignment boundaries and corresponding chunks
+	 * of the strings have the same letters.  Chunk A has been checked in
+	 * the previous iteration.  This iteration, we first check that string
+	 * RSI doesn't end within region 2, then we compare chunk B between the
+	 * two strings.  As RSI is known not to hold a NUL byte in regsions 1
+	 * and 2 at this point, this also ensures that RDI has not ended yet.
+	 */
+	ALIGN_TEXT
+0:	movdqu		(%rsi, %rdx, 1), %xmm0 # chunk of 2nd string corresponding to RDI?
+	pxor		%xmm1, %xmm1
+	pcmpeqb		(%rsi, %rdi, 1), %xmm1 # end of string in RSI?
+	pcmpeqb		(%rsi), %xmm0	# where do the chunks match?
+	pmovmskb	%xmm1, %r8d
+	pmovmskb	%xmm0, %r9d
+	test		%r8d, %r8d
+	jnz		.Lnul_founds
+	xor		$0xffff, %r9d	# any mismatches?
+	jnz		.Lmismatchs
+
+	/* main loop unrolled twice */
+	movdqu		16(%rsi, %rdx, 1), %xmm0 # chunk of 2nd string corresponding to RDI?
+	pxor		%xmm1, %xmm1
+	pcmpeqb		16(%rsi, %rdi, 1), %xmm1 # end of string in RSI?
+	pcmpeqb		16(%rsi), %xmm0	# where do the chunks match?
+	pmovmskb	%xmm1, %r8d
+	pmovmskb	%xmm0, %r9d
+	add		$32, %rsi
+	test		%r8d, %r8d
+	jnz		.Lnul_found2s
+	xor		$0xffff, %r9d	# any mismatches?
+	jz		0b
+
+	sub		$16, %rsi	# roll back second increment
+
+	/* a mismatch has been found between RDX and RDI */
+.Lmismatchs:
+	tzcnt		%r9d, %r9d	# where is the mismatch?
+	add		%rsi, %rdx	# turn RDX from offset to pointer
+	movzbl		(%rdx, %r9, 1), %eax
+	movzbl		(%rsi, %r9, 1), %ecx
+	sub		%ecx, %eax	# difference of the mismatching chars
+	ret
+
+.Lnul_found2s:
+	sub		$16, %rsi	# roll back second increment
+
+	/* a NUL has been found in RSI */
+.Lnul_founds:
+	mov		%eax, %ecx
+	mov		%r8d, %r10d
+	shl		%cl, %r8w	# adjust NUL mask to positions in RDI/RDX
+	xor		$0xffff, %r9d	# mask of mismatches
+	or		%r8d, %r9d	# NUL bytes also count as mismatches
+	jnz		.Lmismatchs
+
+	/*
+	 * (RDI) == (RSI) and NUL is past the string.
+	 * Compare (RSI) with the corresponding part
+	 * of the other string until the NUL byte.
+	 */
+	movdqu		(%rsi, %rax, 1), %xmm0
+	pcmpeqb		(%rsi, %rdi, 1), %xmm0
+	add		%rsi, %rdi	# restore RDI pointer
+	add		%rax, %rsi	# point RSI to chunk corresponding to (RDI)
+	pmovmskb	%xmm0, %ecx	# mask of matches
+	not		%ecx		# mask of mismatches
+	or		%r10d, %ecx	# mask of mismatches or NUL bytes
+	tzcnt		%ecx, %ecx	# location of first mismatch
+	movzbl		(%rdi, %rcx, 1), %eax
+	movzbl		(%rsi, %rcx, 1), %ecx
+	sub		%ecx, %eax
+	ret
+ARCHEND(strcmp, baseline)
 
 	.section .note.GNU-stack,"",%progbits