This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [PATCH, GCC] PR middle-end/55299, fold bitnot through ASR and rotates
- From: Mikhail Maltsev <maltsevm at gmail dot com>
- To: Marc Glisse <marc dot glisse at inria dot fr>
- Cc: Richard Biener <richard dot guenther at gmail dot com>, gcc-patches at gcc dot gnu dot org
- Date: Fri, 13 May 2016 14:55:16 +0300
- Subject: Re: [PATCH, GCC] PR middle-end/55299, fold bitnot through ASR and rotates
- Authentication-results: sourceware.org; auth=none
- References: <572F6B36 dot 8050804 at gmail dot com> <alpine dot DEB dot 2 dot 20 dot 1605082148450 dot 2068 at laptop-mg dot saclay dot inria dot fr> <5731E816 dot 9050006 at gmail dot com> <alpine dot DEB dot 2 dot 20 dot 1605110924430 dot 1902 at laptop-mg dot saclay dot inria dot fr>
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
diff --git a/gcc/match.pd b/gcc/match.pd
index 55dd23c..bb4bba6 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -1453,6 +1453,27 @@ 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 (convert1?:s (rshift:s (convert2?@0 (bit_not @1)) @2)))
+ (if (!TYPE_UNSIGNED (TREE_TYPE (@0))
+ && element_precision (TREE_TYPE (@0))
+ <= element_precision (TREE_TYPE (@1))
+ && element_precision (type) <= element_precision (TREE_TYPE (@0)))
+ (with
+ { tree shift_type = TREE_TYPE (@0); }
+ (convert (rshift (convert:shift_type @1) @2)))))
+
+/* ~(~X >>r Y) -> X >>r Y
+ ~(~X <<r Y) -> X <<r Y */
+(for rotate (lrotate rrotate)
+ (simplify
+ (bit_not (convert1?:s (rotate:s (convert2?@0 (bit_not @1)) @2)))
+ (if (element_precision (TREE_TYPE (@0)) <= element_precision (TREE_TYPE (@1))
+ && element_precision (type) <= element_precision (TREE_TYPE (@0)))
+ (with
+ { tree rotate_type = TREE_TYPE (@0); }
+ (convert (rotate (convert:rotate_type @1) @2))))))
/* 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..2de236f
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/fold-notshift-1.c
@@ -0,0 +1,77 @@
+/* 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);
+}
+
+typedef __INT32_TYPE__ int32_t;
+typedef __INT64_TYPE__ int64_t;
+
+int32_t
+asr_conv4 (int64_t a, int b)
+{
+ return ~((int32_t)~a >> b);
+}
+
+int32_t
+asr_conv5 (int64_t a, int b)
+{
+ return ~(int32_t)(~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;
+}
+
+int64_t
+asr3l (int64_t 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 ">>" 11 "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..32635f1
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/fold-notshift-2.c
@@ -0,0 +1,33 @@
+/* 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);
+}
+
+typedef __INT32_TYPE__ int32_t;
+typedef __INT64_TYPE__ int64_t;
+
+int64_t
+asr_widen1 (int32_t a, int b)
+{
+ return ~((int64_t)(~a) >> b);
+}
+
+int64_t
+asr_widen2 (int32_t a, int b)
+{
+ return ~(int64_t)(~a >> b);
+}
+
+/* { dg-final { scan-tree-dump-times "~" 8 "cddce1" } } */