Re: RFC: Simplify rules for ctz/clz patterns and RTL

[Zack Weinberg <zack at codesourcery dot com>]

Segher Boessenkool wrote:
> > * I would like to do the same for __builtin_ctz, but there is a catch.
> > The synthetic ctz sequence in terms of popcount (as presently
> > implemented by ia64.md, and potentially usable for at least i386 and
> > rs6000 as well if moved to optabs.c) produces the canonical behavior at
> > zero, but the synthetic sequence in terms of clz (as presently
> > implemented by optabs.c) produces the value -1 at zero.
>
> I suppose you're using (assuming 32-bit)
>
>     ctz(x) := 31 - clz(x & -x)
>
> now, which gives -1 for 0; and the version you're looking for is
>
>     ctz(x) := 32 - clz(~x & (x-1))
>
> which gives 32 for 0.

Thanks!  That's, unfortunately, one more instruction, although I guess a 
lot of chips have "a & ~b" as one operation.

> What does the popcount version look like?  Never seen that before,
> but I think it will be really expensive on PowerPC.

  ctz(x) := popcount(~x & (x-1))

Just the same thing as your version of the ctz-as-clz operation, but 
without the final adjustment.  It looks like ~x & (x-1) turns any number 
into 000...111... where the boundary between zeroes and ones lies at the 
lowest 1 in the original.

Is popcount really slow on PowerPC?  (Compared to clz?)  Ideally one 
would choose between the two expansions based on RTL costs, but the only 
 architectures it matters for are i386 and powerpc, and neither of them 
define the cost of either clz or popcount.

zw