Skip site navigation (1)Skip section navigation (2)
Date:      Sun, 7 Jun 2015 09:37:23 -0700
From:      Davide Italiano <davide@freebsd.org>
To:        Konstantin Belousov <kostikbel@gmail.com>
Cc:        Erich Dollansky <erichsfreebsdlist@alogt.com>, Hans Petter Selasky <hps@selasky.org>,  "freebsd-hackers@freebsd.org" <freebsd-hackers@freebsd.org>
Subject:   Re: allow ffs & co. a binary search
Message-ID:  <CACYV=-Gdyr7kts_=-u8FWCXNjygL4GxSdnvepz2D34XLv%2BJ-jw@mail.gmail.com>
In-Reply-To: <20150607135453.GH2499@kib.kiev.ua>
References:  <20150607081315.7c0f09fb@B85M-HD3-0.alogt.com> <5573EA5E.40806@selasky.org> <20150607195245.62dc191f@B85M-HD3-0.alogt.com> <20150607135453.GH2499@kib.kiev.ua>

next in thread | previous in thread | raw e-mail | index | archive | help
On Sun, Jun 7, 2015 at 6:54 AM, Konstantin Belousov <kostikbel@gmail.com> 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.
>
> 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.
> _______________________________________________
> freebsd-hackers@freebsd.org mailing list
> http://lists.freebsd.org/mailman/listinfo/freebsd-hackers
> To unsubscribe, send any mail to "freebsd-hackers-unsubscribe@freebsd.org"

Clang trunk to the best of my knowledgde hasn't a way to recognize
ffs() pattern.
http://llvm.org/docs/doxygen/html/LoopIdiomRecognize_8cpp_source.html
I can't comment about gcc as long as I'm not familiar with the implementation.

-- 
Davide

"There are no solved problems; there are only problems that are more
or less solved" -- Henri Poincare



Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?CACYV=-Gdyr7kts_=-u8FWCXNjygL4GxSdnvepz2D34XLv%2BJ-jw>