aoqi@0: /*
aoqi@0:  * Copyright (c) 1998, 2011, Oracle and/or its affiliates. All rights reserved.
aoqi@0:  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
aoqi@0:  *
aoqi@0:  * This code is free software; you can redistribute it and/or modify it
aoqi@0:  * under the terms of the GNU General Public License version 2 only, as
aoqi@0:  * published by the Free Software Foundation.
aoqi@0:  *
aoqi@0:  * This code is distributed in the hope that it will be useful, but WITHOUT
aoqi@0:  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
aoqi@0:  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
aoqi@0:  * version 2 for more details (a copy is included in the LICENSE file that
aoqi@0:  * accompanied this code).
aoqi@0:  *
aoqi@0:  * You should have received a copy of the GNU General Public License version
aoqi@0:  * 2 along with this work; if not, write to the Free Software Foundation,
aoqi@0:  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
aoqi@0:  *
aoqi@0:  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
aoqi@0:  * or visit www.oracle.com if you need additional information or have any
aoqi@0:  * questions.
aoqi@0:  *
aoqi@0:  */
aoqi@0: 
aoqi@0: #ifndef SHARE_VM_OPTO_INDEXSET_HPP
aoqi@0: #define SHARE_VM_OPTO_INDEXSET_HPP
aoqi@0: 
aoqi@0: #include "memory/allocation.hpp"
aoqi@0: #include "memory/resourceArea.hpp"
aoqi@0: #include "opto/compile.hpp"
aoqi@0: #include "opto/regmask.hpp"
aoqi@0: 
aoqi@0: // This file defines the IndexSet class, a set of sparse integer indices.
aoqi@0: // This data structure is used by the compiler in its liveness analysis and
aoqi@0: // during register allocation.
aoqi@0: 
aoqi@0: //-------------------------------- class IndexSet ----------------------------
aoqi@0: // An IndexSet is a piece-wise bitvector.  At the top level, we have an array
aoqi@0: // of pointers to bitvector chunks called BitBlocks.  Each BitBlock has a fixed
aoqi@0: // size and is allocated from a shared free list.  The bits which are set in
aoqi@0: // each BitBlock correspond to the elements of the set.
aoqi@0: 
aoqi@0: class IndexSet : public ResourceObj {
aoqi@0:  friend class IndexSetIterator;
aoqi@0: 
aoqi@0:  public:
aoqi@0:   // When we allocate an IndexSet, it starts off with an array of top level block
aoqi@0:   // pointers of a set length.  This size is intended to be large enough for the
aoqi@0:   // majority of IndexSets.  In the cases when this size is not large enough,
aoqi@0:   // a separately allocated array is used.
aoqi@0: 
aoqi@0:   // The length of the preallocated top level block array
aoqi@0:   enum { preallocated_block_list_size = 16 };
aoqi@0: 
aoqi@0:   // Elements of a IndexSet get decomposed into three fields.  The highest order
aoqi@0:   // bits are the block index, which tell which high level block holds the element.
aoqi@0:   // Within that block, the word index indicates which word holds the element.
aoqi@0:   // Finally, the bit index determines which single bit within that word indicates
aoqi@0:   // membership of the element in the set.
aoqi@0: 
aoqi@0:   // The lengths of the index bitfields
aoqi@0:   enum { bit_index_length = 5,
aoqi@0:          word_index_length = 3,
aoqi@0:          block_index_length = 8 // not used
aoqi@0:   };
aoqi@0: 
aoqi@0:   // Derived constants used for manipulating the index bitfields
aoqi@0:   enum {
aoqi@0:          bit_index_offset = 0, // not used
aoqi@0:          word_index_offset = bit_index_length,
aoqi@0:          block_index_offset = bit_index_length + word_index_length,
aoqi@0: 
aoqi@0:          bits_per_word = 1 << bit_index_length,
aoqi@0:          words_per_block = 1 << word_index_length,
aoqi@0:          bits_per_block = bits_per_word * words_per_block,
aoqi@0: 
aoqi@0:          bit_index_mask = right_n_bits(bit_index_length),
aoqi@0:          word_index_mask = right_n_bits(word_index_length)
aoqi@0:   };
aoqi@0: 
aoqi@0:   // These routines are used for extracting the block, word, and bit index
aoqi@0:   // from an element.
aoqi@0:   static uint get_block_index(uint element) {
aoqi@0:     return element >> block_index_offset;
aoqi@0:   }
aoqi@0:   static uint get_word_index(uint element) {
aoqi@0:     return mask_bits(element >> word_index_offset,word_index_mask);
aoqi@0:   }
aoqi@0:   static uint get_bit_index(uint element) {
aoqi@0:     return mask_bits(element,bit_index_mask);
aoqi@0:   }
aoqi@0: 
aoqi@0:   //------------------------------ class BitBlock ----------------------------
aoqi@0:   // The BitBlock class is a segment of a bitvector set.
aoqi@0: 
aoqi@0:   class BitBlock : public ResourceObj {
aoqi@0:    friend class IndexSetIterator;
aoqi@0:    friend class IndexSet;
aoqi@0: 
aoqi@0:    private:
aoqi@0:     // All of BitBlocks fields and methods are declared private.  We limit
aoqi@0:     // access to IndexSet and IndexSetIterator.
aoqi@0: 
aoqi@0:     // A BitBlock is composed of some number of 32 bit words.  When a BitBlock
aoqi@0:     // is not in use by any IndexSet, it is stored on a free list.  The next field
aoqi@0:     // is used by IndexSet to mainting this free list.
aoqi@0: 
aoqi@0:     union {
aoqi@0:       uint32 _words[words_per_block];
aoqi@0:       BitBlock *_next;
aoqi@0:     } _data;
aoqi@0: 
aoqi@0:     // accessors
aoqi@0:     uint32 *words() { return _data._words; }
aoqi@0:     void set_next(BitBlock *next) { _data._next = next; }
aoqi@0:     BitBlock *next() { return _data._next; }
aoqi@0: 
aoqi@0:     // Operations.  A BitBlock supports four simple operations,
aoqi@0:     // clear(), member(), insert(), and remove().  These methods do
aoqi@0:     // not assume that the block index has been masked out.
aoqi@0: 
aoqi@0:     void clear() {
aoqi@0:       memset(words(), 0, sizeof(uint32) * words_per_block);
aoqi@0:     }
aoqi@0: 
aoqi@0:     bool member(uint element) {
aoqi@0:       uint word_index = IndexSet::get_word_index(element);
aoqi@0:       uint bit_index = IndexSet::get_bit_index(element);
aoqi@0: 
aoqi@0:       return ((words()[word_index] & (uint32)(0x1 << bit_index)) != 0);
aoqi@0:     }
aoqi@0: 
aoqi@0:     bool insert(uint element) {
aoqi@0:       uint word_index = IndexSet::get_word_index(element);
aoqi@0:       uint bit_index = IndexSet::get_bit_index(element);
aoqi@0: 
aoqi@0:       uint32 bit = (0x1 << bit_index);
aoqi@0:       uint32 before = words()[word_index];
aoqi@0:       words()[word_index] = before | bit;
aoqi@0:       return ((before & bit) != 0);
aoqi@0:     }
aoqi@0: 
aoqi@0:     bool remove(uint element) {
aoqi@0:       uint word_index = IndexSet::get_word_index(element);
aoqi@0:       uint bit_index = IndexSet::get_bit_index(element);
aoqi@0: 
aoqi@0:       uint32 bit = (0x1 << bit_index);
aoqi@0:       uint32 before = words()[word_index];
aoqi@0:       words()[word_index] = before & ~bit;
aoqi@0:       return ((before & bit) != 0);
aoqi@0:     }
aoqi@0:   };
aoqi@0: 
aoqi@0:   //-------------------------- BitBlock allocation ---------------------------
aoqi@0:  private:
aoqi@0: 
aoqi@0:   // All IndexSets share an arena from which they allocate BitBlocks.  Unused
aoqi@0:   // BitBlocks are placed on a free list.
aoqi@0: 
aoqi@0:   // The number of BitBlocks to allocate at a time
aoqi@0:   enum { bitblock_alloc_chunk_size = 50 };
aoqi@0: 
aoqi@0:   static Arena *arena() { return Compile::current()->indexSet_arena(); }
aoqi@0: 
aoqi@0:   static void populate_free_list();
aoqi@0: 
aoqi@0:  public:
aoqi@0: 
aoqi@0:   // Invalidate the current free BitBlock list and begin allocation
aoqi@0:   // from a new arena.  It is essential that this method is called whenever
aoqi@0:   // the Arena being used for BitBlock allocation is reset.
aoqi@0:   static void reset_memory(Compile* compile, Arena *arena) {
aoqi@0:     compile->set_indexSet_free_block_list(NULL);
aoqi@0:     compile->set_indexSet_arena(arena);
aoqi@0: 
aoqi@0:    // This should probably be done in a static initializer
aoqi@0:    _empty_block.clear();
aoqi@0:   }
aoqi@0: 
aoqi@0:  private:
aoqi@0:   friend class BitBlock;
aoqi@0:   // A distinguished BitBlock which always remains empty.  When a new IndexSet is
aoqi@0:   // created, all of its top level BitBlock pointers are initialized to point to
aoqi@0:   // this.
aoqi@0:   static BitBlock _empty_block;
aoqi@0: 
aoqi@0:   //-------------------------- Members ------------------------------------------
aoqi@0: 
aoqi@0:   // The number of elements in the set
aoqi@0:   uint      _count;
aoqi@0: 
aoqi@0:   // Our top level array of bitvector segments
aoqi@0:   BitBlock **_blocks;
aoqi@0: 
aoqi@0:   BitBlock  *_preallocated_block_list[preallocated_block_list_size];
aoqi@0: 
aoqi@0:   // The number of top level array entries in use
aoqi@0:   uint       _max_blocks;
aoqi@0: 
aoqi@0:   // Our assertions need to know the maximum number allowed in the set
aoqi@0: #ifdef ASSERT
aoqi@0:   uint       _max_elements;
aoqi@0: #endif
aoqi@0: 
aoqi@0:   // The next IndexSet on the free list (not used at same time as count)
aoqi@0:   IndexSet *_next;
aoqi@0: 
aoqi@0:  public:
aoqi@0:   //-------------------------- Free list operations ------------------------------
aoqi@0:   // Individual IndexSets can be placed on a free list.  This is done in PhaseLive.
aoqi@0: 
aoqi@0:   IndexSet *next() {
aoqi@0: #ifdef ASSERT
aoqi@0:     if( VerifyOpto ) {
aoqi@0:       check_watch("removed from free list?", ((_next == NULL) ? 0 : _next->_serial_number));
aoqi@0:     }
aoqi@0: #endif
aoqi@0:     return _next;
aoqi@0:   }
aoqi@0: 
aoqi@0:   void set_next(IndexSet *next) {
aoqi@0: #ifdef ASSERT
aoqi@0:     if( VerifyOpto ) {
aoqi@0:       check_watch("put on free list?", ((next == NULL) ? 0 : next->_serial_number));
aoqi@0:     }
aoqi@0: #endif
aoqi@0:     _next = next;
aoqi@0:   }
aoqi@0: 
aoqi@0:  private:
aoqi@0:   //-------------------------- Utility methods -----------------------------------
aoqi@0: 
aoqi@0:   // Get the block which holds element
aoqi@0:   BitBlock *get_block_containing(uint element) const {
aoqi@0:     assert(element < _max_elements, "element out of bounds");
aoqi@0:     return _blocks[get_block_index(element)];
aoqi@0:   }
aoqi@0: 
aoqi@0:   // Set a block in the top level array
aoqi@0:   void set_block(uint index, BitBlock *block) {
aoqi@0: #ifdef ASSERT
aoqi@0:     if( VerifyOpto )
aoqi@0:       check_watch("set block", index);
aoqi@0: #endif
aoqi@0:     _blocks[index] = block;
aoqi@0:   }
aoqi@0: 
aoqi@0:   // Get a BitBlock from the free list
aoqi@0:   BitBlock *alloc_block();
aoqi@0: 
aoqi@0:   // Get a BitBlock from the free list and place it in the top level array
aoqi@0:   BitBlock *alloc_block_containing(uint element);
aoqi@0: 
aoqi@0:   // Free a block from the top level array, placing it on the free BitBlock list
aoqi@0:   void free_block(uint i);
aoqi@0: 
aoqi@0:  public:
aoqi@0:   //-------------------------- Primitive set operations --------------------------
aoqi@0: 
aoqi@0:   void clear() {
aoqi@0: #ifdef ASSERT
aoqi@0:     if( VerifyOpto )
aoqi@0:       check_watch("clear");
aoqi@0: #endif
aoqi@0:     _count = 0;
aoqi@0:     for (uint i = 0; i < _max_blocks; i++) {
aoqi@0:       BitBlock *block = _blocks[i];
aoqi@0:       if (block != &_empty_block) {
aoqi@0:         free_block(i);
aoqi@0:       }
aoqi@0:     }
aoqi@0:   }
aoqi@0: 
aoqi@0:   uint count() const { return _count; }
aoqi@0: 
aoqi@0:   bool is_empty() const { return _count == 0; }
aoqi@0: 
aoqi@0:   bool member(uint element) const {
aoqi@0:     return get_block_containing(element)->member(element);
aoqi@0:   }
aoqi@0: 
aoqi@0:   bool insert(uint element) {
aoqi@0: #ifdef ASSERT
aoqi@0:     if( VerifyOpto )
aoqi@0:       check_watch("insert", element);
aoqi@0: #endif
aoqi@0:     if (element == 0) {
aoqi@0:       return 0;
aoqi@0:     }
aoqi@0:     BitBlock *block = get_block_containing(element);
aoqi@0:     if (block == &_empty_block) {
aoqi@0:       block = alloc_block_containing(element);
aoqi@0:     }
aoqi@0:     bool present = block->insert(element);
aoqi@0:     if (!present) {
aoqi@0:       _count++;
aoqi@0:     }
aoqi@0:     return !present;
aoqi@0:   }
aoqi@0: 
aoqi@0:   bool remove(uint element) {
aoqi@0: #ifdef ASSERT
aoqi@0:     if( VerifyOpto )
aoqi@0:       check_watch("remove", element);
aoqi@0: #endif
aoqi@0: 
aoqi@0:     BitBlock *block = get_block_containing(element);
aoqi@0:     bool present = block->remove(element);
aoqi@0:     if (present) {
aoqi@0:       _count--;
aoqi@0:     }
aoqi@0:     return present;
aoqi@0:   }
aoqi@0: 
aoqi@0:   //-------------------------- Compound set operations ------------------------
aoqi@0:   // Compute the union of all elements of one and two which interfere
aoqi@0:   // with the RegMask mask.  If the degree of the union becomes
aoqi@0:   // exceeds fail_degree, the union bails out.  The underlying set is
aoqi@0:   // cleared before the union is performed.
aoqi@0:   uint lrg_union(uint lr1, uint lr2,
aoqi@0:                  const uint fail_degree,
aoqi@0:                  const class PhaseIFG *ifg,
aoqi@0:                  const RegMask &mask);
aoqi@0: 
aoqi@0: 
aoqi@0:   //------------------------- Construction, initialization -----------------------
aoqi@0: 
aoqi@0:   IndexSet() {}
aoqi@0: 
aoqi@0:   // This constructor is used for making a deep copy of a IndexSet.
aoqi@0:   IndexSet(IndexSet *set);
aoqi@0: 
aoqi@0:   // Perform initialization on a IndexSet
aoqi@0:   void initialize(uint max_element);
aoqi@0: 
aoqi@0:   // Initialize a IndexSet.  If the top level BitBlock array needs to be
aoqi@0:   // allocated, do it from the proffered arena.  BitBlocks are still allocated
aoqi@0:   // from the static Arena member.
aoqi@0:   void initialize(uint max_element, Arena *arena);
aoqi@0: 
aoqi@0:   // Exchange two sets
aoqi@0:   void swap(IndexSet *set);
aoqi@0: 
aoqi@0:   //-------------------------- Debugging and statistics --------------------------
aoqi@0: 
aoqi@0: #ifndef PRODUCT
aoqi@0:   // Output a IndexSet for debugging
aoqi@0:   void dump() const;
aoqi@0: #endif
aoqi@0: 
aoqi@0: #ifdef ASSERT
aoqi@0:   void tally_iteration_statistics() const;
aoqi@0: 
aoqi@0:   // BitBlock allocation statistics
aoqi@0:   static julong _alloc_new;
aoqi@0:   static julong _alloc_total;
aoqi@0: 
aoqi@0:   // Block density statistics
aoqi@0:   static julong _total_bits;
aoqi@0:   static julong _total_used_blocks;
aoqi@0:   static julong _total_unused_blocks;
aoqi@0: 
aoqi@0:   // Sanity tests
aoqi@0:   void verify() const;
aoqi@0: 
aoqi@0:   static int _serial_count;
aoqi@0:   int        _serial_number;
aoqi@0: 
aoqi@0:   // Check to see if the serial number of the current set is the one we're tracing.
aoqi@0:   // If it is, print a message.
aoqi@0:   void check_watch(const char *operation, uint operand) const {
aoqi@0:     if (IndexSetWatch != 0) {
aoqi@0:       if (IndexSetWatch == -1 || _serial_number == IndexSetWatch) {
aoqi@0:         tty->print_cr("IndexSet %d : %s ( %d )", _serial_number, operation, operand);
aoqi@0:       }
aoqi@0:     }
aoqi@0:   }
aoqi@0:   void check_watch(const char *operation) const {
aoqi@0:     if (IndexSetWatch != 0) {
aoqi@0:       if (IndexSetWatch == -1 || _serial_number == IndexSetWatch) {
aoqi@0:         tty->print_cr("IndexSet %d : %s", _serial_number, operation);
aoqi@0:       }
aoqi@0:     }
aoqi@0:   }
aoqi@0: 
aoqi@0:  public:
aoqi@0:   static void print_statistics();
aoqi@0: 
aoqi@0: #endif
aoqi@0: };
aoqi@0: 
aoqi@0: 
aoqi@0: //-------------------------------- class IndexSetIterator --------------------
aoqi@0: // An iterator for IndexSets.
aoqi@0: 
aoqi@0: class IndexSetIterator VALUE_OBJ_CLASS_SPEC {
aoqi@0:  friend class IndexSet;
aoqi@0: 
aoqi@0:  public:
aoqi@0: 
aoqi@0:   // We walk over the bits in a word in chunks of size window_size.
aoqi@0:   enum { window_size = 5,
aoqi@0:          window_mask = right_n_bits(window_size),
aoqi@0:          table_size  = (1 << window_size) };
aoqi@0: 
aoqi@0:   // For an integer of length window_size, what is the first set bit?
aoqi@0:   static const byte _first_bit[table_size];
aoqi@0: 
aoqi@0:   // For an integer of length window_size, what is the second set bit?
aoqi@0:   static const byte _second_bit[table_size];
aoqi@0: 
aoqi@0:  private:
aoqi@0:   // The current word we are inspecting
aoqi@0:   uint32                _current;
aoqi@0: 
aoqi@0:   // What element number are we currently on?
aoqi@0:   uint                  _value;
aoqi@0: 
aoqi@0:   // The index of the next word we will inspect
aoqi@0:   uint                  _next_word;
aoqi@0: 
aoqi@0:   // A pointer to the contents of the current block
aoqi@0:   uint32               *_words;
aoqi@0: 
aoqi@0:   // The index of the next block we will inspect
aoqi@0:   uint                  _next_block;
aoqi@0: 
aoqi@0:   // A pointer to the blocks in our set
aoqi@0:   IndexSet::BitBlock **_blocks;
aoqi@0: 
aoqi@0:   // The number of blocks in the set
aoqi@0:   uint                  _max_blocks;
aoqi@0: 
aoqi@0:   // If the iterator was created from a non-const set, we replace
aoqi@0:   // non-canonical empty blocks with the _empty_block pointer.  If
aoqi@0:   // _set is NULL, we do no replacement.
aoqi@0:   IndexSet            *_set;
aoqi@0: 
aoqi@0:   // Advance to the next non-empty word and return the next
aoqi@0:   // element in the set.
aoqi@0:   uint advance_and_next();
aoqi@0: 
aoqi@0: 
aoqi@0:  public:
aoqi@0: 
aoqi@0:   // If an iterator is built from a constant set then empty blocks
aoqi@0:   // are not canonicalized.
aoqi@0:   IndexSetIterator(IndexSet *set);
aoqi@0:   IndexSetIterator(const IndexSet *set);
aoqi@0: 
aoqi@0:   // Return the next element of the set.  Return 0 when done.
aoqi@0:   uint next() {
aoqi@0:     uint current = _current;
aoqi@0:     if (current != 0) {
aoqi@0:       uint value = _value;
aoqi@0:       while (mask_bits(current,window_mask) == 0) {
aoqi@0:         current >>= window_size;
aoqi@0:         value += window_size;
aoqi@0:       }
aoqi@0: 
aoqi@0:       uint advance = _second_bit[mask_bits(current,window_mask)];
aoqi@0:       _current = current >> advance;
aoqi@0:       _value = value + advance;
aoqi@0:       return value + _first_bit[mask_bits(current,window_mask)];
aoqi@0:     } else {
aoqi@0:       return advance_and_next();
aoqi@0:     }
aoqi@0:   }
aoqi@0: };
aoqi@0: 
aoqi@0: #endif // SHARE_VM_OPTO_INDEXSET_HPP