I wasn't checking the underflow and overflow conditions well enough in
the original patch for range bound snapping. THe testcxsed in this PR
has a [+INF, +INF] subrange with a bitmask that said it must be an even
value.
The lower bound calculation overflowed (+INF + 1}, but it was not
detected, so a new subrange of [-INF, +INF - 1] was created in its place.
Suprisingly, irange::verify_range was confirming that each subrange has
LB <= UB, but it never checked if the UB of the previous pair was less
than the LB of the current pair. Very surprising or it would have
triggered an obvious trap. INstead, it took quite some time to track
it down as it wasnt triggering a trap until much later when a range was
being loaded from memory.
Regardless, this patch fixes the overflow/underflow issue, and adds
verification that the subrange pairs are also sorted to verify_range.
I also made some minor comment adjustments Aldy pointed out earlier.
Bootstraps on x86_64-pc-linux-gnu with no regressions. Pushed.
Andrew
From b03e0d69b37f6ea7aef220652635031a89f56a11 Mon Sep 17 00:00:00 2001
From: Andrew MacLeod <amacl...@redhat.com>
Date: Fri, 20 Jun 2025 08:50:39 -0400
Subject: [PATCH] Fix range wrap check and enhance verify_range.
when snapping range bounds to satidsdaybitmask constraints, end bound overflow
and underflow checks were not working properly.
Also Adjust some comments, and enhance verify_range to make sure range pairs
are sorted properly.
PR tree-optimization/120701
gcc/
* value-range.cc (irange::verify_range): Verify range pairs are
sorted properly.
(irange::snap): Check for over/underflow properly.
gcc/testsuite/
* gcc.dg/pr120701.c: New.
---
gcc/testsuite/gcc.dg/pr120701.c | 40 +++++++++++++++++++++++++++++++++
gcc/value-range.cc | 38 +++++++++++++++++--------------
2 files changed, 61 insertions(+), 17 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/pr120701.c
diff --git a/gcc/testsuite/gcc.dg/pr120701.c b/gcc/testsuite/gcc.dg/pr120701.c
new file mode 100644
index 00000000000..09f7b6192ed
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr120701.c
@@ -0,0 +1,40 @@
+/* { dg-do compile } */
+/* { dg-options "-O2" } */
+
+int a, b, c, e, f;
+int main() {
+ int d, g, i;
+j:
+ if (d >= 0)
+ goto k;
+ if (g >= 0)
+ goto l;
+k:
+ i = a + 3;
+m:
+ f = 652685095 + 818172564 * g;
+ if (-1101344938 * f - 1654872807 * d >= 0)
+ goto n;
+ goto l;
+o:
+ if (i) {
+ c = -b;
+ if (-c >= 0)
+ goto l;
+ g = b;
+ b = i + 5;
+ if (b * c)
+ goto n;
+ goto o;
+ }
+ if (e)
+ goto m;
+ goto j;
+n:
+ d = 978208086 * g - 1963072513;
+ if (d + i)
+ return 0;
+ goto k;
+l:
+ goto o;
+}
diff --git a/gcc/value-range.cc b/gcc/value-range.cc
index 0f0770ad705..ce13acc312d 100644
--- a/gcc/value-range.cc
+++ b/gcc/value-range.cc
@@ -1552,6 +1552,11 @@ irange::verify_range ()
gcc_checking_assert (ub.get_precision () == prec);
int c = wi::cmp (lb, ub, TYPE_SIGN (m_type));
gcc_checking_assert (c == 0 || c == -1);
+ // Previous UB should be lower than LB
+ if (i > 0)
+ gcc_checking_assert (wi::lt_p (upper_bound (i - 1),
+ lb,
+ TYPE_SIGN (m_type)));
}
m_bitmask.verify_mask ();
}
@@ -1628,7 +1633,7 @@ irange::contains_p (const wide_int &cst) const
if (undefined_p ())
return false;
- // Check is the known bits in bitmask exclude CST.
+ // Check if the known bits in bitmask exclude CST.
if (!m_bitmask.member_p (cst))
return false;
@@ -2269,7 +2274,7 @@ irange::invert ()
// This routine will take the bounds [LB, UB], and apply the bitmask to those
// values such that both bounds satisfy the bitmask. TRUE is returned
-// if either bound changes, and they are retuirned as [NEW_LB, NEW_UB].
+// if either bound changes, and they are returned as [NEW_LB, NEW_UB].
// if NEW_UB < NEW_LB, then the entire bound is to be removed as none of
// the values are valid.
// ie, [4, 14] MASK 0xFFFE VALUE 0x1
@@ -2285,30 +2290,29 @@ irange::snap (const wide_int &lb, const wide_int &ub,
uint z = wi::ctz (m_bitmask.mask ());
if (z == 0)
return false;
- const wide_int &wild_mask = m_bitmask.mask ();
const wide_int step = (wi::one (TYPE_PRECISION (type ())) << z);
const wide_int match_mask = step - 1;
const wide_int value = m_bitmask.value () & match_mask;
- wide_int rem_lb = lb & match_mask;
-
- wi::overflow_type ov_sub;
- wide_int diff = wi::sub(value, rem_lb, UNSIGNED, &ov_sub);
- wide_int offset = diff & match_mask;
+ bool ovf = false;
- wi::overflow_type ov1;
- new_lb = wi::add (lb, offset, UNSIGNED, &ov1);
+ wide_int rem_lb = lb & match_mask;
+ wide_int offset = (value - rem_lb) & match_mask;
+ new_lb = lb + offset;
+ // Check for overflows at +INF
+ if (wi::lt_p (new_lb, lb, TYPE_SIGN (type ())))
+ ovf = true;
wide_int rem_ub = ub & match_mask;
wide_int offset_ub = (rem_ub - value) & match_mask;
-
- wi::overflow_type ov2;
- new_ub = wi::sub (ub, offset_ub, UNSIGNED, &ov2);
+ new_ub = ub - offset_ub;
+ // Check for underflows at -INF
+ if (wi::gt_p (new_ub, ub, TYPE_SIGN (type ())))
+ ovf = true;
// Overflow or inverted range = invalid
- if (ov1 != wi::OVF_NONE || ov2 != wi::OVF_NONE
- || wi::lt_p (new_ub, new_lb, TYPE_SIGN (type ())))
+ if (ovf || wi::lt_p (new_ub, new_lb, TYPE_SIGN (type ())))
{
new_lb = wi::one (lb.get_precision ());
new_ub = wi::zero (ub.get_precision ());
@@ -2454,7 +2458,7 @@ irange::set_range_from_bitmask ()
// Make sure we call intersect, so do it first.
changed = intersect (mask_range) | changed;
- // Npw make sure each subrange endpoint matches the bitmask.
+ // Now make sure each subrange endpoint matches the bitmask.
changed |= snap_subranges ();
return changed;
@@ -2548,7 +2552,7 @@ irange::intersect_bitmask (const irange &r)
irange_bitmask bm = get_bitmask ();
irange_bitmask save = bm;
bm.intersect (r.get_bitmask ());
- // Use ths opportunity to make sure mask reflects always reflects the
+ // Use ths opportunity to make sure mask always reflects the
// best mask we have.
m_bitmask = bm;
--
2.45.0
