1 /* Functions to support general ended bitmaps.
2 Copyright (C) 1997, 1998, 1999, 2000, 2001, 2003, 2004, 2005
3 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 2, 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 COPYING. If not, write to the Free
19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
24 #include "coretypes.h"
33 #ifdef GATHER_STATISTICS
35 /* Store information about each particular bitmap. */
36 struct bitmap_descriptor
48 /* Hashtable mapping bitmap names to descriptors. */
49 static htab_t bitmap_desc_hash
;
51 /* Hashtable helpers. */
53 hash_descriptor (const void *p
)
55 const struct bitmap_descriptor
*d
= p
;
56 return htab_hash_pointer (d
->file
) + d
->line
;
65 eq_descriptor (const void *p1
, const void *p2
)
67 const struct bitmap_descriptor
*d
= p1
;
68 const struct loc
*l
= p2
;
69 return d
->file
== l
->file
&& d
->function
== l
->function
&& d
->line
== l
->line
;
72 /* For given file and line, return descriptor, create new if needed. */
73 static struct bitmap_descriptor
*
74 bitmap_descriptor (const char *file
, const char *function
, int line
)
76 struct bitmap_descriptor
**slot
;
80 loc
.function
= function
;
83 if (!bitmap_desc_hash
)
84 bitmap_desc_hash
= htab_create (10, hash_descriptor
, eq_descriptor
, NULL
);
86 slot
= (struct bitmap_descriptor
**)
87 htab_find_slot_with_hash (bitmap_desc_hash
, &loc
,
88 htab_hash_pointer (file
) + line
,
92 *slot
= xcalloc (sizeof (**slot
), 1);
94 (*slot
)->function
= function
;
99 /* Register new bitmap. */
101 bitmap_register (bitmap b MEM_STAT_DECL
)
103 b
->desc
= bitmap_descriptor (_loc_name
, _loc_function
, _loc_line
);
107 /* Account the overhead. */
109 register_overhead (bitmap b
, int amount
)
111 b
->desc
->current
+= amount
;
113 b
->desc
->allocated
+= amount
;
114 gcc_assert (b
->desc
->current
>= 0);
115 if (b
->desc
->peak
< b
->desc
->current
)
116 b
->desc
->peak
= b
->desc
->current
;
121 bitmap_element bitmap_zero_bits
; /* An element of all zero bits. */
122 bitmap_obstack bitmap_default_obstack
; /* The default bitmap obstack. */
123 static GTY((deletable
)) bitmap_element
*bitmap_ggc_free
; /* Freelist of
126 static void bitmap_elem_to_freelist (bitmap
, bitmap_element
*);
127 static void bitmap_element_free (bitmap
, bitmap_element
*);
128 static bitmap_element
*bitmap_element_allocate (bitmap
);
129 static int bitmap_element_zerop (bitmap_element
*);
130 static void bitmap_element_link (bitmap
, bitmap_element
*);
131 static bitmap_element
*bitmap_elt_insert_after (bitmap
, bitmap_element
*, unsigned int);
132 static void bitmap_elt_clear_from (bitmap
, bitmap_element
*);
133 static bitmap_element
*bitmap_find_bit (bitmap
, unsigned int);
136 /* Add ELEM to the appropriate freelist. */
138 bitmap_elem_to_freelist (bitmap head
, bitmap_element
*elt
)
140 bitmap_obstack
*bit_obstack
= head
->obstack
;
145 elt
->prev
= bit_obstack
->elements
;
146 bit_obstack
->elements
= elt
;
150 elt
->prev
= bitmap_ggc_free
;
151 bitmap_ggc_free
= elt
;
155 /* Free a bitmap element. Since these are allocated off the
156 bitmap_obstack, "free" actually means "put onto the freelist". */
159 bitmap_element_free (bitmap head
, bitmap_element
*elt
)
161 bitmap_element
*next
= elt
->next
;
162 bitmap_element
*prev
= elt
->prev
;
170 if (head
->first
== elt
)
173 /* Since the first thing we try is to insert before current,
174 make current the next entry in preference to the previous. */
175 if (head
->current
== elt
)
177 head
->current
= next
!= 0 ? next
: prev
;
179 head
->indx
= head
->current
->indx
;
183 #ifdef GATHER_STATISTICS
184 register_overhead (head
, -((int)sizeof (bitmap_element
)));
186 bitmap_elem_to_freelist (head
, elt
);
189 /* Allocate a bitmap element. The bits are cleared, but nothing else is. */
191 static inline bitmap_element
*
192 bitmap_element_allocate (bitmap head
)
194 bitmap_element
*element
;
195 bitmap_obstack
*bit_obstack
= head
->obstack
;
199 element
= bit_obstack
->elements
;
202 /* Use up the inner list first before looking at the next
203 element of the outer list. */
206 bit_obstack
->elements
= element
->next
;
207 bit_obstack
->elements
->prev
= element
->prev
;
210 /* Inner list was just a singleton. */
211 bit_obstack
->elements
= element
->prev
;
213 element
= XOBNEW (&bit_obstack
->obstack
, bitmap_element
);
217 element
= bitmap_ggc_free
;
219 /* Use up the inner list first before looking at the next
220 element of the outer list. */
223 bitmap_ggc_free
= element
->next
;
224 bitmap_ggc_free
->prev
= element
->prev
;
227 /* Inner list was just a singleton. */
228 bitmap_ggc_free
= element
->prev
;
230 element
= GGC_NEW (bitmap_element
);
233 #ifdef GATHER_STATISTICS
234 register_overhead (head
, sizeof (bitmap_element
));
236 memset (element
->bits
, 0, sizeof (element
->bits
));
241 /* Remove ELT and all following elements from bitmap HEAD. */
244 bitmap_elt_clear_from (bitmap head
, bitmap_element
*elt
)
246 bitmap_element
*prev
;
247 bitmap_obstack
*bit_obstack
= head
->obstack
;
248 #ifdef GATHER_STATISTICS
253 #ifdef GATHER_STATISTICS
255 for (prev
= elt
; prev
; prev
= prev
->next
)
257 register_overhead (head
, -sizeof (bitmap_element
) * n
);
264 if (head
->current
->indx
> prev
->indx
)
266 head
->current
= prev
;
267 head
->indx
= prev
->indx
;
273 head
->current
= NULL
;
277 /* Put the entire list onto the free list in one operation. */
280 elt
->prev
= bit_obstack
->elements
;
281 bit_obstack
->elements
= elt
;
285 elt
->prev
= bitmap_ggc_free
;
286 bitmap_ggc_free
= elt
;
290 /* Clear a bitmap by freeing the linked list. */
293 bitmap_clear (bitmap head
)
296 bitmap_elt_clear_from (head
, head
->first
);
299 /* Initialize a bitmap obstack. If BIT_OBSTACK is NULL, initialize
300 the default bitmap obstack. */
303 bitmap_obstack_initialize (bitmap_obstack
*bit_obstack
)
306 bit_obstack
= &bitmap_default_obstack
;
308 #if !defined(__GNUC__) || (__GNUC__ < 2)
309 #define __alignof__(type) 0
312 bit_obstack
->elements
= NULL
;
313 bit_obstack
->heads
= NULL
;
314 obstack_specify_allocation (&bit_obstack
->obstack
, OBSTACK_CHUNK_SIZE
,
315 __alignof__ (bitmap_element
),
320 /* Release the memory from a bitmap obstack. If BIT_OBSTACK is NULL,
321 release the default bitmap obstack. */
324 bitmap_obstack_release (bitmap_obstack
*bit_obstack
)
327 bit_obstack
= &bitmap_default_obstack
;
329 bit_obstack
->elements
= NULL
;
330 bit_obstack
->heads
= NULL
;
331 obstack_free (&bit_obstack
->obstack
, NULL
);
334 /* Create a new bitmap on an obstack. If BIT_OBSTACK is NULL, create
335 it on the default bitmap obstack. */
338 bitmap_obstack_alloc_stat (bitmap_obstack
*bit_obstack MEM_STAT_DECL
)
343 bit_obstack
= &bitmap_default_obstack
;
344 map
= bit_obstack
->heads
;
346 bit_obstack
->heads
= (void *)map
->first
;
348 map
= XOBNEW (&bit_obstack
->obstack
, bitmap_head
);
349 bitmap_initialize_stat (map
, bit_obstack PASS_MEM_STAT
);
350 #ifdef GATHER_STATISTICS
351 register_overhead (map
, sizeof (bitmap_head
));
357 /* Create a new GCd bitmap. */
360 bitmap_gc_alloc_stat (ALONE_MEM_STAT_DECL
)
364 map
= GGC_NEW (struct bitmap_head_def
);
365 bitmap_initialize_stat (map
, NULL PASS_MEM_STAT
);
366 #ifdef GATHER_STATISTICS
367 register_overhead (map
, sizeof (bitmap_head
));
373 /* Release an obstack allocated bitmap. */
376 bitmap_obstack_free (bitmap map
)
381 map
->first
= (void *)map
->obstack
->heads
;
382 #ifdef GATHER_STATISTICS
383 register_overhead (map
, -((int)sizeof (bitmap_head
)));
385 map
->obstack
->heads
= map
;
390 /* Return nonzero if all bits in an element are zero. */
393 bitmap_element_zerop (bitmap_element
*element
)
395 #if BITMAP_ELEMENT_WORDS == 2
396 return (element
->bits
[0] | element
->bits
[1]) == 0;
400 for (i
= 0; i
< BITMAP_ELEMENT_WORDS
; i
++)
401 if (element
->bits
[i
] != 0)
408 /* Link the bitmap element into the current bitmap linked list. */
411 bitmap_element_link (bitmap head
, bitmap_element
*element
)
413 unsigned int indx
= element
->indx
;
416 /* If this is the first and only element, set it in. */
417 if (head
->first
== 0)
419 element
->next
= element
->prev
= 0;
420 head
->first
= element
;
423 /* If this index is less than that of the current element, it goes someplace
424 before the current element. */
425 else if (indx
< head
->indx
)
427 for (ptr
= head
->current
;
428 ptr
->prev
!= 0 && ptr
->prev
->indx
> indx
;
433 ptr
->prev
->next
= element
;
435 head
->first
= element
;
437 element
->prev
= ptr
->prev
;
442 /* Otherwise, it must go someplace after the current element. */
445 for (ptr
= head
->current
;
446 ptr
->next
!= 0 && ptr
->next
->indx
< indx
;
451 ptr
->next
->prev
= element
;
453 element
->next
= ptr
->next
;
458 /* Set up so this is the first element searched. */
459 head
->current
= element
;
463 /* Insert a new uninitialized element into bitmap HEAD after element
464 ELT. If ELT is NULL, insert the element at the start. Return the
467 static bitmap_element
*
468 bitmap_elt_insert_after (bitmap head
, bitmap_element
*elt
, unsigned int indx
)
470 bitmap_element
*node
= bitmap_element_allocate (head
);
477 head
->current
= node
;
480 node
->next
= head
->first
;
482 node
->next
->prev
= node
;
488 gcc_assert (head
->current
);
489 node
->next
= elt
->next
;
491 node
->next
->prev
= node
;
498 /* Copy a bitmap to another bitmap. */
501 bitmap_copy (bitmap to
, bitmap from
)
503 bitmap_element
*from_ptr
, *to_ptr
= 0;
507 /* Copy elements in forward direction one at a time. */
508 for (from_ptr
= from
->first
; from_ptr
; from_ptr
= from_ptr
->next
)
510 bitmap_element
*to_elt
= bitmap_element_allocate (to
);
512 to_elt
->indx
= from_ptr
->indx
;
513 memcpy (to_elt
->bits
, from_ptr
->bits
, sizeof (to_elt
->bits
));
515 /* Here we have a special case of bitmap_element_link, for the case
516 where we know the links are being entered in sequence. */
519 to
->first
= to
->current
= to_elt
;
520 to
->indx
= from_ptr
->indx
;
521 to_elt
->next
= to_elt
->prev
= 0;
525 to_elt
->prev
= to_ptr
;
527 to_ptr
->next
= to_elt
;
534 /* Find a bitmap element that would hold a bitmap's bit.
535 Update the `current' field even if we can't find an element that
536 would hold the bitmap's bit to make eventual allocation
539 static inline bitmap_element
*
540 bitmap_find_bit (bitmap head
, unsigned int bit
)
542 bitmap_element
*element
;
543 unsigned int indx
= bit
/ BITMAP_ELEMENT_ALL_BITS
;
545 #ifdef GATHER_STATISTICS
546 head
->desc
->nsearches
++;
548 if (head
->current
== 0
549 || head
->indx
== indx
)
550 return head
->current
;
552 if (head
->indx
< indx
)
553 /* INDX is beyond head->indx. Search from head->current
555 for (element
= head
->current
;
556 element
->next
!= 0 && element
->indx
< indx
;
557 element
= element
->next
)
560 else if (head
->indx
/ 2 < indx
)
561 /* INDX is less than head->indx and closer to head->indx than to
562 0. Search from head->current backward. */
563 for (element
= head
->current
;
564 element
->prev
!= 0 && element
->indx
> indx
;
565 element
= element
->prev
)
569 /* INDX is less than head->indx and closer to 0 than to
570 head->indx. Search from head->first forward. */
571 for (element
= head
->first
;
572 element
->next
!= 0 && element
->indx
< indx
;
573 element
= element
->next
)
576 /* `element' is the nearest to the one we want. If it's not the one we
577 want, the one we want doesn't exist. */
578 head
->current
= element
;
579 head
->indx
= element
->indx
;
580 if (element
!= 0 && element
->indx
!= indx
)
586 /* Clear a single bit in a bitmap. */
589 bitmap_clear_bit (bitmap head
, int bit
)
591 bitmap_element
*ptr
= bitmap_find_bit (head
, bit
);
595 unsigned bit_num
= bit
% BITMAP_WORD_BITS
;
596 unsigned word_num
= bit
/ BITMAP_WORD_BITS
% BITMAP_ELEMENT_WORDS
;
597 ptr
->bits
[word_num
] &= ~ (((BITMAP_WORD
) 1) << bit_num
);
599 /* If we cleared the entire word, free up the element. */
600 if (bitmap_element_zerop (ptr
))
601 bitmap_element_free (head
, ptr
);
605 /* Set a single bit in a bitmap. */
608 bitmap_set_bit (bitmap head
, int bit
)
610 bitmap_element
*ptr
= bitmap_find_bit (head
, bit
);
611 unsigned word_num
= bit
/ BITMAP_WORD_BITS
% BITMAP_ELEMENT_WORDS
;
612 unsigned bit_num
= bit
% BITMAP_WORD_BITS
;
613 BITMAP_WORD bit_val
= ((BITMAP_WORD
) 1) << bit_num
;
617 ptr
= bitmap_element_allocate (head
);
618 ptr
->indx
= bit
/ BITMAP_ELEMENT_ALL_BITS
;
619 ptr
->bits
[word_num
] = bit_val
;
620 bitmap_element_link (head
, ptr
);
623 ptr
->bits
[word_num
] |= bit_val
;
626 /* Return whether a bit is set within a bitmap. */
629 bitmap_bit_p (bitmap head
, int bit
)
635 ptr
= bitmap_find_bit (head
, bit
);
639 bit_num
= bit
% BITMAP_WORD_BITS
;
640 word_num
= bit
/ BITMAP_WORD_BITS
% BITMAP_ELEMENT_WORDS
;
642 return (ptr
->bits
[word_num
] >> bit_num
) & 1;
645 #if GCC_VERSION < 3400
646 /* Table of number of set bits in a character, indexed by value of char. */
647 static unsigned char popcount_table
[] =
649 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,
650 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,
651 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,
652 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,
653 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,
654 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,
655 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,
656 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,
660 bitmap_popcount (BITMAP_WORD a
)
662 unsigned long ret
= 0;
665 /* Just do this the table way for now */
666 for (i
= 0; i
< BITMAP_WORD_BITS
; i
+= 8)
667 ret
+= popcount_table
[(a
>> i
) & 0xff];
671 /* Count the number of bits set in the bitmap, and return it. */
674 bitmap_count_bits (bitmap a
)
676 unsigned long count
= 0;
680 for (elt
= a
->first
; elt
; elt
= elt
->next
)
682 for (ix
= 0; ix
!= BITMAP_ELEMENT_WORDS
; ix
++)
684 #if GCC_VERSION >= 3400
685 /* Note that popcountl matches BITMAP_WORD in type, so the actual size
686 of BITMAP_WORD is not material. */
687 count
+= __builtin_popcountl (elt
->bits
[ix
]);
689 count
+= bitmap_popcount (elt
->bits
[ix
]);
698 /* Return the bit number of the first set bit in the bitmap. The
699 bitmap must be non-empty. */
702 bitmap_first_set_bit (bitmap a
)
704 bitmap_element
*elt
= a
->first
;
710 bit_no
= elt
->indx
* BITMAP_ELEMENT_ALL_BITS
;
711 for (ix
= 0; ix
!= BITMAP_ELEMENT_WORDS
; ix
++)
713 word
= elt
->bits
[ix
];
719 bit_no
+= ix
* BITMAP_WORD_BITS
;
721 #if GCC_VERSION >= 3004
722 gcc_assert (sizeof(long) == sizeof (word
));
723 bit_no
+= __builtin_ctzl (word
);
725 /* Binary search for the first set bit. */
726 #if BITMAP_WORD_BITS > 64
727 #error "Fill out the table."
729 #if BITMAP_WORD_BITS > 32
730 if (!(word
& 0xffffffff))
731 word
>>= 32, bit_no
+= 32;
733 if (!(word
& 0xffff))
734 word
>>= 16, bit_no
+= 16;
736 word
>>= 8, bit_no
+= 8;
738 word
>>= 4, bit_no
+= 4;
740 word
>>= 2, bit_no
+= 2;
742 word
>>= 1, bit_no
+= 1;
744 gcc_assert (word
& 1);
753 bitmap_and (bitmap dst
, bitmap a
, bitmap b
)
755 bitmap_element
*dst_elt
= dst
->first
;
756 bitmap_element
*a_elt
= a
->first
;
757 bitmap_element
*b_elt
= b
->first
;
758 bitmap_element
*dst_prev
= NULL
;
760 gcc_assert (dst
!= a
&& dst
!= b
);
764 bitmap_copy (dst
, a
);
768 while (a_elt
&& b_elt
)
770 if (a_elt
->indx
< b_elt
->indx
)
772 else if (b_elt
->indx
< a_elt
->indx
)
776 /* Matching elts, generate A & B. */
781 dst_elt
= bitmap_elt_insert_after (dst
, dst_prev
, a_elt
->indx
);
783 dst_elt
->indx
= a_elt
->indx
;
784 for (ix
= BITMAP_ELEMENT_WORDS
; ix
--;)
786 BITMAP_WORD r
= a_elt
->bits
[ix
] & b_elt
->bits
[ix
];
788 dst_elt
->bits
[ix
] = r
;
794 dst_elt
= dst_elt
->next
;
800 bitmap_elt_clear_from (dst
, dst_elt
);
801 gcc_assert (!dst
->current
== !dst
->first
);
803 dst
->indx
= dst
->current
->indx
;
809 bitmap_and_into (bitmap a
, bitmap b
)
811 bitmap_element
*a_elt
= a
->first
;
812 bitmap_element
*b_elt
= b
->first
;
813 bitmap_element
*next
;
818 while (a_elt
&& b_elt
)
820 if (a_elt
->indx
< b_elt
->indx
)
823 bitmap_element_free (a
, a_elt
);
826 else if (b_elt
->indx
< a_elt
->indx
)
830 /* Matching elts, generate A &= B. */
834 for (ix
= BITMAP_ELEMENT_WORDS
; ix
--;)
836 BITMAP_WORD r
= a_elt
->bits
[ix
] & b_elt
->bits
[ix
];
843 bitmap_element_free (a
, a_elt
);
848 bitmap_elt_clear_from (a
, a_elt
);
849 gcc_assert (!a
->current
== !a
->first
);
850 gcc_assert (!a
->current
|| a
->indx
== a
->current
->indx
);
856 bitmap_and_compl (bitmap dst
, bitmap a
, bitmap b
)
858 bitmap_element
*dst_elt
= dst
->first
;
859 bitmap_element
*a_elt
= a
->first
;
860 bitmap_element
*b_elt
= b
->first
;
861 bitmap_element
*dst_prev
= NULL
;
863 gcc_assert (dst
!= a
&& dst
!= b
);
873 if (!b_elt
|| a_elt
->indx
< b_elt
->indx
)
877 dst_elt
= bitmap_elt_insert_after (dst
, dst_prev
, a_elt
->indx
);
879 dst_elt
->indx
= a_elt
->indx
;
880 memcpy (dst_elt
->bits
, a_elt
->bits
, sizeof (dst_elt
->bits
));
882 dst_elt
= dst_elt
->next
;
885 else if (b_elt
->indx
< a_elt
->indx
)
889 /* Matching elts, generate A & ~B. */
894 dst_elt
= bitmap_elt_insert_after (dst
, dst_prev
, a_elt
->indx
);
896 dst_elt
->indx
= a_elt
->indx
;
897 for (ix
= BITMAP_ELEMENT_WORDS
; ix
--;)
899 BITMAP_WORD r
= a_elt
->bits
[ix
] & ~b_elt
->bits
[ix
];
901 dst_elt
->bits
[ix
] = r
;
907 dst_elt
= dst_elt
->next
;
913 bitmap_elt_clear_from (dst
, dst_elt
);
914 gcc_assert (!dst
->current
== !dst
->first
);
916 dst
->indx
= dst
->current
->indx
;
919 /* A &= ~B. Returns true if A changes */
922 bitmap_and_compl_into (bitmap a
, bitmap b
)
924 bitmap_element
*a_elt
= a
->first
;
925 bitmap_element
*b_elt
= b
->first
;
926 bitmap_element
*next
;
927 BITMAP_WORD changed
= 0;
931 if (bitmap_empty_p (a
))
940 while (a_elt
&& b_elt
)
942 if (a_elt
->indx
< b_elt
->indx
)
944 else if (b_elt
->indx
< a_elt
->indx
)
948 /* Matching elts, generate A &= ~B. */
952 for (ix
= BITMAP_ELEMENT_WORDS
; ix
--;)
954 BITMAP_WORD cleared
= a_elt
->bits
[ix
] & b_elt
->bits
[ix
];
955 BITMAP_WORD r
= a_elt
->bits
[ix
] ^ cleared
;
963 bitmap_element_free (a
, a_elt
);
968 gcc_assert (!a
->current
== !a
->first
);
969 gcc_assert (!a
->current
|| a
->indx
== a
->current
->indx
);
973 /* Clear COUNT bits from START in HEAD. */
975 bitmap_clear_range (bitmap head
, unsigned int start
, unsigned int count
)
977 unsigned int first_index
= start
/ BITMAP_ELEMENT_ALL_BITS
;
978 unsigned int end_bit_plus1
= start
+ count
;
979 unsigned int end_bit
= end_bit_plus1
- 1;
980 unsigned int last_index
= (end_bit
) / BITMAP_ELEMENT_ALL_BITS
;
981 bitmap_element
*elt
= bitmap_find_bit (head
, start
);
983 /* If bitmap_find_bit returns zero, the current is the closest block
984 to the result. If the current is less than first index, find the
985 next one. Otherwise, just set elt to be current. */
990 if (head
->indx
< first_index
)
992 elt
= head
->current
->next
;
1003 while (elt
&& (elt
->indx
<= last_index
))
1005 bitmap_element
* next_elt
= elt
->next
;
1006 unsigned elt_start_bit
= (elt
->indx
) * BITMAP_ELEMENT_ALL_BITS
;
1007 unsigned elt_end_bit_plus1
= elt_start_bit
+ BITMAP_ELEMENT_ALL_BITS
;
1010 if (elt_start_bit
>= start
&& elt_end_bit_plus1
<= end_bit_plus1
)
1011 /* Get rid of the entire elt and go to the next one. */
1012 bitmap_element_free (head
, elt
);
1015 /* Going to have to knock out some bits in this elt. */
1016 unsigned int first_word_to_mod
;
1017 BITMAP_WORD first_mask
;
1018 unsigned int last_word_to_mod
;
1019 BITMAP_WORD last_mask
;
1023 if (elt_start_bit
<= start
)
1025 /* The first bit to turn off is somewhere inside this
1027 first_word_to_mod
= (start
- elt_start_bit
) / BITMAP_WORD_BITS
;
1029 /* This mask should have 1s in all bits >= start position. */
1031 (((BITMAP_WORD
) 1) << ((start
% BITMAP_WORD_BITS
))) - 1;
1032 first_mask
= ~first_mask
;
1036 /* The first bit to turn off is below this start of this elt. */
1037 first_word_to_mod
= 0;
1039 first_mask
= ~first_mask
;
1042 if (elt_end_bit_plus1
<= end_bit_plus1
)
1044 /* The last bit to turn off is beyond this elt. */
1045 last_word_to_mod
= BITMAP_ELEMENT_WORDS
- 1;
1047 last_mask
= ~last_mask
;
1051 /* The last bit to turn off is inside to this elt. */
1053 (end_bit_plus1
- elt_start_bit
) / BITMAP_WORD_BITS
;
1055 /* The last mask should have 1s below the end bit. */
1057 (((BITMAP_WORD
) 1) << (((end_bit_plus1
) % BITMAP_WORD_BITS
))) - 1;
1061 if (first_word_to_mod
== last_word_to_mod
)
1063 BITMAP_WORD mask
= first_mask
& last_mask
;
1064 elt
->bits
[first_word_to_mod
] &= ~mask
;
1068 elt
->bits
[first_word_to_mod
] &= ~first_mask
;
1069 for (i
= first_word_to_mod
+ 1; i
< last_word_to_mod
; i
++)
1071 elt
->bits
[last_word_to_mod
] &= ~last_mask
;
1073 for (i
= 0; i
< BITMAP_ELEMENT_WORDS
; i
++)
1079 /* Check to see if there are any bits left. */
1081 bitmap_element_free (head
, elt
);
1088 head
->current
= elt
;
1089 head
->indx
= head
->current
->indx
;
1096 bitmap_compl_and_into (bitmap a
, bitmap b
)
1098 bitmap_element
*a_elt
= a
->first
;
1099 bitmap_element
*b_elt
= b
->first
;
1100 bitmap_element
*a_prev
= NULL
;
1101 bitmap_element
*next
;
1103 gcc_assert (a
!= b
);
1105 if (bitmap_empty_p (a
))
1110 if (bitmap_empty_p (b
))
1116 while (a_elt
|| b_elt
)
1118 if (!b_elt
|| (a_elt
&& a_elt
->indx
< b_elt
->indx
))
1120 /* A is before B. Remove A */
1122 a_prev
= a_elt
->prev
;
1123 bitmap_element_free (a
, a_elt
);
1126 else if (!a_elt
|| b_elt
->indx
< a_elt
->indx
)
1128 /* B is before A. Copy B. */
1129 next
= bitmap_elt_insert_after (a
, a_prev
, b_elt
->indx
);
1130 memcpy (next
->bits
, b_elt
->bits
, sizeof (next
->bits
));
1132 b_elt
= b_elt
->next
;
1136 /* Matching elts, generate A = ~A & B. */
1138 BITMAP_WORD ior
= 0;
1140 for (ix
= BITMAP_ELEMENT_WORDS
; ix
--;)
1142 BITMAP_WORD cleared
= a_elt
->bits
[ix
] & b_elt
->bits
[ix
];
1143 BITMAP_WORD r
= b_elt
->bits
[ix
] ^ cleared
;
1145 a_elt
->bits
[ix
] = r
;
1150 bitmap_element_free (a
, a_elt
);
1154 b_elt
= b_elt
->next
;
1157 gcc_assert (!a
->current
== !a
->first
);
1158 gcc_assert (!a
->current
|| a
->indx
== a
->current
->indx
);
1162 /* DST = A | B. Return true if DST changes. */
1165 bitmap_ior (bitmap dst
, bitmap a
, bitmap b
)
1167 bitmap_element
*dst_elt
= dst
->first
;
1168 bitmap_element
*a_elt
= a
->first
;
1169 bitmap_element
*b_elt
= b
->first
;
1170 bitmap_element
*dst_prev
= NULL
;
1171 bool changed
= false;
1173 gcc_assert (dst
!= a
&& dst
!= b
);
1175 while (a_elt
|| b_elt
)
1177 if (a_elt
&& b_elt
&& a_elt
->indx
== b_elt
->indx
)
1179 /* Matching elts, generate A | B. */
1182 if (!changed
&& dst_elt
&& dst_elt
->indx
== a_elt
->indx
)
1184 for (ix
= BITMAP_ELEMENT_WORDS
; ix
--;)
1186 BITMAP_WORD r
= a_elt
->bits
[ix
] | b_elt
->bits
[ix
];
1188 if (r
!= dst_elt
->bits
[ix
])
1190 dst_elt
->bits
[ix
] = r
;
1199 dst_elt
= bitmap_elt_insert_after (dst
, dst_prev
, a_elt
->indx
);
1201 dst_elt
->indx
= a_elt
->indx
;
1202 for (ix
= BITMAP_ELEMENT_WORDS
; ix
--;)
1204 BITMAP_WORD r
= a_elt
->bits
[ix
] | b_elt
->bits
[ix
];
1206 dst_elt
->bits
[ix
] = r
;
1209 a_elt
= a_elt
->next
;
1210 b_elt
= b_elt
->next
;
1212 dst_elt
= dst_elt
->next
;
1216 /* Copy a single element. */
1217 bitmap_element
*src
;
1219 if (!b_elt
|| (a_elt
&& a_elt
->indx
< b_elt
->indx
))
1222 a_elt
= a_elt
->next
;
1227 b_elt
= b_elt
->next
;
1230 if (!changed
&& dst_elt
&& dst_elt
->indx
== src
->indx
)
1234 for (ix
= BITMAP_ELEMENT_WORDS
; ix
--;)
1235 if (src
->bits
[ix
] != dst_elt
->bits
[ix
])
1237 dst_elt
->bits
[ix
] = src
->bits
[ix
];
1245 dst_elt
= bitmap_elt_insert_after (dst
, dst_prev
, src
->indx
);
1247 dst_elt
->indx
= src
->indx
;
1248 memcpy (dst_elt
->bits
, src
->bits
, sizeof (dst_elt
->bits
));
1252 dst_elt
= dst_elt
->next
;
1259 bitmap_elt_clear_from (dst
, dst_elt
);
1261 gcc_assert (!dst
->current
== !dst
->first
);
1263 dst
->indx
= dst
->current
->indx
;
1267 /* A |= B. Return true if A changes. */
1270 bitmap_ior_into (bitmap a
, bitmap b
)
1272 bitmap_element
*a_elt
= a
->first
;
1273 bitmap_element
*b_elt
= b
->first
;
1274 bitmap_element
*a_prev
= NULL
;
1275 bool changed
= false;
1282 if (!a_elt
|| b_elt
->indx
< a_elt
->indx
)
1285 bitmap_element
*dst
= bitmap_elt_insert_after (a
, a_prev
, b_elt
->indx
);
1286 memcpy (dst
->bits
, b_elt
->bits
, sizeof (dst
->bits
));
1288 b_elt
= b_elt
->next
;
1291 else if (a_elt
->indx
< b_elt
->indx
)
1294 a_elt
= a_elt
->next
;
1298 /* Matching elts, generate A |= B. */
1302 for (ix
= BITMAP_ELEMENT_WORDS
; ix
--;)
1304 BITMAP_WORD r
= a_elt
->bits
[ix
] | b_elt
->bits
[ix
];
1306 a_elt
->bits
[ix
] = r
;
1309 for (ix
= BITMAP_ELEMENT_WORDS
; ix
--;)
1311 BITMAP_WORD r
= a_elt
->bits
[ix
] | b_elt
->bits
[ix
];
1313 if (a_elt
->bits
[ix
] != r
)
1316 a_elt
->bits
[ix
] = r
;
1319 b_elt
= b_elt
->next
;
1321 a_elt
= a_elt
->next
;
1324 gcc_assert (!a
->current
== !a
->first
);
1326 a
->indx
= a
->current
->indx
;
1333 bitmap_xor (bitmap dst
, bitmap a
, bitmap b
)
1335 bitmap_element
*dst_elt
= dst
->first
;
1336 bitmap_element
*a_elt
= a
->first
;
1337 bitmap_element
*b_elt
= b
->first
;
1338 bitmap_element
*dst_prev
= NULL
;
1340 gcc_assert (dst
!= a
&& dst
!= b
);
1347 while (a_elt
|| b_elt
)
1349 if (a_elt
&& b_elt
&& a_elt
->indx
== b_elt
->indx
)
1351 /* Matching elts, generate A ^ B. */
1353 BITMAP_WORD ior
= 0;
1356 dst_elt
= bitmap_elt_insert_after (dst
, dst_prev
, a_elt
->indx
);
1358 dst_elt
->indx
= a_elt
->indx
;
1359 for (ix
= BITMAP_ELEMENT_WORDS
; ix
--;)
1361 BITMAP_WORD r
= a_elt
->bits
[ix
] ^ b_elt
->bits
[ix
];
1364 dst_elt
->bits
[ix
] = r
;
1366 a_elt
= a_elt
->next
;
1367 b_elt
= b_elt
->next
;
1371 dst_elt
= dst_elt
->next
;
1376 /* Copy a single element. */
1377 bitmap_element
*src
;
1379 if (!b_elt
|| (a_elt
&& a_elt
->indx
< b_elt
->indx
))
1382 a_elt
= a_elt
->next
;
1387 b_elt
= b_elt
->next
;
1391 dst_elt
= bitmap_elt_insert_after (dst
, dst_prev
, src
->indx
);
1393 dst_elt
->indx
= src
->indx
;
1394 memcpy (dst_elt
->bits
, src
->bits
, sizeof (dst_elt
->bits
));
1396 dst_elt
= dst_elt
->next
;
1399 bitmap_elt_clear_from (dst
, dst_elt
);
1400 gcc_assert (!dst
->current
== !dst
->first
);
1402 dst
->indx
= dst
->current
->indx
;
1408 bitmap_xor_into (bitmap a
, bitmap b
)
1410 bitmap_element
*a_elt
= a
->first
;
1411 bitmap_element
*b_elt
= b
->first
;
1412 bitmap_element
*a_prev
= NULL
;
1422 if (!a_elt
|| b_elt
->indx
< a_elt
->indx
)
1425 bitmap_element
*dst
= bitmap_elt_insert_after (a
, a_prev
, b_elt
->indx
);
1426 memcpy (dst
->bits
, b_elt
->bits
, sizeof (dst
->bits
));
1428 b_elt
= b_elt
->next
;
1430 else if (a_elt
->indx
< b_elt
->indx
)
1433 a_elt
= a_elt
->next
;
1437 /* Matching elts, generate A ^= B. */
1439 BITMAP_WORD ior
= 0;
1440 bitmap_element
*next
= a_elt
->next
;
1442 for (ix
= BITMAP_ELEMENT_WORDS
; ix
--;)
1444 BITMAP_WORD r
= a_elt
->bits
[ix
] ^ b_elt
->bits
[ix
];
1447 a_elt
->bits
[ix
] = r
;
1449 b_elt
= b_elt
->next
;
1453 bitmap_element_free (a
, a_elt
);
1457 gcc_assert (!a
->current
== !a
->first
);
1459 a
->indx
= a
->current
->indx
;
1462 /* Return true if two bitmaps are identical.
1463 We do not bother with a check for pointer equality, as that never
1464 occurs in practice. */
1467 bitmap_equal_p (bitmap a
, bitmap b
)
1469 bitmap_element
*a_elt
;
1470 bitmap_element
*b_elt
;
1473 for (a_elt
= a
->first
, b_elt
= b
->first
;
1475 a_elt
= a_elt
->next
, b_elt
= b_elt
->next
)
1477 if (a_elt
->indx
!= b_elt
->indx
)
1479 for (ix
= BITMAP_ELEMENT_WORDS
; ix
--;)
1480 if (a_elt
->bits
[ix
] != b_elt
->bits
[ix
])
1483 return !a_elt
&& !b_elt
;
1486 /* Return true if A AND B is not empty. */
1489 bitmap_intersect_p (bitmap a
, bitmap b
)
1491 bitmap_element
*a_elt
;
1492 bitmap_element
*b_elt
;
1495 for (a_elt
= a
->first
, b_elt
= b
->first
;
1498 if (a_elt
->indx
< b_elt
->indx
)
1499 a_elt
= a_elt
->next
;
1500 else if (b_elt
->indx
< a_elt
->indx
)
1501 b_elt
= b_elt
->next
;
1504 for (ix
= BITMAP_ELEMENT_WORDS
; ix
--;)
1505 if (a_elt
->bits
[ix
] & b_elt
->bits
[ix
])
1507 a_elt
= a_elt
->next
;
1508 b_elt
= b_elt
->next
;
1514 /* Return true if A AND NOT B is not empty. */
1517 bitmap_intersect_compl_p (bitmap a
, bitmap b
)
1519 bitmap_element
*a_elt
;
1520 bitmap_element
*b_elt
;
1522 for (a_elt
= a
->first
, b_elt
= b
->first
;
1525 if (a_elt
->indx
< b_elt
->indx
)
1527 else if (b_elt
->indx
< a_elt
->indx
)
1528 b_elt
= b_elt
->next
;
1531 for (ix
= BITMAP_ELEMENT_WORDS
; ix
--;)
1532 if (a_elt
->bits
[ix
] & ~b_elt
->bits
[ix
])
1534 a_elt
= a_elt
->next
;
1535 b_elt
= b_elt
->next
;
1538 return a_elt
!= NULL
;
1542 /* DST = A | (FROM1 & ~FROM2). Return true if DST changes. */
1545 bitmap_ior_and_compl (bitmap dst
, bitmap a
, bitmap from1
, bitmap from2
)
1550 bitmap_initialize (&tmp
, &bitmap_default_obstack
);
1551 bitmap_and_compl (&tmp
, from1
, from2
);
1552 changed
= bitmap_ior (dst
, a
, &tmp
);
1553 bitmap_clear (&tmp
);
1558 /* A |= (FROM1 & ~FROM2). Return true if A changes. */
1561 bitmap_ior_and_compl_into (bitmap a
, bitmap from1
, bitmap from2
)
1566 bitmap_initialize (&tmp
, &bitmap_default_obstack
);
1567 bitmap_and_compl (&tmp
, from1
, from2
);
1568 changed
= bitmap_ior_into (a
, &tmp
);
1569 bitmap_clear (&tmp
);
1574 /* Debugging function to print out the contents of a bitmap. */
1577 debug_bitmap_file (FILE *file
, bitmap head
)
1579 bitmap_element
*ptr
;
1581 fprintf (file
, "\nfirst = %p current = %p indx = %u\n",
1582 (void *) head
->first
, (void *) head
->current
, head
->indx
);
1584 for (ptr
= head
->first
; ptr
; ptr
= ptr
->next
)
1586 unsigned int i
, j
, col
= 26;
1588 fprintf (file
, "\t%p next = %p prev = %p indx = %u\n\t\tbits = {",
1589 (void*) ptr
, (void*) ptr
->next
, (void*) ptr
->prev
, ptr
->indx
);
1591 for (i
= 0; i
< BITMAP_ELEMENT_WORDS
; i
++)
1592 for (j
= 0; j
< BITMAP_WORD_BITS
; j
++)
1593 if ((ptr
->bits
[i
] >> j
) & 1)
1597 fprintf (file
, "\n\t\t\t");
1601 fprintf (file
, " %u", (ptr
->indx
* BITMAP_ELEMENT_ALL_BITS
1602 + i
* BITMAP_WORD_BITS
+ j
));
1606 fprintf (file
, " }\n");
1610 /* Function to be called from the debugger to print the contents
1614 debug_bitmap (bitmap head
)
1616 debug_bitmap_file (stdout
, head
);
1619 /* Function to print out the contents of a bitmap. Unlike debug_bitmap_file,
1620 it does not print anything but the bits. */
1623 bitmap_print (FILE *file
, bitmap head
, const char *prefix
, const char *suffix
)
1625 const char *comma
= "";
1629 fputs (prefix
, file
);
1630 EXECUTE_IF_SET_IN_BITMAP (head
, 0, i
, bi
)
1632 fprintf (file
, "%s%d", comma
, i
);
1635 fputs (suffix
, file
);
1637 #ifdef GATHER_STATISTICS
1640 /* Used to accumulate statistics about bitmap sizes. */
1647 /* Called via htab_traverse. Output bitmap descriptor pointed out by SLOT
1648 and update statistics. */
1650 print_statistics (void **slot
, void *b
)
1652 struct bitmap_descriptor
*d
= (struct bitmap_descriptor
*) *slot
;
1653 struct output_info
*i
= (struct output_info
*) b
;
1658 const char *s1
= d
->file
;
1660 while ((s2
= strstr (s1
, "gcc/")))
1662 sprintf (s
, "%s:%i (%s)", s1
, d
->line
, d
->function
);
1664 fprintf (stderr
, "%-41s %6d %10d %10d %10d %10d\n", s
,
1665 d
->created
, d
->allocated
, d
->peak
, d
->current
, d
->nsearches
);
1666 i
->size
+= d
->allocated
;
1667 i
->count
+= d
->created
;
1672 /* Output per-bitmap memory usage statistics. */
1674 dump_bitmap_statistics (void)
1676 #ifdef GATHER_STATISTICS
1677 struct output_info info
;
1679 if (!bitmap_desc_hash
)
1682 fprintf (stderr
, "\nBitmap Overall "
1683 "Allocated Peak Leak searched "
1685 fprintf (stderr
, "---------------------------------------------------------------------------------\n");
1688 htab_traverse (bitmap_desc_hash
, print_statistics
, &info
);
1689 fprintf (stderr
, "---------------------------------------------------------------------------------\n");
1690 fprintf (stderr
, "%-40s %7d %10d\n",
1691 "Total", info
.count
, info
.size
);
1692 fprintf (stderr
, "---------------------------------------------------------------------------------\n");
1696 /* Compute hash of bitmap (for purposes of hashing). */
1698 bitmap_hash (bitmap head
)
1700 bitmap_element
*ptr
;
1701 BITMAP_WORD hash
= 0;
1704 for (ptr
= head
->first
; ptr
; ptr
= ptr
->next
)
1707 for (ix
= 0; ix
!= BITMAP_ELEMENT_WORDS
; ix
++)
1708 hash
^= ptr
->bits
[ix
];
1710 return (hashval_t
)hash
;
1713 #include "gt-bitmap.h"