1 /* Functions to support general ended bitmaps.
2 Copyright (C) 1997-2015 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
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"
25 /* Memory allocation statistics purpose instance. */
26 mem_alloc_description
<bitmap_usage
> bitmap_mem_desc
;
28 /* Register new bitmap. */
30 bitmap_register (bitmap b MEM_STAT_DECL
)
32 bitmap_mem_desc
.register_descriptor (b
, BITMAP_ORIGIN
, false
36 /* Account the overhead. */
38 register_overhead (bitmap b
, int amount
)
40 if (bitmap_mem_desc
.contains_descriptor_for_instance (b
))
41 bitmap_mem_desc
.register_instance_overhead (amount
, b
);
45 bitmap_element bitmap_zero_bits
; /* An element of all zero bits. */
46 bitmap_obstack bitmap_default_obstack
; /* The default bitmap obstack. */
47 static int bitmap_default_obstack_depth
;
48 static GTY((deletable
)) bitmap_element
*bitmap_ggc_free
; /* Freelist of
51 static void bitmap_elem_to_freelist (bitmap
, bitmap_element
*);
52 static void bitmap_element_free (bitmap
, bitmap_element
*);
53 static bitmap_element
*bitmap_element_allocate (bitmap
);
54 static int bitmap_element_zerop (const bitmap_element
*);
55 static void bitmap_element_link (bitmap
, bitmap_element
*);
56 static bitmap_element
*bitmap_elt_insert_after (bitmap
, bitmap_element
*, unsigned int);
57 static void bitmap_elt_clear_from (bitmap
, bitmap_element
*);
58 static bitmap_element
*bitmap_find_bit (bitmap
, unsigned int);
61 /* Add ELEM to the appropriate freelist. */
63 bitmap_elem_to_freelist (bitmap head
, bitmap_element
*elt
)
65 bitmap_obstack
*bit_obstack
= head
->obstack
;
70 elt
->prev
= bit_obstack
->elements
;
71 bit_obstack
->elements
= elt
;
75 elt
->prev
= bitmap_ggc_free
;
76 bitmap_ggc_free
= elt
;
80 /* Free a bitmap element. Since these are allocated off the
81 bitmap_obstack, "free" actually means "put onto the freelist". */
84 bitmap_element_free (bitmap head
, bitmap_element
*elt
)
86 bitmap_element
*next
= elt
->next
;
87 bitmap_element
*prev
= elt
->prev
;
95 if (head
->first
== elt
)
98 /* Since the first thing we try is to insert before current,
99 make current the next entry in preference to the previous. */
100 if (head
->current
== elt
)
102 head
->current
= next
!= 0 ? next
: prev
;
104 head
->indx
= head
->current
->indx
;
109 if (GATHER_STATISTICS
)
110 register_overhead (head
, -((int)sizeof (bitmap_element
)));
112 bitmap_elem_to_freelist (head
, elt
);
115 /* Allocate a bitmap element. The bits are cleared, but nothing else is. */
117 static inline bitmap_element
*
118 bitmap_element_allocate (bitmap head
)
120 bitmap_element
*element
;
121 bitmap_obstack
*bit_obstack
= head
->obstack
;
125 element
= bit_obstack
->elements
;
128 /* Use up the inner list first before looking at the next
129 element of the outer list. */
132 bit_obstack
->elements
= element
->next
;
133 bit_obstack
->elements
->prev
= element
->prev
;
136 /* Inner list was just a singleton. */
137 bit_obstack
->elements
= element
->prev
;
139 element
= XOBNEW (&bit_obstack
->obstack
, bitmap_element
);
143 element
= bitmap_ggc_free
;
145 /* Use up the inner list first before looking at the next
146 element of the outer list. */
149 bitmap_ggc_free
= element
->next
;
150 bitmap_ggc_free
->prev
= element
->prev
;
153 /* Inner list was just a singleton. */
154 bitmap_ggc_free
= element
->prev
;
156 element
= ggc_alloc
<bitmap_element
> ();
159 if (GATHER_STATISTICS
)
160 register_overhead (head
, sizeof (bitmap_element
));
162 memset (element
->bits
, 0, sizeof (element
->bits
));
167 /* Remove ELT and all following elements from bitmap HEAD. */
170 bitmap_elt_clear_from (bitmap head
, bitmap_element
*elt
)
172 bitmap_element
*prev
;
173 bitmap_obstack
*bit_obstack
= head
->obstack
;
177 if (GATHER_STATISTICS
)
180 for (prev
= elt
; prev
; prev
= prev
->next
)
182 register_overhead (head
, -sizeof (bitmap_element
) * n
);
189 if (head
->current
->indx
> prev
->indx
)
191 head
->current
= prev
;
192 head
->indx
= prev
->indx
;
198 head
->current
= NULL
;
202 /* Put the entire list onto the free list in one operation. */
205 elt
->prev
= bit_obstack
->elements
;
206 bit_obstack
->elements
= elt
;
210 elt
->prev
= bitmap_ggc_free
;
211 bitmap_ggc_free
= elt
;
215 /* Clear a bitmap by freeing the linked list. */
218 bitmap_clear (bitmap head
)
221 bitmap_elt_clear_from (head
, head
->first
);
224 /* Initialize a bitmap obstack. If BIT_OBSTACK is NULL, initialize
225 the default bitmap obstack. */
228 bitmap_obstack_initialize (bitmap_obstack
*bit_obstack
)
232 if (bitmap_default_obstack_depth
++)
234 bit_obstack
= &bitmap_default_obstack
;
237 #if !defined(__GNUC__) || (__GNUC__ < 2)
238 #define __alignof__(type) 0
241 bit_obstack
->elements
= NULL
;
242 bit_obstack
->heads
= NULL
;
243 obstack_specify_allocation (&bit_obstack
->obstack
, OBSTACK_CHUNK_SIZE
,
244 __alignof__ (bitmap_element
),
249 /* Release the memory from a bitmap obstack. If BIT_OBSTACK is NULL,
250 release the default bitmap obstack. */
253 bitmap_obstack_release (bitmap_obstack
*bit_obstack
)
257 if (--bitmap_default_obstack_depth
)
259 gcc_assert (bitmap_default_obstack_depth
> 0);
262 bit_obstack
= &bitmap_default_obstack
;
265 bit_obstack
->elements
= NULL
;
266 bit_obstack
->heads
= NULL
;
267 obstack_free (&bit_obstack
->obstack
, NULL
);
270 /* Create a new bitmap on an obstack. If BIT_OBSTACK is NULL, create
271 it on the default bitmap obstack. */
274 bitmap_obstack_alloc_stat (bitmap_obstack
*bit_obstack MEM_STAT_DECL
)
279 bit_obstack
= &bitmap_default_obstack
;
280 map
= bit_obstack
->heads
;
282 bit_obstack
->heads
= (struct bitmap_head
*) map
->first
;
284 map
= XOBNEW (&bit_obstack
->obstack
, bitmap_head
);
285 bitmap_initialize_stat (map
, bit_obstack PASS_MEM_STAT
);
287 if (GATHER_STATISTICS
)
288 register_overhead (map
, sizeof (bitmap_head
));
293 /* Create a new GCd bitmap. */
296 bitmap_gc_alloc_stat (ALONE_MEM_STAT_DECL
)
300 map
= ggc_alloc
<bitmap_head
> ();
301 bitmap_initialize_stat (map
, NULL PASS_MEM_STAT
);
303 if (GATHER_STATISTICS
)
304 register_overhead (map
, sizeof (bitmap_head
));
309 /* Release an obstack allocated bitmap. */
312 bitmap_obstack_free (bitmap map
)
317 map
->first
= (bitmap_element
*) map
->obstack
->heads
;
319 if (GATHER_STATISTICS
)
320 register_overhead (map
, -((int)sizeof (bitmap_head
)));
322 map
->obstack
->heads
= map
;
327 /* Return nonzero if all bits in an element are zero. */
330 bitmap_element_zerop (const bitmap_element
*element
)
332 #if BITMAP_ELEMENT_WORDS == 2
333 return (element
->bits
[0] | element
->bits
[1]) == 0;
337 for (i
= 0; i
< BITMAP_ELEMENT_WORDS
; i
++)
338 if (element
->bits
[i
] != 0)
345 /* Link the bitmap element into the current bitmap linked list. */
348 bitmap_element_link (bitmap head
, bitmap_element
*element
)
350 unsigned int indx
= element
->indx
;
353 /* If this is the first and only element, set it in. */
354 if (head
->first
== 0)
356 element
->next
= element
->prev
= 0;
357 head
->first
= element
;
360 /* If this index is less than that of the current element, it goes someplace
361 before the current element. */
362 else if (indx
< head
->indx
)
364 for (ptr
= head
->current
;
365 ptr
->prev
!= 0 && ptr
->prev
->indx
> indx
;
370 ptr
->prev
->next
= element
;
372 head
->first
= element
;
374 element
->prev
= ptr
->prev
;
379 /* Otherwise, it must go someplace after the current element. */
382 for (ptr
= head
->current
;
383 ptr
->next
!= 0 && ptr
->next
->indx
< indx
;
388 ptr
->next
->prev
= element
;
390 element
->next
= ptr
->next
;
395 /* Set up so this is the first element searched. */
396 head
->current
= element
;
400 /* Insert a new uninitialized element into bitmap HEAD after element
401 ELT. If ELT is NULL, insert the element at the start. Return the
404 static bitmap_element
*
405 bitmap_elt_insert_after (bitmap head
, bitmap_element
*elt
, unsigned int indx
)
407 bitmap_element
*node
= bitmap_element_allocate (head
);
414 head
->current
= node
;
417 node
->next
= head
->first
;
419 node
->next
->prev
= node
;
425 gcc_checking_assert (head
->current
);
426 node
->next
= elt
->next
;
428 node
->next
->prev
= node
;
435 /* Copy a bitmap to another bitmap. */
438 bitmap_copy (bitmap to
, const_bitmap from
)
440 const bitmap_element
*from_ptr
;
441 bitmap_element
*to_ptr
= 0;
445 /* Copy elements in forward direction one at a time. */
446 for (from_ptr
= from
->first
; from_ptr
; from_ptr
= from_ptr
->next
)
448 bitmap_element
*to_elt
= bitmap_element_allocate (to
);
450 to_elt
->indx
= from_ptr
->indx
;
451 memcpy (to_elt
->bits
, from_ptr
->bits
, sizeof (to_elt
->bits
));
453 /* Here we have a special case of bitmap_element_link, for the case
454 where we know the links are being entered in sequence. */
457 to
->first
= to
->current
= to_elt
;
458 to
->indx
= from_ptr
->indx
;
459 to_elt
->next
= to_elt
->prev
= 0;
463 to_elt
->prev
= to_ptr
;
465 to_ptr
->next
= to_elt
;
472 /* Find a bitmap element that would hold a bitmap's bit.
473 Update the `current' field even if we can't find an element that
474 would hold the bitmap's bit to make eventual allocation
477 static inline bitmap_element
*
478 bitmap_find_bit (bitmap head
, unsigned int bit
)
480 bitmap_element
*element
;
481 unsigned int indx
= bit
/ BITMAP_ELEMENT_ALL_BITS
;
483 if (head
->current
== NULL
484 || head
->indx
== indx
)
485 return head
->current
;
486 if (head
->current
== head
->first
487 && head
->first
->next
== NULL
)
490 /* Usage can be NULL due to allocated bitmaps for which we do not
491 call initialize function. */
492 bitmap_usage
*usage
= bitmap_mem_desc
.get_descriptor_for_instance (head
);
494 /* This bitmap has more than one element, and we're going to look
495 through the elements list. Count that as a search. */
496 if (GATHER_STATISTICS
&& usage
)
497 usage
->m_nsearches
++;
499 if (head
->indx
< indx
)
500 /* INDX is beyond head->indx. Search from head->current
502 for (element
= head
->current
;
503 element
->next
!= 0 && element
->indx
< indx
;
504 element
= element
->next
)
506 if (GATHER_STATISTICS
&& usage
)
507 usage
->m_search_iter
++;
510 else if (head
->indx
/ 2 < indx
)
511 /* INDX is less than head->indx and closer to head->indx than to
512 0. Search from head->current backward. */
513 for (element
= head
->current
;
514 element
->prev
!= 0 && element
->indx
> indx
;
515 element
= element
->prev
)
517 if (GATHER_STATISTICS
&& usage
)
518 usage
->m_search_iter
++;
522 /* INDX is less than head->indx and closer to 0 than to
523 head->indx. Search from head->first forward. */
524 for (element
= head
->first
;
525 element
->next
!= 0 && element
->indx
< indx
;
526 element
= element
->next
)
527 if (GATHER_STATISTICS
&& usage
)
529 usage
->m_search_iter
++;
532 /* `element' is the nearest to the one we want. If it's not the one we
533 want, the one we want doesn't exist. */
534 head
->current
= element
;
535 head
->indx
= element
->indx
;
536 if (element
!= 0 && element
->indx
!= indx
)
542 /* Clear a single bit in a bitmap. Return true if the bit changed. */
545 bitmap_clear_bit (bitmap head
, int bit
)
547 bitmap_element
*const ptr
= bitmap_find_bit (head
, bit
);
551 unsigned bit_num
= bit
% BITMAP_WORD_BITS
;
552 unsigned word_num
= bit
/ BITMAP_WORD_BITS
% BITMAP_ELEMENT_WORDS
;
553 BITMAP_WORD bit_val
= ((BITMAP_WORD
) 1) << bit_num
;
554 bool res
= (ptr
->bits
[word_num
] & bit_val
) != 0;
557 ptr
->bits
[word_num
] &= ~bit_val
;
558 /* If we cleared the entire word, free up the element. */
559 if (!ptr
->bits
[word_num
]
560 && bitmap_element_zerop (ptr
))
561 bitmap_element_free (head
, ptr
);
570 /* Set a single bit in a bitmap. Return true if the bit changed. */
573 bitmap_set_bit (bitmap head
, int bit
)
575 bitmap_element
*ptr
= bitmap_find_bit (head
, bit
);
576 unsigned word_num
= bit
/ BITMAP_WORD_BITS
% BITMAP_ELEMENT_WORDS
;
577 unsigned bit_num
= bit
% BITMAP_WORD_BITS
;
578 BITMAP_WORD bit_val
= ((BITMAP_WORD
) 1) << bit_num
;
582 ptr
= bitmap_element_allocate (head
);
583 ptr
->indx
= bit
/ BITMAP_ELEMENT_ALL_BITS
;
584 ptr
->bits
[word_num
] = bit_val
;
585 bitmap_element_link (head
, ptr
);
590 bool res
= (ptr
->bits
[word_num
] & bit_val
) == 0;
592 ptr
->bits
[word_num
] |= bit_val
;
597 /* Return whether a bit is set within a bitmap. */
600 bitmap_bit_p (bitmap head
, int bit
)
606 ptr
= bitmap_find_bit (head
, bit
);
610 bit_num
= bit
% BITMAP_WORD_BITS
;
611 word_num
= bit
/ BITMAP_WORD_BITS
% BITMAP_ELEMENT_WORDS
;
613 return (ptr
->bits
[word_num
] >> bit_num
) & 1;
616 #if GCC_VERSION < 3400
617 /* Table of number of set bits in a character, indexed by value of char. */
618 static const unsigned char popcount_table
[] =
620 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,
621 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,
622 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
623 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,
624 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,
625 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,
626 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
627 3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
631 bitmap_popcount (BITMAP_WORD a
)
633 unsigned long ret
= 0;
636 /* Just do this the table way for now */
637 for (i
= 0; i
< BITMAP_WORD_BITS
; i
+= 8)
638 ret
+= popcount_table
[(a
>> i
) & 0xff];
642 /* Count the number of bits set in the bitmap, and return it. */
645 bitmap_count_bits (const_bitmap a
)
647 unsigned long count
= 0;
648 const bitmap_element
*elt
;
651 for (elt
= a
->first
; elt
; elt
= elt
->next
)
653 for (ix
= 0; ix
!= BITMAP_ELEMENT_WORDS
; ix
++)
655 #if GCC_VERSION >= 3400
656 /* Note that popcountl matches BITMAP_WORD in type, so the actual size
657 of BITMAP_WORD is not material. */
658 count
+= __builtin_popcountl (elt
->bits
[ix
]);
660 count
+= bitmap_popcount (elt
->bits
[ix
]);
667 /* Return true if the bitmap has a single bit set. Otherwise return
671 bitmap_single_bit_set_p (const_bitmap a
)
673 unsigned long count
= 0;
674 const bitmap_element
*elt
;
677 if (bitmap_empty_p (a
))
681 /* As there are no completely empty bitmap elements, a second one
682 means we have more than one bit set. */
683 if (elt
->next
!= NULL
)
686 for (ix
= 0; ix
!= BITMAP_ELEMENT_WORDS
; ix
++)
688 #if GCC_VERSION >= 3400
689 /* Note that popcountl matches BITMAP_WORD in type, so the actual size
690 of BITMAP_WORD is not material. */
691 count
+= __builtin_popcountl (elt
->bits
[ix
]);
693 count
+= bitmap_popcount (elt
->bits
[ix
]);
703 /* Return the bit number of the first set bit in the bitmap. The
704 bitmap must be non-empty. */
707 bitmap_first_set_bit (const_bitmap a
)
709 const bitmap_element
*elt
= a
->first
;
714 gcc_checking_assert (elt
);
715 bit_no
= elt
->indx
* BITMAP_ELEMENT_ALL_BITS
;
716 for (ix
= 0; ix
!= BITMAP_ELEMENT_WORDS
; ix
++)
718 word
= elt
->bits
[ix
];
724 bit_no
+= ix
* BITMAP_WORD_BITS
;
726 #if GCC_VERSION >= 3004
727 gcc_assert (sizeof (long) == sizeof (word
));
728 bit_no
+= __builtin_ctzl (word
);
730 /* Binary search for the first set bit. */
731 #if BITMAP_WORD_BITS > 64
732 #error "Fill out the table."
734 #if BITMAP_WORD_BITS > 32
735 if (!(word
& 0xffffffff))
736 word
>>= 32, bit_no
+= 32;
738 if (!(word
& 0xffff))
739 word
>>= 16, bit_no
+= 16;
741 word
>>= 8, bit_no
+= 8;
743 word
>>= 4, bit_no
+= 4;
745 word
>>= 2, bit_no
+= 2;
747 word
>>= 1, bit_no
+= 1;
749 gcc_checking_assert (word
& 1);
754 /* Return the bit number of the first set bit in the bitmap. The
755 bitmap must be non-empty. */
758 bitmap_last_set_bit (const_bitmap a
)
760 const bitmap_element
*elt
= a
->current
? a
->current
: a
->first
;
765 gcc_checking_assert (elt
);
768 bit_no
= elt
->indx
* BITMAP_ELEMENT_ALL_BITS
;
769 for (ix
= BITMAP_ELEMENT_WORDS
- 1; ix
>= 0; ix
--)
771 word
= elt
->bits
[ix
];
777 bit_no
+= ix
* BITMAP_WORD_BITS
;
778 #if GCC_VERSION >= 3004
779 gcc_assert (sizeof (long) == sizeof (word
));
780 bit_no
+= BITMAP_WORD_BITS
- __builtin_clzl (word
) - 1;
782 /* Hopefully this is a twos-complement host... */
783 BITMAP_WORD x
= word
;
789 #if BITMAP_WORD_BITS > 32
792 bit_no
+= bitmap_popcount (x
) - 1;
802 bitmap_and (bitmap dst
, const_bitmap a
, const_bitmap b
)
804 bitmap_element
*dst_elt
= dst
->first
;
805 const bitmap_element
*a_elt
= a
->first
;
806 const bitmap_element
*b_elt
= b
->first
;
807 bitmap_element
*dst_prev
= NULL
;
809 gcc_assert (dst
!= a
&& dst
!= b
);
813 bitmap_copy (dst
, a
);
817 while (a_elt
&& b_elt
)
819 if (a_elt
->indx
< b_elt
->indx
)
821 else if (b_elt
->indx
< a_elt
->indx
)
825 /* Matching elts, generate A & B. */
830 dst_elt
= bitmap_elt_insert_after (dst
, dst_prev
, a_elt
->indx
);
832 dst_elt
->indx
= a_elt
->indx
;
833 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
835 BITMAP_WORD r
= a_elt
->bits
[ix
] & b_elt
->bits
[ix
];
837 dst_elt
->bits
[ix
] = r
;
843 dst_elt
= dst_elt
->next
;
849 /* Ensure that dst->current is valid. */
850 dst
->current
= dst
->first
;
851 bitmap_elt_clear_from (dst
, dst_elt
);
852 gcc_checking_assert (!dst
->current
== !dst
->first
);
854 dst
->indx
= dst
->current
->indx
;
857 /* A &= B. Return true if A changed. */
860 bitmap_and_into (bitmap a
, const_bitmap b
)
862 bitmap_element
*a_elt
= a
->first
;
863 const bitmap_element
*b_elt
= b
->first
;
864 bitmap_element
*next
;
865 bool changed
= false;
870 while (a_elt
&& b_elt
)
872 if (a_elt
->indx
< b_elt
->indx
)
875 bitmap_element_free (a
, a_elt
);
879 else if (b_elt
->indx
< a_elt
->indx
)
883 /* Matching elts, generate A &= B. */
887 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
889 BITMAP_WORD r
= a_elt
->bits
[ix
] & b_elt
->bits
[ix
];
890 if (a_elt
->bits
[ix
] != r
)
897 bitmap_element_free (a
, a_elt
);
906 bitmap_elt_clear_from (a
, a_elt
);
909 gcc_checking_assert (!a
->current
== !a
->first
910 && (!a
->current
|| a
->indx
== a
->current
->indx
));
916 /* Insert an element equal to SRC_ELT after DST_PREV, overwriting DST_ELT
917 if non-NULL. CHANGED is true if the destination bitmap had already been
918 changed; the new value of CHANGED is returned. */
921 bitmap_elt_copy (bitmap dst
, bitmap_element
*dst_elt
, bitmap_element
*dst_prev
,
922 const bitmap_element
*src_elt
, bool changed
)
924 if (!changed
&& dst_elt
&& dst_elt
->indx
== src_elt
->indx
)
928 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
929 if (src_elt
->bits
[ix
] != dst_elt
->bits
[ix
])
931 dst_elt
->bits
[ix
] = src_elt
->bits
[ix
];
939 dst_elt
= bitmap_elt_insert_after (dst
, dst_prev
, src_elt
->indx
);
941 dst_elt
->indx
= src_elt
->indx
;
942 memcpy (dst_elt
->bits
, src_elt
->bits
, sizeof (dst_elt
->bits
));
952 bitmap_and_compl (bitmap dst
, const_bitmap a
, const_bitmap b
)
954 bitmap_element
*dst_elt
= dst
->first
;
955 const bitmap_element
*a_elt
= a
->first
;
956 const bitmap_element
*b_elt
= b
->first
;
957 bitmap_element
*dst_prev
= NULL
;
958 bitmap_element
**dst_prev_pnext
= &dst
->first
;
959 bool changed
= false;
961 gcc_assert (dst
!= a
&& dst
!= b
);
965 changed
= !bitmap_empty_p (dst
);
972 while (b_elt
&& b_elt
->indx
< a_elt
->indx
)
975 if (!b_elt
|| b_elt
->indx
> a_elt
->indx
)
977 changed
= bitmap_elt_copy (dst
, dst_elt
, dst_prev
, a_elt
, changed
);
978 dst_prev
= *dst_prev_pnext
;
979 dst_prev_pnext
= &dst_prev
->next
;
980 dst_elt
= *dst_prev_pnext
;
986 /* Matching elts, generate A & ~B. */
990 if (!changed
&& dst_elt
&& dst_elt
->indx
== a_elt
->indx
)
992 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
994 BITMAP_WORD r
= a_elt
->bits
[ix
] & ~b_elt
->bits
[ix
];
996 if (dst_elt
->bits
[ix
] != r
)
999 dst_elt
->bits
[ix
] = r
;
1007 if (!dst_elt
|| dst_elt
->indx
> a_elt
->indx
)
1009 dst_elt
= bitmap_elt_insert_after (dst
, dst_prev
, a_elt
->indx
);
1014 dst_elt
->indx
= a_elt
->indx
;
1015 new_element
= false;
1018 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1020 BITMAP_WORD r
= a_elt
->bits
[ix
] & ~b_elt
->bits
[ix
];
1022 dst_elt
->bits
[ix
] = r
;
1030 changed
|= !new_element
;
1031 bitmap_element_free (dst
, dst_elt
);
1032 dst_elt
= *dst_prev_pnext
;
1038 dst_prev
= *dst_prev_pnext
;
1039 dst_prev_pnext
= &dst_prev
->next
;
1040 dst_elt
= *dst_prev_pnext
;
1042 a_elt
= a_elt
->next
;
1043 b_elt
= b_elt
->next
;
1047 /* Ensure that dst->current is valid. */
1048 dst
->current
= dst
->first
;
1053 bitmap_elt_clear_from (dst
, dst_elt
);
1055 gcc_checking_assert (!dst
->current
== !dst
->first
);
1057 dst
->indx
= dst
->current
->indx
;
1062 /* A &= ~B. Returns true if A changes */
1065 bitmap_and_compl_into (bitmap a
, const_bitmap b
)
1067 bitmap_element
*a_elt
= a
->first
;
1068 const bitmap_element
*b_elt
= b
->first
;
1069 bitmap_element
*next
;
1070 BITMAP_WORD changed
= 0;
1074 if (bitmap_empty_p (a
))
1083 while (a_elt
&& b_elt
)
1085 if (a_elt
->indx
< b_elt
->indx
)
1086 a_elt
= a_elt
->next
;
1087 else if (b_elt
->indx
< a_elt
->indx
)
1088 b_elt
= b_elt
->next
;
1091 /* Matching elts, generate A &= ~B. */
1093 BITMAP_WORD ior
= 0;
1095 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1097 BITMAP_WORD cleared
= a_elt
->bits
[ix
] & b_elt
->bits
[ix
];
1098 BITMAP_WORD r
= a_elt
->bits
[ix
] ^ cleared
;
1100 a_elt
->bits
[ix
] = r
;
1106 bitmap_element_free (a
, a_elt
);
1108 b_elt
= b_elt
->next
;
1111 gcc_checking_assert (!a
->current
== !a
->first
1112 && (!a
->current
|| a
->indx
== a
->current
->indx
));
1113 return changed
!= 0;
1116 /* Set COUNT bits from START in HEAD. */
1118 bitmap_set_range (bitmap head
, unsigned int start
, unsigned int count
)
1120 unsigned int first_index
, end_bit_plus1
, last_index
;
1121 bitmap_element
*elt
, *elt_prev
;
1129 bitmap_set_bit (head
, start
);
1133 first_index
= start
/ BITMAP_ELEMENT_ALL_BITS
;
1134 end_bit_plus1
= start
+ count
;
1135 last_index
= (end_bit_plus1
- 1) / BITMAP_ELEMENT_ALL_BITS
;
1136 elt
= bitmap_find_bit (head
, start
);
1138 /* If bitmap_find_bit returns zero, the current is the closest block
1139 to the result. Otherwise, just use bitmap_element_allocate to
1140 ensure ELT is set; in the loop below, ELT == NULL means "insert
1141 at the end of the bitmap". */
1144 elt
= bitmap_element_allocate (head
);
1145 elt
->indx
= first_index
;
1146 bitmap_element_link (head
, elt
);
1149 gcc_checking_assert (elt
->indx
== first_index
);
1150 elt_prev
= elt
->prev
;
1151 for (i
= first_index
; i
<= last_index
; i
++)
1153 unsigned elt_start_bit
= i
* BITMAP_ELEMENT_ALL_BITS
;
1154 unsigned elt_end_bit_plus1
= elt_start_bit
+ BITMAP_ELEMENT_ALL_BITS
;
1156 unsigned int first_word_to_mod
;
1157 BITMAP_WORD first_mask
;
1158 unsigned int last_word_to_mod
;
1159 BITMAP_WORD last_mask
;
1162 if (!elt
|| elt
->indx
!= i
)
1163 elt
= bitmap_elt_insert_after (head
, elt_prev
, i
);
1165 if (elt_start_bit
<= start
)
1167 /* The first bit to turn on is somewhere inside this
1169 first_word_to_mod
= (start
- elt_start_bit
) / BITMAP_WORD_BITS
;
1171 /* This mask should have 1s in all bits >= start position. */
1173 (((BITMAP_WORD
) 1) << ((start
% BITMAP_WORD_BITS
))) - 1;
1174 first_mask
= ~first_mask
;
1178 /* The first bit to turn on is below this start of this elt. */
1179 first_word_to_mod
= 0;
1180 first_mask
= ~(BITMAP_WORD
) 0;
1183 if (elt_end_bit_plus1
<= end_bit_plus1
)
1185 /* The last bit to turn on is beyond this elt. */
1186 last_word_to_mod
= BITMAP_ELEMENT_WORDS
- 1;
1187 last_mask
= ~(BITMAP_WORD
) 0;
1191 /* The last bit to turn on is inside to this elt. */
1193 (end_bit_plus1
- elt_start_bit
) / BITMAP_WORD_BITS
;
1195 /* The last mask should have 1s below the end bit. */
1197 (((BITMAP_WORD
) 1) << ((end_bit_plus1
% BITMAP_WORD_BITS
))) - 1;
1200 if (first_word_to_mod
== last_word_to_mod
)
1202 BITMAP_WORD mask
= first_mask
& last_mask
;
1203 elt
->bits
[first_word_to_mod
] |= mask
;
1207 elt
->bits
[first_word_to_mod
] |= first_mask
;
1208 if (BITMAP_ELEMENT_WORDS
> 2)
1209 for (ix
= first_word_to_mod
+ 1; ix
< last_word_to_mod
; ix
++)
1210 elt
->bits
[ix
] = ~(BITMAP_WORD
) 0;
1211 elt
->bits
[last_word_to_mod
] |= last_mask
;
1218 head
->current
= elt
? elt
: elt_prev
;
1219 head
->indx
= head
->current
->indx
;
1222 /* Clear COUNT bits from START in HEAD. */
1224 bitmap_clear_range (bitmap head
, unsigned int start
, unsigned int count
)
1226 unsigned int first_index
, end_bit_plus1
, last_index
;
1227 bitmap_element
*elt
;
1234 bitmap_clear_bit (head
, start
);
1238 first_index
= start
/ BITMAP_ELEMENT_ALL_BITS
;
1239 end_bit_plus1
= start
+ count
;
1240 last_index
= (end_bit_plus1
- 1) / BITMAP_ELEMENT_ALL_BITS
;
1241 elt
= bitmap_find_bit (head
, start
);
1243 /* If bitmap_find_bit returns zero, the current is the closest block
1244 to the result. If the current is less than first index, find the
1245 next one. Otherwise, just set elt to be current. */
1250 if (head
->indx
< first_index
)
1252 elt
= head
->current
->next
;
1257 elt
= head
->current
;
1263 while (elt
&& (elt
->indx
<= last_index
))
1265 bitmap_element
* next_elt
= elt
->next
;
1266 unsigned elt_start_bit
= (elt
->indx
) * BITMAP_ELEMENT_ALL_BITS
;
1267 unsigned elt_end_bit_plus1
= elt_start_bit
+ BITMAP_ELEMENT_ALL_BITS
;
1270 if (elt_start_bit
>= start
&& elt_end_bit_plus1
<= end_bit_plus1
)
1271 /* Get rid of the entire elt and go to the next one. */
1272 bitmap_element_free (head
, elt
);
1275 /* Going to have to knock out some bits in this elt. */
1276 unsigned int first_word_to_mod
;
1277 BITMAP_WORD first_mask
;
1278 unsigned int last_word_to_mod
;
1279 BITMAP_WORD last_mask
;
1283 if (elt_start_bit
<= start
)
1285 /* The first bit to turn off is somewhere inside this
1287 first_word_to_mod
= (start
- elt_start_bit
) / BITMAP_WORD_BITS
;
1289 /* This mask should have 1s in all bits >= start position. */
1291 (((BITMAP_WORD
) 1) << ((start
% BITMAP_WORD_BITS
))) - 1;
1292 first_mask
= ~first_mask
;
1296 /* The first bit to turn off is below this start of this elt. */
1297 first_word_to_mod
= 0;
1299 first_mask
= ~first_mask
;
1302 if (elt_end_bit_plus1
<= end_bit_plus1
)
1304 /* The last bit to turn off is beyond this elt. */
1305 last_word_to_mod
= BITMAP_ELEMENT_WORDS
- 1;
1307 last_mask
= ~last_mask
;
1311 /* The last bit to turn off is inside to this elt. */
1313 (end_bit_plus1
- elt_start_bit
) / BITMAP_WORD_BITS
;
1315 /* The last mask should have 1s below the end bit. */
1317 (((BITMAP_WORD
) 1) << (((end_bit_plus1
) % BITMAP_WORD_BITS
))) - 1;
1321 if (first_word_to_mod
== last_word_to_mod
)
1323 BITMAP_WORD mask
= first_mask
& last_mask
;
1324 elt
->bits
[first_word_to_mod
] &= ~mask
;
1328 elt
->bits
[first_word_to_mod
] &= ~first_mask
;
1329 if (BITMAP_ELEMENT_WORDS
> 2)
1330 for (i
= first_word_to_mod
+ 1; i
< last_word_to_mod
; i
++)
1332 elt
->bits
[last_word_to_mod
] &= ~last_mask
;
1334 for (i
= 0; i
< BITMAP_ELEMENT_WORDS
; i
++)
1340 /* Check to see if there are any bits left. */
1342 bitmap_element_free (head
, elt
);
1349 head
->current
= elt
;
1350 head
->indx
= head
->current
->indx
;
1357 bitmap_compl_and_into (bitmap a
, const_bitmap b
)
1359 bitmap_element
*a_elt
= a
->first
;
1360 const bitmap_element
*b_elt
= b
->first
;
1361 bitmap_element
*a_prev
= NULL
;
1362 bitmap_element
*next
;
1364 gcc_assert (a
!= b
);
1366 if (bitmap_empty_p (a
))
1371 if (bitmap_empty_p (b
))
1377 while (a_elt
|| b_elt
)
1379 if (!b_elt
|| (a_elt
&& a_elt
->indx
< b_elt
->indx
))
1381 /* A is before B. Remove A */
1383 a_prev
= a_elt
->prev
;
1384 bitmap_element_free (a
, a_elt
);
1387 else if (!a_elt
|| b_elt
->indx
< a_elt
->indx
)
1389 /* B is before A. Copy B. */
1390 next
= bitmap_elt_insert_after (a
, a_prev
, b_elt
->indx
);
1391 memcpy (next
->bits
, b_elt
->bits
, sizeof (next
->bits
));
1393 b_elt
= b_elt
->next
;
1397 /* Matching elts, generate A = ~A & B. */
1399 BITMAP_WORD ior
= 0;
1401 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1403 BITMAP_WORD cleared
= a_elt
->bits
[ix
] & b_elt
->bits
[ix
];
1404 BITMAP_WORD r
= b_elt
->bits
[ix
] ^ cleared
;
1406 a_elt
->bits
[ix
] = r
;
1411 bitmap_element_free (a
, a_elt
);
1415 b_elt
= b_elt
->next
;
1418 gcc_checking_assert (!a
->current
== !a
->first
1419 && (!a
->current
|| a
->indx
== a
->current
->indx
));
1424 /* Insert an element corresponding to A_ELT | B_ELT after DST_PREV,
1425 overwriting DST_ELT if non-NULL. CHANGED is true if the destination bitmap
1426 had already been changed; the new value of CHANGED is returned. */
1429 bitmap_elt_ior (bitmap dst
, bitmap_element
*dst_elt
, bitmap_element
*dst_prev
,
1430 const bitmap_element
*a_elt
, const bitmap_element
*b_elt
,
1433 gcc_assert (a_elt
|| b_elt
);
1435 if (a_elt
&& b_elt
&& a_elt
->indx
== b_elt
->indx
)
1437 /* Matching elts, generate A | B. */
1440 if (!changed
&& dst_elt
&& dst_elt
->indx
== a_elt
->indx
)
1442 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1444 BITMAP_WORD r
= a_elt
->bits
[ix
] | b_elt
->bits
[ix
];
1445 if (r
!= dst_elt
->bits
[ix
])
1447 dst_elt
->bits
[ix
] = r
;
1456 dst_elt
= bitmap_elt_insert_after (dst
, dst_prev
, a_elt
->indx
);
1458 dst_elt
->indx
= a_elt
->indx
;
1459 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1461 BITMAP_WORD r
= a_elt
->bits
[ix
] | b_elt
->bits
[ix
];
1462 dst_elt
->bits
[ix
] = r
;
1468 /* Copy a single element. */
1469 const bitmap_element
*src
;
1471 if (!b_elt
|| (a_elt
&& a_elt
->indx
< b_elt
->indx
))
1476 gcc_checking_assert (src
);
1477 changed
= bitmap_elt_copy (dst
, dst_elt
, dst_prev
, src
, changed
);
1483 /* DST = A | B. Return true if DST changes. */
1486 bitmap_ior (bitmap dst
, const_bitmap a
, const_bitmap b
)
1488 bitmap_element
*dst_elt
= dst
->first
;
1489 const bitmap_element
*a_elt
= a
->first
;
1490 const bitmap_element
*b_elt
= b
->first
;
1491 bitmap_element
*dst_prev
= NULL
;
1492 bitmap_element
**dst_prev_pnext
= &dst
->first
;
1493 bool changed
= false;
1495 gcc_assert (dst
!= a
&& dst
!= b
);
1497 while (a_elt
|| b_elt
)
1499 changed
= bitmap_elt_ior (dst
, dst_elt
, dst_prev
, a_elt
, b_elt
, changed
);
1501 if (a_elt
&& b_elt
&& a_elt
->indx
== b_elt
->indx
)
1503 a_elt
= a_elt
->next
;
1504 b_elt
= b_elt
->next
;
1508 if (a_elt
&& (!b_elt
|| a_elt
->indx
<= b_elt
->indx
))
1509 a_elt
= a_elt
->next
;
1510 else if (b_elt
&& (!a_elt
|| b_elt
->indx
<= a_elt
->indx
))
1511 b_elt
= b_elt
->next
;
1514 dst_prev
= *dst_prev_pnext
;
1515 dst_prev_pnext
= &dst_prev
->next
;
1516 dst_elt
= *dst_prev_pnext
;
1522 /* Ensure that dst->current is valid. */
1523 dst
->current
= dst
->first
;
1524 bitmap_elt_clear_from (dst
, dst_elt
);
1526 gcc_checking_assert (!dst
->current
== !dst
->first
);
1528 dst
->indx
= dst
->current
->indx
;
1532 /* A |= B. Return true if A changes. */
1535 bitmap_ior_into (bitmap a
, const_bitmap b
)
1537 bitmap_element
*a_elt
= a
->first
;
1538 const bitmap_element
*b_elt
= b
->first
;
1539 bitmap_element
*a_prev
= NULL
;
1540 bitmap_element
**a_prev_pnext
= &a
->first
;
1541 bool changed
= false;
1548 /* If A lags behind B, just advance it. */
1549 if (!a_elt
|| a_elt
->indx
== b_elt
->indx
)
1551 changed
= bitmap_elt_ior (a
, a_elt
, a_prev
, a_elt
, b_elt
, changed
);
1552 b_elt
= b_elt
->next
;
1554 else if (a_elt
->indx
> b_elt
->indx
)
1556 changed
= bitmap_elt_copy (a
, NULL
, a_prev
, b_elt
, changed
);
1557 b_elt
= b_elt
->next
;
1560 a_prev
= *a_prev_pnext
;
1561 a_prev_pnext
= &a_prev
->next
;
1562 a_elt
= *a_prev_pnext
;
1565 gcc_checking_assert (!a
->current
== !a
->first
);
1567 a
->indx
= a
->current
->indx
;
1574 bitmap_xor (bitmap dst
, const_bitmap a
, const_bitmap b
)
1576 bitmap_element
*dst_elt
= dst
->first
;
1577 const bitmap_element
*a_elt
= a
->first
;
1578 const bitmap_element
*b_elt
= b
->first
;
1579 bitmap_element
*dst_prev
= NULL
;
1581 gcc_assert (dst
!= a
&& dst
!= b
);
1588 while (a_elt
|| b_elt
)
1590 if (a_elt
&& b_elt
&& a_elt
->indx
== b_elt
->indx
)
1592 /* Matching elts, generate A ^ B. */
1594 BITMAP_WORD ior
= 0;
1597 dst_elt
= bitmap_elt_insert_after (dst
, dst_prev
, a_elt
->indx
);
1599 dst_elt
->indx
= a_elt
->indx
;
1600 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1602 BITMAP_WORD r
= a_elt
->bits
[ix
] ^ b_elt
->bits
[ix
];
1605 dst_elt
->bits
[ix
] = r
;
1607 a_elt
= a_elt
->next
;
1608 b_elt
= b_elt
->next
;
1612 dst_elt
= dst_elt
->next
;
1617 /* Copy a single element. */
1618 const bitmap_element
*src
;
1620 if (!b_elt
|| (a_elt
&& a_elt
->indx
< b_elt
->indx
))
1623 a_elt
= a_elt
->next
;
1628 b_elt
= b_elt
->next
;
1632 dst_elt
= bitmap_elt_insert_after (dst
, dst_prev
, src
->indx
);
1634 dst_elt
->indx
= src
->indx
;
1635 memcpy (dst_elt
->bits
, src
->bits
, sizeof (dst_elt
->bits
));
1637 dst_elt
= dst_elt
->next
;
1640 /* Ensure that dst->current is valid. */
1641 dst
->current
= dst
->first
;
1642 bitmap_elt_clear_from (dst
, dst_elt
);
1643 gcc_checking_assert (!dst
->current
== !dst
->first
);
1645 dst
->indx
= dst
->current
->indx
;
1651 bitmap_xor_into (bitmap a
, const_bitmap b
)
1653 bitmap_element
*a_elt
= a
->first
;
1654 const bitmap_element
*b_elt
= b
->first
;
1655 bitmap_element
*a_prev
= NULL
;
1665 if (!a_elt
|| b_elt
->indx
< a_elt
->indx
)
1668 bitmap_element
*dst
= bitmap_elt_insert_after (a
, a_prev
, b_elt
->indx
);
1669 memcpy (dst
->bits
, b_elt
->bits
, sizeof (dst
->bits
));
1671 b_elt
= b_elt
->next
;
1673 else if (a_elt
->indx
< b_elt
->indx
)
1676 a_elt
= a_elt
->next
;
1680 /* Matching elts, generate A ^= B. */
1682 BITMAP_WORD ior
= 0;
1683 bitmap_element
*next
= a_elt
->next
;
1685 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1687 BITMAP_WORD r
= a_elt
->bits
[ix
] ^ b_elt
->bits
[ix
];
1690 a_elt
->bits
[ix
] = r
;
1692 b_elt
= b_elt
->next
;
1696 bitmap_element_free (a
, a_elt
);
1700 gcc_checking_assert (!a
->current
== !a
->first
);
1702 a
->indx
= a
->current
->indx
;
1705 /* Return true if two bitmaps are identical.
1706 We do not bother with a check for pointer equality, as that never
1707 occurs in practice. */
1710 bitmap_equal_p (const_bitmap a
, const_bitmap b
)
1712 const bitmap_element
*a_elt
;
1713 const bitmap_element
*b_elt
;
1716 for (a_elt
= a
->first
, b_elt
= b
->first
;
1718 a_elt
= a_elt
->next
, b_elt
= b_elt
->next
)
1720 if (a_elt
->indx
!= b_elt
->indx
)
1722 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1723 if (a_elt
->bits
[ix
] != b_elt
->bits
[ix
])
1726 return !a_elt
&& !b_elt
;
1729 /* Return true if A AND B is not empty. */
1732 bitmap_intersect_p (const_bitmap a
, const_bitmap b
)
1734 const bitmap_element
*a_elt
;
1735 const bitmap_element
*b_elt
;
1738 for (a_elt
= a
->first
, b_elt
= b
->first
;
1741 if (a_elt
->indx
< b_elt
->indx
)
1742 a_elt
= a_elt
->next
;
1743 else if (b_elt
->indx
< a_elt
->indx
)
1744 b_elt
= b_elt
->next
;
1747 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1748 if (a_elt
->bits
[ix
] & b_elt
->bits
[ix
])
1750 a_elt
= a_elt
->next
;
1751 b_elt
= b_elt
->next
;
1757 /* Return true if A AND NOT B is not empty. */
1760 bitmap_intersect_compl_p (const_bitmap a
, const_bitmap b
)
1762 const bitmap_element
*a_elt
;
1763 const bitmap_element
*b_elt
;
1765 for (a_elt
= a
->first
, b_elt
= b
->first
;
1768 if (a_elt
->indx
< b_elt
->indx
)
1770 else if (b_elt
->indx
< a_elt
->indx
)
1771 b_elt
= b_elt
->next
;
1774 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1775 if (a_elt
->bits
[ix
] & ~b_elt
->bits
[ix
])
1777 a_elt
= a_elt
->next
;
1778 b_elt
= b_elt
->next
;
1781 return a_elt
!= NULL
;
1785 /* DST = A | (FROM1 & ~FROM2). Return true if DST changes. */
1788 bitmap_ior_and_compl (bitmap dst
, const_bitmap a
, const_bitmap b
, const_bitmap kill
)
1790 bool changed
= false;
1792 bitmap_element
*dst_elt
= dst
->first
;
1793 const bitmap_element
*a_elt
= a
->first
;
1794 const bitmap_element
*b_elt
= b
->first
;
1795 const bitmap_element
*kill_elt
= kill
->first
;
1796 bitmap_element
*dst_prev
= NULL
;
1797 bitmap_element
**dst_prev_pnext
= &dst
->first
;
1799 gcc_assert (dst
!= a
&& dst
!= b
&& dst
!= kill
);
1801 /* Special cases. We don't bother checking for bitmap_equal_p (b, kill). */
1802 if (b
== kill
|| bitmap_empty_p (b
))
1804 changed
= !bitmap_equal_p (dst
, a
);
1806 bitmap_copy (dst
, a
);
1809 if (bitmap_empty_p (kill
))
1810 return bitmap_ior (dst
, a
, b
);
1811 if (bitmap_empty_p (a
))
1812 return bitmap_and_compl (dst
, b
, kill
);
1814 while (a_elt
|| b_elt
)
1816 bool new_element
= false;
1819 while (kill_elt
&& kill_elt
->indx
< b_elt
->indx
)
1820 kill_elt
= kill_elt
->next
;
1822 if (b_elt
&& kill_elt
&& kill_elt
->indx
== b_elt
->indx
1823 && (!a_elt
|| a_elt
->indx
>= b_elt
->indx
))
1825 bitmap_element tmp_elt
;
1828 BITMAP_WORD ior
= 0;
1829 tmp_elt
.indx
= b_elt
->indx
;
1830 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1832 BITMAP_WORD r
= b_elt
->bits
[ix
] & ~kill_elt
->bits
[ix
];
1834 tmp_elt
.bits
[ix
] = r
;
1839 changed
= bitmap_elt_ior (dst
, dst_elt
, dst_prev
,
1840 a_elt
, &tmp_elt
, changed
);
1842 if (a_elt
&& a_elt
->indx
== b_elt
->indx
)
1843 a_elt
= a_elt
->next
;
1846 b_elt
= b_elt
->next
;
1847 kill_elt
= kill_elt
->next
;
1851 changed
= bitmap_elt_ior (dst
, dst_elt
, dst_prev
,
1852 a_elt
, b_elt
, changed
);
1855 if (a_elt
&& b_elt
&& a_elt
->indx
== b_elt
->indx
)
1857 a_elt
= a_elt
->next
;
1858 b_elt
= b_elt
->next
;
1862 if (a_elt
&& (!b_elt
|| a_elt
->indx
<= b_elt
->indx
))
1863 a_elt
= a_elt
->next
;
1864 else if (b_elt
&& (!a_elt
|| b_elt
->indx
<= a_elt
->indx
))
1865 b_elt
= b_elt
->next
;
1871 dst_prev
= *dst_prev_pnext
;
1872 dst_prev_pnext
= &dst_prev
->next
;
1873 dst_elt
= *dst_prev_pnext
;
1880 /* Ensure that dst->current is valid. */
1881 dst
->current
= dst
->first
;
1882 bitmap_elt_clear_from (dst
, dst_elt
);
1884 gcc_checking_assert (!dst
->current
== !dst
->first
);
1886 dst
->indx
= dst
->current
->indx
;
1891 /* A |= (FROM1 & ~FROM2). Return true if A changes. */
1894 bitmap_ior_and_compl_into (bitmap a
, const_bitmap from1
, const_bitmap from2
)
1899 bitmap_initialize (&tmp
, &bitmap_default_obstack
);
1900 bitmap_and_compl (&tmp
, from1
, from2
);
1901 changed
= bitmap_ior_into (a
, &tmp
);
1902 bitmap_clear (&tmp
);
1907 /* A |= (B & C). Return true if A changes. */
1910 bitmap_ior_and_into (bitmap a
, const_bitmap b
, const_bitmap c
)
1912 bitmap_element
*a_elt
= a
->first
;
1913 const bitmap_element
*b_elt
= b
->first
;
1914 const bitmap_element
*c_elt
= c
->first
;
1915 bitmap_element and_elt
;
1916 bitmap_element
*a_prev
= NULL
;
1917 bitmap_element
**a_prev_pnext
= &a
->first
;
1918 bool changed
= false;
1922 return bitmap_ior_into (a
, b
);
1923 if (bitmap_empty_p (b
) || bitmap_empty_p (c
))
1927 while (b_elt
&& c_elt
)
1929 BITMAP_WORD overall
;
1931 /* Find a common item of B and C. */
1932 while (b_elt
->indx
!= c_elt
->indx
)
1934 if (b_elt
->indx
< c_elt
->indx
)
1936 b_elt
= b_elt
->next
;
1942 c_elt
= c_elt
->next
;
1949 and_elt
.indx
= b_elt
->indx
;
1950 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1952 and_elt
.bits
[ix
] = b_elt
->bits
[ix
] & c_elt
->bits
[ix
];
1953 overall
|= and_elt
.bits
[ix
];
1956 b_elt
= b_elt
->next
;
1957 c_elt
= c_elt
->next
;
1961 /* Now find a place to insert AND_ELT. */
1964 ix
= a_elt
? a_elt
->indx
: and_elt
.indx
;
1965 if (ix
== and_elt
.indx
)
1966 changed
= bitmap_elt_ior (a
, a_elt
, a_prev
, a_elt
, &and_elt
, changed
);
1967 else if (ix
> and_elt
.indx
)
1968 changed
= bitmap_elt_copy (a
, NULL
, a_prev
, &and_elt
, changed
);
1970 a_prev
= *a_prev_pnext
;
1971 a_prev_pnext
= &a_prev
->next
;
1972 a_elt
= *a_prev_pnext
;
1974 /* If A lagged behind B/C, we advanced it so loop once more. */
1976 while (ix
< and_elt
.indx
);
1980 gcc_checking_assert (!a
->current
== !a
->first
);
1982 a
->indx
= a
->current
->indx
;
1986 /* Compute hash of bitmap (for purposes of hashing). */
1988 bitmap_hash (const_bitmap head
)
1990 const bitmap_element
*ptr
;
1991 BITMAP_WORD hash
= 0;
1994 for (ptr
= head
->first
; ptr
; ptr
= ptr
->next
)
1997 for (ix
= 0; ix
!= BITMAP_ELEMENT_WORDS
; ix
++)
1998 hash
^= ptr
->bits
[ix
];
2000 return (hashval_t
)hash
;
2004 /* Debugging function to print out the contents of a bitmap. */
2007 debug_bitmap_file (FILE *file
, const_bitmap head
)
2009 const bitmap_element
*ptr
;
2011 fprintf (file
, "\nfirst = " HOST_PTR_PRINTF
2012 " current = " HOST_PTR_PRINTF
" indx = %u\n",
2013 (void *) head
->first
, (void *) head
->current
, head
->indx
);
2015 for (ptr
= head
->first
; ptr
; ptr
= ptr
->next
)
2017 unsigned int i
, j
, col
= 26;
2019 fprintf (file
, "\t" HOST_PTR_PRINTF
" next = " HOST_PTR_PRINTF
2020 " prev = " HOST_PTR_PRINTF
" indx = %u\n\t\tbits = {",
2021 (const void*) ptr
, (const void*) ptr
->next
,
2022 (const void*) ptr
->prev
, ptr
->indx
);
2024 for (i
= 0; i
< BITMAP_ELEMENT_WORDS
; i
++)
2025 for (j
= 0; j
< BITMAP_WORD_BITS
; j
++)
2026 if ((ptr
->bits
[i
] >> j
) & 1)
2030 fprintf (file
, "\n\t\t\t");
2034 fprintf (file
, " %u", (ptr
->indx
* BITMAP_ELEMENT_ALL_BITS
2035 + i
* BITMAP_WORD_BITS
+ j
));
2039 fprintf (file
, " }\n");
2043 /* Function to be called from the debugger to print the contents
2047 debug_bitmap (const_bitmap head
)
2049 debug_bitmap_file (stderr
, head
);
2052 /* Function to print out the contents of a bitmap. Unlike debug_bitmap_file,
2053 it does not print anything but the bits. */
2056 bitmap_print (FILE *file
, const_bitmap head
, const char *prefix
,
2059 const char *comma
= "";
2063 fputs (prefix
, file
);
2064 EXECUTE_IF_SET_IN_BITMAP (head
, 0, i
, bi
)
2066 fprintf (file
, "%s%d", comma
, i
);
2069 fputs (suffix
, file
);
2072 /* Output per-bitmap memory usage statistics. */
2074 dump_bitmap_statistics (void)
2076 if (!GATHER_STATISTICS
)
2079 bitmap_mem_desc
.dump (BITMAP_ORIGIN
);
2083 debug (const bitmap_head
&ref
)
2085 dump_bitmap (stderr
, &ref
);
2089 debug (const bitmap_head
*ptr
)
2094 fprintf (stderr
, "<nil>\n");
2098 #include "gt-bitmap.h"