1 /* Functions to support general ended bitmaps.
2 Copyright (C) 1997-2021 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 /* Static zero-initialized bitmap obstack used for default initialization
31 bitmap_obstack
bitmap_head::crashme
;
33 static bitmap_element
*bitmap_tree_listify_from (bitmap
, bitmap_element
*);
35 /* Register new bitmap. */
37 bitmap_register (bitmap b MEM_STAT_DECL
)
39 static unsigned alloc_descriptor_max_uid
= 1;
40 gcc_assert (b
->alloc_descriptor
== 0);
41 b
->alloc_descriptor
= alloc_descriptor_max_uid
++;
43 bitmap_mem_desc
.register_descriptor (b
->get_descriptor (), BITMAP_ORIGIN
,
44 false FINAL_PASS_MEM_STAT
);
47 /* Account the overhead. */
49 register_overhead (bitmap b
, size_t amount
)
51 unsigned *d
= b
->get_descriptor ();
52 if (bitmap_mem_desc
.contains_descriptor_for_instance (d
))
53 bitmap_mem_desc
.register_instance_overhead (amount
, d
);
56 /* Release the overhead. */
58 release_overhead (bitmap b
, size_t amount
, bool remove_from_map
)
60 unsigned *d
= b
->get_descriptor ();
61 if (bitmap_mem_desc
.contains_descriptor_for_instance (d
))
62 bitmap_mem_desc
.release_instance_overhead (d
, amount
, remove_from_map
);
67 bitmap_element bitmap_zero_bits
; /* An element of all zero bits. */
68 bitmap_obstack bitmap_default_obstack
; /* The default bitmap obstack. */
69 static int bitmap_default_obstack_depth
;
70 static GTY((deletable
)) bitmap_element
*bitmap_ggc_free
; /* Freelist of
74 /* Bitmap memory management. */
76 /* Add ELT to the appropriate freelist. */
78 bitmap_elem_to_freelist (bitmap head
, bitmap_element
*elt
)
80 bitmap_obstack
*bit_obstack
= head
->obstack
;
82 if (GATHER_STATISTICS
)
83 release_overhead (head
, sizeof (bitmap_element
), false);
89 elt
->prev
= bit_obstack
->elements
;
90 bit_obstack
->elements
= elt
;
94 elt
->prev
= bitmap_ggc_free
;
95 bitmap_ggc_free
= elt
;
99 /* Allocate a bitmap element. The bits are cleared, but nothing else is. */
101 static inline bitmap_element
*
102 bitmap_element_allocate (bitmap head
)
104 bitmap_element
*element
;
105 bitmap_obstack
*bit_obstack
= head
->obstack
;
109 element
= bit_obstack
->elements
;
112 /* Use up the inner list first before looking at the next
113 element of the outer list. */
116 bit_obstack
->elements
= element
->next
;
117 bit_obstack
->elements
->prev
= element
->prev
;
120 /* Inner list was just a singleton. */
121 bit_obstack
->elements
= element
->prev
;
123 element
= XOBNEW (&bit_obstack
->obstack
, bitmap_element
);
127 element
= bitmap_ggc_free
;
129 /* Use up the inner list first before looking at the next
130 element of the outer list. */
133 bitmap_ggc_free
= element
->next
;
134 bitmap_ggc_free
->prev
= element
->prev
;
137 /* Inner list was just a singleton. */
138 bitmap_ggc_free
= element
->prev
;
140 element
= ggc_alloc
<bitmap_element
> ();
143 if (GATHER_STATISTICS
)
144 register_overhead (head
, sizeof (bitmap_element
));
146 memset (element
->bits
, 0, sizeof (element
->bits
));
151 /* Remove ELT and all following elements from bitmap HEAD.
152 Put the released elements in the freelist for HEAD. */
155 bitmap_elt_clear_from (bitmap head
, bitmap_element
*elt
)
157 bitmap_element
*prev
;
158 bitmap_obstack
*bit_obstack
= head
->obstack
;
164 elt
= bitmap_tree_listify_from (head
, elt
);
166 if (GATHER_STATISTICS
)
169 for (prev
= elt
; prev
; prev
= prev
->next
)
171 release_overhead (head
, sizeof (bitmap_element
) * n
, false);
178 if (head
->current
->indx
> prev
->indx
)
180 head
->current
= prev
;
181 head
->indx
= prev
->indx
;
187 head
->current
= NULL
;
191 /* Put the entire list onto the freelist in one operation. */
194 elt
->prev
= bit_obstack
->elements
;
195 bit_obstack
->elements
= elt
;
199 elt
->prev
= bitmap_ggc_free
;
200 bitmap_ggc_free
= elt
;
204 /* Linked-list view of bitmaps.
206 In this representation, the bitmap elements form a double-linked list
207 with elements sorted by increasing index. */
209 /* Link the bitmap element into the current bitmap linked list. */
212 bitmap_list_link_element (bitmap head
, bitmap_element
*element
)
214 unsigned int indx
= element
->indx
;
217 gcc_checking_assert (!head
->tree_form
);
219 /* If this is the first and only element, set it in. */
220 if (head
->first
== 0)
222 element
->next
= element
->prev
= 0;
223 head
->first
= element
;
226 /* If this index is less than that of the current element, it goes someplace
227 before the current element. */
228 else if (indx
< head
->indx
)
230 for (ptr
= head
->current
;
231 ptr
->prev
!= 0 && ptr
->prev
->indx
> indx
;
236 ptr
->prev
->next
= element
;
238 head
->first
= element
;
240 element
->prev
= ptr
->prev
;
245 /* Otherwise, it must go someplace after the current element. */
248 for (ptr
= head
->current
;
249 ptr
->next
!= 0 && ptr
->next
->indx
< indx
;
254 ptr
->next
->prev
= element
;
256 element
->next
= ptr
->next
;
261 /* Set up so this is the first element searched. */
262 head
->current
= element
;
266 /* Unlink the bitmap element from the current bitmap linked list,
267 and return it to the freelist. */
270 bitmap_list_unlink_element (bitmap head
, bitmap_element
*element
,
271 bool to_freelist
= true)
273 bitmap_element
*next
= element
->next
;
274 bitmap_element
*prev
= element
->prev
;
276 gcc_checking_assert (!head
->tree_form
);
284 if (head
->first
== element
)
287 /* Since the first thing we try is to insert before current,
288 make current the next entry in preference to the previous. */
289 if (head
->current
== element
)
291 head
->current
= next
!= 0 ? next
: prev
;
293 head
->indx
= head
->current
->indx
;
299 bitmap_elem_to_freelist (head
, element
);
302 /* Insert a new uninitialized element (or NODE if not NULL) into bitmap
303 HEAD after element ELT. If ELT is NULL, insert the element at the start.
304 Return the new element. */
306 static bitmap_element
*
307 bitmap_list_insert_element_after (bitmap head
,
308 bitmap_element
*elt
, unsigned int indx
,
309 bitmap_element
*node
= NULL
)
312 node
= bitmap_element_allocate (head
);
315 gcc_checking_assert (!head
->tree_form
);
321 head
->current
= node
;
324 node
->next
= head
->first
;
326 node
->next
->prev
= node
;
332 gcc_checking_assert (head
->current
);
333 node
->next
= elt
->next
;
335 node
->next
->prev
= node
;
342 /* Return the element for INDX, or NULL if the element doesn't exist.
343 Update the `current' field even if we can't find an element that
344 would hold the bitmap's bit to make eventual allocation
347 static inline bitmap_element
*
348 bitmap_list_find_element (bitmap head
, unsigned int indx
)
350 bitmap_element
*element
;
352 if (head
->current
== NULL
353 || head
->indx
== indx
)
354 return head
->current
;
356 if (head
->current
== head
->first
357 && head
->first
->next
== NULL
)
360 /* Usage can be NULL due to allocated bitmaps for which we do not
361 call initialize function. */
362 bitmap_usage
*usage
= NULL
;
363 if (GATHER_STATISTICS
)
364 usage
= bitmap_mem_desc
.get_descriptor_for_instance (head
);
366 /* This bitmap has more than one element, and we're going to look
367 through the elements list. Count that as a search. */
368 if (GATHER_STATISTICS
&& usage
)
369 usage
->m_nsearches
++;
371 if (head
->indx
< indx
)
372 /* INDX is beyond head->indx. Search from head->current
374 for (element
= head
->current
;
375 element
->next
!= 0 && element
->indx
< indx
;
376 element
= element
->next
)
378 if (GATHER_STATISTICS
&& usage
)
379 usage
->m_search_iter
++;
382 else if (head
->indx
/ 2 < indx
)
383 /* INDX is less than head->indx and closer to head->indx than to
384 0. Search from head->current backward. */
385 for (element
= head
->current
;
386 element
->prev
!= 0 && element
->indx
> indx
;
387 element
= element
->prev
)
389 if (GATHER_STATISTICS
&& usage
)
390 usage
->m_search_iter
++;
394 /* INDX is less than head->indx and closer to 0 than to
395 head->indx. Search from head->first forward. */
396 for (element
= head
->first
;
397 element
->next
!= 0 && element
->indx
< indx
;
398 element
= element
->next
)
400 if (GATHER_STATISTICS
&& usage
)
401 usage
->m_search_iter
++;
404 /* `element' is the nearest to the one we want. If it's not the one we
405 want, the one we want doesn't exist. */
406 gcc_checking_assert (element
!= NULL
);
407 head
->current
= element
;
408 head
->indx
= element
->indx
;
409 if (element
->indx
!= indx
)
415 /* Splay-tree view of bitmaps.
417 This is an almost one-to-one the implementatin of the simple top-down
418 splay tree in Sleator and Tarjan's "Self-adjusting Binary Search Trees".
419 It is probably not the most efficient form of splay trees, but it should
420 be good enough to experiment with this idea of bitmaps-as-trees.
422 For all functions below, the variable or function argument "t" is a node
423 in the tree, and "e" is a temporary or new node in the tree. The rest
424 is sufficiently straigh-forward (and very well explained in the paper)
425 that comment would only clutter things. */
428 bitmap_tree_link_left (bitmap_element
* &t
, bitmap_element
* &l
)
436 bitmap_tree_link_right (bitmap_element
* &t
, bitmap_element
* &r
)
444 bitmap_tree_rotate_left (bitmap_element
* &t
)
446 bitmap_element
*e
= t
->next
;
447 t
->next
= t
->next
->prev
;
453 bitmap_tree_rotate_right (bitmap_element
* &t
)
455 bitmap_element
*e
= t
->prev
;
456 t
->prev
= t
->prev
->next
;
461 static bitmap_element
*
462 bitmap_tree_splay (bitmap head
, bitmap_element
*t
, unsigned int indx
)
464 bitmap_element N
, *l
, *r
;
469 bitmap_usage
*usage
= NULL
;
470 if (GATHER_STATISTICS
)
471 usage
= bitmap_mem_desc
.get_descriptor_for_instance (head
);
473 N
.prev
= N
.next
= NULL
;
476 while (indx
!= t
->indx
)
478 if (GATHER_STATISTICS
&& usage
)
479 usage
->m_search_iter
++;
483 if (t
->prev
!= NULL
&& indx
< t
->prev
->indx
)
484 bitmap_tree_rotate_right (t
);
487 bitmap_tree_link_right (t
, r
);
489 else if (indx
> t
->indx
)
491 if (t
->next
!= NULL
&& indx
> t
->next
->indx
)
492 bitmap_tree_rotate_left (t
);
495 bitmap_tree_link_left (t
, l
);
506 /* Link bitmap element E into the current bitmap splay tree. */
509 bitmap_tree_link_element (bitmap head
, bitmap_element
*e
)
511 if (head
->first
== NULL
)
512 e
->prev
= e
->next
= NULL
;
515 bitmap_element
*t
= bitmap_tree_splay (head
, head
->first
, e
->indx
);
516 if (e
->indx
< t
->indx
)
522 else if (e
->indx
> t
->indx
)
533 head
->indx
= e
->indx
;
536 /* Unlink bitmap element E from the current bitmap splay tree,
537 and return it to the freelist. */
540 bitmap_tree_unlink_element (bitmap head
, bitmap_element
*e
)
542 bitmap_element
*t
= bitmap_tree_splay (head
, head
->first
, e
->indx
);
544 gcc_checking_assert (t
== e
);
550 t
= bitmap_tree_splay (head
, e
->prev
, e
->indx
);
555 head
->indx
= (t
!= NULL
) ? t
->indx
: 0;
557 bitmap_elem_to_freelist (head
, e
);
560 /* Return the element for INDX, or NULL if the element doesn't exist. */
562 static inline bitmap_element
*
563 bitmap_tree_find_element (bitmap head
, unsigned int indx
)
565 if (head
->current
== NULL
566 || head
->indx
== indx
)
567 return head
->current
;
569 /* Usage can be NULL due to allocated bitmaps for which we do not
570 call initialize function. */
571 bitmap_usage
*usage
= NULL
;
572 if (GATHER_STATISTICS
)
573 usage
= bitmap_mem_desc
.get_descriptor_for_instance (head
);
575 /* This bitmap has more than one element, and we're going to look
576 through the elements list. Count that as a search. */
577 if (GATHER_STATISTICS
&& usage
)
578 usage
->m_nsearches
++;
580 bitmap_element
*element
= bitmap_tree_splay (head
, head
->first
, indx
);
581 gcc_checking_assert (element
!= NULL
);
582 head
->first
= element
;
583 head
->current
= element
;
584 head
->indx
= element
->indx
;
585 if (element
->indx
!= indx
)
590 /* Converting bitmap views from linked-list to tree and vice versa. */
592 /* Splice element E and all elements with a larger index from
593 bitmap HEAD, convert the spliced elements to the linked-list
594 view, and return the head of the list (which should be E again), */
596 static bitmap_element
*
597 bitmap_tree_listify_from (bitmap head
, bitmap_element
*e
)
599 bitmap_element
*t
, *erb
;
601 /* Detach the right branch from E (all elements with indx > E->indx),
602 and splay E to the root. */
605 t
= bitmap_tree_splay (head
, head
->first
, e
->indx
);
606 gcc_checking_assert (t
== e
);
608 /* Because E has no right branch, and we rotated it to the root,
609 the left branch is the new root. */
613 head
->indx
= (t
!= NULL
) ? t
->indx
: 0;
615 /* Detach the tree from E, and re-attach the right branch of E. */
619 /* The tree is now valid again. Now we need to "un-tree" E.
620 It is imperative that a non-recursive implementation is used
621 for this, because splay trees have a worst case depth of O(N)
622 for a tree with N nodes. A recursive implementation could
623 result in a stack overflow for a sufficiently large, unbalanced
626 auto_vec
<bitmap_element
*, 32> stack
;
627 auto_vec
<bitmap_element
*, 32> sorted_elements
;
628 bitmap_element
*n
= e
;
638 if (stack
.is_empty ())
642 sorted_elements
.safe_push (n
);
646 gcc_assert (sorted_elements
[0] == e
);
648 bitmap_element
*prev
= NULL
;
650 FOR_EACH_VEC_ELT (sorted_elements
, ix
, n
)
662 /* Convert bitmap HEAD from splay-tree view to linked-list view. */
665 bitmap_list_view (bitmap head
)
669 gcc_assert (head
->tree_form
);
675 bitmap_tree_rotate_right (ptr
);
677 head
->first
= bitmap_tree_listify_from (head
, ptr
);
680 head
->tree_form
= false;
683 head
->current
= head
->first
;
684 head
->indx
= head
->current
? head
->current
->indx
: 0;
688 /* Convert bitmap HEAD from linked-list view to splay-tree view.
689 This is simply a matter of dropping the prev or next pointers
690 and setting the tree_form flag. The tree will balance itself
691 if and when it is used. */
694 bitmap_tree_view (bitmap head
)
698 gcc_assert (! head
->tree_form
);
707 head
->tree_form
= true;
710 /* Clear a bitmap by freeing all its elements. */
713 bitmap_clear (bitmap head
)
715 if (head
->first
== NULL
)
719 bitmap_element
*e
, *t
;
720 for (e
= head
->first
; e
->prev
; e
= e
->prev
)
721 /* Loop to find the element with the smallest index. */ ;
722 t
= bitmap_tree_splay (head
, head
->first
, e
->indx
);
723 gcc_checking_assert (t
== e
);
726 bitmap_elt_clear_from (head
, head
->first
);
729 /* Initialize a bitmap obstack. If BIT_OBSTACK is NULL, initialize
730 the default bitmap obstack. */
733 bitmap_obstack_initialize (bitmap_obstack
*bit_obstack
)
737 if (bitmap_default_obstack_depth
++)
739 bit_obstack
= &bitmap_default_obstack
;
742 #if !defined(__GNUC__) || (__GNUC__ < 2)
743 #define __alignof__(type) 0
746 bit_obstack
->elements
= NULL
;
747 bit_obstack
->heads
= NULL
;
748 obstack_specify_allocation (&bit_obstack
->obstack
, OBSTACK_CHUNK_SIZE
,
749 __alignof__ (bitmap_element
),
754 /* Release the memory from a bitmap obstack. If BIT_OBSTACK is NULL,
755 release the default bitmap obstack. */
758 bitmap_obstack_release (bitmap_obstack
*bit_obstack
)
762 if (--bitmap_default_obstack_depth
)
764 gcc_assert (bitmap_default_obstack_depth
> 0);
767 bit_obstack
= &bitmap_default_obstack
;
770 bit_obstack
->elements
= NULL
;
771 bit_obstack
->heads
= NULL
;
772 obstack_free (&bit_obstack
->obstack
, NULL
);
775 /* Create a new bitmap on an obstack. If BIT_OBSTACK is NULL, create
776 it on the default bitmap obstack. */
779 bitmap_alloc (bitmap_obstack
*bit_obstack MEM_STAT_DECL
)
784 bit_obstack
= &bitmap_default_obstack
;
785 map
= bit_obstack
->heads
;
787 bit_obstack
->heads
= (class bitmap_head
*) map
->first
;
789 map
= XOBNEW (&bit_obstack
->obstack
, bitmap_head
);
790 bitmap_initialize (map
, bit_obstack PASS_MEM_STAT
);
792 if (GATHER_STATISTICS
)
793 register_overhead (map
, sizeof (bitmap_head
));
798 /* Create a new GCd bitmap. */
801 bitmap_gc_alloc (ALONE_MEM_STAT_DECL
)
805 map
= ggc_alloc
<bitmap_head
> ();
806 bitmap_initialize (map
, NULL PASS_MEM_STAT
);
808 if (GATHER_STATISTICS
)
809 register_overhead (map
, sizeof (bitmap_head
));
814 /* Release an obstack allocated bitmap. */
817 bitmap_obstack_free (bitmap map
)
822 map
->first
= (bitmap_element
*) map
->obstack
->heads
;
824 if (GATHER_STATISTICS
)
825 release_overhead (map
, sizeof (bitmap_head
), true);
827 map
->obstack
->heads
= map
;
832 /* Return nonzero if all bits in an element are zero. */
835 bitmap_element_zerop (const bitmap_element
*element
)
837 #if BITMAP_ELEMENT_WORDS == 2
838 return (element
->bits
[0] | element
->bits
[1]) == 0;
842 for (i
= 0; i
< BITMAP_ELEMENT_WORDS
; i
++)
843 if (element
->bits
[i
] != 0)
850 /* Copy a bitmap to another bitmap. */
853 bitmap_copy (bitmap to
, const_bitmap from
)
855 const bitmap_element
*from_ptr
;
856 bitmap_element
*to_ptr
= 0;
858 gcc_checking_assert (!to
->tree_form
&& !from
->tree_form
);
862 /* Copy elements in forward direction one at a time. */
863 for (from_ptr
= from
->first
; from_ptr
; from_ptr
= from_ptr
->next
)
865 bitmap_element
*to_elt
= bitmap_element_allocate (to
);
867 to_elt
->indx
= from_ptr
->indx
;
868 memcpy (to_elt
->bits
, from_ptr
->bits
, sizeof (to_elt
->bits
));
870 /* Here we have a special case of bitmap_list_link_element,
871 for the case where we know the links are being entered
875 to
->first
= to
->current
= to_elt
;
876 to
->indx
= from_ptr
->indx
;
877 to_elt
->next
= to_elt
->prev
= 0;
881 to_elt
->prev
= to_ptr
;
883 to_ptr
->next
= to_elt
;
890 /* Move a bitmap to another bitmap. */
893 bitmap_move (bitmap to
, bitmap from
)
895 gcc_assert (to
->obstack
== from
->obstack
);
900 if (GATHER_STATISTICS
)
902 for (bitmap_element
*e
= to
->first
; e
; e
= e
->next
)
903 sz
+= sizeof (bitmap_element
);
904 register_overhead (to
, sz
);
909 if (GATHER_STATISTICS
)
910 release_overhead (from
, sz
, false);
913 /* Clear a single bit in a bitmap. Return true if the bit changed. */
916 bitmap_clear_bit (bitmap head
, int bit
)
918 unsigned int indx
= bit
/ BITMAP_ELEMENT_ALL_BITS
;
921 if (!head
->tree_form
)
922 ptr
= bitmap_list_find_element (head
, indx
);
924 ptr
= bitmap_tree_find_element (head
, indx
);
927 unsigned bit_num
= bit
% BITMAP_WORD_BITS
;
928 unsigned word_num
= bit
/ BITMAP_WORD_BITS
% BITMAP_ELEMENT_WORDS
;
929 BITMAP_WORD bit_val
= ((BITMAP_WORD
) 1) << bit_num
;
930 bool res
= (ptr
->bits
[word_num
] & bit_val
) != 0;
933 ptr
->bits
[word_num
] &= ~bit_val
;
934 /* If we cleared the entire word, free up the element. */
935 if (!ptr
->bits
[word_num
]
936 && bitmap_element_zerop (ptr
))
938 if (!head
->tree_form
)
939 bitmap_list_unlink_element (head
, ptr
);
941 bitmap_tree_unlink_element (head
, ptr
);
951 /* Set a single bit in a bitmap. Return true if the bit changed. */
954 bitmap_set_bit (bitmap head
, int bit
)
956 unsigned indx
= bit
/ BITMAP_ELEMENT_ALL_BITS
;
958 if (!head
->tree_form
)
959 ptr
= bitmap_list_find_element (head
, indx
);
961 ptr
= bitmap_tree_find_element (head
, indx
);
962 unsigned word_num
= bit
/ BITMAP_WORD_BITS
% BITMAP_ELEMENT_WORDS
;
963 unsigned bit_num
= bit
% BITMAP_WORD_BITS
;
964 BITMAP_WORD bit_val
= ((BITMAP_WORD
) 1) << bit_num
;
968 bool res
= (ptr
->bits
[word_num
] & bit_val
) == 0;
970 ptr
->bits
[word_num
] |= bit_val
;
974 ptr
= bitmap_element_allocate (head
);
975 ptr
->indx
= bit
/ BITMAP_ELEMENT_ALL_BITS
;
976 ptr
->bits
[word_num
] = bit_val
;
977 if (!head
->tree_form
)
978 bitmap_list_link_element (head
, ptr
);
980 bitmap_tree_link_element (head
, ptr
);
984 /* Return whether a bit is set within a bitmap. */
987 bitmap_bit_p (const_bitmap head
, int bit
)
989 unsigned int indx
= bit
/ BITMAP_ELEMENT_ALL_BITS
;
990 const bitmap_element
*ptr
;
994 if (!head
->tree_form
)
995 ptr
= bitmap_list_find_element (const_cast<bitmap
> (head
), indx
);
997 ptr
= bitmap_tree_find_element (const_cast<bitmap
> (head
), indx
);
1001 bit_num
= bit
% BITMAP_WORD_BITS
;
1002 word_num
= bit
/ BITMAP_WORD_BITS
% BITMAP_ELEMENT_WORDS
;
1004 return (ptr
->bits
[word_num
] >> bit_num
) & 1;
1007 #if GCC_VERSION < 3400
1008 /* Table of number of set bits in a character, indexed by value of char. */
1009 static const unsigned char popcount_table
[] =
1011 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,
1012 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,
1013 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,
1014 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,
1015 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,
1016 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,
1017 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,
1018 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,
1021 static unsigned long
1022 bitmap_popcount (BITMAP_WORD a
)
1024 unsigned long ret
= 0;
1027 /* Just do this the table way for now */
1028 for (i
= 0; i
< BITMAP_WORD_BITS
; i
+= 8)
1029 ret
+= popcount_table
[(a
>> i
) & 0xff];
1034 /* Count and return the number of bits set in the bitmap word BITS. */
1035 static unsigned long
1036 bitmap_count_bits_in_word (const BITMAP_WORD
*bits
)
1038 unsigned long count
= 0;
1040 for (unsigned ix
= 0; ix
!= BITMAP_ELEMENT_WORDS
; ix
++)
1042 #if GCC_VERSION >= 3400
1043 /* Note that popcountl matches BITMAP_WORD in type, so the actual size
1044 of BITMAP_WORD is not material. */
1045 count
+= __builtin_popcountl (bits
[ix
]);
1047 count
+= bitmap_popcount (bits
[ix
]);
1053 /* Count the number of bits set in the bitmap, and return it. */
1056 bitmap_count_bits (const_bitmap a
)
1058 unsigned long count
= 0;
1059 const bitmap_element
*elt
;
1061 gcc_checking_assert (!a
->tree_form
);
1062 for (elt
= a
->first
; elt
; elt
= elt
->next
)
1063 count
+= bitmap_count_bits_in_word (elt
->bits
);
1068 /* Count the number of unique bits set in A and B and return it. */
1071 bitmap_count_unique_bits (const_bitmap a
, const_bitmap b
)
1073 unsigned long count
= 0;
1074 const bitmap_element
*elt_a
, *elt_b
;
1076 for (elt_a
= a
->first
, elt_b
= b
->first
; elt_a
&& elt_b
; )
1078 /* If we're at different indices, then count all the bits
1079 in the lower element. If we're at the same index, then
1080 count the bits in the IOR of the two elements. */
1081 if (elt_a
->indx
< elt_b
->indx
)
1083 count
+= bitmap_count_bits_in_word (elt_a
->bits
);
1084 elt_a
= elt_a
->next
;
1086 else if (elt_b
->indx
< elt_a
->indx
)
1088 count
+= bitmap_count_bits_in_word (elt_b
->bits
);
1089 elt_b
= elt_b
->next
;
1093 BITMAP_WORD bits
[BITMAP_ELEMENT_WORDS
];
1094 for (unsigned ix
= 0; ix
!= BITMAP_ELEMENT_WORDS
; ix
++)
1095 bits
[ix
] = elt_a
->bits
[ix
] | elt_b
->bits
[ix
];
1096 count
+= bitmap_count_bits_in_word (bits
);
1097 elt_a
= elt_a
->next
;
1098 elt_b
= elt_b
->next
;
1104 /* Return true if the bitmap has a single bit set. Otherwise return
1108 bitmap_single_bit_set_p (const_bitmap a
)
1110 unsigned long count
= 0;
1111 const bitmap_element
*elt
;
1114 if (bitmap_empty_p (a
))
1119 /* As there are no completely empty bitmap elements, a second one
1120 means we have more than one bit set. */
1121 if (elt
->next
!= NULL
1122 && (!a
->tree_form
|| elt
->prev
!= NULL
))
1125 for (ix
= 0; ix
!= BITMAP_ELEMENT_WORDS
; ix
++)
1127 #if GCC_VERSION >= 3400
1128 /* Note that popcountl matches BITMAP_WORD in type, so the actual size
1129 of BITMAP_WORD is not material. */
1130 count
+= __builtin_popcountl (elt
->bits
[ix
]);
1132 count
+= bitmap_popcount (elt
->bits
[ix
]);
1142 /* Return the bit number of the first set bit in the bitmap. The
1143 bitmap must be non-empty. */
1146 bitmap_first_set_bit (const_bitmap a
)
1148 const bitmap_element
*elt
= a
->first
;
1153 gcc_checking_assert (elt
);
1159 bit_no
= elt
->indx
* BITMAP_ELEMENT_ALL_BITS
;
1160 for (ix
= 0; ix
!= BITMAP_ELEMENT_WORDS
; ix
++)
1162 word
= elt
->bits
[ix
];
1168 bit_no
+= ix
* BITMAP_WORD_BITS
;
1170 #if GCC_VERSION >= 3004
1171 gcc_assert (sizeof (long) == sizeof (word
));
1172 bit_no
+= __builtin_ctzl (word
);
1174 /* Binary search for the first set bit. */
1175 #if BITMAP_WORD_BITS > 64
1176 #error "Fill out the table."
1178 #if BITMAP_WORD_BITS > 32
1179 if (!(word
& 0xffffffff))
1180 word
>>= 32, bit_no
+= 32;
1182 if (!(word
& 0xffff))
1183 word
>>= 16, bit_no
+= 16;
1185 word
>>= 8, bit_no
+= 8;
1187 word
>>= 4, bit_no
+= 4;
1189 word
>>= 2, bit_no
+= 2;
1191 word
>>= 1, bit_no
+= 1;
1193 gcc_checking_assert (word
& 1);
1198 /* Return the bit number of the first set bit in the bitmap. The
1199 bitmap must be non-empty. */
1202 bitmap_last_set_bit (const_bitmap a
)
1204 const bitmap_element
*elt
;
1212 elt
= a
->current
? a
->current
: a
->first
;
1213 gcc_checking_assert (elt
);
1218 bit_no
= elt
->indx
* BITMAP_ELEMENT_ALL_BITS
;
1219 for (ix
= BITMAP_ELEMENT_WORDS
- 1; ix
>= 1; ix
--)
1221 word
= elt
->bits
[ix
];
1225 gcc_assert (elt
->bits
[ix
] != 0);
1227 bit_no
+= ix
* BITMAP_WORD_BITS
;
1228 #if GCC_VERSION >= 3004
1229 gcc_assert (sizeof (long) == sizeof (word
));
1230 bit_no
+= BITMAP_WORD_BITS
- __builtin_clzl (word
) - 1;
1232 /* Hopefully this is a twos-complement host... */
1233 BITMAP_WORD x
= word
;
1239 #if BITMAP_WORD_BITS > 32
1242 bit_no
+= bitmap_popcount (x
) - 1;
1252 bitmap_and (bitmap dst
, const_bitmap a
, const_bitmap b
)
1254 bitmap_element
*dst_elt
= dst
->first
;
1255 const bitmap_element
*a_elt
= a
->first
;
1256 const bitmap_element
*b_elt
= b
->first
;
1257 bitmap_element
*dst_prev
= NULL
;
1259 gcc_checking_assert (!dst
->tree_form
&& !a
->tree_form
&& !b
->tree_form
);
1260 gcc_assert (dst
!= a
&& dst
!= b
);
1264 bitmap_copy (dst
, a
);
1268 while (a_elt
&& b_elt
)
1270 if (a_elt
->indx
< b_elt
->indx
)
1271 a_elt
= a_elt
->next
;
1272 else if (b_elt
->indx
< a_elt
->indx
)
1273 b_elt
= b_elt
->next
;
1276 /* Matching elts, generate A & B. */
1278 BITMAP_WORD ior
= 0;
1281 dst_elt
= bitmap_list_insert_element_after (dst
, dst_prev
,
1284 dst_elt
->indx
= a_elt
->indx
;
1285 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1287 BITMAP_WORD r
= a_elt
->bits
[ix
] & b_elt
->bits
[ix
];
1289 dst_elt
->bits
[ix
] = r
;
1295 dst_elt
= dst_elt
->next
;
1297 a_elt
= a_elt
->next
;
1298 b_elt
= b_elt
->next
;
1301 /* Ensure that dst->current is valid. */
1302 dst
->current
= dst
->first
;
1303 bitmap_elt_clear_from (dst
, dst_elt
);
1304 gcc_checking_assert (!dst
->current
== !dst
->first
);
1306 dst
->indx
= dst
->current
->indx
;
1309 /* A &= B. Return true if A changed. */
1312 bitmap_and_into (bitmap a
, const_bitmap b
)
1314 bitmap_element
*a_elt
= a
->first
;
1315 const bitmap_element
*b_elt
= b
->first
;
1316 bitmap_element
*next
;
1317 bool changed
= false;
1319 gcc_checking_assert (!a
->tree_form
&& !b
->tree_form
);
1324 while (a_elt
&& b_elt
)
1326 if (a_elt
->indx
< b_elt
->indx
)
1329 bitmap_list_unlink_element (a
, a_elt
);
1333 else if (b_elt
->indx
< a_elt
->indx
)
1334 b_elt
= b_elt
->next
;
1337 /* Matching elts, generate A &= B. */
1339 BITMAP_WORD ior
= 0;
1341 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1343 BITMAP_WORD r
= a_elt
->bits
[ix
] & b_elt
->bits
[ix
];
1344 if (a_elt
->bits
[ix
] != r
)
1346 a_elt
->bits
[ix
] = r
;
1351 bitmap_list_unlink_element (a
, a_elt
);
1353 b_elt
= b_elt
->next
;
1360 bitmap_elt_clear_from (a
, a_elt
);
1363 gcc_checking_assert (!a
->current
== !a
->first
1364 && (!a
->current
|| a
->indx
== a
->current
->indx
));
1370 /* Insert an element equal to SRC_ELT after DST_PREV, overwriting DST_ELT
1371 if non-NULL. CHANGED is true if the destination bitmap had already been
1372 changed; the new value of CHANGED is returned. */
1375 bitmap_elt_copy (bitmap dst
, bitmap_element
*dst_elt
, bitmap_element
*dst_prev
,
1376 const bitmap_element
*src_elt
, bool changed
)
1378 if (!changed
&& dst_elt
&& dst_elt
->indx
== src_elt
->indx
)
1382 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1383 if (src_elt
->bits
[ix
] != dst_elt
->bits
[ix
])
1385 dst_elt
->bits
[ix
] = src_elt
->bits
[ix
];
1393 dst_elt
= bitmap_list_insert_element_after (dst
, dst_prev
,
1396 dst_elt
->indx
= src_elt
->indx
;
1397 memcpy (dst_elt
->bits
, src_elt
->bits
, sizeof (dst_elt
->bits
));
1407 bitmap_and_compl (bitmap dst
, const_bitmap a
, const_bitmap b
)
1409 bitmap_element
*dst_elt
= dst
->first
;
1410 const bitmap_element
*a_elt
= a
->first
;
1411 const bitmap_element
*b_elt
= b
->first
;
1412 bitmap_element
*dst_prev
= NULL
;
1413 bitmap_element
**dst_prev_pnext
= &dst
->first
;
1414 bool changed
= false;
1416 gcc_checking_assert (!dst
->tree_form
&& !a
->tree_form
&& !b
->tree_form
);
1417 gcc_assert (dst
!= a
&& dst
!= b
);
1421 changed
= !bitmap_empty_p (dst
);
1428 while (b_elt
&& b_elt
->indx
< a_elt
->indx
)
1429 b_elt
= b_elt
->next
;
1431 if (!b_elt
|| b_elt
->indx
> a_elt
->indx
)
1433 changed
= bitmap_elt_copy (dst
, dst_elt
, dst_prev
, a_elt
, changed
);
1434 dst_prev
= *dst_prev_pnext
;
1435 dst_prev_pnext
= &dst_prev
->next
;
1436 dst_elt
= *dst_prev_pnext
;
1437 a_elt
= a_elt
->next
;
1442 /* Matching elts, generate A & ~B. */
1444 BITMAP_WORD ior
= 0;
1446 if (!changed
&& dst_elt
&& dst_elt
->indx
== a_elt
->indx
)
1448 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1450 BITMAP_WORD r
= a_elt
->bits
[ix
] & ~b_elt
->bits
[ix
];
1452 if (dst_elt
->bits
[ix
] != r
)
1455 dst_elt
->bits
[ix
] = r
;
1463 if (!dst_elt
|| dst_elt
->indx
> a_elt
->indx
)
1465 dst_elt
= bitmap_list_insert_element_after (dst
, dst_prev
,
1471 dst_elt
->indx
= a_elt
->indx
;
1472 new_element
= false;
1475 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1477 BITMAP_WORD r
= a_elt
->bits
[ix
] & ~b_elt
->bits
[ix
];
1479 dst_elt
->bits
[ix
] = r
;
1487 changed
|= !new_element
;
1488 bitmap_list_unlink_element (dst
, dst_elt
);
1489 dst_elt
= *dst_prev_pnext
;
1495 dst_prev
= *dst_prev_pnext
;
1496 dst_prev_pnext
= &dst_prev
->next
;
1497 dst_elt
= *dst_prev_pnext
;
1499 a_elt
= a_elt
->next
;
1500 b_elt
= b_elt
->next
;
1504 /* Ensure that dst->current is valid. */
1505 dst
->current
= dst
->first
;
1510 bitmap_elt_clear_from (dst
, dst_elt
);
1512 gcc_checking_assert (!dst
->current
== !dst
->first
);
1514 dst
->indx
= dst
->current
->indx
;
1519 /* A &= ~B. Returns true if A changes */
1522 bitmap_and_compl_into (bitmap a
, const_bitmap b
)
1524 bitmap_element
*a_elt
= a
->first
;
1525 const bitmap_element
*b_elt
= b
->first
;
1526 bitmap_element
*next
;
1527 BITMAP_WORD changed
= 0;
1529 gcc_checking_assert (!a
->tree_form
&& !b
->tree_form
);
1533 if (bitmap_empty_p (a
))
1542 while (a_elt
&& b_elt
)
1544 if (a_elt
->indx
< b_elt
->indx
)
1545 a_elt
= a_elt
->next
;
1546 else if (b_elt
->indx
< a_elt
->indx
)
1547 b_elt
= b_elt
->next
;
1550 /* Matching elts, generate A &= ~B. */
1552 BITMAP_WORD ior
= 0;
1554 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1556 BITMAP_WORD cleared
= a_elt
->bits
[ix
] & b_elt
->bits
[ix
];
1557 BITMAP_WORD r
= a_elt
->bits
[ix
] ^ cleared
;
1559 a_elt
->bits
[ix
] = r
;
1565 bitmap_list_unlink_element (a
, a_elt
);
1567 b_elt
= b_elt
->next
;
1570 gcc_checking_assert (!a
->current
== !a
->first
1571 && (!a
->current
|| a
->indx
== a
->current
->indx
));
1572 return changed
!= 0;
1575 /* Set COUNT bits from START in HEAD. */
1577 bitmap_set_range (bitmap head
, unsigned int start
, unsigned int count
)
1579 unsigned int first_index
, end_bit_plus1
, last_index
;
1580 bitmap_element
*elt
, *elt_prev
;
1583 gcc_checking_assert (!head
->tree_form
);
1590 bitmap_set_bit (head
, start
);
1594 first_index
= start
/ BITMAP_ELEMENT_ALL_BITS
;
1595 end_bit_plus1
= start
+ count
;
1596 last_index
= (end_bit_plus1
- 1) / BITMAP_ELEMENT_ALL_BITS
;
1597 elt
= bitmap_list_find_element (head
, first_index
);
1599 /* If bitmap_list_find_element returns zero, the current is the closest block
1600 to the result. Otherwise, just use bitmap_element_allocate to
1601 ensure ELT is set; in the loop below, ELT == NULL means "insert
1602 at the end of the bitmap". */
1605 elt
= bitmap_element_allocate (head
);
1606 elt
->indx
= first_index
;
1607 bitmap_list_link_element (head
, elt
);
1610 gcc_checking_assert (elt
->indx
== first_index
);
1611 elt_prev
= elt
->prev
;
1612 for (i
= first_index
; i
<= last_index
; i
++)
1614 unsigned elt_start_bit
= i
* BITMAP_ELEMENT_ALL_BITS
;
1615 unsigned elt_end_bit_plus1
= elt_start_bit
+ BITMAP_ELEMENT_ALL_BITS
;
1617 unsigned int first_word_to_mod
;
1618 BITMAP_WORD first_mask
;
1619 unsigned int last_word_to_mod
;
1620 BITMAP_WORD last_mask
;
1623 if (!elt
|| elt
->indx
!= i
)
1624 elt
= bitmap_list_insert_element_after (head
, elt_prev
, i
);
1626 if (elt_start_bit
<= start
)
1628 /* The first bit to turn on is somewhere inside this
1630 first_word_to_mod
= (start
- elt_start_bit
) / BITMAP_WORD_BITS
;
1632 /* This mask should have 1s in all bits >= start position. */
1634 (((BITMAP_WORD
) 1) << ((start
% BITMAP_WORD_BITS
))) - 1;
1635 first_mask
= ~first_mask
;
1639 /* The first bit to turn on is below this start of this elt. */
1640 first_word_to_mod
= 0;
1641 first_mask
= ~(BITMAP_WORD
) 0;
1644 if (elt_end_bit_plus1
<= end_bit_plus1
)
1646 /* The last bit to turn on is beyond this elt. */
1647 last_word_to_mod
= BITMAP_ELEMENT_WORDS
- 1;
1648 last_mask
= ~(BITMAP_WORD
) 0;
1652 /* The last bit to turn on is inside to this elt. */
1654 (end_bit_plus1
- elt_start_bit
) / BITMAP_WORD_BITS
;
1656 /* The last mask should have 1s below the end bit. */
1658 (((BITMAP_WORD
) 1) << ((end_bit_plus1
% BITMAP_WORD_BITS
))) - 1;
1661 if (first_word_to_mod
== last_word_to_mod
)
1663 BITMAP_WORD mask
= first_mask
& last_mask
;
1664 elt
->bits
[first_word_to_mod
] |= mask
;
1668 elt
->bits
[first_word_to_mod
] |= first_mask
;
1669 if (BITMAP_ELEMENT_WORDS
> 2)
1670 for (ix
= first_word_to_mod
+ 1; ix
< last_word_to_mod
; ix
++)
1671 elt
->bits
[ix
] = ~(BITMAP_WORD
) 0;
1672 elt
->bits
[last_word_to_mod
] |= last_mask
;
1679 head
->current
= elt
? elt
: elt_prev
;
1680 head
->indx
= head
->current
->indx
;
1683 /* Clear COUNT bits from START in HEAD. */
1685 bitmap_clear_range (bitmap head
, unsigned int start
, unsigned int count
)
1687 unsigned int first_index
, end_bit_plus1
, last_index
;
1688 bitmap_element
*elt
;
1690 gcc_checking_assert (!head
->tree_form
);
1697 bitmap_clear_bit (head
, start
);
1701 first_index
= start
/ BITMAP_ELEMENT_ALL_BITS
;
1702 end_bit_plus1
= start
+ count
;
1703 last_index
= (end_bit_plus1
- 1) / BITMAP_ELEMENT_ALL_BITS
;
1704 elt
= bitmap_list_find_element (head
, first_index
);
1706 /* If bitmap_list_find_element returns zero, the current is the closest block
1707 to the result. If the current is less than first index, find the
1708 next one. Otherwise, just set elt to be current. */
1713 if (head
->indx
< first_index
)
1715 elt
= head
->current
->next
;
1720 elt
= head
->current
;
1726 while (elt
&& (elt
->indx
<= last_index
))
1728 bitmap_element
* next_elt
= elt
->next
;
1729 unsigned elt_start_bit
= (elt
->indx
) * BITMAP_ELEMENT_ALL_BITS
;
1730 unsigned elt_end_bit_plus1
= elt_start_bit
+ BITMAP_ELEMENT_ALL_BITS
;
1733 if (elt_start_bit
>= start
&& elt_end_bit_plus1
<= end_bit_plus1
)
1734 /* Get rid of the entire elt and go to the next one. */
1735 bitmap_list_unlink_element (head
, elt
);
1738 /* Going to have to knock out some bits in this elt. */
1739 unsigned int first_word_to_mod
;
1740 BITMAP_WORD first_mask
;
1741 unsigned int last_word_to_mod
;
1742 BITMAP_WORD last_mask
;
1746 if (elt_start_bit
<= start
)
1748 /* The first bit to turn off is somewhere inside this
1750 first_word_to_mod
= (start
- elt_start_bit
) / BITMAP_WORD_BITS
;
1752 /* This mask should have 1s in all bits >= start position. */
1754 (((BITMAP_WORD
) 1) << ((start
% BITMAP_WORD_BITS
))) - 1;
1755 first_mask
= ~first_mask
;
1759 /* The first bit to turn off is below this start of this elt. */
1760 first_word_to_mod
= 0;
1762 first_mask
= ~first_mask
;
1765 if (elt_end_bit_plus1
<= end_bit_plus1
)
1767 /* The last bit to turn off is beyond this elt. */
1768 last_word_to_mod
= BITMAP_ELEMENT_WORDS
- 1;
1770 last_mask
= ~last_mask
;
1774 /* The last bit to turn off is inside to this elt. */
1776 (end_bit_plus1
- elt_start_bit
) / BITMAP_WORD_BITS
;
1778 /* The last mask should have 1s below the end bit. */
1780 (((BITMAP_WORD
) 1) << (((end_bit_plus1
) % BITMAP_WORD_BITS
))) - 1;
1784 if (first_word_to_mod
== last_word_to_mod
)
1786 BITMAP_WORD mask
= first_mask
& last_mask
;
1787 elt
->bits
[first_word_to_mod
] &= ~mask
;
1791 elt
->bits
[first_word_to_mod
] &= ~first_mask
;
1792 if (BITMAP_ELEMENT_WORDS
> 2)
1793 for (i
= first_word_to_mod
+ 1; i
< last_word_to_mod
; i
++)
1795 elt
->bits
[last_word_to_mod
] &= ~last_mask
;
1797 for (i
= 0; i
< BITMAP_ELEMENT_WORDS
; i
++)
1803 /* Check to see if there are any bits left. */
1805 bitmap_list_unlink_element (head
, elt
);
1812 head
->current
= elt
;
1813 head
->indx
= head
->current
->indx
;
1820 bitmap_compl_and_into (bitmap a
, const_bitmap b
)
1822 bitmap_element
*a_elt
= a
->first
;
1823 const bitmap_element
*b_elt
= b
->first
;
1824 bitmap_element
*a_prev
= NULL
;
1825 bitmap_element
*next
;
1827 gcc_checking_assert (!a
->tree_form
&& !b
->tree_form
);
1828 gcc_assert (a
!= b
);
1830 if (bitmap_empty_p (a
))
1835 if (bitmap_empty_p (b
))
1841 while (a_elt
|| b_elt
)
1843 if (!b_elt
|| (a_elt
&& a_elt
->indx
< b_elt
->indx
))
1845 /* A is before B. Remove A */
1847 a_prev
= a_elt
->prev
;
1848 bitmap_list_unlink_element (a
, a_elt
);
1851 else if (!a_elt
|| b_elt
->indx
< a_elt
->indx
)
1853 /* B is before A. Copy B. */
1854 next
= bitmap_list_insert_element_after (a
, a_prev
, b_elt
->indx
);
1855 memcpy (next
->bits
, b_elt
->bits
, sizeof (next
->bits
));
1857 b_elt
= b_elt
->next
;
1861 /* Matching elts, generate A = ~A & B. */
1863 BITMAP_WORD ior
= 0;
1865 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1867 BITMAP_WORD cleared
= a_elt
->bits
[ix
] & b_elt
->bits
[ix
];
1868 BITMAP_WORD r
= b_elt
->bits
[ix
] ^ cleared
;
1870 a_elt
->bits
[ix
] = r
;
1875 bitmap_list_unlink_element (a
, a_elt
);
1879 b_elt
= b_elt
->next
;
1882 gcc_checking_assert (!a
->current
== !a
->first
1883 && (!a
->current
|| a
->indx
== a
->current
->indx
));
1888 /* Insert an element corresponding to A_ELT | B_ELT after DST_PREV,
1889 overwriting DST_ELT if non-NULL. CHANGED is true if the destination bitmap
1890 had already been changed; the new value of CHANGED is returned. */
1893 bitmap_elt_ior (bitmap dst
, bitmap_element
*dst_elt
, bitmap_element
*dst_prev
,
1894 const bitmap_element
*a_elt
, const bitmap_element
*b_elt
,
1897 gcc_assert (a_elt
|| b_elt
);
1899 if (a_elt
&& b_elt
&& a_elt
->indx
== b_elt
->indx
)
1901 /* Matching elts, generate A | B. */
1904 if (!changed
&& dst_elt
&& dst_elt
->indx
== a_elt
->indx
)
1906 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1908 BITMAP_WORD r
= a_elt
->bits
[ix
] | b_elt
->bits
[ix
];
1909 if (r
!= dst_elt
->bits
[ix
])
1911 dst_elt
->bits
[ix
] = r
;
1920 dst_elt
= bitmap_list_insert_element_after (dst
, dst_prev
,
1923 dst_elt
->indx
= a_elt
->indx
;
1924 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1926 BITMAP_WORD r
= a_elt
->bits
[ix
] | b_elt
->bits
[ix
];
1927 dst_elt
->bits
[ix
] = r
;
1933 /* Copy a single element. */
1934 const bitmap_element
*src
;
1936 if (!b_elt
|| (a_elt
&& a_elt
->indx
< b_elt
->indx
))
1941 gcc_checking_assert (src
);
1942 changed
= bitmap_elt_copy (dst
, dst_elt
, dst_prev
, src
, changed
);
1948 /* DST = A | B. Return true if DST changes. */
1951 bitmap_ior (bitmap dst
, const_bitmap a
, const_bitmap b
)
1953 bitmap_element
*dst_elt
= dst
->first
;
1954 const bitmap_element
*a_elt
= a
->first
;
1955 const bitmap_element
*b_elt
= b
->first
;
1956 bitmap_element
*dst_prev
= NULL
;
1957 bitmap_element
**dst_prev_pnext
= &dst
->first
;
1958 bool changed
= false;
1960 gcc_checking_assert (!dst
->tree_form
&& !a
->tree_form
&& !b
->tree_form
);
1961 gcc_assert (dst
!= a
&& dst
!= b
);
1963 while (a_elt
|| b_elt
)
1965 changed
= bitmap_elt_ior (dst
, dst_elt
, dst_prev
, a_elt
, b_elt
, changed
);
1967 if (a_elt
&& b_elt
&& a_elt
->indx
== b_elt
->indx
)
1969 a_elt
= a_elt
->next
;
1970 b_elt
= b_elt
->next
;
1974 if (a_elt
&& (!b_elt
|| a_elt
->indx
<= b_elt
->indx
))
1975 a_elt
= a_elt
->next
;
1976 else if (b_elt
&& (!a_elt
|| b_elt
->indx
<= a_elt
->indx
))
1977 b_elt
= b_elt
->next
;
1980 dst_prev
= *dst_prev_pnext
;
1981 dst_prev_pnext
= &dst_prev
->next
;
1982 dst_elt
= *dst_prev_pnext
;
1988 /* Ensure that dst->current is valid. */
1989 dst
->current
= dst
->first
;
1990 bitmap_elt_clear_from (dst
, dst_elt
);
1992 gcc_checking_assert (!dst
->current
== !dst
->first
);
1994 dst
->indx
= dst
->current
->indx
;
1998 /* A |= B. Return true if A changes. */
2001 bitmap_ior_into (bitmap a
, const_bitmap b
)
2003 bitmap_element
*a_elt
= a
->first
;
2004 const bitmap_element
*b_elt
= b
->first
;
2005 bitmap_element
*a_prev
= NULL
;
2006 bitmap_element
**a_prev_pnext
= &a
->first
;
2007 bool changed
= false;
2009 gcc_checking_assert (!a
->tree_form
&& !b
->tree_form
);
2015 /* If A lags behind B, just advance it. */
2016 if (!a_elt
|| a_elt
->indx
== b_elt
->indx
)
2018 changed
= bitmap_elt_ior (a
, a_elt
, a_prev
, a_elt
, b_elt
, changed
);
2019 b_elt
= b_elt
->next
;
2021 else if (a_elt
->indx
> b_elt
->indx
)
2023 changed
= bitmap_elt_copy (a
, NULL
, a_prev
, b_elt
, changed
);
2024 b_elt
= b_elt
->next
;
2027 a_prev
= *a_prev_pnext
;
2028 a_prev_pnext
= &a_prev
->next
;
2029 a_elt
= *a_prev_pnext
;
2032 gcc_checking_assert (!a
->current
== !a
->first
);
2034 a
->indx
= a
->current
->indx
;
2038 /* A |= B. Return true if A changes. Free B (re-using its storage
2042 bitmap_ior_into_and_free (bitmap a
, bitmap
*b_
)
2045 bitmap_element
*a_elt
= a
->first
;
2046 bitmap_element
*b_elt
= b
->first
;
2047 bitmap_element
*a_prev
= NULL
;
2048 bitmap_element
**a_prev_pnext
= &a
->first
;
2049 bool changed
= false;
2051 gcc_checking_assert (!a
->tree_form
&& !b
->tree_form
);
2052 gcc_assert (a
->obstack
== b
->obstack
);
2058 /* If A lags behind B, just advance it. */
2059 if (!a_elt
|| a_elt
->indx
== b_elt
->indx
)
2061 changed
= bitmap_elt_ior (a
, a_elt
, a_prev
, a_elt
, b_elt
, changed
);
2062 b_elt
= b_elt
->next
;
2064 else if (a_elt
->indx
> b_elt
->indx
)
2066 bitmap_element
*b_elt_next
= b_elt
->next
;
2067 bitmap_list_unlink_element (b
, b_elt
, false);
2068 bitmap_list_insert_element_after (a
, a_prev
, b_elt
->indx
, b_elt
);
2072 a_prev
= *a_prev_pnext
;
2073 a_prev_pnext
= &a_prev
->next
;
2074 a_elt
= *a_prev_pnext
;
2077 gcc_checking_assert (!a
->current
== !a
->first
);
2079 a
->indx
= a
->current
->indx
;
2091 bitmap_xor (bitmap dst
, const_bitmap a
, const_bitmap b
)
2093 bitmap_element
*dst_elt
= dst
->first
;
2094 const bitmap_element
*a_elt
= a
->first
;
2095 const bitmap_element
*b_elt
= b
->first
;
2096 bitmap_element
*dst_prev
= NULL
;
2098 gcc_checking_assert (!dst
->tree_form
&& !a
->tree_form
&& !b
->tree_form
);
2099 gcc_assert (dst
!= a
&& dst
!= b
);
2107 while (a_elt
|| b_elt
)
2109 if (a_elt
&& b_elt
&& a_elt
->indx
== b_elt
->indx
)
2111 /* Matching elts, generate A ^ B. */
2113 BITMAP_WORD ior
= 0;
2116 dst_elt
= bitmap_list_insert_element_after (dst
, dst_prev
,
2119 dst_elt
->indx
= a_elt
->indx
;
2120 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
2122 BITMAP_WORD r
= a_elt
->bits
[ix
] ^ b_elt
->bits
[ix
];
2125 dst_elt
->bits
[ix
] = r
;
2127 a_elt
= a_elt
->next
;
2128 b_elt
= b_elt
->next
;
2132 dst_elt
= dst_elt
->next
;
2137 /* Copy a single element. */
2138 const bitmap_element
*src
;
2140 if (!b_elt
|| (a_elt
&& a_elt
->indx
< b_elt
->indx
))
2143 a_elt
= a_elt
->next
;
2148 b_elt
= b_elt
->next
;
2152 dst_elt
= bitmap_list_insert_element_after (dst
, dst_prev
,
2155 dst_elt
->indx
= src
->indx
;
2156 memcpy (dst_elt
->bits
, src
->bits
, sizeof (dst_elt
->bits
));
2158 dst_elt
= dst_elt
->next
;
2161 /* Ensure that dst->current is valid. */
2162 dst
->current
= dst
->first
;
2163 bitmap_elt_clear_from (dst
, dst_elt
);
2164 gcc_checking_assert (!dst
->current
== !dst
->first
);
2166 dst
->indx
= dst
->current
->indx
;
2172 bitmap_xor_into (bitmap a
, const_bitmap b
)
2174 bitmap_element
*a_elt
= a
->first
;
2175 const bitmap_element
*b_elt
= b
->first
;
2176 bitmap_element
*a_prev
= NULL
;
2178 gcc_checking_assert (!a
->tree_form
&& !b
->tree_form
);
2188 if (!a_elt
|| b_elt
->indx
< a_elt
->indx
)
2191 bitmap_element
*dst
= bitmap_list_insert_element_after (a
, a_prev
,
2193 memcpy (dst
->bits
, b_elt
->bits
, sizeof (dst
->bits
));
2195 b_elt
= b_elt
->next
;
2197 else if (a_elt
->indx
< b_elt
->indx
)
2200 a_elt
= a_elt
->next
;
2204 /* Matching elts, generate A ^= B. */
2206 BITMAP_WORD ior
= 0;
2207 bitmap_element
*next
= a_elt
->next
;
2209 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
2211 BITMAP_WORD r
= a_elt
->bits
[ix
] ^ b_elt
->bits
[ix
];
2214 a_elt
->bits
[ix
] = r
;
2216 b_elt
= b_elt
->next
;
2220 bitmap_list_unlink_element (a
, a_elt
);
2224 gcc_checking_assert (!a
->current
== !a
->first
);
2226 a
->indx
= a
->current
->indx
;
2229 /* Return true if two bitmaps are identical.
2230 We do not bother with a check for pointer equality, as that never
2231 occurs in practice. */
2234 bitmap_equal_p (const_bitmap a
, const_bitmap b
)
2236 const bitmap_element
*a_elt
;
2237 const bitmap_element
*b_elt
;
2240 gcc_checking_assert (!a
->tree_form
&& !b
->tree_form
);
2242 for (a_elt
= a
->first
, b_elt
= b
->first
;
2244 a_elt
= a_elt
->next
, b_elt
= b_elt
->next
)
2246 if (a_elt
->indx
!= b_elt
->indx
)
2248 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
2249 if (a_elt
->bits
[ix
] != b_elt
->bits
[ix
])
2252 return !a_elt
&& !b_elt
;
2255 /* Return true if A AND B is not empty. */
2258 bitmap_intersect_p (const_bitmap a
, const_bitmap b
)
2260 const bitmap_element
*a_elt
;
2261 const bitmap_element
*b_elt
;
2264 gcc_checking_assert (!a
->tree_form
&& !b
->tree_form
);
2266 for (a_elt
= a
->first
, b_elt
= b
->first
;
2269 if (a_elt
->indx
< b_elt
->indx
)
2270 a_elt
= a_elt
->next
;
2271 else if (b_elt
->indx
< a_elt
->indx
)
2272 b_elt
= b_elt
->next
;
2275 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
2276 if (a_elt
->bits
[ix
] & b_elt
->bits
[ix
])
2278 a_elt
= a_elt
->next
;
2279 b_elt
= b_elt
->next
;
2285 /* Return true if A AND NOT B is not empty. */
2288 bitmap_intersect_compl_p (const_bitmap a
, const_bitmap b
)
2290 const bitmap_element
*a_elt
;
2291 const bitmap_element
*b_elt
;
2294 gcc_checking_assert (!a
->tree_form
&& !b
->tree_form
);
2296 for (a_elt
= a
->first
, b_elt
= b
->first
;
2299 if (a_elt
->indx
< b_elt
->indx
)
2301 else if (b_elt
->indx
< a_elt
->indx
)
2302 b_elt
= b_elt
->next
;
2305 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
2306 if (a_elt
->bits
[ix
] & ~b_elt
->bits
[ix
])
2308 a_elt
= a_elt
->next
;
2309 b_elt
= b_elt
->next
;
2312 return a_elt
!= NULL
;
2316 /* DST = A | (FROM1 & ~FROM2). Return true if DST changes. */
2319 bitmap_ior_and_compl (bitmap dst
, const_bitmap a
, const_bitmap b
, const_bitmap kill
)
2321 bool changed
= false;
2323 bitmap_element
*dst_elt
= dst
->first
;
2324 const bitmap_element
*a_elt
= a
->first
;
2325 const bitmap_element
*b_elt
= b
->first
;
2326 const bitmap_element
*kill_elt
= kill
->first
;
2327 bitmap_element
*dst_prev
= NULL
;
2328 bitmap_element
**dst_prev_pnext
= &dst
->first
;
2330 gcc_checking_assert (!dst
->tree_form
&& !a
->tree_form
&& !b
->tree_form
2331 && !kill
->tree_form
);
2332 gcc_assert (dst
!= a
&& dst
!= b
&& dst
!= kill
);
2334 /* Special cases. We don't bother checking for bitmap_equal_p (b, kill). */
2335 if (b
== kill
|| bitmap_empty_p (b
))
2337 changed
= !bitmap_equal_p (dst
, a
);
2339 bitmap_copy (dst
, a
);
2342 if (bitmap_empty_p (kill
))
2343 return bitmap_ior (dst
, a
, b
);
2344 if (bitmap_empty_p (a
))
2345 return bitmap_and_compl (dst
, b
, kill
);
2347 while (a_elt
|| b_elt
)
2349 bool new_element
= false;
2352 while (kill_elt
&& kill_elt
->indx
< b_elt
->indx
)
2353 kill_elt
= kill_elt
->next
;
2355 if (b_elt
&& kill_elt
&& kill_elt
->indx
== b_elt
->indx
2356 && (!a_elt
|| a_elt
->indx
>= b_elt
->indx
))
2358 bitmap_element tmp_elt
;
2361 BITMAP_WORD ior
= 0;
2362 tmp_elt
.indx
= b_elt
->indx
;
2363 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
2365 BITMAP_WORD r
= b_elt
->bits
[ix
] & ~kill_elt
->bits
[ix
];
2367 tmp_elt
.bits
[ix
] = r
;
2372 changed
= bitmap_elt_ior (dst
, dst_elt
, dst_prev
,
2373 a_elt
, &tmp_elt
, changed
);
2375 if (a_elt
&& a_elt
->indx
== b_elt
->indx
)
2376 a_elt
= a_elt
->next
;
2379 b_elt
= b_elt
->next
;
2380 kill_elt
= kill_elt
->next
;
2384 changed
= bitmap_elt_ior (dst
, dst_elt
, dst_prev
,
2385 a_elt
, b_elt
, changed
);
2388 if (a_elt
&& b_elt
&& a_elt
->indx
== b_elt
->indx
)
2390 a_elt
= a_elt
->next
;
2391 b_elt
= b_elt
->next
;
2395 if (a_elt
&& (!b_elt
|| a_elt
->indx
<= b_elt
->indx
))
2396 a_elt
= a_elt
->next
;
2397 else if (b_elt
&& (!a_elt
|| b_elt
->indx
<= a_elt
->indx
))
2398 b_elt
= b_elt
->next
;
2404 dst_prev
= *dst_prev_pnext
;
2405 dst_prev_pnext
= &dst_prev
->next
;
2406 dst_elt
= *dst_prev_pnext
;
2413 /* Ensure that dst->current is valid. */
2414 dst
->current
= dst
->first
;
2415 bitmap_elt_clear_from (dst
, dst_elt
);
2417 gcc_checking_assert (!dst
->current
== !dst
->first
);
2419 dst
->indx
= dst
->current
->indx
;
2424 /* A |= (B & ~C). Return true if A changes. */
2427 bitmap_ior_and_compl_into (bitmap a
, const_bitmap b
, const_bitmap c
)
2429 bitmap_element
*a_elt
= a
->first
;
2430 const bitmap_element
*b_elt
= b
->first
;
2431 const bitmap_element
*c_elt
= c
->first
;
2432 bitmap_element and_elt
;
2433 bitmap_element
*a_prev
= NULL
;
2434 bitmap_element
**a_prev_pnext
= &a
->first
;
2435 bool changed
= false;
2438 gcc_checking_assert (!a
->tree_form
&& !b
->tree_form
&& !c
->tree_form
);
2442 if (bitmap_empty_p (c
))
2443 return bitmap_ior_into (a
, b
);
2444 else if (bitmap_empty_p (a
))
2445 return bitmap_and_compl (a
, b
, c
);
2451 while (c_elt
&& c_elt
->indx
< b_elt
->indx
)
2452 c_elt
= c_elt
->next
;
2454 const bitmap_element
*and_elt_ptr
;
2455 if (c_elt
&& c_elt
->indx
== b_elt
->indx
)
2457 BITMAP_WORD overall
= 0;
2458 and_elt_ptr
= &and_elt
;
2459 and_elt
.indx
= b_elt
->indx
;
2460 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
2462 and_elt
.bits
[ix
] = b_elt
->bits
[ix
] & ~c_elt
->bits
[ix
];
2463 overall
|= and_elt
.bits
[ix
];
2467 b_elt
= b_elt
->next
;
2472 and_elt_ptr
= b_elt
;
2474 b_elt
= b_elt
->next
;
2476 /* Now find a place to insert AND_ELT. */
2479 ix
= a_elt
? a_elt
->indx
: and_elt_ptr
->indx
;
2480 if (ix
== and_elt_ptr
->indx
)
2481 changed
= bitmap_elt_ior (a
, a_elt
, a_prev
, a_elt
,
2482 and_elt_ptr
, changed
);
2483 else if (ix
> and_elt_ptr
->indx
)
2484 changed
= bitmap_elt_copy (a
, NULL
, a_prev
, and_elt_ptr
, changed
);
2486 a_prev
= *a_prev_pnext
;
2487 a_prev_pnext
= &a_prev
->next
;
2488 a_elt
= *a_prev_pnext
;
2490 /* If A lagged behind B/C, we advanced it so loop once more. */
2492 while (ix
< and_elt_ptr
->indx
);
2495 gcc_checking_assert (!a
->current
== !a
->first
);
2497 a
->indx
= a
->current
->indx
;
2501 /* A |= (B & C). Return true if A changes. */
2504 bitmap_ior_and_into (bitmap a
, const_bitmap b
, const_bitmap c
)
2506 bitmap_element
*a_elt
= a
->first
;
2507 const bitmap_element
*b_elt
= b
->first
;
2508 const bitmap_element
*c_elt
= c
->first
;
2509 bitmap_element and_elt
;
2510 bitmap_element
*a_prev
= NULL
;
2511 bitmap_element
**a_prev_pnext
= &a
->first
;
2512 bool changed
= false;
2515 gcc_checking_assert (!a
->tree_form
&& !b
->tree_form
&& !c
->tree_form
);
2518 return bitmap_ior_into (a
, b
);
2519 if (bitmap_empty_p (b
) || bitmap_empty_p (c
))
2523 while (b_elt
&& c_elt
)
2525 BITMAP_WORD overall
;
2527 /* Find a common item of B and C. */
2528 while (b_elt
->indx
!= c_elt
->indx
)
2530 if (b_elt
->indx
< c_elt
->indx
)
2532 b_elt
= b_elt
->next
;
2538 c_elt
= c_elt
->next
;
2545 and_elt
.indx
= b_elt
->indx
;
2546 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
2548 and_elt
.bits
[ix
] = b_elt
->bits
[ix
] & c_elt
->bits
[ix
];
2549 overall
|= and_elt
.bits
[ix
];
2552 b_elt
= b_elt
->next
;
2553 c_elt
= c_elt
->next
;
2557 /* Now find a place to insert AND_ELT. */
2560 ix
= a_elt
? a_elt
->indx
: and_elt
.indx
;
2561 if (ix
== and_elt
.indx
)
2562 changed
= bitmap_elt_ior (a
, a_elt
, a_prev
, a_elt
, &and_elt
, changed
);
2563 else if (ix
> and_elt
.indx
)
2564 changed
= bitmap_elt_copy (a
, NULL
, a_prev
, &and_elt
, changed
);
2566 a_prev
= *a_prev_pnext
;
2567 a_prev_pnext
= &a_prev
->next
;
2568 a_elt
= *a_prev_pnext
;
2570 /* If A lagged behind B/C, we advanced it so loop once more. */
2572 while (ix
< and_elt
.indx
);
2576 gcc_checking_assert (!a
->current
== !a
->first
);
2578 a
->indx
= a
->current
->indx
;
2582 /* Compute hash of bitmap (for purposes of hashing). */
2585 bitmap_hash (const_bitmap head
)
2587 const bitmap_element
*ptr
;
2588 BITMAP_WORD hash
= 0;
2591 gcc_checking_assert (!head
->tree_form
);
2593 for (ptr
= head
->first
; ptr
; ptr
= ptr
->next
)
2596 for (ix
= 0; ix
!= BITMAP_ELEMENT_WORDS
; ix
++)
2597 hash
^= ptr
->bits
[ix
];
2599 return (hashval_t
)hash
;
2603 /* Function to obtain a vector of bitmap elements in bit order from
2604 HEAD in tree view. */
2607 bitmap_tree_to_vec (vec
<bitmap_element
*> &elts
, const_bitmap head
)
2609 gcc_checking_assert (head
->tree_form
);
2610 auto_vec
<bitmap_element
*, 32> stack
;
2611 bitmap_element
*e
= head
->first
;
2616 stack
.safe_push (e
);
2619 if (stack
.is_empty ())
2628 /* Debugging function to print out the contents of a bitmap element. */
2631 debug_bitmap_elt_file (FILE *file
, const bitmap_element
*ptr
)
2633 unsigned int i
, j
, col
= 26;
2635 fprintf (file
, "\t" HOST_PTR_PRINTF
" next = " HOST_PTR_PRINTF
2636 " prev = " HOST_PTR_PRINTF
" indx = %u\n\t\tbits = {",
2637 (const void*) ptr
, (const void*) ptr
->next
,
2638 (const void*) ptr
->prev
, ptr
->indx
);
2640 for (i
= 0; i
< BITMAP_ELEMENT_WORDS
; i
++)
2641 for (j
= 0; j
< BITMAP_WORD_BITS
; j
++)
2642 if ((ptr
->bits
[i
] >> j
) & 1)
2646 fprintf (file
, "\n\t\t\t");
2650 fprintf (file
, " %u", (ptr
->indx
* BITMAP_ELEMENT_ALL_BITS
2651 + i
* BITMAP_WORD_BITS
+ j
));
2655 fprintf (file
, " }\n");
2658 /* Debugging function to print out the contents of a bitmap. */
2661 debug_bitmap_file (FILE *file
, const_bitmap head
)
2663 const bitmap_element
*ptr
;
2665 fprintf (file
, "\nfirst = " HOST_PTR_PRINTF
2666 " current = " HOST_PTR_PRINTF
" indx = %u\n",
2667 (void *) head
->first
, (void *) head
->current
, head
->indx
);
2669 if (head
->tree_form
)
2671 auto_vec
<bitmap_element
*, 32> elts
;
2672 bitmap_tree_to_vec (elts
, head
);
2673 for (unsigned i
= 0; i
< elts
.length (); ++i
)
2674 debug_bitmap_elt_file (file
, elts
[i
]);
2677 for (ptr
= head
->first
; ptr
; ptr
= ptr
->next
)
2678 debug_bitmap_elt_file (file
, ptr
);
2681 /* Function to be called from the debugger to print the contents
2685 debug_bitmap (const_bitmap head
)
2687 debug_bitmap_file (stderr
, head
);
2690 /* Function to print out the contents of a bitmap. Unlike debug_bitmap_file,
2691 it does not print anything but the bits. */
2694 bitmap_print (FILE *file
, const_bitmap head
, const char *prefix
,
2697 const char *comma
= "";
2700 fputs (prefix
, file
);
2701 if (head
->tree_form
)
2703 auto_vec
<bitmap_element
*, 32> elts
;
2704 bitmap_tree_to_vec (elts
, head
);
2705 for (i
= 0; i
< elts
.length (); ++i
)
2706 for (unsigned ix
= 0; ix
!= BITMAP_ELEMENT_WORDS
; ++ix
)
2708 BITMAP_WORD word
= elts
[i
]->bits
[ix
];
2709 for (unsigned bit
= 0; bit
!= BITMAP_WORD_BITS
; ++bit
)
2710 if (word
& ((BITMAP_WORD
)1 << bit
))
2712 fprintf (file
, "%s%d", comma
,
2713 (bit
+ BITMAP_WORD_BITS
* ix
2714 + elts
[i
]->indx
* BITMAP_ELEMENT_ALL_BITS
));
2722 EXECUTE_IF_SET_IN_BITMAP (head
, 0, i
, bi
)
2724 fprintf (file
, "%s%d", comma
, i
);
2728 fputs (suffix
, file
);
2731 /* Output per-bitmap memory usage statistics. */
2733 dump_bitmap_statistics (void)
2735 if (!GATHER_STATISTICS
)
2738 bitmap_mem_desc
.dump (BITMAP_ORIGIN
);
2742 debug (const bitmap_head
&ref
)
2744 dump_bitmap (stderr
, &ref
);
2748 debug (const bitmap_head
*ptr
)
2753 fprintf (stderr
, "<nil>\n");
2757 bitmap_head::dump ()
2764 namespace selftest
{
2766 /* Selftests for bitmaps. */
2768 /* Freshly-created bitmaps ought to be empty. */
2773 bitmap b
= bitmap_gc_alloc ();
2774 ASSERT_TRUE (bitmap_empty_p (b
));
2777 /* Verify bitmap_set_range. */
2782 bitmap b
= bitmap_gc_alloc ();
2783 ASSERT_TRUE (bitmap_empty_p (b
));
2785 bitmap_set_range (b
, 7, 5);
2786 ASSERT_FALSE (bitmap_empty_p (b
));
2787 ASSERT_EQ (5, bitmap_count_bits (b
));
2789 /* Verify bitmap_bit_p at the boundaries. */
2790 ASSERT_FALSE (bitmap_bit_p (b
, 6));
2791 ASSERT_TRUE (bitmap_bit_p (b
, 7));
2792 ASSERT_TRUE (bitmap_bit_p (b
, 11));
2793 ASSERT_FALSE (bitmap_bit_p (b
, 12));
2796 /* Verify splitting a range into two pieces using bitmap_clear_bit. */
2799 test_clear_bit_in_middle ()
2801 bitmap b
= bitmap_gc_alloc ();
2803 /* Set b to [100..200]. */
2804 bitmap_set_range (b
, 100, 100);
2805 ASSERT_EQ (100, bitmap_count_bits (b
));
2807 /* Clear a bit in the middle. */
2808 bool changed
= bitmap_clear_bit (b
, 150);
2809 ASSERT_TRUE (changed
);
2810 ASSERT_EQ (99, bitmap_count_bits (b
));
2811 ASSERT_TRUE (bitmap_bit_p (b
, 149));
2812 ASSERT_FALSE (bitmap_bit_p (b
, 150));
2813 ASSERT_TRUE (bitmap_bit_p (b
, 151));
2816 /* Verify bitmap_copy. */
2821 bitmap src
= bitmap_gc_alloc ();
2822 bitmap_set_range (src
, 40, 10);
2824 bitmap dst
= bitmap_gc_alloc ();
2825 ASSERT_FALSE (bitmap_equal_p (src
, dst
));
2826 bitmap_copy (dst
, src
);
2827 ASSERT_TRUE (bitmap_equal_p (src
, dst
));
2829 /* Verify that we can make them unequal again... */
2830 bitmap_set_range (src
, 70, 5);
2831 ASSERT_FALSE (bitmap_equal_p (src
, dst
));
2833 /* ...and that changing src after the copy didn't affect
2835 ASSERT_FALSE (bitmap_bit_p (dst
, 70));
2838 /* Verify bitmap_single_bit_set_p. */
2841 test_bitmap_single_bit_set_p ()
2843 bitmap b
= bitmap_gc_alloc ();
2845 ASSERT_FALSE (bitmap_single_bit_set_p (b
));
2847 bitmap_set_range (b
, 42, 1);
2848 ASSERT_TRUE (bitmap_single_bit_set_p (b
));
2849 ASSERT_EQ (42, bitmap_first_set_bit (b
));
2851 bitmap_set_range (b
, 1066, 1);
2852 ASSERT_FALSE (bitmap_single_bit_set_p (b
));
2853 ASSERT_EQ (42, bitmap_first_set_bit (b
));
2855 bitmap_clear_range (b
, 0, 100);
2856 ASSERT_TRUE (bitmap_single_bit_set_p (b
));
2857 ASSERT_EQ (1066, bitmap_first_set_bit (b
));
2860 /* Run all of the selftests within this file. */
2867 test_clear_bit_in_middle ();
2869 test_bitmap_single_bit_set_p ();
2872 } // namespace selftest
2873 #endif /* CHECKING_P */
2875 #include "gt-bitmap.h"