This was a fun one! An actual bug, and it took a while to sort out.
After chasing down some red herrings, this turns out to be an issue of
interaction between the range and value masks and intervening calculations.
The original patch from 11/2023 adjusts intersection so that it can
enhance subranges based on the value mask. ie in this testcase
[irange] int [-INF, 2147483644] MASK 0xfffffffc VALUE 0x1
If adjust_range() were called on this, it would eliminate the trailing
mask/value bit ranges that are invalid and turn it into :
[-INF, -3][1, 1][4, 2147483626] MASK 0xfffffffc VALUE 0x1
reflecting the lower bits into the range. The problem develops because
we only apply adjust_range () during intersection in an attempt to
avoid expensive work when it isnt needed.
Unfortunately, that is what triggers this infinite loop. Rangers cache
propagates changes, and the algorithm is designed to always improve the
range. In this case, the first iteration through, _11 receives the
above value, [irange] int [-INF, 2147483644] MASK 0xfffffffc VALUE 0x1
which via the mask, excludes 0, 2 and 3.
The ensuing calculations in block 7 do not trigger a successful
intersection operation, and thus the range pairs are never expanded to
eliminate the lower ranges, and it triggers another change in values
which leads to the next iteration being less precise, but not obviously
so. [irange] int [-INF, 2147483644] MASK 0xfffffffd VALUE 0x0 is a
result of the calculation. As ranges as suppose to always get better
with this algorithm, we simply compare for difference.. and this range
is different, and thus we replace it. It only excludes 2 and 3.
Next iteration through the less precise range DOES trigger an
intersection operation in block 7, and when that is expanded to [irange]
int [-INF, 1][4, 2147483644] MASK 0xfffffffd VALUE 0x0 using that we can
again create the more precise range for _11 that started the cycle. and
we go on and on and on.
If we fix this so that we always expand subranges to reflect the lower
bits in a bitmask, the initial value starts with
[irange] int [-INF, -3][1, 1][4, 2147483644] MASK 0xfffffffc VALUE 0x1
And everything falls into place as it should. The fix is to be
consistent about expanding those lower subranges.
I also added a couple of minor performance tweaks to avoid unnecessary
work, along with removing adjust_range () directly into
set_range_from_bitmask () .
I started at a 0.2% overall compilation increase (1.8% in VRP). In the
end, this patch is down to 0.6% in VRP, and only 0.08% overall, so
manageable for all the extra work.
It also causes a few ripples in the testsuite so 3 test cases also
needed adjustment:
* gcc.dg/pr83072-2.c : With the addition of the expanded ranges, CCP
use to export a global:
Global Exported: c_3 = [irange] int [-INF, +INF] MASK 0xfffffffe
VALUE 0x1
and now
Global Exported: c_3 = [irange] int [-INF, -1][1, +INF] MASK
0xfffffffe VALUE 0x1
Which in turn enables forwprop to collapse part of the testcase much
earlier. So I turned off forwprop for the testcase
* gcc.dg/tree-ssa/phi-opt-value-5.c : WIth the expanded ranges, CCP2
pass use to export:
Global Exported: d_3 = [irange] int [-INF, +INF] MASK 0xfffffffe
VALUE 0x1
and now
Global Exported: d_3 = [irange] int [-INF, -1][1, +INF] MASK
0xfffffffe VALUE 0x1
which in turn makes the following comment obsolete as the optimization
does happen earlier.:
/* fdiv1 requires until later than phiopt2 to be able to detect that
d is non-zero. to be able to remove the conditional. */
Adjusted the testcase to expect everything to be taken care of by
phi-opt2 pass.
* gcc.dg/tree-ssa/vrp122.c : Previously, CCP exported:
Global Exported: g_4 = [irange] unsigned int [0, +INF] MASK
0xfffffff0 VALUE 0x0
and then EVRP refined that and stored it, then the testcase tested for:
Global Exported: g_4 = [irange] unsigned int [0, 0][16, +INF] MASK
0xfffffff0 VALUE 0x0
Now, CCP itself exported the expanded range, so there is nothing for VRP
to do.
adjusted the testcase to look for the expanded range in CCP.
Now we never get into this situation where the bitmask is explicitly
applied in some places and not others.
Bootstraps on x86_64-pc-linux-gnu with no regressions. Finally. Is
this OK for trunk, or should I hold off a little bit?
Andrew
From 36e4b77565a1965d5bca15d196f32d5758393063 Mon Sep 17 00:00:00 2001
From: Andrew MacLeod <amacl...@redhat.com>
Date: Mon, 14 Apr 2025 16:25:15 -0400
Subject: [PATCH 3/3] Always reflect lower bits from mask in subranges.
During intersection, we expand the subranges to exclude the lower values
from a bitmask with trailing zeros. This leads to inconsistant evaluations
and in this case of this PR, that lead to an infinite cycle.
Always expand the lower subranges in set_range_from_bitmask instead.
PR tree-optimization/119712
gcc/
* value-range.cc (range_bitmask::adjust_range): Delete.
(irange::set_range_from_bitmask): Integrate adjust_range.
(irange::update_bitmask): Do nothing if bitmask doesnt change.
(irange:intersect_bitmask): Do not call adjust_range. Exit if there
is no second bitmask.
* value-range.h (adjust_range): Remove prototype.
gcc/testsuite/
* gcc.dg/pr119712.c: New.
* gcc.dg/pr83072-2.c: Adjust.
* gcc.dg/tree-ssa/phi-opt-value-5.c: Adjust.
* gcc.dg/tree-ssa/vrp122.c: Adjust
---
gcc/testsuite/gcc.dg/pr119712.c | 27 ++++++++
gcc/testsuite/gcc.dg/pr83072-2.c | 2 +-
.../gcc.dg/tree-ssa/phi-opt-value-5.c | 2 +-
gcc/testsuite/gcc.dg/tree-ssa/vrp122.c | 4 +-
gcc/value-range.cc | 64 +++++++++----------
gcc/value-range.h | 1 -
6 files changed, 61 insertions(+), 39 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/pr119712.c
diff --git a/gcc/testsuite/gcc.dg/pr119712.c b/gcc/testsuite/gcc.dg/pr119712.c
new file mode 100644
index 00000000000..e845dd9ce55
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr119712.c
@@ -0,0 +1,27 @@
+/* { dg-do compile } */
+/* { dg-options "-O2" } */
+int a, b, c, d, e, f;
+int main() {
+ f--;
+ goto q;
+j:
+ if (-1642776935 * c + 7 >= 0)
+ goto l;
+m:
+ if (4 * a - c - 21 >= 0)
+ goto i;
+ return 0;
+i:
+ if (d)
+ goto l;
+q:
+ c = 4 * c - 3;
+ if (c - f)
+ goto m;
+ goto j;
+l:
+ e = b + 1958960196 * c - 1016458303;
+ if (20 * e + 1 >= 0)
+ return 0;
+ goto j;
+}
diff --git a/gcc/testsuite/gcc.dg/pr83072-2.c b/gcc/testsuite/gcc.dg/pr83072-2.c
index dff6b50b717..485e8041381 100644
--- a/gcc/testsuite/gcc.dg/pr83072-2.c
+++ b/gcc/testsuite/gcc.dg/pr83072-2.c
@@ -1,5 +1,5 @@
/* { dg-do compile } */
-/* { dg-options "-O2 -fdump-tree-evrp-details" } */
+/* { dg-options "-O2 -fdump-tree-evrp-details -fno-tree-forwprop" } */
int f1(int a, int b, int c){
if(c==0)__builtin_unreachable();
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-value-5.c b/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-value-5.c
index 12ba475b24e..cb781774294 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-value-5.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-value-5.c
@@ -33,7 +33,7 @@ int fdiv1(int a, int b)
/* fdiv1 requires until later than phiopt2 to be able to detect that
d is non-zero. to be able to remove the conditional. */
-/* { dg-final { scan-tree-dump-times "goto" 2 "phiopt2" } } */
+/* { dg-final { scan-tree-dump-not "goto" "phiopt2" } } */
/* { dg-final { scan-tree-dump-not "goto" "phiopt3" } } */
/* { dg-final { scan-tree-dump-not "goto" "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp122.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp122.c
index 5a4ca850bee..def2b892bd6 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/vrp122.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp122.c
@@ -1,5 +1,5 @@
// { dg-do compile }
-// { dg-options "-O2 -fdump-tree-evrp-details" }
+// { dg-options "-O2 -fdump-tree-ccp1-details" }
void gg(void);
int f(unsigned t)
@@ -16,4 +16,4 @@ int f(unsigned t)
return 0;
}
-// { dg-final { scan-tree-dump "Global Exported: g_.* MASK 0x1 VALUE 0x0" "evrp" } }
+// { dg-final { scan-tree-dump "Global Exported: g_.*MASK.*0 VALUE 0x0" "ccp1" } }
diff --git a/gcc/value-range.cc b/gcc/value-range.cc
index 5136674b361..a770b41b474 100644
--- a/gcc/value-range.cc
+++ b/gcc/value-range.cc
@@ -2251,37 +2251,9 @@ irange::invert ()
verify_range ();
}
-// Remove trailing ranges that this bitmask indicates can't exist.
-
-void
-irange_bitmask::adjust_range (irange &r) const
-{
- if (unknown_p () || r.undefined_p ())
- return;
-
- int_range_max range;
- tree type = r.type ();
- int prec = TYPE_PRECISION (type);
- // If there are trailing zeros, create a range representing those bits.
- gcc_checking_assert (m_mask != 0);
- int z = wi::ctz (m_mask);
- if (z)
- {
- wide_int ub = (wi::one (prec) << z) - 1;
- range = int_range<5> (type, wi::zero (prec), ub);
- // Then remove the specific value these bits contain from the range.
- wide_int value = m_value & ub;
- range.intersect (int_range<2> (type, value, value, VR_ANTI_RANGE));
- // Inverting produces a list of ranges which can be valid.
- range.invert ();
- // And finally select R from only those valid values.
- r.intersect (range);
- return;
- }
-}
-
-// If the mask can be trivially converted to a range, do so and
-// return TRUE.
+// 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.
bool
irange::set_range_from_bitmask ()
@@ -2326,7 +2298,28 @@ irange::set_range_from_bitmask ()
set_zero (type ());
return true;
}
- return false;
+
+ // If the mask doesn't have any trailing zero, return.
+ int z = wi::ctz (m_bitmask.mask ());
+ if (!z)
+ return false;
+
+ // Remove trailing ranges that this bitmask indicates can't exist.
+ int_range_max mask_range;
+ int prec = TYPE_PRECISION (type ());
+ wide_int ub = (wi::one (prec) << z) - 1;
+ mask_range = int_range<2> (type (), wi::zero (prec), ub);
+
+ // Then remove the specific value these bits contain from the range.
+ wide_int value = m_bitmask.value () & ub;
+ mask_range.intersect (int_range<2> (type (), value, value, VR_ANTI_RANGE));
+
+ // Inverting produces a list of ranges which can be valid.
+ mask_range.invert ();
+
+ // And finally select R from only those valid values.
+ intersect (mask_range);
+ return true;
}
void
@@ -2334,6 +2327,10 @@ irange::update_bitmask (const irange_bitmask &bm)
{
gcc_checking_assert (!undefined_p ());
+ // If masks are the same, there is no change.
+ if (m_bitmask == bm)
+ return;
+
// Drop VARYINGs with known bits to a plain range.
if (m_kind == VR_VARYING && !bm.unknown_p ())
m_kind = VR_RANGE;
@@ -2408,7 +2405,7 @@ irange::intersect_bitmask (const irange &r)
{
gcc_checking_assert (!undefined_p () && !r.undefined_p ());
- if (m_bitmask == r.m_bitmask)
+ if (r.m_bitmask.unknown_p () || m_bitmask == r.m_bitmask)
return false;
irange_bitmask bm = get_bitmask ();
@@ -2427,7 +2424,6 @@ irange::intersect_bitmask (const irange &r)
if (!set_range_from_bitmask ())
normalize_kind ();
- m_bitmask.adjust_range (*this);
if (flag_checking)
verify_range ();
return true;
diff --git a/gcc/value-range.h b/gcc/value-range.h
index b50cb896340..f6942989a6f 100644
--- a/gcc/value-range.h
+++ b/gcc/value-range.h
@@ -149,7 +149,6 @@ public:
void dump (FILE *) const;
bool member_p (const wide_int &val) const;
- void adjust_range (irange &r) const;
// Convenience functions for nonzero bitmask compatibility.
wide_int get_nonzero_bits () const;
--
2.45.0
