[gcc r17-3352] match.pd: fold (t * u) % u to zero when the product cannot overflow

https://gcc.gnu.org/g:ce6a2e9349065db52a7e25808aefc97ddaef9cba

commit r17-3352-gce6a2e9349065db52a7e25808aefc97ddaef9cba
Author: Dominic P <[email protected]>
Date:   Thu Aug 13 20:46:26 2026 +0100

    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]>

Diff:
---
 gcc/match.pd                           | 19 +++++++++++++++++++
 gcc/testsuite/gcc.dg/fold-mod-mult-1.c | 25 +++++++++++++++++++++++++
 2 files changed, 44 insertions(+)

diff --git a/gcc/match.pd b/gcc/match.pd
index 665e8eede7f2..0c399a11f8de 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -1141,6 +1141,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 000000000000..9315e94822c4
--- /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" } } */