| /* |
| * Copyright (c) 1998, 2011, 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 |
| * under the terms of the GNU General Public License version 2 only, as |
| * published by the Free Software Foundation. |
| * |
| * This code is distributed in the hope that it will be useful, but WITHOUT |
| * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
| * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
| * version 2 for more details (a copy is included in the LICENSE file that |
| * accompanied this code). |
| * |
| * You should have received a copy of the GNU General Public License version |
| * 2 along with this work; if not, write to the Free Software Foundation, |
| * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
| * |
| * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
| * or visit www.oracle.com if you need additional information or have any |
| * questions. |
| * |
| */ |
| |
| #ifndef SHARE_VM_OPTO_INDEXSET_HPP |
| #define SHARE_VM_OPTO_INDEXSET_HPP |
| |
| #include "memory/allocation.hpp" |
| #include "memory/resourceArea.hpp" |
| #include "opto/compile.hpp" |
| #include "opto/regmask.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 |
| // 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 _words[words_per_block]; |
| BitBlock *_next; |
| } _data; |
| |
| // accessors |
| uint32 *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) * 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)(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 bit = (0x1 << bit_index); |
| uint32 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 bit = (0x1 << bit_index); |
| uint32 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 byte _first_bit[table_size]; |
| |
| // For an integer of length window_size, what is the second set bit? |
| static const byte _second_bit[table_size]; |
| |
| private: |
| // The current word we are inspecting |
| uint32 _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 *_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 |