[Bug tree-optimization/108341] New: argument to `__builtin_ctz` should be assumed non-zero

[Bug tree-optimization/108341] New: argument to `__builtin_ctz` should be assumed non-zero

[lh_mouse at 126 dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108341

            Bug ID: 108341
           Summary: argument to `__builtin_ctz` should be assumed non-zero
           Product: gcc
           Version: 12.2.1
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: lh_mouse at 126 dot com
  Target Milestone: ---

Godbolt: https://gcc.godbolt.org/z/PrPP4v9z1


```
extern int r;

int
bz(int value)
  {
    r = __builtin_ctz(value);
    return value != 0;  // always true
  }
```


According to GCC manual, if the argument to `__builtin_ctz()` is zero then the
behavior is undefined, but GCC fails to assume that this function always
returns `1`. 

But I have read https://gcc.gnu.org/bugzilla/show_bug.cgi?id=94801, not sure
whether it's related.

[Bug tree-optimization/108341] argument to `__builtin_ctz` should be assumed non-zero

[marxin at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108341

Martin Liška <marxin at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |aldyh at gcc dot gnu.org,
                   |                            |amacleod at redhat dot com,
                   |                            |marxin at gcc dot gnu.org

--- Comment #1 from Martin Liška <marxin at gcc dot gnu.org> ---
May be an opportunity for Ranger?

[Bug tree-optimization/108341] argument to `__builtin_ctz` should be assumed non-zero

[aldyh at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108341

--- Comment #2 from Aldy Hernandez <aldyh at gcc dot gnu.org> ---
(In reply to Martin Liška from comment #1)
> May be an opportunity for Ranger?

Hmmm... I don't think so:

    <bb 2> :
    value.0_1 = (unsigned int) value_4(D);
    _2 = __builtin_ctz (value.0_1);
    r = _2;
    _3 = value_4(D) != 0;
    _7 = (int) _3;
    return _7;

We could add an op1_range operator to class cfn_clz to return nonzero for op1,
but that would only work if we knew _2 to be anything...and have no info on _2.

[Bug tree-optimization/108341] argument to `__builtin_ctz` should be assumed non-zero

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108341

--- Comment #3 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Not always.
It depends on the definition of CTZ_DEFINED_VALUE_AT_ZERO.

/* The value at zero is only defined for the BMI instructions
   LZCNT and TZCNT, not the BSR/BSF insns in the original isa.  */
#define CTZ_DEFINED_VALUE_AT_ZERO(MODE, VALUE) \
        ((VALUE) = GET_MODE_BITSIZE (MODE), TARGET_BMI ? 2 : 0)
#define CLZ_DEFINED_VALUE_AT_ZERO(MODE, VALUE) \
        ((VALUE) = GET_MODE_BITSIZE (MODE), TARGET_LZCNT ? 2 : 0)



So assuming !=0 with -mbmi would be an invalid assumitation.

[Bug tree-optimization/108341] argument to `__builtin_ctz` should be assumed non-zero when CTZ_DEFINED_VALUE_AT_ZERO says it is undefined

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108341

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jakub at gcc dot gnu.org

--- Comment #4 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
I think 0 argument for __builtin_c[lt]z{,l,ll,imax} is always undefined, 0
argument
to .C[LT]Z (internal calls) is undefined if C[LT]Z_DEFINED_VALUE_AT_ZERO is not
2 and
0 argument to C[LT]Z RTL is undefined if C[LT]Z_DEFINED_VALUE_AT_ZERO is not
non-zero.

[Bug tree-optimization/108341] argument to `__builtin_ctz` should be assumed non-zero when CTZ_DEFINED_VALUE_AT_ZERO says it is undefined

[amacleod at redhat dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108341

--- Comment #5 from Andrew Macleod <amacleod at redhat dot com> ---
(In reply to Aldy Hernandez from comment #2)
> (In reply to Martin Liška from comment #1)
> > May be an opportunity for Ranger?
> 
> Hmmm... I don't think so:
> 
>     <bb 2> :
>     value.0_1 = (unsigned int) value_4(D);
>     _2 = __builtin_ctz (value.0_1);
>     r = _2;
>     _3 = value_4(D) != 0;
>     _7 = (int) _3;
>     return _7;
> 
> We could add an op1_range operator to class cfn_clz to return nonzero for
> op1, but that would only work if we knew _2 to be anything...and have no
> info on _2.

Seems more like a candidate for gimpe_infer::gimple_infer (gimple *s).

THe side effect to register would be to check if 's' is a builtin_ctz and if
so, call add_nonzero (operand1) if whatever those other conditions are are
matched which make it true.

That should register a non-zero inferred range on value.0_1 after the
assignment of _2.


=========== BB 2 ============
Partial equiv (value.0_1 pe32 value_4(D))
    <bb 2> :
    value.0_1 = (unsigned int) value_4(D);
    _2 = __builtin_ctz (value.0_1);
    r = _2;
    _3 = value_4(D) != 0;
    _7 = (int) _3;
    return _7;

I see ranger also registers a 32 bit equivalence between value.0_1 and value_4,
so in theory we would then be able to determine that value_4 is also non-zero
for the comparison.

[Bug tree-optimization/108341] argument to `__builtin_ctz` should be assumed non-zero when CTZ_DEFINED_VALUE_AT_ZERO says it is undefined

[aldyh at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108341

Aldy Hernandez <aldyh at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|normal                      |enhancement

--- Comment #6 from Aldy Hernandez <aldyh at gcc dot gnu.org> ---
Huh.  Didn't know you could do that.  Thanks.

FWIW, the function is actually:

gimple_infer_range::gimple_infer_range (gimple *s)

[Bug tree-optimization/108341] argument to `__builtin_ctz` should be assumed non-zero when CTZ_DEFINED_VALUE_AT_ZERO says it is undefined

[lh_mouse at 126 dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108341

--- Comment #7 from LIU Hao <lh_mouse at 126 dot com> ---
(In reply to Jakub Jelinek from comment #4)
> I think 0 argument for __builtin_c[lt]z{,l,ll,imax} is always undefined, 0
> argument
> to .C[LT]Z (internal calls) is undefined if C[LT]Z_DEFINED_VALUE_AT_ZERO is
> not 2 and
> 0 argument to C[LT]Z RTL is undefined if C[LT]Z_DEFINED_VALUE_AT_ZERO is not
> non-zero.

I agree with this.


#94801 mentioned the `if(value == 0) __builtin_unreachable();` trick, but it
isn't an option if the argument is really possibly a zero:

(https://gcc.godbolt.org/z/dePvcMhTr)
```
#include <stdint.h>

uint32_t
my_tzcnt(uint32_t value)
  {
    return (value == 0) ? 32 : __builtin_ctz(value);
  }
```

This can be TZCNT if the CPU supports it.