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