1 /* Functions to support general ended bitmaps.
2 Copyright (C) 1997, 1998, 1999, 2000, 2001, 2003, 2004, 2005,
3 2006, 2007, 2008, 2009, 2010 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
29 /* Store information about each particular bitmap. */
30 struct bitmap_descriptor
36 HOST_WIDEST_INT allocated
;
38 HOST_WIDEST_INT current
;
43 /* Hashtable mapping bitmap names to descriptors. */
44 static htab_t bitmap_desc_hash
;
46 /* Hashtable helpers. */
48 hash_descriptor (const void *p
)
50 const struct bitmap_descriptor
*const d
=
51 (const struct bitmap_descriptor
*) p
;
52 return htab_hash_pointer (d
->file
) + d
->line
;
61 eq_descriptor (const void *p1
, const void *p2
)
63 const struct bitmap_descriptor
*const d
=
64 (const struct bitmap_descriptor
*) p1
;
65 const struct loc
*const l
= (const struct loc
*) p2
;
66 return d
->file
== l
->file
&& d
->function
== l
->function
&& d
->line
== l
->line
;
69 /* For given file and line, return descriptor, create new if needed. */
70 static struct bitmap_descriptor
*
71 bitmap_descriptor (const char *file
, int line
, const char *function
)
73 struct bitmap_descriptor
**slot
;
77 loc
.function
= function
;
80 if (!bitmap_desc_hash
)
81 bitmap_desc_hash
= htab_create (10, hash_descriptor
, eq_descriptor
, NULL
);
83 slot
= (struct bitmap_descriptor
**)
84 htab_find_slot_with_hash (bitmap_desc_hash
, &loc
,
85 htab_hash_pointer (file
) + line
,
89 *slot
= XCNEW (struct bitmap_descriptor
);
91 (*slot
)->function
= function
;
96 /* Register new bitmap. */
98 bitmap_register (bitmap b MEM_STAT_DECL
)
100 b
->desc
= bitmap_descriptor (ALONE_FINAL_PASS_MEM_STAT
);
104 /* Account the overhead. */
106 register_overhead (bitmap b
, int amount
)
108 b
->desc
->current
+= amount
;
110 b
->desc
->allocated
+= amount
;
111 gcc_assert (b
->desc
->current
>= 0);
112 if (b
->desc
->peak
< b
->desc
->current
)
113 b
->desc
->peak
= b
->desc
->current
;
117 bitmap_element bitmap_zero_bits
; /* An element of all zero bits. */
118 bitmap_obstack bitmap_default_obstack
; /* The default bitmap obstack. */
119 static int bitmap_default_obstack_depth
;
120 static GTY((deletable
)) bitmap_element
*bitmap_ggc_free
; /* Freelist of
123 static void bitmap_elem_to_freelist (bitmap
, bitmap_element
*);
124 static void bitmap_element_free (bitmap
, bitmap_element
*);
125 static bitmap_element
*bitmap_element_allocate (bitmap
);
126 static int bitmap_element_zerop (const bitmap_element
*);
127 static void bitmap_element_link (bitmap
, bitmap_element
*);
128 static bitmap_element
*bitmap_elt_insert_after (bitmap
, bitmap_element
*, unsigned int);
129 static void bitmap_elt_clear_from (bitmap
, bitmap_element
*);
130 static bitmap_element
*bitmap_find_bit (bitmap
, unsigned int);
133 /* Add ELEM to the appropriate freelist. */
135 bitmap_elem_to_freelist (bitmap head
, bitmap_element
*elt
)
137 bitmap_obstack
*bit_obstack
= head
->obstack
;
142 elt
->prev
= bit_obstack
->elements
;
143 bit_obstack
->elements
= elt
;
147 elt
->prev
= bitmap_ggc_free
;
148 bitmap_ggc_free
= elt
;
152 /* Free a bitmap element. Since these are allocated off the
153 bitmap_obstack, "free" actually means "put onto the freelist". */
156 bitmap_element_free (bitmap head
, bitmap_element
*elt
)
158 bitmap_element
*next
= elt
->next
;
159 bitmap_element
*prev
= elt
->prev
;
167 if (head
->first
== elt
)
170 /* Since the first thing we try is to insert before current,
171 make current the next entry in preference to the previous. */
172 if (head
->current
== elt
)
174 head
->current
= next
!= 0 ? next
: prev
;
176 head
->indx
= head
->current
->indx
;
181 if (GATHER_STATISTICS
)
182 register_overhead (head
, -((int)sizeof (bitmap_element
)));
184 bitmap_elem_to_freelist (head
, elt
);
187 /* Allocate a bitmap element. The bits are cleared, but nothing else is. */
189 static inline bitmap_element
*
190 bitmap_element_allocate (bitmap head
)
192 bitmap_element
*element
;
193 bitmap_obstack
*bit_obstack
= head
->obstack
;
197 element
= bit_obstack
->elements
;
200 /* Use up the inner list first before looking at the next
201 element of the outer list. */
204 bit_obstack
->elements
= element
->next
;
205 bit_obstack
->elements
->prev
= element
->prev
;
208 /* Inner list was just a singleton. */
209 bit_obstack
->elements
= element
->prev
;
211 element
= XOBNEW (&bit_obstack
->obstack
, bitmap_element
);
215 element
= bitmap_ggc_free
;
217 /* Use up the inner list first before looking at the next
218 element of the outer list. */
221 bitmap_ggc_free
= element
->next
;
222 bitmap_ggc_free
->prev
= element
->prev
;
225 /* Inner list was just a singleton. */
226 bitmap_ggc_free
= element
->prev
;
228 element
= ggc_alloc_bitmap_element_def ();
231 if (GATHER_STATISTICS
)
232 register_overhead (head
, sizeof (bitmap_element
));
234 memset (element
->bits
, 0, sizeof (element
->bits
));
239 /* Remove ELT and all following elements from bitmap HEAD. */
242 bitmap_elt_clear_from (bitmap head
, bitmap_element
*elt
)
244 bitmap_element
*prev
;
245 bitmap_obstack
*bit_obstack
= head
->obstack
;
249 if (GATHER_STATISTICS
)
252 for (prev
= elt
; prev
; prev
= prev
->next
)
254 register_overhead (head
, -sizeof (bitmap_element
) * n
);
261 if (head
->current
->indx
> prev
->indx
)
263 head
->current
= prev
;
264 head
->indx
= prev
->indx
;
270 head
->current
= NULL
;
274 /* Put the entire list onto the free list in one operation. */
277 elt
->prev
= bit_obstack
->elements
;
278 bit_obstack
->elements
= elt
;
282 elt
->prev
= bitmap_ggc_free
;
283 bitmap_ggc_free
= elt
;
287 /* Clear a bitmap by freeing the linked list. */
290 bitmap_clear (bitmap head
)
293 bitmap_elt_clear_from (head
, head
->first
);
296 /* Initialize a bitmap obstack. If BIT_OBSTACK is NULL, initialize
297 the default bitmap obstack. */
300 bitmap_obstack_initialize (bitmap_obstack
*bit_obstack
)
304 if (bitmap_default_obstack_depth
++)
306 bit_obstack
= &bitmap_default_obstack
;
309 #if !defined(__GNUC__) || (__GNUC__ < 2)
310 #define __alignof__(type) 0
313 bit_obstack
->elements
= NULL
;
314 bit_obstack
->heads
= NULL
;
315 obstack_specify_allocation (&bit_obstack
->obstack
, OBSTACK_CHUNK_SIZE
,
316 __alignof__ (bitmap_element
),
321 /* Release the memory from a bitmap obstack. If BIT_OBSTACK is NULL,
322 release the default bitmap obstack. */
325 bitmap_obstack_release (bitmap_obstack
*bit_obstack
)
329 if (--bitmap_default_obstack_depth
)
331 gcc_assert (bitmap_default_obstack_depth
> 0);
334 bit_obstack
= &bitmap_default_obstack
;
337 bit_obstack
->elements
= NULL
;
338 bit_obstack
->heads
= NULL
;
339 obstack_free (&bit_obstack
->obstack
, NULL
);
342 /* Create a new bitmap on an obstack. If BIT_OBSTACK is NULL, create
343 it on the default bitmap obstack. */
346 bitmap_obstack_alloc_stat (bitmap_obstack
*bit_obstack MEM_STAT_DECL
)
351 bit_obstack
= &bitmap_default_obstack
;
352 map
= bit_obstack
->heads
;
354 bit_obstack
->heads
= (struct bitmap_head_def
*) map
->first
;
356 map
= XOBNEW (&bit_obstack
->obstack
, bitmap_head
);
357 bitmap_initialize_stat (map
, bit_obstack PASS_MEM_STAT
);
359 if (GATHER_STATISTICS
)
360 register_overhead (map
, sizeof (bitmap_head
));
365 /* Create a new GCd bitmap. */
368 bitmap_gc_alloc_stat (ALONE_MEM_STAT_DECL
)
372 map
= ggc_alloc_bitmap_head_def ();
373 bitmap_initialize_stat (map
, NULL PASS_MEM_STAT
);
375 if (GATHER_STATISTICS
)
376 register_overhead (map
, sizeof (bitmap_head
));
381 /* Release an obstack allocated bitmap. */
384 bitmap_obstack_free (bitmap map
)
389 map
->first
= (bitmap_element
*) map
->obstack
->heads
;
391 if (GATHER_STATISTICS
)
392 register_overhead (map
, -((int)sizeof (bitmap_head
)));
394 map
->obstack
->heads
= map
;
399 /* Return nonzero if all bits in an element are zero. */
402 bitmap_element_zerop (const bitmap_element
*element
)
404 #if BITMAP_ELEMENT_WORDS == 2
405 return (element
->bits
[0] | element
->bits
[1]) == 0;
409 for (i
= 0; i
< BITMAP_ELEMENT_WORDS
; i
++)
410 if (element
->bits
[i
] != 0)
417 /* Link the bitmap element into the current bitmap linked list. */
420 bitmap_element_link (bitmap head
, bitmap_element
*element
)
422 unsigned int indx
= element
->indx
;
425 /* If this is the first and only element, set it in. */
426 if (head
->first
== 0)
428 element
->next
= element
->prev
= 0;
429 head
->first
= element
;
432 /* If this index is less than that of the current element, it goes someplace
433 before the current element. */
434 else if (indx
< head
->indx
)
436 for (ptr
= head
->current
;
437 ptr
->prev
!= 0 && ptr
->prev
->indx
> indx
;
442 ptr
->prev
->next
= element
;
444 head
->first
= element
;
446 element
->prev
= ptr
->prev
;
451 /* Otherwise, it must go someplace after the current element. */
454 for (ptr
= head
->current
;
455 ptr
->next
!= 0 && ptr
->next
->indx
< indx
;
460 ptr
->next
->prev
= element
;
462 element
->next
= ptr
->next
;
467 /* Set up so this is the first element searched. */
468 head
->current
= element
;
472 /* Insert a new uninitialized element into bitmap HEAD after element
473 ELT. If ELT is NULL, insert the element at the start. Return the
476 static bitmap_element
*
477 bitmap_elt_insert_after (bitmap head
, bitmap_element
*elt
, unsigned int indx
)
479 bitmap_element
*node
= bitmap_element_allocate (head
);
486 head
->current
= node
;
489 node
->next
= head
->first
;
491 node
->next
->prev
= node
;
497 gcc_checking_assert (head
->current
);
498 node
->next
= elt
->next
;
500 node
->next
->prev
= node
;
507 /* Copy a bitmap to another bitmap. */
510 bitmap_copy (bitmap to
, const_bitmap from
)
512 const bitmap_element
*from_ptr
;
513 bitmap_element
*to_ptr
= 0;
517 /* Copy elements in forward direction one at a time. */
518 for (from_ptr
= from
->first
; from_ptr
; from_ptr
= from_ptr
->next
)
520 bitmap_element
*to_elt
= bitmap_element_allocate (to
);
522 to_elt
->indx
= from_ptr
->indx
;
523 memcpy (to_elt
->bits
, from_ptr
->bits
, sizeof (to_elt
->bits
));
525 /* Here we have a special case of bitmap_element_link, for the case
526 where we know the links are being entered in sequence. */
529 to
->first
= to
->current
= to_elt
;
530 to
->indx
= from_ptr
->indx
;
531 to_elt
->next
= to_elt
->prev
= 0;
535 to_elt
->prev
= to_ptr
;
537 to_ptr
->next
= to_elt
;
544 /* Find a bitmap element that would hold a bitmap's bit.
545 Update the `current' field even if we can't find an element that
546 would hold the bitmap's bit to make eventual allocation
549 static inline bitmap_element
*
550 bitmap_find_bit (bitmap head
, unsigned int bit
)
552 bitmap_element
*element
;
553 unsigned int indx
= bit
/ BITMAP_ELEMENT_ALL_BITS
;
555 if (head
->current
== 0
556 || head
->indx
== indx
)
557 return head
->current
;
559 if (GATHER_STATISTICS
)
560 head
->desc
->nsearches
++;
562 if (head
->indx
< indx
)
563 /* INDX is beyond head->indx. Search from head->current
565 for (element
= head
->current
;
566 element
->next
!= 0 && element
->indx
< indx
;
567 element
= element
->next
)
569 if (GATHER_STATISTICS
)
570 head
->desc
->search_iter
++;
573 else if (head
->indx
/ 2 < indx
)
574 /* INDX is less than head->indx and closer to head->indx than to
575 0. Search from head->current backward. */
576 for (element
= head
->current
;
577 element
->prev
!= 0 && element
->indx
> indx
;
578 element
= element
->prev
)
580 if (GATHER_STATISTICS
)
581 head
->desc
->search_iter
++;
585 /* INDX is less than head->indx and closer to 0 than to
586 head->indx. Search from head->first forward. */
587 for (element
= head
->first
;
588 element
->next
!= 0 && element
->indx
< indx
;
589 element
= element
->next
)
590 if (GATHER_STATISTICS
)
592 head
->desc
->search_iter
++;
595 /* `element' is the nearest to the one we want. If it's not the one we
596 want, the one we want doesn't exist. */
597 head
->current
= element
;
598 head
->indx
= element
->indx
;
599 if (element
!= 0 && element
->indx
!= indx
)
605 /* Clear a single bit in a bitmap. Return true if the bit changed. */
608 bitmap_clear_bit (bitmap head
, int bit
)
610 bitmap_element
*const ptr
= bitmap_find_bit (head
, bit
);
614 unsigned bit_num
= bit
% BITMAP_WORD_BITS
;
615 unsigned word_num
= bit
/ BITMAP_WORD_BITS
% BITMAP_ELEMENT_WORDS
;
616 BITMAP_WORD bit_val
= ((BITMAP_WORD
) 1) << bit_num
;
617 bool res
= (ptr
->bits
[word_num
] & bit_val
) != 0;
620 ptr
->bits
[word_num
] &= ~bit_val
;
621 /* If we cleared the entire word, free up the element. */
622 if (!ptr
->bits
[word_num
]
623 && bitmap_element_zerop (ptr
))
624 bitmap_element_free (head
, ptr
);
633 /* Set a single bit in a bitmap. Return true if the bit changed. */
636 bitmap_set_bit (bitmap head
, int bit
)
638 bitmap_element
*ptr
= bitmap_find_bit (head
, bit
);
639 unsigned word_num
= bit
/ BITMAP_WORD_BITS
% BITMAP_ELEMENT_WORDS
;
640 unsigned bit_num
= bit
% BITMAP_WORD_BITS
;
641 BITMAP_WORD bit_val
= ((BITMAP_WORD
) 1) << bit_num
;
645 ptr
= bitmap_element_allocate (head
);
646 ptr
->indx
= bit
/ BITMAP_ELEMENT_ALL_BITS
;
647 ptr
->bits
[word_num
] = bit_val
;
648 bitmap_element_link (head
, ptr
);
653 bool res
= (ptr
->bits
[word_num
] & bit_val
) == 0;
655 ptr
->bits
[word_num
] |= bit_val
;
660 /* Return whether a bit is set within a bitmap. */
663 bitmap_bit_p (bitmap head
, int bit
)
669 ptr
= bitmap_find_bit (head
, bit
);
673 bit_num
= bit
% BITMAP_WORD_BITS
;
674 word_num
= bit
/ BITMAP_WORD_BITS
% BITMAP_ELEMENT_WORDS
;
676 return (ptr
->bits
[word_num
] >> bit_num
) & 1;
679 #if GCC_VERSION < 3400
680 /* Table of number of set bits in a character, indexed by value of char. */
681 static const unsigned char popcount_table
[] =
683 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,
684 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,
685 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,
686 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,
687 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,
688 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,
689 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,
690 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,
694 bitmap_popcount (BITMAP_WORD a
)
696 unsigned long ret
= 0;
699 /* Just do this the table way for now */
700 for (i
= 0; i
< BITMAP_WORD_BITS
; i
+= 8)
701 ret
+= popcount_table
[(a
>> i
) & 0xff];
705 /* Count the number of bits set in the bitmap, and return it. */
708 bitmap_count_bits (const_bitmap a
)
710 unsigned long count
= 0;
711 const bitmap_element
*elt
;
714 for (elt
= a
->first
; elt
; elt
= elt
->next
)
716 for (ix
= 0; ix
!= BITMAP_ELEMENT_WORDS
; ix
++)
718 #if GCC_VERSION >= 3400
719 /* Note that popcountl matches BITMAP_WORD in type, so the actual size
720 of BITMAP_WORD is not material. */
721 count
+= __builtin_popcountl (elt
->bits
[ix
]);
723 count
+= bitmap_popcount (elt
->bits
[ix
]);
730 /* Return true if the bitmap has a single bit set. Otherwise return
734 bitmap_single_bit_set_p (const_bitmap a
)
736 unsigned long count
= 0;
737 const bitmap_element
*elt
;
740 if (bitmap_empty_p (a
))
744 /* As there are no completely empty bitmap elements, a second one
745 means we have more than one bit set. */
746 if (elt
->next
!= NULL
)
749 for (ix
= 0; ix
!= BITMAP_ELEMENT_WORDS
; ix
++)
751 #if GCC_VERSION >= 3400
752 /* Note that popcountl matches BITMAP_WORD in type, so the actual size
753 of BITMAP_WORD is not material. */
754 count
+= __builtin_popcountl (elt
->bits
[ix
]);
756 count
+= bitmap_popcount (elt
->bits
[ix
]);
766 /* Return the bit number of the first set bit in the bitmap. The
767 bitmap must be non-empty. */
770 bitmap_first_set_bit (const_bitmap a
)
772 const bitmap_element
*elt
= a
->first
;
777 gcc_checking_assert (elt
);
778 bit_no
= elt
->indx
* BITMAP_ELEMENT_ALL_BITS
;
779 for (ix
= 0; ix
!= BITMAP_ELEMENT_WORDS
; ix
++)
781 word
= elt
->bits
[ix
];
787 bit_no
+= ix
* BITMAP_WORD_BITS
;
789 #if GCC_VERSION >= 3004
790 gcc_assert (sizeof(long) == sizeof (word
));
791 bit_no
+= __builtin_ctzl (word
);
793 /* Binary search for the first set bit. */
794 #if BITMAP_WORD_BITS > 64
795 #error "Fill out the table."
797 #if BITMAP_WORD_BITS > 32
798 if (!(word
& 0xffffffff))
799 word
>>= 32, bit_no
+= 32;
801 if (!(word
& 0xffff))
802 word
>>= 16, bit_no
+= 16;
804 word
>>= 8, bit_no
+= 8;
806 word
>>= 4, bit_no
+= 4;
808 word
>>= 2, bit_no
+= 2;
810 word
>>= 1, bit_no
+= 1;
812 gcc_checking_assert (word
& 1);
817 /* Return the bit number of the first set bit in the bitmap. The
818 bitmap must be non-empty. */
821 bitmap_last_set_bit (const_bitmap a
)
823 const bitmap_element
*elt
= a
->current
? a
->current
: a
->first
;
828 gcc_checking_assert (elt
);
831 bit_no
= elt
->indx
* BITMAP_ELEMENT_ALL_BITS
;
832 for (ix
= BITMAP_ELEMENT_WORDS
- 1; ix
>= 0; ix
--)
834 word
= elt
->bits
[ix
];
840 bit_no
+= ix
* BITMAP_WORD_BITS
;
842 /* Binary search for the last set bit. */
843 #if GCC_VERSION >= 3004
844 gcc_assert (sizeof(long) == sizeof (word
));
845 bit_no
+= sizeof (long) * 8 - __builtin_ctzl (word
);
847 #if BITMAP_WORD_BITS > 64
848 #error "Fill out the table."
850 #if BITMAP_WORD_BITS > 32
851 if ((word
& 0xffffffff00000000))
852 word
>>= 32, bit_no
+= 32;
854 if (word
& 0xffff0000)
855 word
>>= 16, bit_no
+= 16;
856 if (!(word
& 0xff00))
857 word
>>= 8, bit_no
+= 8;
859 word
>>= 4, bit_no
+= 4;
861 word
>>= 2, bit_no
+= 2;
863 word
>>= 1, bit_no
+= 1;
866 gcc_checking_assert (word
& 1);
874 bitmap_and (bitmap dst
, const_bitmap a
, const_bitmap b
)
876 bitmap_element
*dst_elt
= dst
->first
;
877 const bitmap_element
*a_elt
= a
->first
;
878 const bitmap_element
*b_elt
= b
->first
;
879 bitmap_element
*dst_prev
= NULL
;
881 gcc_assert (dst
!= a
&& dst
!= b
);
885 bitmap_copy (dst
, a
);
889 while (a_elt
&& b_elt
)
891 if (a_elt
->indx
< b_elt
->indx
)
893 else if (b_elt
->indx
< a_elt
->indx
)
897 /* Matching elts, generate A & B. */
902 dst_elt
= bitmap_elt_insert_after (dst
, dst_prev
, a_elt
->indx
);
904 dst_elt
->indx
= a_elt
->indx
;
905 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
907 BITMAP_WORD r
= a_elt
->bits
[ix
] & b_elt
->bits
[ix
];
909 dst_elt
->bits
[ix
] = r
;
915 dst_elt
= dst_elt
->next
;
921 /* Ensure that dst->current is valid. */
922 dst
->current
= dst
->first
;
923 bitmap_elt_clear_from (dst
, dst_elt
);
924 gcc_checking_assert (!dst
->current
== !dst
->first
);
926 dst
->indx
= dst
->current
->indx
;
932 bitmap_and_into (bitmap a
, const_bitmap b
)
934 bitmap_element
*a_elt
= a
->first
;
935 const bitmap_element
*b_elt
= b
->first
;
936 bitmap_element
*next
;
941 while (a_elt
&& b_elt
)
943 if (a_elt
->indx
< b_elt
->indx
)
946 bitmap_element_free (a
, a_elt
);
949 else if (b_elt
->indx
< a_elt
->indx
)
953 /* Matching elts, generate A &= B. */
957 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
959 BITMAP_WORD r
= a_elt
->bits
[ix
] & b_elt
->bits
[ix
];
966 bitmap_element_free (a
, a_elt
);
971 bitmap_elt_clear_from (a
, a_elt
);
972 gcc_checking_assert (!a
->current
== !a
->first
973 && (!a
->current
|| a
->indx
== a
->current
->indx
));
977 /* Insert an element equal to SRC_ELT after DST_PREV, overwriting DST_ELT
978 if non-NULL. CHANGED is true if the destination bitmap had already been
979 changed; the new value of CHANGED is returned. */
982 bitmap_elt_copy (bitmap dst
, bitmap_element
*dst_elt
, bitmap_element
*dst_prev
,
983 const bitmap_element
*src_elt
, bool changed
)
985 if (!changed
&& dst_elt
&& dst_elt
->indx
== src_elt
->indx
)
989 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
990 if (src_elt
->bits
[ix
] != dst_elt
->bits
[ix
])
992 dst_elt
->bits
[ix
] = src_elt
->bits
[ix
];
1000 dst_elt
= bitmap_elt_insert_after (dst
, dst_prev
, src_elt
->indx
);
1002 dst_elt
->indx
= src_elt
->indx
;
1003 memcpy (dst_elt
->bits
, src_elt
->bits
, sizeof (dst_elt
->bits
));
1013 bitmap_and_compl (bitmap dst
, const_bitmap a
, const_bitmap b
)
1015 bitmap_element
*dst_elt
= dst
->first
;
1016 const bitmap_element
*a_elt
= a
->first
;
1017 const bitmap_element
*b_elt
= b
->first
;
1018 bitmap_element
*dst_prev
= NULL
;
1019 bitmap_element
**dst_prev_pnext
= &dst
->first
;
1020 bool changed
= false;
1022 gcc_assert (dst
!= a
&& dst
!= b
);
1026 changed
= !bitmap_empty_p (dst
);
1033 while (b_elt
&& b_elt
->indx
< a_elt
->indx
)
1034 b_elt
= b_elt
->next
;
1036 if (!b_elt
|| b_elt
->indx
> a_elt
->indx
)
1038 changed
= bitmap_elt_copy (dst
, dst_elt
, dst_prev
, a_elt
, changed
);
1039 dst_prev
= *dst_prev_pnext
;
1040 dst_prev_pnext
= &dst_prev
->next
;
1041 dst_elt
= *dst_prev_pnext
;
1042 a_elt
= a_elt
->next
;
1047 /* Matching elts, generate A & ~B. */
1049 BITMAP_WORD ior
= 0;
1051 if (!changed
&& dst_elt
&& dst_elt
->indx
== a_elt
->indx
)
1053 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1055 BITMAP_WORD r
= a_elt
->bits
[ix
] & ~b_elt
->bits
[ix
];
1057 if (dst_elt
->bits
[ix
] != r
)
1060 dst_elt
->bits
[ix
] = r
;
1068 if (!dst_elt
|| dst_elt
->indx
> a_elt
->indx
)
1070 dst_elt
= bitmap_elt_insert_after (dst
, dst_prev
, a_elt
->indx
);
1075 dst_elt
->indx
= a_elt
->indx
;
1076 new_element
= false;
1079 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1081 BITMAP_WORD r
= a_elt
->bits
[ix
] & ~b_elt
->bits
[ix
];
1083 dst_elt
->bits
[ix
] = r
;
1091 changed
|= !new_element
;
1092 bitmap_element_free (dst
, dst_elt
);
1093 dst_elt
= *dst_prev_pnext
;
1099 dst_prev
= *dst_prev_pnext
;
1100 dst_prev_pnext
= &dst_prev
->next
;
1101 dst_elt
= *dst_prev_pnext
;
1103 a_elt
= a_elt
->next
;
1104 b_elt
= b_elt
->next
;
1108 /* Ensure that dst->current is valid. */
1109 dst
->current
= dst
->first
;
1114 bitmap_elt_clear_from (dst
, dst_elt
);
1116 gcc_checking_assert (!dst
->current
== !dst
->first
);
1118 dst
->indx
= dst
->current
->indx
;
1123 /* A &= ~B. Returns true if A changes */
1126 bitmap_and_compl_into (bitmap a
, const_bitmap b
)
1128 bitmap_element
*a_elt
= a
->first
;
1129 const bitmap_element
*b_elt
= b
->first
;
1130 bitmap_element
*next
;
1131 BITMAP_WORD changed
= 0;
1135 if (bitmap_empty_p (a
))
1144 while (a_elt
&& b_elt
)
1146 if (a_elt
->indx
< b_elt
->indx
)
1147 a_elt
= a_elt
->next
;
1148 else if (b_elt
->indx
< a_elt
->indx
)
1149 b_elt
= b_elt
->next
;
1152 /* Matching elts, generate A &= ~B. */
1154 BITMAP_WORD ior
= 0;
1156 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1158 BITMAP_WORD cleared
= a_elt
->bits
[ix
] & b_elt
->bits
[ix
];
1159 BITMAP_WORD r
= a_elt
->bits
[ix
] ^ cleared
;
1161 a_elt
->bits
[ix
] = r
;
1167 bitmap_element_free (a
, a_elt
);
1169 b_elt
= b_elt
->next
;
1172 gcc_checking_assert (!a
->current
== !a
->first
1173 && (!a
->current
|| a
->indx
== a
->current
->indx
));
1174 return changed
!= 0;
1177 /* Set COUNT bits from START in HEAD. */
1179 bitmap_set_range (bitmap head
, unsigned int start
, unsigned int count
)
1181 unsigned int first_index
, end_bit_plus1
, last_index
;
1182 bitmap_element
*elt
, *elt_prev
;
1188 first_index
= start
/ BITMAP_ELEMENT_ALL_BITS
;
1189 end_bit_plus1
= start
+ count
;
1190 last_index
= (end_bit_plus1
- 1) / BITMAP_ELEMENT_ALL_BITS
;
1191 elt
= bitmap_find_bit (head
, start
);
1193 /* If bitmap_find_bit returns zero, the current is the closest block
1194 to the result. Otherwise, just use bitmap_element_allocate to
1195 ensure ELT is set; in the loop below, ELT == NULL means "insert
1196 at the end of the bitmap". */
1199 elt
= bitmap_element_allocate (head
);
1200 elt
->indx
= first_index
;
1201 bitmap_element_link (head
, elt
);
1204 gcc_checking_assert (elt
->indx
== first_index
);
1205 elt_prev
= elt
->prev
;
1206 for (i
= first_index
; i
<= last_index
; i
++)
1208 unsigned elt_start_bit
= i
* BITMAP_ELEMENT_ALL_BITS
;
1209 unsigned elt_end_bit_plus1
= elt_start_bit
+ BITMAP_ELEMENT_ALL_BITS
;
1211 unsigned int first_word_to_mod
;
1212 BITMAP_WORD first_mask
;
1213 unsigned int last_word_to_mod
;
1214 BITMAP_WORD last_mask
;
1217 if (!elt
|| elt
->indx
!= i
)
1218 elt
= bitmap_elt_insert_after (head
, elt_prev
, i
);
1220 if (elt_start_bit
<= start
)
1222 /* The first bit to turn on is somewhere inside this
1224 first_word_to_mod
= (start
- elt_start_bit
) / BITMAP_WORD_BITS
;
1226 /* This mask should have 1s in all bits >= start position. */
1228 (((BITMAP_WORD
) 1) << ((start
% BITMAP_WORD_BITS
))) - 1;
1229 first_mask
= ~first_mask
;
1233 /* The first bit to turn on is below this start of this elt. */
1234 first_word_to_mod
= 0;
1235 first_mask
= ~(BITMAP_WORD
) 0;
1238 if (elt_end_bit_plus1
<= end_bit_plus1
)
1240 /* The last bit to turn on is beyond this elt. */
1241 last_word_to_mod
= BITMAP_ELEMENT_WORDS
- 1;
1242 last_mask
= ~(BITMAP_WORD
) 0;
1246 /* The last bit to turn on is inside to this elt. */
1248 (end_bit_plus1
- elt_start_bit
) / BITMAP_WORD_BITS
;
1250 /* The last mask should have 1s below the end bit. */
1252 (((BITMAP_WORD
) 1) << ((end_bit_plus1
% BITMAP_WORD_BITS
))) - 1;
1255 if (first_word_to_mod
== last_word_to_mod
)
1257 BITMAP_WORD mask
= first_mask
& last_mask
;
1258 elt
->bits
[first_word_to_mod
] |= mask
;
1262 elt
->bits
[first_word_to_mod
] |= first_mask
;
1263 if (BITMAP_ELEMENT_WORDS
> 2)
1264 for (ix
= first_word_to_mod
+ 1; ix
< last_word_to_mod
; ix
++)
1265 elt
->bits
[ix
] = ~(BITMAP_WORD
) 0;
1266 elt
->bits
[last_word_to_mod
] |= last_mask
;
1273 head
->current
= elt
? elt
: elt_prev
;
1274 head
->indx
= head
->current
->indx
;
1277 /* Clear COUNT bits from START in HEAD. */
1279 bitmap_clear_range (bitmap head
, unsigned int start
, unsigned int count
)
1281 unsigned int first_index
, end_bit_plus1
, last_index
;
1282 bitmap_element
*elt
;
1287 first_index
= start
/ BITMAP_ELEMENT_ALL_BITS
;
1288 end_bit_plus1
= start
+ count
;
1289 last_index
= (end_bit_plus1
- 1) / BITMAP_ELEMENT_ALL_BITS
;
1290 elt
= bitmap_find_bit (head
, start
);
1292 /* If bitmap_find_bit returns zero, the current is the closest block
1293 to the result. If the current is less than first index, find the
1294 next one. Otherwise, just set elt to be current. */
1299 if (head
->indx
< first_index
)
1301 elt
= head
->current
->next
;
1306 elt
= head
->current
;
1312 while (elt
&& (elt
->indx
<= last_index
))
1314 bitmap_element
* next_elt
= elt
->next
;
1315 unsigned elt_start_bit
= (elt
->indx
) * BITMAP_ELEMENT_ALL_BITS
;
1316 unsigned elt_end_bit_plus1
= elt_start_bit
+ BITMAP_ELEMENT_ALL_BITS
;
1319 if (elt_start_bit
>= start
&& elt_end_bit_plus1
<= end_bit_plus1
)
1320 /* Get rid of the entire elt and go to the next one. */
1321 bitmap_element_free (head
, elt
);
1324 /* Going to have to knock out some bits in this elt. */
1325 unsigned int first_word_to_mod
;
1326 BITMAP_WORD first_mask
;
1327 unsigned int last_word_to_mod
;
1328 BITMAP_WORD last_mask
;
1332 if (elt_start_bit
<= start
)
1334 /* The first bit to turn off is somewhere inside this
1336 first_word_to_mod
= (start
- elt_start_bit
) / BITMAP_WORD_BITS
;
1338 /* This mask should have 1s in all bits >= start position. */
1340 (((BITMAP_WORD
) 1) << ((start
% BITMAP_WORD_BITS
))) - 1;
1341 first_mask
= ~first_mask
;
1345 /* The first bit to turn off is below this start of this elt. */
1346 first_word_to_mod
= 0;
1348 first_mask
= ~first_mask
;
1351 if (elt_end_bit_plus1
<= end_bit_plus1
)
1353 /* The last bit to turn off is beyond this elt. */
1354 last_word_to_mod
= BITMAP_ELEMENT_WORDS
- 1;
1356 last_mask
= ~last_mask
;
1360 /* The last bit to turn off is inside to this elt. */
1362 (end_bit_plus1
- elt_start_bit
) / BITMAP_WORD_BITS
;
1364 /* The last mask should have 1s below the end bit. */
1366 (((BITMAP_WORD
) 1) << (((end_bit_plus1
) % BITMAP_WORD_BITS
))) - 1;
1370 if (first_word_to_mod
== last_word_to_mod
)
1372 BITMAP_WORD mask
= first_mask
& last_mask
;
1373 elt
->bits
[first_word_to_mod
] &= ~mask
;
1377 elt
->bits
[first_word_to_mod
] &= ~first_mask
;
1378 if (BITMAP_ELEMENT_WORDS
> 2)
1379 for (i
= first_word_to_mod
+ 1; i
< last_word_to_mod
; i
++)
1381 elt
->bits
[last_word_to_mod
] &= ~last_mask
;
1383 for (i
= 0; i
< BITMAP_ELEMENT_WORDS
; i
++)
1389 /* Check to see if there are any bits left. */
1391 bitmap_element_free (head
, elt
);
1398 head
->current
= elt
;
1399 head
->indx
= head
->current
->indx
;
1406 bitmap_compl_and_into (bitmap a
, const_bitmap b
)
1408 bitmap_element
*a_elt
= a
->first
;
1409 const bitmap_element
*b_elt
= b
->first
;
1410 bitmap_element
*a_prev
= NULL
;
1411 bitmap_element
*next
;
1413 gcc_assert (a
!= b
);
1415 if (bitmap_empty_p (a
))
1420 if (bitmap_empty_p (b
))
1426 while (a_elt
|| b_elt
)
1428 if (!b_elt
|| (a_elt
&& a_elt
->indx
< b_elt
->indx
))
1430 /* A is before B. Remove A */
1432 a_prev
= a_elt
->prev
;
1433 bitmap_element_free (a
, a_elt
);
1436 else if (!a_elt
|| b_elt
->indx
< a_elt
->indx
)
1438 /* B is before A. Copy B. */
1439 next
= bitmap_elt_insert_after (a
, a_prev
, b_elt
->indx
);
1440 memcpy (next
->bits
, b_elt
->bits
, sizeof (next
->bits
));
1442 b_elt
= b_elt
->next
;
1446 /* Matching elts, generate A = ~A & B. */
1448 BITMAP_WORD ior
= 0;
1450 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1452 BITMAP_WORD cleared
= a_elt
->bits
[ix
] & b_elt
->bits
[ix
];
1453 BITMAP_WORD r
= b_elt
->bits
[ix
] ^ cleared
;
1455 a_elt
->bits
[ix
] = r
;
1460 bitmap_element_free (a
, a_elt
);
1464 b_elt
= b_elt
->next
;
1467 gcc_checking_assert (!a
->current
== !a
->first
1468 && (!a
->current
|| a
->indx
== a
->current
->indx
));
1473 /* Insert an element corresponding to A_ELT | B_ELT after DST_PREV,
1474 overwriting DST_ELT if non-NULL. CHANGED is true if the destination bitmap
1475 had already been changed; the new value of CHANGED is returned. */
1478 bitmap_elt_ior (bitmap dst
, bitmap_element
*dst_elt
, bitmap_element
*dst_prev
,
1479 const bitmap_element
*a_elt
, const bitmap_element
*b_elt
,
1482 gcc_assert (a_elt
|| b_elt
);
1484 if (a_elt
&& b_elt
&& a_elt
->indx
== b_elt
->indx
)
1486 /* Matching elts, generate A | B. */
1489 if (!changed
&& dst_elt
&& dst_elt
->indx
== a_elt
->indx
)
1491 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1493 BITMAP_WORD r
= a_elt
->bits
[ix
] | b_elt
->bits
[ix
];
1494 if (r
!= dst_elt
->bits
[ix
])
1496 dst_elt
->bits
[ix
] = r
;
1505 dst_elt
= bitmap_elt_insert_after (dst
, dst_prev
, a_elt
->indx
);
1507 dst_elt
->indx
= a_elt
->indx
;
1508 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1510 BITMAP_WORD r
= a_elt
->bits
[ix
] | b_elt
->bits
[ix
];
1511 dst_elt
->bits
[ix
] = r
;
1517 /* Copy a single element. */
1518 const bitmap_element
*src
;
1520 if (!b_elt
|| (a_elt
&& a_elt
->indx
< b_elt
->indx
))
1525 gcc_checking_assert (src
);
1526 changed
= bitmap_elt_copy (dst
, dst_elt
, dst_prev
, src
, changed
);
1532 /* DST = A | B. Return true if DST changes. */
1535 bitmap_ior (bitmap dst
, const_bitmap a
, const_bitmap b
)
1537 bitmap_element
*dst_elt
= dst
->first
;
1538 const bitmap_element
*a_elt
= a
->first
;
1539 const bitmap_element
*b_elt
= b
->first
;
1540 bitmap_element
*dst_prev
= NULL
;
1541 bitmap_element
**dst_prev_pnext
= &dst
->first
;
1542 bool changed
= false;
1544 gcc_assert (dst
!= a
&& dst
!= b
);
1546 while (a_elt
|| b_elt
)
1548 changed
= bitmap_elt_ior (dst
, dst_elt
, dst_prev
, a_elt
, b_elt
, changed
);
1550 if (a_elt
&& b_elt
&& a_elt
->indx
== b_elt
->indx
)
1552 a_elt
= a_elt
->next
;
1553 b_elt
= b_elt
->next
;
1557 if (a_elt
&& (!b_elt
|| a_elt
->indx
<= b_elt
->indx
))
1558 a_elt
= a_elt
->next
;
1559 else if (b_elt
&& (!a_elt
|| b_elt
->indx
<= a_elt
->indx
))
1560 b_elt
= b_elt
->next
;
1563 dst_prev
= *dst_prev_pnext
;
1564 dst_prev_pnext
= &dst_prev
->next
;
1565 dst_elt
= *dst_prev_pnext
;
1571 bitmap_elt_clear_from (dst
, dst_elt
);
1573 gcc_checking_assert (!dst
->current
== !dst
->first
);
1575 dst
->indx
= dst
->current
->indx
;
1579 /* A |= B. Return true if A changes. */
1582 bitmap_ior_into (bitmap a
, const_bitmap b
)
1584 bitmap_element
*a_elt
= a
->first
;
1585 const bitmap_element
*b_elt
= b
->first
;
1586 bitmap_element
*a_prev
= NULL
;
1587 bitmap_element
**a_prev_pnext
= &a
->first
;
1588 bool changed
= false;
1595 /* If A lags behind B, just advance it. */
1596 if (!a_elt
|| a_elt
->indx
== b_elt
->indx
)
1598 changed
= bitmap_elt_ior (a
, a_elt
, a_prev
, a_elt
, b_elt
, changed
);
1599 b_elt
= b_elt
->next
;
1601 else if (a_elt
->indx
> b_elt
->indx
)
1603 changed
= bitmap_elt_copy (a
, NULL
, a_prev
, b_elt
, changed
);
1604 b_elt
= b_elt
->next
;
1607 a_prev
= *a_prev_pnext
;
1608 a_prev_pnext
= &a_prev
->next
;
1609 a_elt
= *a_prev_pnext
;
1612 gcc_checking_assert (!a
->current
== !a
->first
);
1614 a
->indx
= a
->current
->indx
;
1621 bitmap_xor (bitmap dst
, const_bitmap a
, const_bitmap b
)
1623 bitmap_element
*dst_elt
= dst
->first
;
1624 const bitmap_element
*a_elt
= a
->first
;
1625 const bitmap_element
*b_elt
= b
->first
;
1626 bitmap_element
*dst_prev
= NULL
;
1628 gcc_assert (dst
!= a
&& dst
!= b
);
1635 while (a_elt
|| b_elt
)
1637 if (a_elt
&& b_elt
&& a_elt
->indx
== b_elt
->indx
)
1639 /* Matching elts, generate A ^ B. */
1641 BITMAP_WORD ior
= 0;
1644 dst_elt
= bitmap_elt_insert_after (dst
, dst_prev
, a_elt
->indx
);
1646 dst_elt
->indx
= a_elt
->indx
;
1647 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1649 BITMAP_WORD r
= a_elt
->bits
[ix
] ^ b_elt
->bits
[ix
];
1652 dst_elt
->bits
[ix
] = r
;
1654 a_elt
= a_elt
->next
;
1655 b_elt
= b_elt
->next
;
1659 dst_elt
= dst_elt
->next
;
1664 /* Copy a single element. */
1665 const bitmap_element
*src
;
1667 if (!b_elt
|| (a_elt
&& a_elt
->indx
< b_elt
->indx
))
1670 a_elt
= a_elt
->next
;
1675 b_elt
= b_elt
->next
;
1679 dst_elt
= bitmap_elt_insert_after (dst
, dst_prev
, src
->indx
);
1681 dst_elt
->indx
= src
->indx
;
1682 memcpy (dst_elt
->bits
, src
->bits
, sizeof (dst_elt
->bits
));
1684 dst_elt
= dst_elt
->next
;
1687 /* Ensure that dst->current is valid. */
1688 dst
->current
= dst
->first
;
1689 bitmap_elt_clear_from (dst
, dst_elt
);
1690 gcc_checking_assert (!dst
->current
== !dst
->first
);
1692 dst
->indx
= dst
->current
->indx
;
1698 bitmap_xor_into (bitmap a
, const_bitmap b
)
1700 bitmap_element
*a_elt
= a
->first
;
1701 const bitmap_element
*b_elt
= b
->first
;
1702 bitmap_element
*a_prev
= NULL
;
1712 if (!a_elt
|| b_elt
->indx
< a_elt
->indx
)
1715 bitmap_element
*dst
= bitmap_elt_insert_after (a
, a_prev
, b_elt
->indx
);
1716 memcpy (dst
->bits
, b_elt
->bits
, sizeof (dst
->bits
));
1718 b_elt
= b_elt
->next
;
1720 else if (a_elt
->indx
< b_elt
->indx
)
1723 a_elt
= a_elt
->next
;
1727 /* Matching elts, generate A ^= B. */
1729 BITMAP_WORD ior
= 0;
1730 bitmap_element
*next
= a_elt
->next
;
1732 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1734 BITMAP_WORD r
= a_elt
->bits
[ix
] ^ b_elt
->bits
[ix
];
1737 a_elt
->bits
[ix
] = r
;
1739 b_elt
= b_elt
->next
;
1743 bitmap_element_free (a
, a_elt
);
1747 gcc_checking_assert (!a
->current
== !a
->first
);
1749 a
->indx
= a
->current
->indx
;
1752 /* Return true if two bitmaps are identical.
1753 We do not bother with a check for pointer equality, as that never
1754 occurs in practice. */
1757 bitmap_equal_p (const_bitmap a
, const_bitmap b
)
1759 const bitmap_element
*a_elt
;
1760 const bitmap_element
*b_elt
;
1763 for (a_elt
= a
->first
, b_elt
= b
->first
;
1765 a_elt
= a_elt
->next
, b_elt
= b_elt
->next
)
1767 if (a_elt
->indx
!= b_elt
->indx
)
1769 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1770 if (a_elt
->bits
[ix
] != b_elt
->bits
[ix
])
1773 return !a_elt
&& !b_elt
;
1776 /* Return true if A AND B is not empty. */
1779 bitmap_intersect_p (const_bitmap a
, const_bitmap b
)
1781 const bitmap_element
*a_elt
;
1782 const bitmap_element
*b_elt
;
1785 for (a_elt
= a
->first
, b_elt
= b
->first
;
1788 if (a_elt
->indx
< b_elt
->indx
)
1789 a_elt
= a_elt
->next
;
1790 else if (b_elt
->indx
< a_elt
->indx
)
1791 b_elt
= b_elt
->next
;
1794 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1795 if (a_elt
->bits
[ix
] & b_elt
->bits
[ix
])
1797 a_elt
= a_elt
->next
;
1798 b_elt
= b_elt
->next
;
1804 /* Return true if A AND NOT B is not empty. */
1807 bitmap_intersect_compl_p (const_bitmap a
, const_bitmap b
)
1809 const bitmap_element
*a_elt
;
1810 const bitmap_element
*b_elt
;
1812 for (a_elt
= a
->first
, b_elt
= b
->first
;
1815 if (a_elt
->indx
< b_elt
->indx
)
1817 else if (b_elt
->indx
< a_elt
->indx
)
1818 b_elt
= b_elt
->next
;
1821 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1822 if (a_elt
->bits
[ix
] & ~b_elt
->bits
[ix
])
1824 a_elt
= a_elt
->next
;
1825 b_elt
= b_elt
->next
;
1828 return a_elt
!= NULL
;
1832 /* DST = A | (FROM1 & ~FROM2). Return true if DST changes. */
1835 bitmap_ior_and_compl (bitmap dst
, const_bitmap a
, const_bitmap b
, const_bitmap kill
)
1837 bool changed
= false;
1839 bitmap_element
*dst_elt
= dst
->first
;
1840 const bitmap_element
*a_elt
= a
->first
;
1841 const bitmap_element
*b_elt
= b
->first
;
1842 const bitmap_element
*kill_elt
= kill
->first
;
1843 bitmap_element
*dst_prev
= NULL
;
1844 bitmap_element
**dst_prev_pnext
= &dst
->first
;
1846 gcc_assert (dst
!= a
&& dst
!= b
&& dst
!= kill
);
1848 /* Special cases. We don't bother checking for bitmap_equal_p (b, kill). */
1849 if (b
== kill
|| bitmap_empty_p (b
))
1851 changed
= !bitmap_equal_p (dst
, a
);
1853 bitmap_copy (dst
, a
);
1856 if (bitmap_empty_p (kill
))
1857 return bitmap_ior (dst
, a
, b
);
1858 if (bitmap_empty_p (a
))
1859 return bitmap_and_compl (dst
, b
, kill
);
1861 while (a_elt
|| b_elt
)
1863 bool new_element
= false;
1866 while (kill_elt
&& kill_elt
->indx
< b_elt
->indx
)
1867 kill_elt
= kill_elt
->next
;
1869 if (b_elt
&& kill_elt
&& kill_elt
->indx
== b_elt
->indx
1870 && (!a_elt
|| a_elt
->indx
>= b_elt
->indx
))
1872 bitmap_element tmp_elt
;
1875 BITMAP_WORD ior
= 0;
1876 tmp_elt
.indx
= b_elt
->indx
;
1877 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1879 BITMAP_WORD r
= b_elt
->bits
[ix
] & ~kill_elt
->bits
[ix
];
1881 tmp_elt
.bits
[ix
] = r
;
1886 changed
= bitmap_elt_ior (dst
, dst_elt
, dst_prev
,
1887 a_elt
, &tmp_elt
, changed
);
1889 if (a_elt
&& a_elt
->indx
== b_elt
->indx
)
1890 a_elt
= a_elt
->next
;
1893 b_elt
= b_elt
->next
;
1894 kill_elt
= kill_elt
->next
;
1898 changed
= bitmap_elt_ior (dst
, dst_elt
, dst_prev
,
1899 a_elt
, b_elt
, changed
);
1902 if (a_elt
&& b_elt
&& a_elt
->indx
== b_elt
->indx
)
1904 a_elt
= a_elt
->next
;
1905 b_elt
= b_elt
->next
;
1909 if (a_elt
&& (!b_elt
|| a_elt
->indx
<= b_elt
->indx
))
1910 a_elt
= a_elt
->next
;
1911 else if (b_elt
&& (!a_elt
|| b_elt
->indx
<= a_elt
->indx
))
1912 b_elt
= b_elt
->next
;
1918 dst_prev
= *dst_prev_pnext
;
1919 dst_prev_pnext
= &dst_prev
->next
;
1920 dst_elt
= *dst_prev_pnext
;
1927 bitmap_elt_clear_from (dst
, dst_elt
);
1929 gcc_checking_assert (!dst
->current
== !dst
->first
);
1931 dst
->indx
= dst
->current
->indx
;
1936 /* A |= (FROM1 & ~FROM2). Return true if A changes. */
1939 bitmap_ior_and_compl_into (bitmap a
, const_bitmap from1
, const_bitmap from2
)
1944 bitmap_initialize (&tmp
, &bitmap_default_obstack
);
1945 bitmap_and_compl (&tmp
, from1
, from2
);
1946 changed
= bitmap_ior_into (a
, &tmp
);
1947 bitmap_clear (&tmp
);
1952 /* A |= (B & C). Return true if A changes. */
1955 bitmap_ior_and_into (bitmap a
, const_bitmap b
, const_bitmap c
)
1957 bitmap_element
*a_elt
= a
->first
;
1958 const bitmap_element
*b_elt
= b
->first
;
1959 const bitmap_element
*c_elt
= c
->first
;
1960 bitmap_element and_elt
;
1961 bitmap_element
*a_prev
= NULL
;
1962 bitmap_element
**a_prev_pnext
= &a
->first
;
1963 bool changed
= false;
1967 return bitmap_ior_into (a
, b
);
1968 if (bitmap_empty_p (b
) || bitmap_empty_p (c
))
1972 while (b_elt
&& c_elt
)
1974 BITMAP_WORD overall
;
1976 /* Find a common item of B and C. */
1977 while (b_elt
->indx
!= c_elt
->indx
)
1979 if (b_elt
->indx
< c_elt
->indx
)
1981 b_elt
= b_elt
->next
;
1987 c_elt
= c_elt
->next
;
1994 and_elt
.indx
= b_elt
->indx
;
1995 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1997 and_elt
.bits
[ix
] = b_elt
->bits
[ix
] & c_elt
->bits
[ix
];
1998 overall
|= and_elt
.bits
[ix
];
2001 b_elt
= b_elt
->next
;
2002 c_elt
= c_elt
->next
;
2006 /* Now find a place to insert AND_ELT. */
2009 ix
= a_elt
? a_elt
->indx
: and_elt
.indx
;
2010 if (ix
== and_elt
.indx
)
2011 changed
= bitmap_elt_ior (a
, a_elt
, a_prev
, a_elt
, &and_elt
, changed
);
2012 else if (ix
> and_elt
.indx
)
2013 changed
= bitmap_elt_copy (a
, NULL
, a_prev
, &and_elt
, changed
);
2015 a_prev
= *a_prev_pnext
;
2016 a_prev_pnext
= &a_prev
->next
;
2017 a_elt
= *a_prev_pnext
;
2019 /* If A lagged behind B/C, we advanced it so loop once more. */
2021 while (ix
< and_elt
.indx
);
2025 gcc_checking_assert (!a
->current
== !a
->first
);
2027 a
->indx
= a
->current
->indx
;
2031 /* Compute hash of bitmap (for purposes of hashing). */
2033 bitmap_hash (const_bitmap head
)
2035 const bitmap_element
*ptr
;
2036 BITMAP_WORD hash
= 0;
2039 for (ptr
= head
->first
; ptr
; ptr
= ptr
->next
)
2042 for (ix
= 0; ix
!= BITMAP_ELEMENT_WORDS
; ix
++)
2043 hash
^= ptr
->bits
[ix
];
2045 return (hashval_t
)hash
;
2049 /* Debugging function to print out the contents of a bitmap. */
2052 debug_bitmap_file (FILE *file
, const_bitmap head
)
2054 const bitmap_element
*ptr
;
2056 fprintf (file
, "\nfirst = " HOST_PTR_PRINTF
2057 " current = " HOST_PTR_PRINTF
" indx = %u\n",
2058 (void *) head
->first
, (void *) head
->current
, head
->indx
);
2060 for (ptr
= head
->first
; ptr
; ptr
= ptr
->next
)
2062 unsigned int i
, j
, col
= 26;
2064 fprintf (file
, "\t" HOST_PTR_PRINTF
" next = " HOST_PTR_PRINTF
2065 " prev = " HOST_PTR_PRINTF
" indx = %u\n\t\tbits = {",
2066 (const void*) ptr
, (const void*) ptr
->next
,
2067 (const void*) ptr
->prev
, ptr
->indx
);
2069 for (i
= 0; i
< BITMAP_ELEMENT_WORDS
; i
++)
2070 for (j
= 0; j
< BITMAP_WORD_BITS
; j
++)
2071 if ((ptr
->bits
[i
] >> j
) & 1)
2075 fprintf (file
, "\n\t\t\t");
2079 fprintf (file
, " %u", (ptr
->indx
* BITMAP_ELEMENT_ALL_BITS
2080 + i
* BITMAP_WORD_BITS
+ j
));
2084 fprintf (file
, " }\n");
2088 /* Function to be called from the debugger to print the contents
2092 debug_bitmap (const_bitmap head
)
2094 debug_bitmap_file (stdout
, head
);
2097 /* Function to print out the contents of a bitmap. Unlike debug_bitmap_file,
2098 it does not print anything but the bits. */
2101 bitmap_print (FILE *file
, const_bitmap head
, const char *prefix
, const char *suffix
)
2103 const char *comma
= "";
2107 fputs (prefix
, file
);
2108 EXECUTE_IF_SET_IN_BITMAP (head
, 0, i
, bi
)
2110 fprintf (file
, "%s%d", comma
, i
);
2113 fputs (suffix
, file
);
2117 /* Used to accumulate statistics about bitmap sizes. */
2120 HOST_WIDEST_INT size
;
2124 /* Called via htab_traverse. Output bitmap descriptor pointed out by SLOT
2125 and update statistics. */
2127 print_statistics (void **slot
, void *b
)
2129 struct bitmap_descriptor
*d
= (struct bitmap_descriptor
*) *slot
;
2130 struct output_info
*i
= (struct output_info
*) b
;
2135 const char *s1
= d
->file
;
2137 while ((s2
= strstr (s1
, "gcc/")))
2139 sprintf (s
, "%s:%i (%s)", s1
, d
->line
, d
->function
);
2141 fprintf (stderr
, "%-41s %8d %15"HOST_WIDEST_INT_PRINT
"d %15"
2142 HOST_WIDEST_INT_PRINT
"d %15"HOST_WIDEST_INT_PRINT
"d %10d %10d\n",
2143 s
, d
->created
, d
->allocated
, d
->peak
, d
->current
, d
->nsearches
,
2145 i
->size
+= d
->allocated
;
2146 i
->count
+= d
->created
;
2151 /* Output per-bitmap memory usage statistics. */
2153 dump_bitmap_statistics (void)
2155 struct output_info info
;
2157 if (! GATHER_STATISTICS
)
2160 if (!bitmap_desc_hash
)
2163 fprintf (stderr
, "\nBitmap Overall "
2164 " Allocated Peak Leak searched "
2166 fprintf (stderr
, "---------------------------------------------------------------------------------\n");
2169 htab_traverse (bitmap_desc_hash
, print_statistics
, &info
);
2170 fprintf (stderr
, "---------------------------------------------------------------------------------\n");
2171 fprintf (stderr
, "%-40s %9d %15"HOST_WIDEST_INT_PRINT
"d\n",
2172 "Total", info
.count
, info
.size
);
2173 fprintf (stderr
, "---------------------------------------------------------------------------------\n");
2176 #include "gt-bitmap.h"