[v2] tree-optimization: Reduce (t * u) / v when gcd(u, v) > 1

Message ID 20261011112109.329442-1-shivam98.tkg@gmail.com
State New
Headers
Series [v2] tree-optimization: Reduce (t * u) / v when gcd(u, v) > 1 |

Commit Message

Shivam Gupta Oct. 11, 2026, 11:21 a.m. UTC
  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

Jeff Law Oct. 25, 2026, 2:54 p.m. UTC | #1
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
  
Jeff Law Oct. 25, 2026, 2:55 p.m. UTC | #2
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
  

Patch

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
+     ))))))
+
 /* 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.  */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr126311.c b/gcc/testsuite/gcc.dg/tree-ssa/pr126311.c
new file mode 100644
index 000000000..45381c2b4
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr126311.c
@@ -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" } } */