Page MenuHomeFreeBSD
Differential D46023 Diff 165554 lib/libc/riscv/string/memchr.S

Changeset View

Standalone View

View Options

lib/libc/riscv/string/memchr.S

  • This file was added.
/*-
* SPDX-License-Identifier: BSD-2-Clause
*
* Copyright (c) 2024 Strahinja Stanisic <strajabot@FreeBSD.org>
*/
#include <machine/asm.h>
/*
* a0 - const void *b
* a1 - int c
* a2 - size_t len
*/
ENTRY(memchr)
/*
* a0 - const char *ptr
* a1 - char cccccccc[8]
* a2 - char iter[8]
* a3 - uint8_t *end
* a4 - uint64_t *end_align
* a5 - uint64_t *end_unroll
*/
beqz a2, .Lno_match
/* c = (uint8_t) c */
andi a1, a1, 0xFF
/*
* t0 = 0x0101010101010101
* t1 = 0x8080808080808080
* t2 = b << 3
* cccccccc = (uint8_t)c * t0
* end = b + len;
* ptr = b & ~0b111
*/
fuzUnsubmitted
Done
Inline Actions

Could you somehow avoid having to deal with two counters here? Each addition is 20% of the full loop, so if you get rid of one, that's a 20% speedup.

Also consider completely peeling the loop or using Duff's device.

fuz: Could you somehow avoid having to deal with two counters here? Each addition is 20% of the…
add a3, a0, a2
li t0, 0x01010101
sltu t2, a0, a3
slli t1, t0, 32
neg t2, t2
or t0, t0, t1
and a3, a3, t2
slli t1, t0, 7
slli t2, a0, 3
and a0, a0, ~0b111
mul a1, t0, a1
ld a2, (a0)
/*
* mask_start = REP8_0x01 ^ (REP8_0x01 << t2)
* iter = iter ^ cccccccc
* iter = iter | mask_start
*/
sll t2, t0, t2
xor a2, a2, a1
xor t2, t2, t0
or a2, a2, t2
/* has_zero(iter)
* end_align = (end + 7) & ~0b111;
*/
addi a4, a3, 7
not t2, a2
sub a2, a2, t0
and t2, t2, t1
andi a4, a4, ~0b111
and a2, a2, t2
/* ptr = ptr + 8 */
addi a0, a0, 8
bnez a2, .Lfind_zero
/* if(ptr == end_align) */
beq a0, a4, .Lno_match
/* end_unroll = end_align & ~0b1111 */
andi a5, a4, ~0b1111
/*
* Instead of branching to check if `ptr` is 16-byte aligned:
* - Probe the next 8 bytes for `c`
* - Align `ptr` down to the nearest 16-byte boundary
*
mhorneUnsubmitted
Not Done
Inline Actions

Please improve the formatting of this comment.

mhorne: Please improve the formatting of this comment.
* If `ptr` was already 16-byte aligned, those 8 bytes will be
* checked again inside the unrolled loop.
*
* This removes an unpredictable branch and improves performance.
*/
ld a2, (a0)
xor a2, a2, a1
not t2, a2
sub a2, a2, t0
and t2, t2, t1
and a2, a2, t2
addi a0, a0, 8
bnez a2, .Lfind_zero
andi a0, a0, ~0b1111
/* while(ptr != end_unroll) */
beq a0, a5, .Lskip_loop
.Lloop:
ld a2, (a0)
ld t3, 8(a0)
xor a2, a2, a1
xor t3, t3, a1
not t2, a2
not t4, t3
sub a2, a2, t0
sub t3, t3, t0
and t2, t2, t1
fuzUnsubmitted
Done
Inline Actions
/* 0 bytes remaining to check */
- beqz a3, .Lno_match
+ beqz a6, .Lno_match
ld a4, (a0)

Avoid depending on the previous instruction.

fuz: Avoid depending on the previous instruction.
and t4, t4, t1
and a2, a2, t2
and t3, t3, t4
addi a0, a0, 8
bnez a2, .Lfind_zero
/* move into iter for find_zero */
mv a2, t3
addi a0, a0, 8
bnez a2, .Lfind_zero
bne a0, a5, .Lloop
.Lskip_loop:
/* there might be one 8byte left */
beq a0, a4, .Lno_match
ld a2, (a0)
xor a2, a2, a1
not t2, a2
sub a2, a2, t0
and t2, t2, t1
and a2, a2, t2
addi a0, a0, 8
beqz a2, .Lno_match
.Lfind_zero:
/*
* ptr = ptr - 8
* t1 = 0x0001020304050607
* iter = iter & (-iter)
* iter = iter >> 7
* iter = iter * t1
* iter = iter >> 56
*/
li t1, 0x10203000
neg t0, a2
slli t1, t1, 4
and a2, a2, t0
addi t1, t1, 0x405
srli a2, a2, 7
slli t1, t1, 16
addi a0, a0, -8
addi t1, t1, 0x607
mul a2, a2, t1
srli a2, a2, 56
/* left = end - ptr */
sub t0, a3, a0
/* return iter < left ? ptr + iter : NULL */
sltu t1, a2, t0
neg t1, t1
add a0, a0, a2
and a0, a0, t1
ret
.Lno_match:
li a0, 0
ret
END(memchr)