This also fixes PR 121468 and PR 122200.
There were some unfortunate interactions with adjusting range bounds to
match the bitmask. With bitmasks being set lazily, and the bounds
being adjusted only during intersection operations, we were sometimes
getting ranges which should have been undefined, but continued to exist
with bounds and a bitmask that invalidated them.
This patch cleans things up a bit, and hopefully prevents more such PRs .
1 - The original bounds snapping routine tried to return invalid ranges
by setting UB < LB. This turns out to be a problem with with single bit
signed ranges (:-p). Instead, this routine now explcitly sets an
overflow flag to indicate the entire sub range is invalid.
2 - When a bitmask is set, the upper and lower bounds are immediately
snapped to conform with the bitmask before any additional steps are
taken. This sometimes results in an UNDEFINED value before any
additional processing takes place.
3 - Valid ranges for a bitmask are now computed by the bitmask class,
and then the bitmask_intersect method range intersects the current range
directly with that range. Previously it tried to adjust the current
range on the fly based on what whether the existing bounds fit or not.
4 - subrange bounds snapping (processing each individual subrange)
continues to be performed only on bitmasks with trialing zeros in the
mask. I am working on a general solution that works for all bitmasks,
but rather than holding up the patch which is causing compilation
hangs, I decided to leave this as is for the moment while I investigate
possible solutions.
5 - range snapping also was enhanced to produce specific ranges for 0, 1
or 2 bits set in the the mask. (ie, 1, 2 or 4 individual value
subranges) rather than allowing large ranges with small bitmask
possibilities. I considered adding the case for 3 bits (8 ranges), but
at this point left that undone.
The patch also required some adjustments to the selftests for
bitmasks. There were self tests which assuming that taking VARYING,
applying a mask, then unapplying the mask would result in VARYING
again. Once we trim out ranges, we don't add them back because the
bitmask was later relaxed. I do not believe that behaviour was expected
anywhere else, and consider that to be incorrect selftests. Other tests
required adjusting the expected results to be finer grained.
We are doing a lot more bound adjustment with bitmasks as a result. I
added a a short circuit to avoid doing the work if it wasn't needed, but
we still take a 3% hit to VRP. overall compilation time is <0.4%.
Given that this (hopefully) results in a significantly more robust
bitmask interaction, I consider that acceptable for the moment. As I
continue to look into the more general snapping mechanism, I will look
for addition ways to speed this up.
Hopefully this resolves a class of issues and doesn't cause more :-)
Bootstrapped on x86_64-pc-linux-gnu with no regressions. Pushed.
Andrew
From 9e04a43012be504b75217704124987d0510f7fdc Mon Sep 17 00:00:00 2001
From: Andrew MacLeod <[email protected]>
Date: Tue, 7 Oct 2025 11:56:08 -0400
Subject: [PATCH] Range snap bitmasks as they are set.
Range bounds adjustments based on a bitmask were lazily set. This lead
to some inconsitencies which were causing problems. Improve the bounds,
and do it every time the bitmask is adjusted.
PR tree-optimization/121468
PR tree-optimization/121206
PR tree-optimization/122200
gcc/
* value-range.cc (irange_bitmask::range_from_mask): New.
(irange::snap): Add explicit overflow flag.
(irange::snap_subranges): Use overflow flag.
(irange::set_range_from_bitmask): Use range_from_mask.
(test_irange_snap_bounds): Adjust for improved ranges.
* value-range.h (irange::range_from_mask): Add prototype.
(irange::snap): Adjust prototype.
gcc/testsuite/
* gcc.dg/pr121468.c: New.
* gcc.dg/pr122200.c: New.
---
gcc/testsuite/gcc.dg/pr121468.c | 30 ++++
gcc/testsuite/gcc.dg/pr122200.c | 23 +++
gcc/value-range.cc | 258 ++++++++++++++++----------------
gcc/value-range.h | 4 +-
4 files changed, 185 insertions(+), 130 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/pr121468.c
create mode 100644 gcc/testsuite/gcc.dg/pr122200.c
diff --git a/gcc/testsuite/gcc.dg/pr121468.c b/gcc/testsuite/gcc.dg/pr121468.c
new file mode 100644
index 00000000000..07df274be83
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr121468.c
@@ -0,0 +1,30 @@
+/* { dg-do compile } */
+/* { dg-options "-Os" } */
+int e, f, n;
+static int a () { return e; }
+void b () { while (a()); }
+static int d () { return e; }
+static void g (int h) {
+ if (e)
+ c:
+ if (d())
+ goto i;
+ do {
+ if (f)
+ goto c;
+ goto k;
+ i:
+ h = 2147483647;
+ k:
+ e = 2147483646;
+ e = 6 + e;
+ do {
+ b ();
+ } while (1784828957 / f + e + (808 + h) > 0);
+ } while (1 % h);
+}
+void m () { g (-2); }
+int main () {
+ if (n)
+ g (-1);
+}
diff --git a/gcc/testsuite/gcc.dg/pr122200.c b/gcc/testsuite/gcc.dg/pr122200.c
new file mode 100644
index 00000000000..cd770fcaaf2
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr122200.c
@@ -0,0 +1,23 @@
+/* { dg-do compile } */
+/* { dg-options "-O3" } */
+/* { dg-additional-options "-mavx" { target { x86_64-*-* i?86-*-* } } } */
+
+
+int a, b;
+
+void f(float g[][5]) {
+ int c;
+
+ for (c = 0; c != a; c++)
+ g[1][c] = c;
+
+ for (int d; d; d++)
+ for (int e = 1; e != b; e++) {
+ for (c = 0; c != a; c++) {
+ g[0][1] = 1;
+
+ if (g[1][c])
+ g[1][c] = 1;
+ }
+ }
+}
diff --git a/gcc/value-range.cc b/gcc/value-range.cc
index d34a2623db4..f93a7e5c53a 100644
--- a/gcc/value-range.cc
+++ b/gcc/value-range.cc
@@ -55,6 +55,93 @@ irange_bitmask::irange_bitmask (tree type,
}
}
+// Return a range in R of TYPE for this bitmask which encompasses
+// a set of valid values which are allowable for this bitmask/value
+// combination. If false is returned, no range was set.
+
+bool
+irange_bitmask::range_from_mask (irange &r, tree type) const
+{
+ if (unknown_p ())
+ return false;
+
+ gcc_checking_assert ((value () & mask ()) == 0);
+ unsigned popcount = wi::popcount (mask ());
+
+ // For 0, 1 or 2 bits set, create a range with only the allowed values.
+ if (popcount <= 2)
+ {
+ // VALUE is always a valid range.
+ r.set (type, value (), value ());
+ // If there are bits in mask, (VALUE | MASK) is also valid.
+ if (popcount >= 1)
+ r.union_ (int_range<1> (type, value () | mask (), value () | mask ()));
+ // If there are 2 bits set, add the other 2 possible values.
+ if (popcount == 2)
+ {
+ // Extract the two 1-bit masks into lb and ub.
+ wide_int lb = mask () & -mask (); // Lowest set bit.
+ wide_int ub = mask () & (mask () - 1); // The other bit.
+ r.union_ (int_range<1> (type, value () | lb, value () | lb));
+ r.union_ (int_range<1> (type, value () | ub, value () | ub));
+ }
+ return true;
+ }
+
+ // Otherwise, calculate the valid range allowed by the bitmask.
+ int prec = TYPE_PRECISION (type);
+ wide_int ub = mask () | value ();
+ wide_int sign_bit = wi::one (prec) << (prec - 1);
+ wide_int sign_mask = mask () & sign_bit;
+ wide_int sign_value = value () & sign_bit;
+ // Create a lower and upper bound.
+ // If unsigned, or the sign is known to be positive, create [lb, ub]
+ if (TYPE_SIGN (type) == UNSIGNED || (sign_mask == 0 && sign_value == 0))
+ r.set (type, value (), mask () | value ());
+ // If the sign bit is KNOWN to be 1, we have a completely negative range.
+ else if (sign_mask == 0 && sign_value != 0)
+ r.set (type, value (), value () | (mask () & ~sign_bit));
+ else
+ {
+ // Otherwise there are 2 ranges, a negative and positive interval.
+ wide_int neg_base = value () | sign_bit;
+ wide_int pos_mask = mask () & ~sign_bit;
+ r.set (type, neg_base , neg_base | pos_mask);
+ r.union_ (int_range<1> (type, value (), value () | pos_mask));
+ }
+
+ // If the mask doesn't have a trailing zero, there is nothing else to filter.
+ int z = wi::ctz (mask ());
+ if (z == 0)
+ return true;
+
+ // Remove the [0, X] values which the trailing-zero mask rules out.
+ // For example, if z == 4, the mask is 0xFFF0, and the lowest 4 bits
+ // define the range [0, 15]. Only (value & low_mask) is allowed.
+ ub = (wi::one (prec) << z) - 1; // Upper bound of range.
+ int_range<4> mask_range (type, wi::zero (prec), ub);
+ // Remove the valid value from the excluded range and form an anti-range.
+ wide_int allow = value () & ub;
+ mask_range.intersect (int_range<2> (type, allow, allow, VR_ANTI_RANGE));
+ mask_range.invert ();
+ r.intersect (mask_range);
+
+ if (TYPE_SIGN (type) == SIGNED)
+ {
+ // For signed negative values, find the lowest value with trailing zeros.
+ // This forms a range such as [-512, -1] for z=9.
+ wide_int lb = -(wi::one (prec) << z);
+ int_range<4> mask_range (type, lb, wi::minus_one (prec));
+ // Remove the one allowed value from that set.
+ wide_int allow = value () | lb;
+ mask_range.intersect (int_range<2> (type, allow, allow, VR_ANTI_RANGE));
+ mask_range.invert ();
+ r.intersect (mask_range);
+ }
+ return true;
+}
+
+
void
irange::accept (const vrange_visitor &v) const
{
@@ -2275,47 +2362,57 @@ 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 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.
+// If there is an overflow, or if (NEW_UB < NEW_LB), then the entire bound is
+// to be removed as none of the values are valid. This is indicated by
+// teturning TRUE in OVF. False indicates the bounds are fine.
// ie, [4, 14] MASK 0xFFFE VALUE 0x1
-// means all values must be odd, the new bounds returned will be [5, 13].
+// means all values must be odd, the new bounds returned will be [5, 13] with
+// OVF set to FALSE.
// ie, [4, 4] MASK 0xFFFE VALUE 0x1
-// would return [1, 0] and as the LB < UB, the entire subrange is invalid
-// and should be removed.
+// would return TRUE and OVF == TRUE. The entire subrange should be removed.
bool
irange::snap (const wide_int &lb, const wide_int &ub,
- wide_int &new_lb, wide_int &new_ub)
+ wide_int &new_lb, wide_int &new_ub, bool &ovf)
{
+ ovf = false;
int z = wi::ctz (m_bitmask.mask ());
if (z == 0)
return false;
+ // Shortcircuit check for values that are already good.
+ if ((((lb ^ m_bitmask.value ()) | (ub ^ m_bitmask.value ()))
+ & ~m_bitmask.mask ()) == 0)
+ return false;
+
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;
- bool ovf = false;
-
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;
+ {
+ ovf = true;
+ return true;
+ }
wide_int rem_ub = ub & match_mask;
wide_int offset_ub = (rem_ub - value) & match_mask;
new_ub = ub - offset_ub;
// Check for underflows at -INF
if (wi::gt_p (new_ub, ub, TYPE_SIGN (type ())))
- ovf = true;
+ {
+ ovf = true;
+ return true;
+ }
- // Overflow or inverted range = invalid
- if (ovf || wi::lt_p (new_ub, new_lb, TYPE_SIGN (type ())))
+ // If inverted range is invalid, set overflow to TRUE.
+ if (wi::lt_p (new_ub, new_lb, TYPE_SIGN (type ())))
{
- new_lb = wi::one (lb.get_precision ());
- new_ub = wi::zero (ub.get_precision ());
+ ovf = true;
return true;
}
return (new_lb != lb) || (new_ub != ub);
@@ -2334,11 +2431,12 @@ irange::snap_subranges ()
wide_int lb, ub;
for (x = 0; x < m_num_ranges; x++)
{
- if (snap (lower_bound (x), upper_bound (x), lb, ub))
+ bool ovf;
+ if (snap (lower_bound (x), upper_bound (x), lb, ub, ovf))
{
changed = true;
- // This subrange is to be completely removed.
- if (wi::lt_p (ub, lb, TYPE_SIGN (type ())))
+ // Check if this subrange is to be completely removed.
+ if (ovf)
{
int_range<1> tmp (type (), lower_bound (x), upper_bound (x));
invalid.union_ (tmp);
@@ -2359,109 +2457,25 @@ irange::snap_subranges ()
return changed;
}
-// If the mask can be trivially converted to a range, do so.
-// Otherwise attempt to remove the lower bits from the range.
-// Return true if the range changed in any way.
+// If the bitmask has a range representation, intersect this range with
+// the bitmasks range. Then ensure all enpoints match the bitmask.
+// Return TRUE if the range changes at all.
bool
irange::set_range_from_bitmask ()
{
gcc_checking_assert (!undefined_p ());
- if (m_bitmask.unknown_p ())
- return false;
-
- // If all the bits are known, this is a singleton.
- if (m_bitmask.mask () == 0)
- {
- // Make sure the singleton is within the range.
- if (contains_p (m_bitmask.value ()))
- set (m_type, m_bitmask.value (), m_bitmask.value ());
- else
- set_undefined ();
- return true;
- }
-
- unsigned popcount = wi::popcount (m_bitmask.get_nonzero_bits ());
-
- // If we have only one bit set in the mask, we can figure out the
- // range immediately.
- if (popcount == 1)
- {
- // Make sure we don't pessimize the range.
- if (!contains_p (m_bitmask.get_nonzero_bits ()))
- return false;
-
- bool has_zero = contains_zero_p (*this);
- wide_int nz = m_bitmask.get_nonzero_bits ();
- set (m_type, nz, nz);
- m_bitmask.set_nonzero_bits (nz);
- if (has_zero)
- {
- int_range<2> zero;
- zero.set_zero (m_type);
- union_ (zero);
- }
- if (flag_checking)
- verify_range ();
- return true;
- }
- else if (popcount == 0)
- {
- set_zero (m_type);
- return true;
- }
+ // Snap subranmges when bitmask is first set.
+ snap_subranges ();
+ if (undefined_p ())
+ return true;
- // If the mask doesn't have a trailing zero, theres nothing to filter.
- int z = wi::ctz (m_bitmask.mask ());
- if (!z)
+ // Calculate the set of ranges valid for the bitmask.
+ int_range_max allow;
+ if (!m_bitmask.range_from_mask (allow, m_type))
return false;
-
- int prec = TYPE_PRECISION (m_type);
- wide_int value = m_bitmask.value ();
- wide_int mask = m_bitmask.mask ();
-
- // Remove the [0, X] values which the trailing-zero mask rules out.
- // For example, if z == 4, the mask is 0xFFF0, and the lowest 4 bits
- // define the range [0, 15]. Only one of which (value & low_mask) is allowed.
- wide_int ub = (wi::one (prec) << z) - 1; // Upper bound of affected range.
- int_range_max mask_range (m_type, wi::zero (prec), ub);
-
- // Remove the one valid value from the excluded range and form an anti-range.
- wide_int allow = value & ub;
- mask_range.intersect (int_range<2> (m_type, allow, allow, VR_ANTI_RANGE));
-
- // Invert it to get the allowed values and intersect it with the main range.
- mask_range.invert ();
- bool changed = intersect (mask_range);
-
- // Now handle the rest of the domain — the upper side for positive values,
- // or [-X, -1] for signed negatives.
- // Compute the maximum value representable under the mask/value constraint.
- ub = mask | value;
-
- // If value is non-negative, adjust the upper limit to remove values above
- // UB that conflict with known fixed bits.
- if (TYPE_SIGN (m_type) == UNSIGNED || wi::clz (ub) > 0)
- mask_range = int_range<1> (m_type, wi::zero (prec), ub);
- else
- {
- // For signed negative values, find the lowest value with trailing zeros.
- // This forms a range such as [-512, -1] for z=9.
- wide_int lb = -(wi::one (prec) << z);
- mask_range = int_range<2> (m_type, lb, wi::minus_one (prec));
-
- // Remove the one allowed value from that set.
- allow = value | lb;
- mask_range.intersect (int_range<2> (m_type, allow, allow, VR_ANTI_RANGE));
- mask_range.invert ();
- }
-
- // Make sure we call intersect, so do it first.
- changed = intersect (mask_range) | changed;
- // Now make sure each subrange endpoint matches the bitmask.
- changed |= snap_subranges ();
-
- return changed;
+ // And intersect that set of ranges with the current set.
+ return intersect (allow);
}
void
@@ -2932,7 +2946,7 @@ test_irange_snap_bounds ()
tree u1 = build_nonstandard_integer_type (1, /*unsigned=*/ 1);
// Basic aligned range: even-only
- assert_snap_result (5, 15, 6, 14, 0xFFFFFFFE, 0x0, u32);
+ assert_snap_result (5, 15, 6, 14, 0xE, 0x0, u32);
// Singleton that doesn't match mask: undefined.
assert_snap_result (7, 7, 1, 0, 0xFFFFFFFE, 0x0, u32);
// 8-bit signed char, mask 0xF0 (i.e. step of 16).
@@ -3204,15 +3218,12 @@ range_tests_misc ()
static void
range_tests_nonzero_bits ()
{
- int_range<2> r0, r1;
+ int_range<8> r0, r1;
// Adding nonzero bits to a varying drops the varying.
r0.set_varying (integer_type_node);
r0.set_nonzero_bits (INT (255));
ASSERT_TRUE (!r0.varying_p ());
- // Dropping the nonzero bits brings us back to varying.
- r0.set_nonzero_bits (INT (-1));
- ASSERT_TRUE (r0.varying_p ());
// Test contains_p with nonzero bits.
r0.set_zero (integer_type_node);
@@ -3244,17 +3255,6 @@ range_tests_nonzero_bits ()
r0.intersect (r1);
ASSERT_TRUE (r0.get_nonzero_bits () == 0xff);
- // The union of a mask of 0xff..ffff00 with a mask of 0xff spans the
- // entire domain, and makes the range a varying.
- r0.set_varying (integer_type_node);
- wide_int x = wi::shwi (0xff, TYPE_PRECISION (integer_type_node));
- x = wi::bit_not (x);
- r0.set_nonzero_bits (x); // 0xff..ff00
- r1.set_varying (integer_type_node);
- r1.set_nonzero_bits (INT (0xff));
- r0.union_ (r1);
- ASSERT_TRUE (r0.varying_p ());
-
// Test that setting a nonzero bit of 1 does not pessimize the range.
r0.set_zero (integer_type_node);
r0.set_nonzero_bits (INT (1));
diff --git a/gcc/value-range.h b/gcc/value-range.h
index 3bc02db43a5..6ae46e17959 100644
--- a/gcc/value-range.h
+++ b/gcc/value-range.h
@@ -150,6 +150,7 @@ public:
bool operator!= (const irange_bitmask &src) const { return !(*this == src); }
void verify_mask () const;
void dump (FILE *) const;
+ bool range_from_mask (irange &r, tree type) const;
bool member_p (const wide_int &val) const;
@@ -346,7 +347,8 @@ private:
bool union_bitmask (const irange &r);
bool set_range_from_bitmask ();
bool snap_subranges ();
- bool snap (const wide_int &, const wide_int &, wide_int &, wide_int &);
+ bool snap (const wide_int &, const wide_int &, wide_int &, wide_int &,
+ bool &);
bool intersect (const wide_int& lb, const wide_int& ub);
bool union_append (const irange &r);
--
2.45.0
