The pattern that folds (X >> C1) & C2 and (X << C1) & C2 was limited
to types with precision <= HOST_BITS_PER_WIDE_INT because it used
unsigned HOST_WIDE_INT for mask and zerobits arithmetic. This prevents
the optimization from firing on __int128 and wider types at the GIMPLE
level.
Convert the pattern to use wide_int and remove the TYPE_PRECISION guard.
Replace the mode-mask loop with wi::exact_log2 (newmask + 1) to check
whether newmask is (2^n - 1) for a power-of-two n >= BITS_PER_UNIT.
Handle the case where newmask is all-ones at full type precision
separately, since newmask + 1 overflows to zero in that case.
PR120524
PR tree-optimization/120524
gcc/ChangeLog:
* match.pd: Use wide_int for shift-and-mask folding [PR120524]
gcc/testsuite/ChangeLog:
* gcc.dg/tree-ssa/pr120524.c: New test.
Signed-off-by: Avinal Kumar <[email protected]>
---
Chnages from RFC:
- fixed pattern not hitting due to overflow
- added more tests and a regression guard
Tested on x86_64 machine. Optimization result:
avinal@cfarm422:~/gcc-work/build$ ./gcc/xgcc -B ./gcc -O2
-fdump-tree-optimized=/dev/stdout
~/gcc-work/gcc/gcc/testsuite/gcc.dg/tree-ssa/pr120524.c -c -o /dev/null
;; Function f1 (f1, funcdef_no=0, decl_uid=2966, cgraph_uid=1, symbol_order=0)
__int128 f1 (__int128 a)
{
uint128_t a.0_1;
uint128_t _2;
__int128 _4;
<bb 2> [local count: 1073741824]:
a.0_1 = (uint128_t) a_3(D);
_2 = a.0_1 >> 127;
_4 = (__int128) _2;
return _4;
}
;; Function f2 (f2, funcdef_no=1, decl_uid=2969, cgraph_uid=2, symbol_order=1)
__int128 f2 (__int128 a)
{
uint128_t a.1_1;
uint128_t _2;
__int128 _4;
<bb 2> [local count: 1073741824]:
a.1_1 = (uint128_t) a_3(D);
_2 = a.1_1 >> 120;
_4 = (__int128) _2;
return _4;
}
;; Function f3 (f3, funcdef_no=2, decl_uid=2972, cgraph_uid=3, symbol_order=2)
__int128 f3 (__int128 a)
{
__int128 _2;
<bb 2> [local count: 1073741824]:
_2 = a_1(D) << 120;
return _2;
}
;; Function f4 (f4, funcdef_no=3, decl_uid=2975, cgraph_uid=4, symbol_order=3)
long long int f4 (long long int a)
{
unsigned long a.2_1;
unsigned long _2;
long long int _4;
<bb 2> [local count: 1073741824]:
a.2_1 = (unsigned long) a_3(D);
_2 = a.2_1 >> 63;
_4 = (long long int) _2;
return _4;
}
gcc/match.pd | 55 ++++++++++++------------
gcc/testsuite/gcc.dg/tree-ssa/pr120524.c | 28 ++++++++++++
2 files changed, 56 insertions(+), 27 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr120524.c
diff --git a/gcc/match.pd b/gcc/match.pd
index 2a5f948c965..5825ebafaf6 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -5670,20 +5670,19 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
(bit_and (convert?:s@4 (shift:s@5 (convert1?@3 @0) INTEGER_CST@1))
INTEGER_CST@2)
(if (tree_nop_conversion_p (TREE_TYPE (@4), TREE_TYPE (@5))
- && TYPE_PRECISION (type) <= HOST_BITS_PER_WIDE_INT
&& tree_fits_uhwi_p (@1)
&& tree_to_uhwi (@1) > 0
&& tree_to_uhwi (@1) < TYPE_PRECISION (type))
(with
{
unsigned int shiftc = tree_to_uhwi (@1);
- unsigned HOST_WIDE_INT mask = TREE_INT_CST_LOW (@2);
- unsigned HOST_WIDE_INT newmask, zerobits = 0;
+ wide_int mask = wi::to_wide (@2);
+ wide_int newmask, zerobits = wi::zero (TYPE_PRECISION (type));
tree shift_type = TREE_TYPE (@3);
unsigned int prec;
if (shift == LSHIFT_EXPR)
- zerobits = ((HOST_WIDE_INT_1U << shiftc) - 1);
+ zerobits = wi::mask (shiftc, false, TYPE_PRECISION (type));
else if (shift == RSHIFT_EXPR
&& type_has_mode_precision_p (shift_type))
{
@@ -5707,12 +5706,9 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
is all ones. */
}
}
- zerobits = HOST_WIDE_INT_M1U;
+ zerobits = wi::minus_one (TYPE_PRECISION (type));
if (shiftc < prec)
- {
- zerobits >>= HOST_BITS_PER_WIDE_INT - shiftc;
- zerobits <<= prec - shiftc;
- }
+ zerobits = wi::mask (prec - shiftc, true, TYPE_PRECISION (type));
/* For arithmetic shift if sign bit could be set, zerobits
can contain actually sign bits, so no transformation is
possible, unless MASK masks them all away. In that
@@ -5720,35 +5716,40 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
if (!TYPE_UNSIGNED (TREE_TYPE (@3))
&& prec == TYPE_PRECISION (TREE_TYPE (@3)))
{
- if ((mask & zerobits) == 0)
+ if (wi::eq_p (wi::bit_and (mask, zerobits),
+ wi::zero (TYPE_PRECISION (type))))
shift_type = unsigned_type_for (TREE_TYPE (@3));
else
- zerobits = 0;
+ zerobits = wi::zero (TYPE_PRECISION (type));
}
}
}
/* ((X << 16) & 0xff00) is (X, 0). */
- (if ((mask & zerobits) == mask)
+ (if (wi::eq_p (wi::bit_and (mask, zerobits), mask))
{ build_int_cst (type, 0); }
- (with { newmask = mask | zerobits; }
- (if (newmask != mask && (newmask & (newmask + 1)) == 0)
- (with
- {
- /* Only do the transformation if NEWMASK is some integer
- mode's mask. */
- for (prec = BITS_PER_UNIT;
- prec < HOST_BITS_PER_WIDE_INT; prec <<= 1)
- if (newmask == (HOST_WIDE_INT_1U << prec) - 1)
- break;
- }
- (if (prec < HOST_BITS_PER_WIDE_INT
- || newmask == HOST_WIDE_INT_M1U)
+ (with { newmask = wi::bit_or (mask, zerobits);
+ /* Only do the transformation if NEWMASK is some integer
+ mode's mask, i.e. an all-ones value (2^n - 1) where n
+ is a power of 2 precision >= BITS_PER_UNIT. We check
+ this by testing whether newmask + 1 is a power of two
+ via wi::exact_log2. */
+ int lg;
+ /* newmask + 1 overflows at full type precision (e.g. 128-bit
+ all-ones), so handle that case directly. */
+ if (wi::eq_p (newmask, wi::minus_one (TYPE_PRECISION (type))))
+ lg = TYPE_PRECISION (type);
+ else
+ lg = wi::exact_log2 (wi::add (newmask, 1));
+ unsigned int newmask_prec = lg >= 0 ? (unsigned int) lg : 0; }
+ (if (!wi::eq_p (newmask, mask)
+ && lg > 0 && (newmask_prec & (newmask_prec - 1)) == 0
+ && newmask_prec >= BITS_PER_UNIT)
(with
- { tree newmaskt = build_int_cst_type (TREE_TYPE (@2), newmask); }
+ { tree newmaskt = wide_int_to_tree (TREE_TYPE (@2), newmask); }
(if (!tree_int_cst_equal (newmaskt, @2))
(if (shift_type != TREE_TYPE (@3))
(bit_and (convert (shift:shift_type (convert @3) @1)) { newmaskt;
})
- (bit_and @4 { newmaskt; })))))))))))))
+ (bit_and @4 { newmaskt; })))))))))))
/* ((1 << n) & M) != 0 -> n == log2 (M) */
(for cmp (ne eq)
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr120524.c
b/gcc/testsuite/gcc.dg/tree-ssa/pr120524.c
new file mode 100644
index 00000000000..b9d9bae74ff
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr120524.c
@@ -0,0 +1,28 @@
+/* PR tree-optimization/120524 */
+/* { dg-do compile } */
+/* { dg-require-effective-target int128 } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+/* Verify (a >> 127) & 1 is optimized to (unsigned __int128)a >> 127.
+ The mask 1 covers all sign-extended bits, so the arithmetic right shift
+ can be converted to a logical right shift. */
+__int128 f1(__int128 a) { return (a >> 127) & 1; }
+
+/* Verify (a >> 120) & 0xff is similarly optimized. */
+__int128 f2(__int128 a) { return (a >> 120) & 0xff; }
+
+/* Verify the left shift path of the same pattern also works for 128-bit
+ types. The mask isolates only the shifted bits, so the redundant lower
+ bits can be folded into the mask. */
+__int128 f3(__int128 a) { return (a << 120) & ((__int128)0xff << 120); }
+
+/* f1, f2: arithmetic right shifts should be converted to logical shifts. */
+/* { dg-final { scan-tree-dump "uint128_t" "optimized" } } */
+
+/* Verify 64-bit case also works, this is folded by C frontend putting it
+ here as regression guard. */
+long long f4(long long a) { return (a >> 63) & 1; }
+
+/* All BIT_AND masks should be folded away. */
+/* { dg-final { scan-tree-dump-not "& 1" "optimized" } } */
+/* { dg-final { scan-tree-dump-not "& 255" "optimized" } } */
--
2.55.0
