src/share/vm/opto/indexSet.hpp
Print this page
*** 33,471 ****
// 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
// during register allocation.
//-------------------------------- class IndexSet ----------------------------
! // An IndexSet is a piece-wise bitvector. At the top level, we have an array
! // of pointers to bitvector chunks called BitBlocks. Each BitBlock has a fixed
! // size and is allocated from a shared free list. The bits which are set in
! // each BitBlock correspond to the elements of the set.
class IndexSet : public ResourceObj {
friend class IndexSetIterator;
- public:
- // When we allocate an IndexSet, it starts off with an array of top level block
- // pointers of a set length. This size is intended to be large enough for the
- // majority of IndexSets. In the cases when this size is not large enough,
- // a separately allocated array is used.
-
- // The length of the preallocated top level block array
- enum { preallocated_block_list_size = 16 };
-
- // Elements of a IndexSet get decomposed into three fields. The highest order
- // bits are the block index, which tell which high level block holds the element.
- // Within that block, the word index indicates which word holds the element.
- // Finally, the bit index determines which single bit within that word indicates
- // membership of the element in the set.
-
- // The lengths of the index bitfields
- enum { bit_index_length = 5,
- word_index_length = 3,
- block_index_length = 8 // not used
- };
-
- // Derived constants used for manipulating the index bitfields
- enum {
- bit_index_offset = 0, // not used
- word_index_offset = bit_index_length,
- block_index_offset = bit_index_length + word_index_length,
-
- bits_per_word = 1 << bit_index_length,
- words_per_block = 1 << word_index_length,
- bits_per_block = bits_per_word * words_per_block,
-
- bit_index_mask = right_n_bits(bit_index_length),
- word_index_mask = right_n_bits(word_index_length)
- };
-
- // These routines are used for extracting the block, word, and bit index
- // from an element.
- static uint get_block_index(uint element) {
- return element >> block_index_offset;
- }
- static uint get_word_index(uint element) {
- return mask_bits(element >> word_index_offset,word_index_mask);
- }
- static uint get_bit_index(uint element) {
- return mask_bits(element,bit_index_mask);
- }
-
- //------------------------------ class BitBlock ----------------------------
- // The BitBlock class is a segment of a bitvector set.
-
- class BitBlock : public ResourceObj {
- friend class IndexSetIterator;
- friend class IndexSet;
-
- private:
- // All of BitBlocks fields and methods are declared private. We limit
- // access to IndexSet and IndexSetIterator.
-
- // A BitBlock is composed of some number of 32 bit words. When a BitBlock
- // is not in use by any IndexSet, it is stored on a free list. The next field
- // is used by IndexSet to mainting this free list.
-
- union {
- uint32_t _words[words_per_block];
- BitBlock *_next;
- } _data;
-
- // accessors
- uint32_t* words() { return _data._words; }
- void set_next(BitBlock *next) { _data._next = next; }
- BitBlock *next() { return _data._next; }
-
- // Operations. A BitBlock supports four simple operations,
- // clear(), member(), insert(), and remove(). These methods do
- // not assume that the block index has been masked out.
-
- void clear() {
- memset(words(), 0, sizeof(uint32_t) * words_per_block);
- }
-
- bool member(uint element) {
- uint word_index = IndexSet::get_word_index(element);
- uint bit_index = IndexSet::get_bit_index(element);
-
- return ((words()[word_index] & (uint32_t)(0x1 << bit_index)) != 0);
- }
-
- bool insert(uint element) {
- uint word_index = IndexSet::get_word_index(element);
- uint bit_index = IndexSet::get_bit_index(element);
-
- uint32_t bit = (0x1 << bit_index);
- uint32_t before = words()[word_index];
- words()[word_index] = before | bit;
- return ((before & bit) != 0);
- }
-
- bool remove(uint element) {
- uint word_index = IndexSet::get_word_index(element);
- uint bit_index = IndexSet::get_bit_index(element);
-
- uint32_t bit = (0x1 << bit_index);
- uint32_t before = words()[word_index];
- words()[word_index] = before & ~bit;
- return ((before & bit) != 0);
- }
- };
-
- //-------------------------- BitBlock allocation ---------------------------
- private:
-
- // All IndexSets share an arena from which they allocate BitBlocks. Unused
- // BitBlocks are placed on a free list.
-
- // The number of BitBlocks to allocate at a time
- enum { bitblock_alloc_chunk_size = 50 };
-
- static Arena *arena() { return Compile::current()->indexSet_arena(); }
-
- static void populate_free_list();
-
- public:
-
- // Invalidate the current free BitBlock list and begin allocation
- // from a new arena. It is essential that this method is called whenever
- // the Arena being used for BitBlock allocation is reset.
- static void reset_memory(Compile* compile, Arena *arena) {
- compile->set_indexSet_free_block_list(NULL);
- compile->set_indexSet_arena(arena);
-
- // This should probably be done in a static initializer
- _empty_block.clear();
- }
-
- private:
- friend class BitBlock;
- // A distinguished BitBlock which always remains empty. When a new IndexSet is
- // created, all of its top level BitBlock pointers are initialized to point to
- // this.
- static BitBlock _empty_block;
-
//-------------------------- Members ------------------------------------------
! // The number of elements in the set
! uint _count;
!
! // Our top level array of bitvector segments
! BitBlock **_blocks;
!
! BitBlock *_preallocated_block_list[preallocated_block_list_size];
!
! // The number of top level array entries in use
! uint _max_blocks;
!
! // Our assertions need to know the maximum number allowed in the set
! #ifdef ASSERT
! uint _max_elements;
! #endif
! // The next IndexSet on the free list (not used at same time as count)
IndexSet *_next;
- public:
//-------------------------- Free list operations ------------------------------
// Individual IndexSets can be placed on a free list. This is done in PhaseLive.
! IndexSet *next() {
! #ifdef ASSERT
! if( VerifyOpto ) {
! check_watch("removed from free list?", ((_next == NULL) ? 0 : _next->_serial_number));
! }
! #endif
return _next;
}
! void set_next(IndexSet *next) {
! #ifdef ASSERT
! if( VerifyOpto ) {
! check_watch("put on free list?", ((next == NULL) ? 0 : next->_serial_number));
! }
! #endif
_next = next;
}
- private:
- //-------------------------- Utility methods -----------------------------------
-
- // Get the block which holds element
- BitBlock *get_block_containing(uint element) const {
- assert(element < _max_elements, "element out of bounds");
- return _blocks[get_block_index(element)];
- }
-
- // Set a block in the top level array
- void set_block(uint index, BitBlock *block) {
- #ifdef ASSERT
- if( VerifyOpto )
- check_watch("set block", index);
- #endif
- _blocks[index] = block;
- }
-
- // Get a BitBlock from the free list
- BitBlock *alloc_block();
-
- // Get a BitBlock from the free list and place it in the top level array
- BitBlock *alloc_block_containing(uint element);
-
- // Free a block from the top level array, placing it on the free BitBlock list
- void free_block(uint i);
-
public:
//-------------------------- Primitive set operations --------------------------
! void clear() {
! #ifdef ASSERT
! if( VerifyOpto )
! check_watch("clear");
! #endif
! _count = 0;
! for (uint i = 0; i < _max_blocks; i++) {
! BitBlock *block = _blocks[i];
! if (block != &_empty_block) {
! free_block(i);
! }
! }
}
! uint count() const { return _count; }
! bool is_empty() const { return _count == 0; }
! bool member(uint element) const {
! return get_block_containing(element)->member(element);
}
! bool insert(uint element) {
! #ifdef ASSERT
! if( VerifyOpto )
! check_watch("insert", element);
! #endif
if (element == 0) {
return 0;
}
! BitBlock *block = get_block_containing(element);
! if (block == &_empty_block) {
! block = alloc_block_containing(element);
! }
! bool present = block->insert(element);
! if (!present) {
! _count++;
}
- return !present;
- }
-
- bool remove(uint element) {
- #ifdef ASSERT
- if( VerifyOpto )
- check_watch("remove", element);
- #endif
-
- BitBlock *block = get_block_containing(element);
- bool present = block->remove(element);
- if (present) {
- _count--;
- }
- return present;
- }
-
- //-------------------------- Compound set operations ------------------------
- // Compute the union of all elements of one and two which interfere
- // with the RegMask mask. If the degree of the union becomes
- // exceeds fail_degree, the union bails out. The underlying set is
- // cleared before the union is performed.
- uint lrg_union(uint lr1, uint lr2,
- const uint fail_degree,
- const class PhaseIFG *ifg,
- const RegMask &mask);
//------------------------- Construction, initialization -----------------------
IndexSet() {}
// This constructor is used for making a deep copy of a IndexSet.
! IndexSet(IndexSet *set);
// Perform initialization on a IndexSet
! void initialize(uint max_element);
!
! // Initialize a IndexSet. If the top level BitBlock array needs to be
! // allocated, do it from the proffered arena. BitBlocks are still allocated
! // from the static Arena member.
! void initialize(uint max_element, Arena *arena);
!
! // Exchange two sets
! void swap(IndexSet *set);
!
! //-------------------------- Debugging and statistics --------------------------
!
! #ifndef PRODUCT
! // Output a IndexSet for debugging
! void dump() const;
! #endif
!
! #ifdef ASSERT
! void tally_iteration_statistics() const;
!
! // BitBlock allocation statistics
! static julong _alloc_new;
! static julong _alloc_total;
!
! // Block density statistics
! static julong _total_bits;
! static julong _total_used_blocks;
! static julong _total_unused_blocks;
!
! // Sanity tests
! void verify() const;
!
! static int _serial_count;
! int _serial_number;
! // Check to see if the serial number of the current set is the one we're tracing.
! // If it is, print a message.
! void check_watch(const char *operation, uint operand) const {
! if (IndexSetWatch != 0) {
! if (IndexSetWatch == -1 || _serial_number == IndexSetWatch) {
! tty->print_cr("IndexSet %d : %s ( %d )", _serial_number, operation, operand);
! }
! }
! }
! void check_watch(const char *operation) const {
! if (IndexSetWatch != 0) {
! if (IndexSetWatch == -1 || _serial_number == IndexSetWatch) {
! tty->print_cr("IndexSet %d : %s", _serial_number, operation);
! }
}
- }
-
- public:
- static void print_statistics();
#endif
};
//-------------------------------- class IndexSetIterator --------------------
// An iterator for IndexSets.
! class IndexSetIterator VALUE_OBJ_CLASS_SPEC {
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;
!
! // What element number are we currently on?
! uint _value;
!
! // The index of the next word we will inspect
! uint _next_word;
!
! // A pointer to the contents of the current block
! uint32_t *_words;
!
! // The index of the next block we will inspect
! uint _next_block;
!
! // A pointer to the blocks in our set
! IndexSet::BitBlock **_blocks;
!
! // The number of blocks in the set
! uint _max_blocks;
!
! // If the iterator was created from a non-const set, we replace
! // non-canonical empty blocks with the _empty_block pointer. If
! // _set is NULL, we do no replacement.
! IndexSet *_set;
!
! // Advance to the next non-empty word and return the next
! // element in the set.
! uint advance_and_next();
!
public:
! // If an iterator is built from a constant set then empty blocks
! // are not canonicalized.
! IndexSetIterator(IndexSet *set);
! IndexSetIterator(const IndexSet *set);
!
! // Return the next element of the set. Return 0 when done.
! 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)];
! } else {
! return advance_and_next();
! }
}
};
#endif // SHARE_VM_OPTO_INDEXSET_HPP
--- 33,138 ----
// 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
// during register allocation.
//-------------------------------- class IndexSet ----------------------------
! // An IndexSet is an adapter for high-performance BitMap implementation in
! // VM utility classes. See JDK-8059461 for performance investigation.
class IndexSet : public ResourceObj {
friend class IndexSetIterator;
//-------------------------- Members ------------------------------------------
+ private:
! // Underlying BitMap where we store the values
! BitMap _map;
! // The next IndexSet on the free list
IndexSet *_next;
//-------------------------- Free list operations ------------------------------
// Individual IndexSets can be placed on a free list. This is done in PhaseLive.
+ public:
! inline IndexSet *next() {
return _next;
}
! inline void set_next(IndexSet *next) {
_next = next;
}
public:
//-------------------------- Primitive set operations --------------------------
! inline void clear() {
! _map.clear();
}
! inline uint count() const {
! return (uint)_map.count_one_bits();
! }
! inline bool is_empty() const {
! return _map.is_empty();
! }
! inline bool member(uint element) const {
! return _map.at(element);
}
! inline bool insert(uint element) {
if (element == 0) {
return 0;
}
! return _map.set_bit_with_result(element);
}
+ inline bool remove(uint element) {
+ return _map.clear_bit_with_result(element);
+ }
//------------------------- Construction, initialization -----------------------
IndexSet() {}
// This constructor is used for making a deep copy of a IndexSet.
! IndexSet(IndexSet *set) {
! _map = BitMap(set->_map.size());
! _map.set_from(set->_map);
! };
// Perform initialization on a IndexSet
! inline void initialize(uint max_element) {
! _map = BitMap(max_element);
! };
! // Overwrite current IndexSet with another set
! inline void set_from(IndexSet *set) {
! _map.set_from(set->_map);
}
+ #ifndef PRODUCT
+ void dump();
#endif
};
//-------------------------------- class IndexSetIterator --------------------
// An iterator for IndexSets.
! class IndexSetIterator {
friend class IndexSet;
! BitMapIterator iter;
public:
+ IndexSetIterator(IndexSet *set) : iter(&(set->_map)) {}
! inline uint next() {
! return (uint)iter.next();
}
+
};
#endif // SHARE_VM_OPTO_INDEXSET_HPP