1 /* Functions to support general ended bitmaps.
2 Copyright (C) 1997-2016 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
22 #include "coretypes.h"
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
, size_t 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 /* Move a bitmap to another bitmap. */
475 bitmap_move (bitmap to
, bitmap from
)
477 gcc_assert (to
->obstack
== from
->obstack
);
483 if (GATHER_STATISTICS
)
486 for (bitmap_element
*e
= to
->first
; e
; e
= e
->next
)
487 sz
+= sizeof (bitmap_element
);
488 register_overhead (to
, sz
);
489 register_overhead (from
, -sz
);
493 /* Find a bitmap element that would hold a bitmap's bit.
494 Update the `current' field even if we can't find an element that
495 would hold the bitmap's bit to make eventual allocation
498 static inline bitmap_element
*
499 bitmap_find_bit (bitmap head
, unsigned int bit
)
501 bitmap_element
*element
;
502 unsigned int indx
= bit
/ BITMAP_ELEMENT_ALL_BITS
;
504 if (head
->current
== NULL
505 || head
->indx
== indx
)
506 return head
->current
;
507 if (head
->current
== head
->first
508 && head
->first
->next
== NULL
)
511 /* Usage can be NULL due to allocated bitmaps for which we do not
512 call initialize function. */
513 bitmap_usage
*usage
= NULL
;
514 if (GATHER_STATISTICS
)
515 usage
= bitmap_mem_desc
.get_descriptor_for_instance (head
);
517 /* This bitmap has more than one element, and we're going to look
518 through the elements list. Count that as a search. */
519 if (GATHER_STATISTICS
&& usage
)
520 usage
->m_nsearches
++;
522 if (head
->indx
< indx
)
523 /* INDX is beyond head->indx. Search from head->current
525 for (element
= head
->current
;
526 element
->next
!= 0 && element
->indx
< indx
;
527 element
= element
->next
)
529 if (GATHER_STATISTICS
&& usage
)
530 usage
->m_search_iter
++;
533 else if (head
->indx
/ 2 < indx
)
534 /* INDX is less than head->indx and closer to head->indx than to
535 0. Search from head->current backward. */
536 for (element
= head
->current
;
537 element
->prev
!= 0 && element
->indx
> indx
;
538 element
= element
->prev
)
540 if (GATHER_STATISTICS
&& usage
)
541 usage
->m_search_iter
++;
545 /* INDX is less than head->indx and closer to 0 than to
546 head->indx. Search from head->first forward. */
547 for (element
= head
->first
;
548 element
->next
!= 0 && element
->indx
< indx
;
549 element
= element
->next
)
550 if (GATHER_STATISTICS
&& usage
)
552 usage
->m_search_iter
++;
555 /* `element' is the nearest to the one we want. If it's not the one we
556 want, the one we want doesn't exist. */
557 head
->current
= element
;
558 head
->indx
= element
->indx
;
559 if (element
!= 0 && element
->indx
!= indx
)
565 /* Clear a single bit in a bitmap. Return true if the bit changed. */
568 bitmap_clear_bit (bitmap head
, int bit
)
570 bitmap_element
*const ptr
= bitmap_find_bit (head
, bit
);
574 unsigned bit_num
= bit
% BITMAP_WORD_BITS
;
575 unsigned word_num
= bit
/ BITMAP_WORD_BITS
% BITMAP_ELEMENT_WORDS
;
576 BITMAP_WORD bit_val
= ((BITMAP_WORD
) 1) << bit_num
;
577 bool res
= (ptr
->bits
[word_num
] & bit_val
) != 0;
580 ptr
->bits
[word_num
] &= ~bit_val
;
581 /* If we cleared the entire word, free up the element. */
582 if (!ptr
->bits
[word_num
]
583 && bitmap_element_zerop (ptr
))
584 bitmap_element_free (head
, ptr
);
593 /* Set a single bit in a bitmap. Return true if the bit changed. */
596 bitmap_set_bit (bitmap head
, int bit
)
598 bitmap_element
*ptr
= bitmap_find_bit (head
, bit
);
599 unsigned word_num
= bit
/ BITMAP_WORD_BITS
% BITMAP_ELEMENT_WORDS
;
600 unsigned bit_num
= bit
% BITMAP_WORD_BITS
;
601 BITMAP_WORD bit_val
= ((BITMAP_WORD
) 1) << bit_num
;
605 ptr
= bitmap_element_allocate (head
);
606 ptr
->indx
= bit
/ BITMAP_ELEMENT_ALL_BITS
;
607 ptr
->bits
[word_num
] = bit_val
;
608 bitmap_element_link (head
, ptr
);
613 bool res
= (ptr
->bits
[word_num
] & bit_val
) == 0;
615 ptr
->bits
[word_num
] |= bit_val
;
620 /* Return whether a bit is set within a bitmap. */
623 bitmap_bit_p (bitmap head
, int bit
)
629 ptr
= bitmap_find_bit (head
, bit
);
633 bit_num
= bit
% BITMAP_WORD_BITS
;
634 word_num
= bit
/ BITMAP_WORD_BITS
% BITMAP_ELEMENT_WORDS
;
636 return (ptr
->bits
[word_num
] >> bit_num
) & 1;
639 #if GCC_VERSION < 3400
640 /* Table of number of set bits in a character, indexed by value of char. */
641 static const unsigned char popcount_table
[] =
643 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,
644 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,
645 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
646 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,
647 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,
648 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,
649 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
650 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,
654 bitmap_popcount (BITMAP_WORD a
)
656 unsigned long ret
= 0;
659 /* Just do this the table way for now */
660 for (i
= 0; i
< BITMAP_WORD_BITS
; i
+= 8)
661 ret
+= popcount_table
[(a
>> i
) & 0xff];
665 /* Count the number of bits set in the bitmap, and return it. */
668 bitmap_count_bits (const_bitmap a
)
670 unsigned long count
= 0;
671 const bitmap_element
*elt
;
674 for (elt
= a
->first
; elt
; elt
= elt
->next
)
676 for (ix
= 0; ix
!= BITMAP_ELEMENT_WORDS
; ix
++)
678 #if GCC_VERSION >= 3400
679 /* Note that popcountl matches BITMAP_WORD in type, so the actual size
680 of BITMAP_WORD is not material. */
681 count
+= __builtin_popcountl (elt
->bits
[ix
]);
683 count
+= bitmap_popcount (elt
->bits
[ix
]);
690 /* Return true if the bitmap has a single bit set. Otherwise return
694 bitmap_single_bit_set_p (const_bitmap a
)
696 unsigned long count
= 0;
697 const bitmap_element
*elt
;
700 if (bitmap_empty_p (a
))
704 /* As there are no completely empty bitmap elements, a second one
705 means we have more than one bit set. */
706 if (elt
->next
!= NULL
)
709 for (ix
= 0; ix
!= BITMAP_ELEMENT_WORDS
; ix
++)
711 #if GCC_VERSION >= 3400
712 /* Note that popcountl matches BITMAP_WORD in type, so the actual size
713 of BITMAP_WORD is not material. */
714 count
+= __builtin_popcountl (elt
->bits
[ix
]);
716 count
+= bitmap_popcount (elt
->bits
[ix
]);
726 /* Return the bit number of the first set bit in the bitmap. The
727 bitmap must be non-empty. */
730 bitmap_first_set_bit (const_bitmap a
)
732 const bitmap_element
*elt
= a
->first
;
737 gcc_checking_assert (elt
);
738 bit_no
= elt
->indx
* BITMAP_ELEMENT_ALL_BITS
;
739 for (ix
= 0; ix
!= BITMAP_ELEMENT_WORDS
; ix
++)
741 word
= elt
->bits
[ix
];
747 bit_no
+= ix
* BITMAP_WORD_BITS
;
749 #if GCC_VERSION >= 3004
750 gcc_assert (sizeof (long) == sizeof (word
));
751 bit_no
+= __builtin_ctzl (word
);
753 /* Binary search for the first set bit. */
754 #if BITMAP_WORD_BITS > 64
755 #error "Fill out the table."
757 #if BITMAP_WORD_BITS > 32
758 if (!(word
& 0xffffffff))
759 word
>>= 32, bit_no
+= 32;
761 if (!(word
& 0xffff))
762 word
>>= 16, bit_no
+= 16;
764 word
>>= 8, bit_no
+= 8;
766 word
>>= 4, bit_no
+= 4;
768 word
>>= 2, bit_no
+= 2;
770 word
>>= 1, bit_no
+= 1;
772 gcc_checking_assert (word
& 1);
777 /* Return the bit number of the first set bit in the bitmap. The
778 bitmap must be non-empty. */
781 bitmap_last_set_bit (const_bitmap a
)
783 const bitmap_element
*elt
= a
->current
? a
->current
: a
->first
;
788 gcc_checking_assert (elt
);
791 bit_no
= elt
->indx
* BITMAP_ELEMENT_ALL_BITS
;
792 for (ix
= BITMAP_ELEMENT_WORDS
- 1; ix
>= 0; ix
--)
794 word
= elt
->bits
[ix
];
800 bit_no
+= ix
* BITMAP_WORD_BITS
;
801 #if GCC_VERSION >= 3004
802 gcc_assert (sizeof (long) == sizeof (word
));
803 bit_no
+= BITMAP_WORD_BITS
- __builtin_clzl (word
) - 1;
805 /* Hopefully this is a twos-complement host... */
806 BITMAP_WORD x
= word
;
812 #if BITMAP_WORD_BITS > 32
815 bit_no
+= bitmap_popcount (x
) - 1;
825 bitmap_and (bitmap dst
, const_bitmap a
, const_bitmap b
)
827 bitmap_element
*dst_elt
= dst
->first
;
828 const bitmap_element
*a_elt
= a
->first
;
829 const bitmap_element
*b_elt
= b
->first
;
830 bitmap_element
*dst_prev
= NULL
;
832 gcc_assert (dst
!= a
&& dst
!= b
);
836 bitmap_copy (dst
, a
);
840 while (a_elt
&& b_elt
)
842 if (a_elt
->indx
< b_elt
->indx
)
844 else if (b_elt
->indx
< a_elt
->indx
)
848 /* Matching elts, generate A & B. */
853 dst_elt
= bitmap_elt_insert_after (dst
, dst_prev
, a_elt
->indx
);
855 dst_elt
->indx
= a_elt
->indx
;
856 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
858 BITMAP_WORD r
= a_elt
->bits
[ix
] & b_elt
->bits
[ix
];
860 dst_elt
->bits
[ix
] = r
;
866 dst_elt
= dst_elt
->next
;
872 /* Ensure that dst->current is valid. */
873 dst
->current
= dst
->first
;
874 bitmap_elt_clear_from (dst
, dst_elt
);
875 gcc_checking_assert (!dst
->current
== !dst
->first
);
877 dst
->indx
= dst
->current
->indx
;
880 /* A &= B. Return true if A changed. */
883 bitmap_and_into (bitmap a
, const_bitmap b
)
885 bitmap_element
*a_elt
= a
->first
;
886 const bitmap_element
*b_elt
= b
->first
;
887 bitmap_element
*next
;
888 bool changed
= false;
893 while (a_elt
&& b_elt
)
895 if (a_elt
->indx
< b_elt
->indx
)
898 bitmap_element_free (a
, a_elt
);
902 else if (b_elt
->indx
< a_elt
->indx
)
906 /* Matching elts, generate A &= B. */
910 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
912 BITMAP_WORD r
= a_elt
->bits
[ix
] & b_elt
->bits
[ix
];
913 if (a_elt
->bits
[ix
] != r
)
920 bitmap_element_free (a
, a_elt
);
929 bitmap_elt_clear_from (a
, a_elt
);
932 gcc_checking_assert (!a
->current
== !a
->first
933 && (!a
->current
|| a
->indx
== a
->current
->indx
));
939 /* Insert an element equal to SRC_ELT after DST_PREV, overwriting DST_ELT
940 if non-NULL. CHANGED is true if the destination bitmap had already been
941 changed; the new value of CHANGED is returned. */
944 bitmap_elt_copy (bitmap dst
, bitmap_element
*dst_elt
, bitmap_element
*dst_prev
,
945 const bitmap_element
*src_elt
, bool changed
)
947 if (!changed
&& dst_elt
&& dst_elt
->indx
== src_elt
->indx
)
951 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
952 if (src_elt
->bits
[ix
] != dst_elt
->bits
[ix
])
954 dst_elt
->bits
[ix
] = src_elt
->bits
[ix
];
962 dst_elt
= bitmap_elt_insert_after (dst
, dst_prev
, src_elt
->indx
);
964 dst_elt
->indx
= src_elt
->indx
;
965 memcpy (dst_elt
->bits
, src_elt
->bits
, sizeof (dst_elt
->bits
));
975 bitmap_and_compl (bitmap dst
, const_bitmap a
, const_bitmap b
)
977 bitmap_element
*dst_elt
= dst
->first
;
978 const bitmap_element
*a_elt
= a
->first
;
979 const bitmap_element
*b_elt
= b
->first
;
980 bitmap_element
*dst_prev
= NULL
;
981 bitmap_element
**dst_prev_pnext
= &dst
->first
;
982 bool changed
= false;
984 gcc_assert (dst
!= a
&& dst
!= b
);
988 changed
= !bitmap_empty_p (dst
);
995 while (b_elt
&& b_elt
->indx
< a_elt
->indx
)
998 if (!b_elt
|| b_elt
->indx
> a_elt
->indx
)
1000 changed
= bitmap_elt_copy (dst
, dst_elt
, dst_prev
, a_elt
, changed
);
1001 dst_prev
= *dst_prev_pnext
;
1002 dst_prev_pnext
= &dst_prev
->next
;
1003 dst_elt
= *dst_prev_pnext
;
1004 a_elt
= a_elt
->next
;
1009 /* Matching elts, generate A & ~B. */
1011 BITMAP_WORD ior
= 0;
1013 if (!changed
&& dst_elt
&& dst_elt
->indx
== a_elt
->indx
)
1015 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1017 BITMAP_WORD r
= a_elt
->bits
[ix
] & ~b_elt
->bits
[ix
];
1019 if (dst_elt
->bits
[ix
] != r
)
1022 dst_elt
->bits
[ix
] = r
;
1030 if (!dst_elt
|| dst_elt
->indx
> a_elt
->indx
)
1032 dst_elt
= bitmap_elt_insert_after (dst
, dst_prev
, a_elt
->indx
);
1037 dst_elt
->indx
= a_elt
->indx
;
1038 new_element
= false;
1041 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1043 BITMAP_WORD r
= a_elt
->bits
[ix
] & ~b_elt
->bits
[ix
];
1045 dst_elt
->bits
[ix
] = r
;
1053 changed
|= !new_element
;
1054 bitmap_element_free (dst
, dst_elt
);
1055 dst_elt
= *dst_prev_pnext
;
1061 dst_prev
= *dst_prev_pnext
;
1062 dst_prev_pnext
= &dst_prev
->next
;
1063 dst_elt
= *dst_prev_pnext
;
1065 a_elt
= a_elt
->next
;
1066 b_elt
= b_elt
->next
;
1070 /* Ensure that dst->current is valid. */
1071 dst
->current
= dst
->first
;
1076 bitmap_elt_clear_from (dst
, dst_elt
);
1078 gcc_checking_assert (!dst
->current
== !dst
->first
);
1080 dst
->indx
= dst
->current
->indx
;
1085 /* A &= ~B. Returns true if A changes */
1088 bitmap_and_compl_into (bitmap a
, const_bitmap b
)
1090 bitmap_element
*a_elt
= a
->first
;
1091 const bitmap_element
*b_elt
= b
->first
;
1092 bitmap_element
*next
;
1093 BITMAP_WORD changed
= 0;
1097 if (bitmap_empty_p (a
))
1106 while (a_elt
&& b_elt
)
1108 if (a_elt
->indx
< b_elt
->indx
)
1109 a_elt
= a_elt
->next
;
1110 else if (b_elt
->indx
< a_elt
->indx
)
1111 b_elt
= b_elt
->next
;
1114 /* Matching elts, generate A &= ~B. */
1116 BITMAP_WORD ior
= 0;
1118 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1120 BITMAP_WORD cleared
= a_elt
->bits
[ix
] & b_elt
->bits
[ix
];
1121 BITMAP_WORD r
= a_elt
->bits
[ix
] ^ cleared
;
1123 a_elt
->bits
[ix
] = r
;
1129 bitmap_element_free (a
, a_elt
);
1131 b_elt
= b_elt
->next
;
1134 gcc_checking_assert (!a
->current
== !a
->first
1135 && (!a
->current
|| a
->indx
== a
->current
->indx
));
1136 return changed
!= 0;
1139 /* Set COUNT bits from START in HEAD. */
1141 bitmap_set_range (bitmap head
, unsigned int start
, unsigned int count
)
1143 unsigned int first_index
, end_bit_plus1
, last_index
;
1144 bitmap_element
*elt
, *elt_prev
;
1152 bitmap_set_bit (head
, start
);
1156 first_index
= start
/ BITMAP_ELEMENT_ALL_BITS
;
1157 end_bit_plus1
= start
+ count
;
1158 last_index
= (end_bit_plus1
- 1) / BITMAP_ELEMENT_ALL_BITS
;
1159 elt
= bitmap_find_bit (head
, start
);
1161 /* If bitmap_find_bit returns zero, the current is the closest block
1162 to the result. Otherwise, just use bitmap_element_allocate to
1163 ensure ELT is set; in the loop below, ELT == NULL means "insert
1164 at the end of the bitmap". */
1167 elt
= bitmap_element_allocate (head
);
1168 elt
->indx
= first_index
;
1169 bitmap_element_link (head
, elt
);
1172 gcc_checking_assert (elt
->indx
== first_index
);
1173 elt_prev
= elt
->prev
;
1174 for (i
= first_index
; i
<= last_index
; i
++)
1176 unsigned elt_start_bit
= i
* BITMAP_ELEMENT_ALL_BITS
;
1177 unsigned elt_end_bit_plus1
= elt_start_bit
+ BITMAP_ELEMENT_ALL_BITS
;
1179 unsigned int first_word_to_mod
;
1180 BITMAP_WORD first_mask
;
1181 unsigned int last_word_to_mod
;
1182 BITMAP_WORD last_mask
;
1185 if (!elt
|| elt
->indx
!= i
)
1186 elt
= bitmap_elt_insert_after (head
, elt_prev
, i
);
1188 if (elt_start_bit
<= start
)
1190 /* The first bit to turn on is somewhere inside this
1192 first_word_to_mod
= (start
- elt_start_bit
) / BITMAP_WORD_BITS
;
1194 /* This mask should have 1s in all bits >= start position. */
1196 (((BITMAP_WORD
) 1) << ((start
% BITMAP_WORD_BITS
))) - 1;
1197 first_mask
= ~first_mask
;
1201 /* The first bit to turn on is below this start of this elt. */
1202 first_word_to_mod
= 0;
1203 first_mask
= ~(BITMAP_WORD
) 0;
1206 if (elt_end_bit_plus1
<= end_bit_plus1
)
1208 /* The last bit to turn on is beyond this elt. */
1209 last_word_to_mod
= BITMAP_ELEMENT_WORDS
- 1;
1210 last_mask
= ~(BITMAP_WORD
) 0;
1214 /* The last bit to turn on is inside to this elt. */
1216 (end_bit_plus1
- elt_start_bit
) / BITMAP_WORD_BITS
;
1218 /* The last mask should have 1s below the end bit. */
1220 (((BITMAP_WORD
) 1) << ((end_bit_plus1
% BITMAP_WORD_BITS
))) - 1;
1223 if (first_word_to_mod
== last_word_to_mod
)
1225 BITMAP_WORD mask
= first_mask
& last_mask
;
1226 elt
->bits
[first_word_to_mod
] |= mask
;
1230 elt
->bits
[first_word_to_mod
] |= first_mask
;
1231 if (BITMAP_ELEMENT_WORDS
> 2)
1232 for (ix
= first_word_to_mod
+ 1; ix
< last_word_to_mod
; ix
++)
1233 elt
->bits
[ix
] = ~(BITMAP_WORD
) 0;
1234 elt
->bits
[last_word_to_mod
] |= last_mask
;
1241 head
->current
= elt
? elt
: elt_prev
;
1242 head
->indx
= head
->current
->indx
;
1245 /* Clear COUNT bits from START in HEAD. */
1247 bitmap_clear_range (bitmap head
, unsigned int start
, unsigned int count
)
1249 unsigned int first_index
, end_bit_plus1
, last_index
;
1250 bitmap_element
*elt
;
1257 bitmap_clear_bit (head
, start
);
1261 first_index
= start
/ BITMAP_ELEMENT_ALL_BITS
;
1262 end_bit_plus1
= start
+ count
;
1263 last_index
= (end_bit_plus1
- 1) / BITMAP_ELEMENT_ALL_BITS
;
1264 elt
= bitmap_find_bit (head
, start
);
1266 /* If bitmap_find_bit returns zero, the current is the closest block
1267 to the result. If the current is less than first index, find the
1268 next one. Otherwise, just set elt to be current. */
1273 if (head
->indx
< first_index
)
1275 elt
= head
->current
->next
;
1280 elt
= head
->current
;
1286 while (elt
&& (elt
->indx
<= last_index
))
1288 bitmap_element
* next_elt
= elt
->next
;
1289 unsigned elt_start_bit
= (elt
->indx
) * BITMAP_ELEMENT_ALL_BITS
;
1290 unsigned elt_end_bit_plus1
= elt_start_bit
+ BITMAP_ELEMENT_ALL_BITS
;
1293 if (elt_start_bit
>= start
&& elt_end_bit_plus1
<= end_bit_plus1
)
1294 /* Get rid of the entire elt and go to the next one. */
1295 bitmap_element_free (head
, elt
);
1298 /* Going to have to knock out some bits in this elt. */
1299 unsigned int first_word_to_mod
;
1300 BITMAP_WORD first_mask
;
1301 unsigned int last_word_to_mod
;
1302 BITMAP_WORD last_mask
;
1306 if (elt_start_bit
<= start
)
1308 /* The first bit to turn off is somewhere inside this
1310 first_word_to_mod
= (start
- elt_start_bit
) / BITMAP_WORD_BITS
;
1312 /* This mask should have 1s in all bits >= start position. */
1314 (((BITMAP_WORD
) 1) << ((start
% BITMAP_WORD_BITS
))) - 1;
1315 first_mask
= ~first_mask
;
1319 /* The first bit to turn off is below this start of this elt. */
1320 first_word_to_mod
= 0;
1322 first_mask
= ~first_mask
;
1325 if (elt_end_bit_plus1
<= end_bit_plus1
)
1327 /* The last bit to turn off is beyond this elt. */
1328 last_word_to_mod
= BITMAP_ELEMENT_WORDS
- 1;
1330 last_mask
= ~last_mask
;
1334 /* The last bit to turn off is inside to this elt. */
1336 (end_bit_plus1
- elt_start_bit
) / BITMAP_WORD_BITS
;
1338 /* The last mask should have 1s below the end bit. */
1340 (((BITMAP_WORD
) 1) << (((end_bit_plus1
) % BITMAP_WORD_BITS
))) - 1;
1344 if (first_word_to_mod
== last_word_to_mod
)
1346 BITMAP_WORD mask
= first_mask
& last_mask
;
1347 elt
->bits
[first_word_to_mod
] &= ~mask
;
1351 elt
->bits
[first_word_to_mod
] &= ~first_mask
;
1352 if (BITMAP_ELEMENT_WORDS
> 2)
1353 for (i
= first_word_to_mod
+ 1; i
< last_word_to_mod
; i
++)
1355 elt
->bits
[last_word_to_mod
] &= ~last_mask
;
1357 for (i
= 0; i
< BITMAP_ELEMENT_WORDS
; i
++)
1363 /* Check to see if there are any bits left. */
1365 bitmap_element_free (head
, elt
);
1372 head
->current
= elt
;
1373 head
->indx
= head
->current
->indx
;
1380 bitmap_compl_and_into (bitmap a
, const_bitmap b
)
1382 bitmap_element
*a_elt
= a
->first
;
1383 const bitmap_element
*b_elt
= b
->first
;
1384 bitmap_element
*a_prev
= NULL
;
1385 bitmap_element
*next
;
1387 gcc_assert (a
!= b
);
1389 if (bitmap_empty_p (a
))
1394 if (bitmap_empty_p (b
))
1400 while (a_elt
|| b_elt
)
1402 if (!b_elt
|| (a_elt
&& a_elt
->indx
< b_elt
->indx
))
1404 /* A is before B. Remove A */
1406 a_prev
= a_elt
->prev
;
1407 bitmap_element_free (a
, a_elt
);
1410 else if (!a_elt
|| b_elt
->indx
< a_elt
->indx
)
1412 /* B is before A. Copy B. */
1413 next
= bitmap_elt_insert_after (a
, a_prev
, b_elt
->indx
);
1414 memcpy (next
->bits
, b_elt
->bits
, sizeof (next
->bits
));
1416 b_elt
= b_elt
->next
;
1420 /* Matching elts, generate A = ~A & B. */
1422 BITMAP_WORD ior
= 0;
1424 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1426 BITMAP_WORD cleared
= a_elt
->bits
[ix
] & b_elt
->bits
[ix
];
1427 BITMAP_WORD r
= b_elt
->bits
[ix
] ^ cleared
;
1429 a_elt
->bits
[ix
] = r
;
1434 bitmap_element_free (a
, a_elt
);
1438 b_elt
= b_elt
->next
;
1441 gcc_checking_assert (!a
->current
== !a
->first
1442 && (!a
->current
|| a
->indx
== a
->current
->indx
));
1447 /* Insert an element corresponding to A_ELT | B_ELT after DST_PREV,
1448 overwriting DST_ELT if non-NULL. CHANGED is true if the destination bitmap
1449 had already been changed; the new value of CHANGED is returned. */
1452 bitmap_elt_ior (bitmap dst
, bitmap_element
*dst_elt
, bitmap_element
*dst_prev
,
1453 const bitmap_element
*a_elt
, const bitmap_element
*b_elt
,
1456 gcc_assert (a_elt
|| b_elt
);
1458 if (a_elt
&& b_elt
&& a_elt
->indx
== b_elt
->indx
)
1460 /* Matching elts, generate A | B. */
1463 if (!changed
&& dst_elt
&& 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 if (r
!= dst_elt
->bits
[ix
])
1470 dst_elt
->bits
[ix
] = r
;
1479 dst_elt
= bitmap_elt_insert_after (dst
, dst_prev
, a_elt
->indx
);
1481 dst_elt
->indx
= a_elt
->indx
;
1482 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1484 BITMAP_WORD r
= a_elt
->bits
[ix
] | b_elt
->bits
[ix
];
1485 dst_elt
->bits
[ix
] = r
;
1491 /* Copy a single element. */
1492 const bitmap_element
*src
;
1494 if (!b_elt
|| (a_elt
&& a_elt
->indx
< b_elt
->indx
))
1499 gcc_checking_assert (src
);
1500 changed
= bitmap_elt_copy (dst
, dst_elt
, dst_prev
, src
, changed
);
1506 /* DST = A | B. Return true if DST changes. */
1509 bitmap_ior (bitmap dst
, const_bitmap a
, const_bitmap b
)
1511 bitmap_element
*dst_elt
= dst
->first
;
1512 const bitmap_element
*a_elt
= a
->first
;
1513 const bitmap_element
*b_elt
= b
->first
;
1514 bitmap_element
*dst_prev
= NULL
;
1515 bitmap_element
**dst_prev_pnext
= &dst
->first
;
1516 bool changed
= false;
1518 gcc_assert (dst
!= a
&& dst
!= b
);
1520 while (a_elt
|| b_elt
)
1522 changed
= bitmap_elt_ior (dst
, dst_elt
, dst_prev
, a_elt
, b_elt
, changed
);
1524 if (a_elt
&& b_elt
&& a_elt
->indx
== b_elt
->indx
)
1526 a_elt
= a_elt
->next
;
1527 b_elt
= b_elt
->next
;
1531 if (a_elt
&& (!b_elt
|| a_elt
->indx
<= b_elt
->indx
))
1532 a_elt
= a_elt
->next
;
1533 else if (b_elt
&& (!a_elt
|| b_elt
->indx
<= a_elt
->indx
))
1534 b_elt
= b_elt
->next
;
1537 dst_prev
= *dst_prev_pnext
;
1538 dst_prev_pnext
= &dst_prev
->next
;
1539 dst_elt
= *dst_prev_pnext
;
1545 /* Ensure that dst->current is valid. */
1546 dst
->current
= dst
->first
;
1547 bitmap_elt_clear_from (dst
, dst_elt
);
1549 gcc_checking_assert (!dst
->current
== !dst
->first
);
1551 dst
->indx
= dst
->current
->indx
;
1555 /* A |= B. Return true if A changes. */
1558 bitmap_ior_into (bitmap a
, const_bitmap b
)
1560 bitmap_element
*a_elt
= a
->first
;
1561 const bitmap_element
*b_elt
= b
->first
;
1562 bitmap_element
*a_prev
= NULL
;
1563 bitmap_element
**a_prev_pnext
= &a
->first
;
1564 bool changed
= false;
1571 /* If A lags behind B, just advance it. */
1572 if (!a_elt
|| a_elt
->indx
== b_elt
->indx
)
1574 changed
= bitmap_elt_ior (a
, a_elt
, a_prev
, a_elt
, b_elt
, changed
);
1575 b_elt
= b_elt
->next
;
1577 else if (a_elt
->indx
> b_elt
->indx
)
1579 changed
= bitmap_elt_copy (a
, NULL
, a_prev
, b_elt
, changed
);
1580 b_elt
= b_elt
->next
;
1583 a_prev
= *a_prev_pnext
;
1584 a_prev_pnext
= &a_prev
->next
;
1585 a_elt
= *a_prev_pnext
;
1588 gcc_checking_assert (!a
->current
== !a
->first
);
1590 a
->indx
= a
->current
->indx
;
1597 bitmap_xor (bitmap dst
, const_bitmap a
, const_bitmap b
)
1599 bitmap_element
*dst_elt
= dst
->first
;
1600 const bitmap_element
*a_elt
= a
->first
;
1601 const bitmap_element
*b_elt
= b
->first
;
1602 bitmap_element
*dst_prev
= NULL
;
1604 gcc_assert (dst
!= a
&& dst
!= b
);
1611 while (a_elt
|| b_elt
)
1613 if (a_elt
&& b_elt
&& a_elt
->indx
== b_elt
->indx
)
1615 /* Matching elts, generate A ^ B. */
1617 BITMAP_WORD ior
= 0;
1620 dst_elt
= bitmap_elt_insert_after (dst
, dst_prev
, a_elt
->indx
);
1622 dst_elt
->indx
= a_elt
->indx
;
1623 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1625 BITMAP_WORD r
= a_elt
->bits
[ix
] ^ b_elt
->bits
[ix
];
1628 dst_elt
->bits
[ix
] = r
;
1630 a_elt
= a_elt
->next
;
1631 b_elt
= b_elt
->next
;
1635 dst_elt
= dst_elt
->next
;
1640 /* Copy a single element. */
1641 const bitmap_element
*src
;
1643 if (!b_elt
|| (a_elt
&& a_elt
->indx
< b_elt
->indx
))
1646 a_elt
= a_elt
->next
;
1651 b_elt
= b_elt
->next
;
1655 dst_elt
= bitmap_elt_insert_after (dst
, dst_prev
, src
->indx
);
1657 dst_elt
->indx
= src
->indx
;
1658 memcpy (dst_elt
->bits
, src
->bits
, sizeof (dst_elt
->bits
));
1660 dst_elt
= dst_elt
->next
;
1663 /* Ensure that dst->current is valid. */
1664 dst
->current
= dst
->first
;
1665 bitmap_elt_clear_from (dst
, dst_elt
);
1666 gcc_checking_assert (!dst
->current
== !dst
->first
);
1668 dst
->indx
= dst
->current
->indx
;
1674 bitmap_xor_into (bitmap a
, const_bitmap b
)
1676 bitmap_element
*a_elt
= a
->first
;
1677 const bitmap_element
*b_elt
= b
->first
;
1678 bitmap_element
*a_prev
= NULL
;
1688 if (!a_elt
|| b_elt
->indx
< a_elt
->indx
)
1691 bitmap_element
*dst
= bitmap_elt_insert_after (a
, a_prev
, b_elt
->indx
);
1692 memcpy (dst
->bits
, b_elt
->bits
, sizeof (dst
->bits
));
1694 b_elt
= b_elt
->next
;
1696 else if (a_elt
->indx
< b_elt
->indx
)
1699 a_elt
= a_elt
->next
;
1703 /* Matching elts, generate A ^= B. */
1705 BITMAP_WORD ior
= 0;
1706 bitmap_element
*next
= a_elt
->next
;
1708 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1710 BITMAP_WORD r
= a_elt
->bits
[ix
] ^ b_elt
->bits
[ix
];
1713 a_elt
->bits
[ix
] = r
;
1715 b_elt
= b_elt
->next
;
1719 bitmap_element_free (a
, a_elt
);
1723 gcc_checking_assert (!a
->current
== !a
->first
);
1725 a
->indx
= a
->current
->indx
;
1728 /* Return true if two bitmaps are identical.
1729 We do not bother with a check for pointer equality, as that never
1730 occurs in practice. */
1733 bitmap_equal_p (const_bitmap a
, const_bitmap b
)
1735 const bitmap_element
*a_elt
;
1736 const bitmap_element
*b_elt
;
1739 for (a_elt
= a
->first
, b_elt
= b
->first
;
1741 a_elt
= a_elt
->next
, b_elt
= b_elt
->next
)
1743 if (a_elt
->indx
!= b_elt
->indx
)
1745 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1746 if (a_elt
->bits
[ix
] != b_elt
->bits
[ix
])
1749 return !a_elt
&& !b_elt
;
1752 /* Return true if A AND B is not empty. */
1755 bitmap_intersect_p (const_bitmap a
, const_bitmap b
)
1757 const bitmap_element
*a_elt
;
1758 const bitmap_element
*b_elt
;
1761 for (a_elt
= a
->first
, b_elt
= b
->first
;
1764 if (a_elt
->indx
< b_elt
->indx
)
1765 a_elt
= a_elt
->next
;
1766 else if (b_elt
->indx
< a_elt
->indx
)
1767 b_elt
= b_elt
->next
;
1770 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1771 if (a_elt
->bits
[ix
] & b_elt
->bits
[ix
])
1773 a_elt
= a_elt
->next
;
1774 b_elt
= b_elt
->next
;
1780 /* Return true if A AND NOT B is not empty. */
1783 bitmap_intersect_compl_p (const_bitmap a
, const_bitmap b
)
1785 const bitmap_element
*a_elt
;
1786 const bitmap_element
*b_elt
;
1788 for (a_elt
= a
->first
, b_elt
= b
->first
;
1791 if (a_elt
->indx
< b_elt
->indx
)
1793 else if (b_elt
->indx
< a_elt
->indx
)
1794 b_elt
= b_elt
->next
;
1797 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1798 if (a_elt
->bits
[ix
] & ~b_elt
->bits
[ix
])
1800 a_elt
= a_elt
->next
;
1801 b_elt
= b_elt
->next
;
1804 return a_elt
!= NULL
;
1808 /* DST = A | (FROM1 & ~FROM2). Return true if DST changes. */
1811 bitmap_ior_and_compl (bitmap dst
, const_bitmap a
, const_bitmap b
, const_bitmap kill
)
1813 bool changed
= false;
1815 bitmap_element
*dst_elt
= dst
->first
;
1816 const bitmap_element
*a_elt
= a
->first
;
1817 const bitmap_element
*b_elt
= b
->first
;
1818 const bitmap_element
*kill_elt
= kill
->first
;
1819 bitmap_element
*dst_prev
= NULL
;
1820 bitmap_element
**dst_prev_pnext
= &dst
->first
;
1822 gcc_assert (dst
!= a
&& dst
!= b
&& dst
!= kill
);
1824 /* Special cases. We don't bother checking for bitmap_equal_p (b, kill). */
1825 if (b
== kill
|| bitmap_empty_p (b
))
1827 changed
= !bitmap_equal_p (dst
, a
);
1829 bitmap_copy (dst
, a
);
1832 if (bitmap_empty_p (kill
))
1833 return bitmap_ior (dst
, a
, b
);
1834 if (bitmap_empty_p (a
))
1835 return bitmap_and_compl (dst
, b
, kill
);
1837 while (a_elt
|| b_elt
)
1839 bool new_element
= false;
1842 while (kill_elt
&& kill_elt
->indx
< b_elt
->indx
)
1843 kill_elt
= kill_elt
->next
;
1845 if (b_elt
&& kill_elt
&& kill_elt
->indx
== b_elt
->indx
1846 && (!a_elt
|| a_elt
->indx
>= b_elt
->indx
))
1848 bitmap_element tmp_elt
;
1851 BITMAP_WORD ior
= 0;
1852 tmp_elt
.indx
= b_elt
->indx
;
1853 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1855 BITMAP_WORD r
= b_elt
->bits
[ix
] & ~kill_elt
->bits
[ix
];
1857 tmp_elt
.bits
[ix
] = r
;
1862 changed
= bitmap_elt_ior (dst
, dst_elt
, dst_prev
,
1863 a_elt
, &tmp_elt
, changed
);
1865 if (a_elt
&& a_elt
->indx
== b_elt
->indx
)
1866 a_elt
= a_elt
->next
;
1869 b_elt
= b_elt
->next
;
1870 kill_elt
= kill_elt
->next
;
1874 changed
= bitmap_elt_ior (dst
, dst_elt
, dst_prev
,
1875 a_elt
, b_elt
, changed
);
1878 if (a_elt
&& b_elt
&& a_elt
->indx
== b_elt
->indx
)
1880 a_elt
= a_elt
->next
;
1881 b_elt
= b_elt
->next
;
1885 if (a_elt
&& (!b_elt
|| a_elt
->indx
<= b_elt
->indx
))
1886 a_elt
= a_elt
->next
;
1887 else if (b_elt
&& (!a_elt
|| b_elt
->indx
<= a_elt
->indx
))
1888 b_elt
= b_elt
->next
;
1894 dst_prev
= *dst_prev_pnext
;
1895 dst_prev_pnext
= &dst_prev
->next
;
1896 dst_elt
= *dst_prev_pnext
;
1903 /* Ensure that dst->current is valid. */
1904 dst
->current
= dst
->first
;
1905 bitmap_elt_clear_from (dst
, dst_elt
);
1907 gcc_checking_assert (!dst
->current
== !dst
->first
);
1909 dst
->indx
= dst
->current
->indx
;
1914 /* A |= (FROM1 & ~FROM2). Return true if A changes. */
1917 bitmap_ior_and_compl_into (bitmap a
, const_bitmap from1
, const_bitmap from2
)
1922 bitmap_initialize (&tmp
, &bitmap_default_obstack
);
1923 bitmap_and_compl (&tmp
, from1
, from2
);
1924 changed
= bitmap_ior_into (a
, &tmp
);
1925 bitmap_clear (&tmp
);
1930 /* A |= (B & C). Return true if A changes. */
1933 bitmap_ior_and_into (bitmap a
, const_bitmap b
, const_bitmap c
)
1935 bitmap_element
*a_elt
= a
->first
;
1936 const bitmap_element
*b_elt
= b
->first
;
1937 const bitmap_element
*c_elt
= c
->first
;
1938 bitmap_element and_elt
;
1939 bitmap_element
*a_prev
= NULL
;
1940 bitmap_element
**a_prev_pnext
= &a
->first
;
1941 bool changed
= false;
1945 return bitmap_ior_into (a
, b
);
1946 if (bitmap_empty_p (b
) || bitmap_empty_p (c
))
1950 while (b_elt
&& c_elt
)
1952 BITMAP_WORD overall
;
1954 /* Find a common item of B and C. */
1955 while (b_elt
->indx
!= c_elt
->indx
)
1957 if (b_elt
->indx
< c_elt
->indx
)
1959 b_elt
= b_elt
->next
;
1965 c_elt
= c_elt
->next
;
1972 and_elt
.indx
= b_elt
->indx
;
1973 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1975 and_elt
.bits
[ix
] = b_elt
->bits
[ix
] & c_elt
->bits
[ix
];
1976 overall
|= and_elt
.bits
[ix
];
1979 b_elt
= b_elt
->next
;
1980 c_elt
= c_elt
->next
;
1984 /* Now find a place to insert AND_ELT. */
1987 ix
= a_elt
? a_elt
->indx
: and_elt
.indx
;
1988 if (ix
== and_elt
.indx
)
1989 changed
= bitmap_elt_ior (a
, a_elt
, a_prev
, a_elt
, &and_elt
, changed
);
1990 else if (ix
> and_elt
.indx
)
1991 changed
= bitmap_elt_copy (a
, NULL
, a_prev
, &and_elt
, changed
);
1993 a_prev
= *a_prev_pnext
;
1994 a_prev_pnext
= &a_prev
->next
;
1995 a_elt
= *a_prev_pnext
;
1997 /* If A lagged behind B/C, we advanced it so loop once more. */
1999 while (ix
< and_elt
.indx
);
2003 gcc_checking_assert (!a
->current
== !a
->first
);
2005 a
->indx
= a
->current
->indx
;
2009 /* Compute hash of bitmap (for purposes of hashing). */
2011 bitmap_hash (const_bitmap head
)
2013 const bitmap_element
*ptr
;
2014 BITMAP_WORD hash
= 0;
2017 for (ptr
= head
->first
; ptr
; ptr
= ptr
->next
)
2020 for (ix
= 0; ix
!= BITMAP_ELEMENT_WORDS
; ix
++)
2021 hash
^= ptr
->bits
[ix
];
2023 return (hashval_t
)hash
;
2027 /* Debugging function to print out the contents of a bitmap. */
2030 debug_bitmap_file (FILE *file
, const_bitmap head
)
2032 const bitmap_element
*ptr
;
2034 fprintf (file
, "\nfirst = " HOST_PTR_PRINTF
2035 " current = " HOST_PTR_PRINTF
" indx = %u\n",
2036 (void *) head
->first
, (void *) head
->current
, head
->indx
);
2038 for (ptr
= head
->first
; ptr
; ptr
= ptr
->next
)
2040 unsigned int i
, j
, col
= 26;
2042 fprintf (file
, "\t" HOST_PTR_PRINTF
" next = " HOST_PTR_PRINTF
2043 " prev = " HOST_PTR_PRINTF
" indx = %u\n\t\tbits = {",
2044 (const void*) ptr
, (const void*) ptr
->next
,
2045 (const void*) ptr
->prev
, ptr
->indx
);
2047 for (i
= 0; i
< BITMAP_ELEMENT_WORDS
; i
++)
2048 for (j
= 0; j
< BITMAP_WORD_BITS
; j
++)
2049 if ((ptr
->bits
[i
] >> j
) & 1)
2053 fprintf (file
, "\n\t\t\t");
2057 fprintf (file
, " %u", (ptr
->indx
* BITMAP_ELEMENT_ALL_BITS
2058 + i
* BITMAP_WORD_BITS
+ j
));
2062 fprintf (file
, " }\n");
2066 /* Function to be called from the debugger to print the contents
2070 debug_bitmap (const_bitmap head
)
2072 debug_bitmap_file (stderr
, head
);
2075 /* Function to print out the contents of a bitmap. Unlike debug_bitmap_file,
2076 it does not print anything but the bits. */
2079 bitmap_print (FILE *file
, const_bitmap head
, const char *prefix
,
2082 const char *comma
= "";
2086 fputs (prefix
, file
);
2087 EXECUTE_IF_SET_IN_BITMAP (head
, 0, i
, bi
)
2089 fprintf (file
, "%s%d", comma
, i
);
2092 fputs (suffix
, file
);
2095 /* Output per-bitmap memory usage statistics. */
2097 dump_bitmap_statistics (void)
2099 if (!GATHER_STATISTICS
)
2102 bitmap_mem_desc
.dump (BITMAP_ORIGIN
);
2106 debug (const bitmap_head
&ref
)
2108 dump_bitmap (stderr
, &ref
);
2112 debug (const bitmap_head
*ptr
)
2117 fprintf (stderr
, "<nil>\n");
2121 #include "gt-bitmap.h"