changeset 53961:e5b461681b88

8219922: Simplify and optimize IndexSetIterator::next using count_trailing_zeros Reviewed-by: kvn, neliasso
author redestad
date Thu, 28 Feb 2019 22:11:46 +0100
parents 6c3fd94de35a
children 2653e078b057 7f01a85f2710
files src/hotspot/share/opto/indexSet.cpp src/hotspot/share/opto/indexSet.hpp
diffstat 2 files changed, 6 insertions(+), 90 deletions(-) [+]
line wrap: on
line diff
--- a/src/hotspot/share/opto/indexSet.cpp	Thu Feb 28 13:12:26 2019 -0800
+++ b/src/hotspot/share/opto/indexSet.cpp	Thu Feb 28 22:11:46 2019 +0100
@@ -50,72 +50,6 @@
 int IndexSet::_serial_count = 1;
 #endif
 
-// What is the first set bit in a 5 bit integer?
-const uint8_t IndexSetIterator::_first_bit[32] = {
-  0, 0, 1, 0,
-  2, 0, 1, 0,
-  3, 0, 1, 0,
-  2, 0, 1, 0,
-  4, 0, 1, 0,
-  2, 0, 1, 0,
-  3, 0, 1, 0,
-  2, 0, 1, 0
-};
-
-// What is the second set bit in a 5 bit integer?
-const uint8_t IndexSetIterator::_second_bit[32] = {
-  5, 5, 5, 1,
-  5, 2, 2, 1,
-  5, 3, 3, 1,
-  3, 2, 2, 1,
-  5, 4, 4, 1,
-  4, 2, 2, 1,
-  4, 3, 3, 1,
-  3, 2, 2, 1
-};
-
-// I tried implementing the IndexSetIterator with a window_size of 8 and
-// didn't seem to get a noticeable speedup.  I am leaving in the tables
-// in case we want to switch back.
-
-/*const byte IndexSetIterator::_first_bit[256] = {
-  8, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
-  4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
-  5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
-  4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
-  6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
-  4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
-  5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
-  4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
-  7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
-  4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
-  5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
-  4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
-  6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
-  4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
-  5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
-  4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
-};
-
-const byte IndexSetIterator::_second_bit[256] = {
-  8, 8, 8, 1, 8, 2, 2, 1, 8, 3, 3, 1, 3, 2, 2, 1,
-  8, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
-  8, 5, 5, 1, 5, 2, 2, 1, 5, 3, 3, 1, 3, 2, 2, 1,
-  5, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
-  8, 6, 6, 1, 6, 2, 2, 1, 6, 3, 3, 1, 3, 2, 2, 1,
-  6, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
-  6, 5, 5, 1, 5, 2, 2, 1, 5, 3, 3, 1, 3, 2, 2, 1,
-  5, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
-  8, 7, 7, 1, 7, 2, 2, 1, 7, 3, 3, 1, 3, 2, 2, 1,
-  7, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
-  7, 5, 5, 1, 5, 2, 2, 1, 5, 3, 3, 1, 3, 2, 2, 1,
-  5, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
-  7, 6, 6, 1, 6, 2, 2, 1, 6, 3, 3, 1, 3, 2, 2, 1,
-  6, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
-  6, 5, 5, 1, 5, 2, 2, 1, 5, 3, 3, 1, 3, 2, 2, 1,
-  5, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1
-};*/
-
 //---------------------------- IndexSet::populate_free_list() -----------------------------
 // Populate the free BitBlock list with a batch of BitBlocks.  The BitBlocks
 // are 32 bit aligned.
--- a/src/hotspot/share/opto/indexSet.hpp	Thu Feb 28 13:12:26 2019 -0800
+++ b/src/hotspot/share/opto/indexSet.hpp	Thu Feb 28 22:11:46 2019 +0100
@@ -29,6 +29,7 @@
 #include "memory/resourceArea.hpp"
 #include "opto/compile.hpp"
 #include "opto/regmask.hpp"
+#include "utilities/count_trailing_zeros.hpp"
 
 // This file defines the IndexSet class, a set of sparse integer indices.
 // This data structure is used by the compiler in its liveness analysis and
@@ -396,19 +397,6 @@
 class IndexSetIterator {
  friend class IndexSet;
 
- public:
-
-  // We walk over the bits in a word in chunks of size window_size.
-  enum { window_size = 5,
-         window_mask = right_n_bits(window_size),
-         table_size  = (1 << window_size) };
-
-  // For an integer of length window_size, what is the first set bit?
-  static const uint8_t _first_bit[table_size];
-
-  // For an integer of length window_size, what is the second set bit?
-  static const uint8_t _second_bit[table_size];
-
  private:
   // The current word we are inspecting
   uint32_t              _current;
@@ -440,7 +428,6 @@
   // element in the set.
   uint advance_and_next();
 
-
  public:
 
   // If an iterator is built from a constant set then empty blocks
@@ -452,16 +439,11 @@
   uint next() {
     uint current = _current;
     if (current != 0) {
-      uint value = _value;
-      while (mask_bits(current,window_mask) == 0) {
-        current >>= window_size;
-        value += window_size;
-      }
-
-      uint advance = _second_bit[mask_bits(current,window_mask)];
-      _current = current >> advance;
-      _value = value + advance;
-      return value + _first_bit[mask_bits(current,window_mask)];
+      uint advance = count_trailing_zeros(current);
+      assert((current >> advance) & 0x1 == 1, "sanity");
+      _current = (current >> advance) - 1;
+      _value += advance;
+      return _value;
     } else {
       return advance_and_next();
     }