When evaluating integer division of the form (t * u) / v where constants
u and v share a common factor g = gcd(u, v) > 1, the expression can be
simplified to (t * (u / g)) / (v / g).
This patch adds a new match.pd pattern to compute the GCD of INTEGER_CST
operands using wi::gcd on absolute values and reduce both operands
accordingly to reduce signed overflow and generate cheaper
division-by-constant reciprocal sequences.
Regression tested on x86_64-pc-linux-gnu.
PR tree-optimization/126311
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 <[email protected]>
---
gcc/match.pd | 26 ++++++++++++++++++++++++
gcc/testsuite/gcc.dg/tree-ssa/pr126311.c | 23 +++++++++++++++++++++
2 files changed, 49 insertions(+)
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr126311.c
diff --git a/gcc/match.pd b/gcc/match.pd
index 54cad1cd2..4df6d289a 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -1139,6 +1139,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..108e9ea45
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr126311.c
@@ -0,0 +1,23 @@
+/* { 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;
+}
+
+int src_neg (int t) {
+ return (t * -6) / 10;
+}
+
+unsigned int src_unsigned (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" 1 "optimized" } } */
--
2.43.0
