jdk

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
}
292