[PATCH] match.pd: fold extract-bitfield-and-shift expressions

This patch adds a simplification rule for expressions of the form
((X >> C1) & C2) << C3, which extract some bits from X at position C1,
perform an "and" with a mask which is normally just 2^N - 1, then shift
the result left by C3.  The transformation is limited to cases where X
is unsigned, has its precision equal to its width and where C1 and C3
are smaller than the precision of X (the last condition could probably
be just assumed but I wasn't sure so decided to play it safe).

When all of the above conditions hold, the expression is folded into
either: (a) (X >> (C1 - C3)) & (C2 << C3) when C1 >= C3, or (b)
(X << (C3 - C1)) & (C2 << C3) when C1 < C3.  Additional care is required
to preserve the leading zeros formed by the X >> C1 operation in the
original expression; to handle this, we clear the leading bits of the
mask operand as a preliminary step.

The corner case where C1 is one less the precision of X is handled
elsewhere (and is folded to just (X >> C1) << C3 as long as the LSB of
C2 isn't 0.)

On aarch64, this results in:

        lsr     x0, x0, 16
        and     w0, w0, 130816

being emitted instead of:

        lsr     x1, x0, 32
        lsr     x0, x0, 24
        ubfiz   w1, w1, 16, 1
        ubfiz   w0, w0, 8, 8
        orr     w0, w1, w0

for the expression "((x >> 32) & 1) << 16) | (x >> 24) & 0xff) << 8)".

A couple of new testcases added, with some focus on the case where X is
shifted too far to the right as described above.

Survives bootstrap and regtest on aarch64-linux-gnu and x86_64-linux-gnu.

gcc/ChangeLog:

        * match.pd: New rule to fold ((X >> C1) & C2) << C3.

gcc/testsuite/ChangeLog:

        * gcc.dg/tree-ssa/match-bit-extract-shift.c: New test.
---
 gcc/match.pd                                  | 21 +++++++
 .../gcc.dg/tree-ssa/match-bit-extract-shift.c | 61 +++++++++++++++++++
 2 files changed, 82 insertions(+)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/match-bit-extract-shift.c

diff --git a/gcc/match.pd b/gcc/match.pd
index beea45357e2..5f914cd0fad 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -1481,6 +1481,27 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
     { tree utype = unsigned_type_for (type); }
     (convert (rshift (lshift (convert:utype @0) @2) @3))))))
 
+/* Fold (((X >> C1) & C2) << C3) into (X >>/<< |C1 - C3|) & (C2 << C3).  */
+(simplify
+ (lshift (bit_and (rshift @0 INTEGER_CST@1) INTEGER_CST@2) INTEGER_CST@3)
+  (if (TYPE_UNSIGNED (TREE_TYPE (@0))
+       && type_has_mode_precision_p (TREE_TYPE (@0)))
+   (with { int prec = TYPE_PRECISION (TREE_TYPE (@0)); }
+    (if (wi::ltu_p (wi::to_wide (@1), prec)
+	 && wi::ltu_p (wi::to_wide (@3), prec))
+     (with
+      {
+	/* Clear the first PREC - @1 bits of the mask, then shift it.  */
+	wide_int mask_lz = wi::mask (prec - tree_to_uhwi (@1), false, prec);
+	tree mask = fold_build2 (BIT_AND_EXPR, TREE_TYPE (@0),
+			@2, wide_int_to_tree (TREE_TYPE (@0), mask_lz));
+	tree mask_shifted = fold_build2 (LSHIFT_EXPR, TREE_TYPE (@0),
+					 mask, @3);
+      }
+      (if (wi::leu_p (wi::to_wide (@1), wi::to_wide (@3)))
+       (bit_and (lshift @0 (minus @3 @1)) { mask_shifted; })
+       (bit_and (rshift @0 (minus @1 @3)) { mask_shifted; })))))))
+
 /* Fold ((type)(a<0)) << SIGNBITOFA into ((type)a) & signbit. */
 (simplify
  (lshift (convert (lt @0 integer_zerop@1)) INTEGER_CST@2)
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/match-bit-extract-shift.c b/gcc/testsuite/gcc.dg/tree-ssa/match-bit-extract-shift.c
new file mode 100644
index 00000000000..292ce5a41c9
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/match-bit-extract-shift.c
@@ -0,0 +1,61 @@
+/* { dg-require-effective-target stdint_types } */
+/* { dg-do compile } */
+/* { dg-options "-O1 -fdump-tree-forwprop1" } */
+
+#include <stdint.h>
+
+uint32_t f (uint64_t x)
+{
+  return (((x >> 32) & 0x1) << 16)
+	  | (((x >> 24) & 0xff) << 8);
+}
+
+uint32_t f2 (uint64_t x)
+{
+  return (((x >> 3) & 0x3) << 16);
+}
+
+uint32_t f3 (uint64_t x)
+{
+  return (((x >> 61) & 0xE) << 16);
+}
+
+uint32_t f4 (uint64_t x)
+{
+  return (((x >> 62) & 0xE) << 16);
+}
+
+uint32_t f5 (uint64_t x)
+{
+  return (((x >> 63) & 0xF) << 17);
+}
+
+uint64_t f6 (uint64_t x)
+{
+  return (((x >> 32) & 0xFFFFFF) << 47);
+}
+
+/* { dg-final { scan-tree-dump-not "<< 16" forwprop1 } } */
+/* { dg-final { scan-tree-dump-not ">> 32" forwprop1 } } */
+/* { dg-final { scan-tree-dump-not ">> 24" forwprop1 } } */
+/* { dg-final { scan-tree-dump-not ">> 3" forwprop1 } } */
+/* { dg-final { scan-tree-dump-not ">> 61" forwprop1 } } */
+/* { dg-final { scan-tree-dump-not ">> 62" forwprop1 } } */
+/* { dg-final { scan-tree-dump-not "<< 47" forwprop1 } } */
+/* { dg-final { scan-tree-dump-not "& 65536" forwprop1 } } */
+/* { dg-final { scan-tree-dump-not "& 65535" forwprop1 } } */
+/* { dg-final { scan-tree-dump-not "& 917504" forwprop1 } } */
+
+/* { dg-final { scan-tree-dump-times ">> 16" 1 forwprop1 } } */
+/* { dg-final { scan-tree-dump-times ">> 45" 1 forwprop1 } } */
+/* { dg-final { scan-tree-dump-times ">> 46" 1 forwprop1 } } */
+/* { dg-final { scan-tree-dump-times "<< 13" 1 forwprop1 } } */
+/* { dg-final { scan-tree-dump-times ">> 63" 1 forwprop1 } } */
+/* { dg-final { scan-tree-dump-times "<< 17" 1 forwprop1 } } */
+/* { dg-final { scan-tree-dump-times "<< 15" 1 forwprop1 } } */
+/* { dg-final { scan-tree-dump-times "& 130816" 1 forwprop1 } } */
+/* { dg-final { scan-tree-dump-times "& 196608" 1 forwprop1 } } */
+/* { dg-final { scan-tree-dump-times "& 393216" 1 forwprop1 } } */
+/* { dg-final { scan-tree-dump-times "& 131072" 1 forwprop1 } } */
+/* { dg-final { scan-tree-dump-times "& 18446603336221196288" 1 forwprop1 } } */
+
-- 
2.34.1