Failure to recognize table-based ctz implementation

[GabrielRavier]

Bugzilla Link	46434
Version	trunk
OS	Linux
CC	@topperc,@shubhamnarlawar77

Extended Description

int f(unsigned x)
{
    static const char table[32] = {0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9};
    return table[((unsigned)((x & -x) * 0x077CB531U)) >> 27];
}

This can be optimized to __builtin_ctz(x);. This transformation is done by GCC (or at least https://gcc.gnu.org/bugzilla/show_bug.cgi?id=90838 claims to do so, though I can't get it to trigger), but not by LLVM.

[GabrielRavier]

assigned to @shubhamnarlawar77

[topperc]

Minor correction

__builtin_ctz is undefined for 0 and that table lookup isn't.

So its really

x != 0 ? __builtin_ctz(x) : 0

or if you have the tzcnt instruction which produces a defined value of 32 for 0.

tzcnt(x) & 0x1f

I believe where this gets used based on the linked bug, it never gets called with a value of 0. But the compiler will have to prove that to avoid the select/and

[shubhamnarlawar77]

From above, it seems optimization is forward propagation pass, basically wherever the RHS of an assignment statement is used to replalce the uses of the LHS statement.

e.g. if i have

a = b + c
d = a + e
f = a + g

then it will create

d = b + c + e
f = b + c + g

however this is a propagator for specific situations, i.e. it checks for specific patterns and then replaces it. And for ctz it is specific pattern of exactly that magic number statement.

So my question is where can I find such pattern matching pass in the source code? Where exactly do I need to look in? Can someone please guide me on this?
@GabrielRavier @topperc

[topperc]

There was a proposed patch for this here https://reviews.llvm.org/D113291

[shubhamnarlawar77]

There was a proposed patch for this here https://reviews.llvm.org/D113291

Thanks for sharing. I will go through it! Since it is unmerged, should my patch be based on it which will be more amenable to accept by the community?

What is the reason for above patch to be on hold?

[shubhamnarlawar77]

Hello,

I have a small query regarding this patch. The patch emits following llvm assembly for ctz table -

-----Patch assembly-------

// %bb.0:

rbit w8, w0
cmp w0, #0
clz w8, w8
csel w0, wzr, w8, eq
ret

but in gcc, we have the following assembly being emitted -

------------GCC---------------------

f(unsigned int):

rbit    w0, w0
clz     w0, w0
and     w0, w0, 31
ret

Reference - https://gcc.gnu.org/bugzilla/show_bug.cgi?id=90838

[1] My question is - To solve the bug, do I have to generate assembly similar to GCC?

Please give me suggestions on moving forward in solving this bug.
@GabrielRavier @topperc @momchil-velikov

[topperc]

I think we can solve replacing the cmp w0, #0 and csel with and as a separate optimization.

[shubhamnarlawar77]

I think we can solve replacing the cmp w0, #0 and csel with and as a separate optimization.

This has been merged with this patch - https://reviews.llvm.org/D123782

[shubhamnarlawar77]

Emit table lookup from TargetLowering::expandCTTZ() patch - https://reviews.llvm.org/D128911 has been merged, but below cttz intrinsic transformation is still in progresss which I am looking forward to contribute and close it -

https://reviews.llvm.org/D113291

[shubhamnarlawar77]

Emit table lookup from TargetLowering::expandCTTZ() patch - https://reviews.llvm.org/D128911 has been merged, but below cttz intrinsic transformation is still in progresss which I am looking forward to contribute and close it -

https://reviews.llvm.org/D113291

@djtodoro - Have you made any changes from the latest review comments? Will there be any timeline about the changes to be submitted by you?

[djtodoro]

Updated.