1 /* 2 * Copyright (c) 1998, 2010, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. 8 * 9 * This code is distributed in the hope that it will be useful, but WITHOUT 10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 12 * version 2 for more details (a copy is included in the LICENSE file that 13 * accompanied this code). 14 * 15 * You should have received a copy of the GNU General Public License version 16 * 2 along with this work; if not, write to the Free Software Foundation, 17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 18 * 19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 20 * or visit www.oracle.com if you need additional information or have any 21 * questions. 22 * 23 */ 24 25 #ifndef SHARE_VM_OPTO_INDEXSET_HPP 26 #define SHARE_VM_OPTO_INDEXSET_HPP 27 28 #include "memory/allocation.hpp" 29 #include "memory/resourceArea.hpp" 30 #include "opto/compile.hpp" 31 #include "opto/regmask.hpp" 32 33 // This file defines the IndexSet class, a set of sparse integer indices. 34 // This data structure is used by the compiler in its liveness analysis and 35 // during register allocation. 36 37 //-------------------------------- class IndexSet ---------------------------- 38 // An IndexSet is a piece-wise bitvector. At the top level, we have an array 39 // of pointers to bitvector chunks called BitBlocks. Each BitBlock has a fixed 40 // size and is allocated from a shared free list. The bits which are set in 41 // each BitBlock correspond to the elements of the set. 42 43 class IndexSet : public ResourceObj { 44 friend class IndexSetIterator; 45 46 public: 47 // When we allocate an IndexSet, it starts off with an array of top level block 48 // pointers of a set length. This size is intended to be large enough for the 49 // majority of IndexSets. In the cases when this size is not large enough, 50 // a separately allocated array is used. 51 52 // The length of the preallocated top level block array 53 enum { preallocated_block_list_size = 16 }; 54 55 // Elements of a IndexSet get decomposed into three fields. The highest order 56 // bits are the block index, which tell which high level block holds the element. 57 // Within that block, the word index indicates which word holds the element. 58 // Finally, the bit index determines which single bit within that word indicates 59 // membership of the element in the set. 60 61 // The lengths of the index bitfields 62 enum { bit_index_length = 5, 63 word_index_length = 3, 64 block_index_length = 8 // not used 65 }; 66 67 // Derived constants used for manipulating the index bitfields 68 enum { 69 bit_index_offset = 0, // not used 70 word_index_offset = bit_index_length, 71 block_index_offset = bit_index_length + word_index_length, 72 73 bits_per_word = 1 << bit_index_length, 74 words_per_block = 1 << word_index_length, 75 bits_per_block = bits_per_word * words_per_block, 76 77 bit_index_mask = right_n_bits(bit_index_length), 78 word_index_mask = right_n_bits(word_index_length) 79 }; 80 81 // These routines are used for extracting the block, word, and bit index 82 // from an element. 83 static uint get_block_index(uint element) { 84 return element >> block_index_offset; 85 } 86 static uint get_word_index(uint element) { 87 return mask_bits(element >> word_index_offset,word_index_mask); 88 } 89 static uint get_bit_index(uint element) { 90 return mask_bits(element,bit_index_mask); 91 } 92 93 //------------------------------ class BitBlock ---------------------------- 94 // The BitBlock class is a segment of a bitvector set. 95 96 class BitBlock : public ResourceObj { 97 friend class IndexSetIterator; 98 friend class IndexSet; 99 100 private: 101 // All of BitBlocks fields and methods are declared private. We limit 102 // access to IndexSet and IndexSetIterator. 103 104 // A BitBlock is composed of some number of 32 bit words. When a BitBlock 105 // is not in use by any IndexSet, it is stored on a free list. The next field 106 // is used by IndexSet to mainting this free list. 107 108 union { 109 uint32 _words[words_per_block]; 110 BitBlock *_next; 111 } _data; 112 113 // accessors 114 uint32 *words() { return _data._words; } 115 void set_next(BitBlock *next) { _data._next = next; } 116 BitBlock *next() { return _data._next; } 117 118 // Operations. A BitBlock supports four simple operations, 119 // clear(), member(), insert(), and remove(). These methods do 120 // not assume that the block index has been masked out. 121 122 void clear() { 123 memset(words(), 0, sizeof(uint32) * words_per_block); 124 } 125 126 bool member(uint element) { 127 uint word_index = IndexSet::get_word_index(element); 128 uint bit_index = IndexSet::get_bit_index(element); 129 130 return ((words()[word_index] & (uint32)(0x1 << bit_index)) != 0); 131 } 132 133 bool insert(uint element) { 134 uint word_index = IndexSet::get_word_index(element); 135 uint bit_index = IndexSet::get_bit_index(element); 136 137 uint32 bit = (0x1 << bit_index); 138 uint32 before = words()[word_index]; 139 words()[word_index] = before | bit; 140 return ((before & bit) != 0); 141 } 142 143 bool remove(uint element) { 144 uint word_index = IndexSet::get_word_index(element); 145 uint bit_index = IndexSet::get_bit_index(element); 146 147 uint32 bit = (0x1 << bit_index); 148 uint32 before = words()[word_index]; 149 words()[word_index] = before & ~bit; 150 return ((before & bit) != 0); 151 } 152 }; 153 154 //-------------------------- BitBlock allocation --------------------------- 155 private: 156 157 // All IndexSets share an arena from which they allocate BitBlocks. Unused 158 // BitBlocks are placed on a free list. 159 160 // The number of BitBlocks to allocate at a time 161 enum { bitblock_alloc_chunk_size = 50 }; 162 163 static Arena *arena() { return Compile::current()->indexSet_arena(); } 164 165 static void populate_free_list(); 166 167 public: 168 169 // Invalidate the current free BitBlock list and begin allocation 170 // from a new arena. It is essential that this method is called whenever 171 // the Arena being used for BitBlock allocation is reset. 172 static void reset_memory(Compile* compile, Arena *arena) { 173 compile->set_indexSet_free_block_list(NULL); 174 compile->set_indexSet_arena(arena); 175 176 // This should probably be done in a static initializer 177 _empty_block.clear(); 178 } 179 180 private: 181 friend class BitBlock; 182 // A distinguished BitBlock which always remains empty. When a new IndexSet is 183 // created, all of its top level BitBlock pointers are initialized to point to 184 // this. 185 static BitBlock _empty_block; 186 187 //-------------------------- Members ------------------------------------------ 188 189 // The number of elements in the set 190 uint _count; 191 192 // Our top level array of bitvector segments 193 BitBlock **_blocks; 194 195 BitBlock *_preallocated_block_list[preallocated_block_list_size]; 196 197 // The number of top level array entries in use 198 uint _max_blocks; 199 200 // Our assertions need to know the maximum number allowed in the set 201 #ifdef ASSERT 202 uint _max_elements; 203 #endif 204 205 // The next IndexSet on the free list (not used at same time as count) 206 IndexSet *_next; 207 208 public: 209 //-------------------------- Free list operations ------------------------------ 210 // Individual IndexSets can be placed on a free list. This is done in PhaseLive. 211 212 IndexSet *next() { 213 #ifdef ASSERT 214 if( VerifyOpto ) { 215 check_watch("removed from free list?", ((_next == NULL) ? 0 : _next->_serial_number)); 216 } 217 #endif 218 return _next; 219 } 220 221 void set_next(IndexSet *next) { 222 #ifdef ASSERT 223 if( VerifyOpto ) { 224 check_watch("put on free list?", ((next == NULL) ? 0 : next->_serial_number)); 225 } 226 #endif 227 _next = next; 228 } 229 230 private: 231 //-------------------------- Utility methods ----------------------------------- 232 233 // Get the block which holds element 234 BitBlock *get_block_containing(uint element) const { 235 assert(element < _max_elements, "element out of bounds"); 236 return _blocks[get_block_index(element)]; 237 } 238 239 // Set a block in the top level array 240 void set_block(uint index, BitBlock *block) { 241 #ifdef ASSERT 242 if( VerifyOpto ) 243 check_watch("set block", index); 244 #endif 245 _blocks[index] = block; 246 } 247 248 // Get a BitBlock from the free list 249 BitBlock *alloc_block(); 250 251 // Get a BitBlock from the free list and place it in the top level array 252 BitBlock *alloc_block_containing(uint element); 253 254 // Free a block from the top level array, placing it on the free BitBlock list 255 void free_block(uint i); 256 257 public: 258 //-------------------------- Primitive set operations -------------------------- 259 260 void clear() { 261 #ifdef ASSERT 262 if( VerifyOpto ) 263 check_watch("clear"); 264 #endif 265 _count = 0; 266 for (uint i = 0; i < _max_blocks; i++) { 267 BitBlock *block = _blocks[i]; 268 if (block != &_empty_block) { 269 free_block(i); 270 } 271 } 272 } 273 274 uint count() const { return _count; } 275 276 bool is_empty() const { return _count == 0; } 277 278 bool member(uint element) const { 279 return get_block_containing(element)->member(element); 280 } 281 282 bool insert(uint element) { 283 #ifdef ASSERT 284 if( VerifyOpto ) 285 check_watch("insert", element); 286 #endif 287 if (element == 0) { 288 return 0; 289 } 290 BitBlock *block = get_block_containing(element); 291 if (block == &_empty_block) { 292 block = alloc_block_containing(element); 293 } 294 bool present = block->insert(element); 295 if (!present) { 296 _count++; 297 } 298 return !present; 299 } 300 301 bool remove(uint element) { 302 #ifdef ASSERT 303 if( VerifyOpto ) 304 check_watch("remove", element); 305 #endif 306 307 BitBlock *block = get_block_containing(element); 308 bool present = block->remove(element); 309 if (present) { 310 _count--; 311 } 312 return present; 313 } 314 315 //-------------------------- Compound set operations ------------------------ 316 // Compute the union of all elements of one and two which interfere 317 // with the RegMask mask. If the degree of the union becomes 318 // exceeds fail_degree, the union bails out. The underlying set is 319 // cleared before the union is performed. 320 uint lrg_union(uint lr1, uint lr2, 321 const uint fail_degree, 322 const class PhaseIFG *ifg, 323 const RegMask &mask); 324 325 326 //------------------------- Construction, initialization ----------------------- 327 328 IndexSet() {} 329 330 // This constructor is used for making a deep copy of a IndexSet. 331 IndexSet(IndexSet *set); 332 333 // Perform initialization on a IndexSet 334 void initialize(uint max_element); 335 336 // Initialize a IndexSet. If the top level BitBlock array needs to be 337 // allocated, do it from the proffered arena. BitBlocks are still allocated 338 // from the static Arena member. 339 void initialize(uint max_element, Arena *arena); 340 341 // Exchange two sets 342 void swap(IndexSet *set); 343 344 //-------------------------- Debugging and statistics -------------------------- 345 346 #ifndef PRODUCT 347 // Output a IndexSet for debugging 348 void dump() const; 349 #endif 350 351 #ifdef ASSERT 352 void tally_iteration_statistics() const; 353 354 // BitBlock allocation statistics 355 static uint _alloc_new; 356 static uint _alloc_total; 357 358 // Block density statistics 359 static long _total_bits; 360 static long _total_used_blocks; 361 static long _total_unused_blocks; 362 363 // Sanity tests 364 void verify() const; 365 366 static int _serial_count; 367 int _serial_number; 368 369 // Check to see if the serial number of the current set is the one we're tracing. 370 // If it is, print a message. 371 void check_watch(const char *operation, uint operand) const { 372 if (IndexSetWatch != 0) { 373 if (IndexSetWatch == -1 || _serial_number == IndexSetWatch) { 374 tty->print_cr("IndexSet %d : %s ( %d )", _serial_number, operation, operand); 375 } 376 } 377 } 378 void check_watch(const char *operation) const { 379 if (IndexSetWatch != 0) { 380 if (IndexSetWatch == -1 || _serial_number == IndexSetWatch) { 381 tty->print_cr("IndexSet %d : %s", _serial_number, operation); 382 } 383 } 384 } 385 386 public: 387 static void print_statistics(); 388 389 #endif 390 }; 391 392 393 //-------------------------------- class IndexSetIterator -------------------- 394 // An iterator for IndexSets. 395 396 class IndexSetIterator VALUE_OBJ_CLASS_SPEC { 397 friend class IndexSet; 398 399 public: 400 401 // We walk over the bits in a word in chunks of size window_size. 402 enum { window_size = 5, 403 window_mask = right_n_bits(window_size), 404 table_size = (1 << window_size) }; 405 406 // For an integer of length window_size, what is the first set bit? 407 static const byte _first_bit[table_size]; 408 409 // For an integer of length window_size, what is the second set bit? 410 static const byte _second_bit[table_size]; 411 412 private: 413 // The current word we are inspecting 414 uint32 _current; 415 416 // What element number are we currently on? 417 uint _value; 418 419 // The index of the next word we will inspect 420 uint _next_word; 421 422 // A pointer to the contents of the current block 423 uint32 *_words; 424 425 // The index of the next block we will inspect 426 uint _next_block; 427 428 // A pointer to the blocks in our set 429 IndexSet::BitBlock **_blocks; 430 431 // The number of blocks in the set 432 uint _max_blocks; 433 434 // If the iterator was created from a non-const set, we replace 435 // non-canonical empty blocks with the _empty_block pointer. If 436 // _set is NULL, we do no replacement. 437 IndexSet *_set; 438 439 // Advance to the next non-empty word and return the next 440 // element in the set. 441 uint advance_and_next(); 442 443 444 public: 445 446 // If an iterator is built from a constant set then empty blocks 447 // are not canonicalized. 448 IndexSetIterator(IndexSet *set); 449 IndexSetIterator(const IndexSet *set); 450 451 // Return the next element of the set. Return 0 when done. 452 uint next() { 453 uint current = _current; 454 if (current != 0) { 455 uint value = _value; 456 while (mask_bits(current,window_mask) == 0) { 457 current >>= window_size; 458 value += window_size; 459 } 460 461 uint advance = _second_bit[mask_bits(current,window_mask)]; 462 _current = current >> advance; 463 _value = value + advance; 464 return value + _first_bit[mask_bits(current,window_mask)]; 465 } else { 466 return advance_and_next(); 467 } 468 } 469 }; 470 471 #endif // SHARE_VM_OPTO_INDEXSET_HPP