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

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

[Arjun Shankar]

[-- Attachment #1: Type: text/plain, Size: 573 bytes --]

Expressions of the form "X + CST < Y + CST" where X and Y are of int
type and CST is of unsigned type with only the MSB on can be simplified
to "X < Y" because "X + 0x80000000" increases monotonically with X.

gcc/
        * match.pd (X + C < Y + C -> X < Y, if C is 0x80000000): New
        simplification.
gcc/testsuite/
        * gcc.dg/pr94899.c: New test.
---
 gcc/match.pd                   | 18 ++++++++++++++++++
 gcc/testsuite/gcc.dg/pr94899.c | 28 ++++++++++++++++++++++++++++
 2 files changed, 46 insertions(+)
 create mode 100644 gcc/testsuite/gcc.dg/pr94899.c

[-- Attachment #2: pr94899.patch --]
[-- Type: text/x-patch, Size: 1957 bytes --]

diff --git a/gcc/match.pd b/gcc/match.pd
index b942cb2930a..49ac0c43f83 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -1975,6 +1975,24 @@ 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 X < Y even with wrapping
+   overflow if X and Y are signed integers of the same size, and C is an
+   unsigned constant with all bits except MSB set to 0 and size >= that of
+   X/Y.  */
+(for op (lt le ge gt)
+ (simplify
+  (op (plus:c (convert@0 @1) @4) (plus:c (convert@2 @3) @4))
+  (if (CONSTANT_CLASS_P (@4)
+       && TYPE_UNSIGNED (TREE_TYPE (@4))
+       && !TYPE_UNSIGNED (TREE_TYPE (@1))
+       && !TYPE_UNSIGNED (TREE_TYPE (@3))
+       && (TYPE_PRECISION (TREE_TYPE (@1)) == TYPE_PRECISION (TREE_TYPE (@3)))
+       && (TYPE_PRECISION (TREE_TYPE (@1)) <= TYPE_PRECISION (TREE_TYPE (@4)))
+       && wi::only_sign_bit_p (wi::to_wide (@4),
+                               TYPE_PRECISION (TREE_TYPE (@0))))
+   (op @1 @3))))
+
 /* 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..304aaf3c6e6
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr94899.c
@@ -0,0 +1,28 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-original" } */
+
+typedef __INT16_TYPE__ int16_t;
+typedef __INT32_TYPE__ int32_t;
+
+#define MAGIC 0x80000000
+
+int
+f_i16_i16 (int16_t x, int16_t y)
+{
+  return x + MAGIC < y + MAGIC;
+}
+
+int
+f_i32_i32 (int32_t x, int32_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 "original"} } */
-- 
2.31.1

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

[Richard Biener]

On Tue, Feb 1, 2022 at 5:54 AM Arjun Shankar via Gcc-patches
<gcc-patches@gcc.gnu.org> wrote:
>
> Expressions of the form "X + CST < Y + CST" where X and Y are of int
> type and CST is of unsigned type with only the MSB on can be simplified
> to "X < Y" because "X + 0x80000000" increases monotonically with X.

+/* As a special case, X + C < Y + C is the same as X < Y even with wrapping
+   overflow if X and Y are signed integers of the same size, and C is an
+   unsigned constant with all bits except MSB set to 0 and size >= that of
+   X/Y.  */
+(for op (lt le ge gt)
+ (simplify
+  (op (plus:c (convert@0 @1) @4) (plus:c (convert@2 @3) @4))
+  (if (CONSTANT_CLASS_P (@4)
+       && TYPE_UNSIGNED (TREE_TYPE (@4))

why include (convert ..) here?  It looks like you could do without,
merging the special case with the preceding pattern and let a followup
pattern simplify (lt (convert @1) (convert @2)) instead?

> gcc/
>         * match.pd (X + C < Y + C -> X < Y, if C is 0x80000000): New
>         simplification.
> gcc/testsuite/
>         * gcc.dg/pr94899.c: New test.
> ---
>  gcc/match.pd                   | 18 ++++++++++++++++++
>  gcc/testsuite/gcc.dg/pr94899.c | 28 ++++++++++++++++++++++++++++
>  2 files changed, 46 insertions(+)
>  create mode 100644 gcc/testsuite/gcc.dg/pr94899.c

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

[Arjun Shankar]

> +/* As a special case, X + C < Y + C is the same as X < Y even with wrapping
> +   overflow if X and Y are signed integers of the same size, and C is an
> +   unsigned constant with all bits except MSB set to 0 and size >= that of
> +   X/Y.  */
> +(for op (lt le ge gt)
> + (simplify
> +  (op (plus:c (convert@0 @1) @4) (plus:c (convert@2 @3) @4))
> +  (if (CONSTANT_CLASS_P (@4)
> +       && TYPE_UNSIGNED (TREE_TYPE (@4))
>
> why include (convert ..) here?  It looks like you could do without,
> merging the special case with the preceding pattern and let a followup
> pattern simplify (lt (convert @1) (convert @2)) instead?

Thanks for taking a look at this patch.

It looks like the convert and plus need to be taken into account
together when applying this simplification.

1. 0x80000000 is *just* large enough to be interpreted as an unsigned.

2. So, an expression like...

x + 0x80000000 < y + 0x80000000;

...where x and y are signed actually gets interpreted as:

(unsigned) x + 0x80000000 < (unsigned) y + 0x80000000

3. Now, adding 0x80000000 to (unsigned) INT_MIN gives us 0,
and adding it to (unsigned) INT_MAX gives us UINT_MAX.

4. So, if x < y is true when they are compared as signed integers, then...
(unsigned) x + 0x80000000 < (unsigned) y + 0x80000000
...will also be true.

5. i.e. the unsigned comparison must be replaced by a signed
comparison when we remove the constant, and so the constant and
convert need to be matched and removed together.

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

[Richard Biener]

On Tue, Feb 1, 2022 at 4:21 PM Arjun Shankar <arjun@redhat.com> wrote:
>
> > +/* As a special case, X + C < Y + C is the same as X < Y even with wrapping
> > +   overflow if X and Y are signed integers of the same size, and C is an
> > +   unsigned constant with all bits except MSB set to 0 and size >= that of
> > +   X/Y.  */
> > +(for op (lt le ge gt)
> > + (simplify
> > +  (op (plus:c (convert@0 @1) @4) (plus:c (convert@2 @3) @4))
> > +  (if (CONSTANT_CLASS_P (@4)
> > +       && TYPE_UNSIGNED (TREE_TYPE (@4))
> >
> > why include (convert ..) here?  It looks like you could do without,
> > merging the special case with the preceding pattern and let a followup
> > pattern simplify (lt (convert @1) (convert @2)) instead?
>
> Thanks for taking a look at this patch.
>
> It looks like the convert and plus need to be taken into account
> together when applying this simplification.
>
> 1. 0x80000000 is *just* large enough to be interpreted as an unsigned.
>
> 2. So, an expression like...
>
> x + 0x80000000 < y + 0x80000000;
>
> ...where x and y are signed actually gets interpreted as:
>
> (unsigned) x + 0x80000000 < (unsigned) y + 0x80000000
>
> 3. Now, adding 0x80000000 to (unsigned) INT_MIN gives us 0,
> and adding it to (unsigned) INT_MAX gives us UINT_MAX.
>
> 4. So, if x < y is true when they are compared as signed integers, then...
> (unsigned) x + 0x80000000 < (unsigned) y + 0x80000000
> ...will also be true.
>
> 5. i.e. the unsigned comparison must be replaced by a signed
> comparison when we remove the constant, and so the constant and
> convert need to be matched and removed together.

Oh, I see - that's very special then and the pattern in the comment
does not include this conversion.  I think you can simplify the checking
done by requiring types_match (TREE_TYPE (@1), TREE_TYPE (@3))
and by noting that the types of @0, @2 and @4 are the same
(you don't seem to use @2).

I wonder how relevant these kind of patterns are?  Probably clang
catches this simplification while we don't?

Btw, you fail to check for INTEGRAL_TYPE_P, the whole thing
would also match floats as-is, I think the easiest thing would be to
change the match to

+  (op (plus:c (convert@0 @1) INTEGER_CST@4) (plus:c (convert@2 @3)
INTEGER_CST@4))

where you then also can elide the CONSTANT_CLASS_P (@4) check.

Btw, for

  unsigned x, y;
  if (x + 0x80000000 < y + 0x80000000)

it would be valid to transform this into

  if ((int)x < (int)y)

which is a simplification that's worthwhile as well I think?  So we
might not actually
need the (convert ...) but rely on (convert (convert @0)) being
simplfiied?  You'd
then use

 (with { stype = signed_type_for (TREE_TYPE (@1)); }
  (op (convert:stype @1) (convert:stype @3)))

as transform.

Thanks,
Richard.

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

[Arjun Shankar]

Hi Richard,

> Oh, I see - that's very special then and the pattern in the comment
> does not include this conversion.  I think you can simplify the checking
> done by requiring types_match (TREE_TYPE (@1), TREE_TYPE (@3))
> and by noting that the types of @0, @2 and @4 are the same
> (you don't seem to use @2).
>
> I wonder how relevant these kind of patterns are?  Probably clang
> catches this simplification while we don't?

Yes. The bug report was based on a comparison with clang.

> Btw, you fail to check for INTEGRAL_TYPE_P, the whole thing
> would also match floats as-is, I think the easiest thing would be to
> change the match to
>
> +  (op (plus:c (convert@0 @1) INTEGER_CST@4) (plus:c (convert@2 @3)
> INTEGER_CST@4))
>
> where you then also can elide the CONSTANT_CLASS_P (@4) check.

Thanks. I did miss checking for INTEGRAL_TYPE_P, and I didn't think to
use INTEGER_CST.

> Btw, for
>
>   unsigned x, y;
>   if (x + 0x80000000 < y + 0x80000000)
>
> it would be valid to transform this into
>
>   if ((int)x < (int)y)
>
> which is a simplification that's worthwhile as well I think?  So we
> might not actually
> need the (convert ...) but rely on (convert (convert @0)) being
> simplfiied?  You'd
> then use
>
>  (with { stype = signed_type_for (TREE_TYPE (@1)); }
>   (op (convert:stype @1) (convert:stype @3)))
>
> as transform.

Thank you for all the hints! I'm going to work a v2 based on these.

Cheers,
Arjun

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

[Arjun Shankar]

[-- Attachment #1: Type: text/plain, Size: 1586 bytes --]

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
---
v1: https://gcc.gnu.org/pipermail/gcc-patches/2022-February/589557.html

Notes on v2, based on Richard's review comments:

1. I removed matching on "convert", and therefore also replaced the
removal of convert upon simplification with an explicit cast to
signed. I originally thought this simplification only applies to
signed operands that have been cast to unsigned, but thinking about
it, it became clear that they do not necessarily have to be signed
originally. The simplification is now a bit more general.

2. Removed checks for operands' types as it seems to be unnecessary. I
hope this is correct.

3. Added unsigned types and mismatched sizes of operands to the test.
These are now simplified.

[-- Attachment #2: pr94899-v2.patch --]
[-- Type: text/x-patch, Size: 2050 bytes --]

diff --git a/gcc/match.pd b/gcc/match.pd
index b942cb2930a..fabb06c6808 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -1975,6 +1975,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:c INTEGER_CST@0 @1) (plus:c INTEGER_CST@0 @2))
+  (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..f47120988b7
--- /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 0x80000000
+
+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"} } */
-- 
2.34.1

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

[Richard Biener]

On Thu, Feb 3, 2022 at 4:50 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)

+  (op (plus:c INTEGER_CST@0 @1) (plus:c INTEGER_CST@0 @2))

INTEGER_CST are put last by canonicalization so you should write

  (op (plus @1 INTEGER_CST@0) (plus @2 INTEGER_CST@0))

and thus omit the :c.

+#define MAGIC 0x80000000

I _think_ writing the constant this way requires

/* { dg-require-effective-target int32plus } */

as on a target where int is 16 bits it possibly yields a diagnostic?
I've been using explicit int32_t types w/o such effective target
in the past but I'm not sure how to write an explicit precision
constant to avoid diagnostics.

Note I didn't actually check we get a diagnostic ...

Slapping on the dg-requires-effective-target should be safe though.

Otherwise looks good now - note this has to wait for stage1 of GCC 13,
so make sure to ping then or commit then in case you have git access.

Thanks,
Richard.

> 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
> ---
> v1: https://gcc.gnu.org/pipermail/gcc-patches/2022-February/589557.html
>
> Notes on v2, based on Richard's review comments:
>
> 1. I removed matching on "convert", and therefore also replaced the
> removal of convert upon simplification with an explicit cast to
> signed. I originally thought this simplification only applies to
> signed operands that have been cast to unsigned, but thinking about
> it, it became clear that they do not necessarily have to be signed
> originally. The simplification is now a bit more general.
>
> 2. Removed checks for operands' types as it seems to be unnecessary. I
> hope this is correct.
>
> 3. Added unsigned types and mismatched sizes of operands to the test.
> These are now simplified.

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

[Jakub Jelinek]

On Fri, Feb 04, 2022 at 12:14:33PM +0100, Richard Biener via Gcc-patches wrote:
> +#define MAGIC 0x80000000
> 
> I _think_ writing the constant this way requires

Perhaps use (~(uint32_t)0 / 2 + 1) as MAGIC instead?
Then it doesn't actually require that uint32_t actually is exactly 32 bits.
On the other side the regex checks for the exact 32-bit constant.

	Jakub

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

[Richard Biener]

On Fri, Feb 4, 2022 at 12:50 PM Jakub Jelinek <jakub@redhat.com> wrote:
>
> On Fri, Feb 04, 2022 at 12:14:33PM +0100, Richard Biener via Gcc-patches wrote:
> > +#define MAGIC 0x80000000
> >
> > I _think_ writing the constant this way requires
>
> Perhaps use (~(uint32_t)0 / 2 + 1) as MAGIC instead?
> Then it doesn't actually require that uint32_t actually is exactly 32 bits.
> On the other side the regex checks for the exact 32-bit constant.

I think uint32_t always is 32-bit in practice, compared to unsigned
int which is not.

Richard.

>         Jakub
>