RFR: 8360561: PhaseIdealLoop::create_new_if_for_predicate hits "must be a uct if pattern" assert
Marc Chevalier
mchevalier at openjdk.org
Thu Jul 31 11:14:50 UTC 2025
On Mon, 28 Jul 2025 16:36:12 GMT, Quan Anh Mai <qamai at openjdk.org> wrote:
>> Did you know that ranges can be disjoints and yet not ordered?! Well, in modular arithmetic.
>>
>> Let's look at a simplistic example:
>>
>> int x;
>> if (?) {
>> x = -1;
>> } else {
>> x = 1;
>> }
>>
>> if (x != 0) {
>> return;
>> }
>> // Unreachable
>>
>>
>> With signed ranges, before the second `if`, `x` is in `[-1, 1]`. Which is enough to enter to second if, but not enough to prove you have to enter it: it wrongly seems that after the second `if` is still reachable. Twaddle!
>>
>> With unsigned ranges, at this point `x` is in `[1, 2^32-1]`, and then, it is clear that `x != 0`. This information is used to refine the value of `x` in the (missing) else-branch, and so, after the if. This is done with simple lattice meet (Hotspot's join): in the else-branch, the possible values of `x` are the meet of what is was worth before, and the interval in the guard, that is `[0, 0]`. Thanks to the unsigned range, this is known to be empty (that is bottom, or Hotspot's top). And with a little reduced product, the whole type of `x` is empty as well. Yet, this information is not used to kill control yet.
>>
>> This is here the center of the problem: we have a situation such as:
>> <img width="1538" height="1345" alt="2 after-CastII" src="https://github.com/user-attachments/assets/bd59de79-f366-43c6-93c0-1098fd80c874" />
>> After node `110 CastII` is idealized, it is found to be Top, and then the uncommon trap at `129` is replaced by `238 Halt` by being value-dead.
>> <img width="1890" height="1389" alt="1 before-CastII" src="https://github.com/user-attachments/assets/9a664c97-771f-4ba5-92f2-bdf342ccf74f" />
>> Since the control is not killed, the node stay there, eventually making some predicate-related assert fail as a trap is expected under a `ParsePredicate`.
>>
>> And that's what this change proposes: when comparing integers with non-ordered ranges, let's see if the unsigned ranges overlap, by computing the meet. If the intersection is empty, then the values can't be equals, without being able to order them. This is new! Without unsigned information for signed integer, either they overlap, or we can order them. Adding modular arithmetic allows to have non-overlapping ranges that are also not ordered.
>>
>> Let's also notice that 0 is special: it is important bounds are on each side of 0 (or 2^31, the other discontinuity). For instance if `x` can be 1 or 5, for instance, both the signed and unsigned range will agree on `[1, 5]` and not be able to prove it's, let's say, 3.
> ...
>
> Should these be done for `CmpL`, `CmpU`, `CmpUL` as well?
@merykitty yes, probably, I was indeed looking into which flavors of `Cmp` would need something like that, and how hard it'd be to exhibit the problem. It's still a draft, it wasn't quite done 😉
-------------
PR Comment: https://git.openjdk.org/jdk/pull/26504#issuecomment-3130996399
More information about the hotspot-compiler-dev
mailing list