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 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"
32 #ifdef GATHER_STATISTICS
34 /* Store information about each particular bitmap. */
35 struct bitmap_descriptor
47 /* Hashtable mapping bitmap names to descriptors. */
48 static htab_t bitmap_desc_hash
;
50 /* Hashtable helpers. */
52 hash_descriptor (const void *p
)
54 const struct bitmap_descriptor
*const d
= p
;
55 return htab_hash_pointer (d
->file
) + d
->line
;
64 eq_descriptor (const void *p1
, const void *p2
)
66 const struct bitmap_descriptor
*const d
= p1
;
67 const struct loc
*const l
= p2
;
68 return d
->file
== l
->file
&& d
->function
== l
->function
&& d
->line
== l
->line
;
71 /* For given file and line, return descriptor, create new if needed. */
72 static struct bitmap_descriptor
*
73 bitmap_descriptor (const char *file
, const char *function
, int line
)
75 struct bitmap_descriptor
**slot
;
79 loc
.function
= function
;
82 if (!bitmap_desc_hash
)
83 bitmap_desc_hash
= htab_create (10, hash_descriptor
, eq_descriptor
, NULL
);
85 slot
= (struct bitmap_descriptor
**)
86 htab_find_slot_with_hash (bitmap_desc_hash
, &loc
,
87 htab_hash_pointer (file
) + line
,
91 *slot
= xcalloc (sizeof (**slot
), 1);
93 (*slot
)->function
= function
;
98 /* Register new bitmap. */
100 bitmap_register (bitmap b MEM_STAT_DECL
)
102 b
->desc
= bitmap_descriptor (_loc_name
, _loc_function
, _loc_line
);
106 /* Account the overhead. */
108 register_overhead (bitmap b
, int amount
)
110 b
->desc
->current
+= amount
;
112 b
->desc
->allocated
+= amount
;
113 gcc_assert (b
->desc
->current
>= 0);
114 if (b
->desc
->peak
< b
->desc
->current
)
115 b
->desc
->peak
= b
->desc
->current
;
120 bitmap_element bitmap_zero_bits
; /* An element of all zero bits. */
121 bitmap_obstack bitmap_default_obstack
; /* The default bitmap obstack. */
122 static GTY((deletable
)) bitmap_element
*bitmap_ggc_free
; /* Freelist of
125 static void bitmap_elem_to_freelist (bitmap
, bitmap_element
*);
126 static void bitmap_element_free (bitmap
, bitmap_element
*);
127 static bitmap_element
*bitmap_element_allocate (bitmap
);
128 static int bitmap_element_zerop (const bitmap_element
*);
129 static void bitmap_element_link (bitmap
, bitmap_element
*);
130 static bitmap_element
*bitmap_elt_insert_after (bitmap
, bitmap_element
*, unsigned int);
131 static void bitmap_elt_clear_from (bitmap
, bitmap_element
*);
132 static bitmap_element
*bitmap_find_bit (bitmap
, unsigned int);
135 /* Add ELEM to the appropriate freelist. */
137 bitmap_elem_to_freelist (bitmap head
, bitmap_element
*elt
)
139 bitmap_obstack
*bit_obstack
= head
->obstack
;
144 elt
->prev
= bit_obstack
->elements
;
145 bit_obstack
->elements
= elt
;
149 elt
->prev
= bitmap_ggc_free
;
150 bitmap_ggc_free
= elt
;
154 /* Free a bitmap element. Since these are allocated off the
155 bitmap_obstack, "free" actually means "put onto the freelist". */
158 bitmap_element_free (bitmap head
, bitmap_element
*elt
)
160 bitmap_element
*next
= elt
->next
;
161 bitmap_element
*prev
= elt
->prev
;
169 if (head
->first
== elt
)
172 /* Since the first thing we try is to insert before current,
173 make current the next entry in preference to the previous. */
174 if (head
->current
== elt
)
176 head
->current
= next
!= 0 ? next
: prev
;
178 head
->indx
= head
->current
->indx
;
182 #ifdef GATHER_STATISTICS
183 register_overhead (head
, -((int)sizeof (bitmap_element
)));
185 bitmap_elem_to_freelist (head
, elt
);
188 /* Allocate a bitmap element. The bits are cleared, but nothing else is. */
190 static inline bitmap_element
*
191 bitmap_element_allocate (bitmap head
)
193 bitmap_element
*element
;
194 bitmap_obstack
*bit_obstack
= head
->obstack
;
198 element
= bit_obstack
->elements
;
201 /* Use up the inner list first before looking at the next
202 element of the outer list. */
205 bit_obstack
->elements
= element
->next
;
206 bit_obstack
->elements
->prev
= element
->prev
;
209 /* Inner list was just a singleton. */
210 bit_obstack
->elements
= element
->prev
;
212 element
= XOBNEW (&bit_obstack
->obstack
, bitmap_element
);
216 element
= bitmap_ggc_free
;
218 /* Use up the inner list first before looking at the next
219 element of the outer list. */
222 bitmap_ggc_free
= element
->next
;
223 bitmap_ggc_free
->prev
= element
->prev
;
226 /* Inner list was just a singleton. */
227 bitmap_ggc_free
= element
->prev
;
229 element
= GGC_NEW (bitmap_element
);
232 #ifdef GATHER_STATISTICS
233 register_overhead (head
, sizeof (bitmap_element
));
235 memset (element
->bits
, 0, sizeof (element
->bits
));
240 /* Remove ELT and all following elements from bitmap HEAD. */
243 bitmap_elt_clear_from (bitmap head
, bitmap_element
*elt
)
245 bitmap_element
*prev
;
246 bitmap_obstack
*bit_obstack
= head
->obstack
;
247 #ifdef GATHER_STATISTICS
252 #ifdef GATHER_STATISTICS
254 for (prev
= elt
; prev
; prev
= prev
->next
)
256 register_overhead (head
, -sizeof (bitmap_element
) * n
);
263 if (head
->current
->indx
> prev
->indx
)
265 head
->current
= prev
;
266 head
->indx
= prev
->indx
;
272 head
->current
= NULL
;
276 /* Put the entire list onto the free list in one operation. */
279 elt
->prev
= bit_obstack
->elements
;
280 bit_obstack
->elements
= elt
;
284 elt
->prev
= bitmap_ggc_free
;
285 bitmap_ggc_free
= elt
;
289 /* Clear a bitmap by freeing the linked list. */
292 bitmap_clear (bitmap head
)
295 bitmap_elt_clear_from (head
, head
->first
);
298 /* Initialize a bitmap obstack. If BIT_OBSTACK is NULL, initialize
299 the default bitmap obstack. */
302 bitmap_obstack_initialize (bitmap_obstack
*bit_obstack
)
305 bit_obstack
= &bitmap_default_obstack
;
307 #if !defined(__GNUC__) || (__GNUC__ < 2)
308 #define __alignof__(type) 0
311 bit_obstack
->elements
= NULL
;
312 bit_obstack
->heads
= NULL
;
313 obstack_specify_allocation (&bit_obstack
->obstack
, OBSTACK_CHUNK_SIZE
,
314 __alignof__ (bitmap_element
),
319 /* Release the memory from a bitmap obstack. If BIT_OBSTACK is NULL,
320 release the default bitmap obstack. */
323 bitmap_obstack_release (bitmap_obstack
*bit_obstack
)
326 bit_obstack
= &bitmap_default_obstack
;
328 bit_obstack
->elements
= NULL
;
329 bit_obstack
->heads
= NULL
;
330 obstack_free (&bit_obstack
->obstack
, NULL
);
333 /* Create a new bitmap on an obstack. If BIT_OBSTACK is NULL, create
334 it on the default bitmap obstack. */
337 bitmap_obstack_alloc_stat (bitmap_obstack
*bit_obstack MEM_STAT_DECL
)
342 bit_obstack
= &bitmap_default_obstack
;
343 map
= bit_obstack
->heads
;
345 bit_obstack
->heads
= (void *)map
->first
;
347 map
= XOBNEW (&bit_obstack
->obstack
, bitmap_head
);
348 bitmap_initialize_stat (map
, bit_obstack PASS_MEM_STAT
);
349 #ifdef GATHER_STATISTICS
350 register_overhead (map
, sizeof (bitmap_head
));
356 /* Create a new GCd bitmap. */
359 bitmap_gc_alloc_stat (ALONE_MEM_STAT_DECL
)
363 map
= GGC_NEW (struct bitmap_head_def
);
364 bitmap_initialize_stat (map
, NULL PASS_MEM_STAT
);
365 #ifdef GATHER_STATISTICS
366 register_overhead (map
, sizeof (bitmap_head
));
372 /* Release an obstack allocated bitmap. */
375 bitmap_obstack_free (bitmap map
)
380 map
->first
= (void *)map
->obstack
->heads
;
381 #ifdef GATHER_STATISTICS
382 register_overhead (map
, -((int)sizeof (bitmap_head
)));
384 map
->obstack
->heads
= map
;
389 /* Return nonzero if all bits in an element are zero. */
392 bitmap_element_zerop (const bitmap_element
*element
)
394 #if BITMAP_ELEMENT_WORDS == 2
395 return (element
->bits
[0] | element
->bits
[1]) == 0;
399 for (i
= 0; i
< BITMAP_ELEMENT_WORDS
; i
++)
400 if (element
->bits
[i
] != 0)
407 /* Link the bitmap element into the current bitmap linked list. */
410 bitmap_element_link (bitmap head
, bitmap_element
*element
)
412 unsigned int indx
= element
->indx
;
415 /* If this is the first and only element, set it in. */
416 if (head
->first
== 0)
418 element
->next
= element
->prev
= 0;
419 head
->first
= element
;
422 /* If this index is less than that of the current element, it goes someplace
423 before the current element. */
424 else if (indx
< head
->indx
)
426 for (ptr
= head
->current
;
427 ptr
->prev
!= 0 && ptr
->prev
->indx
> indx
;
432 ptr
->prev
->next
= element
;
434 head
->first
= element
;
436 element
->prev
= ptr
->prev
;
441 /* Otherwise, it must go someplace after the current element. */
444 for (ptr
= head
->current
;
445 ptr
->next
!= 0 && ptr
->next
->indx
< indx
;
450 ptr
->next
->prev
= element
;
452 element
->next
= ptr
->next
;
457 /* Set up so this is the first element searched. */
458 head
->current
= element
;
462 /* Insert a new uninitialized element into bitmap HEAD after element
463 ELT. If ELT is NULL, insert the element at the start. Return the
466 static bitmap_element
*
467 bitmap_elt_insert_after (bitmap head
, bitmap_element
*elt
, unsigned int indx
)
469 bitmap_element
*node
= bitmap_element_allocate (head
);
476 head
->current
= node
;
479 node
->next
= head
->first
;
481 node
->next
->prev
= node
;
487 gcc_assert (head
->current
);
488 node
->next
= elt
->next
;
490 node
->next
->prev
= node
;
497 /* Copy a bitmap to another bitmap. */
500 bitmap_copy (bitmap to
, const_bitmap from
)
502 const bitmap_element
*from_ptr
;
503 bitmap_element
*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
*const 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 const 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 (const_bitmap a
)
676 unsigned long count
= 0;
677 const bitmap_element
*elt
;
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 (const_bitmap a
)
704 const 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
, const_bitmap a
, const_bitmap b
)
755 bitmap_element
*dst_elt
= dst
->first
;
756 const bitmap_element
*a_elt
= a
->first
;
757 const 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
, const_bitmap b
)
813 bitmap_element
*a_elt
= a
->first
;
814 const 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 const 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
, const_bitmap a
, const_bitmap b
)
894 bitmap_element
*dst_elt
= dst
->first
;
895 const bitmap_element
*a_elt
= a
->first
;
896 const 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
, const_bitmap b
)
1007 bitmap_element
*a_elt
= a
->first
;
1008 const 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
, const_bitmap b
)
1287 bitmap_element
*a_elt
= a
->first
;
1288 const 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 const bitmap_element
*a_elt
, const 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 const 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
, const_bitmap a
, const_bitmap b
)
1416 bitmap_element
*dst_elt
= dst
->first
;
1417 const bitmap_element
*a_elt
= a
->first
;
1418 const 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
, const_bitmap b
)
1463 bitmap_element
*a_elt
= a
->first
;
1464 const 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
, const_bitmap a
, const_bitmap b
)
1502 bitmap_element
*dst_elt
= dst
->first
;
1503 const bitmap_element
*a_elt
= a
->first
;
1504 const 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 const 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
, const_bitmap b
)
1579 bitmap_element
*a_elt
= a
->first
;
1580 const 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 (const_bitmap a
, const_bitmap b
)
1638 const bitmap_element
*a_elt
;
1639 const 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 (const_bitmap a
, const_bitmap b
)
1660 const bitmap_element
*a_elt
;
1661 const 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 (const_bitmap a
, const_bitmap b
)
1688 const bitmap_element
*a_elt
;
1689 const 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
, const_bitmap a
, const_bitmap b
, const_bitmap kill
)
1716 bool changed
= false;
1718 bitmap_element
*dst_elt
= dst
->first
;
1719 const bitmap_element
*a_elt
= a
->first
;
1720 const bitmap_element
*b_elt
= b
->first
;
1721 const 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
, const_bitmap from1
, const_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
, const_bitmap head
)
1837 const 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 (const void*) ptr
, (const void*) ptr
->next
,
1848 (const void*) ptr
->prev
, ptr
->indx
);
1850 for (i
= 0; i
< BITMAP_ELEMENT_WORDS
; i
++)
1851 for (j
= 0; j
< BITMAP_WORD_BITS
; j
++)
1852 if ((ptr
->bits
[i
] >> j
) & 1)
1856 fprintf (file
, "\n\t\t\t");
1860 fprintf (file
, " %u", (ptr
->indx
* BITMAP_ELEMENT_ALL_BITS
1861 + i
* BITMAP_WORD_BITS
+ j
));
1865 fprintf (file
, " }\n");
1869 /* Function to be called from the debugger to print the contents
1873 debug_bitmap (const_bitmap head
)
1875 debug_bitmap_file (stdout
, head
);
1878 /* Function to print out the contents of a bitmap. Unlike debug_bitmap_file,
1879 it does not print anything but the bits. */
1882 bitmap_print (FILE *file
, const_bitmap head
, const char *prefix
, const char *suffix
)
1884 const char *comma
= "";
1888 fputs (prefix
, file
);
1889 EXECUTE_IF_SET_IN_BITMAP (head
, 0, i
, bi
)
1891 fprintf (file
, "%s%d", comma
, i
);
1894 fputs (suffix
, file
);
1896 #ifdef GATHER_STATISTICS
1899 /* Used to accumulate statistics about bitmap sizes. */
1906 /* Called via htab_traverse. Output bitmap descriptor pointed out by SLOT
1907 and update statistics. */
1909 print_statistics (void **slot
, void *b
)
1911 struct bitmap_descriptor
*d
= (struct bitmap_descriptor
*) *slot
;
1912 struct output_info
*i
= (struct output_info
*) b
;
1917 const char *s1
= d
->file
;
1919 while ((s2
= strstr (s1
, "gcc/")))
1921 sprintf (s
, "%s:%i (%s)", s1
, d
->line
, d
->function
);
1923 fprintf (stderr
, "%-41s %6d %10d %10d %10d %10d\n", s
,
1924 d
->created
, d
->allocated
, d
->peak
, d
->current
, d
->nsearches
);
1925 i
->size
+= d
->allocated
;
1926 i
->count
+= d
->created
;
1931 /* Output per-bitmap memory usage statistics. */
1933 dump_bitmap_statistics (void)
1935 #ifdef GATHER_STATISTICS
1936 struct output_info info
;
1938 if (!bitmap_desc_hash
)
1941 fprintf (stderr
, "\nBitmap Overall "
1942 "Allocated Peak Leak searched "
1944 fprintf (stderr
, "---------------------------------------------------------------------------------\n");
1947 htab_traverse (bitmap_desc_hash
, print_statistics
, &info
);
1948 fprintf (stderr
, "---------------------------------------------------------------------------------\n");
1949 fprintf (stderr
, "%-40s %7d %10d\n",
1950 "Total", info
.count
, info
.size
);
1951 fprintf (stderr
, "---------------------------------------------------------------------------------\n");
1955 /* Compute hash of bitmap (for purposes of hashing). */
1957 bitmap_hash (const_bitmap head
)
1959 const bitmap_element
*ptr
;
1960 BITMAP_WORD hash
= 0;
1963 for (ptr
= head
->first
; ptr
; ptr
= ptr
->next
)
1966 for (ix
= 0; ix
!= BITMAP_ELEMENT_WORDS
; ix
++)
1967 hash
^= ptr
->bits
[ix
];
1969 return (hashval_t
)hash
;
1972 #include "gt-bitmap.h"