From 466b03933234017473c12dd1d92bda5e7fe49df7 Mon Sep 17 00:00:00 2001 From: Alan Modra Date: Sat, 17 Aug 2013 18:48:36 +0930 Subject: PowerPC LE memchr and memrchr http://sourceware.org/ml/libc-alpha/2013-08/msg00105.html Like strnlen, memchr and memrchr had a number of defects fixed by this patch as well as adding little-endian support. The first one I noticed was that the entry to the main loop needlessly checked for "are we done yet?" when we know the size is large enough that we can't be done. The second defect I noticed was that the main loop count was wrong, which in turn meant that the small loop needed to handle an extra word. Thirdly, there is nothing to say that the string can't wrap around zero, except of course that we'd normally hit a segfault on trying to read from address zero. Fixing that simplified a number of places: - /* Are we done already? */ - addi r9,r8,8 - cmpld r9,r7 - bge L(null) becomes + cmpld r8,r7 + beqlr However, the exit gets an extra test because I test for being on the last word then if so whether the byte offset is less than the end. Overall, the change is a win. Lastly, memrchr used the wrong cache hint. * sysdeps/powerpc/powerpc64/power7/memchr.S: Replace rlwimi with insrdi. Make better use of reg selection to speed exit slightly. Schedule entry path a little better. Remove useless "are we done" checks on entry to main loop. Handle wrapping around zero address. Correct main loop count. Handle single left-over word from main loop inline rather than by using loop_small. Remove extra word case in loop_small caused by wrong loop count. Add little-endian support. * sysdeps/powerpc/powerpc32/power7/memchr.S: Likewise. * sysdeps/powerpc/powerpc64/power7/memrchr.S: Likewise. Use proper cache hint. * sysdeps/powerpc/powerpc32/power7/memrchr.S: Likewise. * sysdeps/powerpc/powerpc64/power7/rawmemchr.S: Add little-endian support. Avoid rlwimi. * sysdeps/powerpc/powerpc32/power7/rawmemchr.S: Likewise. --- sysdeps/powerpc/powerpc32/power7/memchr.S | 185 ++++++++++++-------------- sysdeps/powerpc/powerpc32/power7/memrchr.S | 187 +++++++++++++++------------ sysdeps/powerpc/powerpc32/power7/rawmemchr.S | 17 ++- 3 files changed, 200 insertions(+), 189 deletions(-) (limited to 'sysdeps/powerpc/powerpc32/power7') diff --git a/sysdeps/powerpc/powerpc32/power7/memchr.S b/sysdeps/powerpc/powerpc32/power7/memchr.S index 369e5e0483..85754f3f17 100644 --- a/sysdeps/powerpc/powerpc32/power7/memchr.S +++ b/sysdeps/powerpc/powerpc32/power7/memchr.S @@ -25,107 +25,111 @@ ENTRY (__memchr) CALL_MCOUNT dcbt 0,r3 clrrwi r8,r3,2 - rlwimi r4,r4,8,16,23 - rlwimi r4,r4,16,0,15 + insrdi r4,r4,8,48 add r7,r3,r5 /* Calculate the last acceptable address. */ + insrdi r4,r4,16,32 cmplwi r5,16 + li r9, -1 + rlwinm r6,r3,3,27,28 /* Calculate padding. */ + addi r7,r7,-1 +#ifdef __LITTLE_ENDIAN__ + slw r9,r9,r6 +#else + srw r9,r9,r6 +#endif ble L(small_range) - cmplw cr7,r3,r7 /* Compare the starting address (r3) with the - ending address (r7). If (r3 >= r7), the size - passed in is zero or negative. */ - ble cr7,L(proceed) - - li r7,-1 /* Artificially set our ending address (r7) - such that we will exit early. */ -L(proceed): - rlwinm r6,r3,3,27,28 /* Calculate padding. */ - cmpli cr6,r6,0 /* cr6 == Do we have padding? */ lwz r12,0(r8) /* Load word from memory. */ - cmpb r10,r12,r4 /* Check for BYTEs in WORD1. */ - beq cr6,L(proceed_no_padding) - slw r10,r10,r6 - srw r10,r10,r6 -L(proceed_no_padding): - cmplwi cr7,r10,0 /* If r10 == 0, no BYTEs have been found. */ + cmpb r3,r12,r4 /* Check for BYTEs in WORD1. */ + and r3,r3,r9 + clrlwi r5,r7,30 /* Byte count - 1 in last word. */ + clrrwi r7,r7,2 /* Address of last word. */ + cmplwi cr7,r3,0 /* If r3 == 0, no BYTEs have been found. */ bne cr7,L(done) - /* Are we done already? */ - addi r9,r8,4 - cmplw cr6,r9,r7 - bge cr6,L(null) - mtcrf 0x01,r8 /* Are we now aligned to a doubleword boundary? If so, skip to the main loop. Otherwise, go through the alignment code. */ - bt 29,L(loop_setup) /* Handle WORD2 of pair. */ lwzu r12,4(r8) - cmpb r10,r12,r4 - cmplwi cr7,r10,0 + cmpb r3,r12,r4 + cmplwi cr7,r3,0 bne cr7,L(done) - /* Are we done already? */ - addi r9,r8,4 - cmplw cr6,r9,r7 - bge cr6,L(null) - L(loop_setup): - sub r5,r7,r9 - srwi r6,r5,3 /* Number of loop iterations. */ + /* The last word we want to read in the loop below is the one + containing the last byte of the string, ie. the word at + (s + size - 1) & ~3, or r7. The first word read is at + r8 + 4, we read 2 * cnt words, so the last word read will + be at r8 + 4 + 8 * cnt - 4. Solving for cnt gives + cnt = (r7 - r8) / 8 */ + sub r6,r7,r8 + srwi r6,r6,3 /* Number of loop iterations. */ mtctr r6 /* Setup the counter. */ - b L(loop) - /* Main loop to look for BYTE backwards in the string. Since - it's a small loop (< 8 instructions), align it to 32-bytes. */ - .p2align 5 + + /* Main loop to look for BYTE in the string. Since + it's a small loop (8 instructions), align it to 32-bytes. */ + .align 5 L(loop): /* Load two words, compare and merge in a single register for speed. This is an attempt to speed up the byte-checking process for bigger strings. */ lwz r12,4(r8) lwzu r11,8(r8) - cmpb r10,r12,r4 + cmpb r3,r12,r4 cmpb r9,r11,r4 - or r5,r9,r10 /* Merge everything in one word. */ - cmplwi cr7,r5,0 + or r6,r9,r3 /* Merge everything in one word. */ + cmplwi cr7,r6,0 bne cr7,L(found) bdnz L(loop) - /* We're here because the counter reached 0, and that means we - didn't have any matches for BYTE in the whole range. */ - subi r11,r7,4 - cmplw cr6,r8,r11 - blt cr6,L(loop_small) - b L(null) + /* We may have one more dword to read. */ + cmplw r8,r7 + beqlr + + lwzu r12,4(r8) + cmpb r3,r12,r4 + cmplwi cr6,r3,0 + bne cr6,L(done) + blr + .align 4 +L(found): /* OK, one (or both) of the words contains BYTE. Check the first word and decrement the address in case the first word really contains BYTE. */ - .align 4 -L(found): - cmplwi cr6,r10,0 + cmplwi cr6,r3,0 addi r8,r8,-4 bne cr6,L(done) /* BYTE must be in the second word. Adjust the address - again and move the result of cmpb to r10 so we can calculate the + again and move the result of cmpb to r3 so we can calculate the pointer. */ - mr r10,r9 + mr r3,r9 addi r8,r8,4 - /* r10 has the output of the cmpb instruction, that is, it contains + /* r3 has the output of the cmpb instruction, that is, it contains 0xff in the same position as BYTE in the original word from the string. Use that to calculate the pointer. We need to make sure BYTE is *before* the end of the range. */ L(done): - cntlzw r0,r10 /* Count leading zeroes before the match. */ - srwi r0,r0,3 /* Convert leading zeroes to bytes. */ +#ifdef __LITTLE_ENDIAN__ + addi r0,r3,-1 + andc r0,r0,r3 + popcntw r0,r0 /* Count trailing zeros. */ +#else + cntlzw r0,r3 /* Count leading zeros before the match. */ +#endif + cmplw r8,r7 /* Are we on the last word? */ + srwi r0,r0,3 /* Convert leading/trailing zeros to bytes. */ add r3,r8,r0 - cmplw r3,r7 - bge L(null) + cmplw cr7,r0,r5 /* If on the last dword, check byte offset. */ + bnelr + blelr cr7 + li r3,0 blr .align 4 @@ -137,67 +141,42 @@ L(null): .align 4 L(small_range): cmplwi r5,0 - rlwinm r6,r3,3,27,28 /* Calculate padding. */ - beq L(null) /* This branch is for the cmplwi r5,0 above */ + beq L(null) lwz r12,0(r8) /* Load word from memory. */ - cmplwi cr6,r6,0 /* cr6 == Do we have padding? */ - cmpb r10,r12,r4 /* Check for BYTE in DWORD1. */ - beq cr6,L(small_no_padding) - slw r10,r10,r6 - srw r10,r10,r6 -L(small_no_padding): - cmplwi cr7,r10,0 + cmpb r3,r12,r4 /* Check for BYTE in DWORD1. */ + and r3,r3,r9 + cmplwi cr7,r3,0 + clrlwi r5,r7,30 /* Byte count - 1 in last word. */ + clrrwi r7,r7,2 /* Address of last word. */ + cmplw r8,r7 /* Are we done already? */ bne cr7,L(done) + beqlr - /* Are we done already? */ - addi r9,r8,4 - cmplw r9,r7 - bge L(null) - -L(loop_small): /* loop_small has been unrolled. */ lwzu r12,4(r8) - cmpb r10,r12,r4 - addi r9,r8,4 - cmplwi cr6,r10,0 - cmplw r9,r7 + cmpb r3,r12,r4 + cmplwi cr6,r3,0 + cmplw r8,r7 bne cr6,L(done) - bge L(null) + beqlr lwzu r12,4(r8) - cmpb r10,r12,r4 - addi r9,r8,4 - cmplwi cr6,r10,0 - cmplw r9,r7 + cmpb r3,r12,r4 + cmplwi cr6,r3,0 + cmplw r8,r7 bne cr6,L(done) - bge L(null) + beqlr lwzu r12,4(r8) - cmpb r10,r12,r4 - addi r9,r8,4 - cmplwi cr6,r10,0 - cmplw r9,r7 + cmpb r3,r12,r4 + cmplwi cr6,r3,0 + cmplw r8,r7 bne cr6,L(done) - bge L(null) + beqlr lwzu r12,4(r8) - cmpb r10,r12,r4 - addi r9,r8,4 - cmplwi cr6,r10,0 - cmplw r9,r7 + cmpb r3,r12,r4 + cmplwi cr6,r3,0 bne cr6,L(done) - bge L(null) - - /* For most cases we will never get here. Under some combinations of - padding + length there is a leftover word that still needs to be - checked. */ - lwzu r12,4(r8) - cmpb r10,r12,r4 - addi r9,r8,4 - cmplwi cr6,r10,0 - bne cr6,L(done) - - /* save a branch and exit directly */ - li r3,0 blr END (__memchr) diff --git a/sysdeps/powerpc/powerpc32/power7/memrchr.S b/sysdeps/powerpc/powerpc32/power7/memrchr.S index defd832b0a..9601aa7997 100644 --- a/sysdeps/powerpc/powerpc32/power7/memrchr.S +++ b/sysdeps/powerpc/powerpc32/power7/memrchr.S @@ -23,117 +23,131 @@ .machine power7 ENTRY (__memrchr) CALL_MCOUNT - dcbt 0,r3 - mr r7,r3 - add r3,r7,r5 /* Calculate the last acceptable address. */ - cmplw cr7,r3,r7 /* Is the address equal or less than r3? */ + add r7,r3,r5 /* Calculate the last acceptable address. */ + neg r0,r7 + addi r7,r7,-1 + mr r10,r3 + clrrwi r6,r7,7 + li r9,3<<5 + dcbt r9,r6,16 /* Stream hint, decreasing addresses. */ /* Replicate BYTE to word. */ - rlwimi r4,r4,8,16,23 - rlwimi r4,r4,16,0,15 - bge cr7,L(proceed) - - li r3,-1 /* Make r11 the biggest if r4 <= 0. */ -L(proceed): + rldimi r4,r4,8,48 + rldimi r4,r4,16,32 li r6,-4 - addi r9,r3,-1 - clrrwi r8,r9,2 - addi r8,r8,4 - neg r0,r3 + li r9,-1 rlwinm r0,r0,3,27,28 /* Calculate padding. */ - + clrrwi r8,r7,2 + srw r9,r9,r0 cmplwi r5,16 + clrrwi r0,r10,2 ble L(small_range) - lwbrx r12,r8,r6 /* Load reversed word from memory. */ - cmpb r10,r12,r4 /* Check for BYTE in WORD1. */ - slw r10,r10,r0 - srw r10,r10,r0 - cmplwi cr7,r10,0 /* If r10 == 0, no BYTEs have been found. */ +#ifdef __LITTLE_ENDIAN__ + lwzx r12,0,r8 +#else + lwbrx r12,0,r8 /* Load reversed word from memory. */ +#endif + cmpb r3,r12,r4 /* Check for BYTE in WORD1. */ + and r3,r3,r9 + cmplwi cr7,r3,0 /* If r3 == 0, no BYTEs have been found. */ bne cr7,L(done) - /* Are we done already? */ - addi r9,r8,-4 - cmplw cr6,r9,r7 - ble cr6,L(null) - mtcrf 0x01,r8 /* Are we now aligned to a doubleword boundary? If so, skip to the main loop. Otherwise, go through the alignment code. */ - mr r8,r9 - bt 29,L(loop_setup) + bf 29,L(loop_setup) /* Handle WORD2 of pair. */ +#ifdef __LITTLE_ENDIAN__ + lwzx r12,r8,r6 +#else lwbrx r12,r8,r6 - cmpb r10,r12,r4 - cmplwi cr7,r10,0 - bne cr7,L(done) - - /* Are we done already? */ +#endif addi r8,r8,-4 - cmplw cr6,r8,r7 - ble cr6,L(null) + cmpb r3,r12,r4 + cmplwi cr7,r3,0 + bne cr7,L(done) L(loop_setup): - li r0,-8 - sub r5,r8,r7 - srwi r9,r5,3 /* Number of loop iterations. */ + /* The last word we want to read in the loop below is the one + containing the first byte of the string, ie. the word at + s & ~3, or r0. The first word read is at r8 - 4, we + read 2 * cnt words, so the last word read will be at + r8 - 4 - 8 * cnt + 4. Solving for cnt gives + cnt = (r8 - r0) / 8 */ + sub r5,r8,r0 + addi r8,r8,-4 + srwi r9,r5,3 /* Number of loop iterations. */ mtctr r9 /* Setup the counter. */ - b L(loop) - /* Main loop to look for BYTE backwards in the string. Since it's a - small loop (< 8 instructions), align it to 32-bytes. */ - .p2align 5 + + /* Main loop to look for BYTE backwards in the string. + FIXME: Investigate whether 32 byte align helps with this + 9 instruction loop. */ + .align 5 L(loop): /* Load two words, compare and merge in a single register for speed. This is an attempt to speed up the byte-checking process for bigger strings. */ - lwbrx r12,r8,r6 - lwbrx r11,r8,r0 - addi r8,r8,-4 - cmpb r10,r12,r4 +#ifdef __LITTLE_ENDIAN__ + lwzx r12,0,r8 + lwzx r11,r8,r6 +#else + lwbrx r12,0,r8 + lwbrx r11,r8,r6 +#endif + cmpb r3,r12,r4 cmpb r9,r11,r4 - or r5,r9,r10 /* Merge everything in one word. */ + or r5,r9,r3 /* Merge everything in one word. */ cmplwi cr7,r5,0 bne cr7,L(found) - addi r8,r8,-4 + addi r8,r8,-8 bdnz L(loop) - /* We're here because the counter reached 0, and that means we - didn't have any matches for BYTE in the whole range. Just return - the original range. */ - addi r8,r8,4 - cmplw cr6,r8,r7 - bgt cr6,L(loop_small) - b L(null) - /* OK, one (or both) of the words contains BYTE. Check - the first word and decrement the address in case the first - word really contains BYTE. */ + /* We may have one more word to read. */ + cmplw r8,r0 + bnelr + +#ifdef __LITTLE_ENDIAN__ + lwzx r12,0,r8 +#else + lwbrx r12,0,r8 +#endif + cmpb r3,r12,r4 + cmplwi cr7,r3,0 + bne cr7,L(done) + blr + .align 4 L(found): - cmplwi cr6,r10,0 - addi r8,r8,4 + /* OK, one (or both) of the words contains BYTE. Check + the first word. */ + cmplwi cr6,r3,0 bne cr6,L(done) /* BYTE must be in the second word. Adjust the address - again and move the result of cmpb to r10 so we can calculate the + again and move the result of cmpb to r3 so we can calculate the pointer. */ - mr r10,r9 + mr r3,r9 addi r8,r8,-4 - /* r10 has the output of the cmpb instruction, that is, it contains + /* r3 has the output of the cmpb instruction, that is, it contains 0xff in the same position as BYTE in the original word from the string. Use that to calculate the pointer. We need to make sure BYTE is *before* the end of the range. */ L(done): - cntlzw r0,r10 /* Count leading zeroes before the match. */ - srwi r6,r0,3 /* Convert leading zeroes to bytes. */ - addi r0,r6,1 + cntlzw r9,r3 /* Count leading zeros before the match. */ + cmplw r8,r0 /* Are we on the last word? */ + srwi r6,r9,3 /* Convert leading zeros to bytes. */ + addi r0,r6,-3 sub r3,r8,r0 - cmplw r3,r7 - blt L(null) + cmplw cr7,r3,r10 + bnelr + bgelr cr7 + li r3,0 blr .align 4 @@ -147,28 +161,35 @@ L(small_range): cmplwi r5,0 beq L(null) - lwbrx r12,r8,r6 /* Load reversed word from memory. */ - cmpb r10,r12,r4 /* Check for null bytes in WORD1. */ - slw r10,r10,r0 - srw r10,r10,r0 - cmplwi cr7,r10,0 +#ifdef __LITTLE_ENDIAN__ + lwzx r12,0,r8 +#else + lwbrx r12,0,r8 /* Load reversed word from memory. */ +#endif + cmpb r3,r12,r4 /* Check for BYTE in WORD1. */ + and r3,r3,r9 + cmplwi cr7,r3,0 bne cr7,L(done) + /* Are we done already? */ + cmplw r8,r0 addi r8,r8,-4 - cmplw r8,r7 - ble L(null) - b L(loop_small) + beqlr - .p2align 5 + .align 5 L(loop_small): - lwbrx r12,r8,r6 - cmpb r10,r12,r4 - cmplwi cr6,r10,0 - bne cr6,L(done) +#ifdef __LITTLE_ENDIAN__ + lwzx r12,0,r8 +#else + lwbrx r12,0,r8 +#endif + cmpb r3,r12,r4 + cmplw r8,r0 + cmplwi cr7,r3,0 + bne cr7,L(done) addi r8,r8,-4 - cmplw r8,r7 - ble L(null) - b L(loop_small) + bne L(loop_small) + blr END (__memrchr) weak_alias (__memrchr, memrchr) diff --git a/sysdeps/powerpc/powerpc32/power7/rawmemchr.S b/sysdeps/powerpc/powerpc32/power7/rawmemchr.S index a80c74a092..c2d8c4b7be 100644 --- a/sysdeps/powerpc/powerpc32/power7/rawmemchr.S +++ b/sysdeps/powerpc/powerpc32/power7/rawmemchr.S @@ -27,16 +27,21 @@ ENTRY (__rawmemchr) clrrwi r8,r3,2 /* Align the address to word boundary. */ /* Replicate byte to word. */ - rlwimi r4,r4,8,16,23 - rlwimi r4,r4,16,0,15 + rldimi r4,r4,8,48 + rldimi r4,r4,16,32 /* Now r4 has a word of c bytes. */ rlwinm r6,r3,3,27,28 /* Calculate padding. */ lwz r12,0(r8) /* Load word from memory. */ cmpb r5,r12,r4 /* Compare each byte against c byte. */ +#ifdef __LITTLE_ENDIAN__ + srw r5,r5,r6 + slw r5,r5,r6 +#else slw r5,r5,r6 /* Move left to discard ignored bits. */ srw r5,r5,r6 /* Bring the bits back as zeros. */ +#endif cmpwi cr7,r5,0 /* If r5 == 0, no c bytes have been found. */ bne cr7,L(done) @@ -90,8 +95,14 @@ L(loop): word from the string. Use that fact to find out what is the position of the byte inside the string. */ L(done): +#ifdef __LITTLE_ENDIAN__ + addi r0,r5,-1 + andc r0,r0,r5 + popcntw r0,r0 +#else cntlzw r0,r5 /* Count leading zeros before the match. */ - srwi r0,r0,3 /* Convert leading zeroes to bytes. */ +#endif + srwi r0,r0,3 /* Convert leading zeros to bytes. */ add r3,r8,r0 /* Return address of the matching char. */ blr END (__rawmemchr) -- cgit v1.2.1