1 /* Functions to support general ended bitmaps.
2 Copyright (C) 1997-2023 Free Software Foundation, Inc.
3
4 This file is part of GCC.
5
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.
10
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.
15
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/>. */
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 * choose_one : (not implemented, but could be
114 in constant time)
115
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:
119
120 * member_p : bitmap_bit_p
121 * add_member : bitmap_set_bit / bitmap_set_range
122 * remove_member : bitmap_clear_bit / bitmap_clear_range
123
124 The following operations can be performed in O(E) time in list view:
125
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
131
132 In tree view the following operations can all be performed in O(log E)
133 amortized time with O(E) worst-case behavior.
134
135 * smallest_member
136 * largest_member
137 * set_size
138 * member_p
139 * add_member
140 * remove_member
141
142 Additionally, the linked-list sparse set representation supports
143 enumeration of the members in O(E) time:
144
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
156
157 Some operations on 3 sets that occur frequently in data flow problems
158 are also implemented:
159
160 * A | (B & C) : bitmap_ior_and_into
161 * A | (B & ~C) : bitmap_ior_and_compl /
162 bitmap_ior_and_compl_into
163
164
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.
171
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.
177
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).
182
183 The following operations can always be performed in O(1) time:
184
185 * choose_one : (not implemented, but could be
186 implemented in constant time)
187
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.
191
192 * member_p : bitmap_bit_p
193 * add_member : bitmap_set_bit
194 * remove_member : bitmap_clear_bit
195
196 The following operations can be performed in O(logE) time amortized
197 but O(E) time worst-case:
198
199 * smallest_member : bitmap_first_set_bit
200 * largest_member : bitmap_last_set_bit
201 * set_size : bitmap_last_set_bit
202
203 The following operations can be performed in O(E) time:
204
205 * clear : bitmap_clear
206
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. */
211
212 #include "obstack.h"
213 #include "array-traits.h"
214
215 /* Bitmap memory usage. */
216 class bitmap_usage: public mem_usage
217 {
218 public:
219 /* Default contructor. */
220 bitmap_usage (): m_nsearches (0), m_search_iter (0) {}
221 /* Constructor. */
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) {}
226
227 /* Sum the usage with SECOND usage. */
228 bitmap_usage
229 operator+ (const bitmap_usage &second)
230 {
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);
236 }
237
238 /* Dump usage coupled to LOC location, where TOTAL is sum of all rows. */
239 inline void
240 dump (mem_location *loc, const mem_usage &total) const
241 {
242 char *location_string = loc->to_string ();
243
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");
253
254 free (location_string);
255 }
256
257 /* Dump header with NAME. */
258 static inline void
259 dump_header (const char *name)
260 {
261 fprintf (stderr, "%-48s %11s%16s%17s%12s%12s%10s\n", name, "Leak", "Peak",
262 "Times", "N searches", "Search iter", "Type");
263 }
264
265 /* Number search operations. */
266 uint64_t m_nsearches;
267 /* Number of search iterations. */
268 uint64_t m_search_iter;
269 };
270
271 /* Bitmap memory description. */
272 extern mem_alloc_description<bitmap_usage> bitmap_mem_desc;
273
274 /* Fundamental storage type for bitmap. */
275
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)
280
281 /* Number of words to use for each element in the linked list. */
282
283 #ifndef BITMAP_ELEMENT_WORDS
284 #define BITMAP_ELEMENT_WORDS ((128 + BITMAP_WORD_BITS - 1) / BITMAP_WORD_BITS)
285 #endif
286
287 /* Number of bits in each actual element of a bitmap. */
288
289 #define BITMAP_ELEMENT_ALL_BITS (BITMAP_ELEMENT_WORDS * BITMAP_WORD_BITS)
290
291 /* Obstack for allocating bitmaps and elements from. */
292 struct bitmap_obstack {
293 struct bitmap_element *elements;
294 bitmap_head *heads;
295 struct obstack obstack;
296 };
297
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.
301
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. */
309
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. */
318 unsigned int indx;
319 /* Bits that are set, counting from INDX, inclusive */
320 BITMAP_WORD bits[BITMAP_ELEMENT_WORDS];
321 };
322
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. */
325
326 class GTY(()) bitmap_head {
327 public:
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)
333 {}
334 /* Index of last element looked at. */
335 unsigned int indx;
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. */
340 unsigned padding: 2;
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;
350
351 /* Dump bitmap. */
352 void dump ();
353
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 ()
358 {
359 return (unsigned *)(ptrdiff_t)(alloc_descriptor << 3);
360 }
361 };
362
363 /* Global data */
364 extern bitmap_element bitmap_zero_bits; /* Zero bitmap element */
365 extern bitmap_obstack bitmap_default_obstack; /* Default bitmap obstack */
366
367 /* Change the view of the bitmap to list, or tree. */
368 void bitmap_list_view (bitmap);
369 void bitmap_tree_view (bitmap);
370
371 /* Clear a bitmap by freeing up the linked list. */
372 extern void bitmap_clear (bitmap);
373
374 /* Copy a bitmap to another bitmap. */
375 extern void bitmap_copy (bitmap, const_bitmap);
376
377 /* Move a bitmap to another bitmap. */
378 extern void bitmap_move (bitmap, bitmap);
379
380 /* True if two bitmaps are identical. */
381 extern bool bitmap_equal_p (const_bitmap, const_bitmap);
382
383 /* True if the bitmaps intersect (their AND is non-empty). */
384 extern bool bitmap_intersect_p (const_bitmap, const_bitmap);
385
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);
389
390 /* True if MAP is an empty bitmap. */
391 inline bool bitmap_empty_p (const_bitmap map)
392 {
393 return !map->first;
394 }
395
396 /* True if the bitmap has only a single bit set. */
397 extern bool bitmap_single_bit_set_p (const_bitmap);
398
399 /* Count the number of bits set in the bitmap. */
400 extern unsigned long bitmap_count_bits (const_bitmap);
401
402 /* Count the number of unique bits set across the two bitmaps. */
403 extern unsigned long bitmap_count_unique_bits (const_bitmap, const_bitmap);
404
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);
422
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);
431
432 /* Clear a single bit in a bitmap. Return true if the bit changed. */
433 extern bool bitmap_clear_bit (bitmap, int);
434
435 /* Set a single bit in a bitmap. Return true if the bit changed. */
436 extern bool bitmap_set_bit (bitmap, int);
437
438 /* Return true if a bit is set in a bitmap. */
439 extern bool bitmap_bit_p (const_bitmap, int);
440
441 /* Set and get multiple bit values in a sparse bitmap. This allows a bitmap to
442 function as a sparse array of bit patterns where the patterns are
443 multiples of power of 2. This is more efficient than performing this as
444 multiple individual operations. */
445 void bitmap_set_aligned_chunk (bitmap, unsigned int, unsigned int, BITMAP_WORD);
446 BITMAP_WORD bitmap_get_aligned_chunk (const_bitmap, unsigned int, unsigned int);
447
448 /* Debug functions to print a bitmap. */
449 extern void debug_bitmap (const_bitmap);
450 extern void debug_bitmap_file (FILE *, const_bitmap);
451
452 /* Print a bitmap. */
453 extern void bitmap_print (FILE *, const_bitmap, const char *, const char *);
454
455 /* Initialize and release a bitmap obstack. */
456 extern void bitmap_obstack_initialize (bitmap_obstack *);
457 extern void bitmap_obstack_release (bitmap_obstack *);
458 extern void bitmap_register (bitmap MEM_STAT_DECL);
459 extern void dump_bitmap_statistics (void);
460
461 /* Initialize a bitmap header. OBSTACK indicates the bitmap obstack
462 to allocate from, NULL for GC'd bitmap. */
463
464 inline void
465 bitmap_initialize (bitmap head, bitmap_obstack *obstack CXX_MEM_STAT_INFO)
466 {
467 head->first = head->current = NULL;
468 head->indx = head->tree_form = 0;
469 head->padding = 0;
470 head->alloc_descriptor = 0;
471 head->obstack = obstack;
472 if (GATHER_STATISTICS)
473 bitmap_register (head PASS_MEM_STAT);
474 }
475
476 /* Release a bitmap (but not its head). This is suitable for pairing with
477 bitmap_initialize. */
478
479 inline void
480 bitmap_release (bitmap head)
481 {
482 bitmap_clear (head);
483 /* Poison the obstack pointer so the obstack can be safely released.
484 Do not zero it as the bitmap then becomes initialized GC. */
485 head->obstack = &bitmap_head::crashme;
486 }
487
488 /* Allocate and free bitmaps from obstack, malloc and gc'd memory. */
489 extern bitmap bitmap_alloc (bitmap_obstack *obstack CXX_MEM_STAT_INFO);
490 #define BITMAP_ALLOC bitmap_alloc
491 extern bitmap bitmap_gc_alloc (ALONE_CXX_MEM_STAT_INFO);
492 #define BITMAP_GGC_ALLOC bitmap_gc_alloc
493 extern void bitmap_obstack_free (bitmap);
494
495 /* A few compatibility/functions macros for compatibility with sbitmaps */
496 inline void dump_bitmap (FILE *file, const_bitmap map)
497 {
498 bitmap_print (file, map, "", "\n");
499 }
500 extern void debug (const bitmap_head &ref);
501 extern void debug (const bitmap_head *ptr);
502
503 extern unsigned bitmap_first_set_bit (const_bitmap);
504 extern unsigned bitmap_last_set_bit (const_bitmap);
505
506 /* Compute bitmap hash (for purposes of hashing etc.) */
507 extern hashval_t bitmap_hash (const_bitmap);
508
509 /* Do any cleanup needed on a bitmap when it is no longer used. */
510 #define BITMAP_FREE(BITMAP) \
511 ((void) (bitmap_obstack_free ((bitmap) BITMAP), (BITMAP) = (bitmap) NULL))
512
513 /* Iterator for bitmaps. */
514
515 struct bitmap_iterator
516 {
517 /* Pointer to the current bitmap element. */
518 bitmap_element *elt1;
519
520 /* Pointer to 2nd bitmap element when two are involved. */
521 bitmap_element *elt2;
522
523 /* Word within the current element. */
524 unsigned word_no;
525
526 /* Contents of the actually processed word. When finding next bit
527 it is shifted right, so that the actual bit is always the least
528 significant bit of ACTUAL. */
529 BITMAP_WORD bits;
530 };
531
532 /* Initialize a single bitmap iterator. START_BIT is the first bit to
533 iterate from. */
534
535 inline void
536 bmp_iter_set_init (bitmap_iterator *bi, const_bitmap map,
537 unsigned start_bit, unsigned *bit_no)
538 {
539 bi->elt1 = map->first;
540 bi->elt2 = NULL;
541
542 gcc_checking_assert (!map->tree_form);
543
544 /* Advance elt1 until it is not before the block containing start_bit. */
545 while (1)
546 {
547 if (!bi->elt1)
548 {
549 bi->elt1 = &bitmap_zero_bits;
550 break;
551 }
552
553 if (bi->elt1->indx >= start_bit / BITMAP_ELEMENT_ALL_BITS)
554 break;
555 bi->elt1 = bi->elt1->next;
556 }
557
558 /* We might have gone past the start bit, so reinitialize it. */
559 if (bi->elt1->indx != start_bit / BITMAP_ELEMENT_ALL_BITS)
560 start_bit = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
561
562 /* Initialize for what is now start_bit. */
563 bi->word_no = start_bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
564 bi->bits = bi->elt1->bits[bi->word_no];
565 bi->bits >>= start_bit % BITMAP_WORD_BITS;
566
567 /* If this word is zero, we must make sure we're not pointing at the
568 first bit, otherwise our incrementing to the next word boundary
569 will fail. It won't matter if this increment moves us into the
570 next word. */
571 start_bit += !bi->bits;
572
573 *bit_no = start_bit;
574 }
575
576 /* Initialize an iterator to iterate over the intersection of two
577 bitmaps. START_BIT is the bit to commence from. */
578
579 inline void
580 bmp_iter_and_init (bitmap_iterator *bi, const_bitmap map1, const_bitmap map2,
581 unsigned start_bit, unsigned *bit_no)
582 {
583 bi->elt1 = map1->first;
584 bi->elt2 = map2->first;
585
586 gcc_checking_assert (!map1->tree_form && !map2->tree_form);
587
588 /* Advance elt1 until it is not before the block containing
589 start_bit. */
590 while (1)
591 {
592 if (!bi->elt1)
593 {
594 bi->elt2 = NULL;
595 break;
596 }
597
598 if (bi->elt1->indx >= start_bit / BITMAP_ELEMENT_ALL_BITS)
599 break;
600 bi->elt1 = bi->elt1->next;
601 }
602
603 /* Advance elt2 until it is not before elt1. */
604 while (1)
605 {
606 if (!bi->elt2)
607 {
608 bi->elt1 = bi->elt2 = &bitmap_zero_bits;
609 break;
610 }
611
612 if (bi->elt2->indx >= bi->elt1->indx)
613 break;
614 bi->elt2 = bi->elt2->next;
615 }
616
617 /* If we're at the same index, then we have some intersecting bits. */
618 if (bi->elt1->indx == bi->elt2->indx)
619 {
620 /* We might have advanced beyond the start_bit, so reinitialize
621 for that. */
622 if (bi->elt1->indx != start_bit / BITMAP_ELEMENT_ALL_BITS)
623 start_bit = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
624
625 bi->word_no = start_bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
626 bi->bits = bi->elt1->bits[bi->word_no] & bi->elt2->bits[bi->word_no];
627 bi->bits >>= start_bit % BITMAP_WORD_BITS;
628 }
629 else
630 {
631 /* Otherwise we must immediately advance elt1, so initialize for
632 that. */
633 bi->word_no = BITMAP_ELEMENT_WORDS - 1;
634 bi->bits = 0;
635 }
636
637 /* If this word is zero, we must make sure we're not pointing at the
638 first bit, otherwise our incrementing to the next word boundary
639 will fail. It won't matter if this increment moves us into the
640 next word. */
641 start_bit += !bi->bits;
642
643 *bit_no = start_bit;
644 }
645
646 /* Initialize an iterator to iterate over the bits in MAP1 & ~MAP2. */
647
648 inline void
649 bmp_iter_and_compl_init (bitmap_iterator *bi,
650 const_bitmap map1, const_bitmap map2,
651 unsigned start_bit, unsigned *bit_no)
652 {
653 bi->elt1 = map1->first;
654 bi->elt2 = map2->first;
655
656 gcc_checking_assert (!map1->tree_form && !map2->tree_form);
657
658 /* Advance elt1 until it is not before the block containing start_bit. */
659 while (1)
660 {
661 if (!bi->elt1)
662 {
663 bi->elt1 = &bitmap_zero_bits;
664 break;
665 }
666
667 if (bi->elt1->indx >= start_bit / BITMAP_ELEMENT_ALL_BITS)
668 break;
669 bi->elt1 = bi->elt1->next;
670 }
671
672 /* Advance elt2 until it is not before elt1. */
673 while (bi->elt2 && bi->elt2->indx < bi->elt1->indx)
674 bi->elt2 = bi->elt2->next;
675
676 /* We might have advanced beyond the start_bit, so reinitialize for
677 that. */
678 if (bi->elt1->indx != start_bit / BITMAP_ELEMENT_ALL_BITS)
679 start_bit = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
680
681 bi->word_no = start_bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
682 bi->bits = bi->elt1->bits[bi->word_no];
683 if (bi->elt2 && bi->elt1->indx == bi->elt2->indx)
684 bi->bits &= ~bi->elt2->bits[bi->word_no];
685 bi->bits >>= start_bit % BITMAP_WORD_BITS;
686
687 /* If this word is zero, we must make sure we're not pointing at the
688 first bit, otherwise our incrementing to the next word boundary
689 will fail. It won't matter if this increment moves us into the
690 next word. */
691 start_bit += !bi->bits;
692
693 *bit_no = start_bit;
694 }
695
696 /* Advance to the next bit in BI. We don't advance to the next
697 nonzero bit yet. */
698
699 inline void
700 bmp_iter_next (bitmap_iterator *bi, unsigned *bit_no)
701 {
702 bi->bits >>= 1;
703 *bit_no += 1;
704 }
705
706 /* Advance to first set bit in BI. */
707
708 inline void
709 bmp_iter_next_bit (bitmap_iterator * bi, unsigned *bit_no)
710 {
711 #if (GCC_VERSION >= 3004)
712 {
713 unsigned int n = __builtin_ctzl (bi->bits);
714 gcc_assert (sizeof (unsigned long) == sizeof (BITMAP_WORD));
715 bi->bits >>= n;
716 *bit_no += n;
717 }
718 #else
719 while (!(bi->bits & 1))
720 {
721 bi->bits >>= 1;
722 *bit_no += 1;
723 }
724 #endif
725 }
726
727 /* Advance to the next nonzero bit of a single bitmap, we will have
728 already advanced past the just iterated bit. Return true if there
729 is a bit to iterate. */
730
731 inline bool
732 bmp_iter_set (bitmap_iterator *bi, unsigned *bit_no)
733 {
734 /* If our current word is nonzero, it contains the bit we want. */
735 if (bi->bits)
736 {
737 next_bit:
738 bmp_iter_next_bit (bi, bit_no);
739 return true;
740 }
741
742 /* Round up to the word boundary. We might have just iterated past
743 the end of the last word, hence the -1. It is not possible for
744 bit_no to point at the beginning of the now last word. */
745 *bit_no = ((*bit_no + BITMAP_WORD_BITS - 1)
746 / BITMAP_WORD_BITS * BITMAP_WORD_BITS);
747 bi->word_no++;
748
749 while (1)
750 {
751 /* Find the next nonzero word in this elt. */
752 while (bi->word_no != BITMAP_ELEMENT_WORDS)
753 {
754 bi->bits = bi->elt1->bits[bi->word_no];
755 if (bi->bits)
756 goto next_bit;
757 *bit_no += BITMAP_WORD_BITS;
758 bi->word_no++;
759 }
760
761 /* Make sure we didn't remove the element while iterating. */
762 gcc_checking_assert (bi->elt1->indx != -1U);
763
764 /* Advance to the next element. */
765 bi->elt1 = bi->elt1->next;
766 if (!bi->elt1)
767 return false;
768 *bit_no = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
769 bi->word_no = 0;
770 }
771 }
772
773 /* Advance to the next nonzero bit of an intersecting pair of
774 bitmaps. We will have already advanced past the just iterated bit.
775 Return true if there is a bit to iterate. */
776
777 inline bool
778 bmp_iter_and (bitmap_iterator *bi, unsigned *bit_no)
779 {
780 /* If our current word is nonzero, it contains the bit we want. */
781 if (bi->bits)
782 {
783 next_bit:
784 bmp_iter_next_bit (bi, bit_no);
785 return true;
786 }
787
788 /* Round up to the word boundary. We might have just iterated past
789 the end of the last word, hence the -1. It is not possible for
790 bit_no to point at the beginning of the now last word. */
791 *bit_no = ((*bit_no + BITMAP_WORD_BITS - 1)
792 / BITMAP_WORD_BITS * BITMAP_WORD_BITS);
793 bi->word_no++;
794
795 while (1)
796 {
797 /* Find the next nonzero word in this elt. */
798 while (bi->word_no != BITMAP_ELEMENT_WORDS)
799 {
800 bi->bits = bi->elt1->bits[bi->word_no] & bi->elt2->bits[bi->word_no];
801 if (bi->bits)
802 goto next_bit;
803 *bit_no += BITMAP_WORD_BITS;
804 bi->word_no++;
805 }
806
807 /* Advance to the next identical element. */
808 do
809 {
810 /* Make sure we didn't remove the element while iterating. */
811 gcc_checking_assert (bi->elt1->indx != -1U);
812
813 /* Advance elt1 while it is less than elt2. We always want
814 to advance one elt. */
815 do
816 {
817 bi->elt1 = bi->elt1->next;
818 if (!bi->elt1)
819 return false;
820 }
821 while (bi->elt1->indx < bi->elt2->indx);
822
823 /* Make sure we didn't remove the element while iterating. */
824 gcc_checking_assert (bi->elt2->indx != -1U);
825
826 /* Advance elt2 to be no less than elt1. This might not
827 advance. */
828 while (bi->elt2->indx < bi->elt1->indx)
829 {
830 bi->elt2 = bi->elt2->next;
831 if (!bi->elt2)
832 return false;
833 }
834 }
835 while (bi->elt1->indx != bi->elt2->indx);
836
837 *bit_no = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
838 bi->word_no = 0;
839 }
840 }
841
842 /* Advance to the next nonzero bit in the intersection of
843 complemented bitmaps. We will have already advanced past the just
844 iterated bit. */
845
846 inline bool
847 bmp_iter_and_compl (bitmap_iterator *bi, unsigned *bit_no)
848 {
849 /* If our current word is nonzero, it contains the bit we want. */
850 if (bi->bits)
851 {
852 next_bit:
853 bmp_iter_next_bit (bi, bit_no);
854 return true;
855 }
856
857 /* Round up to the word boundary. We might have just iterated past
858 the end of the last word, hence the -1. It is not possible for
859 bit_no to point at the beginning of the now last word. */
860 *bit_no = ((*bit_no + BITMAP_WORD_BITS - 1)
861 / BITMAP_WORD_BITS * BITMAP_WORD_BITS);
862 bi->word_no++;
863
864 while (1)
865 {
866 /* Find the next nonzero word in this elt. */
867 while (bi->word_no != BITMAP_ELEMENT_WORDS)
868 {
869 bi->bits = bi->elt1->bits[bi->word_no];
870 if (bi->elt2 && bi->elt2->indx == bi->elt1->indx)
871 bi->bits &= ~bi->elt2->bits[bi->word_no];
872 if (bi->bits)
873 goto next_bit;
874 *bit_no += BITMAP_WORD_BITS;
875 bi->word_no++;
876 }
877
878 /* Make sure we didn't remove the element while iterating. */
879 gcc_checking_assert (bi->elt1->indx != -1U);
880
881 /* Advance to the next element of elt1. */
882 bi->elt1 = bi->elt1->next;
883 if (!bi->elt1)
884 return false;
885
886 /* Make sure we didn't remove the element while iterating. */
887 gcc_checking_assert (! bi->elt2 || bi->elt2->indx != -1U);
888
889 /* Advance elt2 until it is no less than elt1. */
890 while (bi->elt2 && bi->elt2->indx < bi->elt1->indx)
891 bi->elt2 = bi->elt2->next;
892
893 *bit_no = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
894 bi->word_no = 0;
895 }
896 }
897
898 /* If you are modifying a bitmap you are currently iterating over you
899 have to ensure to
900 - never remove the current bit;
901 - if you set or clear a bit before the current bit this operation
902 will not affect the set of bits you are visiting during the iteration;
903 - if you set or clear a bit after the current bit it is unspecified
904 whether that affects the set of bits you are visiting during the
905 iteration.
906 If you want to remove the current bit you can delay this to the next
907 iteration (and after the iteration in case the last iteration is
908 affected). */
909
910 /* Loop over all bits set in BITMAP, starting with MIN and setting
911 BITNUM to the bit number. ITER is a bitmap iterator. BITNUM
912 should be treated as a read-only variable as it contains loop
913 state. */
914
915 #ifndef EXECUTE_IF_SET_IN_BITMAP
916 /* See sbitmap.h for the other definition of EXECUTE_IF_SET_IN_BITMAP. */
917 #define EXECUTE_IF_SET_IN_BITMAP(BITMAP, MIN, BITNUM, ITER) \
918 for (bmp_iter_set_init (&(ITER), (BITMAP), (MIN), &(BITNUM)); \
919 bmp_iter_set (&(ITER), &(BITNUM)); \
920 bmp_iter_next (&(ITER), &(BITNUM)))
921 #endif
922
923 /* Loop over all the bits set in BITMAP1 & BITMAP2, starting with MIN
924 and setting BITNUM to the bit number. ITER is a bitmap iterator.
925 BITNUM should be treated as a read-only variable as it contains
926 loop state. */
927
928 #define EXECUTE_IF_AND_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, ITER) \
929 for (bmp_iter_and_init (&(ITER), (BITMAP1), (BITMAP2), (MIN), \
930 &(BITNUM)); \
931 bmp_iter_and (&(ITER), &(BITNUM)); \
932 bmp_iter_next (&(ITER), &(BITNUM)))
933
934 /* Loop over all the bits set in BITMAP1 & ~BITMAP2, starting with MIN
935 and setting BITNUM to the bit number. ITER is a bitmap iterator.
936 BITNUM should be treated as a read-only variable as it contains
937 loop state. */
938
939 #define EXECUTE_IF_AND_COMPL_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, ITER) \
940 for (bmp_iter_and_compl_init (&(ITER), (BITMAP1), (BITMAP2), (MIN), \
941 &(BITNUM)); \
942 bmp_iter_and_compl (&(ITER), &(BITNUM)); \
943 bmp_iter_next (&(ITER), &(BITNUM)))
944
945 /* A class that ties the lifetime of a bitmap to its scope. */
946 class auto_bitmap
947 {
948 public:
949 auto_bitmap (ALONE_CXX_MEM_STAT_INFO)
950 { bitmap_initialize (&m_bits, &bitmap_default_obstack PASS_MEM_STAT); }
951 explicit auto_bitmap (bitmap_obstack *o CXX_MEM_STAT_INFO)
952 { bitmap_initialize (&m_bits, o PASS_MEM_STAT); }
953 ~auto_bitmap () { bitmap_clear (&m_bits); }
954 // Allow calling bitmap functions on our bitmap.
955 operator bitmap () { return &m_bits; }
956
957 private:
958 // Prevent making a copy that references our bitmap.
959 auto_bitmap (const auto_bitmap &);
960 auto_bitmap &operator = (const auto_bitmap &);
961 auto_bitmap (auto_bitmap &&);
962 auto_bitmap &operator = (auto_bitmap &&);
963
964 bitmap_head m_bits;
965 };
966
967 extern void debug (const auto_bitmap &ref);
968 extern void debug (const auto_bitmap *ptr);
969
970 /* Base class for bitmap_view; see there for details. */
971 template<typename T, typename Traits = array_traits<T> >
972 class base_bitmap_view
973 {
974 public:
975 typedef typename Traits::element_type array_element_type;
976
977 base_bitmap_view (const T &, bitmap_element *);
978 operator const_bitmap () const { return &m_head; }
979
980 private:
981 base_bitmap_view (const base_bitmap_view &);
982
983 bitmap_head m_head;
984 };
985
986 /* Provides a read-only bitmap view of a single integer bitmask or a
987 constant-sized array of integer bitmasks, or of a wrapper around such
988 bitmasks. */
989 template<typename T, typename Traits>
990 class bitmap_view<T, Traits, true> : public base_bitmap_view<T, Traits>
991 {
992 public:
993 bitmap_view (const T &array)
994 : base_bitmap_view<T, Traits> (array, m_bitmap_elements) {}
995
996 private:
997 /* How many bitmap_elements we need to hold a full T. */
998 static const size_t num_bitmap_elements
999 = CEIL (CHAR_BIT
1000 * sizeof (typename Traits::element_type)
1001 * Traits::constant_size,
1002 BITMAP_ELEMENT_ALL_BITS);
1003 bitmap_element m_bitmap_elements[num_bitmap_elements];
1004 };
1005
1006 /* Initialize the view for array ARRAY, using the array of bitmap
1007 elements in BITMAP_ELEMENTS (which is known to contain enough
1008 entries). */
1009 template<typename T, typename Traits>
1010 base_bitmap_view<T, Traits>::base_bitmap_view (const T &array,
1011 bitmap_element *bitmap_elements)
1012 {
1013 m_head.obstack = NULL;
1014
1015 /* The code currently assumes that each element of ARRAY corresponds
1016 to exactly one bitmap_element. */
1017 const size_t array_element_bits = CHAR_BIT * sizeof (array_element_type);
1018 STATIC_ASSERT (BITMAP_ELEMENT_ALL_BITS % array_element_bits == 0);
1019 size_t array_step = BITMAP_ELEMENT_ALL_BITS / array_element_bits;
1020 size_t array_size = Traits::size (array);
1021
1022 /* Process each potential bitmap_element in turn. The loop is written
1023 this way rather than per array element because usually there are
1024 only a small number of array elements per bitmap element (typically
1025 two or four). The inner loops should therefore unroll completely. */
1026 const array_element_type *array_elements = Traits::base (array);
1027 unsigned int indx = 0;
1028 for (size_t array_base = 0;
1029 array_base < array_size;
1030 array_base += array_step, indx += 1)
1031 {
1032 /* How many array elements are in this particular bitmap_element. */
1033 unsigned int array_count
1034 = (STATIC_CONSTANT_P (array_size % array_step == 0)
1035 ? array_step : MIN (array_step, array_size - array_base));
1036
1037 /* See whether we need this bitmap element. */
1038 array_element_type ior = array_elements[array_base];
1039 for (size_t i = 1; i < array_count; ++i)
1040 ior |= array_elements[array_base + i];
1041 if (ior == 0)
1042 continue;
1043
1044 /* Grab the next bitmap element and chain it. */
1045 bitmap_element *bitmap_element = bitmap_elements++;
1046 if (m_head.current)
1047 m_head.current->next = bitmap_element;
1048 else
1049 m_head.first = bitmap_element;
1050 bitmap_element->prev = m_head.current;
1051 bitmap_element->next = NULL;
1052 bitmap_element->indx = indx;
1053 m_head.current = bitmap_element;
1054 m_head.indx = indx;
1055
1056 /* Fill in the bits of the bitmap element. */
1057 if (array_element_bits < BITMAP_WORD_BITS)
1058 {
1059 /* Multiple array elements fit in one element of
1060 bitmap_element->bits. */
1061 size_t array_i = array_base;
1062 for (unsigned int word_i = 0; word_i < BITMAP_ELEMENT_WORDS;
1063 ++word_i)
1064 {
1065 BITMAP_WORD word = 0;
1066 for (unsigned int shift = 0;
1067 shift < BITMAP_WORD_BITS && array_i < array_size;
1068 shift += array_element_bits)
1069 word |= array_elements[array_i++] << shift;
1070 bitmap_element->bits[word_i] = word;
1071 }
1072 }
1073 else
1074 {
1075 /* Array elements are the same size as elements of
1076 bitmap_element->bits, or are an exact multiple of that size. */
1077 unsigned int word_i = 0;
1078 for (unsigned int i = 0; i < array_count; ++i)
1079 for (unsigned int shift = 0; shift < array_element_bits;
1080 shift += BITMAP_WORD_BITS)
1081 bitmap_element->bits[word_i++]
1082 = array_elements[array_base + i] >> shift;
1083 while (word_i < BITMAP_ELEMENT_WORDS)
1084 bitmap_element->bits[word_i++] = 0;
1085 }
1086 }
1087 }
1088
1089 #endif /* GCC_BITMAP_H */