On 9/19/26 3:47 AM, Shivam Gupta wrote:
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 ()
That call is probably worth a comment. Guessing you're trying to guard
against the overflow_free test always returning true for signed types?
+#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))
You're checking < precision - 1. Should this be < precision? At first
glance that seems more correct to me, but maybe I'm missing something.
Otherwise it looks pretty good. Just want to close on the motivation
(and likely missing comment) on the first issue and whether or not we've
got an off-by-one error with the second issue.
jeff
