1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 1.2 +++ b/src/share/vm/opto/indexSet.hpp Sat Dec 01 00:00:00 2007 +0000 1.3 @@ -0,0 +1,461 @@ 1.4 +/* 1.5 + * Copyright 1998-2005 Sun Microsystems, Inc. All Rights Reserved. 1.6 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 1.7 + * 1.8 + * This code is free software; you can redistribute it and/or modify it 1.9 + * under the terms of the GNU General Public License version 2 only, as 1.10 + * published by the Free Software Foundation. 1.11 + * 1.12 + * This code is distributed in the hope that it will be useful, but WITHOUT 1.13 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 1.14 + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1.15 + * version 2 for more details (a copy is included in the LICENSE file that 1.16 + * accompanied this code). 1.17 + * 1.18 + * You should have received a copy of the GNU General Public License version 1.19 + * 2 along with this work; if not, write to the Free Software Foundation, 1.20 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 1.21 + * 1.22 + * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, 1.23 + * CA 95054 USA or visit www.sun.com if you need additional information or 1.24 + * have any questions. 1.25 + * 1.26 + */ 1.27 + 1.28 +// This file defines the IndexSet class, a set of sparse integer indices. 1.29 +// This data structure is used by the compiler in its liveness analysis and 1.30 +// during register allocation. 1.31 + 1.32 +//-------------------------------- class IndexSet ---------------------------- 1.33 +// An IndexSet is a piece-wise bitvector. At the top level, we have an array 1.34 +// of pointers to bitvector chunks called BitBlocks. Each BitBlock has a fixed 1.35 +// size and is allocated from a shared free list. The bits which are set in 1.36 +// each BitBlock correspond to the elements of the set. 1.37 + 1.38 +class IndexSet : public ResourceObj { 1.39 + friend class IndexSetIterator; 1.40 + 1.41 + public: 1.42 + // When we allocate an IndexSet, it starts off with an array of top level block 1.43 + // pointers of a set length. This size is intended to be large enough for the 1.44 + // majority of IndexSets. In the cases when this size is not large enough, 1.45 + // a separately allocated array is used. 1.46 + 1.47 + // The length of the preallocated top level block array 1.48 + enum { preallocated_block_list_size = 16 }; 1.49 + 1.50 + // Elements of a IndexSet get decomposed into three fields. The highest order 1.51 + // bits are the block index, which tell which high level block holds the element. 1.52 + // Within that block, the word index indicates which word holds the element. 1.53 + // Finally, the bit index determines which single bit within that word indicates 1.54 + // membership of the element in the set. 1.55 + 1.56 + // The lengths of the index bitfields 1.57 + enum { bit_index_length = 5, 1.58 + word_index_length = 3, 1.59 + block_index_length = 8 // not used 1.60 + }; 1.61 + 1.62 + // Derived constants used for manipulating the index bitfields 1.63 + enum { 1.64 + bit_index_offset = 0, // not used 1.65 + word_index_offset = bit_index_length, 1.66 + block_index_offset = bit_index_length + word_index_length, 1.67 + 1.68 + bits_per_word = 1 << bit_index_length, 1.69 + words_per_block = 1 << word_index_length, 1.70 + bits_per_block = bits_per_word * words_per_block, 1.71 + 1.72 + bit_index_mask = right_n_bits(bit_index_length), 1.73 + word_index_mask = right_n_bits(word_index_length) 1.74 + }; 1.75 + 1.76 + // These routines are used for extracting the block, word, and bit index 1.77 + // from an element. 1.78 + static uint get_block_index(uint element) { 1.79 + return element >> block_index_offset; 1.80 + } 1.81 + static uint get_word_index(uint element) { 1.82 + return mask_bits(element >> word_index_offset,word_index_mask); 1.83 + } 1.84 + static uint get_bit_index(uint element) { 1.85 + return mask_bits(element,bit_index_mask); 1.86 + } 1.87 + 1.88 + //------------------------------ class BitBlock ---------------------------- 1.89 + // The BitBlock class is a segment of a bitvector set. 1.90 + 1.91 + class BitBlock : public ResourceObj { 1.92 + friend class IndexSetIterator; 1.93 + friend class IndexSet; 1.94 + 1.95 + private: 1.96 + // All of BitBlocks fields and methods are declared private. We limit 1.97 + // access to IndexSet and IndexSetIterator. 1.98 + 1.99 + // A BitBlock is composed of some number of 32 bit words. When a BitBlock 1.100 + // is not in use by any IndexSet, it is stored on a free list. The next field 1.101 + // is used by IndexSet to mainting this free list. 1.102 + 1.103 + union { 1.104 + uint32 _words[words_per_block]; 1.105 + BitBlock *_next; 1.106 + } _data; 1.107 + 1.108 + // accessors 1.109 + uint32 *words() { return _data._words; } 1.110 + void set_next(BitBlock *next) { _data._next = next; } 1.111 + BitBlock *next() { return _data._next; } 1.112 + 1.113 + // Operations. A BitBlock supports four simple operations, 1.114 + // clear(), member(), insert(), and remove(). These methods do 1.115 + // not assume that the block index has been masked out. 1.116 + 1.117 + void clear() { 1.118 + memset(words(), 0, sizeof(uint32) * words_per_block); 1.119 + } 1.120 + 1.121 + bool member(uint element) { 1.122 + uint word_index = IndexSet::get_word_index(element); 1.123 + uint bit_index = IndexSet::get_bit_index(element); 1.124 + 1.125 + return ((words()[word_index] & (uint32)(0x1 << bit_index)) != 0); 1.126 + } 1.127 + 1.128 + bool insert(uint element) { 1.129 + uint word_index = IndexSet::get_word_index(element); 1.130 + uint bit_index = IndexSet::get_bit_index(element); 1.131 + 1.132 + uint32 bit = (0x1 << bit_index); 1.133 + uint32 before = words()[word_index]; 1.134 + words()[word_index] = before | bit; 1.135 + return ((before & bit) != 0); 1.136 + } 1.137 + 1.138 + bool remove(uint element) { 1.139 + uint word_index = IndexSet::get_word_index(element); 1.140 + uint bit_index = IndexSet::get_bit_index(element); 1.141 + 1.142 + uint32 bit = (0x1 << bit_index); 1.143 + uint32 before = words()[word_index]; 1.144 + words()[word_index] = before & ~bit; 1.145 + return ((before & bit) != 0); 1.146 + } 1.147 + }; 1.148 + 1.149 + //-------------------------- BitBlock allocation --------------------------- 1.150 + private: 1.151 + 1.152 + // All IndexSets share an arena from which they allocate BitBlocks. Unused 1.153 + // BitBlocks are placed on a free list. 1.154 + 1.155 + // The number of BitBlocks to allocate at a time 1.156 + enum { bitblock_alloc_chunk_size = 50 }; 1.157 + 1.158 + static Arena *arena() { return Compile::current()->indexSet_arena(); } 1.159 + 1.160 + static void populate_free_list(); 1.161 + 1.162 + public: 1.163 + 1.164 + // Invalidate the current free BitBlock list and begin allocation 1.165 + // from a new arena. It is essential that this method is called whenever 1.166 + // the Arena being used for BitBlock allocation is reset. 1.167 + static void reset_memory(Compile* compile, Arena *arena) { 1.168 + compile->set_indexSet_free_block_list(NULL); 1.169 + compile->set_indexSet_arena(arena); 1.170 + 1.171 + // This should probably be done in a static initializer 1.172 + _empty_block.clear(); 1.173 + } 1.174 + 1.175 + private: 1.176 + friend class BitBlock; 1.177 + // A distinguished BitBlock which always remains empty. When a new IndexSet is 1.178 + // created, all of its top level BitBlock pointers are initialized to point to 1.179 + // this. 1.180 + static BitBlock _empty_block; 1.181 + 1.182 + //-------------------------- Members ------------------------------------------ 1.183 + 1.184 + // The number of elements in the set 1.185 + uint _count; 1.186 + 1.187 + // Our top level array of bitvector segments 1.188 + BitBlock **_blocks; 1.189 + 1.190 + BitBlock *_preallocated_block_list[preallocated_block_list_size]; 1.191 + 1.192 + // The number of top level array entries in use 1.193 + uint _max_blocks; 1.194 + 1.195 + // Our assertions need to know the maximum number allowed in the set 1.196 +#ifdef ASSERT 1.197 + uint _max_elements; 1.198 +#endif 1.199 + 1.200 + // The next IndexSet on the free list (not used at same time as count) 1.201 + IndexSet *_next; 1.202 + 1.203 + public: 1.204 + //-------------------------- Free list operations ------------------------------ 1.205 + // Individual IndexSets can be placed on a free list. This is done in PhaseLive. 1.206 + 1.207 + IndexSet *next() { 1.208 +#ifdef ASSERT 1.209 + if( VerifyOpto ) { 1.210 + check_watch("removed from free list?", ((_next == NULL) ? 0 : _next->_serial_number)); 1.211 + } 1.212 +#endif 1.213 + return _next; 1.214 + } 1.215 + 1.216 + void set_next(IndexSet *next) { 1.217 +#ifdef ASSERT 1.218 + if( VerifyOpto ) { 1.219 + check_watch("put on free list?", ((next == NULL) ? 0 : next->_serial_number)); 1.220 + } 1.221 +#endif 1.222 + _next = next; 1.223 + } 1.224 + 1.225 + private: 1.226 + //-------------------------- Utility methods ----------------------------------- 1.227 + 1.228 + // Get the block which holds element 1.229 + BitBlock *get_block_containing(uint element) const { 1.230 + assert(element < _max_elements, "element out of bounds"); 1.231 + return _blocks[get_block_index(element)]; 1.232 + } 1.233 + 1.234 + // Set a block in the top level array 1.235 + void set_block(uint index, BitBlock *block) { 1.236 +#ifdef ASSERT 1.237 + if( VerifyOpto ) 1.238 + check_watch("set block", index); 1.239 +#endif 1.240 + _blocks[index] = block; 1.241 + } 1.242 + 1.243 + // Get a BitBlock from the free list 1.244 + BitBlock *alloc_block(); 1.245 + 1.246 + // Get a BitBlock from the free list and place it in the top level array 1.247 + BitBlock *alloc_block_containing(uint element); 1.248 + 1.249 + // Free a block from the top level array, placing it on the free BitBlock list 1.250 + void free_block(uint i); 1.251 + 1.252 + public: 1.253 + //-------------------------- Primitive set operations -------------------------- 1.254 + 1.255 + void clear() { 1.256 +#ifdef ASSERT 1.257 + if( VerifyOpto ) 1.258 + check_watch("clear"); 1.259 +#endif 1.260 + _count = 0; 1.261 + for (uint i = 0; i < _max_blocks; i++) { 1.262 + BitBlock *block = _blocks[i]; 1.263 + if (block != &_empty_block) { 1.264 + free_block(i); 1.265 + } 1.266 + } 1.267 + } 1.268 + 1.269 + uint count() const { return _count; } 1.270 + 1.271 + bool is_empty() const { return _count == 0; } 1.272 + 1.273 + bool member(uint element) const { 1.274 + return get_block_containing(element)->member(element); 1.275 + } 1.276 + 1.277 + bool insert(uint element) { 1.278 +#ifdef ASSERT 1.279 + if( VerifyOpto ) 1.280 + check_watch("insert", element); 1.281 +#endif 1.282 + if (element == 0) { 1.283 + return 0; 1.284 + } 1.285 + BitBlock *block = get_block_containing(element); 1.286 + if (block == &_empty_block) { 1.287 + block = alloc_block_containing(element); 1.288 + } 1.289 + bool present = block->insert(element); 1.290 + if (!present) { 1.291 + _count++; 1.292 + } 1.293 + return !present; 1.294 + } 1.295 + 1.296 + bool remove(uint element) { 1.297 +#ifdef ASSERT 1.298 + if( VerifyOpto ) 1.299 + check_watch("remove", element); 1.300 +#endif 1.301 + 1.302 + BitBlock *block = get_block_containing(element); 1.303 + bool present = block->remove(element); 1.304 + if (present) { 1.305 + _count--; 1.306 + } 1.307 + return present; 1.308 + } 1.309 + 1.310 + //-------------------------- Compound set operations ------------------------ 1.311 + // Compute the union of all elements of one and two which interfere 1.312 + // with the RegMask mask. If the degree of the union becomes 1.313 + // exceeds fail_degree, the union bails out. The underlying set is 1.314 + // cleared before the union is performed. 1.315 + uint lrg_union(uint lr1, uint lr2, 1.316 + const uint fail_degree, 1.317 + const class PhaseIFG *ifg, 1.318 + const RegMask &mask); 1.319 + 1.320 + 1.321 + //------------------------- Construction, initialization ----------------------- 1.322 + 1.323 + IndexSet() {} 1.324 + 1.325 + // This constructor is used for making a deep copy of a IndexSet. 1.326 + IndexSet(IndexSet *set); 1.327 + 1.328 + // Perform initialization on a IndexSet 1.329 + void initialize(uint max_element); 1.330 + 1.331 + // Initialize a IndexSet. If the top level BitBlock array needs to be 1.332 + // allocated, do it from the proffered arena. BitBlocks are still allocated 1.333 + // from the static Arena member. 1.334 + void initialize(uint max_element, Arena *arena); 1.335 + 1.336 + // Exchange two sets 1.337 + void swap(IndexSet *set); 1.338 + 1.339 + //-------------------------- Debugging and statistics -------------------------- 1.340 + 1.341 +#ifndef PRODUCT 1.342 + // Output a IndexSet for debugging 1.343 + void dump() const; 1.344 +#endif 1.345 + 1.346 +#ifdef ASSERT 1.347 + void tally_iteration_statistics() const; 1.348 + 1.349 + // BitBlock allocation statistics 1.350 + static uint _alloc_new; 1.351 + static uint _alloc_total; 1.352 + 1.353 + // Block density statistics 1.354 + static long _total_bits; 1.355 + static long _total_used_blocks; 1.356 + static long _total_unused_blocks; 1.357 + 1.358 + // Sanity tests 1.359 + void verify() const; 1.360 + 1.361 + static int _serial_count; 1.362 + int _serial_number; 1.363 + 1.364 + // Check to see if the serial number of the current set is the one we're tracing. 1.365 + // If it is, print a message. 1.366 + void check_watch(const char *operation, uint operand) const { 1.367 + if (IndexSetWatch != 0) { 1.368 + if (IndexSetWatch == -1 || _serial_number == IndexSetWatch) { 1.369 + tty->print_cr("IndexSet %d : %s ( %d )", _serial_number, operation, operand); 1.370 + } 1.371 + } 1.372 + } 1.373 + void check_watch(const char *operation) const { 1.374 + if (IndexSetWatch != 0) { 1.375 + if (IndexSetWatch == -1 || _serial_number == IndexSetWatch) { 1.376 + tty->print_cr("IndexSet %d : %s", _serial_number, operation); 1.377 + } 1.378 + } 1.379 + } 1.380 + 1.381 + public: 1.382 + static void print_statistics(); 1.383 + 1.384 +#endif 1.385 +}; 1.386 + 1.387 + 1.388 +//-------------------------------- class IndexSetIterator -------------------- 1.389 +// An iterator for IndexSets. 1.390 + 1.391 +class IndexSetIterator VALUE_OBJ_CLASS_SPEC { 1.392 + friend class IndexSet; 1.393 + 1.394 + public: 1.395 + 1.396 + // We walk over the bits in a word in chunks of size window_size. 1.397 + enum { window_size = 5, 1.398 + window_mask = right_n_bits(window_size), 1.399 + table_size = (1 << window_size) }; 1.400 + 1.401 + // For an integer of length window_size, what is the first set bit? 1.402 + static const byte _first_bit[table_size]; 1.403 + 1.404 + // For an integer of length window_size, what is the second set bit? 1.405 + static const byte _second_bit[table_size]; 1.406 + 1.407 + private: 1.408 + // The current word we are inspecting 1.409 + uint32 _current; 1.410 + 1.411 + // What element number are we currently on? 1.412 + uint _value; 1.413 + 1.414 + // The index of the next word we will inspect 1.415 + uint _next_word; 1.416 + 1.417 + // A pointer to the contents of the current block 1.418 + uint32 *_words; 1.419 + 1.420 + // The index of the next block we will inspect 1.421 + uint _next_block; 1.422 + 1.423 + // A pointer to the blocks in our set 1.424 + IndexSet::BitBlock **_blocks; 1.425 + 1.426 + // The number of blocks in the set 1.427 + uint _max_blocks; 1.428 + 1.429 + // If the iterator was created from a non-const set, we replace 1.430 + // non-canonical empty blocks with the _empty_block pointer. If 1.431 + // _set is NULL, we do no replacement. 1.432 + IndexSet *_set; 1.433 + 1.434 + // Advance to the next non-empty word and return the next 1.435 + // element in the set. 1.436 + uint advance_and_next(); 1.437 + 1.438 + 1.439 + public: 1.440 + 1.441 + // If an iterator is built from a constant set then empty blocks 1.442 + // are not canonicalized. 1.443 + IndexSetIterator(IndexSet *set); 1.444 + IndexSetIterator(const IndexSet *set); 1.445 + 1.446 + // Return the next element of the set. Return 0 when done. 1.447 + uint next() { 1.448 + uint current = _current; 1.449 + if (current != 0) { 1.450 + uint value = _value; 1.451 + while (mask_bits(current,window_mask) == 0) { 1.452 + current >>= window_size; 1.453 + value += window_size; 1.454 + } 1.455 + 1.456 + uint advance = _second_bit[mask_bits(current,window_mask)]; 1.457 + _current = current >> advance; 1.458 + _value = value + advance; 1.459 + return value + _first_bit[mask_bits(current,window_mask)]; 1.460 + } else { 1.461 + return advance_and_next(); 1.462 + } 1.463 + } 1.464 +};