jdk8-mips64-public/hotspot: src/share/vm/opto/indexSet.hpp@7bb995fbd3c0 (annotated)

src/share/vm/opto/indexSet.hpp@7bb995fbd3c0 (annotated)

src/share/vm/opto/indexSet.hpp

Thu, 12 Mar 2009 18:16:36 -0700

author: trims
date: Thu, 12 Mar 2009 18:16:36 -0700
changeset 1063: 7bb995fbd3c0
parent 435: a61af66fc99e
child 1907: c18cbe5936b8
permissions: -rw-r--r--

Merge

 /*
  * 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();
     }
   }
 };

Mercurial > jdk8-mips64-public > hotspot / annotate

src/share/vm/opto/indexSet.hpp@7bb995fbd3c0 (annotated)

src/share/vm/opto/indexSet.hpp