Multiarch optimization for strspn on POWERPC
Commit Message
Hi Adhemerval , fixed it. Please push if OKay.
On Monday 10 March 2014 08:09 PM, Adhemerval Zanella wrote:
> Hi Vidya,
>
> Sorry if I didn't catch it early, but just noted some line are not respecting the 80 column
> requirement from code guidelines, please fix these (example below). Also, I just also noted
> since you are touching 'string/strspn.c' it is worth of cleanup the old C-style (comment
> below). With this change I think it is good to push upstream.
>
>
> On 07-03-2014 07:23, R Vidya wrote:
>> diff --git a/string/strspn.c b/string/strspn.c
>> index 37e8161..557eec5 100644
>> --- a/string/strspn.c
>> +++ b/string/strspn.c
>> @@ -18,11 +18,14 @@
>> #include <string.h>
>>
>> #undef strspn
>> +#ifndef STRSPN
>> +#define STRSPN strspn
>> +#endif
>>
>> /* Return the length of the maximum initial segment
>> of S which contains only characters in ACCEPT. */
>> size_t
>> -strspn (s, accept)
>> +STRSPN (s, accept)
>> const char *s;
>> const char *accept;
>> {
> There is no need on using old K&R style, just convert it to STRSPN (const char *s, const char *accept)
>
>> 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
>> + <http://www.gnu.org/licenses/>. */
>> +
>> +#include <sysdep.h>
>> +
>> +#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 <sysdeps/powerpc/powerpc64/power7/strspn.S>
>> 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
>> + <http://www.gnu.org/licenses/>. */
>> +
>> +#include <string.h>
>> +
>> +#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 <string/strspn.c>
>> 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
>> + <http://www.gnu.org/licenses/>. */
>> +
>> +#if defined SHARED && !defined NOT_IN_libc
>> +# include <string.h>
>> +# include <shlib-compat.h>
>> +# 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..876e9cc
>> --- /dev/null
>> +++ b/sysdeps/powerpc/powerpc64/power7/strspn.S
>> @@ -0,0 +1,148 @@
>> +/* 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
>> + <http://www.gnu.org/licenses/>. */
>> +
>> +/* 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
> Here it is an example of the column limit limit, please break it to fix 80 column.
> Also check for all file, since there are other issues relating to this.
>
>> + 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 <sysdep.h>
>> +
>> +#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)
Comments
Hi Vidya,
Pushed as e65caf1f1df4ecc122da3d30689ee2e8e2bd354f , thanks
On 10-03-2014 14:36, R Vidya wrote:
> Hi Adhemerval , fixed it. Please push if OKay.
>
>
> On Monday 10 March 2014 08:09 PM, Adhemerval Zanella wrote:
>> Hi Vidya,
>>
>> Sorry if I didn't catch it early, but just noted some line are not respecting the 80 column
>> requirement from code guidelines, please fix these (example below). Also, I just also noted
>> since you are touching 'string/strspn.c' it is worth of cleanup the old C-style (comment
>> below). With this change I think it is good to push upstream.
>>
>>
>> On 07-03-2014 07:23, R Vidya wrote:
>>> diff --git a/string/strspn.c b/string/strspn.c
>>> index 37e8161..557eec5 100644
>>> --- a/string/strspn.c
>>> +++ b/string/strspn.c
>>> @@ -18,11 +18,14 @@
>>> #include <string.h>
>>>
>>> #undef strspn
>>> +#ifndef STRSPN
>>> +#define STRSPN strspn
>>> +#endif
>>>
>>> /* Return the length of the maximum initial segment
>>> of S which contains only characters in ACCEPT. */
>>> size_t
>>> -strspn (s, accept)
>>> +STRSPN (s, accept)
>>> const char *s;
>>> const char *accept;
>>> {
>> There is no need on using old K&R style, just convert it to STRSPN (const char *s, const char *accept)
>>
>>> 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
>>> + <http://www.gnu.org/licenses/>. */
>>> +
>>> +#include <sysdep.h>
>>> +
>>> +#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 <sysdeps/powerpc/powerpc64/power7/strspn.S>
>>> 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
>>> + <http://www.gnu.org/licenses/>. */
>>> +
>>> +#include <string.h>
>>> +
>>> +#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 <string/strspn.c>
>>> 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
>>> + <http://www.gnu.org/licenses/>. */
>>> +
>>> +#if defined SHARED && !defined NOT_IN_libc
>>> +# include <string.h>
>>> +# include <shlib-compat.h>
>>> +# 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..876e9cc
>>> --- /dev/null
>>> +++ b/sysdeps/powerpc/powerpc64/power7/strspn.S
>>> @@ -0,0 +1,148 @@
>>> +/* 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
>>> + <http://www.gnu.org/licenses/>. */
>>> +
>>> +/* 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
>> Here it is an example of the column limit limit, please break it to fix 80 column.
>> Also check for all file, since there are other issues relating to this.
>>
>>> + 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 <sysdep.h>
>>> +
>>> +#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)
>
>From 49b84f6296408669abd6d73beb5fe7e2c37fcdba Mon Sep 17 00:00:00 2001
From: Vidya Ranganathan <vidya@linux.vnet.ibm.com>
Date: Mon, 10 Mar 2014 12:20:36 -0400
Subject: [PATCH] Multiarch optimization for strspn() on PowerPC. I have
attached the benchtest output to show the performance improvement.
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.
ChangeLog:
2014-03-04 Vidya Ranganathan <vidya@linux.vnet.ibm.com>
* sysdeps/powerpc/powerpc64/power7/strspn.S: New file: Optimization.
* sysdeps/powerpc/powerpc64/multiarch/strspn.c: New file:
multiarch strspn for PPC64.
* sysdeps/powerpc/powerpc64/multiarch/strspn-ppc64.c: New file
* sysdeps/powerpc/powerpc64/multiarch/strspn-power7.S: New file
* sysdeps/powerpc/powerpc64/multiarch/ifunc-impl-list.c:
(__libc_ifunc_impl_list): Likewise.
* sysdeps/powerpc/powerpc64/multiarch/Makefile: Add strspn
multiarch optimizations
* string/strspn.c (strspn): Using macro to redefine symbol name.
Signed-off-by: Vidya Ranganathan <vidya@linux.vnet.ibm.com>
---
string/strspn.c | 7 +-
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 | 155 +++++++++++++++++++++
7 files changed, 273 insertions(+), 4 deletions(-)
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
@@ -18,13 +18,14 @@
#include <string.h>
#undef strspn
+#ifndef STRSPN
+#define STRSPN strspn
+#endif
/* Return the length of the maximum initial segment
of S which contains only characters in ACCEPT. */
size_t
-strspn (s, accept)
- const char *s;
- const char *accept;
+STRSPN (const char *s, const char *accept)
{
const char *p;
const char *a;
@@ -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
@@ -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;
}
new file mode 100644
@@ -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
+ <http://www.gnu.org/licenses/>. */
+
+#include <sysdep.h>
+
+#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 <sysdeps/powerpc/powerpc64/power7/strspn.S>
new file mode 100644
@@ -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
+ <http://www.gnu.org/licenses/>. */
+
+#include <string.h>
+
+#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 <string/strspn.c>
new file mode 100644
@@ -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
+ <http://www.gnu.org/licenses/>. */
+
+#if defined SHARED && !defined NOT_IN_libc
+# include <string.h>
+# include <shlib-compat.h>
+# 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
new file mode 100644
@@ -0,0 +1,155 @@
+/* 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
+ <http://www.gnu.org/licenses/>. */
+
+/* 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 <sysdep.h>
+
+#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)
--
1.8.3.1