Branch data Line data Source code
1 : : /* Simple bitmaps.
2 : : Copyright (C) 1999-2025 Free Software Foundation, Inc.
3 : :
4 : : This file is part of GCC.
5 : :
6 : : GCC is free software; you can redistribute it and/or modify it under
7 : : the terms of the GNU General Public License as published by the Free
8 : : Software Foundation; either version 3, or (at your option) any later
9 : : version.
10 : :
11 : : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 : : WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 : : FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 : : for more details.
15 : :
16 : : You should have received a copy of the GNU General Public License
17 : : along with GCC; see the file COPYING3. If not see
18 : : <http://www.gnu.org/licenses/>. */
19 : :
20 : : #include "config.h"
21 : : #include "system.h"
22 : : #include "coretypes.h"
23 : : #include "sbitmap.h"
24 : : #include "selftest.h"
25 : :
26 : : typedef SBITMAP_ELT_TYPE *sbitmap_ptr;
27 : : typedef const SBITMAP_ELT_TYPE *const_sbitmap_ptr;
28 : :
29 : : /* Return the size in bytes of a bitmap MAP. */
30 : :
31 : 1277414444 : static inline unsigned int sbitmap_size_bytes (const_sbitmap map)
32 : : {
33 : 1277414444 : return map->size * sizeof (SBITMAP_ELT_TYPE);
34 : : }
35 : :
36 : :
37 : : /* Bitmap manipulation routines. */
38 : :
39 : : /* Allocate a simple bitmap of N_ELMS bits. */
40 : :
41 : : sbitmap
42 : 920831826 : sbitmap_alloc (unsigned int n_elms)
43 : : {
44 : 920831826 : unsigned int bytes, size, amt;
45 : 920831826 : sbitmap bmap;
46 : :
47 : 920831826 : size = SBITMAP_SET_SIZE (n_elms);
48 : 920831826 : bytes = size * sizeof (SBITMAP_ELT_TYPE);
49 : 920831826 : amt = (sizeof (struct simple_bitmap_def)
50 : : + bytes - sizeof (SBITMAP_ELT_TYPE));
51 : 920831826 : bmap = (sbitmap) xmalloc (amt);
52 : 920831826 : bmap->n_bits = n_elms;
53 : 920831826 : bmap->size = size;
54 : 920831826 : return bmap;
55 : : }
56 : :
57 : : /* Resize a simple bitmap BMAP to N_ELMS bits. If increasing the
58 : : size of BMAP, clear the new bits to zero if the DEF argument
59 : : is zero, and set them to one otherwise. */
60 : :
61 : : sbitmap
62 : 1545090 : sbitmap_resize (sbitmap bmap, unsigned int n_elms, int def)
63 : : {
64 : 1545090 : unsigned int bytes, size, amt;
65 : 1545090 : unsigned int last_bit;
66 : :
67 : 1545090 : size = SBITMAP_SET_SIZE (n_elms);
68 : 1545090 : bytes = size * sizeof (SBITMAP_ELT_TYPE);
69 : 1545090 : if (bytes > sbitmap_size_bytes (bmap))
70 : : {
71 : 358466 : amt = (sizeof (struct simple_bitmap_def)
72 : : + bytes - sizeof (SBITMAP_ELT_TYPE));
73 : 358466 : bmap = (sbitmap) xrealloc (bmap, amt);
74 : : }
75 : :
76 : 1545090 : if (n_elms > bmap->n_bits)
77 : : {
78 : 1545090 : if (def)
79 : : {
80 : 0 : memset (bmap->elms + bmap->size, -1,
81 : 0 : bytes - sbitmap_size_bytes (bmap));
82 : :
83 : : /* Set the new bits if the original last element. */
84 : 0 : last_bit = bmap->n_bits % SBITMAP_ELT_BITS;
85 : 0 : if (last_bit)
86 : 0 : bmap->elms[bmap->size - 1]
87 : 0 : |= ~((SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit));
88 : :
89 : : /* Clear the unused bit in the new last element. */
90 : 0 : last_bit = n_elms % SBITMAP_ELT_BITS;
91 : 0 : if (last_bit)
92 : 0 : bmap->elms[size - 1]
93 : 0 : &= (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit);
94 : : }
95 : : else
96 : 1545090 : memset (bmap->elms + bmap->size, 0, bytes - sbitmap_size_bytes (bmap));
97 : : }
98 : 0 : else if (n_elms < bmap->n_bits)
99 : : {
100 : : /* Clear the surplus bits in the last word. */
101 : 0 : last_bit = n_elms % SBITMAP_ELT_BITS;
102 : 0 : if (last_bit)
103 : 0 : bmap->elms[size - 1]
104 : 0 : &= (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit);
105 : : }
106 : :
107 : 1545090 : bmap->n_bits = n_elms;
108 : 1545090 : bmap->size = size;
109 : 1545090 : return bmap;
110 : : }
111 : :
112 : : /* Re-allocate a simple bitmap of N_ELMS bits. New storage is uninitialized. */
113 : :
114 : : sbitmap
115 : 0 : sbitmap_realloc (sbitmap src, unsigned int n_elms)
116 : : {
117 : 0 : unsigned int bytes, size, amt;
118 : 0 : sbitmap bmap;
119 : :
120 : 0 : size = SBITMAP_SET_SIZE (n_elms);
121 : 0 : bytes = size * sizeof (SBITMAP_ELT_TYPE);
122 : 0 : amt = (sizeof (struct simple_bitmap_def)
123 : : + bytes - sizeof (SBITMAP_ELT_TYPE));
124 : :
125 : 0 : if (sbitmap_size_bytes (src) >= bytes)
126 : : {
127 : 0 : src->n_bits = n_elms;
128 : 0 : return src;
129 : : }
130 : :
131 : 0 : bmap = (sbitmap) xrealloc (src, amt);
132 : 0 : bmap->n_bits = n_elms;
133 : 0 : bmap->size = size;
134 : 0 : return bmap;
135 : : }
136 : :
137 : : /* Allocate a vector of N_VECS bitmaps of N_ELMS bits. */
138 : :
139 : : sbitmap *
140 : 12055670 : sbitmap_vector_alloc (unsigned int n_vecs, unsigned int n_elms)
141 : : {
142 : 12055670 : unsigned int i, size;
143 : 12055670 : size_t amt, bytes, vector_bytes, elm_bytes, offset;
144 : 12055670 : sbitmap *bitmap_vector;
145 : :
146 : 12055670 : size = SBITMAP_SET_SIZE (n_elms);
147 : 12055670 : bytes = size * sizeof (SBITMAP_ELT_TYPE);
148 : 12055670 : elm_bytes = (sizeof (struct simple_bitmap_def)
149 : : + bytes - sizeof (SBITMAP_ELT_TYPE));
150 : 12055670 : vector_bytes = n_vecs * sizeof (sbitmap *);
151 : :
152 : : /* Round up `vector_bytes' to account for the alignment requirements
153 : : of an sbitmap. One could allocate the vector-table and set of sbitmaps
154 : : separately, but that requires maintaining two pointers or creating
155 : : a cover struct to hold both pointers (so our result is still just
156 : : one pointer). Neither is a bad idea, but this is simpler for now. */
157 : 12055670 : {
158 : : /* Based on DEFAULT_ALIGNMENT computation in obstack.c. */
159 : 12055670 : struct { char x; SBITMAP_ELT_TYPE y; } align;
160 : 12055670 : int alignment = (char *) & align.y - & align.x;
161 : 12055670 : vector_bytes = (vector_bytes + alignment - 1) & ~ (alignment - 1);
162 : : }
163 : :
164 : 12055670 : amt = vector_bytes + (n_vecs * elm_bytes);
165 : 12055670 : bitmap_vector = (sbitmap *) xmalloc (amt);
166 : :
167 : 312544672 : for (i = 0, offset = vector_bytes; i < n_vecs; i++, offset += elm_bytes)
168 : : {
169 : 300489002 : sbitmap b = (sbitmap) ((char *) bitmap_vector + offset);
170 : :
171 : 300489002 : bitmap_vector[i] = b;
172 : 300489002 : b->n_bits = n_elms;
173 : 300489002 : b->size = size;
174 : : }
175 : :
176 : 12055670 : return bitmap_vector;
177 : : }
178 : :
179 : : /* Copy sbitmap SRC to DST. */
180 : :
181 : : void
182 : 64298363 : bitmap_copy (sbitmap dst, const_sbitmap src)
183 : : {
184 : 64298363 : gcc_checking_assert (src->size <= dst->size);
185 : :
186 : 64298363 : memcpy (dst->elms, src->elms, sizeof (SBITMAP_ELT_TYPE) * dst->size);
187 : 64298363 : }
188 : :
189 : : /* Determine if a == b. */
190 : : bool
191 : 0 : bitmap_equal_p (const_sbitmap a, const_sbitmap b)
192 : : {
193 : 0 : bitmap_check_sizes (a, b);
194 : :
195 : 0 : return !memcmp (a->elms, b->elms, sizeof (SBITMAP_ELT_TYPE) * a->size);
196 : : }
197 : :
198 : : /* Return true if the bitmap is empty. */
199 : :
200 : : bool
201 : 175414109 : bitmap_empty_p (const_sbitmap bmap)
202 : : {
203 : 175414109 : unsigned int i;
204 : 191290761 : for (i=0; i<bmap->size; i++)
205 : 186935504 : if (bmap->elms[i])
206 : : return false;
207 : :
208 : : return true;
209 : : }
210 : :
211 : : /* Clear COUNT bits from START in BMAP. */
212 : :
213 : : void
214 : 4472302 : bitmap_clear_range (sbitmap bmap, unsigned int start, unsigned int count)
215 : : {
216 : 4472302 : if (count == 0)
217 : : return;
218 : :
219 : 3063470 : bitmap_check_index (bmap, start + count - 1);
220 : :
221 : 3063470 : unsigned int start_word = start / SBITMAP_ELT_BITS;
222 : 3063470 : unsigned int start_bitno = start % SBITMAP_ELT_BITS;
223 : :
224 : : /* Clearing less than a full word, starting at the beginning of a word. */
225 : 3063470 : if (start_bitno == 0 && count < SBITMAP_ELT_BITS)
226 : : {
227 : 1061421 : SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE)1 << count) - 1;
228 : 1061421 : bmap->elms[start_word] &= ~mask;
229 : 1061421 : return;
230 : : }
231 : :
232 : 2002049 : unsigned int end_word = (start + count) / SBITMAP_ELT_BITS;
233 : 2002049 : unsigned int end_bitno = (start + count) % SBITMAP_ELT_BITS;
234 : :
235 : : /* Clearing starts somewhere in the middle of the first word. Clear up to
236 : : the end of the first word or the end of the requested region, whichever
237 : : comes first. */
238 : 2002049 : if (start_bitno != 0)
239 : : {
240 : 3977286 : unsigned int nbits = ((start_word == end_word)
241 : 1988643 : ? end_bitno - start_bitno
242 : : : SBITMAP_ELT_BITS - start_bitno);
243 : 1988643 : SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE)1 << nbits) - 1;
244 : 1988643 : mask <<= start_bitno;
245 : 1988643 : bmap->elms[start_word] &= ~mask;
246 : 1988643 : start_word++;
247 : 1988643 : count -= nbits;
248 : : }
249 : :
250 : 2002049 : if (count == 0)
251 : : return;
252 : :
253 : : /* Now clear words at a time until we hit a partial word. */
254 : 25318 : unsigned int nwords = (end_word - start_word);
255 : 25318 : if (nwords)
256 : : {
257 : 13528 : memset (&bmap->elms[start_word], 0, nwords * sizeof (SBITMAP_ELT_TYPE));
258 : 13528 : count -= nwords * sizeof (SBITMAP_ELT_TYPE) * BITS_PER_UNIT;
259 : 13528 : start_word += nwords;
260 : : }
261 : :
262 : 25318 : if (count == 0)
263 : : return;
264 : :
265 : : /* Now handle residuals in the last word. */
266 : 15313 : SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE)1 << count) - 1;
267 : 15313 : bmap->elms[start_word] &= ~mask;
268 : : }
269 : :
270 : : /* Set COUNT bits from START in BMAP. */
271 : : void
272 : 29527192 : bitmap_set_range (sbitmap bmap, unsigned int start, unsigned int count)
273 : : {
274 : 29527192 : if (count == 0)
275 : : return;
276 : :
277 : 29527192 : bitmap_check_index (bmap, start + count - 1);
278 : :
279 : 29527192 : unsigned int start_word = start / SBITMAP_ELT_BITS;
280 : 29527192 : unsigned int start_bitno = start % SBITMAP_ELT_BITS;
281 : :
282 : : /* Setting less than a full word, starting at the beginning of a word. */
283 : 29527192 : if (start_bitno == 0 && count < SBITMAP_ELT_BITS)
284 : : {
285 : 28960585 : SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE)1 << count) - 1;
286 : 28960585 : bmap->elms[start_word] |= mask;
287 : 28960585 : return;
288 : : }
289 : :
290 : 566607 : unsigned int end_word = (start + count) / SBITMAP_ELT_BITS;
291 : 566607 : unsigned int end_bitno = (start + count) % SBITMAP_ELT_BITS;
292 : :
293 : : /* Setting starts somewhere in the middle of the first word. Set up to
294 : : the end of the first word or the end of the requested region, whichever
295 : : comes first. */
296 : 566607 : if (start_bitno != 0)
297 : : {
298 : 108 : unsigned int nbits = ((start_word == end_word)
299 : 54 : ? end_bitno - start_bitno
300 : : : SBITMAP_ELT_BITS - start_bitno);
301 : 54 : SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE)1 << nbits) - 1;
302 : 54 : mask <<= start_bitno;
303 : 54 : bmap->elms[start_word] |= mask;
304 : 54 : start_word++;
305 : 54 : count -= nbits;
306 : : }
307 : :
308 : 566607 : if (count == 0)
309 : : return;
310 : :
311 : : /* Now set words at a time until we hit a partial word. */
312 : 566553 : unsigned int nwords = (end_word - start_word);
313 : 566553 : if (nwords)
314 : : {
315 : 566553 : memset (&bmap->elms[start_word], 0xff,
316 : 566553 : nwords * sizeof (SBITMAP_ELT_TYPE));
317 : 566553 : count -= nwords * sizeof (SBITMAP_ELT_TYPE) * BITS_PER_UNIT;
318 : 566553 : start_word += nwords;
319 : : }
320 : :
321 : 566553 : if (count == 0)
322 : : return;
323 : :
324 : : /* Now handle residuals in the last word. */
325 : 337083 : SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE)1 << count) - 1;
326 : 337083 : bmap->elms[start_word] |= mask;
327 : : }
328 : :
329 : : /* Return TRUE if any bit between START and END inclusive is set within
330 : : the simple bitmap BMAP. Return FALSE otherwise. */
331 : :
332 : : bool
333 : 1067084 : bitmap_bit_in_range_p (const_sbitmap bmap, unsigned int start, unsigned int end)
334 : : {
335 : 1067084 : gcc_checking_assert (start <= end);
336 : 1067084 : bitmap_check_index (bmap, end);
337 : :
338 : 1067084 : unsigned int start_word = start / SBITMAP_ELT_BITS;
339 : 1067084 : unsigned int start_bitno = start % SBITMAP_ELT_BITS;
340 : :
341 : 1067084 : unsigned int end_word = end / SBITMAP_ELT_BITS;
342 : 1067084 : unsigned int end_bitno = end % SBITMAP_ELT_BITS;
343 : :
344 : : /* Check beginning of first word if different from zero. */
345 : 1067084 : if (start_bitno != 0)
346 : : {
347 : 832049 : SBITMAP_ELT_TYPE high_mask = ~(SBITMAP_ELT_TYPE)0;
348 : 832049 : if (start_word == end_word && end_bitno + 1 < SBITMAP_ELT_BITS)
349 : 821756 : high_mask = ((SBITMAP_ELT_TYPE)1 << (end_bitno + 1)) - 1;
350 : :
351 : 832049 : SBITMAP_ELT_TYPE low_mask = ((SBITMAP_ELT_TYPE)1 << start_bitno) - 1;
352 : 832049 : SBITMAP_ELT_TYPE mask = high_mask - low_mask;
353 : 832049 : if (bmap->elms[start_word] & mask)
354 : : return true;
355 : 3117 : start_word++;
356 : : }
357 : :
358 : 238152 : if (start_word > end_word)
359 : : return false;
360 : :
361 : : /* Now test words at a time until we hit a partial word. */
362 : 235071 : unsigned int nwords = (end_word - start_word);
363 : 235419 : while (nwords)
364 : : {
365 : 9409 : if (bmap->elms[start_word])
366 : : return true;
367 : 348 : start_word++;
368 : 348 : nwords--;
369 : : }
370 : :
371 : : /* Now handle residuals in the last word. */
372 : 226010 : SBITMAP_ELT_TYPE mask = ~(SBITMAP_ELT_TYPE)0;
373 : 226010 : if (end_bitno + 1 < SBITMAP_ELT_BITS)
374 : 219037 : mask = ((SBITMAP_ELT_TYPE)1 << (end_bitno + 1)) - 1;
375 : 226010 : return (bmap->elms[start_word] & mask) != 0;
376 : : }
377 : :
378 : : #if GCC_VERSION < 3400
379 : : /* Table of number of set bits in a character, indexed by value of char. */
380 : : static const unsigned char popcount_table[] =
381 : : {
382 : : 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
383 : : 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
384 : : 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
385 : : 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
386 : : 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
387 : : 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
388 : : 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
389 : : 3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
390 : : };
391 : :
392 : : static unsigned long
393 : : sbitmap_popcount (SBITMAP_ELT_TYPE a)
394 : : {
395 : : unsigned long ret = 0;
396 : : unsigned i;
397 : :
398 : : /* Just do this the table way for now */
399 : : for (i = 0; i < HOST_BITS_PER_WIDEST_FAST_INT; i += 8)
400 : : ret += popcount_table[(a >> i) & 0xff];
401 : : return ret;
402 : : }
403 : : #endif
404 : :
405 : : /* Count and return the number of bits set in the bitmap BMAP. */
406 : :
407 : : unsigned int
408 : 578 : bitmap_count_bits (const_sbitmap bmap)
409 : : {
410 : 578 : unsigned int count = 0;
411 : 1158 : for (unsigned int i = 0; i < bmap->size; i++)
412 : 580 : if (bmap->elms[i])
413 : : {
414 : : #if GCC_VERSION < 3400
415 : : count += sbitmap_popcount (bmap->elms[i]);
416 : : #else
417 : : # if HOST_BITS_PER_WIDEST_FAST_INT == HOST_BITS_PER_LONG
418 : 580 : count += __builtin_popcountl (bmap->elms[i]);
419 : : # elif HOST_BITS_PER_WIDEST_FAST_INT == HOST_BITS_PER_LONGLONG
420 : : count += __builtin_popcountll (bmap->elms[i]);
421 : : # else
422 : : count += __builtin_popcount (bmap->elms[i]);
423 : : # endif
424 : : #endif
425 : : }
426 : 578 : return count;
427 : : }
428 : :
429 : : /* Zero all elements in a bitmap. */
430 : :
431 : : void
432 : 1180547631 : bitmap_clear (sbitmap bmap)
433 : : {
434 : 1180547631 : memset (bmap->elms, 0, sbitmap_size_bytes (bmap));
435 : 1180547631 : }
436 : :
437 : : /* Set all elements in a bitmap to ones. */
438 : :
439 : : void
440 : 93776633 : bitmap_ones (sbitmap bmap)
441 : : {
442 : 93776633 : unsigned int last_bit;
443 : :
444 : 93776633 : memset (bmap->elms, -1, sbitmap_size_bytes (bmap));
445 : :
446 : 93776633 : last_bit = bmap->n_bits % SBITMAP_ELT_BITS;
447 : 93776633 : if (last_bit)
448 : 93192003 : bmap->elms[bmap->size - 1]
449 : 93192003 : = (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit);
450 : 93776633 : }
451 : :
452 : : /* Zero a vector of N_VECS bitmaps. */
453 : :
454 : : void
455 : 5455381 : bitmap_vector_clear (sbitmap *bmap, unsigned int n_vecs)
456 : : {
457 : 5455381 : unsigned int i;
458 : :
459 : 143576532 : for (i = 0; i < n_vecs; i++)
460 : 138121151 : bitmap_clear (bmap[i]);
461 : 5455381 : }
462 : :
463 : : /* Set a vector of N_VECS bitmaps to ones. */
464 : :
465 : : void
466 : 3290744 : bitmap_vector_ones (sbitmap *bmap, unsigned int n_vecs)
467 : : {
468 : 3290744 : unsigned int i;
469 : :
470 : 84526107 : for (i = 0; i < n_vecs; i++)
471 : 81235363 : bitmap_ones (bmap[i]);
472 : 3290744 : }
473 : :
474 : : /* Set DST to be A union (B - C).
475 : : DST = A | (B & ~C).
476 : : Returns true if any change is made. */
477 : :
478 : : bool
479 : 70100618 : bitmap_ior_and_compl (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
480 : : {
481 : 70100618 : bitmap_check_sizes (a, b);
482 : 70100618 : bitmap_check_sizes (b, c);
483 : :
484 : 70100618 : unsigned int i, n = dst->size;
485 : 70100618 : sbitmap_ptr dstp = dst->elms;
486 : 70100618 : const_sbitmap_ptr ap = a->elms;
487 : 70100618 : const_sbitmap_ptr bp = b->elms;
488 : 70100618 : const_sbitmap_ptr cp = c->elms;
489 : 70100618 : SBITMAP_ELT_TYPE changed = 0;
490 : :
491 : 290566718 : for (i = 0; i < n; i++)
492 : : {
493 : 220466100 : const SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & ~*cp++);
494 : 220466100 : changed |= *dstp ^ tmp;
495 : 220466100 : *dstp++ = tmp;
496 : : }
497 : :
498 : 70100618 : return changed != 0;
499 : : }
500 : :
501 : : /* Set bitmap DST to the bitwise negation of the bitmap SRC. */
502 : :
503 : : void
504 : 22113410 : bitmap_not (sbitmap dst, const_sbitmap src)
505 : : {
506 : 22113410 : bitmap_check_sizes (src, dst);
507 : :
508 : 22113410 : unsigned int i, n = dst->size;
509 : 22113410 : sbitmap_ptr dstp = dst->elms;
510 : 22113410 : const_sbitmap_ptr srcp = src->elms;
511 : 22113410 : unsigned int last_bit;
512 : :
513 : 80543015 : for (i = 0; i < n; i++)
514 : 58429605 : *dstp++ = ~*srcp++;
515 : :
516 : : /* Zero all bits past n_bits, by ANDing dst with bitmap_ones. */
517 : 22113410 : last_bit = src->n_bits % SBITMAP_ELT_BITS;
518 : 22113410 : if (last_bit)
519 : 21933556 : dst->elms[n-1] = dst->elms[n-1]
520 : 21933556 : & ((SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit));
521 : 22113410 : }
522 : :
523 : : /* Set the bits in DST to be the difference between the bits
524 : : in A and the bits in B. i.e. dst = a & (~b). */
525 : :
526 : : void
527 : 36838899 : bitmap_and_compl (sbitmap dst, const_sbitmap a, const_sbitmap b)
528 : : {
529 : 36838899 : bitmap_check_sizes (a, b);
530 : 36838899 : bitmap_check_sizes (b, dst);
531 : :
532 : 36838899 : unsigned int i, dst_size = dst->size;
533 : 36838899 : unsigned int min_size = dst->size;
534 : 36838899 : sbitmap_ptr dstp = dst->elms;
535 : 36838899 : const_sbitmap_ptr ap = a->elms;
536 : 36838899 : const_sbitmap_ptr bp = b->elms;
537 : :
538 : : /* A should be at least as large as DEST, to have a defined source. */
539 : 36838899 : gcc_assert (a->size >= dst_size);
540 : : /* If minuend is smaller, we simply pretend it to be zero bits, i.e.
541 : : only copy the subtrahend into dest. */
542 : 36838899 : if (b->size < min_size)
543 : : min_size = b->size;
544 : 132859021 : for (i = 0; i < min_size; i++)
545 : 96020122 : *dstp++ = *ap++ & (~*bp++);
546 : : /* Now fill the rest of dest from A, if B was too short.
547 : : This makes sense only when destination and A differ. */
548 : 36838899 : if (dst != a && i != dst_size)
549 : 0 : for (; i < dst_size; i++)
550 : 0 : *dstp++ = *ap++;
551 : 36838899 : }
552 : :
553 : : /* Return true if there are any bits set in A are also set in B.
554 : : Return false otherwise. */
555 : :
556 : : bool
557 : 0 : bitmap_intersect_p (const_sbitmap a, const_sbitmap b)
558 : : {
559 : 0 : bitmap_check_sizes (a, b);
560 : :
561 : 0 : const_sbitmap_ptr ap = a->elms;
562 : 0 : const_sbitmap_ptr bp = b->elms;
563 : 0 : unsigned int i, n;
564 : :
565 : 0 : n = MIN (a->size, b->size);
566 : 0 : for (i = 0; i < n; i++)
567 : 0 : if ((*ap++ & *bp++) != 0)
568 : : return true;
569 : :
570 : : return false;
571 : : }
572 : :
573 : : /* Set DST to be (A and B).
574 : : Return nonzero if any change is made. */
575 : :
576 : : bool
577 : 15928476 : bitmap_and (sbitmap dst, const_sbitmap a, const_sbitmap b)
578 : : {
579 : 15928476 : bitmap_check_sizes (a, b);
580 : 15928476 : bitmap_check_sizes (b, dst);
581 : :
582 : 15928476 : unsigned int i, n = dst->size;
583 : 15928476 : sbitmap_ptr dstp = dst->elms;
584 : 15928476 : const_sbitmap_ptr ap = a->elms;
585 : 15928476 : const_sbitmap_ptr bp = b->elms;
586 : 15928476 : SBITMAP_ELT_TYPE changed = 0;
587 : :
588 : 57495208 : for (i = 0; i < n; i++)
589 : : {
590 : 41566732 : const SBITMAP_ELT_TYPE tmp = *ap++ & *bp++;
591 : 41566732 : SBITMAP_ELT_TYPE wordchanged = *dstp ^ tmp;
592 : 41566732 : *dstp++ = tmp;
593 : 41566732 : changed |= wordchanged;
594 : : }
595 : 15928476 : return changed != 0;
596 : : }
597 : :
598 : : /* Set DST to be (A xor B)).
599 : : Return nonzero if any change is made. */
600 : :
601 : : bool
602 : 0 : bitmap_xor (sbitmap dst, const_sbitmap a, const_sbitmap b)
603 : : {
604 : 0 : bitmap_check_sizes (a, b);
605 : 0 : bitmap_check_sizes (b, dst);
606 : :
607 : 0 : unsigned int i, n = dst->size;
608 : 0 : sbitmap_ptr dstp = dst->elms;
609 : 0 : const_sbitmap_ptr ap = a->elms;
610 : 0 : const_sbitmap_ptr bp = b->elms;
611 : 0 : SBITMAP_ELT_TYPE changed = 0;
612 : :
613 : 0 : for (i = 0; i < n; i++)
614 : : {
615 : 0 : const SBITMAP_ELT_TYPE tmp = *ap++ ^ *bp++;
616 : 0 : SBITMAP_ELT_TYPE wordchanged = *dstp ^ tmp;
617 : 0 : *dstp++ = tmp;
618 : 0 : changed |= wordchanged;
619 : : }
620 : 0 : return changed != 0;
621 : : }
622 : :
623 : : /* Set DST to be (A or B)).
624 : : Return nonzero if any change is made. */
625 : :
626 : : bool
627 : 12276186 : bitmap_ior (sbitmap dst, const_sbitmap a, const_sbitmap b)
628 : : {
629 : 12276186 : bitmap_check_sizes (a, b);
630 : 12276186 : bitmap_check_sizes (b, dst);
631 : :
632 : 12276186 : unsigned int i, n = dst->size;
633 : 12276186 : sbitmap_ptr dstp = dst->elms;
634 : 12276186 : const_sbitmap_ptr ap = a->elms;
635 : 12276186 : const_sbitmap_ptr bp = b->elms;
636 : 12276186 : SBITMAP_ELT_TYPE changed = 0;
637 : :
638 : 45903143 : for (i = 0; i < n; i++)
639 : : {
640 : 33626957 : const SBITMAP_ELT_TYPE tmp = *ap++ | *bp++;
641 : 33626957 : SBITMAP_ELT_TYPE wordchanged = *dstp ^ tmp;
642 : 33626957 : *dstp++ = tmp;
643 : 33626957 : changed |= wordchanged;
644 : : }
645 : 12276186 : return changed != 0;
646 : : }
647 : :
648 : : /* Return nonzero if A is a subset of B. */
649 : :
650 : : bool
651 : 0 : bitmap_subset_p (const_sbitmap a, const_sbitmap b)
652 : : {
653 : 0 : bitmap_check_sizes (a, b);
654 : :
655 : 0 : unsigned int i, n = a->size;
656 : 0 : const_sbitmap_ptr ap, bp;
657 : :
658 : 0 : for (ap = a->elms, bp = b->elms, i = 0; i < n; i++, ap++, bp++)
659 : 0 : if ((*ap | *bp) != *bp)
660 : : return false;
661 : :
662 : : return true;
663 : : }
664 : :
665 : : /* Set DST to be (A or (B and C)).
666 : : Return nonzero if any change is made. */
667 : :
668 : : bool
669 : 10846772 : bitmap_or_and (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
670 : : {
671 : 10846772 : bitmap_check_sizes (a, b);
672 : 10846772 : bitmap_check_sizes (b, c);
673 : 10846772 : bitmap_check_sizes (c, dst);
674 : :
675 : 10846772 : unsigned int i, n = dst->size;
676 : 10846772 : sbitmap_ptr dstp = dst->elms;
677 : 10846772 : const_sbitmap_ptr ap = a->elms;
678 : 10846772 : const_sbitmap_ptr bp = b->elms;
679 : 10846772 : const_sbitmap_ptr cp = c->elms;
680 : 10846772 : SBITMAP_ELT_TYPE changed = 0;
681 : :
682 : 39943372 : for (i = 0; i < n; i++)
683 : : {
684 : 29096600 : const SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & *cp++);
685 : 29096600 : changed |= *dstp ^ tmp;
686 : 29096600 : *dstp++ = tmp;
687 : : }
688 : :
689 : 10846772 : return changed != 0;
690 : : }
691 : :
692 : : /* Set DST to be (A and (B or C)).
693 : : Return nonzero if any change is made. */
694 : :
695 : : bool
696 : 12990320 : bitmap_and_or (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
697 : : {
698 : 12990320 : bitmap_check_sizes (a, b);
699 : 12990320 : bitmap_check_sizes (b, c);
700 : 12990320 : bitmap_check_sizes (c, dst);
701 : :
702 : 12990320 : unsigned int i, n = dst->size;
703 : 12990320 : sbitmap_ptr dstp = dst->elms;
704 : 12990320 : const_sbitmap_ptr ap = a->elms;
705 : 12990320 : const_sbitmap_ptr bp = b->elms;
706 : 12990320 : const_sbitmap_ptr cp = c->elms;
707 : 12990320 : SBITMAP_ELT_TYPE changed = 0;
708 : :
709 : 48008536 : for (i = 0; i < n; i++)
710 : : {
711 : 35018216 : const SBITMAP_ELT_TYPE tmp = *ap++ & (*bp++ | *cp++);
712 : 35018216 : changed |= *dstp ^ tmp;
713 : 35018216 : *dstp++ = tmp;
714 : : }
715 : :
716 : 12990320 : return changed != 0;
717 : : }
718 : :
719 : : /* Return number of first bit set in the bitmap, -1 if none. */
720 : :
721 : : int
722 : 578402 : bitmap_first_set_bit (const_sbitmap bmap)
723 : : {
724 : 578402 : unsigned int n = 0;
725 : 578402 : sbitmap_iterator sbi;
726 : :
727 : 1156804 : EXECUTE_IF_SET_IN_BITMAP (bmap, 0, n, sbi)
728 : 578402 : return n;
729 : : return -1;
730 : : }
731 : :
732 : : /* Return number of last bit set in the bitmap, -1 if none. */
733 : :
734 : : int
735 : 49458684 : bitmap_last_set_bit (const_sbitmap bmap)
736 : : {
737 : 49458684 : int i;
738 : 49458684 : const SBITMAP_ELT_TYPE *const ptr = bmap->elms;
739 : :
740 : 68509065 : for (i = bmap->size - 1; i >= 0; i--)
741 : : {
742 : 51120485 : const SBITMAP_ELT_TYPE word = ptr[i];
743 : :
744 : 51120485 : if (word != 0)
745 : : {
746 : 32070104 : unsigned int index = (i + 1) * SBITMAP_ELT_BITS - 1;
747 : 32070104 : SBITMAP_ELT_TYPE mask
748 : : = (SBITMAP_ELT_TYPE) 1 << (SBITMAP_ELT_BITS - 1);
749 : :
750 : 3820431884 : while (1)
751 : : {
752 : 1926250994 : if ((word & mask) != 0)
753 : 32070104 : return index;
754 : :
755 : 1894180890 : mask >>= 1;
756 : 1894180890 : index--;
757 : : }
758 : : }
759 : : }
760 : :
761 : : return -1;
762 : : }
763 : :
764 : : void
765 : 28 : dump_bitmap (FILE *file, const_sbitmap bmap)
766 : : {
767 : 28 : unsigned int i, n, j;
768 : 28 : unsigned int set_size = bmap->size;
769 : 28 : unsigned int total_bits = bmap->n_bits;
770 : :
771 : 28 : fprintf (file, " ");
772 : 84 : for (i = n = 0; i < set_size && n < total_bits; i++)
773 : 56 : for (j = 0; j < SBITMAP_ELT_BITS && n < total_bits; j++, n++)
774 : : {
775 : 28 : if (n != 0 && n % 10 == 0)
776 : 0 : fprintf (file, " ");
777 : :
778 : 28 : fprintf (file, "%d",
779 : 28 : (bmap->elms[i] & ((SBITMAP_ELT_TYPE) 1 << j)) != 0);
780 : : }
781 : :
782 : 28 : fprintf (file, "\n");
783 : 28 : }
784 : :
785 : : DEBUG_FUNCTION void
786 : 0 : debug_raw (simple_bitmap_def &ref)
787 : : {
788 : 0 : dump_bitmap (stderr, &ref);
789 : 0 : }
790 : :
791 : : DEBUG_FUNCTION void
792 : 0 : debug_raw (simple_bitmap_def *ptr)
793 : : {
794 : 0 : if (ptr)
795 : 0 : debug_raw (*ptr);
796 : : else
797 : 0 : fprintf (stderr, "<nil>\n");
798 : 0 : }
799 : :
800 : : void
801 : 62 : dump_bitmap_file (FILE *file, const_sbitmap bmap)
802 : : {
803 : 62 : unsigned int i, pos;
804 : :
805 : 62 : fprintf (file, "n_bits = %d, set = {", bmap->n_bits);
806 : :
807 : 916 : for (pos = 30, i = 0; i < bmap->n_bits; i++)
808 : 792 : if (bitmap_bit_p (bmap, i))
809 : : {
810 : 118 : if (pos > 70)
811 : : {
812 : 1 : fprintf (file, "\n ");
813 : 1 : pos = 0;
814 : : }
815 : :
816 : 118 : fprintf (file, "%d ", i);
817 : 181 : pos += 2 + (i >= 10) + (i >= 100) + (i >= 1000);
818 : : }
819 : :
820 : 62 : fprintf (file, "}\n");
821 : 62 : }
822 : :
823 : : DEBUG_FUNCTION void
824 : 0 : debug_bitmap (const_sbitmap bmap)
825 : : {
826 : 0 : dump_bitmap_file (stderr, bmap);
827 : 0 : }
828 : :
829 : : DEBUG_FUNCTION void
830 : 0 : debug (simple_bitmap_def &ref)
831 : : {
832 : 0 : dump_bitmap_file (stderr, &ref);
833 : 0 : }
834 : :
835 : : DEBUG_FUNCTION void
836 : 0 : debug (simple_bitmap_def *ptr)
837 : : {
838 : 0 : if (ptr)
839 : 0 : debug (*ptr);
840 : : else
841 : 0 : fprintf (stderr, "<nil>\n");
842 : 0 : }
843 : :
844 : : void
845 : 4 : dump_bitmap_vector (FILE *file, const char *title, const char *subtitle,
846 : : sbitmap *bmaps, int n_maps)
847 : : {
848 : 4 : int i;
849 : :
850 : 4 : fprintf (file, "%s\n", title);
851 : 36 : for (i = 0; i < n_maps; i++)
852 : : {
853 : 28 : fprintf (file, "%s %d\n", subtitle, i);
854 : 28 : dump_bitmap (file, bmaps[i]);
855 : : }
856 : :
857 : 4 : fprintf (file, "\n");
858 : 4 : }
859 : :
860 : : #if CHECKING_P
861 : :
862 : : namespace selftest {
863 : :
864 : : /* Selftests for sbitmaps. */
865 : :
866 : : /* Checking function that uses both bitmap_bit_in_range_p and
867 : : loop of bitmap_bit_p and verifies consistent results. */
868 : :
869 : : static bool
870 : 56 : bitmap_bit_in_range_p_checking (sbitmap s, unsigned int start,
871 : : unsigned end)
872 : : {
873 : 56 : bool r1 = bitmap_bit_in_range_p (s, start, end);
874 : 56 : bool r2 = false;
875 : :
876 : 8152 : for (unsigned int i = start; i <= end; i++)
877 : 8124 : if (bitmap_bit_p (s, i))
878 : : {
879 : : r2 = true;
880 : : break;
881 : : }
882 : :
883 : 56 : ASSERT_EQ (r1, r2);
884 : 56 : return r1;
885 : : }
886 : :
887 : : /* Verify bitmap_set_range functions for sbitmap. */
888 : :
889 : : static void
890 : 4 : test_set_range ()
891 : : {
892 : 4 : sbitmap s = sbitmap_alloc (16);
893 : 4 : bitmap_clear (s);
894 : :
895 : 4 : bitmap_set_range (s, 0, 1);
896 : 4 : ASSERT_TRUE (bitmap_bit_in_range_p_checking (s, 0, 0));
897 : 4 : ASSERT_FALSE (bitmap_bit_in_range_p_checking (s, 1, 15));
898 : 4 : bitmap_set_range (s, 15, 1);
899 : 4 : ASSERT_FALSE (bitmap_bit_in_range_p_checking (s, 1, 14));
900 : 4 : ASSERT_TRUE (bitmap_bit_in_range_p_checking (s, 15, 15));
901 : 4 : sbitmap_free (s);
902 : :
903 : 4 : s = sbitmap_alloc (1024);
904 : 4 : bitmap_clear (s);
905 : 4 : bitmap_set_range (s, 512, 1);
906 : 4 : ASSERT_FALSE (bitmap_bit_in_range_p_checking (s, 0, 511));
907 : 4 : ASSERT_FALSE (bitmap_bit_in_range_p_checking (s, 513, 1023));
908 : 4 : ASSERT_TRUE (bitmap_bit_in_range_p_checking (s, 512, 512));
909 : 4 : ASSERT_TRUE (bitmap_bit_in_range_p_checking (s, 508, 512));
910 : 4 : ASSERT_TRUE (bitmap_bit_in_range_p_checking (s, 508, 513));
911 : 4 : ASSERT_FALSE (bitmap_bit_in_range_p_checking (s, 508, 511));
912 : :
913 : 4 : bitmap_clear (s);
914 : 4 : bitmap_set_range (s, 512, 64);
915 : 4 : ASSERT_FALSE (bitmap_bit_in_range_p_checking (s, 0, 511));
916 : 4 : ASSERT_FALSE (bitmap_bit_in_range_p_checking (s, 512 + 64, 1023));
917 : 4 : ASSERT_TRUE (bitmap_bit_in_range_p_checking (s, 512, 512));
918 : 4 : ASSERT_TRUE (bitmap_bit_in_range_p_checking (s, 512 + 63, 512 + 63));
919 : 4 : sbitmap_free (s);
920 : 4 : }
921 : :
922 : : /* Verify bitmap_bit_in_range_p functions for sbitmap. */
923 : :
924 : : static void
925 : 4 : test_bit_in_range ()
926 : : {
927 : 4 : sbitmap s = sbitmap_alloc (1024);
928 : 4 : bitmap_clear (s);
929 : :
930 : 4 : ASSERT_FALSE (bitmap_bit_in_range_p (s, 512, 1023));
931 : 4 : bitmap_set_bit (s, 100);
932 : :
933 : 4 : ASSERT_FALSE (bitmap_bit_in_range_p (s, 512, 1023));
934 : 4 : ASSERT_FALSE (bitmap_bit_in_range_p (s, 0, 99));
935 : 4 : ASSERT_FALSE (bitmap_bit_in_range_p (s, 101, 1023));
936 : 4 : ASSERT_TRUE (bitmap_bit_in_range_p (s, 1, 100));
937 : 4 : ASSERT_TRUE (bitmap_bit_in_range_p (s, 64, 100));
938 : 4 : ASSERT_TRUE (bitmap_bit_in_range_p (s, 100, 100));
939 : 4 : ASSERT_TRUE (bitmap_bit_p (s, 100));
940 : :
941 : 4 : sbitmap_free (s);
942 : :
943 : 4 : s = sbitmap_alloc (64);
944 : 4 : bitmap_clear (s);
945 : 4 : bitmap_set_bit (s, 63);
946 : 4 : ASSERT_TRUE (bitmap_bit_in_range_p (s, 0, 63));
947 : 4 : ASSERT_TRUE (bitmap_bit_in_range_p (s, 1, 63));
948 : 4 : ASSERT_TRUE (bitmap_bit_in_range_p (s, 63, 63));
949 : 4 : ASSERT_TRUE (bitmap_bit_p (s, 63));
950 : 4 : sbitmap_free (s);
951 : :
952 : 4 : s = sbitmap_alloc (1024);
953 : 4 : bitmap_clear (s);
954 : 4 : bitmap_set_bit (s, 128);
955 : 4 : ASSERT_FALSE (bitmap_bit_in_range_p (s, 0, 127));
956 : 4 : ASSERT_FALSE (bitmap_bit_in_range_p (s, 129, 1023));
957 : :
958 : 4 : ASSERT_TRUE (bitmap_bit_in_range_p (s, 0, 128));
959 : 4 : ASSERT_TRUE (bitmap_bit_in_range_p (s, 1, 128));
960 : 4 : ASSERT_TRUE (bitmap_bit_in_range_p (s, 128, 255));
961 : 4 : ASSERT_TRUE (bitmap_bit_in_range_p (s, 128, 254));
962 : 4 : ASSERT_TRUE (bitmap_bit_p (s, 128));
963 : :
964 : 4 : bitmap_clear (s);
965 : 4 : bitmap_set_bit (s, 8);
966 : 4 : ASSERT_TRUE (bitmap_bit_in_range_p (s, 0, 8));
967 : 4 : ASSERT_TRUE (bitmap_bit_in_range_p (s, 0, 12));
968 : 4 : ASSERT_TRUE (bitmap_bit_in_range_p (s, 0, 63));
969 : 4 : ASSERT_TRUE (bitmap_bit_in_range_p (s, 0, 127));
970 : 4 : ASSERT_TRUE (bitmap_bit_in_range_p (s, 0, 512));
971 : 4 : ASSERT_TRUE (bitmap_bit_in_range_p (s, 8, 8));
972 : 4 : ASSERT_TRUE (bitmap_bit_p (s, 8));
973 : :
974 : 4 : bitmap_clear (s);
975 : 4 : ASSERT_FALSE (bitmap_bit_in_range_p (s, 0, 0));
976 : 4 : ASSERT_FALSE (bitmap_bit_in_range_p (s, 0, 8));
977 : 4 : ASSERT_FALSE (bitmap_bit_in_range_p (s, 0, 63));
978 : 4 : ASSERT_FALSE (bitmap_bit_in_range_p (s, 1, 63));
979 : 4 : ASSERT_FALSE (bitmap_bit_in_range_p (s, 0, 256));
980 : :
981 : 4 : bitmap_set_bit (s, 0);
982 : 4 : bitmap_set_bit (s, 16);
983 : 4 : bitmap_set_bit (s, 32);
984 : 4 : bitmap_set_bit (s, 48);
985 : 4 : bitmap_set_bit (s, 64);
986 : 4 : ASSERT_TRUE (bitmap_bit_in_range_p (s, 0, 0));
987 : 4 : ASSERT_TRUE (bitmap_bit_in_range_p (s, 1, 16));
988 : 4 : ASSERT_TRUE (bitmap_bit_in_range_p (s, 48, 63));
989 : 4 : ASSERT_TRUE (bitmap_bit_in_range_p (s, 64, 64));
990 : 4 : ASSERT_FALSE (bitmap_bit_in_range_p (s, 1, 15));
991 : 4 : ASSERT_FALSE (bitmap_bit_in_range_p (s, 17, 31));
992 : 4 : ASSERT_FALSE (bitmap_bit_in_range_p (s, 49, 63));
993 : 4 : ASSERT_FALSE (bitmap_bit_in_range_p (s, 65, 1023));
994 : 4 : sbitmap_free (s);
995 : 4 : }
996 : :
997 : : /* Run all of the selftests within this file. */
998 : :
999 : : void
1000 : 4 : sbitmap_cc_tests ()
1001 : : {
1002 : 4 : test_set_range ();
1003 : 4 : test_bit_in_range ();
1004 : 4 : }
1005 : :
1006 : : } // namespace selftest
1007 : : #endif /* CHECKING_P */
|
