Java example source code file (indexSet.hpp)

This example Java source code file (indexSet.hpp) is included in the alvinalexander.com "Java Source Code Warehouse" project. The intent of this project is to help you "Learn Java by Example" ^TM.

Learn more about this Java project at its project page.

Java - Java tags/keywords

arena, assert, bitblock, compile\:\:current, indexset, indexset\:\:get_bit_index, indexset\:\:get_word_index, indexsetiterator, indexsetwatch, null, phaseifg, resourceobj, share_vm_opto_indexset_hpp, verifyopto

The indexSet.hpp Java example source code

/*
 * 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