1/* Functions to support general ended bitmaps.
2 Copyright (C) 1997-2023 Free Software Foundation, Inc.
3
4This file is part of GCC.
5
6GCC is free software; you can redistribute it and/or modify it under
7the terms of the GNU General Public License as published by the Free
8Software Foundation; either version 3, or (at your option) any later
9version.
10
11GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12WARRANTY; without even the implied warranty of MERCHANTABILITY or
13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14for more details.
15
16You should have received a copy of the GNU General Public License
17along with GCC; see the file COPYING3. If not see
18<http://www.gnu.org/licenses/>. */
19
20#ifndef GCC_BITMAP_H
21#define GCC_BITMAP_H
22
23/* Implementation of sparse integer sets as a linked list or tree.
24
25 This sparse set representation is suitable for sparse sets with an
26 unknown (a priori) universe.
27
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.
38
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)
42
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.
49
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).
53
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.
58
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.).
63
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.
69
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:
74
75 * from list to tree view : bitmap_tree_view
76 * from tree to list view : bitmap_list_view
77
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.
85
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.
89
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.
93
94
95 LINKED LIST FORM
96 ================
97
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).
102
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.
107
108 The following operations can always be performed in O(1) time in
109 list view:
110
111 * clear : bitmap_clear
112 * smallest_member : bitmap_first_set_bit
113 * pop_smallest : bitmap_clear_first_set_bit
114 * choose_one : (not implemented, but could be
115 in constant time)
116
117 The following operations can be performed in O(E) time worst-case in
118 list view (with E the number of elements in the linked list), but in
119 O(1) time with a suitable access patterns:
120
121 * member_p : bitmap_bit_p
122 * add_member : bitmap_set_bit / bitmap_set_range
123 * remove_member : bitmap_clear_bit / bitmap_clear_range
124
125 The following operations can be performed in O(E) time in list view:
126
127 * cardinality : bitmap_count_bits
128 * largest_member : bitmap_last_set_bit (but this could
129 in constant time with a pointer to
130 the last element in the chain)
131 * set_size : bitmap_last_set_bit
132
133 In tree view the following operations can all be performed in O(log E)
134 amortized time with O(E) worst-case behavior.
135
136 * smallest_member
137 * pop_smallest
138 * largest_member
139 * set_size
140 * member_p
141 * add_member
142 * remove_member
143
144 Additionally, the linked-list sparse set representation supports
145 enumeration of the members in O(E) time:
146
147 * forall : EXECUTE_IF_SET_IN_BITMAP
148 * set_copy : bitmap_copy
149 * set_intersection : bitmap_intersect_p /
150 bitmap_and / bitmap_and_into /
151 EXECUTE_IF_AND_IN_BITMAP
152 * set_union : bitmap_ior / bitmap_ior_into
153 * set_difference : bitmap_intersect_compl_p /
154 bitmap_and_comp / bitmap_and_comp_into /
155 EXECUTE_IF_AND_COMPL_IN_BITMAP
156 * set_disjuction : bitmap_xor_comp / bitmap_xor_comp_into
157 * set_compare : bitmap_equal_p
158
159 Some operations on 3 sets that occur frequently in data flow problems
160 are also implemented:
161
162 * A | (B & C) : bitmap_ior_and_into
163 * A | (B & ~C) : bitmap_ior_and_compl /
164 bitmap_ior_and_compl_into
165
166
167 BINARY TREE FORM
168 ================
169 An alternate "view" of a bitmap is its binary tree representation.
170 For this representation, splay trees are used because they can be
171 implemented using the same data structures as the linked list, with
172 no overhead for meta-data (like color, or rank) on the tree nodes.
173
174 In binary tree form, random-access to the set is much more efficient
175 than for the linked-list representation. Downsides are the high cost
176 of clearing the set, and the relatively large number of operations
177 necessary to balance the tree. Also, iterating the set members is
178 not supported.
179
180 As for the linked-list representation, the last accessed element and
181 its index are cached, so that membership tests on the latest accessed
182 members is a constant-time operation. Other lookups take O(logE)
183 time amortized (but O(E) time worst-case).
184
185 The following operations can always be performed in O(1) time:
186
187 * choose_one : (not implemented, but could be
188 implemented in constant time)
189
190 The following operations can be performed in O(logE) time amortized
191 but O(E) time worst-case, but in O(1) time if the same element is
192 accessed.
193
194 * member_p : bitmap_bit_p
195 * add_member : bitmap_set_bit
196 * remove_member : bitmap_clear_bit
197
198 The following operations can be performed in O(logE) time amortized
199 but O(E) time worst-case:
200
201 * smallest_member : bitmap_first_set_bit
202 * largest_member : bitmap_last_set_bit
203 * set_size : bitmap_last_set_bit
204
205 The following operations can be performed in O(E) time:
206
207 * clear : bitmap_clear
208
209 The binary tree sparse set representation does *not* support any form
210 of enumeration, and does also *not* support logical operations on sets.
211 The binary tree representation is only supposed to be used for sets
212 on which many random-access membership tests will happen. */
213
214#include "obstack.h"
215#include "array-traits.h"
216
217/* Bitmap memory usage. */
218class bitmap_usage: public mem_usage
219{
220public:
221 /* Default contructor. */
222 bitmap_usage (): m_nsearches (0), m_search_iter (0) {}
223 /* Constructor. */
224 bitmap_usage (size_t allocated, size_t times, size_t peak,
225 uint64_t nsearches, uint64_t search_iter)
226 : mem_usage (allocated, times, peak),
227 m_nsearches (nsearches), m_search_iter (search_iter) {}
228
229 /* Sum the usage with SECOND usage. */
230 bitmap_usage
231 operator+ (const bitmap_usage &second)
232 {
233 return bitmap_usage (m_allocated + second.m_allocated,
234 m_times + second.m_times,
235 m_peak + second.m_peak,
236 m_nsearches + second.m_nsearches,
237 m_search_iter + second.m_search_iter);
238 }
239
240 /* Dump usage coupled to LOC location, where TOTAL is sum of all rows. */
241 inline void
242 dump (mem_location *loc, const mem_usage &total) const
243 {
244 char *location_string = loc->to_string ();
245
246 fprintf (stderr, format: "%-48s " PRsa (9) ":%5.1f%%"
247 PRsa (9) PRsa (9) ":%5.1f%%"
248 PRsa (11) PRsa (11) "%10s\n",
249 location_string, SIZE_AMOUNT (m_allocated),
250 get_percent (nominator: m_allocated, denominator: total.m_allocated),
251 SIZE_AMOUNT (m_peak), SIZE_AMOUNT (m_times),
252 get_percent (nominator: m_times, denominator: total.m_times),
253 SIZE_AMOUNT (m_nsearches), SIZE_AMOUNT (m_search_iter),
254 loc->m_ggc ? "ggc" : "heap");
255
256 free (ptr: location_string);
257 }
258
259 /* Dump header with NAME. */
260 static inline void
261 dump_header (const char *name)
262 {
263 fprintf (stderr, format: "%-48s %11s%16s%17s%12s%12s%10s\n", name, "Leak", "Peak",
264 "Times", "N searches", "Search iter", "Type");
265 }
266
267 /* Number search operations. */
268 uint64_t m_nsearches;
269 /* Number of search iterations. */
270 uint64_t m_search_iter;
271};
272
273/* Bitmap memory description. */
274extern mem_alloc_description<bitmap_usage> bitmap_mem_desc;
275
276/* Fundamental storage type for bitmap. */
277
278typedef unsigned long BITMAP_WORD;
279/* BITMAP_WORD_BITS needs to be unsigned, but cannot contain casts as
280 it is used in preprocessor directives -- hence the 1u. */
281#define BITMAP_WORD_BITS (CHAR_BIT * SIZEOF_LONG * 1u)
282
283/* Number of words to use for each element in the linked list. */
284
285#ifndef BITMAP_ELEMENT_WORDS
286#define BITMAP_ELEMENT_WORDS ((128 + BITMAP_WORD_BITS - 1) / BITMAP_WORD_BITS)
287#endif
288
289/* Number of bits in each actual element of a bitmap. */
290
291#define BITMAP_ELEMENT_ALL_BITS (BITMAP_ELEMENT_WORDS * BITMAP_WORD_BITS)
292
293/* Obstack for allocating bitmaps and elements from. */
294struct bitmap_obstack {
295 struct bitmap_element *elements;
296 bitmap_head *heads;
297 struct obstack obstack;
298};
299
300/* Bitmap set element. We use a linked list to hold only the bits that
301 are set. This allows for use to grow the bitset dynamically without
302 having to realloc and copy a giant bit array.
303
304 The free list is implemented as a list of lists. There is one
305 outer list connected together by prev fields. Each element of that
306 outer is an inner list (that may consist only of the outer list
307 element) that are connected by the next fields. The prev pointer
308 is undefined for interior elements. This allows
309 bitmap_elt_clear_from to be implemented in unit time rather than
310 linear in the number of elements to be freed. */
311
312struct GTY((chain_next ("%h.next"))) bitmap_element {
313 /* In list form, the next element in the linked list;
314 in tree form, the left child node in the tree. */
315 struct bitmap_element *next;
316 /* In list form, the previous element in the linked list;
317 in tree form, the right child node in the tree. */
318 struct bitmap_element *prev;
319 /* regno/BITMAP_ELEMENT_ALL_BITS. */
320 unsigned int indx;
321 /* Bits that are set, counting from INDX, inclusive */
322 BITMAP_WORD bits[BITMAP_ELEMENT_WORDS];
323};
324
325/* Head of bitmap linked list. The 'current' member points to something
326 already pointed to by the chain started by first, so GTY((skip)) it. */
327
328class GTY(()) bitmap_head {
329public:
330 static bitmap_obstack crashme;
331 /* Poison obstack to not make it not a valid initialized GC bitmap. */
332 CONSTEXPR bitmap_head()
333 : indx (0), tree_form (false), padding (0), alloc_descriptor (0), first (NULL),
334 current (NULL), obstack (&crashme)
335 {}
336 /* Index of last element looked at. */
337 unsigned int indx;
338 /* False if the bitmap is in list form; true if the bitmap is in tree form.
339 Bitmap iterators only work on bitmaps in list form. */
340 unsigned tree_form: 1;
341 /* Next integer is shifted, so padding is needed. */
342 unsigned padding: 2;
343 /* Bitmap UID used for memory allocation statistics. */
344 unsigned alloc_descriptor: 29;
345 /* In list form, the first element in the linked list;
346 in tree form, the root of the tree. */
347 bitmap_element *first;
348 /* Last element looked at. */
349 bitmap_element * GTY((skip(""))) current;
350 /* Obstack to allocate elements from. If NULL, then use GGC allocation. */
351 bitmap_obstack * GTY((skip(""))) obstack;
352
353 /* Dump bitmap. */
354 void dump ();
355
356 /* Get bitmap descriptor UID casted to an unsigned integer pointer.
357 Shift the descriptor because pointer_hash<Type>::hash is
358 doing >> 3 shift operation. */
359 unsigned *get_descriptor ()
360 {
361 return (unsigned *)(ptrdiff_t)(alloc_descriptor << 3);
362 }
363};
364
365/* Global data */
366extern bitmap_element bitmap_zero_bits; /* Zero bitmap element */
367extern bitmap_obstack bitmap_default_obstack; /* Default bitmap obstack */
368
369/* Change the view of the bitmap to list, or tree. */
370void bitmap_list_view (bitmap);
371void bitmap_tree_view (bitmap);
372
373/* Clear a bitmap by freeing up the linked list. */
374extern void bitmap_clear (bitmap);
375
376/* Copy a bitmap to another bitmap. */
377extern void bitmap_copy (bitmap, const_bitmap);
378
379/* Move a bitmap to another bitmap. */
380extern void bitmap_move (bitmap, bitmap);
381
382/* True if two bitmaps are identical. */
383extern bool bitmap_equal_p (const_bitmap, const_bitmap);
384
385/* True if the bitmaps intersect (their AND is non-empty). */
386extern bool bitmap_intersect_p (const_bitmap, const_bitmap);
387
388/* True if the complement of the second intersects the first (their
389 AND_COMPL is non-empty). */
390extern bool bitmap_intersect_compl_p (const_bitmap, const_bitmap);
391
392/* True if MAP is an empty bitmap. */
393inline bool bitmap_empty_p (const_bitmap map)
394{
395 return !map->first;
396}
397
398/* True if the bitmap has only a single bit set. */
399extern bool bitmap_single_bit_set_p (const_bitmap);
400
401/* Count the number of bits set in the bitmap. */
402extern unsigned long bitmap_count_bits (const_bitmap);
403
404/* Count the number of unique bits set across the two bitmaps. */
405extern unsigned long bitmap_count_unique_bits (const_bitmap, const_bitmap);
406
407/* Boolean operations on bitmaps. The _into variants are two operand
408 versions that modify the first source operand. The other variants
409 are three operand versions that to not destroy the source bitmaps.
410 The operations supported are &, & ~, |, ^. */
411extern void bitmap_and (bitmap, const_bitmap, const_bitmap);
412extern bool bitmap_and_into (bitmap, const_bitmap);
413extern bool bitmap_and_compl (bitmap, const_bitmap, const_bitmap);
414extern bool bitmap_and_compl_into (bitmap, const_bitmap);
415#define bitmap_compl_and(DST, A, B) bitmap_and_compl (DST, B, A)
416extern void bitmap_compl_and_into (bitmap, const_bitmap);
417extern void bitmap_clear_range (bitmap, unsigned int, unsigned int);
418extern void bitmap_set_range (bitmap, unsigned int, unsigned int);
419extern bool bitmap_ior (bitmap, const_bitmap, const_bitmap);
420extern bool bitmap_ior_into (bitmap, const_bitmap);
421extern bool bitmap_ior_into_and_free (bitmap, bitmap *);
422extern void bitmap_xor (bitmap, const_bitmap, const_bitmap);
423extern void bitmap_xor_into (bitmap, const_bitmap);
424
425/* DST = A | (B & C). Return true if DST changes. */
426extern bool bitmap_ior_and_into (bitmap DST, const_bitmap B, const_bitmap C);
427/* DST = A | (B & ~C). Return true if DST changes. */
428extern bool bitmap_ior_and_compl (bitmap DST, const_bitmap A,
429 const_bitmap B, const_bitmap C);
430/* A |= (B & ~C). Return true if A changes. */
431extern bool bitmap_ior_and_compl_into (bitmap A,
432 const_bitmap B, const_bitmap C);
433
434/* Clear a single bit in a bitmap. Return true if the bit changed. */
435extern bool bitmap_clear_bit (bitmap, int);
436
437/* Set a single bit in a bitmap. Return true if the bit changed. */
438extern bool bitmap_set_bit (bitmap, int);
439
440/* Return true if a bit is set in a bitmap. */
441extern bool bitmap_bit_p (const_bitmap, int);
442
443/* Set and get multiple bit values in a sparse bitmap. This allows a bitmap to
444 function as a sparse array of bit patterns where the patterns are
445 multiples of power of 2. This is more efficient than performing this as
446 multiple individual operations. */
447void bitmap_set_aligned_chunk (bitmap, unsigned int, unsigned int, BITMAP_WORD);
448BITMAP_WORD bitmap_get_aligned_chunk (const_bitmap, unsigned int, unsigned int);
449
450/* Debug functions to print a bitmap. */
451extern void debug_bitmap (const_bitmap);
452extern void debug_bitmap_file (FILE *, const_bitmap);
453
454/* Print a bitmap. */
455extern void bitmap_print (FILE *, const_bitmap, const char *, const char *);
456
457/* Initialize and release a bitmap obstack. */
458extern void bitmap_obstack_initialize (bitmap_obstack *);
459extern void bitmap_obstack_release (bitmap_obstack *);
460extern void bitmap_register (bitmap MEM_STAT_DECL);
461extern void dump_bitmap_statistics (void);
462
463/* Initialize a bitmap header. OBSTACK indicates the bitmap obstack
464 to allocate from, NULL for GC'd bitmap. */
465
466inline void
467bitmap_initialize (bitmap head, bitmap_obstack *obstack CXX_MEM_STAT_INFO)
468{
469 head->first = head->current = NULL;
470 head->indx = head->tree_form = 0;
471 head->padding = 0;
472 head->alloc_descriptor = 0;
473 head->obstack = obstack;
474 if (GATHER_STATISTICS)
475 bitmap_register (head PASS_MEM_STAT);
476}
477
478/* Release a bitmap (but not its head). This is suitable for pairing with
479 bitmap_initialize. */
480
481inline void
482bitmap_release (bitmap head)
483{
484 bitmap_clear (head);
485 /* Poison the obstack pointer so the obstack can be safely released.
486 Do not zero it as the bitmap then becomes initialized GC. */
487 head->obstack = &bitmap_head::crashme;
488}
489
490/* Allocate and free bitmaps from obstack, malloc and gc'd memory. */
491extern bitmap bitmap_alloc (bitmap_obstack *obstack CXX_MEM_STAT_INFO);
492#define BITMAP_ALLOC bitmap_alloc
493extern bitmap bitmap_gc_alloc (ALONE_CXX_MEM_STAT_INFO);
494#define BITMAP_GGC_ALLOC bitmap_gc_alloc
495extern void bitmap_obstack_free (bitmap);
496
497/* A few compatibility/functions macros for compatibility with sbitmaps */
498inline void dump_bitmap (FILE *file, const_bitmap map)
499{
500 bitmap_print (file, map, "", "\n");
501}
502extern void debug (const bitmap_head &ref);
503extern void debug (const bitmap_head *ptr);
504
505extern unsigned bitmap_first_set_bit (const_bitmap);
506extern unsigned bitmap_clear_first_set_bit (bitmap);
507extern unsigned bitmap_last_set_bit (const_bitmap);
508
509/* Compute bitmap hash (for purposes of hashing etc.) */
510extern hashval_t bitmap_hash (const_bitmap);
511
512/* Do any cleanup needed on a bitmap when it is no longer used. */
513#define BITMAP_FREE(BITMAP) \
514 ((void) (bitmap_obstack_free ((bitmap) BITMAP), (BITMAP) = (bitmap) NULL))
515
516/* Iterator for bitmaps. */
517
518struct bitmap_iterator
519{
520 /* Pointer to the current bitmap element. */
521 bitmap_element *elt1;
522
523 /* Pointer to 2nd bitmap element when two are involved. */
524 bitmap_element *elt2;
525
526 /* Word within the current element. */
527 unsigned word_no;
528
529 /* Contents of the actually processed word. When finding next bit
530 it is shifted right, so that the actual bit is always the least
531 significant bit of ACTUAL. */
532 BITMAP_WORD bits;
533};
534
535/* Initialize a single bitmap iterator. START_BIT is the first bit to
536 iterate from. */
537
538inline void
539bmp_iter_set_init (bitmap_iterator *bi, const_bitmap map,
540 unsigned start_bit, unsigned *bit_no)
541{
542 bi->elt1 = map->first;
543 bi->elt2 = NULL;
544
545 gcc_checking_assert (!map->tree_form);
546
547 /* Advance elt1 until it is not before the block containing start_bit. */
548 while (1)
549 {
550 if (!bi->elt1)
551 {
552 bi->elt1 = &bitmap_zero_bits;
553 break;
554 }
555
556 if (bi->elt1->indx >= start_bit / BITMAP_ELEMENT_ALL_BITS)
557 break;
558 bi->elt1 = bi->elt1->next;
559 }
560
561 /* We might have gone past the start bit, so reinitialize it. */
562 if (bi->elt1->indx != start_bit / BITMAP_ELEMENT_ALL_BITS)
563 start_bit = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
564
565 /* Initialize for what is now start_bit. */
566 bi->word_no = start_bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
567 bi->bits = bi->elt1->bits[bi->word_no];
568 bi->bits >>= start_bit % BITMAP_WORD_BITS;
569
570 /* If this word is zero, we must make sure we're not pointing at the
571 first bit, otherwise our incrementing to the next word boundary
572 will fail. It won't matter if this increment moves us into the
573 next word. */
574 start_bit += !bi->bits;
575
576 *bit_no = start_bit;
577}
578
579/* Initialize an iterator to iterate over the intersection of two
580 bitmaps. START_BIT is the bit to commence from. */
581
582inline void
583bmp_iter_and_init (bitmap_iterator *bi, const_bitmap map1, const_bitmap map2,
584 unsigned start_bit, unsigned *bit_no)
585{
586 bi->elt1 = map1->first;
587 bi->elt2 = map2->first;
588
589 gcc_checking_assert (!map1->tree_form && !map2->tree_form);
590
591 /* Advance elt1 until it is not before the block containing
592 start_bit. */
593 while (1)
594 {
595 if (!bi->elt1)
596 {
597 bi->elt2 = NULL;
598 break;
599 }
600
601 if (bi->elt1->indx >= start_bit / BITMAP_ELEMENT_ALL_BITS)
602 break;
603 bi->elt1 = bi->elt1->next;
604 }
605
606 /* Advance elt2 until it is not before elt1. */
607 while (1)
608 {
609 if (!bi->elt2)
610 {
611 bi->elt1 = bi->elt2 = &bitmap_zero_bits;
612 break;
613 }
614
615 if (bi->elt2->indx >= bi->elt1->indx)
616 break;
617 bi->elt2 = bi->elt2->next;
618 }
619
620 /* If we're at the same index, then we have some intersecting bits. */
621 if (bi->elt1->indx == bi->elt2->indx)
622 {
623 /* We might have advanced beyond the start_bit, so reinitialize
624 for that. */
625 if (bi->elt1->indx != start_bit / BITMAP_ELEMENT_ALL_BITS)
626 start_bit = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
627
628 bi->word_no = start_bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
629 bi->bits = bi->elt1->bits[bi->word_no] & bi->elt2->bits[bi->word_no];
630 bi->bits >>= start_bit % BITMAP_WORD_BITS;
631 }
632 else
633 {
634 /* Otherwise we must immediately advance elt1, so initialize for
635 that. */
636 bi->word_no = BITMAP_ELEMENT_WORDS - 1;
637 bi->bits = 0;
638 }
639
640 /* If this word is zero, we must make sure we're not pointing at the
641 first bit, otherwise our incrementing to the next word boundary
642 will fail. It won't matter if this increment moves us into the
643 next word. */
644 start_bit += !bi->bits;
645
646 *bit_no = start_bit;
647}
648
649/* Initialize an iterator to iterate over the bits in MAP1 & ~MAP2. */
650
651inline void
652bmp_iter_and_compl_init (bitmap_iterator *bi,
653 const_bitmap map1, const_bitmap map2,
654 unsigned start_bit, unsigned *bit_no)
655{
656 bi->elt1 = map1->first;
657 bi->elt2 = map2->first;
658
659 gcc_checking_assert (!map1->tree_form && !map2->tree_form);
660
661 /* Advance elt1 until it is not before the block containing start_bit. */
662 while (1)
663 {
664 if (!bi->elt1)
665 {
666 bi->elt1 = &bitmap_zero_bits;
667 break;
668 }
669
670 if (bi->elt1->indx >= start_bit / BITMAP_ELEMENT_ALL_BITS)
671 break;
672 bi->elt1 = bi->elt1->next;
673 }
674
675 /* Advance elt2 until it is not before elt1. */
676 while (bi->elt2 && bi->elt2->indx < bi->elt1->indx)
677 bi->elt2 = bi->elt2->next;
678
679 /* We might have advanced beyond the start_bit, so reinitialize for
680 that. */
681 if (bi->elt1->indx != start_bit / BITMAP_ELEMENT_ALL_BITS)
682 start_bit = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
683
684 bi->word_no = start_bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
685 bi->bits = bi->elt1->bits[bi->word_no];
686 if (bi->elt2 && bi->elt1->indx == bi->elt2->indx)
687 bi->bits &= ~bi->elt2->bits[bi->word_no];
688 bi->bits >>= start_bit % BITMAP_WORD_BITS;
689
690 /* If this word is zero, we must make sure we're not pointing at the
691 first bit, otherwise our incrementing to the next word boundary
692 will fail. It won't matter if this increment moves us into the
693 next word. */
694 start_bit += !bi->bits;
695
696 *bit_no = start_bit;
697}
698
699/* Advance to the next bit in BI. We don't advance to the next
700 nonzero bit yet. */
701
702inline void
703bmp_iter_next (bitmap_iterator *bi, unsigned *bit_no)
704{
705 bi->bits >>= 1;
706 *bit_no += 1;
707}
708
709/* Advance to first set bit in BI. */
710
711inline void
712bmp_iter_next_bit (bitmap_iterator * bi, unsigned *bit_no)
713{
714#if (GCC_VERSION >= 3004)
715 {
716 unsigned int n = __builtin_ctzl (bi->bits);
717 gcc_assert (sizeof (unsigned long) == sizeof (BITMAP_WORD));
718 bi->bits >>= n;
719 *bit_no += n;
720 }
721#else
722 while (!(bi->bits & 1))
723 {
724 bi->bits >>= 1;
725 *bit_no += 1;
726 }
727#endif
728}
729
730/* Advance to the next nonzero bit of a single bitmap, we will have
731 already advanced past the just iterated bit. Return true if there
732 is a bit to iterate. */
733
734inline bool
735bmp_iter_set (bitmap_iterator *bi, unsigned *bit_no)
736{
737 /* If our current word is nonzero, it contains the bit we want. */
738 if (bi->bits)
739 {
740 next_bit:
741 bmp_iter_next_bit (bi, bit_no);
742 return true;
743 }
744
745 /* Round up to the word boundary. We might have just iterated past
746 the end of the last word, hence the -1. It is not possible for
747 bit_no to point at the beginning of the now last word. */
748 *bit_no = ((*bit_no + BITMAP_WORD_BITS - 1)
749 / BITMAP_WORD_BITS * BITMAP_WORD_BITS);
750 bi->word_no++;
751
752 while (1)
753 {
754 /* Find the next nonzero word in this elt. */
755 while (bi->word_no != BITMAP_ELEMENT_WORDS)
756 {
757 bi->bits = bi->elt1->bits[bi->word_no];
758 if (bi->bits)
759 goto next_bit;
760 *bit_no += BITMAP_WORD_BITS;
761 bi->word_no++;
762 }
763
764 /* Make sure we didn't remove the element while iterating. */
765 gcc_checking_assert (bi->elt1->indx != -1U);
766
767 /* Advance to the next element. */
768 bi->elt1 = bi->elt1->next;
769 if (!bi->elt1)
770 return false;
771 *bit_no = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
772 bi->word_no = 0;
773 }
774}
775
776/* Advance to the next nonzero bit of an intersecting pair of
777 bitmaps. We will have already advanced past the just iterated bit.
778 Return true if there is a bit to iterate. */
779
780inline bool
781bmp_iter_and (bitmap_iterator *bi, unsigned *bit_no)
782{
783 /* If our current word is nonzero, it contains the bit we want. */
784 if (bi->bits)
785 {
786 next_bit:
787 bmp_iter_next_bit (bi, bit_no);
788 return true;
789 }
790
791 /* Round up to the word boundary. We might have just iterated past
792 the end of the last word, hence the -1. It is not possible for
793 bit_no to point at the beginning of the now last word. */
794 *bit_no = ((*bit_no + BITMAP_WORD_BITS - 1)
795 / BITMAP_WORD_BITS * BITMAP_WORD_BITS);
796 bi->word_no++;
797
798 while (1)
799 {
800 /* Find the next nonzero word in this elt. */
801 while (bi->word_no != BITMAP_ELEMENT_WORDS)
802 {
803 bi->bits = bi->elt1->bits[bi->word_no] & bi->elt2->bits[bi->word_no];
804 if (bi->bits)
805 goto next_bit;
806 *bit_no += BITMAP_WORD_BITS;
807 bi->word_no++;
808 }
809
810 /* Advance to the next identical element. */
811 do
812 {
813 /* Make sure we didn't remove the element while iterating. */
814 gcc_checking_assert (bi->elt1->indx != -1U);
815
816 /* Advance elt1 while it is less than elt2. We always want
817 to advance one elt. */
818 do
819 {
820 bi->elt1 = bi->elt1->next;
821 if (!bi->elt1)
822 return false;
823 }
824 while (bi->elt1->indx < bi->elt2->indx);
825
826 /* Make sure we didn't remove the element while iterating. */
827 gcc_checking_assert (bi->elt2->indx != -1U);
828
829 /* Advance elt2 to be no less than elt1. This might not
830 advance. */
831 while (bi->elt2->indx < bi->elt1->indx)
832 {
833 bi->elt2 = bi->elt2->next;
834 if (!bi->elt2)
835 return false;
836 }
837 }
838 while (bi->elt1->indx != bi->elt2->indx);
839
840 *bit_no = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
841 bi->word_no = 0;
842 }
843}
844
845/* Advance to the next nonzero bit in the intersection of
846 complemented bitmaps. We will have already advanced past the just
847 iterated bit. */
848
849inline bool
850bmp_iter_and_compl (bitmap_iterator *bi, unsigned *bit_no)
851{
852 /* If our current word is nonzero, it contains the bit we want. */
853 if (bi->bits)
854 {
855 next_bit:
856 bmp_iter_next_bit (bi, bit_no);
857 return true;
858 }
859
860 /* Round up to the word boundary. We might have just iterated past
861 the end of the last word, hence the -1. It is not possible for
862 bit_no to point at the beginning of the now last word. */
863 *bit_no = ((*bit_no + BITMAP_WORD_BITS - 1)
864 / BITMAP_WORD_BITS * BITMAP_WORD_BITS);
865 bi->word_no++;
866
867 while (1)
868 {
869 /* Find the next nonzero word in this elt. */
870 while (bi->word_no != BITMAP_ELEMENT_WORDS)
871 {
872 bi->bits = bi->elt1->bits[bi->word_no];
873 if (bi->elt2 && bi->elt2->indx == bi->elt1->indx)
874 bi->bits &= ~bi->elt2->bits[bi->word_no];
875 if (bi->bits)
876 goto next_bit;
877 *bit_no += BITMAP_WORD_BITS;
878 bi->word_no++;
879 }
880
881 /* Make sure we didn't remove the element while iterating. */
882 gcc_checking_assert (bi->elt1->indx != -1U);
883
884 /* Advance to the next element of elt1. */
885 bi->elt1 = bi->elt1->next;
886 if (!bi->elt1)
887 return false;
888
889 /* Make sure we didn't remove the element while iterating. */
890 gcc_checking_assert (! bi->elt2 || bi->elt2->indx != -1U);
891
892 /* Advance elt2 until it is no less than elt1. */
893 while (bi->elt2 && bi->elt2->indx < bi->elt1->indx)
894 bi->elt2 = bi->elt2->next;
895
896 *bit_no = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
897 bi->word_no = 0;
898 }
899}
900
901/* If you are modifying a bitmap you are currently iterating over you
902 have to ensure to
903 - never remove the current bit;
904 - if you set or clear a bit before the current bit this operation
905 will not affect the set of bits you are visiting during the iteration;
906 - if you set or clear a bit after the current bit it is unspecified
907 whether that affects the set of bits you are visiting during the
908 iteration.
909 If you want to remove the current bit you can delay this to the next
910 iteration (and after the iteration in case the last iteration is
911 affected). */
912
913/* Loop over all bits set in BITMAP, starting with MIN and setting
914 BITNUM to the bit number. ITER is a bitmap iterator. BITNUM
915 should be treated as a read-only variable as it contains loop
916 state. */
917
918#ifndef EXECUTE_IF_SET_IN_BITMAP
919/* See sbitmap.h for the other definition of EXECUTE_IF_SET_IN_BITMAP. */
920#define EXECUTE_IF_SET_IN_BITMAP(BITMAP, MIN, BITNUM, ITER) \
921 for (bmp_iter_set_init (&(ITER), (BITMAP), (MIN), &(BITNUM)); \
922 bmp_iter_set (&(ITER), &(BITNUM)); \
923 bmp_iter_next (&(ITER), &(BITNUM)))
924#endif
925
926/* Loop over all the bits set in BITMAP1 & BITMAP2, starting with MIN
927 and setting BITNUM to the bit number. ITER is a bitmap iterator.
928 BITNUM should be treated as a read-only variable as it contains
929 loop state. */
930
931#define EXECUTE_IF_AND_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, ITER) \
932 for (bmp_iter_and_init (&(ITER), (BITMAP1), (BITMAP2), (MIN), \
933 &(BITNUM)); \
934 bmp_iter_and (&(ITER), &(BITNUM)); \
935 bmp_iter_next (&(ITER), &(BITNUM)))
936
937/* Loop over all the bits set in BITMAP1 & ~BITMAP2, starting with MIN
938 and setting BITNUM to the bit number. ITER is a bitmap iterator.
939 BITNUM should be treated as a read-only variable as it contains
940 loop state. */
941
942#define EXECUTE_IF_AND_COMPL_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, ITER) \
943 for (bmp_iter_and_compl_init (&(ITER), (BITMAP1), (BITMAP2), (MIN), \
944 &(BITNUM)); \
945 bmp_iter_and_compl (&(ITER), &(BITNUM)); \
946 bmp_iter_next (&(ITER), &(BITNUM)))
947
948/* A class that ties the lifetime of a bitmap to its scope. */
949class auto_bitmap
950{
951 public:
952 auto_bitmap (ALONE_CXX_MEM_STAT_INFO)
953 { bitmap_initialize (head: &m_bits, obstack: &bitmap_default_obstack PASS_MEM_STAT); }
954 explicit auto_bitmap (bitmap_obstack *o CXX_MEM_STAT_INFO)
955 { bitmap_initialize (head: &m_bits, obstack: o PASS_MEM_STAT); }
956 ~auto_bitmap () { bitmap_clear (&m_bits); }
957 // Allow calling bitmap functions on our bitmap.
958 operator bitmap () { return &m_bits; }
959
960 private:
961 // Prevent making a copy that references our bitmap.
962 auto_bitmap (const auto_bitmap &);
963 auto_bitmap &operator = (const auto_bitmap &);
964 auto_bitmap (auto_bitmap &&);
965 auto_bitmap &operator = (auto_bitmap &&);
966
967 bitmap_head m_bits;
968};
969
970extern void debug (const auto_bitmap &ref);
971extern void debug (const auto_bitmap *ptr);
972
973/* Base class for bitmap_view; see there for details. */
974template<typename T, typename Traits = array_traits<T> >
975class base_bitmap_view
976{
977public:
978 typedef typename Traits::element_type array_element_type;
979
980 base_bitmap_view (const T &, bitmap_element *);
981 operator const_bitmap () const { return &m_head; }
982
983private:
984 base_bitmap_view (const base_bitmap_view &);
985
986 bitmap_head m_head;
987};
988
989/* Provides a read-only bitmap view of a single integer bitmask or a
990 constant-sized array of integer bitmasks, or of a wrapper around such
991 bitmasks. */
992template<typename T, typename Traits>
993class bitmap_view<T, Traits, true> : public base_bitmap_view<T, Traits>
994{
995public:
996 bitmap_view (const T &array)
997 : base_bitmap_view<T, Traits> (array, m_bitmap_elements) {}
998
999private:
1000 /* How many bitmap_elements we need to hold a full T. */
1001 static const size_t num_bitmap_elements
1002 = CEIL (CHAR_BIT
1003 * sizeof (typename Traits::element_type)
1004 * Traits::constant_size,
1005 BITMAP_ELEMENT_ALL_BITS);
1006 bitmap_element m_bitmap_elements[num_bitmap_elements];
1007};
1008
1009/* Initialize the view for array ARRAY, using the array of bitmap
1010 elements in BITMAP_ELEMENTS (which is known to contain enough
1011 entries). */
1012template<typename T, typename Traits>
1013base_bitmap_view<T, Traits>::base_bitmap_view (const T &array,
1014 bitmap_element *bitmap_elements)
1015{
1016 m_head.obstack = NULL;
1017
1018 /* The code currently assumes that each element of ARRAY corresponds
1019 to exactly one bitmap_element. */
1020 const size_t array_element_bits = CHAR_BIT * sizeof (array_element_type);
1021 STATIC_ASSERT (BITMAP_ELEMENT_ALL_BITS % array_element_bits == 0);
1022 size_t array_step = BITMAP_ELEMENT_ALL_BITS / array_element_bits;
1023 size_t array_size = Traits::size (array);
1024
1025 /* Process each potential bitmap_element in turn. The loop is written
1026 this way rather than per array element because usually there are
1027 only a small number of array elements per bitmap element (typically
1028 two or four). The inner loops should therefore unroll completely. */
1029 const array_element_type *array_elements = Traits::base (array);
1030 unsigned int indx = 0;
1031 for (size_t array_base = 0;
1032 array_base < array_size;
1033 array_base += array_step, indx += 1)
1034 {
1035 /* How many array elements are in this particular bitmap_element. */
1036 unsigned int array_count
1037 = (STATIC_CONSTANT_P (array_size % array_step == 0)
1038 ? array_step : MIN (array_step, array_size - array_base));
1039
1040 /* See whether we need this bitmap element. */
1041 array_element_type ior = array_elements[array_base];
1042 for (size_t i = 1; i < array_count; ++i)
1043 ior |= array_elements[array_base + i];
1044 if (ior == 0)
1045 continue;
1046
1047 /* Grab the next bitmap element and chain it. */
1048 bitmap_element *bitmap_element = bitmap_elements++;
1049 if (m_head.current)
1050 m_head.current->next = bitmap_element;
1051 else
1052 m_head.first = bitmap_element;
1053 bitmap_element->prev = m_head.current;
1054 bitmap_element->next = NULL;
1055 bitmap_element->indx = indx;
1056 m_head.current = bitmap_element;
1057 m_head.indx = indx;
1058
1059 /* Fill in the bits of the bitmap element. */
1060 if (array_element_bits < BITMAP_WORD_BITS)
1061 {
1062 /* Multiple array elements fit in one element of
1063 bitmap_element->bits. */
1064 size_t array_i = array_base;
1065 for (unsigned int word_i = 0; word_i < BITMAP_ELEMENT_WORDS;
1066 ++word_i)
1067 {
1068 BITMAP_WORD word = 0;
1069 for (unsigned int shift = 0;
1070 shift < BITMAP_WORD_BITS && array_i < array_size;
1071 shift += array_element_bits)
1072 word |= array_elements[array_i++] << shift;
1073 bitmap_element->bits[word_i] = word;
1074 }
1075 }
1076 else
1077 {
1078 /* Array elements are the same size as elements of
1079 bitmap_element->bits, or are an exact multiple of that size. */
1080 unsigned int word_i = 0;
1081 for (unsigned int i = 0; i < array_count; ++i)
1082 for (unsigned int shift = 0; shift < array_element_bits;
1083 shift += BITMAP_WORD_BITS)
1084 bitmap_element->bits[word_i++]
1085 = array_elements[array_base + i] >> shift;
1086 while (word_i < BITMAP_ELEMENT_WORDS)
1087 bitmap_element->bits[word_i++] = 0;
1088 }
1089 }
1090}
1091
1092#endif /* GCC_BITMAP_H */
1093

source code of gcc/bitmap.h