[v3] tree-optimization/94899: Remove "+ 0x80000000" in int comparisons

  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/
        * match.pd (X + C < Y + C -> (signed) X < (signed) Y, if C is
        0x80000000): New simplification.
gcc/testsuite/
        * gcc.dg/pr94899.c: New test.
---
 gcc/match.pd                   | 13 +++++++++
 gcc/testsuite/gcc.dg/pr94899.c | 48 ++++++++++++++++++++++++++++++++++
 2 files changed, 61 insertions(+)
 create mode 100644 gcc/testsuite/gcc.dg/pr94899.c
---
v2: https://gcc.gnu.org/pipermail/gcc-patches/2022-February/589709.html

Notes on v3, based on Richard and Jakub's review comments:

1. Canonicalized the match expression to avoid having to use ":c".
2. Redefined MAGIC in the test to avoid running afoul of 16-bit int
   machines.

Richard has approved this patch for inclusion in GCC 13:
https://gcc.gnu.org/pipermail/gcc-patches/2022-February/589852.html
  

On Fri, Jun 17, 2022 at 10:57 AM Arjun Shankar <arjun@redhat.com> wrote:
>
> 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/
>         * match.pd (X + C < Y + C -> (signed) X < (signed) Y, if C is
>         0x80000000): New simplification.
> gcc/testsuite/
>         * gcc.dg/pr94899.c: New test.
> ---
>  gcc/match.pd                   | 13 +++++++++
>  gcc/testsuite/gcc.dg/pr94899.c | 48 ++++++++++++++++++++++++++++++++++
>  2 files changed, 61 insertions(+)
>  create mode 100644 gcc/testsuite/gcc.dg/pr94899.c
> ---
> v2: https://gcc.gnu.org/pipermail/gcc-patches/2022-February/589709.html
>
> Notes on v3, based on Richard and Jakub's review comments:
>
> 1. Canonicalized the match expression to avoid having to use ":c".
> 2. Redefined MAGIC in the test to avoid running afoul of 16-bit int
>    machines.
>
> Richard has approved this patch for inclusion in GCC 13:
> https://gcc.gnu.org/pipermail/gcc-patches/2022-February/589852.html
>
> diff --git a/gcc/match.pd b/gcc/match.pd
> index 3e9572e4c9c..ef42611854a 100644
> --- a/gcc/match.pd
> +++ b/gcc/match.pd
> @@ -2080,6 +2080,19 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
>    (if (ANY_INTEGRAL_TYPE_P (TREE_TYPE (@0))
>         && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (@0)))
>     (op @0 @1))))
> +
> +/* As a special case, X + C < Y + C is the same as (signed) X < (signed) Y
> +   when C is an unsigned integer constant with only the MSB set, and X and
> +   Y have types of equal or lower integer conversion rank than C's.  */
> +(for op (lt le ge gt)
> + (simplify
> +  (op (plus @1 INTEGER_CST@0) (plus @2 INTEGER_CST@0))
> +  (if (INTEGRAL_TYPE_P (TREE_TYPE (@0))
> +       && TYPE_UNSIGNED (TREE_TYPE (@0))
> +       && wi::only_sign_bit_p (wi::to_wide (@0)))
> +   (with { tree stype = signed_type_for (TREE_TYPE (@0)); }
> +    (op (convert:stype @1) (convert:stype @2))))))
> +
>  /* For equality and subtraction, this is also true with wrapping overflow.  */
>  (for op (eq ne minus)
>   (simplify
> diff --git a/gcc/testsuite/gcc.dg/pr94899.c b/gcc/testsuite/gcc.dg/pr94899.c
> new file mode 100644
> index 00000000000..685201307ec
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/pr94899.c
> @@ -0,0 +1,48 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-optimized" } */
> +
> +typedef __INT16_TYPE__ int16_t;
> +typedef __INT32_TYPE__ int32_t;
> +typedef __UINT16_TYPE__ uint16_t;
> +typedef __UINT32_TYPE__ uint32_t;
> +
> +#define MAGIC (~ (uint32_t) 0 / 2 + 1)
> +
> +int
> +f_i16_i16 (int16_t x, int16_t y)
> +{
> +  return x + MAGIC < y + MAGIC;
> +}
> +
> +int
> +f_i16_i32 (int16_t x, int32_t y)
> +{
> +  return x + MAGIC < y + MAGIC;
> +}
> +
> +int
> +f_i32_i32 (int32_t x, int32_t y)
> +{
> +  return x + MAGIC < y + MAGIC;
> +}
> +
> +int
> +f_u32_i32 (uint32_t x, int32_t y)
> +{
> +  return x + MAGIC < y + MAGIC;
> +}
> +
> +int
> +f_u32_u32 (uint32_t x, uint32_t y)
> +{
> +  return x + MAGIC < y + MAGIC;
> +}
> +
> +int
> +f_i32_i32_sub (int32_t x, int32_t y)
> +{
> +  return x - MAGIC < y - MAGIC;
> +}
> +
> +/* The constants above should have been optimized away.  */
> +/* { dg-final { scan-tree-dump-times "2147483648" 0 "optimized"} } */

It might be possible to test for zero + or - operations instead?

OK otherwise.

Thanks,
Richard.

> --
> 2.35.3
>
  

On Mon, Jun 20, 2022 at 09:36:28AM +0200, Richard Biener wrote:
> > --- a/gcc/match.pd
> > +++ b/gcc/match.pd
> > @@ -2080,6 +2080,19 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
> >    (if (ANY_INTEGRAL_TYPE_P (TREE_TYPE (@0))
> >         && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (@0)))
> >     (op @0 @1))))
> > +
> > +/* As a special case, X + C < Y + C is the same as (signed) X < (signed) Y
> > +   when C is an unsigned integer constant with only the MSB set, and X and
> > +   Y have types of equal or lower integer conversion rank than C's.  */
> > +(for op (lt le ge gt)
> > + (simplify
> > +  (op (plus @1 INTEGER_CST@0) (plus @2 INTEGER_CST@0))

Can't one just omit the INTEGER_CST part on the second @0?

> > +  (if (INTEGRAL_TYPE_P (TREE_TYPE (@0))
> > +       && TYPE_UNSIGNED (TREE_TYPE (@0))
> > +       && wi::only_sign_bit_p (wi::to_wide (@0)))
> > +   (with { tree stype = signed_type_for (TREE_TYPE (@0)); }
> > +    (op (convert:stype @1) (convert:stype @2))))))

As a follow-up, it might be useful to make it work for vector integral types
too,
typedef unsigned V __attribute__((vector_size (4 * sizeof (int))));
#define M __INT_MAX__ + 1U
V foo (V x, V y)
{
  return x + (V) { M, M, M, M } < y + (V) { M, M, M, M };
}
using uniform_integer_cst_p.

	Jakub
  

On Mon, Jun 20, 2022 at 10:38 AM Jakub Jelinek <jakub@redhat.com> wrote:
>
> On Mon, Jun 20, 2022 at 09:36:28AM +0200, Richard Biener wrote:
> > > --- a/gcc/match.pd
> > > +++ b/gcc/match.pd
> > > @@ -2080,6 +2080,19 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
> > >    (if (ANY_INTEGRAL_TYPE_P (TREE_TYPE (@0))
> > >         && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (@0)))
> > >     (op @0 @1))))
> > > +
> > > +/* As a special case, X + C < Y + C is the same as (signed) X < (signed) Y
> > > +   when C is an unsigned integer constant with only the MSB set, and X and
> > > +   Y have types of equal or lower integer conversion rank than C's.  */
> > > +(for op (lt le ge gt)
> > > + (simplify
> > > +  (op (plus @1 INTEGER_CST@0) (plus @2 INTEGER_CST@0))
>
> Can't one just omit the INTEGER_CST part on the second @0?

Ah, yes.

> > > +  (if (INTEGRAL_TYPE_P (TREE_TYPE (@0))
> > > +       && TYPE_UNSIGNED (TREE_TYPE (@0))
> > > +       && wi::only_sign_bit_p (wi::to_wide (@0)))
> > > +   (with { tree stype = signed_type_for (TREE_TYPE (@0)); }
> > > +    (op (convert:stype @1) (convert:stype @2))))))
>
> As a follow-up, it might be useful to make it work for vector integral types
> too,
> typedef unsigned V __attribute__((vector_size (4 * sizeof (int))));
> #define M __INT_MAX__ + 1U
> V foo (V x, V y)
> {
>   return x + (V) { M, M, M, M } < y + (V) { M, M, M, M };
> }
> using uniform_integer_cst_p.
>
>         Jakub
>