[Bug tree-optimization/96707] New: Failure to optimize right shift+unsigned compare of two variables optimally

[Bug tree-optimization/96707] New: Failure to optimize right shift+unsigned compare of two variables optimally

[gabravier at gmail dot com]

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

            Bug ID: 96707
           Summary: Failure to optimize right shift+unsigned compare of
                    two variables optimally
           Product: gcc
           Version: 11.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: ---

bool f(unsigned x, unsigned y)
{
    return (x >> y) <= x;
}

This can be optimized to `return true;`. This transformation is done by LLVM,
but not by GCC.

[Bug tree-optimization/96707] Failure to optimize right shift+unsigned compare of two variables optimally

[gabravier at gmail dot com]

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

--- Comment #1 from Gabriel Ravier <gabravier at gmail dot com> ---
PS: This transformation can also be done with a very similar pattern where the
return statement is replaced with this : `return (x / y) <= x;`

[Bug tree-optimization/96707] Failure to optimize right shift+unsigned compare of two variables optimally

[pinskia at gcc dot gnu.org]

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

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

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

[Bug tree-optimization/96707] Failure to optimize right shift+unsigned compare of two variables optimally

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
     Ever confirmed|0                           |1
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2020-08-25

[Bug tree-optimization/96707] Failure to optimize right shift+unsigned compare of two variables optimally

[jakub at gcc dot gnu.org]

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

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

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

--- Comment #2 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
I think another case for ranger symbolic ranges?

[Bug tree-optimization/96707] Failure to optimize right shift+unsigned compare of two variables optimally

[amacleod at redhat dot com]

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

--- Comment #3 from Andrew Macleod <amacleod at redhat dot com> ---
(In reply to Jakub Jelinek from comment #2)
> I think another case for ranger symbolic ranges?

indeed.

[Bug tree-optimization/96707] Failure to optimize right shift+unsigned compare of two variables optimally

[amacleod at redhat dot com]

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

--- Comment #4 from Andrew Macleod <amacleod at redhat dot com> ---
The IL generated is:

  _1 = x_2(D) >> y_3(D);
  _4 = _1 <= x_2(D);
  return _4;

All that should be needed is for the right shift operator in range-ops to
implement lhs_op1_relation() to indicate that if the range of op2 is >=0, then 
return LE_EXPR.   

this will automatically register  the relation _1 <= x_2 at the def point for
_1, and then _4 should simply fold away as true.

[Bug tree-optimization/96707] Failure to optimize right shift+unsigned compare of two variables optimally

[cvs-commit at gcc dot gnu.org]

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

--- Comment #5 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Andrew Macleod <amacleod@gcc.gnu.org>:

https://gcc.gnu.org/g:27e4260166950b784fe270ba4f0cae9a66faf1c4

commit r12-6558-g27e4260166950b784fe270ba4f0cae9a66faf1c4
Author: Andrew MacLeod <amacleod@redhat.com>
Date:   Wed Jan 12 13:28:55 2022 -0500

    Add relation to unsigned right shift.

    If the first operand and the shift value of a right shift operation are
both
    >= 0, then we know the LHS of the operation is <= the first operand.

            PR tree-optimization/96707
            gcc/
            * range-op.cc (operator_rshift::lhs_op1_relation): New.

            gcc/testsuite/
            * g++.dg/pr96707.C: New.

[Bug tree-optimization/96707] Failure to optimize right shift+unsigned compare of two variables optimally

[amacleod at redhat dot com]

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

Andrew Macleod <amacleod at redhat dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|---                         |FIXED

--- Comment #6 from Andrew Macleod <amacleod at redhat dot com> ---
fixed.