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