1 /* Functions to support general ended bitmaps.
2 Copyright (C) 1997-2019 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/>. */
23 /* Implementation of sparse integer sets as a linked list or tree.
25 This sparse set representation is suitable for sparse sets with an
26 unknown (a priori) universe.
28 Sets are represented as double-linked lists of container nodes of
29 type "struct bitmap_element" or as a binary trees of the same
30 container nodes. Each container node consists of an index for the
31 first member that could be held in the container, a small array of
32 integers that represent the members in the container, and pointers
33 to the next and previous element in the linked list, or left and
34 right children in the tree. In linked-list form, the container
35 nodes in the list are sorted in ascending order, i.e. the head of
36 the list holds the element with the smallest member of the set.
37 In tree form, nodes to the left have a smaller container index.
39 For a given member I in the set:
40 - the element for I will have index is I / (bits per element)
41 - the position for I within element is I % (bits per element)
43 This representation is very space-efficient for large sparse sets, and
44 the size of the set can be changed dynamically without much overhead.
45 An important parameter is the number of bits per element. In this
46 implementation, there are 128 bits per element. This results in a
47 high storage overhead *per element*, but a small overall overhead if
48 the set is very sparse.
50 The storage requirements for linked-list sparse sets are O(E), with E->N
51 in the worst case (a sparse set with large distances between the values
54 This representation also works well for data flow problems where the size
55 of the set may grow dynamically, but care must be taken that the member_p,
56 add_member, and remove_member operations occur with a suitable access
59 The linked-list set representation works well for problems involving very
60 sparse sets. The canonical example in GCC is, of course, the "set of
61 sets" for some CFG-based data flow problems (liveness analysis, dominance
64 For random-access sparse sets of unknown universe, the binary tree
65 representation is likely to be a more suitable choice. Theoretical
66 access times for the binary tree representation are better than those
67 for the linked-list, but in practice this is only true for truely
70 Often the most suitable representation during construction of the set
71 is not the best choice for the usage of the set. For such cases, the
72 "view" of the set can be changed from one representation to the other.
73 This is an O(E) operation:
75 * from list to tree view : bitmap_tree_view
76 * from tree to list view : bitmap_list_view
78 Traversing linked lists or trees can be cache-unfriendly. Performance
79 can be improved by keeping container nodes in the set grouped together
80 in memory, using a dedicated obstack for a set (or group of related
81 sets). Elements allocated on obstacks are released to a free-list and
82 taken off the free list. If multiple sets are allocated on the same
83 obstack, elements freed from one set may be re-used for one of the other
84 sets. This usually helps avoid cache misses.
86 A single free-list is used for all sets allocated in GGC space. This is
87 bad for persistent sets, so persistent sets should be allocated on an
88 obstack whenever possible.
90 For random-access sets with a known, relatively small universe size, the
91 SparseSet or simple bitmap representations may be more efficient than a
98 In linked-list form, in-order iterations of the set can be executed
99 efficiently. The downside is that many random-access operations are
100 relatively slow, because the linked list has to be traversed to test
101 membership (i.e. member_p/ add_member/remove_member).
103 To improve the performance of this set representation, the last
104 accessed element and its index are cached. For membership tests on
105 members close to recently accessed members, the cached last element
106 improves membership test to a constant-time operation.
108 The following operations can always be performed in O(1) time in
111 * clear : bitmap_clear
112 * smallest_member : bitmap_first_set_bit
113 * choose_one : (not implemented, but could be
116 The following operations can be performed in O(E) time worst-case in
117 list view (with E the number of elements in the linked list), but in
118 O(1) time with a suitable access patterns:
120 * member_p : bitmap_bit_p
121 * add_member : bitmap_set_bit / bitmap_set_range
122 * remove_member : bitmap_clear_bit / bitmap_clear_range
124 The following operations can be performed in O(E) time in list view:
126 * cardinality : bitmap_count_bits
127 * largest_member : bitmap_last_set_bit (but this could
128 in constant time with a pointer to
129 the last element in the chain)
130 * set_size : bitmap_last_set_bit
132 In tree view the following operations can all be performed in O(log E)
133 amortized time with O(E) worst-case behavior.
142 Additionally, the linked-list sparse set representation supports
143 enumeration of the members in O(E) time:
145 * forall : EXECUTE_IF_SET_IN_BITMAP
146 * set_copy : bitmap_copy
147 * set_intersection : bitmap_intersect_p /
148 bitmap_and / bitmap_and_into /
149 EXECUTE_IF_AND_IN_BITMAP
150 * set_union : bitmap_ior / bitmap_ior_into
151 * set_difference : bitmap_intersect_compl_p /
152 bitmap_and_comp / bitmap_and_comp_into /
153 EXECUTE_IF_AND_COMPL_IN_BITMAP
154 * set_disjuction : bitmap_xor_comp / bitmap_xor_comp_into
155 * set_compare : bitmap_equal_p
157 Some operations on 3 sets that occur frequently in data flow problems
158 are also implemented:
160 * A | (B & C) : bitmap_ior_and_into
161 * A | (B & ~C) : bitmap_ior_and_compl /
162 bitmap_ior_and_compl_into
167 An alternate "view" of a bitmap is its binary tree representation.
168 For this representation, splay trees are used because they can be
169 implemented using the same data structures as the linked list, with
170 no overhead for meta-data (like color, or rank) on the tree nodes.
172 In binary tree form, random-access to the set is much more efficient
173 than for the linked-list representation. Downsides are the high cost
174 of clearing the set, and the relatively large number of operations
175 necessary to balance the tree. Also, iterating the set members is
178 As for the linked-list representation, the last accessed element and
179 its index are cached, so that membership tests on the latest accessed
180 members is a constant-time operation. Other lookups take O(logE)
181 time amortized (but O(E) time worst-case).
183 The following operations can always be performed in O(1) time:
185 * choose_one : (not implemented, but could be
186 implemented in constant time)
188 The following operations can be performed in O(logE) time amortized
189 but O(E) time worst-case, but in O(1) time if the same element is
192 * member_p : bitmap_bit_p
193 * add_member : bitmap_set_bit
194 * remove_member : bitmap_clear_bit
196 The following operations can be performed in O(logE) time amortized
197 but O(E) time worst-case:
199 * smallest_member : bitmap_first_set_bit
200 * largest_member : bitmap_last_set_bit
201 * set_size : bitmap_last_set_bit
203 The following operations can be performed in O(E) time:
205 * clear : bitmap_clear
207 The binary tree sparse set representation does *not* support any form
208 of enumeration, and does also *not* support logical operations on sets.
209 The binary tree representation is only supposed to be used for sets
210 on which many random-access membership tests will happen. */
214 /* Bitmap memory usage. */
215 class bitmap_usage
: public mem_usage
218 /* Default contructor. */
219 bitmap_usage (): m_nsearches (0), m_search_iter (0) {}
221 bitmap_usage (size_t allocated
, size_t times
, size_t peak
,
222 uint64_t nsearches
, uint64_t search_iter
)
223 : mem_usage (allocated
, times
, peak
),
224 m_nsearches (nsearches
), m_search_iter (search_iter
) {}
226 /* Sum the usage with SECOND usage. */
228 operator+ (const bitmap_usage
&second
)
230 return bitmap_usage (m_allocated
+ second
.m_allocated
,
231 m_times
+ second
.m_times
,
232 m_peak
+ second
.m_peak
,
233 m_nsearches
+ second
.m_nsearches
,
234 m_search_iter
+ second
.m_search_iter
);
237 /* Dump usage coupled to LOC location, where TOTAL is sum of all rows. */
239 dump (mem_location
*loc
, mem_usage
&total
) const
241 char *location_string
= loc
->to_string ();
243 fprintf (stderr
, "%-48s " PRsa (9) ":%5.1f%%"
244 PRsa (9) PRsa (9) ":%5.1f%%"
245 PRsa (11) PRsa (11) "%10s\n",
246 location_string
, SIZE_AMOUNT (m_allocated
),
247 get_percent (m_allocated
, total
.m_allocated
),
248 SIZE_AMOUNT (m_peak
), SIZE_AMOUNT (m_times
),
249 get_percent (m_times
, total
.m_times
),
250 SIZE_AMOUNT (m_nsearches
), SIZE_AMOUNT (m_search_iter
),
251 loc
->m_ggc
? "ggc" : "heap");
253 free (location_string
);
256 /* Dump header with NAME. */
258 dump_header (const char *name
)
260 fprintf (stderr
, "%-48s %11s%16s%17s%12s%12s%10s\n", name
, "Leak", "Peak",
261 "Times", "N searches", "Search iter", "Type");
264 /* Number search operations. */
265 uint64_t m_nsearches
;
266 /* Number of search iterations. */
267 uint64_t m_search_iter
;
270 /* Bitmap memory description. */
271 extern mem_alloc_description
<bitmap_usage
> bitmap_mem_desc
;
273 /* Fundamental storage type for bitmap. */
275 typedef unsigned long BITMAP_WORD
;
276 /* BITMAP_WORD_BITS needs to be unsigned, but cannot contain casts as
277 it is used in preprocessor directives -- hence the 1u. */
278 #define BITMAP_WORD_BITS (CHAR_BIT * SIZEOF_LONG * 1u)
280 /* Number of words to use for each element in the linked list. */
282 #ifndef BITMAP_ELEMENT_WORDS
283 #define BITMAP_ELEMENT_WORDS ((128 + BITMAP_WORD_BITS - 1) / BITMAP_WORD_BITS)
286 /* Number of bits in each actual element of a bitmap. */
288 #define BITMAP_ELEMENT_ALL_BITS (BITMAP_ELEMENT_WORDS * BITMAP_WORD_BITS)
290 /* Obstack for allocating bitmaps and elements from. */
291 struct bitmap_obstack
{
292 struct bitmap_element
*elements
;
294 struct obstack obstack
;
297 /* Bitmap set element. We use a linked list to hold only the bits that
298 are set. This allows for use to grow the bitset dynamically without
299 having to realloc and copy a giant bit array.
301 The free list is implemented as a list of lists. There is one
302 outer list connected together by prev fields. Each element of that
303 outer is an inner list (that may consist only of the outer list
304 element) that are connected by the next fields. The prev pointer
305 is undefined for interior elements. This allows
306 bitmap_elt_clear_from to be implemented in unit time rather than
307 linear in the number of elements to be freed. */
309 struct GTY((chain_next ("%h.next"))) bitmap_element
{
310 /* In list form, the next element in the linked list;
311 in tree form, the left child node in the tree. */
312 struct bitmap_element
*next
;
313 /* In list form, the previous element in the linked list;
314 in tree form, the right child node in the tree. */
315 struct bitmap_element
*prev
;
316 /* regno/BITMAP_ELEMENT_ALL_BITS. */
318 /* Bits that are set, counting from INDX, inclusive */
319 BITMAP_WORD bits
[BITMAP_ELEMENT_WORDS
];
322 /* Head of bitmap linked list. The 'current' member points to something
323 already pointed to by the chain started by first, so GTY((skip)) it. */
325 class GTY(()) bitmap_head
{
327 static bitmap_obstack crashme
;
328 /* Poison obstack to not make it not a valid initialized GC bitmap. */
329 CONSTEXPR
bitmap_head()
330 : indx (0), tree_form (false), padding (0), alloc_descriptor (0), first (NULL
),
331 current (NULL
), obstack (&crashme
)
333 /* Index of last element looked at. */
335 /* False if the bitmap is in list form; true if the bitmap is in tree form.
336 Bitmap iterators only work on bitmaps in list form. */
337 unsigned tree_form
: 1;
338 /* Next integer is shifted, so padding is needed. */
340 /* Bitmap UID used for memory allocation statistics. */
341 unsigned alloc_descriptor
: 29;
342 /* In list form, the first element in the linked list;
343 in tree form, the root of the tree. */
344 bitmap_element
*first
;
345 /* Last element looked at. */
346 bitmap_element
* GTY((skip(""))) current
;
347 /* Obstack to allocate elements from. If NULL, then use GGC allocation. */
348 bitmap_obstack
* GTY((skip(""))) obstack
;
353 /* Get bitmap descriptor UID casted to an unsigned integer pointer.
354 Shift the descriptor because pointer_hash<Type>::hash is
355 doing >> 3 shift operation. */
356 unsigned *get_descriptor ()
358 return (unsigned *)(ptrdiff_t)(alloc_descriptor
<< 3);
363 extern bitmap_element bitmap_zero_bits
; /* Zero bitmap element */
364 extern bitmap_obstack bitmap_default_obstack
; /* Default bitmap obstack */
366 /* Change the view of the bitmap to list, or tree. */
367 void bitmap_list_view (bitmap
);
368 void bitmap_tree_view (bitmap
);
370 /* Clear a bitmap by freeing up the linked list. */
371 extern void bitmap_clear (bitmap
);
373 /* Copy a bitmap to another bitmap. */
374 extern void bitmap_copy (bitmap
, const_bitmap
);
376 /* Move a bitmap to another bitmap. */
377 extern void bitmap_move (bitmap
, bitmap
);
379 /* True if two bitmaps are identical. */
380 extern bool bitmap_equal_p (const_bitmap
, const_bitmap
);
382 /* True if the bitmaps intersect (their AND is non-empty). */
383 extern bool bitmap_intersect_p (const_bitmap
, const_bitmap
);
385 /* True if the complement of the second intersects the first (their
386 AND_COMPL is non-empty). */
387 extern bool bitmap_intersect_compl_p (const_bitmap
, const_bitmap
);
389 /* True if MAP is an empty bitmap. */
390 inline bool bitmap_empty_p (const_bitmap map
)
395 /* True if the bitmap has only a single bit set. */
396 extern bool bitmap_single_bit_set_p (const_bitmap
);
398 /* Count the number of bits set in the bitmap. */
399 extern unsigned long bitmap_count_bits (const_bitmap
);
401 /* Count the number of unique bits set across the two bitmaps. */
402 extern unsigned long bitmap_count_unique_bits (const_bitmap
, const_bitmap
);
404 /* Boolean operations on bitmaps. The _into variants are two operand
405 versions that modify the first source operand. The other variants
406 are three operand versions that to not destroy the source bitmaps.
407 The operations supported are &, & ~, |, ^. */
408 extern void bitmap_and (bitmap
, const_bitmap
, const_bitmap
);
409 extern bool bitmap_and_into (bitmap
, const_bitmap
);
410 extern bool bitmap_and_compl (bitmap
, const_bitmap
, const_bitmap
);
411 extern bool bitmap_and_compl_into (bitmap
, const_bitmap
);
412 #define bitmap_compl_and(DST, A, B) bitmap_and_compl (DST, B, A)
413 extern void bitmap_compl_and_into (bitmap
, const_bitmap
);
414 extern void bitmap_clear_range (bitmap
, unsigned int, unsigned int);
415 extern void bitmap_set_range (bitmap
, unsigned int, unsigned int);
416 extern bool bitmap_ior (bitmap
, const_bitmap
, const_bitmap
);
417 extern bool bitmap_ior_into (bitmap
, const_bitmap
);
418 extern void bitmap_xor (bitmap
, const_bitmap
, const_bitmap
);
419 extern void bitmap_xor_into (bitmap
, const_bitmap
);
421 /* DST = A | (B & C). Return true if DST changes. */
422 extern bool bitmap_ior_and_into (bitmap DST
, const_bitmap B
, const_bitmap C
);
423 /* DST = A | (B & ~C). Return true if DST changes. */
424 extern bool bitmap_ior_and_compl (bitmap DST
, const_bitmap A
,
425 const_bitmap B
, const_bitmap C
);
426 /* A |= (B & ~C). Return true if A changes. */
427 extern bool bitmap_ior_and_compl_into (bitmap A
,
428 const_bitmap B
, const_bitmap C
);
430 /* Clear a single bit in a bitmap. Return true if the bit changed. */
431 extern bool bitmap_clear_bit (bitmap
, int);
433 /* Set a single bit in a bitmap. Return true if the bit changed. */
434 extern bool bitmap_set_bit (bitmap
, int);
436 /* Return true if a bit is set in a bitmap. */
437 extern int bitmap_bit_p (bitmap
, int);
439 /* Debug functions to print a bitmap. */
440 extern void debug_bitmap (const_bitmap
);
441 extern void debug_bitmap_file (FILE *, const_bitmap
);
443 /* Print a bitmap. */
444 extern void bitmap_print (FILE *, const_bitmap
, const char *, const char *);
446 /* Initialize and release a bitmap obstack. */
447 extern void bitmap_obstack_initialize (bitmap_obstack
*);
448 extern void bitmap_obstack_release (bitmap_obstack
*);
449 extern void bitmap_register (bitmap MEM_STAT_DECL
);
450 extern void dump_bitmap_statistics (void);
452 /* Initialize a bitmap header. OBSTACK indicates the bitmap obstack
453 to allocate from, NULL for GC'd bitmap. */
456 bitmap_initialize (bitmap head
, bitmap_obstack
*obstack CXX_MEM_STAT_INFO
)
458 head
->first
= head
->current
= NULL
;
459 head
->indx
= head
->tree_form
= 0;
461 head
->alloc_descriptor
= 0;
462 head
->obstack
= obstack
;
463 if (GATHER_STATISTICS
)
464 bitmap_register (head PASS_MEM_STAT
);
467 /* Release a bitmap (but not its head). This is suitable for pairing with
468 bitmap_initialize. */
471 bitmap_release (bitmap head
)
474 /* Poison the obstack pointer so the obstack can be safely released.
475 Do not zero it as the bitmap then becomes initialized GC. */
476 head
->obstack
= &bitmap_head::crashme
;
479 /* Allocate and free bitmaps from obstack, malloc and gc'd memory. */
480 extern bitmap
bitmap_alloc (bitmap_obstack
*obstack CXX_MEM_STAT_INFO
);
481 #define BITMAP_ALLOC bitmap_alloc
482 extern bitmap
bitmap_gc_alloc (ALONE_CXX_MEM_STAT_INFO
);
483 #define BITMAP_GGC_ALLOC bitmap_gc_alloc
484 extern void bitmap_obstack_free (bitmap
);
486 /* A few compatibility/functions macros for compatibility with sbitmaps */
487 inline void dump_bitmap (FILE *file
, const_bitmap map
)
489 bitmap_print (file
, map
, "", "\n");
491 extern void debug (const bitmap_head
&ref
);
492 extern void debug (const bitmap_head
*ptr
);
494 extern unsigned bitmap_first_set_bit (const_bitmap
);
495 extern unsigned bitmap_last_set_bit (const_bitmap
);
497 /* Compute bitmap hash (for purposes of hashing etc.) */
498 extern hashval_t
bitmap_hash (const_bitmap
);
500 /* Do any cleanup needed on a bitmap when it is no longer used. */
501 #define BITMAP_FREE(BITMAP) \
502 ((void) (bitmap_obstack_free ((bitmap) BITMAP), (BITMAP) = (bitmap) NULL))
504 /* Iterator for bitmaps. */
506 struct bitmap_iterator
508 /* Pointer to the current bitmap element. */
509 bitmap_element
*elt1
;
511 /* Pointer to 2nd bitmap element when two are involved. */
512 bitmap_element
*elt2
;
514 /* Word within the current element. */
517 /* Contents of the actually processed word. When finding next bit
518 it is shifted right, so that the actual bit is always the least
519 significant bit of ACTUAL. */
523 /* Initialize a single bitmap iterator. START_BIT is the first bit to
527 bmp_iter_set_init (bitmap_iterator
*bi
, const_bitmap map
,
528 unsigned start_bit
, unsigned *bit_no
)
530 bi
->elt1
= map
->first
;
533 gcc_checking_assert (!map
->tree_form
);
535 /* Advance elt1 until it is not before the block containing start_bit. */
540 bi
->elt1
= &bitmap_zero_bits
;
544 if (bi
->elt1
->indx
>= start_bit
/ BITMAP_ELEMENT_ALL_BITS
)
546 bi
->elt1
= bi
->elt1
->next
;
549 /* We might have gone past the start bit, so reinitialize it. */
550 if (bi
->elt1
->indx
!= start_bit
/ BITMAP_ELEMENT_ALL_BITS
)
551 start_bit
= bi
->elt1
->indx
* BITMAP_ELEMENT_ALL_BITS
;
553 /* Initialize for what is now start_bit. */
554 bi
->word_no
= start_bit
/ BITMAP_WORD_BITS
% BITMAP_ELEMENT_WORDS
;
555 bi
->bits
= bi
->elt1
->bits
[bi
->word_no
];
556 bi
->bits
>>= start_bit
% BITMAP_WORD_BITS
;
558 /* If this word is zero, we must make sure we're not pointing at the
559 first bit, otherwise our incrementing to the next word boundary
560 will fail. It won't matter if this increment moves us into the
562 start_bit
+= !bi
->bits
;
567 /* Initialize an iterator to iterate over the intersection of two
568 bitmaps. START_BIT is the bit to commence from. */
571 bmp_iter_and_init (bitmap_iterator
*bi
, const_bitmap map1
, const_bitmap map2
,
572 unsigned start_bit
, unsigned *bit_no
)
574 bi
->elt1
= map1
->first
;
575 bi
->elt2
= map2
->first
;
577 gcc_checking_assert (!map1
->tree_form
&& !map2
->tree_form
);
579 /* Advance elt1 until it is not before the block containing
589 if (bi
->elt1
->indx
>= start_bit
/ BITMAP_ELEMENT_ALL_BITS
)
591 bi
->elt1
= bi
->elt1
->next
;
594 /* Advance elt2 until it is not before elt1. */
599 bi
->elt1
= bi
->elt2
= &bitmap_zero_bits
;
603 if (bi
->elt2
->indx
>= bi
->elt1
->indx
)
605 bi
->elt2
= bi
->elt2
->next
;
608 /* If we're at the same index, then we have some intersecting bits. */
609 if (bi
->elt1
->indx
== bi
->elt2
->indx
)
611 /* We might have advanced beyond the start_bit, so reinitialize
613 if (bi
->elt1
->indx
!= start_bit
/ BITMAP_ELEMENT_ALL_BITS
)
614 start_bit
= bi
->elt1
->indx
* BITMAP_ELEMENT_ALL_BITS
;
616 bi
->word_no
= start_bit
/ BITMAP_WORD_BITS
% BITMAP_ELEMENT_WORDS
;
617 bi
->bits
= bi
->elt1
->bits
[bi
->word_no
] & bi
->elt2
->bits
[bi
->word_no
];
618 bi
->bits
>>= start_bit
% BITMAP_WORD_BITS
;
622 /* Otherwise we must immediately advance elt1, so initialize for
624 bi
->word_no
= BITMAP_ELEMENT_WORDS
- 1;
628 /* If this word is zero, we must make sure we're not pointing at the
629 first bit, otherwise our incrementing to the next word boundary
630 will fail. It won't matter if this increment moves us into the
632 start_bit
+= !bi
->bits
;
637 /* Initialize an iterator to iterate over the bits in MAP1 & ~MAP2. */
640 bmp_iter_and_compl_init (bitmap_iterator
*bi
,
641 const_bitmap map1
, const_bitmap map2
,
642 unsigned start_bit
, unsigned *bit_no
)
644 bi
->elt1
= map1
->first
;
645 bi
->elt2
= map2
->first
;
647 gcc_checking_assert (!map1
->tree_form
&& !map2
->tree_form
);
649 /* Advance elt1 until it is not before the block containing start_bit. */
654 bi
->elt1
= &bitmap_zero_bits
;
658 if (bi
->elt1
->indx
>= start_bit
/ BITMAP_ELEMENT_ALL_BITS
)
660 bi
->elt1
= bi
->elt1
->next
;
663 /* Advance elt2 until it is not before elt1. */
664 while (bi
->elt2
&& bi
->elt2
->indx
< bi
->elt1
->indx
)
665 bi
->elt2
= bi
->elt2
->next
;
667 /* We might have advanced beyond the start_bit, so reinitialize for
669 if (bi
->elt1
->indx
!= start_bit
/ BITMAP_ELEMENT_ALL_BITS
)
670 start_bit
= bi
->elt1
->indx
* BITMAP_ELEMENT_ALL_BITS
;
672 bi
->word_no
= start_bit
/ BITMAP_WORD_BITS
% BITMAP_ELEMENT_WORDS
;
673 bi
->bits
= bi
->elt1
->bits
[bi
->word_no
];
674 if (bi
->elt2
&& bi
->elt1
->indx
== bi
->elt2
->indx
)
675 bi
->bits
&= ~bi
->elt2
->bits
[bi
->word_no
];
676 bi
->bits
>>= start_bit
% BITMAP_WORD_BITS
;
678 /* If this word is zero, we must make sure we're not pointing at the
679 first bit, otherwise our incrementing to the next word boundary
680 will fail. It won't matter if this increment moves us into the
682 start_bit
+= !bi
->bits
;
687 /* Advance to the next bit in BI. We don't advance to the next
691 bmp_iter_next (bitmap_iterator
*bi
, unsigned *bit_no
)
697 /* Advance to first set bit in BI. */
700 bmp_iter_next_bit (bitmap_iterator
* bi
, unsigned *bit_no
)
702 #if (GCC_VERSION >= 3004)
704 unsigned int n
= __builtin_ctzl (bi
->bits
);
705 gcc_assert (sizeof (unsigned long) == sizeof (BITMAP_WORD
));
710 while (!(bi
->bits
& 1))
718 /* Advance to the next nonzero bit of a single bitmap, we will have
719 already advanced past the just iterated bit. Return true if there
720 is a bit to iterate. */
723 bmp_iter_set (bitmap_iterator
*bi
, unsigned *bit_no
)
725 /* If our current word is nonzero, it contains the bit we want. */
729 bmp_iter_next_bit (bi
, bit_no
);
733 /* Round up to the word boundary. We might have just iterated past
734 the end of the last word, hence the -1. It is not possible for
735 bit_no to point at the beginning of the now last word. */
736 *bit_no
= ((*bit_no
+ BITMAP_WORD_BITS
- 1)
737 / BITMAP_WORD_BITS
* BITMAP_WORD_BITS
);
742 /* Find the next nonzero word in this elt. */
743 while (bi
->word_no
!= BITMAP_ELEMENT_WORDS
)
745 bi
->bits
= bi
->elt1
->bits
[bi
->word_no
];
748 *bit_no
+= BITMAP_WORD_BITS
;
752 /* Make sure we didn't remove the element while iterating. */
753 gcc_checking_assert (bi
->elt1
->indx
!= -1U);
755 /* Advance to the next element. */
756 bi
->elt1
= bi
->elt1
->next
;
759 *bit_no
= bi
->elt1
->indx
* BITMAP_ELEMENT_ALL_BITS
;
764 /* Advance to the next nonzero bit of an intersecting pair of
765 bitmaps. We will have already advanced past the just iterated bit.
766 Return true if there is a bit to iterate. */
769 bmp_iter_and (bitmap_iterator
*bi
, unsigned *bit_no
)
771 /* If our current word is nonzero, it contains the bit we want. */
775 bmp_iter_next_bit (bi
, bit_no
);
779 /* Round up to the word boundary. We might have just iterated past
780 the end of the last word, hence the -1. It is not possible for
781 bit_no to point at the beginning of the now last word. */
782 *bit_no
= ((*bit_no
+ BITMAP_WORD_BITS
- 1)
783 / BITMAP_WORD_BITS
* BITMAP_WORD_BITS
);
788 /* Find the next nonzero word in this elt. */
789 while (bi
->word_no
!= BITMAP_ELEMENT_WORDS
)
791 bi
->bits
= bi
->elt1
->bits
[bi
->word_no
] & bi
->elt2
->bits
[bi
->word_no
];
794 *bit_no
+= BITMAP_WORD_BITS
;
798 /* Advance to the next identical element. */
801 /* Make sure we didn't remove the element while iterating. */
802 gcc_checking_assert (bi
->elt1
->indx
!= -1U);
804 /* Advance elt1 while it is less than elt2. We always want
805 to advance one elt. */
808 bi
->elt1
= bi
->elt1
->next
;
812 while (bi
->elt1
->indx
< bi
->elt2
->indx
);
814 /* Make sure we didn't remove the element while iterating. */
815 gcc_checking_assert (bi
->elt2
->indx
!= -1U);
817 /* Advance elt2 to be no less than elt1. This might not
819 while (bi
->elt2
->indx
< bi
->elt1
->indx
)
821 bi
->elt2
= bi
->elt2
->next
;
826 while (bi
->elt1
->indx
!= bi
->elt2
->indx
);
828 *bit_no
= bi
->elt1
->indx
* BITMAP_ELEMENT_ALL_BITS
;
833 /* Advance to the next nonzero bit in the intersection of
834 complemented bitmaps. We will have already advanced past the just
838 bmp_iter_and_compl (bitmap_iterator
*bi
, unsigned *bit_no
)
840 /* If our current word is nonzero, it contains the bit we want. */
844 bmp_iter_next_bit (bi
, bit_no
);
848 /* Round up to the word boundary. We might have just iterated past
849 the end of the last word, hence the -1. It is not possible for
850 bit_no to point at the beginning of the now last word. */
851 *bit_no
= ((*bit_no
+ BITMAP_WORD_BITS
- 1)
852 / BITMAP_WORD_BITS
* BITMAP_WORD_BITS
);
857 /* Find the next nonzero word in this elt. */
858 while (bi
->word_no
!= BITMAP_ELEMENT_WORDS
)
860 bi
->bits
= bi
->elt1
->bits
[bi
->word_no
];
861 if (bi
->elt2
&& bi
->elt2
->indx
== bi
->elt1
->indx
)
862 bi
->bits
&= ~bi
->elt2
->bits
[bi
->word_no
];
865 *bit_no
+= BITMAP_WORD_BITS
;
869 /* Make sure we didn't remove the element while iterating. */
870 gcc_checking_assert (bi
->elt1
->indx
!= -1U);
872 /* Advance to the next element of elt1. */
873 bi
->elt1
= bi
->elt1
->next
;
877 /* Make sure we didn't remove the element while iterating. */
878 gcc_checking_assert (! bi
->elt2
|| bi
->elt2
->indx
!= -1U);
880 /* Advance elt2 until it is no less than elt1. */
881 while (bi
->elt2
&& bi
->elt2
->indx
< bi
->elt1
->indx
)
882 bi
->elt2
= bi
->elt2
->next
;
884 *bit_no
= bi
->elt1
->indx
* BITMAP_ELEMENT_ALL_BITS
;
889 /* If you are modifying a bitmap you are currently iterating over you
891 - never remove the current bit;
892 - if you set or clear a bit before the current bit this operation
893 will not affect the set of bits you are visiting during the iteration;
894 - if you set or clear a bit after the current bit it is unspecified
895 whether that affects the set of bits you are visiting during the
897 If you want to remove the current bit you can delay this to the next
898 iteration (and after the iteration in case the last iteration is
901 /* Loop over all bits set in BITMAP, starting with MIN and setting
902 BITNUM to the bit number. ITER is a bitmap iterator. BITNUM
903 should be treated as a read-only variable as it contains loop
906 #ifndef EXECUTE_IF_SET_IN_BITMAP
907 /* See sbitmap.h for the other definition of EXECUTE_IF_SET_IN_BITMAP. */
908 #define EXECUTE_IF_SET_IN_BITMAP(BITMAP, MIN, BITNUM, ITER) \
909 for (bmp_iter_set_init (&(ITER), (BITMAP), (MIN), &(BITNUM)); \
910 bmp_iter_set (&(ITER), &(BITNUM)); \
911 bmp_iter_next (&(ITER), &(BITNUM)))
914 /* Loop over all the bits set in BITMAP1 & BITMAP2, starting with MIN
915 and setting BITNUM to the bit number. ITER is a bitmap iterator.
916 BITNUM should be treated as a read-only variable as it contains
919 #define EXECUTE_IF_AND_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, ITER) \
920 for (bmp_iter_and_init (&(ITER), (BITMAP1), (BITMAP2), (MIN), \
922 bmp_iter_and (&(ITER), &(BITNUM)); \
923 bmp_iter_next (&(ITER), &(BITNUM)))
925 /* Loop over all the bits set in BITMAP1 & ~BITMAP2, starting with MIN
926 and setting BITNUM to the bit number. ITER is a bitmap iterator.
927 BITNUM should be treated as a read-only variable as it contains
930 #define EXECUTE_IF_AND_COMPL_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, ITER) \
931 for (bmp_iter_and_compl_init (&(ITER), (BITMAP1), (BITMAP2), (MIN), \
933 bmp_iter_and_compl (&(ITER), &(BITNUM)); \
934 bmp_iter_next (&(ITER), &(BITNUM)))
936 /* A class that ties the lifetime of a bitmap to its scope. */
940 auto_bitmap () { bitmap_initialize (&m_bits
, &bitmap_default_obstack
); }
941 explicit auto_bitmap (bitmap_obstack
*o
) { bitmap_initialize (&m_bits
, o
); }
942 ~auto_bitmap () { bitmap_clear (&m_bits
); }
943 // Allow calling bitmap functions on our bitmap.
944 operator bitmap () { return &m_bits
; }
947 // Prevent making a copy that references our bitmap.
948 auto_bitmap (const auto_bitmap
&);
949 auto_bitmap
&operator = (const auto_bitmap
&);
950 #if __cplusplus >= 201103L
951 auto_bitmap (auto_bitmap
&&);
952 auto_bitmap
&operator = (auto_bitmap
&&);
958 #endif /* GCC_BITMAP_H */