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
