[Bug tree-optimization/111280] New: CLZ(0) generated when CLZ_DEFINED_VALUE_AT_ZERO is false

[Bug tree-optimization/111280] New: CLZ(0) generated when CLZ_DEFINED_VALUE_AT_ZERO is false

[kristerw at gcc dot gnu.org]

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

            Bug ID: 111280
           Summary: CLZ(0) generated when CLZ_DEFINED_VALUE_AT_ZERO is
                    false
           Product: gcc
           Version: 14.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: kristerw at gcc dot gnu.org
  Target Milestone: ---

GCC may generate an internal call to CLZ with 0 when CLZ_DEFINED_VALUE_AT_ZERO
is false, which can be seen with gcc.c-torture/execute/920501-6.c where sccp
changes a loop to

  _36 = t_10(D) != 0;
  _35 = .CLZ (t_10(D));
  _34 = 63 - _35;
  _33 = (unsigned int) _34;
  _32 = (long long unsigned int) _33;
  _31 = _32 + 1;
  b_38 = _36 ? _31 : 1;

The value _35 is not used when t_10(D) is 0, so it may be reasonable to allow
this. But the value _35 may then be any value, so _34 may overflow. I.e., the
calculation
  _34 = 63 - _35;
must be changed to be done unsigned.

And the ranges calculated during the dom3 pass claims that _35 has a range
  _35  : [irange] int [0, 63]
which also is wrong.

[Bug tree-optimization/111280] CLZ(0) generated when CLZ_DEFINED_VALUE_AT_ZERO is false

[pinskia at gcc dot gnu.org]

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

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
     Ever confirmed|0                           |1
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2023-09-04

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
number_of_iterations_cltz_complement builds the COND_EXPR correctly.

In that it does:
(cast)(cast)(64 - (t !=0 ? .CLZ(t) : 64)) + 1

But calls fold_build2 to do the building
and that gets folded into:
t != 0 ? ((cast)(cast)(64 - .CLZ(t))) + 1 : 1
Which is fine.
and stores that into niter

But then we use force_gimple_operand/force_gimple_operand_gsi which does
creates the GIMPLE_COND ect.

And the check for rewriting from undefined to defined for addition is done via
the following check:
      /* If def's type has undefined overflow and there were folded
         casts, rewrite all stmts added for def into arithmetics
         with defined overflow behavior.  */
      if (folded_casts && ANY_INTEGRAL_TYPE_P (TREE_TYPE (def))
          && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (def)))

I don't know understand how folded_casts comes into play really.

[Bug tree-optimization/111280] CLZ(0) generated when CLZ_DEFINED_VALUE_AT_ZERO is false

[pinskia at gcc dot gnu.org]

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

--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Maybe during final_value_replacement_loop we should create a new BB for the
COND_EXPR instead of creating GIMPLE_COND ...

[Bug tree-optimization/111280] CLZ(0) generated when CLZ_DEFINED_VALUE_AT_ZERO is false

[rguenth at gcc dot gnu.org]

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

Richard Biener <rguenth at gcc dot gnu.org> changed:

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

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
force_gimple_operand will never create basic-blocks but instead makes scalar
code with a COND_EXPR rhs.  There's no existing infrastructure to handle this,
"pre-scanning" the GENERIC, splitting it at COND_EXPR points, might be a way
to fix this.

Note what niter analysis produces either is wrong or gimplification isn't
conservative enough with

          if (gimplify_ctxp->allow_rhs_cond_expr
              /* If either branch has side effects or could trap, it can't be
                 evaluated unconditionally.  */
              && !TREE_SIDE_EFFECTS (then_)
              && !generic_expr_could_trap_p (then_)
              && !TREE_SIDE_EFFECTS (else_)
              && !generic_expr_could_trap_p (else_))
            return gimplify_pure_cond_expr (expr_p, pre_p);

since that doesn't consider conditional undefined behavior.  Note fixing that
would then ICE or build gotos/labels (we could then use sth like
find_many_sub_bbs on).

[Bug tree-optimization/111280] CLZ(0) generated when CLZ_DEFINED_VALUE_AT_ZERO is false

[jakub at gcc dot gnu.org]

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

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> ---
Note, in PR111309 we briefly discussed adding
__builtin_{clz,ctz,popcount,ffs,clrsb} builtin type-generic variants which
would be well defined for clz/ctz cases.
I think the best representation of that would be to lower those builtins (dunno
what suffix to use for them yet) to .CLZ/.CTZ ifns with 2 arguments where the
second argument would be the value to be returned if the first argument is
zero.
Then at expansion time we could compare that value against
C?Z_VALUE_DEFINED_AT_ZERO, if it is the same, don't do anything special,
otherwise add a test against 0.