Mercurial > hg > graal-compiler
annotate src/share/vm/opto/indexSet.hpp @ 1941:79d04223b8a5
Added caching for resolved types and resolved fields.
This is crucial, because the local load elimination will lead to wrong results, if field equality (of two RiField objects with the same object and the same RiType) is not given. The caching makes sure that the default equals implementation is sufficient.
| author | Thomas Wuerthinger <wuerthinger@ssw.jku.at> |
|---|---|
| date | Tue, 28 Dec 2010 18:33:26 +0100 |
| parents | c18cbe5936b8 |
| children | f95d63e2154a |
| rev | line source |
|---|---|
| 0 | 1 /* |
|
1552
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
0
diff
changeset
|
2 * Copyright (c) 1998, 2005, 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 | |
| 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 }; |