]>
Commit | Line | Data |
---|---|---|
53a853de | 1 | /* Sparse array-based bitmaps. |
0263463d | 2 | Copyright (C) 2007-2012 Free Software Foundation, Inc. |
53a853de DB |
3 | Contributed by Daniel Berlin <dberlin@dberlin.org> |
4 | ||
5 | This file is part of GCC. | |
6 | ||
7 | GCC is free software; you can redistribute it and/or modify it under | |
8 | the terms of the GNU General Public License as published by the Free | |
9dcd6f09 | 9 | Software Foundation; either version 3, or (at your option) any later |
53a853de DB |
10 | version. |
11 | ||
12 | GCC is distributed in the hope that it will be useful, but WITHOUT ANY | |
13 | WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
14 | FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
15 | for more details. | |
16 | ||
17 | You should have received a copy of the GNU General Public License | |
9dcd6f09 NC |
18 | along with GCC; see the file COPYING3. If not see |
19 | <http://www.gnu.org/licenses/>. */ | |
53a853de DB |
20 | |
21 | #include "config.h" | |
22 | #include "system.h" | |
23 | #include "coretypes.h" | |
53a853de DB |
24 | #include "ebitmap.h" |
25 | ||
26 | /* The ebitmap data structure is a sparse bitmap structure that works | |
27 | by having two pieces: | |
110abdbc | 28 | 1. An array of all nonzero words in the structures, organized as |
53a853de DB |
29 | an array of HOST_WIDE_INT's. |
30 | 2. A non-sparse bitmap saying which bitmap words are present in the | |
31 | array. | |
32 | ||
33 | As a consequence of this representation, testing whether a bit | |
34 | exists in the bitmap is faster than linked-list bitmaps. For bits | |
35 | in words that are all zero, the time to test is O(1). For bits in | |
36 | words that exist, it requires O(n/sizeof(word)) time to perform the | |
37 | test (ignoring the one element cache). It also has much better | |
38 | locality than linked-list bitmaps. | |
39 | ||
40 | To test whether a bit exists, we do the following: | |
41 | 1. Test whether the word the bit would appear in exists in the | |
42 | bitmap (O(1) check of the mask). If not, fail. | |
43 | ||
44 | 2. Population count the mask up to the word containing the bit, to | |
45 | find the place in the array the word would be (popcount is cached, | |
46 | but this is just as slow as the linked-list bitmap) | |
47 | 3. Test the word to see if the bit exists. | |
48 | ||
49 | Just like linked-list bitmaps, we cache the last element that has | |
50 | been tested in order to speed up common access patterns. | |
51 | ||
52 | Most of the other speedups are simply due to better locality of the | |
53 | single contiguous array. | |
54 | ||
55 | As would be expected in a structure like this, insertion into an | |
56 | empty word in the middle requires moving bits to make room for the | |
57 | new word. As most operations that perform sets perform them in | |
58 | order, this is rarely a problem. We also take advantage of the | |
59 | same element cache to make repeated sets to the same word O(1). | |
60 | ||
61 | Operations on the entire bitmap are also more efficient than linked | |
62 | list bitmaps, as they are all operating on contiguous memory, and | |
63 | can be easily vectorized. They are all O(number of words) + | |
64 | O(number of bits that may end up in the destination), as the | |
65 | appropriate operation is first performed on the word mask, and then | |
66 | only those elements that may generate results are touched. | |
67 | ||
68 | Memory wise, the ebitmap starts out using less memory than the | |
69 | linked-list bitmap, but its size in memory is technically bounded | |
70 | by ((index of the highest bit set) / (size of a word) + (index of | |
71 | the highest bit set) / ((size of a word) * (size of a word))) This | |
72 | is because the mask is non-sparse. The mask could be transformed | |
73 | into a sparse bitmap at the cost of making bit testing | |
74 | *theoretically* slower (real world numbers have not been computed | |
75 | yet as to whether it matters or not). */ | |
76 | ||
77 | /* #define EBITMAP_DEBUGGING */ | |
78 | ||
79 | /* Find the last set bit in ebitmap MAP. */ | |
80 | ||
81 | int | |
82 | ebitmap_last_set_bit (ebitmap map) | |
83 | { | |
84 | unsigned int i = 0; | |
85 | ebitmap_iterator ebi; | |
86 | bool foundbit = false; | |
b8698a0f | 87 | |
53a853de DB |
88 | /* This is not the fastest way to do this, we could simply look for |
89 | the popcount, and start there, but this function is not used | |
90 | anywhere speed critical. */ | |
91 | EXECUTE_IF_SET_IN_EBITMAP (map, 0, i, ebi) | |
92 | { | |
93 | foundbit = true; | |
94 | } | |
b8698a0f | 95 | |
53a853de DB |
96 | |
97 | if (foundbit) | |
98 | return i; | |
99 | return -1; | |
100 | } | |
101 | ||
102 | /* Grow or shrink the internal word array for MAP to NEWSIZE | |
103 | elements. */ | |
104 | ||
105 | static inline void | |
106 | ebitmap_array_grow (ebitmap map, unsigned int newsize) | |
107 | { | |
108 | if (newsize <= map->n_elts) | |
109 | { | |
110 | map->n_elts = newsize; | |
111 | return; | |
112 | } | |
113 | ||
114 | newsize += newsize / 4; | |
115 | ||
116 | map->n_elts = newsize; | |
1b4572a8 | 117 | map->elts = XRESIZEVEC (EBITMAP_ELT_TYPE, map->elts, newsize); |
53a853de DB |
118 | } |
119 | ||
120 | /* Grow the internal word array for MAP so it is at least SIZE | |
121 | elements. Will not shrink the array if it is already big | |
122 | enough. */ | |
123 | ||
124 | static inline void | |
125 | ebitmap_array_maybe_grow (ebitmap map, unsigned int size) | |
126 | { | |
127 | if (size >= map->n_elts) | |
128 | ebitmap_array_grow (map, size + 1); | |
129 | } | |
130 | ||
131 | /* Retrieve the IDX'th element from the word array for MAP. */ | |
132 | ||
133 | static inline EBITMAP_ELT_TYPE | |
134 | ebitmap_array_get (ebitmap map, unsigned int idx) | |
135 | { | |
136 | gcc_assert (idx < map->n_elts); | |
137 | return map->elts[idx]; | |
138 | } | |
139 | ||
140 | /* Retrieve a pointer to the IDX'th element from the word array for | |
141 | MAP. If the element index is greater than the size of the array, | |
142 | the array will be grown to the correct size. */ | |
143 | ||
144 | static inline EBITMAP_ELT_TYPE * | |
145 | ebitmap_array_grow_get (ebitmap map, unsigned int idx) | |
146 | { | |
147 | if (idx >= map->n_elts) | |
148 | ebitmap_array_grow (map, idx + 1); | |
149 | return &map->elts[idx]; | |
150 | } | |
151 | ||
152 | /* Initialize the internal word array for MAP, so that it is SIZE | |
153 | elements. */ | |
154 | ||
155 | static inline void | |
156 | ebitmap_array_init (ebitmap map, unsigned int size) | |
157 | { | |
158 | if (size > 0) | |
159 | { | |
1b4572a8 | 160 | map->elts = XNEWVEC (EBITMAP_ELT_TYPE, size); |
53a853de DB |
161 | map->n_elts = size; |
162 | } | |
163 | else | |
164 | { | |
165 | map->n_elts = 0; | |
166 | map->elts = NULL; | |
167 | } | |
168 | } | |
169 | ||
170 | /* Free the internal word array for MAP. */ | |
171 | ||
172 | static inline void | |
173 | ebitmap_array_clear (ebitmap map) | |
174 | { | |
b8698a0f | 175 | if (map->elts) |
53a853de DB |
176 | { |
177 | free (map->elts); | |
178 | map->elts = NULL; | |
179 | } | |
180 | map->n_elts = 0; | |
181 | } | |
182 | ||
183 | /* Clear ebitmap MAP. */ | |
184 | ||
185 | void | |
186 | ebitmap_clear (ebitmap map) | |
187 | { | |
188 | ebitmap_array_clear (map); | |
189 | sbitmap_zero (map->wordmask); | |
190 | map->wordmask = sbitmap_resize (map->wordmask, 1, 0); | |
191 | map->numwords = 0; | |
192 | map->cache = NULL; | |
193 | map->cacheindex = 0; | |
194 | } | |
195 | ||
196 | /* Allocate an ebitmap with enough room for SIZE bits to start out. */ | |
197 | ||
198 | ebitmap | |
199 | ebitmap_alloc (unsigned int size) | |
200 | { | |
1b4572a8 | 201 | ebitmap ret = XNEW (struct ebitmap_def); |
53a853de DB |
202 | if (size == 0) |
203 | size = EBITMAP_ELT_BITS; | |
204 | ebitmap_array_init (ret, (size + EBITMAP_ELT_BITS - 1) / EBITMAP_ELT_BITS); | |
205 | ret->wordmask = sbitmap_alloc_with_popcount (size); | |
206 | sbitmap_zero (ret->wordmask); | |
207 | ret->numwords = 0; | |
208 | ret->cache = NULL; | |
209 | ret->cacheindex = 0; | |
210 | ||
211 | return ret; | |
212 | } | |
213 | ||
214 | /* Clear BIT from ebitmap MAP. */ | |
215 | ||
216 | void | |
217 | ebitmap_clear_bit (ebitmap map, unsigned int bit) | |
218 | { | |
219 | unsigned int wordindex = bit / EBITMAP_ELT_BITS; | |
220 | unsigned int eltwordindex = 0; | |
221 | unsigned int bitindex, shift; | |
222 | bool have_eltwordindex = false; | |
223 | EBITMAP_ELT_TYPE *elt_ptr; | |
b8698a0f | 224 | |
53a853de DB |
225 | /* If the bit can't exist in our bitmap, just return. */ |
226 | if (map->numwords == 0) | |
227 | return; | |
228 | ||
229 | if (wordindex >= map->wordmask->n_bits | |
230 | || !TEST_BIT (map->wordmask, wordindex)) | |
231 | return; | |
b8698a0f | 232 | |
53a853de DB |
233 | if (map->cache != NULL && map->cacheindex == wordindex) |
234 | elt_ptr = map->cache; | |
235 | else | |
236 | { | |
237 | eltwordindex = sbitmap_popcount (map->wordmask, wordindex); | |
238 | elt_ptr = &map->elts[eltwordindex]; | |
239 | have_eltwordindex = true; | |
240 | } | |
b8698a0f | 241 | |
53a853de DB |
242 | bitindex = bit % EBITMAP_ELT_BITS; |
243 | shift = bitindex; | |
b8698a0f | 244 | |
53a853de DB |
245 | *(elt_ptr) &= ~(((EBITMAP_ELT_TYPE)1) << shift); |
246 | ||
247 | /* Clear out the empty words. */ | |
248 | if (*(elt_ptr) == 0) | |
249 | { | |
250 | if (!have_eltwordindex) | |
251 | eltwordindex = sbitmap_popcount (map->wordmask, wordindex); | |
b8698a0f | 252 | |
4b9c6075 NB |
253 | if (map->cache != NULL) |
254 | { | |
255 | if (map->cacheindex == wordindex) | |
256 | map->cache = NULL; | |
257 | else if (map->cacheindex > wordindex) | |
258 | map->cache = map->cache - 1; | |
259 | } | |
53a853de | 260 | |
0263463d | 261 | RESET_BIT_WITH_POPCOUNT (map->wordmask, wordindex); |
53a853de DB |
262 | |
263 | memmove(&map->elts[eltwordindex], &map->elts[eltwordindex + 1], | |
264 | sizeof (EBITMAP_ELT_TYPE) * (map->numwords - eltwordindex)); | |
265 | map->numwords--; | |
266 | } | |
267 | } | |
268 | ||
269 | /* Set BIT in ebitmap MAP. */ | |
270 | ||
271 | void | |
272 | ebitmap_set_bit (ebitmap map, unsigned int bit) | |
273 | { | |
274 | unsigned int wordindex = bit / EBITMAP_ELT_BITS; | |
275 | unsigned int eltwordindex; | |
276 | unsigned int bitindex = bit % EBITMAP_ELT_BITS; | |
277 | ||
278 | /* If we have this element cached, just set the bit in it. */ | |
279 | if (map->cache && map->cacheindex == wordindex) | |
280 | { | |
281 | (*map->cache) |= (EBITMAP_ELT_TYPE)1 << bitindex; | |
282 | return; | |
283 | } | |
284 | ||
285 | /* Resize the wordmask if necessary. */ | |
286 | if (wordindex >= map->wordmask->n_bits) | |
287 | map->wordmask = sbitmap_resize (map->wordmask, wordindex + 1, 0); | |
288 | ||
289 | /* Allocate a new word in the array and move whatever is in it's | |
290 | place, if necessary. */ | |
291 | if (!TEST_BIT (map->wordmask, wordindex)) | |
292 | { | |
293 | unsigned long count; | |
294 | unsigned int i; | |
295 | ||
0263463d | 296 | SET_BIT_WITH_POPCOUNT (map->wordmask, wordindex); |
53a853de DB |
297 | count = sbitmap_popcount (map->wordmask, wordindex); |
298 | gcc_assert (count <= map->numwords); | |
299 | ||
300 | for (i = map->numwords; i > count; i--) | |
301 | { | |
302 | EBITMAP_ELT_TYPE *newelt; | |
303 | newelt = ebitmap_array_grow_get (map, i); | |
304 | *newelt = ebitmap_array_get (map, i - 1); | |
305 | } | |
306 | map->numwords++; | |
307 | eltwordindex = count; | |
308 | ebitmap_array_maybe_grow (map, eltwordindex); | |
309 | map->elts[eltwordindex] = 0; | |
310 | } | |
311 | else | |
312 | { | |
313 | eltwordindex = sbitmap_popcount (map->wordmask, wordindex); | |
314 | } | |
315 | ||
316 | /* Set the actual bit. */ | |
317 | bitindex = bit % EBITMAP_ELT_BITS; | |
318 | ||
319 | map->elts[eltwordindex] |= (EBITMAP_ELT_TYPE)1 << bitindex; | |
320 | map->cache = &map->elts[eltwordindex]; | |
321 | map->cacheindex = wordindex; | |
322 | } | |
323 | ||
324 | ||
325 | /* Return true if MAP contains BIT. */ | |
326 | ||
327 | bool | |
328 | ebitmap_bit_p (ebitmap map, unsigned int bit) | |
329 | { | |
330 | unsigned int wordindex = bit / EBITMAP_ELT_BITS; | |
331 | unsigned int bitindex= bit % EBITMAP_ELT_BITS; | |
332 | ||
333 | /* Trivial empty ebitmap case. */ | |
334 | if (map->numwords == 0) | |
335 | return false; | |
336 | ||
337 | if (map->cache && map->cacheindex == wordindex) | |
338 | return ((*map->cache) >> bitindex) & 1; | |
339 | ||
340 | /* If the wordindex is greater than the size of the wordmask, *or* | |
341 | it's not set in the wordmask, this bit can't exist in our | |
342 | ebitmap. */ | |
343 | if (wordindex >= map->wordmask->n_bits | |
344 | || !TEST_BIT (map->wordmask, wordindex)) | |
345 | return false; | |
346 | ||
347 | /* Find the bit and test it. */ | |
348 | map->cacheindex = wordindex; | |
349 | wordindex = sbitmap_popcount (map->wordmask, wordindex); | |
350 | map->cache = &map->elts[wordindex]; | |
351 | ||
352 | return (map->elts[wordindex] >> bitindex) & 1; | |
353 | } | |
354 | ||
355 | /* Copy ebitmap SRC to DST. */ | |
356 | ||
357 | void | |
358 | ebitmap_copy (ebitmap dst, ebitmap src) | |
359 | { | |
360 | /* Blow away any existing wordmask, and copy the new one. */ | |
361 | sbitmap_free (dst->wordmask); | |
362 | dst->wordmask = sbitmap_alloc_with_popcount (src->wordmask->n_bits); | |
363 | sbitmap_copy (dst->wordmask, src->wordmask); | |
364 | ||
365 | /* Make sure our destination array is big enough, and then copy the | |
366 | actual words. */ | |
367 | ebitmap_array_grow (dst, src->numwords); | |
368 | memcpy (dst->elts, src->elts, | |
369 | src->numwords * sizeof (EBITMAP_ELT_TYPE)); | |
370 | dst->numwords = src->numwords; | |
371 | dst->cache = NULL; | |
372 | } | |
373 | ||
374 | /* Dump ebitmap BMAP to FILE. */ | |
375 | ||
376 | void | |
377 | dump_ebitmap (FILE *file, ebitmap bmap) | |
378 | { | |
379 | unsigned int pos; | |
380 | unsigned int i; | |
381 | int res; | |
382 | unsigned int size; | |
383 | ||
384 | res = sbitmap_last_set_bit (bmap->wordmask); | |
385 | if (res == -1) | |
386 | size = 0; | |
387 | else | |
388 | size = (res + 1) * EBITMAP_ELT_BITS; | |
389 | ||
390 | fprintf (file, "n_words = %d, set = {", bmap->numwords); | |
391 | ||
392 | for (pos = 30, i = 0; i < size; i++) | |
393 | if (ebitmap_bit_p (bmap, i)) | |
394 | { | |
395 | if (pos > 70) | |
396 | { | |
397 | fprintf (file, "\n "); | |
398 | pos = 0; | |
399 | } | |
400 | ||
401 | pos += fprintf (file, "%d ", i); | |
402 | } | |
403 | ||
404 | fprintf (file, "}\n"); | |
405 | } | |
406 | ||
407 | /* Dump ebitmap BMAP to stderr. */ | |
408 | ||
24e47c76 | 409 | DEBUG_FUNCTION void |
53a853de DB |
410 | debug_ebitmap (ebitmap bmap) |
411 | { | |
412 | dump_ebitmap (stderr, bmap); | |
413 | } | |
414 | ||
415 | /* Perform the operation DST &= SRC. */ | |
416 | ||
417 | void | |
418 | ebitmap_and_into (ebitmap dst, ebitmap src) | |
419 | { | |
420 | sbitmap_iterator sbi; | |
421 | unsigned int i; | |
422 | unsigned int neweltindex = 0; | |
423 | unsigned int dsteltindex = 0; | |
424 | unsigned int srceltindex = 0; | |
425 | ||
426 | gcc_assert (dst != src); | |
427 | ||
428 | dst->cache = NULL; | |
429 | ||
430 | /* Short circuit the empty bitmap cases. */ | |
431 | if (src->numwords == 0 || dst->numwords == 0) | |
432 | { | |
433 | ebitmap_clear (dst); | |
434 | return; | |
435 | } | |
436 | ||
437 | /* AND the masks, then walk the words that may actually appear in | |
438 | the result, AND'ing them. */ | |
439 | sbitmap_a_and_b (dst->wordmask, dst->wordmask, src->wordmask); | |
440 | ||
441 | EXECUTE_IF_SET_IN_SBITMAP (dst->wordmask, 0, i, sbi) | |
442 | { | |
443 | EBITMAP_ELT_TYPE tmpword = ebitmap_array_get (src, srceltindex++); | |
444 | tmpword &= ebitmap_array_get (dst, dsteltindex++); | |
445 | if (tmpword != 0) | |
446 | { | |
447 | EBITMAP_ELT_TYPE *dstplace; | |
448 | dstplace = ebitmap_array_grow_get (dst, neweltindex++); | |
449 | *dstplace = tmpword; | |
450 | } | |
451 | else | |
0263463d | 452 | RESET_BIT_WITH_POPCOUNT (dst->wordmask, i); |
53a853de DB |
453 | } |
454 | #ifdef EBITMAP_DEBUGGING | |
455 | { | |
456 | unsigned int i; | |
457 | ||
458 | for (i = 0; i < dst->numwords; i++) | |
459 | gcc_assert (dst->elts[i] != 0); | |
460 | ||
4b9c6075 | 461 | sbitmap_verify_popcount (dst->wordmask); |
53a853de DB |
462 | gcc_assert (sbitmap_popcount (dst->wordmask, |
463 | dst->wordmask->n_bits) == dst->numwords); | |
464 | } | |
465 | #endif | |
466 | dst->numwords = neweltindex; | |
467 | } | |
468 | ||
469 | /* Perform the operation DST = SRC1 & SRC2. */ | |
470 | ||
471 | void | |
472 | ebitmap_and (ebitmap dst, ebitmap src1, ebitmap src2) | |
473 | { | |
474 | sbitmap_iterator sbi; | |
475 | unsigned int i; | |
476 | unsigned int neweltindex = 0; | |
477 | unsigned int src1eltindex = 0; | |
478 | unsigned int src2eltindex = 0; | |
479 | ||
480 | dst->cache = NULL; | |
481 | if (src1->numwords == 0 || src2->numwords == 0) | |
482 | { | |
483 | ebitmap_clear (dst); | |
484 | return; | |
485 | } | |
486 | ||
487 | dst->wordmask | |
488 | = sbitmap_resize (dst->wordmask, | |
489 | MIN (src1->wordmask->n_bits, src2->wordmask->n_bits), | |
490 | 0); | |
491 | sbitmap_a_and_b (dst->wordmask, src1->wordmask, src2->wordmask); | |
492 | ||
493 | EXECUTE_IF_SET_IN_SBITMAP (dst->wordmask, 0, i, sbi) | |
494 | { | |
495 | bool src1hasword, src2hasword; | |
496 | ||
497 | src1hasword = TEST_BIT (src1->wordmask, i); | |
498 | src2hasword = TEST_BIT (src2->wordmask, i); | |
499 | ||
500 | if (src1hasword && src2hasword) | |
501 | { | |
502 | EBITMAP_ELT_TYPE tmpword = ebitmap_array_get (src1, src1eltindex++); | |
503 | tmpword &= ebitmap_array_get (src2, src2eltindex++); | |
504 | if (tmpword != 0) | |
505 | { | |
506 | EBITMAP_ELT_TYPE *dstplace; | |
507 | dstplace = ebitmap_array_grow_get (dst, neweltindex++); | |
508 | *dstplace = tmpword; | |
509 | } | |
510 | else | |
0263463d | 511 | RESET_BIT_WITH_POPCOUNT (dst->wordmask, i); |
53a853de DB |
512 | } |
513 | else if (src1hasword) | |
514 | src1eltindex++; | |
515 | else | |
516 | src2eltindex++; | |
517 | } | |
518 | #ifdef EBITMAP_DEBUGGING | |
519 | { | |
520 | ebitmap_iterator ebi; | |
521 | unsigned int i; | |
522 | ||
523 | for (i = 0; i < dst->numwords; i++) | |
524 | gcc_assert (dst->elts[i] != 0); | |
525 | ||
526 | EXECUTE_IF_SET_IN_EBITMAP (src1, 0, i, ebi) | |
527 | if (ebitmap_bit_p (src2, i)) | |
528 | gcc_assert (ebitmap_bit_p (dst, i)); | |
529 | ||
530 | for (i = 0; i < dst->numwords; i++) | |
531 | gcc_assert (dst->elts[i] != 0); | |
532 | ||
4b9c6075 | 533 | sbitmap_verify_popcount (dst->wordmask); |
53a853de DB |
534 | gcc_assert (sbitmap_popcount (dst->wordmask, |
535 | dst->wordmask->n_bits) == dst->numwords); | |
536 | } | |
537 | #endif | |
538 | dst->numwords = neweltindex; | |
539 | } | |
540 | ||
541 | /* Perform the operation DST |= SRC. Return true if any bits in DST | |
542 | changed. */ | |
543 | ||
544 | bool | |
545 | ebitmap_ior_into (ebitmap dst, ebitmap src) | |
546 | { | |
547 | unsigned int dstsize = dst->wordmask->n_bits; | |
548 | unsigned int srcsize = src->wordmask->n_bits; | |
549 | sbitmap_iterator sbi; | |
550 | unsigned int i; | |
551 | sbitmap tempmask; | |
552 | unsigned int neweltindex = 0; | |
553 | unsigned int dsteltindex = 0; | |
554 | unsigned int srceltindex = 0; | |
555 | bool changed = false; | |
556 | EBITMAP_ELT_TYPE *newarray; | |
557 | unsigned int newarraysize; | |
558 | #ifdef EBITMAP_DEBUGGING | |
559 | ebitmap dstcopy = ebitmap_alloc (1); | |
560 | ebitmap_copy (dstcopy, dst); | |
561 | #endif | |
562 | ||
563 | dst->cache = NULL; | |
564 | if (dst == src) | |
565 | return false; | |
566 | ||
567 | if (dst->numwords == 0 && src->numwords != 0) | |
568 | { | |
569 | ebitmap_copy (dst, src); | |
570 | return true; | |
571 | } | |
572 | else if (src->numwords == 0) | |
573 | return false; | |
574 | ||
575 | /* We can do without the temp mask if it's faster, but it would mean | |
576 | touching more words in the actual dense vector. */ | |
577 | tempmask = sbitmap_alloc (MAX (srcsize, dstsize)); | |
578 | sbitmap_zero (tempmask); | |
579 | if (srcsize == dstsize) | |
580 | { | |
581 | sbitmap_a_or_b (tempmask, dst->wordmask, src->wordmask); | |
582 | } | |
583 | else | |
584 | { | |
585 | dst->wordmask = sbitmap_resize (dst->wordmask, MAX (srcsize, dstsize), | |
586 | 0); | |
587 | if (srcsize >= dstsize) | |
588 | { | |
589 | sbitmap_copy_n (tempmask, dst->wordmask, dst->wordmask->size); | |
590 | sbitmap_a_or_b (tempmask, tempmask, src->wordmask); | |
591 | } | |
592 | else | |
593 | { | |
594 | sbitmap_copy_n (tempmask, src->wordmask, src->wordmask->size); | |
595 | sbitmap_a_or_b (tempmask, tempmask, dst->wordmask); | |
596 | } | |
597 | } | |
598 | newarraysize = src->numwords + dst->numwords; | |
1b4572a8 | 599 | newarray = XNEWVEC (EBITMAP_ELT_TYPE, newarraysize); |
53a853de DB |
600 | |
601 | EXECUTE_IF_SET_IN_SBITMAP (tempmask, 0, i, sbi) | |
602 | { | |
603 | bool dsthasword, srchasword; | |
604 | ||
605 | dsthasword = (i < dst->wordmask->n_bits | |
606 | && TEST_BIT (dst->wordmask, i)); | |
607 | srchasword = (i < src->wordmask->n_bits | |
608 | && TEST_BIT (src->wordmask, i)); | |
609 | ||
610 | if (dsthasword && srchasword) | |
611 | { | |
612 | EBITMAP_ELT_TYPE tmpword = ebitmap_array_get (src, srceltindex++); | |
613 | tmpword |= ebitmap_array_get (dst, dsteltindex); | |
614 | if (!changed) | |
615 | changed |= tmpword != ebitmap_array_get (dst, dsteltindex); | |
616 | dsteltindex++; | |
617 | newarray[neweltindex++] = tmpword; | |
618 | } | |
619 | else if (dsthasword) | |
620 | { | |
621 | newarray [neweltindex++] = ebitmap_array_get (dst, dsteltindex++); | |
622 | } | |
623 | else | |
624 | { | |
625 | newarray [neweltindex++] = ebitmap_array_get (src, srceltindex++); | |
626 | gcc_assert (i < dst->wordmask->n_bits); | |
0263463d | 627 | SET_BIT_WITH_POPCOUNT (dst->wordmask, i); |
53a853de DB |
628 | changed |= true; |
629 | } | |
630 | } | |
631 | ||
632 | sbitmap_free (tempmask); | |
633 | if (changed) | |
634 | { | |
635 | dst->numwords = neweltindex; | |
636 | free (dst->elts); | |
637 | dst->elts = newarray; | |
638 | dst->n_elts = newarraysize; | |
639 | } | |
640 | else | |
641 | free (newarray); | |
642 | ||
643 | #ifdef EBITMAP_DEBUGGING | |
644 | { | |
645 | ebitmap_iterator ebi; | |
646 | unsigned int i; | |
647 | ||
648 | for (i = 0; i < dst->numwords; i++) | |
649 | gcc_assert (dst->elts[i] != 0); | |
650 | ||
651 | EXECUTE_IF_SET_IN_EBITMAP (src, 0, i, ebi) | |
652 | gcc_assert (ebitmap_bit_p (dst, i)); | |
653 | EXECUTE_IF_SET_IN_EBITMAP (dstcopy, 0, i, ebi) | |
654 | gcc_assert (ebitmap_bit_p (dst, i)); | |
655 | ||
4b9c6075 | 656 | sbitmap_verify_popcount (dst->wordmask); |
53a853de DB |
657 | gcc_assert (changed == !ebitmap_equal_p (dst, dstcopy)); |
658 | gcc_assert (sbitmap_popcount (dst->wordmask, | |
659 | dst->wordmask->n_bits) == dst->numwords); | |
660 | } | |
661 | #endif | |
662 | return changed; | |
663 | } | |
664 | ||
665 | /* Perform the operation DST = SRC1 | SRC2. Return true if any bit | |
666 | in DST has changed. */ | |
667 | ||
668 | bool | |
669 | ebitmap_ior (ebitmap dst, ebitmap src1, ebitmap src2) | |
670 | { | |
671 | unsigned int src1size = src1->wordmask->n_bits; | |
672 | unsigned int src2size = src2->wordmask->n_bits; | |
673 | sbitmap_iterator sbi; | |
674 | unsigned int i; | |
675 | sbitmap tempmask; | |
676 | unsigned int neweltindex = 0; | |
677 | unsigned int src1eltindex = 0; | |
678 | unsigned int src2eltindex = 0; | |
679 | bool changed = false; | |
680 | EBITMAP_ELT_TYPE *newarray; | |
681 | unsigned int newarraysize; | |
682 | #ifdef EBITMAP_DEBUGGING | |
683 | ebitmap dstcopy = ebitmap_alloc (1); | |
684 | ebitmap_copy (dstcopy, dst); | |
685 | #endif | |
686 | ||
687 | dst->cache = NULL; | |
688 | tempmask = sbitmap_alloc_with_popcount (MAX (src1size, src2size)); | |
689 | sbitmap_zero (tempmask); | |
690 | if (src1size == src2size) | |
691 | { | |
692 | sbitmap_a_or_b (tempmask, src1->wordmask, src2->wordmask); | |
693 | } | |
694 | else | |
695 | { | |
696 | if (src1size >= src2size) | |
697 | { | |
698 | sbitmap_copy_n (tempmask, src2->wordmask, src2->wordmask->size); | |
699 | sbitmap_a_or_b (tempmask, tempmask, src1->wordmask); | |
700 | } | |
701 | else | |
702 | { | |
703 | sbitmap_copy_n (tempmask, src1->wordmask, src1->wordmask->size); | |
704 | sbitmap_a_or_b (tempmask, tempmask, src2->wordmask); | |
705 | } | |
706 | } | |
707 | newarraysize = src1->numwords + src2->numwords; | |
1b4572a8 | 708 | newarray = XNEWVEC (EBITMAP_ELT_TYPE, newarraysize); |
53a853de DB |
709 | |
710 | EXECUTE_IF_SET_IN_SBITMAP (tempmask, 0, i, sbi) | |
711 | { | |
712 | bool src1hasword, src2hasword; | |
713 | EBITMAP_ELT_TYPE tmpword; | |
714 | src1hasword = (i < src1->wordmask->n_bits | |
715 | && TEST_BIT (src1->wordmask, i)); | |
716 | src2hasword = (i < src2->wordmask->n_bits | |
717 | && TEST_BIT (src2->wordmask, i)); | |
718 | ||
719 | if (src1hasword && src2hasword) | |
720 | { | |
721 | tmpword = (ebitmap_array_get (src1, src1eltindex++) | |
722 | | ebitmap_array_get (src2, src2eltindex++)); | |
723 | newarray[neweltindex++] = tmpword; | |
724 | } | |
725 | else if (src1hasword) | |
726 | { | |
727 | tmpword = ebitmap_array_get (src1, src1eltindex++); | |
728 | newarray [neweltindex++] = tmpword; | |
729 | } | |
730 | else | |
731 | { | |
732 | tmpword = ebitmap_array_get (src2, src2eltindex++); | |
733 | newarray [neweltindex++] = tmpword; | |
734 | } | |
735 | ||
736 | if (i >= dst->wordmask->n_bits || !TEST_BIT (dst->wordmask, i)) | |
737 | { | |
738 | changed = true; | |
739 | } | |
740 | else if (!changed) | |
741 | { | |
742 | unsigned int count = sbitmap_popcount (dst->wordmask, i); | |
743 | changed |= ebitmap_array_get (dst, count) != tmpword; | |
744 | } | |
745 | } | |
746 | ||
747 | if (changed) | |
748 | { | |
749 | sbitmap_free (dst->wordmask); | |
750 | dst->wordmask = tempmask; | |
751 | dst->numwords = neweltindex; | |
752 | free (dst->elts); | |
753 | dst->elts = newarray; | |
754 | dst->n_elts = newarraysize; | |
755 | } | |
756 | else | |
757 | { | |
758 | sbitmap_free (tempmask); | |
759 | free (newarray); | |
760 | } | |
761 | ||
762 | #ifdef EBITMAP_DEBUGGING | |
763 | { | |
764 | ebitmap_iterator ebi; | |
765 | unsigned int i; | |
766 | ||
767 | for (i = 0; i < dst->numwords; i++) | |
768 | gcc_assert (dst->elts[i] != 0); | |
769 | ||
770 | EXECUTE_IF_SET_IN_EBITMAP (src1, 0, i, ebi) | |
771 | gcc_assert (ebitmap_bit_p (dst, i)); | |
772 | ||
773 | EXECUTE_IF_SET_IN_EBITMAP (src2, 0, i, ebi) | |
774 | gcc_assert (ebitmap_bit_p (dst, i)); | |
775 | } | |
4b9c6075 | 776 | sbitmap_verify_popcount (dst->wordmask); |
53a853de DB |
777 | gcc_assert (changed == !ebitmap_equal_p (dst, dstcopy)); |
778 | gcc_assert (sbitmap_popcount (dst->wordmask, | |
779 | dst->wordmask->n_bits) == dst->numwords); | |
780 | #endif | |
781 | ||
782 | return changed; | |
783 | } | |
784 | ||
785 | /* Perform the operation DST &= ~SRC. Return true if any bit in DST | |
786 | has changed. */ | |
787 | ||
788 | bool | |
789 | ebitmap_and_compl_into (ebitmap dst, ebitmap src) | |
790 | { | |
791 | bool changed = false; | |
792 | unsigned int i; | |
793 | unsigned int neweltindex = 0; | |
794 | unsigned int dsteltindex = 0; | |
795 | sbitmap_iterator sbi; | |
796 | #ifdef EBITMAP_DEBUGGING | |
797 | ebitmap dstcopy = ebitmap_alloc (1); | |
798 | ebitmap_copy (dstcopy, dst); | |
799 | #endif | |
800 | ||
801 | gcc_assert (dst != src); | |
802 | dst->cache = NULL; | |
803 | if (src->numwords == 0) | |
804 | return false; | |
805 | ||
806 | EXECUTE_IF_SET_IN_SBITMAP (dst->wordmask, 0, i, sbi) | |
807 | { | |
808 | bool srchasword; | |
809 | ||
810 | srchasword = (i < src->wordmask->n_bits | |
811 | && TEST_BIT (src->wordmask, i)); | |
812 | ||
813 | if (srchasword) | |
814 | { | |
815 | unsigned int srccount = sbitmap_popcount (src->wordmask, i); | |
816 | EBITMAP_ELT_TYPE tmpword = ebitmap_array_get (dst, dsteltindex); | |
817 | tmpword &= ~(ebitmap_array_get (src, srccount)); | |
818 | if (!changed) | |
819 | changed |= ebitmap_array_get (dst, dsteltindex) != tmpword; | |
820 | dsteltindex++; | |
821 | if (tmpword != 0) | |
822 | { | |
823 | EBITMAP_ELT_TYPE *dstplace; | |
824 | dstplace = ebitmap_array_grow_get (dst, neweltindex++); | |
825 | *dstplace = tmpword; | |
826 | } | |
827 | else | |
0263463d | 828 | RESET_BIT_WITH_POPCOUNT (dst->wordmask, i); |
53a853de DB |
829 | } |
830 | else | |
831 | { | |
832 | dsteltindex++; | |
833 | neweltindex++; | |
834 | } | |
835 | } | |
836 | #ifdef EBITMAP_DEBUGGING | |
837 | { | |
838 | unsigned int i; | |
839 | ebitmap_iterator ebi; | |
840 | ||
841 | EXECUTE_IF_SET_IN_EBITMAP (dstcopy, 0, i, ebi) | |
842 | { | |
843 | if (!ebitmap_bit_p (src, i)) | |
844 | gcc_assert (ebitmap_bit_p (dst, i)); | |
845 | } | |
846 | ||
847 | for (i = 0; i < dst->numwords; i++) | |
848 | gcc_assert (dst->elts[i] != 0); | |
849 | ||
850 | gcc_assert (sbitmap_popcount (dst->wordmask, | |
851 | dst->wordmask->n_bits) == neweltindex); | |
4b9c6075 | 852 | sbitmap_verify_popcount (dst->wordmask); |
53a853de DB |
853 | gcc_assert (changed == !ebitmap_equal_p (dst, dstcopy)); |
854 | gcc_assert (sbitmap_popcount (dst->wordmask, | |
855 | dst->wordmask->n_bits) == dst->numwords); | |
856 | } | |
857 | #endif | |
858 | dst->numwords = neweltindex; | |
859 | /* sbitmap_popcount (dst->wordmask, -1); */ | |
860 | ||
861 | return changed; | |
862 | } | |
863 | ||
864 | /* Perform the operation DST = SRC1 & ~SRC2. Return true if any bit | |
865 | in DST has changed. */ | |
866 | ||
867 | bool | |
868 | ebitmap_and_compl (ebitmap dst, ebitmap src1, ebitmap src2) | |
869 | { | |
870 | unsigned int src1size = src1->wordmask->n_bits; | |
871 | sbitmap_iterator sbi; | |
872 | unsigned int i; | |
873 | sbitmap tempmask; | |
874 | unsigned int neweltindex = 0; | |
875 | unsigned int src1eltindex = 0; | |
876 | bool changed = false; | |
877 | EBITMAP_ELT_TYPE *newarray; | |
878 | unsigned int newarraysize; | |
879 | ||
880 | /* XXX: Optimize like the into version. */ | |
881 | dst->cache = NULL; | |
882 | tempmask = sbitmap_alloc_with_popcount (src1size); | |
883 | sbitmap_zero (tempmask); | |
884 | sbitmap_copy (tempmask, src1->wordmask); | |
885 | ||
886 | newarraysize = src1->numwords; | |
1b4572a8 | 887 | newarray = XNEWVEC (EBITMAP_ELT_TYPE, newarraysize); |
53a853de DB |
888 | |
889 | EXECUTE_IF_SET_IN_SBITMAP (src1->wordmask, 0, i, sbi) | |
890 | { | |
891 | bool src2hasword; | |
892 | EBITMAP_ELT_TYPE tmpword; | |
893 | ||
894 | src2hasword = (i < src2->wordmask->n_bits | |
895 | && TEST_BIT (src2->wordmask, i)); | |
896 | ||
897 | if (src2hasword) | |
898 | { | |
899 | unsigned int src2count = sbitmap_popcount (src2->wordmask, i); | |
900 | tmpword = ebitmap_array_get (src1, src1eltindex++) | |
901 | & ~(ebitmap_array_get (src2, src2count)); | |
902 | if (tmpword) | |
903 | { | |
904 | newarray[neweltindex++] = tmpword; | |
905 | } | |
906 | else | |
0263463d | 907 | RESET_BIT_WITH_POPCOUNT (tempmask, i); |
53a853de DB |
908 | |
909 | } | |
910 | else | |
911 | { | |
912 | tmpword = ebitmap_array_get (src1, src1eltindex++); | |
913 | gcc_assert (tmpword != 0); | |
914 | newarray[neweltindex++] = tmpword; | |
915 | } | |
916 | ||
917 | if (i >= dst->wordmask->n_bits || !TEST_BIT (dst->wordmask, i)) | |
918 | { | |
919 | changed = true; | |
920 | } | |
921 | else if (!changed) | |
922 | { | |
923 | unsigned int count = sbitmap_popcount (dst->wordmask, i); | |
924 | changed |= ebitmap_array_get (dst, count) != tmpword; | |
925 | } | |
926 | } | |
927 | if (changed) | |
928 | { | |
929 | sbitmap_free (dst->wordmask); | |
930 | dst->wordmask = tempmask; | |
931 | dst->numwords = neweltindex; | |
932 | free (dst->elts); | |
933 | dst->elts = newarray; | |
934 | dst->n_elts = newarraysize; | |
935 | } | |
936 | else | |
937 | { | |
938 | free (tempmask); | |
939 | free (newarray); | |
940 | } | |
941 | #ifdef EBITMAP_DEBUGGING | |
942 | { | |
943 | unsigned int i; | |
944 | ebitmap_iterator ebi; | |
945 | ||
946 | EXECUTE_IF_SET_IN_EBITMAP (src1, 0, i, ebi) | |
947 | { | |
948 | if (!ebitmap_bit_p (src2, i)) | |
949 | gcc_assert (ebitmap_bit_p (dst, i)); | |
950 | } | |
951 | for (i = 0; i < dst->numwords; i++) | |
952 | gcc_assert (dst->elts[i] != 0); | |
953 | ||
4b9c6075 | 954 | sbitmap_verify_popcount (dst->wordmask); |
53a853de DB |
955 | gcc_assert (sbitmap_popcount (dst->wordmask, |
956 | dst->wordmask->n_bits) == dst->numwords); | |
957 | } | |
958 | #endif | |
959 | return changed; | |
960 | } | |
961 | ||
962 | /* Perform the operation DST = A | (B & ~C). */ | |
963 | ||
964 | bool | |
965 | ebitmap_ior_and_compl (ebitmap dst, ebitmap a, ebitmap b, ebitmap c) | |
966 | { | |
967 | bool changed; | |
968 | ebitmap temp = ebitmap_alloc (1); | |
969 | #ifdef EBITMAP_DEBUGGING | |
970 | ebitmap dstcopy = ebitmap_alloc (1); | |
971 | ebitmap_copy (dstcopy, dst); | |
972 | #endif | |
973 | ||
974 | dst->cache = NULL; | |
975 | ebitmap_and_compl (temp, b, c); | |
976 | changed = ebitmap_ior (dst, a, temp); | |
977 | #ifdef EBITMAP_DEBUGGING | |
978 | { | |
979 | ebitmap_iterator ebi; | |
980 | unsigned int i; | |
981 | ||
982 | EXECUTE_IF_SET_IN_EBITMAP (a, 0, i, ebi) | |
983 | gcc_assert (ebitmap_bit_p (dst, i)); | |
984 | ||
985 | EXECUTE_IF_SET_IN_EBITMAP (b, 0, i, ebi) | |
986 | if (!ebitmap_bit_p (c, i)) | |
987 | gcc_assert (ebitmap_bit_p (dst, i)); | |
988 | gcc_assert (changed == !ebitmap_equal_p (dst, dstcopy)); | |
989 | } | |
990 | #endif | |
991 | ebitmap_free (temp); | |
992 | ||
993 | return changed; | |
994 | } | |
995 | ||
996 | /* Return true if ebitmap DST is equal to ebitmap SRC. */ | |
997 | ||
998 | bool | |
999 | ebitmap_equal_p (ebitmap dst, ebitmap src) | |
1000 | { | |
1001 | unsigned int which = MIN (dst->wordmask->size, src->wordmask->size); | |
1002 | ||
1003 | if (dst->numwords != src->numwords) | |
1004 | return false; | |
1005 | ||
1006 | /* sbitmap_equal compares up to the size of the first argument, so | |
1007 | if the two sbitmaps are not equally sized, we need to pass the | |
1008 | smaller one as the first argument, or it will crash. */ | |
1009 | if (which == dst->wordmask->size | |
1010 | && !sbitmap_equal (dst->wordmask, src->wordmask)) | |
1011 | return false; | |
1012 | else if (which == src->wordmask->size | |
1013 | && !sbitmap_equal (src->wordmask, dst->wordmask)) | |
1014 | return false; | |
1015 | ||
1016 | return memcmp (dst->elts, src->elts, | |
1017 | dst->numwords * sizeof (EBITMAP_ELT_TYPE)) == 0; | |
1018 | return true; | |
1019 | } |