On 11/27/25 07:10, Richard Biener wrote:
On Thu, Nov 27, 2025 at 2:05 AM Andrew MacLeod <[email protected]> wrote:
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.
Hmm, you mean making the range minimal for a mask?
Likewise implementing a "true" compare operation by enumerating
the set of values in the ranges + masks.
no, making the mask minimal for the range. its always minimal for the
upper and lower bound, but there is no attempt to make sure any bits in
the middle could be one way or the other based on subranges. Any other
bits are purely from bitwise operations.
I dont know what you mean by true compare. the ranges are compared,a dn
the bitmasks are compared and must be identical in order to compare
equal. what else could you do. a single bit different in the bitmask
implies a diffrerent layout of the subranges.. so the bitmask implies
ranges differences. IK think the current compare is fine for equality.
[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.
But then, if there's new masks the range part could oscillate similarly?
Given we're likely not splitting into N ranges when the LSB is known to be
not set, aka [0,0] [2,2] [4,4] [6,6] ...
The ranges will never oscillate.. they will only ever be reduced in an
intersection operation. If the bitmask changes, we don't add new ranges
in, the bitmask merely would imply there could be. That would only be a
problem if we then unioned with ranges which the bitmask no longer
eliminates. As long as intersect works as advertised, this should be fine.
So the issue is probably not so much on int_range intersection or
unioning but that during iteration we do both. That makes convergence
difficult if we also cannot reliably canonicalize? We'd need to enforce
canonicalization on either intersection or unioning, or alternatively
forgo one - which would necessarily (for correctness) be intersection?
I dont think its quite that bad. I perhaps overstated the case for
canonicalization in my annoyance in the first patch as I hadn't
discovered that bitmask::intersect had actually done the wrong thing
. That code predates ranger and was part of the original bitmask code.
I don't think the bitmasks *need* to be canonicalized in a single way
because they are always calculated independent of the range... In fact
I don't think its possible simply because multiple bitmasks can be
applied to a range, and multiple ranges can be applied to a single
bitmask. I think the 2 together is the best we can do, and is about as
precise as we can get. What we can count on, is that intersection
doesn't make ranges larger, and union doesn't make them smaller. And
generally speaking,I think they both do that now. except for the bug in
this PR. The places that create bitmasks will always create the same
bitmasks, so I guess that is about as "canonincal" as we need.
Given that, the only union we do is to collect incoming edges and
combine them. Those incoming edges are the product of intersections.
As long as each work, I think were fine.
Every time the iteration in propagation ends up in one of these cycles
it has been when the computations cycle involves a value which becomes
UNDEFINED, but which then picks up stray values , so is no longer
UNDEFINED, and evolves back to UNDEFINED again. 100% fo the time.
One of my previous patches fixed most of this class of PR related to
bitmasks . They were all due to subranges existing which the bitmask
indicated were undefined. In that patch, I enforce all the subrange
bounds to always conform to the bitmask rather then doing it lazily like
we once did. That was no end fo trouble. That patch eliminates all stray
ranges, and produces UNDFEFINED for the range immediately if none of the
range elements conform. This eliminated most of the oscillation.
commit 9e04a43012be504b75217704124987d0510f7fdc
Author: Andrew MacLeod <[email protected]>
Date: Tue Oct 7 11:56:08 2025 -0400
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.
In this PRs case, It is the bitmask itself which devolved which is why
that patch didnt resolve it. we went from having 2 bitmasks to none
because bitmask::intersection bailed. This allowed 2 range elements to
remain which should have been removed ([12,12] was removed,
[20,20][28,28] remained). This caused another value in the chain which
was already UNDEFINED to evolve to another value, and caused the cycle.
bitmask intersection broke the rule., so that needs to be fixed.
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.
On a CFG merge we have unioning as well.
All range on entries are UNIONs of edges. As long as intersection
never makes things bigger, union will not be adding in new values that
didnt exist before.
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 don't think we can do that, you can ferry valid bits in a value with UNDEF
bits and later test those. Unless any operation invokes UB we can't
make the whole range UNDEFINED.
But we can arbitrarily chose '0' for UNDEF bits for example.
We have no spare bits.. mask is 1 for unknown and 0 for known. if a bit
is 0, then value has 1 or 0 to represent its value.
After giving it thought, I believe we can always go straight to
UNDEFINED. I think a single undefined bit *does* mean the entire range
is UNDEFINED. IF a single bit is undefined, that means there is no
value that exists which can satisfy it. Doesnt matter about the rest of
the bits, it means there is no value.
It is no different than
if (a & 8)
if (a & ~8)
// a is undefined
It doesnt matter what value a has, regardless of the 8 bit,... a is
undefined. in the final block.
IF the bitmask has an impossible bit, I don't think there is any point
in tracking it, what purpose does that serve? I think we just make
the entire range go to UNDEFINED.
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.
But for example [0, 0] union UNDEF is [0, 0], not UNDEF, so with
N bits and N subranges only one of the intersections is UNDEF,
if you union back the N bits into one value you do not get UNDEF?
We arent talking about union...? IM confused. [0,0] union UNDEF is
[0, 0]. Its additive and so UNDEF simply doesnt add anything else.
The only time union became a problem is when the intersection at the end
of some other block feeding the union made a range larger than the last
time the union was processed. So far, this has only ever happened
when we had an undefined value become larger when it should have
remained undefined.. The next iteration or two turns it back to
undefined and the cycle repeats..
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?
As said, I think dropping to UNDEFINED overall seems wrong. The
proposed API change is a bit limiting since the bitmask is altered
to VARYING but false is returned. It might be better to leave the
bitmask unaltered? After all both *this and SRC are valid approximations
to their intersection.
I'm not sure we should leave the choice to a caller btw, either it's
correct or it is not.
Sure, changing the bitmask is perhaps pointless, so we could just return
false. It going to be ignored anyway
And the only thing up to the caller is to make a decision of what to do
with an UNDEFINED bitmask. Because a bitmask is a separate object,
(which may or may not be part of a range), its up to the consumer of the
bitmask class to decide what to do if bitmask::intersect says there is
no possible value. Returning false seems to allow for that quite
easily. I don't see the point in adding a new field to the structure
to indicate undefined either.. and as soon as the irange or prange is
set to UNDEFINED, the bitmask ceases to exist as a concern.. we dont
apply bitmasks to undefined ranges.
There are exactly 3 consumers of bitmask::intersect.
prange::intersect
irange:intersect_bitmask() which is a call from irange::intersect
opertator_bitwise_and::op1_range().
the first 2 have the bitmask as a component of a range, the latter uses
it as a separate class to work out what effect an operation might have
on a range, and then apply it.
I'd try forcing UNDEF bits to zero, possibly leave the caller to say
whether zero or one with a flag argument?
but forcing them to zero is also incorrect. whats the difference between
one incorrect result vs another?
Ive attached the patch tweaked to not set any field in the bitmask when
it is undefined, just return false.
I do think this is the correct solution. I dont think there is any point
in enhancing the bitmask class to have a representation of UNDEFINED as
it would be such a transient thing, and serves little purpose in the
class itself.
ok?
Andrew
From d46828612c6481e3510af54335cab2b4cdab0e91 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 | 17 +++++++----------
3 files changed, 23 insertions(+), 18 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..11d1ed75744 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,20 +247,16 @@ 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
- // bit is undefined. It is unclear whether we should set the entire
- // range to UNDEFINED, or just a subset of it. For now, set the
- // entire bitmask to unknown (VARYING).
+ // bit and therefore entire range is undefined. Return FALSE.
if (wi::bit_and (~(m_mask | src.m_mask),
m_value ^ src.m_value) != 0)
- {
- unsigned prec = m_mask.get_precision ();
- m_mask = wi::minus_one (prec);
- m_value = wi::zero (prec);
- }
+ return false;
else
{
m_mask = m_mask & src.m_mask;
@@ -268,6 +264,7 @@ irange_bitmask::intersect (const irange_bitmask &src)
}
if (flag_checking)
verify_mask ();
+ return true;
}
// An integer range without any storage.
--
2.45.0
