[PATCH 1/2] match.pd: fold (t * u) % u to zero when the product cannot overflow

A product t * u is an exact multiple of u, so t * u % u is zero under
every rounding convention whenever the multiplication does not wrap.
For signed types the overflow is undefined so this always holds; for
others use value ranges to prove the multiply is overflow-free, exactly
as the neighbouring (t * u) / u -> t already does.  This is the
remainder counterpart of that fold, for all four modulo codes: the
C family only produces TRUNC_MOD_EXPR, but Fortran's MODULO and Ada's
mod produce the floor and ceiling forms, which fold equally.

Assisted-by: Claude Opus 4.8 (Anthropic)

gcc/ChangeLog:

	* match.pd ((t * u) % u -> 0): New simplification.

gcc/testsuite/ChangeLog:

	* gcc.dg/fold-mod-mult-1.c: New test.

Signed-off-by: Dominic P <[email protected]>
---
 gcc/match.pd                           | 19 +++++++++++++++++++
 gcc/testsuite/gcc.dg/fold-mod-mult-1.c | 25 +++++++++++++++++++++++++
 2 files changed, 44 insertions(+)
 create mode 100644 gcc/testsuite/gcc.dg/fold-mod-mult-1.c

diff --git a/gcc/match.pd b/gcc/match.pd
index 3f476cc4baa..90fb2acede4 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -1144,6 +1144,25 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
 #endif
    ))))
 
+/* Simplify (t * u) % u -> 0.  The product is an exact multiple of u, so
+   the remainder is zero under every rounding convention as long as the
+   multiplication does not overflow.  Mirrors (t * u) / u -> t above.  */
+(for mod (trunc_mod floor_mod ceil_mod round_mod)
+ (simplify
+  (mod (mult:c@2 @0 @1) @1)
+  (if (ANY_INTEGRAL_TYPE_P (type))
+   (if (TYPE_OVERFLOW_UNDEFINED (type) && !TYPE_OVERFLOW_SANITIZED (type))
+    { build_zero_cst (type); }
+#if GIMPLE
+    (with {int_range_max vr0, vr1;}
+     (if (INTEGRAL_TYPE_P (type)
+	  && gimple_match_range_of_expr (vr0, @0, @2)
+	  && gimple_match_range_of_expr (vr1, @1, @2)
+	  && range_op_handler (MULT_EXPR).overflow_free_p (vr0, vr1))
+      { build_zero_cst (type); }))
+#endif
+   ))))
+
 #if GIMPLE
 (for div (trunc_div exact_div)
  /* Simplify (X + M*N) / N -> X / N + M.  */
diff --git a/gcc/testsuite/gcc.dg/fold-mod-mult-1.c b/gcc/testsuite/gcc.dg/fold-mod-mult-1.c
new file mode 100644
index 00000000000..9315e94822c
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/fold-mod-mult-1.c
@@ -0,0 +1,25 @@
+/* (t * u) % u is zero whenever the product does not overflow: for signed
+   types the overflow is undefined so it always folds; for unsigned types it
+   folds when value ranges prove the multiply cannot wrap.  */
+/* { dg-do compile } */
+/* { dg-require-effective-target int32plus } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+int
+f_signed (int a, int b)
+{
+  return (a * b) % b;
+}
+
+unsigned
+f_ranged (unsigned a, unsigned b)
+{
+  a &= 0xffff;
+  b &= 0xffff;
+  if (b == 0)
+    return 7;
+  return (a * b) % b;		/* a*b <= 0xfffe0001, cannot wrap */
+}
+
+/* Both remainders fold away; no modulo survives.  */
+/* { dg-final { scan-tree-dump-not " % " "optimized" } } */
-- 
2.55.0