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

On Mon, 17 Aug 2026 at 13:57, Richard Biener <[email protected]> wrote:

> On Thu, 13 Aug 2026, Dominic P wrote:
>
> > 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)
>
> Looks OK, but how did you test this patch?
>
 Bootstrapped and regtested on x86_64-pc-linux-gnu, no regressions.

>
> Richard.
>
> > 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" } } */
> >
>
> --
> Richard Biener <[email protected]>
> SUSE Software Solutions Germany GmbH,
> Frankenstrasse 146, 90461 Nuernberg, Germany;
> GF: Jochen Jaser, Andrew McDonald, Abhinav Puri; (HRB 36809, AG Nuernberg)
>
>