RFR: 8350896: Integer/Long.compress gets wrong type from CompressBitsNode::Value [v5]

[Emanuel Peter]

On Tue, 6 May 2025 08:53:48 GMT, Jatin Bhateja <jbhateja at openjdk.org> wrote:

> > @jatin-bhateja I think I'd rather wait until you have more thorough testing and the proofs I asked for, otherwise I would need to run the testing twice ;)
> 
> I have added comments in the code which give sufficient details, let me know if you still need more explanation

@jatin-bhateja I assume you are referring to the comments here:

      // Following rules applies to upper bound estimation of results value range
      // res.hi = src.hi iff src.hi > 0 else max_value
      // if result_bit_width < mask_bit_width, then we can further constrain res.hi as follows.
      // res.hi = MIN(res.hi, (1L << result_bit_width) - 1)
      hi = src_type->hi_as_long() >= 0 ? src_type->hi_as_long() : hi;
      hi = result_bit_width < mask_bit_width ? MIN2((jlong)((1L << result_bit_width) - 1L), hi) : hi;


To me this looks more like simply a "statement" `we can`. It may be correct, or may be not. Even @merykitty says this is non-trivial, and he is a bit-magic master.

There have now been multiple bugs in this code:
-  I filed this bug after finding it with my Template based Fuzzer.
- Then I found a bug in your fix here.
- And now @merykitty  even found UB in this code.

As I asked above:
> We got this code wrong before, and now again. How can we gain confidence that it will be correct on the next attempt?

You are claiming **that** your code is true, but you do not give proof for it. What I am looking for is **why** it is correct, and correct for all cases.

To repeat myself from above:
> For me to approve this code, you will have to do more than that. I will need:
> - Proof of the implemented logic.
> - More tests.

@merykitty has pointed you to the tests here: https://github.com/openjdk/jdk/pull/23089
Have you responded to that yet? I agree with him that we need such tests.
I would point you specifically to the range verification like this:

        int sum = 0;
        if (z > LIMIT_1) { sum += 1; }
        if (z > LIMIT_2) { sum += 2; }
        if (z > LIMIT_3) { sum += 4; }
        if (z > LIMIT_4) { sum += 8; }
        if (z > LIMIT_5) { sum += 16; }
        if (z > LIMIT_6) { sum += 32; }
        if (z > LIMIT_7) { sum += 64; }
        if (z > LIMIT_8) { sum += 128; }

If a limit wrongly constant folds, then we get wrong results, by either always adding or never adding to the `sum`.
This allows us to do checks against ranges.

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

An alternative is always to "backout" the broken optimization, as @merykitty suggested:

> @jatin-bhateja This operation is non-trivial, I expect the level of coverage to be on par with https://github.com/openjdk/jdk/pull/23089. If you want to have a quick fix, I suggest removing all the logic and simply returning the bottom type.

I.e. you could the problematic part of the changes from https://github.com/openjdk/jdk/pull/8498.

We may want to revisit the `expand / compress` optimizations once we have `KnownBits` anyway, and we are quite close with it now https://github.com/openjdk/jdk/pull/17508.

But even then: we will need good tests eventually. And with `KnownBits` we do not only need the "range" verification I showed above from https://github.com/openjdk/jdk/pull/23089, but we would have to do something similar with bits, to check if the type has one bit as always one or zero, which could lead to wrong constant folding below.

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

PR Comment: https://git.openjdk.org/jdk/pull/23947#issuecomment-2853896251