Mercurial > hg > CbC > CbC_gcc

comparison gcc/ebitmap.c @ 0:a06113de4d67

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
first commit
author kent <kent@cr.ie.u-ryukyu.ac.jp>
date Fri, 17 Jul 2009 14:47:48 +0900
parents
children 77e2b8dfacca
comparison
equal deleted inserted replaced
-1:000000000000 0:a06113de4d67
1 /* Sparse array-based bitmaps.
2 Copyright (C) 2007, 2008 Free Software Foundation, Inc.
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
9 Software Foundation; either version 3, or (at your option) any later
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
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
20
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"
29
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.
36
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.
43
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.
47
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.
52
53 Just like linked-list bitmaps, we cache the last element that has
54 been tested in order to speed up common access patterns.
55
56 Most of the other speedups are simply due to better locality of the
57 single contiguous array.
58
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).
64
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.
71
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). */
80
81 /* #define EBITMAP_DEBUGGING */
82
83 /* Find the last set bit in ebitmap MAP. */
84
85 int
86 ebitmap_last_set_bit (ebitmap map)
87 {
88 unsigned int i = 0;
89 ebitmap_iterator ebi;
90 bool foundbit = false;
91
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)
96 {
97 foundbit = true;
98 }
99
100
101 if (foundbit)
102 return i;
103 return -1;
104 }
105
106 /* Grow or shrink the internal word array for MAP to NEWSIZE
107 elements. */
108
109 static inline void
110 ebitmap_array_grow (ebitmap map, unsigned int newsize)
111 {
112 if (newsize <= map->n_elts)
113 {
114 map->n_elts = newsize;
115 return;
116 }
117
118 newsize += newsize / 4;
119
120 map->n_elts = newsize;
121 map->elts = XRESIZEVEC (EBITMAP_ELT_TYPE, map->elts, newsize);
122 }
123
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. */
127
128 static inline void
129 ebitmap_array_maybe_grow (ebitmap map, unsigned int size)
130 {
131 if (size >= map->n_elts)
132 ebitmap_array_grow (map, size + 1);
133 }
134
135 /* Retrieve the IDX'th element from the word array for MAP. */
136
137 static inline EBITMAP_ELT_TYPE
138 ebitmap_array_get (ebitmap map, unsigned int idx)
139 {
140 gcc_assert (idx < map->n_elts);
141 return map->elts[idx];
142 }
143
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. */
147
148 static inline EBITMAP_ELT_TYPE *
149 ebitmap_array_grow_get (ebitmap map, unsigned int idx)
150 {
151 if (idx >= map->n_elts)
152 ebitmap_array_grow (map, idx + 1);
153 return &map->elts[idx];
154 }
155
156 /* Initialize the internal word array for MAP, so that it is SIZE
157 elements. */
158
159 static inline void
160 ebitmap_array_init (ebitmap map, unsigned int size)
161 {
162 if (size > 0)
163 {
164 map->elts = XNEWVEC (EBITMAP_ELT_TYPE, size);
165 map->n_elts = size;
166 }
167 else
168 {
169 map->n_elts = 0;
170 map->elts = NULL;
171 }
172 }
173
174 /* Free the internal word array for MAP. */
175
176 static inline void
177 ebitmap_array_clear (ebitmap map)
178 {
179 if (map->elts)
180 {
181 free (map->elts);
182 map->elts = NULL;
183 }
184 map->n_elts = 0;
185 }
186
187 /* Clear ebitmap MAP. */
188
189 void
190 ebitmap_clear (ebitmap map)
191 {
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;
198 }
199
200 /* Allocate an ebitmap with enough room for SIZE bits to start out. */
201
202 ebitmap
203 ebitmap_alloc (unsigned int size)
204 {
205 ebitmap ret = XNEW (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;
214
215 return ret;
216 }
217
218 /* Clear BIT from ebitmap MAP. */
219
220 void
221 ebitmap_clear_bit (ebitmap map, unsigned int bit)
222 {
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;
228
229 /* If the bit can't exist in our bitmap, just return. */
230 if (map->numwords == 0)
231 return;
232
233 if (wordindex >= map->wordmask->n_bits
234 || !TEST_BIT (map->wordmask, wordindex))
235 return;
236
237 if (map->cache != NULL && map->cacheindex == wordindex)
238 elt_ptr = map->cache;
239 else
240 {
241 eltwordindex = sbitmap_popcount (map->wordmask, wordindex);
242 elt_ptr = &map->elts[eltwordindex];
243 have_eltwordindex = true;
244 }
245
246 bitindex = bit % EBITMAP_ELT_BITS;
247 shift = bitindex;
248
249 *(elt_ptr) &= ~(((EBITMAP_ELT_TYPE)1) << shift);
250
251 /* Clear out the empty words. */
252 if (*(elt_ptr) == 0)
253 {
254 if (!have_eltwordindex)
255 eltwordindex = sbitmap_popcount (map->wordmask, wordindex);
256
257 if (map->cache != NULL && map->cacheindex == eltwordindex)
258 map->cache = NULL;
259
260 RESET_BIT (map->wordmask, wordindex);
261
262 memmove(&map->elts[eltwordindex], &map->elts[eltwordindex + 1],
263 sizeof (EBITMAP_ELT_TYPE) * (map->numwords - eltwordindex));
264 map->numwords--;
265 }
266 }
267
268 /* Set BIT in ebitmap MAP. */
269
270 void
271 ebitmap_set_bit (ebitmap map, unsigned int bit)
272 {
273 unsigned int wordindex = bit / EBITMAP_ELT_BITS;
274 unsigned int eltwordindex;
275 unsigned int bitindex = bit % EBITMAP_ELT_BITS;
276
277 /* If we have this element cached, just set the bit in it. */
278 if (map->cache && map->cacheindex == wordindex)
279 {
280 (*map->cache) |= (EBITMAP_ELT_TYPE)1 << bitindex;
281 return;
282 }
283
284 /* Resize the wordmask if necessary. */
285 if (wordindex >= map->wordmask->n_bits)
286 map->wordmask = sbitmap_resize (map->wordmask, wordindex + 1, 0);
287
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))
291 {
292 unsigned long count;
293 unsigned int i;
294
295 SET_BIT (map->wordmask, wordindex);
296 count = sbitmap_popcount (map->wordmask, wordindex);
297 gcc_assert (count <= map->numwords);
298
299 for (i = map->numwords; i > count; i--)
300 {
301 EBITMAP_ELT_TYPE *newelt;
302 newelt = ebitmap_array_grow_get (map, i);
303 *newelt = ebitmap_array_get (map, i - 1);
304 }
305 map->numwords++;
306 eltwordindex = count;
307 ebitmap_array_maybe_grow (map, eltwordindex);
308 map->elts[eltwordindex] = 0;
309 }
310 else
311 {
312 eltwordindex = sbitmap_popcount (map->wordmask, wordindex);
313 }
314
315 /* Set the actual bit. */
316 bitindex = bit % EBITMAP_ELT_BITS;
317
318 map->elts[eltwordindex] |= (EBITMAP_ELT_TYPE)1 << bitindex;
319 map->cache = &map->elts[eltwordindex];
320 map->cacheindex = wordindex;
321 }
322
323
324 /* Return true if MAP contains BIT. */
325
326 bool
327 ebitmap_bit_p (ebitmap map, unsigned int bit)
328 {
329 unsigned int wordindex = bit / EBITMAP_ELT_BITS;
330 unsigned int bitindex= bit % EBITMAP_ELT_BITS;
331
332 /* Trivial empty ebitmap case. */
333 if (map->numwords == 0)
334 return false;
335
336 if (map->cache && map->cacheindex == wordindex)
337 return ((*map->cache) >> bitindex) & 1;
338
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;
345
346 /* Find the bit and test it. */
347 map->cacheindex = wordindex;
348 wordindex = sbitmap_popcount (map->wordmask, wordindex);
349 map->cache = &map->elts[wordindex];
350
351 return (map->elts[wordindex] >> bitindex) & 1;
352 }
353
354 /* Copy ebitmap SRC to DST. */
355
356 void
357 ebitmap_copy (ebitmap dst, ebitmap src)
358 {
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);
363
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;
371 }
372
373 /* Dump ebitmap BMAP to FILE. */
374
375 void
376 dump_ebitmap (FILE *file, ebitmap bmap)
377 {
378 unsigned int pos;
379 unsigned int i;
380 int res;
381 unsigned int size;
382
383 res = sbitmap_last_set_bit (bmap->wordmask);
384 if (res == -1)
385 size = 0;
386 else
387 size = (res + 1) * EBITMAP_ELT_BITS;
388
389 fprintf (file, "n_words = %d, set = {", bmap->numwords);
390
391 for (pos = 30, i = 0; i < size; i++)
392 if (ebitmap_bit_p (bmap, i))
393 {
394 if (pos > 70)
395 {
396 fprintf (file, "\n ");
397 pos = 0;
398 }
399
400 pos += fprintf (file, "%d ", i);
401 }
402
403 fprintf (file, "}\n");
404 }
405
406 /* Dump ebitmap BMAP to stderr. */
407
408 void
409 debug_ebitmap (ebitmap bmap)
410 {
411 dump_ebitmap (stderr, bmap);
412 }
413
414 /* Perform the operation DST &= SRC. */
415
416 void
417 ebitmap_and_into (ebitmap dst, ebitmap src)
418 {
419 sbitmap_iterator sbi;
420 unsigned int i;
421 unsigned int neweltindex = 0;
422 unsigned int dsteltindex = 0;
423 unsigned int srceltindex = 0;
424
425 gcc_assert (dst != src);
426
427 dst->cache = NULL;
428
429 /* Short circuit the empty bitmap cases. */
430 if (src->numwords == 0 || dst->numwords == 0)
431 {
432 ebitmap_clear (dst);
433 return;
434 }
435
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);
439
440 EXECUTE_IF_SET_IN_SBITMAP (dst->wordmask, 0, i, sbi)
441 {
442 EBITMAP_ELT_TYPE tmpword = ebitmap_array_get (src, srceltindex++);
443 tmpword &= ebitmap_array_get (dst, dsteltindex++);
444 if (tmpword != 0)
445 {
446 EBITMAP_ELT_TYPE *dstplace;
447 dstplace = ebitmap_array_grow_get (dst, neweltindex++);
448 *dstplace = tmpword;
449 }
450 else
451 RESET_BIT (dst->wordmask, i);
452 }
453 #ifdef EBITMAP_DEBUGGING
454 {
455 unsigned int i;
456
457 for (i = 0; i < dst->numwords; i++)
458 gcc_assert (dst->elts[i] != 0);
459
460 verify_popcount (dst->wordmask);
461 gcc_assert (sbitmap_popcount (dst->wordmask,
462 dst->wordmask->n_bits) == dst->numwords);
463 }
464 #endif
465 dst->numwords = neweltindex;
466 }
467
468 /* Perform the operation DST = SRC1 & SRC2. */
469
470 void
471 ebitmap_and (ebitmap dst, ebitmap src1, ebitmap src2)
472 {
473 sbitmap_iterator sbi;
474 unsigned int i;
475 unsigned int neweltindex = 0;
476 unsigned int src1eltindex = 0;
477 unsigned int src2eltindex = 0;
478
479 dst->cache = NULL;
480 if (src1->numwords == 0 || src2->numwords == 0)
481 {
482 ebitmap_clear (dst);
483 return;
484 }
485
486 dst->wordmask
487 = sbitmap_resize (dst->wordmask,
488 MIN (src1->wordmask->n_bits, src2->wordmask->n_bits),
489 0);
490 sbitmap_a_and_b (dst->wordmask, src1->wordmask, src2->wordmask);
491
492 EXECUTE_IF_SET_IN_SBITMAP (dst->wordmask, 0, i, sbi)
493 {
494 bool src1hasword, src2hasword;
495
496 src1hasword = TEST_BIT (src1->wordmask, i);
497 src2hasword = TEST_BIT (src2->wordmask, i);
498
499 if (src1hasword && src2hasword)
500 {
501 EBITMAP_ELT_TYPE tmpword = ebitmap_array_get (src1, src1eltindex++);
502 tmpword &= ebitmap_array_get (src2, src2eltindex++);
503 if (tmpword != 0)
504 {
505 EBITMAP_ELT_TYPE *dstplace;
506 dstplace = ebitmap_array_grow_get (dst, neweltindex++);
507 *dstplace = tmpword;
508 }
509 else
510 RESET_BIT (dst->wordmask, i);
511 }
512 else if (src1hasword)
513 src1eltindex++;
514 else
515 src2eltindex++;
516 }
517 #ifdef EBITMAP_DEBUGGING
518 {
519 ebitmap_iterator ebi;
520 unsigned int i;
521
522 for (i = 0; i < dst->numwords; i++)
523 gcc_assert (dst->elts[i] != 0);
524
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));
528
529 for (i = 0; i < dst->numwords; i++)
530 gcc_assert (dst->elts[i] != 0);
531
532 verify_popcount (dst->wordmask);
533 gcc_assert (sbitmap_popcount (dst->wordmask,
534 dst->wordmask->n_bits) == dst->numwords);
535 }
536 #endif
537 dst->numwords = neweltindex;
538 }
539
540 /* Perform the operation DST |= SRC. Return true if any bits in DST
541 changed. */
542
543 bool
544 ebitmap_ior_into (ebitmap dst, ebitmap src)
545 {
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
561
562 dst->cache = NULL;
563 if (dst == src)
564 return false;
565
566 if (dst->numwords == 0 && src->numwords != 0)
567 {
568 ebitmap_copy (dst, src);
569 return true;
570 }
571 else if (src->numwords == 0)
572 return false;
573
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)
579 {
580 sbitmap_a_or_b (tempmask, dst->wordmask, src->wordmask);
581 }
582 else
583 {
584 dst->wordmask = sbitmap_resize (dst->wordmask, MAX (srcsize, dstsize),
585 0);
586 if (srcsize >= dstsize)
587 {
588 sbitmap_copy_n (tempmask, dst->wordmask, dst->wordmask->size);
589 sbitmap_a_or_b (tempmask, tempmask, src->wordmask);
590 }
591 else
592 {
593 sbitmap_copy_n (tempmask, src->wordmask, src->wordmask->size);
594 sbitmap_a_or_b (tempmask, tempmask, dst->wordmask);
595 }
596 }
597 newarraysize = src->numwords + dst->numwords;
598 newarray = XNEWVEC (EBITMAP_ELT_TYPE, newarraysize);
599
600 EXECUTE_IF_SET_IN_SBITMAP (tempmask, 0, i, sbi)
601 {
602 bool dsthasword, srchasword;
603
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));
608
609 if (dsthasword && srchasword)
610 {
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;
617 }
618 else if (dsthasword)
619 {
620 newarray [neweltindex++] = ebitmap_array_get (dst, dsteltindex++);
621 }
622 else
623 {
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;
628 }
629 }
630
631 sbitmap_free (tempmask);
632 if (changed)
633 {
634 dst->numwords = neweltindex;
635 free (dst->elts);
636 dst->elts = newarray;
637 dst->n_elts = newarraysize;
638 }
639 else
640 free (newarray);
641
642 #ifdef EBITMAP_DEBUGGING
643 {
644 ebitmap_iterator ebi;
645 unsigned int i;
646
647 for (i = 0; i < dst->numwords; i++)
648 gcc_assert (dst->elts[i] != 0);
649
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));
654
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);
659 }
660 #endif
661 return changed;
662 }
663
664 /* Perform the operation DST = SRC1 | SRC2. Return true if any bit
665 in DST has changed. */
666
667 bool
668 ebitmap_ior (ebitmap dst, ebitmap src1, ebitmap src2)
669 {
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
685
686 dst->cache = NULL;
687 tempmask = sbitmap_alloc_with_popcount (MAX (src1size, src2size));
688 sbitmap_zero (tempmask);
689 if (src1size == src2size)
690 {
691 sbitmap_a_or_b (tempmask, src1->wordmask, src2->wordmask);
692 }
693 else
694 {
695 if (src1size >= src2size)
696 {
697 sbitmap_copy_n (tempmask, src2->wordmask, src2->wordmask->size);
698 sbitmap_a_or_b (tempmask, tempmask, src1->wordmask);
699 }
700 else
701 {
702 sbitmap_copy_n (tempmask, src1->wordmask, src1->wordmask->size);
703 sbitmap_a_or_b (tempmask, tempmask, src2->wordmask);
704 }
705 }
706 newarraysize = src1->numwords + src2->numwords;
707 newarray = XNEWVEC (EBITMAP_ELT_TYPE, newarraysize);
708
709 EXECUTE_IF_SET_IN_SBITMAP (tempmask, 0, i, sbi)
710 {
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));
717
718 if (src1hasword && src2hasword)
719 {
720 tmpword = (ebitmap_array_get (src1, src1eltindex++)
721 | ebitmap_array_get (src2, src2eltindex++));
722 newarray[neweltindex++] = tmpword;
723 }
724 else if (src1hasword)
725 {
726 tmpword = ebitmap_array_get (src1, src1eltindex++);
727 newarray [neweltindex++] = tmpword;
728 }
729 else
730 {
731 tmpword = ebitmap_array_get (src2, src2eltindex++);
732 newarray [neweltindex++] = tmpword;
733 }
734
735 if (i >= dst->wordmask->n_bits || !TEST_BIT (dst->wordmask, i))
736 {
737 changed = true;
738 }
739 else if (!changed)
740 {
741 unsigned int count = sbitmap_popcount (dst->wordmask, i);
742 changed |= ebitmap_array_get (dst, count) != tmpword;
743 }
744 }
745
746 if (changed)
747 {
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;
754 }
755 else
756 {
757 sbitmap_free (tempmask);
758 free (newarray);
759 }
760
761 #ifdef EBITMAP_DEBUGGING
762 {
763 ebitmap_iterator ebi;
764 unsigned int i;
765
766 for (i = 0; i < dst->numwords; i++)
767 gcc_assert (dst->elts[i] != 0);
768
769 EXECUTE_IF_SET_IN_EBITMAP (src1, 0, i, ebi)
770 gcc_assert (ebitmap_bit_p (dst, i));
771
772 EXECUTE_IF_SET_IN_EBITMAP (src2, 0, i, ebi)
773 gcc_assert (ebitmap_bit_p (dst, i));
774 }
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
780
781 return changed;
782 }
783
784 /* Perform the operation DST &= ~SRC. Return true if any bit in DST
785 has changed. */
786
787 bool
788 ebitmap_and_compl_into (ebitmap dst, ebitmap src)
789 {
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
799
800 gcc_assert (dst != src);
801 dst->cache = NULL;
802 if (src->numwords == 0)
803 return false;
804
805 EXECUTE_IF_SET_IN_SBITMAP (dst->wordmask, 0, i, sbi)
806 {
807 bool srchasword;
808
809 srchasword = (i < src->wordmask->n_bits
810 && TEST_BIT (src->wordmask, i));
811
812 if (srchasword)
813 {
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)
821 {
822 EBITMAP_ELT_TYPE *dstplace;
823 dstplace = ebitmap_array_grow_get (dst, neweltindex++);
824 *dstplace = tmpword;
825 }
826 else
827 RESET_BIT (dst->wordmask, i);
828 }
829 else
830 {
831 dsteltindex++;
832 neweltindex++;
833 }
834 }
835 #ifdef EBITMAP_DEBUGGING
836 {
837 unsigned int i;
838 ebitmap_iterator ebi;
839
840 EXECUTE_IF_SET_IN_EBITMAP (dstcopy, 0, i, ebi)
841 {
842 if (!ebitmap_bit_p (src, i))
843 gcc_assert (ebitmap_bit_p (dst, i));
844 }
845
846 for (i = 0; i < dst->numwords; i++)
847 gcc_assert (dst->elts[i] != 0);
848
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);
855 }
856 #endif
857 dst->numwords = neweltindex;
858 /* sbitmap_popcount (dst->wordmask, -1); */
859
860 return changed;
861 }
862
863 /* Perform the operation DST = SRC1 & ~SRC2. Return true if any bit
864 in DST has changed. */
865
866 bool
867 ebitmap_and_compl (ebitmap dst, ebitmap src1, ebitmap src2)
868 {
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;
878
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);
884
885 newarraysize = src1->numwords;
886 newarray = XNEWVEC (EBITMAP_ELT_TYPE, newarraysize);
887
888 EXECUTE_IF_SET_IN_SBITMAP (src1->wordmask, 0, i, sbi)
889 {
890 bool src2hasword;
891 EBITMAP_ELT_TYPE tmpword;
892
893 src2hasword = (i < src2->wordmask->n_bits
894 && TEST_BIT (src2->wordmask, i));
895
896 if (src2hasword)
897 {
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)
902 {
903 newarray[neweltindex++] = tmpword;
904 }
905 else
906 RESET_BIT (tempmask, i);
907
908 }
909 else
910 {
911 tmpword = ebitmap_array_get (src1, src1eltindex++);
912 gcc_assert (tmpword != 0);
913 newarray[neweltindex++] = tmpword;
914 }
915
916 if (i >= dst->wordmask->n_bits || !TEST_BIT (dst->wordmask, i))
917 {
918 changed = true;
919 }
920 else if (!changed)
921 {
922 unsigned int count = sbitmap_popcount (dst->wordmask, i);
923 changed |= ebitmap_array_get (dst, count) != tmpword;
924 }
925 }
926 if (changed)
927 {
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;
934 }
935 else
936 {
937 free (tempmask);
938 free (newarray);
939 }
940 #ifdef EBITMAP_DEBUGGING
941 {
942 unsigned int i;
943 ebitmap_iterator ebi;
944
945 EXECUTE_IF_SET_IN_EBITMAP (src1, 0, i, ebi)
946 {
947 if (!ebitmap_bit_p (src2, i))
948 gcc_assert (ebitmap_bit_p (dst, i));
949 }
950 for (i = 0; i < dst->numwords; i++)
951 gcc_assert (dst->elts[i] != 0);
952
953 verify_popcount (dst->wordmask);
954 gcc_assert (sbitmap_popcount (dst->wordmask,
955 dst->wordmask->n_bits) == dst->numwords);
956 }
957 #endif
958 return changed;
959 }
960
961 /* Perform the operation DST = A | (B & ~C). */
962
963 bool
964 ebitmap_ior_and_compl (ebitmap dst, ebitmap a, ebitmap b, ebitmap c)
965 {
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
972
973 dst->cache = NULL;
974 ebitmap_and_compl (temp, b, c);
975 changed = ebitmap_ior (dst, a, temp);
976 #ifdef EBITMAP_DEBUGGING
977 {
978 ebitmap_iterator ebi;
979 unsigned int i;
980
981 EXECUTE_IF_SET_IN_EBITMAP (a, 0, i, ebi)
982 gcc_assert (ebitmap_bit_p (dst, i));
983
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));
988 }
989 #endif
990 ebitmap_free (temp);
991
992 return changed;
993 }
994
995 /* Return true if ebitmap DST is equal to ebitmap SRC. */
996
997 bool
998 ebitmap_equal_p (ebitmap dst, ebitmap src)
999 {
1000 unsigned int which = MIN (dst->wordmask->size, src->wordmask->size);
1001
1002 if (dst->numwords != src->numwords)
1003 return false;
1004
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;
1014
1015 return memcmp (dst->elts, src->elts,
1016 dst->numwords * sizeof (EBITMAP_ELT_TYPE)) == 0;
1017 return true;
1018 }