Fold bit_not through ASR and rotate

gcc/

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

gcc/testsuite

	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.

From-SVN: r236344

6 files changed, 199 insertions, 0 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 76c40ae..cf13477 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,9 @@
+2016-05-17  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.
+
 2016-05-17  Marek Polacek  <polacek@redhat.com>
 
 	PR ipa/71146
diff --git a/gcc/match.pd b/gcc/match.pd
index db8e39c..eddacd4 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -1501,6 +1501,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/ChangeLog b/gcc/testsuite/ChangeLog
index 3b4d72c..e5127af 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,11 @@
+2016-05-17  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.
+
 2016-05-17  Marek Polacek  <polacek@redhat.com>
 
 	PR ipa/71146
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" } } */