[Bug tree-optimization/94899] New: Failure to optimize out add before compare

[Bug tree-optimization/94899] New: Failure to optimize out add before compare

[gabravier at gmail dot com]

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

            Bug ID: 94899
           Summary: Failure to optimize out add before compare
           Product: gcc
           Version: 10.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, int y)
{
    return x + 0x80000000 < y + 0x80000000;
}

This can be optimized to `return x < y`. LLVM does this transformation, but GCC
does not.

[Bug tree-optimization/94899] Failure to optimize out add before compare with INT_MIN

[pinskia at gcc dot gnu.org]

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

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
The problem is only with INT_MIN.

[Bug tree-optimization/94899] Failure to optimize out add before compare with INT_MIN

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |RESOLVED
         Resolution|---                         |INVALID

--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
/* X + Z < Y + Z is the same as X < Y when there is no overflow.  */
(for op (lt le ge gt)
 (simplify
  (op (plus:c @0 @2) (plus:c @1 @2))
  (if (ANY_INTEGRAL_TYPE_P (TREE_TYPE (@0))
       && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (@0)))
   (op @0 @1))))
...
/* X - Z < Y - Z is the same as X < Y when there is no overflow.  */
(for op (lt le ge gt)
 (simplify
  (op (minus @0 @2) (minus @1 @2))
  (if (ANY_INTEGRAL_TYPE_P (TREE_TYPE (@0))
       && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (@0)))
   (op @0 @1))))

This is invalid as 0x80000000 is unsigned (C90/C++03) or long (C99/C++11) in
type.
Which means then overflow is not undefined but rather wrapping.

THIS ALSO means clang is broken.

[Bug tree-optimization/94899] Failure to optimize out add before compare with INT_MIN

[pinskia at gcc dot gnu.org]

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

--- Comment #3 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
If I used (int)(0x80000000) instead, I get the optimization which means GCC is
correct.

[Bug tree-optimization/94899] Failure to optimize out add before compare with INT_MIN

[rsandifo at gcc dot gnu.org]

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

rsandifo at gcc dot gnu.org <rsandifo at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |easyhack
             Status|RESOLVED                    |NEW
   Last reconfirmed|                            |2020-05-01
                 CC|                            |rsandifo at gcc dot gnu.org
         Resolution|INVALID                     |---
     Ever confirmed|0                           |1

--- Comment #4 from rsandifo at gcc dot gnu.org <rsandifo at gcc dot gnu.org> ---
Reopening because...

(In reply to Andrew Pinski from comment #2)
> This is invalid as 0x80000000 is unsigned (C90/C++03) or long (C99/C++11) in
> type.
> Which means then overflow is not undefined but rather wrapping.

It's unsigned int for C99/C++11 too (see the different handling of
decimal-literals and other integer-literals in [lex.icon.type]).

This means that the result of the addition is also unsigned,
For the specific value of 0x80000000, the transformation is monotonic,
so the optimisation is valid and well-defined.

[Bug tree-optimization/94899] Failure to optimize out add before compare with INT_MIN

[cvs-commit at gcc dot gnu.org]

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

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

https://gcc.gnu.org/g:ab981aab92cbc71918fbaadcf6fa64bdb2b69be7

commit r13-1187-gab981aab92cbc71918fbaadcf6fa64bdb2b69be7
Author: Arjun Shankar <arjun@redhat.com>
Date:   Tue Jun 21 12:12:11 2022 +0200

    match.pd: Remove "+ 0x80000000" in int comparisons [PR94899]

    Expressions of the form "X + CST < Y + CST" where:

    * CST is an unsigned integer constant with only the MSB set, and
    * X and Y's types have integer conversion ranks <= CST's

    can be simplified to "(signed) X < (signed) Y".

    This is because, assuming a 32-bit signed numbers,
    (unsigned) INT_MIN + 0x80000000 is 0, and
    (unsigned) INT_MAX + 0x80000000 is UINT_MAX.

    i.e. the result increases monotonically with signed input.

    This means:
    ((signed) X < (signed) Y) iff (X + 0x80000000 < Y + 0x80000000)

    gcc/
            PR tree-optimization/94899
            * match.pd (X + C < Y + C -> (signed) X < (signed) Y, if C is
            0x80000000): New simplification.
    gcc/testsuite/
            * gcc.dg/pr94899.c: New test.

[Bug tree-optimization/94899] Failure to optimize out add before compare with INT_MIN

[gabravier at gmail dot com]

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

--- Comment #6 from Gabriel Ravier <gabravier at gmail dot com> ---
Can confirm that this appears to be fixed.

[Bug tree-optimization/94899] Failure to optimize out add before compare with INT_MIN

[gabravier at gmail dot com]

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

--- Comment #7 from Gabriel Ravier <gabravier at gmail dot com> ---
I don't know if I've missed something obvious but this still appears to be
fixed.

[Bug tree-optimization/94899] Failure to optimize out add before compare with INT_MIN

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |13.0
         Resolution|---                         |FIXED
             Status|NEW                         |RESOLVED

--- Comment #8 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Fixed.

[Bug tree-optimization/94899] Failure to optimize out add before compare with INT_MIN

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |davidfromonline at gmail dot com

--- Comment #9 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
*** Bug 105768 has been marked as a duplicate of this bug. ***