1 /* Functions to support general ended bitmaps.
2 Copyright (C) 1997-2016 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
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
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/>. */
22 #include "coretypes.h"
26 /* Memory allocation statistics purpose instance. */
27 mem_alloc_description
<bitmap_usage
> bitmap_mem_desc
;
29 /* Register new bitmap. */
31 bitmap_register (bitmap b MEM_STAT_DECL
)
33 bitmap_mem_desc
.register_descriptor (b
, BITMAP_ORIGIN
, false
37 /* Account the overhead. */
39 register_overhead (bitmap b
, size_t amount
)
41 if (bitmap_mem_desc
.contains_descriptor_for_instance (b
))
42 bitmap_mem_desc
.register_instance_overhead (amount
, b
);
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
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. */
64 bitmap_elem_to_freelist (bitmap head
, bitmap_element
*elt
)
66 bitmap_obstack
*bit_obstack
= head
->obstack
;
71 elt
->prev
= bit_obstack
->elements
;
72 bit_obstack
->elements
= elt
;
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". */
85 bitmap_element_free (bitmap head
, bitmap_element
*elt
)
87 bitmap_element
*next
= elt
->next
;
88 bitmap_element
*prev
= elt
->prev
;
96 if (head
->first
== elt
)
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
;
105 head
->indx
= head
->current
->indx
;
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
;
126 element
= bit_obstack
->elements
;
129 /* Use up the inner list first before looking at the next
130 element of the outer list. */
133 bit_obstack
->elements
= element
->next
;
134 bit_obstack
->elements
->prev
= element
->prev
;
137 /* Inner list was just a singleton. */
138 bit_obstack
->elements
= element
->prev
;
140 element
= XOBNEW (&bit_obstack
->obstack
, bitmap_element
);
144 element
= bitmap_ggc_free
;
146 /* Use up the inner list first before looking at the next
147 element of the outer list. */
150 bitmap_ggc_free
= element
->next
;
151 bitmap_ggc_free
->prev
= element
->prev
;
154 /* Inner list was just a singleton. */
155 bitmap_ggc_free
= element
->prev
;
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
));
168 /* Remove ELT and all following elements from bitmap HEAD. */
171 bitmap_elt_clear_from (bitmap head
, bitmap_element
*elt
)
173 bitmap_element
*prev
;
174 bitmap_obstack
*bit_obstack
= head
->obstack
;
178 if (GATHER_STATISTICS
)
181 for (prev
= elt
; prev
; prev
= prev
->next
)
183 register_overhead (head
, -sizeof (bitmap_element
) * n
);
190 if (head
->current
->indx
> prev
->indx
)
192 head
->current
= prev
;
193 head
->indx
= prev
->indx
;
199 head
->current
= NULL
;
203 /* Put the entire list onto the free list in one operation. */
206 elt
->prev
= bit_obstack
->elements
;
207 bit_obstack
->elements
= elt
;
211 elt
->prev
= bitmap_ggc_free
;
212 bitmap_ggc_free
= elt
;
216 /* Clear a bitmap by freeing the linked list. */
219 bitmap_clear (bitmap head
)
222 bitmap_elt_clear_from (head
, head
->first
);
225 /* Initialize a bitmap obstack. If BIT_OBSTACK is NULL, initialize
226 the default bitmap obstack. */
229 bitmap_obstack_initialize (bitmap_obstack
*bit_obstack
)
233 if (bitmap_default_obstack_depth
++)
235 bit_obstack
= &bitmap_default_obstack
;
238 #if !defined(__GNUC__) || (__GNUC__ < 2)
239 #define __alignof__(type) 0
242 bit_obstack
->elements
= NULL
;
243 bit_obstack
->heads
= NULL
;
244 obstack_specify_allocation (&bit_obstack
->obstack
, OBSTACK_CHUNK_SIZE
,
245 __alignof__ (bitmap_element
),
250 /* Release the memory from a bitmap obstack. If BIT_OBSTACK is NULL,
251 release the default bitmap obstack. */
254 bitmap_obstack_release (bitmap_obstack
*bit_obstack
)
258 if (--bitmap_default_obstack_depth
)
260 gcc_assert (bitmap_default_obstack_depth
> 0);
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. */
275 bitmap_obstack_alloc_stat (bitmap_obstack
*bit_obstack MEM_STAT_DECL
)
280 bit_obstack
= &bitmap_default_obstack
;
281 map
= bit_obstack
->heads
;
283 bit_obstack
->heads
= (struct bitmap_head
*) map
->first
;
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
));
294 /* Create a new GCd bitmap. */
297 bitmap_gc_alloc_stat (ALONE_MEM_STAT_DECL
)
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
));
310 /* Release an obstack allocated bitmap. */
313 bitmap_obstack_free (bitmap 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. */
331 bitmap_element_zerop (const bitmap_element
*element
)
333 #if BITMAP_ELEMENT_WORDS == 2
334 return (element
->bits
[0] | element
->bits
[1]) == 0;
338 for (i
= 0; i
< BITMAP_ELEMENT_WORDS
; i
++)
339 if (element
->bits
[i
] != 0)
346 /* Link the bitmap element into the current bitmap linked list. */
349 bitmap_element_link (bitmap head
, bitmap_element
*element
)
351 unsigned int indx
= element
->indx
;
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
;
371 ptr
->prev
->next
= element
;
373 head
->first
= element
;
375 element
->prev
= ptr
->prev
;
380 /* Otherwise, it must go someplace after the current element. */
383 for (ptr
= head
->current
;
384 ptr
->next
!= 0 && ptr
->next
->indx
< indx
;
389 ptr
->next
->prev
= element
;
391 element
->next
= ptr
->next
;
396 /* Set up so this is the first element searched. */
397 head
->current
= element
;
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
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
);
415 head
->current
= node
;
418 node
->next
= head
->first
;
420 node
->next
->prev
= node
;
426 gcc_checking_assert (head
->current
);
427 node
->next
= elt
->next
;
429 node
->next
->prev
= node
;
436 /* Copy a bitmap to another bitmap. */
439 bitmap_copy (bitmap to
, const_bitmap from
)
441 const bitmap_element
*from_ptr
;
442 bitmap_element
*to_ptr
= 0;
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. */
458 to
->first
= to
->current
= to_elt
;
459 to
->indx
= from_ptr
->indx
;
460 to_elt
->next
= to_elt
->prev
= 0;
464 to_elt
->prev
= to_ptr
;
466 to_ptr
->next
= to_elt
;
473 /* Move a bitmap to another bitmap. */
476 bitmap_move (bitmap to
, bitmap from
)
478 gcc_assert (to
->obstack
== from
->obstack
);
484 if (GATHER_STATISTICS
)
487 for (bitmap_element
*e
= to
->first
; e
; e
= e
->next
)
488 sz
+= sizeof (bitmap_element
);
489 register_overhead (to
, sz
);
490 register_overhead (from
, -sz
);
494 /* Find a bitmap element that would hold a bitmap's bit.
495 Update the `current' field even if we can't find an element that
496 would hold the bitmap's bit to make eventual allocation
499 static inline bitmap_element
*
500 bitmap_find_bit (bitmap head
, unsigned int bit
)
502 bitmap_element
*element
;
503 unsigned int indx
= bit
/ BITMAP_ELEMENT_ALL_BITS
;
505 if (head
->current
== NULL
506 || head
->indx
== indx
)
507 return head
->current
;
508 if (head
->current
== head
->first
509 && head
->first
->next
== NULL
)
512 /* Usage can be NULL due to allocated bitmaps for which we do not
513 call initialize function. */
514 bitmap_usage
*usage
= NULL
;
515 if (GATHER_STATISTICS
)
516 usage
= bitmap_mem_desc
.get_descriptor_for_instance (head
);
518 /* This bitmap has more than one element, and we're going to look
519 through the elements list. Count that as a search. */
520 if (GATHER_STATISTICS
&& usage
)
521 usage
->m_nsearches
++;
523 if (head
->indx
< indx
)
524 /* INDX is beyond head->indx. Search from head->current
526 for (element
= head
->current
;
527 element
->next
!= 0 && element
->indx
< indx
;
528 element
= element
->next
)
530 if (GATHER_STATISTICS
&& usage
)
531 usage
->m_search_iter
++;
534 else if (head
->indx
/ 2 < indx
)
535 /* INDX is less than head->indx and closer to head->indx than to
536 0. Search from head->current backward. */
537 for (element
= head
->current
;
538 element
->prev
!= 0 && element
->indx
> indx
;
539 element
= element
->prev
)
541 if (GATHER_STATISTICS
&& usage
)
542 usage
->m_search_iter
++;
546 /* INDX is less than head->indx and closer to 0 than to
547 head->indx. Search from head->first forward. */
548 for (element
= head
->first
;
549 element
->next
!= 0 && element
->indx
< indx
;
550 element
= element
->next
)
551 if (GATHER_STATISTICS
&& usage
)
553 usage
->m_search_iter
++;
556 /* `element' is the nearest to the one we want. If it's not the one we
557 want, the one we want doesn't exist. */
558 head
->current
= element
;
559 head
->indx
= element
->indx
;
560 if (element
->indx
!= indx
)
566 /* Clear a single bit in a bitmap. Return true if the bit changed. */
569 bitmap_clear_bit (bitmap head
, int bit
)
571 bitmap_element
*const ptr
= bitmap_find_bit (head
, bit
);
575 unsigned bit_num
= bit
% BITMAP_WORD_BITS
;
576 unsigned word_num
= bit
/ BITMAP_WORD_BITS
% BITMAP_ELEMENT_WORDS
;
577 BITMAP_WORD bit_val
= ((BITMAP_WORD
) 1) << bit_num
;
578 bool res
= (ptr
->bits
[word_num
] & bit_val
) != 0;
581 ptr
->bits
[word_num
] &= ~bit_val
;
582 /* If we cleared the entire word, free up the element. */
583 if (!ptr
->bits
[word_num
]
584 && bitmap_element_zerop (ptr
))
585 bitmap_element_free (head
, ptr
);
594 /* Set a single bit in a bitmap. Return true if the bit changed. */
597 bitmap_set_bit (bitmap head
, int bit
)
599 bitmap_element
*ptr
= bitmap_find_bit (head
, bit
);
600 unsigned word_num
= bit
/ BITMAP_WORD_BITS
% BITMAP_ELEMENT_WORDS
;
601 unsigned bit_num
= bit
% BITMAP_WORD_BITS
;
602 BITMAP_WORD bit_val
= ((BITMAP_WORD
) 1) << bit_num
;
606 ptr
= bitmap_element_allocate (head
);
607 ptr
->indx
= bit
/ BITMAP_ELEMENT_ALL_BITS
;
608 ptr
->bits
[word_num
] = bit_val
;
609 bitmap_element_link (head
, ptr
);
614 bool res
= (ptr
->bits
[word_num
] & bit_val
) == 0;
616 ptr
->bits
[word_num
] |= bit_val
;
621 /* Return whether a bit is set within a bitmap. */
624 bitmap_bit_p (bitmap head
, int bit
)
630 ptr
= bitmap_find_bit (head
, bit
);
634 bit_num
= bit
% BITMAP_WORD_BITS
;
635 word_num
= bit
/ BITMAP_WORD_BITS
% BITMAP_ELEMENT_WORDS
;
637 return (ptr
->bits
[word_num
] >> bit_num
) & 1;
640 #if GCC_VERSION < 3400
641 /* Table of number of set bits in a character, indexed by value of char. */
642 static const unsigned char popcount_table
[] =
644 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,
645 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,
646 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,
647 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,
648 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,
649 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,
650 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,
651 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,
655 bitmap_popcount (BITMAP_WORD a
)
657 unsigned long ret
= 0;
660 /* Just do this the table way for now */
661 for (i
= 0; i
< BITMAP_WORD_BITS
; i
+= 8)
662 ret
+= popcount_table
[(a
>> i
) & 0xff];
667 /* Count and return the number of bits set in the bitmap word BITS. */
669 bitmap_count_bits_in_word (const BITMAP_WORD
*bits
)
671 unsigned long count
= 0;
673 for (unsigned ix
= 0; ix
!= BITMAP_ELEMENT_WORDS
; ix
++)
675 #if GCC_VERSION >= 3400
676 /* Note that popcountl matches BITMAP_WORD in type, so the actual size
677 of BITMAP_WORD is not material. */
678 count
+= __builtin_popcountl (bits
[ix
]);
680 count
+= bitmap_popcount (bits
[ix
]);
686 /* Count the number of bits set in the bitmap, and return it. */
689 bitmap_count_bits (const_bitmap a
)
691 unsigned long count
= 0;
692 const bitmap_element
*elt
;
694 for (elt
= a
->first
; elt
; elt
= elt
->next
)
695 count
+= bitmap_count_bits_in_word (elt
->bits
);
700 /* Count the number of unique bits set in A and B and return it. */
703 bitmap_count_unique_bits (const_bitmap a
, const_bitmap b
)
705 unsigned long count
= 0;
706 const bitmap_element
*elt_a
, *elt_b
;
708 for (elt_a
= a
->first
, elt_b
= b
->first
; elt_a
&& elt_b
; )
710 /* If we're at different indices, then count all the bits
711 in the lower element. If we're at the same index, then
712 count the bits in the IOR of the two elements. */
713 if (elt_a
->indx
< elt_b
->indx
)
715 count
+= bitmap_count_bits_in_word (elt_a
->bits
);
718 else if (elt_b
->indx
< elt_a
->indx
)
720 count
+= bitmap_count_bits_in_word (elt_b
->bits
);
725 BITMAP_WORD bits
[BITMAP_ELEMENT_WORDS
];
726 for (unsigned ix
= 0; ix
!= BITMAP_ELEMENT_WORDS
; ix
++)
727 bits
[ix
] = elt_a
->bits
[ix
] | elt_b
->bits
[ix
];
728 count
+= bitmap_count_bits_in_word (bits
);
736 /* Return true if the bitmap has a single bit set. Otherwise return
740 bitmap_single_bit_set_p (const_bitmap a
)
742 unsigned long count
= 0;
743 const bitmap_element
*elt
;
746 if (bitmap_empty_p (a
))
750 /* As there are no completely empty bitmap elements, a second one
751 means we have more than one bit set. */
752 if (elt
->next
!= NULL
)
755 for (ix
= 0; ix
!= BITMAP_ELEMENT_WORDS
; ix
++)
757 #if GCC_VERSION >= 3400
758 /* Note that popcountl matches BITMAP_WORD in type, so the actual size
759 of BITMAP_WORD is not material. */
760 count
+= __builtin_popcountl (elt
->bits
[ix
]);
762 count
+= bitmap_popcount (elt
->bits
[ix
]);
772 /* Return the bit number of the first set bit in the bitmap. The
773 bitmap must be non-empty. */
776 bitmap_first_set_bit (const_bitmap a
)
778 const bitmap_element
*elt
= a
->first
;
783 gcc_checking_assert (elt
);
784 bit_no
= elt
->indx
* BITMAP_ELEMENT_ALL_BITS
;
785 for (ix
= 0; ix
!= BITMAP_ELEMENT_WORDS
; ix
++)
787 word
= elt
->bits
[ix
];
793 bit_no
+= ix
* BITMAP_WORD_BITS
;
795 #if GCC_VERSION >= 3004
796 gcc_assert (sizeof (long) == sizeof (word
));
797 bit_no
+= __builtin_ctzl (word
);
799 /* Binary search for the first set bit. */
800 #if BITMAP_WORD_BITS > 64
801 #error "Fill out the table."
803 #if BITMAP_WORD_BITS > 32
804 if (!(word
& 0xffffffff))
805 word
>>= 32, bit_no
+= 32;
807 if (!(word
& 0xffff))
808 word
>>= 16, bit_no
+= 16;
810 word
>>= 8, bit_no
+= 8;
812 word
>>= 4, bit_no
+= 4;
814 word
>>= 2, bit_no
+= 2;
816 word
>>= 1, bit_no
+= 1;
818 gcc_checking_assert (word
& 1);
823 /* Return the bit number of the first set bit in the bitmap. The
824 bitmap must be non-empty. */
827 bitmap_last_set_bit (const_bitmap a
)
829 const bitmap_element
*elt
= a
->current
? a
->current
: a
->first
;
834 gcc_checking_assert (elt
);
837 bit_no
= elt
->indx
* BITMAP_ELEMENT_ALL_BITS
;
838 for (ix
= BITMAP_ELEMENT_WORDS
- 1; ix
>= 0; ix
--)
840 word
= elt
->bits
[ix
];
846 bit_no
+= ix
* BITMAP_WORD_BITS
;
847 #if GCC_VERSION >= 3004
848 gcc_assert (sizeof (long) == sizeof (word
));
849 bit_no
+= BITMAP_WORD_BITS
- __builtin_clzl (word
) - 1;
851 /* Hopefully this is a twos-complement host... */
852 BITMAP_WORD x
= word
;
858 #if BITMAP_WORD_BITS > 32
861 bit_no
+= bitmap_popcount (x
) - 1;
871 bitmap_and (bitmap dst
, const_bitmap a
, const_bitmap b
)
873 bitmap_element
*dst_elt
= dst
->first
;
874 const bitmap_element
*a_elt
= a
->first
;
875 const bitmap_element
*b_elt
= b
->first
;
876 bitmap_element
*dst_prev
= NULL
;
878 gcc_assert (dst
!= a
&& dst
!= b
);
882 bitmap_copy (dst
, a
);
886 while (a_elt
&& b_elt
)
888 if (a_elt
->indx
< b_elt
->indx
)
890 else if (b_elt
->indx
< a_elt
->indx
)
894 /* Matching elts, generate A & B. */
899 dst_elt
= bitmap_elt_insert_after (dst
, dst_prev
, a_elt
->indx
);
901 dst_elt
->indx
= a_elt
->indx
;
902 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
904 BITMAP_WORD r
= a_elt
->bits
[ix
] & b_elt
->bits
[ix
];
906 dst_elt
->bits
[ix
] = r
;
912 dst_elt
= dst_elt
->next
;
918 /* Ensure that dst->current is valid. */
919 dst
->current
= dst
->first
;
920 bitmap_elt_clear_from (dst
, dst_elt
);
921 gcc_checking_assert (!dst
->current
== !dst
->first
);
923 dst
->indx
= dst
->current
->indx
;
926 /* A &= B. Return true if A changed. */
929 bitmap_and_into (bitmap a
, const_bitmap b
)
931 bitmap_element
*a_elt
= a
->first
;
932 const bitmap_element
*b_elt
= b
->first
;
933 bitmap_element
*next
;
934 bool changed
= false;
939 while (a_elt
&& b_elt
)
941 if (a_elt
->indx
< b_elt
->indx
)
944 bitmap_element_free (a
, a_elt
);
948 else if (b_elt
->indx
< a_elt
->indx
)
952 /* Matching elts, generate A &= B. */
956 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
958 BITMAP_WORD r
= a_elt
->bits
[ix
] & b_elt
->bits
[ix
];
959 if (a_elt
->bits
[ix
] != r
)
966 bitmap_element_free (a
, a_elt
);
975 bitmap_elt_clear_from (a
, a_elt
);
978 gcc_checking_assert (!a
->current
== !a
->first
979 && (!a
->current
|| a
->indx
== a
->current
->indx
));
985 /* Insert an element equal to SRC_ELT after DST_PREV, overwriting DST_ELT
986 if non-NULL. CHANGED is true if the destination bitmap had already been
987 changed; the new value of CHANGED is returned. */
990 bitmap_elt_copy (bitmap dst
, bitmap_element
*dst_elt
, bitmap_element
*dst_prev
,
991 const bitmap_element
*src_elt
, bool changed
)
993 if (!changed
&& dst_elt
&& dst_elt
->indx
== src_elt
->indx
)
997 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
998 if (src_elt
->bits
[ix
] != dst_elt
->bits
[ix
])
1000 dst_elt
->bits
[ix
] = src_elt
->bits
[ix
];
1008 dst_elt
= bitmap_elt_insert_after (dst
, dst_prev
, src_elt
->indx
);
1010 dst_elt
->indx
= src_elt
->indx
;
1011 memcpy (dst_elt
->bits
, src_elt
->bits
, sizeof (dst_elt
->bits
));
1021 bitmap_and_compl (bitmap dst
, const_bitmap a
, const_bitmap b
)
1023 bitmap_element
*dst_elt
= dst
->first
;
1024 const bitmap_element
*a_elt
= a
->first
;
1025 const bitmap_element
*b_elt
= b
->first
;
1026 bitmap_element
*dst_prev
= NULL
;
1027 bitmap_element
**dst_prev_pnext
= &dst
->first
;
1028 bool changed
= false;
1030 gcc_assert (dst
!= a
&& dst
!= b
);
1034 changed
= !bitmap_empty_p (dst
);
1041 while (b_elt
&& b_elt
->indx
< a_elt
->indx
)
1042 b_elt
= b_elt
->next
;
1044 if (!b_elt
|| b_elt
->indx
> a_elt
->indx
)
1046 changed
= bitmap_elt_copy (dst
, dst_elt
, dst_prev
, a_elt
, changed
);
1047 dst_prev
= *dst_prev_pnext
;
1048 dst_prev_pnext
= &dst_prev
->next
;
1049 dst_elt
= *dst_prev_pnext
;
1050 a_elt
= a_elt
->next
;
1055 /* Matching elts, generate A & ~B. */
1057 BITMAP_WORD ior
= 0;
1059 if (!changed
&& dst_elt
&& dst_elt
->indx
== a_elt
->indx
)
1061 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1063 BITMAP_WORD r
= a_elt
->bits
[ix
] & ~b_elt
->bits
[ix
];
1065 if (dst_elt
->bits
[ix
] != r
)
1068 dst_elt
->bits
[ix
] = r
;
1076 if (!dst_elt
|| dst_elt
->indx
> a_elt
->indx
)
1078 dst_elt
= bitmap_elt_insert_after (dst
, dst_prev
, a_elt
->indx
);
1083 dst_elt
->indx
= a_elt
->indx
;
1084 new_element
= false;
1087 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1089 BITMAP_WORD r
= a_elt
->bits
[ix
] & ~b_elt
->bits
[ix
];
1091 dst_elt
->bits
[ix
] = r
;
1099 changed
|= !new_element
;
1100 bitmap_element_free (dst
, dst_elt
);
1101 dst_elt
= *dst_prev_pnext
;
1107 dst_prev
= *dst_prev_pnext
;
1108 dst_prev_pnext
= &dst_prev
->next
;
1109 dst_elt
= *dst_prev_pnext
;
1111 a_elt
= a_elt
->next
;
1112 b_elt
= b_elt
->next
;
1116 /* Ensure that dst->current is valid. */
1117 dst
->current
= dst
->first
;
1122 bitmap_elt_clear_from (dst
, dst_elt
);
1124 gcc_checking_assert (!dst
->current
== !dst
->first
);
1126 dst
->indx
= dst
->current
->indx
;
1131 /* A &= ~B. Returns true if A changes */
1134 bitmap_and_compl_into (bitmap a
, const_bitmap b
)
1136 bitmap_element
*a_elt
= a
->first
;
1137 const bitmap_element
*b_elt
= b
->first
;
1138 bitmap_element
*next
;
1139 BITMAP_WORD changed
= 0;
1143 if (bitmap_empty_p (a
))
1152 while (a_elt
&& b_elt
)
1154 if (a_elt
->indx
< b_elt
->indx
)
1155 a_elt
= a_elt
->next
;
1156 else if (b_elt
->indx
< a_elt
->indx
)
1157 b_elt
= b_elt
->next
;
1160 /* Matching elts, generate A &= ~B. */
1162 BITMAP_WORD ior
= 0;
1164 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1166 BITMAP_WORD cleared
= a_elt
->bits
[ix
] & b_elt
->bits
[ix
];
1167 BITMAP_WORD r
= a_elt
->bits
[ix
] ^ cleared
;
1169 a_elt
->bits
[ix
] = r
;
1175 bitmap_element_free (a
, a_elt
);
1177 b_elt
= b_elt
->next
;
1180 gcc_checking_assert (!a
->current
== !a
->first
1181 && (!a
->current
|| a
->indx
== a
->current
->indx
));
1182 return changed
!= 0;
1185 /* Set COUNT bits from START in HEAD. */
1187 bitmap_set_range (bitmap head
, unsigned int start
, unsigned int count
)
1189 unsigned int first_index
, end_bit_plus1
, last_index
;
1190 bitmap_element
*elt
, *elt_prev
;
1198 bitmap_set_bit (head
, start
);
1202 first_index
= start
/ BITMAP_ELEMENT_ALL_BITS
;
1203 end_bit_plus1
= start
+ count
;
1204 last_index
= (end_bit_plus1
- 1) / BITMAP_ELEMENT_ALL_BITS
;
1205 elt
= bitmap_find_bit (head
, start
);
1207 /* If bitmap_find_bit returns zero, the current is the closest block
1208 to the result. Otherwise, just use bitmap_element_allocate to
1209 ensure ELT is set; in the loop below, ELT == NULL means "insert
1210 at the end of the bitmap". */
1213 elt
= bitmap_element_allocate (head
);
1214 elt
->indx
= first_index
;
1215 bitmap_element_link (head
, elt
);
1218 gcc_checking_assert (elt
->indx
== first_index
);
1219 elt_prev
= elt
->prev
;
1220 for (i
= first_index
; i
<= last_index
; i
++)
1222 unsigned elt_start_bit
= i
* BITMAP_ELEMENT_ALL_BITS
;
1223 unsigned elt_end_bit_plus1
= elt_start_bit
+ BITMAP_ELEMENT_ALL_BITS
;
1225 unsigned int first_word_to_mod
;
1226 BITMAP_WORD first_mask
;
1227 unsigned int last_word_to_mod
;
1228 BITMAP_WORD last_mask
;
1231 if (!elt
|| elt
->indx
!= i
)
1232 elt
= bitmap_elt_insert_after (head
, elt_prev
, i
);
1234 if (elt_start_bit
<= start
)
1236 /* The first bit to turn on is somewhere inside this
1238 first_word_to_mod
= (start
- elt_start_bit
) / BITMAP_WORD_BITS
;
1240 /* This mask should have 1s in all bits >= start position. */
1242 (((BITMAP_WORD
) 1) << ((start
% BITMAP_WORD_BITS
))) - 1;
1243 first_mask
= ~first_mask
;
1247 /* The first bit to turn on is below this start of this elt. */
1248 first_word_to_mod
= 0;
1249 first_mask
= ~(BITMAP_WORD
) 0;
1252 if (elt_end_bit_plus1
<= end_bit_plus1
)
1254 /* The last bit to turn on is beyond this elt. */
1255 last_word_to_mod
= BITMAP_ELEMENT_WORDS
- 1;
1256 last_mask
= ~(BITMAP_WORD
) 0;
1260 /* The last bit to turn on is inside to this elt. */
1262 (end_bit_plus1
- elt_start_bit
) / BITMAP_WORD_BITS
;
1264 /* The last mask should have 1s below the end bit. */
1266 (((BITMAP_WORD
) 1) << ((end_bit_plus1
% BITMAP_WORD_BITS
))) - 1;
1269 if (first_word_to_mod
== last_word_to_mod
)
1271 BITMAP_WORD mask
= first_mask
& last_mask
;
1272 elt
->bits
[first_word_to_mod
] |= mask
;
1276 elt
->bits
[first_word_to_mod
] |= first_mask
;
1277 if (BITMAP_ELEMENT_WORDS
> 2)
1278 for (ix
= first_word_to_mod
+ 1; ix
< last_word_to_mod
; ix
++)
1279 elt
->bits
[ix
] = ~(BITMAP_WORD
) 0;
1280 elt
->bits
[last_word_to_mod
] |= last_mask
;
1287 head
->current
= elt
? elt
: elt_prev
;
1288 head
->indx
= head
->current
->indx
;
1291 /* Clear COUNT bits from START in HEAD. */
1293 bitmap_clear_range (bitmap head
, unsigned int start
, unsigned int count
)
1295 unsigned int first_index
, end_bit_plus1
, last_index
;
1296 bitmap_element
*elt
;
1303 bitmap_clear_bit (head
, start
);
1307 first_index
= start
/ BITMAP_ELEMENT_ALL_BITS
;
1308 end_bit_plus1
= start
+ count
;
1309 last_index
= (end_bit_plus1
- 1) / BITMAP_ELEMENT_ALL_BITS
;
1310 elt
= bitmap_find_bit (head
, start
);
1312 /* If bitmap_find_bit returns zero, the current is the closest block
1313 to the result. If the current is less than first index, find the
1314 next one. Otherwise, just set elt to be current. */
1319 if (head
->indx
< first_index
)
1321 elt
= head
->current
->next
;
1326 elt
= head
->current
;
1332 while (elt
&& (elt
->indx
<= last_index
))
1334 bitmap_element
* next_elt
= elt
->next
;
1335 unsigned elt_start_bit
= (elt
->indx
) * BITMAP_ELEMENT_ALL_BITS
;
1336 unsigned elt_end_bit_plus1
= elt_start_bit
+ BITMAP_ELEMENT_ALL_BITS
;
1339 if (elt_start_bit
>= start
&& elt_end_bit_plus1
<= end_bit_plus1
)
1340 /* Get rid of the entire elt and go to the next one. */
1341 bitmap_element_free (head
, elt
);
1344 /* Going to have to knock out some bits in this elt. */
1345 unsigned int first_word_to_mod
;
1346 BITMAP_WORD first_mask
;
1347 unsigned int last_word_to_mod
;
1348 BITMAP_WORD last_mask
;
1352 if (elt_start_bit
<= start
)
1354 /* The first bit to turn off is somewhere inside this
1356 first_word_to_mod
= (start
- elt_start_bit
) / BITMAP_WORD_BITS
;
1358 /* This mask should have 1s in all bits >= start position. */
1360 (((BITMAP_WORD
) 1) << ((start
% BITMAP_WORD_BITS
))) - 1;
1361 first_mask
= ~first_mask
;
1365 /* The first bit to turn off is below this start of this elt. */
1366 first_word_to_mod
= 0;
1368 first_mask
= ~first_mask
;
1371 if (elt_end_bit_plus1
<= end_bit_plus1
)
1373 /* The last bit to turn off is beyond this elt. */
1374 last_word_to_mod
= BITMAP_ELEMENT_WORDS
- 1;
1376 last_mask
= ~last_mask
;
1380 /* The last bit to turn off is inside to this elt. */
1382 (end_bit_plus1
- elt_start_bit
) / BITMAP_WORD_BITS
;
1384 /* The last mask should have 1s below the end bit. */
1386 (((BITMAP_WORD
) 1) << (((end_bit_plus1
) % BITMAP_WORD_BITS
))) - 1;
1390 if (first_word_to_mod
== last_word_to_mod
)
1392 BITMAP_WORD mask
= first_mask
& last_mask
;
1393 elt
->bits
[first_word_to_mod
] &= ~mask
;
1397 elt
->bits
[first_word_to_mod
] &= ~first_mask
;
1398 if (BITMAP_ELEMENT_WORDS
> 2)
1399 for (i
= first_word_to_mod
+ 1; i
< last_word_to_mod
; i
++)
1401 elt
->bits
[last_word_to_mod
] &= ~last_mask
;
1403 for (i
= 0; i
< BITMAP_ELEMENT_WORDS
; i
++)
1409 /* Check to see if there are any bits left. */
1411 bitmap_element_free (head
, elt
);
1418 head
->current
= elt
;
1419 head
->indx
= head
->current
->indx
;
1426 bitmap_compl_and_into (bitmap a
, const_bitmap b
)
1428 bitmap_element
*a_elt
= a
->first
;
1429 const bitmap_element
*b_elt
= b
->first
;
1430 bitmap_element
*a_prev
= NULL
;
1431 bitmap_element
*next
;
1433 gcc_assert (a
!= b
);
1435 if (bitmap_empty_p (a
))
1440 if (bitmap_empty_p (b
))
1446 while (a_elt
|| b_elt
)
1448 if (!b_elt
|| (a_elt
&& a_elt
->indx
< b_elt
->indx
))
1450 /* A is before B. Remove A */
1452 a_prev
= a_elt
->prev
;
1453 bitmap_element_free (a
, a_elt
);
1456 else if (!a_elt
|| b_elt
->indx
< a_elt
->indx
)
1458 /* B is before A. Copy B. */
1459 next
= bitmap_elt_insert_after (a
, a_prev
, b_elt
->indx
);
1460 memcpy (next
->bits
, b_elt
->bits
, sizeof (next
->bits
));
1462 b_elt
= b_elt
->next
;
1466 /* Matching elts, generate A = ~A & B. */
1468 BITMAP_WORD ior
= 0;
1470 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1472 BITMAP_WORD cleared
= a_elt
->bits
[ix
] & b_elt
->bits
[ix
];
1473 BITMAP_WORD r
= b_elt
->bits
[ix
] ^ cleared
;
1475 a_elt
->bits
[ix
] = r
;
1480 bitmap_element_free (a
, a_elt
);
1484 b_elt
= b_elt
->next
;
1487 gcc_checking_assert (!a
->current
== !a
->first
1488 && (!a
->current
|| a
->indx
== a
->current
->indx
));
1493 /* Insert an element corresponding to A_ELT | B_ELT after DST_PREV,
1494 overwriting DST_ELT if non-NULL. CHANGED is true if the destination bitmap
1495 had already been changed; the new value of CHANGED is returned. */
1498 bitmap_elt_ior (bitmap dst
, bitmap_element
*dst_elt
, bitmap_element
*dst_prev
,
1499 const bitmap_element
*a_elt
, const bitmap_element
*b_elt
,
1502 gcc_assert (a_elt
|| b_elt
);
1504 if (a_elt
&& b_elt
&& a_elt
->indx
== b_elt
->indx
)
1506 /* Matching elts, generate A | B. */
1509 if (!changed
&& dst_elt
&& dst_elt
->indx
== a_elt
->indx
)
1511 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1513 BITMAP_WORD r
= a_elt
->bits
[ix
] | b_elt
->bits
[ix
];
1514 if (r
!= dst_elt
->bits
[ix
])
1516 dst_elt
->bits
[ix
] = r
;
1525 dst_elt
= bitmap_elt_insert_after (dst
, dst_prev
, a_elt
->indx
);
1527 dst_elt
->indx
= a_elt
->indx
;
1528 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1530 BITMAP_WORD r
= a_elt
->bits
[ix
] | b_elt
->bits
[ix
];
1531 dst_elt
->bits
[ix
] = r
;
1537 /* Copy a single element. */
1538 const bitmap_element
*src
;
1540 if (!b_elt
|| (a_elt
&& a_elt
->indx
< b_elt
->indx
))
1545 gcc_checking_assert (src
);
1546 changed
= bitmap_elt_copy (dst
, dst_elt
, dst_prev
, src
, changed
);
1552 /* DST = A | B. Return true if DST changes. */
1555 bitmap_ior (bitmap dst
, const_bitmap a
, const_bitmap b
)
1557 bitmap_element
*dst_elt
= dst
->first
;
1558 const bitmap_element
*a_elt
= a
->first
;
1559 const bitmap_element
*b_elt
= b
->first
;
1560 bitmap_element
*dst_prev
= NULL
;
1561 bitmap_element
**dst_prev_pnext
= &dst
->first
;
1562 bool changed
= false;
1564 gcc_assert (dst
!= a
&& dst
!= b
);
1566 while (a_elt
|| b_elt
)
1568 changed
= bitmap_elt_ior (dst
, dst_elt
, dst_prev
, a_elt
, b_elt
, changed
);
1570 if (a_elt
&& b_elt
&& a_elt
->indx
== b_elt
->indx
)
1572 a_elt
= a_elt
->next
;
1573 b_elt
= b_elt
->next
;
1577 if (a_elt
&& (!b_elt
|| a_elt
->indx
<= b_elt
->indx
))
1578 a_elt
= a_elt
->next
;
1579 else if (b_elt
&& (!a_elt
|| b_elt
->indx
<= a_elt
->indx
))
1580 b_elt
= b_elt
->next
;
1583 dst_prev
= *dst_prev_pnext
;
1584 dst_prev_pnext
= &dst_prev
->next
;
1585 dst_elt
= *dst_prev_pnext
;
1591 /* Ensure that dst->current is valid. */
1592 dst
->current
= dst
->first
;
1593 bitmap_elt_clear_from (dst
, dst_elt
);
1595 gcc_checking_assert (!dst
->current
== !dst
->first
);
1597 dst
->indx
= dst
->current
->indx
;
1601 /* A |= B. Return true if A changes. */
1604 bitmap_ior_into (bitmap a
, const_bitmap b
)
1606 bitmap_element
*a_elt
= a
->first
;
1607 const bitmap_element
*b_elt
= b
->first
;
1608 bitmap_element
*a_prev
= NULL
;
1609 bitmap_element
**a_prev_pnext
= &a
->first
;
1610 bool changed
= false;
1617 /* If A lags behind B, just advance it. */
1618 if (!a_elt
|| a_elt
->indx
== b_elt
->indx
)
1620 changed
= bitmap_elt_ior (a
, a_elt
, a_prev
, a_elt
, b_elt
, changed
);
1621 b_elt
= b_elt
->next
;
1623 else if (a_elt
->indx
> b_elt
->indx
)
1625 changed
= bitmap_elt_copy (a
, NULL
, a_prev
, b_elt
, changed
);
1626 b_elt
= b_elt
->next
;
1629 a_prev
= *a_prev_pnext
;
1630 a_prev_pnext
= &a_prev
->next
;
1631 a_elt
= *a_prev_pnext
;
1634 gcc_checking_assert (!a
->current
== !a
->first
);
1636 a
->indx
= a
->current
->indx
;
1643 bitmap_xor (bitmap dst
, const_bitmap a
, const_bitmap b
)
1645 bitmap_element
*dst_elt
= dst
->first
;
1646 const bitmap_element
*a_elt
= a
->first
;
1647 const bitmap_element
*b_elt
= b
->first
;
1648 bitmap_element
*dst_prev
= NULL
;
1650 gcc_assert (dst
!= a
&& dst
!= b
);
1657 while (a_elt
|| b_elt
)
1659 if (a_elt
&& b_elt
&& a_elt
->indx
== b_elt
->indx
)
1661 /* Matching elts, generate A ^ B. */
1663 BITMAP_WORD ior
= 0;
1666 dst_elt
= bitmap_elt_insert_after (dst
, dst_prev
, a_elt
->indx
);
1668 dst_elt
->indx
= a_elt
->indx
;
1669 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1671 BITMAP_WORD r
= a_elt
->bits
[ix
] ^ b_elt
->bits
[ix
];
1674 dst_elt
->bits
[ix
] = r
;
1676 a_elt
= a_elt
->next
;
1677 b_elt
= b_elt
->next
;
1681 dst_elt
= dst_elt
->next
;
1686 /* Copy a single element. */
1687 const bitmap_element
*src
;
1689 if (!b_elt
|| (a_elt
&& a_elt
->indx
< b_elt
->indx
))
1692 a_elt
= a_elt
->next
;
1697 b_elt
= b_elt
->next
;
1701 dst_elt
= bitmap_elt_insert_after (dst
, dst_prev
, src
->indx
);
1703 dst_elt
->indx
= src
->indx
;
1704 memcpy (dst_elt
->bits
, src
->bits
, sizeof (dst_elt
->bits
));
1706 dst_elt
= dst_elt
->next
;
1709 /* Ensure that dst->current is valid. */
1710 dst
->current
= dst
->first
;
1711 bitmap_elt_clear_from (dst
, dst_elt
);
1712 gcc_checking_assert (!dst
->current
== !dst
->first
);
1714 dst
->indx
= dst
->current
->indx
;
1720 bitmap_xor_into (bitmap a
, const_bitmap b
)
1722 bitmap_element
*a_elt
= a
->first
;
1723 const bitmap_element
*b_elt
= b
->first
;
1724 bitmap_element
*a_prev
= NULL
;
1734 if (!a_elt
|| b_elt
->indx
< a_elt
->indx
)
1737 bitmap_element
*dst
= bitmap_elt_insert_after (a
, a_prev
, b_elt
->indx
);
1738 memcpy (dst
->bits
, b_elt
->bits
, sizeof (dst
->bits
));
1740 b_elt
= b_elt
->next
;
1742 else if (a_elt
->indx
< b_elt
->indx
)
1745 a_elt
= a_elt
->next
;
1749 /* Matching elts, generate A ^= B. */
1751 BITMAP_WORD ior
= 0;
1752 bitmap_element
*next
= a_elt
->next
;
1754 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1756 BITMAP_WORD r
= a_elt
->bits
[ix
] ^ b_elt
->bits
[ix
];
1759 a_elt
->bits
[ix
] = r
;
1761 b_elt
= b_elt
->next
;
1765 bitmap_element_free (a
, a_elt
);
1769 gcc_checking_assert (!a
->current
== !a
->first
);
1771 a
->indx
= a
->current
->indx
;
1774 /* Return true if two bitmaps are identical.
1775 We do not bother with a check for pointer equality, as that never
1776 occurs in practice. */
1779 bitmap_equal_p (const_bitmap a
, const_bitmap b
)
1781 const bitmap_element
*a_elt
;
1782 const bitmap_element
*b_elt
;
1785 for (a_elt
= a
->first
, b_elt
= b
->first
;
1787 a_elt
= a_elt
->next
, b_elt
= b_elt
->next
)
1789 if (a_elt
->indx
!= b_elt
->indx
)
1791 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1792 if (a_elt
->bits
[ix
] != b_elt
->bits
[ix
])
1795 return !a_elt
&& !b_elt
;
1798 /* Return true if A AND B is not empty. */
1801 bitmap_intersect_p (const_bitmap a
, const_bitmap b
)
1803 const bitmap_element
*a_elt
;
1804 const bitmap_element
*b_elt
;
1807 for (a_elt
= a
->first
, b_elt
= b
->first
;
1810 if (a_elt
->indx
< b_elt
->indx
)
1811 a_elt
= a_elt
->next
;
1812 else if (b_elt
->indx
< a_elt
->indx
)
1813 b_elt
= b_elt
->next
;
1816 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1817 if (a_elt
->bits
[ix
] & b_elt
->bits
[ix
])
1819 a_elt
= a_elt
->next
;
1820 b_elt
= b_elt
->next
;
1826 /* Return true if A AND NOT B is not empty. */
1829 bitmap_intersect_compl_p (const_bitmap a
, const_bitmap b
)
1831 const bitmap_element
*a_elt
;
1832 const bitmap_element
*b_elt
;
1834 for (a_elt
= a
->first
, b_elt
= b
->first
;
1837 if (a_elt
->indx
< b_elt
->indx
)
1839 else if (b_elt
->indx
< a_elt
->indx
)
1840 b_elt
= b_elt
->next
;
1843 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1844 if (a_elt
->bits
[ix
] & ~b_elt
->bits
[ix
])
1846 a_elt
= a_elt
->next
;
1847 b_elt
= b_elt
->next
;
1850 return a_elt
!= NULL
;
1854 /* DST = A | (FROM1 & ~FROM2). Return true if DST changes. */
1857 bitmap_ior_and_compl (bitmap dst
, const_bitmap a
, const_bitmap b
, const_bitmap kill
)
1859 bool changed
= false;
1861 bitmap_element
*dst_elt
= dst
->first
;
1862 const bitmap_element
*a_elt
= a
->first
;
1863 const bitmap_element
*b_elt
= b
->first
;
1864 const bitmap_element
*kill_elt
= kill
->first
;
1865 bitmap_element
*dst_prev
= NULL
;
1866 bitmap_element
**dst_prev_pnext
= &dst
->first
;
1868 gcc_assert (dst
!= a
&& dst
!= b
&& dst
!= kill
);
1870 /* Special cases. We don't bother checking for bitmap_equal_p (b, kill). */
1871 if (b
== kill
|| bitmap_empty_p (b
))
1873 changed
= !bitmap_equal_p (dst
, a
);
1875 bitmap_copy (dst
, a
);
1878 if (bitmap_empty_p (kill
))
1879 return bitmap_ior (dst
, a
, b
);
1880 if (bitmap_empty_p (a
))
1881 return bitmap_and_compl (dst
, b
, kill
);
1883 while (a_elt
|| b_elt
)
1885 bool new_element
= false;
1888 while (kill_elt
&& kill_elt
->indx
< b_elt
->indx
)
1889 kill_elt
= kill_elt
->next
;
1891 if (b_elt
&& kill_elt
&& kill_elt
->indx
== b_elt
->indx
1892 && (!a_elt
|| a_elt
->indx
>= b_elt
->indx
))
1894 bitmap_element tmp_elt
;
1897 BITMAP_WORD ior
= 0;
1898 tmp_elt
.indx
= b_elt
->indx
;
1899 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1901 BITMAP_WORD r
= b_elt
->bits
[ix
] & ~kill_elt
->bits
[ix
];
1903 tmp_elt
.bits
[ix
] = r
;
1908 changed
= bitmap_elt_ior (dst
, dst_elt
, dst_prev
,
1909 a_elt
, &tmp_elt
, changed
);
1911 if (a_elt
&& a_elt
->indx
== b_elt
->indx
)
1912 a_elt
= a_elt
->next
;
1915 b_elt
= b_elt
->next
;
1916 kill_elt
= kill_elt
->next
;
1920 changed
= bitmap_elt_ior (dst
, dst_elt
, dst_prev
,
1921 a_elt
, b_elt
, changed
);
1924 if (a_elt
&& b_elt
&& a_elt
->indx
== b_elt
->indx
)
1926 a_elt
= a_elt
->next
;
1927 b_elt
= b_elt
->next
;
1931 if (a_elt
&& (!b_elt
|| a_elt
->indx
<= b_elt
->indx
))
1932 a_elt
= a_elt
->next
;
1933 else if (b_elt
&& (!a_elt
|| b_elt
->indx
<= a_elt
->indx
))
1934 b_elt
= b_elt
->next
;
1940 dst_prev
= *dst_prev_pnext
;
1941 dst_prev_pnext
= &dst_prev
->next
;
1942 dst_elt
= *dst_prev_pnext
;
1949 /* Ensure that dst->current is valid. */
1950 dst
->current
= dst
->first
;
1951 bitmap_elt_clear_from (dst
, dst_elt
);
1953 gcc_checking_assert (!dst
->current
== !dst
->first
);
1955 dst
->indx
= dst
->current
->indx
;
1960 /* A |= (FROM1 & ~FROM2). Return true if A changes. */
1963 bitmap_ior_and_compl_into (bitmap a
, const_bitmap from1
, const_bitmap from2
)
1968 bitmap_initialize (&tmp
, &bitmap_default_obstack
);
1969 bitmap_and_compl (&tmp
, from1
, from2
);
1970 changed
= bitmap_ior_into (a
, &tmp
);
1971 bitmap_clear (&tmp
);
1976 /* A |= (B & C). Return true if A changes. */
1979 bitmap_ior_and_into (bitmap a
, const_bitmap b
, const_bitmap c
)
1981 bitmap_element
*a_elt
= a
->first
;
1982 const bitmap_element
*b_elt
= b
->first
;
1983 const bitmap_element
*c_elt
= c
->first
;
1984 bitmap_element and_elt
;
1985 bitmap_element
*a_prev
= NULL
;
1986 bitmap_element
**a_prev_pnext
= &a
->first
;
1987 bool changed
= false;
1991 return bitmap_ior_into (a
, b
);
1992 if (bitmap_empty_p (b
) || bitmap_empty_p (c
))
1996 while (b_elt
&& c_elt
)
1998 BITMAP_WORD overall
;
2000 /* Find a common item of B and C. */
2001 while (b_elt
->indx
!= c_elt
->indx
)
2003 if (b_elt
->indx
< c_elt
->indx
)
2005 b_elt
= b_elt
->next
;
2011 c_elt
= c_elt
->next
;
2018 and_elt
.indx
= b_elt
->indx
;
2019 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
2021 and_elt
.bits
[ix
] = b_elt
->bits
[ix
] & c_elt
->bits
[ix
];
2022 overall
|= and_elt
.bits
[ix
];
2025 b_elt
= b_elt
->next
;
2026 c_elt
= c_elt
->next
;
2030 /* Now find a place to insert AND_ELT. */
2033 ix
= a_elt
? a_elt
->indx
: and_elt
.indx
;
2034 if (ix
== and_elt
.indx
)
2035 changed
= bitmap_elt_ior (a
, a_elt
, a_prev
, a_elt
, &and_elt
, changed
);
2036 else if (ix
> and_elt
.indx
)
2037 changed
= bitmap_elt_copy (a
, NULL
, a_prev
, &and_elt
, changed
);
2039 a_prev
= *a_prev_pnext
;
2040 a_prev_pnext
= &a_prev
->next
;
2041 a_elt
= *a_prev_pnext
;
2043 /* If A lagged behind B/C, we advanced it so loop once more. */
2045 while (ix
< and_elt
.indx
);
2049 gcc_checking_assert (!a
->current
== !a
->first
);
2051 a
->indx
= a
->current
->indx
;
2055 /* Compute hash of bitmap (for purposes of hashing). */
2057 bitmap_hash (const_bitmap head
)
2059 const bitmap_element
*ptr
;
2060 BITMAP_WORD hash
= 0;
2063 for (ptr
= head
->first
; ptr
; ptr
= ptr
->next
)
2066 for (ix
= 0; ix
!= BITMAP_ELEMENT_WORDS
; ix
++)
2067 hash
^= ptr
->bits
[ix
];
2069 return (hashval_t
)hash
;
2073 /* Debugging function to print out the contents of a bitmap. */
2076 debug_bitmap_file (FILE *file
, const_bitmap head
)
2078 const bitmap_element
*ptr
;
2080 fprintf (file
, "\nfirst = " HOST_PTR_PRINTF
2081 " current = " HOST_PTR_PRINTF
" indx = %u\n",
2082 (void *) head
->first
, (void *) head
->current
, head
->indx
);
2084 for (ptr
= head
->first
; ptr
; ptr
= ptr
->next
)
2086 unsigned int i
, j
, col
= 26;
2088 fprintf (file
, "\t" HOST_PTR_PRINTF
" next = " HOST_PTR_PRINTF
2089 " prev = " HOST_PTR_PRINTF
" indx = %u\n\t\tbits = {",
2090 (const void*) ptr
, (const void*) ptr
->next
,
2091 (const void*) ptr
->prev
, ptr
->indx
);
2093 for (i
= 0; i
< BITMAP_ELEMENT_WORDS
; i
++)
2094 for (j
= 0; j
< BITMAP_WORD_BITS
; j
++)
2095 if ((ptr
->bits
[i
] >> j
) & 1)
2099 fprintf (file
, "\n\t\t\t");
2103 fprintf (file
, " %u", (ptr
->indx
* BITMAP_ELEMENT_ALL_BITS
2104 + i
* BITMAP_WORD_BITS
+ j
));
2108 fprintf (file
, " }\n");
2112 /* Function to be called from the debugger to print the contents
2116 debug_bitmap (const_bitmap head
)
2118 debug_bitmap_file (stderr
, head
);
2121 /* Function to print out the contents of a bitmap. Unlike debug_bitmap_file,
2122 it does not print anything but the bits. */
2125 bitmap_print (FILE *file
, const_bitmap head
, const char *prefix
,
2128 const char *comma
= "";
2132 fputs (prefix
, file
);
2133 EXECUTE_IF_SET_IN_BITMAP (head
, 0, i
, bi
)
2135 fprintf (file
, "%s%d", comma
, i
);
2138 fputs (suffix
, file
);
2141 /* Output per-bitmap memory usage statistics. */
2143 dump_bitmap_statistics (void)
2145 if (!GATHER_STATISTICS
)
2148 bitmap_mem_desc
.dump (BITMAP_ORIGIN
);
2152 debug (const bitmap_head
&ref
)
2154 dump_bitmap (stderr
, &ref
);
2158 debug (const bitmap_head
*ptr
)
2163 fprintf (stderr
, "<nil>\n");
2168 namespace selftest
{
2170 /* Selftests for bitmaps. */
2172 /* Freshly-created bitmaps ought to be empty. */
2177 bitmap b
= bitmap_gc_alloc ();
2178 ASSERT_TRUE (bitmap_empty_p (b
));
2181 /* Verify bitmap_set_range. */
2186 bitmap b
= bitmap_gc_alloc ();
2187 ASSERT_TRUE (bitmap_empty_p (b
));
2189 bitmap_set_range (b
, 7, 5);
2190 ASSERT_FALSE (bitmap_empty_p (b
));
2191 ASSERT_EQ (5, bitmap_count_bits (b
));
2193 /* Verify bitmap_bit_p at the boundaries. */
2194 ASSERT_FALSE (bitmap_bit_p (b
, 6));
2195 ASSERT_TRUE (bitmap_bit_p (b
, 7));
2196 ASSERT_TRUE (bitmap_bit_p (b
, 11));
2197 ASSERT_FALSE (bitmap_bit_p (b
, 12));
2200 /* Verify splitting a range into two pieces using bitmap_clear_bit. */
2203 test_clear_bit_in_middle ()
2205 bitmap b
= bitmap_gc_alloc ();
2207 /* Set b to [100..200]. */
2208 bitmap_set_range (b
, 100, 100);
2209 ASSERT_EQ (100, bitmap_count_bits (b
));
2211 /* Clear a bit in the middle. */
2212 bool changed
= bitmap_clear_bit (b
, 150);
2213 ASSERT_TRUE (changed
);
2214 ASSERT_EQ (99, bitmap_count_bits (b
));
2215 ASSERT_TRUE (bitmap_bit_p (b
, 149));
2216 ASSERT_FALSE (bitmap_bit_p (b
, 150));
2217 ASSERT_TRUE (bitmap_bit_p (b
, 151));
2220 /* Verify bitmap_copy. */
2225 bitmap src
= bitmap_gc_alloc ();
2226 bitmap_set_range (src
, 40, 10);
2228 bitmap dst
= bitmap_gc_alloc ();
2229 ASSERT_FALSE (bitmap_equal_p (src
, dst
));
2230 bitmap_copy (dst
, src
);
2231 ASSERT_TRUE (bitmap_equal_p (src
, dst
));
2233 /* Verify that we can make them unequal again... */
2234 bitmap_set_range (src
, 70, 5);
2235 ASSERT_FALSE (bitmap_equal_p (src
, dst
));
2237 /* ...and that changing src after the copy didn't affect
2239 ASSERT_FALSE (bitmap_bit_p (dst
, 70));
2242 /* Verify bitmap_single_bit_set_p. */
2245 test_bitmap_single_bit_set_p ()
2247 bitmap b
= bitmap_gc_alloc ();
2249 ASSERT_FALSE (bitmap_single_bit_set_p (b
));
2251 bitmap_set_range (b
, 42, 1);
2252 ASSERT_TRUE (bitmap_single_bit_set_p (b
));
2253 ASSERT_EQ (42, bitmap_first_set_bit (b
));
2255 bitmap_set_range (b
, 1066, 1);
2256 ASSERT_FALSE (bitmap_single_bit_set_p (b
));
2257 ASSERT_EQ (42, bitmap_first_set_bit (b
));
2259 bitmap_clear_range (b
, 0, 100);
2260 ASSERT_TRUE (bitmap_single_bit_set_p (b
));
2261 ASSERT_EQ (1066, bitmap_first_set_bit (b
));
2264 /* Run all of the selftests within this file. */
2271 test_clear_bit_in_middle ();
2273 test_bitmap_single_bit_set_p ();
2276 } // namespace selftest
2277 #endif /* CHECKING_P */
2279 #include "gt-bitmap.h"