RFR: 8365205: C2: Optimize popcount value computation using knownbits [v3]

[Emanuel Peter]

On Tue, 9 Sep 2025 11:03:26 GMT, Emanuel Peter <epeter at openjdk.org> wrote:

>> Jatin Bhateja has updated the pull request incrementally with one additional commit since the last revision:
>> 
>>   Update countbitsnode.cpp
>
> src/hotspot/share/opto/countbitsnode.cpp line 125:
> 
>> 123:         range is computed using the following formulas:-
>> 124:         - _hi = ~ZEROS
>> 125:         - _lo = ONES
> 
> Is there going to be some other Lemma here, that gives rise to the numbering? I'd just remove the numbering.

Also: this is not really a mathematical statement that can be proven, rather some sort of high-level intention.

> src/hotspot/share/opto/countbitsnode.cpp line 150:
> 
>> 148:   - Therefore, popcount(ONES) and popcount(~ZEROS) can safely be assumed as the upper and lower
>> 149:     bounds of the result value range.
>> 150: */
> 
> Suggestion:
> 
> // We use the KnownBits information from the integer types to derive how many one bits
> // we have at least and at most.
> // From the definition of KnownBits, we know:
> //   zeros: Indicates which bits must be 0: ones[i] =1 -> t[i]=0
> //   ones:  Indicates which bits must be 1: zeros[i]=1 -> t[i]=1
> //
> // From this, we derive:
> //   numer_of_zeros_in_t >= pop_count(zeros)
> //   -> number_of_ones_in_t <= bits_per_type - pop_count(zeros) = pop_count(~zeros)
> //   number_of_ones_in_t >= pop_count(ones)
> //
> // By definition:
> //   pop_count(t) = number_of_ones_in_t
> //
> // It follows:
> //   pop_count(ones) <= pop_count(t) <= pop_count(~zeros)
> //
> // Note: signed _lo and _hi, as well as unsigned _ulo and _uhi bounds of the integer types
> //       are already reflected in the KnownBits information, see TypeInt / TypeLong definitions.
> 
> Feel free to adjust the formulation :)

It goes along the lines of what @SirYwell proposed.

> test/hotspot/jtreg/compiler/intrinsics/TestPopCountValueTransforms.java line 114:
> 
>> 112:         }
>> 113:         return 1;
>> 114:     }
> 
> Thanks for the tests!
> 
> I think it would be quite valuable to have some tests that do not just clamp the range, but also create random `KnownBits`, i.e. with random and/or masks.
> 
> For example:
> `num = (num | ONES) & ZEROS;`
> 
> And then you generate `ONES` and `ZEROS` randomly, maybe even using `Generators`?
> Then round it off with some random range comparisons at the end:
> `        if (Integer.bitCount(num) >= CON1 && Integer.bitCount(num) <= CON2) {`

Also: how many popcount instructions are left? Should it not at most be 1?

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

PR Review Comment: https://git.openjdk.org/jdk/pull/27075#discussion_r2333112033
PR Review Comment: https://git.openjdk.org/jdk/pull/27075#discussion_r2333226941
PR Review Comment: https://git.openjdk.org/jdk/pull/27075#discussion_r2333218115