Mercurial > hg > truffle
annotate src/share/vm/opto/indexSet.hpp @ 17716:cdb71841f4bc
6498581: ThreadInterruptTest3 produces wrong output on Windows
Summary: There is race condition between os::interrupt and os::is_interrupted on Windows. In JVM_Sleep(Thread.sleep), check if thread gets interrupted, it may see interrupted but not really interrupted so cause spurious waking up (early return from sleep). Fix by checking if interrupt event really gets set thus prevent false return. For intrinsic of _isInterrupted, on Windows, go fastpath only on bit not set.
Reviewed-by: acorn, kvn
Contributed-by: david.holmes@oracle.com, yumin.qi@oracle.com
| author | minqi |
|---|---|
| date | Wed, 26 Feb 2014 15:20:41 -0800 |
| 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 |