RFR: 8327093: Add slice function to BitMap API

[Axel Boldt-Christmas]

On Fri, 1 Mar 2024 23:14:18 GMT, Matias Saavedra Silva <matsaave at openjdk.org> wrote:

> The BitMap does not currently have a "slice" method which can return a subset of the bitmap defined by a start and end bit. This utility can be used to analyze portions of a bitmap or to overwrite the existing map with a shorter, modified map. 
> 
> This implementation has two core methods: 
> `copy_of_range` allocates and returns a new word array as used internally by BitMap
> `truncate` overwrites the internal array with the one generated by `copy_of_range` so none of the internal workings are exposed to callers outside of BitMap.
> 
> This change is verified with an included test.

The parameter here `bool clear = true` does nothing and it is unclear to me why it is added. 

That `truncate(n)` is `[n:]` and not `[:n]` does not feel intuitive to me. Maybe having a `truncate_start` as well as `truncate_end` which covers both the explicit cases.

The `copy_of_range` logic seems broken. It is caught in the 32-bit gtests. Maybe it should be extended to cover more edge cases. Maybe add some different striped bitmaps.

src/hotspot/share/utilities/bitMap.cpp line 111:

> 109:   idx_t start_word = to_words_align_down(start_bit);
> 110:   idx_t end_word = to_words_align_up(end_bit);
> 111:   bm_word_t* const old_map = map();

I would rather all variables be const than just this one.

src/hotspot/share/utilities/bitMap.cpp line 123:

> 121: 
> 122:   // Iterate the map backwards as the shift will result in carry-out bits
> 123:   for (idx_t i = end_word; i --> start_word;) {

I guess that mutating `i` inside the conditional is to deal with `idx_t` being unsigned. But the `i --> start_word` rather than  `i-- > start_word` looks strange to me.

src/hotspot/share/utilities/bitMap.cpp line 126:

> 124:     // First iteration is a special case:
> 125:     // There may be left over bits in the last word that we want to keep while discarding the rest
> 126:     if (i == end_word - 1 && cutoff > 0) {

Is it important that the msb are cleared (beyond the `size()` bit). Could always just do `new_map[i-start_word] = old_map[i] >> shift;`

src/hotspot/share/utilities/bitMap.cpp line 135:

> 133: 
> 134:     // A full shift by BitsPerWord could be sign extended
> 135:     carry = old_map[i] << (BitsPerWord - shift) % BitsPerWord;

This contains both UB (shift too large) and it is unclear to me what this does. Should this whole loop not simply be:
```C++
  for (idx_t i = end_word; i-- > start_word;) {
    new_map[i-start_word] = old_map[i] >> shift;

    if (shift != 0) {
      new_map[i-start_word] |= carry;
      carry = old_map[i] << (BitsPerWord - shift);
    }
  }

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

PR Review: https://git.openjdk.org/jdk/pull/18092#pullrequestreview-1916252315
PR Review Comment: https://git.openjdk.org/jdk/pull/18092#discussion_r1512362746
PR Review Comment: https://git.openjdk.org/jdk/pull/18092#discussion_r1512362335
PR Review Comment: https://git.openjdk.org/jdk/pull/18092#discussion_r1512368106
PR Review Comment: https://git.openjdk.org/jdk/pull/18092#discussion_r1512375862