[RFA] Reimplement canonicalization of comparison arguments in match.pd

[RFA] Reimplement canonicalization of comparison arguments in match.pd

[Jeff Law]

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


c-common.c::shorten_compare has code to canonicalize the arguments of a 
comparison so that the constant is the second argument.  This patch 
removes the implementation from c-common.c and instead implements it in 
match.pd.

Note the match.pd tries to match the prior behavior of shorten_compare, 
hence the strange handling of zero.  No justification exists AFAIK for 
that strange handling in shorten_compare.

The match.pd pattern is primarily Kai's -- I just took the 4 patterns he 
wrote and squashed them into a single pattern to avoid the test duplication.

The xfailed testcase is only case I saw across my comparison tests where 
this change regressed.  Basically shorten-compare had something 
non-canonical when called.  It was able to canonicalize, then optimize 
the result.  I just wanted a record of that test in the testsuite. 
Obviously if we hit our goal of implementing everything from 
shorten_compare, that test will no longer need to be xfailed :-)

Bootstrapped and regression tested on x86-linux-gnu.  OK for the trunk?




[-- Attachment #2: patch --]
[-- Type: text/plain, Size: 3356 bytes --]

	* c-common.c (shorten_compare): Remove code to swap arguments
	if the first is a constant and the second is not zero.
	* match.md: Add patterns to canonicalize comparisons so that the
	constant argument is second.

	* short-compare-3.c: New test, currently xfailed.

kkk
diff --git a/gcc/c-family/c-common.c b/gcc/c-family/c-common.c
index 36c984c..8ba4f13 100644
--- a/gcc/c-family/c-common.c
+++ b/gcc/c-family/c-common.c
@@ -4364,41 +4364,6 @@ shorten_compare (location_t loc, tree *op0_ptr, tree *op1_ptr,
   real1 = TREE_CODE (TREE_TYPE (primop0)) == REAL_TYPE;
   real2 = TREE_CODE (TREE_TYPE (primop1)) == REAL_TYPE;
 
-  /* If first arg is constant, swap the args (changing operation
-     so value is preserved), for canonicalization.  Don't do this if
-     the second arg is 0.  */
-
-  if (TREE_CONSTANT (primop0)
-      && !integer_zerop (primop1) && !real_zerop (primop1)
-      && !fixed_zerop (primop1))
-    {
-      std::swap (primop0, primop1);
-      std::swap (op0, op1);
-      *op0_ptr = op0;
-      *op1_ptr = op1;
-      std::swap (unsignedp0, unsignedp1);
-      std::swap (real1, real2);
-
-      switch (code)
-	{
-	case LT_EXPR:
-	  code = GT_EXPR;
-	  break;
-	case GT_EXPR:
-	  code = LT_EXPR;
-	  break;
-	case LE_EXPR:
-	  code = GE_EXPR;
-	  break;
-	case GE_EXPR:
-	  code = LE_EXPR;
-	  break;
-	default:
-	  break;
-	}
-      *rescode_ptr = code;
-    }
-
   /* If comparing an integer against a constant more bits wide,
      maybe we can deduce a value of 1 or 0 independent of the data.
      Or else truncate the constant now
diff --git a/gcc/match.pd b/gcc/match.pd
index bf4da61..1f6dbfe 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -1182,6 +1182,25 @@ along with GCC; see the file COPYING3.  If not see
 	(convert (bit_and (op (convert:utype @0) (convert:utype @1))
 			  (convert:utype @4)))))))
 
+/* This pattern canonicalizes comparisons so the constant operand
+   is second, unless the constant operand is zero.
+
+   This mirrors the prior behaviour of shorten_comparison.  There wasn't
+   any justification for the special handling of zero in
+   shorten_comparison.  */
+(for op (lt gt le ge)
+  (simplify
+    (op CONSTANT_CLASS_P@0 @1)
+    (if (!integer_zerop (@1) && !real_zerop (@1) && !fixed_zerop (@1)
+         && (TREE_CODE (TREE_TYPE (@0)) != REAL_TYPE
+             || !DECIMAL_FLOAT_MODE_P (TYPE_MODE (TREE_TYPE (@0))))
+         && (TREE_CODE (TREE_TYPE (@1)) != REAL_TYPE
+            || !DECIMAL_FLOAT_MODE_P (TYPE_MODE (TREE_TYPE (@1)))))
+      (if (op == LT_EXPR) (gt @1 @0))
+      (if (op == GT_EXPR) (lt @1 @0))
+      (if (op == LE_EXPR) (ge @1 @0))
+      (if (op == GE_EXPR) (le @1 @0)))))
+
 /* fold-const has a rich set of optimizations for expressions of the
    form A op B ? A : B.   However, those optimizations can be easily
    confused by typecasting, particularly in the true/false arms of the
--- /dev/null	2015-05-20 16:48:49.438489869 -0600
+++ testsuite/gcc.dg/short-compare-3.c	2015-05-29 22:28:50.931836673 -0600
@@ -0,0 +1,15 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-original" } */
+
+extern unsigned short mode_size[];
+void oof (void);
+void
+fu ()
+{
+  if (64 >= mode_size[42])
+    oof ();
+}
+
+/* { dg-final { scan-tree-dump-times "\(int\)" 0 "original" {xfail *-*-*}} } */
+/* { dg-final { cleanup-tree-dump "original" } } */
+

Re: [RFA] Reimplement canonicalization of comparison arguments in match.pd

[Marc Glisse]

On Fri, 29 May 2015, Jeff Law wrote:

> c-common.c::shorten_compare has code to canonicalize the arguments of a 
> comparison so that the constant is the second argument.  This patch removes 
> the implementation from c-common.c and instead implements it in match.pd.
>
> Note the match.pd tries to match the prior behavior of shorten_compare, hence 
> the strange handling of zero.  No justification exists AFAIK for that strange 
> handling in shorten_compare.
>
> The match.pd pattern is primarily Kai's -- I just took the 4 patterns he 
> wrote and squashed them into a single pattern to avoid the test duplication.
>
> The xfailed testcase is only case I saw across my comparison tests where this 
> change regressed.  Basically shorten-compare had something non-canonical when 
> called.  It was able to canonicalize, then optimize the result.  I just 
> wanted a record of that test in the testsuite. Obviously if we hit our goal 
> of implementing everything from shorten_compare, that test will no longer 
> need to be xfailed :-)
>
> Bootstrapped and regression tested on x86-linux-gnu.  OK for the trunk?

I understand doing it in 2 commits to better see what regresses, but I 
don't think we should keep the weirdness in match.pd.

Does it regress anything if we instead add inside the for loop that 
follows /* -A CMP -B -> B CMP A.  */

(simplify
  (cmp CONSTANT_CLASS_P@0 @1)
  (scmp @1 @0))

? If we want to inhibit in some cases because we fail to fold to a 
constant, or because COND_EXPR needs 1 != 0 or something, we can always 
add checks:

(simplify
  (cmp CONSTANT_CLASS_P@0 @1)
  (if (!zerop (@1))
   (scmp @1 @0)))

(hmm, I didn't add zerop to tree.[hc] yet) or !CONSTANT_CLASS_P (@1) or 
whatever is necessary.

-- 
Marc Glisse

Re: [RFA] Reimplement canonicalization of comparison arguments in match.pd

[Jeff Law]

On 05/30/2015 03:57 AM, Marc Glisse wrote:
> On Fri, 29 May 2015, Jeff Law wrote:
>
>> c-common.c::shorten_compare has code to canonicalize the arguments of
>> a comparison so that the constant is the second argument.  This patch
>> removes the implementation from c-common.c and instead implements it
>> in match.pd.
>>
>> Note the match.pd tries to match the prior behavior of
>> shorten_compare, hence the strange handling of zero.  No justification
>> exists AFAIK for that strange handling in shorten_compare.
>>
>> The match.pd pattern is primarily Kai's -- I just took the 4 patterns
>> he wrote and squashed them into a single pattern to avoid the test
>> duplication.
>>
>> The xfailed testcase is only case I saw across my comparison tests
>> where this change regressed.  Basically shorten-compare had something
>> non-canonical when called.  It was able to canonicalize, then optimize
>> the result.  I just wanted a record of that test in the testsuite.
>> Obviously if we hit our goal of implementing everything from
>> shorten_compare, that test will no longer need to be xfailed :-)
>>
>> Bootstrapped and regression tested on x86-linux-gnu.  OK for the trunk?
>
> I understand doing it in 2 commits to better see what regresses, but I
> don't think we should keep the weirdness in match.pd.
By the weirdness, are you referring to the handling of zero?  I don't 
mind losing that at all.    I'd speculate that Kai was just trying to 
mirror what shorten_compare did to make testing easier.

In fact, that seems like something we ought to test.  If that special 
handling gets ripped out, does anything change and if it does we can 
evaluate the pros/cons of whatever we see.


>
> Does it regress anything if we instead add inside the for loop that
> follows /* -A CMP -B -> B CMP A.  */
>
> (simplify
>   (cmp CONSTANT_CLASS_P@0 @1)
>   (scmp @1 @0))
I'll give it a try.  If we can cleanly integrate this into an existing 
pattern, that works for me.

Jeff

Re: [RFA] Reimplement canonicalization of comparison arguments in match.pd

[Jeff Law]

On 05/30/2015 03:57 AM, Marc Glisse wrote:
> On Fri, 29 May 2015, Jeff Law wrote:
>
>> c-common.c::shorten_compare has code to canonicalize the arguments of
>> a comparison so that the constant is the second argument.  This patch
>> removes the implementation from c-common.c and instead implements it
>> in match.pd.
>>
>> Note the match.pd tries to match the prior behavior of
>> shorten_compare, hence the strange handling of zero.  No justification
>> exists AFAIK for that strange handling in shorten_compare.
>>
>> The match.pd pattern is primarily Kai's -- I just took the 4 patterns
>> he wrote and squashed them into a single pattern to avoid the test
>> duplication.
>>
>> The xfailed testcase is only case I saw across my comparison tests
>> where this change regressed.  Basically shorten-compare had something
>> non-canonical when called.  It was able to canonicalize, then optimize
>> the result.  I just wanted a record of that test in the testsuite.
>> Obviously if we hit our goal of implementing everything from
>> shorten_compare, that test will no longer need to be xfailed :-)
>>
>> Bootstrapped and regression tested on x86-linux-gnu.  OK for the trunk?
>
> I understand doing it in 2 commits to better see what regresses, but I
> don't think we should keep the weirdness in match.pd.
>
> Does it regress anything if we instead add inside the for loop that
> follows /* -A CMP -B -> B CMP A.  */
>
> (simplify
>   (cmp CONSTANT_CLASS_P@0 @1)
>   (scmp @1 @0))
Nothing regresses compared to the version I posted with the distinct 
patterns for canonicalization in my tests.  This seems the cleanest, so 
I'm going to spin it as a patch and repost.

Thanks for the suggestion,
jeff

Re: [RFA] Reimplement canonicalization of comparison arguments in match.pd

[Richard Biener]

On Sat, May 30, 2015 at 6:41 AM, Jeff Law <law@redhat.com> wrote:
>
> c-common.c::shorten_compare has code to canonicalize the arguments of a
> comparison so that the constant is the second argument.  This patch removes
> the implementation from c-common.c and instead implements it in match.pd.
>
> Note the match.pd tries to match the prior behavior of shorten_compare,
> hence the strange handling of zero.  No justification exists AFAIK for that
> strange handling in shorten_compare.
>
> The match.pd pattern is primarily Kai's -- I just took the 4 patterns he
> wrote and squashed them into a single pattern to avoid the test duplication.
>
> The xfailed testcase is only case I saw across my comparison tests where
> this change regressed.  Basically shorten-compare had something
> non-canonical when called.  It was able to canonicalize, then optimize the
> result.  I just wanted a record of that test in the testsuite. Obviously if
> we hit our goal of implementing everything from shorten_compare, that test
> will no longer need to be xfailed :-)
>
> Bootstrapped and regression tested on x86-linux-gnu.  OK for the trunk?
>
>
>
>
>         * c-common.c (shorten_compare): Remove code to swap arguments
>         if the first is a constant and the second is not zero.
>         * match.md: Add patterns to canonicalize comparisons so that the
>         constant argument is second.
>
>         * short-compare-3.c: New test, currently xfailed.
>
> kkk
> diff --git a/gcc/c-family/c-common.c b/gcc/c-family/c-common.c
> index 36c984c..8ba4f13 100644
> --- a/gcc/c-family/c-common.c
> +++ b/gcc/c-family/c-common.c
> @@ -4364,41 +4364,6 @@ shorten_compare (location_t loc, tree *op0_ptr, tree
> *op1_ptr,
>    real1 = TREE_CODE (TREE_TYPE (primop0)) == REAL_TYPE;
>    real2 = TREE_CODE (TREE_TYPE (primop1)) == REAL_TYPE;
>
> -  /* If first arg is constant, swap the args (changing operation
> -     so value is preserved), for canonicalization.  Don't do this if
> -     the second arg is 0.  */
> -
> -  if (TREE_CONSTANT (primop0)
> -      && !integer_zerop (primop1) && !real_zerop (primop1)
> -      && !fixed_zerop (primop1))
> -    {
> -      std::swap (primop0, primop1);
> -      std::swap (op0, op1);
> -      *op0_ptr = op0;
> -      *op1_ptr = op1;
> -      std::swap (unsignedp0, unsignedp1);
> -      std::swap (real1, real2);
> -
> -      switch (code)
> -       {
> -       case LT_EXPR:
> -         code = GT_EXPR;
> -         break;
> -       case GT_EXPR:
> -         code = LT_EXPR;
> -         break;
> -       case LE_EXPR:
> -         code = GE_EXPR;
> -         break;
> -       case GE_EXPR:
> -         code = LE_EXPR;
> -         break;
> -       default:
> -         break;
> -       }
> -      *rescode_ptr = code;
> -    }
> -
>    /* If comparing an integer against a constant more bits wide,
>       maybe we can deduce a value of 1 or 0 independent of the data.
>       Or else truncate the constant now
> diff --git a/gcc/match.pd b/gcc/match.pd
> index bf4da61..1f6dbfe 100644
> --- a/gcc/match.pd
> +++ b/gcc/match.pd
> @@ -1182,6 +1182,25 @@ along with GCC; see the file COPYING3.  If not see
>         (convert (bit_and (op (convert:utype @0) (convert:utype @1))
>                           (convert:utype @4)))))))
>
> +/* This pattern canonicalizes comparisons so the constant operand
> +   is second, unless the constant operand is zero.
> +
> +   This mirrors the prior behaviour of shorten_comparison.  There wasn't
> +   any justification for the special handling of zero in
> +   shorten_comparison.  */
> +(for op (lt gt le ge)
> +  (simplify
> +    (op CONSTANT_CLASS_P@0 @1)
> +    (if (!integer_zerop (@1) && !real_zerop (@1) && !fixed_zerop (@1)
> +         && (TREE_CODE (TREE_TYPE (@0)) != REAL_TYPE
> +             || !DECIMAL_FLOAT_MODE_P (TYPE_MODE (TREE_TYPE (@0))))
> +         && (TREE_CODE (TREE_TYPE (@1)) != REAL_TYPE
> +            || !DECIMAL_FLOAT_MODE_P (TYPE_MODE (TREE_TYPE (@1)))))
> +      (if (op == LT_EXPR) (gt @1 @0))
> +      (if (op == GT_EXPR) (lt @1 @0))
> +      (if (op == LE_EXPR) (ge @1 @0))
> +      (if (op == GE_EXPR) (le @1 @0)))))
> +

In addition to what Marc said we'd simplify 1 != 0 immediately anyway (to 1),
so I don't think the special-cases should make a difference (and if they
do I'd like to see a testcase!).

Note that you should use a double-for here,

 (for op (lt gt le ge)
      iop (gt lt ge le)
  (simplify ...
    (if ...
     (iop @1 @0)

and drop the inner ifs.  You get op and iop iterated in lock-step.
IMHO you should
simply iterate over all comparison codes, thus

 (for op (tcc_comparison)
      iop (inverted_tcc_comparison)
      nop (inverted_tcc_comparison_with_nans)
  (...

see the existing patterns using invert_tree_comparison.  Or not care
about handling
NANs correctly and guard with

     && invert_tree_comparison (op, HONOR_NANS (..)) == iop

Richard.

>  /* fold-const has a rich set of optimizations for expressions of the
>     form A op B ? A : B.   However, those optimizations can be easily
>     confused by typecasting, particularly in the true/false arms of the
> --- /dev/null   2015-05-20 16:48:49.438489869 -0600
> +++ testsuite/gcc.dg/short-compare-3.c  2015-05-29 22:28:50.931836673 -0600
> @@ -0,0 +1,15 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-original" } */
> +
> +extern unsigned short mode_size[];
> +void oof (void);
> +void
> +fu ()
> +{
> +  if (64 >= mode_size[42])
> +    oof ();
> +}
> +
> +/* { dg-final { scan-tree-dump-times "\(int\)" 0 "original" {xfail *-*-*}}
> } */
> +/* { dg-final { cleanup-tree-dump "original" } } */
> +
>

Re: [RFA] Reimplement canonicalization of comparison arguments in match.pd

[Jeff Law]

On 06/01/2015 05:15 AM, Richard Biener wrote:
> On Sat, May 30, 2015 at 6:41 AM, Jeff Law <law@redhat.com> wrote:
>>
>> c-common.c::shorten_compare has code to canonicalize the arguments of a
>> comparison so that the constant is the second argument.  This patch removes
>> the implementation from c-common.c and instead implements it in match.pd.
>>
>> Note the match.pd tries to match the prior behavior of shorten_compare,
>> hence the strange handling of zero.  No justification exists AFAIK for that
>> strange handling in shorten_compare.
>>
>> The match.pd pattern is primarily Kai's -- I just took the 4 patterns he
>> wrote and squashed them into a single pattern to avoid the test duplication.
>>
>> The xfailed testcase is only case I saw across my comparison tests where
>> this change regressed.  Basically shorten-compare had something
>> non-canonical when called.  It was able to canonicalize, then optimize the
>> result.  I just wanted a record of that test in the testsuite. Obviously if
>> we hit our goal of implementing everything from shorten_compare, that test
>> will no longer need to be xfailed :-)
>>
>> Bootstrapped and regression tested on x86-linux-gnu.  OK for the trunk?
>>
>>
>>
>>
>>          * c-common.c (shorten_compare): Remove code to swap arguments
>>          if the first is a constant and the second is not zero.
>>          * match.md: Add patterns to canonicalize comparisons so that the
>>          constant argument is second.
>>
>>          * short-compare-3.c: New test, currently xfailed.
>>
>> kkk
>> diff --git a/gcc/c-family/c-common.c b/gcc/c-family/c-common.c
>> index 36c984c..8ba4f13 100644
>> --- a/gcc/c-family/c-common.c
>> +++ b/gcc/c-family/c-common.c
>> @@ -4364,41 +4364,6 @@ shorten_compare (location_t loc, tree *op0_ptr, tree
>> *op1_ptr,
>>     real1 = TREE_CODE (TREE_TYPE (primop0)) == REAL_TYPE;
>>     real2 = TREE_CODE (TREE_TYPE (primop1)) == REAL_TYPE;
>>
>> -  /* If first arg is constant, swap the args (changing operation
>> -     so value is preserved), for canonicalization.  Don't do this if
>> -     the second arg is 0.  */
>> -
>> -  if (TREE_CONSTANT (primop0)
>> -      && !integer_zerop (primop1) && !real_zerop (primop1)
>> -      && !fixed_zerop (primop1))
>> -    {
>> -      std::swap (primop0, primop1);
>> -      std::swap (op0, op1);
>> -      *op0_ptr = op0;
>> -      *op1_ptr = op1;
>> -      std::swap (unsignedp0, unsignedp1);
>> -      std::swap (real1, real2);
>> -
>> -      switch (code)
>> -       {
>> -       case LT_EXPR:
>> -         code = GT_EXPR;
>> -         break;
>> -       case GT_EXPR:
>> -         code = LT_EXPR;
>> -         break;
>> -       case LE_EXPR:
>> -         code = GE_EXPR;
>> -         break;
>> -       case GE_EXPR:
>> -         code = LE_EXPR;
>> -         break;
>> -       default:
>> -         break;
>> -       }
>> -      *rescode_ptr = code;
>> -    }
>> -
>>     /* If comparing an integer against a constant more bits wide,
>>        maybe we can deduce a value of 1 or 0 independent of the data.
>>        Or else truncate the constant now
>> diff --git a/gcc/match.pd b/gcc/match.pd
>> index bf4da61..1f6dbfe 100644
>> --- a/gcc/match.pd
>> +++ b/gcc/match.pd
>> @@ -1182,6 +1182,25 @@ along with GCC; see the file COPYING3.  If not see
>>          (convert (bit_and (op (convert:utype @0) (convert:utype @1))
>>                            (convert:utype @4)))))))
>>
>> +/* This pattern canonicalizes comparisons so the constant operand
>> +   is second, unless the constant operand is zero.
>> +
>> +   This mirrors the prior behaviour of shorten_comparison.  There wasn't
>> +   any justification for the special handling of zero in
>> +   shorten_comparison.  */
>> +(for op (lt gt le ge)
>> +  (simplify
>> +    (op CONSTANT_CLASS_P@0 @1)
>> +    (if (!integer_zerop (@1) && !real_zerop (@1) && !fixed_zerop (@1)
>> +         && (TREE_CODE (TREE_TYPE (@0)) != REAL_TYPE
>> +             || !DECIMAL_FLOAT_MODE_P (TYPE_MODE (TREE_TYPE (@0))))
>> +         && (TREE_CODE (TREE_TYPE (@1)) != REAL_TYPE
>> +            || !DECIMAL_FLOAT_MODE_P (TYPE_MODE (TREE_TYPE (@1)))))
>> +      (if (op == LT_EXPR) (gt @1 @0))
>> +      (if (op == GT_EXPR) (lt @1 @0))
>> +      (if (op == LE_EXPR) (ge @1 @0))
>> +      (if (op == GE_EXPR) (le @1 @0)))))
>> +
>
> In addition to what Marc said we'd simplify 1 != 0 immediately anyway (to 1),
> so I don't think the special-cases should make a difference (and if they
> do I'd like to see a testcase!).
>
> Note that you should use a double-for here,
>
>   (for op (lt gt le ge)
>        iop (gt lt ge le)
>    (simplify ...
>      (if ...
>       (iop @1 @0)
>
> and drop the inner ifs.  You get op and iop iterated in lock-step.
> IMHO you should
> simply iterate over all comparison codes, thus
>
>   (for op (tcc_comparison)
>        iop (inverted_tcc_comparison)
>        nop (inverted_tcc_comparison_with_nans)
Which starts to look a lot like the pattern Marc suggested we change 
instead:

/* -A CMP -B -> B CMP A.  */
(for cmp (tcc_comparison)
      scmp (swapped_tcc_comparison)


jeff

Re: [RFA] Reimplement canonicalization of comparison arguments in match.pd

[Jeff Law]

On 06/01/2015 05:15 AM, Richard Biener wrote:
>
> In addition to what Marc said we'd simplify 1 != 0 immediately anyway (to 1),
> so I don't think the special-cases should make a difference (and if they
> do I'd like to see a testcase!).
FWIW, I agree -- and across my testfiles I don't see any difference in 
the dumps with the special casing of 0 removed.


>
> Note that you should use a double-for here,
>
>   (for op (lt gt le ge)
>        iop (gt lt ge le)
>    (simplify ...
>      (if ...
>       (iop @1 @0)
>
> and drop the inner ifs.  You get op and iop iterated in lock-step.
> IMHO you should
> simply iterate over all comparison codes, thus
>
>   (for op (tcc_comparison)
>        iop (inverted_tcc_comparison)
>        nop (inverted_tcc_comparison_with_nans)
>    (...
>
> see the existing patterns using invert_tree_comparison.  Or not care
> about handling
> NANs correctly and guard with
>
>       && invert_tree_comparison (op, HONOR_NANS (..)) == iop
We actually want swapped_tcc_comparison.  We're swapping the operands, 
not inverting the comparison.  Swapping the operands also happens to be 
safe for FP, so no need to do anything special there.

Using Marc's suggestion for integrating canonicalization into the 
existing pattern seems the cleanest to me and that's what I'm testing now.

jeff