Mercurial > hg > graal-compiler
view src/share/vm/opto/indexSet.hpp @ 3837:43f9d800f276
7066339: Tiered: policy should make consistent decisions about osr levels
Summary: Added feedback disabling flag to common(), fixed handling of TieredStopAtLevel.
Reviewed-by: kvn, never
author | iveresov |
---|---|
date | Wed, 20 Jul 2011 18:04:17 -0700 |
parents | f7de3327c683 |
children |
line wrap: on
line source
/* * 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