--- a/src/hotspot/share/utilities/bitMap.hpp	Fri Nov 02 14:00:29 2018 -0700
+++ b/src/hotspot/share/utilities/bitMap.hpp	Fri Nov 02 17:51:21 2018 -0400
@@ -61,6 +61,17 @@
   bm_word_t* _map;     // First word in bitmap
   idx_t      _size;    // Size of bitmap (in bits)
 
+  // Helper for get_next_{zero,one}_bit variants.
+  // - flip designates whether searching for 1s or 0s.  Must be one of
+  //   find_{zeros,ones}_flip.
+  // - aligned_right is true if r_index is a priori on a bm_word_t boundary.
+  template<bm_word_t flip, bool aligned_right>
+  inline idx_t get_next_bit_impl(idx_t l_index, idx_t r_index) const;
+
+  // Values for get_next_bit_impl flip parameter.
+  static const bm_word_t find_ones_flip = 0;
+  static const bm_word_t find_zeros_flip = ~(bm_word_t)0;
+
  protected:
   // Return the position of bit within the word that contains it (e.g., if
   // bitmap words are 32 bits, return a number 0 <= n <= 31).

--- a/src/hotspot/share/utilities/bitMap.inline.hpp	Fri Nov 02 14:00:29 2018 -0700
+++ b/src/hotspot/share/utilities/bitMap.inline.hpp	Fri Nov 02 17:51:21 2018 -0400
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2005, 2017, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 2005, 2018, 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
@@ -27,6 +27,7 @@
 
 #include "runtime/atomic.hpp"
 #include "utilities/bitMap.hpp"
+#include "utilities/count_trailing_zeros.hpp"
 
 inline void BitMap::set_bit(idx_t bit) {
   verify_index(bit);
@@ -141,152 +142,84 @@
   }
 }
 
+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
+      // poorly with doing this check first; count_trailing_zeros can be
+      // relatively expensive, plus there is the additional range check.
+      // But when the first bit isn't set, the cost of having tested for
+      // it is relatively small compared to the rest of the search.
+      return l_index;
+    } else if (cword != 0) {
+      // Flipped and shifted first word is non-zero.
+      idx_t result = l_index + count_trailing_zeros(cword);
+      if (aligned_right || (result < r_index)) return result;
+      // 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;
+          // Result is beyond range bound; return r_index.
+          assert((index + 1) == limit, "invariant");
+          break;
+        }
+      }
+      // No bits in range; return r_index.
+    }
+  }
+  return r_index;
+}
+
 inline BitMap::idx_t
 BitMap::get_next_one_offset(idx_t l_offset, idx_t r_offset) const {
-  assert(l_offset <= size(), "BitMap index out of bounds");
-  assert(r_offset <= size(), "BitMap index out of bounds");
-  assert(l_offset <= r_offset, "l_offset > r_offset ?");
-
-  if (l_offset == r_offset) {
-    return l_offset;
-  }
-  idx_t   index = word_index(l_offset);
-  idx_t r_index = word_index(r_offset-1) + 1;
-  idx_t res_offset = l_offset;
-
-  // check bits including and to the _left_ of offset's position
-  idx_t pos = bit_in_word(res_offset);
-  bm_word_t res = map(index) >> pos;
-  if (res != 0) {
-    // find the position of the 1-bit
-    for (; !(res & 1); res_offset++) {
-      res = res >> 1;
-    }
-
-#ifdef ASSERT
-    // In the following assert, if r_offset is not bitamp word aligned,
-    // checking that res_offset is strictly less than r_offset is too
-    // strong and will trip the assert.
-    //
-    // Consider the case where l_offset is bit 15 and r_offset is bit 17
-    // of the same map word, and where bits [15:16:17:18] == [00:00:00:01].
-    // All the bits in the range [l_offset:r_offset) are 0.
-    // The loop that calculates res_offset, above, would yield the offset
-    // of bit 18 because it's in the same map word as l_offset and there
-    // is a set bit in that map word above l_offset (i.e. res != NoBits).
-    //
-    // In this case, however, we can assert is that res_offset is strictly
-    // less than size() since we know that there is at least one set bit
-    // at an offset above, but in the same map word as, r_offset.
-    // Otherwise, if r_offset is word aligned then it will not be in the
-    // same map word as l_offset (unless it equals l_offset). So either
-    // there won't be a set bit between l_offset and the end of it's map
-    // word (i.e. res == NoBits), or res_offset will be less than r_offset.
-
-    idx_t limit = is_word_aligned(r_offset) ? r_offset : size();
-    assert(res_offset >= l_offset && res_offset < limit, "just checking");
-#endif // ASSERT
-    return MIN2(res_offset, r_offset);
-  }
-  // skip over all word length 0-bit runs
-  for (index++; index < r_index; index++) {
-    res = map(index);
-    if (res != 0) {
-      // found a 1, return the offset
-      for (res_offset = bit_index(index); !(res & 1); res_offset++) {
-        res = res >> 1;
-      }
-      assert(res & 1, "tautology; see loop condition");
-      assert(res_offset >= l_offset, "just checking");
-      return MIN2(res_offset, r_offset);
-    }
-  }
-  return r_offset;
+  return get_next_bit_impl<find_ones_flip, false>(l_offset, r_offset);
 }
 
 inline BitMap::idx_t
 BitMap::get_next_zero_offset(idx_t l_offset, idx_t r_offset) const {
-  assert(l_offset <= size(), "BitMap index out of bounds");
-  assert(r_offset <= size(), "BitMap index out of bounds");
-  assert(l_offset <= r_offset, "l_offset > r_offset ?");
-
-  if (l_offset == r_offset) {
-    return l_offset;
-  }
-  idx_t   index = word_index(l_offset);
-  idx_t r_index = word_index(r_offset-1) + 1;
-  idx_t res_offset = l_offset;
-
-  // check bits including and to the _left_ of offset's position
-  idx_t pos = bit_in_word(res_offset);
-  bm_word_t res = ~map(index) >> pos; // flip bits and shift for l_offset
-
-  if (res != 0) {
-    // find the position of the 1-bit
-    for (; !(res & 1); res_offset++) {
-      res = res >> 1;
-    }
-    assert(res_offset >= l_offset, "just checking");
-    return MIN2(res_offset, r_offset);
-  }
-  // skip over all word length 1-bit runs
-  for (index++; index < r_index; index++) {
-    res = map(index);
-    if (res != ~(bm_word_t)0) {
-      // found a 0, return the offset
-      for (res_offset = index << LogBitsPerWord; res & 1;
-           res_offset++) {
-        res = res >> 1;
-      }
-      assert(!(res & 1), "tautology; see loop condition");
-      assert(res_offset >= l_offset, "just checking");
-      return MIN2(res_offset, r_offset);
-    }
-  }
-  return r_offset;
+  return get_next_bit_impl<find_zeros_flip, false>(l_offset, r_offset);
 }
 
 inline BitMap::idx_t
-BitMap::get_next_one_offset_aligned_right(idx_t l_offset, idx_t r_offset) const
-{
-  verify_range(l_offset, r_offset);
-  assert(bit_in_word(r_offset) == 0, "r_offset not word-aligned");
-
-  if (l_offset == r_offset) {
-    return l_offset;
-  }
-  idx_t   index = word_index(l_offset);
-  idx_t r_index = word_index(r_offset);
-  idx_t res_offset = l_offset;
-
-  // check bits including and to the _left_ of offset's position
-  bm_word_t res = map(index) >> bit_in_word(res_offset);
-  if (res != 0) {
-    // find the position of the 1-bit
-    for (; !(res & 1); res_offset++) {
-      res = res >> 1;
-    }
-    assert(res_offset >= l_offset &&
-           res_offset < r_offset, "just checking");
-    return res_offset;
-  }
-  // skip over all word length 0-bit runs
-  for (index++; index < r_index; index++) {
-    res = map(index);
-    if (res != 0) {
-      // found a 1, return the offset
-      for (res_offset = bit_index(index); !(res & 1); res_offset++) {
-        res = res >> 1;
-      }
-      assert(res & 1, "tautology; see loop condition");
-      assert(res_offset >= l_offset && res_offset < r_offset, "just checking");
-      return res_offset;
-    }
-  }
-  return r_offset;
+BitMap::get_next_one_offset_aligned_right(idx_t l_offset, idx_t r_offset) const {
+  return get_next_bit_impl<find_ones_flip, true>(l_offset, r_offset);
 }
 
-
 // Returns a bit mask for a range of bits [beg, end) within a single word.  Each
 // bit in the mask is 0 if the bit is in the range, 1 if not in the range.  The
 // returned mask can be used directly to clear the range, or inverted to set the