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
