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 | * 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. */ |
218 | class bitmap_usage: public mem_usage |
219 | { |
220 | public: |
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 | (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. */ |
274 | extern mem_alloc_description<bitmap_usage> bitmap_mem_desc; |
275 | |
276 | /* Fundamental storage type for bitmap. */ |
277 | |
278 | typedef 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. */ |
294 | struct 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 | |
312 | struct 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 | |
328 | class GTY(()) bitmap_head { |
329 | public: |
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 */ |
366 | extern bitmap_element bitmap_zero_bits; /* Zero bitmap element */ |
367 | extern bitmap_obstack bitmap_default_obstack; /* Default bitmap obstack */ |
368 | |
369 | /* Change the view of the bitmap to list, or tree. */ |
370 | void bitmap_list_view (bitmap); |
371 | void bitmap_tree_view (bitmap); |
372 | |
373 | /* Clear a bitmap by freeing up the linked list. */ |
374 | extern void bitmap_clear (bitmap); |
375 | |
376 | /* Copy a bitmap to another bitmap. */ |
377 | extern void bitmap_copy (bitmap, const_bitmap); |
378 | |
379 | /* Move a bitmap to another bitmap. */ |
380 | extern void bitmap_move (bitmap, bitmap); |
381 | |
382 | /* True if two bitmaps are identical. */ |
383 | extern bool bitmap_equal_p (const_bitmap, const_bitmap); |
384 | |
385 | /* True if the bitmaps intersect (their AND is non-empty). */ |
386 | extern 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). */ |
390 | extern bool bitmap_intersect_compl_p (const_bitmap, const_bitmap); |
391 | |
392 | /* True if MAP is an empty bitmap. */ |
393 | inline 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. */ |
399 | extern bool bitmap_single_bit_set_p (const_bitmap); |
400 | |
401 | /* Count the number of bits set in the bitmap. */ |
402 | extern unsigned long bitmap_count_bits (const_bitmap); |
403 | |
404 | /* Count the number of unique bits set across the two bitmaps. */ |
405 | extern 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 &, & ~, |, ^. */ |
411 | extern void bitmap_and (bitmap, const_bitmap, const_bitmap); |
412 | extern bool bitmap_and_into (bitmap, const_bitmap); |
413 | extern bool bitmap_and_compl (bitmap, const_bitmap, const_bitmap); |
414 | extern bool bitmap_and_compl_into (bitmap, const_bitmap); |
415 | #define bitmap_compl_and(DST, A, B) bitmap_and_compl (DST, B, A) |
416 | extern void bitmap_compl_and_into (bitmap, const_bitmap); |
417 | extern void bitmap_clear_range (bitmap, unsigned int, unsigned int); |
418 | extern void bitmap_set_range (bitmap, unsigned int, unsigned int); |
419 | extern bool bitmap_ior (bitmap, const_bitmap, const_bitmap); |
420 | extern bool bitmap_ior_into (bitmap, const_bitmap); |
421 | extern bool bitmap_ior_into_and_free (bitmap, bitmap *); |
422 | extern void bitmap_xor (bitmap, const_bitmap, const_bitmap); |
423 | extern void bitmap_xor_into (bitmap, const_bitmap); |
424 | |
425 | /* DST = A | (B & C). Return true if DST changes. */ |
426 | extern bool bitmap_ior_and_into (bitmap DST, const_bitmap B, const_bitmap C); |
427 | /* DST = A | (B & ~C). Return true if DST changes. */ |
428 | extern 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. */ |
431 | extern 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. */ |
435 | extern bool bitmap_clear_bit (bitmap, int); |
436 | |
437 | /* Set a single bit in a bitmap. Return true if the bit changed. */ |
438 | extern bool bitmap_set_bit (bitmap, int); |
439 | |
440 | /* Return true if a bit is set in a bitmap. */ |
441 | extern 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. */ |
447 | void bitmap_set_aligned_chunk (bitmap, unsigned int, unsigned int, BITMAP_WORD); |
448 | BITMAP_WORD bitmap_get_aligned_chunk (const_bitmap, unsigned int, unsigned int); |
449 | |
450 | /* Debug functions to print a bitmap. */ |
451 | extern void debug_bitmap (const_bitmap); |
452 | extern void debug_bitmap_file (FILE *, const_bitmap); |
453 | |
454 | /* Print a bitmap. */ |
455 | extern void bitmap_print (FILE *, const_bitmap, const char *, const char *); |
456 | |
457 | /* Initialize and release a bitmap obstack. */ |
458 | extern void bitmap_obstack_initialize (bitmap_obstack *); |
459 | extern void bitmap_obstack_release (bitmap_obstack *); |
460 | extern void bitmap_register (bitmap MEM_STAT_DECL); |
461 | extern 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 | |
466 | inline void |
467 | bitmap_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 | |
481 | inline void |
482 | bitmap_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. */ |
491 | extern bitmap bitmap_alloc (bitmap_obstack *obstack CXX_MEM_STAT_INFO); |
492 | #define BITMAP_ALLOC bitmap_alloc |
493 | extern bitmap bitmap_gc_alloc (ALONE_CXX_MEM_STAT_INFO); |
494 | #define BITMAP_GGC_ALLOC bitmap_gc_alloc |
495 | extern void bitmap_obstack_free (bitmap); |
496 | |
497 | /* A few compatibility/functions macros for compatibility with sbitmaps */ |
498 | inline void dump_bitmap (FILE *file, const_bitmap map) |
499 | { |
500 | bitmap_print (file, map, "" , "\n" ); |
501 | } |
502 | extern void debug (const bitmap_head &ref); |
503 | extern void debug (const bitmap_head *ptr); |
504 | |
505 | extern unsigned bitmap_first_set_bit (const_bitmap); |
506 | extern unsigned bitmap_clear_first_set_bit (bitmap); |
507 | extern unsigned bitmap_last_set_bit (const_bitmap); |
508 | |
509 | /* Compute bitmap hash (for purposes of hashing etc.) */ |
510 | extern 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 | |
518 | struct 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 | |
538 | inline void |
539 | bmp_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 | |
582 | inline void |
583 | bmp_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 | |
651 | inline void |
652 | bmp_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 | |
702 | inline void |
703 | bmp_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 | |
711 | inline void |
712 | bmp_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 | |
734 | inline bool |
735 | bmp_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 | |
780 | inline bool |
781 | bmp_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 | |
849 | inline bool |
850 | bmp_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. */ |
949 | class 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 | |
970 | extern void debug (const auto_bitmap &ref); |
971 | extern void debug (const auto_bitmap *ptr); |
972 | |
973 | /* Base class for bitmap_view; see there for details. */ |
974 | template<typename T, typename Traits = array_traits<T> > |
975 | class base_bitmap_view |
976 | { |
977 | public: |
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 | |
983 | private: |
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. */ |
992 | template<typename T, typename Traits> |
993 | class bitmap_view<T, Traits, true> : public base_bitmap_view<T, Traits> |
994 | { |
995 | public: |
996 | bitmap_view (const T &array) |
997 | : base_bitmap_view<T, Traits> (array, m_bitmap_elements) {} |
998 | |
999 | private: |
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). */ |
1012 | template<typename T, typename Traits> |
1013 | base_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 | |