diff mbox series

match: fold a remainder compared with its dividend

Message ID 20260804100602.56531-1-ktkachov@nvidia.com
State New
Headers
Series match: fold a remainder compared with its dividend |

Checks

Context Check Description
linaro-tcwg-bot/tcwg_simplebootstrap_build--master-arm-bootstrap success Build passed
linaro-tcwg-bot/tcwg_simplebootstrap_build--master-aarch64-bootstrap success Build passed
linaro-tcwg-bot/tcwg_gcc_build--master-arm success Build passed
linaro-tcwg-bot/tcwg_gcc_build--master-aarch64 success Build passed

Commit Message

Kyrylo Tkachov Aug. 4, 2026, 10:06 a.m. UTC 
  From: Kyrylo Tkachov <ktkachov@nvidia.com>

A remainder of non-negative operands equals its dividend exactly when the
dividend is smaller than the divisor.  Comparing the two therefore does
not need the division at all.  This sits next to the (X / Y) == 0 rule,
which has the same shape and the same non-negativity requirement.

  int f (unsigned x, unsigned y) { return x % y == x; }

aarch64 -O2:

  before                          after
    udiv  w2, w0, w1                cmp   w0, w1
    msub  w2, w2, w1, w0            cset  w0, cc
    cmp   w2, w0
    cset  w0, eq

The :s marker cannot reject this flat replacement.  Remove the inactive
marker.

A zero divisor can raise a non-call exception.  Keep the division or
remainder when the divisor might be zero and non-call exceptions are
enabled.  Also keep an explicit zero divisor for diagnostics.

Bootstrapped and tested on aarch64-none-linux-gnu.
Ok for trunk?
Thanks,
Kyrill

gcc/ChangeLog:

	* match.pd ((X / Y) ==/!= 0): Preserve a possible zero-divisor
	exception.
	((X % Y) ==/!= X): New simplification.  Preserve a possible
	zero-divisor exception.

gcc/testsuite/ChangeLog:

	* gcc.dg/tree-ssa/modcmp-1.c: New test.
	* gcc.dg/tree-ssa/modcmp-noncall-1.c: Likewise.

Signed-off-by: Kyrylo Tkachov <ktkachov@nvidia.com>
---
 gcc/match.pd                                  | 16 +++++++++--
 gcc/testsuite/gcc.dg/tree-ssa/modcmp-1.c      | 22 +++++++++++++++
 .../gcc.dg/tree-ssa/modcmp-noncall-1.c        | 27 +++++++++++++++++++
 3 files changed, 63 insertions(+), 2 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/modcmp-1.c
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/modcmp-noncall-1.c

Comments

Jeffrey Law Aug. 6, 2026, 4:58 a.m. UTC | #1 
On 8/4/2026 4:06 AM, ktkachov@nvidia.com wrote:
> From: Kyrylo Tkachov <ktkachov@nvidia.com>
>
> A remainder of non-negative operands equals its dividend exactly when the
> dividend is smaller than the divisor.  Comparing the two therefore does
> not need the division at all.  This sits next to the (X / Y) == 0 rule,
> which has the same shape and the same non-negativity requirement.
>
>    int f (unsigned x, unsigned y) { return x % y == x; }
>
> aarch64 -O2:
>
>    before                          after
>      udiv  w2, w0, w1                cmp   w0, w1
>      msub  w2, w2, w1, w0            cset  w0, cc
>      cmp   w2, w0
>      cset  w0, eq
>
> The :s marker cannot reject this flat replacement.  Remove the inactive
> marker.
>
> A zero divisor can raise a non-call exception.  Keep the division or
> remainder when the divisor might be zero and non-call exceptions are
> enabled.  Also keep an explicit zero divisor for diagnostics.
>
> Bootstrapped and tested on aarch64-none-linux-gnu.
> Ok for trunk?
> Thanks,
> Kyrill
>
> gcc/ChangeLog:
>
> 	* match.pd ((X / Y) ==/!= 0): Preserve a possible zero-divisor
> 	exception.
> 	((X % Y) ==/!= X): New simplification.  Preserve a possible
> 	zero-divisor exception.
>
> gcc/testsuite/ChangeLog:
>
> 	* gcc.dg/tree-ssa/modcmp-1.c: New test.
> 	* gcc.dg/tree-ssa/modcmp-noncall-1.c: Likewise.
Like most of these, I'm curious where this showed up :-)

It looks correct to me.  OK for the trunk.  Note that your cover 
indicates you removed a :s tag, but I don't see that in the patch. 
  Probably best to resolve that one way or another before committing.

Thanks,

jeff
Kyrylo Tkachov Aug. 6, 2026, 5:06 a.m. UTC | #2 
> On 6 Aug 2026, at 06:58, Jeffrey Law <jeffrey.law@oss.qualcomm.com> wrote:
> 
> 
> 
> On 8/4/2026 4:06 AM, ktkachov@nvidia.com wrote:
>> From: Kyrylo Tkachov <ktkachov@nvidia.com>
>> 
>> A remainder of non-negative operands equals its dividend exactly when the
>> dividend is smaller than the divisor.  Comparing the two therefore does
>> not need the division at all.  This sits next to the (X / Y) == 0 rule,
>> which has the same shape and the same non-negativity requirement.
>> 
>>   int f (unsigned x, unsigned y) { return x % y == x; }
>> 
>> aarch64 -O2:
>> 
>>   before                          after
>>     udiv  w2, w0, w1                cmp   w0, w1
>>     msub  w2, w2, w1, w0            cset  w0, cc
>>     cmp   w2, w0
>>     cset  w0, eq
>> 
>> The :s marker cannot reject this flat replacement.  Remove the inactive
>> marker.
>> 
>> A zero divisor can raise a non-call exception.  Keep the division or
>> remainder when the divisor might be zero and non-call exceptions are
>> enabled.  Also keep an explicit zero divisor for diagnostics.
>> 
>> Bootstrapped and tested on aarch64-none-linux-gnu.
>> Ok for trunk?
>> Thanks,
>> Kyrill
>> 
>> gcc/ChangeLog:
>> 
>> * match.pd ((X / Y) ==/!= 0): Preserve a possible zero-divisor
>> exception.
>> ((X % Y) ==/!= X): New simplification.  Preserve a possible
>> zero-divisor exception.
>> 
>> gcc/testsuite/ChangeLog:
>> 
>> * gcc.dg/tree-ssa/modcmp-1.c: New test.
>> * gcc.dg/tree-ssa/modcmp-noncall-1.c: Likewise.
> Like most of these, I'm curious where this showed up :-)

I asked an AI agent to mine SPEC2026 and a few other workloads that are of interest to me to find missing folds.
It turned out to be a quite productive exercise. I can recommend it as a way to constructively use these agents for things other than writing GCC code. I don’t think this particular fold is on a hot path or anything, but it is obviously a beneficial one anyway (it reduces the complexity of the IR, as match.pd folds intend) 

> 
> It looks correct to me.  OK for the trunk.  Note that your cover indicates you removed a :s tag, but I don't see that in the patch.  Probably best to resolve that one way or another before committing.

Yes, will do.
Thanks,
Kyrill

> 
> Thanks,
> 
> jeff
Jeffrey Law Aug. 6, 2026, 5:45 a.m. UTC | #3 
On 8/5/2026 11:06 PM, Kyrylo Tkachov wrote:
>> Like most of these, I'm curious where this showed up :-)
> I asked an AI agent to mine SPEC2026 and a few other workloads that are of interest to me to find missing folds.
> It turned out to be a quite productive exercise. I can recommend it as a way to constructively use these agents for things other than writing GCC code. I don’t think this particular fold is on a hot path or anything, but it is obviously a beneficial one anyway (it reduces the complexity of the IR, as match.pd folds intend)
THanks.  We should probably talk further given that info.    I've 
proposed a talk for Cauldron, one section of which would be using LLMs 
to help discover code sequences we can improve.  What we've been 
experimenting with is taking hot block information from QEMU (in the 
form of assembly blocks with headers indicating how hot the block is), 
then having the LLM mine those blocks for improved instruction 
sequences.  Then we (of course) validate what the LLM finds and 
determine if it's worth implementing.  We've found several things using 
this approach for RISC-V.  It has the nice property that when the LLM 
flags something, you know it's hit at runtime and you can evaluate if 
it's hot enough to be likely worth the time to fix.

If you wanted to co-present what you're doing, I can certainly make 
room.  Or if you're already proposing a session, I'll have to make sure 
to attend.

Jeff
Kyrylo Tkachov Aug. 7, 2026, 5:55 a.m. UTC | #4 
> On 6 Aug 2026, at 07:45, Jeffrey Law <jeffrey.law@oss.qualcomm.com> wrote:
> 
> 
> 
> On 8/5/2026 11:06 PM, Kyrylo Tkachov wrote:
>>> Like most of these, I'm curious where this showed up :-)
>> I asked an AI agent to mine SPEC2026 and a few other workloads that are of interest to me to find missing folds.
>> It turned out to be a quite productive exercise. I can recommend it as a way to constructively use these agents for things other than writing GCC code. I don’t think this particular fold is on a hot path or anything, but it is obviously a beneficial one anyway (it reduces the complexity of the IR, as match.pd folds intend)
> THanks.  We should probably talk further given that info.    I've proposed a talk for Cauldron, one section of which would be using LLMs to help discover code sequences we can improve.  What we've been experimenting with is taking hot block information from QEMU (in the form of assembly blocks with headers indicating how hot the block is), then having the LLM mine those blocks for improved instruction sequences.  Then we (of course) validate what the LLM finds and determine if it's worth implementing.  We've found several things using this approach for RISC-V.  It has the nice property that when the LLM flags something, you know it's hit at runtime and you can evaluate if it's hot enough to be likely worth the time to fix.
> 
> If you wanted to co-present what you're doing, I can certainly make room.  Or if you're already proposing a session, I'll have to make sure to attend.

I’d be happy to.
I was thinking of proposing a session on using AI tools for GCC development in general: finding opportunities, bugs, orchestration etc. I’m happy to co-present at your session as it seems we’re thinking about the same topics.
Thanks,
Kyrill 

> 
> Jeff
diff mbox series

Patch

diff --git a/gcc/match.pd b/gcc/match.pd
index 285e3ead48a..d797893d228 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -3160,13 +3160,25 @@  DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
 
 /* Transform:
    (X / Y) == 0 -> X < Y if X, Y are non-negative.
-   (X / Y) != 0 -> X >= Y, if X, Y are non-negative.  */
+   (X / Y) != 0 -> X >= Y, if X, Y are non-negative.
+   (X % Y) == X -> X < Y if X, Y are non-negative.
+   (X % Y) != X -> X >= Y, if X, Y are non-negative.  */
 (for cmp (eq ne)
      ocmp (lt ge)
  (simplify
   (cmp (trunc_div tree_expr_nonnegative_p@0 tree_expr_nonnegative_p@1) integer_zerop)
        /* Complex ==/!= is allowed, but not </>=.  */
-  (if (TREE_CODE (TREE_TYPE (@0)) != COMPLEX_TYPE
+  (if (!integer_zerop (@1)
+       && (!flag_non_call_exceptions || tree_expr_nonzero_p (@1))
+       && TREE_CODE (TREE_TYPE (@0)) != COMPLEX_TYPE
+       && (VECTOR_TYPE_P (type) || !VECTOR_TYPE_P (TREE_TYPE (@0))))
+   (ocmp @0 @1)))
+ (simplify
+  (cmp:c (trunc_mod tree_expr_nonnegative_p@0 tree_expr_nonnegative_p@1) @0)
+  /* A complex modulo cannot exist, so unlike the division above this
+     needs no complex exclusion.  */
+  (if (!integer_zerop (@1)
+       && (!flag_non_call_exceptions || tree_expr_nonzero_p (@1))
        && (VECTOR_TYPE_P (type) || !VECTOR_TYPE_P (TREE_TYPE (@0))))
    (ocmp @0 @1))))
 
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/modcmp-1.c b/gcc/testsuite/gcc.dg/tree-ssa/modcmp-1.c
new file mode 100644
index 00000000000..a59882e66a3
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/modcmp-1.c
@@ -0,0 +1,22 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+/* A remainder of non-negative operands equals its dividend exactly when the
+   dividend is smaller than the divisor, so the division can go away.  */
+
+int f1 (unsigned int x, unsigned int y) { return x % y == x; }
+int f2 (unsigned int x, unsigned int y) { return x % y != x; }
+int f3 (unsigned long x, unsigned long y) { return x == x % y; }
+int f4 (int x, int y)
+{
+  x &= __INT_MAX__;
+  y &= __INT_MAX__;
+  return x % y == x;
+}
+
+/* Signed operands that may be negative do not have that property.  */
+int f5 (int x, int y) { return x % y == x; }
+
+/* { dg-final { scan-tree-dump-times " % " 1 "optimized" } } */
+/* { dg-final { scan-tree-dump-times " < " 3 "optimized" } } */
+/* { dg-final { scan-tree-dump-times " >= " 1 "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/modcmp-noncall-1.c b/gcc/testsuite/gcc.dg/tree-ssa/modcmp-noncall-1.c
new file mode 100644
index 00000000000..aa5074b4517
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/modcmp-noncall-1.c
@@ -0,0 +1,27 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O2 -fnon-call-exceptions -fdump-tree-optimized" } */
+
+/* A possibly zero divisor can trap when non-call exceptions are enabled,
+   so the comparison must keep the division or remainder.  */
+
+int f1 (unsigned int x, unsigned int y) { return x / y == 0; }
+int f2 (unsigned int x, unsigned int y) { return x / y != 0; }
+int f3 (unsigned int x, unsigned int y) { return x % y == x; }
+int f4 (unsigned int x, unsigned int y) { return x % y != x; }
+
+/* A known nonzero divisor can still fold.  */
+int f5 (unsigned int x) { return x / 3 == 0; }
+int f6 (unsigned int x) { return x % 3 == x; }
+
+/* An explicit zero must retain the front-end diagnostic and trap.  */
+int f7 (unsigned int x)
+{
+  return x / 0 == 0; /* { dg-warning "division by zero" } */
+}
+int f8 (unsigned int x)
+{
+  return x % 0 == x; /* { dg-warning "division by zero" } */
+}
+
+/* { dg-final { scan-tree-dump-times " / " 3 "optimized" } } */
+/* { dg-final { scan-tree-dump-times " % " 3 "optimized" } } */