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

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

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

> +/* 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.

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.

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