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