RFR: 8360561: PhaseIdealLoop::create_new_if_for_predicate hits "must be a uct if pattern" assert

[Marc Chevalier]

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.

What would there be other ways to treat this problem a bit more generally? The classic solution is not to use intervals all the time: allow small set of values, up to a fixed cardinal (for instance 5 or 10), after which we switch to a range. This is quite easy and handle many cases: it is not that common that it is important for a variable to be equal to one of 10 distinct values, but not anything else in between. A modulo domain would also work along with interval (with a reduced product), but for only two values, or specific cases. That is not very general. A donut domain can also be helpful, but it needs smart heuristic. For 2 points, there are two donuts: in the previous example `[1, 5]` and `[INT_MIN, INT_MAX] \ [2, 4]`, but only the second allows to prove 3 is not in. Having signed and unsigned range is somewhat having both donuts for some cases, and having just one when they agree.

There is another underlying question: why do we need to have code both for meet (HS's join, to refine the value of `x`), and for guarding (to know whether a branch is taken). A typical abstract interpreter would actually do that with just one step, using a `Guard` function that refines a abstract state given a condition to satisfy. The resulting state is whatever enters the branch, already refined. If the branch is impossible, then the state has an empty concretization. This happens typically when one variable (in a non-relational domain) has an empty value (bottom), then the whole abstract state is empty. It can then be optimized into skipping the whole branch. In Hotspot, there are some major differences:
- the evaluation of the condition is not monolithically done in the abstract domain, but instead we want abstract value of each node
- at the end, we request the value of a comparison, without knowing which operator we are going to use, so the abstract value needs to specify all the operators that would allow entering the branch: instead of having a refined abstract state, we just know for which comparison operator, the abstract state is not empty.

We could imagine another way of working, returning the refined value of each variable in a condition (using a side table or spamming Cast nodes), for a given `BoolNode`, without holding the abstract domain by the hand too much. But of course, asking first "for which operators is the comparison non-empty", and then "give me the refined value of this variable for this given operator" leads to duplication of work.

Thanks,
Marc

-------------

Commit messages:
 - Tests
 - Trying for CmpU CmpL CmpUL
 - Fix EOF
 - + tests
 - cc2logical: CC_NE with != -> yes!
 - != if empty overlap

Changes: https://git.openjdk.org/jdk/pull/26504/files
  Webrev: https://webrevs.openjdk.org/?repo=jdk&pr=26504&range=00
  Issue: https://bugs.openjdk.org/browse/JDK-8360561
  Stats: 227 lines in 4 files changed: 227 ins; 0 del; 0 mod
  Patch: https://git.openjdk.org/jdk/pull/26504.diff
  Fetch: git fetch https://git.openjdk.org/jdk.git pull/26504/head:pull/26504

PR: https://git.openjdk.org/jdk/pull/26504