Re: rs6000 and ffs

[Michael S. Zick <mszick at goquest dot com>]

On Monday 20 January 2003 05:41 am, Håkan Hjort wrote:
> Mon Dec 02 2002, David Edelsohn wrote:
> > 	I have committed the patch with the additional change that the
> > DImode patterns should have TARGET_POWERPC64 in the final condition.  The
> > cntlzd instruction only is available in 64-bit mode and the condition was
> > present in the original ffsdi2 pattern.
>
> Not directly related to this but I thought I'd ask.
>
> For rs6000 the cntlz instruction is used to calculate ffs(), this is
> nice and all but what's really hard to do is fls() i.e. exaclty what
> cntlz is doing.  Count _leading_ zeros or finding the most significant
> bit set.  There doesn't seem to be any standardized function for this,
- - - - - - - - - - - - - - - - - - - - ^ ^ ^ ? ? ? ? ? ? ^ ^ ^
> and writing it in plain C is really slow. I guess that there might be

Try the key phrase: "Bit Parallel, Binary Reduction"

What you have posted is a special case version of the general algorithm.

The general algorithm finds {Leading, Trailing}{One, Zero} and has
a double output - the bit position in positional notation and the
corresponding bit mask.

>From the bit mask, in addition to the obvious {Bit Set, Bit Clear,
Bit Complement} you can also, in a few ALU instructions, find
bit field mask {Leading, Trailing}{Inclusive, Exclusive}.

Takes more code space than a bit scan instruction, but is
not always slower. (on 80386 the algorithm beats its own
micro-coded BSx instructions.)

Ask Toshi to provide you with a complete 
cross system analysis - since from his mail, he is the
only person on the list who ever does so.

Yes, it can be written in C.
Should I just post the sources?

Mike