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"
26 #include "hash-table.h"
29 #include "mem-stats.h"
32 /* Memory allocation statistics purpose instance. */
33 mem_alloc_description
<bitmap_usage
> bitmap_mem_desc
;
35 /* Register new bitmap. */
37 bitmap_register (bitmap b MEM_STAT_DECL
)
39 bitmap_mem_desc
.register_descriptor (b
, BITMAP
, false FINAL_PASS_MEM_STAT
);
42 /* Account the overhead. */
44 register_overhead (bitmap b
, int amount
)
46 if (bitmap_mem_desc
.contains_descriptor_for_instance (b
))
47 bitmap_mem_desc
.register_instance_overhead (amount
, b
);
51 bitmap_element bitmap_zero_bits
; /* An element of all zero bits. */
52 bitmap_obstack bitmap_default_obstack
; /* The default bitmap obstack. */
53 static int bitmap_default_obstack_depth
;
54 static GTY((deletable
)) bitmap_element
*bitmap_ggc_free
; /* Freelist of
57 static void bitmap_elem_to_freelist (bitmap
, bitmap_element
*);
58 static void bitmap_element_free (bitmap
, bitmap_element
*);
59 static bitmap_element
*bitmap_element_allocate (bitmap
);
60 static int bitmap_element_zerop (const bitmap_element
*);
61 static void bitmap_element_link (bitmap
, bitmap_element
*);
62 static bitmap_element
*bitmap_elt_insert_after (bitmap
, bitmap_element
*, unsigned int);
63 static void bitmap_elt_clear_from (bitmap
, bitmap_element
*);
64 static bitmap_element
*bitmap_find_bit (bitmap
, unsigned int);
67 /* Add ELEM to the appropriate freelist. */
69 bitmap_elem_to_freelist (bitmap head
, bitmap_element
*elt
)
71 bitmap_obstack
*bit_obstack
= head
->obstack
;
76 elt
->prev
= bit_obstack
->elements
;
77 bit_obstack
->elements
= elt
;
81 elt
->prev
= bitmap_ggc_free
;
82 bitmap_ggc_free
= elt
;
86 /* Free a bitmap element. Since these are allocated off the
87 bitmap_obstack, "free" actually means "put onto the freelist". */
90 bitmap_element_free (bitmap head
, bitmap_element
*elt
)
92 bitmap_element
*next
= elt
->next
;
93 bitmap_element
*prev
= elt
->prev
;
101 if (head
->first
== elt
)
104 /* Since the first thing we try is to insert before current,
105 make current the next entry in preference to the previous. */
106 if (head
->current
== elt
)
108 head
->current
= next
!= 0 ? next
: prev
;
110 head
->indx
= head
->current
->indx
;
115 if (GATHER_STATISTICS
)
116 register_overhead (head
, -((int)sizeof (bitmap_element
)));
118 bitmap_elem_to_freelist (head
, elt
);
121 /* Allocate a bitmap element. The bits are cleared, but nothing else is. */
123 static inline bitmap_element
*
124 bitmap_element_allocate (bitmap head
)
126 bitmap_element
*element
;
127 bitmap_obstack
*bit_obstack
= head
->obstack
;
131 element
= bit_obstack
->elements
;
134 /* Use up the inner list first before looking at the next
135 element of the outer list. */
138 bit_obstack
->elements
= element
->next
;
139 bit_obstack
->elements
->prev
= element
->prev
;
142 /* Inner list was just a singleton. */
143 bit_obstack
->elements
= element
->prev
;
145 element
= XOBNEW (&bit_obstack
->obstack
, bitmap_element
);
149 element
= bitmap_ggc_free
;
151 /* Use up the inner list first before looking at the next
152 element of the outer list. */
155 bitmap_ggc_free
= element
->next
;
156 bitmap_ggc_free
->prev
= element
->prev
;
159 /* Inner list was just a singleton. */
160 bitmap_ggc_free
= element
->prev
;
162 element
= ggc_alloc
<bitmap_element
> ();
165 if (GATHER_STATISTICS
)
166 register_overhead (head
, sizeof (bitmap_element
));
168 memset (element
->bits
, 0, sizeof (element
->bits
));
173 /* Remove ELT and all following elements from bitmap HEAD. */
176 bitmap_elt_clear_from (bitmap head
, bitmap_element
*elt
)
178 bitmap_element
*prev
;
179 bitmap_obstack
*bit_obstack
= head
->obstack
;
183 if (GATHER_STATISTICS
)
186 for (prev
= elt
; prev
; prev
= prev
->next
)
188 register_overhead (head
, -sizeof (bitmap_element
) * n
);
195 if (head
->current
->indx
> prev
->indx
)
197 head
->current
= prev
;
198 head
->indx
= prev
->indx
;
204 head
->current
= NULL
;
208 /* Put the entire list onto the free list in one operation. */
211 elt
->prev
= bit_obstack
->elements
;
212 bit_obstack
->elements
= elt
;
216 elt
->prev
= bitmap_ggc_free
;
217 bitmap_ggc_free
= elt
;
221 /* Clear a bitmap by freeing the linked list. */
224 bitmap_clear (bitmap head
)
227 bitmap_elt_clear_from (head
, head
->first
);
230 /* Initialize a bitmap obstack. If BIT_OBSTACK is NULL, initialize
231 the default bitmap obstack. */
234 bitmap_obstack_initialize (bitmap_obstack
*bit_obstack
)
238 if (bitmap_default_obstack_depth
++)
240 bit_obstack
= &bitmap_default_obstack
;
243 #if !defined(__GNUC__) || (__GNUC__ < 2)
244 #define __alignof__(type) 0
247 bit_obstack
->elements
= NULL
;
248 bit_obstack
->heads
= NULL
;
249 obstack_specify_allocation (&bit_obstack
->obstack
, OBSTACK_CHUNK_SIZE
,
250 __alignof__ (bitmap_element
),
255 /* Release the memory from a bitmap obstack. If BIT_OBSTACK is NULL,
256 release the default bitmap obstack. */
259 bitmap_obstack_release (bitmap_obstack
*bit_obstack
)
263 if (--bitmap_default_obstack_depth
)
265 gcc_assert (bitmap_default_obstack_depth
> 0);
268 bit_obstack
= &bitmap_default_obstack
;
271 bit_obstack
->elements
= NULL
;
272 bit_obstack
->heads
= NULL
;
273 obstack_free (&bit_obstack
->obstack
, NULL
);
276 /* Create a new bitmap on an obstack. If BIT_OBSTACK is NULL, create
277 it on the default bitmap obstack. */
280 bitmap_obstack_alloc_stat (bitmap_obstack
*bit_obstack MEM_STAT_DECL
)
285 bit_obstack
= &bitmap_default_obstack
;
286 map
= bit_obstack
->heads
;
288 bit_obstack
->heads
= (struct bitmap_head
*) map
->first
;
290 map
= XOBNEW (&bit_obstack
->obstack
, bitmap_head
);
291 bitmap_initialize_stat (map
, bit_obstack PASS_MEM_STAT
);
293 if (GATHER_STATISTICS
)
294 register_overhead (map
, sizeof (bitmap_head
));
299 /* Create a new GCd bitmap. */
302 bitmap_gc_alloc_stat (ALONE_MEM_STAT_DECL
)
306 map
= ggc_alloc
<bitmap_head
> ();
307 bitmap_initialize_stat (map
, NULL PASS_MEM_STAT
);
309 if (GATHER_STATISTICS
)
310 register_overhead (map
, sizeof (bitmap_head
));
315 /* Release an obstack allocated bitmap. */
318 bitmap_obstack_free (bitmap map
)
323 map
->first
= (bitmap_element
*) map
->obstack
->heads
;
325 if (GATHER_STATISTICS
)
326 register_overhead (map
, -((int)sizeof (bitmap_head
)));
328 map
->obstack
->heads
= map
;
333 /* Return nonzero if all bits in an element are zero. */
336 bitmap_element_zerop (const bitmap_element
*element
)
338 #if BITMAP_ELEMENT_WORDS == 2
339 return (element
->bits
[0] | element
->bits
[1]) == 0;
343 for (i
= 0; i
< BITMAP_ELEMENT_WORDS
; i
++)
344 if (element
->bits
[i
] != 0)
351 /* Link the bitmap element into the current bitmap linked list. */
354 bitmap_element_link (bitmap head
, bitmap_element
*element
)
356 unsigned int indx
= element
->indx
;
359 /* If this is the first and only element, set it in. */
360 if (head
->first
== 0)
362 element
->next
= element
->prev
= 0;
363 head
->first
= element
;
366 /* If this index is less than that of the current element, it goes someplace
367 before the current element. */
368 else if (indx
< head
->indx
)
370 for (ptr
= head
->current
;
371 ptr
->prev
!= 0 && ptr
->prev
->indx
> indx
;
376 ptr
->prev
->next
= element
;
378 head
->first
= element
;
380 element
->prev
= ptr
->prev
;
385 /* Otherwise, it must go someplace after the current element. */
388 for (ptr
= head
->current
;
389 ptr
->next
!= 0 && ptr
->next
->indx
< indx
;
394 ptr
->next
->prev
= element
;
396 element
->next
= ptr
->next
;
401 /* Set up so this is the first element searched. */
402 head
->current
= element
;
406 /* Insert a new uninitialized element into bitmap HEAD after element
407 ELT. If ELT is NULL, insert the element at the start. Return the
410 static bitmap_element
*
411 bitmap_elt_insert_after (bitmap head
, bitmap_element
*elt
, unsigned int indx
)
413 bitmap_element
*node
= bitmap_element_allocate (head
);
420 head
->current
= node
;
423 node
->next
= head
->first
;
425 node
->next
->prev
= node
;
431 gcc_checking_assert (head
->current
);
432 node
->next
= elt
->next
;
434 node
->next
->prev
= node
;
441 /* Copy a bitmap to another bitmap. */
444 bitmap_copy (bitmap to
, const_bitmap from
)
446 const bitmap_element
*from_ptr
;
447 bitmap_element
*to_ptr
= 0;
451 /* Copy elements in forward direction one at a time. */
452 for (from_ptr
= from
->first
; from_ptr
; from_ptr
= from_ptr
->next
)
454 bitmap_element
*to_elt
= bitmap_element_allocate (to
);
456 to_elt
->indx
= from_ptr
->indx
;
457 memcpy (to_elt
->bits
, from_ptr
->bits
, sizeof (to_elt
->bits
));
459 /* Here we have a special case of bitmap_element_link, for the case
460 where we know the links are being entered in sequence. */
463 to
->first
= to
->current
= to_elt
;
464 to
->indx
= from_ptr
->indx
;
465 to_elt
->next
= to_elt
->prev
= 0;
469 to_elt
->prev
= to_ptr
;
471 to_ptr
->next
= to_elt
;
478 /* Find a bitmap element that would hold a bitmap's bit.
479 Update the `current' field even if we can't find an element that
480 would hold the bitmap's bit to make eventual allocation
483 static inline bitmap_element
*
484 bitmap_find_bit (bitmap head
, unsigned int bit
)
486 bitmap_element
*element
;
487 unsigned int indx
= bit
/ BITMAP_ELEMENT_ALL_BITS
;
489 if (head
->current
== NULL
490 || head
->indx
== indx
)
491 return head
->current
;
492 if (head
->current
== head
->first
493 && head
->first
->next
== NULL
)
496 /* Usage can be NULL due to allocated bitmaps for which we do not
497 call initialize function. */
498 bitmap_usage
*usage
= bitmap_mem_desc
.get_descriptor_for_instance (head
);
500 /* This bitmap has more than one element, and we're going to look
501 through the elements list. Count that as a search. */
502 if (GATHER_STATISTICS
&& usage
)
503 usage
->m_nsearches
++;
505 if (head
->indx
< indx
)
506 /* INDX is beyond head->indx. Search from head->current
508 for (element
= head
->current
;
509 element
->next
!= 0 && element
->indx
< indx
;
510 element
= element
->next
)
512 if (GATHER_STATISTICS
&& usage
)
513 usage
->m_search_iter
++;
516 else if (head
->indx
/ 2 < indx
)
517 /* INDX is less than head->indx and closer to head->indx than to
518 0. Search from head->current backward. */
519 for (element
= head
->current
;
520 element
->prev
!= 0 && element
->indx
> indx
;
521 element
= element
->prev
)
523 if (GATHER_STATISTICS
&& usage
)
524 usage
->m_search_iter
++;
528 /* INDX is less than head->indx and closer to 0 than to
529 head->indx. Search from head->first forward. */
530 for (element
= head
->first
;
531 element
->next
!= 0 && element
->indx
< indx
;
532 element
= element
->next
)
533 if (GATHER_STATISTICS
&& usage
)
535 usage
->m_search_iter
++;
538 /* `element' is the nearest to the one we want. If it's not the one we
539 want, the one we want doesn't exist. */
540 head
->current
= element
;
541 head
->indx
= element
->indx
;
542 if (element
!= 0 && element
->indx
!= indx
)
548 /* Clear a single bit in a bitmap. Return true if the bit changed. */
551 bitmap_clear_bit (bitmap head
, int bit
)
553 bitmap_element
*const ptr
= bitmap_find_bit (head
, bit
);
557 unsigned bit_num
= bit
% BITMAP_WORD_BITS
;
558 unsigned word_num
= bit
/ BITMAP_WORD_BITS
% BITMAP_ELEMENT_WORDS
;
559 BITMAP_WORD bit_val
= ((BITMAP_WORD
) 1) << bit_num
;
560 bool res
= (ptr
->bits
[word_num
] & bit_val
) != 0;
563 ptr
->bits
[word_num
] &= ~bit_val
;
564 /* If we cleared the entire word, free up the element. */
565 if (!ptr
->bits
[word_num
]
566 && bitmap_element_zerop (ptr
))
567 bitmap_element_free (head
, ptr
);
576 /* Set a single bit in a bitmap. Return true if the bit changed. */
579 bitmap_set_bit (bitmap head
, int bit
)
581 bitmap_element
*ptr
= bitmap_find_bit (head
, bit
);
582 unsigned word_num
= bit
/ BITMAP_WORD_BITS
% BITMAP_ELEMENT_WORDS
;
583 unsigned bit_num
= bit
% BITMAP_WORD_BITS
;
584 BITMAP_WORD bit_val
= ((BITMAP_WORD
) 1) << bit_num
;
588 ptr
= bitmap_element_allocate (head
);
589 ptr
->indx
= bit
/ BITMAP_ELEMENT_ALL_BITS
;
590 ptr
->bits
[word_num
] = bit_val
;
591 bitmap_element_link (head
, ptr
);
596 bool res
= (ptr
->bits
[word_num
] & bit_val
) == 0;
598 ptr
->bits
[word_num
] |= bit_val
;
603 /* Return whether a bit is set within a bitmap. */
606 bitmap_bit_p (bitmap head
, int bit
)
612 ptr
= bitmap_find_bit (head
, bit
);
616 bit_num
= bit
% BITMAP_WORD_BITS
;
617 word_num
= bit
/ BITMAP_WORD_BITS
% BITMAP_ELEMENT_WORDS
;
619 return (ptr
->bits
[word_num
] >> bit_num
) & 1;
622 #if GCC_VERSION < 3400
623 /* Table of number of set bits in a character, indexed by value of char. */
624 static const unsigned char popcount_table
[] =
626 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,
627 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,
628 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,
629 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,
630 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,
631 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,
632 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,
633 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,
637 bitmap_popcount (BITMAP_WORD a
)
639 unsigned long ret
= 0;
642 /* Just do this the table way for now */
643 for (i
= 0; i
< BITMAP_WORD_BITS
; i
+= 8)
644 ret
+= popcount_table
[(a
>> i
) & 0xff];
648 /* Count the number of bits set in the bitmap, and return it. */
651 bitmap_count_bits (const_bitmap a
)
653 unsigned long count
= 0;
654 const bitmap_element
*elt
;
657 for (elt
= a
->first
; elt
; elt
= elt
->next
)
659 for (ix
= 0; ix
!= BITMAP_ELEMENT_WORDS
; ix
++)
661 #if GCC_VERSION >= 3400
662 /* Note that popcountl matches BITMAP_WORD in type, so the actual size
663 of BITMAP_WORD is not material. */
664 count
+= __builtin_popcountl (elt
->bits
[ix
]);
666 count
+= bitmap_popcount (elt
->bits
[ix
]);
673 /* Return true if the bitmap has a single bit set. Otherwise return
677 bitmap_single_bit_set_p (const_bitmap a
)
679 unsigned long count
= 0;
680 const bitmap_element
*elt
;
683 if (bitmap_empty_p (a
))
687 /* As there are no completely empty bitmap elements, a second one
688 means we have more than one bit set. */
689 if (elt
->next
!= NULL
)
692 for (ix
= 0; ix
!= BITMAP_ELEMENT_WORDS
; ix
++)
694 #if GCC_VERSION >= 3400
695 /* Note that popcountl matches BITMAP_WORD in type, so the actual size
696 of BITMAP_WORD is not material. */
697 count
+= __builtin_popcountl (elt
->bits
[ix
]);
699 count
+= bitmap_popcount (elt
->bits
[ix
]);
709 /* Return the bit number of the first set bit in the bitmap. The
710 bitmap must be non-empty. */
713 bitmap_first_set_bit (const_bitmap a
)
715 const bitmap_element
*elt
= a
->first
;
720 gcc_checking_assert (elt
);
721 bit_no
= elt
->indx
* BITMAP_ELEMENT_ALL_BITS
;
722 for (ix
= 0; ix
!= BITMAP_ELEMENT_WORDS
; ix
++)
724 word
= elt
->bits
[ix
];
730 bit_no
+= ix
* BITMAP_WORD_BITS
;
732 #if GCC_VERSION >= 3004
733 gcc_assert (sizeof (long) == sizeof (word
));
734 bit_no
+= __builtin_ctzl (word
);
736 /* Binary search for the first set bit. */
737 #if BITMAP_WORD_BITS > 64
738 #error "Fill out the table."
740 #if BITMAP_WORD_BITS > 32
741 if (!(word
& 0xffffffff))
742 word
>>= 32, bit_no
+= 32;
744 if (!(word
& 0xffff))
745 word
>>= 16, bit_no
+= 16;
747 word
>>= 8, bit_no
+= 8;
749 word
>>= 4, bit_no
+= 4;
751 word
>>= 2, bit_no
+= 2;
753 word
>>= 1, bit_no
+= 1;
755 gcc_checking_assert (word
& 1);
760 /* Return the bit number of the first set bit in the bitmap. The
761 bitmap must be non-empty. */
764 bitmap_last_set_bit (const_bitmap a
)
766 const bitmap_element
*elt
= a
->current
? a
->current
: a
->first
;
771 gcc_checking_assert (elt
);
774 bit_no
= elt
->indx
* BITMAP_ELEMENT_ALL_BITS
;
775 for (ix
= BITMAP_ELEMENT_WORDS
- 1; ix
>= 0; ix
--)
777 word
= elt
->bits
[ix
];
783 bit_no
+= ix
* BITMAP_WORD_BITS
;
784 #if GCC_VERSION >= 3004
785 gcc_assert (sizeof (long) == sizeof (word
));
786 bit_no
+= BITMAP_WORD_BITS
- __builtin_clzl (word
) - 1;
788 /* Hopefully this is a twos-complement host... */
789 BITMAP_WORD x
= word
;
795 #if BITMAP_WORD_BITS > 32
798 bit_no
+= bitmap_popcount (x
) - 1;
808 bitmap_and (bitmap dst
, const_bitmap a
, const_bitmap b
)
810 bitmap_element
*dst_elt
= dst
->first
;
811 const bitmap_element
*a_elt
= a
->first
;
812 const bitmap_element
*b_elt
= b
->first
;
813 bitmap_element
*dst_prev
= NULL
;
815 gcc_assert (dst
!= a
&& dst
!= b
);
819 bitmap_copy (dst
, a
);
823 while (a_elt
&& b_elt
)
825 if (a_elt
->indx
< b_elt
->indx
)
827 else if (b_elt
->indx
< a_elt
->indx
)
831 /* Matching elts, generate A & B. */
836 dst_elt
= bitmap_elt_insert_after (dst
, dst_prev
, a_elt
->indx
);
838 dst_elt
->indx
= a_elt
->indx
;
839 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
841 BITMAP_WORD r
= a_elt
->bits
[ix
] & b_elt
->bits
[ix
];
843 dst_elt
->bits
[ix
] = r
;
849 dst_elt
= dst_elt
->next
;
855 /* Ensure that dst->current is valid. */
856 dst
->current
= dst
->first
;
857 bitmap_elt_clear_from (dst
, dst_elt
);
858 gcc_checking_assert (!dst
->current
== !dst
->first
);
860 dst
->indx
= dst
->current
->indx
;
863 /* A &= B. Return true if A changed. */
866 bitmap_and_into (bitmap a
, const_bitmap b
)
868 bitmap_element
*a_elt
= a
->first
;
869 const bitmap_element
*b_elt
= b
->first
;
870 bitmap_element
*next
;
871 bool changed
= false;
876 while (a_elt
&& b_elt
)
878 if (a_elt
->indx
< b_elt
->indx
)
881 bitmap_element_free (a
, a_elt
);
885 else if (b_elt
->indx
< a_elt
->indx
)
889 /* Matching elts, generate A &= B. */
893 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
895 BITMAP_WORD r
= a_elt
->bits
[ix
] & b_elt
->bits
[ix
];
896 if (a_elt
->bits
[ix
] != r
)
903 bitmap_element_free (a
, a_elt
);
912 bitmap_elt_clear_from (a
, a_elt
);
915 gcc_checking_assert (!a
->current
== !a
->first
916 && (!a
->current
|| a
->indx
== a
->current
->indx
));
922 /* Insert an element equal to SRC_ELT after DST_PREV, overwriting DST_ELT
923 if non-NULL. CHANGED is true if the destination bitmap had already been
924 changed; the new value of CHANGED is returned. */
927 bitmap_elt_copy (bitmap dst
, bitmap_element
*dst_elt
, bitmap_element
*dst_prev
,
928 const bitmap_element
*src_elt
, bool changed
)
930 if (!changed
&& dst_elt
&& dst_elt
->indx
== src_elt
->indx
)
934 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
935 if (src_elt
->bits
[ix
] != dst_elt
->bits
[ix
])
937 dst_elt
->bits
[ix
] = src_elt
->bits
[ix
];
945 dst_elt
= bitmap_elt_insert_after (dst
, dst_prev
, src_elt
->indx
);
947 dst_elt
->indx
= src_elt
->indx
;
948 memcpy (dst_elt
->bits
, src_elt
->bits
, sizeof (dst_elt
->bits
));
958 bitmap_and_compl (bitmap dst
, const_bitmap a
, const_bitmap b
)
960 bitmap_element
*dst_elt
= dst
->first
;
961 const bitmap_element
*a_elt
= a
->first
;
962 const bitmap_element
*b_elt
= b
->first
;
963 bitmap_element
*dst_prev
= NULL
;
964 bitmap_element
**dst_prev_pnext
= &dst
->first
;
965 bool changed
= false;
967 gcc_assert (dst
!= a
&& dst
!= b
);
971 changed
= !bitmap_empty_p (dst
);
978 while (b_elt
&& b_elt
->indx
< a_elt
->indx
)
981 if (!b_elt
|| b_elt
->indx
> a_elt
->indx
)
983 changed
= bitmap_elt_copy (dst
, dst_elt
, dst_prev
, a_elt
, changed
);
984 dst_prev
= *dst_prev_pnext
;
985 dst_prev_pnext
= &dst_prev
->next
;
986 dst_elt
= *dst_prev_pnext
;
992 /* Matching elts, generate A & ~B. */
996 if (!changed
&& dst_elt
&& dst_elt
->indx
== a_elt
->indx
)
998 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1000 BITMAP_WORD r
= a_elt
->bits
[ix
] & ~b_elt
->bits
[ix
];
1002 if (dst_elt
->bits
[ix
] != r
)
1005 dst_elt
->bits
[ix
] = r
;
1013 if (!dst_elt
|| dst_elt
->indx
> a_elt
->indx
)
1015 dst_elt
= bitmap_elt_insert_after (dst
, dst_prev
, a_elt
->indx
);
1020 dst_elt
->indx
= a_elt
->indx
;
1021 new_element
= false;
1024 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1026 BITMAP_WORD r
= a_elt
->bits
[ix
] & ~b_elt
->bits
[ix
];
1028 dst_elt
->bits
[ix
] = r
;
1036 changed
|= !new_element
;
1037 bitmap_element_free (dst
, dst_elt
);
1038 dst_elt
= *dst_prev_pnext
;
1044 dst_prev
= *dst_prev_pnext
;
1045 dst_prev_pnext
= &dst_prev
->next
;
1046 dst_elt
= *dst_prev_pnext
;
1048 a_elt
= a_elt
->next
;
1049 b_elt
= b_elt
->next
;
1053 /* Ensure that dst->current is valid. */
1054 dst
->current
= dst
->first
;
1059 bitmap_elt_clear_from (dst
, dst_elt
);
1061 gcc_checking_assert (!dst
->current
== !dst
->first
);
1063 dst
->indx
= dst
->current
->indx
;
1068 /* A &= ~B. Returns true if A changes */
1071 bitmap_and_compl_into (bitmap a
, const_bitmap b
)
1073 bitmap_element
*a_elt
= a
->first
;
1074 const bitmap_element
*b_elt
= b
->first
;
1075 bitmap_element
*next
;
1076 BITMAP_WORD changed
= 0;
1080 if (bitmap_empty_p (a
))
1089 while (a_elt
&& b_elt
)
1091 if (a_elt
->indx
< b_elt
->indx
)
1092 a_elt
= a_elt
->next
;
1093 else if (b_elt
->indx
< a_elt
->indx
)
1094 b_elt
= b_elt
->next
;
1097 /* Matching elts, generate A &= ~B. */
1099 BITMAP_WORD ior
= 0;
1101 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1103 BITMAP_WORD cleared
= a_elt
->bits
[ix
] & b_elt
->bits
[ix
];
1104 BITMAP_WORD r
= a_elt
->bits
[ix
] ^ cleared
;
1106 a_elt
->bits
[ix
] = r
;
1112 bitmap_element_free (a
, a_elt
);
1114 b_elt
= b_elt
->next
;
1117 gcc_checking_assert (!a
->current
== !a
->first
1118 && (!a
->current
|| a
->indx
== a
->current
->indx
));
1119 return changed
!= 0;
1122 /* Set COUNT bits from START in HEAD. */
1124 bitmap_set_range (bitmap head
, unsigned int start
, unsigned int count
)
1126 unsigned int first_index
, end_bit_plus1
, last_index
;
1127 bitmap_element
*elt
, *elt_prev
;
1135 bitmap_set_bit (head
, start
);
1139 first_index
= start
/ BITMAP_ELEMENT_ALL_BITS
;
1140 end_bit_plus1
= start
+ count
;
1141 last_index
= (end_bit_plus1
- 1) / BITMAP_ELEMENT_ALL_BITS
;
1142 elt
= bitmap_find_bit (head
, start
);
1144 /* If bitmap_find_bit returns zero, the current is the closest block
1145 to the result. Otherwise, just use bitmap_element_allocate to
1146 ensure ELT is set; in the loop below, ELT == NULL means "insert
1147 at the end of the bitmap". */
1150 elt
= bitmap_element_allocate (head
);
1151 elt
->indx
= first_index
;
1152 bitmap_element_link (head
, elt
);
1155 gcc_checking_assert (elt
->indx
== first_index
);
1156 elt_prev
= elt
->prev
;
1157 for (i
= first_index
; i
<= last_index
; i
++)
1159 unsigned elt_start_bit
= i
* BITMAP_ELEMENT_ALL_BITS
;
1160 unsigned elt_end_bit_plus1
= elt_start_bit
+ BITMAP_ELEMENT_ALL_BITS
;
1162 unsigned int first_word_to_mod
;
1163 BITMAP_WORD first_mask
;
1164 unsigned int last_word_to_mod
;
1165 BITMAP_WORD last_mask
;
1168 if (!elt
|| elt
->indx
!= i
)
1169 elt
= bitmap_elt_insert_after (head
, elt_prev
, i
);
1171 if (elt_start_bit
<= start
)
1173 /* The first bit to turn on is somewhere inside this
1175 first_word_to_mod
= (start
- elt_start_bit
) / BITMAP_WORD_BITS
;
1177 /* This mask should have 1s in all bits >= start position. */
1179 (((BITMAP_WORD
) 1) << ((start
% BITMAP_WORD_BITS
))) - 1;
1180 first_mask
= ~first_mask
;
1184 /* The first bit to turn on is below this start of this elt. */
1185 first_word_to_mod
= 0;
1186 first_mask
= ~(BITMAP_WORD
) 0;
1189 if (elt_end_bit_plus1
<= end_bit_plus1
)
1191 /* The last bit to turn on is beyond this elt. */
1192 last_word_to_mod
= BITMAP_ELEMENT_WORDS
- 1;
1193 last_mask
= ~(BITMAP_WORD
) 0;
1197 /* The last bit to turn on is inside to this elt. */
1199 (end_bit_plus1
- elt_start_bit
) / BITMAP_WORD_BITS
;
1201 /* The last mask should have 1s below the end bit. */
1203 (((BITMAP_WORD
) 1) << ((end_bit_plus1
% BITMAP_WORD_BITS
))) - 1;
1206 if (first_word_to_mod
== last_word_to_mod
)
1208 BITMAP_WORD mask
= first_mask
& last_mask
;
1209 elt
->bits
[first_word_to_mod
] |= mask
;
1213 elt
->bits
[first_word_to_mod
] |= first_mask
;
1214 if (BITMAP_ELEMENT_WORDS
> 2)
1215 for (ix
= first_word_to_mod
+ 1; ix
< last_word_to_mod
; ix
++)
1216 elt
->bits
[ix
] = ~(BITMAP_WORD
) 0;
1217 elt
->bits
[last_word_to_mod
] |= last_mask
;
1224 head
->current
= elt
? elt
: elt_prev
;
1225 head
->indx
= head
->current
->indx
;
1228 /* Clear COUNT bits from START in HEAD. */
1230 bitmap_clear_range (bitmap head
, unsigned int start
, unsigned int count
)
1232 unsigned int first_index
, end_bit_plus1
, last_index
;
1233 bitmap_element
*elt
;
1240 bitmap_clear_bit (head
, start
);
1244 first_index
= start
/ BITMAP_ELEMENT_ALL_BITS
;
1245 end_bit_plus1
= start
+ count
;
1246 last_index
= (end_bit_plus1
- 1) / BITMAP_ELEMENT_ALL_BITS
;
1247 elt
= bitmap_find_bit (head
, start
);
1249 /* If bitmap_find_bit returns zero, the current is the closest block
1250 to the result. If the current is less than first index, find the
1251 next one. Otherwise, just set elt to be current. */
1256 if (head
->indx
< first_index
)
1258 elt
= head
->current
->next
;
1263 elt
= head
->current
;
1269 while (elt
&& (elt
->indx
<= last_index
))
1271 bitmap_element
* next_elt
= elt
->next
;
1272 unsigned elt_start_bit
= (elt
->indx
) * BITMAP_ELEMENT_ALL_BITS
;
1273 unsigned elt_end_bit_plus1
= elt_start_bit
+ BITMAP_ELEMENT_ALL_BITS
;
1276 if (elt_start_bit
>= start
&& elt_end_bit_plus1
<= end_bit_plus1
)
1277 /* Get rid of the entire elt and go to the next one. */
1278 bitmap_element_free (head
, elt
);
1281 /* Going to have to knock out some bits in this elt. */
1282 unsigned int first_word_to_mod
;
1283 BITMAP_WORD first_mask
;
1284 unsigned int last_word_to_mod
;
1285 BITMAP_WORD last_mask
;
1289 if (elt_start_bit
<= start
)
1291 /* The first bit to turn off is somewhere inside this
1293 first_word_to_mod
= (start
- elt_start_bit
) / BITMAP_WORD_BITS
;
1295 /* This mask should have 1s in all bits >= start position. */
1297 (((BITMAP_WORD
) 1) << ((start
% BITMAP_WORD_BITS
))) - 1;
1298 first_mask
= ~first_mask
;
1302 /* The first bit to turn off is below this start of this elt. */
1303 first_word_to_mod
= 0;
1305 first_mask
= ~first_mask
;
1308 if (elt_end_bit_plus1
<= end_bit_plus1
)
1310 /* The last bit to turn off is beyond this elt. */
1311 last_word_to_mod
= BITMAP_ELEMENT_WORDS
- 1;
1313 last_mask
= ~last_mask
;
1317 /* The last bit to turn off is inside to this elt. */
1319 (end_bit_plus1
- elt_start_bit
) / BITMAP_WORD_BITS
;
1321 /* The last mask should have 1s below the end bit. */
1323 (((BITMAP_WORD
) 1) << (((end_bit_plus1
) % BITMAP_WORD_BITS
))) - 1;
1327 if (first_word_to_mod
== last_word_to_mod
)
1329 BITMAP_WORD mask
= first_mask
& last_mask
;
1330 elt
->bits
[first_word_to_mod
] &= ~mask
;
1334 elt
->bits
[first_word_to_mod
] &= ~first_mask
;
1335 if (BITMAP_ELEMENT_WORDS
> 2)
1336 for (i
= first_word_to_mod
+ 1; i
< last_word_to_mod
; i
++)
1338 elt
->bits
[last_word_to_mod
] &= ~last_mask
;
1340 for (i
= 0; i
< BITMAP_ELEMENT_WORDS
; i
++)
1346 /* Check to see if there are any bits left. */
1348 bitmap_element_free (head
, elt
);
1355 head
->current
= elt
;
1356 head
->indx
= head
->current
->indx
;
1363 bitmap_compl_and_into (bitmap a
, const_bitmap b
)
1365 bitmap_element
*a_elt
= a
->first
;
1366 const bitmap_element
*b_elt
= b
->first
;
1367 bitmap_element
*a_prev
= NULL
;
1368 bitmap_element
*next
;
1370 gcc_assert (a
!= b
);
1372 if (bitmap_empty_p (a
))
1377 if (bitmap_empty_p (b
))
1383 while (a_elt
|| b_elt
)
1385 if (!b_elt
|| (a_elt
&& a_elt
->indx
< b_elt
->indx
))
1387 /* A is before B. Remove A */
1389 a_prev
= a_elt
->prev
;
1390 bitmap_element_free (a
, a_elt
);
1393 else if (!a_elt
|| b_elt
->indx
< a_elt
->indx
)
1395 /* B is before A. Copy B. */
1396 next
= bitmap_elt_insert_after (a
, a_prev
, b_elt
->indx
);
1397 memcpy (next
->bits
, b_elt
->bits
, sizeof (next
->bits
));
1399 b_elt
= b_elt
->next
;
1403 /* Matching elts, generate A = ~A & B. */
1405 BITMAP_WORD ior
= 0;
1407 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1409 BITMAP_WORD cleared
= a_elt
->bits
[ix
] & b_elt
->bits
[ix
];
1410 BITMAP_WORD r
= b_elt
->bits
[ix
] ^ cleared
;
1412 a_elt
->bits
[ix
] = r
;
1417 bitmap_element_free (a
, a_elt
);
1421 b_elt
= b_elt
->next
;
1424 gcc_checking_assert (!a
->current
== !a
->first
1425 && (!a
->current
|| a
->indx
== a
->current
->indx
));
1430 /* Insert an element corresponding to A_ELT | B_ELT after DST_PREV,
1431 overwriting DST_ELT if non-NULL. CHANGED is true if the destination bitmap
1432 had already been changed; the new value of CHANGED is returned. */
1435 bitmap_elt_ior (bitmap dst
, bitmap_element
*dst_elt
, bitmap_element
*dst_prev
,
1436 const bitmap_element
*a_elt
, const bitmap_element
*b_elt
,
1439 gcc_assert (a_elt
|| b_elt
);
1441 if (a_elt
&& b_elt
&& a_elt
->indx
== b_elt
->indx
)
1443 /* Matching elts, generate A | B. */
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
];
1451 if (r
!= dst_elt
->bits
[ix
])
1453 dst_elt
->bits
[ix
] = r
;
1462 dst_elt
= bitmap_elt_insert_after (dst
, dst_prev
, a_elt
->indx
);
1464 dst_elt
->indx
= a_elt
->indx
;
1465 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1467 BITMAP_WORD r
= a_elt
->bits
[ix
] | b_elt
->bits
[ix
];
1468 dst_elt
->bits
[ix
] = r
;
1474 /* Copy a single element. */
1475 const bitmap_element
*src
;
1477 if (!b_elt
|| (a_elt
&& a_elt
->indx
< b_elt
->indx
))
1482 gcc_checking_assert (src
);
1483 changed
= bitmap_elt_copy (dst
, dst_elt
, dst_prev
, src
, changed
);
1489 /* DST = A | B. Return true if DST changes. */
1492 bitmap_ior (bitmap dst
, const_bitmap a
, const_bitmap b
)
1494 bitmap_element
*dst_elt
= dst
->first
;
1495 const bitmap_element
*a_elt
= a
->first
;
1496 const bitmap_element
*b_elt
= b
->first
;
1497 bitmap_element
*dst_prev
= NULL
;
1498 bitmap_element
**dst_prev_pnext
= &dst
->first
;
1499 bool changed
= false;
1501 gcc_assert (dst
!= a
&& dst
!= b
);
1503 while (a_elt
|| b_elt
)
1505 changed
= bitmap_elt_ior (dst
, dst_elt
, dst_prev
, a_elt
, b_elt
, changed
);
1507 if (a_elt
&& b_elt
&& a_elt
->indx
== b_elt
->indx
)
1509 a_elt
= a_elt
->next
;
1510 b_elt
= b_elt
->next
;
1514 if (a_elt
&& (!b_elt
|| a_elt
->indx
<= b_elt
->indx
))
1515 a_elt
= a_elt
->next
;
1516 else if (b_elt
&& (!a_elt
|| b_elt
->indx
<= a_elt
->indx
))
1517 b_elt
= b_elt
->next
;
1520 dst_prev
= *dst_prev_pnext
;
1521 dst_prev_pnext
= &dst_prev
->next
;
1522 dst_elt
= *dst_prev_pnext
;
1528 /* Ensure that dst->current is valid. */
1529 dst
->current
= dst
->first
;
1530 bitmap_elt_clear_from (dst
, dst_elt
);
1532 gcc_checking_assert (!dst
->current
== !dst
->first
);
1534 dst
->indx
= dst
->current
->indx
;
1538 /* A |= B. Return true if A changes. */
1541 bitmap_ior_into (bitmap a
, const_bitmap b
)
1543 bitmap_element
*a_elt
= a
->first
;
1544 const bitmap_element
*b_elt
= b
->first
;
1545 bitmap_element
*a_prev
= NULL
;
1546 bitmap_element
**a_prev_pnext
= &a
->first
;
1547 bool changed
= false;
1554 /* If A lags behind B, just advance it. */
1555 if (!a_elt
|| a_elt
->indx
== b_elt
->indx
)
1557 changed
= bitmap_elt_ior (a
, a_elt
, a_prev
, a_elt
, b_elt
, changed
);
1558 b_elt
= b_elt
->next
;
1560 else if (a_elt
->indx
> b_elt
->indx
)
1562 changed
= bitmap_elt_copy (a
, NULL
, a_prev
, b_elt
, changed
);
1563 b_elt
= b_elt
->next
;
1566 a_prev
= *a_prev_pnext
;
1567 a_prev_pnext
= &a_prev
->next
;
1568 a_elt
= *a_prev_pnext
;
1571 gcc_checking_assert (!a
->current
== !a
->first
);
1573 a
->indx
= a
->current
->indx
;
1580 bitmap_xor (bitmap dst
, const_bitmap a
, const_bitmap b
)
1582 bitmap_element
*dst_elt
= dst
->first
;
1583 const bitmap_element
*a_elt
= a
->first
;
1584 const bitmap_element
*b_elt
= b
->first
;
1585 bitmap_element
*dst_prev
= NULL
;
1587 gcc_assert (dst
!= a
&& dst
!= b
);
1594 while (a_elt
|| b_elt
)
1596 if (a_elt
&& b_elt
&& a_elt
->indx
== b_elt
->indx
)
1598 /* Matching elts, generate A ^ B. */
1600 BITMAP_WORD ior
= 0;
1603 dst_elt
= bitmap_elt_insert_after (dst
, dst_prev
, a_elt
->indx
);
1605 dst_elt
->indx
= a_elt
->indx
;
1606 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1608 BITMAP_WORD r
= a_elt
->bits
[ix
] ^ b_elt
->bits
[ix
];
1611 dst_elt
->bits
[ix
] = r
;
1613 a_elt
= a_elt
->next
;
1614 b_elt
= b_elt
->next
;
1618 dst_elt
= dst_elt
->next
;
1623 /* Copy a single element. */
1624 const bitmap_element
*src
;
1626 if (!b_elt
|| (a_elt
&& a_elt
->indx
< b_elt
->indx
))
1629 a_elt
= a_elt
->next
;
1634 b_elt
= b_elt
->next
;
1638 dst_elt
= bitmap_elt_insert_after (dst
, dst_prev
, src
->indx
);
1640 dst_elt
->indx
= src
->indx
;
1641 memcpy (dst_elt
->bits
, src
->bits
, sizeof (dst_elt
->bits
));
1643 dst_elt
= dst_elt
->next
;
1646 /* Ensure that dst->current is valid. */
1647 dst
->current
= dst
->first
;
1648 bitmap_elt_clear_from (dst
, dst_elt
);
1649 gcc_checking_assert (!dst
->current
== !dst
->first
);
1651 dst
->indx
= dst
->current
->indx
;
1657 bitmap_xor_into (bitmap a
, const_bitmap b
)
1659 bitmap_element
*a_elt
= a
->first
;
1660 const bitmap_element
*b_elt
= b
->first
;
1661 bitmap_element
*a_prev
= NULL
;
1671 if (!a_elt
|| b_elt
->indx
< a_elt
->indx
)
1674 bitmap_element
*dst
= bitmap_elt_insert_after (a
, a_prev
, b_elt
->indx
);
1675 memcpy (dst
->bits
, b_elt
->bits
, sizeof (dst
->bits
));
1677 b_elt
= b_elt
->next
;
1679 else if (a_elt
->indx
< b_elt
->indx
)
1682 a_elt
= a_elt
->next
;
1686 /* Matching elts, generate A ^= B. */
1688 BITMAP_WORD ior
= 0;
1689 bitmap_element
*next
= a_elt
->next
;
1691 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1693 BITMAP_WORD r
= a_elt
->bits
[ix
] ^ b_elt
->bits
[ix
];
1696 a_elt
->bits
[ix
] = r
;
1698 b_elt
= b_elt
->next
;
1702 bitmap_element_free (a
, a_elt
);
1706 gcc_checking_assert (!a
->current
== !a
->first
);
1708 a
->indx
= a
->current
->indx
;
1711 /* Return true if two bitmaps are identical.
1712 We do not bother with a check for pointer equality, as that never
1713 occurs in practice. */
1716 bitmap_equal_p (const_bitmap a
, const_bitmap b
)
1718 const bitmap_element
*a_elt
;
1719 const bitmap_element
*b_elt
;
1722 for (a_elt
= a
->first
, b_elt
= b
->first
;
1724 a_elt
= a_elt
->next
, b_elt
= b_elt
->next
)
1726 if (a_elt
->indx
!= b_elt
->indx
)
1728 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1729 if (a_elt
->bits
[ix
] != b_elt
->bits
[ix
])
1732 return !a_elt
&& !b_elt
;
1735 /* Return true if A AND B is not empty. */
1738 bitmap_intersect_p (const_bitmap a
, const_bitmap b
)
1740 const bitmap_element
*a_elt
;
1741 const bitmap_element
*b_elt
;
1744 for (a_elt
= a
->first
, b_elt
= b
->first
;
1747 if (a_elt
->indx
< b_elt
->indx
)
1748 a_elt
= a_elt
->next
;
1749 else if (b_elt
->indx
< a_elt
->indx
)
1750 b_elt
= b_elt
->next
;
1753 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1754 if (a_elt
->bits
[ix
] & b_elt
->bits
[ix
])
1756 a_elt
= a_elt
->next
;
1757 b_elt
= b_elt
->next
;
1763 /* Return true if A AND NOT B is not empty. */
1766 bitmap_intersect_compl_p (const_bitmap a
, const_bitmap b
)
1768 const bitmap_element
*a_elt
;
1769 const bitmap_element
*b_elt
;
1771 for (a_elt
= a
->first
, b_elt
= b
->first
;
1774 if (a_elt
->indx
< b_elt
->indx
)
1776 else if (b_elt
->indx
< a_elt
->indx
)
1777 b_elt
= b_elt
->next
;
1780 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1781 if (a_elt
->bits
[ix
] & ~b_elt
->bits
[ix
])
1783 a_elt
= a_elt
->next
;
1784 b_elt
= b_elt
->next
;
1787 return a_elt
!= NULL
;
1791 /* DST = A | (FROM1 & ~FROM2). Return true if DST changes. */
1794 bitmap_ior_and_compl (bitmap dst
, const_bitmap a
, const_bitmap b
, const_bitmap kill
)
1796 bool changed
= false;
1798 bitmap_element
*dst_elt
= dst
->first
;
1799 const bitmap_element
*a_elt
= a
->first
;
1800 const bitmap_element
*b_elt
= b
->first
;
1801 const bitmap_element
*kill_elt
= kill
->first
;
1802 bitmap_element
*dst_prev
= NULL
;
1803 bitmap_element
**dst_prev_pnext
= &dst
->first
;
1805 gcc_assert (dst
!= a
&& dst
!= b
&& dst
!= kill
);
1807 /* Special cases. We don't bother checking for bitmap_equal_p (b, kill). */
1808 if (b
== kill
|| bitmap_empty_p (b
))
1810 changed
= !bitmap_equal_p (dst
, a
);
1812 bitmap_copy (dst
, a
);
1815 if (bitmap_empty_p (kill
))
1816 return bitmap_ior (dst
, a
, b
);
1817 if (bitmap_empty_p (a
))
1818 return bitmap_and_compl (dst
, b
, kill
);
1820 while (a_elt
|| b_elt
)
1822 bool new_element
= false;
1825 while (kill_elt
&& kill_elt
->indx
< b_elt
->indx
)
1826 kill_elt
= kill_elt
->next
;
1828 if (b_elt
&& kill_elt
&& kill_elt
->indx
== b_elt
->indx
1829 && (!a_elt
|| a_elt
->indx
>= b_elt
->indx
))
1831 bitmap_element tmp_elt
;
1834 BITMAP_WORD ior
= 0;
1835 tmp_elt
.indx
= b_elt
->indx
;
1836 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1838 BITMAP_WORD r
= b_elt
->bits
[ix
] & ~kill_elt
->bits
[ix
];
1840 tmp_elt
.bits
[ix
] = r
;
1845 changed
= bitmap_elt_ior (dst
, dst_elt
, dst_prev
,
1846 a_elt
, &tmp_elt
, changed
);
1848 if (a_elt
&& a_elt
->indx
== b_elt
->indx
)
1849 a_elt
= a_elt
->next
;
1852 b_elt
= b_elt
->next
;
1853 kill_elt
= kill_elt
->next
;
1857 changed
= bitmap_elt_ior (dst
, dst_elt
, dst_prev
,
1858 a_elt
, b_elt
, changed
);
1861 if (a_elt
&& b_elt
&& a_elt
->indx
== b_elt
->indx
)
1863 a_elt
= a_elt
->next
;
1864 b_elt
= b_elt
->next
;
1868 if (a_elt
&& (!b_elt
|| a_elt
->indx
<= b_elt
->indx
))
1869 a_elt
= a_elt
->next
;
1870 else if (b_elt
&& (!a_elt
|| b_elt
->indx
<= a_elt
->indx
))
1871 b_elt
= b_elt
->next
;
1877 dst_prev
= *dst_prev_pnext
;
1878 dst_prev_pnext
= &dst_prev
->next
;
1879 dst_elt
= *dst_prev_pnext
;
1886 /* Ensure that dst->current is valid. */
1887 dst
->current
= dst
->first
;
1888 bitmap_elt_clear_from (dst
, dst_elt
);
1890 gcc_checking_assert (!dst
->current
== !dst
->first
);
1892 dst
->indx
= dst
->current
->indx
;
1897 /* A |= (FROM1 & ~FROM2). Return true if A changes. */
1900 bitmap_ior_and_compl_into (bitmap a
, const_bitmap from1
, const_bitmap from2
)
1905 bitmap_initialize (&tmp
, &bitmap_default_obstack
);
1906 bitmap_and_compl (&tmp
, from1
, from2
);
1907 changed
= bitmap_ior_into (a
, &tmp
);
1908 bitmap_clear (&tmp
);
1913 /* A |= (B & C). Return true if A changes. */
1916 bitmap_ior_and_into (bitmap a
, const_bitmap b
, const_bitmap c
)
1918 bitmap_element
*a_elt
= a
->first
;
1919 const bitmap_element
*b_elt
= b
->first
;
1920 const bitmap_element
*c_elt
= c
->first
;
1921 bitmap_element and_elt
;
1922 bitmap_element
*a_prev
= NULL
;
1923 bitmap_element
**a_prev_pnext
= &a
->first
;
1924 bool changed
= false;
1928 return bitmap_ior_into (a
, b
);
1929 if (bitmap_empty_p (b
) || bitmap_empty_p (c
))
1933 while (b_elt
&& c_elt
)
1935 BITMAP_WORD overall
;
1937 /* Find a common item of B and C. */
1938 while (b_elt
->indx
!= c_elt
->indx
)
1940 if (b_elt
->indx
< c_elt
->indx
)
1942 b_elt
= b_elt
->next
;
1948 c_elt
= c_elt
->next
;
1955 and_elt
.indx
= b_elt
->indx
;
1956 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1958 and_elt
.bits
[ix
] = b_elt
->bits
[ix
] & c_elt
->bits
[ix
];
1959 overall
|= and_elt
.bits
[ix
];
1962 b_elt
= b_elt
->next
;
1963 c_elt
= c_elt
->next
;
1967 /* Now find a place to insert AND_ELT. */
1970 ix
= a_elt
? a_elt
->indx
: and_elt
.indx
;
1971 if (ix
== and_elt
.indx
)
1972 changed
= bitmap_elt_ior (a
, a_elt
, a_prev
, a_elt
, &and_elt
, changed
);
1973 else if (ix
> and_elt
.indx
)
1974 changed
= bitmap_elt_copy (a
, NULL
, a_prev
, &and_elt
, changed
);
1976 a_prev
= *a_prev_pnext
;
1977 a_prev_pnext
= &a_prev
->next
;
1978 a_elt
= *a_prev_pnext
;
1980 /* If A lagged behind B/C, we advanced it so loop once more. */
1982 while (ix
< and_elt
.indx
);
1986 gcc_checking_assert (!a
->current
== !a
->first
);
1988 a
->indx
= a
->current
->indx
;
1992 /* Compute hash of bitmap (for purposes of hashing). */
1994 bitmap_hash (const_bitmap head
)
1996 const bitmap_element
*ptr
;
1997 BITMAP_WORD hash
= 0;
2000 for (ptr
= head
->first
; ptr
; ptr
= ptr
->next
)
2003 for (ix
= 0; ix
!= BITMAP_ELEMENT_WORDS
; ix
++)
2004 hash
^= ptr
->bits
[ix
];
2006 return (hashval_t
)hash
;
2010 /* Debugging function to print out the contents of a bitmap. */
2013 debug_bitmap_file (FILE *file
, const_bitmap head
)
2015 const bitmap_element
*ptr
;
2017 fprintf (file
, "\nfirst = " HOST_PTR_PRINTF
2018 " current = " HOST_PTR_PRINTF
" indx = %u\n",
2019 (void *) head
->first
, (void *) head
->current
, head
->indx
);
2021 for (ptr
= head
->first
; ptr
; ptr
= ptr
->next
)
2023 unsigned int i
, j
, col
= 26;
2025 fprintf (file
, "\t" HOST_PTR_PRINTF
" next = " HOST_PTR_PRINTF
2026 " prev = " HOST_PTR_PRINTF
" indx = %u\n\t\tbits = {",
2027 (const void*) ptr
, (const void*) ptr
->next
,
2028 (const void*) ptr
->prev
, ptr
->indx
);
2030 for (i
= 0; i
< BITMAP_ELEMENT_WORDS
; i
++)
2031 for (j
= 0; j
< BITMAP_WORD_BITS
; j
++)
2032 if ((ptr
->bits
[i
] >> j
) & 1)
2036 fprintf (file
, "\n\t\t\t");
2040 fprintf (file
, " %u", (ptr
->indx
* BITMAP_ELEMENT_ALL_BITS
2041 + i
* BITMAP_WORD_BITS
+ j
));
2045 fprintf (file
, " }\n");
2049 /* Function to be called from the debugger to print the contents
2053 debug_bitmap (const_bitmap head
)
2055 debug_bitmap_file (stderr
, head
);
2058 /* Function to print out the contents of a bitmap. Unlike debug_bitmap_file,
2059 it does not print anything but the bits. */
2062 bitmap_print (FILE *file
, const_bitmap head
, const char *prefix
,
2065 const char *comma
= "";
2069 fputs (prefix
, file
);
2070 EXECUTE_IF_SET_IN_BITMAP (head
, 0, i
, bi
)
2072 fprintf (file
, "%s%d", comma
, i
);
2075 fputs (suffix
, file
);
2078 /* Output per-bitmap memory usage statistics. */
2080 dump_bitmap_statistics (void)
2082 if (! GATHER_STATISTICS
)
2085 bitmap_mem_desc
.dump (BITMAP
);
2089 debug (const bitmap_head
&ref
)
2091 dump_bitmap (stderr
, &ref
);
2095 debug (const bitmap_head
*ptr
)
2100 fprintf (stderr
, "<nil>\n");
2104 #include "gt-bitmap.h"