1 /* Functions to support general ended bitmaps.
2 Copyright (C) 1997, 1998, 1999, 2000, 2001, 2003, 2004, 2005,
3 2006, 2007, 2008, 2009 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
32 #ifdef GATHER_STATISTICS
34 /* Store information about each particular bitmap. */
35 struct bitmap_descriptor
41 HOST_WIDEST_INT allocated
;
43 HOST_WIDEST_INT current
;
48 /* Hashtable mapping bitmap names to descriptors. */
49 static htab_t bitmap_desc_hash
;
51 /* Hashtable helpers. */
53 hash_descriptor (const void *p
)
55 const struct bitmap_descriptor
*const d
=
56 (const struct bitmap_descriptor
*) p
;
57 return htab_hash_pointer (d
->file
) + d
->line
;
66 eq_descriptor (const void *p1
, const void *p2
)
68 const struct bitmap_descriptor
*const d
=
69 (const struct bitmap_descriptor
*) p1
;
70 const struct loc
*const l
= (const struct loc
*) p2
;
71 return d
->file
== l
->file
&& d
->function
== l
->function
&& d
->line
== l
->line
;
74 /* For given file and line, return descriptor, create new if needed. */
75 static struct bitmap_descriptor
*
76 bitmap_descriptor (const char *file
, const char *function
, int line
)
78 struct bitmap_descriptor
**slot
;
82 loc
.function
= function
;
85 if (!bitmap_desc_hash
)
86 bitmap_desc_hash
= htab_create (10, hash_descriptor
, eq_descriptor
, NULL
);
88 slot
= (struct bitmap_descriptor
**)
89 htab_find_slot_with_hash (bitmap_desc_hash
, &loc
,
90 htab_hash_pointer (file
) + line
,
94 *slot
= XCNEW (struct bitmap_descriptor
);
96 (*slot
)->function
= function
;
101 /* Register new bitmap. */
103 bitmap_register (bitmap b MEM_STAT_DECL
)
105 b
->desc
= bitmap_descriptor (_loc_name
, _loc_function
, _loc_line
);
109 /* Account the overhead. */
111 register_overhead (bitmap b
, int amount
)
113 b
->desc
->current
+= amount
;
115 b
->desc
->allocated
+= amount
;
116 gcc_assert (b
->desc
->current
>= 0);
117 if (b
->desc
->peak
< b
->desc
->current
)
118 b
->desc
->peak
= b
->desc
->current
;
123 bitmap_element bitmap_zero_bits
; /* An element of all zero bits. */
124 bitmap_obstack bitmap_default_obstack
; /* The default bitmap obstack. */
125 static int bitmap_default_obstack_depth
;
126 static GTY((deletable
)) bitmap_element
*bitmap_ggc_free
; /* Freelist of
129 static void bitmap_elem_to_freelist (bitmap
, bitmap_element
*);
130 static void bitmap_element_free (bitmap
, bitmap_element
*);
131 static bitmap_element
*bitmap_element_allocate (bitmap
);
132 static int bitmap_element_zerop (const bitmap_element
*);
133 static void bitmap_element_link (bitmap
, bitmap_element
*);
134 static bitmap_element
*bitmap_elt_insert_after (bitmap
, bitmap_element
*, unsigned int);
135 static void bitmap_elt_clear_from (bitmap
, bitmap_element
*);
136 static bitmap_element
*bitmap_find_bit (bitmap
, unsigned int);
139 /* Add ELEM to the appropriate freelist. */
141 bitmap_elem_to_freelist (bitmap head
, bitmap_element
*elt
)
143 bitmap_obstack
*bit_obstack
= head
->obstack
;
148 elt
->prev
= bit_obstack
->elements
;
149 bit_obstack
->elements
= elt
;
153 elt
->prev
= bitmap_ggc_free
;
154 bitmap_ggc_free
= elt
;
158 /* Free a bitmap element. Since these are allocated off the
159 bitmap_obstack, "free" actually means "put onto the freelist". */
162 bitmap_element_free (bitmap head
, bitmap_element
*elt
)
164 bitmap_element
*next
= elt
->next
;
165 bitmap_element
*prev
= elt
->prev
;
173 if (head
->first
== elt
)
176 /* Since the first thing we try is to insert before current,
177 make current the next entry in preference to the previous. */
178 if (head
->current
== elt
)
180 head
->current
= next
!= 0 ? next
: prev
;
182 head
->indx
= head
->current
->indx
;
186 #ifdef GATHER_STATISTICS
187 register_overhead (head
, -((int)sizeof (bitmap_element
)));
189 bitmap_elem_to_freelist (head
, elt
);
192 /* Allocate a bitmap element. The bits are cleared, but nothing else is. */
194 static inline bitmap_element
*
195 bitmap_element_allocate (bitmap head
)
197 bitmap_element
*element
;
198 bitmap_obstack
*bit_obstack
= head
->obstack
;
202 element
= bit_obstack
->elements
;
205 /* Use up the inner list first before looking at the next
206 element of the outer list. */
209 bit_obstack
->elements
= element
->next
;
210 bit_obstack
->elements
->prev
= element
->prev
;
213 /* Inner list was just a singleton. */
214 bit_obstack
->elements
= element
->prev
;
216 element
= XOBNEW (&bit_obstack
->obstack
, bitmap_element
);
220 element
= bitmap_ggc_free
;
222 /* Use up the inner list first before looking at the next
223 element of the outer list. */
226 bitmap_ggc_free
= element
->next
;
227 bitmap_ggc_free
->prev
= element
->prev
;
230 /* Inner list was just a singleton. */
231 bitmap_ggc_free
= element
->prev
;
233 element
= ggc_alloc_bitmap_element_def ();
236 #ifdef GATHER_STATISTICS
237 register_overhead (head
, sizeof (bitmap_element
));
239 memset (element
->bits
, 0, sizeof (element
->bits
));
244 /* Remove ELT and all following elements from bitmap HEAD. */
247 bitmap_elt_clear_from (bitmap head
, bitmap_element
*elt
)
249 bitmap_element
*prev
;
250 bitmap_obstack
*bit_obstack
= head
->obstack
;
251 #ifdef GATHER_STATISTICS
256 #ifdef GATHER_STATISTICS
258 for (prev
= elt
; prev
; prev
= prev
->next
)
260 register_overhead (head
, -sizeof (bitmap_element
) * n
);
267 if (head
->current
->indx
> prev
->indx
)
269 head
->current
= prev
;
270 head
->indx
= prev
->indx
;
276 head
->current
= NULL
;
280 /* Put the entire list onto the free list in one operation. */
283 elt
->prev
= bit_obstack
->elements
;
284 bit_obstack
->elements
= elt
;
288 elt
->prev
= bitmap_ggc_free
;
289 bitmap_ggc_free
= elt
;
293 /* Clear a bitmap by freeing the linked list. */
296 bitmap_clear (bitmap head
)
299 bitmap_elt_clear_from (head
, head
->first
);
302 /* Initialize a bitmap obstack. If BIT_OBSTACK is NULL, initialize
303 the default bitmap obstack. */
306 bitmap_obstack_initialize (bitmap_obstack
*bit_obstack
)
310 if (bitmap_default_obstack_depth
++)
312 bit_obstack
= &bitmap_default_obstack
;
315 #if !defined(__GNUC__) || (__GNUC__ < 2)
316 #define __alignof__(type) 0
319 bit_obstack
->elements
= NULL
;
320 bit_obstack
->heads
= NULL
;
321 obstack_specify_allocation (&bit_obstack
->obstack
, OBSTACK_CHUNK_SIZE
,
322 __alignof__ (bitmap_element
),
327 /* Release the memory from a bitmap obstack. If BIT_OBSTACK is NULL,
328 release the default bitmap obstack. */
331 bitmap_obstack_release (bitmap_obstack
*bit_obstack
)
335 if (--bitmap_default_obstack_depth
)
337 gcc_assert (bitmap_default_obstack_depth
> 0);
340 bit_obstack
= &bitmap_default_obstack
;
343 bit_obstack
->elements
= NULL
;
344 bit_obstack
->heads
= NULL
;
345 obstack_free (&bit_obstack
->obstack
, NULL
);
348 /* Create a new bitmap on an obstack. If BIT_OBSTACK is NULL, create
349 it on the default bitmap obstack. */
352 bitmap_obstack_alloc_stat (bitmap_obstack
*bit_obstack MEM_STAT_DECL
)
357 bit_obstack
= &bitmap_default_obstack
;
358 map
= bit_obstack
->heads
;
360 bit_obstack
->heads
= (struct bitmap_head_def
*) map
->first
;
362 map
= XOBNEW (&bit_obstack
->obstack
, bitmap_head
);
363 bitmap_initialize_stat (map
, bit_obstack PASS_MEM_STAT
);
364 #ifdef GATHER_STATISTICS
365 register_overhead (map
, sizeof (bitmap_head
));
371 /* Create a new GCd bitmap. */
374 bitmap_gc_alloc_stat (ALONE_MEM_STAT_DECL
)
378 map
= ggc_alloc_bitmap_head_def ();
379 bitmap_initialize_stat (map
, NULL PASS_MEM_STAT
);
380 #ifdef GATHER_STATISTICS
381 register_overhead (map
, sizeof (bitmap_head
));
387 /* Release an obstack allocated bitmap. */
390 bitmap_obstack_free (bitmap map
)
395 map
->first
= (bitmap_element
*) map
->obstack
->heads
;
396 #ifdef GATHER_STATISTICS
397 register_overhead (map
, -((int)sizeof (bitmap_head
)));
399 map
->obstack
->heads
= map
;
404 /* Return nonzero if all bits in an element are zero. */
407 bitmap_element_zerop (const bitmap_element
*element
)
409 #if BITMAP_ELEMENT_WORDS == 2
410 return (element
->bits
[0] | element
->bits
[1]) == 0;
414 for (i
= 0; i
< BITMAP_ELEMENT_WORDS
; i
++)
415 if (element
->bits
[i
] != 0)
422 /* Link the bitmap element into the current bitmap linked list. */
425 bitmap_element_link (bitmap head
, bitmap_element
*element
)
427 unsigned int indx
= element
->indx
;
430 /* If this is the first and only element, set it in. */
431 if (head
->first
== 0)
433 element
->next
= element
->prev
= 0;
434 head
->first
= element
;
437 /* If this index is less than that of the current element, it goes someplace
438 before the current element. */
439 else if (indx
< head
->indx
)
441 for (ptr
= head
->current
;
442 ptr
->prev
!= 0 && ptr
->prev
->indx
> indx
;
447 ptr
->prev
->next
= element
;
449 head
->first
= element
;
451 element
->prev
= ptr
->prev
;
456 /* Otherwise, it must go someplace after the current element. */
459 for (ptr
= head
->current
;
460 ptr
->next
!= 0 && ptr
->next
->indx
< indx
;
465 ptr
->next
->prev
= element
;
467 element
->next
= ptr
->next
;
472 /* Set up so this is the first element searched. */
473 head
->current
= element
;
477 /* Insert a new uninitialized element into bitmap HEAD after element
478 ELT. If ELT is NULL, insert the element at the start. Return the
481 static bitmap_element
*
482 bitmap_elt_insert_after (bitmap head
, bitmap_element
*elt
, unsigned int indx
)
484 bitmap_element
*node
= bitmap_element_allocate (head
);
491 head
->current
= node
;
494 node
->next
= head
->first
;
496 node
->next
->prev
= node
;
502 gcc_checking_assert (head
->current
);
503 node
->next
= elt
->next
;
505 node
->next
->prev
= node
;
512 /* Copy a bitmap to another bitmap. */
515 bitmap_copy (bitmap to
, const_bitmap from
)
517 const bitmap_element
*from_ptr
;
518 bitmap_element
*to_ptr
= 0;
522 /* Copy elements in forward direction one at a time. */
523 for (from_ptr
= from
->first
; from_ptr
; from_ptr
= from_ptr
->next
)
525 bitmap_element
*to_elt
= bitmap_element_allocate (to
);
527 to_elt
->indx
= from_ptr
->indx
;
528 memcpy (to_elt
->bits
, from_ptr
->bits
, sizeof (to_elt
->bits
));
530 /* Here we have a special case of bitmap_element_link, for the case
531 where we know the links are being entered in sequence. */
534 to
->first
= to
->current
= to_elt
;
535 to
->indx
= from_ptr
->indx
;
536 to_elt
->next
= to_elt
->prev
= 0;
540 to_elt
->prev
= to_ptr
;
542 to_ptr
->next
= to_elt
;
549 /* Find a bitmap element that would hold a bitmap's bit.
550 Update the `current' field even if we can't find an element that
551 would hold the bitmap's bit to make eventual allocation
554 static inline bitmap_element
*
555 bitmap_find_bit (bitmap head
, unsigned int bit
)
557 bitmap_element
*element
;
558 unsigned int indx
= bit
/ BITMAP_ELEMENT_ALL_BITS
;
560 if (head
->current
== 0
561 || head
->indx
== indx
)
562 return head
->current
;
563 #ifdef GATHER_STATISTICS
564 head
->desc
->nsearches
++;
567 if (head
->indx
< indx
)
568 /* INDX is beyond head->indx. Search from head->current
570 for (element
= head
->current
;
571 element
->next
!= 0 && element
->indx
< indx
;
572 element
= element
->next
)
573 #ifdef GATHER_STATISTICS
574 head
->desc
->search_iter
++;
579 else if (head
->indx
/ 2 < indx
)
580 /* INDX is less than head->indx and closer to head->indx than to
581 0. Search from head->current backward. */
582 for (element
= head
->current
;
583 element
->prev
!= 0 && element
->indx
> indx
;
584 element
= element
->prev
)
585 #ifdef GATHER_STATISTICS
586 head
->desc
->search_iter
++;
592 /* INDX is less than head->indx and closer to 0 than to
593 head->indx. Search from head->first forward. */
594 for (element
= head
->first
;
595 element
->next
!= 0 && element
->indx
< indx
;
596 element
= element
->next
)
597 #ifdef GATHER_STATISTICS
598 head
->desc
->search_iter
++;
603 /* `element' is the nearest to the one we want. If it's not the one we
604 want, the one we want doesn't exist. */
605 head
->current
= element
;
606 head
->indx
= element
->indx
;
607 if (element
!= 0 && element
->indx
!= indx
)
613 /* Clear a single bit in a bitmap. Return true if the bit changed. */
616 bitmap_clear_bit (bitmap head
, int bit
)
618 bitmap_element
*const ptr
= bitmap_find_bit (head
, bit
);
622 unsigned bit_num
= bit
% BITMAP_WORD_BITS
;
623 unsigned word_num
= bit
/ BITMAP_WORD_BITS
% BITMAP_ELEMENT_WORDS
;
624 BITMAP_WORD bit_val
= ((BITMAP_WORD
) 1) << bit_num
;
625 bool res
= (ptr
->bits
[word_num
] & bit_val
) != 0;
627 ptr
->bits
[word_num
] &= ~bit_val
;
629 /* If we cleared the entire word, free up the element. */
630 if (bitmap_element_zerop (ptr
))
631 bitmap_element_free (head
, ptr
);
639 /* Set a single bit in a bitmap. Return true if the bit changed. */
642 bitmap_set_bit (bitmap head
, int bit
)
644 bitmap_element
*ptr
= bitmap_find_bit (head
, bit
);
645 unsigned word_num
= bit
/ BITMAP_WORD_BITS
% BITMAP_ELEMENT_WORDS
;
646 unsigned bit_num
= bit
% BITMAP_WORD_BITS
;
647 BITMAP_WORD bit_val
= ((BITMAP_WORD
) 1) << bit_num
;
651 ptr
= bitmap_element_allocate (head
);
652 ptr
->indx
= bit
/ BITMAP_ELEMENT_ALL_BITS
;
653 ptr
->bits
[word_num
] = bit_val
;
654 bitmap_element_link (head
, ptr
);
659 bool res
= (ptr
->bits
[word_num
] & bit_val
) == 0;
661 ptr
->bits
[word_num
] |= bit_val
;
666 /* Return whether a bit is set within a bitmap. */
669 bitmap_bit_p (bitmap head
, int bit
)
675 ptr
= bitmap_find_bit (head
, bit
);
679 bit_num
= bit
% BITMAP_WORD_BITS
;
680 word_num
= bit
/ BITMAP_WORD_BITS
% BITMAP_ELEMENT_WORDS
;
682 return (ptr
->bits
[word_num
] >> bit_num
) & 1;
685 #if GCC_VERSION < 3400
686 /* Table of number of set bits in a character, indexed by value of char. */
687 static const unsigned char popcount_table
[] =
689 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,
690 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,
691 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,
692 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,
693 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,
694 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,
695 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,
696 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,
700 bitmap_popcount (BITMAP_WORD a
)
702 unsigned long ret
= 0;
705 /* Just do this the table way for now */
706 for (i
= 0; i
< BITMAP_WORD_BITS
; i
+= 8)
707 ret
+= popcount_table
[(a
>> i
) & 0xff];
711 /* Count the number of bits set in the bitmap, and return it. */
714 bitmap_count_bits (const_bitmap a
)
716 unsigned long count
= 0;
717 const bitmap_element
*elt
;
720 for (elt
= a
->first
; elt
; elt
= elt
->next
)
722 for (ix
= 0; ix
!= BITMAP_ELEMENT_WORDS
; ix
++)
724 #if GCC_VERSION >= 3400
725 /* Note that popcountl matches BITMAP_WORD in type, so the actual size
726 of BITMAP_WORD is not material. */
727 count
+= __builtin_popcountl (elt
->bits
[ix
]);
729 count
+= bitmap_popcount (elt
->bits
[ix
]);
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
;
848 /* Binary search for the last set bit. */
849 #if GCC_VERSION >= 3004
850 gcc_assert (sizeof(long) == sizeof (word
));
851 bit_no
+= sizeof (long) * 8 - __builtin_ctzl (word
);
853 #if BITMAP_WORD_BITS > 64
854 #error "Fill out the table."
856 #if BITMAP_WORD_BITS > 32
857 if ((word
& 0xffffffff00000000))
858 word
>>= 32, bit_no
+= 32;
860 if (word
& 0xffff0000)
861 word
>>= 16, bit_no
+= 16;
862 if (!(word
& 0xff00))
863 word
>>= 8, bit_no
+= 8;
865 word
>>= 4, bit_no
+= 4;
867 word
>>= 2, bit_no
+= 2;
869 word
>>= 1, bit_no
+= 1;
872 gcc_checking_assert (word
& 1);
880 bitmap_and (bitmap dst
, const_bitmap a
, const_bitmap b
)
882 bitmap_element
*dst_elt
= dst
->first
;
883 const bitmap_element
*a_elt
= a
->first
;
884 const bitmap_element
*b_elt
= b
->first
;
885 bitmap_element
*dst_prev
= NULL
;
887 gcc_assert (dst
!= a
&& dst
!= b
);
891 bitmap_copy (dst
, a
);
895 while (a_elt
&& b_elt
)
897 if (a_elt
->indx
< b_elt
->indx
)
899 else if (b_elt
->indx
< a_elt
->indx
)
903 /* Matching elts, generate A & B. */
908 dst_elt
= bitmap_elt_insert_after (dst
, dst_prev
, a_elt
->indx
);
910 dst_elt
->indx
= a_elt
->indx
;
911 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
913 BITMAP_WORD r
= a_elt
->bits
[ix
] & b_elt
->bits
[ix
];
915 dst_elt
->bits
[ix
] = r
;
921 dst_elt
= dst_elt
->next
;
927 /* Ensure that dst->current is valid. */
928 dst
->current
= dst
->first
;
929 bitmap_elt_clear_from (dst
, dst_elt
);
930 gcc_checking_assert (!dst
->current
== !dst
->first
);
932 dst
->indx
= dst
->current
->indx
;
938 bitmap_and_into (bitmap a
, const_bitmap b
)
940 bitmap_element
*a_elt
= a
->first
;
941 const bitmap_element
*b_elt
= b
->first
;
942 bitmap_element
*next
;
947 while (a_elt
&& b_elt
)
949 if (a_elt
->indx
< b_elt
->indx
)
952 bitmap_element_free (a
, a_elt
);
955 else if (b_elt
->indx
< a_elt
->indx
)
959 /* Matching elts, generate A &= B. */
963 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
965 BITMAP_WORD r
= a_elt
->bits
[ix
] & b_elt
->bits
[ix
];
972 bitmap_element_free (a
, a_elt
);
977 bitmap_elt_clear_from (a
, a_elt
);
978 gcc_checking_assert (!a
->current
== !a
->first
979 && (!a
->current
|| a
->indx
== a
->current
->indx
));
983 /* Insert an element equal to SRC_ELT after DST_PREV, overwriting DST_ELT
984 if non-NULL. CHANGED is true if the destination bitmap had already been
985 changed; the new value of CHANGED is returned. */
988 bitmap_elt_copy (bitmap dst
, bitmap_element
*dst_elt
, bitmap_element
*dst_prev
,
989 const bitmap_element
*src_elt
, bool changed
)
991 if (!changed
&& dst_elt
&& dst_elt
->indx
== src_elt
->indx
)
995 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
996 if (src_elt
->bits
[ix
] != dst_elt
->bits
[ix
])
998 dst_elt
->bits
[ix
] = src_elt
->bits
[ix
];
1006 dst_elt
= bitmap_elt_insert_after (dst
, dst_prev
, src_elt
->indx
);
1008 dst_elt
->indx
= src_elt
->indx
;
1009 memcpy (dst_elt
->bits
, src_elt
->bits
, sizeof (dst_elt
->bits
));
1019 bitmap_and_compl (bitmap dst
, const_bitmap a
, const_bitmap b
)
1021 bitmap_element
*dst_elt
= dst
->first
;
1022 const bitmap_element
*a_elt
= a
->first
;
1023 const bitmap_element
*b_elt
= b
->first
;
1024 bitmap_element
*dst_prev
= NULL
;
1025 bitmap_element
**dst_prev_pnext
= &dst
->first
;
1026 bool changed
= false;
1028 gcc_assert (dst
!= a
&& dst
!= b
);
1032 changed
= !bitmap_empty_p (dst
);
1039 while (b_elt
&& b_elt
->indx
< a_elt
->indx
)
1040 b_elt
= b_elt
->next
;
1042 if (!b_elt
|| b_elt
->indx
> a_elt
->indx
)
1044 changed
= bitmap_elt_copy (dst
, dst_elt
, dst_prev
, a_elt
, changed
);
1045 dst_prev
= *dst_prev_pnext
;
1046 dst_prev_pnext
= &dst_prev
->next
;
1047 dst_elt
= *dst_prev_pnext
;
1048 a_elt
= a_elt
->next
;
1053 /* Matching elts, generate A & ~B. */
1055 BITMAP_WORD ior
= 0;
1057 if (!changed
&& dst_elt
&& dst_elt
->indx
== a_elt
->indx
)
1059 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1061 BITMAP_WORD r
= a_elt
->bits
[ix
] & ~b_elt
->bits
[ix
];
1063 if (dst_elt
->bits
[ix
] != r
)
1066 dst_elt
->bits
[ix
] = r
;
1074 if (!dst_elt
|| dst_elt
->indx
> a_elt
->indx
)
1076 dst_elt
= bitmap_elt_insert_after (dst
, dst_prev
, a_elt
->indx
);
1081 dst_elt
->indx
= a_elt
->indx
;
1082 new_element
= false;
1085 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1087 BITMAP_WORD r
= a_elt
->bits
[ix
] & ~b_elt
->bits
[ix
];
1089 dst_elt
->bits
[ix
] = r
;
1097 changed
|= !new_element
;
1098 bitmap_element_free (dst
, dst_elt
);
1099 dst_elt
= *dst_prev_pnext
;
1105 dst_prev
= *dst_prev_pnext
;
1106 dst_prev_pnext
= &dst_prev
->next
;
1107 dst_elt
= *dst_prev_pnext
;
1109 a_elt
= a_elt
->next
;
1110 b_elt
= b_elt
->next
;
1114 /* Ensure that dst->current is valid. */
1115 dst
->current
= dst
->first
;
1120 bitmap_elt_clear_from (dst
, dst_elt
);
1122 gcc_checking_assert (!dst
->current
== !dst
->first
);
1124 dst
->indx
= dst
->current
->indx
;
1129 /* A &= ~B. Returns true if A changes */
1132 bitmap_and_compl_into (bitmap a
, const_bitmap b
)
1134 bitmap_element
*a_elt
= a
->first
;
1135 const bitmap_element
*b_elt
= b
->first
;
1136 bitmap_element
*next
;
1137 BITMAP_WORD changed
= 0;
1141 if (bitmap_empty_p (a
))
1150 while (a_elt
&& b_elt
)
1152 if (a_elt
->indx
< b_elt
->indx
)
1153 a_elt
= a_elt
->next
;
1154 else if (b_elt
->indx
< a_elt
->indx
)
1155 b_elt
= b_elt
->next
;
1158 /* Matching elts, generate A &= ~B. */
1160 BITMAP_WORD ior
= 0;
1162 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1164 BITMAP_WORD cleared
= a_elt
->bits
[ix
] & b_elt
->bits
[ix
];
1165 BITMAP_WORD r
= a_elt
->bits
[ix
] ^ cleared
;
1167 a_elt
->bits
[ix
] = r
;
1173 bitmap_element_free (a
, a_elt
);
1175 b_elt
= b_elt
->next
;
1178 gcc_checking_assert (!a
->current
== !a
->first
1179 && (!a
->current
|| a
->indx
== a
->current
->indx
));
1180 return changed
!= 0;
1183 /* Set COUNT bits from START in HEAD. */
1185 bitmap_set_range (bitmap head
, unsigned int start
, unsigned int count
)
1187 unsigned int first_index
, end_bit_plus1
, last_index
;
1188 bitmap_element
*elt
, *elt_prev
;
1194 first_index
= start
/ BITMAP_ELEMENT_ALL_BITS
;
1195 end_bit_plus1
= start
+ count
;
1196 last_index
= (end_bit_plus1
- 1) / BITMAP_ELEMENT_ALL_BITS
;
1197 elt
= bitmap_find_bit (head
, start
);
1199 /* If bitmap_find_bit returns zero, the current is the closest block
1200 to the result. Otherwise, just use bitmap_element_allocate to
1201 ensure ELT is set; in the loop below, ELT == NULL means "insert
1202 at the end of the bitmap". */
1205 elt
= bitmap_element_allocate (head
);
1206 elt
->indx
= first_index
;
1207 bitmap_element_link (head
, elt
);
1210 gcc_checking_assert (elt
->indx
== first_index
);
1211 elt_prev
= elt
->prev
;
1212 for (i
= first_index
; i
<= last_index
; i
++)
1214 unsigned elt_start_bit
= i
* BITMAP_ELEMENT_ALL_BITS
;
1215 unsigned elt_end_bit_plus1
= elt_start_bit
+ BITMAP_ELEMENT_ALL_BITS
;
1217 unsigned int first_word_to_mod
;
1218 BITMAP_WORD first_mask
;
1219 unsigned int last_word_to_mod
;
1220 BITMAP_WORD last_mask
;
1223 if (!elt
|| elt
->indx
!= i
)
1224 elt
= bitmap_elt_insert_after (head
, elt_prev
, i
);
1226 if (elt_start_bit
<= start
)
1228 /* The first bit to turn on is somewhere inside this
1230 first_word_to_mod
= (start
- elt_start_bit
) / BITMAP_WORD_BITS
;
1232 /* This mask should have 1s in all bits >= start position. */
1234 (((BITMAP_WORD
) 1) << ((start
% BITMAP_WORD_BITS
))) - 1;
1235 first_mask
= ~first_mask
;
1239 /* The first bit to turn on is below this start of this elt. */
1240 first_word_to_mod
= 0;
1241 first_mask
= ~(BITMAP_WORD
) 0;
1244 if (elt_end_bit_plus1
<= end_bit_plus1
)
1246 /* The last bit to turn on is beyond this elt. */
1247 last_word_to_mod
= BITMAP_ELEMENT_WORDS
- 1;
1248 last_mask
= ~(BITMAP_WORD
) 0;
1252 /* The last bit to turn on is inside to this elt. */
1254 (end_bit_plus1
- elt_start_bit
) / BITMAP_WORD_BITS
;
1256 /* The last mask should have 1s below the end bit. */
1258 (((BITMAP_WORD
) 1) << ((end_bit_plus1
% BITMAP_WORD_BITS
))) - 1;
1261 if (first_word_to_mod
== last_word_to_mod
)
1263 BITMAP_WORD mask
= first_mask
& last_mask
;
1264 elt
->bits
[first_word_to_mod
] |= mask
;
1268 elt
->bits
[first_word_to_mod
] |= first_mask
;
1269 if (BITMAP_ELEMENT_WORDS
> 2)
1270 for (ix
= first_word_to_mod
+ 1; ix
< last_word_to_mod
; ix
++)
1271 elt
->bits
[ix
] = ~(BITMAP_WORD
) 0;
1272 elt
->bits
[last_word_to_mod
] |= last_mask
;
1279 head
->current
= elt
? elt
: elt_prev
;
1280 head
->indx
= head
->current
->indx
;
1283 /* Clear COUNT bits from START in HEAD. */
1285 bitmap_clear_range (bitmap head
, unsigned int start
, unsigned int count
)
1287 unsigned int first_index
, end_bit_plus1
, last_index
;
1288 bitmap_element
*elt
;
1293 first_index
= start
/ BITMAP_ELEMENT_ALL_BITS
;
1294 end_bit_plus1
= start
+ count
;
1295 last_index
= (end_bit_plus1
- 1) / BITMAP_ELEMENT_ALL_BITS
;
1296 elt
= bitmap_find_bit (head
, start
);
1298 /* If bitmap_find_bit returns zero, the current is the closest block
1299 to the result. If the current is less than first index, find the
1300 next one. Otherwise, just set elt to be current. */
1305 if (head
->indx
< first_index
)
1307 elt
= head
->current
->next
;
1312 elt
= head
->current
;
1318 while (elt
&& (elt
->indx
<= last_index
))
1320 bitmap_element
* next_elt
= elt
->next
;
1321 unsigned elt_start_bit
= (elt
->indx
) * BITMAP_ELEMENT_ALL_BITS
;
1322 unsigned elt_end_bit_plus1
= elt_start_bit
+ BITMAP_ELEMENT_ALL_BITS
;
1325 if (elt_start_bit
>= start
&& elt_end_bit_plus1
<= end_bit_plus1
)
1326 /* Get rid of the entire elt and go to the next one. */
1327 bitmap_element_free (head
, elt
);
1330 /* Going to have to knock out some bits in this elt. */
1331 unsigned int first_word_to_mod
;
1332 BITMAP_WORD first_mask
;
1333 unsigned int last_word_to_mod
;
1334 BITMAP_WORD last_mask
;
1338 if (elt_start_bit
<= start
)
1340 /* The first bit to turn off is somewhere inside this
1342 first_word_to_mod
= (start
- elt_start_bit
) / BITMAP_WORD_BITS
;
1344 /* This mask should have 1s in all bits >= start position. */
1346 (((BITMAP_WORD
) 1) << ((start
% BITMAP_WORD_BITS
))) - 1;
1347 first_mask
= ~first_mask
;
1351 /* The first bit to turn off is below this start of this elt. */
1352 first_word_to_mod
= 0;
1354 first_mask
= ~first_mask
;
1357 if (elt_end_bit_plus1
<= end_bit_plus1
)
1359 /* The last bit to turn off is beyond this elt. */
1360 last_word_to_mod
= BITMAP_ELEMENT_WORDS
- 1;
1362 last_mask
= ~last_mask
;
1366 /* The last bit to turn off is inside to this elt. */
1368 (end_bit_plus1
- elt_start_bit
) / BITMAP_WORD_BITS
;
1370 /* The last mask should have 1s below the end bit. */
1372 (((BITMAP_WORD
) 1) << (((end_bit_plus1
) % BITMAP_WORD_BITS
))) - 1;
1376 if (first_word_to_mod
== last_word_to_mod
)
1378 BITMAP_WORD mask
= first_mask
& last_mask
;
1379 elt
->bits
[first_word_to_mod
] &= ~mask
;
1383 elt
->bits
[first_word_to_mod
] &= ~first_mask
;
1384 if (BITMAP_ELEMENT_WORDS
> 2)
1385 for (i
= first_word_to_mod
+ 1; i
< last_word_to_mod
; i
++)
1387 elt
->bits
[last_word_to_mod
] &= ~last_mask
;
1389 for (i
= 0; i
< BITMAP_ELEMENT_WORDS
; i
++)
1395 /* Check to see if there are any bits left. */
1397 bitmap_element_free (head
, elt
);
1404 head
->current
= elt
;
1405 head
->indx
= head
->current
->indx
;
1412 bitmap_compl_and_into (bitmap a
, const_bitmap b
)
1414 bitmap_element
*a_elt
= a
->first
;
1415 const bitmap_element
*b_elt
= b
->first
;
1416 bitmap_element
*a_prev
= NULL
;
1417 bitmap_element
*next
;
1419 gcc_assert (a
!= b
);
1421 if (bitmap_empty_p (a
))
1426 if (bitmap_empty_p (b
))
1432 while (a_elt
|| b_elt
)
1434 if (!b_elt
|| (a_elt
&& a_elt
->indx
< b_elt
->indx
))
1436 /* A is before B. Remove A */
1438 a_prev
= a_elt
->prev
;
1439 bitmap_element_free (a
, a_elt
);
1442 else if (!a_elt
|| b_elt
->indx
< a_elt
->indx
)
1444 /* B is before A. Copy B. */
1445 next
= bitmap_elt_insert_after (a
, a_prev
, b_elt
->indx
);
1446 memcpy (next
->bits
, b_elt
->bits
, sizeof (next
->bits
));
1448 b_elt
= b_elt
->next
;
1452 /* Matching elts, generate A = ~A & B. */
1454 BITMAP_WORD ior
= 0;
1456 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1458 BITMAP_WORD cleared
= a_elt
->bits
[ix
] & b_elt
->bits
[ix
];
1459 BITMAP_WORD r
= b_elt
->bits
[ix
] ^ cleared
;
1461 a_elt
->bits
[ix
] = r
;
1466 bitmap_element_free (a
, a_elt
);
1470 b_elt
= b_elt
->next
;
1473 gcc_checking_assert (!a
->current
== !a
->first
1474 && (!a
->current
|| a
->indx
== a
->current
->indx
));
1479 /* Insert an element corresponding to A_ELT | B_ELT after DST_PREV,
1480 overwriting DST_ELT if non-NULL. CHANGED is true if the destination bitmap
1481 had already been changed; the new value of CHANGED is returned. */
1484 bitmap_elt_ior (bitmap dst
, bitmap_element
*dst_elt
, bitmap_element
*dst_prev
,
1485 const bitmap_element
*a_elt
, const bitmap_element
*b_elt
,
1488 gcc_assert (a_elt
|| b_elt
);
1490 if (a_elt
&& b_elt
&& a_elt
->indx
== b_elt
->indx
)
1492 /* Matching elts, generate A | B. */
1495 if (!changed
&& dst_elt
&& dst_elt
->indx
== a_elt
->indx
)
1497 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1499 BITMAP_WORD r
= a_elt
->bits
[ix
] | b_elt
->bits
[ix
];
1500 if (r
!= dst_elt
->bits
[ix
])
1502 dst_elt
->bits
[ix
] = r
;
1511 dst_elt
= bitmap_elt_insert_after (dst
, dst_prev
, a_elt
->indx
);
1513 dst_elt
->indx
= a_elt
->indx
;
1514 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1516 BITMAP_WORD r
= a_elt
->bits
[ix
] | b_elt
->bits
[ix
];
1517 dst_elt
->bits
[ix
] = r
;
1523 /* Copy a single element. */
1524 const bitmap_element
*src
;
1526 if (!b_elt
|| (a_elt
&& a_elt
->indx
< b_elt
->indx
))
1531 gcc_checking_assert (src
);
1532 changed
= bitmap_elt_copy (dst
, dst_elt
, dst_prev
, src
, changed
);
1538 /* DST = A | B. Return true if DST changes. */
1541 bitmap_ior (bitmap dst
, const_bitmap a
, const_bitmap b
)
1543 bitmap_element
*dst_elt
= dst
->first
;
1544 const bitmap_element
*a_elt
= a
->first
;
1545 const bitmap_element
*b_elt
= b
->first
;
1546 bitmap_element
*dst_prev
= NULL
;
1547 bitmap_element
**dst_prev_pnext
= &dst
->first
;
1548 bool changed
= false;
1550 gcc_assert (dst
!= a
&& dst
!= b
);
1552 while (a_elt
|| b_elt
)
1554 changed
= bitmap_elt_ior (dst
, dst_elt
, dst_prev
, a_elt
, b_elt
, changed
);
1556 if (a_elt
&& b_elt
&& a_elt
->indx
== b_elt
->indx
)
1558 a_elt
= a_elt
->next
;
1559 b_elt
= b_elt
->next
;
1563 if (a_elt
&& (!b_elt
|| a_elt
->indx
<= b_elt
->indx
))
1564 a_elt
= a_elt
->next
;
1565 else if (b_elt
&& (!a_elt
|| b_elt
->indx
<= a_elt
->indx
))
1566 b_elt
= b_elt
->next
;
1569 dst_prev
= *dst_prev_pnext
;
1570 dst_prev_pnext
= &dst_prev
->next
;
1571 dst_elt
= *dst_prev_pnext
;
1577 bitmap_elt_clear_from (dst
, dst_elt
);
1579 gcc_checking_assert (!dst
->current
== !dst
->first
);
1581 dst
->indx
= dst
->current
->indx
;
1585 /* A |= B. Return true if A changes. */
1588 bitmap_ior_into (bitmap a
, const_bitmap b
)
1590 bitmap_element
*a_elt
= a
->first
;
1591 const bitmap_element
*b_elt
= b
->first
;
1592 bitmap_element
*a_prev
= NULL
;
1593 bitmap_element
**a_prev_pnext
= &a
->first
;
1594 bool changed
= false;
1601 /* If A lags behind B, just advance it. */
1602 if (!a_elt
|| a_elt
->indx
== b_elt
->indx
)
1604 changed
= bitmap_elt_ior (a
, a_elt
, a_prev
, a_elt
, b_elt
, changed
);
1605 b_elt
= b_elt
->next
;
1607 else if (a_elt
->indx
> b_elt
->indx
)
1609 changed
= bitmap_elt_copy (a
, NULL
, a_prev
, b_elt
, changed
);
1610 b_elt
= b_elt
->next
;
1613 a_prev
= *a_prev_pnext
;
1614 a_prev_pnext
= &a_prev
->next
;
1615 a_elt
= *a_prev_pnext
;
1618 gcc_checking_assert (!a
->current
== !a
->first
);
1620 a
->indx
= a
->current
->indx
;
1627 bitmap_xor (bitmap dst
, const_bitmap a
, const_bitmap b
)
1629 bitmap_element
*dst_elt
= dst
->first
;
1630 const bitmap_element
*a_elt
= a
->first
;
1631 const bitmap_element
*b_elt
= b
->first
;
1632 bitmap_element
*dst_prev
= NULL
;
1634 gcc_assert (dst
!= a
&& dst
!= b
);
1641 while (a_elt
|| b_elt
)
1643 if (a_elt
&& b_elt
&& a_elt
->indx
== b_elt
->indx
)
1645 /* Matching elts, generate A ^ B. */
1647 BITMAP_WORD ior
= 0;
1650 dst_elt
= bitmap_elt_insert_after (dst
, dst_prev
, a_elt
->indx
);
1652 dst_elt
->indx
= a_elt
->indx
;
1653 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1655 BITMAP_WORD r
= a_elt
->bits
[ix
] ^ b_elt
->bits
[ix
];
1658 dst_elt
->bits
[ix
] = r
;
1660 a_elt
= a_elt
->next
;
1661 b_elt
= b_elt
->next
;
1665 dst_elt
= dst_elt
->next
;
1670 /* Copy a single element. */
1671 const bitmap_element
*src
;
1673 if (!b_elt
|| (a_elt
&& a_elt
->indx
< b_elt
->indx
))
1676 a_elt
= a_elt
->next
;
1681 b_elt
= b_elt
->next
;
1685 dst_elt
= bitmap_elt_insert_after (dst
, dst_prev
, src
->indx
);
1687 dst_elt
->indx
= src
->indx
;
1688 memcpy (dst_elt
->bits
, src
->bits
, sizeof (dst_elt
->bits
));
1690 dst_elt
= dst_elt
->next
;
1693 /* Ensure that dst->current is valid. */
1694 dst
->current
= dst
->first
;
1695 bitmap_elt_clear_from (dst
, dst_elt
);
1696 gcc_checking_assert (!dst
->current
== !dst
->first
);
1698 dst
->indx
= dst
->current
->indx
;
1704 bitmap_xor_into (bitmap a
, const_bitmap b
)
1706 bitmap_element
*a_elt
= a
->first
;
1707 const bitmap_element
*b_elt
= b
->first
;
1708 bitmap_element
*a_prev
= NULL
;
1718 if (!a_elt
|| b_elt
->indx
< a_elt
->indx
)
1721 bitmap_element
*dst
= bitmap_elt_insert_after (a
, a_prev
, b_elt
->indx
);
1722 memcpy (dst
->bits
, b_elt
->bits
, sizeof (dst
->bits
));
1724 b_elt
= b_elt
->next
;
1726 else if (a_elt
->indx
< b_elt
->indx
)
1729 a_elt
= a_elt
->next
;
1733 /* Matching elts, generate A ^= B. */
1735 BITMAP_WORD ior
= 0;
1736 bitmap_element
*next
= a_elt
->next
;
1738 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1740 BITMAP_WORD r
= a_elt
->bits
[ix
] ^ b_elt
->bits
[ix
];
1743 a_elt
->bits
[ix
] = r
;
1745 b_elt
= b_elt
->next
;
1749 bitmap_element_free (a
, a_elt
);
1753 gcc_checking_assert (!a
->current
== !a
->first
);
1755 a
->indx
= a
->current
->indx
;
1758 /* Return true if two bitmaps are identical.
1759 We do not bother with a check for pointer equality, as that never
1760 occurs in practice. */
1763 bitmap_equal_p (const_bitmap a
, const_bitmap b
)
1765 const bitmap_element
*a_elt
;
1766 const bitmap_element
*b_elt
;
1769 for (a_elt
= a
->first
, b_elt
= b
->first
;
1771 a_elt
= a_elt
->next
, b_elt
= b_elt
->next
)
1773 if (a_elt
->indx
!= b_elt
->indx
)
1775 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1776 if (a_elt
->bits
[ix
] != b_elt
->bits
[ix
])
1779 return !a_elt
&& !b_elt
;
1782 /* Return true if A AND B is not empty. */
1785 bitmap_intersect_p (const_bitmap a
, const_bitmap b
)
1787 const bitmap_element
*a_elt
;
1788 const bitmap_element
*b_elt
;
1791 for (a_elt
= a
->first
, b_elt
= b
->first
;
1794 if (a_elt
->indx
< b_elt
->indx
)
1795 a_elt
= a_elt
->next
;
1796 else if (b_elt
->indx
< a_elt
->indx
)
1797 b_elt
= b_elt
->next
;
1800 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1801 if (a_elt
->bits
[ix
] & b_elt
->bits
[ix
])
1803 a_elt
= a_elt
->next
;
1804 b_elt
= b_elt
->next
;
1810 /* Return true if A AND NOT B is not empty. */
1813 bitmap_intersect_compl_p (const_bitmap a
, const_bitmap b
)
1815 const bitmap_element
*a_elt
;
1816 const bitmap_element
*b_elt
;
1818 for (a_elt
= a
->first
, b_elt
= b
->first
;
1821 if (a_elt
->indx
< b_elt
->indx
)
1823 else if (b_elt
->indx
< a_elt
->indx
)
1824 b_elt
= b_elt
->next
;
1827 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1828 if (a_elt
->bits
[ix
] & ~b_elt
->bits
[ix
])
1830 a_elt
= a_elt
->next
;
1831 b_elt
= b_elt
->next
;
1834 return a_elt
!= NULL
;
1838 /* DST = A | (FROM1 & ~FROM2). Return true if DST changes. */
1841 bitmap_ior_and_compl (bitmap dst
, const_bitmap a
, const_bitmap b
, const_bitmap kill
)
1843 bool changed
= false;
1845 bitmap_element
*dst_elt
= dst
->first
;
1846 const bitmap_element
*a_elt
= a
->first
;
1847 const bitmap_element
*b_elt
= b
->first
;
1848 const bitmap_element
*kill_elt
= kill
->first
;
1849 bitmap_element
*dst_prev
= NULL
;
1850 bitmap_element
**dst_prev_pnext
= &dst
->first
;
1852 gcc_assert (dst
!= a
&& dst
!= b
&& dst
!= kill
);
1854 /* Special cases. We don't bother checking for bitmap_equal_p (b, kill). */
1855 if (b
== kill
|| bitmap_empty_p (b
))
1857 changed
= !bitmap_equal_p (dst
, a
);
1859 bitmap_copy (dst
, a
);
1862 if (bitmap_empty_p (kill
))
1863 return bitmap_ior (dst
, a
, b
);
1864 if (bitmap_empty_p (a
))
1865 return bitmap_and_compl (dst
, b
, kill
);
1867 while (a_elt
|| b_elt
)
1869 bool new_element
= false;
1872 while (kill_elt
&& kill_elt
->indx
< b_elt
->indx
)
1873 kill_elt
= kill_elt
->next
;
1875 if (b_elt
&& kill_elt
&& kill_elt
->indx
== b_elt
->indx
1876 && (!a_elt
|| a_elt
->indx
>= b_elt
->indx
))
1878 bitmap_element tmp_elt
;
1881 BITMAP_WORD ior
= 0;
1882 tmp_elt
.indx
= b_elt
->indx
;
1883 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1885 BITMAP_WORD r
= b_elt
->bits
[ix
] & ~kill_elt
->bits
[ix
];
1887 tmp_elt
.bits
[ix
] = r
;
1892 changed
= bitmap_elt_ior (dst
, dst_elt
, dst_prev
,
1893 a_elt
, &tmp_elt
, changed
);
1895 if (a_elt
&& a_elt
->indx
== b_elt
->indx
)
1896 a_elt
= a_elt
->next
;
1899 b_elt
= b_elt
->next
;
1900 kill_elt
= kill_elt
->next
;
1904 changed
= bitmap_elt_ior (dst
, dst_elt
, dst_prev
,
1905 a_elt
, b_elt
, changed
);
1908 if (a_elt
&& b_elt
&& a_elt
->indx
== b_elt
->indx
)
1910 a_elt
= a_elt
->next
;
1911 b_elt
= b_elt
->next
;
1915 if (a_elt
&& (!b_elt
|| a_elt
->indx
<= b_elt
->indx
))
1916 a_elt
= a_elt
->next
;
1917 else if (b_elt
&& (!a_elt
|| b_elt
->indx
<= a_elt
->indx
))
1918 b_elt
= b_elt
->next
;
1924 dst_prev
= *dst_prev_pnext
;
1925 dst_prev_pnext
= &dst_prev
->next
;
1926 dst_elt
= *dst_prev_pnext
;
1933 bitmap_elt_clear_from (dst
, dst_elt
);
1935 gcc_checking_assert (!dst
->current
== !dst
->first
);
1937 dst
->indx
= dst
->current
->indx
;
1942 /* A |= (FROM1 & ~FROM2). Return true if A changes. */
1945 bitmap_ior_and_compl_into (bitmap a
, const_bitmap from1
, const_bitmap from2
)
1950 bitmap_initialize (&tmp
, &bitmap_default_obstack
);
1951 bitmap_and_compl (&tmp
, from1
, from2
);
1952 changed
= bitmap_ior_into (a
, &tmp
);
1953 bitmap_clear (&tmp
);
1958 /* A |= (B & C). Return true if A changes. */
1961 bitmap_ior_and_into (bitmap a
, const_bitmap b
, const_bitmap c
)
1963 bitmap_element
*a_elt
= a
->first
;
1964 const bitmap_element
*b_elt
= b
->first
;
1965 const bitmap_element
*c_elt
= c
->first
;
1966 bitmap_element and_elt
;
1967 bitmap_element
*a_prev
= NULL
;
1968 bitmap_element
**a_prev_pnext
= &a
->first
;
1969 bool changed
= false;
1973 return bitmap_ior_into (a
, b
);
1974 if (bitmap_empty_p (b
) || bitmap_empty_p (c
))
1978 while (b_elt
&& c_elt
)
1980 BITMAP_WORD overall
;
1982 /* Find a common item of B and C. */
1983 while (b_elt
->indx
!= c_elt
->indx
)
1985 if (b_elt
->indx
< c_elt
->indx
)
1987 b_elt
= b_elt
->next
;
1993 c_elt
= c_elt
->next
;
2000 and_elt
.indx
= b_elt
->indx
;
2001 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
2003 and_elt
.bits
[ix
] = b_elt
->bits
[ix
] & c_elt
->bits
[ix
];
2004 overall
|= and_elt
.bits
[ix
];
2007 b_elt
= b_elt
->next
;
2008 c_elt
= c_elt
->next
;
2012 /* Now find a place to insert AND_ELT. */
2015 ix
= a_elt
? a_elt
->indx
: and_elt
.indx
;
2016 if (ix
== and_elt
.indx
)
2017 changed
= bitmap_elt_ior (a
, a_elt
, a_prev
, a_elt
, &and_elt
, changed
);
2018 else if (ix
> and_elt
.indx
)
2019 changed
= bitmap_elt_copy (a
, NULL
, a_prev
, &and_elt
, changed
);
2021 a_prev
= *a_prev_pnext
;
2022 a_prev_pnext
= &a_prev
->next
;
2023 a_elt
= *a_prev_pnext
;
2025 /* If A lagged behind B/C, we advanced it so loop once more. */
2027 while (ix
< and_elt
.indx
);
2031 gcc_checking_assert (!a
->current
== !a
->first
);
2033 a
->indx
= a
->current
->indx
;
2037 /* Debugging function to print out the contents of a bitmap. */
2040 debug_bitmap_file (FILE *file
, const_bitmap head
)
2042 const bitmap_element
*ptr
;
2044 fprintf (file
, "\nfirst = " HOST_PTR_PRINTF
2045 " current = " HOST_PTR_PRINTF
" indx = %u\n",
2046 (void *) head
->first
, (void *) head
->current
, head
->indx
);
2048 for (ptr
= head
->first
; ptr
; ptr
= ptr
->next
)
2050 unsigned int i
, j
, col
= 26;
2052 fprintf (file
, "\t" HOST_PTR_PRINTF
" next = " HOST_PTR_PRINTF
2053 " prev = " HOST_PTR_PRINTF
" indx = %u\n\t\tbits = {",
2054 (const void*) ptr
, (const void*) ptr
->next
,
2055 (const void*) ptr
->prev
, ptr
->indx
);
2057 for (i
= 0; i
< BITMAP_ELEMENT_WORDS
; i
++)
2058 for (j
= 0; j
< BITMAP_WORD_BITS
; j
++)
2059 if ((ptr
->bits
[i
] >> j
) & 1)
2063 fprintf (file
, "\n\t\t\t");
2067 fprintf (file
, " %u", (ptr
->indx
* BITMAP_ELEMENT_ALL_BITS
2068 + i
* BITMAP_WORD_BITS
+ j
));
2072 fprintf (file
, " }\n");
2076 /* Function to be called from the debugger to print the contents
2080 debug_bitmap (const_bitmap head
)
2082 debug_bitmap_file (stdout
, head
);
2085 /* Function to print out the contents of a bitmap. Unlike debug_bitmap_file,
2086 it does not print anything but the bits. */
2089 bitmap_print (FILE *file
, const_bitmap head
, const char *prefix
, const char *suffix
)
2091 const char *comma
= "";
2095 fputs (prefix
, file
);
2096 EXECUTE_IF_SET_IN_BITMAP (head
, 0, i
, bi
)
2098 fprintf (file
, "%s%d", comma
, i
);
2101 fputs (suffix
, file
);
2103 #ifdef GATHER_STATISTICS
2106 /* Used to accumulate statistics about bitmap sizes. */
2109 HOST_WIDEST_INT size
;
2113 /* Called via htab_traverse. Output bitmap descriptor pointed out by SLOT
2114 and update statistics. */
2116 print_statistics (void **slot
, void *b
)
2118 struct bitmap_descriptor
*d
= (struct bitmap_descriptor
*) *slot
;
2119 struct output_info
*i
= (struct output_info
*) b
;
2124 const char *s1
= d
->file
;
2126 while ((s2
= strstr (s1
, "gcc/")))
2128 sprintf (s
, "%s:%i (%s)", s1
, d
->line
, d
->function
);
2130 fprintf (stderr
, "%-41s %8d %15"HOST_WIDEST_INT_PRINT
"d %15"
2131 HOST_WIDEST_INT_PRINT
"d %15"HOST_WIDEST_INT_PRINT
"d %10d %10d\n",
2132 s
, d
->created
, d
->allocated
, d
->peak
, d
->current
, d
->nsearches
,
2134 i
->size
+= d
->allocated
;
2135 i
->count
+= d
->created
;
2140 /* Output per-bitmap memory usage statistics. */
2142 dump_bitmap_statistics (void)
2144 #ifdef GATHER_STATISTICS
2145 struct output_info info
;
2147 if (!bitmap_desc_hash
)
2150 fprintf (stderr
, "\nBitmap Overall "
2151 " Allocated Peak Leak searched "
2153 fprintf (stderr
, "---------------------------------------------------------------------------------\n");
2156 htab_traverse (bitmap_desc_hash
, print_statistics
, &info
);
2157 fprintf (stderr
, "---------------------------------------------------------------------------------\n");
2158 fprintf (stderr
, "%-40s %9d %15"HOST_WIDEST_INT_PRINT
"d\n",
2159 "Total", info
.count
, info
.size
);
2160 fprintf (stderr
, "---------------------------------------------------------------------------------\n");
2164 /* Compute hash of bitmap (for purposes of hashing). */
2166 bitmap_hash (const_bitmap head
)
2168 const bitmap_element
*ptr
;
2169 BITMAP_WORD hash
= 0;
2172 for (ptr
= head
->first
; ptr
; ptr
= ptr
->next
)
2175 for (ix
= 0; ix
!= BITMAP_ELEMENT_WORDS
; ix
++)
2176 hash
^= ptr
->bits
[ix
];
2178 return (hashval_t
)hash
;
2181 #include "gt-bitmap.h"