rev 2896 : 7121547: G1: High number mispredicted branches while iterating over the marking bitmap
Summary: There is a high number of mispredicted branches associated with calling BitMap::iteratate() from within CMBitMapRO::iterate(). Implement a version of CMBitMapRO::iterate() directly using inline-able routines.
Reviewed-by:

          --- old/src/share/vm/utilities/bitMap.inline.hpp
          +++ new/src/share/vm/utilities/bitMap.inline.hpp

   1    1  /*
   2    2   * Copyright (c) 2005, 2010, Oracle and/or its affiliates. All rights reserved.
   3    3   * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4    4   *
   5    5   * This code is free software; you can redistribute it and/or modify it
   6    6   * under the terms of the GNU General Public License version 2 only, as
   7    7   * published by the Free Software Foundation.
   8    8   *
   9    9   * This code is distributed in the hope that it will be useful, but WITHOUT
  10   10   * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11   11   * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12   12   * version 2 for more details (a copy is included in the LICENSE file that
  13   13   * accompanied this code).
  14   14   *
  15   15   * You should have received a copy of the GNU General Public License version
  16   16   * 2 along with this work; if not, write to the Free Software Foundation,
  17   17   * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18   18   *
  19   19   * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20   20   * or visit www.oracle.com if you need additional information or have any
  21   21   * questions.
  22   22   *
  23   23   */
  24   24  
  25   25  #ifndef SHARE_VM_UTILITIES_BITMAP_INLINE_HPP
  26   26  #define SHARE_VM_UTILITIES_BITMAP_INLINE_HPP
  27   27  
  28   28  #include "runtime/atomic.hpp"
  29   29  #include "utilities/bitMap.hpp"
  30   30  
  31   31  #ifdef ASSERT
  32   32  inline void BitMap::verify_index(idx_t index) const {
  33   33    assert(index < _size, "BitMap index out of bounds");
  34   34  }
  35   35  
  36   36  inline void BitMap::verify_range(idx_t beg_index, idx_t end_index) const {
  37   37    assert(beg_index <= end_index, "BitMap range error");
  38   38    // Note that [0,0) and [size,size) are both valid ranges.
  39   39    if (end_index != _size) verify_index(end_index);
  40   40  }
  41   41  #endif // #ifdef ASSERT
  42   42  
  43   43  inline void BitMap::set_bit(idx_t bit) {
  44   44    verify_index(bit);
  45   45    *word_addr(bit) |= bit_mask(bit);
  46   46  }
  47   47  
  48   48  inline void BitMap::clear_bit(idx_t bit) {
  49   49    verify_index(bit);
  50   50    *word_addr(bit) &= ~bit_mask(bit);
  51   51  }
  52   52  
  53   53  inline bool BitMap::par_set_bit(idx_t bit) {
  54   54    verify_index(bit);
  55   55    volatile idx_t* const addr = word_addr(bit);
  56   56    const idx_t mask = bit_mask(bit);
  57   57    idx_t old_val = *addr;
  58   58  
  59   59    do {
  60   60      const idx_t new_val = old_val | mask;
  61   61      if (new_val == old_val) {
  62   62        return false;     // Someone else beat us to it.
  63   63      }
  64   64      const idx_t cur_val = (idx_t) Atomic::cmpxchg_ptr((void*) new_val,
  65   65                                                        (volatile void*) addr,
  66   66                                                        (void*) old_val);
  67   67      if (cur_val == old_val) {
  68   68        return true;      // Success.
  69   69      }
  70   70      old_val = cur_val;  // The value changed, try again.
  71   71    } while (true);
  72   72  }
  73   73  
  74   74  inline bool BitMap::par_clear_bit(idx_t bit) {
  75   75    verify_index(bit);
  76   76    volatile idx_t* const addr = word_addr(bit);
  77   77    const idx_t mask = ~bit_mask(bit);
  78   78    idx_t old_val = *addr;
  79   79  
  80   80    do {
  81   81      const idx_t new_val = old_val & mask;
  82   82      if (new_val == old_val) {
  83   83        return false;     // Someone else beat us to it.
  84   84      }
  85   85      const idx_t cur_val = (idx_t) Atomic::cmpxchg_ptr((void*) new_val,
  86   86                                                        (volatile void*) addr,
  87   87                                                        (void*) old_val);
  88   88      if (cur_val == old_val) {
  89   89        return true;      // Success.
  90   90      }
  91   91      old_val = cur_val;  // The value changed, try again.
  92   92    } while (true);
  93   93  }
  94   94  
  95   95  inline void BitMap::set_range(idx_t beg, idx_t end, RangeSizeHint hint) {
  96   96    if (hint == small_range && end - beg == 1) {
  97   97      set_bit(beg);
  98   98    } else {
  99   99      if (hint == large_range) {
 100  100        set_large_range(beg, end);
 101  101      } else {
 102  102        set_range(beg, end);
 103  103      }
 104  104    }
 105  105  }
 106  106  
 107  107  inline void BitMap::clear_range(idx_t beg, idx_t end, RangeSizeHint hint) {
 108  108    if (hint == small_range && end - beg == 1) {
 109  109      clear_bit(beg);
 110  110    } else {
 111  111      if (hint == large_range) {
 112  112        clear_large_range(beg, end);
 113  113      } else {
 114  114        clear_range(beg, end);
 115  115      }
 116  116    }
 117  117  }
 118  118  
 119  119  inline void BitMap::par_set_range(idx_t beg, idx_t end, RangeSizeHint hint) {
 120  120    if (hint == small_range && end - beg == 1) {
 121  121      par_at_put(beg, true);
 122  122    } else {
 123  123      if (hint == large_range) {
 124  124        par_at_put_large_range(beg, end, true);
 125  125      } else {
 126  126        par_at_put_range(beg, end, true);
 127  127      }
 128  128    }
 129  129  }
 130  130  
 131  131  inline void BitMap::set_range_of_words(idx_t beg, idx_t end) {
 132  132    bm_word_t* map = _map;
 133  133    for (idx_t i = beg; i < end; ++i) map[i] = ~(uintptr_t)0;
 134  134  }
 135  135  
 136  136  
 137  137  inline void BitMap::clear_range_of_words(idx_t beg, idx_t end) {
 138  138    bm_word_t* map = _map;
 139  139    for (idx_t i = beg; i < end; ++i) map[i] = 0;
 140  140  }
 141  141  
 142  142  
 143  143  inline void BitMap::clear() {
 144  144    clear_range_of_words(0, size_in_words());
 145  145  }
 146  146  
 147  147  
 148  148  inline void BitMap::par_clear_range(idx_t beg, idx_t end, RangeSizeHint hint) {
 149  149    if (hint == small_range && end - beg == 1) {
 150  150      par_at_put(beg, false);
 151  151    } else {
 152  152      if (hint == large_range) {
 153  153        par_at_put_large_range(beg, end, false);
 154  154      } else {
 155  155        par_at_put_range(beg, end, false);
 156  156      }
 157  157    }
 158  158  }
 159  159  
 160  160  inline BitMap::idx_t
 161  161  BitMap::get_next_one_offset_inline(idx_t l_offset, idx_t r_offset) const {
 162  162    assert(l_offset <= size(), "BitMap index out of bounds");
 163  163    assert(r_offset <= size(), "BitMap index out of bounds");
 164  164    assert(l_offset <= r_offset, "l_offset > r_offset ?");
 165  165  
 166  166    if (l_offset == r_offset) {
 167  167      return l_offset;
 168  168    }
 169  169    idx_t   index = word_index(l_offset);
 170  170    idx_t r_index = word_index(r_offset-1) + 1;

 171  171    idx_t res_offset = l_offset;
 172  172  
 173  173    // check bits including and to the _left_ of offset's position
 174  174    idx_t pos = bit_in_word(res_offset);
 175  175    idx_t res = map(index) >> pos;
 176  176    if (res != (uintptr_t)NoBits) {
 177  177      // find the position of the 1-bit
 178  178      for (; !(res & 1); res_offset++) {
 179  179        res = res >> 1;
 180  180      }
 181      -    assert(res_offset >= l_offset &&
 182      -           res_offset < r_offset, "just checking");
      181 +
      182 +    // In the following assert, checking that res_offset is strictly
      183 +    // less than r_offset is too strong. Consider the case where
      184 +    // l_offset is bit 15 and r_offset is bit 17 of the same map word,
      185 +    // and where bits [18:17:16:15] == [01:00:00:00]. The calculation
      186 +    // above would yield the offset of bit 18. All we can assert is that
      187 +    // res_offset is strictly less than size() since we know that there
      188 +    // are set bits at offsets above, but in the same map word as, r_offset
      189 +    // The bits in the range (r_offset:l_offset] are all 0.
      190 +    assert(res_offset >= l_offset && res_offset < size(), "just checking");
 183  191      return MIN2(res_offset, r_offset);
 184  192    }
 185  193    // skip over all word length 0-bit runs
 186  194    for (index++; index < r_index; index++) {
 187  195      res = map(index);
 188  196      if (res != (uintptr_t)NoBits) {
 189  197        // found a 1, return the offset
 190  198        for (res_offset = bit_index(index); !(res & 1); res_offset++) {
 191  199          res = res >> 1;
 192  200        }

 193  201        assert(res & 1, "tautology; see loop condition");
 194  202        assert(res_offset >= l_offset, "just checking");
 195  203        return MIN2(res_offset, r_offset);
 196  204      }
 197  205    }
 198  206    return r_offset;
 199  207  }
 200  208  
 201  209  inline BitMap::idx_t
 202  210  BitMap::get_next_zero_offset_inline(idx_t l_offset, idx_t r_offset) const {
 203  211    assert(l_offset <= size(), "BitMap index out of bounds");
 204  212    assert(r_offset <= size(), "BitMap index out of bounds");
 205  213    assert(l_offset <= r_offset, "l_offset > r_offset ?");
 206  214  
 207  215    if (l_offset == r_offset) {
 208  216      return l_offset;
 209  217    }
 210  218    idx_t   index = word_index(l_offset);
 211  219    idx_t r_index = word_index(r_offset-1) + 1;
 212  220    idx_t res_offset = l_offset;
 213  221  
 214  222    // check bits including and to the _left_ of offset's position
 215  223    idx_t pos = res_offset & (BitsPerWord - 1);
 216  224    idx_t res = (map(index) >> pos) | left_n_bits((int)pos);
 217  225  
 218  226    if (res != (uintptr_t)AllBits) {
 219  227      // find the position of the 0-bit
 220  228      for (; res & 1; res_offset++) {
 221  229        res = res >> 1;
 222  230      }
 223  231      assert(res_offset >= l_offset, "just checking");
 224  232      return MIN2(res_offset, r_offset);
 225  233    }
 226  234    // skip over all word length 1-bit runs
 227  235    for (index++; index < r_index; index++) {
 228  236      res = map(index);
 229  237      if (res != (uintptr_t)AllBits) {
 230  238        // found a 0, return the offset
 231  239        for (res_offset = index << LogBitsPerWord; res & 1;
 232  240             res_offset++) {
 233  241          res = res >> 1;
 234  242        }
 235  243        assert(!(res & 1), "tautology; see loop condition");
 236  244        assert(res_offset >= l_offset, "just checking");
 237  245        return MIN2(res_offset, r_offset);
 238  246      }
 239  247    }
 240  248    return r_offset;
 241  249  }
 242  250  
 243  251  inline BitMap::idx_t
 244  252  BitMap::get_next_one_offset_inline_aligned_right(idx_t l_offset,
 245  253                                                   idx_t r_offset) const
 246  254  {
 247  255    verify_range(l_offset, r_offset);
 248  256    assert(bit_in_word(r_offset) == 0, "r_offset not word-aligned");
 249  257  
 250  258    if (l_offset == r_offset) {
 251  259      return l_offset;
 252  260    }
 253  261    idx_t   index = word_index(l_offset);
 254  262    idx_t r_index = word_index(r_offset);
 255  263    idx_t res_offset = l_offset;
 256  264  
 257  265    // check bits including and to the _left_ of offset's position
 258  266    idx_t res = map(index) >> bit_in_word(res_offset);
 259  267    if (res != (uintptr_t)NoBits) {
 260  268      // find the position of the 1-bit
 261  269      for (; !(res & 1); res_offset++) {
 262  270        res = res >> 1;
 263  271      }
 264  272      assert(res_offset >= l_offset &&
 265  273             res_offset < r_offset, "just checking");
 266  274      return res_offset;
 267  275    }
 268  276    // skip over all word length 0-bit runs
 269  277    for (index++; index < r_index; index++) {
 270  278      res = map(index);
 271  279      if (res != (uintptr_t)NoBits) {
 272  280        // found a 1, return the offset
 273  281        for (res_offset = bit_index(index); !(res & 1); res_offset++) {
 274  282          res = res >> 1;
 275  283        }
 276  284        assert(res & 1, "tautology; see loop condition");
 277  285        assert(res_offset >= l_offset && res_offset < r_offset, "just checking");
 278  286        return res_offset;
 279  287      }
 280  288    }
 281  289    return r_offset;
 282  290  }
 283  291  
 284  292  
 285  293  // Returns a bit mask for a range of bits [beg, end) within a single word.  Each
 286  294  // bit in the mask is 0 if the bit is in the range, 1 if not in the range.  The
 287  295  // returned mask can be used directly to clear the range, or inverted to set the
 288  296  // range.  Note:  end must not be 0.
 289  297  inline BitMap::bm_word_t
 290  298  BitMap::inverted_bit_mask_for_range(idx_t beg, idx_t end) const {
 291  299    assert(end != 0, "does not work when end == 0");
 292  300    assert(beg == end || word_index(beg) == word_index(end - 1),
 293  301           "must be a single-word range");
 294  302    bm_word_t mask = bit_mask(beg) - 1;   // low (right) bits
 295  303    if (bit_in_word(end) != 0) {
 296  304      mask |= ~(bit_mask(end) - 1);       // high (left) bits
 297  305    }
 298  306    return mask;
 299  307  }
 300  308  
 301  309  inline void BitMap::set_large_range_of_words(idx_t beg, idx_t end) {
 302  310    memset(_map + beg, ~(unsigned char)0, (end - beg) * sizeof(uintptr_t));
 303  311  }
 304  312  
 305  313  inline void BitMap::clear_large_range_of_words(idx_t beg, idx_t end) {
 306  314    memset(_map + beg, 0, (end - beg) * sizeof(uintptr_t));
 307  315  }
 308  316  
 309  317  inline BitMap::idx_t BitMap::word_index_round_up(idx_t bit) const {
 310  318    idx_t bit_rounded_up = bit + (BitsPerWord - 1);
 311  319    // Check for integer arithmetic overflow.
 312  320    return bit_rounded_up > bit ? word_index(bit_rounded_up) : size_in_words();
 313  321  }
 314  322  
 315  323  inline BitMap::idx_t BitMap::get_next_one_offset(idx_t l_offset,
 316  324                                            idx_t r_offset) const {
 317  325    return get_next_one_offset_inline(l_offset, r_offset);
 318  326  }
 319  327  
 320  328  inline BitMap::idx_t BitMap::get_next_zero_offset(idx_t l_offset,
 321  329                                             idx_t r_offset) const {
 322  330    return get_next_zero_offset_inline(l_offset, r_offset);
 323  331  }
 324  332  
 325  333  inline void BitMap2D::clear() {
 326  334    _map.clear();
 327  335  }
 328  336  
 329  337  #endif // SHARE_VM_UTILITIES_BITMAP_INLINE_HPP

XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX