FW: [PATCH, ARM] memchr for ARM

["Greta Yorsh" <Greta dot Yorsh at arm dot com>]

A couple of small comments below.

> -----Original Message-----
> From: newlib-owner@sourceware.org [mailto:newlib-owner@sourceware.org]
> On Behalf Of Dr. David Alan Gilbert
> Sent: 10 October 2011 19:11
> To: newlib@sourceware.org
> Cc: nickc@redhat.com; michael.hope@linaro.org; patches@linaro.org
> Subject: [PATCH, ARM] memchr for ARM
> 
> Please find below an ARM optimised memchr; it needs
> Thumb2 and at least ARMv6T2. In the case of not having thumb or being
> on
> an earlier architecture it just includes the generic .c version.
> 
> It's been tested on arm-sim target; and the same assembly
> has been tested on eglibc as well on real hardware under Linux.
> 
> Performance testing (on a 1GHz A9) shows it's faster
> than the plain newlib code in most cases, and the xscale version
> in almost all cases, see:
> 
> https://wiki.linaro.org/WorkingGroups/ToolChain/Benchmarks/InitialMemch
> r?action=AttachFile&do=view&target=sizes-memchr-08.png
> 
> ('this' on the graph is the routine attached).
> 
> I wasn't sure whether the right thing was to include the Makefile.in
>  diff, or just let you regenerate on release - in the end I included
> it.
> 
> Thanks in advance,
> 
> Dave
> 
> 2011-10-10 Dr David Alan Gilbert <david.gilbert@linaro.org>
>   * libc/machine/arm/Makefile.am (lib_a_SOURCES): Add memchr.c
>   * libc/machine/arm/memchr.c: New file.
>   * libc/machine/arm/Makefile.in: Manually add same change as
> Makefile.am
> 
> .....
> +
> +   This memchr routine is optimised on a Cortex-A9 and should work on
> +   all ARMv7 processors.   It has a fast past for short sizes, and has

typo: past -> path ?

> +   an optimised path for large data sets; the worst case is finding
> the
> +   match early in a large data set. */
> +
> +/* 2011-02-07 david.gilbert@linaro.org
> +    Extracted from local git a5b438d861
> +   2011-07-14 david.gilbert@linaro.org
> +    Import endianness fix from local git ea786f1b
> +   2011-10-06 david.gilbert@linaro.org
> +    Import into Newlib from cortex-strings bzr rev 63 */
> +
> +#include "arm_asm.h"
> +
> +/* The code makes use of cbz, cbnz (in a way that's difficult to ifdef
> around
> +   so it's thumb2 only, and uses uadd8/sel that are 6T2 (Thumb) and 7a
> */
> +#if !defined( __thumb2__ ) || !(defined(_ISA_ARM_7) || \
> +	(defined(__ARM_ARCH_6T2__)))
> +  /* Fall back to generic C code */

Performance results you have for memchr show that the optimized version is
much better than the plain memchr in newlib. Perhaps this version should be
enabled in ARM mode as well? How much slower would it be if cbz/cbnz are
replaced with instructions available in both ARM and Thumb (instead of
ifdef)?

> +#include "../../string/memchr.c"
> +#else
> +
> +
> +#include <sys/types.h>
> +
> +/* this lets us check a flag in a 00/ff byte easily in either
> endianness */
> +#ifdef __ARMEB__
> +#define CHARTSTMASK(c) "1<<(31-(" #c "*8))"
> +#else
> +#define CHARTSTMASK(c) "1<<(" #c "*8)"
> +#endif
> +
> +/* -------------------------------------------------------------------
> ------- */
> +void*
> +__attribute__((naked)) memchr(const void* s, int c, size_t n)
> +{
> +  asm(
> +	/* r0 = start of memory to scan
> +	   r1 = character to look for
> +	   r2 = length
> +	   returns r0 = pointer to character or NULL if not found */
> +	"and	r1,r1,#0xff\n\t"	/* Don't think we can trust the
caller
> +					   to actually pass a char */
> +
> +	"cmp	r2,#16\n\t"		/* If it's short don't bother with
> +					   anything clever */
> +	"blt	20f\n\t"
> +
> +	"tst	r0, #7\n\t"		/* already aligned? skip the next
bit */
> +	"beq	10f\n"
> +
> +	/* Work up to an aligned point */
> +"5:\n\t"
> +	"ldrb	r3, [r0],#1\n\t"
> +	"subs	r2, r2, #1\n\t"

The flags are not used: subs -> sub.

> +	"cmp	r3, r1\n\t"
> +	"beq	50f\n\t"		/* If it matches exit found */
> +	"tst	r0, #7\n\t"
> +	"cbz	r2, 40f\n\t"		/* If we run off the end, exit
> !found */
> +	"bne	5b\n"			/* If not aligned yet, do next byte
*/
> +
> +"10:\n\t"
> +	/* At this point, we are aligned, we know we have at least 8
> bytes
> +	   to work with */
> +	"push	{r4,r5,r6,r7}\n\t"
> +	"orr	r1, r1, r1, lsl #8\n\t"	/* expand the match word to all
> bytes */
> +	"orr	r1, r1, r1, lsl #16\n\t"
Does this shift work for either endianness?

> +	"bic	r4, r2, #7\n\t"		/* No of double words to work with
> */
The comment is a bit confusing: r4 is the number of bytes (of the double
words to work with), not the number of words. 

> +	"mvns	r7, #0\n\t"		/* all F's */
> +	"movs	r3, #0\n"

Flags not used: mvns -> mvn, movs -> mov ?

> +
> +"15:\n\t"
> +	"ldmia	r0!,{r5,r6}\n\t"

It is probably better to use LDRD instead of LDM. On Cortex-A9, LDRD should
perform similar to LDM of 2 words, but on Cortex-A15 LDRD is expected to be
faster. 
There are more restrictions on ARM for registers used with LDRD, but it
should be easy to change of roles of the temporary registers such that the
same code works in both ARM and Thumb modes (e.g., using r6 for the counter
and "ldrd r4, r5, [r0], #8").

> +	"subs	r4, r4, #8\n\t"
> +	"eor	r5,r5, r1\n\t"	/* Make r5,r6 00's where bytes match
> target */
> +	"eor	r6,r6, r1\n\t"
> +	"uadd8	r5, r5, r7\n\t"	/* Par add 0xff, sets GE bits for
> bytes!=0 */
> +	"sel	r5, r3, r7\n\t"	/* bytes are 00 for none-00 bytes,
> +				   or ff for 00 bytes - NOTE INVERSION */
> +	"uadd8	r6, r6, r7\n\t"	/* Par add 0xff, sets GE bits for
> bytes!=0 */
> +	"sel	r6, r5, r7\n\t"	/* chained....bytes are 00 for none-00
> bytes,
> +				   or ff for 00 bytes - NOTE INVERSION */

Why is it chained? Wouldn't it also be correct to use r3 again: "sel r6, r3,
r7\n\t" ?

> +	"cbnz	r6, 60f\n\t"
> +	"bne	15b\n\t"	/* (Flags from the subs above) */
> +
> +	"pop	{r4,r5,r6,r7}\n\t"
> +	"and	r1,r1,#0xff\n\t" /* r1 back to a single character from
> above */
> +	"and	r2,r2,#7\n"	/* Leave the count remaining as the number
> +				   after the double words have been done */
> +
> +"20:\n\t"
> +	"cbz	r2, 40f\n\t"	/* 0 length or hit the end already ->
> !found */
> +
> +"21:\n\t"  /* Post aligned section, or just a short call */
> +	"ldrb	r3,[r0],#1\n\t"
> +	"subs	r2,r2,#1\n\t"
> +	"eor	r3,r3,r1\n\t"	/* r3 = 0 if match */
> +	"cbz	r3, 50f\n\t"
> +	"bne	21b\n"		/* on r2 flags */
> +
> +"40:\n\t"
> +	"movs	r0,#0\n\t"	/* not found */
> +	"bx	lr\n"
> +
> +"50:\n\t"
> +	"subs	r0,r0,#1\n\t"	/* found */
> +	"bx	lr\n"
> +
> +"60:\n\t"
> +	/* We're here because the fast path found a hit - now we have to
> track
> +	   down exactly which word it was
> +	   r0 points to the start of the double word after the one that
> +		was tested
> +	   r5 has the 00/ff pattern for the first word, r6 has the
> chained
> +		value */
> +	"cmp	r5, #0\n\t"
> +	"itte	eq\n\t"
> +	"moveq	r5, r6\n\t"	/* the end is in the 2nd word */
> +	"subeq	r0,r0,#3\n\t"	/* Points to 2nd byte of 2nd word
> */
> +	"subne	r0,r0,#7\n\t"	/* or 2nd byte of 1st word */
> +
> +	/* r0 currently points to the 3rd byte of the word containing the
> hit */

Do you mean "the 2nd byte of the word containing the hit"?

> +	"tst	r5, #" CHARTSTMASK(0) "\n\t"	/* 1st character */
> +	"bne	61f\n\t"
> +	"adds	r0,r0,#1\n\t"

Flags not used: adds -> add.

> +	"tst	r5, #" CHARTSTMASK(1) "\n\t"	/* 2nd character */
> +	"ittt	eq\n\t"
> +	"addeq	r0,r0,#1\n\t"
> +	"tsteq	r5, # (3<<15)\n\t"	/* 2nd & 3rd character */

Does it need to take into account endianness here?

> +	/* If not the 3rd must be the last one */
> +	"addeq	r0,r0,#1\n"
> +
> +"61:\n\t"
> +	"pop	{r4,r5,r6,r7}\n\t"
> +	"subs	r0,r0,#1\n\t"
> +	"bx	lr\n"
> +  );
> +}
> +#endif
> +


Thanks,
Greta