RFR: 8315066: Add unsigned bounds and known bits to TypeInt/Long [v20]

[Emanuel Peter]

On Thu, 19 Sep 2024 14:24:12 GMT, Quan Anh Mai <qamai at openjdk.org> wrote:

>> src/hotspot/share/opto/rangeinference.cpp line 104:
>> 
>>> 102:     // This means that the first bit that does not satisfy the bit requirement
>>> 103:     // is a 0 that should be a 1, this may be the first different bit we want
>>> 104:     // to find.
>> 
>> I would say something like this.
>> 
>> The msb violation is a one_violation - i.e. lo[i] = 0, instead of 1.
>> We construct the result from the high bits of lo, a 1, and the low bits of ones:
>> result = lo[i>i], 1, ones[<i]
>> 
>> Proof of correctness:
>> - TODO: why the high bits must be lo[>i]
>> - TODO: why the low bits must be ones[<i]
>
> It would be tempting to do that, but it would make the second case harder to understand. The explanation I settled on makes the 2 cases similar, which I hope would help understand the whole picture more easily.
> 
> In short, since `result > lo`, there must be a bit position `i` such that `result[i] = 1` and `lo[i] = 0` and all bits before `i` would be the same in `result` and `lo`. In both cases, we find a position `j` such that `result[j] != lo[j]`, which leads to `i >= j`; and prove that `j` leads to an acceptable result.

This sounds much better :)

>> src/hotspot/share/opto/rangeinference.hpp line 141:
>> 
>>> 139:     }
>>> 140: 
>>> 141:     return (urange._hi - U(srange._lo)) + (U(srange._hi) - urange._lo) + 1;
>> 
>> It looks good, but I don't understand it 🙈 Can you please explain?
>
> Basically `urange` and `srange` can be the same, or their intersection is the union of `[srange._lo, urange._hi]` and `[urange._lo, srange._hi]`. This simply calculates the size of 2 intervals and add them together.

Ah thanks! Can you make that a comment in the code?

>> src/hotspot/share/opto/rangeinference.hpp line 157:
>> 
>>> 155:     return super->_lo <= sub->_lo && super->_hi >= sub->_hi && super->_ulo <= sub->_ulo && super->_uhi >= sub->_uhi &&
>>> 156:           (super->_bits._zeros &~ sub->_bits._zeros) == 0 && (super->_bits._ones &~ sub->_bits._ones) == 0;
>>> 157:   }
>> 
>> why are these not member methods of `CT`? It also looks like this could be split for the components - at least the `_bits` could be a member method of `KnownBits`.
>> 
>> Having it more modular would make it easier to read and understand.
>
> They are helper methods that get called from `CT`, the main reason is that `TypeInt` and `TypeLong` are not templates so implementing these would be a huge duplication. This class is used merely to help reduce this duplication.

Ah fair enough. Ok.

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

PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r1767399737
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r1767397636
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r1767397153