Mercurial > hg > truffle
annotate src/share/vm/opto/indexSet.cpp @ 6972:bd7a7ce2e264
6830717: replay of compilations would help with debugging
Summary: When java process crashed in compiler thread, repeat the compilation process will help finding root cause. This is done with using SA dump application class data and replay data from core dump, then use debug version of jvm to recompile the problematic java method.
Reviewed-by: kvn, twisti, sspitsyn
Contributed-by: yumin.qi@oracle.com
| author | minqi |
|---|---|
| date | Mon, 12 Nov 2012 14:03:53 -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 #include "precompiled.hpp" |
| 26 #include "memory/allocation.inline.hpp" | |
| 27 #include "opto/chaitin.hpp" | |
| 28 #include "opto/compile.hpp" | |
| 29 #include "opto/indexSet.hpp" | |
| 30 #include "opto/regmask.hpp" | |
| 31 | |
| 0 | 32 // This file defines the IndexSet class, a set of sparse integer indices. |
| 33 // This data structure is used by the compiler in its liveness analysis and | |
| 34 // during register allocation. It also defines an iterator for this class. | |
| 35 | |
| 36 //-------------------------------- Initializations ------------------------------ | |
| 37 | |
| 38 IndexSet::BitBlock IndexSet::_empty_block = IndexSet::BitBlock(); | |
| 39 | |
| 40 #ifdef ASSERT | |
| 41 // Initialize statistics counters | |
| 2250 | 42 julong IndexSet::_alloc_new = 0; |
| 43 julong IndexSet::_alloc_total = 0; | |
| 0 | 44 |
| 2250 | 45 julong IndexSet::_total_bits = 0; |
| 46 julong IndexSet::_total_used_blocks = 0; | |
| 47 julong IndexSet::_total_unused_blocks = 0; | |
| 0 | 48 |
| 49 // Per set, or all sets operation tracing | |
| 50 int IndexSet::_serial_count = 1; | |
| 51 #endif | |
| 52 | |
| 53 // What is the first set bit in a 5 bit integer? | |
| 54 const byte IndexSetIterator::_first_bit[32] = { | |
| 55 0, 0, 1, 0, | |
| 56 2, 0, 1, 0, | |
| 57 3, 0, 1, 0, | |
| 58 2, 0, 1, 0, | |
| 59 4, 0, 1, 0, | |
| 60 2, 0, 1, 0, | |
| 61 3, 0, 1, 0, | |
| 62 2, 0, 1, 0 | |
| 63 }; | |
| 64 | |
| 65 // What is the second set bit in a 5 bit integer? | |
| 66 const byte IndexSetIterator::_second_bit[32] = { | |
| 67 5, 5, 5, 1, | |
| 68 5, 2, 2, 1, | |
| 69 5, 3, 3, 1, | |
| 70 3, 2, 2, 1, | |
| 71 5, 4, 4, 1, | |
| 72 4, 2, 2, 1, | |
| 73 4, 3, 3, 1, | |
| 74 3, 2, 2, 1 | |
| 75 }; | |
| 76 | |
| 77 // I tried implementing the IndexSetIterator with a window_size of 8 and | |
| 78 // didn't seem to get a noticeable speedup. I am leaving in the tables | |
| 79 // in case we want to switch back. | |
| 80 | |
| 81 /*const byte IndexSetIterator::_first_bit[256] = { | |
| 82 8, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, | |
| 83 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, | |
| 84 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, | |
| 85 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, | |
| 86 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, | |
| 87 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, | |
| 88 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, | |
| 89 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, | |
| 90 7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, | |
| 91 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, | |
| 92 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, | |
| 93 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, | |
| 94 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, | |
| 95 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, | |
| 96 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, | |
| 97 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0 | |
| 98 }; | |
| 99 | |
| 100 const byte IndexSetIterator::_second_bit[256] = { | |
| 101 8, 8, 8, 1, 8, 2, 2, 1, 8, 3, 3, 1, 3, 2, 2, 1, | |
| 102 8, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1, | |
| 103 8, 5, 5, 1, 5, 2, 2, 1, 5, 3, 3, 1, 3, 2, 2, 1, | |
| 104 5, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1, | |
| 105 8, 6, 6, 1, 6, 2, 2, 1, 6, 3, 3, 1, 3, 2, 2, 1, | |
| 106 6, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1, | |
| 107 6, 5, 5, 1, 5, 2, 2, 1, 5, 3, 3, 1, 3, 2, 2, 1, | |
| 108 5, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1, | |
| 109 8, 7, 7, 1, 7, 2, 2, 1, 7, 3, 3, 1, 3, 2, 2, 1, | |
| 110 7, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1, | |
| 111 7, 5, 5, 1, 5, 2, 2, 1, 5, 3, 3, 1, 3, 2, 2, 1, | |
| 112 5, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1, | |
| 113 7, 6, 6, 1, 6, 2, 2, 1, 6, 3, 3, 1, 3, 2, 2, 1, | |
| 114 6, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1, | |
| 115 6, 5, 5, 1, 5, 2, 2, 1, 5, 3, 3, 1, 3, 2, 2, 1, | |
| 116 5, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1 | |
| 117 };*/ | |
| 118 | |
| 119 //---------------------------- IndexSet::populate_free_list() ----------------------------- | |
| 120 // Populate the free BitBlock list with a batch of BitBlocks. The BitBlocks | |
| 121 // are 32 bit aligned. | |
| 122 | |
| 123 void IndexSet::populate_free_list() { | |
| 124 Compile *compile = Compile::current(); | |
| 125 BitBlock *free = (BitBlock*)compile->indexSet_free_block_list(); | |
| 126 | |
| 127 char *mem = (char*)arena()->Amalloc_4(sizeof(BitBlock) * | |
| 128 bitblock_alloc_chunk_size + 32); | |
| 129 | |
| 130 // Align the pointer to a 32 bit boundary. | |
| 131 BitBlock *new_blocks = (BitBlock*)(((uintptr_t)mem + 32) & ~0x001F); | |
| 132 | |
| 133 // Add the new blocks to the free list. | |
| 134 for (int i = 0; i < bitblock_alloc_chunk_size; i++) { | |
| 135 new_blocks->set_next(free); | |
| 136 free = new_blocks; | |
| 137 new_blocks++; | |
| 138 } | |
| 139 | |
| 140 compile->set_indexSet_free_block_list(free); | |
| 141 | |
| 142 #ifdef ASSERT | |
| 143 if (CollectIndexSetStatistics) { | |
| 2250 | 144 inc_stat_counter(&_alloc_new, bitblock_alloc_chunk_size); |
| 0 | 145 } |
| 146 #endif | |
| 147 } | |
| 148 | |
| 149 | |
| 150 //---------------------------- IndexSet::alloc_block() ------------------------ | |
| 151 // Allocate a BitBlock from the free list. If the free list is empty, | |
| 152 // prime it. | |
| 153 | |
| 154 IndexSet::BitBlock *IndexSet::alloc_block() { | |
| 155 #ifdef ASSERT | |
| 156 if (CollectIndexSetStatistics) { | |
| 2250 | 157 inc_stat_counter(&_alloc_total, 1); |
| 0 | 158 } |
| 159 #endif | |
| 160 Compile *compile = Compile::current(); | |
| 161 BitBlock* free_list = (BitBlock*)compile->indexSet_free_block_list(); | |
| 162 if (free_list == NULL) { | |
| 163 populate_free_list(); | |
| 164 free_list = (BitBlock*)compile->indexSet_free_block_list(); | |
| 165 } | |
| 166 BitBlock *block = free_list; | |
| 167 compile->set_indexSet_free_block_list(block->next()); | |
| 168 | |
| 169 block->clear(); | |
| 170 return block; | |
| 171 } | |
| 172 | |
| 173 //---------------------------- IndexSet::alloc_block_containing() ------------- | |
| 174 // Allocate a new BitBlock and put it into the position in the _blocks array | |
| 175 // corresponding to element. | |
| 176 | |
| 177 IndexSet::BitBlock *IndexSet::alloc_block_containing(uint element) { | |
| 178 BitBlock *block = alloc_block(); | |
| 179 uint bi = get_block_index(element); | |
| 180 _blocks[bi] = block; | |
| 181 return block; | |
| 182 } | |
| 183 | |
| 184 //---------------------------- IndexSet::free_block() ------------------------- | |
| 185 // Add a BitBlock to the free list. | |
| 186 | |
| 187 void IndexSet::free_block(uint i) { | |
| 188 debug_only(check_watch("free block", i)); | |
| 189 assert(i < _max_blocks, "block index too large"); | |
| 190 BitBlock *block = _blocks[i]; | |
| 191 assert(block != &_empty_block, "cannot free the empty block"); | |
| 192 block->set_next((IndexSet::BitBlock*)Compile::current()->indexSet_free_block_list()); | |
| 193 Compile::current()->set_indexSet_free_block_list(block); | |
| 194 set_block(i,&_empty_block); | |
| 195 } | |
| 196 | |
| 197 //------------------------------lrg_union-------------------------------------- | |
| 198 // Compute the union of all elements of one and two which interfere with | |
| 199 // the RegMask mask. If the degree of the union becomes exceeds | |
| 200 // fail_degree, the union bails out. The underlying set is cleared before | |
| 201 // the union is performed. | |
| 202 | |
| 203 uint IndexSet::lrg_union(uint lr1, uint lr2, | |
| 204 const uint fail_degree, | |
| 205 const PhaseIFG *ifg, | |
| 206 const RegMask &mask ) { | |
| 207 IndexSet *one = ifg->neighbors(lr1); | |
| 208 IndexSet *two = ifg->neighbors(lr2); | |
| 209 LRG &lrg1 = ifg->lrgs(lr1); | |
| 210 LRG &lrg2 = ifg->lrgs(lr2); | |
| 211 #ifdef ASSERT | |
| 212 assert(_max_elements == one->_max_elements, "max element mismatch"); | |
| 213 check_watch("union destination"); | |
| 214 one->check_watch("union source"); | |
| 215 two->check_watch("union source"); | |
| 216 #endif | |
| 217 | |
| 218 // Compute the degree of the combined live-range. The combined | |
| 219 // live-range has the union of the original live-ranges' neighbors set as | |
| 220 // well as the neighbors of all intermediate copies, minus those neighbors | |
| 221 // that can not use the intersected allowed-register-set. | |
| 222 | |
| 223 // Copy the larger set. Insert the smaller set into the larger. | |
| 224 if (two->count() > one->count()) { | |
| 225 IndexSet *temp = one; | |
| 226 one = two; | |
| 227 two = temp; | |
| 228 } | |
| 229 | |
| 230 clear(); | |
| 231 | |
| 232 // Used to compute degree of register-only interferences. Infinite-stack | |
| 233 // neighbors do not alter colorability, as they can always color to some | |
| 234 // other color. (A variant of the Briggs assertion) | |
| 235 uint reg_degree = 0; | |
| 236 | |
| 237 uint element; | |
| 238 // Load up the combined interference set with the neighbors of one | |
| 239 IndexSetIterator elements(one); | |
| 240 while ((element = elements.next()) != 0) { | |
| 241 LRG &lrg = ifg->lrgs(element); | |
| 242 if (mask.overlap(lrg.mask())) { | |
| 243 insert(element); | |
| 244 if( !lrg.mask().is_AllStack() ) { | |
| 245 reg_degree += lrg1.compute_degree(lrg); | |
| 246 if( reg_degree >= fail_degree ) return reg_degree; | |
| 247 } else { | |
| 248 // !!!!! Danger! No update to reg_degree despite having a neighbor. | |
| 249 // A variant of the Briggs assertion. | |
| 250 // Not needed if I simplify during coalesce, ala George/Appel. | |
| 251 assert( lrg.lo_degree(), "" ); | |
| 252 } | |
| 253 } | |
| 254 } | |
| 255 // Add neighbors of two as well | |
| 256 IndexSetIterator elements2(two); | |
| 257 while ((element = elements2.next()) != 0) { | |
| 258 LRG &lrg = ifg->lrgs(element); | |
| 259 if (mask.overlap(lrg.mask())) { | |
| 260 if (insert(element)) { | |
| 261 if( !lrg.mask().is_AllStack() ) { | |
| 262 reg_degree += lrg2.compute_degree(lrg); | |
| 263 if( reg_degree >= fail_degree ) return reg_degree; | |
| 264 } else { | |
| 265 // !!!!! Danger! No update to reg_degree despite having a neighbor. | |
| 266 // A variant of the Briggs assertion. | |
| 267 // Not needed if I simplify during coalesce, ala George/Appel. | |
| 268 assert( lrg.lo_degree(), "" ); | |
| 269 } | |
| 270 } | |
| 271 } | |
| 272 } | |
| 273 | |
| 274 return reg_degree; | |
| 275 } | |
| 276 | |
| 277 //---------------------------- IndexSet() ----------------------------- | |
| 278 // A deep copy constructor. This is used when you need a scratch copy of this set. | |
| 279 | |
| 280 IndexSet::IndexSet (IndexSet *set) { | |
| 281 #ifdef ASSERT | |
| 282 _serial_number = _serial_count++; | |
| 283 set->check_watch("copied", _serial_number); | |
| 284 check_watch("initialized by copy", set->_serial_number); | |
| 285 _max_elements = set->_max_elements; | |
| 286 #endif | |
| 287 _count = set->_count; | |
| 288 _max_blocks = set->_max_blocks; | |
| 289 if (_max_blocks <= preallocated_block_list_size) { | |
| 290 _blocks = _preallocated_block_list; | |
| 291 } else { | |
| 292 _blocks = | |
| 293 (IndexSet::BitBlock**) arena()->Amalloc_4(sizeof(IndexSet::BitBlock**) * _max_blocks); | |
| 294 } | |
| 295 for (uint i = 0; i < _max_blocks; i++) { | |
| 296 BitBlock *block = set->_blocks[i]; | |
| 297 if (block == &_empty_block) { | |
| 298 set_block(i, &_empty_block); | |
| 299 } else { | |
| 300 BitBlock *new_block = alloc_block(); | |
| 301 memcpy(new_block->words(), block->words(), sizeof(uint32) * words_per_block); | |
| 302 set_block(i, new_block); | |
| 303 } | |
| 304 } | |
| 305 } | |
| 306 | |
| 307 //---------------------------- IndexSet::initialize() ----------------------------- | |
| 308 // Prepare an IndexSet for use. | |
| 309 | |
| 310 void IndexSet::initialize(uint max_elements) { | |
| 311 #ifdef ASSERT | |
| 312 _serial_number = _serial_count++; | |
| 313 check_watch("initialized", max_elements); | |
| 314 _max_elements = max_elements; | |
| 315 #endif | |
| 316 _count = 0; | |
| 317 _max_blocks = (max_elements + bits_per_block - 1) / bits_per_block; | |
| 318 | |
| 319 if (_max_blocks <= preallocated_block_list_size) { | |
| 320 _blocks = _preallocated_block_list; | |
| 321 } else { | |
| 322 _blocks = (IndexSet::BitBlock**) arena()->Amalloc_4(sizeof(IndexSet::BitBlock**) * _max_blocks); | |
| 323 } | |
| 324 for (uint i = 0; i < _max_blocks; i++) { | |
| 325 set_block(i, &_empty_block); | |
| 326 } | |
| 327 } | |
| 328 | |
| 329 //---------------------------- IndexSet::initialize()------------------------------ | |
| 330 // Prepare an IndexSet for use. If it needs to allocate its _blocks array, it does | |
| 331 // so from the Arena passed as a parameter. BitBlock allocation is still done from | |
| 332 // the static Arena which was set with reset_memory(). | |
| 333 | |
| 334 void IndexSet::initialize(uint max_elements, Arena *arena) { | |
| 335 #ifdef ASSERT | |
| 336 _serial_number = _serial_count++; | |
| 337 check_watch("initialized2", max_elements); | |
| 338 _max_elements = max_elements; | |
| 339 #endif // ASSERT | |
| 340 _count = 0; | |
| 341 _max_blocks = (max_elements + bits_per_block - 1) / bits_per_block; | |
| 342 | |
| 343 if (_max_blocks <= preallocated_block_list_size) { | |
| 344 _blocks = _preallocated_block_list; | |
| 345 } else { | |
| 346 _blocks = (IndexSet::BitBlock**) arena->Amalloc_4(sizeof(IndexSet::BitBlock**) * _max_blocks); | |
| 347 } | |
| 348 for (uint i = 0; i < _max_blocks; i++) { | |
| 349 set_block(i, &_empty_block); | |
| 350 } | |
| 351 } | |
| 352 | |
| 353 //---------------------------- IndexSet::swap() ----------------------------- | |
| 354 // Exchange two IndexSets. | |
| 355 | |
| 356 void IndexSet::swap(IndexSet *set) { | |
| 357 #ifdef ASSERT | |
| 358 assert(_max_elements == set->_max_elements, "must have same universe size to swap"); | |
| 359 check_watch("swap", set->_serial_number); | |
| 360 set->check_watch("swap", _serial_number); | |
| 361 #endif | |
| 362 | |
| 363 for (uint i = 0; i < _max_blocks; i++) { | |
| 364 BitBlock *temp = _blocks[i]; | |
| 365 set_block(i, set->_blocks[i]); | |
| 366 set->set_block(i, temp); | |
| 367 } | |
| 368 uint temp = _count; | |
| 369 _count = set->_count; | |
| 370 set->_count = temp; | |
| 371 } | |
| 372 | |
| 373 //---------------------------- IndexSet::dump() ----------------------------- | |
| 374 // Print this set. Used for debugging. | |
| 375 | |
| 376 #ifndef PRODUCT | |
| 377 void IndexSet::dump() const { | |
| 378 IndexSetIterator elements(this); | |
| 379 | |
| 380 tty->print("{"); | |
| 381 uint i; | |
| 382 while ((i = elements.next()) != 0) { | |
| 383 tty->print("L%d ", i); | |
| 384 } | |
| 385 tty->print_cr("}"); | |
| 386 } | |
| 387 #endif | |
| 388 | |
| 389 #ifdef ASSERT | |
| 390 //---------------------------- IndexSet::tally_iteration_statistics() ----------------------------- | |
| 391 // Update block/bit counts to reflect that this set has been iterated over. | |
| 392 | |
| 393 void IndexSet::tally_iteration_statistics() const { | |
| 2250 | 394 inc_stat_counter(&_total_bits, count()); |
| 0 | 395 |
| 396 for (uint i = 0; i < _max_blocks; i++) { | |
| 397 if (_blocks[i] != &_empty_block) { | |
| 2250 | 398 inc_stat_counter(&_total_used_blocks, 1); |
| 0 | 399 } else { |
| 2250 | 400 inc_stat_counter(&_total_unused_blocks, 1); |
| 0 | 401 } |
| 402 } | |
| 403 } | |
| 404 | |
| 405 //---------------------------- IndexSet::print_statistics() ----------------------------- | |
| 406 // Print statistics about IndexSet usage. | |
| 407 | |
| 408 void IndexSet::print_statistics() { | |
| 2250 | 409 julong total_blocks = _total_used_blocks + _total_unused_blocks; |
| 0 | 410 tty->print_cr ("Accumulated IndexSet usage statistics:"); |
| 411 tty->print_cr ("--------------------------------------"); | |
| 412 tty->print_cr (" Iteration:"); | |
| 2250 | 413 tty->print_cr (" blocks visited: " UINT64_FORMAT, total_blocks); |
| 414 tty->print_cr (" blocks empty: %4.2f%%", 100.0*(double)_total_unused_blocks/total_blocks); | |
| 415 tty->print_cr (" bit density (bits/used blocks): %4.2f", (double)_total_bits/_total_used_blocks); | |
| 416 tty->print_cr (" bit density (bits/all blocks): %4.2f", (double)_total_bits/total_blocks); | |
| 0 | 417 tty->print_cr (" Allocation:"); |
| 2250 | 418 tty->print_cr (" blocks allocated: " UINT64_FORMAT, _alloc_new); |
| 419 tty->print_cr (" blocks used/reused: " UINT64_FORMAT, _alloc_total); | |
| 0 | 420 } |
| 421 | |
| 422 //---------------------------- IndexSet::verify() ----------------------------- | |
| 423 // Expensive test of IndexSet sanity. Ensure that the count agrees with the | |
| 424 // number of bits in the blocks. Make sure the iterator is seeing all elements | |
| 425 // of the set. Meant for use during development. | |
| 426 | |
| 427 void IndexSet::verify() const { | |
| 428 assert(!member(0), "zero cannot be a member"); | |
| 429 uint count = 0; | |
| 430 uint i; | |
| 431 for (i = 1; i < _max_elements; i++) { | |
| 432 if (member(i)) { | |
| 433 count++; | |
| 434 assert(count <= _count, "_count is messed up"); | |
| 435 } | |
| 436 } | |
| 437 | |
| 438 IndexSetIterator elements(this); | |
| 439 count = 0; | |
| 440 while ((i = elements.next()) != 0) { | |
| 441 count++; | |
| 442 assert(member(i), "returned a non member"); | |
| 443 assert(count <= _count, "iterator returned wrong number of elements"); | |
| 444 } | |
| 445 } | |
| 446 #endif | |
| 447 | |
| 448 //---------------------------- IndexSetIterator() ----------------------------- | |
| 449 // Create an iterator for a set. If empty blocks are detected when iterating | |
| 450 // over the set, these blocks are replaced. | |
| 451 | |
| 452 IndexSetIterator::IndexSetIterator(IndexSet *set) { | |
| 453 #ifdef ASSERT | |
| 454 if (CollectIndexSetStatistics) { | |
| 455 set->tally_iteration_statistics(); | |
| 456 } | |
| 457 set->check_watch("traversed", set->count()); | |
| 458 #endif | |
| 459 if (set->is_empty()) { | |
| 460 _current = 0; | |
| 461 _next_word = IndexSet::words_per_block; | |
| 462 _next_block = 1; | |
| 463 _max_blocks = 1; | |
| 464 | |
| 465 // We don't need the following values when we iterate over an empty set. | |
| 466 // The commented out code is left here to document that the omission | |
| 467 // is intentional. | |
| 468 // | |
| 469 //_value = 0; | |
| 470 //_words = NULL; | |
| 471 //_blocks = NULL; | |
| 472 //_set = NULL; | |
| 473 } else { | |
| 474 _current = 0; | |
| 475 _value = 0; | |
| 476 _next_block = 0; | |
| 477 _next_word = IndexSet::words_per_block; | |
| 478 | |
| 479 _max_blocks = set->_max_blocks; | |
| 480 _words = NULL; | |
| 481 _blocks = set->_blocks; | |
| 482 _set = set; | |
| 483 } | |
| 484 } | |
| 485 | |
| 486 //---------------------------- IndexSetIterator(const) ----------------------------- | |
| 487 // Iterate over a constant IndexSet. | |
| 488 | |
| 489 IndexSetIterator::IndexSetIterator(const IndexSet *set) { | |
| 490 #ifdef ASSERT | |
| 491 if (CollectIndexSetStatistics) { | |
| 492 set->tally_iteration_statistics(); | |
| 493 } | |
| 494 // We don't call check_watch from here to avoid bad recursion. | |
| 495 // set->check_watch("traversed const", set->count()); | |
| 496 #endif | |
| 497 if (set->is_empty()) { | |
| 498 _current = 0; | |
| 499 _next_word = IndexSet::words_per_block; | |
| 500 _next_block = 1; | |
| 501 _max_blocks = 1; | |
| 502 | |
| 503 // We don't need the following values when we iterate over an empty set. | |
| 504 // The commented out code is left here to document that the omission | |
| 505 // is intentional. | |
| 506 // | |
| 507 //_value = 0; | |
| 508 //_words = NULL; | |
| 509 //_blocks = NULL; | |
| 510 //_set = NULL; | |
| 511 } else { | |
| 512 _current = 0; | |
| 513 _value = 0; | |
| 514 _next_block = 0; | |
| 515 _next_word = IndexSet::words_per_block; | |
| 516 | |
| 517 _max_blocks = set->_max_blocks; | |
| 518 _words = NULL; | |
| 519 _blocks = set->_blocks; | |
| 520 _set = NULL; | |
| 521 } | |
| 522 } | |
| 523 | |
| 524 //---------------------------- List16Iterator::advance_and_next() ----------------------------- | |
| 525 // Advance to the next non-empty word in the set being iterated over. Return the next element | |
| 526 // if there is one. If we are done, return 0. This method is called from the next() method | |
| 527 // when it gets done with a word. | |
| 528 | |
| 529 uint IndexSetIterator::advance_and_next() { | |
| 530 // See if there is another non-empty word in the current block. | |
| 531 for (uint wi = _next_word; wi < (unsigned)IndexSet::words_per_block; wi++) { | |
| 532 if (_words[wi] != 0) { | |
| 533 // Found a non-empty word. | |
| 534 _value = ((_next_block - 1) * IndexSet::bits_per_block) + (wi * IndexSet::bits_per_word); | |
| 535 _current = _words[wi]; | |
| 536 | |
| 537 _next_word = wi+1; | |
| 538 | |
| 539 return next(); | |
| 540 } | |
| 541 } | |
| 542 | |
| 543 // We ran out of words in the current block. Advance to next non-empty block. | |
| 544 for (uint bi = _next_block; bi < _max_blocks; bi++) { | |
| 545 if (_blocks[bi] != &IndexSet::_empty_block) { | |
| 546 // Found a non-empty block. | |
| 547 | |
| 548 _words = _blocks[bi]->words(); | |
| 549 for (uint wi = 0; wi < (unsigned)IndexSet::words_per_block; wi++) { | |
| 550 if (_words[wi] != 0) { | |
| 551 // Found a non-empty word. | |
| 552 _value = (bi * IndexSet::bits_per_block) + (wi * IndexSet::bits_per_word); | |
| 553 _current = _words[wi]; | |
| 554 | |
| 555 _next_block = bi+1; | |
| 556 _next_word = wi+1; | |
| 557 | |
| 558 return next(); | |
| 559 } | |
| 560 } | |
| 561 | |
| 562 // All of the words in the block were empty. Replace | |
| 563 // the block with the empty block. | |
| 564 if (_set) { | |
| 565 _set->free_block(bi); | |
| 566 } | |
| 567 } | |
| 568 } | |
| 569 | |
| 570 // These assignments make redundant calls to next on a finished iterator | |
| 571 // faster. Probably not necessary. | |
| 572 _next_block = _max_blocks; | |
| 573 _next_word = IndexSet::words_per_block; | |
| 574 | |
| 575 // No more words. | |
| 576 return 0; | |
| 577 } |