[RFC PATCH] match: Use wide_int for shift-and-mask folding [PR120524]

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.

Signed-off-by: Avinal Kumar <[email protected]>
---
Hi, I tried to replace it 1:1. But it isn't working. I think I have hit a wall
with this. The change compiles fine but never gets fired for
any case. Please take a look.

For 64-bit types (long long), the C frontend already performs
this optimization during parsing. it appears in
-fdump-tree-original, so the match.pd pattern was never the
path that optimized (a >> 63) & 1. This means there is no
easy way to test whether the pattern fires for the simpler
case.

Expected variable values for (a >> 127) & 1 with __int128 (prec=128):
 - shiftc = 127
 - mask = 0x1
 - zerobits = ~0 with top bit clear  (wi::mask(128-127, true, 128) = 0xfff...fe)
 - mask & zerobits = 0,  shift_type = unsigned __int128
 - newmask = mask | zerobits = 0xfff...ff
 - newmask + 1 = 2^128 (overflows to 0 in 128-bit precision)

That last point may be the problem, wi::exact_log2 of a 128-bit
zero would return -1, failing the lg > 0 check.  But I haven't been
able to confirm this is the issue since the pattern doesn't appear
to be reached at all.

Thanks

 gcc/match.pd                             | 49 +++++++++++-------------
 gcc/testsuite/gcc.dg/tree-ssa/pr120524.c | 12 ++++++
 2 files changed, 34 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 eae8717bcfe..4ee309b324b 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -5643,20 +5643,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))
 	 {
@@ -5680,12 +5679,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
@@ -5693,35 +5689,34 @@ 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 = 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..19993665c92
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr120524.c
@@ -0,0 +1,12 @@
+/* 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; }
+
+/* The arithmetic right shifts should be converted to logical shifts.  */
+/* { dg-final { scan-tree-dump "unsigned __int128"  "optimized" } } */
-- 
2.55.0