https://gcc.gnu.org/g:980c3302d34f1a6977f69cacbe327ac894844e1d
commit r17-3053-g980c3302d34f1a6977f69cacbe327ac894844e1d Author: Kyrylo Tkachov <[email protected]> Date: Wed Jul 29 21:26:46 2026 +0200 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]> Diff: --- 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(+) diff --git a/gcc/match.pd b/gcc/match.pd index 94801f19fc61..62cc01380bcc 100644 --- a/gcc/match.pd +++ b/gcc/match.pd @@ -940,6 +940,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 000000000000..aa5cd9858c2e --- /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 000000000000..0fe749327769 --- /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 000000000000..9d90173f6a53 --- /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 000000000000..a19da7928f91 --- /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 000000000000..d76fb619990c --- /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; +}
