On 11/26/25 03:33, Richard Biener wrote:
On Tue, Nov 25, 2025 at 8:54 PM Andrew MacLeod <[email protected]> wrote:
When bitmasks were added to value-range, they were also added to
operator==. we never added the ability to compare just the ranges and
ignore the bitmask. There have been a couple of times that would have
been convenient, but never really had a serious need.
This patch adds equal_p () which also takes a flag indicating whether to
include bitmasks in the comparison. And the first consumer is the
on-entry cache propagator.
We've had a number of cases over the past few months which generate
oscillating patterns in rangers cache propogator. I fixed most of them
by ensuring all the subrange bounds conformed to the bitmask.. this
prevented stray values that were not relevant from causing this sort of
oscillation. This case is slightly different.
There is no canonical representation of bitmasks. Multiple bitmasks can
represent the same thing..
How's that? It isn't immediately obvious to me.
in this particular case, we have the cache
containing
[irange] sizetype [12, 12][20, 20][28, 28] MASK 0x18 VALUE 0x4
So here the mask says bit 0x10 has value 0, bit 0x8 has value 0 as well.
Why is VALUE not 0x0? It seems 'value' lacks canonicalization by
& mask?
What I mean is both those masks are valid for the range specified. we
make sure the range bounds fit the mask, but we make no attempt to
ensure the mask is "minimal" for the range.. that could be a very
expensive operation.
[irange] sizetype [12, 12][20, 20][28, 28] MASK 0x18 VALUE 0x4
that mask and value allows exactly 4 values.. [4, 4] [12, 12] [20, 20]
[28, 28] so it applies to the specified range. The 0x4 in value
indicates that we know 0x100 is set
[irange] sizetype [12, 12][20, 20][28, 28] MASK 0x1c VALUE 0x0
is slightly less restrictive, allowing multiple of 4 < 32, so [0,0] [4,
4][8, 8][12, 12][16, 16][20, 20], [24, 24][28, 28] it doesn't force
the 0x100 bit to be 1, but rather allows it to be 0 or 1. thus twice
the eligible ranges.
Both masks are valid for this range, which is what I meant by no
canonical representation. I do not think we can afford to examine the
range and determine a *minimal* canonical value for the bitmask. this
is a very small case, if the mask allowed some of the upper bits to be
variable as well, I think its prohibitive to figure out a "minimal" bitmask.
and when we calculate an ew on-entry range, the incoming edges are
unioned together and value_range::union_ decided to produce:
[irange] sizetype [12, 12][20, 20][28, 28] MASK 0x1c VALUE 0x0
This has on bit more set in MASK, bit 0x4, at value 0x0. That looks
either "wrong" or the range side is overly pessimistic, it should have
dropped [28, 28] here? Or do we not even try to prune ranges by
the bitmask? Or the other way around?
we prune range bounds by bitmask, but we do not prune bitmasks by range.
This example is not wrong, it simply eliminates any ranges where a 0
bit occurs in bit 2.. so, 0, 8, 16, and 24. [28,28] is allowed by
0x1c. .
Is there a single place somewhere in the ranger code that implements
the range<->bitmask "interaction"? Can you point me to that?
It seems that the iteration process, even if we (as it seems) treat
the range and the bitmask part separately, does not ensure ranges
and bitmasks either only grow or shrink.
The iteration process always ensures a range improves, as long as
intersect method never makes a range larger.
I traced The problem being encountered to what we do when 2 incompatible
bitmasks are encountered. bb188 has an incoming/exit range for _1740 of
[irange] sizetype [12, 12][20, 20][28, 28] MASK 0x1c VALUE 0x4
The outgoing edge has some complexity, and GORI reports the edge is
restricted to [irange] sizetype [16, 17179869168][17179869184,
17179869184] MASK 0x7fffffff0 VALUE 0x0
intersection is performed in 2 stages.. First the range is intersected,
and then we intersect the bitmask structure. Range intersection
returns [20,20][28,28], but the problem comes with the bitmasks. The
First bitmask requires a 1 in bit 2 position (multiples of 4), the other
(outgoing edge range) requires a 0 in that bit. the bitmask
intersection routine recognizes this incompatible bit situation, and
currently gives up as there is no way to represent UNDEFINED. Instead
it bails and returns "unknown" which is technically varying. This
breaks the "intersection never making a range larger" rule, and is the
root of this problem.
We could change the range itself to UNDEFINED in this circumstance. The
question is "does one incompatible bit in the bitmask" make the entire
range UNDEFINED? perhaps. Maybe that is the correct course of action,
I *think* it is always correct, but it was unclear to the original
authors as well according to the comments. If you project it out,
[0,255] mask xFE value 0 intersect [0,255] mask xFE value 1
has to be undefined. If we had infinite sub ranges, it would be
represented as all evens intersect all odds... and thus undefined. So
I guess it makes sense.
I've attached a patch which changes the irange_bitmask::intersect
routine to return FALSE if the result has undefined bits, and then the
callers can change their range to UNDEFINED. (The callers being
irange::intersect and prange::intersect mostly, not users).
It causes the testcase to finish, and it also bootstraps on
x86_64-pc-linux-gnu with no regressions.
Im good with this instead. OK?
Andrew
From 178e11d0d7d4bdbac03181e6b5fbf7164ca6f883 Mon Sep 17 00:00:00 2001
From: Andrew MacLeod <[email protected]>
Date: Wed, 26 Nov 2025 14:21:13 -0500
Subject: [PATCH] Undefined bitmasks imply undefined ranges.
bitmask have no way of representing UNDEFINED, and as such, bitmask
intersection returns an unknown_p values instead. This patch has the
function return false in this case, which will indicate UNDEFINED.
PR tree-optimization/122686
gcc/
* range-op.cc (operator_bitwise_and::op1_range): Check for
undefined bitmask.
* value-range.cc (prange::intersect): Handle undefined bitmask
intersection.
(irange::get_bitmask): Ditto.
(irange::intersect_bitmask): Ditto.
* value-range.h (irange_bitmask::intersect): Return false if the
result is UNDEFINED.
---
gcc/range-op.cc | 9 ++++++---
gcc/value-range.cc | 15 ++++++++++-----
gcc/value-range.h | 8 ++++++--
3 files changed, 22 insertions(+), 10 deletions(-)
diff --git a/gcc/range-op.cc b/gcc/range-op.cc
index 82a994b4ca5..fb7d4742bb6 100644
--- a/gcc/range-op.cc
+++ b/gcc/range-op.cc
@@ -3848,9 +3848,12 @@ operator_bitwise_and::op1_range (irange &r, tree type,
// extraneous values thats are not convered by the mask.
wide_int op1_value = lhs_bm.value () & ~op1_mask;
irange_bitmask op1_bm (op1_value, op1_mask);
- // INtersect this mask with anything already known about the value.
- op1_bm.intersect (r.get_bitmask ());
- r.update_bitmask (op1_bm);
+ // Intersect this mask with anything already known about the value.
+ // A return valueof false indicated the bitmask is an UNDEFINED range.
+ if (op1_bm.intersect (r.get_bitmask ()))
+ r.update_bitmask (op1_bm);
+ else
+ r.set_undefined ();
return true;
}
diff --git a/gcc/value-range.cc b/gcc/value-range.cc
index f93a7e5c53a..605f7081737 100644
--- a/gcc/value-range.cc
+++ b/gcc/value-range.cc
@@ -674,8 +674,10 @@ prange::intersect (const vrange &v)
// Intersect all bitmasks: the old one, the new one, and the other operand's.
irange_bitmask new_bitmask (m_type, m_min, m_max);
- m_bitmask.intersect (new_bitmask);
- m_bitmask.intersect (r.m_bitmask);
+ if (!m_bitmask.intersect (new_bitmask))
+ set_undefined ();
+ else if (!m_bitmask.intersect (r.m_bitmask))
+ set_undefined ();
if (varying_compatible_p ())
{
set_varying (type ());
@@ -2528,10 +2530,9 @@ irange::get_bitmask () const
irange_bitmask bm (type (), lower_bound (), upper_bound ());
if (!m_bitmask.unknown_p ())
{
- bm.intersect (m_bitmask);
// If the new intersection is unknown, it means there are inconstent
// bits, so simply return the original bitmask.
- if (bm.unknown_p ())
+ if (!bm.intersect (m_bitmask))
return m_bitmask;
}
return bm;
@@ -2572,7 +2573,11 @@ irange::intersect_bitmask (const irange &r)
irange_bitmask bm = get_bitmask ();
irange_bitmask save = bm;
- bm.intersect (r.get_bitmask ());
+ if (!bm.intersect (r.get_bitmask ()))
+ {
+ set_undefined ();
+ return true;
+ }
// If the new mask is the same, there is no change.
if (m_bitmask == bm)
diff --git a/gcc/value-range.h b/gcc/value-range.h
index 6ae46e17959..0affc391a3e 100644
--- a/gcc/value-range.h
+++ b/gcc/value-range.h
@@ -145,7 +145,7 @@ public:
bool unknown_p () const;
unsigned get_precision () const;
void union_ (const irange_bitmask &src);
- void intersect (const irange_bitmask &src);
+ bool intersect (const irange_bitmask &src);
bool operator== (const irange_bitmask &src) const;
bool operator!= (const irange_bitmask &src) const { return !(*this == src); }
void verify_mask () const;
@@ -247,7 +247,9 @@ irange_bitmask::union_ (const irange_bitmask &src)
verify_mask ();
}
-inline void
+// Return FALSE if the bitmask intersection is undefined.
+
+inline bool
irange_bitmask::intersect (const irange_bitmask &src)
{
// If we have two known bits that are incompatible, the resulting
@@ -260,6 +262,7 @@ irange_bitmask::intersect (const irange_bitmask &src)
unsigned prec = m_mask.get_precision ();
m_mask = wi::minus_one (prec);
m_value = wi::zero (prec);
+ return false;
}
else
{
@@ -268,6 +271,7 @@ irange_bitmask::intersect (const irange_bitmask &src)
}
if (flag_checking)
verify_mask ();
+ return true;
}
// An integer range without any storage.
--
2.45.0
