Re: [PATCH] match: fold a remainder of a remainder by a multiple
Kyrylo Tkachov <[email protected]> Thu, 6 Aug 2026 14:42:01 +0000
| Newsgroups | gmane.comp.gcc.patches |
|---|---|
| Message-ID | <[email protected]> |
> On 6 Aug 2026, at 06:16, Jeffrey Law <[email protected]> wrote: > > > > On 8/4/2026 3:50 AM, [email protected] wrote: >> From: Kyrylo Tkachov <[email protected]> >> >> Truncating remainder keeps the sign of the dividend and its magnitude >> modulo the divisor, so reducing X % C1 again modulo C2 gives the same >> result as reducing X directly whenever C2 divides C1. Folding the pair >> removes one division. >> >> int f (int x) { return (x % 12) % 4; } >> >> aarch64 -O2: >> >> before after >> mov w1, 12 negs w1, w0 >> sdiv w1, w0, w1 and w0, w0, 3 >> add w1, w1, w1, lsl 1 and w1, w1, 3 >> sub w0, w0, w1, lsl 2 csneg w0, w0, w1, mi >> negs w1, w0 >> and w0, w0, 3 >> and w1, w1, 3 >> csneg w0, w0, w1, mi >> >> Bootstrapped and tested on aarch64-none-linux-gnu. >> Ok for trunk? >> Thanks, >> Kyrill >> >> gcc/ChangeLog: >> >> * match.pd ((X % C1) % C2): New simplification. >> >> gcc/testsuite/ChangeLog: >> >> * gcc.dg/tree-ssa/modmod-1.c: New test. >> >> Signed-off-by: Kyrylo Tkachov <[email protected]> >> --- >> gcc/match.pd | 12 ++++++++++++ >> gcc/testsuite/gcc.dg/tree-ssa/modmod-1.c | 19 +++++++++++++++++++ >> 2 files changed, 31 insertions(+) >> create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/modmod-1.c >> >> diff --git a/gcc/match.pd b/gcc/match.pd >> index 4fca75d6fb6..22202af2cc1 100644 >> --- a/gcc/match.pd >> +++ b/gcc/match.pd >> @@ -975,6 +975,18 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) >> (with { tree utype = unsigned_type_for (TREE_TYPE (@0)); } >> (cmp (mod (convert:utype @0) (convert:utype @2)) (convert:utype @1))))))) >> +/* (X % C1) % C2 is X % C2 when C2 divides C1. Truncating remainder keeps >> + the sign of X and the magnitude modulo C1, so reducing modulo C2 gives >> + the same result as reducing X directly. */ >> +(simplify >> + (trunc_mod (trunc_mod @0 INTEGER_CST@1) INTEGER_CST@2) >> + (if (INTEGRAL_TYPE_P (type) >> + && !TYPE_OVERFLOW_TRAPS (type) >> + && !integer_zerop (@1) >> + && !integer_zerop (@2) >> + && wi::multiple_of_p (wi::to_widest (@1), wi::to_widest (@2), SIGNED)) > Is SIGNED really correct for that argument to wi::multiple_of_p? I don't have a testcase where it matters. Just a generic question. > I think so, yes. UNSIGNED would misinterpret negative constants. One change I did make is guard against (X % -1) % C2 to avoid removing a trap or diagnostic under -ftrapv for x = INT_MIN. > > >> + (trunc_mod @0 @2))) >> + >> /* X % -C is the same as X % C. */ >> (simplify >> (trunc_mod @0 INTEGER_CST@1) >> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/modmod-1.c b/gcc/testsuite/gcc.dg/tree-ssa/modmod-1.c >> new file mode 100644 >> index 00000000000..6689a518ff3 >> --- /dev/null >> +++ b/gcc/testsuite/gcc.dg/tree-ssa/modmod-1.c >> @@ -0,0 +1,19 @@ >> +/* { dg-do compile } */ >> +/* { dg-options "-O2 -fdump-tree-optimized" } */ >> + >> +/* (X % C1) % C2 is X % C2 when C2 divides C1. */ >> + >> +int f1 (int x) { return (x % 12) % 4; } >> +int f2 (int x) { return (x % 100) % 25; } >> +int f3 (int x) { return (x % -12) % 4; } >> +int f4 (int x) { return (x % 12) % -4; } >> +unsigned int f5 (unsigned int x) { return (x % 12) % 4; } > For f5, do you want to verify it collapses to an & 3? I guess the lack of % 12 or %4 for it is probably sufficient since the other counts would get thrown off if we failed to optimize f5 down to &3. Yes, I’ve made that change > > Generally it looks good. Just like to nail down that the SIGNED argument is really what we want. Thanks, attached is an updated version. Is this one ok? Kyrill > > Jeff
0001-match-fold-a-remainder-of-a-remainder-by-a-multiple.patch
(application/octet-stream, 6.6 KB)
From 2848029c4d064edc7aa9fc00dba4c70aea3e48be Mon Sep 17 00:00:00 2001 From: Kyrylo Tkachov <[email protected]> Date: Wed, 29 Jul 2026 21:26:46 +0200 Subject: [PATCH] match: fold a remainder of a remainder by a multiple Truncating remainder keeps the sign of the dividend and its magnitude modulo the divisor, so reducing X % C1 again modulo C2 gives the same result as reducing X directly whenever C2 divides C1. Folding the pair removes one division. int f (int x) { return (x % 12) % 4; } aarch64 -O2: before after mov w1, 12 negs w1, w0 sdiv w1, w0, w1 and w0, w0, 3 add w1, w1, w1, lsl 1 and w1, w1, 3 sub w0, w0, w1, lsl 2 csneg w0, w0, w1, mi negs w1, w0 and w0, w0, 3 and w1, w1, 3 csneg w0, w0, w1, mi Use signed divisibility because wi::to_widest preserves the signed value of a negative constant. Keep an inner remainder by -1 when it can trap or carry sanitizer instrumentation. An outer remainder by -1 is zero after a safe inner remainder and folds without introducing an INT_MIN % -1 operation. Bootstrapped and tested on aarch64-none-linux-gnu. gcc/ChangeLog: * match.pd ((X % C1) % C2): New simplification. gcc/testsuite/ChangeLog: * gcc.dg/tree-ssa/modmod-1.c: New test. * gcc.dg/tree-ssa/modmod-2.c: Likewise. * gcc.dg/tree-ssa/modmod-3.c: Likewise. * gcc.dg/tree-ssa/modmod-4.c: Likewise. * gcc.dg/tree-ssa/modmod-5.c: Likewise. Signed-off-by: Kyrylo Tkachov <[email protected]> --- gcc/match.pd | 16 ++++++++++++++++ gcc/testsuite/gcc.dg/tree-ssa/modmod-1.c | 17 +++++++++++++++++ gcc/testsuite/gcc.dg/tree-ssa/modmod-2.c | 8 ++++++++ gcc/testsuite/gcc.dg/tree-ssa/modmod-3.c | 10 ++++++++++ gcc/testsuite/gcc.dg/tree-ssa/modmod-4.c | 11 +++++++++++ gcc/testsuite/gcc.dg/tree-ssa/modmod-5.c | 19 +++++++++++++++++++ 6 files changed, 81 insertions(+) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/modmod-1.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/modmod-2.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/modmod-3.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/modmod-4.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/modmod-5.c diff --git a/gcc/match.pd b/gcc/match.pd index c35792cd7e2..127ba0d0873 100644 --- a/gcc/match.pd +++ b/gcc/match.pd @@ -974,6 +974,22 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) (with { tree utype = unsigned_type_for (TREE_TYPE (@0)); } (cmp (mod (convert:utype @0) (convert:utype @2)) (convert:utype @1))))))) +/* (X % C1) % C2 is X % C2 when C2 divides C1. Truncating remainder keeps + the sign of X and the magnitude modulo C1, so reducing modulo C2 gives + the same result as reducing X directly. */ +(simplify + (trunc_mod (trunc_mod @0 INTEGER_CST@1) INTEGER_CST@2) + (if (INTEGRAL_TYPE_P (type) + && ((!TYPE_OVERFLOW_TRAPS (type) + && !TYPE_OVERFLOW_SANITIZED (type)) + || !integer_minus_onep (@1)) + && !integer_zerop (@1) + && !integer_zerop (@2) + && wi::multiple_of_p (wi::to_widest (@1), wi::to_widest (@2), SIGNED)) + (if (!TYPE_UNSIGNED (type) && integer_minus_onep (@2)) + { build_zero_cst (type); } + (trunc_mod @0 @2)))) + /* X % -C is the same as X % C. */ (simplify (trunc_mod @0 INTEGER_CST@1) diff --git a/gcc/testsuite/gcc.dg/tree-ssa/modmod-1.c b/gcc/testsuite/gcc.dg/tree-ssa/modmod-1.c new file mode 100644 index 00000000000..aa5cd9858c2 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/modmod-1.c @@ -0,0 +1,17 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +/* (X % C1) % C2 is X % C2 when C2 divides C1. */ + +int f1 (int x) { return (x % 12) % 4; } +int f2 (int x) { return (x % 100) % 25; } +int f3 (int x) { return (x % -15) % 3; } +int f4 (int x) { return (x % 15) % -3; } +unsigned int f5 (unsigned int x) { return (x % 12) % 4; } + +/* Each pair folds to one remainder. */ +/* { dg-final { scan-tree-dump-not " % 12;" "optimized" } } */ +/* { dg-final { scan-tree-dump-times " % 4;" 1 "optimized" } } */ +/* { dg-final { scan-tree-dump-times " % 25;" 1 "optimized" } } */ +/* { dg-final { scan-tree-dump-times " % 3;" 2 "optimized" } } */ +/* { dg-final { scan-tree-dump-times " & 3;" 1 "optimized" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/modmod-2.c b/gcc/testsuite/gcc.dg/tree-ssa/modmod-2.c new file mode 100644 index 00000000000..0fe74932776 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/modmod-2.c @@ -0,0 +1,8 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +/* Five does not divide twelve, so both remainders have to stay. */ +int f (int x) { return (x % 12) % 5; } + +/* { dg-final { scan-tree-dump-times " % 12;" 1 "optimized" } } */ +/* { dg-final { scan-tree-dump-times " % 5;" 1 "optimized" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/modmod-3.c b/gcc/testsuite/gcc.dg/tree-ssa/modmod-3.c new file mode 100644 index 00000000000..9d90173f6a5 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/modmod-3.c @@ -0,0 +1,10 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -ftrapv -fdump-tree-optimized" } */ + +/* Interpreting -15 as signed proves that three divides it. The inner + remainder cannot overflow, so trapping arithmetic does not block the + fold. */ +int f (int x) { return (x % -15) % 3; } + +/* { dg-final { scan-tree-dump-not " % 15;" "optimized" } } */ +/* { dg-final { scan-tree-dump-times " % 3;" 1 "optimized" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/modmod-4.c b/gcc/testsuite/gcc.dg/tree-ssa/modmod-4.c new file mode 100644 index 00000000000..a19da7928f9 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/modmod-4.c @@ -0,0 +1,11 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fsanitize=signed-integer-overflow -fdump-tree-optimized" } */ + +int f1 (int x) { return (x % -1) % 1; } +int f2 (int x) { return (x % -15) % 3; } + +/* Keep the possible INT_MIN % -1 diagnostic in f1. The safe f2 pair still + folds. */ +/* { dg-final { scan-tree-dump-times "__ubsan_handle_divrem_overflow" 1 "optimized" } } */ +/* { dg-final { scan-tree-dump-not " % 15;" "optimized" } } */ +/* { dg-final { scan-tree-dump-times " % 3;" 1 "optimized" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/modmod-5.c b/gcc/testsuite/gcc.dg/tree-ssa/modmod-5.c new file mode 100644 index 00000000000..d76fb619990 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/modmod-5.c @@ -0,0 +1,19 @@ +/* { dg-do run } */ +/* { dg-options "-O2 -ftrapv" } */ + +#include <limits.h> + +__attribute__ ((noipa)) +static int +f (int x) +{ + return (x % 12) % -1; +} + +int +main (void) +{ + if (f (INT_MIN) != 0 || f (-1) != 0 || f (0) != 0 || f (INT_MAX) != 0) + __builtin_abort (); + return 0; +} -- 2.50.1 (Apple Git-155)