Daily bump.
[official-gcc.git] / gcc / ebitmap.c
blob8a7c7cb75421377d951073a6eb053a8a820a3ba6
1 /* Sparse array-based bitmaps.
2 Copyright (C) 2007 Free Software Foundation, Inc.
3 Contributed by Daniel Berlin <dberlin@dberlin.org>
5 This file is part of GCC.
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
9 Software Foundation; either version 3, or (at your option) any later
10 version.
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.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "rtl.h"
26 #include "flags.h"
27 #include "obstack.h"
28 #include "ebitmap.h"
30 /* The ebitmap data structure is a sparse bitmap structure that works
31 by having two pieces:
32 1. An array of all nonzero words in the structures, organized as
33 an array of HOST_WIDE_INT's.
34 2. A non-sparse bitmap saying which bitmap words are present in the
35 array.
37 As a consequence of this representation, testing whether a bit
38 exists in the bitmap is faster than linked-list bitmaps. For bits
39 in words that are all zero, the time to test is O(1). For bits in
40 words that exist, it requires O(n/sizeof(word)) time to perform the
41 test (ignoring the one element cache). It also has much better
42 locality than linked-list bitmaps.
44 To test whether a bit exists, we do the following:
45 1. Test whether the word the bit would appear in exists in the
46 bitmap (O(1) check of the mask). If not, fail.
48 2. Population count the mask up to the word containing the bit, to
49 find the place in the array the word would be (popcount is cached,
50 but this is just as slow as the linked-list bitmap)
51 3. Test the word to see if the bit exists.
53 Just like linked-list bitmaps, we cache the last element that has
54 been tested in order to speed up common access patterns.
56 Most of the other speedups are simply due to better locality of the
57 single contiguous array.
59 As would be expected in a structure like this, insertion into an
60 empty word in the middle requires moving bits to make room for the
61 new word. As most operations that perform sets perform them in
62 order, this is rarely a problem. We also take advantage of the
63 same element cache to make repeated sets to the same word O(1).
65 Operations on the entire bitmap are also more efficient than linked
66 list bitmaps, as they are all operating on contiguous memory, and
67 can be easily vectorized. They are all O(number of words) +
68 O(number of bits that may end up in the destination), as the
69 appropriate operation is first performed on the word mask, and then
70 only those elements that may generate results are touched.
72 Memory wise, the ebitmap starts out using less memory than the
73 linked-list bitmap, but its size in memory is technically bounded
74 by ((index of the highest bit set) / (size of a word) + (index of
75 the highest bit set) / ((size of a word) * (size of a word))) This
76 is because the mask is non-sparse. The mask could be transformed
77 into a sparse bitmap at the cost of making bit testing
78 *theoretically* slower (real world numbers have not been computed
79 yet as to whether it matters or not). */
81 /* #define EBITMAP_DEBUGGING */
83 /* Find the last set bit in ebitmap MAP. */
85 int
86 ebitmap_last_set_bit (ebitmap map)
88 unsigned int i = 0;
89 ebitmap_iterator ebi;
90 bool foundbit = false;
92 /* This is not the fastest way to do this, we could simply look for
93 the popcount, and start there, but this function is not used
94 anywhere speed critical. */
95 EXECUTE_IF_SET_IN_EBITMAP (map, 0, i, ebi)
97 foundbit = true;
101 if (foundbit)
102 return i;
103 return -1;
106 /* Grow or shrink the internal word array for MAP to NEWSIZE
107 elements. */
109 static inline void
110 ebitmap_array_grow (ebitmap map, unsigned int newsize)
112 if (newsize <= map->n_elts)
114 map->n_elts = newsize;
115 return;
118 newsize += newsize / 4;
120 map->n_elts = newsize;
121 map->elts = xrealloc (map->elts, sizeof (EBITMAP_ELT_TYPE) * newsize);
124 /* Grow the internal word array for MAP so it is at least SIZE
125 elements. Will not shrink the array if it is already big
126 enough. */
128 static inline void
129 ebitmap_array_maybe_grow (ebitmap map, unsigned int size)
131 if (size >= map->n_elts)
132 ebitmap_array_grow (map, size + 1);
135 /* Retrieve the IDX'th element from the word array for MAP. */
137 static inline EBITMAP_ELT_TYPE
138 ebitmap_array_get (ebitmap map, unsigned int idx)
140 gcc_assert (idx < map->n_elts);
141 return map->elts[idx];
144 /* Retrieve a pointer to the IDX'th element from the word array for
145 MAP. If the element index is greater than the size of the array,
146 the array will be grown to the correct size. */
148 static inline EBITMAP_ELT_TYPE *
149 ebitmap_array_grow_get (ebitmap map, unsigned int idx)
151 if (idx >= map->n_elts)
152 ebitmap_array_grow (map, idx + 1);
153 return &map->elts[idx];
156 /* Initialize the internal word array for MAP, so that it is SIZE
157 elements. */
159 static inline void
160 ebitmap_array_init (ebitmap map, unsigned int size)
162 if (size > 0)
164 map->elts = xmalloc (sizeof (EBITMAP_ELT_TYPE) * size);
165 map->n_elts = size;
167 else
169 map->n_elts = 0;
170 map->elts = NULL;
174 /* Free the internal word array for MAP. */
176 static inline void
177 ebitmap_array_clear (ebitmap map)
179 if (map->elts)
181 free (map->elts);
182 map->elts = NULL;
184 map->n_elts = 0;
187 /* Clear ebitmap MAP. */
189 void
190 ebitmap_clear (ebitmap map)
192 ebitmap_array_clear (map);
193 sbitmap_zero (map->wordmask);
194 map->wordmask = sbitmap_resize (map->wordmask, 1, 0);
195 map->numwords = 0;
196 map->cache = NULL;
197 map->cacheindex = 0;
200 /* Allocate an ebitmap with enough room for SIZE bits to start out. */
202 ebitmap
203 ebitmap_alloc (unsigned int size)
205 ebitmap ret = xmalloc (sizeof (struct ebitmap_def));
206 if (size == 0)
207 size = EBITMAP_ELT_BITS;
208 ebitmap_array_init (ret, (size + EBITMAP_ELT_BITS - 1) / EBITMAP_ELT_BITS);
209 ret->wordmask = sbitmap_alloc_with_popcount (size);
210 sbitmap_zero (ret->wordmask);
211 ret->numwords = 0;
212 ret->cache = NULL;
213 ret->cacheindex = 0;
215 return ret;
218 /* Clear BIT from ebitmap MAP. */
220 void
221 ebitmap_clear_bit (ebitmap map, unsigned int bit)
223 unsigned int wordindex = bit / EBITMAP_ELT_BITS;
224 unsigned int eltwordindex = 0;
225 unsigned int bitindex, shift;
226 bool have_eltwordindex = false;
227 EBITMAP_ELT_TYPE *elt_ptr;
229 /* If the bit can't exist in our bitmap, just return. */
230 if (map->numwords == 0)
231 return;
233 if (wordindex >= map->wordmask->n_bits
234 || !TEST_BIT (map->wordmask, wordindex))
235 return;
237 if (map->cache != NULL && map->cacheindex == wordindex)
238 elt_ptr = map->cache;
239 else
241 eltwordindex = sbitmap_popcount (map->wordmask, wordindex);
242 elt_ptr = &map->elts[eltwordindex];
243 have_eltwordindex = true;
246 bitindex = bit % EBITMAP_ELT_BITS;
247 shift = bitindex;
249 *(elt_ptr) &= ~(((EBITMAP_ELT_TYPE)1) << shift);
251 /* Clear out the empty words. */
252 if (*(elt_ptr) == 0)
254 if (!have_eltwordindex)
255 eltwordindex = sbitmap_popcount (map->wordmask, wordindex);
257 if (map->cache != NULL && map->cacheindex == eltwordindex)
258 map->cache = NULL;
260 RESET_BIT (map->wordmask, wordindex);
262 memmove(&map->elts[eltwordindex], &map->elts[eltwordindex + 1],
263 sizeof (EBITMAP_ELT_TYPE) * (map->numwords - eltwordindex));
264 map->numwords--;
268 /* Set BIT in ebitmap MAP. */
270 void
271 ebitmap_set_bit (ebitmap map, unsigned int bit)
273 unsigned int wordindex = bit / EBITMAP_ELT_BITS;
274 unsigned int eltwordindex;
275 unsigned int bitindex = bit % EBITMAP_ELT_BITS;
277 /* If we have this element cached, just set the bit in it. */
278 if (map->cache && map->cacheindex == wordindex)
280 (*map->cache) |= (EBITMAP_ELT_TYPE)1 << bitindex;
281 return;
284 /* Resize the wordmask if necessary. */
285 if (wordindex >= map->wordmask->n_bits)
286 map->wordmask = sbitmap_resize (map->wordmask, wordindex + 1, 0);
288 /* Allocate a new word in the array and move whatever is in it's
289 place, if necessary. */
290 if (!TEST_BIT (map->wordmask, wordindex))
292 unsigned long count;
293 unsigned int i;
295 SET_BIT (map->wordmask, wordindex);
296 count = sbitmap_popcount (map->wordmask, wordindex);
297 gcc_assert (count <= map->numwords);
299 for (i = map->numwords; i > count; i--)
301 EBITMAP_ELT_TYPE *newelt;
302 newelt = ebitmap_array_grow_get (map, i);
303 *newelt = ebitmap_array_get (map, i - 1);
305 map->numwords++;
306 eltwordindex = count;
307 ebitmap_array_maybe_grow (map, eltwordindex);
308 map->elts[eltwordindex] = 0;
310 else
312 eltwordindex = sbitmap_popcount (map->wordmask, wordindex);
315 /* Set the actual bit. */
316 bitindex = bit % EBITMAP_ELT_BITS;
318 map->elts[eltwordindex] |= (EBITMAP_ELT_TYPE)1 << bitindex;
319 map->cache = &map->elts[eltwordindex];
320 map->cacheindex = wordindex;
324 /* Return true if MAP contains BIT. */
326 bool
327 ebitmap_bit_p (ebitmap map, unsigned int bit)
329 unsigned int wordindex = bit / EBITMAP_ELT_BITS;
330 unsigned int bitindex= bit % EBITMAP_ELT_BITS;
332 /* Trivial empty ebitmap case. */
333 if (map->numwords == 0)
334 return false;
336 if (map->cache && map->cacheindex == wordindex)
337 return ((*map->cache) >> bitindex) & 1;
339 /* If the wordindex is greater than the size of the wordmask, *or*
340 it's not set in the wordmask, this bit can't exist in our
341 ebitmap. */
342 if (wordindex >= map->wordmask->n_bits
343 || !TEST_BIT (map->wordmask, wordindex))
344 return false;
346 /* Find the bit and test it. */
347 map->cacheindex = wordindex;
348 wordindex = sbitmap_popcount (map->wordmask, wordindex);
349 map->cache = &map->elts[wordindex];
351 return (map->elts[wordindex] >> bitindex) & 1;
354 /* Copy ebitmap SRC to DST. */
356 void
357 ebitmap_copy (ebitmap dst, ebitmap src)
359 /* Blow away any existing wordmask, and copy the new one. */
360 sbitmap_free (dst->wordmask);
361 dst->wordmask = sbitmap_alloc_with_popcount (src->wordmask->n_bits);
362 sbitmap_copy (dst->wordmask, src->wordmask);
364 /* Make sure our destination array is big enough, and then copy the
365 actual words. */
366 ebitmap_array_grow (dst, src->numwords);
367 memcpy (dst->elts, src->elts,
368 src->numwords * sizeof (EBITMAP_ELT_TYPE));
369 dst->numwords = src->numwords;
370 dst->cache = NULL;
373 /* Dump ebitmap BMAP to FILE. */
375 void
376 dump_ebitmap (FILE *file, ebitmap bmap)
378 unsigned int pos;
379 unsigned int i;
380 int res;
381 unsigned int size;
383 res = sbitmap_last_set_bit (bmap->wordmask);
384 if (res == -1)
385 size = 0;
386 else
387 size = (res + 1) * EBITMAP_ELT_BITS;
389 fprintf (file, "n_words = %d, set = {", bmap->numwords);
391 for (pos = 30, i = 0; i < size; i++)
392 if (ebitmap_bit_p (bmap, i))
394 if (pos > 70)
396 fprintf (file, "\n ");
397 pos = 0;
400 pos += fprintf (file, "%d ", i);
403 fprintf (file, "}\n");
406 /* Dump ebitmap BMAP to stderr. */
408 void
409 debug_ebitmap (ebitmap bmap)
411 dump_ebitmap (stderr, bmap);
414 /* Perform the operation DST &= SRC. */
416 void
417 ebitmap_and_into (ebitmap dst, ebitmap src)
419 sbitmap_iterator sbi;
420 unsigned int i;
421 unsigned int neweltindex = 0;
422 unsigned int dsteltindex = 0;
423 unsigned int srceltindex = 0;
425 gcc_assert (dst != src);
427 dst->cache = NULL;
429 /* Short circuit the empty bitmap cases. */
430 if (src->numwords == 0 || dst->numwords == 0)
432 ebitmap_clear (dst);
433 return;
436 /* AND the masks, then walk the words that may actually appear in
437 the result, AND'ing them. */
438 sbitmap_a_and_b (dst->wordmask, dst->wordmask, src->wordmask);
440 EXECUTE_IF_SET_IN_SBITMAP (dst->wordmask, 0, i, sbi)
442 EBITMAP_ELT_TYPE tmpword = ebitmap_array_get (src, srceltindex++);
443 tmpword &= ebitmap_array_get (dst, dsteltindex++);
444 if (tmpword != 0)
446 EBITMAP_ELT_TYPE *dstplace;
447 dstplace = ebitmap_array_grow_get (dst, neweltindex++);
448 *dstplace = tmpword;
450 else
451 RESET_BIT (dst->wordmask, i);
453 #ifdef EBITMAP_DEBUGGING
455 unsigned int i;
457 for (i = 0; i < dst->numwords; i++)
458 gcc_assert (dst->elts[i] != 0);
460 verify_popcount (dst->wordmask);
461 gcc_assert (sbitmap_popcount (dst->wordmask,
462 dst->wordmask->n_bits) == dst->numwords);
464 #endif
465 dst->numwords = neweltindex;
468 /* Perform the operation DST = SRC1 & SRC2. */
470 void
471 ebitmap_and (ebitmap dst, ebitmap src1, ebitmap src2)
473 sbitmap_iterator sbi;
474 unsigned int i;
475 unsigned int neweltindex = 0;
476 unsigned int src1eltindex = 0;
477 unsigned int src2eltindex = 0;
479 dst->cache = NULL;
480 if (src1->numwords == 0 || src2->numwords == 0)
482 ebitmap_clear (dst);
483 return;
486 dst->wordmask
487 = sbitmap_resize (dst->wordmask,
488 MIN (src1->wordmask->n_bits, src2->wordmask->n_bits),
490 sbitmap_a_and_b (dst->wordmask, src1->wordmask, src2->wordmask);
492 EXECUTE_IF_SET_IN_SBITMAP (dst->wordmask, 0, i, sbi)
494 bool src1hasword, src2hasword;
496 src1hasword = TEST_BIT (src1->wordmask, i);
497 src2hasword = TEST_BIT (src2->wordmask, i);
499 if (src1hasword && src2hasword)
501 EBITMAP_ELT_TYPE tmpword = ebitmap_array_get (src1, src1eltindex++);
502 tmpword &= ebitmap_array_get (src2, src2eltindex++);
503 if (tmpword != 0)
505 EBITMAP_ELT_TYPE *dstplace;
506 dstplace = ebitmap_array_grow_get (dst, neweltindex++);
507 *dstplace = tmpword;
509 else
510 RESET_BIT (dst->wordmask, i);
512 else if (src1hasword)
513 src1eltindex++;
514 else
515 src2eltindex++;
517 #ifdef EBITMAP_DEBUGGING
519 ebitmap_iterator ebi;
520 unsigned int i;
522 for (i = 0; i < dst->numwords; i++)
523 gcc_assert (dst->elts[i] != 0);
525 EXECUTE_IF_SET_IN_EBITMAP (src1, 0, i, ebi)
526 if (ebitmap_bit_p (src2, i))
527 gcc_assert (ebitmap_bit_p (dst, i));
529 for (i = 0; i < dst->numwords; i++)
530 gcc_assert (dst->elts[i] != 0);
532 verify_popcount (dst->wordmask);
533 gcc_assert (sbitmap_popcount (dst->wordmask,
534 dst->wordmask->n_bits) == dst->numwords);
536 #endif
537 dst->numwords = neweltindex;
540 /* Perform the operation DST |= SRC. Return true if any bits in DST
541 changed. */
543 bool
544 ebitmap_ior_into (ebitmap dst, ebitmap src)
546 unsigned int dstsize = dst->wordmask->n_bits;
547 unsigned int srcsize = src->wordmask->n_bits;
548 sbitmap_iterator sbi;
549 unsigned int i;
550 sbitmap tempmask;
551 unsigned int neweltindex = 0;
552 unsigned int dsteltindex = 0;
553 unsigned int srceltindex = 0;
554 bool changed = false;
555 EBITMAP_ELT_TYPE *newarray;
556 unsigned int newarraysize;
557 #ifdef EBITMAP_DEBUGGING
558 ebitmap dstcopy = ebitmap_alloc (1);
559 ebitmap_copy (dstcopy, dst);
560 #endif
562 dst->cache = NULL;
563 if (dst == src)
564 return false;
566 if (dst->numwords == 0 && src->numwords != 0)
568 ebitmap_copy (dst, src);
569 return true;
571 else if (src->numwords == 0)
572 return false;
574 /* We can do without the temp mask if it's faster, but it would mean
575 touching more words in the actual dense vector. */
576 tempmask = sbitmap_alloc (MAX (srcsize, dstsize));
577 sbitmap_zero (tempmask);
578 if (srcsize == dstsize)
580 sbitmap_a_or_b (tempmask, dst->wordmask, src->wordmask);
582 else
584 dst->wordmask = sbitmap_resize (dst->wordmask, MAX (srcsize, dstsize),
586 if (srcsize >= dstsize)
588 sbitmap_copy_n (tempmask, dst->wordmask, dst->wordmask->size);
589 sbitmap_a_or_b (tempmask, tempmask, src->wordmask);
591 else
593 sbitmap_copy_n (tempmask, src->wordmask, src->wordmask->size);
594 sbitmap_a_or_b (tempmask, tempmask, dst->wordmask);
597 newarraysize = src->numwords + dst->numwords;
598 newarray = xmalloc (newarraysize * sizeof (EBITMAP_ELT_TYPE));
600 EXECUTE_IF_SET_IN_SBITMAP (tempmask, 0, i, sbi)
602 bool dsthasword, srchasword;
604 dsthasword = (i < dst->wordmask->n_bits
605 && TEST_BIT (dst->wordmask, i));
606 srchasword = (i < src->wordmask->n_bits
607 && TEST_BIT (src->wordmask, i));
609 if (dsthasword && srchasword)
611 EBITMAP_ELT_TYPE tmpword = ebitmap_array_get (src, srceltindex++);
612 tmpword |= ebitmap_array_get (dst, dsteltindex);
613 if (!changed)
614 changed |= tmpword != ebitmap_array_get (dst, dsteltindex);
615 dsteltindex++;
616 newarray[neweltindex++] = tmpword;
618 else if (dsthasword)
620 newarray [neweltindex++] = ebitmap_array_get (dst, dsteltindex++);
622 else
624 newarray [neweltindex++] = ebitmap_array_get (src, srceltindex++);
625 gcc_assert (i < dst->wordmask->n_bits);
626 SET_BIT (dst->wordmask, i);
627 changed |= true;
631 sbitmap_free (tempmask);
632 if (changed)
634 dst->numwords = neweltindex;
635 free (dst->elts);
636 dst->elts = newarray;
637 dst->n_elts = newarraysize;
639 else
640 free (newarray);
642 #ifdef EBITMAP_DEBUGGING
644 ebitmap_iterator ebi;
645 unsigned int i;
647 for (i = 0; i < dst->numwords; i++)
648 gcc_assert (dst->elts[i] != 0);
650 EXECUTE_IF_SET_IN_EBITMAP (src, 0, i, ebi)
651 gcc_assert (ebitmap_bit_p (dst, i));
652 EXECUTE_IF_SET_IN_EBITMAP (dstcopy, 0, i, ebi)
653 gcc_assert (ebitmap_bit_p (dst, i));
655 verify_popcount (dst->wordmask);
656 gcc_assert (changed == !ebitmap_equal_p (dst, dstcopy));
657 gcc_assert (sbitmap_popcount (dst->wordmask,
658 dst->wordmask->n_bits) == dst->numwords);
660 #endif
661 return changed;
664 /* Perform the operation DST = SRC1 | SRC2. Return true if any bit
665 in DST has changed. */
667 bool
668 ebitmap_ior (ebitmap dst, ebitmap src1, ebitmap src2)
670 unsigned int src1size = src1->wordmask->n_bits;
671 unsigned int src2size = src2->wordmask->n_bits;
672 sbitmap_iterator sbi;
673 unsigned int i;
674 sbitmap tempmask;
675 unsigned int neweltindex = 0;
676 unsigned int src1eltindex = 0;
677 unsigned int src2eltindex = 0;
678 bool changed = false;
679 EBITMAP_ELT_TYPE *newarray;
680 unsigned int newarraysize;
681 #ifdef EBITMAP_DEBUGGING
682 ebitmap dstcopy = ebitmap_alloc (1);
683 ebitmap_copy (dstcopy, dst);
684 #endif
686 dst->cache = NULL;
687 tempmask = sbitmap_alloc_with_popcount (MAX (src1size, src2size));
688 sbitmap_zero (tempmask);
689 if (src1size == src2size)
691 sbitmap_a_or_b (tempmask, src1->wordmask, src2->wordmask);
693 else
695 if (src1size >= src2size)
697 sbitmap_copy_n (tempmask, src2->wordmask, src2->wordmask->size);
698 sbitmap_a_or_b (tempmask, tempmask, src1->wordmask);
700 else
702 sbitmap_copy_n (tempmask, src1->wordmask, src1->wordmask->size);
703 sbitmap_a_or_b (tempmask, tempmask, src2->wordmask);
706 newarraysize = src1->numwords + src2->numwords;
707 newarray = xmalloc (newarraysize * sizeof (EBITMAP_ELT_TYPE));
709 EXECUTE_IF_SET_IN_SBITMAP (tempmask, 0, i, sbi)
711 bool src1hasword, src2hasword;
712 EBITMAP_ELT_TYPE tmpword;
713 src1hasword = (i < src1->wordmask->n_bits
714 && TEST_BIT (src1->wordmask, i));
715 src2hasword = (i < src2->wordmask->n_bits
716 && TEST_BIT (src2->wordmask, i));
718 if (src1hasword && src2hasword)
720 tmpword = (ebitmap_array_get (src1, src1eltindex++)
721 | ebitmap_array_get (src2, src2eltindex++));
722 newarray[neweltindex++] = tmpword;
724 else if (src1hasword)
726 tmpword = ebitmap_array_get (src1, src1eltindex++);
727 newarray [neweltindex++] = tmpword;
729 else
731 tmpword = ebitmap_array_get (src2, src2eltindex++);
732 newarray [neweltindex++] = tmpword;
735 if (i >= dst->wordmask->n_bits || !TEST_BIT (dst->wordmask, i))
737 changed = true;
739 else if (!changed)
741 unsigned int count = sbitmap_popcount (dst->wordmask, i);
742 changed |= ebitmap_array_get (dst, count) != tmpword;
746 if (changed)
748 sbitmap_free (dst->wordmask);
749 dst->wordmask = tempmask;
750 dst->numwords = neweltindex;
751 free (dst->elts);
752 dst->elts = newarray;
753 dst->n_elts = newarraysize;
755 else
757 sbitmap_free (tempmask);
758 free (newarray);
761 #ifdef EBITMAP_DEBUGGING
763 ebitmap_iterator ebi;
764 unsigned int i;
766 for (i = 0; i < dst->numwords; i++)
767 gcc_assert (dst->elts[i] != 0);
769 EXECUTE_IF_SET_IN_EBITMAP (src1, 0, i, ebi)
770 gcc_assert (ebitmap_bit_p (dst, i));
772 EXECUTE_IF_SET_IN_EBITMAP (src2, 0, i, ebi)
773 gcc_assert (ebitmap_bit_p (dst, i));
775 verify_popcount (dst->wordmask);
776 gcc_assert (changed == !ebitmap_equal_p (dst, dstcopy));
777 gcc_assert (sbitmap_popcount (dst->wordmask,
778 dst->wordmask->n_bits) == dst->numwords);
779 #endif
781 return changed;
784 /* Perform the operation DST &= ~SRC. Return true if any bit in DST
785 has changed. */
787 bool
788 ebitmap_and_compl_into (ebitmap dst, ebitmap src)
790 bool changed = false;
791 unsigned int i;
792 unsigned int neweltindex = 0;
793 unsigned int dsteltindex = 0;
794 sbitmap_iterator sbi;
795 #ifdef EBITMAP_DEBUGGING
796 ebitmap dstcopy = ebitmap_alloc (1);
797 ebitmap_copy (dstcopy, dst);
798 #endif
800 gcc_assert (dst != src);
801 dst->cache = NULL;
802 if (src->numwords == 0)
803 return false;
805 EXECUTE_IF_SET_IN_SBITMAP (dst->wordmask, 0, i, sbi)
807 bool srchasword;
809 srchasword = (i < src->wordmask->n_bits
810 && TEST_BIT (src->wordmask, i));
812 if (srchasword)
814 unsigned int srccount = sbitmap_popcount (src->wordmask, i);
815 EBITMAP_ELT_TYPE tmpword = ebitmap_array_get (dst, dsteltindex);
816 tmpword &= ~(ebitmap_array_get (src, srccount));
817 if (!changed)
818 changed |= ebitmap_array_get (dst, dsteltindex) != tmpword;
819 dsteltindex++;
820 if (tmpword != 0)
822 EBITMAP_ELT_TYPE *dstplace;
823 dstplace = ebitmap_array_grow_get (dst, neweltindex++);
824 *dstplace = tmpword;
826 else
827 RESET_BIT (dst->wordmask, i);
829 else
831 dsteltindex++;
832 neweltindex++;
835 #ifdef EBITMAP_DEBUGGING
837 unsigned int i;
838 ebitmap_iterator ebi;
840 EXECUTE_IF_SET_IN_EBITMAP (dstcopy, 0, i, ebi)
842 if (!ebitmap_bit_p (src, i))
843 gcc_assert (ebitmap_bit_p (dst, i));
846 for (i = 0; i < dst->numwords; i++)
847 gcc_assert (dst->elts[i] != 0);
849 gcc_assert (sbitmap_popcount (dst->wordmask,
850 dst->wordmask->n_bits) == neweltindex);
851 verify_popcount (dst->wordmask);
852 gcc_assert (changed == !ebitmap_equal_p (dst, dstcopy));
853 gcc_assert (sbitmap_popcount (dst->wordmask,
854 dst->wordmask->n_bits) == dst->numwords);
856 #endif
857 dst->numwords = neweltindex;
858 /* sbitmap_popcount (dst->wordmask, -1); */
860 return changed;
863 /* Perform the operation DST = SRC1 & ~SRC2. Return true if any bit
864 in DST has changed. */
866 bool
867 ebitmap_and_compl (ebitmap dst, ebitmap src1, ebitmap src2)
869 unsigned int src1size = src1->wordmask->n_bits;
870 sbitmap_iterator sbi;
871 unsigned int i;
872 sbitmap tempmask;
873 unsigned int neweltindex = 0;
874 unsigned int src1eltindex = 0;
875 bool changed = false;
876 EBITMAP_ELT_TYPE *newarray;
877 unsigned int newarraysize;
879 /* XXX: Optimize like the into version. */
880 dst->cache = NULL;
881 tempmask = sbitmap_alloc_with_popcount (src1size);
882 sbitmap_zero (tempmask);
883 sbitmap_copy (tempmask, src1->wordmask);
885 newarraysize = src1->numwords;
886 newarray = xmalloc (newarraysize * sizeof (EBITMAP_ELT_TYPE));
888 EXECUTE_IF_SET_IN_SBITMAP (src1->wordmask, 0, i, sbi)
890 bool src2hasword;
891 EBITMAP_ELT_TYPE tmpword;
893 src2hasword = (i < src2->wordmask->n_bits
894 && TEST_BIT (src2->wordmask, i));
896 if (src2hasword)
898 unsigned int src2count = sbitmap_popcount (src2->wordmask, i);
899 tmpword = ebitmap_array_get (src1, src1eltindex++)
900 & ~(ebitmap_array_get (src2, src2count));
901 if (tmpword)
903 newarray[neweltindex++] = tmpword;
905 else
906 RESET_BIT (tempmask, i);
909 else
911 tmpword = ebitmap_array_get (src1, src1eltindex++);
912 gcc_assert (tmpword != 0);
913 newarray[neweltindex++] = tmpword;
916 if (i >= dst->wordmask->n_bits || !TEST_BIT (dst->wordmask, i))
918 changed = true;
920 else if (!changed)
922 unsigned int count = sbitmap_popcount (dst->wordmask, i);
923 changed |= ebitmap_array_get (dst, count) != tmpword;
926 if (changed)
928 sbitmap_free (dst->wordmask);
929 dst->wordmask = tempmask;
930 dst->numwords = neweltindex;
931 free (dst->elts);
932 dst->elts = newarray;
933 dst->n_elts = newarraysize;
935 else
937 free (tempmask);
938 free (newarray);
940 #ifdef EBITMAP_DEBUGGING
942 unsigned int i;
943 ebitmap_iterator ebi;
945 EXECUTE_IF_SET_IN_EBITMAP (src1, 0, i, ebi)
947 if (!ebitmap_bit_p (src2, i))
948 gcc_assert (ebitmap_bit_p (dst, i));
950 for (i = 0; i < dst->numwords; i++)
951 gcc_assert (dst->elts[i] != 0);
953 verify_popcount (dst->wordmask);
954 gcc_assert (sbitmap_popcount (dst->wordmask,
955 dst->wordmask->n_bits) == dst->numwords);
957 #endif
958 return changed;
961 /* Perform the operation DST = A | (B & ~C). */
963 bool
964 ebitmap_ior_and_compl (ebitmap dst, ebitmap a, ebitmap b, ebitmap c)
966 bool changed;
967 ebitmap temp = ebitmap_alloc (1);
968 #ifdef EBITMAP_DEBUGGING
969 ebitmap dstcopy = ebitmap_alloc (1);
970 ebitmap_copy (dstcopy, dst);
971 #endif
973 dst->cache = NULL;
974 ebitmap_and_compl (temp, b, c);
975 changed = ebitmap_ior (dst, a, temp);
976 #ifdef EBITMAP_DEBUGGING
978 ebitmap_iterator ebi;
979 unsigned int i;
981 EXECUTE_IF_SET_IN_EBITMAP (a, 0, i, ebi)
982 gcc_assert (ebitmap_bit_p (dst, i));
984 EXECUTE_IF_SET_IN_EBITMAP (b, 0, i, ebi)
985 if (!ebitmap_bit_p (c, i))
986 gcc_assert (ebitmap_bit_p (dst, i));
987 gcc_assert (changed == !ebitmap_equal_p (dst, dstcopy));
989 #endif
990 ebitmap_free (temp);
992 return changed;
995 /* Return true if ebitmap DST is equal to ebitmap SRC. */
997 bool
998 ebitmap_equal_p (ebitmap dst, ebitmap src)
1000 unsigned int which = MIN (dst->wordmask->size, src->wordmask->size);
1002 if (dst->numwords != src->numwords)
1003 return false;
1005 /* sbitmap_equal compares up to the size of the first argument, so
1006 if the two sbitmaps are not equally sized, we need to pass the
1007 smaller one as the first argument, or it will crash. */
1008 if (which == dst->wordmask->size
1009 && !sbitmap_equal (dst->wordmask, src->wordmask))
1010 return false;
1011 else if (which == src->wordmask->size
1012 && !sbitmap_equal (src->wordmask, dst->wordmask))
1013 return false;
1015 return memcmp (dst->elts, src->elts,
1016 dst->numwords * sizeof (EBITMAP_ELT_TYPE)) == 0;
1017 return true;