OSDN Git Service

472ff2e57ae7d003b90db93fc8d8eb9cb1a196e2
[pf3gnuchains/gcc-fork.git] / gcc / ebitmap.c
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 }