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