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