From e65caf1f1df4ecc122da3d30689ee2e8e2bd354f Mon Sep 17 00:00:00 2001 From: Vidya Ranganathan Date: Mon, 10 Mar 2014 12:20:36 -0400 Subject: PowerPC: strspn optimization for PPC64/POWER7 The optimization is achieved by following techniques: > hashing of needle. > hashing avoids scanning of duplicate entries in needle across the string. > initializing the hash table with Vector instructions (VSX) by quadword access. > unrolling when scanning for character in string across hash table. --- sysdeps/powerpc/powerpc64/multiarch/Makefile | 3 +- .../powerpc/powerpc64/multiarch/ifunc-impl-list.c | 8 + .../powerpc/powerpc64/multiarch/strspn-power7.S | 40 +++++ sysdeps/powerpc/powerpc64/multiarch/strspn-ppc64.c | 33 +++++ sysdeps/powerpc/powerpc64/multiarch/strspn.c | 31 ++++ sysdeps/powerpc/powerpc64/power7/strspn.S | 165 +++++++++++++++++++++ 6 files changed, 279 insertions(+), 1 deletion(-) create mode 100644 sysdeps/powerpc/powerpc64/multiarch/strspn-power7.S create mode 100644 sysdeps/powerpc/powerpc64/multiarch/strspn-ppc64.c create mode 100644 sysdeps/powerpc/powerpc64/multiarch/strspn.c create mode 100644 sysdeps/powerpc/powerpc64/power7/strspn.S (limited to 'sysdeps') diff --git a/sysdeps/powerpc/powerpc64/multiarch/Makefile b/sysdeps/powerpc/powerpc64/multiarch/Makefile index a03569e..3e8010c 100644 --- a/sysdeps/powerpc/powerpc64/multiarch/Makefile +++ b/sysdeps/powerpc/powerpc64/multiarch/Makefile @@ -14,7 +14,8 @@ sysdep_routines += memcpy-power7 memcpy-a2 memcpy-power6 memcpy-cell \ wcsrchr-ppc64 wcscpy-power7 wcscpy-power6 wcscpy-ppc64 \ wordcopy-power7 wordcopy-power6 wordcopy-ppc64 \ strcpy-power7 strcpy-ppc64 stpcpy-power7 stpcpy-ppc64 \ - strrchr-power7 strrchr-ppc64 strncat-power7 strncat-ppc64 + strrchr-power7 strrchr-ppc64 strncat-power7 strncat-ppc64 \ + strspn-power7 strspn-ppc64 CFLAGS-strncase-power7.c += -mcpu=power7 -funroll-loops CFLAGS-strncase_l-power7.c += -mcpu=power7 -funroll-loops diff --git a/sysdeps/powerpc/powerpc64/multiarch/ifunc-impl-list.c b/sysdeps/powerpc/powerpc64/multiarch/ifunc-impl-list.c index 11a3bed..20d7918 100644 --- a/sysdeps/powerpc/powerpc64/multiarch/ifunc-impl-list.c +++ b/sysdeps/powerpc/powerpc64/multiarch/ifunc-impl-list.c @@ -254,5 +254,13 @@ __libc_ifunc_impl_list (const char *name, struct libc_ifunc_impl *array, IFUNC_IMPL_ADD (array, i, strncat, 1, __strncat_ppc)) + /* Support sysdeps/powerpc/powerpc64/multiarch/strspn.c. */ + IFUNC_IMPL (i, name, strspn, + IFUNC_IMPL_ADD (array, i, strspn, + hwcap & PPC_FEATURE_HAS_VSX, + __strspn_power7) + IFUNC_IMPL_ADD (array, i, strspn, 1, + __strspn_ppc)) + return i; } diff --git a/sysdeps/powerpc/powerpc64/multiarch/strspn-power7.S b/sysdeps/powerpc/powerpc64/multiarch/strspn-power7.S new file mode 100644 index 0000000..889dfee --- /dev/null +++ b/sysdeps/powerpc/powerpc64/multiarch/strspn-power7.S @@ -0,0 +1,40 @@ +/* Optimized strspn 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 + . */ + +#include + +#undef EALIGN +#define EALIGN(name, alignt, words) \ + .section ".text"; \ + ENTRY_2(__strspn_power7) \ + .align ALIGNARG(alignt); \ + EALIGN_W_##words; \ + BODY_LABEL(__strspn_power7): \ + cfi_startproc; \ + LOCALENTRY(__strspn_power7) + +#undef END +#define END(name) \ + cfi_endproc; \ + TRACEBACK(__strspn_power7) \ + END_2(__strspn_power7) + +#undef libc_hidden_builtin_def +#define libc_hidden_builtin_def(name) + +#include diff --git a/sysdeps/powerpc/powerpc64/multiarch/strspn-ppc64.c b/sysdeps/powerpc/powerpc64/multiarch/strspn-ppc64.c new file mode 100644 index 0000000..d543772 --- /dev/null +++ b/sysdeps/powerpc/powerpc64/multiarch/strspn-ppc64.c @@ -0,0 +1,33 @@ +/* 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 + . */ + +#include + +#define STRSPN __strspn_ppc +#undef weak_alias +#define weak_alias(name, aliasname) \ + extern __typeof (__strspn_ppc) aliasname \ + __attribute__ ((weak, alias ("__strspn_ppc"))); +#if !defined(NOT_IN_libc) && defined(SHARED) +# undef libc_hidden_builtin_def +# define libc_hidden_builtin_def(name) \ + __hidden_ver1(__strspn_ppc, __GI_strspn, __strspn_ppc); +#endif + +extern __typeof (strspn) __strspn_ppc attribute_hidden; + +#include diff --git a/sysdeps/powerpc/powerpc64/multiarch/strspn.c b/sysdeps/powerpc/powerpc64/multiarch/strspn.c new file mode 100644 index 0000000..44945f3 --- /dev/null +++ b/sysdeps/powerpc/powerpc64/multiarch/strspn.c @@ -0,0 +1,31 @@ +/* Multiple versions of strspn. 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 + . */ + +#if defined SHARED && !defined NOT_IN_libc +# include +# include +# include "init-arch.h" + +extern __typeof (strspn) __strspn_ppc attribute_hidden; +extern __typeof (strspn) __strspn_power7 attribute_hidden; + +libc_ifunc (strspn, + (hwcap & PPC_FEATURE_HAS_VSX) + ? __strspn_power7 + : __strspn_ppc); +#endif diff --git a/sysdeps/powerpc/powerpc64/power7/strspn.S b/sysdeps/powerpc/powerpc64/power7/strspn.S new file mode 100644 index 0000000..d587a67 --- /dev/null +++ b/sysdeps/powerpc/powerpc64/power7/strspn.S @@ -0,0 +1,165 @@ +/* Optimized strspn 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 + . */ + +/* size_t [r3] strspn (const char *string [r3], + const char *needleAccept [r4] */ + +/* 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 to be found is set to 0 + 4. If hash index is set to 1 for the index of string, + count is returned. + 5. Otherwise count is incremented and scanning continues + until end of string. */ + +#include + +#undef strspn + + .machine power7 +EALIGN(strspn, 4, 0) + CALL_MCOUNT 2 + + lbz r10, 0(r4) /* load r10 with needle (r4) */ + addi r9, r1, -256 /* r9 is a hash of 256 bytes */ + + li r5, 16 /* set r5 = 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, r5 + 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, r5 + 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, r5 + 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, r5 + 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 /* if we hit marker in hash, we have found + accept needle */ + beq cr7, L(ret1stIndex) /* we have hit accept needle, return the + count */ + + lbz r8, 1(r3) /* load string[1] into r8 */ + addi r10, r10, 4 /* increment counter */ + lbzx r8, r9, r8 /* load r8 with hash value at index */ + cmpwi cr7, r8, 0 /* if we hit marker in hash, we have found + accept needle */ + beq cr7, L(ret2ndIndex) /* we have hit accept needle, return the + count */ + + lbz r8, 2(r3) /* load string[2] into r8 */ + lbzx r8, r9, r8 /* load r8 with hash value at index */ + cmpwi cr7, r8, 0 /* if we hit marker in hash, we have found + accept needle */ + beq cr7, L(ret3rdIndex) /* we have hit accept needle, return the + count */ + + lbz r8, 3(r3) /* load string[3] into r8 */ + lbzx r8, r9, r8 /* load r8 with hash value at index */ + addi r3, r3, 4 /* unroll factor , increment string by 4 */ + cmpwi cr7, r8, 0 /* if we hit marker in hash, we have found + accept needle */ + beq cr7,L(ret4thIndex) /* we have hit accept needle, return the + count */ + +L(beginScan): + lbz r8, 0(r3) /* load string[0] into r8 */ + addi r6, r10, 1 /* place holder for counter + 1 */ + addi r5, r10, 2 /* place holder for counter + 2 */ + addi r4, r10, 3 /* place holder for counter + 3 */ + cmpdi cr7, r8, 0 /* if we hit marker in hash, we have found + accept needle */ + bne cr7, L(scanUnroll) /* continue scanning */ + +L(ret1stIndex): + mr r3, r10 /* update r3 for return */ + blr /* return */ + +L(ret2ndIndex): + mr r3, r6 /* update r3 for return */ + blr /* return */ + +L(ret3rdIndex): + mr r3, r5 /* update r3 for return */ + blr /* return */ + +L(ret4thIndex): + mr r3, r4 /* update r3 for return */ + blr /* done */ +END(strspn) +libc_hidden_builtin_def (strspn) -- cgit v1.1