allow ffs & co. a binary search
Andriy Gapon
avg at FreeBSD.org
Wed Jun 17 13:29:26 UTC 2015
On 07/06/2015 16:54, Konstantin Belousov wrote:
> On Sun, Jun 07, 2015 at 07:52:45PM +0800, Erich Dollansky wrote:
>> What I saw is that all CPUs except ARM uses the software version [of ffs].
>
> Without quantifiers, this statement is not true. i386 libc function ffs(3)
> uses bsfl instruction to do the job. Compilers know about ffs(3) and friends
> as well, so e.g. gcc 5.1.0 generates the following code for the given
> fragment:
> return (ffs(x) + 1);
> is translated to
> 0: 0f bc c7 bsf %edi,%eax
> 3: ba ff ff ff ff mov $0xffffffff,%edx
> 8: 0f 44 c2 cmove %edx,%eax
> b: 83 c0 02 add $0x2,%eax
> (arg in %edi, result in %eax).
>
> I wrote a patch for amd64 libc long time ago to convert ffs/fls etc to use
> of the bitstring instruction, but Bruce Evans argued that this would be
> excessive. Your patch is excessive for the similar reasons.
Out of curiosity, what are those (Bruce's) reasons?
> My guess is that significantly clever compiler would recognize a pattern
> used by native ffs implementation and automatically use bitstring
> instructions. E.g., this already happens with popcnt and recent
> gcc/clang, I am just lazy to verify ffs.
It seems that both clang and gcc are smart enough to replace ffs*() with
__builtin_ffs*() which expand to the corresponding instructions.
On the other hand, neither clang nor gcc has __builtin_fls*() and as far as I
can see neither does anything special for fls*() calls.
Funny that __builtin_clz is complemented by __builtin_ctz, but there is no
counterpart to __builtin_ffs.
Lastly, I see no reason to have have different implementations of these
functions for the kernel and userland.
--
Andriy Gapon
More information about the freebsd-hackers
mailing list