[v2] tree-optimization: Reduce (t * u) / v when gcd(u, v) > 1
Commit Message
For an integer division (t * u) / v where the constants u and v share a
common factor g = gcd (u, v) > 1, rewrite it as (t * (u / g)) / (v / g).
This is done when t * u is known not to overflow: always for types with
undefined overflow, otherwise only if the value range of t shows that the
multiplication cannot wrap.
The smaller constants avoid overflow and give cheaper
division-by-constant sequences.
Regression tested on aarch64-unknown-linux-gnu.
PR tree-optimization/126311
Changes since v1:
* v2: Fix the scan counts in pr126311.c.
Add a bounded unsigned case in the same test file.
gcc/ChangeLog:
* match.pd ((t * u) / v): Reduce integer constants u and v by
their greatest common divisor if gcd(u, v) > 1.
gcc/testsuite/ChangeLog:
* gcc.dg/tree-ssa/pr126311.c: New test.
Signed-off-by: Shivam Gupta <shivam98.tkg@gmail.com>
---
gcc/match.pd | 26 +++++++++++++++++++
gcc/testsuite/gcc.dg/tree-ssa/pr126311.c | 32 ++++++++++++++++++++++++
2 files changed, 58 insertions(+)
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr126311.c
Comments
On 10/11/26 5:21 AM, Shivam Gupta wrote:
> For an integer division (t * u) / v where the constants u and v share a
> common factor g = gcd (u, v) > 1, rewrite it as (t * (u / g)) / (v / g).
>
> This is done when t * u is known not to overflow: always for types with
> undefined overflow, otherwise only if the value range of t shows that the
> multiplication cannot wrap.
>
> The smaller constants avoid overflow and give cheaper
> division-by-constant sequences.
>
> Regression tested on aarch64-unknown-linux-gnu.
>
> PR tree-optimization/126311
>
> Changes since v1:
> * v2: Fix the scan counts in pr126311.c.
> Add a bounded unsigned case in the same test file.
>
> gcc/ChangeLog:
>
> * match.pd ((t * u) / v): Reduce integer constants u and v by
> their greatest common divisor if gcd(u, v) > 1.
>
> gcc/testsuite/ChangeLog:
>
> * gcc.dg/tree-ssa/pr126311.c: New test.
>
> Signed-off-by: Shivam Gupta <shivam98.tkg@gmail.com>
> ---
> gcc/match.pd | 26 +++++++++++++++++++
> gcc/testsuite/gcc.dg/tree-ssa/pr126311.c | 32 ++++++++++++++++++++++++
> 2 files changed, 58 insertions(+)
> create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr126311.c
>
> diff --git a/gcc/match.pd b/gcc/match.pd
> index 2d1161b86..5b2b5c09c 100644
> --- a/gcc/match.pd
> +++ b/gcc/match.pd
> @@ -1163,6 +1163,32 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
> #endif
> ))))
>
> +/* Simplify (t * u) / v -> (t * (u / g)) / (v / g) where g = gcd(u, v) > 1. */
> +(for div (trunc_div exact_div)
> + (simplify
> + (div (mult@3 @0 INTEGER_CST@1) INTEGER_CST@2)
> + (if (INTEGRAL_TYPE_P (type)
> + && !integer_zerop (@2))
> + (with {
> + wide_int w1 = wi::to_wide (@1);
> + wide_int w2 = wi::to_wide (@2);
> + wide_int g = wi::gcd (w1, w2, TYPE_SIGN (type));
> + }
> + (if (wi::gt_p (g, 1, TYPE_SIGN (type))
> + && wi::ne_p (g, w2))
> + (if (TYPE_OVERFLOW_UNDEFINED (type) && !TYPE_OVERFLOW_SANITIZED (type))
> + (div (mult @0 { wide_int_to_tree (type, wi::div_trunc (w1, g, TYPE_SIGN (type))); })
> + { wide_int_to_tree (type, wi::div_trunc (w2, g, TYPE_SIGN (type))); })
> +#if GIMPLE
> + (with { int_range_max vr0, vr1; }
> + (if (gimple_match_range_of_expr (vr0, @0, @3)
> + && gimple_match_range_of_expr (vr1, @1)
> + && range_op_handler (MULT_EXPR).overflow_free_p (vr0, vr1))
> + (div (mult @0 { wide_int_to_tree (type, wi::div_trunc (w1, g, TYPE_SIGN (type))); })
> + { wide_int_to_tree (type, wi::div_trunc (w2, g, TYPE_SIGN (type))); })))
> +#endif
> + ))))))
LLM review suggests this may not be correct due to how wi::abs works
under the hood. Can you please double-check the LLM finding and take
appropriate action. LLM review also suggested a ":s" on the multiply
expression to ensure the only use is in your pattern. If it were used
elsewhere you'd end up with two multiplies since you emit a fresh one in
your pattern.
Given the LLM flagged a potential mis-compilation, please try to include
that case as a runnable regression test if you can get it to trigger.
jeff
On 10/11/26 5:21 AM, Shivam Gupta wrote:
> For an integer division (t * u) / v where the constants u and v share a
> common factor g = gcd (u, v) > 1, rewrite it as (t * (u / g)) / (v / g).
>
> This is done when t * u is known not to overflow: always for types with
> undefined overflow, otherwise only if the value range of t shows that the
> multiplication cannot wrap.
>
> The smaller constants avoid overflow and give cheaper
> division-by-constant sequences.
>
> Regression tested on aarch64-unknown-linux-gnu.
>
> PR tree-optimization/126311
>
> Changes since v1:
> * v2: Fix the scan counts in pr126311.c.
> Add a bounded unsigned case in the same test file.
>
> gcc/ChangeLog:
>
> * match.pd ((t * u) / v): Reduce integer constants u and v by
> their greatest common divisor if gcd(u, v) > 1.
>
> gcc/testsuite/ChangeLog:
>
> * gcc.dg/tree-ssa/pr126311.c: New test.
>
> Signed-off-by: Shivam Gupta <shivam98.tkg@gmail.com>
Forgot pointer to the LLM review:
https://gcc.sashiko.dev/#/patchset/20261011112109.329442-1-shivam98.tkg%40gmail.com
Jeff
@@ -1163,6 +1163,32 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
#endif
))))
+/* Simplify (t * u) / v -> (t * (u / g)) / (v / g) where g = gcd(u, v) > 1. */
+(for div (trunc_div exact_div)
+ (simplify
+ (div (mult@3 @0 INTEGER_CST@1) INTEGER_CST@2)
+ (if (INTEGRAL_TYPE_P (type)
+ && !integer_zerop (@2))
+ (with {
+ wide_int w1 = wi::to_wide (@1);
+ wide_int w2 = wi::to_wide (@2);
+ wide_int g = wi::gcd (w1, w2, TYPE_SIGN (type));
+ }
+ (if (wi::gt_p (g, 1, TYPE_SIGN (type))
+ && wi::ne_p (g, w2))
+ (if (TYPE_OVERFLOW_UNDEFINED (type) && !TYPE_OVERFLOW_SANITIZED (type))
+ (div (mult @0 { wide_int_to_tree (type, wi::div_trunc (w1, g, TYPE_SIGN (type))); })
+ { wide_int_to_tree (type, wi::div_trunc (w2, g, TYPE_SIGN (type))); })
+#if GIMPLE
+ (with { int_range_max vr0, vr1; }
+ (if (gimple_match_range_of_expr (vr0, @0, @3)
+ && gimple_match_range_of_expr (vr1, @1)
+ && range_op_handler (MULT_EXPR).overflow_free_p (vr0, vr1))
+ (div (mult @0 { wide_int_to_tree (type, wi::div_trunc (w1, g, TYPE_SIGN (type))); })
+ { wide_int_to_tree (type, wi::div_trunc (w2, g, TYPE_SIGN (type))); })))
+#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. */
new file mode 100644
@@ -0,0 +1,32 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+/* gcd(6, 10) == 2: (t * 6) / 10 -> (t * 3) / 5 */
+int src_pos (int t) {
+ return (t * 6) / 10;
+}
+
+/* Same with a negative multiplier: (t * -6) / 10 -> (t * -3) / 5 */
+int src_neg (int t) {
+ return (t * -6) / 10;
+}
+
+/* Reduced: b is unsigned short, so t is in [0, 65535] and t * 6u cannot wrap. */
+unsigned int src_unsigned_bounded (unsigned short b) {
+ unsigned int t = b;
+ return (t * 6u) / 10u;
+}
+
+/* Not reduced: t may be any unsigned value, so ranger can't prove
+ t * 6u doesn't wrap. */
+unsigned int src_unsigned_unbounded (unsigned int t) {
+ return (t * 6u) / 10u;
+}
+
+/* No common factor: gcd(7, 10) == 1 (should stay / 10) */
+int src_gcd_one (int t) {
+ return (t * 7) / 10;
+}
+
+/* { dg-final { scan-tree-dump-times " / 5" 3 "optimized" } } */
+/* { dg-final { scan-tree-dump-times " / 10" 2 "optimized" } } */