OSDN Git Service

2010-02-25 Nicolas Benoit <nbenoit@tuxfamily.org>
[pf3gnuchains/gcc-fork.git] / gcc / ebitmap.c
1 /* Sparse array-based bitmaps.
2    Copyright (C) 2007, 2008, 2009, 2010 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)
258         {
259           if (map->cacheindex == wordindex)
260             map->cache = NULL;
261           else if (map->cacheindex > wordindex)
262             map->cache = map->cache - 1;
263         }
264
265       RESET_BIT (map->wordmask, wordindex);
266
267       memmove(&map->elts[eltwordindex], &map->elts[eltwordindex + 1],
268               sizeof (EBITMAP_ELT_TYPE) * (map->numwords - eltwordindex));
269       map->numwords--;
270     }
271 }
272
273 /* Set BIT in ebitmap MAP.  */
274
275 void
276 ebitmap_set_bit (ebitmap map, unsigned int bit)
277 {
278   unsigned int wordindex = bit / EBITMAP_ELT_BITS;
279   unsigned int eltwordindex;
280   unsigned int bitindex =   bit % EBITMAP_ELT_BITS;
281
282   /* If we have this element cached, just set the bit in it.  */
283   if (map->cache && map->cacheindex == wordindex)
284     {
285       (*map->cache) |= (EBITMAP_ELT_TYPE)1 << bitindex;
286       return;
287     }
288
289   /* Resize the wordmask if necessary.  */
290   if (wordindex >= map->wordmask->n_bits)
291     map->wordmask = sbitmap_resize (map->wordmask, wordindex + 1, 0);
292
293   /* Allocate a new word in the array and move whatever is in it's
294      place, if necessary. */
295   if (!TEST_BIT (map->wordmask, wordindex))
296     {
297       unsigned long count;
298       unsigned int i;
299
300       SET_BIT (map->wordmask, wordindex);
301       count = sbitmap_popcount (map->wordmask, wordindex);
302       gcc_assert (count <= map->numwords);
303
304       for (i = map->numwords; i > count; i--)
305         {
306           EBITMAP_ELT_TYPE *newelt;
307           newelt = ebitmap_array_grow_get (map, i);
308           *newelt = ebitmap_array_get (map, i - 1);
309         }
310       map->numwords++;
311       eltwordindex = count;
312       ebitmap_array_maybe_grow (map, eltwordindex);
313       map->elts[eltwordindex] = 0;
314     }
315   else
316     {
317       eltwordindex = sbitmap_popcount (map->wordmask, wordindex);
318     }
319
320   /* Set the actual bit.  */
321   bitindex = bit % EBITMAP_ELT_BITS;
322
323   map->elts[eltwordindex] |= (EBITMAP_ELT_TYPE)1 << bitindex;
324   map->cache = &map->elts[eltwordindex];
325   map->cacheindex = wordindex;
326 }
327
328
329 /* Return true if MAP contains BIT.  */
330
331 bool
332 ebitmap_bit_p (ebitmap map, unsigned int bit)
333 {
334   unsigned int wordindex = bit / EBITMAP_ELT_BITS;
335   unsigned int bitindex= bit % EBITMAP_ELT_BITS;
336
337   /* Trivial empty ebitmap case.  */
338   if (map->numwords == 0)
339     return false;
340
341   if (map->cache && map->cacheindex == wordindex)
342     return ((*map->cache) >> bitindex) & 1;
343
344   /* If the wordindex is greater than the size of the wordmask, *or*
345      it's not set in the wordmask, this bit can't exist in our
346      ebitmap.  */
347   if (wordindex >= map->wordmask->n_bits
348       || !TEST_BIT (map->wordmask, wordindex))
349     return false;
350
351   /* Find the bit and test it.  */
352   map->cacheindex = wordindex;
353   wordindex = sbitmap_popcount (map->wordmask, wordindex);
354   map->cache = &map->elts[wordindex];
355
356   return (map->elts[wordindex] >> bitindex) & 1;
357 }
358
359 /* Copy ebitmap SRC to DST.  */
360
361 void
362 ebitmap_copy (ebitmap dst, ebitmap src)
363 {
364   /* Blow away any existing wordmask, and copy the new one.  */
365   sbitmap_free (dst->wordmask);
366   dst->wordmask = sbitmap_alloc_with_popcount (src->wordmask->n_bits);
367   sbitmap_copy (dst->wordmask, src->wordmask);
368
369   /* Make sure our destination array is big enough, and then copy the
370      actual words.  */
371   ebitmap_array_grow (dst, src->numwords);
372   memcpy (dst->elts, src->elts,
373           src->numwords * sizeof (EBITMAP_ELT_TYPE));
374   dst->numwords = src->numwords;
375   dst->cache = NULL;
376 }
377
378 /* Dump ebitmap BMAP to FILE.  */
379
380 void
381 dump_ebitmap (FILE *file, ebitmap bmap)
382 {
383   unsigned int pos;
384   unsigned int i;
385   int res;
386   unsigned int size;
387
388   res = sbitmap_last_set_bit (bmap->wordmask);
389   if (res == -1)
390     size = 0;
391   else
392     size = (res + 1) * EBITMAP_ELT_BITS;
393
394   fprintf (file, "n_words = %d, set = {", bmap->numwords);
395
396   for (pos = 30, i = 0; i < size; i++)
397     if (ebitmap_bit_p (bmap, i))
398       {
399         if (pos > 70)
400           {
401             fprintf (file, "\n  ");
402             pos = 0;
403           }
404
405         pos += fprintf (file, "%d ", i);
406       }
407
408   fprintf (file, "}\n");
409 }
410
411 /* Dump ebitmap BMAP to stderr.  */
412
413 void
414 debug_ebitmap (ebitmap bmap)
415 {
416   dump_ebitmap (stderr, bmap);
417 }
418
419 /* Perform the operation DST &= SRC.  */
420
421 void
422 ebitmap_and_into (ebitmap dst, ebitmap src)
423 {
424   sbitmap_iterator sbi;
425   unsigned int i;
426   unsigned int neweltindex = 0;
427   unsigned int dsteltindex = 0;
428   unsigned int srceltindex = 0;
429
430   gcc_assert (dst != src);
431
432   dst->cache = NULL;
433
434   /* Short circuit the empty bitmap cases.  */
435   if (src->numwords == 0 || dst->numwords == 0)
436     {
437       ebitmap_clear (dst);
438       return;
439     }
440
441   /* AND the masks, then walk the words that may actually appear in
442      the result, AND'ing them.  */
443   sbitmap_a_and_b (dst->wordmask, dst->wordmask, src->wordmask);
444
445   EXECUTE_IF_SET_IN_SBITMAP (dst->wordmask, 0, i, sbi)
446     {
447       EBITMAP_ELT_TYPE tmpword = ebitmap_array_get (src, srceltindex++);
448       tmpword &= ebitmap_array_get (dst, dsteltindex++);
449       if (tmpword != 0)
450         {
451           EBITMAP_ELT_TYPE *dstplace;
452           dstplace = ebitmap_array_grow_get (dst, neweltindex++);
453           *dstplace = tmpword;
454         }
455       else
456         RESET_BIT (dst->wordmask, i);
457     }
458 #ifdef EBITMAP_DEBUGGING
459   {
460     unsigned int i;
461
462     for (i = 0; i <  dst->numwords; i++)
463       gcc_assert (dst->elts[i] != 0);
464
465     sbitmap_verify_popcount (dst->wordmask);
466     gcc_assert (sbitmap_popcount (dst->wordmask,
467                                   dst->wordmask->n_bits) == dst->numwords);
468   }
469 #endif
470   dst->numwords = neweltindex;
471 }
472
473 /* Perform the operation DST = SRC1 & SRC2.  */
474
475 void
476 ebitmap_and (ebitmap dst, ebitmap src1, ebitmap src2)
477 {
478   sbitmap_iterator sbi;
479   unsigned int i;
480   unsigned int neweltindex = 0;
481   unsigned int src1eltindex = 0;
482   unsigned int src2eltindex = 0;
483
484   dst->cache = NULL;
485   if (src1->numwords == 0 || src2->numwords == 0)
486     {
487       ebitmap_clear (dst);
488       return;
489     }
490
491   dst->wordmask
492     = sbitmap_resize (dst->wordmask,
493                       MIN (src1->wordmask->n_bits, src2->wordmask->n_bits),
494                       0);
495   sbitmap_a_and_b (dst->wordmask, src1->wordmask, src2->wordmask);
496
497   EXECUTE_IF_SET_IN_SBITMAP (dst->wordmask, 0, i, sbi)
498     {
499       bool src1hasword, src2hasword;
500
501       src1hasword = TEST_BIT (src1->wordmask, i);
502       src2hasword = TEST_BIT (src2->wordmask, i);
503
504       if (src1hasword && src2hasword)
505         {
506           EBITMAP_ELT_TYPE tmpword = ebitmap_array_get (src1, src1eltindex++);
507           tmpword &= ebitmap_array_get (src2, src2eltindex++);
508           if (tmpword != 0)
509             {
510               EBITMAP_ELT_TYPE *dstplace;
511               dstplace = ebitmap_array_grow_get (dst, neweltindex++);
512               *dstplace = tmpword;
513             }
514           else
515             RESET_BIT (dst->wordmask, i);
516         }
517       else if (src1hasword)
518         src1eltindex++;
519       else
520         src2eltindex++;
521     }
522 #ifdef EBITMAP_DEBUGGING
523   {
524     ebitmap_iterator ebi;
525     unsigned int i;
526
527     for (i = 0; i <  dst->numwords; i++)
528       gcc_assert (dst->elts[i] != 0);
529
530     EXECUTE_IF_SET_IN_EBITMAP (src1, 0, i, ebi)
531       if (ebitmap_bit_p (src2, i))
532         gcc_assert (ebitmap_bit_p (dst, i));
533
534     for (i = 0; i <  dst->numwords; i++)
535       gcc_assert (dst->elts[i] != 0);
536
537     sbitmap_verify_popcount (dst->wordmask);
538     gcc_assert (sbitmap_popcount (dst->wordmask,
539                                   dst->wordmask->n_bits) == dst->numwords);
540   }
541 #endif
542   dst->numwords = neweltindex;
543 }
544
545 /* Perform the operation DST |= SRC.  Return true if any bits in DST
546    changed.  */
547
548 bool
549 ebitmap_ior_into (ebitmap dst, ebitmap src)
550 {
551   unsigned int dstsize = dst->wordmask->n_bits;
552   unsigned int srcsize = src->wordmask->n_bits;
553   sbitmap_iterator sbi;
554   unsigned int i;
555   sbitmap tempmask;
556   unsigned int neweltindex = 0;
557   unsigned int dsteltindex = 0;
558   unsigned int srceltindex = 0;
559   bool changed = false;
560   EBITMAP_ELT_TYPE *newarray;
561   unsigned int newarraysize;
562 #ifdef EBITMAP_DEBUGGING
563   ebitmap dstcopy = ebitmap_alloc (1);
564   ebitmap_copy (dstcopy, dst);
565 #endif
566
567   dst->cache = NULL;
568   if (dst == src)
569     return false;
570
571   if (dst->numwords == 0 && src->numwords != 0)
572     {
573       ebitmap_copy (dst, src);
574       return true;
575     }
576   else if (src->numwords == 0)
577     return false;
578
579   /* We can do without the temp mask if it's faster, but it would mean
580      touching more words in the actual dense vector.  */
581   tempmask = sbitmap_alloc (MAX (srcsize, dstsize));
582   sbitmap_zero (tempmask);
583   if (srcsize == dstsize)
584     {
585       sbitmap_a_or_b (tempmask, dst->wordmask, src->wordmask);
586     }
587   else
588     {
589       dst->wordmask = sbitmap_resize (dst->wordmask, MAX (srcsize, dstsize),
590                                       0);
591       if (srcsize >= dstsize)
592         {
593           sbitmap_copy_n (tempmask, dst->wordmask, dst->wordmask->size);
594           sbitmap_a_or_b (tempmask, tempmask, src->wordmask);
595         }
596       else
597         {
598           sbitmap_copy_n (tempmask, src->wordmask, src->wordmask->size);
599           sbitmap_a_or_b (tempmask, tempmask, dst->wordmask);
600         }
601     }
602   newarraysize = src->numwords + dst->numwords;
603   newarray = XNEWVEC (EBITMAP_ELT_TYPE, newarraysize);
604
605   EXECUTE_IF_SET_IN_SBITMAP (tempmask, 0, i, sbi)
606     {
607       bool dsthasword, srchasword;
608
609       dsthasword = (i < dst->wordmask->n_bits
610                     && TEST_BIT (dst->wordmask, i));
611       srchasword = (i < src->wordmask->n_bits
612                     && TEST_BIT (src->wordmask, i));
613
614       if (dsthasword && srchasword)
615         {
616           EBITMAP_ELT_TYPE tmpword = ebitmap_array_get (src, srceltindex++);
617           tmpword |= ebitmap_array_get (dst, dsteltindex);
618           if (!changed)
619             changed |= tmpword != ebitmap_array_get (dst, dsteltindex);
620           dsteltindex++;
621           newarray[neweltindex++] = tmpword;
622         }
623       else if (dsthasword)
624         {
625           newarray [neweltindex++] = ebitmap_array_get (dst, dsteltindex++);
626         }
627       else
628         {
629           newarray [neweltindex++] = ebitmap_array_get (src, srceltindex++);
630           gcc_assert (i < dst->wordmask->n_bits);
631           SET_BIT (dst->wordmask, i);
632           changed |= true;
633         }
634     }
635
636   sbitmap_free (tempmask);
637   if (changed)
638     {
639       dst->numwords = neweltindex;
640       free (dst->elts);
641       dst->elts = newarray;
642       dst->n_elts = newarraysize;
643     }
644   else
645     free (newarray);
646
647 #ifdef EBITMAP_DEBUGGING
648   {
649     ebitmap_iterator ebi;
650     unsigned int i;
651
652     for (i = 0; i <  dst->numwords; i++)
653       gcc_assert (dst->elts[i] != 0);
654
655     EXECUTE_IF_SET_IN_EBITMAP (src, 0, i, ebi)
656       gcc_assert (ebitmap_bit_p (dst, i));
657     EXECUTE_IF_SET_IN_EBITMAP (dstcopy, 0, i, ebi)
658       gcc_assert (ebitmap_bit_p (dst, i));
659
660     sbitmap_verify_popcount (dst->wordmask);
661     gcc_assert (changed == !ebitmap_equal_p (dst, dstcopy));
662     gcc_assert (sbitmap_popcount (dst->wordmask,
663                                   dst->wordmask->n_bits) == dst->numwords);
664   }
665 #endif
666   return changed;
667 }
668
669 /* Perform the operation DST = SRC1 | SRC2.  Return true if any bit
670    in DST has changed.  */
671
672 bool
673 ebitmap_ior (ebitmap dst, ebitmap src1, ebitmap src2)
674 {
675   unsigned int src1size = src1->wordmask->n_bits;
676   unsigned int src2size = src2->wordmask->n_bits;
677   sbitmap_iterator sbi;
678   unsigned int i;
679   sbitmap tempmask;
680   unsigned int neweltindex = 0;
681   unsigned int src1eltindex = 0;
682   unsigned int src2eltindex = 0;
683   bool changed = false;
684   EBITMAP_ELT_TYPE *newarray;
685   unsigned int newarraysize;
686 #ifdef EBITMAP_DEBUGGING
687   ebitmap dstcopy = ebitmap_alloc (1);
688   ebitmap_copy (dstcopy, dst);
689 #endif
690
691   dst->cache = NULL;
692   tempmask = sbitmap_alloc_with_popcount (MAX (src1size, src2size));
693   sbitmap_zero (tempmask);
694   if (src1size == src2size)
695     {
696       sbitmap_a_or_b (tempmask, src1->wordmask, src2->wordmask);
697     }
698   else
699     {
700       if (src1size >= src2size)
701         {
702           sbitmap_copy_n (tempmask, src2->wordmask, src2->wordmask->size);
703           sbitmap_a_or_b (tempmask, tempmask, src1->wordmask);
704         }
705       else
706         {
707           sbitmap_copy_n (tempmask, src1->wordmask, src1->wordmask->size);
708           sbitmap_a_or_b (tempmask, tempmask, src2->wordmask);
709         }
710     }
711   newarraysize = src1->numwords + src2->numwords;
712   newarray = XNEWVEC (EBITMAP_ELT_TYPE, newarraysize);
713
714   EXECUTE_IF_SET_IN_SBITMAP (tempmask, 0, i, sbi)
715     {
716       bool src1hasword, src2hasword;
717       EBITMAP_ELT_TYPE tmpword;
718       src1hasword = (i < src1->wordmask->n_bits
719                     && TEST_BIT (src1->wordmask, i));
720       src2hasword = (i < src2->wordmask->n_bits
721                     && TEST_BIT (src2->wordmask, i));
722
723       if (src1hasword && src2hasword)
724         {
725           tmpword = (ebitmap_array_get (src1, src1eltindex++)
726                      | ebitmap_array_get (src2, src2eltindex++));
727           newarray[neweltindex++] = tmpword;
728         }
729       else if (src1hasword)
730         {
731           tmpword = ebitmap_array_get (src1, src1eltindex++);
732           newarray [neweltindex++] = tmpword;
733         }
734       else
735         {
736           tmpword = ebitmap_array_get (src2, src2eltindex++);
737           newarray [neweltindex++] = tmpword;
738         }
739
740       if (i >= dst->wordmask->n_bits || !TEST_BIT (dst->wordmask, i))
741         {
742           changed = true;
743         }
744       else if (!changed)
745         {
746           unsigned int count = sbitmap_popcount (dst->wordmask, i);
747           changed |= ebitmap_array_get (dst, count) != tmpword;
748         }
749     }
750
751   if (changed)
752     {
753       sbitmap_free (dst->wordmask);
754       dst->wordmask = tempmask;
755       dst->numwords = neweltindex;
756       free (dst->elts);
757       dst->elts = newarray;
758       dst->n_elts = newarraysize;
759     }
760   else
761     {
762       sbitmap_free (tempmask);
763       free (newarray);
764     }
765
766 #ifdef EBITMAP_DEBUGGING
767   {
768     ebitmap_iterator ebi;
769     unsigned int i;
770
771     for (i = 0; i <  dst->numwords; i++)
772       gcc_assert (dst->elts[i] != 0);
773
774     EXECUTE_IF_SET_IN_EBITMAP (src1, 0, i, ebi)
775       gcc_assert (ebitmap_bit_p (dst, i));
776
777     EXECUTE_IF_SET_IN_EBITMAP (src2, 0, i, ebi)
778       gcc_assert (ebitmap_bit_p (dst, i));
779   }
780   sbitmap_verify_popcount (dst->wordmask);
781   gcc_assert (changed == !ebitmap_equal_p (dst, dstcopy));
782   gcc_assert (sbitmap_popcount (dst->wordmask,
783                                 dst->wordmask->n_bits) == dst->numwords);
784 #endif
785
786   return changed;
787 }
788
789 /* Perform the operation DST &= ~SRC.  Return true if any bit in DST
790    has changed.  */
791
792 bool
793 ebitmap_and_compl_into (ebitmap dst, ebitmap src)
794 {
795   bool changed = false;
796   unsigned int i;
797   unsigned int neweltindex = 0;
798   unsigned int dsteltindex = 0;
799   sbitmap_iterator sbi;
800 #ifdef EBITMAP_DEBUGGING
801   ebitmap dstcopy = ebitmap_alloc (1);
802   ebitmap_copy (dstcopy, dst);
803 #endif
804
805   gcc_assert (dst != src);
806   dst->cache = NULL;
807   if (src->numwords == 0)
808     return false;
809
810   EXECUTE_IF_SET_IN_SBITMAP (dst->wordmask, 0, i, sbi)
811     {
812       bool srchasword;
813
814       srchasword = (i < src->wordmask->n_bits
815                     && TEST_BIT (src->wordmask, i));
816
817       if (srchasword)
818         {
819           unsigned int srccount = sbitmap_popcount (src->wordmask, i);
820           EBITMAP_ELT_TYPE tmpword = ebitmap_array_get (dst, dsteltindex);
821           tmpword &= ~(ebitmap_array_get (src, srccount));
822           if (!changed)
823             changed |= ebitmap_array_get (dst, dsteltindex) != tmpword;
824           dsteltindex++;
825           if (tmpword != 0)
826             {
827               EBITMAP_ELT_TYPE *dstplace;
828               dstplace = ebitmap_array_grow_get (dst, neweltindex++);
829               *dstplace = tmpword;
830             }
831           else
832             RESET_BIT (dst->wordmask, i);
833         }
834       else
835         {
836           dsteltindex++;
837           neweltindex++;
838         }
839     }
840 #ifdef EBITMAP_DEBUGGING
841   {
842     unsigned int i;
843     ebitmap_iterator ebi;
844
845     EXECUTE_IF_SET_IN_EBITMAP (dstcopy, 0, i, ebi)
846       {
847         if (!ebitmap_bit_p (src, i))
848           gcc_assert (ebitmap_bit_p (dst, i));
849       }
850
851     for (i = 0; i <  dst->numwords; i++)
852       gcc_assert (dst->elts[i] != 0);
853
854     gcc_assert (sbitmap_popcount (dst->wordmask,
855                                   dst->wordmask->n_bits) == neweltindex);
856     sbitmap_verify_popcount (dst->wordmask);
857     gcc_assert (changed == !ebitmap_equal_p (dst, dstcopy));
858     gcc_assert (sbitmap_popcount (dst->wordmask,
859                                   dst->wordmask->n_bits) == dst->numwords);
860   }
861 #endif
862   dst->numwords = neweltindex;
863   /* sbitmap_popcount (dst->wordmask, -1); */
864
865   return changed;
866 }
867
868 /* Perform the operation DST = SRC1 & ~SRC2.  Return true if any bit
869    in DST has changed.  */
870
871 bool
872 ebitmap_and_compl (ebitmap dst, ebitmap src1, ebitmap src2)
873 {
874   unsigned int src1size = src1->wordmask->n_bits;
875   sbitmap_iterator sbi;
876   unsigned int i;
877   sbitmap tempmask;
878   unsigned int neweltindex = 0;
879   unsigned int src1eltindex = 0;
880   bool changed = false;
881   EBITMAP_ELT_TYPE *newarray;
882   unsigned int newarraysize;
883
884   /* XXX: Optimize like the into version.  */
885   dst->cache = NULL;
886   tempmask = sbitmap_alloc_with_popcount (src1size);
887   sbitmap_zero (tempmask);
888   sbitmap_copy (tempmask, src1->wordmask);
889
890   newarraysize = src1->numwords;
891   newarray = XNEWVEC (EBITMAP_ELT_TYPE, newarraysize);
892
893   EXECUTE_IF_SET_IN_SBITMAP (src1->wordmask, 0, i, sbi)
894     {
895       bool src2hasword;
896       EBITMAP_ELT_TYPE tmpword;
897
898       src2hasword = (i < src2->wordmask->n_bits
899                      && TEST_BIT (src2->wordmask, i));
900
901       if (src2hasword)
902         {
903           unsigned int src2count = sbitmap_popcount (src2->wordmask, i);
904           tmpword = ebitmap_array_get (src1, src1eltindex++)
905                     & ~(ebitmap_array_get (src2, src2count));
906           if (tmpword)
907             {
908               newarray[neweltindex++] = tmpword;
909             }
910           else
911             RESET_BIT (tempmask, i);
912
913         }
914       else
915         {
916           tmpword = ebitmap_array_get (src1, src1eltindex++);
917           gcc_assert (tmpword != 0);
918           newarray[neweltindex++] = tmpword;
919         }
920
921       if (i >= dst->wordmask->n_bits || !TEST_BIT (dst->wordmask, i))
922         {
923           changed = true;
924         }
925       else if (!changed)
926         {
927           unsigned int count = sbitmap_popcount (dst->wordmask, i);
928           changed |= ebitmap_array_get (dst, count) != tmpword;
929         }
930     }
931   if (changed)
932     {
933       sbitmap_free (dst->wordmask);
934       dst->wordmask = tempmask;
935       dst->numwords = neweltindex;
936       free (dst->elts);
937       dst->elts = newarray;
938       dst->n_elts = newarraysize;
939     }
940   else
941     {
942       free (tempmask);
943       free (newarray);
944     }
945 #ifdef EBITMAP_DEBUGGING
946   {
947     unsigned int i;
948     ebitmap_iterator ebi;
949
950     EXECUTE_IF_SET_IN_EBITMAP (src1, 0, i, ebi)
951       {
952         if (!ebitmap_bit_p (src2, i))
953           gcc_assert (ebitmap_bit_p (dst, i));
954       }
955   for (i = 0; i <  dst->numwords; i++)
956     gcc_assert (dst->elts[i] != 0);
957
958   sbitmap_verify_popcount (dst->wordmask);
959   gcc_assert (sbitmap_popcount (dst->wordmask,
960                                 dst->wordmask->n_bits) == dst->numwords);
961   }
962 #endif
963   return changed;
964 }
965
966 /* Perform the operation DST = A | (B & ~C).  */
967
968 bool
969 ebitmap_ior_and_compl (ebitmap dst, ebitmap a, ebitmap b, ebitmap c)
970 {
971   bool changed;
972   ebitmap temp = ebitmap_alloc (1);
973 #ifdef EBITMAP_DEBUGGING
974   ebitmap dstcopy = ebitmap_alloc (1);
975   ebitmap_copy (dstcopy, dst);
976 #endif
977
978   dst->cache = NULL;
979   ebitmap_and_compl (temp, b, c);
980   changed = ebitmap_ior (dst, a, temp);
981 #ifdef EBITMAP_DEBUGGING
982   {
983     ebitmap_iterator ebi;
984     unsigned int i;
985
986     EXECUTE_IF_SET_IN_EBITMAP (a, 0, i, ebi)
987       gcc_assert (ebitmap_bit_p (dst, i));
988
989     EXECUTE_IF_SET_IN_EBITMAP (b, 0, i, ebi)
990       if (!ebitmap_bit_p (c, i))
991         gcc_assert (ebitmap_bit_p (dst, i));
992     gcc_assert (changed == !ebitmap_equal_p (dst, dstcopy));
993   }
994 #endif
995   ebitmap_free (temp);
996
997   return changed;
998 }
999
1000 /* Return true if ebitmap DST is equal to ebitmap SRC.  */
1001
1002 bool
1003 ebitmap_equal_p (ebitmap dst, ebitmap src)
1004 {
1005   unsigned int which = MIN (dst->wordmask->size, src->wordmask->size);
1006
1007   if (dst->numwords != src->numwords)
1008     return false;
1009
1010   /* sbitmap_equal compares up to the size of the first argument, so
1011      if the two sbitmaps are not equally sized, we need to pass the
1012      smaller one as the first argument, or it will crash.  */
1013   if (which == dst->wordmask->size
1014       && !sbitmap_equal (dst->wordmask, src->wordmask))
1015     return false;
1016   else if (which == src->wordmask->size
1017            && !sbitmap_equal (src->wordmask, dst->wordmask))
1018     return false;
1019
1020   return memcmp (dst->elts, src->elts,
1021                  dst->numwords * sizeof (EBITMAP_ELT_TYPE)) == 0;
1022   return true;
1023 }