Mercurial > hg > graal-compiler
annotate src/share/vm/utilities/bitMap.hpp @ 1091:6aa7255741f3
6906727: UseCompressedOops: some card-marking fixes related to object arrays
Summary: Introduced a new write_ref_array(HeapWords* start, size_t count) method that does the requisite MemRegion range calculation so (some of the) clients of the erstwhile write_ref_array(MemRegion mr) do not need to worry. This removed all external uses of array_size(), which was also simplified and made private. Asserts were added to catch other possible issues. Further, less essential, fixes stemming from this investigation are deferred to CR 6904516 (to follow shortly in hs17).
Reviewed-by: kvn, coleenp, jmasa
| author | ysr |
|---|---|
| date | Thu, 03 Dec 2009 15:01:57 -0800 |
| parents | bd02caa94611 |
| children | c18cbe5936b8 |
| rev | line source |
|---|---|
| 0 | 1 /* |
| 844 | 2 * Copyright 1997-2009 Sun Microsystems, Inc. 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 * | |
| 19 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, | |
| 20 * CA 95054 USA or visit www.sun.com if you need additional information or | |
| 21 * have any questions. | |
| 22 * | |
| 23 */ | |
| 24 | |
| 342 | 25 // Forward decl; |
| 26 class BitMapClosure; | |
| 0 | 27 |
| 342 | 28 // Operations for bitmaps represented as arrays of unsigned integers. |
| 29 // Bit offsets are numbered from 0 to size-1. | |
| 0 | 30 |
| 31 class BitMap VALUE_OBJ_CLASS_SPEC { | |
| 32 friend class BitMap2D; | |
| 33 | |
| 34 public: | |
| 35 typedef size_t idx_t; // Type used for bit and word indices. | |
| 342 | 36 typedef uintptr_t bm_word_t; // Element type of array that represents |
| 37 // the bitmap. | |
| 0 | 38 |
| 39 // Hints for range sizes. | |
| 40 typedef enum { | |
| 41 unknown_range, small_range, large_range | |
| 42 } RangeSizeHint; | |
| 43 | |
| 44 private: | |
| 342 | 45 bm_word_t* _map; // First word in bitmap |
| 46 idx_t _size; // Size of bitmap (in bits) | |
| 0 | 47 |
| 48 // Puts the given value at the given offset, using resize() to size | |
| 49 // the bitmap appropriately if needed using factor-of-two expansion. | |
| 50 void at_put_grow(idx_t index, bool value); | |
| 51 | |
| 52 protected: | |
| 53 // Return the position of bit within the word that contains it (e.g., if | |
| 54 // bitmap words are 32 bits, return a number 0 <= n <= 31). | |
| 55 static idx_t bit_in_word(idx_t bit) { return bit & (BitsPerWord - 1); } | |
| 56 | |
| 57 // Return a mask that will select the specified bit, when applied to the word | |
| 58 // containing the bit. | |
| 342 | 59 static bm_word_t bit_mask(idx_t bit) { return (bm_word_t)1 << bit_in_word(bit); } |
| 0 | 60 |
| 61 // Return the index of the word containing the specified bit. | |
| 62 static idx_t word_index(idx_t bit) { return bit >> LogBitsPerWord; } | |
| 63 | |
| 64 // Return the bit number of the first bit in the specified word. | |
| 65 static idx_t bit_index(idx_t word) { return word << LogBitsPerWord; } | |
| 66 | |
| 67 // Return the array of bitmap words, or a specific word from it. | |
| 342 | 68 bm_word_t* map() const { return _map; } |
| 69 bm_word_t map(idx_t word) const { return _map[word]; } | |
| 0 | 70 |
| 71 // Return a pointer to the word containing the specified bit. | |
| 342 | 72 bm_word_t* word_addr(idx_t bit) const { return map() + word_index(bit); } |
| 0 | 73 |
| 74 // Set a word to a specified value or to all ones; clear a word. | |
| 342 | 75 void set_word (idx_t word, bm_word_t val) { _map[word] = val; } |
| 0 | 76 void set_word (idx_t word) { set_word(word, ~(uintptr_t)0); } |
| 77 void clear_word(idx_t word) { _map[word] = 0; } | |
| 78 | |
| 79 // Utilities for ranges of bits. Ranges are half-open [beg, end). | |
| 80 | |
| 81 // Ranges within a single word. | |
| 342 | 82 bm_word_t inverted_bit_mask_for_range(idx_t beg, idx_t end) const; |
| 83 void set_range_within_word (idx_t beg, idx_t end); | |
| 84 void clear_range_within_word (idx_t beg, idx_t end); | |
| 85 void par_put_range_within_word (idx_t beg, idx_t end, bool value); | |
| 0 | 86 |
| 87 // Ranges spanning entire words. | |
| 342 | 88 void set_range_of_words (idx_t beg, idx_t end); |
| 89 void clear_range_of_words (idx_t beg, idx_t end); | |
| 90 void set_large_range_of_words (idx_t beg, idx_t end); | |
| 91 void clear_large_range_of_words (idx_t beg, idx_t end); | |
| 0 | 92 |
| 93 // The index of the first full word in a range. | |
| 342 | 94 idx_t word_index_round_up(idx_t bit) const; |
| 0 | 95 |
|
809
6e2afda171db
6849716: BitMap - performance regression introduced with G1
jcoomes
parents:
342
diff
changeset
|
96 // Verification. |
|
6e2afda171db
6849716: BitMap - performance regression introduced with G1
jcoomes
parents:
342
diff
changeset
|
97 inline void verify_index(idx_t index) const NOT_DEBUG_RETURN; |
|
6e2afda171db
6849716: BitMap - performance regression introduced with G1
jcoomes
parents:
342
diff
changeset
|
98 inline void verify_range(idx_t beg_index, idx_t end_index) const |
|
6e2afda171db
6849716: BitMap - performance regression introduced with G1
jcoomes
parents:
342
diff
changeset
|
99 NOT_DEBUG_RETURN; |
| 0 | 100 |
|
809
6e2afda171db
6849716: BitMap - performance regression introduced with G1
jcoomes
parents:
342
diff
changeset
|
101 // Statistics. |
| 342 | 102 static idx_t* _pop_count_table; |
| 103 static void init_pop_count_table(); | |
| 104 static idx_t num_set_bits(bm_word_t w); | |
| 105 static idx_t num_set_bits_from_table(unsigned char c); | |
| 0 | 106 |
| 107 public: | |
| 108 | |
| 109 // Constructs a bitmap with no map, and size 0. | |
| 110 BitMap() : _map(NULL), _size(0) {} | |
| 111 | |
| 342 | 112 // Constructs a bitmap with the given map and size. |
| 113 BitMap(bm_word_t* map, idx_t size_in_bits); | |
| 0 | 114 |
| 342 | 115 // Constructs an empty bitmap of the given size (that is, this clears the |
| 116 // new bitmap). Allocates the map array in resource area if | |
| 117 // "in_resource_area" is true, else in the C heap. | |
| 118 BitMap(idx_t size_in_bits, bool in_resource_area = true); | |
| 0 | 119 |
| 342 | 120 // Set the map and size. |
| 121 void set_map(bm_word_t* map) { _map = map; } | |
| 0 | 122 void set_size(idx_t size_in_bits) { _size = size_in_bits; } |
| 123 | |
| 342 | 124 // Allocates necessary data structure, either in the resource area |
| 125 // or in the C heap, as indicated by "in_resource_area." | |
| 0 | 126 // Preserves state currently in bit map by copying data. |
| 127 // Zeros any newly-addressable bits. | |
| 342 | 128 // If "in_resource_area" is false, frees the current map. |
| 129 // (Note that this assumes that all calls to "resize" on the same BitMap | |
| 130 // use the same value for "in_resource_area".) | |
| 131 void resize(idx_t size_in_bits, bool in_resource_area = true); | |
| 0 | 132 |
| 133 // Accessing | |
| 134 idx_t size() const { return _size; } | |
| 135 idx_t size_in_words() const { | |
| 136 return word_index(size() + BitsPerWord - 1); | |
| 137 } | |
| 138 | |
| 139 bool at(idx_t index) const { | |
| 140 verify_index(index); | |
| 141 return (*word_addr(index) & bit_mask(index)) != 0; | |
| 142 } | |
| 143 | |
| 144 // Align bit index up or down to the next bitmap word boundary, or check | |
| 145 // alignment. | |
| 146 static idx_t word_align_up(idx_t bit) { | |
| 147 return align_size_up(bit, BitsPerWord); | |
| 148 } | |
| 149 static idx_t word_align_down(idx_t bit) { | |
| 150 return align_size_down(bit, BitsPerWord); | |
| 151 } | |
| 152 static bool is_word_aligned(idx_t bit) { | |
| 153 return word_align_up(bit) == bit; | |
| 154 } | |
| 155 | |
| 156 // Set or clear the specified bit. | |
| 157 inline void set_bit(idx_t bit); | |
| 342 | 158 void clear_bit(idx_t bit); |
| 0 | 159 |
| 160 // Atomically set or clear the specified bit. | |
| 342 | 161 bool par_set_bit(idx_t bit); |
| 162 bool par_clear_bit(idx_t bit); | |
| 0 | 163 |
| 164 // Put the given value at the given offset. The parallel version | |
| 165 // will CAS the value into the bitmap and is quite a bit slower. | |
| 166 // The parallel version also returns a value indicating if the | |
| 167 // calling thread was the one that changed the value of the bit. | |
| 168 void at_put(idx_t index, bool value); | |
| 169 bool par_at_put(idx_t index, bool value); | |
| 170 | |
| 171 // Update a range of bits. Ranges are half-open [beg, end). | |
| 172 void set_range (idx_t beg, idx_t end); | |
| 173 void clear_range (idx_t beg, idx_t end); | |
| 174 void set_large_range (idx_t beg, idx_t end); | |
| 175 void clear_large_range (idx_t beg, idx_t end); | |
| 176 void at_put_range(idx_t beg, idx_t end, bool value); | |
| 177 void par_at_put_range(idx_t beg, idx_t end, bool value); | |
| 178 void at_put_large_range(idx_t beg, idx_t end, bool value); | |
| 179 void par_at_put_large_range(idx_t beg, idx_t end, bool value); | |
| 180 | |
| 181 // Update a range of bits, using a hint about the size. Currently only | |
| 182 // inlines the predominant case of a 1-bit range. Works best when hint is a | |
| 183 // compile-time constant. | |
| 342 | 184 void set_range(idx_t beg, idx_t end, RangeSizeHint hint); |
| 185 void clear_range(idx_t beg, idx_t end, RangeSizeHint hint); | |
| 186 void par_set_range(idx_t beg, idx_t end, RangeSizeHint hint); | |
| 187 void par_clear_range (idx_t beg, idx_t end, RangeSizeHint hint); | |
| 188 | |
| 189 // It performs the union operation between subsets of equal length | |
| 190 // of two bitmaps (the target bitmap of the method and the | |
| 191 // from_bitmap) and stores the result to the target bitmap. The | |
| 192 // from_start_index represents the first bit index of the subrange | |
| 193 // of the from_bitmap. The to_start_index is the equivalent of the | |
| 194 // target bitmap. Both indexes should be word-aligned, i.e. they | |
| 195 // should correspond to the first bit on a bitmap word (it's up to | |
| 196 // the caller to ensure this; the method does check it). The length | |
| 197 // of the subset is specified with word_num and it is in number of | |
| 198 // bitmap words. The caller should ensure that this is at least 2 | |
| 199 // (smaller ranges are not support to save extra checks). Again, | |
| 200 // this is checked in the method. | |
| 201 // | |
| 202 // Atomicity concerns: it is assumed that any contention on the | |
| 203 // target bitmap with other threads will happen on the first and | |
| 204 // last words; the ones in between will be "owned" exclusively by | |
| 205 // the calling thread and, in fact, they will already be 0. So, the | |
| 206 // method performs a CAS on the first word, copies the next | |
| 207 // word_num-2 words, and finally performs a CAS on the last word. | |
| 208 void mostly_disjoint_range_union(BitMap* from_bitmap, | |
| 209 idx_t from_start_index, | |
| 210 idx_t to_start_index, | |
| 211 size_t word_num); | |
| 212 | |
| 0 | 213 |
| 214 // Clearing | |
| 215 void clear_large(); | |
| 342 | 216 inline void clear(); |
| 0 | 217 |
| 342 | 218 // Iteration support. Returns "true" if the iteration completed, false |
| 219 // if the iteration terminated early (because the closure "blk" returned | |
| 220 // false). | |
| 221 bool iterate(BitMapClosure* blk, idx_t leftIndex, idx_t rightIndex); | |
| 222 bool iterate(BitMapClosure* blk) { | |
| 0 | 223 // call the version that takes an interval |
| 342 | 224 return iterate(blk, 0, size()); |
| 0 | 225 } |
| 226 | |
| 342 | 227 // Looking for 1's and 0's at indices equal to or greater than "l_index", |
| 228 // stopping if none has been found before "r_index", and returning | |
| 229 // "r_index" (which must be at most "size") in that case. | |
| 230 idx_t get_next_one_offset_inline (idx_t l_index, idx_t r_index) const; | |
| 231 idx_t get_next_zero_offset_inline(idx_t l_index, idx_t r_index) const; | |
| 232 | |
| 233 // Like "get_next_one_offset_inline", except requires that "r_index" is | |
| 234 // aligned to bitsizeof(bm_word_t). | |
| 235 idx_t get_next_one_offset_inline_aligned_right(idx_t l_index, | |
| 236 idx_t r_index) const; | |
| 237 | |
| 238 // Non-inline versionsof the above. | |
| 0 | 239 idx_t get_next_one_offset (idx_t l_index, idx_t r_index) const; |
| 240 idx_t get_next_zero_offset(idx_t l_index, idx_t r_index) const; | |
| 241 | |
| 242 idx_t get_next_one_offset(idx_t offset) const { | |
| 243 return get_next_one_offset(offset, size()); | |
| 244 } | |
| 245 idx_t get_next_zero_offset(idx_t offset) const { | |
| 246 return get_next_zero_offset(offset, size()); | |
| 247 } | |
| 248 | |
| 342 | 249 // Returns the number of bits set in the bitmap. |
| 250 idx_t count_one_bits() const; | |
| 0 | 251 |
| 252 // Set operations. | |
| 253 void set_union(BitMap bits); | |
| 254 void set_difference(BitMap bits); | |
| 255 void set_intersection(BitMap bits); | |
| 256 // Returns true iff "this" is a superset of "bits". | |
| 257 bool contains(const BitMap bits) const; | |
| 258 // Returns true iff "this and "bits" have a non-empty intersection. | |
| 259 bool intersects(const BitMap bits) const; | |
| 260 | |
| 261 // Returns result of whether this map changed | |
| 262 // during the operation | |
| 263 bool set_union_with_result(BitMap bits); | |
| 264 bool set_difference_with_result(BitMap bits); | |
| 265 bool set_intersection_with_result(BitMap bits); | |
| 266 | |
| 342 | 267 // Requires the submap of "bits" starting at offset to be at least as |
| 268 // large as "this". Modifies "this" to be the intersection of its | |
| 269 // current contents and the submap of "bits" starting at "offset" of the | |
| 270 // same length as "this." | |
| 271 // (For expedience, currently requires the offset to be aligned to the | |
| 272 // bitsize of a uintptr_t. This should go away in the future though it | |
| 273 // will probably remain a good case to optimize.) | |
| 274 void set_intersection_at_offset(BitMap bits, idx_t offset); | |
| 275 | |
| 0 | 276 void set_from(BitMap bits); |
| 277 | |
| 278 bool is_same(BitMap bits); | |
| 279 | |
| 280 // Test if all bits are set or cleared | |
| 281 bool is_full() const; | |
| 282 bool is_empty() const; | |
| 283 | |
| 284 | |
| 285 #ifndef PRODUCT | |
| 286 public: | |
| 287 // Printing | |
| 288 void print_on(outputStream* st) const; | |
| 289 #endif | |
| 290 }; | |
| 291 | |
| 292 // Convenience class wrapping BitMap which provides multiple bits per slot. | |
| 293 class BitMap2D VALUE_OBJ_CLASS_SPEC { | |
| 294 public: | |
| 342 | 295 typedef BitMap::idx_t idx_t; // Type used for bit and word indices. |
| 296 typedef BitMap::bm_word_t bm_word_t; // Element type of array that | |
| 297 // represents the bitmap. | |
| 0 | 298 private: |
| 299 BitMap _map; | |
| 300 idx_t _bits_per_slot; | |
| 301 | |
| 302 idx_t bit_index(idx_t slot_index, idx_t bit_within_slot_index) const { | |
| 303 return slot_index * _bits_per_slot + bit_within_slot_index; | |
| 304 } | |
| 305 | |
| 306 void verify_bit_within_slot_index(idx_t index) const { | |
| 307 assert(index < _bits_per_slot, "bit_within_slot index out of bounds"); | |
| 308 } | |
| 309 | |
| 310 public: | |
| 311 // Construction. bits_per_slot must be greater than 0. | |
| 342 | 312 BitMap2D(bm_word_t* map, idx_t size_in_slots, idx_t bits_per_slot); |
| 0 | 313 |
| 314 // Allocates necessary data structure in resource area. bits_per_slot must be greater than 0. | |
| 315 BitMap2D(idx_t size_in_slots, idx_t bits_per_slot); | |
| 316 | |
| 317 idx_t size_in_bits() { | |
| 318 return _map.size(); | |
| 319 } | |
| 320 | |
| 321 // Returns number of full slots that have been allocated | |
| 322 idx_t size_in_slots() { | |
| 323 // Round down | |
| 324 return _map.size() / _bits_per_slot; | |
| 325 } | |
| 326 | |
| 327 bool is_valid_index(idx_t slot_index, idx_t bit_within_slot_index) { | |
| 328 verify_bit_within_slot_index(bit_within_slot_index); | |
| 329 return (bit_index(slot_index, bit_within_slot_index) < size_in_bits()); | |
| 330 } | |
| 331 | |
| 332 bool at(idx_t slot_index, idx_t bit_within_slot_index) const { | |
| 333 verify_bit_within_slot_index(bit_within_slot_index); | |
| 334 return _map.at(bit_index(slot_index, bit_within_slot_index)); | |
| 335 } | |
| 336 | |
| 337 void set_bit(idx_t slot_index, idx_t bit_within_slot_index) { | |
| 338 verify_bit_within_slot_index(bit_within_slot_index); | |
| 339 _map.set_bit(bit_index(slot_index, bit_within_slot_index)); | |
| 340 } | |
| 341 | |
| 342 void clear_bit(idx_t slot_index, idx_t bit_within_slot_index) { | |
| 343 verify_bit_within_slot_index(bit_within_slot_index); | |
| 344 _map.clear_bit(bit_index(slot_index, bit_within_slot_index)); | |
| 345 } | |
| 346 | |
| 347 void at_put(idx_t slot_index, idx_t bit_within_slot_index, bool value) { | |
| 348 verify_bit_within_slot_index(bit_within_slot_index); | |
| 349 _map.at_put(bit_index(slot_index, bit_within_slot_index), value); | |
| 350 } | |
| 351 | |
| 352 void at_put_grow(idx_t slot_index, idx_t bit_within_slot_index, bool value) { | |
| 353 verify_bit_within_slot_index(bit_within_slot_index); | |
| 354 _map.at_put_grow(bit_index(slot_index, bit_within_slot_index), value); | |
| 355 } | |
| 356 | |
| 342 | 357 void clear(); |
| 0 | 358 }; |
| 359 | |
| 342 | 360 // Closure for iterating over BitMaps |
| 0 | 361 |
| 342 | 362 class BitMapClosure VALUE_OBJ_CLASS_SPEC { |
| 363 public: | |
| 364 // Callback when bit in map is set. Should normally return "true"; | |
| 365 // return of false indicates that the bitmap iteration should terminate. | |
| 366 virtual bool do_bit(BitMap::idx_t offset) = 0; | |
| 367 }; |