Re: Suspecting a wrong behavior in the value range propagation analysis for __builtin_clz

[Richard Biener <richard.guenther@gmail.com>]

On Wed, Nov 1, 2023 at 12:30 PM Giuseppe Tagliavini via Gcc
<gcc@gcc.gnu.org> wrote:
>
> I found an unexpected issue working with an experimental target (available here: https://github.com/EEESlab/tricore-gcc), but I was able to reproduce it on mainstream architectures. For the sake of clarity and reproducibility, I always refer to upstream code in the rest of the discussion.
>
> Consider this simple test:
>
> #include <stdio.h>
> int f(unsigned int a) {
>   unsigned int res = 8*sizeof(unsigned int) - __builtin_clz(a);
>   if(res>0) printf("test passed\n");
>   return res-1;
> }
>
> I tested this code on GCC 9 and GCC 11 branches, obtaining the expected result from GCC 9 and the wrong one from GCC 11. In GCC 11 and newer versions, the condition check is removed by a gimple-level optimization (I will provide details later), and the printf is always invoked at the assembly level with no branch.
>
> According to the GCC manual, __builtin_clz "returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined." However, it is possible to define a CLZ_DEFINED_VALUE_AT_ZERO in the architecture backend to specify a defined behavior for this case. For instance, this has been done for SPARC and AARCH64 architectures. Compiling my test with SPARC GCC 13.2.0 with the -O3 flag on CompilerExplorer I got this assembly:

Note the semantic of __builtin_clz is _not_ altered by
CLZ_DEFINED_VALUE_AT_ZERO, the behavior
of __builtin_clz (x) is that is has undefined result for x == 0.
CLZ_DEFINED_VALUE_AT_ZERO
is only used to optimize code generation when the user writes say
x == 0 ? 0 : __builtin_clz (x)

Richard.

> .LC0:
>         .asciz  "test"
> f:
>         save    %sp, -96, %sp
>         call    __clzsi2, 0
>          mov    %i0, %o0
>         mov     %o0, %i0
>         sethi   %hi(.LC0), %o0
>         call    printf, 0
>          or     %o0, %lo(.LC0), %o0
>         mov     31, %g1
>         return  %i7+8
>          sub    %g1, %o0, %o0
>
> After some investigation, I found this optimization derives from the results of the value range propagation analysis: https://github.com/gcc-mirror/gcc/blob/master/gcc/gimple-range-op.cc#L917
> In this code, I do not understand why CLZ_DEFINED_VALUE_AT_ZERO is verified only if the function call is tagged as internal. A gimple call is tagged as internal at creation time only when there is no associated function declaration (see https://github.com/gcc-mirror/gcc/blob/master/gcc/gimple.cc#L371), which is not the case for the builtins. From my point of view, this condition prevents the computation of the correct upper bound for this case, resulting in a wrong result from the VRP analysis.
>
> Before considering this behavior as a bug, I prefer to ask the community to understand if there is any aspect I have missed in my reasoning.