src/hotspot/share/utilities/bitMap.inline.hpp

rev 57098 : [mq]: max_size
rev 57099 : [mq]: improve
rev 57100 : [mq]: tschatzl_review

*** 24,34 ****
  
  #ifndef SHARE_UTILITIES_BITMAP_INLINE_HPP
  #define SHARE_UTILITIES_BITMAP_INLINE_HPP
  
  #include "runtime/atomic.hpp"
! #include "runtime/orderAccess.hpp"
  #include "utilities/bitMap.hpp"
  #include "utilities/count_trailing_zeros.hpp"
  
  inline void BitMap::set_bit(idx_t bit) {
    verify_index(bit);
--- 24,34 ----
  
  #ifndef SHARE_UTILITIES_BITMAP_INLINE_HPP
  #define SHARE_UTILITIES_BITMAP_INLINE_HPP
  
  #include "runtime/atomic.hpp"
! #include "utilities/align.hpp"
  #include "utilities/bitMap.hpp"
  #include "utilities/count_trailing_zeros.hpp"
  
  inline void BitMap::set_bit(idx_t bit) {
    verify_index(bit);
*** 166,197 ****
  
  template<BitMap::bm_word_t flip, bool aligned_right>
  inline BitMap::idx_t BitMap::get_next_bit_impl(idx_t l_index, idx_t r_index) const {
    STATIC_ASSERT(flip == find_ones_flip || flip == find_zeros_flip);
    verify_range(l_index, r_index);
!   assert(!aligned_right || is_word_aligned(r_index), "r_index not aligned");
  
    // The first word often contains an interesting bit, either due to
    // density or because of features of the calling algorithm.  So it's
    // important to examine that first word with a minimum of fuss,
    // minimizing setup time for later words that will be wasted if the
    // first word is indeed interesting.
  
    // The benefit from aligned_right being true is relatively small.
!   // It saves a couple instructions in the setup for the word search
!   // loop.  It also eliminates the range check on the final result.
    // However, callers often have a comparison with r_index, and
    // inlining often allows the two comparisons to be combined; it is
    // important when !aligned_right that return paths either return
    // r_index or a value dominated by a comparison with r_index.
    // aligned_right is still helpful when the caller doesn't have a
    // range check because features of the calling algorithm guarantee
    // an interesting bit will be present.
  
    if (l_index < r_index) {
      // Get the word containing l_index, and shift out low bits.
!     idx_t index = word_index(l_index);
      bm_word_t cword = (map(index) ^ flip) >> bit_in_word(l_index);
      if ((cword & 1) != 0) {
        // The first bit is similarly often interesting. When it matters
        // (density or features of the calling algorithm make it likely
        // the first bit is set), going straight to the next clause compares
--- 166,197 ----
  
  template<BitMap::bm_word_t flip, bool aligned_right>
  inline BitMap::idx_t BitMap::get_next_bit_impl(idx_t l_index, idx_t r_index) const {
    STATIC_ASSERT(flip == find_ones_flip || flip == find_zeros_flip);
    verify_range(l_index, r_index);
!   assert(!aligned_right || is_aligned(r_index, BitsPerWord), "r_index not aligned");
  
    // The first word often contains an interesting bit, either due to
    // density or because of features of the calling algorithm.  So it's
    // important to examine that first word with a minimum of fuss,
    // minimizing setup time for later words that will be wasted if the
    // first word is indeed interesting.
  
    // The benefit from aligned_right being true is relatively small.
!   // It saves an operation in the setup for the word search loop.
!   // It also eliminates the range check on the final result.
    // However, callers often have a comparison with r_index, and
    // inlining often allows the two comparisons to be combined; it is
    // important when !aligned_right that return paths either return
    // r_index or a value dominated by a comparison with r_index.
    // aligned_right is still helpful when the caller doesn't have a
    // range check because features of the calling algorithm guarantee
    // an interesting bit will be present.
  
    if (l_index < r_index) {
      // Get the word containing l_index, and shift out low bits.
!     idx_t index = to_words_align_down(l_index);
      bm_word_t cword = (map(index) ^ flip) >> bit_in_word(l_index);
      if ((cword & 1) != 0) {
        // The first bit is similarly often interesting. When it matters
        // (density or features of the calling algorithm make it likely
        // the first bit is set), going straight to the next clause compares
*** 207,218 ****
        // Result is beyond range bound; return r_index.
      } else {
        // Flipped and shifted first word is zero.  Word search through
        // aligned up r_index for a non-zero flipped word.
        idx_t limit = aligned_right
!         ? word_index(r_index)
!         : (word_index(r_index - 1) + 1); // Align up, knowing r_index > 0.
        while (++index < limit) {
          cword = map(index) ^ flip;
          if (cword != 0) {
            idx_t result = bit_index(index) + count_trailing_zeros(cword);
            if (aligned_right || (result < r_index)) return result;
--- 207,218 ----
        // Result is beyond range bound; return r_index.
      } else {
        // Flipped and shifted first word is zero.  Word search through
        // aligned up r_index for a non-zero flipped word.
        idx_t limit = aligned_right
!         ? to_words_align_down(r_index) // Miniscule savings when aligned.
!         : to_words_align_up(r_index);
        while (++index < limit) {
          cword = map(index) ^ flip;
          if (cword != 0) {
            idx_t result = bit_index(index) + count_trailing_zeros(cword);
            if (aligned_right || (result < r_index)) return result;
*** 247,257 ****
  // returned mask can be used directly to clear the range, or inverted to set the
  // range.  Note:  end must not be 0.
  inline BitMap::bm_word_t
  BitMap::inverted_bit_mask_for_range(idx_t beg, idx_t end) const {
    assert(end != 0, "does not work when end == 0");
!   assert(beg == end || word_index(beg) == word_index(end - 1),
           "must be a single-word range");
    bm_word_t mask = bit_mask(beg) - 1;   // low (right) bits
    if (bit_in_word(end) != 0) {
      mask |= ~(bit_mask(end) - 1);       // high (left) bits
    }
--- 247,257 ----
  // returned mask can be used directly to clear the range, or inverted to set the
  // range.  Note:  end must not be 0.
  inline BitMap::bm_word_t
  BitMap::inverted_bit_mask_for_range(idx_t beg, idx_t end) const {
    assert(end != 0, "does not work when end == 0");
!   assert(beg == end || to_words_align_down(beg) == to_words_align_down(end - 1),
           "must be a single-word range");
    bm_word_t mask = bit_mask(beg) - 1;   // low (right) bits
    if (bit_in_word(end) != 0) {
      mask |= ~(bit_mask(end) - 1);       // high (left) bits
    }
*** 266,281 ****
  inline void BitMap::clear_large_range_of_words(idx_t beg, idx_t end) {
    assert(beg <= end, "underflow");
    memset(_map + beg, 0, (end - beg) * sizeof(bm_word_t));
  }
  
- inline BitMap::idx_t BitMap::word_index_round_up(idx_t bit) const {
-   idx_t bit_rounded_up = bit + (BitsPerWord - 1);
-   // Check for integer arithmetic overflow.
-   return bit_rounded_up > bit ? word_index(bit_rounded_up) : size_in_words();
- }
- 
  inline bool BitMap2D::is_valid_index(idx_t slot_index, idx_t bit_within_slot_index) {
    verify_bit_within_slot_index(bit_within_slot_index);
    return (bit_index(slot_index, bit_within_slot_index) < size_in_bits());
  }
  
--- 266,275 ----