Mercurial > hg > truffle
annotate src/share/vm/opto/indexSet.hpp @ 12355:cefad50507d8
Merge with hs25-b53
| author | Gilles Duboscq <duboscq@ssw.jku.at> |
|---|---|
| date | Fri, 11 Oct 2013 10:38:03 +0200 |
| parents | f7de3327c683 |
| children |
| rev | line source |
|---|---|
| 0 | 1 /* |
| 2250 | 2 * Copyright (c) 1998, 2011, Oracle and/or its affiliates. All rights reserved. |
| 0 | 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 * | |
|
1552
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
0
diff
changeset
|
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
|
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
0
diff
changeset
|
20 * or visit www.oracle.com if you need additional information or have any |
|
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
0
diff
changeset
|
21 * questions. |
| 0 | 22 * |
| 23 */ | |
| 24 | |
| 1972 | 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 | |
| 0 | 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 | |
| 2250 | 355 static julong _alloc_new; |
| 356 static julong _alloc_total; | |
| 0 | 357 |
| 358 // Block density statistics | |
| 2250 | 359 static julong _total_bits; |
| 360 static julong _total_used_blocks; | |
| 361 static julong _total_unused_blocks; | |
| 0 | 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 }; | |
| 1972 | 470 |
| 471 #endif // SHARE_VM_OPTO_INDEXSET_HPP |