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. > [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] ... 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? > > >> 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. > 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. > 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? > > 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. I'd try forcing UNDEF bits to zero, possibly leave the caller to say whether zero or one with a flag argument? Richard. > > Andrew > > >
