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

[Quan Anh Mai]

On Fri, 2 May 2025 16:22:24 GMT, Hannes Greule <hgreule at openjdk.org> wrote:

>> src/hotspot/share/opto/rangeinference.cpp line 378:
>> 
>>> 376:     // it directly without going through i.
>>> 377:     //           0 0 1 0 0 0 0 0
>>> 378:     U alignment = tmp & (-tmp);
>> 
>> Suggestion:
>> 
>>     // We now want to select the last one of these candidates, which is
>>     // exactly the last index i upto first_violation such that lo[i] == zeros[i] == 0.
>>     // In our example we have i == 2.
>>     //           0 0 1 0 0 0 0 0
>>     U alignment = alignment_candidates & (-alignment_candidates);
>> 
>> Ok, well what is still missing is how the bit trick with `-alignment_candidates` works here.
>> 
>> Let me try:
>> 
>>  alignment_candidates =  0 1 1 0 0 0 0 0
>> -alignment_candidates =  1 0 1 0 0 0 0 0
>> 
>> Hmm yeah I'm not sure about this one....
>> I suppose I would have tried this via trailing zeros, but not sure about it...
>> 
>> What is the argument here, why this extracts the last bit?
>
> I think it gets easier when splitting the `-` into a `~` and a `+ 1`. After `~`, the trailing zeros become ones, and adding 1 has a cascading effect of producing zeros again that is stopped by the lowest zero bit (which is a one in the original value, and now is becoming a one again). Due to the `~`, all higher bits are flipped, so they are just becoming zeros when `&`-ing.

`-x == ~x + 1`. From the lowest set bit of `x`, we have `x == 0b...100...0`, `~x == 0b...011...1` and `~x + 1 == 0b...100...0`. Also, the higher bits are unchanged by the `+ 1`, so it is equivalent to `x & ~x`. As a result, the only bit remaining in `x & (-x)` is the last bit 1 of `x`. This is a pretty basic bit manipulation, though:

https://en.wikipedia.org/wiki/X86_Bit_manipulation_instruction_set#BMI1

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

PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r2071875022