Fold some equal to and not equal to patterns in match.pd

Fold some equal to and not equal to patterns in match.pd

[Hurugalawadi, Naveen]

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

Hi,

Please find attached the patch which performs following patterns folding
in match.pd:-

a ==/!= a p+ b to b ==/!= 0.
a << N ==/!= 0 to a&(-1>>N) ==/!= 0.
a * N ==/!= 0 where N is a power of 2 to a & (-1<<N2) ==/!= 0 where N2 is log2 of N.

Please review the same and let us know if its okay?

Regression Tested on X86_64.

On Behalf of Andrew Pinski.

Thanks,

gcc/testsuite/ChangeLog:

2015-01-21  Andrew Pinski  <apinski@cavium.com>

	* testsuite/gcc.dg/tree-ssa/compare-shiftmult-1.c: New testcase.
	* testsuite/gcc.dg/tree-ssa/compare_pointers-1.c: New testcase.

gcc/ChangeLog:

2015-01-21  Andrew Pinski  <apinski@cavium.com>

	* match.pd (define_predicates): Add integer_pow2p.
	Add pattern for folding of a ==/!= a p+ b to b ==/!= 0.
	(unsigned_integral_valued_p): New match.
	Add pattern for folding of a<<N ==/!= 0 to a&(-1>>N) ==/!= 0.
	Add pattern for folding of a*N ==/!= 0 where N is a power of 2
	to a&(-1<<N2) ==/!= 0 where N2 is log2 of N.

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: gcc_match.patch --]
[-- Type: text/x-patch; name="gcc_match.patch", Size: 2739 bytes --]

--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -29,7 +29,8 @@ along with GCC; see the file COPYING3.  If not see
    integer_each_onep integer_truep
    real_zerop real_onep real_minus_onep
    CONSTANT_CLASS_P
-   tree_expr_nonnegative_p)
+   tree_expr_nonnegative_p
+   integer_pow2p)
 
 /* Operator lists.  */
 (define_operator_list tcc_comparison
@@ -104,6 +105,35 @@ along with GCC; see the file COPYING3.  If not see
  (if (!HONOR_NANS (type) && !HONOR_SIGNED_ZEROS (type))
   @1))
 
+/* Fold a ==/!= a p + b to b ==/!= 0.  */
+(for op (ne eq)
+ (simplify
+  (op:c @0 (pointer_plus @0 @1))
+  (op @1 { build_zero_cst (TREE_TYPE (@1)); })))
+
+(match unsigned_integral_valued_p
+ @0
+ (if (INTEGRAL_TYPE_P (type) && TYPE_UNSIGNED (type))))
+
+/* a << N ==/!= 0 to  a & (-1>>N) ==/!= 0.  */
+(for op (ne eq)
+ (simplify
+  (op (lshift unsigned_integral_valued_p@0 INTEGER_CST@1) integer_zerop@2)
+   (op (bit_and @0 (rshift { build_minus_one_cst (TREE_TYPE (@0)); }
+		    @1))
+       @2)))
+
+/* a * N ==/!= 0 where N is a power of 2 to a & (-1<<N2) ==/!= 0
+   where N2 is log2 of N.  */
+(for op (ne eq)
+ (simplify
+  (op (mult:c unsigned_integral_valued_p@0 integer_pow2p@1) integer_zerop@2)
+  (with { tree n2 = build_int_cst (TREE_TYPE (@0),
+				   wi::exact_log2 (@1)); }
+   (op (bit_and @0 (rshift { build_minus_one_cst (TREE_TYPE (@0)); }
+		    { n2 ; }))
+        @2))))
+
 /* In IEEE floating point, x*1 is not equivalent to x for snans.
    Likewise for complex arithmetic with signed zeros.  */
 (simplify
new file mode 100644
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/compare-shiftmult-1.c
@@ -0,0 +1,17 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-forwprop1-details" } */
+
+int f(unsigned c)
+{
+  unsigned a = c*4;
+  return (a == 0);
+}
+
+/* { dg-final { scan-tree-dump-times "gimple_simplified to _\[0-9\] = c_\[0-9\].D. & 1073741823" 2 "forwprop1" } } */
+int f1(unsigned c)
+{
+  unsigned a = c<<2;
+  return (a != 0);
+}
+
+/* { dg-final { cleanup-tree-dump "forwprop1" } } */
new file mode 100644
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/compare_pointers-1.c
@@ -0,0 +1,19 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-forwprop1-details" } */
+
+int f(char *b, __SIZE_TYPE__ c)
+{
+  char *a = b + c;
+  return (a == b);
+}
+
+/* { dg-final { scan-tree-dump-times "gimple_simplified to _\[0-9\] = c_\[0-9\].D. == 0" 1 "forwprop1" } } */
+int f1(char *b, __SIZE_TYPE__ c)
+{
+  char *a = b + c;
+  return (a != b);
+}
+
+/* { dg-final { scan-tree-dump-times "gimple_simplified to _\[0-9\] = c_\[0-9\].D. != 0" 1 "forwprop1" } } */
+/* { dg-final { scan-tree-dump-times "Applying pattern" 2 "forwprop1" } } */
+/* { dg-final { cleanup-tree-dump "forwprop1" } } */

Re: Fold some equal to and not equal to patterns in match.pd

[pinskia]

> On Jul 21, 2015, at 2:15 AM, Hurugalawadi, Naveen <Naveen.Hurugalawadi@caviumnetworks.com> wrote:
> 
> Hi,
> 
> Please find attached the patch which performs following patterns folding
> in match.pd:-
> 
> a ==/!= a p+ b to b ==/!= 0.
> a << N ==/!= 0 to a&(-1>>N) ==/!= 0.
> a * N ==/!= 0 where N is a power of 2 to a & (-1<<N2) ==/!= 0 where N2 is log2 of N.
> 
> Please review the same and let us know if its okay?

I should note this shows up in perlbmk in spec 2006. 

Thanks,
Andrew

> 
> Regression Tested on X86_64.
> 
> On Behalf of Andrew Pinski.
> 
> Thanks,
> 
> gcc/testsuite/ChangeLog:
> 
> 2015-01-21  Andrew Pinski  <apinski@cavium.com>
> 
>    * testsuite/gcc.dg/tree-ssa/compare-shiftmult-1.c: New testcase.
>    * testsuite/gcc.dg/tree-ssa/compare_pointers-1.c: New testcase.
> 
> gcc/ChangeLog:
> 
> 2015-01-21  Andrew Pinski  <apinski@cavium.com>
> 
>    * match.pd (define_predicates): Add integer_pow2p.
>    Add pattern for folding of a ==/!= a p+ b to b ==/!= 0.
>    (unsigned_integral_valued_p): New match.
>    Add pattern for folding of a<<N ==/!= 0 to a&(-1>>N) ==/!= 0.
>    Add pattern for folding of a*N ==/!= 0 where N is a power of 2
>    to a&(-1<<N2) ==/!= 0 where N2 is log2 of N.
> <gcc_match.patch>

Re: Fold some equal to and not equal to patterns in match.pd

[Kyrill Tkachov]

On 21/07/15 10:26, pinskia@gmail.com wrote:
>
>
>
>> On Jul 21, 2015, at 2:15 AM, Hurugalawadi, Naveen <Naveen.Hurugalawadi@caviumnetworks.com> wrote:
>>
>> Hi,
>>
>> Please find attached the patch which performs following patterns folding
>> in match.pd:-
>>
>> a ==/!= a p+ b to b ==/!= 0.
>> a << N ==/!= 0 to a&(-1>>N) ==/!= 0.
>> a * N ==/!= 0 where N is a power of 2 to a & (-1<<N2) ==/!= 0 where N2 is log2 of N.
>>
>> Please review the same and let us know if its okay?
> I should note this shows up in perlbmk in spec 2006.

Yes, I see it triggering there for aarch64, but I also see some undesired effects,
for example in gcc:
     lsl    x24, x24, 3
     cbz    x24, .L1194

now becomes:
     and    x0, x24, 2305843009213693951
     lsl    x24, x24, 3
     cbz    x0, .L1194

> Thanks,
> Andrew
>
>> Regression Tested on X86_64.
>>
>> On Behalf of Andrew Pinski.
>>
>> Thanks,
>>
>> gcc/testsuite/ChangeLog:
>>
>> 2015-01-21  Andrew Pinski  <apinski@cavium.com>
>>
>>     * testsuite/gcc.dg/tree-ssa/compare-shiftmult-1.c: New testcase.
>>     * testsuite/gcc.dg/tree-ssa/compare_pointers-1.c: New testcase.
>>
>> gcc/ChangeLog:
>>
>> 2015-01-21  Andrew Pinski  <apinski@cavium.com>
>>
>>     * match.pd (define_predicates): Add integer_pow2p.
>>     Add pattern for folding of a ==/!= a p+ b to b ==/!= 0.
>>     (unsigned_integral_valued_p): New match.
>>     Add pattern for folding of a<<N ==/!= 0 to a&(-1>>N) ==/!= 0.
>>     Add pattern for folding of a*N ==/!= 0 where N is a power of 2
>>     to a&(-1<<N2) ==/!= 0 where N2 is log2 of N.
>> <gcc_match.patch>

Re: Fold some equal to and not equal to patterns in match.pd

[pinskia]

> On Jul 21, 2015, at 3:31 AM, Kyrill Tkachov <kyrylo.tkachov@arm.com> wrote:
> 
> 
>> On 21/07/15 10:26, pinskia@gmail.com wrote:
>> 
>> 
>> 
>>> On Jul 21, 2015, at 2:15 AM, Hurugalawadi, Naveen <Naveen.Hurugalawadi@caviumnetworks.com> wrote:
>>> 
>>> Hi,
>>> 
>>> Please find attached the patch which performs following patterns folding
>>> in match.pd:-
>>> 
>>> a ==/!= a p+ b to b ==/!= 0.
>>> a << N ==/!= 0 to a&(-1>>N) ==/!= 0.
>>> a * N ==/!= 0 where N is a power of 2 to a & (-1<<N2) ==/!= 0 where N2 is log2 of N.
>>> 
>>> Please review the same and let us know if its okay?
>> I should note this shows up in perlbmk in spec 2006.
> 
> Yes, I see it triggering there for aarch64, but I also see some undesired effects,
> for example in gcc:
>    lsl    x24, x24, 3
>    cbz    x24, .L1194
> 
> now becomes:
>    and    x0, x24, 2305843009213693951
>    lsl    x24, x24, 3
>    cbz    x0, .L1194

Shouldn't the and become a tst instead and the cbz be a b.eq?  Oh I have another patch which does that and the reason the performance for me does not regress on thunderx (tst and branches can merge before issue). 

Thanks,
Andrew

> 
>> Thanks,
>> Andrew
>> 
>>> Regression Tested on X86_64.
>>> 
>>> On Behalf of Andrew Pinski.
>>> 
>>> Thanks,
>>> 
>>> gcc/testsuite/ChangeLog:
>>> 
>>> 2015-01-21  Andrew Pinski  <apinski@cavium.com>
>>> 
>>>    * testsuite/gcc.dg/tree-ssa/compare-shiftmult-1.c: New testcase.
>>>    * testsuite/gcc.dg/tree-ssa/compare_pointers-1.c: New testcase.
>>> 
>>> gcc/ChangeLog:
>>> 
>>> 2015-01-21  Andrew Pinski  <apinski@cavium.com>
>>> 
>>>    * match.pd (define_predicates): Add integer_pow2p.
>>>    Add pattern for folding of a ==/!= a p+ b to b ==/!= 0.
>>>    (unsigned_integral_valued_p): New match.
>>>    Add pattern for folding of a<<N ==/!= 0 to a&(-1>>N) ==/!= 0.
>>>    Add pattern for folding of a*N ==/!= 0 where N is a power of 2
>>>    to a&(-1<<N2) ==/!= 0 where N2 is log2 of N.
>>> <gcc_match.patch>
> 

Re: Fold some equal to and not equal to patterns in match.pd

[Kyrill Tkachov]

On 21/07/15 11:46, pinskia@gmail.com wrote:
>
>
>
>> On Jul 21, 2015, at 3:31 AM, Kyrill Tkachov <kyrylo.tkachov@arm.com> wrote:
>>
>>
>>> On 21/07/15 10:26, pinskia@gmail.com wrote:
>>>
>>>
>>>
>>>> On Jul 21, 2015, at 2:15 AM, Hurugalawadi, Naveen <Naveen.Hurugalawadi@caviumnetworks.com> wrote:
>>>>
>>>> Hi,
>>>>
>>>> Please find attached the patch which performs following patterns folding
>>>> in match.pd:-
>>>>
>>>> a ==/!= a p+ b to b ==/!= 0.
>>>> a << N ==/!= 0 to a&(-1>>N) ==/!= 0.
>>>> a * N ==/!= 0 where N is a power of 2 to a & (-1<<N2) ==/!= 0 where N2 is log2 of N.
>>>>
>>>> Please review the same and let us know if its okay?
>>> I should note this shows up in perlbmk in spec 2006.
>> Yes, I see it triggering there for aarch64, but I also see some undesired effects,
>> for example in gcc:
>>     lsl    x24, x24, 3
>>     cbz    x24, .L1194
>>
>> now becomes:
>>     and    x0, x24, 2305843009213693951
>>     lsl    x24, x24, 3
>>     cbz    x0, .L1194
> Shouldn't the and become a tst instead and the cbz be a b.eq?  Oh I have another patch which does that and the reason the performance for me does not regress on thunderx (tst and branches can merge before issue).

well, the overall effect in perlbench and gcc is beneficial (at least code size-wise).
It's just a few warts like this here and there.

Kyrill

>
> Thanks,
> Andrew
>
>>> Thanks,
>>> Andrew
>>>
>>>> Regression Tested on X86_64.
>>>>
>>>> On Behalf of Andrew Pinski.
>>>>
>>>> Thanks,
>>>>
>>>> gcc/testsuite/ChangeLog:
>>>>
>>>> 2015-01-21  Andrew Pinski  <apinski@cavium.com>
>>>>
>>>>     * testsuite/gcc.dg/tree-ssa/compare-shiftmult-1.c: New testcase.
>>>>     * testsuite/gcc.dg/tree-ssa/compare_pointers-1.c: New testcase.
>>>>
>>>> gcc/ChangeLog:
>>>>
>>>> 2015-01-21  Andrew Pinski  <apinski@cavium.com>
>>>>
>>>>     * match.pd (define_predicates): Add integer_pow2p.
>>>>     Add pattern for folding of a ==/!= a p+ b to b ==/!= 0.
>>>>     (unsigned_integral_valued_p): New match.
>>>>     Add pattern for folding of a<<N ==/!= 0 to a&(-1>>N) ==/!= 0.
>>>>     Add pattern for folding of a*N ==/!= 0 where N is a power of 2
>>>>     to a&(-1<<N2) ==/!= 0 where N2 is log2 of N.
>>>> <gcc_match.patch>

Re: Fold some equal to and not equal to patterns in match.pd

[Kyrill Tkachov]

On 21/07/15 11:46, pinskia@gmail.com wrote:
>
>
>
>> On Jul 21, 2015, at 3:31 AM, Kyrill Tkachov <kyrylo.tkachov@arm.com> wrote:
>>
>>
>>> On 21/07/15 10:26, pinskia@gmail.com wrote:
>>>
>>>
>>>
>>>> On Jul 21, 2015, at 2:15 AM, Hurugalawadi, Naveen <Naveen.Hurugalawadi@caviumnetworks.com> wrote:
>>>>
>>>> Hi,
>>>>
>>>> Please find attached the patch which performs following patterns folding
>>>> in match.pd:-
>>>>
>>>> a ==/!= a p+ b to b ==/!= 0.
>>>> a << N ==/!= 0 to a&(-1>>N) ==/!= 0.
>>>> a * N ==/!= 0 where N is a power of 2 to a & (-1<<N2) ==/!= 0 where N2 is log2 of N.
>>>>
>>>> Please review the same and let us know if its okay?
>>> I should note this shows up in perlbmk in spec 2006.
>> Yes, I see it triggering there for aarch64, but I also see some undesired effects,
>> for example in gcc:
>>     lsl    x24, x24, 3
>>     cbz    x24, .L1194
>>
>> now becomes:
>>     and    x0, x24, 2305843009213693951
>>     lsl    x24, x24, 3
>>     cbz    x0, .L1194
> Shouldn't the and become a tst instead and the cbz be a b.eq?  Oh I have another patch which does that and the reason the performance for me does not regress on thunderx (tst and branches can merge before issue).

I also see a code size regression on xalancbmk.
If you have an aarch64 patch that mitigates this there, could you post that as well?
Would be nice to get the benefits of this folding without regressing existing cases on aarch64.

Thanks,
Kyrill

>
> Thanks,
> Andrew
>
>>> Thanks,
>>> Andrew
>>>
>>>> Regression Tested on X86_64.
>>>>
>>>> On Behalf of Andrew Pinski.
>>>>
>>>> Thanks,
>>>>
>>>> gcc/testsuite/ChangeLog:
>>>>
>>>> 2015-01-21  Andrew Pinski  <apinski@cavium.com>
>>>>
>>>>     * testsuite/gcc.dg/tree-ssa/compare-shiftmult-1.c: New testcase.
>>>>     * testsuite/gcc.dg/tree-ssa/compare_pointers-1.c: New testcase.
>>>>
>>>> gcc/ChangeLog:
>>>>
>>>> 2015-01-21  Andrew Pinski  <apinski@cavium.com>
>>>>
>>>>     * match.pd (define_predicates): Add integer_pow2p.
>>>>     Add pattern for folding of a ==/!= a p+ b to b ==/!= 0.
>>>>     (unsigned_integral_valued_p): New match.
>>>>     Add pattern for folding of a<<N ==/!= 0 to a&(-1>>N) ==/!= 0.
>>>>     Add pattern for folding of a*N ==/!= 0 where N is a power of 2
>>>>     to a&(-1<<N2) ==/!= 0 where N2 is log2 of N.
>>>> <gcc_match.patch>

Re: Fold some equal to and not equal to patterns in match.pd

[Jakub Jelinek]

On Tue, Jul 21, 2015 at 09:15:31AM +0000, Hurugalawadi, Naveen wrote:
> Please find attached the patch which performs following patterns folding
> in match.pd:-
> 
> a ==/!= a p+ b to b ==/!= 0.
> a << N ==/!= 0 to a&(-1>>N) ==/!= 0.

Not sure about this second one.  Why do you think it is generally
beneficial?  On many targets, shifts are as fast as bitwise and, and
-1>>N could be e.g. significantly more expensive constant (say require
3 instructions to construct).

	Jakub

Re: Fold some equal to and not equal to patterns in match.pd

[Richard Biener]

On July 21, 2015 11:38:31 AM GMT+02:00, Jakub Jelinek <jakub@redhat.com> wrote:
>On Tue, Jul 21, 2015 at 09:15:31AM +0000, Hurugalawadi, Naveen wrote:
>> Please find attached the patch which performs following patterns
>folding
>> in match.pd:-
>> 
>> a ==/!= a p+ b to b ==/!= 0.
>> a << N ==/!= 0 to a&(-1>>N) ==/!= 0.
>
>Not sure about this second one.  Why do you think it is generally
>beneficial?  On many targets, shifts are as fast as bitwise and, and
>-1>>N could be e.g. significantly more expensive constant (say require
>3 instructions to construct).

And may set flags while shift not? Of course we do a very poor job of representing this kind of stuff on gimple.

Richard.

>	Jakub

Re: Fold some equal to and not equal to patterns in match.pd

[Andrew Pinski]

On Tue, Jul 21, 2015 at 12:16 PM, Richard Biener
<richard.guenther@gmail.com> wrote:
> On July 21, 2015 11:38:31 AM GMT+02:00, Jakub Jelinek <jakub@redhat.com> wrote:
>>On Tue, Jul 21, 2015 at 09:15:31AM +0000, Hurugalawadi, Naveen wrote:
>>> Please find attached the patch which performs following patterns
>>folding
>>> in match.pd:-
>>>
>>> a ==/!= a p+ b to b ==/!= 0.
>>> a << N ==/!= 0 to a&(-1>>N) ==/!= 0.
>>
>>Not sure about this second one.  Why do you think it is generally
>>beneficial?  On many targets, shifts are as fast as bitwise and, and
>>-1>>N could be e.g. significantly more expensive constant (say require
>>3 instructions to construct).
>
> And may set flags while shift not? Of course we do a very poor job of representing this kind of stuff on gimple.

The biggest question now becomes which way is the canonical form for
gimple and we can decide to optimize it on the RTL level (combine)
instead if it produces better code in those cases.
Note on AARCH64, producing x&(-1>>N) has no cost difference from a<<N
so we would like to do it there.  Also in this case producing flags is
useful.

Thanks,
Andrew

>
> Richard.
>
>>       Jakub
>
>

Re: Fold some equal to and not equal to patterns in match.pd

[Richard Biener]

On Wed, Jul 22, 2015 at 2:40 AM, Andrew Pinski
<andrew.pinski@caviumnetworks.com> wrote:
> On Tue, Jul 21, 2015 at 12:16 PM, Richard Biener
> <richard.guenther@gmail.com> wrote:
>> On July 21, 2015 11:38:31 AM GMT+02:00, Jakub Jelinek <jakub@redhat.com> wrote:
>>>On Tue, Jul 21, 2015 at 09:15:31AM +0000, Hurugalawadi, Naveen wrote:
>>>> Please find attached the patch which performs following patterns
>>>folding
>>>> in match.pd:-
>>>>
>>>> a ==/!= a p+ b to b ==/!= 0.
>>>> a << N ==/!= 0 to a&(-1>>N) ==/!= 0.
>>>
>>>Not sure about this second one.  Why do you think it is generally
>>>beneficial?  On many targets, shifts are as fast as bitwise and, and
>>>-1>>N could be e.g. significantly more expensive constant (say require
>>>3 instructions to construct).
>>
>> And may set flags while shift not? Of course we do a very poor job of representing this kind of stuff on gimple.
>
> The biggest question now becomes which way is the canonical form for
> gimple and we can decide to optimize it on the RTL level (combine)
> instead if it produces better code in those cases.
> Note on AARCH64, producing x&(-1>>N) has no cost difference from a<<N
> so we would like to do it there.  Also in this case producing flags is
> useful.

Canonical GIMPLE is what has less GIMPLE operations.  In this case it's
a << N ==/!= 0 (two ops), not a & (-1 >> N) ==/!= 0 (three ops).

Thus on GIMPLE the transform is not wanted.

Richard.

> Thanks,
> Andrew
>
>>
>> Richard.
>>
>>>       Jakub
>>
>>

Re: Fold some equal to and not equal to patterns in match.pd

[Segher Boessenkool]

On Tue, Jul 21, 2015 at 05:40:07PM -0700, Andrew Pinski wrote:
> The biggest question now becomes which way is the canonical form for
> gimple and we can decide to optimize it on the RTL level (combine)
> instead if it produces better code in those cases.

combine does not do instruction selection in general; it only does
instruction combination.  It already handles most cases where shifts
and masks are combined; if you find one where it doesn't, please
report.


Segher

Re: Fold some equal to and not equal to patterns in match.pd

[Jeff Law]

On 07/21/2015 06:40 PM, Andrew Pinski wrote:
> On Tue, Jul 21, 2015 at 12:16 PM, Richard Biener
> <richard.guenther@gmail.com> wrote:
>> On July 21, 2015 11:38:31 AM GMT+02:00, Jakub Jelinek <jakub@redhat.com> wrote:
>>> On Tue, Jul 21, 2015 at 09:15:31AM +0000, Hurugalawadi, Naveen wrote:
>>>> Please find attached the patch which performs following patterns
>>> folding
>>>> in match.pd:-
>>>>
>>>> a ==/!= a p+ b to b ==/!= 0.
>>>> a << N ==/!= 0 to a&(-1>>N) ==/!= 0.
>>>
>>> Not sure about this second one.  Why do you think it is generally
>>> beneficial?  On many targets, shifts are as fast as bitwise and, and
>>> -1>>N could be e.g. significantly more expensive constant (say require
>>> 3 instructions to construct).
>>
>> And may set flags while shift not? Of course we do a very poor job of representing this kind of stuff on gimple.
>
> The biggest question now becomes which way is the canonical form for
> gimple and we can decide to optimize it on the RTL level (combine)
> instead if it produces better code in those cases.
> Note on AARCH64, producing x&(-1>>N) has no cost difference from a<<N
> so we would like to do it there.  Also in this case producing flags is
> useful.
Funny I was having a discussion with Kai about this class of problems 
yesterday.

It seems to me in these kind of cases that selection of the canonical 
form should be driven by factors outside of which is better for a 
particular target.  ie, which is simpler

Instead we should be looking at the gimple->rtl expansion phase to 
expand using a form that is better for a particluar target.

[And yes, I think I've violated this new guiding principle in the past]

Given the (a << n) EQ/NE form, can we reasonably detect this in the 
gimple->expansion phase and emit code as if we had the alternate form 
for targets such as aarch64?

jeff

Re: Fold some equal to and not equal to patterns in match.pd

[Segher Boessenkool]

On Thu, Jul 23, 2015 at 10:09:49AM -0600, Jeff Law wrote:
> It seems to me in these kind of cases that selection of the canonical 
> form should be driven by factors outside of which is better for a 
> particular target.  ie, which is simpler

I agree.  But neither form is simpler here, and we need to have both
forms in other contexts, so there is no real benefit to canonicalising.

> Instead we should be looking at the gimple->rtl expansion phase to 
> expand using a form that is better for a particluar target.
> 
> [And yes, I think I've violated this new guiding principle in the past]
> 
> Given the (a << n) EQ/NE form, can we reasonably detect this in the 
> gimple->expansion phase and emit code as if we had the alternate form 
> for targets such as aarch64?

In gimple, both forms have the same complexity as far as I see.

In RTL both forms have the same complexity as well.  RTX cost can be
higher for the AND form (or, in theory at least, can be lower for some
targets).

In my opinion expand shouldn't do anything special here, just emit RTL
like the gimple it is fed, and let the target deal with it, or the
generic RTL optimisers.  Or do we have an example where that does not
work or is inconvenient?


Segher

Re: Fold some equal to and not equal to patterns in match.pd

[Jeff Law]

On 07/23/2015 10:33 AM, Segher Boessenkool wrote:
> On Thu, Jul 23, 2015 at 10:09:49AM -0600, Jeff Law wrote:
>> It seems to me in these kind of cases that selection of the canonical
>> form should be driven by factors outside of which is better for a
>> particular target.  ie, which is simpler
>
> I agree.  But neither form is simpler here, and we need to have both
> forms in other contexts, so there is no real benefit to canonicalising.


a << N ==/!= 0

Looks like two operations.  A shift and a comparison against zero 
regardless of whether or not N is constant.


a&(-1>>N) ==/!= 0

For a varying N, this has a shift, logical and and comparison against zero.

For a constant N obviously the shift collapses to a constant and we're 
left with two operations again.

So for gimple, I'd prefer to see us using the a << N form.

If we need both forms in other contexts, we ought to be looking to 
eliminate that need :-)

If we go to the RTL level, then it's more complex -- it might depend on 
the constant produced by the -1 >> N operation, whether or not the 
target can shift by more than one bit at a time (H8/300 series is 
limited here for example), whether or not one operation sets condition 
codes in a useful way, potentially allowing the comparison to be 
removed, etc etc.  rtx_costs, even with its limitations is probably the 
way to drive selection of form for the RTL optimizers.


Jeff

Re: Fold some equal to and not equal to patterns in match.pd

[Kai Tietz]

2015-07-24 7:54 GMT+02:00 Jeff Law <law@redhat.com>:
> On 07/23/2015 10:33 AM, Segher Boessenkool wrote:
>>
>> On Thu, Jul 23, 2015 at 10:09:49AM -0600, Jeff Law wrote:
>>>
>>> It seems to me in these kind of cases that selection of the canonical
>>> form should be driven by factors outside of which is better for a
>>> particular target.  ie, which is simpler
>>
>>
>> I agree.  But neither form is simpler here, and we need to have both
>> forms in other contexts, so there is no real benefit to canonicalising.
>
>
>
> a << N ==/!= 0
>
> Looks like two operations.  A shift and a comparison against zero regardless
> of whether or not N is constant.
>
>
> a&(-1>>N) ==/!= 0
>
> For a varying N, this has a shift, logical and and comparison against zero.
>
> For a constant N obviously the shift collapses to a constant and we're left
> with two operations again.
>
> So for gimple, I'd prefer to see us using the a << N form.
>
> If we need both forms in other contexts, we ought to be looking to eliminate
> that need :-)
>
> If we go to the RTL level, then it's more complex -- it might depend on the
> constant produced by the -1 >> N operation, whether or not the target can
> shift by more than one bit at a time (H8/300 series is limited here for
> example), whether or not one operation sets condition codes in a useful way,
> potentially allowing the comparison to be removed, etc etc.  rtx_costs, even
> with its limitations is probably the way to drive selection of form for the
> RTL optimizers.
>
>
> Jeff

I fully agree.  But there are case there is not necessarily a 'better'
representation.  For example for sinking converts into shift-operation
can be tricky.

for 'typea a;'

(typeb) (a << N) -> ((typeb) a) << N

'bitsizeof (typeb) <= N' result is always zero.
'bitsizeof (typeb) > N' result needs to be calculated.

But it isn't necessarily easy to say if form '(typeb) (a << N)', or
'((typeb) a) << N' form is to be prefered.  It strongly depends on
expression this pattern is used in.

For RTL this pattern has another issue, as we need to take natural
mode into account here too,

We should define for such forms our 'normal' representation.

Kai

Re: Fold some equal to and not equal to patterns in match.pd

[Richard Biener]

On Fri, Jul 24, 2015 at 9:48 AM, Kai Tietz <ktietz70@googlemail.com> wrote:
> 2015-07-24 7:54 GMT+02:00 Jeff Law <law@redhat.com>:
>> On 07/23/2015 10:33 AM, Segher Boessenkool wrote:
>>>
>>> On Thu, Jul 23, 2015 at 10:09:49AM -0600, Jeff Law wrote:
>>>>
>>>> It seems to me in these kind of cases that selection of the canonical
>>>> form should be driven by factors outside of which is better for a
>>>> particular target.  ie, which is simpler
>>>
>>>
>>> I agree.  But neither form is simpler here, and we need to have both
>>> forms in other contexts, so there is no real benefit to canonicalising.
>>
>>
>>
>> a << N ==/!= 0
>>
>> Looks like two operations.  A shift and a comparison against zero regardless
>> of whether or not N is constant.
>>
>>
>> a&(-1>>N) ==/!= 0
>>
>> For a varying N, this has a shift, logical and and comparison against zero.
>>
>> For a constant N obviously the shift collapses to a constant and we're left
>> with two operations again.
>>
>> So for gimple, I'd prefer to see us using the a << N form.
>>
>> If we need both forms in other contexts, we ought to be looking to eliminate
>> that need :-)
>>
>> If we go to the RTL level, then it's more complex -- it might depend on the
>> constant produced by the -1 >> N operation, whether or not the target can
>> shift by more than one bit at a time (H8/300 series is limited here for
>> example), whether or not one operation sets condition codes in a useful way,
>> potentially allowing the comparison to be removed, etc etc.  rtx_costs, even
>> with its limitations is probably the way to drive selection of form for the
>> RTL optimizers.
>>
>>
>> Jeff
>
> I fully agree.  But there are case there is not necessarily a 'better'
> representation.  For example for sinking converts into shift-operation
> can be tricky.
>
> for 'typea a;'
>
> (typeb) (a << N) -> ((typeb) a) << N
>
> 'bitsizeof (typeb) <= N' result is always zero.
> 'bitsizeof (typeb) > N' result needs to be calculated.
>
> But it isn't necessarily easy to say if form '(typeb) (a << N)', or
> '((typeb) a) << N' form is to be prefered.  It strongly depends on
> expression this pattern is used in.
>
> For RTL this pattern has another issue, as we need to take natural
> mode into account here too,
>
> We should define for such forms our 'normal' representation.

The usual reason for canonicalization is CSE.  In this case you'd
need to have

 X = a & (-1 >> N) == 0;
 Y = a << N == 0;

and want to CSE Y.  Might be not a very common pattern though.

Richard.

> Kai

Re: Fold some equal to and not equal to patterns in match.pd

[Richard Biener]

On Tue, Jul 21, 2015 at 11:15 AM, Hurugalawadi, Naveen
<Naveen.Hurugalawadi@caviumnetworks.com> wrote:
> Hi,
>
> Please find attached the patch which performs following patterns folding
> in match.pd:-
>
> a ==/!= a p+ b to b ==/!= 0.
> a << N ==/!= 0 to a&(-1>>N) ==/!= 0.
> a * N ==/!= 0 where N is a power of 2 to a & (-1<<N2) ==/!= 0 where N2 is log2 of N.
>
> Please review the same and let us know if its okay?

+(match unsigned_integral_valued_p
+ @0
+ (if (INTEGRAL_TYPE_P (type) && TYPE_UNSIGNED (type))))

please avoid adding matches for simple things like this, instead inline the if.

> a * N ==/!= 0 where N is a power of 2 to a & (-1<<N2) ==/!= 0 where N2 is log2 of N.

We have the similar (for the signed case)

/* Transform comparisons of the form X * C1 CMP 0 to X CMP 0 in the
   signed arithmetic case.  That form is created by the compiler
   often enough for folding it to be of value.  One example is in
   computing loop trip counts after Operator Strength Reduction.  */

which shows the transform may be valid for other comparison codes as well.
Note as Jakub says the (-1 << N2) constant may be expensive to generate.
Did you check if we expand to a multiply again if that is the case?

Also you have the same idea in two patterns so if a & (-1 << N2) should
be canonical on GIMPLE (I'd say gimple should prefer "smaller" constants
when the number of operations is the same) then why not simplify
all multiplies that way instead of just those feeding comparisons?  That is,
a * N -> a << N?

So we have the remaining

+/* Fold a ==/!= a p + b to b ==/!= 0.  */
+(for op (ne eq)
+ (simplify
+  (op:c @0 (pointer_plus @0 @1))
+  (op @1 { build_zero_cst (TREE_TYPE (@1)); })))

fold_comparison has the more "complete"

  /* For comparisons of pointers we can decompose it to a compile time
     comparison of the base objects and the offsets into the object.
     This requires at least one operand being an ADDR_EXPR or a
     POINTER_PLUS_EXPR to do more than the operand_equal_p test below.  */

but it looks like you are implementing fold_binarys

      /* Transform comparisons of the form X +- Y CMP X to Y CMP 0.  */
      if ((TREE_CODE (arg0) == PLUS_EXPR
           || TREE_CODE (arg0) == POINTER_PLUS_EXPR
           || TREE_CODE (arg0) == MINUS_EXPR)
          && operand_equal_p (tree_strip_nop_conversions (TREE_OPERAND (arg0,
                                                                        0)),
                              arg1, 0)
          && (INTEGRAL_TYPE_P (TREE_TYPE (arg0))
              || POINTER_TYPE_P (TREE_TYPE (arg0))))
        {
          tree val = TREE_OPERAND (arg0, 1);
          return omit_two_operands_loc (loc, type,
                                    fold_build2_loc (loc, code, type,
                                                 val,
                                                 build_int_cst (TREE_TYPE (val),
                                                                0)),
                                    TREE_OPERAND (arg0, 0), arg1);
        }

but leave out non-pointer support.  So please start over with just
moving the above
code from fold-const.c to match.pd as a pattern.

Thanks,
Richard.


> Regression Tested on X86_64.
>
> On Behalf of Andrew Pinski.
>
> Thanks,
>
> gcc/testsuite/ChangeLog:
>
> 2015-01-21  Andrew Pinski  <apinski@cavium.com>
>
>         * testsuite/gcc.dg/tree-ssa/compare-shiftmult-1.c: New testcase.
>         * testsuite/gcc.dg/tree-ssa/compare_pointers-1.c: New testcase.
>
> gcc/ChangeLog:
>
> 2015-01-21  Andrew Pinski  <apinski@cavium.com>
>
>         * match.pd (define_predicates): Add integer_pow2p.
>         Add pattern for folding of a ==/!= a p+ b to b ==/!= 0.
>         (unsigned_integral_valued_p): New match.
>         Add pattern for folding of a<<N ==/!= 0 to a&(-1>>N) ==/!= 0.
>         Add pattern for folding of a*N ==/!= 0 where N is a power of 2
>         to a&(-1<<N2) ==/!= 0 where N2 is log2 of N.