RFR: 8287215: Add method to scan bitmap backwards [v4]

[Kim Barrett]

On Mon, 30 May 2022 09:19:25 GMT, Thomas Schatzl <tschatzl at openjdk.org> wrote:

>> Hi all,
>> 
>>   can I have reviews for this change that adds a method to scan bitmaps backwards? This functionality is necessary for upcoming change to remove on of the mark bitmaps [JDK-8210708](https://bugs.openjdk.java.net/browse/JDK-8210708).
>> 
>> As such this is only an addition of that functionality with no reference (apart from the gtest) from Hotspot itself.
>> 
>> Testing: gtest
>> 
>> Thanks,
>>   Thomas
>
> Thomas Schatzl has updated the pull request incrementally with one additional commit since the last revision:
> 
>   Make r_index exclusive

Changes requested by kbarrett (Reviewer).

src/hotspot/share/utilities/bitMap.inline.hpp line 233:

> 231: template<BitMap::bm_word_t flip, bool aligned_left>
> 232: inline BitMap::idx_t BitMap::get_prev_bit_impl(idx_t l_index, idx_t r_index) const {
> 233:   STATIC_ASSERT(flip == find_ones_flip || flip == find_zeros_flip);

We have `static_assert` now, which requires a message but gives easier to understand errors.

src/hotspot/share/utilities/bitMap.inline.hpp line 246:

> 244:   // an operation when returning results.
> 245: 
> 246:   // The return value of l_index when no bit is found is BitMap::NotFound.

The mention of `l_index` here seems wrong - maybe an incomplete edit?

src/hotspot/share/utilities/bitMap.inline.hpp line 254:

> 252:     bm_word_t cword = (map(index) ^ flip) << (BitsPerWord - 1 - bit_in_word(r_index));
> 253: 
> 254:     STATIC_ASSERT(sizeof(intptr_t) == sizeof(bm_word_t));

Another place that should be `static_assert`.

src/hotspot/share/utilities/bitMap.inline.hpp line 270:

> 268:         return result;
> 269:       }
> 270:       // Result is beyond range bound.

Maybe add "return NotFound" for consistency with later comment?

src/hotspot/share/utilities/bitMap.inline.hpp line 274:

> 272:       // Flipped and shifted first word is zero.  Word search through
> 273:       // aligned down l_index for a non-zero flipped word.
> 274:       idx_t limit = to_words_align_down(l_index); // Minuscule savings when aligned.

The comment about a "minuscule savings" is copied from the forward search, but is only relevant there, not here.  It's about using `aligned_right` (in the forward search case) to decide whether we can use the cheaper `to_words_align_down` or need to use the (slightly) more expensive `to_words_align_up`.  There's nothing like that here, as can be seen by there being no conditional on alignment

src/hotspot/share/utilities/bitMap.inline.hpp line 278:

> 276:         cword = map(index) ^ flip;
> 277:         if (cword != 0) {
> 278:           idx_t result = bit_index(index + 1) - count_leading_zeros(cword) - 1;

I think this calculation would be clearer as

bit_index(index) + (BitsPerWord - 1) - count_leading_zeros(cword)

getting the position of the last bit in the current word directly and counting backward from there.

It's ultimately the same calculation, but I found the suggested alternative more obvious and easier to reason about.  For example, can `bit_index(index + 1)` overflow?  It can't, but I had to think about it.

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

PR: https://git.openjdk.java.net/jdk/pull/8869