On Thu, Nov 27, 2025 at 7:39 PM Andrew MacLeod <[email protected]> wrote: > > > 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.
I was thinking of using mask 0 (aka known) and value 0 (aka bit zero) as an arbitrary (but fixed) choice since that "satisfies" UNDEFINED. But ... > 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. ... OK, this sounds convincing, so let's try it. > > > > >> 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.. Yes. I'm just worried in general about a dataflow problem on a cycle that has both growing and shrinking operations... but yes, if intersection suddenly sometimes grows the set that's indeed even more concerning, so let's fix that first (and hope for the best!). > > > > >> 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? OK. Thanks, Richard. > Andrew
