PR libstdc++/87308 adjust regex used in std::any pretty printer
[official-gcc.git] / gcc / bitmap.h
blob9a180daa7454722756d9acccc273eb2d22e45a63
1 /* Functions to support general ended bitmaps.
2 Copyright (C) 1997-2018 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
9 version.
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
14 for more details.
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/>. */
20 #ifndef GCC_BITMAP_H
21 #define GCC_BITMAP_H
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
52 of the set members).
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
57 pattern.
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
62 frontiers, etc.).
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
68 random access.
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
92 linked-list set.
95 LINKED LIST FORM
96 ================
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
109 list view:
111 * clear : bitmap_clear
112 * smallest_member : bitmap_first_set_bit
113 * choose_one : (not implemented, but could be
114 in constant time)
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.
135 * smallest_member
136 * largest_member
137 * set_size
138 * member_p
139 * add_member
140 * remove_member
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
165 BINARY TREE FORM
166 ================
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
176 not supported.
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
190 accessed.
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. */
212 #include "obstack.h"
214 /* Bitmap memory usage. */
215 struct bitmap_usage: public mem_usage
217 /* Default contructor. */
218 bitmap_usage (): m_nsearches (0), m_search_iter (0) {}
219 /* Constructor. */
220 bitmap_usage (size_t allocated, size_t times, size_t peak,
221 uint64_t nsearches, uint64_t search_iter)
222 : mem_usage (allocated, times, peak),
223 m_nsearches (nsearches), m_search_iter (search_iter) {}
225 /* Sum the usage with SECOND usage. */
226 bitmap_usage
227 operator+ (const bitmap_usage &second)
229 return bitmap_usage (m_allocated + second.m_allocated,
230 m_times + second.m_times,
231 m_peak + second.m_peak,
232 m_nsearches + second.m_nsearches,
233 m_search_iter + second.m_search_iter);
236 /* Dump usage coupled to LOC location, where TOTAL is sum of all rows. */
237 inline void
238 dump (mem_location *loc, mem_usage &total) const
240 char *location_string = loc->to_string ();
242 fprintf (stderr, "%-48s " PRsa (9) ":%5.1f%%"
243 PRsa (9) PRsa (9) ":%5.1f%%"
244 PRsa (11) PRsa (11) "%10s\n",
245 location_string, SIZE_AMOUNT (m_allocated),
246 get_percent (m_allocated, total.m_allocated),
247 SIZE_AMOUNT (m_peak), SIZE_AMOUNT (m_times),
248 get_percent (m_times, total.m_times),
249 SIZE_AMOUNT (m_nsearches), SIZE_AMOUNT (m_search_iter),
250 loc->m_ggc ? "ggc" : "heap");
252 free (location_string);
255 /* Dump header with NAME. */
256 static inline void
257 dump_header (const char *name)
259 fprintf (stderr, "%-48s %11s%16s%17s%12s%12s%10s\n", name, "Leak", "Peak",
260 "Times", "N searches", "Search iter", "Type");
261 print_dash_line ();
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)
284 #endif
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 GTY (()) bitmap_obstack {
292 struct bitmap_element *elements;
293 struct bitmap_head *heads;
294 struct obstack GTY ((skip)) 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"), chain_prev ("%h.prev"))) 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. */
317 unsigned int indx;
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 struct GTY(()) bitmap_head {
326 /* Index of last element looked at. */
327 unsigned int indx;
328 /* False if the bitmap is in list form; true if the bitmap is in tree form.
329 Bitmap iterators only work on bitmaps in list form. */
330 bool tree_form;
331 /* In list form, the first element in the linked list;
332 in tree form, the root of the tree. */
333 bitmap_element *first;
334 /* Last element looked at. */
335 bitmap_element * GTY((skip(""))) current;
336 /* Obstack to allocate elements from. If NULL, then use GGC allocation. */
337 bitmap_obstack *obstack;
338 void dump ();
341 /* Global data */
342 extern bitmap_element bitmap_zero_bits; /* Zero bitmap element */
343 extern bitmap_obstack bitmap_default_obstack; /* Default bitmap obstack */
345 /* Change the view of the bitmap to list, or tree. */
346 void bitmap_list_view (bitmap);
347 void bitmap_tree_view (bitmap);
349 /* Clear a bitmap by freeing up the linked list. */
350 extern void bitmap_clear (bitmap);
352 /* Copy a bitmap to another bitmap. */
353 extern void bitmap_copy (bitmap, const_bitmap);
355 /* Move a bitmap to another bitmap. */
356 extern void bitmap_move (bitmap, bitmap);
358 /* True if two bitmaps are identical. */
359 extern bool bitmap_equal_p (const_bitmap, const_bitmap);
361 /* True if the bitmaps intersect (their AND is non-empty). */
362 extern bool bitmap_intersect_p (const_bitmap, const_bitmap);
364 /* True if the complement of the second intersects the first (their
365 AND_COMPL is non-empty). */
366 extern bool bitmap_intersect_compl_p (const_bitmap, const_bitmap);
368 /* True if MAP is an empty bitmap. */
369 inline bool bitmap_empty_p (const_bitmap map)
371 return !map->first;
374 /* True if the bitmap has only a single bit set. */
375 extern bool bitmap_single_bit_set_p (const_bitmap);
377 /* Count the number of bits set in the bitmap. */
378 extern unsigned long bitmap_count_bits (const_bitmap);
380 /* Count the number of unique bits set across the two bitmaps. */
381 extern unsigned long bitmap_count_unique_bits (const_bitmap, const_bitmap);
383 /* Boolean operations on bitmaps. The _into variants are two operand
384 versions that modify the first source operand. The other variants
385 are three operand versions that to not destroy the source bitmaps.
386 The operations supported are &, & ~, |, ^. */
387 extern void bitmap_and (bitmap, const_bitmap, const_bitmap);
388 extern bool bitmap_and_into (bitmap, const_bitmap);
389 extern bool bitmap_and_compl (bitmap, const_bitmap, const_bitmap);
390 extern bool bitmap_and_compl_into (bitmap, const_bitmap);
391 #define bitmap_compl_and(DST, A, B) bitmap_and_compl (DST, B, A)
392 extern void bitmap_compl_and_into (bitmap, const_bitmap);
393 extern void bitmap_clear_range (bitmap, unsigned int, unsigned int);
394 extern void bitmap_set_range (bitmap, unsigned int, unsigned int);
395 extern bool bitmap_ior (bitmap, const_bitmap, const_bitmap);
396 extern bool bitmap_ior_into (bitmap, const_bitmap);
397 extern void bitmap_xor (bitmap, const_bitmap, const_bitmap);
398 extern void bitmap_xor_into (bitmap, const_bitmap);
400 /* DST = A | (B & C). Return true if DST changes. */
401 extern bool bitmap_ior_and_into (bitmap DST, const_bitmap B, const_bitmap C);
402 /* DST = A | (B & ~C). Return true if DST changes. */
403 extern bool bitmap_ior_and_compl (bitmap DST, const_bitmap A,
404 const_bitmap B, const_bitmap C);
405 /* A |= (B & ~C). Return true if A changes. */
406 extern bool bitmap_ior_and_compl_into (bitmap A,
407 const_bitmap B, const_bitmap C);
409 /* Clear a single bit in a bitmap. Return true if the bit changed. */
410 extern bool bitmap_clear_bit (bitmap, int);
412 /* Set a single bit in a bitmap. Return true if the bit changed. */
413 extern bool bitmap_set_bit (bitmap, int);
415 /* Return true if a bit is set in a bitmap. */
416 extern int bitmap_bit_p (bitmap, int);
418 /* Debug functions to print a bitmap. */
419 extern void debug_bitmap (const_bitmap);
420 extern void debug_bitmap_file (FILE *, const_bitmap);
422 /* Print a bitmap. */
423 extern void bitmap_print (FILE *, const_bitmap, const char *, const char *);
425 /* Initialize and release a bitmap obstack. */
426 extern void bitmap_obstack_initialize (bitmap_obstack *);
427 extern void bitmap_obstack_release (bitmap_obstack *);
428 extern void bitmap_register (bitmap MEM_STAT_DECL);
429 extern void dump_bitmap_statistics (void);
431 /* Initialize a bitmap header. OBSTACK indicates the bitmap obstack
432 to allocate from, NULL for GC'd bitmap. */
434 static inline void
435 bitmap_initialize (bitmap head, bitmap_obstack *obstack CXX_MEM_STAT_INFO)
437 head->first = head->current = NULL;
438 head->indx = head->tree_form = 0;
439 head->obstack = obstack;
440 if (GATHER_STATISTICS)
441 bitmap_register (head PASS_MEM_STAT);
444 /* Allocate and free bitmaps from obstack, malloc and gc'd memory. */
445 extern bitmap bitmap_alloc (bitmap_obstack *obstack CXX_MEM_STAT_INFO);
446 #define BITMAP_ALLOC bitmap_alloc
447 extern bitmap bitmap_gc_alloc (ALONE_CXX_MEM_STAT_INFO);
448 #define BITMAP_GGC_ALLOC bitmap_gc_alloc
449 extern void bitmap_obstack_free (bitmap);
451 /* A few compatibility/functions macros for compatibility with sbitmaps */
452 inline void dump_bitmap (FILE *file, const_bitmap map)
454 bitmap_print (file, map, "", "\n");
456 extern void debug (const bitmap_head &ref);
457 extern void debug (const bitmap_head *ptr);
459 extern unsigned bitmap_first_set_bit (const_bitmap);
460 extern unsigned bitmap_last_set_bit (const_bitmap);
462 /* Compute bitmap hash (for purposes of hashing etc.) */
463 extern hashval_t bitmap_hash (const_bitmap);
465 /* Do any cleanup needed on a bitmap when it is no longer used. */
466 #define BITMAP_FREE(BITMAP) \
467 ((void) (bitmap_obstack_free ((bitmap) BITMAP), (BITMAP) = (bitmap) NULL))
469 /* Iterator for bitmaps. */
471 struct bitmap_iterator
473 /* Pointer to the current bitmap element. */
474 bitmap_element *elt1;
476 /* Pointer to 2nd bitmap element when two are involved. */
477 bitmap_element *elt2;
479 /* Word within the current element. */
480 unsigned word_no;
482 /* Contents of the actually processed word. When finding next bit
483 it is shifted right, so that the actual bit is always the least
484 significant bit of ACTUAL. */
485 BITMAP_WORD bits;
488 /* Initialize a single bitmap iterator. START_BIT is the first bit to
489 iterate from. */
491 static inline void
492 bmp_iter_set_init (bitmap_iterator *bi, const_bitmap map,
493 unsigned start_bit, unsigned *bit_no)
495 bi->elt1 = map->first;
496 bi->elt2 = NULL;
498 gcc_checking_assert (!map->tree_form);
500 /* Advance elt1 until it is not before the block containing start_bit. */
501 while (1)
503 if (!bi->elt1)
505 bi->elt1 = &bitmap_zero_bits;
506 break;
509 if (bi->elt1->indx >= start_bit / BITMAP_ELEMENT_ALL_BITS)
510 break;
511 bi->elt1 = bi->elt1->next;
514 /* We might have gone past the start bit, so reinitialize it. */
515 if (bi->elt1->indx != start_bit / BITMAP_ELEMENT_ALL_BITS)
516 start_bit = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
518 /* Initialize for what is now start_bit. */
519 bi->word_no = start_bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
520 bi->bits = bi->elt1->bits[bi->word_no];
521 bi->bits >>= start_bit % BITMAP_WORD_BITS;
523 /* If this word is zero, we must make sure we're not pointing at the
524 first bit, otherwise our incrementing to the next word boundary
525 will fail. It won't matter if this increment moves us into the
526 next word. */
527 start_bit += !bi->bits;
529 *bit_no = start_bit;
532 /* Initialize an iterator to iterate over the intersection of two
533 bitmaps. START_BIT is the bit to commence from. */
535 static inline void
536 bmp_iter_and_init (bitmap_iterator *bi, const_bitmap map1, const_bitmap map2,
537 unsigned start_bit, unsigned *bit_no)
539 bi->elt1 = map1->first;
540 bi->elt2 = map2->first;
542 gcc_checking_assert (!map1->tree_form && !map2->tree_form);
544 /* Advance elt1 until it is not before the block containing
545 start_bit. */
546 while (1)
548 if (!bi->elt1)
550 bi->elt2 = NULL;
551 break;
554 if (bi->elt1->indx >= start_bit / BITMAP_ELEMENT_ALL_BITS)
555 break;
556 bi->elt1 = bi->elt1->next;
559 /* Advance elt2 until it is not before elt1. */
560 while (1)
562 if (!bi->elt2)
564 bi->elt1 = bi->elt2 = &bitmap_zero_bits;
565 break;
568 if (bi->elt2->indx >= bi->elt1->indx)
569 break;
570 bi->elt2 = bi->elt2->next;
573 /* If we're at the same index, then we have some intersecting bits. */
574 if (bi->elt1->indx == bi->elt2->indx)
576 /* We might have advanced beyond the start_bit, so reinitialize
577 for that. */
578 if (bi->elt1->indx != start_bit / BITMAP_ELEMENT_ALL_BITS)
579 start_bit = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
581 bi->word_no = start_bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
582 bi->bits = bi->elt1->bits[bi->word_no] & bi->elt2->bits[bi->word_no];
583 bi->bits >>= start_bit % BITMAP_WORD_BITS;
585 else
587 /* Otherwise we must immediately advance elt1, so initialize for
588 that. */
589 bi->word_no = BITMAP_ELEMENT_WORDS - 1;
590 bi->bits = 0;
593 /* If this word is zero, we must make sure we're not pointing at the
594 first bit, otherwise our incrementing to the next word boundary
595 will fail. It won't matter if this increment moves us into the
596 next word. */
597 start_bit += !bi->bits;
599 *bit_no = start_bit;
602 /* Initialize an iterator to iterate over the bits in MAP1 & ~MAP2. */
604 static inline void
605 bmp_iter_and_compl_init (bitmap_iterator *bi,
606 const_bitmap map1, const_bitmap map2,
607 unsigned start_bit, unsigned *bit_no)
609 bi->elt1 = map1->first;
610 bi->elt2 = map2->first;
612 gcc_checking_assert (!map1->tree_form && !map2->tree_form);
614 /* Advance elt1 until it is not before the block containing start_bit. */
615 while (1)
617 if (!bi->elt1)
619 bi->elt1 = &bitmap_zero_bits;
620 break;
623 if (bi->elt1->indx >= start_bit / BITMAP_ELEMENT_ALL_BITS)
624 break;
625 bi->elt1 = bi->elt1->next;
628 /* Advance elt2 until it is not before elt1. */
629 while (bi->elt2 && bi->elt2->indx < bi->elt1->indx)
630 bi->elt2 = bi->elt2->next;
632 /* We might have advanced beyond the start_bit, so reinitialize for
633 that. */
634 if (bi->elt1->indx != start_bit / BITMAP_ELEMENT_ALL_BITS)
635 start_bit = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
637 bi->word_no = start_bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
638 bi->bits = bi->elt1->bits[bi->word_no];
639 if (bi->elt2 && bi->elt1->indx == bi->elt2->indx)
640 bi->bits &= ~bi->elt2->bits[bi->word_no];
641 bi->bits >>= start_bit % BITMAP_WORD_BITS;
643 /* If this word is zero, we must make sure we're not pointing at the
644 first bit, otherwise our incrementing to the next word boundary
645 will fail. It won't matter if this increment moves us into the
646 next word. */
647 start_bit += !bi->bits;
649 *bit_no = start_bit;
652 /* Advance to the next bit in BI. We don't advance to the next
653 nonzero bit yet. */
655 static inline void
656 bmp_iter_next (bitmap_iterator *bi, unsigned *bit_no)
658 bi->bits >>= 1;
659 *bit_no += 1;
662 /* Advance to first set bit in BI. */
664 static inline void
665 bmp_iter_next_bit (bitmap_iterator * bi, unsigned *bit_no)
667 #if (GCC_VERSION >= 3004)
669 unsigned int n = __builtin_ctzl (bi->bits);
670 gcc_assert (sizeof (unsigned long) == sizeof (BITMAP_WORD));
671 bi->bits >>= n;
672 *bit_no += n;
674 #else
675 while (!(bi->bits & 1))
677 bi->bits >>= 1;
678 *bit_no += 1;
680 #endif
683 /* Advance to the next nonzero bit of a single bitmap, we will have
684 already advanced past the just iterated bit. Return true if there
685 is a bit to iterate. */
687 static inline bool
688 bmp_iter_set (bitmap_iterator *bi, unsigned *bit_no)
690 /* If our current word is nonzero, it contains the bit we want. */
691 if (bi->bits)
693 next_bit:
694 bmp_iter_next_bit (bi, bit_no);
695 return true;
698 /* Round up to the word boundary. We might have just iterated past
699 the end of the last word, hence the -1. It is not possible for
700 bit_no to point at the beginning of the now last word. */
701 *bit_no = ((*bit_no + BITMAP_WORD_BITS - 1)
702 / BITMAP_WORD_BITS * BITMAP_WORD_BITS);
703 bi->word_no++;
705 while (1)
707 /* Find the next nonzero word in this elt. */
708 while (bi->word_no != BITMAP_ELEMENT_WORDS)
710 bi->bits = bi->elt1->bits[bi->word_no];
711 if (bi->bits)
712 goto next_bit;
713 *bit_no += BITMAP_WORD_BITS;
714 bi->word_no++;
717 /* Make sure we didn't remove the element while iterating. */
718 gcc_checking_assert (bi->elt1->indx != -1U);
720 /* Advance to the next element. */
721 bi->elt1 = bi->elt1->next;
722 if (!bi->elt1)
723 return false;
724 *bit_no = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
725 bi->word_no = 0;
729 /* Advance to the next nonzero bit of an intersecting pair of
730 bitmaps. We will have already advanced past the just iterated bit.
731 Return true if there is a bit to iterate. */
733 static inline bool
734 bmp_iter_and (bitmap_iterator *bi, unsigned *bit_no)
736 /* If our current word is nonzero, it contains the bit we want. */
737 if (bi->bits)
739 next_bit:
740 bmp_iter_next_bit (bi, bit_no);
741 return true;
744 /* Round up to the word boundary. We might have just iterated past
745 the end of the last word, hence the -1. It is not possible for
746 bit_no to point at the beginning of the now last word. */
747 *bit_no = ((*bit_no + BITMAP_WORD_BITS - 1)
748 / BITMAP_WORD_BITS * BITMAP_WORD_BITS);
749 bi->word_no++;
751 while (1)
753 /* Find the next nonzero word in this elt. */
754 while (bi->word_no != BITMAP_ELEMENT_WORDS)
756 bi->bits = bi->elt1->bits[bi->word_no] & bi->elt2->bits[bi->word_no];
757 if (bi->bits)
758 goto next_bit;
759 *bit_no += BITMAP_WORD_BITS;
760 bi->word_no++;
763 /* Advance to the next identical element. */
766 /* Make sure we didn't remove the element while iterating. */
767 gcc_checking_assert (bi->elt1->indx != -1U);
769 /* Advance elt1 while it is less than elt2. We always want
770 to advance one elt. */
773 bi->elt1 = bi->elt1->next;
774 if (!bi->elt1)
775 return false;
777 while (bi->elt1->indx < bi->elt2->indx);
779 /* Make sure we didn't remove the element while iterating. */
780 gcc_checking_assert (bi->elt2->indx != -1U);
782 /* Advance elt2 to be no less than elt1. This might not
783 advance. */
784 while (bi->elt2->indx < bi->elt1->indx)
786 bi->elt2 = bi->elt2->next;
787 if (!bi->elt2)
788 return false;
791 while (bi->elt1->indx != bi->elt2->indx);
793 *bit_no = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
794 bi->word_no = 0;
798 /* Advance to the next nonzero bit in the intersection of
799 complemented bitmaps. We will have already advanced past the just
800 iterated bit. */
802 static inline bool
803 bmp_iter_and_compl (bitmap_iterator *bi, unsigned *bit_no)
805 /* If our current word is nonzero, it contains the bit we want. */
806 if (bi->bits)
808 next_bit:
809 bmp_iter_next_bit (bi, bit_no);
810 return true;
813 /* Round up to the word boundary. We might have just iterated past
814 the end of the last word, hence the -1. It is not possible for
815 bit_no to point at the beginning of the now last word. */
816 *bit_no = ((*bit_no + BITMAP_WORD_BITS - 1)
817 / BITMAP_WORD_BITS * BITMAP_WORD_BITS);
818 bi->word_no++;
820 while (1)
822 /* Find the next nonzero word in this elt. */
823 while (bi->word_no != BITMAP_ELEMENT_WORDS)
825 bi->bits = bi->elt1->bits[bi->word_no];
826 if (bi->elt2 && bi->elt2->indx == bi->elt1->indx)
827 bi->bits &= ~bi->elt2->bits[bi->word_no];
828 if (bi->bits)
829 goto next_bit;
830 *bit_no += BITMAP_WORD_BITS;
831 bi->word_no++;
834 /* Make sure we didn't remove the element while iterating. */
835 gcc_checking_assert (bi->elt1->indx != -1U);
837 /* Advance to the next element of elt1. */
838 bi->elt1 = bi->elt1->next;
839 if (!bi->elt1)
840 return false;
842 /* Make sure we didn't remove the element while iterating. */
843 gcc_checking_assert (! bi->elt2 || bi->elt2->indx != -1U);
845 /* Advance elt2 until it is no less than elt1. */
846 while (bi->elt2 && bi->elt2->indx < bi->elt1->indx)
847 bi->elt2 = bi->elt2->next;
849 *bit_no = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
850 bi->word_no = 0;
854 /* If you are modifying a bitmap you are currently iterating over you
855 have to ensure to
856 - never remove the current bit;
857 - if you set or clear a bit before the current bit this operation
858 will not affect the set of bits you are visiting during the iteration;
859 - if you set or clear a bit after the current bit it is unspecified
860 whether that affects the set of bits you are visiting during the
861 iteration.
862 If you want to remove the current bit you can delay this to the next
863 iteration (and after the iteration in case the last iteration is
864 affected). */
866 /* Loop over all bits set in BITMAP, starting with MIN and setting
867 BITNUM to the bit number. ITER is a bitmap iterator. BITNUM
868 should be treated as a read-only variable as it contains loop
869 state. */
871 #ifndef EXECUTE_IF_SET_IN_BITMAP
872 /* See sbitmap.h for the other definition of EXECUTE_IF_SET_IN_BITMAP. */
873 #define EXECUTE_IF_SET_IN_BITMAP(BITMAP, MIN, BITNUM, ITER) \
874 for (bmp_iter_set_init (&(ITER), (BITMAP), (MIN), &(BITNUM)); \
875 bmp_iter_set (&(ITER), &(BITNUM)); \
876 bmp_iter_next (&(ITER), &(BITNUM)))
877 #endif
879 /* Loop over all the bits set in BITMAP1 & BITMAP2, starting with MIN
880 and setting BITNUM to the bit number. ITER is a bitmap iterator.
881 BITNUM should be treated as a read-only variable as it contains
882 loop state. */
884 #define EXECUTE_IF_AND_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, ITER) \
885 for (bmp_iter_and_init (&(ITER), (BITMAP1), (BITMAP2), (MIN), \
886 &(BITNUM)); \
887 bmp_iter_and (&(ITER), &(BITNUM)); \
888 bmp_iter_next (&(ITER), &(BITNUM)))
890 /* Loop over all the bits set in BITMAP1 & ~BITMAP2, starting with MIN
891 and setting BITNUM to the bit number. ITER is a bitmap iterator.
892 BITNUM should be treated as a read-only variable as it contains
893 loop state. */
895 #define EXECUTE_IF_AND_COMPL_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, ITER) \
896 for (bmp_iter_and_compl_init (&(ITER), (BITMAP1), (BITMAP2), (MIN), \
897 &(BITNUM)); \
898 bmp_iter_and_compl (&(ITER), &(BITNUM)); \
899 bmp_iter_next (&(ITER), &(BITNUM)))
901 /* A class that ties the lifetime of a bitmap to its scope. */
902 class auto_bitmap
904 public:
905 auto_bitmap () { bitmap_initialize (&m_bits, &bitmap_default_obstack); }
906 explicit auto_bitmap (bitmap_obstack *o) { bitmap_initialize (&m_bits, o); }
907 ~auto_bitmap () { bitmap_clear (&m_bits); }
908 // Allow calling bitmap functions on our bitmap.
909 operator bitmap () { return &m_bits; }
911 private:
912 // Prevent making a copy that references our bitmap.
913 auto_bitmap (const auto_bitmap &);
914 auto_bitmap &operator = (const auto_bitmap &);
915 #if __cplusplus >= 201103L
916 auto_bitmap (auto_bitmap &&);
917 auto_bitmap &operator = (auto_bitmap &&);
918 #endif
920 bitmap_head m_bits;
923 #endif /* GCC_BITMAP_H */