Re: Speedup bitmap iterators

[Jan Hubicka <hubicka at ucw dot cz>]

> On 06/09/2010 12:32 PM, Richard Guenther wrote:
> > Hm. I am concerned about using __builtin_ctzl unconditionally
> > as it might expand to a call to libgcc which for sure wouldn't be
> > faster(?).
> Somewhen I'd like to understand this issue better, because quite a few
> years ago somebody decided that using unconditionally builtins like
> __builtin_ctzl in <bitset> would be a win...

I would personally sayt hat if we don't generate faster or equal code with
__builtin_ctzl than we do with hand written loop, it is codegen bug on that
particular target.  My preferrence would be to switch to using __builtin_ctzl
and then fix the targets where this results in lousy code.

Note that ctzl is in use in GCC:
bitmap.c:  bit_no += __builtin_ctzl (word);
bitmap.c:  bit_no += sizeof (long) * 8 - __builtin_ctzl (word);
ggc-page.c:       bit = __builtin_ctzl (~entry->in_use_p[word]);
toplev.h:#  define CTZ_HWI __builtin_ctzl
toplev.h:#  define CTZ_HWI __builtin_ctzll
toplev.h:  return x == (x & -x) && x ? (int) CTZ_HWI (x) : -1;

There are I guess 4 ways to handle this.  Either hardware instruction like i386
have, or the loop, jump sequence halving the interval or the libcall.
I guess that depending on target each of those do make sense.

I also don't link longlong.h facility applies here very easilly since it is for
long longs, not for longs that makes difference.

Honza
> 
> Paolo.