src/hotspot/share/gc/shenandoah/shenandoahSimpleBitMap.cpp

/*
 * Copyright Amazon.com Inc. or its affiliates. All Rights Reserved.
 * Copyright (c) 2025, Oracle and/or its affiliates. All rights reserved.
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.
 *
 * This code is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 * or visit www.oracle.com if you need additional information or have any
 * questions.
 *
 */

#include "gc/shenandoah/shenandoahSimpleBitMap.inline.hpp"

ShenandoahSimpleBitMap::ShenandoahSimpleBitMap(size_t num_bits) :
    _num_bits(num_bits),
    _num_words(align_up(num_bits, BitsPerWord) / BitsPerWord),
    _bitmap(NEW_C_HEAP_ARRAY(uintx, _num_words, mtGC))
{
  clear_all();
}

ShenandoahSimpleBitMap::~ShenandoahSimpleBitMap() {
  if (_bitmap != nullptr) {
    FREE_C_HEAP_ARRAY(uintx, _bitmap);
  }
}

size_t ShenandoahSimpleBitMap::count_leading_ones(idx_t start_idx) const {
  assert((start_idx >= 0) && (start_idx < _num_bits), "precondition");
  size_t array_idx = start_idx >> LogBitsPerWord;
  uintx element_bits = _bitmap[array_idx];
  uintx bit_number = start_idx & (BitsPerWord - 1);
  uintx mask = ~tail_mask(bit_number);
  size_t counted_ones = 0;
  while ((element_bits & mask) == mask) {
    // All bits numbered >= bit_number are set
    size_t found_ones = BitsPerWord - bit_number;
    counted_ones += found_ones;
    // Dead code: do not need to compute: start_idx += found_ones;
    // Strength reduction:                array_idx = (start_idx >> LogBitsPerWord)
    array_idx++;
    element_bits = _bitmap[array_idx];
    // Constant folding:                  bit_number = start_idx & (BitsPerWord - 1);
    bit_number = 0;
    // Constant folding:                  mask = ~right_n_bits(bit_number);
    mask = ~0;
  }

  // Add in number of consecutive ones starting with the_bit and including more significant bits and return result
  uintx aligned = element_bits >> bit_number;
  uintx complement = ~aligned;
  return counted_ones + count_trailing_zeros<uintx>(complement);
}

size_t ShenandoahSimpleBitMap::count_trailing_ones(idx_t last_idx) const {
  assert((last_idx >= 0) && (last_idx < _num_bits), "precondition");
  size_t array_idx = last_idx >> LogBitsPerWord;
  uintx element_bits = _bitmap[array_idx];
  uintx bit_number = last_idx & (BitsPerWord - 1);
  // All ones from bit 0 to the_bit
  uintx mask = tail_mask(bit_number + 1);
  size_t counted_ones = 0;
  while ((element_bits & mask) == mask) {
    // All bits numbered <= bit_number are set
    size_t found_ones = bit_number + 1;
    counted_ones += found_ones;
    // Dead code: do not need to compute: last_idx -= found_ones;
    array_idx--;
    element_bits = _bitmap[array_idx];
    // Constant folding:                  bit_number = last_idx & (BitsPerWord - 1);
    bit_number = BitsPerWord - 1;
    // Constant folding:                  mask = right_n_bits(bit_number + 1);
    mask = ~0;
  }

  // Add in number of consecutive ones starting with the_bit and including less significant bits and return result
  uintx aligned = element_bits << (BitsPerWord - (bit_number + 1));
  uintx complement = ~aligned;
  return counted_ones + count_leading_zeros<uintx>(complement);
}

bool ShenandoahSimpleBitMap::is_forward_consecutive_ones(idx_t start_idx, idx_t count) const {
  while (count > 0) {
    assert((start_idx >= 0) && (start_idx < _num_bits), "precondition: start_idx: %zd, count: %zd",
           start_idx, count);
    assert(start_idx + count <= (idx_t) _num_bits, "precondition");
    size_t array_idx = start_idx >> LogBitsPerWord;
    uintx bit_number = start_idx & (BitsPerWord - 1);
    uintx element_bits = _bitmap[array_idx];
    uintx bits_to_examine  = BitsPerWord - bit_number;
    element_bits >>= bit_number;
    uintx complement = ~element_bits;
    uintx trailing_ones;
    if (complement != 0) {
      trailing_ones = count_trailing_zeros<uintx>(complement);
    } else {
      trailing_ones = bits_to_examine;
    }
    if (trailing_ones >= (uintx) count) {
      return true;
    } else if (trailing_ones == bits_to_examine) {
      start_idx += bits_to_examine;
      count -= bits_to_examine;
      // Repeat search with smaller goal
    } else {
      return false;
    }
  }
  return true;
}

bool ShenandoahSimpleBitMap::is_backward_consecutive_ones(idx_t last_idx, idx_t count) const {
  while (count > 0) {
    assert((last_idx >= 0) && (last_idx < _num_bits), "precondition");
    assert(last_idx - count >= -1, "precondition");
    size_t array_idx = last_idx >> LogBitsPerWord;
    uintx bit_number = last_idx & (BitsPerWord - 1);
    uintx element_bits = _bitmap[array_idx];
    uintx bits_to_examine = bit_number + 1;
    element_bits <<= (BitsPerWord - bits_to_examine);
    uintx complement = ~element_bits;
    uintx leading_ones;
    if (complement != 0) {
      leading_ones = count_leading_zeros<uintx>(complement);
    } else {
      leading_ones = bits_to_examine;
    }
    if (leading_ones >= (uintx) count) {
      return true;
    } else if (leading_ones == bits_to_examine) {
      last_idx -= leading_ones;
      count -= leading_ones;
      // Repeat search with smaller goal
    } else {
      return false;
    }
  }
  return true;
}

idx_t ShenandoahSimpleBitMap::find_first_consecutive_set_bits(idx_t beg, idx_t end, size_t num_bits) const {
  assert((beg >= 0) && (beg < _num_bits), "precondition");

  // Stop looking if there are not num_bits remaining in probe space.
  idx_t start_boundary = end - num_bits;
  if (beg > start_boundary) {
    return end;
  }
  uintx array_idx = beg >> LogBitsPerWord;
  uintx bit_number = beg & (BitsPerWord - 1);
  uintx element_bits = _bitmap[array_idx];
  if (bit_number > 0) {
    uintx mask_out = tail_mask(bit_number);
    element_bits &= ~mask_out;
  }

  // The following loop minimizes the number of spans probed in order to find num_bits consecutive bits.
  // For example, if bit_number = beg = 0, num_bits = 8, and element bits equals 00111111_11000000_00000000_10011000B,
  // we need only 3 probes to find the match at bit offset 22.
  //
  // Let beg = 0
  // element_bits = 00111111_11000000_00000000_10011000B;
  //                                           ________   (the searched span)
  //                                           ^   ^  ^- bit_number = beg = 0
  //                                           |   +-- next_start_candidate_1 (where next 1 is found)
  //                                           +------ next_start_candidate_2 (start of the trailing 1s within span)
  // Let beg = 7
  // element_bits = 00111111_11000000_00000000_10011000B;
  //                          ^       ^_________   (the searched span)
  //                          |       |        ^- bit_number = beg = 7
  //                          |       +---------- next_start_candidate_2 (there are no trailing 1s within span)
  //                          +------------------ next_start_candidate_1 (where next 1 is found)
  // Let beg = 22
  // Let beg = 22
  // element_bits = 00111111_11000001_11111100_10011000B;
  //                  _________   (the searched span)
  //                          ^- bit_number = beg = 18
  // Here, is_forward_consecutive_ones(22, 8) succeeds and we report the match

  while (true) {
    if (element_bits == 0) {
      // move to the next element
      beg += BitsPerWord - bit_number;
      if (beg > start_boundary) {
        // No match found.
        return end;
      }
      array_idx++;
      bit_number = 0;
      element_bits = _bitmap[array_idx];
    } else if (is_forward_consecutive_ones(beg, num_bits)) {
      return beg;
    } else {
      // There is at least one non-zero bit within the masked element_bits. Arrange to skip over bits that
      // cannot be part of a consecutive-ones match.
      uintx next_set_bit = count_trailing_zeros<uintx>(element_bits);
      uintx next_start_candidate_1 = (array_idx << LogBitsPerWord) + next_set_bit;

      // There is at least one zero bit in this span. Align the next probe at the start of trailing ones for probed span,
      // or align at end of span if this span has no trailing ones.
      size_t trailing_ones = count_trailing_ones(beg + num_bits - 1);
      uintx next_start_candidate_2 = beg + num_bits - trailing_ones;

      beg = MAX2(next_start_candidate_1, next_start_candidate_2);
      if (beg > start_boundary) {
        // No match found.
        return end;
      }
      array_idx = beg >> LogBitsPerWord;
      element_bits = _bitmap[array_idx];
      bit_number = beg & (BitsPerWord - 1);
      if (bit_number > 0) {
        size_t mask_out = tail_mask(bit_number);
        element_bits &= ~mask_out;
      }
    }
  }
}

idx_t ShenandoahSimpleBitMap::find_last_consecutive_set_bits(const idx_t beg, idx_t end, const size_t num_bits) const {

  assert((end >= 0) && (end < _num_bits), "precondition");

  // Stop looking if there are not num_bits remaining in probe space.
  idx_t last_boundary = beg + num_bits;
  if (end < last_boundary) {
    return beg;
  }

  size_t array_idx = end >> LogBitsPerWord;
  uintx bit_number = end & (BitsPerWord - 1);
  uintx element_bits = _bitmap[array_idx];
  if (bit_number < BitsPerWord - 1) {
    uintx mask_in = tail_mask(bit_number + 1);
    element_bits &= mask_in;
  }

  // See comment in find_first_consecutive_set_bits to understand how this loop works.
  while (true) {
    if (element_bits == 0) {
      // move to the previous element
      end -= bit_number + 1;
      if (end < last_boundary) {
        // No match found.
        return beg;
      }
      array_idx--;
      bit_number = BitsPerWord - 1;
      element_bits = _bitmap[array_idx];
    } else if (is_backward_consecutive_ones(end, num_bits)) {
      return end + 1 - num_bits;
    } else {
      // There is at least one non-zero bit within the masked element_bits. Arrange to skip over bits that
      // cannot be part of a consecutive-ones match.
      uintx next_set_bit = BitsPerWord - (1 + count_leading_zeros<uintx>(element_bits));
      uintx next_last_candidate_1 = (array_idx << LogBitsPerWord) + next_set_bit;

      // There is at least one zero bit in this span.  Align the next probe at the end of leading ones for probed span,
      // or align before start of span if this span has no leading ones.
      size_t leading_ones = count_leading_ones(end - (num_bits - 1));
      uintx next_last_candidate_2 = end - (num_bits - leading_ones);

      end = MIN2(next_last_candidate_1, next_last_candidate_2);
      if (end < last_boundary) {
        // No match found.
        return beg;
      }
      array_idx = end >> LogBitsPerWord;
      bit_number = end & (BitsPerWord - 1);
      element_bits = _bitmap[array_idx];
      if (bit_number < BitsPerWord - 1){
        size_t mask_in = tail_mask(bit_number + 1);
        element_bits &= mask_in;
      }
    }
  }
}