Simplify (t * (C + 1)) / C to t + t / C for signed and unsigned types
when the multiplication is known not to overflow. Unsigned division
by a power of two has already become a right shift when ranges are
available, so also simplify (t * (2^k + 1)) >> k to t + (t >> k) under
the same condition.
For exact_div only, also simplify (t * (C - 1)) / C to t - t / C. For
trunc_div the result is t - ceil (t / C), which differs unless C
divides t. exact_div cannot be produced from C source and the GIMPLE
front end cannot express it, so this case has no testcase.
Bootstrapped and regtested on x86_64-linux-gnu.
PR tree-optimization/126294
gcc/ChangeLog:
* match.pd: Simplify (t * (C + 1)) / C to t + t / C and, for
exact_div, (t * (C - 1)) / C to t - t / C, and
(t * (2^k + 1)) >> k to t + (t >> k), when the multiplication
does not overflow.
gcc/testsuite/ChangeLog:
* gcc.dg/tree-ssa/pr126294.c: New test.
Signed-off-by: Shivam Gupta <[email protected]>
---
gcc/match.pd | 48 ++++++++-
gcc/testsuite/gcc.dg/tree-ssa/pr126294.c | 129 +++++++++++++++++++++++
2 files changed, 176 insertions(+), 1 deletion(-)
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr126294.c
diff --git a/gcc/match.pd b/gcc/match.pd
index 1c0393d11..472551001 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -1141,8 +1141,31 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
(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))
- (mult @0 (div! @1 @2))))
+ (mult @0 (div! @1 @2))
)))
+ /* Otherwise simplify (t * (C + 1)) / C -> t + t / C, and for exact_div
+ only (t * (C - 1)) / C -> t - t / C. The latter is wrong for
+ trunc_div, where the result is t - ceil (t / C). */
+ (if (INTEGRAL_TYPE_P (type)
+ && (div == TRUNC_DIV_EXPR || div == EXACT_DIV_EXPR))
+ (with {
+ wide_int c1 = wi::to_wide (@1);
+ wide_int c2 = wi::to_wide (@2);
+ int_range_max vr0, vr1;
+ }
+ (if (wi::gts_p (c2, 0)
+ /* Avoid this transformation if c2 + 1 wraps, i.e. c2 is INT_MAX. */
+ && wi::gts_p (c1, 0)
+ && (c1 == c2 + 1
+ || (div == EXACT_DIV_EXPR && c1 == c2 - 1))
+ && gimple_match_range_of_expr (vr0, @0, @3)
+ && !vr0.varying_p ()
+ && gimple_match_range_of_expr (vr1, @1)
+ /* t * C1 doesn't overflow. */
+ && range_op_handler (MULT_EXPR).overflow_free_p (vr0, vr1))
+ (if (c1 == c2 + 1)
+ (plus @0 (div @0 @2))
+ (minus @0 (div @0 @2))))))))
#endif
/* Simplify (t * u) / (t * v) -> (u / v) if u is multiple of v. */
(simplify
@@ -1162,6 +1185,29 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
#endif
))))
+#if GIMPLE
+/* Simplify (t * (2^k + 1)) >> k -> t + (t >> k). Unsigned t / 2^k has
+ already become a shift when ranges are available, so the division
+ pattern above cannot see it. */
+(simplify
+ (rshift (mult@3 @0 INTEGER_CST@1) INTEGER_CST@2)
+ (if (INTEGRAL_TYPE_P (type)
+ /* Keep 2^k + 1 from wrapping, and reject bad shift counts. */
+ && wi::ltu_p (wi::to_wide (@2), TYPE_PRECISION (type) - 1))
+ (with {
+ wide_int d = wi::lshift (wi::one (TYPE_PRECISION (type)),
+ wi::to_wide (@2));
+ int_range_max vr0, vr1;
+ }
+ (if (wi::to_wide (@1) == d + 1
+ && gimple_match_range_of_expr (vr0, @0, @3)
+ && !vr0.varying_p ()
+ && gimple_match_range_of_expr (vr1, @1)
+ /* t * C1 doesn't overflow. */
+ && range_op_handler (MULT_EXPR).overflow_free_p (vr0, vr1))
+ (plus @0 (rshift @0 @2))))))
+#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/pr126294.c
b/gcc/testsuite/gcc.dg/tree-ssa/pr126294.c
new file mode 100644
index 000000000..f39be6700
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr126294.c
@@ -0,0 +1,129 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+/* { dg-require-effective-target int32plus } */
+
+/* (t * (C + 1)) / C -> t + t / C */
+unsigned
+plus_1 (unsigned short b)
+{
+ unsigned t = b;
+ return t * 7 / 6;
+}
+
+int
+signed_plus_1 (short b)
+{
+ int t = b;
+ return t * 11 / 10;
+}
+
+
+/* Known negative range */
+int
+signed_plus_neg (short b)
+{
+ int t = b;
+ if (t >= 0)
+ return 0;
+ return t * 25 / 24;
+}
+
+/* (t * (C - 1)) / C with trunc_div: no transform */
+unsigned
+minus_1 (unsigned short b)
+{
+ unsigned t = b;
+ return t * 12 / 13;
+}
+
+int
+signed_minus_1 (short b)
+{
+ int t = b;
+ return t * 16 / 17;
+}
+
+/* Known non-negative range */
+int
+signed_minus_nonneg (short b)
+{
+ int t = b;
+ if (t < 0)
+ return 0;
+ return t * 14 / 15;
+}
+
+/* Unknown range */
+int
+no_range_signed (int t)
+{
+ return t * 19 / 18;
+}
+
+unsigned
+no_range_unsigned (unsigned t)
+{
+ return t * 20 / 19;
+}
+
+/* Too wide range */
+unsigned
+overflow_range (unsigned t)
+{
+ if (t > 0x7fffffff)
+ return 0;
+ return t * 23 / 22;
+}
+
+/* Non-adjacent constants */
+unsigned
+no_transform (unsigned short b)
+{
+ unsigned t = b;
+ return t * 5 / 3;
+}
+
+/* Original PR reproducer: rshift form. */
+unsigned
+pr126294 (unsigned short b)
+{
+ unsigned t = b;
+ return t * 3 / 2;
+}
+
+/* Signed power-of-two divisor */
+int
+signed_pow2 (short b)
+{
+ int t = b;
+ return t * 9 / 8;
+}
+
+/* t * 33 may overflow, no transformation. */
+unsigned
+no_range_shift (unsigned t)
+{
+ return t * 33 / 32;
+}
+
+/* Transformed */
+/* { dg-final { scan-tree-dump-not "\\* 7;" "optimized" } } */
+/* { dg-final { scan-tree-dump " / 6;" "optimized" } } */
+/* { dg-final { scan-tree-dump-not "\\* 11;" "optimized" } } */
+/* { dg-final { scan-tree-dump " / 10;" "optimized" } } */
+/* { dg-final { scan-tree-dump-not "\\* 25;" "optimized" } } */
+/* { dg-final { scan-tree-dump " / 24;" "optimized" } } */
+/* { dg-final { scan-tree-dump-not "\\* 3;" "optimized" } } */
+/* { dg-final { scan-tree-dump " >> 1;" "optimized" } } */
+/* { dg-final { scan-tree-dump-not "\\* 9;" "optimized" } } */
+/* { dg-final { scan-tree-dump " / 8;" "optimized" } } */
+
+/* Not transformed */
+/* { dg-final { scan-tree-dump "\\* 12;" "optimized" } } */
+/* { dg-final { scan-tree-dump "\\* 16;" "optimized" } } */
+/* { dg-final { scan-tree-dump "\\* 14;" "optimized" } } */
+/* { dg-final { scan-tree-dump "\\* 19;" "optimized" } } */
+/* { dg-final { scan-tree-dump "\\* 20;" "optimized" } } */
+/* { dg-final { scan-tree-dump "\\* 23;" "optimized" } } */
+/* { dg-final { scan-tree-dump "\\* 5;" "optimized" } } */
+/* { dg-final { scan-tree-dump "\\* 33;" "optimized" } } */
--
2.43.0
