1 /* Functions to support general ended bitmaps.
2 Copyright (C) 1997-2015 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
22 #include "coretypes.h"
26 #include "hash-table.h"
29 /* Store information about each particular bitmap, per allocation site. */
30 struct bitmap_descriptor_d
44 typedef struct bitmap_descriptor_d
*bitmap_descriptor
;
45 typedef const struct bitmap_descriptor_d
*const_bitmap_descriptor
;
47 /* Next available unique id number for bitmap desciptors. */
48 static int next_bitmap_desc_id
= 0;
50 /* Vector mapping descriptor ids to descriptors. */
51 static vec
<bitmap_descriptor
> bitmap_descriptors
;
53 /* Hashtable helpers. */
62 struct bitmap_desc_hasher
: typed_noop_remove
<bitmap_descriptor_d
>
64 typedef bitmap_descriptor_d
*value_type
;
65 typedef loc
*compare_type
;
66 static inline hashval_t
hash (const bitmap_descriptor_d
*);
67 static inline bool equal (const bitmap_descriptor_d
*, const loc
*);
71 bitmap_desc_hasher::hash (const bitmap_descriptor_d
*d
)
73 return htab_hash_pointer (d
->file
) + d
->line
;
77 bitmap_desc_hasher::equal (const bitmap_descriptor_d
*d
, const loc
*l
)
79 return d
->file
== l
->file
&& d
->function
== l
->function
&& d
->line
== l
->line
;
82 /* Hashtable mapping bitmap names to descriptors. */
83 static hash_table
<bitmap_desc_hasher
> *bitmap_desc_hash
;
85 /* For given file and line, return descriptor, create new if needed. */
86 static bitmap_descriptor
87 get_bitmap_descriptor (const char *file
, int line
, const char *function
)
89 bitmap_descriptor_d
**slot
;
93 loc
.function
= function
;
96 if (!bitmap_desc_hash
)
97 bitmap_desc_hash
= new hash_table
<bitmap_desc_hasher
> (10);
100 = bitmap_desc_hash
->find_slot_with_hash (&loc
,
101 htab_hash_pointer (file
) + line
,
106 *slot
= XCNEW (struct bitmap_descriptor_d
);
107 bitmap_descriptors
.safe_push (*slot
);
108 (*slot
)->id
= next_bitmap_desc_id
++;
109 (*slot
)->file
= file
;
110 (*slot
)->function
= function
;
111 (*slot
)->line
= line
;
115 /* Register new bitmap. */
117 bitmap_register (bitmap b MEM_STAT_DECL
)
119 bitmap_descriptor desc
= get_bitmap_descriptor (ALONE_FINAL_PASS_MEM_STAT
);
121 b
->descriptor_id
= desc
->id
;
124 /* Account the overhead. */
126 register_overhead (bitmap b
, int amount
)
128 bitmap_descriptor desc
= bitmap_descriptors
[b
->descriptor_id
];
129 desc
->current
+= amount
;
131 desc
->allocated
+= amount
;
132 if (desc
->peak
< desc
->current
)
133 desc
->peak
= desc
->current
;
137 bitmap_element bitmap_zero_bits
; /* An element of all zero bits. */
138 bitmap_obstack bitmap_default_obstack
; /* The default bitmap obstack. */
139 static int bitmap_default_obstack_depth
;
140 static GTY((deletable
)) bitmap_element
*bitmap_ggc_free
; /* Freelist of
143 static void bitmap_elem_to_freelist (bitmap
, bitmap_element
*);
144 static void bitmap_element_free (bitmap
, bitmap_element
*);
145 static bitmap_element
*bitmap_element_allocate (bitmap
);
146 static int bitmap_element_zerop (const bitmap_element
*);
147 static void bitmap_element_link (bitmap
, bitmap_element
*);
148 static bitmap_element
*bitmap_elt_insert_after (bitmap
, bitmap_element
*, unsigned int);
149 static void bitmap_elt_clear_from (bitmap
, bitmap_element
*);
150 static bitmap_element
*bitmap_find_bit (bitmap
, unsigned int);
153 /* Add ELEM to the appropriate freelist. */
155 bitmap_elem_to_freelist (bitmap head
, bitmap_element
*elt
)
157 bitmap_obstack
*bit_obstack
= head
->obstack
;
162 elt
->prev
= bit_obstack
->elements
;
163 bit_obstack
->elements
= elt
;
167 elt
->prev
= bitmap_ggc_free
;
168 bitmap_ggc_free
= elt
;
172 /* Free a bitmap element. Since these are allocated off the
173 bitmap_obstack, "free" actually means "put onto the freelist". */
176 bitmap_element_free (bitmap head
, bitmap_element
*elt
)
178 bitmap_element
*next
= elt
->next
;
179 bitmap_element
*prev
= elt
->prev
;
187 if (head
->first
== elt
)
190 /* Since the first thing we try is to insert before current,
191 make current the next entry in preference to the previous. */
192 if (head
->current
== elt
)
194 head
->current
= next
!= 0 ? next
: prev
;
196 head
->indx
= head
->current
->indx
;
201 if (GATHER_STATISTICS
)
202 register_overhead (head
, -((int)sizeof (bitmap_element
)));
204 bitmap_elem_to_freelist (head
, elt
);
207 /* Allocate a bitmap element. The bits are cleared, but nothing else is. */
209 static inline bitmap_element
*
210 bitmap_element_allocate (bitmap head
)
212 bitmap_element
*element
;
213 bitmap_obstack
*bit_obstack
= head
->obstack
;
217 element
= bit_obstack
->elements
;
220 /* Use up the inner list first before looking at the next
221 element of the outer list. */
224 bit_obstack
->elements
= element
->next
;
225 bit_obstack
->elements
->prev
= element
->prev
;
228 /* Inner list was just a singleton. */
229 bit_obstack
->elements
= element
->prev
;
231 element
= XOBNEW (&bit_obstack
->obstack
, bitmap_element
);
235 element
= bitmap_ggc_free
;
237 /* Use up the inner list first before looking at the next
238 element of the outer list. */
241 bitmap_ggc_free
= element
->next
;
242 bitmap_ggc_free
->prev
= element
->prev
;
245 /* Inner list was just a singleton. */
246 bitmap_ggc_free
= element
->prev
;
248 element
= ggc_alloc
<bitmap_element
> ();
251 if (GATHER_STATISTICS
)
252 register_overhead (head
, sizeof (bitmap_element
));
254 memset (element
->bits
, 0, sizeof (element
->bits
));
259 /* Remove ELT and all following elements from bitmap HEAD. */
262 bitmap_elt_clear_from (bitmap head
, bitmap_element
*elt
)
264 bitmap_element
*prev
;
265 bitmap_obstack
*bit_obstack
= head
->obstack
;
269 if (GATHER_STATISTICS
)
272 for (prev
= elt
; prev
; prev
= prev
->next
)
274 register_overhead (head
, -sizeof (bitmap_element
) * n
);
281 if (head
->current
->indx
> prev
->indx
)
283 head
->current
= prev
;
284 head
->indx
= prev
->indx
;
290 head
->current
= NULL
;
294 /* Put the entire list onto the free list in one operation. */
297 elt
->prev
= bit_obstack
->elements
;
298 bit_obstack
->elements
= elt
;
302 elt
->prev
= bitmap_ggc_free
;
303 bitmap_ggc_free
= elt
;
307 /* Clear a bitmap by freeing the linked list. */
310 bitmap_clear (bitmap head
)
313 bitmap_elt_clear_from (head
, head
->first
);
316 /* Initialize a bitmap obstack. If BIT_OBSTACK is NULL, initialize
317 the default bitmap obstack. */
320 bitmap_obstack_initialize (bitmap_obstack
*bit_obstack
)
324 if (bitmap_default_obstack_depth
++)
326 bit_obstack
= &bitmap_default_obstack
;
329 #if !defined(__GNUC__) || (__GNUC__ < 2)
330 #define __alignof__(type) 0
333 bit_obstack
->elements
= NULL
;
334 bit_obstack
->heads
= NULL
;
335 obstack_specify_allocation (&bit_obstack
->obstack
, OBSTACK_CHUNK_SIZE
,
336 __alignof__ (bitmap_element
),
341 /* Release the memory from a bitmap obstack. If BIT_OBSTACK is NULL,
342 release the default bitmap obstack. */
345 bitmap_obstack_release (bitmap_obstack
*bit_obstack
)
349 if (--bitmap_default_obstack_depth
)
351 gcc_assert (bitmap_default_obstack_depth
> 0);
354 bit_obstack
= &bitmap_default_obstack
;
357 bit_obstack
->elements
= NULL
;
358 bit_obstack
->heads
= NULL
;
359 obstack_free (&bit_obstack
->obstack
, NULL
);
362 /* Create a new bitmap on an obstack. If BIT_OBSTACK is NULL, create
363 it on the default bitmap obstack. */
366 bitmap_obstack_alloc_stat (bitmap_obstack
*bit_obstack MEM_STAT_DECL
)
371 bit_obstack
= &bitmap_default_obstack
;
372 map
= bit_obstack
->heads
;
374 bit_obstack
->heads
= (struct bitmap_head
*) map
->first
;
376 map
= XOBNEW (&bit_obstack
->obstack
, bitmap_head
);
377 bitmap_initialize_stat (map
, bit_obstack PASS_MEM_STAT
);
379 if (GATHER_STATISTICS
)
380 register_overhead (map
, sizeof (bitmap_head
));
385 /* Create a new GCd bitmap. */
388 bitmap_gc_alloc_stat (ALONE_MEM_STAT_DECL
)
392 map
= ggc_alloc
<bitmap_head
> ();
393 bitmap_initialize_stat (map
, NULL PASS_MEM_STAT
);
395 if (GATHER_STATISTICS
)
396 register_overhead (map
, sizeof (bitmap_head
));
401 /* Release an obstack allocated bitmap. */
404 bitmap_obstack_free (bitmap map
)
409 map
->first
= (bitmap_element
*) map
->obstack
->heads
;
411 if (GATHER_STATISTICS
)
412 register_overhead (map
, -((int)sizeof (bitmap_head
)));
414 map
->obstack
->heads
= map
;
419 /* Return nonzero if all bits in an element are zero. */
422 bitmap_element_zerop (const bitmap_element
*element
)
424 #if BITMAP_ELEMENT_WORDS == 2
425 return (element
->bits
[0] | element
->bits
[1]) == 0;
429 for (i
= 0; i
< BITMAP_ELEMENT_WORDS
; i
++)
430 if (element
->bits
[i
] != 0)
437 /* Link the bitmap element into the current bitmap linked list. */
440 bitmap_element_link (bitmap head
, bitmap_element
*element
)
442 unsigned int indx
= element
->indx
;
445 /* If this is the first and only element, set it in. */
446 if (head
->first
== 0)
448 element
->next
= element
->prev
= 0;
449 head
->first
= element
;
452 /* If this index is less than that of the current element, it goes someplace
453 before the current element. */
454 else if (indx
< head
->indx
)
456 for (ptr
= head
->current
;
457 ptr
->prev
!= 0 && ptr
->prev
->indx
> indx
;
462 ptr
->prev
->next
= element
;
464 head
->first
= element
;
466 element
->prev
= ptr
->prev
;
471 /* Otherwise, it must go someplace after the current element. */
474 for (ptr
= head
->current
;
475 ptr
->next
!= 0 && ptr
->next
->indx
< indx
;
480 ptr
->next
->prev
= element
;
482 element
->next
= ptr
->next
;
487 /* Set up so this is the first element searched. */
488 head
->current
= element
;
492 /* Insert a new uninitialized element into bitmap HEAD after element
493 ELT. If ELT is NULL, insert the element at the start. Return the
496 static bitmap_element
*
497 bitmap_elt_insert_after (bitmap head
, bitmap_element
*elt
, unsigned int indx
)
499 bitmap_element
*node
= bitmap_element_allocate (head
);
506 head
->current
= node
;
509 node
->next
= head
->first
;
511 node
->next
->prev
= node
;
517 gcc_checking_assert (head
->current
);
518 node
->next
= elt
->next
;
520 node
->next
->prev
= node
;
527 /* Copy a bitmap to another bitmap. */
530 bitmap_copy (bitmap to
, const_bitmap from
)
532 const bitmap_element
*from_ptr
;
533 bitmap_element
*to_ptr
= 0;
537 /* Copy elements in forward direction one at a time. */
538 for (from_ptr
= from
->first
; from_ptr
; from_ptr
= from_ptr
->next
)
540 bitmap_element
*to_elt
= bitmap_element_allocate (to
);
542 to_elt
->indx
= from_ptr
->indx
;
543 memcpy (to_elt
->bits
, from_ptr
->bits
, sizeof (to_elt
->bits
));
545 /* Here we have a special case of bitmap_element_link, for the case
546 where we know the links are being entered in sequence. */
549 to
->first
= to
->current
= to_elt
;
550 to
->indx
= from_ptr
->indx
;
551 to_elt
->next
= to_elt
->prev
= 0;
555 to_elt
->prev
= to_ptr
;
557 to_ptr
->next
= to_elt
;
564 /* Find a bitmap element that would hold a bitmap's bit.
565 Update the `current' field even if we can't find an element that
566 would hold the bitmap's bit to make eventual allocation
569 static inline bitmap_element
*
570 bitmap_find_bit (bitmap head
, unsigned int bit
)
572 bitmap_element
*element
;
573 unsigned int indx
= bit
/ BITMAP_ELEMENT_ALL_BITS
;
575 if (head
->current
== NULL
576 || head
->indx
== indx
)
577 return head
->current
;
578 if (head
->current
== head
->first
579 && head
->first
->next
== NULL
)
582 /* This bitmap has more than one element, and we're going to look
583 through the elements list. Count that as a search. */
584 if (GATHER_STATISTICS
)
585 bitmap_descriptors
[head
->descriptor_id
]->nsearches
++;
587 if (head
->indx
< indx
)
588 /* INDX is beyond head->indx. Search from head->current
590 for (element
= head
->current
;
591 element
->next
!= 0 && element
->indx
< indx
;
592 element
= element
->next
)
594 if (GATHER_STATISTICS
)
595 bitmap_descriptors
[head
->descriptor_id
]->search_iter
++;
598 else if (head
->indx
/ 2 < indx
)
599 /* INDX is less than head->indx and closer to head->indx than to
600 0. Search from head->current backward. */
601 for (element
= head
->current
;
602 element
->prev
!= 0 && element
->indx
> indx
;
603 element
= element
->prev
)
605 if (GATHER_STATISTICS
)
606 bitmap_descriptors
[head
->descriptor_id
]->search_iter
++;
610 /* INDX is less than head->indx and closer to 0 than to
611 head->indx. Search from head->first forward. */
612 for (element
= head
->first
;
613 element
->next
!= 0 && element
->indx
< indx
;
614 element
= element
->next
)
615 if (GATHER_STATISTICS
)
617 bitmap_descriptors
[head
->descriptor_id
]->search_iter
++;
620 /* `element' is the nearest to the one we want. If it's not the one we
621 want, the one we want doesn't exist. */
622 head
->current
= element
;
623 head
->indx
= element
->indx
;
624 if (element
!= 0 && element
->indx
!= indx
)
630 /* Clear a single bit in a bitmap. Return true if the bit changed. */
633 bitmap_clear_bit (bitmap head
, int bit
)
635 bitmap_element
*const ptr
= bitmap_find_bit (head
, bit
);
639 unsigned bit_num
= bit
% BITMAP_WORD_BITS
;
640 unsigned word_num
= bit
/ BITMAP_WORD_BITS
% BITMAP_ELEMENT_WORDS
;
641 BITMAP_WORD bit_val
= ((BITMAP_WORD
) 1) << bit_num
;
642 bool res
= (ptr
->bits
[word_num
] & bit_val
) != 0;
645 ptr
->bits
[word_num
] &= ~bit_val
;
646 /* If we cleared the entire word, free up the element. */
647 if (!ptr
->bits
[word_num
]
648 && bitmap_element_zerop (ptr
))
649 bitmap_element_free (head
, ptr
);
658 /* Set a single bit in a bitmap. Return true if the bit changed. */
661 bitmap_set_bit (bitmap head
, int bit
)
663 bitmap_element
*ptr
= bitmap_find_bit (head
, bit
);
664 unsigned word_num
= bit
/ BITMAP_WORD_BITS
% BITMAP_ELEMENT_WORDS
;
665 unsigned bit_num
= bit
% BITMAP_WORD_BITS
;
666 BITMAP_WORD bit_val
= ((BITMAP_WORD
) 1) << bit_num
;
670 ptr
= bitmap_element_allocate (head
);
671 ptr
->indx
= bit
/ BITMAP_ELEMENT_ALL_BITS
;
672 ptr
->bits
[word_num
] = bit_val
;
673 bitmap_element_link (head
, ptr
);
678 bool res
= (ptr
->bits
[word_num
] & bit_val
) == 0;
680 ptr
->bits
[word_num
] |= bit_val
;
685 /* Return whether a bit is set within a bitmap. */
688 bitmap_bit_p (bitmap head
, int bit
)
694 ptr
= bitmap_find_bit (head
, bit
);
698 bit_num
= bit
% BITMAP_WORD_BITS
;
699 word_num
= bit
/ BITMAP_WORD_BITS
% BITMAP_ELEMENT_WORDS
;
701 return (ptr
->bits
[word_num
] >> bit_num
) & 1;
704 #if GCC_VERSION < 3400
705 /* Table of number of set bits in a character, indexed by value of char. */
706 static const unsigned char popcount_table
[] =
708 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,
709 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,
710 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,
711 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,
712 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,
713 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,
714 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,
715 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,
719 bitmap_popcount (BITMAP_WORD a
)
721 unsigned long ret
= 0;
724 /* Just do this the table way for now */
725 for (i
= 0; i
< BITMAP_WORD_BITS
; i
+= 8)
726 ret
+= popcount_table
[(a
>> i
) & 0xff];
730 /* Count the number of bits set in the bitmap, and return it. */
733 bitmap_count_bits (const_bitmap a
)
735 unsigned long count
= 0;
736 const bitmap_element
*elt
;
739 for (elt
= a
->first
; elt
; elt
= elt
->next
)
741 for (ix
= 0; ix
!= BITMAP_ELEMENT_WORDS
; ix
++)
743 #if GCC_VERSION >= 3400
744 /* Note that popcountl matches BITMAP_WORD in type, so the actual size
745 of BITMAP_WORD is not material. */
746 count
+= __builtin_popcountl (elt
->bits
[ix
]);
748 count
+= bitmap_popcount (elt
->bits
[ix
]);
755 /* Return true if the bitmap has a single bit set. Otherwise return
759 bitmap_single_bit_set_p (const_bitmap a
)
761 unsigned long count
= 0;
762 const bitmap_element
*elt
;
765 if (bitmap_empty_p (a
))
769 /* As there are no completely empty bitmap elements, a second one
770 means we have more than one bit set. */
771 if (elt
->next
!= NULL
)
774 for (ix
= 0; ix
!= BITMAP_ELEMENT_WORDS
; ix
++)
776 #if GCC_VERSION >= 3400
777 /* Note that popcountl matches BITMAP_WORD in type, so the actual size
778 of BITMAP_WORD is not material. */
779 count
+= __builtin_popcountl (elt
->bits
[ix
]);
781 count
+= bitmap_popcount (elt
->bits
[ix
]);
791 /* Return the bit number of the first set bit in the bitmap. The
792 bitmap must be non-empty. */
795 bitmap_first_set_bit (const_bitmap a
)
797 const bitmap_element
*elt
= a
->first
;
802 gcc_checking_assert (elt
);
803 bit_no
= elt
->indx
* BITMAP_ELEMENT_ALL_BITS
;
804 for (ix
= 0; ix
!= BITMAP_ELEMENT_WORDS
; ix
++)
806 word
= elt
->bits
[ix
];
812 bit_no
+= ix
* BITMAP_WORD_BITS
;
814 #if GCC_VERSION >= 3004
815 gcc_assert (sizeof (long) == sizeof (word
));
816 bit_no
+= __builtin_ctzl (word
);
818 /* Binary search for the first set bit. */
819 #if BITMAP_WORD_BITS > 64
820 #error "Fill out the table."
822 #if BITMAP_WORD_BITS > 32
823 if (!(word
& 0xffffffff))
824 word
>>= 32, bit_no
+= 32;
826 if (!(word
& 0xffff))
827 word
>>= 16, bit_no
+= 16;
829 word
>>= 8, bit_no
+= 8;
831 word
>>= 4, bit_no
+= 4;
833 word
>>= 2, bit_no
+= 2;
835 word
>>= 1, bit_no
+= 1;
837 gcc_checking_assert (word
& 1);
842 /* Return the bit number of the first set bit in the bitmap. The
843 bitmap must be non-empty. */
846 bitmap_last_set_bit (const_bitmap a
)
848 const bitmap_element
*elt
= a
->current
? a
->current
: a
->first
;
853 gcc_checking_assert (elt
);
856 bit_no
= elt
->indx
* BITMAP_ELEMENT_ALL_BITS
;
857 for (ix
= BITMAP_ELEMENT_WORDS
- 1; ix
>= 0; ix
--)
859 word
= elt
->bits
[ix
];
865 bit_no
+= ix
* BITMAP_WORD_BITS
;
866 #if GCC_VERSION >= 3004
867 gcc_assert (sizeof (long) == sizeof (word
));
868 bit_no
+= BITMAP_WORD_BITS
- __builtin_clzl (word
) - 1;
870 /* Hopefully this is a twos-complement host... */
871 BITMAP_WORD x
= word
;
877 #if BITMAP_WORD_BITS > 32
880 bit_no
+= bitmap_popcount (x
) - 1;
890 bitmap_and (bitmap dst
, const_bitmap a
, const_bitmap b
)
892 bitmap_element
*dst_elt
= dst
->first
;
893 const bitmap_element
*a_elt
= a
->first
;
894 const bitmap_element
*b_elt
= b
->first
;
895 bitmap_element
*dst_prev
= NULL
;
897 gcc_assert (dst
!= a
&& dst
!= b
);
901 bitmap_copy (dst
, a
);
905 while (a_elt
&& b_elt
)
907 if (a_elt
->indx
< b_elt
->indx
)
909 else if (b_elt
->indx
< a_elt
->indx
)
913 /* Matching elts, generate A & B. */
918 dst_elt
= bitmap_elt_insert_after (dst
, dst_prev
, a_elt
->indx
);
920 dst_elt
->indx
= a_elt
->indx
;
921 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
923 BITMAP_WORD r
= a_elt
->bits
[ix
] & b_elt
->bits
[ix
];
925 dst_elt
->bits
[ix
] = r
;
931 dst_elt
= dst_elt
->next
;
937 /* Ensure that dst->current is valid. */
938 dst
->current
= dst
->first
;
939 bitmap_elt_clear_from (dst
, dst_elt
);
940 gcc_checking_assert (!dst
->current
== !dst
->first
);
942 dst
->indx
= dst
->current
->indx
;
945 /* A &= B. Return true if A changed. */
948 bitmap_and_into (bitmap a
, const_bitmap b
)
950 bitmap_element
*a_elt
= a
->first
;
951 const bitmap_element
*b_elt
= b
->first
;
952 bitmap_element
*next
;
953 bool changed
= false;
958 while (a_elt
&& b_elt
)
960 if (a_elt
->indx
< b_elt
->indx
)
963 bitmap_element_free (a
, a_elt
);
967 else if (b_elt
->indx
< a_elt
->indx
)
971 /* Matching elts, generate A &= B. */
975 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
977 BITMAP_WORD r
= a_elt
->bits
[ix
] & b_elt
->bits
[ix
];
978 if (a_elt
->bits
[ix
] != r
)
985 bitmap_element_free (a
, a_elt
);
994 bitmap_elt_clear_from (a
, a_elt
);
997 gcc_checking_assert (!a
->current
== !a
->first
998 && (!a
->current
|| a
->indx
== a
->current
->indx
));
1004 /* Insert an element equal to SRC_ELT after DST_PREV, overwriting DST_ELT
1005 if non-NULL. CHANGED is true if the destination bitmap had already been
1006 changed; the new value of CHANGED is returned. */
1009 bitmap_elt_copy (bitmap dst
, bitmap_element
*dst_elt
, bitmap_element
*dst_prev
,
1010 const bitmap_element
*src_elt
, bool changed
)
1012 if (!changed
&& dst_elt
&& dst_elt
->indx
== src_elt
->indx
)
1016 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1017 if (src_elt
->bits
[ix
] != dst_elt
->bits
[ix
])
1019 dst_elt
->bits
[ix
] = src_elt
->bits
[ix
];
1027 dst_elt
= bitmap_elt_insert_after (dst
, dst_prev
, src_elt
->indx
);
1029 dst_elt
->indx
= src_elt
->indx
;
1030 memcpy (dst_elt
->bits
, src_elt
->bits
, sizeof (dst_elt
->bits
));
1040 bitmap_and_compl (bitmap dst
, const_bitmap a
, const_bitmap b
)
1042 bitmap_element
*dst_elt
= dst
->first
;
1043 const bitmap_element
*a_elt
= a
->first
;
1044 const bitmap_element
*b_elt
= b
->first
;
1045 bitmap_element
*dst_prev
= NULL
;
1046 bitmap_element
**dst_prev_pnext
= &dst
->first
;
1047 bool changed
= false;
1049 gcc_assert (dst
!= a
&& dst
!= b
);
1053 changed
= !bitmap_empty_p (dst
);
1060 while (b_elt
&& b_elt
->indx
< a_elt
->indx
)
1061 b_elt
= b_elt
->next
;
1063 if (!b_elt
|| b_elt
->indx
> a_elt
->indx
)
1065 changed
= bitmap_elt_copy (dst
, dst_elt
, dst_prev
, a_elt
, changed
);
1066 dst_prev
= *dst_prev_pnext
;
1067 dst_prev_pnext
= &dst_prev
->next
;
1068 dst_elt
= *dst_prev_pnext
;
1069 a_elt
= a_elt
->next
;
1074 /* Matching elts, generate A & ~B. */
1076 BITMAP_WORD ior
= 0;
1078 if (!changed
&& dst_elt
&& dst_elt
->indx
== a_elt
->indx
)
1080 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1082 BITMAP_WORD r
= a_elt
->bits
[ix
] & ~b_elt
->bits
[ix
];
1084 if (dst_elt
->bits
[ix
] != r
)
1087 dst_elt
->bits
[ix
] = r
;
1095 if (!dst_elt
|| dst_elt
->indx
> a_elt
->indx
)
1097 dst_elt
= bitmap_elt_insert_after (dst
, dst_prev
, a_elt
->indx
);
1102 dst_elt
->indx
= a_elt
->indx
;
1103 new_element
= false;
1106 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1108 BITMAP_WORD r
= a_elt
->bits
[ix
] & ~b_elt
->bits
[ix
];
1110 dst_elt
->bits
[ix
] = r
;
1118 changed
|= !new_element
;
1119 bitmap_element_free (dst
, dst_elt
);
1120 dst_elt
= *dst_prev_pnext
;
1126 dst_prev
= *dst_prev_pnext
;
1127 dst_prev_pnext
= &dst_prev
->next
;
1128 dst_elt
= *dst_prev_pnext
;
1130 a_elt
= a_elt
->next
;
1131 b_elt
= b_elt
->next
;
1135 /* Ensure that dst->current is valid. */
1136 dst
->current
= dst
->first
;
1141 bitmap_elt_clear_from (dst
, dst_elt
);
1143 gcc_checking_assert (!dst
->current
== !dst
->first
);
1145 dst
->indx
= dst
->current
->indx
;
1150 /* A &= ~B. Returns true if A changes */
1153 bitmap_and_compl_into (bitmap a
, const_bitmap b
)
1155 bitmap_element
*a_elt
= a
->first
;
1156 const bitmap_element
*b_elt
= b
->first
;
1157 bitmap_element
*next
;
1158 BITMAP_WORD changed
= 0;
1162 if (bitmap_empty_p (a
))
1171 while (a_elt
&& b_elt
)
1173 if (a_elt
->indx
< b_elt
->indx
)
1174 a_elt
= a_elt
->next
;
1175 else if (b_elt
->indx
< a_elt
->indx
)
1176 b_elt
= b_elt
->next
;
1179 /* Matching elts, generate A &= ~B. */
1181 BITMAP_WORD ior
= 0;
1183 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1185 BITMAP_WORD cleared
= a_elt
->bits
[ix
] & b_elt
->bits
[ix
];
1186 BITMAP_WORD r
= a_elt
->bits
[ix
] ^ cleared
;
1188 a_elt
->bits
[ix
] = r
;
1194 bitmap_element_free (a
, a_elt
);
1196 b_elt
= b_elt
->next
;
1199 gcc_checking_assert (!a
->current
== !a
->first
1200 && (!a
->current
|| a
->indx
== a
->current
->indx
));
1201 return changed
!= 0;
1204 /* Set COUNT bits from START in HEAD. */
1206 bitmap_set_range (bitmap head
, unsigned int start
, unsigned int count
)
1208 unsigned int first_index
, end_bit_plus1
, last_index
;
1209 bitmap_element
*elt
, *elt_prev
;
1215 first_index
= start
/ BITMAP_ELEMENT_ALL_BITS
;
1216 end_bit_plus1
= start
+ count
;
1217 last_index
= (end_bit_plus1
- 1) / BITMAP_ELEMENT_ALL_BITS
;
1218 elt
= bitmap_find_bit (head
, start
);
1220 /* If bitmap_find_bit returns zero, the current is the closest block
1221 to the result. Otherwise, just use bitmap_element_allocate to
1222 ensure ELT is set; in the loop below, ELT == NULL means "insert
1223 at the end of the bitmap". */
1226 elt
= bitmap_element_allocate (head
);
1227 elt
->indx
= first_index
;
1228 bitmap_element_link (head
, elt
);
1231 gcc_checking_assert (elt
->indx
== first_index
);
1232 elt_prev
= elt
->prev
;
1233 for (i
= first_index
; i
<= last_index
; i
++)
1235 unsigned elt_start_bit
= i
* BITMAP_ELEMENT_ALL_BITS
;
1236 unsigned elt_end_bit_plus1
= elt_start_bit
+ BITMAP_ELEMENT_ALL_BITS
;
1238 unsigned int first_word_to_mod
;
1239 BITMAP_WORD first_mask
;
1240 unsigned int last_word_to_mod
;
1241 BITMAP_WORD last_mask
;
1244 if (!elt
|| elt
->indx
!= i
)
1245 elt
= bitmap_elt_insert_after (head
, elt_prev
, i
);
1247 if (elt_start_bit
<= start
)
1249 /* The first bit to turn on is somewhere inside this
1251 first_word_to_mod
= (start
- elt_start_bit
) / BITMAP_WORD_BITS
;
1253 /* This mask should have 1s in all bits >= start position. */
1255 (((BITMAP_WORD
) 1) << ((start
% BITMAP_WORD_BITS
))) - 1;
1256 first_mask
= ~first_mask
;
1260 /* The first bit to turn on is below this start of this elt. */
1261 first_word_to_mod
= 0;
1262 first_mask
= ~(BITMAP_WORD
) 0;
1265 if (elt_end_bit_plus1
<= end_bit_plus1
)
1267 /* The last bit to turn on is beyond this elt. */
1268 last_word_to_mod
= BITMAP_ELEMENT_WORDS
- 1;
1269 last_mask
= ~(BITMAP_WORD
) 0;
1273 /* The last bit to turn on is inside to this elt. */
1275 (end_bit_plus1
- elt_start_bit
) / BITMAP_WORD_BITS
;
1277 /* The last mask should have 1s below the end bit. */
1279 (((BITMAP_WORD
) 1) << ((end_bit_plus1
% BITMAP_WORD_BITS
))) - 1;
1282 if (first_word_to_mod
== last_word_to_mod
)
1284 BITMAP_WORD mask
= first_mask
& last_mask
;
1285 elt
->bits
[first_word_to_mod
] |= mask
;
1289 elt
->bits
[first_word_to_mod
] |= first_mask
;
1290 if (BITMAP_ELEMENT_WORDS
> 2)
1291 for (ix
= first_word_to_mod
+ 1; ix
< last_word_to_mod
; ix
++)
1292 elt
->bits
[ix
] = ~(BITMAP_WORD
) 0;
1293 elt
->bits
[last_word_to_mod
] |= last_mask
;
1300 head
->current
= elt
? elt
: elt_prev
;
1301 head
->indx
= head
->current
->indx
;
1304 /* Clear COUNT bits from START in HEAD. */
1306 bitmap_clear_range (bitmap head
, unsigned int start
, unsigned int count
)
1308 unsigned int first_index
, end_bit_plus1
, last_index
;
1309 bitmap_element
*elt
;
1314 first_index
= start
/ BITMAP_ELEMENT_ALL_BITS
;
1315 end_bit_plus1
= start
+ count
;
1316 last_index
= (end_bit_plus1
- 1) / BITMAP_ELEMENT_ALL_BITS
;
1317 elt
= bitmap_find_bit (head
, start
);
1319 /* If bitmap_find_bit returns zero, the current is the closest block
1320 to the result. If the current is less than first index, find the
1321 next one. Otherwise, just set elt to be current. */
1326 if (head
->indx
< first_index
)
1328 elt
= head
->current
->next
;
1333 elt
= head
->current
;
1339 while (elt
&& (elt
->indx
<= last_index
))
1341 bitmap_element
* next_elt
= elt
->next
;
1342 unsigned elt_start_bit
= (elt
->indx
) * BITMAP_ELEMENT_ALL_BITS
;
1343 unsigned elt_end_bit_plus1
= elt_start_bit
+ BITMAP_ELEMENT_ALL_BITS
;
1346 if (elt_start_bit
>= start
&& elt_end_bit_plus1
<= end_bit_plus1
)
1347 /* Get rid of the entire elt and go to the next one. */
1348 bitmap_element_free (head
, elt
);
1351 /* Going to have to knock out some bits in this elt. */
1352 unsigned int first_word_to_mod
;
1353 BITMAP_WORD first_mask
;
1354 unsigned int last_word_to_mod
;
1355 BITMAP_WORD last_mask
;
1359 if (elt_start_bit
<= start
)
1361 /* The first bit to turn off is somewhere inside this
1363 first_word_to_mod
= (start
- elt_start_bit
) / BITMAP_WORD_BITS
;
1365 /* This mask should have 1s in all bits >= start position. */
1367 (((BITMAP_WORD
) 1) << ((start
% BITMAP_WORD_BITS
))) - 1;
1368 first_mask
= ~first_mask
;
1372 /* The first bit to turn off is below this start of this elt. */
1373 first_word_to_mod
= 0;
1375 first_mask
= ~first_mask
;
1378 if (elt_end_bit_plus1
<= end_bit_plus1
)
1380 /* The last bit to turn off is beyond this elt. */
1381 last_word_to_mod
= BITMAP_ELEMENT_WORDS
- 1;
1383 last_mask
= ~last_mask
;
1387 /* The last bit to turn off is inside to this elt. */
1389 (end_bit_plus1
- elt_start_bit
) / BITMAP_WORD_BITS
;
1391 /* The last mask should have 1s below the end bit. */
1393 (((BITMAP_WORD
) 1) << (((end_bit_plus1
) % BITMAP_WORD_BITS
))) - 1;
1397 if (first_word_to_mod
== last_word_to_mod
)
1399 BITMAP_WORD mask
= first_mask
& last_mask
;
1400 elt
->bits
[first_word_to_mod
] &= ~mask
;
1404 elt
->bits
[first_word_to_mod
] &= ~first_mask
;
1405 if (BITMAP_ELEMENT_WORDS
> 2)
1406 for (i
= first_word_to_mod
+ 1; i
< last_word_to_mod
; i
++)
1408 elt
->bits
[last_word_to_mod
] &= ~last_mask
;
1410 for (i
= 0; i
< BITMAP_ELEMENT_WORDS
; i
++)
1416 /* Check to see if there are any bits left. */
1418 bitmap_element_free (head
, elt
);
1425 head
->current
= elt
;
1426 head
->indx
= head
->current
->indx
;
1433 bitmap_compl_and_into (bitmap a
, const_bitmap b
)
1435 bitmap_element
*a_elt
= a
->first
;
1436 const bitmap_element
*b_elt
= b
->first
;
1437 bitmap_element
*a_prev
= NULL
;
1438 bitmap_element
*next
;
1440 gcc_assert (a
!= b
);
1442 if (bitmap_empty_p (a
))
1447 if (bitmap_empty_p (b
))
1453 while (a_elt
|| b_elt
)
1455 if (!b_elt
|| (a_elt
&& a_elt
->indx
< b_elt
->indx
))
1457 /* A is before B. Remove A */
1459 a_prev
= a_elt
->prev
;
1460 bitmap_element_free (a
, a_elt
);
1463 else if (!a_elt
|| b_elt
->indx
< a_elt
->indx
)
1465 /* B is before A. Copy B. */
1466 next
= bitmap_elt_insert_after (a
, a_prev
, b_elt
->indx
);
1467 memcpy (next
->bits
, b_elt
->bits
, sizeof (next
->bits
));
1469 b_elt
= b_elt
->next
;
1473 /* Matching elts, generate A = ~A & B. */
1475 BITMAP_WORD ior
= 0;
1477 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1479 BITMAP_WORD cleared
= a_elt
->bits
[ix
] & b_elt
->bits
[ix
];
1480 BITMAP_WORD r
= b_elt
->bits
[ix
] ^ cleared
;
1482 a_elt
->bits
[ix
] = r
;
1487 bitmap_element_free (a
, a_elt
);
1491 b_elt
= b_elt
->next
;
1494 gcc_checking_assert (!a
->current
== !a
->first
1495 && (!a
->current
|| a
->indx
== a
->current
->indx
));
1500 /* Insert an element corresponding to A_ELT | B_ELT after DST_PREV,
1501 overwriting DST_ELT if non-NULL. CHANGED is true if the destination bitmap
1502 had already been changed; the new value of CHANGED is returned. */
1505 bitmap_elt_ior (bitmap dst
, bitmap_element
*dst_elt
, bitmap_element
*dst_prev
,
1506 const bitmap_element
*a_elt
, const bitmap_element
*b_elt
,
1509 gcc_assert (a_elt
|| b_elt
);
1511 if (a_elt
&& b_elt
&& a_elt
->indx
== b_elt
->indx
)
1513 /* Matching elts, generate A | B. */
1516 if (!changed
&& dst_elt
&& dst_elt
->indx
== a_elt
->indx
)
1518 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1520 BITMAP_WORD r
= a_elt
->bits
[ix
] | b_elt
->bits
[ix
];
1521 if (r
!= dst_elt
->bits
[ix
])
1523 dst_elt
->bits
[ix
] = r
;
1532 dst_elt
= bitmap_elt_insert_after (dst
, dst_prev
, a_elt
->indx
);
1534 dst_elt
->indx
= a_elt
->indx
;
1535 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1537 BITMAP_WORD r
= a_elt
->bits
[ix
] | b_elt
->bits
[ix
];
1538 dst_elt
->bits
[ix
] = r
;
1544 /* Copy a single element. */
1545 const bitmap_element
*src
;
1547 if (!b_elt
|| (a_elt
&& a_elt
->indx
< b_elt
->indx
))
1552 gcc_checking_assert (src
);
1553 changed
= bitmap_elt_copy (dst
, dst_elt
, dst_prev
, src
, changed
);
1559 /* DST = A | B. Return true if DST changes. */
1562 bitmap_ior (bitmap dst
, const_bitmap a
, const_bitmap b
)
1564 bitmap_element
*dst_elt
= dst
->first
;
1565 const bitmap_element
*a_elt
= a
->first
;
1566 const bitmap_element
*b_elt
= b
->first
;
1567 bitmap_element
*dst_prev
= NULL
;
1568 bitmap_element
**dst_prev_pnext
= &dst
->first
;
1569 bool changed
= false;
1571 gcc_assert (dst
!= a
&& dst
!= b
);
1573 while (a_elt
|| b_elt
)
1575 changed
= bitmap_elt_ior (dst
, dst_elt
, dst_prev
, a_elt
, b_elt
, changed
);
1577 if (a_elt
&& b_elt
&& a_elt
->indx
== b_elt
->indx
)
1579 a_elt
= a_elt
->next
;
1580 b_elt
= b_elt
->next
;
1584 if (a_elt
&& (!b_elt
|| a_elt
->indx
<= b_elt
->indx
))
1585 a_elt
= a_elt
->next
;
1586 else if (b_elt
&& (!a_elt
|| b_elt
->indx
<= a_elt
->indx
))
1587 b_elt
= b_elt
->next
;
1590 dst_prev
= *dst_prev_pnext
;
1591 dst_prev_pnext
= &dst_prev
->next
;
1592 dst_elt
= *dst_prev_pnext
;
1598 /* Ensure that dst->current is valid. */
1599 dst
->current
= dst
->first
;
1600 bitmap_elt_clear_from (dst
, dst_elt
);
1602 gcc_checking_assert (!dst
->current
== !dst
->first
);
1604 dst
->indx
= dst
->current
->indx
;
1608 /* A |= B. Return true if A changes. */
1611 bitmap_ior_into (bitmap a
, const_bitmap b
)
1613 bitmap_element
*a_elt
= a
->first
;
1614 const bitmap_element
*b_elt
= b
->first
;
1615 bitmap_element
*a_prev
= NULL
;
1616 bitmap_element
**a_prev_pnext
= &a
->first
;
1617 bool changed
= false;
1624 /* If A lags behind B, just advance it. */
1625 if (!a_elt
|| a_elt
->indx
== b_elt
->indx
)
1627 changed
= bitmap_elt_ior (a
, a_elt
, a_prev
, a_elt
, b_elt
, changed
);
1628 b_elt
= b_elt
->next
;
1630 else if (a_elt
->indx
> b_elt
->indx
)
1632 changed
= bitmap_elt_copy (a
, NULL
, a_prev
, b_elt
, changed
);
1633 b_elt
= b_elt
->next
;
1636 a_prev
= *a_prev_pnext
;
1637 a_prev_pnext
= &a_prev
->next
;
1638 a_elt
= *a_prev_pnext
;
1641 gcc_checking_assert (!a
->current
== !a
->first
);
1643 a
->indx
= a
->current
->indx
;
1650 bitmap_xor (bitmap dst
, const_bitmap a
, const_bitmap b
)
1652 bitmap_element
*dst_elt
= dst
->first
;
1653 const bitmap_element
*a_elt
= a
->first
;
1654 const bitmap_element
*b_elt
= b
->first
;
1655 bitmap_element
*dst_prev
= NULL
;
1657 gcc_assert (dst
!= a
&& dst
!= b
);
1664 while (a_elt
|| b_elt
)
1666 if (a_elt
&& b_elt
&& a_elt
->indx
== b_elt
->indx
)
1668 /* Matching elts, generate A ^ B. */
1670 BITMAP_WORD ior
= 0;
1673 dst_elt
= bitmap_elt_insert_after (dst
, dst_prev
, a_elt
->indx
);
1675 dst_elt
->indx
= a_elt
->indx
;
1676 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1678 BITMAP_WORD r
= a_elt
->bits
[ix
] ^ b_elt
->bits
[ix
];
1681 dst_elt
->bits
[ix
] = r
;
1683 a_elt
= a_elt
->next
;
1684 b_elt
= b_elt
->next
;
1688 dst_elt
= dst_elt
->next
;
1693 /* Copy a single element. */
1694 const bitmap_element
*src
;
1696 if (!b_elt
|| (a_elt
&& a_elt
->indx
< b_elt
->indx
))
1699 a_elt
= a_elt
->next
;
1704 b_elt
= b_elt
->next
;
1708 dst_elt
= bitmap_elt_insert_after (dst
, dst_prev
, src
->indx
);
1710 dst_elt
->indx
= src
->indx
;
1711 memcpy (dst_elt
->bits
, src
->bits
, sizeof (dst_elt
->bits
));
1713 dst_elt
= dst_elt
->next
;
1716 /* Ensure that dst->current is valid. */
1717 dst
->current
= dst
->first
;
1718 bitmap_elt_clear_from (dst
, dst_elt
);
1719 gcc_checking_assert (!dst
->current
== !dst
->first
);
1721 dst
->indx
= dst
->current
->indx
;
1727 bitmap_xor_into (bitmap a
, const_bitmap b
)
1729 bitmap_element
*a_elt
= a
->first
;
1730 const bitmap_element
*b_elt
= b
->first
;
1731 bitmap_element
*a_prev
= NULL
;
1741 if (!a_elt
|| b_elt
->indx
< a_elt
->indx
)
1744 bitmap_element
*dst
= bitmap_elt_insert_after (a
, a_prev
, b_elt
->indx
);
1745 memcpy (dst
->bits
, b_elt
->bits
, sizeof (dst
->bits
));
1747 b_elt
= b_elt
->next
;
1749 else if (a_elt
->indx
< b_elt
->indx
)
1752 a_elt
= a_elt
->next
;
1756 /* Matching elts, generate A ^= B. */
1758 BITMAP_WORD ior
= 0;
1759 bitmap_element
*next
= a_elt
->next
;
1761 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1763 BITMAP_WORD r
= a_elt
->bits
[ix
] ^ b_elt
->bits
[ix
];
1766 a_elt
->bits
[ix
] = r
;
1768 b_elt
= b_elt
->next
;
1772 bitmap_element_free (a
, a_elt
);
1776 gcc_checking_assert (!a
->current
== !a
->first
);
1778 a
->indx
= a
->current
->indx
;
1781 /* Return true if two bitmaps are identical.
1782 We do not bother with a check for pointer equality, as that never
1783 occurs in practice. */
1786 bitmap_equal_p (const_bitmap a
, const_bitmap b
)
1788 const bitmap_element
*a_elt
;
1789 const bitmap_element
*b_elt
;
1792 for (a_elt
= a
->first
, b_elt
= b
->first
;
1794 a_elt
= a_elt
->next
, b_elt
= b_elt
->next
)
1796 if (a_elt
->indx
!= b_elt
->indx
)
1798 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1799 if (a_elt
->bits
[ix
] != b_elt
->bits
[ix
])
1802 return !a_elt
&& !b_elt
;
1805 /* Return true if A AND B is not empty. */
1808 bitmap_intersect_p (const_bitmap a
, const_bitmap b
)
1810 const bitmap_element
*a_elt
;
1811 const bitmap_element
*b_elt
;
1814 for (a_elt
= a
->first
, b_elt
= b
->first
;
1817 if (a_elt
->indx
< b_elt
->indx
)
1818 a_elt
= a_elt
->next
;
1819 else if (b_elt
->indx
< a_elt
->indx
)
1820 b_elt
= b_elt
->next
;
1823 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1824 if (a_elt
->bits
[ix
] & b_elt
->bits
[ix
])
1826 a_elt
= a_elt
->next
;
1827 b_elt
= b_elt
->next
;
1833 /* Return true if A AND NOT B is not empty. */
1836 bitmap_intersect_compl_p (const_bitmap a
, const_bitmap b
)
1838 const bitmap_element
*a_elt
;
1839 const bitmap_element
*b_elt
;
1841 for (a_elt
= a
->first
, b_elt
= b
->first
;
1844 if (a_elt
->indx
< b_elt
->indx
)
1846 else if (b_elt
->indx
< a_elt
->indx
)
1847 b_elt
= b_elt
->next
;
1850 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1851 if (a_elt
->bits
[ix
] & ~b_elt
->bits
[ix
])
1853 a_elt
= a_elt
->next
;
1854 b_elt
= b_elt
->next
;
1857 return a_elt
!= NULL
;
1861 /* DST = A | (FROM1 & ~FROM2). Return true if DST changes. */
1864 bitmap_ior_and_compl (bitmap dst
, const_bitmap a
, const_bitmap b
, const_bitmap kill
)
1866 bool changed
= false;
1868 bitmap_element
*dst_elt
= dst
->first
;
1869 const bitmap_element
*a_elt
= a
->first
;
1870 const bitmap_element
*b_elt
= b
->first
;
1871 const bitmap_element
*kill_elt
= kill
->first
;
1872 bitmap_element
*dst_prev
= NULL
;
1873 bitmap_element
**dst_prev_pnext
= &dst
->first
;
1875 gcc_assert (dst
!= a
&& dst
!= b
&& dst
!= kill
);
1877 /* Special cases. We don't bother checking for bitmap_equal_p (b, kill). */
1878 if (b
== kill
|| bitmap_empty_p (b
))
1880 changed
= !bitmap_equal_p (dst
, a
);
1882 bitmap_copy (dst
, a
);
1885 if (bitmap_empty_p (kill
))
1886 return bitmap_ior (dst
, a
, b
);
1887 if (bitmap_empty_p (a
))
1888 return bitmap_and_compl (dst
, b
, kill
);
1890 while (a_elt
|| b_elt
)
1892 bool new_element
= false;
1895 while (kill_elt
&& kill_elt
->indx
< b_elt
->indx
)
1896 kill_elt
= kill_elt
->next
;
1898 if (b_elt
&& kill_elt
&& kill_elt
->indx
== b_elt
->indx
1899 && (!a_elt
|| a_elt
->indx
>= b_elt
->indx
))
1901 bitmap_element tmp_elt
;
1904 BITMAP_WORD ior
= 0;
1905 tmp_elt
.indx
= b_elt
->indx
;
1906 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
1908 BITMAP_WORD r
= b_elt
->bits
[ix
] & ~kill_elt
->bits
[ix
];
1910 tmp_elt
.bits
[ix
] = r
;
1915 changed
= bitmap_elt_ior (dst
, dst_elt
, dst_prev
,
1916 a_elt
, &tmp_elt
, changed
);
1918 if (a_elt
&& a_elt
->indx
== b_elt
->indx
)
1919 a_elt
= a_elt
->next
;
1922 b_elt
= b_elt
->next
;
1923 kill_elt
= kill_elt
->next
;
1927 changed
= bitmap_elt_ior (dst
, dst_elt
, dst_prev
,
1928 a_elt
, b_elt
, changed
);
1931 if (a_elt
&& b_elt
&& a_elt
->indx
== b_elt
->indx
)
1933 a_elt
= a_elt
->next
;
1934 b_elt
= b_elt
->next
;
1938 if (a_elt
&& (!b_elt
|| a_elt
->indx
<= b_elt
->indx
))
1939 a_elt
= a_elt
->next
;
1940 else if (b_elt
&& (!a_elt
|| b_elt
->indx
<= a_elt
->indx
))
1941 b_elt
= b_elt
->next
;
1947 dst_prev
= *dst_prev_pnext
;
1948 dst_prev_pnext
= &dst_prev
->next
;
1949 dst_elt
= *dst_prev_pnext
;
1956 /* Ensure that dst->current is valid. */
1957 dst
->current
= dst
->first
;
1958 bitmap_elt_clear_from (dst
, dst_elt
);
1960 gcc_checking_assert (!dst
->current
== !dst
->first
);
1962 dst
->indx
= dst
->current
->indx
;
1967 /* A |= (FROM1 & ~FROM2). Return true if A changes. */
1970 bitmap_ior_and_compl_into (bitmap a
, const_bitmap from1
, const_bitmap from2
)
1975 bitmap_initialize (&tmp
, &bitmap_default_obstack
);
1976 bitmap_and_compl (&tmp
, from1
, from2
);
1977 changed
= bitmap_ior_into (a
, &tmp
);
1978 bitmap_clear (&tmp
);
1983 /* A |= (B & C). Return true if A changes. */
1986 bitmap_ior_and_into (bitmap a
, const_bitmap b
, const_bitmap c
)
1988 bitmap_element
*a_elt
= a
->first
;
1989 const bitmap_element
*b_elt
= b
->first
;
1990 const bitmap_element
*c_elt
= c
->first
;
1991 bitmap_element and_elt
;
1992 bitmap_element
*a_prev
= NULL
;
1993 bitmap_element
**a_prev_pnext
= &a
->first
;
1994 bool changed
= false;
1998 return bitmap_ior_into (a
, b
);
1999 if (bitmap_empty_p (b
) || bitmap_empty_p (c
))
2003 while (b_elt
&& c_elt
)
2005 BITMAP_WORD overall
;
2007 /* Find a common item of B and C. */
2008 while (b_elt
->indx
!= c_elt
->indx
)
2010 if (b_elt
->indx
< c_elt
->indx
)
2012 b_elt
= b_elt
->next
;
2018 c_elt
= c_elt
->next
;
2025 and_elt
.indx
= b_elt
->indx
;
2026 for (ix
= 0; ix
< BITMAP_ELEMENT_WORDS
; ix
++)
2028 and_elt
.bits
[ix
] = b_elt
->bits
[ix
] & c_elt
->bits
[ix
];
2029 overall
|= and_elt
.bits
[ix
];
2032 b_elt
= b_elt
->next
;
2033 c_elt
= c_elt
->next
;
2037 /* Now find a place to insert AND_ELT. */
2040 ix
= a_elt
? a_elt
->indx
: and_elt
.indx
;
2041 if (ix
== and_elt
.indx
)
2042 changed
= bitmap_elt_ior (a
, a_elt
, a_prev
, a_elt
, &and_elt
, changed
);
2043 else if (ix
> and_elt
.indx
)
2044 changed
= bitmap_elt_copy (a
, NULL
, a_prev
, &and_elt
, changed
);
2046 a_prev
= *a_prev_pnext
;
2047 a_prev_pnext
= &a_prev
->next
;
2048 a_elt
= *a_prev_pnext
;
2050 /* If A lagged behind B/C, we advanced it so loop once more. */
2052 while (ix
< and_elt
.indx
);
2056 gcc_checking_assert (!a
->current
== !a
->first
);
2058 a
->indx
= a
->current
->indx
;
2062 /* Compute hash of bitmap (for purposes of hashing). */
2064 bitmap_hash (const_bitmap head
)
2066 const bitmap_element
*ptr
;
2067 BITMAP_WORD hash
= 0;
2070 for (ptr
= head
->first
; ptr
; ptr
= ptr
->next
)
2073 for (ix
= 0; ix
!= BITMAP_ELEMENT_WORDS
; ix
++)
2074 hash
^= ptr
->bits
[ix
];
2076 return (hashval_t
)hash
;
2080 /* Debugging function to print out the contents of a bitmap. */
2083 debug_bitmap_file (FILE *file
, const_bitmap head
)
2085 const bitmap_element
*ptr
;
2087 fprintf (file
, "\nfirst = " HOST_PTR_PRINTF
2088 " current = " HOST_PTR_PRINTF
" indx = %u\n",
2089 (void *) head
->first
, (void *) head
->current
, head
->indx
);
2091 for (ptr
= head
->first
; ptr
; ptr
= ptr
->next
)
2093 unsigned int i
, j
, col
= 26;
2095 fprintf (file
, "\t" HOST_PTR_PRINTF
" next = " HOST_PTR_PRINTF
2096 " prev = " HOST_PTR_PRINTF
" indx = %u\n\t\tbits = {",
2097 (const void*) ptr
, (const void*) ptr
->next
,
2098 (const void*) ptr
->prev
, ptr
->indx
);
2100 for (i
= 0; i
< BITMAP_ELEMENT_WORDS
; i
++)
2101 for (j
= 0; j
< BITMAP_WORD_BITS
; j
++)
2102 if ((ptr
->bits
[i
] >> j
) & 1)
2106 fprintf (file
, "\n\t\t\t");
2110 fprintf (file
, " %u", (ptr
->indx
* BITMAP_ELEMENT_ALL_BITS
2111 + i
* BITMAP_WORD_BITS
+ j
));
2115 fprintf (file
, " }\n");
2119 /* Function to be called from the debugger to print the contents
2123 debug_bitmap (const_bitmap head
)
2125 debug_bitmap_file (stderr
, head
);
2128 /* Function to print out the contents of a bitmap. Unlike debug_bitmap_file,
2129 it does not print anything but the bits. */
2132 bitmap_print (FILE *file
, const_bitmap head
, const char *prefix
,
2135 const char *comma
= "";
2139 fputs (prefix
, file
);
2140 EXECUTE_IF_SET_IN_BITMAP (head
, 0, i
, bi
)
2142 fprintf (file
, "%s%d", comma
, i
);
2145 fputs (suffix
, file
);
2149 /* Used to accumulate statistics about bitmap sizes. */
2150 struct bitmap_output_info
2156 /* Called via hash_table::traverse. Output bitmap descriptor pointed out by
2157 SLOT and update statistics. */
2159 print_statistics (bitmap_descriptor_d
**slot
, bitmap_output_info
*i
)
2161 bitmap_descriptor d
= *slot
;
2166 const char *s1
= d
->file
;
2168 while ((s2
= strstr (s1
, "gcc/")))
2170 sprintf (s
, "%s:%i (%s)", s1
, d
->line
, d
->function
);
2173 "%-41s %9u %15"PRId64
" %15"PRId64
" %15"PRId64
2174 " %10"PRId64
" %10"PRId64
"\n",
2176 d
->allocated
, d
->peak
, d
->current
,
2177 d
->nsearches
, d
->search_iter
);
2178 i
->size
+= d
->allocated
;
2179 i
->count
+= d
->created
;
2184 /* Output per-bitmap memory usage statistics. */
2186 dump_bitmap_statistics (void)
2188 struct bitmap_output_info info
;
2190 if (! GATHER_STATISTICS
)
2193 if (!bitmap_desc_hash
)
2197 "\n%-41s %9s %15s %15s %15s %10s %10s\n",
2198 "Bitmap", "Overall",
2199 "Allocated", "Peak", "Leak",
2200 "searched", "search_itr");
2201 fprintf (stderr
, "---------------------------------------------------------------------------------\n");
2204 bitmap_desc_hash
->traverse
<bitmap_output_info
*, print_statistics
> (&info
);
2205 fprintf (stderr
, "---------------------------------------------------------------------------------\n");
2207 "%-41s %9"PRId64
" %15"PRId64
"\n",
2208 "Total", info
.count
, info
.size
);
2209 fprintf (stderr
, "---------------------------------------------------------------------------------\n");
2213 debug (const bitmap_head
&ref
)
2215 dump_bitmap (stderr
, &ref
);
2219 debug (const bitmap_head
*ptr
)
2224 fprintf (stderr
, "<nil>\n");
2228 #include "gt-bitmap.h"