1 /* Optimized strcmp implementation for PowerPC64.
2 Copyright (C) 2003, 2006 Free Software Foundation, Inc.
3 This file is part of the GNU C Library.
5 The GNU C Library is free software; you can redistribute it and/or
6 modify it under the terms of the GNU Lesser General Public
7 License as published by the Free Software Foundation; either
8 version 2.1 of the License, or (at your option) any later version.
10 The GNU C Library is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 Lesser General Public License for more details.
15 You should have received a copy of the GNU Lesser General Public
16 License along with the GNU C Library; if not, write to the Free
17 Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston MA
24 /* int [r3] memcmp (const char *s1 [r3], const char *s2 [r4], size_t size [r5]) */
27 EALIGN (BP_SYM(memcmp), 4, 0)
32 #define rSTR1 r3 /* first string arg */
33 #define rSTR2 r4 /* second string arg */
34 #define rN r5 /* max string length */
35 /* Note: The Bounded pointer support in this code is broken. This code
36 was inherited from PPC32 and and that support was never completed.
37 Current PPC gcc does not support -fbounds-check or -fbounded-pointers. */
38 #define rWORD1 r6 /* current word in s1 */
39 #define rWORD2 r7 /* current word in s2 */
40 #define rWORD3 r8 /* next word in s1 */
41 #define rWORD4 r9 /* next word in s2 */
42 #define rWORD5 r10 /* next word in s1 */
43 #define rWORD6 r11 /* next word in s2 */
44 #define rBITDIF r12 /* bits that differ in s1 & s2 words */
45 #define rWORD7 r30 /* next word in s1 */
46 #define rWORD8 r31 /* next word in s2 */
48 xor rTMP, rSTR2, rSTR1
51 clrldi. rTMP, rTMP, 61
52 clrldi rBITDIF, rSTR1, 61
53 cmpldi cr5, rBITDIF, 0
54 beq- cr6, L(zeroLength)
57 /* If less than 8 bytes or not aligned, use the unalligned
59 blt cr1, L(bytealigned)
63 cfi_offset(rWORD7,-16)
65 /* At this point we know both strings have the same alignment and the
66 compare length is at least 8 bytes. rBITDIF containes the low order
67 3 bits of rSTR1 and cr5 contains the result of the logical compare
68 of rBITDIF to 0. If rBITDIF == 0 then we are already double word
69 aligned and can perform the DWaligned loop.
71 Otherwise we know the two strings have the same alignment (but not
72 yet DW). So we can force the string addresses to the next lower DW
73 boundary and special case this first DW word using shift left to
74 ellimiate bits preceeding the first byte. Since we want to join the
75 normal (DWaligned) compare loop, starting at the second double word,
76 we need to adjust the length (rN) and special case the loop
77 versioning for the first DW. This insures that the loop count is
78 correct and the first DW (shifted) is in the expected resister pair. */
81 clrrdi rSTR1, rSTR1, 3
82 clrrdi rSTR2, rSTR2, 3
86 srdi rTMP, rN, 5 /* Divide by 32 */
87 andi. rBITDIF, rN, 24 /* Get the DW remainder */
90 cmpldi cr1, rBITDIF, 16
94 mtctr rTMP /* Power4 wants mtctr 1st in dispatch group */
101 sld rWORD5, rWORD1, r11
102 sld rWORD6, rWORD2, r11
103 cmpld cr5, rWORD5, rWORD6
105 /* Do something useful in this cycle since we have to branch anyway. */
108 cmpld cr0, rWORD1, rWORD2
110 /* Remainder is 16 */
113 sld rWORD5, rWORD1, r11
114 sld rWORD6, rWORD2, r11
115 cmpld cr6, rWORD5, rWORD6
117 /* Do something useful in this cycle since we have to branch anyway. */
120 cmpld cr5, rWORD7, rWORD8
122 /* Remainder is 24 */
125 sld rWORD3, rWORD1, r11
126 sld rWORD4, rWORD2, r11
127 cmpld cr1, rWORD3, rWORD4
129 /* Count is a multiple of 32, remainder is 0 */
132 mtctr rTMP /* Power4 wants mtctr 1st in dispatch group */
133 sld rWORD1, rWORD1, r11
134 sld rWORD2, rWORD2, r11
135 cmpld cr0, rWORD1, rWORD2
138 /* At this point we know both strings are double word aligned and the
139 compare length is at least 8 bytes. */
142 andi. rBITDIF, rN, 24 /* Get the DW remainder */
143 srdi rTMP, rN, 5 /* Divide by 32 */
144 cmpldi cr1, rBITDIF, 16
154 mtctr rTMP /* Power4 wants mtctr 1st in dispatch group */
155 /* Normally we'd use rWORD7/rWORD8 here, but since we might exit early
156 (8-15 byte compare), we want to use only volitile registers. This
157 means we can avoid restoring non-volitile registers since we did not
158 change any on the early exit path. The key here is the non-early
159 exit path only cares about the condition code (cr5), not about which
160 register pair was used. */
163 cmpld cr5, rWORD5, rWORD6
167 cmpld cr0, rWORD1, rWORD2
171 cmpld cr1, rWORD3, rWORD4
174 cmpld cr6, rWORD5, rWORD6
178 ldu rWORD7, 32(rSTR1)
179 ldu rWORD8, 32(rSTR2)
181 cmpld cr5, rWORD7, rWORD8
190 subfic rN, r12, 64 /* Shift count is 64 - (rN * 8). */
195 /* Remainder is 16 */
198 mtctr rTMP /* Power4 wants mtctr 1st in dispatch group */
201 cmpld cr6, rWORD5, rWORD6
205 cmpld cr5, rWORD7, rWORD8
209 cmpld cr0, rWORD1, rWORD2
212 cmpld cr1, rWORD3, rWORD4
218 /* Again we are on a early exit path (16-23 byte compare), we want to
219 only use volitile registers and avoid restoring non-volitile
225 cmpld cr5, rWORD3, rWORD4
231 subfic rN, r12, 64 /* Shift count is 64 - (rN * 8). */
236 /* Remainder is 24 */
239 mtctr rTMP /* Power4 wants mtctr 1st in dispatch group */
242 cmpld cr1, rWORD3, rWORD4
246 cmpld cr6, rWORD5, rWORD6
250 cmpld cr5, rWORD7, rWORD8
253 cmpld cr0, rWORD1, rWORD2
254 addi rSTR1, rSTR1, 16
255 addi rSTR2, rSTR2, 16
259 /* Again we are on a early exit path (24-31 byte compare), we want to
260 only use volitile registers and avoid restoring non-volitile
266 cmpld cr5, rWORD1, rWORD2
269 addi rSTR1, rSTR1, 16
270 addi rSTR2, rSTR2, 16
272 subfic rN, r12, 64 /* Shift count is 64 - (rN * 8). */
278 /* Count is a multiple of 32, remainder is 0 */
281 mtctr rTMP /* Power4 wants mtctr 1st in dispatch group */
284 cmpld cr0, rWORD1, rWORD2
288 cmpld cr1, rWORD3, rWORD4
291 cmpld cr6, rWORD5, rWORD6
292 ldu rWORD7, 24(rSTR1)
293 ldu rWORD8, 24(rSTR2)
294 cmpld cr5, rWORD7, rWORD8
297 bdz- L(d24) /* Adjust CTR as we start with +4 */
298 /* This is the primary loop */
303 cmpld cr1, rWORD3, rWORD4
308 cmpld cr6, rWORD5, rWORD6
313 cmpld cr5, rWORD7, rWORD8
316 ldu rWORD7, 32(rSTR1)
317 ldu rWORD8, 32(rSTR2)
319 cmpld cr0, rWORD1, rWORD2
323 cmpld cr1, rWORD3, rWORD4
325 cmpld cr6, rWORD5, rWORD6
327 cmpld cr5, rWORD7, rWORD8
340 subfic rN, r12, 64 /* Shift count is 64 - (rN * 8). */
342 /* At this point we have a remainder of 1 to 7 bytes to compare. Since
343 we are aligned it is safe to load the whole double word, and use
344 shift right double to elliminate bits beyond the compare length. */
348 srd rWORD1, rWORD1, rN
349 srd rWORD2, rWORD2, rN
350 cmpld cr5, rWORD1, rWORD2
390 mtctr rN /* Power4 wants mtctr 1st in dispatch group */
391 beq- cr6, L(zeroLength)
393 /* We need to prime this loop. This loop is swing modulo scheduled
394 to avoid pipe delays. The dependent instruction latencies (load to
395 compare to conditional branch) is 2 to 3 cycles. In this loop each
396 dispatch group ends in a branch and takes 1 cycle. Effectively
397 the first iteration of the loop only serves to load operands and
398 branches based on compares are delayed until the next loop.
400 So we must precondition some registers and condition codes so that
401 we don't exit the loop early on the first iteration. */
406 cmpld cr0, rWORD1, rWORD2
410 cmpld cr1, rWORD3, rWORD4
411 lbzu rWORD5, 2(rSTR1)
412 lbzu rWORD6, 2(rSTR2)
416 lbzu rWORD1, 1(rSTR1)
417 lbzu rWORD2, 1(rSTR2)
420 cmpld cr6, rWORD5, rWORD6
423 lbzu rWORD3, 1(rSTR1)
424 lbzu rWORD4, 1(rSTR2)
427 cmpld cr0, rWORD1, rWORD2
430 lbzu rWORD5, 1(rSTR1)
431 lbzu rWORD6, 1(rSTR2)
434 cmpld cr1, rWORD3, rWORD4
437 /* We speculatively loading bytes before we have tested the previous
438 bytes. But we must avoid overrunning the length (in the ctr) to
439 prevent these speculative loads from causing a segfault. In this
440 case the loop will exit early (before the all pending bytes are
441 tested. In this case we must complete the pending operations
478 sub rRTN, rWORD5, rWORD6
484 sub rRTN, rWORD3, rWORD4
488 sub rRTN, rWORD1, rWORD2
499 /* At this point we know the strings have different alignment and the
500 compare length is at least 8 bytes. rBITDIF containes the low order
501 3 bits of rSTR1 and cr5 contains the result of the logical compare
502 of rBITDIF to 0. If rBITDIF == 0 then rStr1 is double word
503 aligned and can perform the DWunaligned loop.
505 Otherwise we know that rSTR1 is not aready DW aligned yet.
506 So we can force the string addresses to the next lower DW
507 boundary and special case this first DW word using shift left to
508 ellimiate bits preceeding the first byte. Since we want to join the
509 normal (DWaligned) compare loop, starting at the second double word,
510 we need to adjust the length (rN) and special case the loop
511 versioning for the first DW. This insures that the loop count is
512 correct and the first DW (shifted) is in the expected resister pair. */
513 #define rSHL r29 /* Unaligned shift left count. */
514 #define rSHR r28 /* Unaligned shift right count. */
515 #define rB r27 /* Left rotation temp for rWORD2. */
516 #define rD r26 /* Left rotation temp for rWORD4. */
517 #define rF r25 /* Left rotation temp for rWORD6. */
518 #define rH r24 /* Left rotation temp for rWORD8. */
519 #define rA r0 /* Right rotation temp for rWORD2. */
520 #define rC r12 /* Right rotation temp for rWORD4. */
521 #define rE r0 /* Right rotation temp for rWORD6. */
522 #define rG r12 /* Right rotation temp for rWORD8. */
526 clrldi rSHL, rSTR2, 61
527 beq- cr6, L(duzeroLength)
530 beq cr5, L(DWunaligned)
533 /* Adjust the logical start of rSTR2 ro compensate for the extra bits
534 in the 1st rSTR1 DW. */
535 sub r27, rSTR2, rBITDIF
536 /* But do not attempt to address the DW before that DW that contains
537 the actual start of rSTR2. */
538 clrrdi rSTR2, rSTR2, 3
541 /* Compute the leaft/right shift counts for the unalign rSTR2,
542 compensating for the logical (DW aligned) start of rSTR1. */
544 clrrdi rSTR1, rSTR1, 3
548 cmpld cr5, r27, rSTR2
553 subfic rSHR, rSHL, 64
554 srdi rTMP, rN, 5 /* Divide by 32 */
555 andi. rBITDIF, rN, 24 /* Get the DW remainder */
556 /* We normally need to load 2 DWs to start the unaligned rSTR2, but in
557 this special case those bits may be discarded anyway. Also we
558 must avoid loading a DW where none of the bits are part of rSTR2 as
559 this may cross a page boundary and cause a page fault. */
564 sld rWORD8, rWORD8, rSHL
569 cmpldi cr1, rBITDIF, 16
574 mtctr rTMP /* Power4 wants mtctr 1st in dispatch group */
575 or rWORD8, rG, rWORD8
583 sld rWORD7, rWORD1, r11
584 sld rWORD8, rWORD8, r11
586 /* At this point we exit early with the first double word compare
587 complete and remainder of 0 to 7 bytes. See L(du14) for details on
588 how we handle the remaining bytes. */
589 cmpld cr5, rWORD7, rWORD8
599 /* Remainder is 16 */
603 sld rWORD5, rWORD1, r11
604 sld rWORD6, rWORD8, r11
606 /* Remainder is 24 */
610 sld rWORD3, rWORD1, r11
611 sld rWORD4, rWORD8, r11
613 /* Count is a multiple of 32, remainder is 0 */
616 mtctr rTMP /* Power4 wants mtctr 1st in dispatch group */
617 or rWORD8, rG, rWORD8
619 sld rWORD1, rWORD1, r11
620 sld rWORD2, rWORD8, r11
623 /* At this point we know rSTR1 is double word aligned and the
624 compare length is at least 8 bytes. */
629 clrrdi rSTR2, rSTR2, 3
632 srdi rTMP, rN, 5 /* Divide by 32 */
635 andi. rBITDIF, rN, 24 /* Get the DW remainder */
641 cmpldi cr1, rBITDIF, 16
644 subfic rSHR, rSHL, 64
647 mtctr rTMP /* Power4 wants mtctr 1st in dispatch group */
662 cmpld cr5, rWORD7, rWORD8
668 cmpld cr0, rWORD1, rWORD2
675 cmpld cr1, rWORD3, rWORD4
680 cmpld cr6, rWORD5, rWORD6
683 /* At this point we exit early with the first double word compare
684 complete and remainder of 0 to 7 bytes. See L(du14) for details on
685 how we handle the remaining bytes. */
687 cmpld cr5, rWORD7, rWORD8
697 /* Remainder is 16 */
707 cmpld cr6, rWORD5, rWORD6
714 cmpld cr5, rWORD7, rWORD8
721 cmpld cr0, rWORD1, rWORD2
728 cmpld cr1, rWORD3, rWORD4
732 cmpld cr5, rWORD7, rWORD8
746 /* Remainder is 24 */
756 cmpld cr1, rWORD3, rWORD4
762 cmpld cr6, rWORD5, rWORD6
770 cmpld cr5, rWORD7, rWORD8
775 addi rSTR1, rSTR1, 16
776 addi rSTR2, rSTR2, 16
777 cmpld cr0, rWORD1, rWORD2
781 addi rSTR1, rSTR1, 16
782 addi rSTR2, rSTR2, 16
784 cmpld cr5, rWORD7, rWORD8
796 /* Count is a multiple of 32, remainder is 0 */
799 mtctr rTMP /* Power4 wants mtctr 1st in dispatch group */
807 cmpld cr0, rWORD1, rWORD2
813 cmpld cr1, rWORD3, rWORD4
818 ldu rWORD7, 24(rSTR1)
819 ldu rWORD8, 24(rSTR2)
820 cmpld cr6, rWORD5, rWORD6
825 cmpld cr5, rWORD7, rWORD8
826 bdz- L(du24) /* Adjust CTR as we start with +4 */
827 /* This is the primary loop */
832 cmpld cr1, rWORD3, rWORD4
840 cmpld cr6, rWORD5, rWORD6
848 cmpld cr5, rWORD7, rWORD8
854 ldu rWORD7, 32(rSTR1)
855 ldu rWORD8, 32(rSTR2)
856 cmpld cr0, rWORD1, rWORD2
865 cmpld cr1, rWORD3, rWORD4
867 cmpld cr6, rWORD5, rWORD6
869 cmpld cr5, rWORD7, rWORD8
879 /* At this point we have a remainder of 1 to 7 bytes to compare. We use
880 shift right double to elliminate bits beyond the compare length.
881 This allows the use of double word subtract to compute the final
884 However it may not be safe to load rWORD2 which may be beyond the
885 string length. So we compare the bit length of the remainder to
886 the right shift count (rSHR). If the bit count is less than or equal
887 we do not need to load rWORD2 (all significant bits are already in
899 subfic rN, rN, 64 /* Shift count is 64 - (rN * 8). */
903 srd rWORD1, rWORD1, rN
904 srd rWORD2, rWORD2, rN
908 cmpld cr0, rWORD1, rWORD2
911 beq cr0, L(dureturn24)
922 bgt cr0, L(dureturn29)
932 bgt cr1, L(dureturn29)
942 bgt cr6, L(dureturn29)
952 bgt cr5, L(dureturn29)
980 END (BP_SYM (memcmp))
981 libc_hidden_builtin_def (memcmp)
982 weak_alias (memcmp, bcmp)