Daily bump.
[official-gcc.git] / gcc / bitmap.c
blobbafb4cc91c9d11f63373ce39c77e582721b74a74
1 /* Functions to support general ended bitmaps.
2 Copyright (C) 1997-2015 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
9 version.
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 for more details.
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 #include "config.h"
21 #include "system.h"
22 #include "coretypes.h"
23 #include "obstack.h"
24 #include "bitmap.h"
26 /* Memory allocation statistics purpose instance. */
27 mem_alloc_description<bitmap_usage> bitmap_mem_desc;
29 /* Register new bitmap. */
30 void
31 bitmap_register (bitmap b MEM_STAT_DECL)
33 bitmap_mem_desc.register_descriptor (b, BITMAP_ORIGIN, false
34 FINAL_PASS_MEM_STAT);
37 /* Account the overhead. */
38 static void
39 register_overhead (bitmap b, int amount)
41 if (bitmap_mem_desc.contains_descriptor_for_instance (b))
42 bitmap_mem_desc.register_instance_overhead (amount, b);
45 /* Global data */
46 bitmap_element bitmap_zero_bits; /* An element of all zero bits. */
47 bitmap_obstack bitmap_default_obstack; /* The default bitmap obstack. */
48 static int bitmap_default_obstack_depth;
49 static GTY((deletable)) bitmap_element *bitmap_ggc_free; /* Freelist of
50 GC'd elements. */
52 static void bitmap_elem_to_freelist (bitmap, bitmap_element *);
53 static void bitmap_element_free (bitmap, bitmap_element *);
54 static bitmap_element *bitmap_element_allocate (bitmap);
55 static int bitmap_element_zerop (const bitmap_element *);
56 static void bitmap_element_link (bitmap, bitmap_element *);
57 static bitmap_element *bitmap_elt_insert_after (bitmap, bitmap_element *, unsigned int);
58 static void bitmap_elt_clear_from (bitmap, bitmap_element *);
59 static bitmap_element *bitmap_find_bit (bitmap, unsigned int);
62 /* Add ELEM to the appropriate freelist. */
63 static inline void
64 bitmap_elem_to_freelist (bitmap head, bitmap_element *elt)
66 bitmap_obstack *bit_obstack = head->obstack;
68 elt->next = NULL;
69 if (bit_obstack)
71 elt->prev = bit_obstack->elements;
72 bit_obstack->elements = elt;
74 else
76 elt->prev = bitmap_ggc_free;
77 bitmap_ggc_free = elt;
81 /* Free a bitmap element. Since these are allocated off the
82 bitmap_obstack, "free" actually means "put onto the freelist". */
84 static inline void
85 bitmap_element_free (bitmap head, bitmap_element *elt)
87 bitmap_element *next = elt->next;
88 bitmap_element *prev = elt->prev;
90 if (prev)
91 prev->next = next;
93 if (next)
94 next->prev = prev;
96 if (head->first == elt)
97 head->first = next;
99 /* Since the first thing we try is to insert before current,
100 make current the next entry in preference to the previous. */
101 if (head->current == elt)
103 head->current = next != 0 ? next : prev;
104 if (head->current)
105 head->indx = head->current->indx;
106 else
107 head->indx = 0;
110 if (GATHER_STATISTICS)
111 register_overhead (head, -((int)sizeof (bitmap_element)));
113 bitmap_elem_to_freelist (head, elt);
116 /* Allocate a bitmap element. The bits are cleared, but nothing else is. */
118 static inline bitmap_element *
119 bitmap_element_allocate (bitmap head)
121 bitmap_element *element;
122 bitmap_obstack *bit_obstack = head->obstack;
124 if (bit_obstack)
126 element = bit_obstack->elements;
128 if (element)
129 /* Use up the inner list first before looking at the next
130 element of the outer list. */
131 if (element->next)
133 bit_obstack->elements = element->next;
134 bit_obstack->elements->prev = element->prev;
136 else
137 /* Inner list was just a singleton. */
138 bit_obstack->elements = element->prev;
139 else
140 element = XOBNEW (&bit_obstack->obstack, bitmap_element);
142 else
144 element = bitmap_ggc_free;
145 if (element)
146 /* Use up the inner list first before looking at the next
147 element of the outer list. */
148 if (element->next)
150 bitmap_ggc_free = element->next;
151 bitmap_ggc_free->prev = element->prev;
153 else
154 /* Inner list was just a singleton. */
155 bitmap_ggc_free = element->prev;
156 else
157 element = ggc_alloc<bitmap_element> ();
160 if (GATHER_STATISTICS)
161 register_overhead (head, sizeof (bitmap_element));
163 memset (element->bits, 0, sizeof (element->bits));
165 return element;
168 /* Remove ELT and all following elements from bitmap HEAD. */
170 void
171 bitmap_elt_clear_from (bitmap head, bitmap_element *elt)
173 bitmap_element *prev;
174 bitmap_obstack *bit_obstack = head->obstack;
176 if (!elt) return;
178 if (GATHER_STATISTICS)
180 int n = 0;
181 for (prev = elt; prev; prev = prev->next)
182 n++;
183 register_overhead (head, -sizeof (bitmap_element) * n);
186 prev = elt->prev;
187 if (prev)
189 prev->next = NULL;
190 if (head->current->indx > prev->indx)
192 head->current = prev;
193 head->indx = prev->indx;
196 else
198 head->first = NULL;
199 head->current = NULL;
200 head->indx = 0;
203 /* Put the entire list onto the free list in one operation. */
204 if (bit_obstack)
206 elt->prev = bit_obstack->elements;
207 bit_obstack->elements = elt;
209 else
211 elt->prev = bitmap_ggc_free;
212 bitmap_ggc_free = elt;
216 /* Clear a bitmap by freeing the linked list. */
218 void
219 bitmap_clear (bitmap head)
221 if (head->first)
222 bitmap_elt_clear_from (head, head->first);
225 /* Initialize a bitmap obstack. If BIT_OBSTACK is NULL, initialize
226 the default bitmap obstack. */
228 void
229 bitmap_obstack_initialize (bitmap_obstack *bit_obstack)
231 if (!bit_obstack)
233 if (bitmap_default_obstack_depth++)
234 return;
235 bit_obstack = &bitmap_default_obstack;
238 #if !defined(__GNUC__) || (__GNUC__ < 2)
239 #define __alignof__(type) 0
240 #endif
242 bit_obstack->elements = NULL;
243 bit_obstack->heads = NULL;
244 obstack_specify_allocation (&bit_obstack->obstack, OBSTACK_CHUNK_SIZE,
245 __alignof__ (bitmap_element),
246 obstack_chunk_alloc,
247 obstack_chunk_free);
250 /* Release the memory from a bitmap obstack. If BIT_OBSTACK is NULL,
251 release the default bitmap obstack. */
253 void
254 bitmap_obstack_release (bitmap_obstack *bit_obstack)
256 if (!bit_obstack)
258 if (--bitmap_default_obstack_depth)
260 gcc_assert (bitmap_default_obstack_depth > 0);
261 return;
263 bit_obstack = &bitmap_default_obstack;
266 bit_obstack->elements = NULL;
267 bit_obstack->heads = NULL;
268 obstack_free (&bit_obstack->obstack, NULL);
271 /* Create a new bitmap on an obstack. If BIT_OBSTACK is NULL, create
272 it on the default bitmap obstack. */
274 bitmap
275 bitmap_obstack_alloc_stat (bitmap_obstack *bit_obstack MEM_STAT_DECL)
277 bitmap map;
279 if (!bit_obstack)
280 bit_obstack = &bitmap_default_obstack;
281 map = bit_obstack->heads;
282 if (map)
283 bit_obstack->heads = (struct bitmap_head *) map->first;
284 else
285 map = XOBNEW (&bit_obstack->obstack, bitmap_head);
286 bitmap_initialize_stat (map, bit_obstack PASS_MEM_STAT);
288 if (GATHER_STATISTICS)
289 register_overhead (map, sizeof (bitmap_head));
291 return map;
294 /* Create a new GCd bitmap. */
296 bitmap
297 bitmap_gc_alloc_stat (ALONE_MEM_STAT_DECL)
299 bitmap map;
301 map = ggc_alloc<bitmap_head> ();
302 bitmap_initialize_stat (map, NULL PASS_MEM_STAT);
304 if (GATHER_STATISTICS)
305 register_overhead (map, sizeof (bitmap_head));
307 return map;
310 /* Release an obstack allocated bitmap. */
312 void
313 bitmap_obstack_free (bitmap map)
315 if (map)
317 bitmap_clear (map);
318 map->first = (bitmap_element *) map->obstack->heads;
320 if (GATHER_STATISTICS)
321 register_overhead (map, -((int)sizeof (bitmap_head)));
323 map->obstack->heads = map;
328 /* Return nonzero if all bits in an element are zero. */
330 static inline int
331 bitmap_element_zerop (const bitmap_element *element)
333 #if BITMAP_ELEMENT_WORDS == 2
334 return (element->bits[0] | element->bits[1]) == 0;
335 #else
336 unsigned i;
338 for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
339 if (element->bits[i] != 0)
340 return 0;
342 return 1;
343 #endif
346 /* Link the bitmap element into the current bitmap linked list. */
348 static inline void
349 bitmap_element_link (bitmap head, bitmap_element *element)
351 unsigned int indx = element->indx;
352 bitmap_element *ptr;
354 /* If this is the first and only element, set it in. */
355 if (head->first == 0)
357 element->next = element->prev = 0;
358 head->first = element;
361 /* If this index is less than that of the current element, it goes someplace
362 before the current element. */
363 else if (indx < head->indx)
365 for (ptr = head->current;
366 ptr->prev != 0 && ptr->prev->indx > indx;
367 ptr = ptr->prev)
370 if (ptr->prev)
371 ptr->prev->next = element;
372 else
373 head->first = element;
375 element->prev = ptr->prev;
376 element->next = ptr;
377 ptr->prev = element;
380 /* Otherwise, it must go someplace after the current element. */
381 else
383 for (ptr = head->current;
384 ptr->next != 0 && ptr->next->indx < indx;
385 ptr = ptr->next)
388 if (ptr->next)
389 ptr->next->prev = element;
391 element->next = ptr->next;
392 element->prev = ptr;
393 ptr->next = element;
396 /* Set up so this is the first element searched. */
397 head->current = element;
398 head->indx = indx;
401 /* Insert a new uninitialized element into bitmap HEAD after element
402 ELT. If ELT is NULL, insert the element at the start. Return the
403 new element. */
405 static bitmap_element *
406 bitmap_elt_insert_after (bitmap head, bitmap_element *elt, unsigned int indx)
408 bitmap_element *node = bitmap_element_allocate (head);
409 node->indx = indx;
411 if (!elt)
413 if (!head->current)
415 head->current = node;
416 head->indx = indx;
418 node->next = head->first;
419 if (node->next)
420 node->next->prev = node;
421 head->first = node;
422 node->prev = NULL;
424 else
426 gcc_checking_assert (head->current);
427 node->next = elt->next;
428 if (node->next)
429 node->next->prev = node;
430 elt->next = node;
431 node->prev = elt;
433 return node;
436 /* Copy a bitmap to another bitmap. */
438 void
439 bitmap_copy (bitmap to, const_bitmap from)
441 const bitmap_element *from_ptr;
442 bitmap_element *to_ptr = 0;
444 bitmap_clear (to);
446 /* Copy elements in forward direction one at a time. */
447 for (from_ptr = from->first; from_ptr; from_ptr = from_ptr->next)
449 bitmap_element *to_elt = bitmap_element_allocate (to);
451 to_elt->indx = from_ptr->indx;
452 memcpy (to_elt->bits, from_ptr->bits, sizeof (to_elt->bits));
454 /* Here we have a special case of bitmap_element_link, for the case
455 where we know the links are being entered in sequence. */
456 if (to_ptr == 0)
458 to->first = to->current = to_elt;
459 to->indx = from_ptr->indx;
460 to_elt->next = to_elt->prev = 0;
462 else
464 to_elt->prev = to_ptr;
465 to_elt->next = 0;
466 to_ptr->next = to_elt;
469 to_ptr = to_elt;
473 /* Find a bitmap element that would hold a bitmap's bit.
474 Update the `current' field even if we can't find an element that
475 would hold the bitmap's bit to make eventual allocation
476 faster. */
478 static inline bitmap_element *
479 bitmap_find_bit (bitmap head, unsigned int bit)
481 bitmap_element *element;
482 unsigned int indx = bit / BITMAP_ELEMENT_ALL_BITS;
484 if (head->current == NULL
485 || head->indx == indx)
486 return head->current;
487 if (head->current == head->first
488 && head->first->next == NULL)
489 return NULL;
491 /* Usage can be NULL due to allocated bitmaps for which we do not
492 call initialize function. */
493 bitmap_usage *usage = bitmap_mem_desc.get_descriptor_for_instance (head);
495 /* This bitmap has more than one element, and we're going to look
496 through the elements list. Count that as a search. */
497 if (GATHER_STATISTICS && usage)
498 usage->m_nsearches++;
500 if (head->indx < indx)
501 /* INDX is beyond head->indx. Search from head->current
502 forward. */
503 for (element = head->current;
504 element->next != 0 && element->indx < indx;
505 element = element->next)
507 if (GATHER_STATISTICS && usage)
508 usage->m_search_iter++;
511 else if (head->indx / 2 < indx)
512 /* INDX is less than head->indx and closer to head->indx than to
513 0. Search from head->current backward. */
514 for (element = head->current;
515 element->prev != 0 && element->indx > indx;
516 element = element->prev)
518 if (GATHER_STATISTICS && usage)
519 usage->m_search_iter++;
522 else
523 /* INDX is less than head->indx and closer to 0 than to
524 head->indx. Search from head->first forward. */
525 for (element = head->first;
526 element->next != 0 && element->indx < indx;
527 element = element->next)
528 if (GATHER_STATISTICS && usage)
530 usage->m_search_iter++;
533 /* `element' is the nearest to the one we want. If it's not the one we
534 want, the one we want doesn't exist. */
535 head->current = element;
536 head->indx = element->indx;
537 if (element != 0 && element->indx != indx)
538 element = 0;
540 return element;
543 /* Clear a single bit in a bitmap. Return true if the bit changed. */
545 bool
546 bitmap_clear_bit (bitmap head, int bit)
548 bitmap_element *const ptr = bitmap_find_bit (head, bit);
550 if (ptr != 0)
552 unsigned bit_num = bit % BITMAP_WORD_BITS;
553 unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
554 BITMAP_WORD bit_val = ((BITMAP_WORD) 1) << bit_num;
555 bool res = (ptr->bits[word_num] & bit_val) != 0;
556 if (res)
558 ptr->bits[word_num] &= ~bit_val;
559 /* If we cleared the entire word, free up the element. */
560 if (!ptr->bits[word_num]
561 && bitmap_element_zerop (ptr))
562 bitmap_element_free (head, ptr);
565 return res;
568 return false;
571 /* Set a single bit in a bitmap. Return true if the bit changed. */
573 bool
574 bitmap_set_bit (bitmap head, int bit)
576 bitmap_element *ptr = bitmap_find_bit (head, bit);
577 unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
578 unsigned bit_num = bit % BITMAP_WORD_BITS;
579 BITMAP_WORD bit_val = ((BITMAP_WORD) 1) << bit_num;
581 if (ptr == 0)
583 ptr = bitmap_element_allocate (head);
584 ptr->indx = bit / BITMAP_ELEMENT_ALL_BITS;
585 ptr->bits[word_num] = bit_val;
586 bitmap_element_link (head, ptr);
587 return true;
589 else
591 bool res = (ptr->bits[word_num] & bit_val) == 0;
592 if (res)
593 ptr->bits[word_num] |= bit_val;
594 return res;
598 /* Return whether a bit is set within a bitmap. */
601 bitmap_bit_p (bitmap head, int bit)
603 bitmap_element *ptr;
604 unsigned bit_num;
605 unsigned word_num;
607 ptr = bitmap_find_bit (head, bit);
608 if (ptr == 0)
609 return 0;
611 bit_num = bit % BITMAP_WORD_BITS;
612 word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
614 return (ptr->bits[word_num] >> bit_num) & 1;
617 #if GCC_VERSION < 3400
618 /* Table of number of set bits in a character, indexed by value of char. */
619 static const unsigned char popcount_table[] =
621 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
622 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
623 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
624 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
625 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
626 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
627 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
628 3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
631 static unsigned long
632 bitmap_popcount (BITMAP_WORD a)
634 unsigned long ret = 0;
635 unsigned i;
637 /* Just do this the table way for now */
638 for (i = 0; i < BITMAP_WORD_BITS; i+= 8)
639 ret += popcount_table[(a >> i) & 0xff];
640 return ret;
642 #endif
643 /* Count the number of bits set in the bitmap, and return it. */
645 unsigned long
646 bitmap_count_bits (const_bitmap a)
648 unsigned long count = 0;
649 const bitmap_element *elt;
650 unsigned ix;
652 for (elt = a->first; elt; elt = elt->next)
654 for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
656 #if GCC_VERSION >= 3400
657 /* Note that popcountl matches BITMAP_WORD in type, so the actual size
658 of BITMAP_WORD is not material. */
659 count += __builtin_popcountl (elt->bits[ix]);
660 #else
661 count += bitmap_popcount (elt->bits[ix]);
662 #endif
665 return count;
668 /* Return true if the bitmap has a single bit set. Otherwise return
669 false. */
671 bool
672 bitmap_single_bit_set_p (const_bitmap a)
674 unsigned long count = 0;
675 const bitmap_element *elt;
676 unsigned ix;
678 if (bitmap_empty_p (a))
679 return false;
681 elt = a->first;
682 /* As there are no completely empty bitmap elements, a second one
683 means we have more than one bit set. */
684 if (elt->next != NULL)
685 return false;
687 for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
689 #if GCC_VERSION >= 3400
690 /* Note that popcountl matches BITMAP_WORD in type, so the actual size
691 of BITMAP_WORD is not material. */
692 count += __builtin_popcountl (elt->bits[ix]);
693 #else
694 count += bitmap_popcount (elt->bits[ix]);
695 #endif
696 if (count > 1)
697 return false;
700 return count == 1;
704 /* Return the bit number of the first set bit in the bitmap. The
705 bitmap must be non-empty. */
707 unsigned
708 bitmap_first_set_bit (const_bitmap a)
710 const bitmap_element *elt = a->first;
711 unsigned bit_no;
712 BITMAP_WORD word;
713 unsigned ix;
715 gcc_checking_assert (elt);
716 bit_no = elt->indx * BITMAP_ELEMENT_ALL_BITS;
717 for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
719 word = elt->bits[ix];
720 if (word)
721 goto found_bit;
723 gcc_unreachable ();
724 found_bit:
725 bit_no += ix * BITMAP_WORD_BITS;
727 #if GCC_VERSION >= 3004
728 gcc_assert (sizeof (long) == sizeof (word));
729 bit_no += __builtin_ctzl (word);
730 #else
731 /* Binary search for the first set bit. */
732 #if BITMAP_WORD_BITS > 64
733 #error "Fill out the table."
734 #endif
735 #if BITMAP_WORD_BITS > 32
736 if (!(word & 0xffffffff))
737 word >>= 32, bit_no += 32;
738 #endif
739 if (!(word & 0xffff))
740 word >>= 16, bit_no += 16;
741 if (!(word & 0xff))
742 word >>= 8, bit_no += 8;
743 if (!(word & 0xf))
744 word >>= 4, bit_no += 4;
745 if (!(word & 0x3))
746 word >>= 2, bit_no += 2;
747 if (!(word & 0x1))
748 word >>= 1, bit_no += 1;
750 gcc_checking_assert (word & 1);
751 #endif
752 return bit_no;
755 /* Return the bit number of the first set bit in the bitmap. The
756 bitmap must be non-empty. */
758 unsigned
759 bitmap_last_set_bit (const_bitmap a)
761 const bitmap_element *elt = a->current ? a->current : a->first;
762 unsigned bit_no;
763 BITMAP_WORD word;
764 int ix;
766 gcc_checking_assert (elt);
767 while (elt->next)
768 elt = elt->next;
769 bit_no = elt->indx * BITMAP_ELEMENT_ALL_BITS;
770 for (ix = BITMAP_ELEMENT_WORDS - 1; ix >= 0; ix--)
772 word = elt->bits[ix];
773 if (word)
774 goto found_bit;
776 gcc_unreachable ();
777 found_bit:
778 bit_no += ix * BITMAP_WORD_BITS;
779 #if GCC_VERSION >= 3004
780 gcc_assert (sizeof (long) == sizeof (word));
781 bit_no += BITMAP_WORD_BITS - __builtin_clzl (word) - 1;
782 #else
783 /* Hopefully this is a twos-complement host... */
784 BITMAP_WORD x = word;
785 x |= (x >> 1);
786 x |= (x >> 2);
787 x |= (x >> 4);
788 x |= (x >> 8);
789 x |= (x >> 16);
790 #if BITMAP_WORD_BITS > 32
791 x |= (x >> 32);
792 #endif
793 bit_no += bitmap_popcount (x) - 1;
794 #endif
796 return bit_no;
800 /* DST = A & B. */
802 void
803 bitmap_and (bitmap dst, const_bitmap a, const_bitmap b)
805 bitmap_element *dst_elt = dst->first;
806 const bitmap_element *a_elt = a->first;
807 const bitmap_element *b_elt = b->first;
808 bitmap_element *dst_prev = NULL;
810 gcc_assert (dst != a && dst != b);
812 if (a == b)
814 bitmap_copy (dst, a);
815 return;
818 while (a_elt && b_elt)
820 if (a_elt->indx < b_elt->indx)
821 a_elt = a_elt->next;
822 else if (b_elt->indx < a_elt->indx)
823 b_elt = b_elt->next;
824 else
826 /* Matching elts, generate A & B. */
827 unsigned ix;
828 BITMAP_WORD ior = 0;
830 if (!dst_elt)
831 dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
832 else
833 dst_elt->indx = a_elt->indx;
834 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
836 BITMAP_WORD r = a_elt->bits[ix] & b_elt->bits[ix];
838 dst_elt->bits[ix] = r;
839 ior |= r;
841 if (ior)
843 dst_prev = dst_elt;
844 dst_elt = dst_elt->next;
846 a_elt = a_elt->next;
847 b_elt = b_elt->next;
850 /* Ensure that dst->current is valid. */
851 dst->current = dst->first;
852 bitmap_elt_clear_from (dst, dst_elt);
853 gcc_checking_assert (!dst->current == !dst->first);
854 if (dst->current)
855 dst->indx = dst->current->indx;
858 /* A &= B. Return true if A changed. */
860 bool
861 bitmap_and_into (bitmap a, const_bitmap b)
863 bitmap_element *a_elt = a->first;
864 const bitmap_element *b_elt = b->first;
865 bitmap_element *next;
866 bool changed = false;
868 if (a == b)
869 return false;
871 while (a_elt && b_elt)
873 if (a_elt->indx < b_elt->indx)
875 next = a_elt->next;
876 bitmap_element_free (a, a_elt);
877 a_elt = next;
878 changed = true;
880 else if (b_elt->indx < a_elt->indx)
881 b_elt = b_elt->next;
882 else
884 /* Matching elts, generate A &= B. */
885 unsigned ix;
886 BITMAP_WORD ior = 0;
888 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
890 BITMAP_WORD r = a_elt->bits[ix] & b_elt->bits[ix];
891 if (a_elt->bits[ix] != r)
892 changed = true;
893 a_elt->bits[ix] = r;
894 ior |= r;
896 next = a_elt->next;
897 if (!ior)
898 bitmap_element_free (a, a_elt);
899 a_elt = next;
900 b_elt = b_elt->next;
904 if (a_elt)
906 changed = true;
907 bitmap_elt_clear_from (a, a_elt);
910 gcc_checking_assert (!a->current == !a->first
911 && (!a->current || a->indx == a->current->indx));
913 return changed;
917 /* Insert an element equal to SRC_ELT after DST_PREV, overwriting DST_ELT
918 if non-NULL. CHANGED is true if the destination bitmap had already been
919 changed; the new value of CHANGED is returned. */
921 static inline bool
922 bitmap_elt_copy (bitmap dst, bitmap_element *dst_elt, bitmap_element *dst_prev,
923 const bitmap_element *src_elt, bool changed)
925 if (!changed && dst_elt && dst_elt->indx == src_elt->indx)
927 unsigned ix;
929 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
930 if (src_elt->bits[ix] != dst_elt->bits[ix])
932 dst_elt->bits[ix] = src_elt->bits[ix];
933 changed = true;
936 else
938 changed = true;
939 if (!dst_elt)
940 dst_elt = bitmap_elt_insert_after (dst, dst_prev, src_elt->indx);
941 else
942 dst_elt->indx = src_elt->indx;
943 memcpy (dst_elt->bits, src_elt->bits, sizeof (dst_elt->bits));
945 return changed;
950 /* DST = A & ~B */
952 bool
953 bitmap_and_compl (bitmap dst, const_bitmap a, const_bitmap b)
955 bitmap_element *dst_elt = dst->first;
956 const bitmap_element *a_elt = a->first;
957 const bitmap_element *b_elt = b->first;
958 bitmap_element *dst_prev = NULL;
959 bitmap_element **dst_prev_pnext = &dst->first;
960 bool changed = false;
962 gcc_assert (dst != a && dst != b);
964 if (a == b)
966 changed = !bitmap_empty_p (dst);
967 bitmap_clear (dst);
968 return changed;
971 while (a_elt)
973 while (b_elt && b_elt->indx < a_elt->indx)
974 b_elt = b_elt->next;
976 if (!b_elt || b_elt->indx > a_elt->indx)
978 changed = bitmap_elt_copy (dst, dst_elt, dst_prev, a_elt, changed);
979 dst_prev = *dst_prev_pnext;
980 dst_prev_pnext = &dst_prev->next;
981 dst_elt = *dst_prev_pnext;
982 a_elt = a_elt->next;
985 else
987 /* Matching elts, generate A & ~B. */
988 unsigned ix;
989 BITMAP_WORD ior = 0;
991 if (!changed && dst_elt && dst_elt->indx == a_elt->indx)
993 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
995 BITMAP_WORD r = a_elt->bits[ix] & ~b_elt->bits[ix];
997 if (dst_elt->bits[ix] != r)
999 changed = true;
1000 dst_elt->bits[ix] = r;
1002 ior |= r;
1005 else
1007 bool new_element;
1008 if (!dst_elt || dst_elt->indx > a_elt->indx)
1010 dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
1011 new_element = true;
1013 else
1015 dst_elt->indx = a_elt->indx;
1016 new_element = false;
1019 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1021 BITMAP_WORD r = a_elt->bits[ix] & ~b_elt->bits[ix];
1023 dst_elt->bits[ix] = r;
1024 ior |= r;
1027 if (ior)
1028 changed = true;
1029 else
1031 changed |= !new_element;
1032 bitmap_element_free (dst, dst_elt);
1033 dst_elt = *dst_prev_pnext;
1037 if (ior)
1039 dst_prev = *dst_prev_pnext;
1040 dst_prev_pnext = &dst_prev->next;
1041 dst_elt = *dst_prev_pnext;
1043 a_elt = a_elt->next;
1044 b_elt = b_elt->next;
1048 /* Ensure that dst->current is valid. */
1049 dst->current = dst->first;
1051 if (dst_elt)
1053 changed = true;
1054 bitmap_elt_clear_from (dst, dst_elt);
1056 gcc_checking_assert (!dst->current == !dst->first);
1057 if (dst->current)
1058 dst->indx = dst->current->indx;
1060 return changed;
1063 /* A &= ~B. Returns true if A changes */
1065 bool
1066 bitmap_and_compl_into (bitmap a, const_bitmap b)
1068 bitmap_element *a_elt = a->first;
1069 const bitmap_element *b_elt = b->first;
1070 bitmap_element *next;
1071 BITMAP_WORD changed = 0;
1073 if (a == b)
1075 if (bitmap_empty_p (a))
1076 return false;
1077 else
1079 bitmap_clear (a);
1080 return true;
1084 while (a_elt && b_elt)
1086 if (a_elt->indx < b_elt->indx)
1087 a_elt = a_elt->next;
1088 else if (b_elt->indx < a_elt->indx)
1089 b_elt = b_elt->next;
1090 else
1092 /* Matching elts, generate A &= ~B. */
1093 unsigned ix;
1094 BITMAP_WORD ior = 0;
1096 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1098 BITMAP_WORD cleared = a_elt->bits[ix] & b_elt->bits[ix];
1099 BITMAP_WORD r = a_elt->bits[ix] ^ cleared;
1101 a_elt->bits[ix] = r;
1102 changed |= cleared;
1103 ior |= r;
1105 next = a_elt->next;
1106 if (!ior)
1107 bitmap_element_free (a, a_elt);
1108 a_elt = next;
1109 b_elt = b_elt->next;
1112 gcc_checking_assert (!a->current == !a->first
1113 && (!a->current || a->indx == a->current->indx));
1114 return changed != 0;
1117 /* Set COUNT bits from START in HEAD. */
1118 void
1119 bitmap_set_range (bitmap head, unsigned int start, unsigned int count)
1121 unsigned int first_index, end_bit_plus1, last_index;
1122 bitmap_element *elt, *elt_prev;
1123 unsigned int i;
1125 if (!count)
1126 return;
1128 if (count == 1)
1130 bitmap_set_bit (head, start);
1131 return;
1134 first_index = start / BITMAP_ELEMENT_ALL_BITS;
1135 end_bit_plus1 = start + count;
1136 last_index = (end_bit_plus1 - 1) / BITMAP_ELEMENT_ALL_BITS;
1137 elt = bitmap_find_bit (head, start);
1139 /* If bitmap_find_bit returns zero, the current is the closest block
1140 to the result. Otherwise, just use bitmap_element_allocate to
1141 ensure ELT is set; in the loop below, ELT == NULL means "insert
1142 at the end of the bitmap". */
1143 if (!elt)
1145 elt = bitmap_element_allocate (head);
1146 elt->indx = first_index;
1147 bitmap_element_link (head, elt);
1150 gcc_checking_assert (elt->indx == first_index);
1151 elt_prev = elt->prev;
1152 for (i = first_index; i <= last_index; i++)
1154 unsigned elt_start_bit = i * BITMAP_ELEMENT_ALL_BITS;
1155 unsigned elt_end_bit_plus1 = elt_start_bit + BITMAP_ELEMENT_ALL_BITS;
1157 unsigned int first_word_to_mod;
1158 BITMAP_WORD first_mask;
1159 unsigned int last_word_to_mod;
1160 BITMAP_WORD last_mask;
1161 unsigned int ix;
1163 if (!elt || elt->indx != i)
1164 elt = bitmap_elt_insert_after (head, elt_prev, i);
1166 if (elt_start_bit <= start)
1168 /* The first bit to turn on is somewhere inside this
1169 elt. */
1170 first_word_to_mod = (start - elt_start_bit) / BITMAP_WORD_BITS;
1172 /* This mask should have 1s in all bits >= start position. */
1173 first_mask =
1174 (((BITMAP_WORD) 1) << ((start % BITMAP_WORD_BITS))) - 1;
1175 first_mask = ~first_mask;
1177 else
1179 /* The first bit to turn on is below this start of this elt. */
1180 first_word_to_mod = 0;
1181 first_mask = ~(BITMAP_WORD) 0;
1184 if (elt_end_bit_plus1 <= end_bit_plus1)
1186 /* The last bit to turn on is beyond this elt. */
1187 last_word_to_mod = BITMAP_ELEMENT_WORDS - 1;
1188 last_mask = ~(BITMAP_WORD) 0;
1190 else
1192 /* The last bit to turn on is inside to this elt. */
1193 last_word_to_mod =
1194 (end_bit_plus1 - elt_start_bit) / BITMAP_WORD_BITS;
1196 /* The last mask should have 1s below the end bit. */
1197 last_mask =
1198 (((BITMAP_WORD) 1) << ((end_bit_plus1 % BITMAP_WORD_BITS))) - 1;
1201 if (first_word_to_mod == last_word_to_mod)
1203 BITMAP_WORD mask = first_mask & last_mask;
1204 elt->bits[first_word_to_mod] |= mask;
1206 else
1208 elt->bits[first_word_to_mod] |= first_mask;
1209 if (BITMAP_ELEMENT_WORDS > 2)
1210 for (ix = first_word_to_mod + 1; ix < last_word_to_mod; ix++)
1211 elt->bits[ix] = ~(BITMAP_WORD) 0;
1212 elt->bits[last_word_to_mod] |= last_mask;
1215 elt_prev = elt;
1216 elt = elt->next;
1219 head->current = elt ? elt : elt_prev;
1220 head->indx = head->current->indx;
1223 /* Clear COUNT bits from START in HEAD. */
1224 void
1225 bitmap_clear_range (bitmap head, unsigned int start, unsigned int count)
1227 unsigned int first_index, end_bit_plus1, last_index;
1228 bitmap_element *elt;
1230 if (!count)
1231 return;
1233 if (count == 1)
1235 bitmap_clear_bit (head, start);
1236 return;
1239 first_index = start / BITMAP_ELEMENT_ALL_BITS;
1240 end_bit_plus1 = start + count;
1241 last_index = (end_bit_plus1 - 1) / BITMAP_ELEMENT_ALL_BITS;
1242 elt = bitmap_find_bit (head, start);
1244 /* If bitmap_find_bit returns zero, the current is the closest block
1245 to the result. If the current is less than first index, find the
1246 next one. Otherwise, just set elt to be current. */
1247 if (!elt)
1249 if (head->current)
1251 if (head->indx < first_index)
1253 elt = head->current->next;
1254 if (!elt)
1255 return;
1257 else
1258 elt = head->current;
1260 else
1261 return;
1264 while (elt && (elt->indx <= last_index))
1266 bitmap_element * next_elt = elt->next;
1267 unsigned elt_start_bit = (elt->indx) * BITMAP_ELEMENT_ALL_BITS;
1268 unsigned elt_end_bit_plus1 = elt_start_bit + BITMAP_ELEMENT_ALL_BITS;
1271 if (elt_start_bit >= start && elt_end_bit_plus1 <= end_bit_plus1)
1272 /* Get rid of the entire elt and go to the next one. */
1273 bitmap_element_free (head, elt);
1274 else
1276 /* Going to have to knock out some bits in this elt. */
1277 unsigned int first_word_to_mod;
1278 BITMAP_WORD first_mask;
1279 unsigned int last_word_to_mod;
1280 BITMAP_WORD last_mask;
1281 unsigned int i;
1282 bool clear = true;
1284 if (elt_start_bit <= start)
1286 /* The first bit to turn off is somewhere inside this
1287 elt. */
1288 first_word_to_mod = (start - elt_start_bit) / BITMAP_WORD_BITS;
1290 /* This mask should have 1s in all bits >= start position. */
1291 first_mask =
1292 (((BITMAP_WORD) 1) << ((start % BITMAP_WORD_BITS))) - 1;
1293 first_mask = ~first_mask;
1295 else
1297 /* The first bit to turn off is below this start of this elt. */
1298 first_word_to_mod = 0;
1299 first_mask = 0;
1300 first_mask = ~first_mask;
1303 if (elt_end_bit_plus1 <= end_bit_plus1)
1305 /* The last bit to turn off is beyond this elt. */
1306 last_word_to_mod = BITMAP_ELEMENT_WORDS - 1;
1307 last_mask = 0;
1308 last_mask = ~last_mask;
1310 else
1312 /* The last bit to turn off is inside to this elt. */
1313 last_word_to_mod =
1314 (end_bit_plus1 - elt_start_bit) / BITMAP_WORD_BITS;
1316 /* The last mask should have 1s below the end bit. */
1317 last_mask =
1318 (((BITMAP_WORD) 1) << (((end_bit_plus1) % BITMAP_WORD_BITS))) - 1;
1322 if (first_word_to_mod == last_word_to_mod)
1324 BITMAP_WORD mask = first_mask & last_mask;
1325 elt->bits[first_word_to_mod] &= ~mask;
1327 else
1329 elt->bits[first_word_to_mod] &= ~first_mask;
1330 if (BITMAP_ELEMENT_WORDS > 2)
1331 for (i = first_word_to_mod + 1; i < last_word_to_mod; i++)
1332 elt->bits[i] = 0;
1333 elt->bits[last_word_to_mod] &= ~last_mask;
1335 for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
1336 if (elt->bits[i])
1338 clear = false;
1339 break;
1341 /* Check to see if there are any bits left. */
1342 if (clear)
1343 bitmap_element_free (head, elt);
1345 elt = next_elt;
1348 if (elt)
1350 head->current = elt;
1351 head->indx = head->current->indx;
1355 /* A = ~A & B. */
1357 void
1358 bitmap_compl_and_into (bitmap a, const_bitmap b)
1360 bitmap_element *a_elt = a->first;
1361 const bitmap_element *b_elt = b->first;
1362 bitmap_element *a_prev = NULL;
1363 bitmap_element *next;
1365 gcc_assert (a != b);
1367 if (bitmap_empty_p (a))
1369 bitmap_copy (a, b);
1370 return;
1372 if (bitmap_empty_p (b))
1374 bitmap_clear (a);
1375 return;
1378 while (a_elt || b_elt)
1380 if (!b_elt || (a_elt && a_elt->indx < b_elt->indx))
1382 /* A is before B. Remove A */
1383 next = a_elt->next;
1384 a_prev = a_elt->prev;
1385 bitmap_element_free (a, a_elt);
1386 a_elt = next;
1388 else if (!a_elt || b_elt->indx < a_elt->indx)
1390 /* B is before A. Copy B. */
1391 next = bitmap_elt_insert_after (a, a_prev, b_elt->indx);
1392 memcpy (next->bits, b_elt->bits, sizeof (next->bits));
1393 a_prev = next;
1394 b_elt = b_elt->next;
1396 else
1398 /* Matching elts, generate A = ~A & B. */
1399 unsigned ix;
1400 BITMAP_WORD ior = 0;
1402 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1404 BITMAP_WORD cleared = a_elt->bits[ix] & b_elt->bits[ix];
1405 BITMAP_WORD r = b_elt->bits[ix] ^ cleared;
1407 a_elt->bits[ix] = r;
1408 ior |= r;
1410 next = a_elt->next;
1411 if (!ior)
1412 bitmap_element_free (a, a_elt);
1413 else
1414 a_prev = a_elt;
1415 a_elt = next;
1416 b_elt = b_elt->next;
1419 gcc_checking_assert (!a->current == !a->first
1420 && (!a->current || a->indx == a->current->indx));
1421 return;
1425 /* Insert an element corresponding to A_ELT | B_ELT after DST_PREV,
1426 overwriting DST_ELT if non-NULL. CHANGED is true if the destination bitmap
1427 had already been changed; the new value of CHANGED is returned. */
1429 static inline bool
1430 bitmap_elt_ior (bitmap dst, bitmap_element *dst_elt, bitmap_element *dst_prev,
1431 const bitmap_element *a_elt, const bitmap_element *b_elt,
1432 bool changed)
1434 gcc_assert (a_elt || b_elt);
1436 if (a_elt && b_elt && a_elt->indx == b_elt->indx)
1438 /* Matching elts, generate A | B. */
1439 unsigned ix;
1441 if (!changed && dst_elt && dst_elt->indx == a_elt->indx)
1443 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1445 BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
1446 if (r != dst_elt->bits[ix])
1448 dst_elt->bits[ix] = r;
1449 changed = true;
1453 else
1455 changed = true;
1456 if (!dst_elt)
1457 dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
1458 else
1459 dst_elt->indx = a_elt->indx;
1460 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1462 BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
1463 dst_elt->bits[ix] = r;
1467 else
1469 /* Copy a single element. */
1470 const bitmap_element *src;
1472 if (!b_elt || (a_elt && a_elt->indx < b_elt->indx))
1473 src = a_elt;
1474 else
1475 src = b_elt;
1477 gcc_checking_assert (src);
1478 changed = bitmap_elt_copy (dst, dst_elt, dst_prev, src, changed);
1480 return changed;
1484 /* DST = A | B. Return true if DST changes. */
1486 bool
1487 bitmap_ior (bitmap dst, const_bitmap a, const_bitmap b)
1489 bitmap_element *dst_elt = dst->first;
1490 const bitmap_element *a_elt = a->first;
1491 const bitmap_element *b_elt = b->first;
1492 bitmap_element *dst_prev = NULL;
1493 bitmap_element **dst_prev_pnext = &dst->first;
1494 bool changed = false;
1496 gcc_assert (dst != a && dst != b);
1498 while (a_elt || b_elt)
1500 changed = bitmap_elt_ior (dst, dst_elt, dst_prev, a_elt, b_elt, changed);
1502 if (a_elt && b_elt && a_elt->indx == b_elt->indx)
1504 a_elt = a_elt->next;
1505 b_elt = b_elt->next;
1507 else
1509 if (a_elt && (!b_elt || a_elt->indx <= b_elt->indx))
1510 a_elt = a_elt->next;
1511 else if (b_elt && (!a_elt || b_elt->indx <= a_elt->indx))
1512 b_elt = b_elt->next;
1515 dst_prev = *dst_prev_pnext;
1516 dst_prev_pnext = &dst_prev->next;
1517 dst_elt = *dst_prev_pnext;
1520 if (dst_elt)
1522 changed = true;
1523 /* Ensure that dst->current is valid. */
1524 dst->current = dst->first;
1525 bitmap_elt_clear_from (dst, dst_elt);
1527 gcc_checking_assert (!dst->current == !dst->first);
1528 if (dst->current)
1529 dst->indx = dst->current->indx;
1530 return changed;
1533 /* A |= B. Return true if A changes. */
1535 bool
1536 bitmap_ior_into (bitmap a, const_bitmap b)
1538 bitmap_element *a_elt = a->first;
1539 const bitmap_element *b_elt = b->first;
1540 bitmap_element *a_prev = NULL;
1541 bitmap_element **a_prev_pnext = &a->first;
1542 bool changed = false;
1544 if (a == b)
1545 return false;
1547 while (b_elt)
1549 /* If A lags behind B, just advance it. */
1550 if (!a_elt || a_elt->indx == b_elt->indx)
1552 changed = bitmap_elt_ior (a, a_elt, a_prev, a_elt, b_elt, changed);
1553 b_elt = b_elt->next;
1555 else if (a_elt->indx > b_elt->indx)
1557 changed = bitmap_elt_copy (a, NULL, a_prev, b_elt, changed);
1558 b_elt = b_elt->next;
1561 a_prev = *a_prev_pnext;
1562 a_prev_pnext = &a_prev->next;
1563 a_elt = *a_prev_pnext;
1566 gcc_checking_assert (!a->current == !a->first);
1567 if (a->current)
1568 a->indx = a->current->indx;
1569 return changed;
1572 /* DST = A ^ B */
1574 void
1575 bitmap_xor (bitmap dst, const_bitmap a, const_bitmap b)
1577 bitmap_element *dst_elt = dst->first;
1578 const bitmap_element *a_elt = a->first;
1579 const bitmap_element *b_elt = b->first;
1580 bitmap_element *dst_prev = NULL;
1582 gcc_assert (dst != a && dst != b);
1583 if (a == b)
1585 bitmap_clear (dst);
1586 return;
1589 while (a_elt || b_elt)
1591 if (a_elt && b_elt && a_elt->indx == b_elt->indx)
1593 /* Matching elts, generate A ^ B. */
1594 unsigned ix;
1595 BITMAP_WORD ior = 0;
1597 if (!dst_elt)
1598 dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
1599 else
1600 dst_elt->indx = a_elt->indx;
1601 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1603 BITMAP_WORD r = a_elt->bits[ix] ^ b_elt->bits[ix];
1605 ior |= r;
1606 dst_elt->bits[ix] = r;
1608 a_elt = a_elt->next;
1609 b_elt = b_elt->next;
1610 if (ior)
1612 dst_prev = dst_elt;
1613 dst_elt = dst_elt->next;
1616 else
1618 /* Copy a single element. */
1619 const bitmap_element *src;
1621 if (!b_elt || (a_elt && a_elt->indx < b_elt->indx))
1623 src = a_elt;
1624 a_elt = a_elt->next;
1626 else
1628 src = b_elt;
1629 b_elt = b_elt->next;
1632 if (!dst_elt)
1633 dst_elt = bitmap_elt_insert_after (dst, dst_prev, src->indx);
1634 else
1635 dst_elt->indx = src->indx;
1636 memcpy (dst_elt->bits, src->bits, sizeof (dst_elt->bits));
1637 dst_prev = dst_elt;
1638 dst_elt = dst_elt->next;
1641 /* Ensure that dst->current is valid. */
1642 dst->current = dst->first;
1643 bitmap_elt_clear_from (dst, dst_elt);
1644 gcc_checking_assert (!dst->current == !dst->first);
1645 if (dst->current)
1646 dst->indx = dst->current->indx;
1649 /* A ^= B */
1651 void
1652 bitmap_xor_into (bitmap a, const_bitmap b)
1654 bitmap_element *a_elt = a->first;
1655 const bitmap_element *b_elt = b->first;
1656 bitmap_element *a_prev = NULL;
1658 if (a == b)
1660 bitmap_clear (a);
1661 return;
1664 while (b_elt)
1666 if (!a_elt || b_elt->indx < a_elt->indx)
1668 /* Copy b_elt. */
1669 bitmap_element *dst = bitmap_elt_insert_after (a, a_prev, b_elt->indx);
1670 memcpy (dst->bits, b_elt->bits, sizeof (dst->bits));
1671 a_prev = dst;
1672 b_elt = b_elt->next;
1674 else if (a_elt->indx < b_elt->indx)
1676 a_prev = a_elt;
1677 a_elt = a_elt->next;
1679 else
1681 /* Matching elts, generate A ^= B. */
1682 unsigned ix;
1683 BITMAP_WORD ior = 0;
1684 bitmap_element *next = a_elt->next;
1686 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1688 BITMAP_WORD r = a_elt->bits[ix] ^ b_elt->bits[ix];
1690 ior |= r;
1691 a_elt->bits[ix] = r;
1693 b_elt = b_elt->next;
1694 if (ior)
1695 a_prev = a_elt;
1696 else
1697 bitmap_element_free (a, a_elt);
1698 a_elt = next;
1701 gcc_checking_assert (!a->current == !a->first);
1702 if (a->current)
1703 a->indx = a->current->indx;
1706 /* Return true if two bitmaps are identical.
1707 We do not bother with a check for pointer equality, as that never
1708 occurs in practice. */
1710 bool
1711 bitmap_equal_p (const_bitmap a, const_bitmap b)
1713 const bitmap_element *a_elt;
1714 const bitmap_element *b_elt;
1715 unsigned ix;
1717 for (a_elt = a->first, b_elt = b->first;
1718 a_elt && b_elt;
1719 a_elt = a_elt->next, b_elt = b_elt->next)
1721 if (a_elt->indx != b_elt->indx)
1722 return false;
1723 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1724 if (a_elt->bits[ix] != b_elt->bits[ix])
1725 return false;
1727 return !a_elt && !b_elt;
1730 /* Return true if A AND B is not empty. */
1732 bool
1733 bitmap_intersect_p (const_bitmap a, const_bitmap b)
1735 const bitmap_element *a_elt;
1736 const bitmap_element *b_elt;
1737 unsigned ix;
1739 for (a_elt = a->first, b_elt = b->first;
1740 a_elt && b_elt;)
1742 if (a_elt->indx < b_elt->indx)
1743 a_elt = a_elt->next;
1744 else if (b_elt->indx < a_elt->indx)
1745 b_elt = b_elt->next;
1746 else
1748 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1749 if (a_elt->bits[ix] & b_elt->bits[ix])
1750 return true;
1751 a_elt = a_elt->next;
1752 b_elt = b_elt->next;
1755 return false;
1758 /* Return true if A AND NOT B is not empty. */
1760 bool
1761 bitmap_intersect_compl_p (const_bitmap a, const_bitmap b)
1763 const bitmap_element *a_elt;
1764 const bitmap_element *b_elt;
1765 unsigned ix;
1766 for (a_elt = a->first, b_elt = b->first;
1767 a_elt && b_elt;)
1769 if (a_elt->indx < b_elt->indx)
1770 return true;
1771 else if (b_elt->indx < a_elt->indx)
1772 b_elt = b_elt->next;
1773 else
1775 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1776 if (a_elt->bits[ix] & ~b_elt->bits[ix])
1777 return true;
1778 a_elt = a_elt->next;
1779 b_elt = b_elt->next;
1782 return a_elt != NULL;
1786 /* DST = A | (FROM1 & ~FROM2). Return true if DST changes. */
1788 bool
1789 bitmap_ior_and_compl (bitmap dst, const_bitmap a, const_bitmap b, const_bitmap kill)
1791 bool changed = false;
1793 bitmap_element *dst_elt = dst->first;
1794 const bitmap_element *a_elt = a->first;
1795 const bitmap_element *b_elt = b->first;
1796 const bitmap_element *kill_elt = kill->first;
1797 bitmap_element *dst_prev = NULL;
1798 bitmap_element **dst_prev_pnext = &dst->first;
1800 gcc_assert (dst != a && dst != b && dst != kill);
1802 /* Special cases. We don't bother checking for bitmap_equal_p (b, kill). */
1803 if (b == kill || bitmap_empty_p (b))
1805 changed = !bitmap_equal_p (dst, a);
1806 if (changed)
1807 bitmap_copy (dst, a);
1808 return changed;
1810 if (bitmap_empty_p (kill))
1811 return bitmap_ior (dst, a, b);
1812 if (bitmap_empty_p (a))
1813 return bitmap_and_compl (dst, b, kill);
1815 while (a_elt || b_elt)
1817 bool new_element = false;
1819 if (b_elt)
1820 while (kill_elt && kill_elt->indx < b_elt->indx)
1821 kill_elt = kill_elt->next;
1823 if (b_elt && kill_elt && kill_elt->indx == b_elt->indx
1824 && (!a_elt || a_elt->indx >= b_elt->indx))
1826 bitmap_element tmp_elt;
1827 unsigned ix;
1829 BITMAP_WORD ior = 0;
1830 tmp_elt.indx = b_elt->indx;
1831 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1833 BITMAP_WORD r = b_elt->bits[ix] & ~kill_elt->bits[ix];
1834 ior |= r;
1835 tmp_elt.bits[ix] = r;
1838 if (ior)
1840 changed = bitmap_elt_ior (dst, dst_elt, dst_prev,
1841 a_elt, &tmp_elt, changed);
1842 new_element = true;
1843 if (a_elt && a_elt->indx == b_elt->indx)
1844 a_elt = a_elt->next;
1847 b_elt = b_elt->next;
1848 kill_elt = kill_elt->next;
1850 else
1852 changed = bitmap_elt_ior (dst, dst_elt, dst_prev,
1853 a_elt, b_elt, changed);
1854 new_element = true;
1856 if (a_elt && b_elt && a_elt->indx == b_elt->indx)
1858 a_elt = a_elt->next;
1859 b_elt = b_elt->next;
1861 else
1863 if (a_elt && (!b_elt || a_elt->indx <= b_elt->indx))
1864 a_elt = a_elt->next;
1865 else if (b_elt && (!a_elt || b_elt->indx <= a_elt->indx))
1866 b_elt = b_elt->next;
1870 if (new_element)
1872 dst_prev = *dst_prev_pnext;
1873 dst_prev_pnext = &dst_prev->next;
1874 dst_elt = *dst_prev_pnext;
1878 if (dst_elt)
1880 changed = true;
1881 /* Ensure that dst->current is valid. */
1882 dst->current = dst->first;
1883 bitmap_elt_clear_from (dst, dst_elt);
1885 gcc_checking_assert (!dst->current == !dst->first);
1886 if (dst->current)
1887 dst->indx = dst->current->indx;
1889 return changed;
1892 /* A |= (FROM1 & ~FROM2). Return true if A changes. */
1894 bool
1895 bitmap_ior_and_compl_into (bitmap a, const_bitmap from1, const_bitmap from2)
1897 bitmap_head tmp;
1898 bool changed;
1900 bitmap_initialize (&tmp, &bitmap_default_obstack);
1901 bitmap_and_compl (&tmp, from1, from2);
1902 changed = bitmap_ior_into (a, &tmp);
1903 bitmap_clear (&tmp);
1905 return changed;
1908 /* A |= (B & C). Return true if A changes. */
1910 bool
1911 bitmap_ior_and_into (bitmap a, const_bitmap b, const_bitmap c)
1913 bitmap_element *a_elt = a->first;
1914 const bitmap_element *b_elt = b->first;
1915 const bitmap_element *c_elt = c->first;
1916 bitmap_element and_elt;
1917 bitmap_element *a_prev = NULL;
1918 bitmap_element **a_prev_pnext = &a->first;
1919 bool changed = false;
1920 unsigned ix;
1922 if (b == c)
1923 return bitmap_ior_into (a, b);
1924 if (bitmap_empty_p (b) || bitmap_empty_p (c))
1925 return false;
1927 and_elt.indx = -1;
1928 while (b_elt && c_elt)
1930 BITMAP_WORD overall;
1932 /* Find a common item of B and C. */
1933 while (b_elt->indx != c_elt->indx)
1935 if (b_elt->indx < c_elt->indx)
1937 b_elt = b_elt->next;
1938 if (!b_elt)
1939 goto done;
1941 else
1943 c_elt = c_elt->next;
1944 if (!c_elt)
1945 goto done;
1949 overall = 0;
1950 and_elt.indx = b_elt->indx;
1951 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1953 and_elt.bits[ix] = b_elt->bits[ix] & c_elt->bits[ix];
1954 overall |= and_elt.bits[ix];
1957 b_elt = b_elt->next;
1958 c_elt = c_elt->next;
1959 if (!overall)
1960 continue;
1962 /* Now find a place to insert AND_ELT. */
1965 ix = a_elt ? a_elt->indx : and_elt.indx;
1966 if (ix == and_elt.indx)
1967 changed = bitmap_elt_ior (a, a_elt, a_prev, a_elt, &and_elt, changed);
1968 else if (ix > and_elt.indx)
1969 changed = bitmap_elt_copy (a, NULL, a_prev, &and_elt, changed);
1971 a_prev = *a_prev_pnext;
1972 a_prev_pnext = &a_prev->next;
1973 a_elt = *a_prev_pnext;
1975 /* If A lagged behind B/C, we advanced it so loop once more. */
1977 while (ix < and_elt.indx);
1980 done:
1981 gcc_checking_assert (!a->current == !a->first);
1982 if (a->current)
1983 a->indx = a->current->indx;
1984 return changed;
1987 /* Compute hash of bitmap (for purposes of hashing). */
1988 hashval_t
1989 bitmap_hash (const_bitmap head)
1991 const bitmap_element *ptr;
1992 BITMAP_WORD hash = 0;
1993 int ix;
1995 for (ptr = head->first; ptr; ptr = ptr->next)
1997 hash ^= ptr->indx;
1998 for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
1999 hash ^= ptr->bits[ix];
2001 return (hashval_t)hash;
2005 /* Debugging function to print out the contents of a bitmap. */
2007 DEBUG_FUNCTION void
2008 debug_bitmap_file (FILE *file, const_bitmap head)
2010 const bitmap_element *ptr;
2012 fprintf (file, "\nfirst = " HOST_PTR_PRINTF
2013 " current = " HOST_PTR_PRINTF " indx = %u\n",
2014 (void *) head->first, (void *) head->current, head->indx);
2016 for (ptr = head->first; ptr; ptr = ptr->next)
2018 unsigned int i, j, col = 26;
2020 fprintf (file, "\t" HOST_PTR_PRINTF " next = " HOST_PTR_PRINTF
2021 " prev = " HOST_PTR_PRINTF " indx = %u\n\t\tbits = {",
2022 (const void*) ptr, (const void*) ptr->next,
2023 (const void*) ptr->prev, ptr->indx);
2025 for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
2026 for (j = 0; j < BITMAP_WORD_BITS; j++)
2027 if ((ptr->bits[i] >> j) & 1)
2029 if (col > 70)
2031 fprintf (file, "\n\t\t\t");
2032 col = 24;
2035 fprintf (file, " %u", (ptr->indx * BITMAP_ELEMENT_ALL_BITS
2036 + i * BITMAP_WORD_BITS + j));
2037 col += 4;
2040 fprintf (file, " }\n");
2044 /* Function to be called from the debugger to print the contents
2045 of a bitmap. */
2047 DEBUG_FUNCTION void
2048 debug_bitmap (const_bitmap head)
2050 debug_bitmap_file (stderr, head);
2053 /* Function to print out the contents of a bitmap. Unlike debug_bitmap_file,
2054 it does not print anything but the bits. */
2056 DEBUG_FUNCTION void
2057 bitmap_print (FILE *file, const_bitmap head, const char *prefix,
2058 const char *suffix)
2060 const char *comma = "";
2061 unsigned i;
2062 bitmap_iterator bi;
2064 fputs (prefix, file);
2065 EXECUTE_IF_SET_IN_BITMAP (head, 0, i, bi)
2067 fprintf (file, "%s%d", comma, i);
2068 comma = ", ";
2070 fputs (suffix, file);
2073 /* Output per-bitmap memory usage statistics. */
2074 void
2075 dump_bitmap_statistics (void)
2077 if (!GATHER_STATISTICS)
2078 return;
2080 bitmap_mem_desc.dump (BITMAP_ORIGIN);
2083 DEBUG_FUNCTION void
2084 debug (const bitmap_head &ref)
2086 dump_bitmap (stderr, &ref);
2089 DEBUG_FUNCTION void
2090 debug (const bitmap_head *ptr)
2092 if (ptr)
2093 debug (*ptr);
2094 else
2095 fprintf (stderr, "<nil>\n");
2099 #include "gt-bitmap.h"