[PATCH, GCC] PR middle-end/55299, fold bitnot through ASR and rotates

[PATCH, GCC] PR middle-end/55299, fold bitnot through ASR and rotates

[Mikhail Maltsev]

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

Hi!

I decided to revive this patch:
https://gcc.gnu.org/ml/gcc-patches/2015-06/msg00999.html.
I addressed review comments about sign conversions. Bootstrapped and regtested
on x86_64-linux-gnu {,-m32}. OK for trunk?

-- 
Regards,
    Mikhail Maltsev

gcc/testsuite/ChangeLog:

2016-05-08  Mikhail Maltsev  <maltsevm@gmail.com>

        PR tree-optimization/54579
        PR middle-end/55299
        * gcc.dg/fold-notrotate-1.c: New test.
        * gcc.dg/fold-notshift-1.c: New test.
        * gcc.dg/fold-notshift-2.c: New test.


gcc/ChangeLog:

2016-05-08  Mikhail Maltsev  <maltsevm@gmail.com>

        PR tree-optimization/54579
        PR middle-end/55299
        * match.pd (~(~X >> Y), ~(~X >>r Y), ~(~X <<r Y)): New patterns.

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

diff --git a/gcc/match.pd b/gcc/match.pd
index 55dd23c..cc0d03b 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -1453,6 +1453,25 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
     (with { tree mask = int_const_binop (shift, fold_convert (type, @2), @1); }
      (bit_op (shift (convert @0) @1) { mask; }))))))
 
+/* ~((~X) >> Y) -> X >> Y (for arithmetic shift).  */
+(simplify
+ (bit_not (convert? (rshift (bit_not @0) @1)))
+  (if (!TYPE_UNSIGNED (TREE_TYPE (@0)))
+   (convert (rshift @0 @1))))
+(simplify
+ (bit_not (convert? (rshift (convert@0 (bit_not @1)) @2)))
+  (if (!TYPE_UNSIGNED (TREE_TYPE (@0)))
+   (with
+    { tree shift_type = TREE_TYPE (@0); }
+     (convert (rshift:shift_type (convert @1) @2)))))
+
+/* Same as above, but for rotates.  */
+(for rotate (lrotate rrotate)
+ (simplify
+  (bit_not (convert1? (rotate (convert2? (bit_not @0)) @1)))
+   (with
+    { tree operand_type = TREE_TYPE (@0); }
+     (convert (rotate:operand_type @0 @1)))))
 
 /* Simplifications of conversions.  */
 
diff --git a/gcc/testsuite/gcc.dg/fold-notrotate-1.c b/gcc/testsuite/gcc.dg/fold-notrotate-1.c
new file mode 100644
index 0000000..a9b3804
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/fold-notrotate-1.c
@@ -0,0 +1,54 @@
+/* { dg-do compile } */
+/* { dg-options "-O -fdump-tree-optimized" } */
+
+#define INT_BITS  (sizeof (int) * __CHAR_BIT__)
+#define ROL(x, y) ((x) << (y) | (x) >> (INT_BITS - (y)))
+#define ROR(x, y) ((x) >> (y) | (x) << (INT_BITS - (y)))
+
+unsigned
+rol (unsigned a, unsigned b)
+{
+  return ~ROL (~a, b);
+}
+
+unsigned int
+ror (unsigned a, unsigned b)
+{
+  return ~ROR (~a, b);
+}
+
+int
+rol_conv1 (int a, unsigned b)
+{
+  return ~(int)ROL((unsigned)~a, b);
+}
+
+int
+rol_conv2 (int a, unsigned b)
+{
+  return ~ROL((unsigned)~a, b);
+}
+
+int
+rol_conv3 (unsigned a, unsigned b)
+{
+  return ~(int)ROL(~a, b);
+}
+
+#define LONG_BITS  (sizeof (long) * __CHAR_BIT__)
+#define ROLL(x, y) ((x) << (y) | (x) >> (LONG_BITS - (y)))
+#define RORL(x, y) ((x) >> (y) | (x) << (LONG_BITS - (y)))
+
+unsigned long
+roll (unsigned long a, unsigned long b)
+{
+  return ~ROLL (~a, b);
+}
+
+unsigned long
+rorl (unsigned long a, unsigned long b)
+{
+  return ~RORL (~a, b);
+}
+
+/* { dg-final { scan-tree-dump-not "~" "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/fold-notshift-1.c b/gcc/testsuite/gcc.dg/fold-notshift-1.c
new file mode 100644
index 0000000..674f3c7
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/fold-notshift-1.c
@@ -0,0 +1,62 @@
+/* PR tree-optimization/54579
+   PR middle-end/55299 */
+
+/* { dg-do compile } */
+/* { dg-options "-O -fdump-tree-cddce1" } */
+
+int
+asr1 (int a, int b)
+{
+  return ~((~a) >> b);
+}
+
+long
+asr1l (long a, long b)
+{
+  return ~((~a) >> b);
+}
+
+int
+asr_conv (unsigned a, unsigned b)
+{
+  return ~((int)~a >> b);
+}
+
+unsigned
+asr_conv2 (unsigned a, unsigned b)
+{
+  return ~(unsigned)((int)~a >> b);
+}
+
+unsigned
+asr_conv3 (int a, int b)
+{
+  return ~(unsigned)(~a >> b);
+}
+
+int
+asr2 (int a, int b)
+{
+  return -((-a - 1) >> b) - 1;
+}
+
+int
+asr3 (int a, int b)
+{
+  return a < 0 ? ~((~a) >> b) : a >> b;
+}
+
+long
+asr3l (long a, int b)
+{
+  return a < 0 ? ~((~a) >> b) : a >> b;
+}
+
+int
+asr4 (int a, int b)
+{
+  return a < 0 ? -((-a - 1) >> b) - 1 : a >> b;
+}
+
+/* { dg-final { scan-tree-dump-times ">>" 9 "cddce1" } } */
+/* { dg-final { scan-tree-dump-not "~" "cddce1" } } */
diff --git a/gcc/testsuite/gcc.dg/fold-notshift-2.c b/gcc/testsuite/gcc.dg/fold-notshift-2.c
new file mode 100644
index 0000000..5287610
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/fold-notshift-2.c
@@ -0,0 +1,18 @@
+/* PR middle-end/55299 */
+
+/* { dg-do compile } */
+/* { dg-options "-O -fdump-tree-cddce1" } */
+
+unsigned int
+lsr (unsigned int a, unsigned int b)
+{
+  return ~((~a) >> b);
+}
+
+int
+sl (int a, int b)
+{
+  return ~((~a) << b);
+}
+
+/* { dg-final { scan-tree-dump-times "~" 4 "cddce1" } } */

Re: [PATCH, GCC] PR middle-end/55299, fold bitnot through ASR and rotates

[Marc Glisse]

On Sun, 8 May 2016, Mikhail Maltsev wrote:

> Hi!
>
> I decided to revive this patch:
> https://gcc.gnu.org/ml/gcc-patches/2015-06/msg00999.html.
> I addressed review comments about sign conversions. Bootstrapped and regtested
> on x86_64-linux-gnu {,-m32}. OK for trunk?

Hello,

are you sure that your transformations are safe for any kind of 
conversion?

-- 
Marc Glisse

Re: [PATCH, GCC] PR middle-end/55299, fold bitnot through ASR and rotates

[Mikhail Maltsev]

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

On 05/08/2016 10:57 PM, Marc Glisse wrote:
> On Sun, 8 May 2016, Mikhail Maltsev wrote:
> 
>> Hi!
>>
>> I decided to revive this patch:
>> https://gcc.gnu.org/ml/gcc-patches/2015-06/msg00999.html.
>> I addressed review comments about sign conversions. Bootstrapped and regtested
>> on x86_64-linux-gnu {,-m32}. OK for trunk?
> 
> Hello,
> 
> are you sure that your transformations are safe for any kind of conversion?
> 
Oops, indeed, only narrowing conversions should be allowed. I updated the patch
and added some more test cases.

-- 
Regards,
    Mikhail Maltsev

[-- Attachment #2: fold_asr2_2.patch --]
[-- Type: application/x-patch, Size: 4739 bytes --]

Re: [PATCH, GCC] PR middle-end/55299, fold bitnot through ASR and rotates

[Marc Glisse]

On Tue, 10 May 2016, Mikhail Maltsev wrote:

> On 05/08/2016 10:57 PM, Marc Glisse wrote:
>> On Sun, 8 May 2016, Mikhail Maltsev wrote:
>>
>>> Hi!
>>>
>>> I decided to revive this patch:
>>> https://gcc.gnu.org/ml/gcc-patches/2015-06/msg00999.html.
>>> I addressed review comments about sign conversions. Bootstrapped and regtested
>>> on x86_64-linux-gnu {,-m32}. OK for trunk?
>>
>> Hello,
>>
>> are you sure that your transformations are safe for any kind of conversion?
>>
> Oops, indeed, only narrowing conversions should be allowed. I updated the patch
> and added some more test cases.

+/* ~((~X) >> Y) -> X >> Y (for arithmetic shift).  */
+(simplify
+ (bit_not (convert? (rshift (bit_not @0) @1)))
+  (if (!TYPE_UNSIGNED (TREE_TYPE (@0))
+       && TYPE_PRECISION (type) <= TYPE_PRECISION (TREE_TYPE (@0)))
+   (convert (rshift @0 @1))))

Is there a particular reason to split the converting / non-converting
cases? For rotate, you managed to merge them nicely.

+
+(simplify
+ (bit_not (convert? (rshift (convert@0 (bit_not @1)) @2)))
+  (if (!TYPE_UNSIGNED (TREE_TYPE (@0))
+       && TYPE_PRECISION (TREE_TYPE (@0)) <= TYPE_PRECISION (TREE_TYPE (@1))
+       && TYPE_PRECISION (type) <= TYPE_PRECISION (TREE_TYPE (@0)))
+   (with
+    { tree shift_type = TREE_TYPE (@0); }
+     (convert (rshift:shift_type (convert @1) @2)))))
+
+/* Same as above, but for rotates.  */
+(for rotate (lrotate rrotate)
+ (simplify
+  (bit_not (convert1?@0 (rotate (convert2?@1 (bit_not @2)) @3)))
+   (if (TYPE_PRECISION (TREE_TYPE (@1)) <= TYPE_PRECISION (TREE_TYPE (@2))
+        && TYPE_PRECISION (TREE_TYPE (@0)) <= TYPE_PRECISION (TREE_TYPE (@1)))
+    (with
+     { tree operand_type = TREE_TYPE (@2); }
+      (convert (rotate:operand_type @2 @3))))))

Is that really safe when the conversion from @2 to @1 is narrowing? I
would expect something closer to
(convert (rotate (convert:type_of_1 @2) @3))
so the rotation is done in a type of the same precision as the original.

Or
(convert (rotate:type_of_1 (convert @2) @3))
if you prefer specifying the type there (I don't), and note that you
need the 'convert' inside or specifying the type on rotate doesn't work.

I have a slight preference for element_precision over TYPE_PRECISION 
(which for vectors is the number of elements), but I don't think it can 
currently cause issues for these particular transformations.

I don't know if we might want some :c / single_use restrictions, maybe 
on the outer convert and the rshift/rotate.

-- 
Marc Glisse

Re: [PATCH, GCC] PR middle-end/55299, fold bitnot through ASR and rotates

[Mikhail Maltsev]

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

On 05/11/2016 10:52 AM, Marc Glisse wrote:
> +/* ~((~X) >> Y) -> X >> Y (for arithmetic shift).  */
> +(simplify
> + (bit_not (convert? (rshift (bit_not @0) @1)))
> +  (if (!TYPE_UNSIGNED (TREE_TYPE (@0))
> +       && TYPE_PRECISION (type) <= TYPE_PRECISION (TREE_TYPE (@0)))
> +   (convert (rshift @0 @1))))
> 
> Is there a particular reason to split the converting / non-converting
> cases? For rotate, you managed to merge them nicely.
Fixed (i.e., merged two shift simplifications into one).
> 
> +
> +(simplify
> + (bit_not (convert? (rshift (convert@0 (bit_not @1)) @2)))
> +  (if (!TYPE_UNSIGNED (TREE_TYPE (@0))
> +       && TYPE_PRECISION (TREE_TYPE (@0)) <= TYPE_PRECISION (TREE_TYPE (@1))
> +       && TYPE_PRECISION (type) <= TYPE_PRECISION (TREE_TYPE (@0)))
> +   (with
> +    { tree shift_type = TREE_TYPE (@0); }
> +     (convert (rshift:shift_type (convert @1) @2)))))
> +
> +/* Same as above, but for rotates.  */
> +(for rotate (lrotate rrotate)
> + (simplify
> +  (bit_not (convert1?@0 (rotate (convert2?@1 (bit_not @2)) @3)))
> +   (if (TYPE_PRECISION (TREE_TYPE (@1)) <= TYPE_PRECISION (TREE_TYPE (@2))
> +        && TYPE_PRECISION (TREE_TYPE (@0)) <= TYPE_PRECISION (TREE_TYPE (@1)))
> +    (with
> +     { tree operand_type = TREE_TYPE (@2); }
> +      (convert (rotate:operand_type @2 @3))))))
> 
> Is that really safe when the conversion from @2 to @1 is narrowing? I
> would expect something closer to
> (convert (rotate (convert:type_of_1 @2) @3))
> so the rotation is done in a type of the same precision as the original.
> 
> Or
> (convert (rotate:type_of_1 (convert @2) @3))
> if you prefer specifying the type there (I don't), and note that you
> need the 'convert' inside or specifying the type on rotate doesn't work.
Fixed.

> 
> I have a slight preference for element_precision over TYPE_PRECISION (which for
> vectors is the number of elements), but I don't think it can currently cause
> issues for these particular transformations.
Fixed.
> 
> I don't know if we might want some :c / single_use restrictions, maybe on the
> outer convert and the rshift/rotate.
> 
I don't think :c can be used here. As for :s, I added it, as you suggested.

Also, I tried to add some more test cases for rotate with conversions, but
unfortunately GCC does not recognize rotate pattern, when narrowing conversions
are present.

-- 
Regards,
    Mikhail Maltsev

[-- Attachment #2: fold_asr2_3.patch --]
[-- Type: application/x-patch, Size: 4595 bytes --]

Re: [PATCH, GCC] PR middle-end/55299, fold bitnot through ASR and rotates

[Marc Glisse]

On Fri, 13 May 2016, Mikhail Maltsev wrote:

>> I don't know if we might want some :c / single_use restrictions, maybe on the
>> outer convert and the rshift/rotate.
>>
> I don't think :c can be used here.

Oups, typo for :s.

> As for :s, I added it, as you suggested.

:s will be ignored when there is no conversion, but I think that's good 
enough for now.

> Also, I tried to add some more test cases for rotate with conversions, but
> unfortunately GCC does not recognize rotate pattern, when narrowing conversions
> are present.

It is usually easier to split your expression into several assignments. 
Untested:

int f(long long a, unsigned long n){
   long long b = ~a;
   unsigned long c = b;
   unsigned long d = ROLL (c, n);
   int e = d;
   return ~e;
}

this way the rotate pattern is detected early (generic) with no extra 
operations to confuse the compiler, while your new transformation will 
happen in gimple (most likely the first forwprop pass).

The patch looks good to me, now wait for Richard's comments.

-- 
Marc Glisse

Re: [PATCH, GCC] PR middle-end/55299, fold bitnot through ASR and rotates

[Richard Biener]

On Fri, May 13, 2016 at 3:36 PM, Marc Glisse <marc.glisse@inria.fr> wrote:
> On Fri, 13 May 2016, Mikhail Maltsev wrote:
>
>>> I don't know if we might want some :c / single_use restrictions, maybe on
>>> the
>>> outer convert and the rshift/rotate.
>>>
>> I don't think :c can be used here.
>
>
> Oups, typo for :s.
>
>> As for :s, I added it, as you suggested.
>
>
> :s will be ignored when there is no conversion, but I think that's good
> enough for now.

Yeah.  Doing :s twice as done in the patch works though.

>> Also, I tried to add some more test cases for rotate with conversions, but
>> unfortunately GCC does not recognize rotate pattern, when narrowing
>> conversions
>> are present.
>
>
> It is usually easier to split your expression into several assignments.
> Untested:
>
> int f(long long a, unsigned long n){
>   long long b = ~a;
>   unsigned long c = b;
>   unsigned long d = ROLL (c, n);
>   int e = d;
>   return ~e;
> }
>
> this way the rotate pattern is detected early (generic) with no extra
> operations to confuse the compiler, while your new transformation will
> happen in gimple (most likely the first forwprop pass).
>
> The patch looks good to me, now wait for Richard's comments.

Are you sure narrowing conversions are valid for rotates?

(char)short_var <<r 8 == (char)short_var but short_var << r8 is its upper byte.

so at least for the conversion inside the rotate (and shift as well)
only nop-conversions
look valid to me.

Thanks,
Richard.

> --
> Marc Glisse

Re: [PATCH, GCC] PR middle-end/55299, fold bitnot through ASR and rotates

[Mikhail Maltsev]

On 05/17/2016 04:39 PM, Richard Biener wrote:
> 
> Are you sure narrowing conversions are valid for rotates?
> 
> (char)short_var <<r 8 == (char)short_var but short_var << r8 is its upper byte.
> 
Yes, but the transformation leaves conversions as-is. Only bit_not is removed.

-- 
Regards,
    Mikhail Maltsev

Re: [PATCH, GCC] PR middle-end/55299, fold bitnot through ASR and rotates

[Marc Glisse]

On Tue, 17 May 2016, Richard Biener wrote:

> On Fri, May 13, 2016 at 3:36 PM, Marc Glisse <marc.glisse@inria.fr> wrote:
>> On Fri, 13 May 2016, Mikhail Maltsev wrote:
>>
>>>> I don't know if we might want some :c / single_use restrictions, maybe on
>>>> the
>>>> outer convert and the rshift/rotate.
>>>>
>>> I don't think :c can be used here.
>>
>>
>> Oups, typo for :s.
>>
>>> As for :s, I added it, as you suggested.
>>
>>
>> :s will be ignored when there is no conversion, but I think that's good
>> enough for now.
>
> Yeah.  Doing :s twice as done in the patch works though.

I meant that the output will be a single instruction, and thus any :s will 
be ignored (I think).

>>> Also, I tried to add some more test cases for rotate with conversions, but
>>> unfortunately GCC does not recognize rotate pattern, when narrowing
>>> conversions
>>> are present.
>>
>>
>> It is usually easier to split your expression into several assignments.
>> Untested:
>>
>> int f(long long a, unsigned long n){
>>   long long b = ~a;
>>   unsigned long c = b;
>>   unsigned long d = ROLL (c, n);
>>   int e = d;
>>   return ~e;
>> }
>>
>> this way the rotate pattern is detected early (generic) with no extra
>> operations to confuse the compiler, while your new transformation will
>> happen in gimple (most likely the first forwprop pass).
>>
>> The patch looks good to me, now wait for Richard's comments.
>
> Are you sure narrowing conversions are valid for rotates?

My reasoning is that narrowing conversions and bit_not commute (sign 
extensions should be fine as well IIRC). So you can essentially pull 
convert1 out and push convert2 down to @1 (notice how the the result 
converts the input and the output), and simplify the middle (rotate and 
bit_not commute) without any conversion.

Note that an alternative way to handle the transformation would be to fix 
a canonical order for some things that commute. Turn non-extending convert 
of bit_not into bit_not of convert, turn rotate of bit_not to bit_not of 
rotate (or the reverse, whatever), etc. If we are lucky, this might move 
the 2 bit_not next to each other, where they can cancel out. But that's 
more ambitious.

I heard that llvm and visual studio were using a prover for such 
transforms. Without going that far, it might be good to use some 
automation to check that a transform works say for all values of all types 
of precision at most 4 or something, if someone is motivated...

> (char)short_var <<r 8 == (char)short_var but short_var << r8 is its upper byte.
>
> so at least for the conversion inside the rotate (and shift as well)
> only nop-conversions look valid to me.

Notice that the rotation is done in the type of @0 both before and after.

-- 
Marc Glisse

Re: [PATCH, GCC] PR middle-end/55299, fold bitnot through ASR and rotates

[Richard Biener]

On Tue, May 17, 2016 at 4:05 PM, Marc Glisse <marc.glisse@inria.fr> wrote:
> On Tue, 17 May 2016, Richard Biener wrote:
>
>> On Fri, May 13, 2016 at 3:36 PM, Marc Glisse <marc.glisse@inria.fr> wrote:
>>>
>>> On Fri, 13 May 2016, Mikhail Maltsev wrote:
>>>
>>>>> I don't know if we might want some :c / single_use restrictions, maybe
>>>>> on
>>>>> the
>>>>> outer convert and the rshift/rotate.
>>>>>
>>>> I don't think :c can be used here.
>>>
>>>
>>>
>>> Oups, typo for :s.
>>>
>>>> As for :s, I added it, as you suggested.
>>>
>>>
>>>
>>> :s will be ignored when there is no conversion, but I think that's good
>>> enough for now.
>>
>>
>> Yeah.  Doing :s twice as done in the patch works though.
>
>
> I meant that the output will be a single instruction, and thus any :s will
> be ignored (I think).

Yes, if the outer convert is a no-op then :s will be ignored (and that is good).

>>>> Also, I tried to add some more test cases for rotate with conversions,
>>>> but
>>>> unfortunately GCC does not recognize rotate pattern, when narrowing
>>>> conversions
>>>> are present.
>>>
>>>
>>>
>>> It is usually easier to split your expression into several assignments.
>>> Untested:
>>>
>>> int f(long long a, unsigned long n){
>>>   long long b = ~a;
>>>   unsigned long c = b;
>>>   unsigned long d = ROLL (c, n);
>>>   int e = d;
>>>   return ~e;
>>> }
>>>
>>> this way the rotate pattern is detected early (generic) with no extra
>>> operations to confuse the compiler, while your new transformation will
>>> happen in gimple (most likely the first forwprop pass).
>>>
>>> The patch looks good to me, now wait for Richard's comments.
>>
>>
>> Are you sure narrowing conversions are valid for rotates?
>
>
> My reasoning is that narrowing conversions and bit_not commute (sign
> extensions should be fine as well IIRC). So you can essentially pull
> convert1 out and push convert2 down to @1 (notice how the the result
> converts the input and the output), and simplify the middle (rotate and
> bit_not commute) without any conversion.

Ah, indeed.  I missed the rotation/shift is done on the same type as before.

> Note that an alternative way to handle the transformation would be to fix a
> canonical order for some things that commute. Turn non-extending convert of
> bit_not into bit_not of convert, turn rotate of bit_not to bit_not of rotate
> (or the reverse, whatever), etc. If we are lucky, this might move the 2
> bit_not next to each other, where they can cancel out. But that's more
> ambitious.
>
> I heard that llvm and visual studio were using a prover for such transforms.
> Without going that far, it might be good to use some automation to check
> that a transform works say for all values of all types of precision at most
> 4 or something, if someone is motivated...
>
>> (char)short_var <<r 8 == (char)short_var but short_var << r8 is its upper
>> byte.
>>
>> so at least for the conversion inside the rotate (and shift as well)
>> only nop-conversions look valid to me.
>
>
> Notice that the rotation is done in the type of @0 both before and after.

Yeah, failed to notice that.

The patch is ok.

Thanks,
Richard.

> --
> Marc Glisse

Re: [PATCH, GCC] PR middle-end/55299, fold bitnot through ASR and rotates

[Mikhail Maltsev]

On 05/17/2016 06:09 PM, Richard Biener wrote:
> 
> The patch is ok.
> 

Committed as r236344.

-- 
Regards,
    Mikhail Maltsev