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