Defining 0 for clz does not optimize

[llvmbot]

Bugzilla Link	10192
Version	trunk
OS	Windows NT
Reporter	LLVM Bugzilla Contributor
CC	@asl,@chandlerc,@lattner,@64

Extended Description

Howdy... GCC leaves __builtin_clz undefined for zero, so writing code in Clang like

return 31 - (value == 0 ? 32 : __builtin_clz(value));

You would think the 'value == 0 ? 32 : ' would get optimized out, since CLZ on ARM is defined as 32 for value 0. However that does not appear to be the case. On Thumb 2 I get the following output for the above snippet:

00000000 <uint32_log2_floor>:
0: 2120 movs r1, #​32
2: 2800 cmp r0, #​0
4: bf18 it ne
6: fab0 f180 clzne r1, r0
a: f1c1 001f rsb r0, r1, #​31 ; 0x1f
e: 4770 bx lr

It would be nice if LLVM could recognize this situation, where the branch is identical to the defined behavior for the CPU instruction.

Thanks

James

[llvmbot]

I suppose a workaround for now can be use of #ifdef although you would be correct there would be nice to recognize by itself

[llvmbot]

Note that the @​llvm.ctlz.* instrinsic does guarantee the same behaviour that you describe ARM as having. So you should be able to use #ifdef to check whether the compiler is Clang or GCC and then define a macro based on which one it is.

http://llvm.org/docs/LangRef.html#int_ctlz

[llvmbot]

Really? What does it do on x86 then?

[llvmbot]

This is an example of a general class of optimizations that are missed.

Consider
%s = select i1 %cond, i32 %x, i32 %y

If you can show that %y coincides with %x when %cond is true then you can
replace the select with %y.

In your example, %cond = (value == 0), %x = 32, %y = __builtin_clz(value).
If value == 0 is true then __builtin_clz(value) is __builtin_clz(0) which LLVM
defines to return 32 (see the LangRef), i.e. it is equal to %x. So for this
example the select could be replaced with __builtin_clz(value), as you want.

Unfortunately the infrastructure for reasoning like this does not exist yet.

[lattner]

We should just fix the LLVM intrinsics to match the GCC definition, and eliminate this class of pessimization.

[llvmbot]

We should just fix the LLVM intrinsics to match the GCC definition, and
eliminate this class of pessimization.

GCC doesn't define __builtin_clz(0)... For ARM, at least, wouldn't that make it an absolute necessity to check, even though the CPU guarantees the value of it?

[lattner]

Being undefined at 0 means that we don't need to produce special code for it. Being (bug) compatible with GCC here is the right thing to do.

[llvmbot]

Being undefined at 0 means that we don't need to produce special code for it.
Being (bug) compatible with GCC here is the right thing to do.

Oh, that would be better for X86 users no doubt. Often you know whether a zero is possible or not anyway. Then the ARM backend could just have a special rule to fold x == 0 ? 32 : __builtin_clz(x).

[chandlerc]

I came up with a plan for fixing this with Owen a while back. I'll see about making that happen now.

The fundamental idea will be to replace the LLVM 'ctlz' and 'cttz' intrinsics with 'clz' and 'ctz' intrinsics that provide the same behavior as GCC, and auto-upgrade users of the old names to the code necessary to achieve their behavior.