[PATCH] powerpc: Optimized strcmp for POWER8/PPC64

[Adhemerval Zanella]

On 07-01-2015 17:32, Ondřej Bílka wrote:
> On Wed, Jan 07, 2015 at 03:10:25PM -0200, Adhemerval Zanella wrote:
>> On 07-01-2015 14:30, Ondrej Bilka wrote:
>>>> +	/* For short string up to 16 bytes, load both s1 and s2 using
>>>> +	   unaligned dwords and compare.  */
>>>> +	ld	r8,0(r3)
>>>> +	ld	r10,0(r4)
>>>> +	li	r9,0
>>>> +	cmpb	r7,r8,r9
>>>> +	cmpdi	cr7,r7,0
>>>> +	mr	r9,r7
>>>> +	bne 	cr7,L(null_found)
>>>> +	cmpld	cr7,r8,r10
>>>> +	bne	cr7,L(different)
>>>> +	ld	r8,8(r3)
>>>> +	ld	r10,8(r4)
>>>> +	cmpb	r9,r8,r7
>>>> +	cmpdi	cr7,r9,r0
>>>> +	bne	cr7,L(null_found)
>>>> +	cmpld	cr7,r8,r10
>>>> +	bne	cr7,L(different)
>>>> +	addi	r7,r3,16
>>>> +	addi	r4,r4,16
>>> It makes no sense to do two separate checks which create pretty unpredictable branches.
>>>
>>> Just or these two check and look at first nonzero byte. Either they differ at that offset or both are zero and easily get result from that.
>>>
>> Which two checks are you referring exactly? The first two:
>>
>> +	ld	r8,0(r3)
>> +	ld	r10,0(r4)
>> +	li	r9,0
>> +	cmpb	r7,r8,r9
>> +	cmpdi	cr7,r7,0
>> +	mr	r9,r7
>> +	bne 	cr7,L(null_found)
>> +	cmpld	cr7,r8,r10
>> +	bne	cr7,L(different)
>>
>> First cmpb instruction is not a branch instruction (and thus has no affect on 
>> branch prediction).  Also, in this code is it has to check for NULL first 
>> before start to check different bytes at second dword.  For instance, for
>> strings:
>>
> No I am refering that to 
> bne cr7,L(null_found) 
> and 
> bne cr7,L(different)
>
> you do need two nearly identical branches, just create mask that detects
> both 0 and difference.
>
> On x64 first 16 bytes are handled using this trick, you could replace
> bytewise minimum there with bytewise and.
>
>         pxor    %xmm2, %xmm2
>         movdqu  (%rdi), %xmm1
>         movdqu  (%rsi), %xmm0
>         pcmpeqb %xmm1, %xmm0
>         pminub  %xmm1, %xmm0
>         pcmpeqb %xmm2, %xmm0
>         pmovmskb        %xmm0, %eax
>         testq   %rax, %rax
>         je      L(next_48_bytes)
> L(return):
>         bsfq    %rax, %rdx
>         movzbl  (%rdi, %rdx), %eax
>         movzbl  (%rsi, %rdx), %edx
>         subl    %edx, %eax
>         ret
>
I see your point now, I have changed to:


        /* For short string up to 16 bytes, load both s1 and s2 using
           unaligned dwords and compare.  */
        ld      r8,0(r3)
        ld      r10,0(r4)
        li      r0,0
        cmpb    r12,r8,r0
        cmpb    r11,r8,r10
        orc.    r9,r12,r11
        bne     cr0,L(different_nocmpb)
        ld      r8,8(r3)
        ld      r10,8(r4)
        cmpb    r12,r8,r0
        cmpb    r11,r8,r10
        orc.    r9,r12,r11
        bne     cr0,L(different_nocmpb)
        addi    r7,r3,16
        addi    r4,r4,16
        b       L(align_16b)
[...]
L(different):
        cmpb    r9,r8,r10
#ifdef __LITTLE_ENDIAN__
        nor     r9,r9,r9
L(different_nocmpb):
        neg     r3,r9
        and     r9,r9,r3
        cntlzd  r9,r9
        subfic  r9,r9,63
#else
        not     r9,r9
L(different_nocmpb):
        cntlzd  r9,r9
        subfic  r9,r9,56
#endif
        srd     r3,r8,r9
        srd     r10,r10,r9
        rldicl  r10,r10,0,56
        rldicl  r3,r3,0,56
        subf    r3,r10,r3
        blr

And after tuning some loop alignments I am seeing some cycles being spared.
Thanks for the tip.