[PATCH] Implement one optimization from build_range_check in match.pd (PR tree-optimization/81346)

[PATCH] Implement one optimization from build_range_check in match.pd (PR tree-optimization/81346)

[Jakub Jelinek]

Hi!

The following patch implements the:
  /* Optimize (c>=1) && (c<=127) into (signed char)c > 0.  */
  if (integer_onep (low) && TREE_CODE (high) == INTEGER_CST)
    {
      int prec = TYPE_PRECISION (etype);

      if (wi::mask (prec - 1, false, prec) == high)
        {
          if (TYPE_UNSIGNED (etype))
            {
              tree signed_etype = signed_type_for (etype);
              if (TYPE_PRECISION (signed_etype) != TYPE_PRECISION (etype))
                etype
                  = build_nonstandard_integer_type (TYPE_PRECISION (etype), 0);
              else
                etype = signed_etype;
              exp = fold_convert_loc (loc, etype, exp);
            }
          return fold_build2_loc (loc, GT_EXPR, type, exp,
                              build_int_cst (etype, 0));
        }
    }
optimization from build_range_check in match.pd if we already have the
less efficient x-1U <= 127U-1U.  If somebody writes the range test
as x>=1 && x <= 127, then it is already optimized well, but if somebody
writes it as x-1U <= 126U, then it is not without this patch.

Bootstrapped/regtested on x86_64-linux and i686-linux.

In the PR Marc noted that the optimization might be useful even for
constants other than 1, by transforming
x+C1 <= C2 if unsigned and C2-C1==INT_MAX into (int)x > (int)(-1-C1).
Shall I do that immediately, or incrementally?  Shall we also change
build_range_check to do that (i.e. drop the integer_onep above and use
right etype constant?  Also, I think the build_nonstandard_integer_type
above is unnecessary, I think signed_type_for does already call that.

2017-07-18  Jakub Jelinek  <jakub@redhat.com>

	PR tree-optimization/81346
	* match.pd: Optimize (X - 1U) <= INT_MAX-1U into (int) X > 0.

	* gcc.dg/tree-ssa/pr81346-5.c: New test.

--- gcc/match.pd.jj	2017-07-17 16:25:20.000000000 +0200
+++ gcc/match.pd	2017-07-18 12:32:52.896924558 +0200
@@ -1125,6 +1125,19 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
 	&& wi::neg_p (@1, TYPE_SIGN (TREE_TYPE (@1))))
     (cmp @2 @0))))))
 
+/* (X - 1U) <= INT_MAX-1U into (int) X > 0.  */
+(for cmp (le gt)
+     icmp (gt le)
+ (simplify
+  (cmp (plus @0 integer_minus_onep@1) INTEGER_CST@2)
+   (if (INTEGRAL_TYPE_P (TREE_TYPE (@0))
+	&& TYPE_UNSIGNED (TREE_TYPE (@0))
+	&& TYPE_PRECISION (TREE_TYPE (@0)) > 1
+	&& wi::eq_p (@2, wi::max_value (TYPE_PRECISION (TREE_TYPE (@0)),
+					SIGNED) - 1))
+    (with { tree stype = signed_type_for (TREE_TYPE (@0)); }
+     (icmp (convert:stype @0) { build_int_cst (stype, 0); })))))
+
 /* X / 4 < Y / 4 iff X < Y when the division is known to be exact.  */
 (for cmp (simple_comparison)
  (simplify
--- gcc/testsuite/gcc.dg/tree-ssa/pr81346-5.c.jj	2017-07-18 12:35:27.406063800 +0200
+++ gcc/testsuite/gcc.dg/tree-ssa/pr81346-5.c	2017-07-18 12:37:04.460894965 +0200
@@ -0,0 +1,17 @@
+/* PR tree-optimization/81346 */
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+/* { dg-final { scan-tree-dump-times "\\(signed int\\) x" 10 "optimized" } } */
+/* { dg-final { scan-tree-dump-times " <= 0;" 5 "optimized" } } */
+/* { dg-final { scan-tree-dump-times " > 0;" 5 "optimized" } } */
+
+int f1 (unsigned x) { return x - 1 <= __INT_MAX__ - 1; }
+int f2 (unsigned x) { unsigned a = 1, b = __INT_MAX__ - 1; return x - a <= b; }
+int f3 (unsigned x) { return x - 1 < __INT_MAX__; }
+int f4 (unsigned x) { unsigned a = 1, b = __INT_MAX__; return x - a < b; }
+int f5 (unsigned x) { return x >= 1 && x <= __INT_MAX__; }
+int f6 (unsigned x) { return x - 1 > __INT_MAX__ - 1; }
+int f7 (unsigned x) { unsigned a = 1, b = __INT_MAX__ - 1; return x - a > b; }
+int f8 (unsigned x) { return x - 1 >= __INT_MAX__; }
+int f9 (unsigned x) { unsigned a = 1, b = __INT_MAX__; return x - a >= b; }
+int f10 (unsigned x) { return x < 1 || x > __INT_MAX__; }

	Jakub

Re: [PATCH] Implement one optimization from build_range_check in match.pd (PR tree-optimization/81346)

[Martin Sebor]

> --- gcc/match.pd.jj	2017-07-17 16:25:20.000000000 +0200
> +++ gcc/match.pd	2017-07-18 12:32:52.896924558 +0200
> @@ -1125,6 +1125,19 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
>  	&& wi::neg_p (@1, TYPE_SIGN (TREE_TYPE (@1))))
>      (cmp @2 @0))))))
>
> +/* (X - 1U) <= INT_MAX-1U into (int) X > 0.  */

Since the transformation applies to other types besides int I
suggest to make it clear in the comment.  E.g., something like:

   /* (X - 1U) <= TYPE_MAX - 1U into (TYPE) X > 0 for any integer
      TYPE.  */

(with spaces around all the operators as per GCC coding style).

Martin

Re: [PATCH] Implement one optimization from build_range_check in match.pd (PR tree-optimization/81346)

[Marc Glisse]

On Tue, 18 Jul 2017, Jakub Jelinek wrote:

> In the PR Marc noted that the optimization might be useful even for
> constants other than 1, by transforming
> x+C1 <= C2 if unsigned and C2-C1==INT_MAX into (int)x > (int)(-1-C1).

(int)x >= (int)(-C1) might be easier (and more valid, except that the only 
case where that makes a difference seems to be when C2==UINT_MAX, in which 
case we could hope not to reach this transformation).

> Shall I do that immediately, or incrementally?

I vote for "incremental", unless someone finds an issue with your current 
patch.

> Shall we also change build_range_check to do that (i.e. drop the 
> integer_onep above and use right etype constant?

I would rather consider build_range_check legacy and avoid modifying it 
too much, but if you are motivated...

> +	&& TYPE_PRECISION (TREE_TYPE (@0)) > 1

I see you've been bitten in the past ;-)

-- 
Marc Glisse

Re: [PATCH] Implement one optimization from build_range_check in match.pd (PR tree-optimization/81346)

[Jakub Jelinek]

On Tue, Jul 18, 2017 at 09:31:11AM -0600, Martin Sebor wrote:
> > --- gcc/match.pd.jj	2017-07-17 16:25:20.000000000 +0200
> > +++ gcc/match.pd	2017-07-18 12:32:52.896924558 +0200
> > @@ -1125,6 +1125,19 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
> >  	&& wi::neg_p (@1, TYPE_SIGN (TREE_TYPE (@1))))
> >      (cmp @2 @0))))))
> > 
> > +/* (X - 1U) <= INT_MAX-1U into (int) X > 0.  */
> 
> Since the transformation applies to other types besides int I
> suggest to make it clear in the comment.  E.g., something like:
> 
>   /* (X - 1U) <= TYPE_MAX - 1U into (TYPE) X > 0 for any integer
>      TYPE.  */
> 
> (with spaces around all the operators as per GCC coding style).

I think many of the match.pd comments are also not fully generic
to describe what it does, just to give an idea what it does.
The above isn't correct either, because it isn't for any integer TYPE,
there needs to be a signed and corresponding unsigned type involved,
X is of the unsigned type, so is the 1.  And TYPE_MAX is actually
the signed type's maximum cast to unsigned type.  And the reason for not putting
spaces around - in the second case was an attempt to give a hint that
it is comparison against a INT_MAX-1U constant, not another subtraction.
After all, the pattern doesn't handle subtraction, because that isn't
what is in the IL, but addition, i.e. X + -1U.
And, the <= -> > is just one possibility, the pattern also handles
> -> <=.

Examples of other comments that "suffer" from similar lack of sufficient
genericity, but perhaps are good enough to let somebody understand it
quickly:
/* Avoid this transformation if C is INT_MIN, i.e. C == -C.  */
      /* Avoid this transformation if X might be INT_MIN or
         Y might be -1, because we would then change valid
         INT_MIN % -(-1) into invalid INT_MIN % -1.  */
       /* If the constant operation overflows we cannot do the transform
          directly as we would introduce undefined overflow, for example
          with (a - 1) + INT_MIN.  */
          /* X+INT_MAX+1 is X-INT_MIN.  */

	Jakub

Re: [PATCH] Implement one optimization from build_range_check in match.pd (PR tree-optimization/81346)

[Jakub Jelinek]

On Tue, Jul 18, 2017 at 05:35:54PM +0200, Marc Glisse wrote:
> On Tue, 18 Jul 2017, Jakub Jelinek wrote:
> 
> > In the PR Marc noted that the optimization might be useful even for
> > constants other than 1, by transforming
> > x+C1 <= C2 if unsigned and C2-C1==INT_MAX into (int)x > (int)(-1-C1).
> 
> (int)x >= (int)(-C1) might be easier (and more valid, except that the only
> case where that makes a difference seems to be when C2==UINT_MAX, in which
> case we could hope not to reach this transformation).

Don't we canonicalize that (int)x >= (int)(-C1) to (int)x > (int)(-1-C1)
immediately though?

> > +	&& TYPE_PRECISION (TREE_TYPE (@0)) > 1
> 
> I see you've been bitten in the past ;-)

Many times ;)

	Jakub

Re: [PATCH] Implement one optimization from build_range_check in match.pd (PR tree-optimization/81346)

[Marc Glisse]

On Tue, 18 Jul 2017, Jakub Jelinek wrote:

> On Tue, Jul 18, 2017 at 05:35:54PM +0200, Marc Glisse wrote:
>> On Tue, 18 Jul 2017, Jakub Jelinek wrote:
>>
>>> In the PR Marc noted that the optimization might be useful even for
>>> constants other than 1, by transforming
>>> x+C1 <= C2 if unsigned and C2-C1==INT_MAX into (int)x > (int)(-1-C1).
>>
>> (int)x >= (int)(-C1) might be easier (and more valid, except that the only
>> case where that makes a difference seems to be when C2==UINT_MAX, in which
>> case we could hope not to reach this transformation).
>
> Don't we canonicalize that (int)x >= (int)(-C1) to (int)x > (int)(-1-C1)
> immediately though?

We probably don't canonicalize (int)x >= INT_MIN to (int)x > INT_MAX ;-) 
(what I was suggesting essentially delegates the check for INT_MIN or 
overflow to the canonicalization code)

-- 
Marc Glisse

Re: [PATCH] Implement one optimization from build_range_check in match.pd (PR tree-optimization/81346)

[Martin Sebor]

On 07/18/2017 09:43 AM, Jakub Jelinek wrote:
> On Tue, Jul 18, 2017 at 09:31:11AM -0600, Martin Sebor wrote:
>>> --- gcc/match.pd.jj	2017-07-17 16:25:20.000000000 +0200
>>> +++ gcc/match.pd	2017-07-18 12:32:52.896924558 +0200
>>> @@ -1125,6 +1125,19 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
>>>  	&& wi::neg_p (@1, TYPE_SIGN (TREE_TYPE (@1))))
>>>      (cmp @2 @0))))))
>>>
>>> +/* (X - 1U) <= INT_MAX-1U into (int) X > 0.  */
>>
>> Since the transformation applies to other types besides int I
>> suggest to make it clear in the comment.  E.g., something like:
>>
>>   /* (X - 1U) <= TYPE_MAX - 1U into (TYPE) X > 0 for any integer
>>      TYPE.  */
>>
>> (with spaces around all the operators as per GCC coding style).
>
> I think many of the match.pd comments are also not fully generic
> to describe what it does, just to give an idea what it does.
...
> Examples of other comments that "suffer" from similar lack of sufficient
> genericity, but perhaps are good enough to let somebody understand it
> quickly:

Sure, but that doesn't make them a good example to follow.  As
someone pointed out to me in code reviews, existing deviations
from the preferred style, whether documented or not, or lack of
clarity, aren't a license to add more.  Please take my suggestion
here in the same constructive spirit.

Martin

Re: [PATCH] Implement one optimization from build_range_check in match.pd (PR tree-optimization/81346)

[Jakub Jelinek]

On Tue, Jul 18, 2017 at 10:47:37AM -0600, Martin Sebor wrote:
> On 07/18/2017 09:43 AM, Jakub Jelinek wrote:
> > On Tue, Jul 18, 2017 at 09:31:11AM -0600, Martin Sebor wrote:
> > > > --- gcc/match.pd.jj	2017-07-17 16:25:20.000000000 +0200
> > > > +++ gcc/match.pd	2017-07-18 12:32:52.896924558 +0200
> > > > @@ -1125,6 +1125,19 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
> > > >  	&& wi::neg_p (@1, TYPE_SIGN (TREE_TYPE (@1))))
> > > >      (cmp @2 @0))))))
> > > > 
> > > > +/* (X - 1U) <= INT_MAX-1U into (int) X > 0.  */
> > > 
> > > Since the transformation applies to other types besides int I
> > > suggest to make it clear in the comment.  E.g., something like:
> > > 
> > >   /* (X - 1U) <= TYPE_MAX - 1U into (TYPE) X > 0 for any integer
> > >      TYPE.  */
> > > 
> > > (with spaces around all the operators as per GCC coding style).
> > 
> > I think many of the match.pd comments are also not fully generic
> > to describe what it does, just to give an idea what it does.
> ...
> > Examples of other comments that "suffer" from similar lack of sufficient
> > genericity, but perhaps are good enough to let somebody understand it
> > quickly:
> 
> Sure, but that doesn't make them a good example to follow.  As
> someone pointed out to me in code reviews, existing deviations
> from the preferred style, whether documented or not, or lack of
> clarity, aren't a license to add more.  Please take my suggestion
> here in the same constructive spirit.

The point I'm trying to make is that in order to make the
comments generic enough they will be too large and too hard to parse.
IMHO sometimes it is better to just give an example of what it
does, and those who want to read all the details on what exactly it does,
there is the simplify below it with all the details.
Consider another randomly chosen comment:
 /* hypot(x,x) -> fabs(x)*sqrt(2).  */
This also isn't describing generically what it does, because
it handles not just hypot ->fabs*sqrt, but also hypotl ->fabsl*sqrtl,
hypotf ->fabsf*sqrtf, maybe others.

In the end, it is Richard's call on what he wants to have in match.pd
comments.

	Jakub

Re: [PATCH] Implement one optimization from build_range_check in match.pd (PR tree-optimization/81346)

[Richard Biener]

On Tue, 18 Jul 2017, Jakub Jelinek wrote:

> On Tue, Jul 18, 2017 at 10:47:37AM -0600, Martin Sebor wrote:
> > On 07/18/2017 09:43 AM, Jakub Jelinek wrote:
> > > On Tue, Jul 18, 2017 at 09:31:11AM -0600, Martin Sebor wrote:
> > > > > --- gcc/match.pd.jj	2017-07-17 16:25:20.000000000 +0200
> > > > > +++ gcc/match.pd	2017-07-18 12:32:52.896924558 +0200
> > > > > @@ -1125,6 +1125,19 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
> > > > >  	&& wi::neg_p (@1, TYPE_SIGN (TREE_TYPE (@1))))
> > > > >      (cmp @2 @0))))))
> > > > > 
> > > > > +/* (X - 1U) <= INT_MAX-1U into (int) X > 0.  */
> > > > 
> > > > Since the transformation applies to other types besides int I
> > > > suggest to make it clear in the comment.  E.g., something like:
> > > > 
> > > >   /* (X - 1U) <= TYPE_MAX - 1U into (TYPE) X > 0 for any integer
> > > >      TYPE.  */
> > > > 
> > > > (with spaces around all the operators as per GCC coding style).
> > > 
> > > I think many of the match.pd comments are also not fully generic
> > > to describe what it does, just to give an idea what it does.
> > ...
> > > Examples of other comments that "suffer" from similar lack of sufficient
> > > genericity, but perhaps are good enough to let somebody understand it
> > > quickly:
> > 
> > Sure, but that doesn't make them a good example to follow.  As
> > someone pointed out to me in code reviews, existing deviations
> > from the preferred style, whether documented or not, or lack of
> > clarity, aren't a license to add more.  Please take my suggestion
> > here in the same constructive spirit.
> 
> The point I'm trying to make is that in order to make the
> comments generic enough they will be too large and too hard to parse.
> IMHO sometimes it is better to just give an example of what it
> does, and those who want to read all the details on what exactly it does,
> there is the simplify below it with all the details.
> Consider another randomly chosen comment:
>  /* hypot(x,x) -> fabs(x)*sqrt(2).  */
> This also isn't describing generically what it does, because
> it handles not just hypot ->fabs*sqrt, but also hypotl ->fabsl*sqrtl,
> hypotf ->fabsf*sqrtf, maybe others.
> 
> In the end, it is Richard's call on what he wants to have in match.pd
> comments.

Generally one example that gives an idea what the pattern does is
fine, enumarating all variants is usually too noisy.  When we can
make them more generic without making them harder to understand
I'm all for it but I have no strong opinion here (but I would ask
to not simply repeat the pattern description for all cases covered).

Richard.

Re: [PATCH] Implement one optimization from build_range_check in match.pd (PR tree-optimization/81346)

[Richard Biener]

On Tue, 18 Jul 2017, Jakub Jelinek wrote:

> Hi!
> 
> The following patch implements the:
>   /* Optimize (c>=1) && (c<=127) into (signed char)c > 0.  */
>   if (integer_onep (low) && TREE_CODE (high) == INTEGER_CST)
>     {
>       int prec = TYPE_PRECISION (etype);
> 
>       if (wi::mask (prec - 1, false, prec) == high)
>         {
>           if (TYPE_UNSIGNED (etype))
>             {
>               tree signed_etype = signed_type_for (etype);
>               if (TYPE_PRECISION (signed_etype) != TYPE_PRECISION (etype))
>                 etype
>                   = build_nonstandard_integer_type (TYPE_PRECISION (etype), 0);
>               else
>                 etype = signed_etype;
>               exp = fold_convert_loc (loc, etype, exp);
>             }
>           return fold_build2_loc (loc, GT_EXPR, type, exp,
>                               build_int_cst (etype, 0));
>         }
>     }
> optimization from build_range_check in match.pd if we already have the
> less efficient x-1U <= 127U-1U.  If somebody writes the range test
> as x>=1 && x <= 127, then it is already optimized well, but if somebody
> writes it as x-1U <= 126U, then it is not without this patch.
> 
> Bootstrapped/regtested on x86_64-linux and i686-linux.
> 
> In the PR Marc noted that the optimization might be useful even for
> constants other than 1, by transforming
> x+C1 <= C2 if unsigned and C2-C1==INT_MAX into (int)x > (int)(-1-C1).
> Shall I do that immediately, or incrementally?  Shall we also change
> build_range_check to do that (i.e. drop the integer_onep above and use
> right etype constant?  Also, I think the build_nonstandard_integer_type
> above is unnecessary, I think signed_type_for does already call that.

Yeah, that's legacy from the times signed_type_for used the langhook.

Let's do any improvements incrementally.  I, too, woudln't worry
about enhancing the fold-const.c variant unless proven necessary
by testcases from real-wrold code.

Patch is ok.

Thanks,
Richard.

> 2017-07-18  Jakub Jelinek  <jakub@redhat.com>
> 
> 	PR tree-optimization/81346
> 	* match.pd: Optimize (X - 1U) <= INT_MAX-1U into (int) X > 0.
> 
> 	* gcc.dg/tree-ssa/pr81346-5.c: New test.
> 
> --- gcc/match.pd.jj	2017-07-17 16:25:20.000000000 +0200
> +++ gcc/match.pd	2017-07-18 12:32:52.896924558 +0200
> @@ -1125,6 +1125,19 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
>  	&& wi::neg_p (@1, TYPE_SIGN (TREE_TYPE (@1))))
>      (cmp @2 @0))))))
>  
> +/* (X - 1U) <= INT_MAX-1U into (int) X > 0.  */
> +(for cmp (le gt)
> +     icmp (gt le)
> + (simplify
> +  (cmp (plus @0 integer_minus_onep@1) INTEGER_CST@2)
> +   (if (INTEGRAL_TYPE_P (TREE_TYPE (@0))
> +	&& TYPE_UNSIGNED (TREE_TYPE (@0))
> +	&& TYPE_PRECISION (TREE_TYPE (@0)) > 1
> +	&& wi::eq_p (@2, wi::max_value (TYPE_PRECISION (TREE_TYPE (@0)),
> +					SIGNED) - 1))
> +    (with { tree stype = signed_type_for (TREE_TYPE (@0)); }
> +     (icmp (convert:stype @0) { build_int_cst (stype, 0); })))))
> +
>  /* X / 4 < Y / 4 iff X < Y when the division is known to be exact.  */
>  (for cmp (simple_comparison)
>   (simplify
> --- gcc/testsuite/gcc.dg/tree-ssa/pr81346-5.c.jj	2017-07-18 12:35:27.406063800 +0200
> +++ gcc/testsuite/gcc.dg/tree-ssa/pr81346-5.c	2017-07-18 12:37:04.460894965 +0200
> @@ -0,0 +1,17 @@
> +/* PR tree-optimization/81346 */
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-optimized" } */
> +/* { dg-final { scan-tree-dump-times "\\(signed int\\) x" 10 "optimized" } } */
> +/* { dg-final { scan-tree-dump-times " <= 0;" 5 "optimized" } } */
> +/* { dg-final { scan-tree-dump-times " > 0;" 5 "optimized" } } */
> +
> +int f1 (unsigned x) { return x - 1 <= __INT_MAX__ - 1; }
> +int f2 (unsigned x) { unsigned a = 1, b = __INT_MAX__ - 1; return x - a <= b; }
> +int f3 (unsigned x) { return x - 1 < __INT_MAX__; }
> +int f4 (unsigned x) { unsigned a = 1, b = __INT_MAX__; return x - a < b; }
> +int f5 (unsigned x) { return x >= 1 && x <= __INT_MAX__; }
> +int f6 (unsigned x) { return x - 1 > __INT_MAX__ - 1; }
> +int f7 (unsigned x) { unsigned a = 1, b = __INT_MAX__ - 1; return x - a > b; }
> +int f8 (unsigned x) { return x - 1 >= __INT_MAX__; }
> +int f9 (unsigned x) { unsigned a = 1, b = __INT_MAX__; return x - a >= b; }
> +int f10 (unsigned x) { return x < 1 || x > __INT_MAX__; }
> 
> 	Jakub
> 
> 

-- 
Richard Biener <rguenther@suse.de>
SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Graham Norton, HRB 21284 (AG Nuernberg)