1 /* Functions to support general ended bitmaps.
2 Copyright (C) 1997, 1998, 1999, 2000, 2001, 2003, 2004, 2005,
3 2006, 2007 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 /* Ensure that dst->current is valid. */
801 dst
->current
= dst
->first
;
802 bitmap_elt_clear_from (dst
, dst_elt
);
803 gcc_assert (!dst
->current
== !dst
->first
);
805 dst
->indx
= dst
->current
->indx
;
811 bitmap_and_into (bitmap a
, bitmap b
)
813 bitmap_element
*a_elt
= a
->first
;
814 bitmap_element
*b_elt
= b
->first
;
815 bitmap_element
*next
;
820 while (a_elt
&& b_elt
)
822 if (a_elt
->indx
< b_elt
->indx
)
825 bitmap_element_free (a
, a_elt
);
828 else if (b_elt
->indx
< a_elt
->indx
)
832 /* Matching elts, generate A &= B. */
836 for (ix
= BITMAP_ELEMENT_WORDS
; ix
--;)
838 BITMAP_WORD r
= a_elt
->bits
[ix
] & b_elt
->bits
[ix
];
845 bitmap_element_free (a
, a_elt
);
850 bitmap_elt_clear_from (a
, a_elt
);
851 gcc_assert (!a
->current
== !a
->first
);
852 gcc_assert (!a
->current
|| a
->indx
== a
->current
->indx
);
856 /* Insert an element equal to SRC_ELT after DST_PREV, overwriting DST_ELT
857 if non-NULL. CHANGED is true if the destination bitmap had already been
858 changed; the new value of CHANGED is returned. */
861 bitmap_elt_copy (bitmap dst
, bitmap_element
*dst_elt
, bitmap_element
*dst_prev
,
862 bitmap_element
*src_elt
, bool changed
)
864 if (!changed
&& dst_elt
&& dst_elt
->indx
== src_elt
->indx
)
868 for (ix
= BITMAP_ELEMENT_WORDS
; ix
--;)
869 if (src_elt
->bits
[ix
] != dst_elt
->bits
[ix
])
871 dst_elt
->bits
[ix
] = src_elt
->bits
[ix
];
879 dst_elt
= bitmap_elt_insert_after (dst
, dst_prev
, src_elt
->indx
);
881 dst_elt
->indx
= src_elt
->indx
;
882 memcpy (dst_elt
->bits
, src_elt
->bits
, sizeof (dst_elt
->bits
));
892 bitmap_and_compl (bitmap dst
, bitmap a
, bitmap b
)
894 bitmap_element
*dst_elt
= dst
->first
;
895 bitmap_element
*a_elt
= a
->first
;
896 bitmap_element
*b_elt
= b
->first
;
897 bitmap_element
*dst_prev
= NULL
;
898 bitmap_element
**dst_prev_pnext
= &dst
->first
;
899 bool changed
= false;
901 gcc_assert (dst
!= a
&& dst
!= b
);
905 changed
= !bitmap_empty_p (dst
);
912 while (b_elt
&& b_elt
->indx
< a_elt
->indx
)
915 if (!b_elt
|| b_elt
->indx
> a_elt
->indx
)
917 changed
= bitmap_elt_copy (dst
, dst_elt
, dst_prev
, a_elt
, changed
);
918 dst_prev
= *dst_prev_pnext
;
919 dst_prev_pnext
= &dst_prev
->next
;
920 dst_elt
= *dst_prev_pnext
;
926 /* Matching elts, generate A & ~B. */
930 if (!changed
&& dst_elt
&& dst_elt
->indx
== a_elt
->indx
)
932 for (ix
= BITMAP_ELEMENT_WORDS
; ix
--;)
934 BITMAP_WORD r
= a_elt
->bits
[ix
] & ~b_elt
->bits
[ix
];
936 if (dst_elt
->bits
[ix
] != r
)
939 dst_elt
->bits
[ix
] = r
;
947 if (!dst_elt
|| dst_elt
->indx
> a_elt
->indx
)
949 dst_elt
= bitmap_elt_insert_after (dst
, dst_prev
, a_elt
->indx
);
954 dst_elt
->indx
= a_elt
->indx
;
958 for (ix
= BITMAP_ELEMENT_WORDS
; ix
--;)
960 BITMAP_WORD r
= a_elt
->bits
[ix
] & ~b_elt
->bits
[ix
];
962 dst_elt
->bits
[ix
] = r
;
970 changed
|= !new_element
;
971 bitmap_element_free (dst
, dst_elt
);
972 dst_elt
= *dst_prev_pnext
;
978 dst_prev
= *dst_prev_pnext
;
979 dst_prev_pnext
= &dst_prev
->next
;
980 dst_elt
= *dst_prev_pnext
;
987 /* Ensure that dst->current is valid. */
988 dst
->current
= dst
->first
;
993 bitmap_elt_clear_from (dst
, dst_elt
);
995 gcc_assert (!dst
->current
== !dst
->first
);
997 dst
->indx
= dst
->current
->indx
;
1002 /* A &= ~B. Returns true if A changes */
1005 bitmap_and_compl_into (bitmap a
, bitmap b
)
1007 bitmap_element
*a_elt
= a
->first
;
1008 bitmap_element
*b_elt
= b
->first
;
1009 bitmap_element
*next
;
1010 BITMAP_WORD changed
= 0;
1014 if (bitmap_empty_p (a
))
1023 while (a_elt
&& b_elt
)
1025 if (a_elt
->indx
< b_elt
->indx
)
1026 a_elt
= a_elt
->next
;
1027 else if (b_elt
->indx
< a_elt
->indx
)
1028 b_elt
= b_elt
->next
;
1031 /* Matching elts, generate A &= ~B. */
1033 BITMAP_WORD ior
= 0;
1035 for (ix
= BITMAP_ELEMENT_WORDS
; ix
--;)
1037 BITMAP_WORD cleared
= a_elt
->bits
[ix
] & b_elt
->bits
[ix
];
1038 BITMAP_WORD r
= a_elt
->bits
[ix
] ^ cleared
;
1040 a_elt
->bits
[ix
] = r
;
1046 bitmap_element_free (a
, a_elt
);
1048 b_elt
= b_elt
->next
;
1051 gcc_assert (!a
->current
== !a
->first
);
1052 gcc_assert (!a
->current
|| a
->indx
== a
->current
->indx
);
1053 return changed
!= 0;
1056 /* Set COUNT bits from START in HEAD. */
1058 bitmap_set_range (bitmap head
, unsigned int start
, unsigned int count
)
1060 unsigned int first_index
, end_bit_plus1
, last_index
;
1061 bitmap_element
*elt
, *elt_prev
;
1067 first_index
= start
/ BITMAP_ELEMENT_ALL_BITS
;
1068 end_bit_plus1
= start
+ count
;
1069 last_index
= (end_bit_plus1
- 1) / BITMAP_ELEMENT_ALL_BITS
;
1070 elt
= bitmap_find_bit (head
, start
);
1072 /* If bitmap_find_bit returns zero, the current is the closest block
1073 to the result. Otherwise, just use bitmap_element_allocate to
1074 ensure ELT is set; in the loop below, ELT == NULL means "insert
1075 at the end of the bitmap". */
1078 elt
= bitmap_element_allocate (head
);
1079 elt
->indx
= first_index
;
1080 bitmap_element_link (head
, elt
);
1083 gcc_assert (elt
->indx
== first_index
);
1084 elt_prev
= elt
->prev
;
1085 for (i
= first_index
; i
<= last_index
; i
++)
1087 unsigned elt_start_bit
= i
* BITMAP_ELEMENT_ALL_BITS
;
1088 unsigned elt_end_bit_plus1
= elt_start_bit
+ BITMAP_ELEMENT_ALL_BITS
;
1090 unsigned int first_word_to_mod
;
1091 BITMAP_WORD first_mask
;
1092 unsigned int last_word_to_mod
;
1093 BITMAP_WORD last_mask
;
1096 if (!elt
|| elt
->indx
!= i
)
1097 elt
= bitmap_elt_insert_after (head
, elt_prev
, i
);
1099 if (elt_start_bit
<= start
)
1101 /* The first bit to turn on is somewhere inside this
1103 first_word_to_mod
= (start
- elt_start_bit
) / BITMAP_WORD_BITS
;
1105 /* This mask should have 1s in all bits >= start position. */
1107 (((BITMAP_WORD
) 1) << ((start
% BITMAP_WORD_BITS
))) - 1;
1108 first_mask
= ~first_mask
;
1112 /* The first bit to turn on is below this start of this elt. */
1113 first_word_to_mod
= 0;
1114 first_mask
= ~(BITMAP_WORD
) 0;
1117 if (elt_end_bit_plus1
<= end_bit_plus1
)
1119 /* The last bit to turn on is beyond this elt. */
1120 last_word_to_mod
= BITMAP_ELEMENT_WORDS
- 1;
1121 last_mask
= ~(BITMAP_WORD
) 0;
1125 /* The last bit to turn on is inside to this elt. */
1127 (end_bit_plus1
- elt_start_bit
) / BITMAP_WORD_BITS
;
1129 /* The last mask should have 1s below the end bit. */
1131 (((BITMAP_WORD
) 1) << ((end_bit_plus1
% BITMAP_WORD_BITS
))) - 1;
1134 if (first_word_to_mod
== last_word_to_mod
)
1136 BITMAP_WORD mask
= first_mask
& last_mask
;
1137 elt
->bits
[first_word_to_mod
] |= mask
;
1141 elt
->bits
[first_word_to_mod
] |= first_mask
;
1142 if (BITMAP_ELEMENT_WORDS
> 2)
1143 for (ix
= first_word_to_mod
+ 1; ix
< last_word_to_mod
; ix
++)
1144 elt
->bits
[ix
] = ~(BITMAP_WORD
) 0;
1145 elt
->bits
[last_word_to_mod
] |= last_mask
;
1152 head
->current
= elt
? elt
: elt_prev
;
1153 head
->indx
= head
->current
->indx
;
1156 /* Clear COUNT bits from START in HEAD. */
1158 bitmap_clear_range (bitmap head
, unsigned int start
, unsigned int count
)
1160 unsigned int first_index
, end_bit_plus1
, last_index
;
1161 bitmap_element
*elt
;
1166 first_index
= start
/ BITMAP_ELEMENT_ALL_BITS
;
1167 end_bit_plus1
= start
+ count
;
1168 last_index
= (end_bit_plus1
- 1) / BITMAP_ELEMENT_ALL_BITS
;
1169 elt
= bitmap_find_bit (head
, start
);
1171 /* If bitmap_find_bit returns zero, the current is the closest block
1172 to the result. If the current is less than first index, find the
1173 next one. Otherwise, just set elt to be current. */
1178 if (head
->indx
< first_index
)
1180 elt
= head
->current
->next
;
1185 elt
= head
->current
;
1191 while (elt
&& (elt
->indx
<= last_index
))
1193 bitmap_element
* next_elt
= elt
->next
;
1194 unsigned elt_start_bit
= (elt
->indx
) * BITMAP_ELEMENT_ALL_BITS
;
1195 unsigned elt_end_bit_plus1
= elt_start_bit
+ BITMAP_ELEMENT_ALL_BITS
;
1198 if (elt_start_bit
>= start
&& elt_end_bit_plus1
<= end_bit_plus1
)
1199 /* Get rid of the entire elt and go to the next one. */
1200 bitmap_element_free (head
, elt
);
1203 /* Going to have to knock out some bits in this elt. */
1204 unsigned int first_word_to_mod
;
1205 BITMAP_WORD first_mask
;
1206 unsigned int last_word_to_mod
;
1207 BITMAP_WORD last_mask
;
1211 if (elt_start_bit
<= start
)
1213 /* The first bit to turn off is somewhere inside this
1215 first_word_to_mod
= (start
- elt_start_bit
) / BITMAP_WORD_BITS
;
1217 /* This mask should have 1s in all bits >= start position. */
1219 (((BITMAP_WORD
) 1) << ((start
% BITMAP_WORD_BITS
))) - 1;
1220 first_mask
= ~first_mask
;
1224 /* The first bit to turn off is below this start of this elt. */
1225 first_word_to_mod
= 0;
1227 first_mask
= ~first_mask
;
1230 if (elt_end_bit_plus1
<= end_bit_plus1
)
1232 /* The last bit to turn off is beyond this elt. */
1233 last_word_to_mod
= BITMAP_ELEMENT_WORDS
- 1;
1235 last_mask
= ~last_mask
;
1239 /* The last bit to turn off is inside to this elt. */
1241 (end_bit_plus1
- elt_start_bit
) / BITMAP_WORD_BITS
;
1243 /* The last mask should have 1s below the end bit. */
1245 (((BITMAP_WORD
) 1) << (((end_bit_plus1
) % BITMAP_WORD_BITS
))) - 1;
1249 if (first_word_to_mod
== last_word_to_mod
)
1251 BITMAP_WORD mask
= first_mask
& last_mask
;
1252 elt
->bits
[first_word_to_mod
] &= ~mask
;
1256 elt
->bits
[first_word_to_mod
] &= ~first_mask
;
1257 if (BITMAP_ELEMENT_WORDS
> 2)
1258 for (i
= first_word_to_mod
+ 1; i
< last_word_to_mod
; i
++)
1260 elt
->bits
[last_word_to_mod
] &= ~last_mask
;
1262 for (i
= 0; i
< BITMAP_ELEMENT_WORDS
; i
++)
1268 /* Check to see if there are any bits left. */
1270 bitmap_element_free (head
, elt
);
1277 head
->current
= elt
;
1278 head
->indx
= head
->current
->indx
;
1285 bitmap_compl_and_into (bitmap a
, bitmap b
)
1287 bitmap_element
*a_elt
= a
->first
;
1288 bitmap_element
*b_elt
= b
->first
;
1289 bitmap_element
*a_prev
= NULL
;
1290 bitmap_element
*next
;
1292 gcc_assert (a
!= b
);
1294 if (bitmap_empty_p (a
))
1299 if (bitmap_empty_p (b
))
1305 while (a_elt
|| b_elt
)
1307 if (!b_elt
|| (a_elt
&& a_elt
->indx
< b_elt
->indx
))
1309 /* A is before B. Remove A */
1311 a_prev
= a_elt
->prev
;
1312 bitmap_element_free (a
, a_elt
);
1315 else if (!a_elt
|| b_elt
->indx
< a_elt
->indx
)
1317 /* B is before A. Copy B. */
1318 next
= bitmap_elt_insert_after (a
, a_prev
, b_elt
->indx
);
1319 memcpy (next
->bits
, b_elt
->bits
, sizeof (next
->bits
));
1321 b_elt
= b_elt
->next
;
1325 /* Matching elts, generate A = ~A & B. */
1327 BITMAP_WORD ior
= 0;
1329 for (ix
= BITMAP_ELEMENT_WORDS
; ix
--;)
1331 BITMAP_WORD cleared
= a_elt
->bits
[ix
] & b_elt
->bits
[ix
];
1332 BITMAP_WORD r
= b_elt
->bits
[ix
] ^ cleared
;
1334 a_elt
->bits
[ix
] = r
;
1339 bitmap_element_free (a
, a_elt
);
1343 b_elt
= b_elt
->next
;
1346 gcc_assert (!a
->current
== !a
->first
);
1347 gcc_assert (!a
->current
|| a
->indx
== a
->current
->indx
);
1352 /* Insert an element corresponding to A_ELT | B_ELT after DST_PREV,
1353 overwriting DST_ELT if non-NULL. CHANGED is true if the destination bitmap
1354 had already been changed; the new value of CHANGED is returned. */
1357 bitmap_elt_ior (bitmap dst
, bitmap_element
*dst_elt
, bitmap_element
*dst_prev
,
1358 bitmap_element
*a_elt
, bitmap_element
*b_elt
,
1361 gcc_assert (a_elt
|| b_elt
);
1363 if (a_elt
&& b_elt
&& a_elt
->indx
== b_elt
->indx
)
1365 /* Matching elts, generate A | B. */
1368 if (!changed
&& dst_elt
&& dst_elt
->indx
== a_elt
->indx
)
1370 for (ix
= BITMAP_ELEMENT_WORDS
; ix
--;)
1372 BITMAP_WORD r
= a_elt
->bits
[ix
] | b_elt
->bits
[ix
];
1373 if (r
!= dst_elt
->bits
[ix
])
1375 dst_elt
->bits
[ix
] = r
;
1384 dst_elt
= bitmap_elt_insert_after (dst
, dst_prev
, a_elt
->indx
);
1386 dst_elt
->indx
= a_elt
->indx
;
1387 for (ix
= BITMAP_ELEMENT_WORDS
; ix
--;)
1389 BITMAP_WORD r
= a_elt
->bits
[ix
] | b_elt
->bits
[ix
];
1390 dst_elt
->bits
[ix
] = r
;
1396 /* Copy a single element. */
1397 bitmap_element
*src
;
1399 if (!b_elt
|| (a_elt
&& a_elt
->indx
< b_elt
->indx
))
1405 changed
= bitmap_elt_copy (dst
, dst_elt
, dst_prev
, src
, changed
);
1411 /* DST = A | B. Return true if DST changes. */
1414 bitmap_ior (bitmap dst
, bitmap a
, bitmap b
)
1416 bitmap_element
*dst_elt
= dst
->first
;
1417 bitmap_element
*a_elt
= a
->first
;
1418 bitmap_element
*b_elt
= b
->first
;
1419 bitmap_element
*dst_prev
= NULL
;
1420 bitmap_element
**dst_prev_pnext
= &dst
->first
;
1421 bool changed
= false;
1423 gcc_assert (dst
!= a
&& dst
!= b
);
1425 while (a_elt
|| b_elt
)
1427 changed
= bitmap_elt_ior (dst
, dst_elt
, dst_prev
, a_elt
, b_elt
, changed
);
1429 if (a_elt
&& b_elt
&& a_elt
->indx
== b_elt
->indx
)
1431 a_elt
= a_elt
->next
;
1432 b_elt
= b_elt
->next
;
1436 if (a_elt
&& (!b_elt
|| a_elt
->indx
<= b_elt
->indx
))
1437 a_elt
= a_elt
->next
;
1438 else if (b_elt
&& (!a_elt
|| b_elt
->indx
<= a_elt
->indx
))
1439 b_elt
= b_elt
->next
;
1442 dst_prev
= *dst_prev_pnext
;
1443 dst_prev_pnext
= &dst_prev
->next
;
1444 dst_elt
= *dst_prev_pnext
;
1450 bitmap_elt_clear_from (dst
, dst_elt
);
1452 gcc_assert (!dst
->current
== !dst
->first
);
1454 dst
->indx
= dst
->current
->indx
;
1458 /* A |= B. Return true if A changes. */
1461 bitmap_ior_into (bitmap a
, bitmap b
)
1463 bitmap_element
*a_elt
= a
->first
;
1464 bitmap_element
*b_elt
= b
->first
;
1465 bitmap_element
*a_prev
= NULL
;
1466 bitmap_element
**a_prev_pnext
= &a
->first
;
1467 bool changed
= false;
1474 /* If A lags behind B, just advance it. */
1475 if (!a_elt
|| a_elt
->indx
== b_elt
->indx
)
1477 changed
= bitmap_elt_ior (a
, a_elt
, a_prev
, a_elt
, b_elt
, changed
);
1478 b_elt
= b_elt
->next
;
1480 else if (a_elt
->indx
> b_elt
->indx
)
1482 changed
= bitmap_elt_copy (a
, NULL
, a_prev
, b_elt
, changed
);
1483 b_elt
= b_elt
->next
;
1486 a_prev
= *a_prev_pnext
;
1487 a_prev_pnext
= &a_prev
->next
;
1488 a_elt
= *a_prev_pnext
;
1491 gcc_assert (!a
->current
== !a
->first
);
1493 a
->indx
= a
->current
->indx
;
1500 bitmap_xor (bitmap dst
, bitmap a
, bitmap b
)
1502 bitmap_element
*dst_elt
= dst
->first
;
1503 bitmap_element
*a_elt
= a
->first
;
1504 bitmap_element
*b_elt
= b
->first
;
1505 bitmap_element
*dst_prev
= NULL
;
1507 gcc_assert (dst
!= a
&& dst
!= b
);
1514 while (a_elt
|| b_elt
)
1516 if (a_elt
&& b_elt
&& a_elt
->indx
== b_elt
->indx
)
1518 /* Matching elts, generate A ^ B. */
1520 BITMAP_WORD ior
= 0;
1523 dst_elt
= bitmap_elt_insert_after (dst
, dst_prev
, a_elt
->indx
);
1525 dst_elt
->indx
= a_elt
->indx
;
1526 for (ix
= BITMAP_ELEMENT_WORDS
; ix
--;)
1528 BITMAP_WORD r
= a_elt
->bits
[ix
] ^ b_elt
->bits
[ix
];
1531 dst_elt
->bits
[ix
] = r
;
1533 a_elt
= a_elt
->next
;
1534 b_elt
= b_elt
->next
;
1538 dst_elt
= dst_elt
->next
;
1543 /* Copy a single element. */
1544 bitmap_element
*src
;
1546 if (!b_elt
|| (a_elt
&& a_elt
->indx
< b_elt
->indx
))
1549 a_elt
= a_elt
->next
;
1554 b_elt
= b_elt
->next
;
1558 dst_elt
= bitmap_elt_insert_after (dst
, dst_prev
, src
->indx
);
1560 dst_elt
->indx
= src
->indx
;
1561 memcpy (dst_elt
->bits
, src
->bits
, sizeof (dst_elt
->bits
));
1563 dst_elt
= dst_elt
->next
;
1566 /* Ensure that dst->current is valid. */
1567 dst
->current
= dst
->first
;
1568 bitmap_elt_clear_from (dst
, dst_elt
);
1569 gcc_assert (!dst
->current
== !dst
->first
);
1571 dst
->indx
= dst
->current
->indx
;
1577 bitmap_xor_into (bitmap a
, bitmap b
)
1579 bitmap_element
*a_elt
= a
->first
;
1580 bitmap_element
*b_elt
= b
->first
;
1581 bitmap_element
*a_prev
= NULL
;
1591 if (!a_elt
|| b_elt
->indx
< a_elt
->indx
)
1594 bitmap_element
*dst
= bitmap_elt_insert_after (a
, a_prev
, b_elt
->indx
);
1595 memcpy (dst
->bits
, b_elt
->bits
, sizeof (dst
->bits
));
1597 b_elt
= b_elt
->next
;
1599 else if (a_elt
->indx
< b_elt
->indx
)
1602 a_elt
= a_elt
->next
;
1606 /* Matching elts, generate A ^= B. */
1608 BITMAP_WORD ior
= 0;
1609 bitmap_element
*next
= a_elt
->next
;
1611 for (ix
= BITMAP_ELEMENT_WORDS
; ix
--;)
1613 BITMAP_WORD r
= a_elt
->bits
[ix
] ^ b_elt
->bits
[ix
];
1616 a_elt
->bits
[ix
] = r
;
1618 b_elt
= b_elt
->next
;
1622 bitmap_element_free (a
, a_elt
);
1626 gcc_assert (!a
->current
== !a
->first
);
1628 a
->indx
= a
->current
->indx
;
1631 /* Return true if two bitmaps are identical.
1632 We do not bother with a check for pointer equality, as that never
1633 occurs in practice. */
1636 bitmap_equal_p (bitmap a
, bitmap b
)
1638 bitmap_element
*a_elt
;
1639 bitmap_element
*b_elt
;
1642 for (a_elt
= a
->first
, b_elt
= b
->first
;
1644 a_elt
= a_elt
->next
, b_elt
= b_elt
->next
)
1646 if (a_elt
->indx
!= b_elt
->indx
)
1648 for (ix
= BITMAP_ELEMENT_WORDS
; ix
--;)
1649 if (a_elt
->bits
[ix
] != b_elt
->bits
[ix
])
1652 return !a_elt
&& !b_elt
;
1655 /* Return true if A AND B is not empty. */
1658 bitmap_intersect_p (bitmap a
, bitmap b
)
1660 bitmap_element
*a_elt
;
1661 bitmap_element
*b_elt
;
1664 for (a_elt
= a
->first
, b_elt
= b
->first
;
1667 if (a_elt
->indx
< b_elt
->indx
)
1668 a_elt
= a_elt
->next
;
1669 else if (b_elt
->indx
< a_elt
->indx
)
1670 b_elt
= b_elt
->next
;
1673 for (ix
= BITMAP_ELEMENT_WORDS
; ix
--;)
1674 if (a_elt
->bits
[ix
] & b_elt
->bits
[ix
])
1676 a_elt
= a_elt
->next
;
1677 b_elt
= b_elt
->next
;
1683 /* Return true if A AND NOT B is not empty. */
1686 bitmap_intersect_compl_p (bitmap a
, bitmap b
)
1688 bitmap_element
*a_elt
;
1689 bitmap_element
*b_elt
;
1691 for (a_elt
= a
->first
, b_elt
= b
->first
;
1694 if (a_elt
->indx
< b_elt
->indx
)
1696 else if (b_elt
->indx
< a_elt
->indx
)
1697 b_elt
= b_elt
->next
;
1700 for (ix
= BITMAP_ELEMENT_WORDS
; ix
--;)
1701 if (a_elt
->bits
[ix
] & ~b_elt
->bits
[ix
])
1703 a_elt
= a_elt
->next
;
1704 b_elt
= b_elt
->next
;
1707 return a_elt
!= NULL
;
1711 /* DST = A | (FROM1 & ~FROM2). Return true if DST changes. */
1714 bitmap_ior_and_compl (bitmap dst
, bitmap a
, bitmap b
, bitmap kill
)
1716 bool changed
= false;
1718 bitmap_element
*dst_elt
= dst
->first
;
1719 bitmap_element
*a_elt
= a
->first
;
1720 bitmap_element
*b_elt
= b
->first
;
1721 bitmap_element
*kill_elt
= kill
->first
;
1722 bitmap_element
*dst_prev
= NULL
;
1723 bitmap_element
**dst_prev_pnext
= &dst
->first
;
1725 gcc_assert (dst
!= a
&& dst
!= b
&& dst
!= kill
);
1727 /* Special cases. We don't bother checking for bitmap_equal_p (b, kill). */
1728 if (b
== kill
|| bitmap_empty_p (b
))
1730 changed
= !bitmap_equal_p (dst
, a
);
1732 bitmap_copy (dst
, a
);
1735 if (bitmap_empty_p (kill
))
1736 return bitmap_ior (dst
, a
, b
);
1737 if (bitmap_empty_p (a
))
1738 return bitmap_and_compl (dst
, b
, kill
);
1740 while (a_elt
|| b_elt
)
1742 bool new_element
= false;
1745 while (kill_elt
&& kill_elt
->indx
< b_elt
->indx
)
1746 kill_elt
= kill_elt
->next
;
1748 if (b_elt
&& kill_elt
&& kill_elt
->indx
== b_elt
->indx
1749 && (!a_elt
|| a_elt
->indx
>= b_elt
->indx
))
1751 bitmap_element tmp_elt
;
1754 BITMAP_WORD ior
= 0;
1755 tmp_elt
.indx
= b_elt
->indx
;
1756 for (ix
= BITMAP_ELEMENT_WORDS
; ix
--;)
1758 BITMAP_WORD r
= b_elt
->bits
[ix
] & ~kill_elt
->bits
[ix
];
1760 tmp_elt
.bits
[ix
] = r
;
1765 changed
= bitmap_elt_ior (dst
, dst_elt
, dst_prev
,
1766 a_elt
, &tmp_elt
, changed
);
1768 if (a_elt
&& a_elt
->indx
== b_elt
->indx
)
1769 a_elt
= a_elt
->next
;
1772 b_elt
= b_elt
->next
;
1773 kill_elt
= kill_elt
->next
;
1777 changed
= bitmap_elt_ior (dst
, dst_elt
, dst_prev
,
1778 a_elt
, b_elt
, changed
);
1781 if (a_elt
&& b_elt
&& a_elt
->indx
== b_elt
->indx
)
1783 a_elt
= a_elt
->next
;
1784 b_elt
= b_elt
->next
;
1788 if (a_elt
&& (!b_elt
|| a_elt
->indx
<= b_elt
->indx
))
1789 a_elt
= a_elt
->next
;
1790 else if (b_elt
&& (!a_elt
|| b_elt
->indx
<= a_elt
->indx
))
1791 b_elt
= b_elt
->next
;
1797 dst_prev
= *dst_prev_pnext
;
1798 dst_prev_pnext
= &dst_prev
->next
;
1799 dst_elt
= *dst_prev_pnext
;
1806 bitmap_elt_clear_from (dst
, dst_elt
);
1808 gcc_assert (!dst
->current
== !dst
->first
);
1810 dst
->indx
= dst
->current
->indx
;
1815 /* A |= (FROM1 & ~FROM2). Return true if A changes. */
1818 bitmap_ior_and_compl_into (bitmap a
, bitmap from1
, bitmap from2
)
1823 bitmap_initialize (&tmp
, &bitmap_default_obstack
);
1824 bitmap_and_compl (&tmp
, from1
, from2
);
1825 changed
= bitmap_ior_into (a
, &tmp
);
1826 bitmap_clear (&tmp
);
1832 /* Debugging function to print out the contents of a bitmap. */
1835 debug_bitmap_file (FILE *file
, bitmap head
)
1837 bitmap_element
*ptr
;
1839 fprintf (file
, "\nfirst = %p current = %p indx = %u\n",
1840 (void *) head
->first
, (void *) head
->current
, head
->indx
);
1842 for (ptr
= head
->first
; ptr
; ptr
= ptr
->next
)
1844 unsigned int i
, j
, col
= 26;
1846 fprintf (file
, "\t%p next = %p prev = %p indx = %u\n\t\tbits = {",
1847 (void*) ptr
, (void*) ptr
->next
, (void*) ptr
->prev
, ptr
->indx
);
1849 for (i
= 0; i
< BITMAP_ELEMENT_WORDS
; i
++)
1850 for (j
= 0; j
< BITMAP_WORD_BITS
; j
++)
1851 if ((ptr
->bits
[i
] >> j
) & 1)
1855 fprintf (file
, "\n\t\t\t");
1859 fprintf (file
, " %u", (ptr
->indx
* BITMAP_ELEMENT_ALL_BITS
1860 + i
* BITMAP_WORD_BITS
+ j
));
1864 fprintf (file
, " }\n");
1868 /* Function to be called from the debugger to print the contents
1872 debug_bitmap (bitmap head
)
1874 debug_bitmap_file (stdout
, head
);
1877 /* Function to print out the contents of a bitmap. Unlike debug_bitmap_file,
1878 it does not print anything but the bits. */
1881 bitmap_print (FILE *file
, bitmap head
, const char *prefix
, const char *suffix
)
1883 const char *comma
= "";
1887 fputs (prefix
, file
);
1888 EXECUTE_IF_SET_IN_BITMAP (head
, 0, i
, bi
)
1890 fprintf (file
, "%s%d", comma
, i
);
1893 fputs (suffix
, file
);
1895 #ifdef GATHER_STATISTICS
1898 /* Used to accumulate statistics about bitmap sizes. */
1905 /* Called via htab_traverse. Output bitmap descriptor pointed out by SLOT
1906 and update statistics. */
1908 print_statistics (void **slot
, void *b
)
1910 struct bitmap_descriptor
*d
= (struct bitmap_descriptor
*) *slot
;
1911 struct output_info
*i
= (struct output_info
*) b
;
1916 const char *s1
= d
->file
;
1918 while ((s2
= strstr (s1
, "gcc/")))
1920 sprintf (s
, "%s:%i (%s)", s1
, d
->line
, d
->function
);
1922 fprintf (stderr
, "%-41s %6d %10d %10d %10d %10d\n", s
,
1923 d
->created
, d
->allocated
, d
->peak
, d
->current
, d
->nsearches
);
1924 i
->size
+= d
->allocated
;
1925 i
->count
+= d
->created
;
1930 /* Output per-bitmap memory usage statistics. */
1932 dump_bitmap_statistics (void)
1934 #ifdef GATHER_STATISTICS
1935 struct output_info info
;
1937 if (!bitmap_desc_hash
)
1940 fprintf (stderr
, "\nBitmap Overall "
1941 "Allocated Peak Leak searched "
1943 fprintf (stderr
, "---------------------------------------------------------------------------------\n");
1946 htab_traverse (bitmap_desc_hash
, print_statistics
, &info
);
1947 fprintf (stderr
, "---------------------------------------------------------------------------------\n");
1948 fprintf (stderr
, "%-40s %7d %10d\n",
1949 "Total", info
.count
, info
.size
);
1950 fprintf (stderr
, "---------------------------------------------------------------------------------\n");
1954 /* Compute hash of bitmap (for purposes of hashing). */
1956 bitmap_hash (bitmap head
)
1958 bitmap_element
*ptr
;
1959 BITMAP_WORD hash
= 0;
1962 for (ptr
= head
->first
; ptr
; ptr
= ptr
->next
)
1965 for (ix
= 0; ix
!= BITMAP_ELEMENT_WORDS
; ix
++)
1966 hash
^= ptr
->bits
[ix
];
1968 return (hashval_t
)hash
;
1971 #include "gt-bitmap.h"