Mercurial > jdk8-mips64-public > hotspot / file revision

 /*

  * Copyright 1998-2005 Sun Microsystems, Inc.  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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,

  * CA 95054 USA or visit www.sun.com if you need additional information or

  * have any questions.

  *

  */

 // 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 uint _alloc_new;

   static uint _alloc_total;

   // Block density statistics

   static long _total_bits;

   static long _total_used_blocks;

   static long _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();

     }

   }

 };