[Bug tree-optimization/102580] New: Failure to optimize signed division to unsigned division when dividend can't be negative

[Bug tree-optimization/102580] New: Failure to optimize signed division to unsigned division when dividend can't be negative

[gabravier at gmail dot com]

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

            Bug ID: 102580
           Summary: Failure to optimize signed division to unsigned
                    division when dividend can't be negative
           Product: gcc
           Version: 12.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: gabravier at gmail dot com
  Target Milestone: ---

int f(int x) {
  if (x < 0) 
    __builtin_abort();
  return x/3;
}

The `return` statement can be optimized to `return (unsigned)x/3;`. This
optimization is done by LLVM, but not by GCC.

[Bug middle-end/102580] Failure to optimize signed division to unsigned division when dividend can't be negative

[pinskia at gcc dot gnu.org]

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

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

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

[Bug middle-end/102580] Failure to optimize signed division to unsigned division when dividend can't be negative

[rguenth at gcc dot gnu.org]

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

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
It's "worse" on GIMPLE though.

[Bug middle-end/102580] Failure to optimize signed division to unsigned division when dividend can't be negative

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever confirmed|0                           |1
   Last reconfirmed|                            |2021-10-17

--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Confirmed, It might be easy to do in the middle-end as we have a range.

[Bug middle-end/102580] Failure to optimize signed division to unsigned division when dividend can't be negative

[pinskia at gcc dot gnu.org]

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

--- Comment #3 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
We can do it for:
int f(int x) {
  if (x < 0) 
    __builtin_abort();
  x+=1;
  return x/3;
}

expand_expr_divmod has the code already to handle this, just needs a range. 
Expand would do querry to get better ranges really.

[Bug middle-end/102580] Failure to optimize signed division to unsigned division when dividend can't be negative

[pinskia at gcc dot gnu.org]

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

--- Comment #4 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
For an example GCC does optimize the following too:
int f(int x) {
  if (x < 0) 
    __builtin_unreachable();
  return x/3;
}

[Bug middle-end/102580] Failure to optimize signed division to unsigned division when dividend can't be negative

[jakub at gcc dot gnu.org]

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

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

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

--- Comment #5 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
To be precise, expand_expr_divmod uses get_range_pos_neg for that during
expansion (unless we'd e.g. somehow noted it in some very late pass before
expansion that the division ought to be expanded both ways and cost compared),
and get_range_pos_neg uses the global range of SSA_NAME only.  In order to
optimize #c0 we'd need to query range with the use stmt and enabling ranger in
the pass (that is possible in some pass before expansion, but doing it during
expansion (which would be useful to other spots too, say .*_OVERFLOW expansion)
would need to deal with some basic blocks already converted into RTL and others
still at GIMPLE).

[Bug middle-end/102580] Failure to optimize signed division to unsigned division when dividend can't be negative

[amacleod at redhat dot com]

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

--- Comment #6 from Andrew Macleod <amacleod at redhat dot com> ---
(In reply to Jakub Jelinek from comment #5)
> To be precise, expand_expr_divmod uses get_range_pos_neg for that during
> expansion (unless we'd e.g. somehow noted it in some very late pass before
> expansion that the division ought to be expanded both ways and cost
> compared), and get_range_pos_neg uses the global range of SSA_NAME only.  In
> order to optimize #c0 we'd need to query range with the use stmt and
> enabling ranger in the pass (that is possible in some pass before expansion,
> but doing it during expansion (which would be useful to other spots too, say
> .*_OVERFLOW expansion) would need to deal with some basic blocks already
> converted into RTL and others still at GIMPLE).

Im working on a logging mechanism for ranges for GCC 15. Its possible that a
side effect of this work could make some selective contextual ranges available
from the global table after .. in which case we could get things like this as
if ranger was running.

My other question. so is the issue that unsigned divides are cheaper than
signed divides?

the global range of _2 is set:
_2  : [irange] int [0, 715827882]

Given the statements in .optimized are: 

  <bb 4> [local count: 1073741824]:
  _2 = x_1(D) / 3;
  return _2;

could we not actually conclude that the divide can be unsigned based on the
result being positive and the divisor being positive?

We have "simple" versions of fold_range() which would calculate _2 on the
statement from the global value of x_1, but there aren't any simple versions of
the operand calculators.  It would be fairly trivial to provide one which,
given the global value for _2, you could ask
  op1_range (stmt)
and get back a value of [0, +INF] for x_1 at that statement.   If that would
help... 
THey are going to be added for GCC 15 anyway...

[Bug middle-end/102580] Failure to optimize signed division to unsigned division when dividend can't be negative

[jakub at gcc dot gnu.org]

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

--- Comment #7 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
(In reply to Andrew Macleod from comment #6)
> My other question. so is the issue that unsigned divides are cheaper than
> signed divides?

The middle-end doesn't really know.  On some targets unsigned divides can be
cheaper than signed divides, on others it doesn't matter, it wouldn't surprise
me if there
were targets where signed divides are cheaper than unsigned.  And then there
could
be targets where say unsigned divides aren't implemented in hw and signed ones
are or vice versa (and the other is implemented in libgcc).

On GIMPLE, adding any further casts makes the IL larger and shorter IL is what
we usually consider the canonical case (sure, there can be some exceptions, but
if there are, it is for stuff that is desirable on all targets, not just a
subset of them).

So, the idea is if we from ranges find out that a division or similar operation
can be equivalently implemented as signed or unsigned because the ranges say
that the operands
don't have MSB set when used on the division/modulo stmt, we emit both as RTL
and ask the backend what is cheaper.