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. */
213 #include "array-traits.h"
215 /* Bitmap memory usage. */
216 class bitmap_usage
: public mem_usage
219 /* Default contructor. */
220 bitmap_usage (): m_nsearches (0), m_search_iter (0) {}
222 bitmap_usage (size_t allocated
, size_t times
, size_t peak
,
223 uint64_t nsearches
, uint64_t search_iter
)
224 : mem_usage (allocated
, times
, peak
),
225 m_nsearches (nsearches
), m_search_iter (search_iter
) {}
227 /* Sum the usage with SECOND usage. */
229 operator+ (const bitmap_usage
&second
)
231 return bitmap_usage (m_allocated
+ second
.m_allocated
,
232 m_times
+ second
.m_times
,
233 m_peak
+ second
.m_peak
,
234 m_nsearches
+ second
.m_nsearches
,
235 m_search_iter
+ second
.m_search_iter
);
238 /* Dump usage coupled to LOC location, where TOTAL is sum of all rows. */
240 dump (mem_location
*loc
, mem_usage
&total
) const
242 char *location_string
= loc
->to_string ();
244 fprintf (stderr
, "%-48s " PRsa (9) ":%5.1f%%"
245 PRsa (9) PRsa (9) ":%5.1f%%"
246 PRsa (11) PRsa (11) "%10s\n",
247 location_string
, SIZE_AMOUNT (m_allocated
),
248 get_percent (m_allocated
, total
.m_allocated
),
249 SIZE_AMOUNT (m_peak
), SIZE_AMOUNT (m_times
),
250 get_percent (m_times
, total
.m_times
),
251 SIZE_AMOUNT (m_nsearches
), SIZE_AMOUNT (m_search_iter
),
252 loc
->m_ggc
? "ggc" : "heap");
254 free (location_string
);
257 /* Dump header with NAME. */
259 dump_header (const char *name
)
261 fprintf (stderr
, "%-48s %11s%16s%17s%12s%12s%10s\n", name
, "Leak", "Peak",
262 "Times", "N searches", "Search iter", "Type");
265 /* Number search operations. */
266 uint64_t m_nsearches
;
267 /* Number of search iterations. */
268 uint64_t m_search_iter
;
271 /* Bitmap memory description. */
272 extern mem_alloc_description
<bitmap_usage
> bitmap_mem_desc
;
274 /* Fundamental storage type for bitmap. */
276 typedef unsigned long BITMAP_WORD
;
277 /* BITMAP_WORD_BITS needs to be unsigned, but cannot contain casts as
278 it is used in preprocessor directives -- hence the 1u. */
279 #define BITMAP_WORD_BITS (CHAR_BIT * SIZEOF_LONG * 1u)
281 /* Number of words to use for each element in the linked list. */
283 #ifndef BITMAP_ELEMENT_WORDS
284 #define BITMAP_ELEMENT_WORDS ((128 + BITMAP_WORD_BITS - 1) / BITMAP_WORD_BITS)
287 /* Number of bits in each actual element of a bitmap. */
289 #define BITMAP_ELEMENT_ALL_BITS (BITMAP_ELEMENT_WORDS * BITMAP_WORD_BITS)
291 /* Obstack for allocating bitmaps and elements from. */
292 struct bitmap_obstack
{
293 struct bitmap_element
*elements
;
295 struct obstack obstack
;
298 /* Bitmap set element. We use a linked list to hold only the bits that
299 are set. This allows for use to grow the bitset dynamically without
300 having to realloc and copy a giant bit array.
302 The free list is implemented as a list of lists. There is one
303 outer list connected together by prev fields. Each element of that
304 outer is an inner list (that may consist only of the outer list
305 element) that are connected by the next fields. The prev pointer
306 is undefined for interior elements. This allows
307 bitmap_elt_clear_from to be implemented in unit time rather than
308 linear in the number of elements to be freed. */
310 struct GTY((chain_next ("%h.next"))) bitmap_element
{
311 /* In list form, the next element in the linked list;
312 in tree form, the left child node in the tree. */
313 struct bitmap_element
*next
;
314 /* In list form, the previous element in the linked list;
315 in tree form, the right child node in the tree. */
316 struct bitmap_element
*prev
;
317 /* regno/BITMAP_ELEMENT_ALL_BITS. */
319 /* Bits that are set, counting from INDX, inclusive */
320 BITMAP_WORD bits
[BITMAP_ELEMENT_WORDS
];
323 /* Head of bitmap linked list. The 'current' member points to something
324 already pointed to by the chain started by first, so GTY((skip)) it. */
326 class GTY(()) bitmap_head
{
328 static bitmap_obstack crashme
;
329 /* Poison obstack to not make it not a valid initialized GC bitmap. */
330 CONSTEXPR
bitmap_head()
331 : indx (0), tree_form (false), padding (0), alloc_descriptor (0), first (NULL
),
332 current (NULL
), obstack (&crashme
)
334 /* Index of last element looked at. */
336 /* False if the bitmap is in list form; true if the bitmap is in tree form.
337 Bitmap iterators only work on bitmaps in list form. */
338 unsigned tree_form
: 1;
339 /* Next integer is shifted, so padding is needed. */
341 /* Bitmap UID used for memory allocation statistics. */
342 unsigned alloc_descriptor
: 29;
343 /* In list form, the first element in the linked list;
344 in tree form, the root of the tree. */
345 bitmap_element
*first
;
346 /* Last element looked at. */
347 bitmap_element
* GTY((skip(""))) current
;
348 /* Obstack to allocate elements from. If NULL, then use GGC allocation. */
349 bitmap_obstack
* GTY((skip(""))) obstack
;
354 /* Get bitmap descriptor UID casted to an unsigned integer pointer.
355 Shift the descriptor because pointer_hash<Type>::hash is
356 doing >> 3 shift operation. */
357 unsigned *get_descriptor ()
359 return (unsigned *)(ptrdiff_t)(alloc_descriptor
<< 3);
364 extern bitmap_element bitmap_zero_bits
; /* Zero bitmap element */
365 extern bitmap_obstack bitmap_default_obstack
; /* Default bitmap obstack */
367 /* Change the view of the bitmap to list, or tree. */
368 void bitmap_list_view (bitmap
);
369 void bitmap_tree_view (bitmap
);
371 /* Clear a bitmap by freeing up the linked list. */
372 extern void bitmap_clear (bitmap
);
374 /* Copy a bitmap to another bitmap. */
375 extern void bitmap_copy (bitmap
, const_bitmap
);
377 /* Move a bitmap to another bitmap. */
378 extern void bitmap_move (bitmap
, bitmap
);
380 /* True if two bitmaps are identical. */
381 extern bool bitmap_equal_p (const_bitmap
, const_bitmap
);
383 /* True if the bitmaps intersect (their AND is non-empty). */
384 extern bool bitmap_intersect_p (const_bitmap
, const_bitmap
);
386 /* True if the complement of the second intersects the first (their
387 AND_COMPL is non-empty). */
388 extern bool bitmap_intersect_compl_p (const_bitmap
, const_bitmap
);
390 /* True if MAP is an empty bitmap. */
391 inline bool bitmap_empty_p (const_bitmap map
)
396 /* True if the bitmap has only a single bit set. */
397 extern bool bitmap_single_bit_set_p (const_bitmap
);
399 /* Count the number of bits set in the bitmap. */
400 extern unsigned long bitmap_count_bits (const_bitmap
);
402 /* Count the number of unique bits set across the two bitmaps. */
403 extern unsigned long bitmap_count_unique_bits (const_bitmap
, const_bitmap
);
405 /* Boolean operations on bitmaps. The _into variants are two operand
406 versions that modify the first source operand. The other variants
407 are three operand versions that to not destroy the source bitmaps.
408 The operations supported are &, & ~, |, ^. */
409 extern void bitmap_and (bitmap
, const_bitmap
, const_bitmap
);
410 extern bool bitmap_and_into (bitmap
, const_bitmap
);
411 extern bool bitmap_and_compl (bitmap
, const_bitmap
, const_bitmap
);
412 extern bool bitmap_and_compl_into (bitmap
, const_bitmap
);
413 #define bitmap_compl_and(DST, A, B) bitmap_and_compl (DST, B, A)
414 extern void bitmap_compl_and_into (bitmap
, const_bitmap
);
415 extern void bitmap_clear_range (bitmap
, unsigned int, unsigned int);
416 extern void bitmap_set_range (bitmap
, unsigned int, unsigned int);
417 extern bool bitmap_ior (bitmap
, const_bitmap
, const_bitmap
);
418 extern bool bitmap_ior_into (bitmap
, const_bitmap
);
419 extern bool bitmap_ior_into_and_free (bitmap
, bitmap
*);
420 extern void bitmap_xor (bitmap
, const_bitmap
, const_bitmap
);
421 extern void bitmap_xor_into (bitmap
, const_bitmap
);
423 /* DST = A | (B & C). Return true if DST changes. */
424 extern bool bitmap_ior_and_into (bitmap DST
, const_bitmap B
, const_bitmap C
);
425 /* DST = A | (B & ~C). Return true if DST changes. */
426 extern bool bitmap_ior_and_compl (bitmap DST
, const_bitmap A
,
427 const_bitmap B
, const_bitmap C
);
428 /* A |= (B & ~C). Return true if A changes. */
429 extern bool bitmap_ior_and_compl_into (bitmap A
,
430 const_bitmap B
, const_bitmap C
);
432 /* Clear a single bit in a bitmap. Return true if the bit changed. */
433 extern bool bitmap_clear_bit (bitmap
, int);
435 /* Set a single bit in a bitmap. Return true if the bit changed. */
436 extern bool bitmap_set_bit (bitmap
, int);
438 /* Return true if a bit is set in a bitmap. */
439 extern int bitmap_bit_p (const_bitmap
, int);
441 /* Debug functions to print a bitmap. */
442 extern void debug_bitmap (const_bitmap
);
443 extern void debug_bitmap_file (FILE *, const_bitmap
);
445 /* Print a bitmap. */
446 extern void bitmap_print (FILE *, const_bitmap
, const char *, const char *);
448 /* Initialize and release a bitmap obstack. */
449 extern void bitmap_obstack_initialize (bitmap_obstack
*);
450 extern void bitmap_obstack_release (bitmap_obstack
*);
451 extern void bitmap_register (bitmap MEM_STAT_DECL
);
452 extern void dump_bitmap_statistics (void);
454 /* Initialize a bitmap header. OBSTACK indicates the bitmap obstack
455 to allocate from, NULL for GC'd bitmap. */
458 bitmap_initialize (bitmap head
, bitmap_obstack
*obstack CXX_MEM_STAT_INFO
)
460 head
->first
= head
->current
= NULL
;
461 head
->indx
= head
->tree_form
= 0;
463 head
->alloc_descriptor
= 0;
464 head
->obstack
= obstack
;
465 if (GATHER_STATISTICS
)
466 bitmap_register (head PASS_MEM_STAT
);
469 /* Release a bitmap (but not its head). This is suitable for pairing with
470 bitmap_initialize. */
473 bitmap_release (bitmap head
)
476 /* Poison the obstack pointer so the obstack can be safely released.
477 Do not zero it as the bitmap then becomes initialized GC. */
478 head
->obstack
= &bitmap_head::crashme
;
481 /* Allocate and free bitmaps from obstack, malloc and gc'd memory. */
482 extern bitmap
bitmap_alloc (bitmap_obstack
*obstack CXX_MEM_STAT_INFO
);
483 #define BITMAP_ALLOC bitmap_alloc
484 extern bitmap
bitmap_gc_alloc (ALONE_CXX_MEM_STAT_INFO
);
485 #define BITMAP_GGC_ALLOC bitmap_gc_alloc
486 extern void bitmap_obstack_free (bitmap
);
488 /* A few compatibility/functions macros for compatibility with sbitmaps */
489 inline void dump_bitmap (FILE *file
, const_bitmap map
)
491 bitmap_print (file
, map
, "", "\n");
493 extern void debug (const bitmap_head
&ref
);
494 extern void debug (const bitmap_head
*ptr
);
496 extern unsigned bitmap_first_set_bit (const_bitmap
);
497 extern unsigned bitmap_last_set_bit (const_bitmap
);
499 /* Compute bitmap hash (for purposes of hashing etc.) */
500 extern hashval_t
bitmap_hash (const_bitmap
);
502 /* Do any cleanup needed on a bitmap when it is no longer used. */
503 #define BITMAP_FREE(BITMAP) \
504 ((void) (bitmap_obstack_free ((bitmap) BITMAP), (BITMAP) = (bitmap) NULL))
506 /* Iterator for bitmaps. */
508 struct bitmap_iterator
510 /* Pointer to the current bitmap element. */
511 bitmap_element
*elt1
;
513 /* Pointer to 2nd bitmap element when two are involved. */
514 bitmap_element
*elt2
;
516 /* Word within the current element. */
519 /* Contents of the actually processed word. When finding next bit
520 it is shifted right, so that the actual bit is always the least
521 significant bit of ACTUAL. */
525 /* Initialize a single bitmap iterator. START_BIT is the first bit to
529 bmp_iter_set_init (bitmap_iterator
*bi
, const_bitmap map
,
530 unsigned start_bit
, unsigned *bit_no
)
532 bi
->elt1
= map
->first
;
535 gcc_checking_assert (!map
->tree_form
);
537 /* Advance elt1 until it is not before the block containing start_bit. */
542 bi
->elt1
= &bitmap_zero_bits
;
546 if (bi
->elt1
->indx
>= start_bit
/ BITMAP_ELEMENT_ALL_BITS
)
548 bi
->elt1
= bi
->elt1
->next
;
551 /* We might have gone past the start bit, so reinitialize it. */
552 if (bi
->elt1
->indx
!= start_bit
/ BITMAP_ELEMENT_ALL_BITS
)
553 start_bit
= bi
->elt1
->indx
* BITMAP_ELEMENT_ALL_BITS
;
555 /* Initialize for what is now start_bit. */
556 bi
->word_no
= start_bit
/ BITMAP_WORD_BITS
% BITMAP_ELEMENT_WORDS
;
557 bi
->bits
= bi
->elt1
->bits
[bi
->word_no
];
558 bi
->bits
>>= start_bit
% BITMAP_WORD_BITS
;
560 /* If this word is zero, we must make sure we're not pointing at the
561 first bit, otherwise our incrementing to the next word boundary
562 will fail. It won't matter if this increment moves us into the
564 start_bit
+= !bi
->bits
;
569 /* Initialize an iterator to iterate over the intersection of two
570 bitmaps. START_BIT is the bit to commence from. */
573 bmp_iter_and_init (bitmap_iterator
*bi
, const_bitmap map1
, const_bitmap map2
,
574 unsigned start_bit
, unsigned *bit_no
)
576 bi
->elt1
= map1
->first
;
577 bi
->elt2
= map2
->first
;
579 gcc_checking_assert (!map1
->tree_form
&& !map2
->tree_form
);
581 /* Advance elt1 until it is not before the block containing
591 if (bi
->elt1
->indx
>= start_bit
/ BITMAP_ELEMENT_ALL_BITS
)
593 bi
->elt1
= bi
->elt1
->next
;
596 /* Advance elt2 until it is not before elt1. */
601 bi
->elt1
= bi
->elt2
= &bitmap_zero_bits
;
605 if (bi
->elt2
->indx
>= bi
->elt1
->indx
)
607 bi
->elt2
= bi
->elt2
->next
;
610 /* If we're at the same index, then we have some intersecting bits. */
611 if (bi
->elt1
->indx
== bi
->elt2
->indx
)
613 /* We might have advanced beyond the start_bit, so reinitialize
615 if (bi
->elt1
->indx
!= start_bit
/ BITMAP_ELEMENT_ALL_BITS
)
616 start_bit
= bi
->elt1
->indx
* BITMAP_ELEMENT_ALL_BITS
;
618 bi
->word_no
= start_bit
/ BITMAP_WORD_BITS
% BITMAP_ELEMENT_WORDS
;
619 bi
->bits
= bi
->elt1
->bits
[bi
->word_no
] & bi
->elt2
->bits
[bi
->word_no
];
620 bi
->bits
>>= start_bit
% BITMAP_WORD_BITS
;
624 /* Otherwise we must immediately advance elt1, so initialize for
626 bi
->word_no
= BITMAP_ELEMENT_WORDS
- 1;
630 /* If this word is zero, we must make sure we're not pointing at the
631 first bit, otherwise our incrementing to the next word boundary
632 will fail. It won't matter if this increment moves us into the
634 start_bit
+= !bi
->bits
;
639 /* Initialize an iterator to iterate over the bits in MAP1 & ~MAP2. */
642 bmp_iter_and_compl_init (bitmap_iterator
*bi
,
643 const_bitmap map1
, const_bitmap map2
,
644 unsigned start_bit
, unsigned *bit_no
)
646 bi
->elt1
= map1
->first
;
647 bi
->elt2
= map2
->first
;
649 gcc_checking_assert (!map1
->tree_form
&& !map2
->tree_form
);
651 /* Advance elt1 until it is not before the block containing start_bit. */
656 bi
->elt1
= &bitmap_zero_bits
;
660 if (bi
->elt1
->indx
>= start_bit
/ BITMAP_ELEMENT_ALL_BITS
)
662 bi
->elt1
= bi
->elt1
->next
;
665 /* Advance elt2 until it is not before elt1. */
666 while (bi
->elt2
&& bi
->elt2
->indx
< bi
->elt1
->indx
)
667 bi
->elt2
= bi
->elt2
->next
;
669 /* We might have advanced beyond the start_bit, so reinitialize for
671 if (bi
->elt1
->indx
!= start_bit
/ BITMAP_ELEMENT_ALL_BITS
)
672 start_bit
= bi
->elt1
->indx
* BITMAP_ELEMENT_ALL_BITS
;
674 bi
->word_no
= start_bit
/ BITMAP_WORD_BITS
% BITMAP_ELEMENT_WORDS
;
675 bi
->bits
= bi
->elt1
->bits
[bi
->word_no
];
676 if (bi
->elt2
&& bi
->elt1
->indx
== bi
->elt2
->indx
)
677 bi
->bits
&= ~bi
->elt2
->bits
[bi
->word_no
];
678 bi
->bits
>>= start_bit
% BITMAP_WORD_BITS
;
680 /* If this word is zero, we must make sure we're not pointing at the
681 first bit, otherwise our incrementing to the next word boundary
682 will fail. It won't matter if this increment moves us into the
684 start_bit
+= !bi
->bits
;
689 /* Advance to the next bit in BI. We don't advance to the next
693 bmp_iter_next (bitmap_iterator
*bi
, unsigned *bit_no
)
699 /* Advance to first set bit in BI. */
702 bmp_iter_next_bit (bitmap_iterator
* bi
, unsigned *bit_no
)
704 #if (GCC_VERSION >= 3004)
706 unsigned int n
= __builtin_ctzl (bi
->bits
);
707 gcc_assert (sizeof (unsigned long) == sizeof (BITMAP_WORD
));
712 while (!(bi
->bits
& 1))
720 /* Advance to the next nonzero bit of a single bitmap, we will have
721 already advanced past the just iterated bit. Return true if there
722 is a bit to iterate. */
725 bmp_iter_set (bitmap_iterator
*bi
, unsigned *bit_no
)
727 /* If our current word is nonzero, it contains the bit we want. */
731 bmp_iter_next_bit (bi
, bit_no
);
735 /* Round up to the word boundary. We might have just iterated past
736 the end of the last word, hence the -1. It is not possible for
737 bit_no to point at the beginning of the now last word. */
738 *bit_no
= ((*bit_no
+ BITMAP_WORD_BITS
- 1)
739 / BITMAP_WORD_BITS
* BITMAP_WORD_BITS
);
744 /* Find the next nonzero word in this elt. */
745 while (bi
->word_no
!= BITMAP_ELEMENT_WORDS
)
747 bi
->bits
= bi
->elt1
->bits
[bi
->word_no
];
750 *bit_no
+= BITMAP_WORD_BITS
;
754 /* Make sure we didn't remove the element while iterating. */
755 gcc_checking_assert (bi
->elt1
->indx
!= -1U);
757 /* Advance to the next element. */
758 bi
->elt1
= bi
->elt1
->next
;
761 *bit_no
= bi
->elt1
->indx
* BITMAP_ELEMENT_ALL_BITS
;
766 /* Advance to the next nonzero bit of an intersecting pair of
767 bitmaps. We will have already advanced past the just iterated bit.
768 Return true if there is a bit to iterate. */
771 bmp_iter_and (bitmap_iterator
*bi
, unsigned *bit_no
)
773 /* If our current word is nonzero, it contains the bit we want. */
777 bmp_iter_next_bit (bi
, bit_no
);
781 /* Round up to the word boundary. We might have just iterated past
782 the end of the last word, hence the -1. It is not possible for
783 bit_no to point at the beginning of the now last word. */
784 *bit_no
= ((*bit_no
+ BITMAP_WORD_BITS
- 1)
785 / BITMAP_WORD_BITS
* BITMAP_WORD_BITS
);
790 /* Find the next nonzero word in this elt. */
791 while (bi
->word_no
!= BITMAP_ELEMENT_WORDS
)
793 bi
->bits
= bi
->elt1
->bits
[bi
->word_no
] & bi
->elt2
->bits
[bi
->word_no
];
796 *bit_no
+= BITMAP_WORD_BITS
;
800 /* Advance to the next identical element. */
803 /* Make sure we didn't remove the element while iterating. */
804 gcc_checking_assert (bi
->elt1
->indx
!= -1U);
806 /* Advance elt1 while it is less than elt2. We always want
807 to advance one elt. */
810 bi
->elt1
= bi
->elt1
->next
;
814 while (bi
->elt1
->indx
< bi
->elt2
->indx
);
816 /* Make sure we didn't remove the element while iterating. */
817 gcc_checking_assert (bi
->elt2
->indx
!= -1U);
819 /* Advance elt2 to be no less than elt1. This might not
821 while (bi
->elt2
->indx
< bi
->elt1
->indx
)
823 bi
->elt2
= bi
->elt2
->next
;
828 while (bi
->elt1
->indx
!= bi
->elt2
->indx
);
830 *bit_no
= bi
->elt1
->indx
* BITMAP_ELEMENT_ALL_BITS
;
835 /* Advance to the next nonzero bit in the intersection of
836 complemented bitmaps. We will have already advanced past the just
840 bmp_iter_and_compl (bitmap_iterator
*bi
, unsigned *bit_no
)
842 /* If our current word is nonzero, it contains the bit we want. */
846 bmp_iter_next_bit (bi
, bit_no
);
850 /* Round up to the word boundary. We might have just iterated past
851 the end of the last word, hence the -1. It is not possible for
852 bit_no to point at the beginning of the now last word. */
853 *bit_no
= ((*bit_no
+ BITMAP_WORD_BITS
- 1)
854 / BITMAP_WORD_BITS
* BITMAP_WORD_BITS
);
859 /* Find the next nonzero word in this elt. */
860 while (bi
->word_no
!= BITMAP_ELEMENT_WORDS
)
862 bi
->bits
= bi
->elt1
->bits
[bi
->word_no
];
863 if (bi
->elt2
&& bi
->elt2
->indx
== bi
->elt1
->indx
)
864 bi
->bits
&= ~bi
->elt2
->bits
[bi
->word_no
];
867 *bit_no
+= BITMAP_WORD_BITS
;
871 /* Make sure we didn't remove the element while iterating. */
872 gcc_checking_assert (bi
->elt1
->indx
!= -1U);
874 /* Advance to the next element of elt1. */
875 bi
->elt1
= bi
->elt1
->next
;
879 /* Make sure we didn't remove the element while iterating. */
880 gcc_checking_assert (! bi
->elt2
|| bi
->elt2
->indx
!= -1U);
882 /* Advance elt2 until it is no less than elt1. */
883 while (bi
->elt2
&& bi
->elt2
->indx
< bi
->elt1
->indx
)
884 bi
->elt2
= bi
->elt2
->next
;
886 *bit_no
= bi
->elt1
->indx
* BITMAP_ELEMENT_ALL_BITS
;
891 /* If you are modifying a bitmap you are currently iterating over you
893 - never remove the current bit;
894 - if you set or clear a bit before the current bit this operation
895 will not affect the set of bits you are visiting during the iteration;
896 - if you set or clear a bit after the current bit it is unspecified
897 whether that affects the set of bits you are visiting during the
899 If you want to remove the current bit you can delay this to the next
900 iteration (and after the iteration in case the last iteration is
903 /* Loop over all bits set in BITMAP, starting with MIN and setting
904 BITNUM to the bit number. ITER is a bitmap iterator. BITNUM
905 should be treated as a read-only variable as it contains loop
908 #ifndef EXECUTE_IF_SET_IN_BITMAP
909 /* See sbitmap.h for the other definition of EXECUTE_IF_SET_IN_BITMAP. */
910 #define EXECUTE_IF_SET_IN_BITMAP(BITMAP, MIN, BITNUM, ITER) \
911 for (bmp_iter_set_init (&(ITER), (BITMAP), (MIN), &(BITNUM)); \
912 bmp_iter_set (&(ITER), &(BITNUM)); \
913 bmp_iter_next (&(ITER), &(BITNUM)))
916 /* Loop over all the bits set in BITMAP1 & BITMAP2, starting with MIN
917 and setting BITNUM to the bit number. ITER is a bitmap iterator.
918 BITNUM should be treated as a read-only variable as it contains
921 #define EXECUTE_IF_AND_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, ITER) \
922 for (bmp_iter_and_init (&(ITER), (BITMAP1), (BITMAP2), (MIN), \
924 bmp_iter_and (&(ITER), &(BITNUM)); \
925 bmp_iter_next (&(ITER), &(BITNUM)))
927 /* Loop over all the bits set in BITMAP1 & ~BITMAP2, starting with MIN
928 and setting BITNUM to the bit number. ITER is a bitmap iterator.
929 BITNUM should be treated as a read-only variable as it contains
932 #define EXECUTE_IF_AND_COMPL_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, ITER) \
933 for (bmp_iter_and_compl_init (&(ITER), (BITMAP1), (BITMAP2), (MIN), \
935 bmp_iter_and_compl (&(ITER), &(BITNUM)); \
936 bmp_iter_next (&(ITER), &(BITNUM)))
938 /* A class that ties the lifetime of a bitmap to its scope. */
942 auto_bitmap () { bitmap_initialize (&m_bits
, &bitmap_default_obstack
); }
943 explicit auto_bitmap (bitmap_obstack
*o
) { bitmap_initialize (&m_bits
, o
); }
944 ~auto_bitmap () { bitmap_clear (&m_bits
); }
945 // Allow calling bitmap functions on our bitmap.
946 operator bitmap () { return &m_bits
; }
949 // Prevent making a copy that references our bitmap.
950 auto_bitmap (const auto_bitmap
&);
951 auto_bitmap
&operator = (const auto_bitmap
&);
952 #if __cplusplus >= 201103L
953 auto_bitmap (auto_bitmap
&&);
954 auto_bitmap
&operator = (auto_bitmap
&&);
960 /* Base class for bitmap_view; see there for details. */
961 template<typename T
, typename Traits
= array_traits
<T
> >
962 class base_bitmap_view
965 typedef typename
Traits::element_type array_element_type
;
967 base_bitmap_view (const T
&, bitmap_element
*);
968 operator const_bitmap () const { return &m_head
; }
971 base_bitmap_view (const base_bitmap_view
&);
976 /* Provides a read-only bitmap view of a single integer bitmask or a
977 constant-sized array of integer bitmasks, or of a wrapper around such
979 template<typename T
, typename Traits
>
980 class bitmap_view
<T
, Traits
, true> : public base_bitmap_view
<T
, Traits
>
983 bitmap_view (const T
&array
)
984 : base_bitmap_view
<T
, Traits
> (array
, m_bitmap_elements
) {}
987 /* How many bitmap_elements we need to hold a full T. */
988 static const size_t num_bitmap_elements
990 * sizeof (typename
Traits::element_type
)
991 * Traits::constant_size
,
992 BITMAP_ELEMENT_ALL_BITS
);
993 bitmap_element m_bitmap_elements
[num_bitmap_elements
];
996 /* Initialize the view for array ARRAY, using the array of bitmap
997 elements in BITMAP_ELEMENTS (which is known to contain enough
999 template<typename T
, typename Traits
>
1000 base_bitmap_view
<T
, Traits
>::base_bitmap_view (const T
&array
,
1001 bitmap_element
*bitmap_elements
)
1003 m_head
.obstack
= NULL
;
1005 /* The code currently assumes that each element of ARRAY corresponds
1006 to exactly one bitmap_element. */
1007 const size_t array_element_bits
= CHAR_BIT
* sizeof (array_element_type
);
1008 STATIC_ASSERT (BITMAP_ELEMENT_ALL_BITS
% array_element_bits
== 0);
1009 size_t array_step
= BITMAP_ELEMENT_ALL_BITS
/ array_element_bits
;
1010 size_t array_size
= Traits::size (array
);
1012 /* Process each potential bitmap_element in turn. The loop is written
1013 this way rather than per array element because usually there are
1014 only a small number of array elements per bitmap element (typically
1015 two or four). The inner loops should therefore unroll completely. */
1016 const array_element_type
*array_elements
= Traits::base (array
);
1017 unsigned int indx
= 0;
1018 for (size_t array_base
= 0;
1019 array_base
< array_size
;
1020 array_base
+= array_step
, indx
+= 1)
1022 /* How many array elements are in this particular bitmap_element. */
1023 unsigned int array_count
1024 = (STATIC_CONSTANT_P (array_size
% array_step
== 0)
1025 ? array_step
: MIN (array_step
, array_size
- array_base
));
1027 /* See whether we need this bitmap element. */
1028 array_element_type ior
= array_elements
[array_base
];
1029 for (size_t i
= 1; i
< array_count
; ++i
)
1030 ior
|= array_elements
[array_base
+ i
];
1034 /* Grab the next bitmap element and chain it. */
1035 bitmap_element
*bitmap_element
= bitmap_elements
++;
1037 m_head
.current
->next
= bitmap_element
;
1039 m_head
.first
= bitmap_element
;
1040 bitmap_element
->prev
= m_head
.current
;
1041 bitmap_element
->next
= NULL
;
1042 bitmap_element
->indx
= indx
;
1043 m_head
.current
= bitmap_element
;
1046 /* Fill in the bits of the bitmap element. */
1047 if (array_element_bits
< BITMAP_WORD_BITS
)
1049 /* Multiple array elements fit in one element of
1050 bitmap_element->bits. */
1051 size_t array_i
= array_base
;
1052 for (unsigned int word_i
= 0; word_i
< BITMAP_ELEMENT_WORDS
;
1055 BITMAP_WORD word
= 0;
1056 for (unsigned int shift
= 0;
1057 shift
< BITMAP_WORD_BITS
&& array_i
< array_size
;
1058 shift
+= array_element_bits
)
1059 word
|= array_elements
[array_i
++] << shift
;
1060 bitmap_element
->bits
[word_i
] = word
;
1065 /* Array elements are the same size as elements of
1066 bitmap_element->bits, or are an exact multiple of that size. */
1067 unsigned int word_i
= 0;
1068 for (unsigned int i
= 0; i
< array_count
; ++i
)
1069 for (unsigned int shift
= 0; shift
< array_element_bits
;
1070 shift
+= BITMAP_WORD_BITS
)
1071 bitmap_element
->bits
[word_i
++]
1072 = array_elements
[array_base
+ i
] >> shift
;
1073 while (word_i
< BITMAP_ELEMENT_WORDS
)
1074 bitmap_element
->bits
[word_i
++] = 0;
1079 #endif /* GCC_BITMAP_H */