Re: [parisc-linux] Re: [PATCH 3/6] C-language equivalents of include/asm-*/bitops.h

[Russell King <rmk+lkml@arm.linux.org.uk>]

On Thu, Jan 26, 2006 at 09:18:49AM -0700, Grant Grundler wrote:
> On Thu, Jan 26, 2006 at 08:55:41AM +0000, Russell King wrote:
> > Unfortunately that's not correct.  You do not appear to have checked
> > the compiler output like I did - this code does _not_ generate
> > constant shifts.
> 
> Russell,
> By "written stupidly", I thought Richard meant they could have
> used constants instead of "s".  e.g.:
> 	if (word << 16 == 0) { b += 16; word >>= 16); }
> 	if (word << 24 == 0) { b +=  8; word >>=  8); }
> 	if (word << 28 == 0) { b +=  4; word >>=  4); }
> 
> But I prefer what Edgar Toernig suggested.

Ok, I can see I'm going to lose this, but what the hell.

Firstly though, an out of line function call on ARM clobbers six out
of 11 CPU registers.

Let's compare the implementations, which are:

int toernig_ffs(unsigned long word)
{
    int bit = 0;
    word &= -word; // only keep the lsb.
    if (word & 0xffff0000) bit |= 16;
    if (word & 0xff00ff00) bit |=  8;
    if (word & 0xf0f0f0f0) bit |=  4;
    if (word & 0xcccccccc) bit |=  2;
    if (word & 0xaaaaaaaa) bit |=  1;
    return bit;
}

toernig_ffs:
        rsb     r3, r0, #0
        and     r0, r0, r3
        mov     r3, r0, lsr #16
        bic     r2, r0, #16711680
        str     lr, [sp, #-4]!
        mov     r3, r3, asl #16
        ldr     lr, .L7
        ldr     r1, .L7+4
        ldr     ip, .L7+8
        cmp     r3, #0
        bic     r2, r2, #255
        and     lr, r0, lr
        and     r1, r0, r1
        and     ip, r0, ip
        movne   r0, #16
        moveq   r0, #0
        cmp     r2, #0
        orrne   r0, r0, #8
        cmp     r1, #0
        orrne   r0, r0, #4
        cmp     ip, #0
        orrne   r0, r0, #2
        cmp     lr, #0
        orrne   r0, r0, #1
        ldr     pc, [sp], #4
.L8:
        .align  2
.L7:
        .word   -1431655766
        .word   -252645136
        .word   -858993460

25 instructions.  3 words of additional data.  5 registers.  0 register
based shifts.

I feel that this is far too expensive to sanely inline - at least three
words of additional data for a use in a function, and has a high register
usage comparable to that of an out of line function.

int mita_ffs(unsigned long word)
{
     int b = 0, s;
     s = 16; if (word << 16 != 0) s = 0; b += s; word >>= s;
     s =  8; if (word << 24 != 0) s = 0; b += s; word >>= s;
     s =  4; if (word << 28 != 0) s = 0; b += s; word >>= s;
     s =  2; if (word << 30 != 0) s = 0; b += s; word >>= s;
     s =  1; if (word << 31 != 0) s = 0; b += s;
     return b;
}

mita_ffs:
        movs    r1, r0, asl #16
        moveq   r2, #16
        movne   r2, #0
        mov     r0, r0, lsr r2		@ register-based shift
        mov     r3, r2
        movs    r2, r0, asl #24
        moveq   r2, #8
        movne   r2, #0
        mov     r0, r0, lsr r2		@ register-based shift
        movs    r1, r0, asl #28
        add     r3, r3, r2
        moveq   r2, #4
        movne   r2, #0
        mov     r0, r0, lsr r2		@ register-based shift
        movs    r1, r0, asl #30
        add     r3, r3, r2
        moveq   r2, #2
        movne   r2, #0
        mov     r0, r0, lsr r2		@ register-based shift
        tst     r0, #1
        add     r3, r3, r2
        moveq   r2, #1
        movne   r2, #0
        add     r3, r3, r2
        mov     r0, r3
        mov     pc, lr

26 instructions.  4 registers used.  4 unconditional register-based
shifts (expensive).

Better, but uses inefficient register based shifts (which can take twice
as many cycles as non-register based shifts depending on the CPU).  Still
has a high usage on CPU registers though.  Could possibly be a candidate
for inlining.

int arm_ffs(unsigned long word)
{
     int k = 31;
     if (word & 0x0000ffff) { k -= 16; word <<= 16; }
     if (word & 0x00ff0000) { k -= 8;  word <<= 8;  }
     if (word & 0x0f000000) { k -= 4;  word <<= 4;  }
     if (word & 0x30000000) { k -= 2;  word <<= 2;  }
     if (word & 0x40000000) { k -= 1; }
     return k;
}

arm_ffs:
        mov     r3, r0, asl #16
        mov     r3, r3, lsr #16
        cmp     r3, #0
        movne   r0, r0, asl #16
        mov     r3, #31
        movne   r3, #15
        tst     r0, #16711680
        movne   r0, r0, asl #8
        subne   r3, r3, #8
        tst     r0, #251658240
        movne   r0, r0, asl #4
        subne   r3, r3, #4
        tst     r0, #805306368
        movne   r0, r0, asl #2
        subne   r3, r3, #2
        tst     r0, #1073741824
        subne   r3, r3, #1
        mov     r0, r3
        mov     pc, lr

19 instructions.  2 registers.  0 register based shifts.  More reasonable
for inlining.

Clearly the smallest of the lot with the smallest register pressure,
being the best candidate out of the lot, whether we inline it or not.

-- 
Russell King
 Linux kernel    2.6 ARM Linux   - http://www.arm.linux.org.uk/
 maintainer of:  2.6 Serial core