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