truffle: src/share/vm/opto/indexSet.hpp comparison

comparison src/share/vm/opto/indexSet.hpp @ 0:a61af66fc99e jdk7-b24

Initial load

author	duke
date	Sat, 01 Dec 2007 00:00:00 +0000
parents
children	c18cbe5936b8

comparison

equal deleted inserted replaced

--1:000000000000
+:a61af66fc99e
+/*
+* 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 > hg > truffle

comparison src/share/vm/opto/indexSet.hpp @ 0:a61af66fc99e jdk7-b24