Hi Raji,
Patch looks good in general, some comments below:
On 12-11-2014 12:03, Rajalakshmi Srinivasaraghavan wrote:
> diff --git a/string/strtok_r.c b/string/strtok_r.c
> index fb5ba8d..54c6cbd 100644
> --- a/string/strtok_r.c
> +++ b/string/strtok_r.c
> @@ -25,6 +25,16 @@
> #undef strtok_r
> #undef __strtok_r
>
> +#ifndef STRTOK_R
> +# ifdef weak_alias
> +# define STRTOK_R __strtok_r
> +weak_alias (__strtok_r, strtok_r)
> +# else
> +# define STRTOK_R strtok_r
> +# endif
> +#endif
> +
> +
> #ifndef _LIBC
> /* Get specification. */
> # include "strtok_r.h"
> @@ -43,7 +53,7 @@
> // s = "abc\0-def\0"
> */
> char *
> -__strtok_r (char *s, const char *delim, char **save_ptr)
> +STRTOK_R (char *s, const char *delim, char **save_ptr)
> {
> char *token;
>
> @@ -74,5 +84,4 @@ __strtok_r (char *s, const char *delim, char **save_ptr)
> }
> #ifdef weak_alias
> libc_hidden_def (__strtok_r)
> -weak_alias (__strtok_r, strtok_r)
> #endif
I think we can drop this modification and just redefine 'weak_alias' in strtok_r-ppc64.c
as:
#undef weak_alias
#define weak_alias(name, alias)
> +
> +/*Iniatliaze hash table with Zeroes in double indexed quadword accesses */
> + xxlxor v0, v0, v0 /* prepare for initializing hash */
> +
> + stxvd2x v0, r0, r9 /* initialize 1st quadword */
> + stxvd2x v0, r9, r12
> + stxvd2x v0, r9, r6
> + stxvd2x v0, r9, r8 /* initialize 4th quadword */
> +
> + addi r11, r9, 64 /* r11 is index to hash */
> +
> + stxvd2x v0, r0, r11 /* initialize 5th quadword */
> + stxvd2x v0, r11, r12
> + stxvd2x v0, r11, r6
> + stxvd2x v0, r11, r8 /* initialize 8th quadword */
> +
> + addi r11, r9, 128 /* r11 is index to hash */
> +
> + stxvd2x v0, r0, r11 /* initialize 9th quadword */
> + stxvd2x v0, r11, r12
> + stxvd2x v0, r11, r6
> + stxvd2x v0, r11, r8 /* initialize 12th quadword */
> +
> + addi r11, r9, 192 /* r11 is index to hash */
> +
> + stxvd2x v0, r0, r11 /* initialize 13th quadword */
> + stxvd2x v0, r11, r12
> + stxvd2x v0, r11, r6
> + stxvd2x v0, r11, r8 /* initialize 16th quadword */
I was thinking about this way of cleaning the hash table using 'stxvd2x' and I did some
testing and using some loop unrolling I see we can use 'std' instead without performance
penalty. It would make the algorithm not ISA 2.06/VSX exclusive and remove a lot of IFUNC
code. What do you think?
I am also thinking about changing it to strcspn, strspn, and strpbrk.
@@ -25,6 +25,16 @@
#undef strtok_r
#undef __strtok_r
+#ifndef STRTOK_R
+# ifdef weak_alias
+# define STRTOK_R __strtok_r
+weak_alias (__strtok_r, strtok_r)
+# else
+# define STRTOK_R strtok_r
+# endif
+#endif
+
+
#ifndef _LIBC
/* Get specification. */
# include "strtok_r.h"
@@ -43,7 +53,7 @@
// s = "abc\0-def\0"
*/
char *
-__strtok_r (char *s, const char *delim, char **save_ptr)
+STRTOK_R (char *s, const char *delim, char **save_ptr)
{
char *token;
@@ -74,5 +84,4 @@ __strtok_r (char *s, const char *delim, char **save_ptr)
}
#ifdef weak_alias
libc_hidden_def (__strtok_r)
-weak_alias (__strtok_r, strtok_r)
#endif
@@ -19,7 +19,8 @@ sysdep_routines += memcpy-power7 memcpy-a2 memcpy-power6 memcpy-cell \
strpbrk-power7 strpbrk-ppc64 strncpy-power7 strncpy-ppc64 \
stpncpy-power7 stpncpy-ppc64 strcmp-power7 strcmp-ppc64 \
strcat-power7 strcat-ppc64 memmove-power7 memmove-ppc64 \
- bcopy-ppc64
+ bcopy-ppc64 strtok-power7 strtok-ppc64 strtok_r-power7 \
+ strtok_r-ppc64
CFLAGS-strncase-power7.c += -mcpu=power7 -funroll-loops
CFLAGS-strncase_l-power7.c += -mcpu=power7 -funroll-loops
@@ -328,5 +328,20 @@ __libc_ifunc_impl_list (const char *name, struct libc_ifunc_impl *array,
IFUNC_IMPL_ADD (array, i, strcat, 1,
__strcat_ppc))
+ /* Support sysdeps/powerpc/powerpc64/multiarch/strtok.c. */
+ IFUNC_IMPL (i, name, strtok,
+ IFUNC_IMPL_ADD (array, i, strtok,
+ hwcap & PPC_FEATURE_HAS_VSX,
+ __strtok_power7)
+ IFUNC_IMPL_ADD (array, i, strtok, 1,
+ __strtok_ppc))
+
+ /* Support sysdeps/powerpc/powerpc64/multiarch/strtok_r.c. */
+ IFUNC_IMPL (i, name, strtok_r,
+ IFUNC_IMPL_ADD (array, i, strtok_r,
+ hwcap & PPC_FEATURE_HAS_VSX,
+ __strtok_r_power7)
+ IFUNC_IMPL_ADD (array, i, strtok_r, 1,
+ __strtok_r_ppc))
return i;
}
new file mode 100644
@@ -0,0 +1,40 @@
+/* Optimized strtok implementation for POWER7.
+ Copyright (C) 2014 Free Software Foundation, Inc.
+ This file is part of the GNU C Library.
+
+ The GNU C Library is free software; you can redistribute it and/or
+ modify it under the terms of the GNU Lesser General Public
+ License as published by the Free Software Foundation; either
+ version 2.1 of the License, or (at your option) any later version.
+
+ The GNU C Library is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Lesser General Public License for more details.
+
+ You should have received a copy of the GNU Lesser General Public
+ License along with the GNU C Library; if not, see
+ <http://www.gnu.org/licenses/>. */
+
+#include <sysdep.h>
+
+#undef EALIGN
+#define EALIGN(name, alignt, words) \
+ .section ".text"; \
+ ENTRY_2(__strtok_power7) \
+ .align ALIGNARG(alignt); \
+ EALIGN_W_##words; \
+ BODY_LABEL(__strtok_power7): \
+ cfi_startproc; \
+ LOCALENTRY(__strtok_power7)
+
+#undef END
+#define END(name) \
+ cfi_endproc; \
+ TRACEBACK(__strtok_power7) \
+ END_2(__strtok_power7)
+
+#undef libc_hidden_builtin_def
+#define libc_hidden_builtin_def(name)
+
+#include <sysdeps/powerpc/powerpc64/power7/strtok.S>
new file mode 100644
@@ -0,0 +1,30 @@
+/* Copyright (C) 2014 Free Software Foundation, Inc.
+ This file is part of the GNU C Library.
+
+ The GNU C Library is free software; you can redistribute it and/or
+ modify it under the terms of the GNU Lesser General Public
+ License as published by the Free Software Foundation; either
+ version 2.1 of the License, or (at your option) any later version.
+
+ The GNU C Library is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Lesser General Public License for more details.
+
+ You should have received a copy of the GNU Lesser General Public
+ License along with the GNU C Library; if not, see
+ <http://www.gnu.org/licenses/>. */
+
+#include <string.h>
+
+#define STRTOK __strtok_ppc
+#ifdef SHARED
+
+# undef libc_hidden_builtin_def
+# define libc_hidden_builtin_def(name) \
+ __hidden_ver1 (__strtok_ppc, __GI_strtok, __strtok_ppc);
+#endif
+
+extern __typeof (strtok) __strtok_ppc attribute_hidden;
+
+#include <string/strtok.c>
new file mode 100644
@@ -0,0 +1,31 @@
+/* Multiple versions of strtok. PowerPC64 version.
+ Copyright (C) 2014 Free Software Foundation, Inc.
+ This file is part of the GNU C Library.
+
+ The GNU C Library is free software; you can redistribute it and/or
+ modify it under the terms of the GNU Lesser General Public
+ License as published by the Free Software Foundation; either
+ version 2.1 of the License, or (at your option) any later version.
+
+ The GNU C Library is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Lesser General Public License for more details.
+
+ You should have received a copy of the GNU Lesser General Public
+ License along with the GNU C Library; if not, see
+ <http://www.gnu.org/licenses/>. */
+
+#ifndef NOT_IN_libc
+# include <string.h>
+# include <shlib-compat.h>
+# include "init-arch.h"
+
+extern __typeof (strtok) __strtok_ppc attribute_hidden;
+extern __typeof (strtok) __strtok_power7 attribute_hidden;
+
+libc_ifunc (strtok,
+ (hwcap & PPC_FEATURE_HAS_VSX)
+ ? __strtok_power7
+ : __strtok_ppc);
+#endif
new file mode 100644
@@ -0,0 +1,40 @@
+/* Optimized strtok_r implementation for POWER7.
+ Copyright (C) 2014 Free Software Foundation, Inc.
+ This file is part of the GNU C Library.
+
+ The GNU C Library is free software; you can redistribute it and/or
+ modify it under the terms of the GNU Lesser General Public
+ License as published by the Free Software Foundation; either
+ version 2.1 of the License, or (at your option) any later version.
+
+ The GNU C Library is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Lesser General Public License for more details.
+
+ You should have received a copy of the GNU Lesser General Public
+ License along with the GNU C Library; if not, see
+ <http://www.gnu.org/licenses/>. */
+
+#include <sysdep.h>
+#define USE_AS_STRTOK_R
+#undef EALIGN
+#define EALIGN(name, alignt, words) \
+ .section ".text"; \
+ ENTRY_2(__strtok_r_power7) \
+ .align ALIGNARG(alignt); \
+ EALIGN_W_##words; \
+ BODY_LABEL(__strtok_r_power7): \
+ cfi_startproc; \
+ LOCALENTRY(__strtok_r_power7)
+
+#undef END
+#define END(name) \
+ cfi_endproc; \
+ TRACEBACK(__strtok_r_power7) \
+ END_2(__strtok_r_power7)
+
+#undef libc_hidden_builtin_def
+#define libc_hidden_builtin_def(name)
+
+#include <sysdeps/powerpc/powerpc64/power7/strtok_r.S>
new file mode 100644
@@ -0,0 +1,28 @@
+/* Copyright (C) 2014 Free Software Foundation, Inc.
+ This file is part of the GNU C Library.
+
+ The GNU C Library is free software; you can redistribute it and/or
+ modify it under the terms of the GNU Lesser General Public
+ License as published by the Free Software Foundation; either
+ version 2.1 of the License, or (at your option) any later version.
+
+ The GNU C Library is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Lesser General Public License for more details.
+
+ You should have received a copy of the GNU Lesser General Public
+ License along with the GNU C Library; if not, see
+ <http://www.gnu.org/licenses/>. */
+
+#include <string.h>
+
+#define STRTOK_R __strtok_r_ppc
+#ifdef SHARED
+
+# undef libc_hidden_def
+# define libc_hidden_def(name) \
+ __hidden_ver1 (__strtok_r_ppc, __GI___strtok_r, __strtok_r_ppc);
+#endif
+
+#include <string/strtok_r.c>
new file mode 100644
@@ -0,0 +1,33 @@
+/* Multiple versions of strtok_r. PowerPC64 version.
+ Copyright (C) 2014 Free Software Foundation, Inc.
+ This file is part of the GNU C Library.
+
+ The GNU C Library is free software; you can redistribute it and/or
+ modify it under the terms of the GNU Lesser General Public
+ License as published by the Free Software Foundation; either
+ version 2.1 of the License, or (at your option) any later version.
+
+ The GNU C Library is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Lesser General Public License for more details.
+
+ You should have received a copy of the GNU Lesser General Public
+ License along with the GNU C Library; if not, see
+ <http://www.gnu.org/licenses/>. */
+
+#ifndef NOT_IN_libc
+# include <string.h>
+# include <shlib-compat.h>
+# include "init-arch.h"
+
+extern __typeof (__strtok_r) __strtok_r_ppc attribute_hidden;
+extern __typeof (__strtok_r) __strtok_r_power7 attribute_hidden;
+
+libc_ifunc (__strtok_r,
+ (hwcap & PPC_FEATURE_HAS_VSX)
+ ? __strtok_r_power7
+ : __strtok_r_ppc);
+weak_alias (__strtok_r, strtok_r)
+
+#endif
new file mode 100644
@@ -0,0 +1,215 @@
+/* Optimized strtok implementation for PowerPC64/POWER7.
+
+ Copyright (C) 2014 Free Software Foundation, Inc.
+ This file is part of the GNU C Library.
+
+ The GNU C Library is free software; you can redistribute it and/or
+ modify it under the terms of the GNU Lesser General Public
+ License as published by the Free Software Foundation; either
+ version 2.1 of the License, or (at your option) any later version.
+
+ The GNU C Library is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Lesser General Public License for more details.
+
+ You should have received a copy of the GNU Lesser General Public
+ License along with the GNU C Library; if not, see
+ <http://www.gnu.org/licenses/>. */
+
+/* Performance gains are grabbed through following techniques:
+
+ > hashing of needle.
+ > hashing avoids scanning of duplicate entries in needle
+ across the string.
+ > initializing the hash table with Vector instructions
+ by quadword access.
+ > unrolling when scanning for character in string
+ across hash table. */
+
+/* Algorithm is as below:
+ 1. A empty hash table/dictionary is created comprising of
+ 256 ascii character set
+ 2. When hash entry is found in needle , the hash index
+ is initialized to 1
+ 3. The string is scanned until end and for every character,
+ its corresponding hash index is compared.
+ 4. initial length of string (count) until first hit of
+ accept needle is calculated and moved.(strspn)
+ 5. The string is again scanned until end and for every character,
+ its corresponding hash index is compared.(strpbrk)
+ 6. If hash index is set to 1 for the index of string,
+ set it to null and set the saveptr to point to the next char.
+ 7. Otherwise count is incremented and scanning continues
+ until end of string. */
+
+#include <sysdep.h>
+#ifdef USE_AS_STRTOK_R
+# define FUNC_NAME __strtok_r
+#else
+# define FUNC_NAME strtok
+#endif
+
+ .machine power7
+EALIGN(FUNC_NAME, 4, 0)
+ CALL_MCOUNT 2
+#ifdef USE_AS_STRTOK_R
+ cmpdi cr7, r3, 0 /* Is input null? */
+ bne cr7, L(inputnotNull)
+ ld r3, 0(r5) /* Load from r5 */
+#else
+ addis r5, r2, .LANCHOR0@toc@ha
+ cmpdi cr7, r3, 0 /* Is r3 NULL? */
+ bne cr7, L(inputnotNull)
+ ld r3, .LANCHOR0@toc@l(r5) /* Load from saveptr */
+#endif
+L(inputnotNull):
+ mr r7, r3
+ cmpdi cr7, r3, 0
+ beq cr7, L(returnNULL)
+ lbz r8, 0(r3)
+ cmpdi cr7, r8, 0
+ beq cr7, L(returnNULL)
+
+ lbz r10, 0(r4) /* load r10 with needle (r4) */
+ addi r9, r1, -256 /* r9 is a hash of 256 bytes */
+
+ li r12, 16 /* set r12 = 16 as offset */
+ li r6, 32 /* set r6 = 32 as offset */
+ li r8, 48 /* set r8 = 48 as offset */
+
+/*Iniatliaze hash table with Zeroes in double indexed quadword accesses */
+ xxlxor v0, v0, v0 /* prepare for initializing hash */
+
+ stxvd2x v0, r0, r9 /* initialize 1st quadword */
+ stxvd2x v0, r9, r12
+ stxvd2x v0, r9, r6
+ stxvd2x v0, r9, r8 /* initialize 4th quadword */
+
+ addi r11, r9, 64 /* r11 is index to hash */
+
+ stxvd2x v0, r0, r11 /* initialize 5th quadword */
+ stxvd2x v0, r11, r12
+ stxvd2x v0, r11, r6
+ stxvd2x v0, r11, r8 /* initialize 8th quadword */
+
+ addi r11, r9, 128 /* r11 is index to hash */
+
+ stxvd2x v0, r0, r11 /* initialize 9th quadword */
+ stxvd2x v0, r11, r12
+ stxvd2x v0, r11, r6
+ stxvd2x v0, r11, r8 /* initialize 12th quadword */
+
+ addi r11, r9, 192 /* r11 is index to hash */
+
+ stxvd2x v0, r0, r11 /* initialize 13th quadword */
+ stxvd2x v0, r11, r12
+ stxvd2x v0, r11, r6
+ stxvd2x v0, r11, r8 /* initialize 16th quadword */
+
+ li r8, 1 /* r8=1, marker into hash if found in
+ needle */
+
+ cmpdi cr7, r10, 0 /* accept needle is NULL */
+ beq cr7, L(skipHashing) /* if needle is NULL, skip hashing */
+
+ .p2align 4 /* align section to 16 byte boundary */
+L(hashing):
+ stbx r8, r9, r10 /* update hash with marker for the pivot of
+ the needle */
+ lbzu r10, 1(r4) /* load needle into r10 and update to next */
+ cmpdi cr7, r10, 0 /* if needle is has reached NULL, continue */
+ bne cr7, L(hashing) /* loop to hash the needle */
+
+L(skipHashing):
+ li r10, 0 /* load counter = 0 */
+ b L(beginScan)
+
+ .p2align 4 /* align section to 16 byte boundary */
+L(scanUnroll):
+ lbzx r8, r9, r8 /* load r8 with hash value at index */
+ cmpwi cr7, r8, 0 /* check the hash value */
+ beq cr7, L(next) /* we have hit accept needle */
+
+ lbzu r8, 1(r7) /* load string[1] into r8 */
+ lbzx r8, r9, r8 /* load r8 with hash value at index */
+ cmpwi cr7, r8, 0 /* check the hash value */
+ beq cr7, L(next) /* we have hit accept needle */
+
+ lbzu r8, 1(r7) /* load string[1] into r8 */
+ lbzx r8, r9, r8 /* load r8 with hash value at index */
+ cmpwi cr7, r8, 0 /* check the hash value */
+ beq cr7, L(next) /* we have hit accept needle */
+
+ lbzu r8, 1(r7) /* load string[1] into r8 */
+ lbzx r8, r9, r8 /* load r8 with hash value at index */
+ cmpwi cr7, r8, 0 /* check the hash value */
+ beq cr7,L(next) /* we have hit accept needle */
+
+L(beginScan):
+ lbz r8, 0(r7) /* load string[0] into r8 */
+ cmpdi cr7, r8, 0 /* check if its null */
+ bne cr7, L(scanUnroll) /* continue scanning */
+
+L(next):
+ lbz r8, 0(r7)
+ cmpdi cr7, r8, 0
+ beq cr7, L(returnNULL)
+ mr r3, r7
+ li r8, 1
+ li r10, 0 /* load counter = 0 */
+ stbx r8, r9, r10 /* update hash for NULL */
+ b L(mainloop)
+
+L(unroll):
+ lbzu r8, 1(r7) /* load string[1] into r8 */
+ lbzx r8, r9, r8 /* load r8 with hash value at index */
+ cmpwi r7, r8, 1 /* check the hash */
+ beq cr7, L(found) /* we have hit accept needle */
+ lbzu r8, 1(r7)
+ lbzx r8, r9, r8
+ cmpwi cr7, r8, 1
+ beq cr7, L(found)
+ lbzu r8, 1(r7)
+ lbzx r8, r9, r8
+ cmpwi cr7, r8, 1
+ beq cr7, L(found)
+L(mainloop):
+ lbz r8, 0(r7)
+ lbzx r8, r9, r8
+ cmpwi cr7, r8, 1
+ bne cr7, L(unroll) /* continue scanning */
+
+L(found):
+ lbz r8, 0(r7)
+ cmpdi cr7, r8, 0
+ beq cr7, L(end)
+ li r10, 0
+ stb r10, 0(r7) /* Terminate string */
+ addi r7, r7, 1 /* Store the pointer to the next char */
+L(end):
+#ifdef USE_AS_STRTOK_R
+ std r7, 0(r5) /* Update saveptr */
+#else
+ std r7, .LANCHOR0@toc@l(r5)
+#endif
+ blr /* done */
+L(returnNULL):
+#ifndef USE_AS_STRTOK_R
+ li r7, 0
+#endif
+ li r3, 0 /* return NULL */
+ b L(end)
+END(FUNC_NAME)
+#ifdef USE_AS_STRTOK_R
+libc_hidden_builtin_def (strtok_r)
+#else
+ .section ".bss"
+ .align 3
+ .set .LANCHOR0,. + 0
+ .type olds, @object
+ .size olds, 8
+olds:
+ .zero 8
+libc_hidden_builtin_def (strtok)
+#endif
new file mode 100644
@@ -0,0 +1,24 @@
+/* Optimized strtok_r implementation for PowerPC64/POWER7.
+ Copyright (C) 2014 Free Software Foundation, Inc.
+ This file is part of the GNU C Library.
+
+ The GNU C Library is free software; you can redistribute it and/or
+ modify it under the terms of the GNU Lesser General Public
+ License as published by the Free Software Foundation; either
+ version 2.1 of the License, or (at your option) any later version.
+
+ The GNU C Library is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Lesser General Public License for more details.
+
+ You should have received a copy of the GNU Lesser General Public
+ License along with the GNU C Library; if not, see
+ <http://www.gnu.org/licenses/>. */
+
+#define USE_AS_STRTOK_R
+#include <sysdeps/powerpc/powerpc64/power7/strtok.S>
+
+weak_alias (__strtok_r, strtok_r)
+libc_hidden_def (__strtok_r)
+libc_hidden_builtin_def (strtok_r)