1 /*
2 * Copyright Amazon.com Inc. or its affiliates. All Rights Reserved.
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 Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 *
23 */
24
25 #include "precompiled.hpp"
26 #include "gc/shenandoah/shenandoahSimpleBitMap.hpp"
27
28 ShenandoahSimpleBitMap::ShenandoahSimpleBitMap(size_t num_bits) :
29 _num_bits(num_bits),
30 _num_words(align_up(num_bits, BitsPerWord) / BitsPerWord),
31 _bitmap(NEW_C_HEAP_ARRAY(uintx, _num_words, mtGC))
32 {
33 clear_all();
34 }
35
36 ShenandoahSimpleBitMap::~ShenandoahSimpleBitMap() {
37 if (_bitmap != nullptr) {
38 FREE_C_HEAP_ARRAY(uintx, _bitmap);
39 }
40 }
41
42 size_t ShenandoahSimpleBitMap::count_leading_ones(idx_t start_idx) const {
43 assert((start_idx >= 0) && (start_idx < _num_bits), "precondition");
44 size_t array_idx = start_idx >> LogBitsPerWord;
45 uintx element_bits = _bitmap[array_idx];
46 uintx bit_number = start_idx & right_n_bits(LogBitsPerWord);
47 uintx mask = ~right_n_bits(bit_number);
48 size_t counted_ones = 0;
49 while ((element_bits & mask) == mask) {
50 // All bits numbered >= bit_number are set
51 size_t found_ones = BitsPerWord - bit_number;
52 counted_ones += found_ones;
53 // Dead code: do not need to compute: start_idx += found_ones;
54 // Strength reduction: array_idx = (start_idx >> LogBitsPerWord)
55 array_idx++;
56 element_bits = _bitmap[array_idx];
57 // Constant folding: bit_number = start_idx & right_n_bits(LogBitsPerWord);
58 bit_number = 0;
59 // Constant folding: mask = ~right_n_bits(bit_number);
60 mask = ~0;
61 }
62
63 // Add in number of consecutive ones starting with the_bit and including more significant bits and return result
64 uintx aligned = element_bits >> bit_number;
65 uintx complement = ~aligned;
66 return counted_ones + count_trailing_zeros<uintx>(complement);
67 }
68
69 size_t ShenandoahSimpleBitMap::count_trailing_ones(idx_t last_idx) const {
70 assert((last_idx >= 0) && (last_idx < _num_bits), "precondition");
71 size_t array_idx = last_idx >> LogBitsPerWord;
72 uintx element_bits = _bitmap[array_idx];
73 uintx bit_number = last_idx & right_n_bits(LogBitsPerWord);
74 // All ones from bit 0 to the_bit
75 uintx mask = right_n_bits(bit_number + 1);
76 size_t counted_ones = 0;
77 while ((element_bits & mask) == mask) {
78 // All bits numbered <= bit_number are set
79 size_t found_ones = bit_number + 1;
80 counted_ones += found_ones;
81 // Dead code: do not need to compute: last_idx -= found_ones;
82 array_idx--;
83 element_bits = _bitmap[array_idx];
84 // Constant folding: bit_number = last_idx & right_n_bits(LogBitsPerWord);
85 bit_number = BitsPerWord - 1;
86 // Constant folding: mask = right_n_bits(bit_number + 1);
87 mask = ~0;
88 }
89
90 // Add in number of consecutive ones starting with the_bit and including less significant bits and return result
91 uintx aligned = element_bits << (BitsPerWord - (bit_number + 1));
92 uintx complement = ~aligned;
93 return counted_ones + count_leading_zeros<uintx>(complement);
94 }
95
96 bool ShenandoahSimpleBitMap::is_forward_consecutive_ones(idx_t start_idx, idx_t count) const {
97 while (count > 0) {
98 assert((start_idx >= 0) && (start_idx < _num_bits), "precondition: start_idx: " SSIZE_FORMAT ", count: " SSIZE_FORMAT,
99 start_idx, count);
100 assert(start_idx + count <= (idx_t) _num_bits, "precondition");
101 size_t array_idx = start_idx >> LogBitsPerWord;
102 uintx bit_number = start_idx & right_n_bits(LogBitsPerWord);
103 uintx element_bits = _bitmap[array_idx];
104 uintx bits_to_examine = BitsPerWord - bit_number;
105 element_bits >>= bit_number;
106 uintx complement = ~element_bits;
107 uintx trailing_ones;
108 if (complement != 0) {
109 trailing_ones = count_trailing_zeros<uintx>(complement);
110 } else {
111 trailing_ones = bits_to_examine;
112 }
113 if (trailing_ones >= (uintx) count) {
114 return true;
115 } else if (trailing_ones == bits_to_examine) {
116 start_idx += bits_to_examine;
117 count -= bits_to_examine;
118 // Repeat search with smaller goal
119 } else {
120 return false;
121 }
122 }
123 return true;
124 }
125
126 bool ShenandoahSimpleBitMap::is_backward_consecutive_ones(idx_t last_idx, idx_t count) const {
127 while (count > 0) {
128 assert((last_idx >= 0) && (last_idx < _num_bits), "precondition");
129 assert(last_idx - count >= -1, "precondition");
130 size_t array_idx = last_idx >> LogBitsPerWord;
131 uintx bit_number = last_idx & right_n_bits(LogBitsPerWord);
132 uintx element_bits = _bitmap[array_idx];
133 uintx bits_to_examine = bit_number + 1;
134 element_bits <<= (BitsPerWord - bits_to_examine);
135 uintx complement = ~element_bits;
136 uintx leading_ones;
137 if (complement != 0) {
138 leading_ones = count_leading_zeros<uintx>(complement);
139 } else {
140 leading_ones = bits_to_examine;
141 }
142 if (leading_ones >= (uintx) count) {
143 return true;
144 } else if (leading_ones == bits_to_examine) {
145 last_idx -= leading_ones;
146 count -= leading_ones;
147 // Repeat search with smaller goal
148 } else {
149 return false;
150 }
151 }
152 return true;
153 }
154
155 idx_t ShenandoahSimpleBitMap::find_first_consecutive_set_bits(idx_t beg, idx_t end, size_t num_bits) const {
156 assert((beg >= 0) && (beg < _num_bits), "precondition");
157
158 // Stop looking if there are not num_bits remaining in probe space.
159 idx_t start_boundary = end - num_bits;
160 if (beg > start_boundary) {
161 return end;
162 }
163 uintx array_idx = beg >> LogBitsPerWord;
164 uintx bit_number = beg & right_n_bits(LogBitsPerWord);
165 uintx element_bits = _bitmap[array_idx];
166 if (bit_number > 0) {
167 uintx mask_out = right_n_bits(bit_number);
168 element_bits &= ~mask_out;
169 }
170
171 // The following loop minimizes the number of spans probed in order to find num_bits consecutive bits.
172 // For example, if bit_number = beg = 0, num_bits = 8, and element bits equals 00111111_11000000_00000000_10011000B,
173 // we need only 3 probes to find the match at bit offset 22.
174 //
175 // Let beg = 0
176 // element_bits = 00111111_11000000_00000000_10011000B;
177 // ________ (the searched span)
178 // ^ ^ ^- bit_number = beg = 0
179 // | +-- next_start_candidate_1 (where next 1 is found)
180 // +------ next_start_candidate_2 (start of the trailing 1s within span)
181 // Let beg = 7
182 // element_bits = 00111111_11000000_00000000_10011000B;
183 // ^ ^_________ (the searched span)
184 // | | ^- bit_number = beg = 7
185 // | +---------- next_start_candidate_2 (there are no trailing 1s within span)
186 // +------------------ next_start_candidate_1 (where next 1 is found)
187 // Let beg = 22
188 // Let beg = 22
189 // element_bits = 00111111_11000001_11111100_10011000B;
190 // _________ (the searched span)
191 // ^- bit_number = beg = 18
192 // Here, is_forward_consecutive_ones(22, 8) succeeds and we report the match
193
194 while (true) {
195 if (element_bits == 0) {
196 // move to the next element
197 beg += BitsPerWord - bit_number;
198 if (beg > start_boundary) {
199 // No match found.
200 return end;
201 }
202 array_idx++;
203 bit_number = 0;
204 element_bits = _bitmap[array_idx];
205 } else if (is_forward_consecutive_ones(beg, num_bits)) {
206 return beg;
207 } else {
208 // There is at least one non-zero bit within the masked element_bits. Arrange to skip over bits that
209 // cannot be part of a consecutive-ones match.
210 uintx next_set_bit = count_trailing_zeros<uintx>(element_bits);
211 uintx next_start_candidate_1 = (array_idx << LogBitsPerWord) + next_set_bit;
212
213 // There is at least one zero bit in this span. Align the next probe at the start of trailing ones for probed span,
214 // or align at end of span if this span has no trailing ones.
215 size_t trailing_ones = count_trailing_ones(beg + num_bits - 1);
216 uintx next_start_candidate_2 = beg + num_bits - trailing_ones;
217
218 beg = MAX2(next_start_candidate_1, next_start_candidate_2);
219 if (beg > start_boundary) {
220 // No match found.
221 return end;
222 }
223 array_idx = beg >> LogBitsPerWord;
224 element_bits = _bitmap[array_idx];
225 bit_number = beg & right_n_bits(LogBitsPerWord);
226 if (bit_number > 0) {
227 size_t mask_out = right_n_bits(bit_number);
228 element_bits &= ~mask_out;
229 }
230 }
231 }
232 }
233
234 idx_t ShenandoahSimpleBitMap::find_last_consecutive_set_bits(const idx_t beg, idx_t end, const size_t num_bits) const {
235
236 assert((end >= 0) && (end < _num_bits), "precondition");
237
238 // Stop looking if there are not num_bits remaining in probe space.
239 idx_t last_boundary = beg + num_bits;
240 if (end < last_boundary) {
241 return beg;
242 }
243
244 size_t array_idx = end >> LogBitsPerWord;
245 uintx bit_number = end & right_n_bits(LogBitsPerWord);
246 uintx element_bits = _bitmap[array_idx];
247 if (bit_number < BitsPerWord - 1) {
248 uintx mask_in = right_n_bits(bit_number + 1);
249 element_bits &= mask_in;
250 }
251
252 // See comment in find_first_consecutive_set_bits to understand how this loop works.
253 while (true) {
254 if (element_bits == 0) {
255 // move to the previous element
256 end -= bit_number + 1;
257 if (end < last_boundary) {
258 // No match found.
259 return beg;
260 }
261 array_idx--;
262 bit_number = BitsPerWord - 1;
263 element_bits = _bitmap[array_idx];
264 } else if (is_backward_consecutive_ones(end, num_bits)) {
265 return end + 1 - num_bits;
266 } else {
267 // There is at least one non-zero bit within the masked element_bits. Arrange to skip over bits that
268 // cannot be part of a consecutive-ones match.
269 uintx next_set_bit = BitsPerWord - (1 + count_leading_zeros<uintx>(element_bits));
270 uintx next_last_candidate_1 = (array_idx << LogBitsPerWord) + next_set_bit;
271
272 // There is at least one zero bit in this span. Align the next probe at the end of leading ones for probed span,
273 // or align before start of span if this span has no leading ones.
274 size_t leading_ones = count_leading_ones(end - (num_bits - 1));
275 uintx next_last_candidate_2 = end - (num_bits - leading_ones);
276
277 end = MIN2(next_last_candidate_1, next_last_candidate_2);
278 if (end < last_boundary) {
279 // No match found.
280 return beg;
281 }
282 array_idx = end >> LogBitsPerWord;
283 bit_number = end & right_n_bits(LogBitsPerWord);
284 element_bits = _bitmap[array_idx];
285 if (bit_number < BitsPerWord - 1){
286 size_t mask_in = right_n_bits(bit_number + 1);
287 element_bits &= mask_in;
288 }
289 }
290 }
291 }