1/* Functions to support general ended bitmaps. 2 Copyright (C) 1997-2020 Free Software Foundation, Inc. 3 4This file is part of GCC. 5 6GCC is free software; you can redistribute it and/or modify it under 7the terms of the GNU General Public License as published by the Free 8Software Foundation; either version 3, or (at your option) any later 9version. 10 11GCC is distributed in the hope that it will be useful, but WITHOUT ANY 12WARRANTY; without even the implied warranty of MERCHANTABILITY or 13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14for more details. 15 16You should have received a copy of the GNU General Public License 17along with GCC; see the file COPYING3. If not see 18<http://www.gnu.org/licenses/>. */ 19 20#ifndef GCC_BITMAP_H 21#define GCC_BITMAP_H 22 23/* Implementation of sparse integer sets as a linked list or tree. 24 25 This sparse set representation is suitable for sparse sets with an 26 unknown (a priori) universe. 27 28 Sets are represented as double-linked lists of container nodes of 29 type "struct bitmap_element" or as a binary trees of the same 30 container nodes. Each container node consists of an index for the 31 first member that could be held in the container, a small array of 32 integers that represent the members in the container, and pointers 33 to the next and previous element in the linked list, or left and 34 right children in the tree. In linked-list form, the container 35 nodes in the list are sorted in ascending order, i.e. the head of 36 the list holds the element with the smallest member of the set. 37 In tree form, nodes to the left have a smaller container index. 38 39 For a given member I in the set: 40 - the element for I will have index is I / (bits per element) 41 - the position for I within element is I % (bits per element) 42 43 This representation is very space-efficient for large sparse sets, and 44 the size of the set can be changed dynamically without much overhead. 45 An important parameter is the number of bits per element. In this 46 implementation, there are 128 bits per element. This results in a 47 high storage overhead *per element*, but a small overall overhead if 48 the set is very sparse. 49 50 The storage requirements for linked-list sparse sets are O(E), with E->N 51 in the worst case (a sparse set with large distances between the values 52 of the set members). 53 54 This representation also works well for data flow problems where the size 55 of the set may grow dynamically, but care must be taken that the member_p, 56 add_member, and remove_member operations occur with a suitable access 57 pattern. 58 59 The linked-list set representation works well for problems involving very 60 sparse sets. The canonical example in GCC is, of course, the "set of 61 sets" for some CFG-based data flow problems (liveness analysis, dominance 62 frontiers, etc.). 63 64 For random-access sparse sets of unknown universe, the binary tree 65 representation is likely to be a more suitable choice. Theoretical 66 access times for the binary tree representation are better than those 67 for the linked-list, but in practice this is only true for truely 68 random access. 69 70 Often the most suitable representation during construction of the set 71 is not the best choice for the usage of the set. For such cases, the 72 "view" of the set can be changed from one representation to the other. 73 This is an O(E) operation: 74 75 * from list to tree view : bitmap_tree_view 76 * from tree to list view : bitmap_list_view 77 78 Traversing linked lists or trees can be cache-unfriendly. Performance 79 can be improved by keeping container nodes in the set grouped together 80 in memory, using a dedicated obstack for a set (or group of related 81 sets). Elements allocated on obstacks are released to a free-list and 82 taken off the free list. If multiple sets are allocated on the same 83 obstack, elements freed from one set may be re-used for one of the other 84 sets. This usually helps avoid cache misses. 85 86 A single free-list is used for all sets allocated in GGC space. This is 87 bad for persistent sets, so persistent sets should be allocated on an 88 obstack whenever possible. 89 90 For random-access sets with a known, relatively small universe size, the 91 SparseSet or simple bitmap representations may be more efficient than a 92 linked-list set. 93 94 95 LINKED LIST FORM 96 ================ 97 98 In linked-list form, in-order iterations of the set can be executed 99 efficiently. The downside is that many random-access operations are 100 relatively slow, because the linked list has to be traversed to test 101 membership (i.e. member_p/ add_member/remove_member). 102 103 To improve the performance of this set representation, the last 104 accessed element and its index are cached. For membership tests on 105 members close to recently accessed members, the cached last element 106 improves membership test to a constant-time operation. 107 108 The following operations can always be performed in O(1) time in 109 list view: 110 111 * clear : bitmap_clear 112 * smallest_member : bitmap_first_set_bit 113 * 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. */ 216class bitmap_usage: public mem_usage 217{ 218public: 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, 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. */ 272extern mem_alloc_description<bitmap_usage> bitmap_mem_desc; 273 274/* Fundamental storage type for bitmap. */ 275 276typedef 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. */ 292struct 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 310struct 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 326class GTY(()) bitmap_head { 327public: 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 */ 364extern bitmap_element bitmap_zero_bits; /* Zero bitmap element */ 365extern bitmap_obstack bitmap_default_obstack; /* Default bitmap obstack */ 366 367/* Change the view of the bitmap to list, or tree. */ 368void bitmap_list_view (bitmap); 369void bitmap_tree_view (bitmap); 370 371/* Clear a bitmap by freeing up the linked list. */ 372extern void bitmap_clear (bitmap); 373 374/* Copy a bitmap to another bitmap. */ 375extern void bitmap_copy (bitmap, const_bitmap); 376 377/* Move a bitmap to another bitmap. */ 378extern void bitmap_move (bitmap, bitmap); 379 380/* True if two bitmaps are identical. */ 381extern bool bitmap_equal_p (const_bitmap, const_bitmap); 382 383/* True if the bitmaps intersect (their AND is non-empty). */ 384extern 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). */ 388extern bool bitmap_intersect_compl_p (const_bitmap, const_bitmap); 389 390/* True if MAP is an empty bitmap. */ 391inline 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. */ 397extern bool bitmap_single_bit_set_p (const_bitmap); 398 399/* Count the number of bits set in the bitmap. */ 400extern unsigned long bitmap_count_bits (const_bitmap); 401 402/* Count the number of unique bits set across the two bitmaps. */ 403extern 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 &, & ~, |, ^. */ 409extern void bitmap_and (bitmap, const_bitmap, const_bitmap); 410extern bool bitmap_and_into (bitmap, const_bitmap); 411extern bool bitmap_and_compl (bitmap, const_bitmap, const_bitmap); 412extern bool bitmap_and_compl_into (bitmap, const_bitmap); 413#define bitmap_compl_and(DST, A, B) bitmap_and_compl (DST, B, A) 414extern void bitmap_compl_and_into (bitmap, const_bitmap); 415extern void bitmap_clear_range (bitmap, unsigned int, unsigned int); 416extern void bitmap_set_range (bitmap, unsigned int, unsigned int); 417extern bool bitmap_ior (bitmap, const_bitmap, const_bitmap); 418extern bool bitmap_ior_into (bitmap, const_bitmap); 419extern bool bitmap_ior_into_and_free (bitmap, bitmap *); 420extern void bitmap_xor (bitmap, const_bitmap, const_bitmap); 421extern void bitmap_xor_into (bitmap, const_bitmap); 422 423/* DST = A | (B & C). Return true if DST changes. */ 424extern bool bitmap_ior_and_into (bitmap DST, const_bitmap B, const_bitmap C); 425/* DST = A | (B & ~C). Return true if DST changes. */ 426extern 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. */ 429extern 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. */ 433extern bool bitmap_clear_bit (bitmap, int); 434 435/* Set a single bit in a bitmap. Return true if the bit changed. */ 436extern bool bitmap_set_bit (bitmap, int); 437 438/* Return true if a bit is set in a bitmap. */ 439extern int bitmap_bit_p (const_bitmap, int); 440 441/* Debug functions to print a bitmap. */ 442extern void debug_bitmap (const_bitmap); 443extern void debug_bitmap_file (FILE *, const_bitmap); 444 445/* Print a bitmap. */ 446extern void bitmap_print (FILE *, const_bitmap, const char *, const char *); 447 448/* Initialize and release a bitmap obstack. */ 449extern void bitmap_obstack_initialize (bitmap_obstack *); 450extern void bitmap_obstack_release (bitmap_obstack *); 451extern void bitmap_register (bitmap MEM_STAT_DECL); 452extern void dump_bitmap_statistics (void); 453 454/* Initialize a bitmap header. OBSTACK indicates the bitmap obstack 455 to allocate from, NULL for GC'd bitmap. */ 456 457static inline void 458bitmap_initialize (bitmap head, bitmap_obstack *obstack CXX_MEM_STAT_INFO) 459{ 460 head->first = head->current = NULL; 461 head->indx = head->tree_form = 0; 462 head->padding = 0; 463 head->alloc_descriptor = 0; 464 head->obstack = obstack; 465 if (GATHER_STATISTICS) 466 bitmap_register (head PASS_MEM_STAT); 467} 468 469/* Release a bitmap (but not its head). This is suitable for pairing with 470 bitmap_initialize. */ 471 472static inline void 473bitmap_release (bitmap head) 474{ 475 bitmap_clear (head); 476 /* Poison the obstack pointer so the obstack can be safely released. 477 Do not zero it as the bitmap then becomes initialized GC. */ 478 head->obstack = &bitmap_head::crashme; 479} 480 481/* Allocate and free bitmaps from obstack, malloc and gc'd memory. */ 482extern bitmap bitmap_alloc (bitmap_obstack *obstack CXX_MEM_STAT_INFO); 483#define BITMAP_ALLOC bitmap_alloc 484extern bitmap bitmap_gc_alloc (ALONE_CXX_MEM_STAT_INFO); 485#define BITMAP_GGC_ALLOC bitmap_gc_alloc 486extern void bitmap_obstack_free (bitmap); 487 488/* A few compatibility/functions macros for compatibility with sbitmaps */ 489inline void dump_bitmap (FILE *file, const_bitmap map) 490{ 491 bitmap_print (file, map, "", "\n"); 492} 493extern void debug (const bitmap_head &ref); 494extern void debug (const bitmap_head *ptr); 495 496extern unsigned bitmap_first_set_bit (const_bitmap); 497extern unsigned bitmap_last_set_bit (const_bitmap); 498 499/* Compute bitmap hash (for purposes of hashing etc.) */ 500extern hashval_t bitmap_hash (const_bitmap); 501 502/* Do any cleanup needed on a bitmap when it is no longer used. */ 503#define BITMAP_FREE(BITMAP) \ 504 ((void) (bitmap_obstack_free ((bitmap) BITMAP), (BITMAP) = (bitmap) NULL)) 505 506/* Iterator for bitmaps. */ 507 508struct bitmap_iterator 509{ 510 /* Pointer to the current bitmap element. */ 511 bitmap_element *elt1; 512 513 /* Pointer to 2nd bitmap element when two are involved. */ 514 bitmap_element *elt2; 515 516 /* Word within the current element. */ 517 unsigned word_no; 518 519 /* Contents of the actually processed word. When finding next bit 520 it is shifted right, so that the actual bit is always the least 521 significant bit of ACTUAL. */ 522 BITMAP_WORD bits; 523}; 524 525/* Initialize a single bitmap iterator. START_BIT is the first bit to 526 iterate from. */ 527 528static inline void 529bmp_iter_set_init (bitmap_iterator *bi, const_bitmap map, 530 unsigned start_bit, unsigned *bit_no) 531{ 532 bi->elt1 = map->first; 533 bi->elt2 = NULL; 534 535 gcc_checking_assert (!map->tree_form); 536 537 /* Advance elt1 until it is not before the block containing start_bit. */ 538 while (1) 539 { 540 if (!bi->elt1) 541 { 542 bi->elt1 = &bitmap_zero_bits; 543 break; 544 } 545 546 if (bi->elt1->indx >= start_bit / BITMAP_ELEMENT_ALL_BITS) 547 break; 548 bi->elt1 = bi->elt1->next; 549 } 550 551 /* We might have gone past the start bit, so reinitialize it. */ 552 if (bi->elt1->indx != start_bit / BITMAP_ELEMENT_ALL_BITS) 553 start_bit = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS; 554 555 /* Initialize for what is now start_bit. */ 556 bi->word_no = start_bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS; 557 bi->bits = bi->elt1->bits[bi->word_no]; 558 bi->bits >>= start_bit % BITMAP_WORD_BITS; 559 560 /* If this word is zero, we must make sure we're not pointing at the 561 first bit, otherwise our incrementing to the next word boundary 562 will fail. It won't matter if this increment moves us into the 563 next word. */ 564 start_bit += !bi->bits; 565 566 *bit_no = start_bit; 567} 568 569/* Initialize an iterator to iterate over the intersection of two 570 bitmaps. START_BIT is the bit to commence from. */ 571 572static inline void 573bmp_iter_and_init (bitmap_iterator *bi, const_bitmap map1, const_bitmap map2, 574 unsigned start_bit, unsigned *bit_no) 575{ 576 bi->elt1 = map1->first; 577 bi->elt2 = map2->first; 578 579 gcc_checking_assert (!map1->tree_form && !map2->tree_form); 580 581 /* Advance elt1 until it is not before the block containing 582 start_bit. */ 583 while (1) 584 { 585 if (!bi->elt1) 586 { 587 bi->elt2 = NULL; 588 break; 589 } 590 591 if (bi->elt1->indx >= start_bit / BITMAP_ELEMENT_ALL_BITS) 592 break; 593 bi->elt1 = bi->elt1->next; 594 } 595 596 /* Advance elt2 until it is not before elt1. */ 597 while (1) 598 { 599 if (!bi->elt2) 600 { 601 bi->elt1 = bi->elt2 = &bitmap_zero_bits; 602 break; 603 } 604 605 if (bi->elt2->indx >= bi->elt1->indx) 606 break; 607 bi->elt2 = bi->elt2->next; 608 } 609 610 /* If we're at the same index, then we have some intersecting bits. */ 611 if (bi->elt1->indx == bi->elt2->indx) 612 { 613 /* We might have advanced beyond the start_bit, so reinitialize 614 for that. */ 615 if (bi->elt1->indx != start_bit / BITMAP_ELEMENT_ALL_BITS) 616 start_bit = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS; 617 618 bi->word_no = start_bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS; 619 bi->bits = bi->elt1->bits[bi->word_no] & bi->elt2->bits[bi->word_no]; 620 bi->bits >>= start_bit % BITMAP_WORD_BITS; 621 } 622 else 623 { 624 /* Otherwise we must immediately advance elt1, so initialize for 625 that. */ 626 bi->word_no = BITMAP_ELEMENT_WORDS - 1; 627 bi->bits = 0; 628 } 629 630 /* If this word is zero, we must make sure we're not pointing at the 631 first bit, otherwise our incrementing to the next word boundary 632 will fail. It won't matter if this increment moves us into the 633 next word. */ 634 start_bit += !bi->bits; 635 636 *bit_no = start_bit; 637} 638 639/* Initialize an iterator to iterate over the bits in MAP1 & ~MAP2. */ 640 641static inline void 642bmp_iter_and_compl_init (bitmap_iterator *bi, 643 const_bitmap map1, const_bitmap map2, 644 unsigned start_bit, unsigned *bit_no) 645{ 646 bi->elt1 = map1->first; 647 bi->elt2 = map2->first; 648 649 gcc_checking_assert (!map1->tree_form && !map2->tree_form); 650 651 /* Advance elt1 until it is not before the block containing start_bit. */ 652 while (1) 653 { 654 if (!bi->elt1) 655 { 656 bi->elt1 = &bitmap_zero_bits; 657 break; 658 } 659 660 if (bi->elt1->indx >= start_bit / BITMAP_ELEMENT_ALL_BITS) 661 break; 662 bi->elt1 = bi->elt1->next; 663 } 664 665 /* Advance elt2 until it is not before elt1. */ 666 while (bi->elt2 && bi->elt2->indx < bi->elt1->indx) 667 bi->elt2 = bi->elt2->next; 668 669 /* We might have advanced beyond the start_bit, so reinitialize for 670 that. */ 671 if (bi->elt1->indx != start_bit / BITMAP_ELEMENT_ALL_BITS) 672 start_bit = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS; 673 674 bi->word_no = start_bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS; 675 bi->bits = bi->elt1->bits[bi->word_no]; 676 if (bi->elt2 && bi->elt1->indx == bi->elt2->indx) 677 bi->bits &= ~bi->elt2->bits[bi->word_no]; 678 bi->bits >>= start_bit % BITMAP_WORD_BITS; 679 680 /* If this word is zero, we must make sure we're not pointing at the 681 first bit, otherwise our incrementing to the next word boundary 682 will fail. It won't matter if this increment moves us into the 683 next word. */ 684 start_bit += !bi->bits; 685 686 *bit_no = start_bit; 687} 688 689/* Advance to the next bit in BI. We don't advance to the next 690 nonzero bit yet. */ 691 692static inline void 693bmp_iter_next (bitmap_iterator *bi, unsigned *bit_no) 694{ 695 bi->bits >>= 1; 696 *bit_no += 1; 697} 698 699/* Advance to first set bit in BI. */ 700 701static inline void 702bmp_iter_next_bit (bitmap_iterator * bi, unsigned *bit_no) 703{ 704#if (GCC_VERSION >= 3004) 705 { 706 unsigned int n = __builtin_ctzl (bi->bits); 707 gcc_assert (sizeof (unsigned long) == sizeof (BITMAP_WORD)); 708 bi->bits >>= n; 709 *bit_no += n; 710 } 711#else 712 while (!(bi->bits & 1)) 713 { 714 bi->bits >>= 1; 715 *bit_no += 1; 716 } 717#endif 718} 719 720/* Advance to the next nonzero bit of a single bitmap, we will have 721 already advanced past the just iterated bit. Return true if there 722 is a bit to iterate. */ 723 724static inline bool 725bmp_iter_set (bitmap_iterator *bi, unsigned *bit_no) 726{ 727 /* If our current word is nonzero, it contains the bit we want. */ 728 if (bi->bits) 729 { 730 next_bit: 731 bmp_iter_next_bit (bi, bit_no); 732 return true; 733 } 734 735 /* Round up to the word boundary. We might have just iterated past 736 the end of the last word, hence the -1. It is not possible for 737 bit_no to point at the beginning of the now last word. */ 738 *bit_no = ((*bit_no + BITMAP_WORD_BITS - 1) 739 / BITMAP_WORD_BITS * BITMAP_WORD_BITS); 740 bi->word_no++; 741 742 while (1) 743 { 744 /* Find the next nonzero word in this elt. */ 745 while (bi->word_no != BITMAP_ELEMENT_WORDS) 746 { 747 bi->bits = bi->elt1->bits[bi->word_no]; 748 if (bi->bits) 749 goto next_bit; 750 *bit_no += BITMAP_WORD_BITS; 751 bi->word_no++; 752 } 753 754 /* Make sure we didn't remove the element while iterating. */ 755 gcc_checking_assert (bi->elt1->indx != -1U); 756 757 /* Advance to the next element. */ 758 bi->elt1 = bi->elt1->next; 759 if (!bi->elt1) 760 return false; 761 *bit_no = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS; 762 bi->word_no = 0; 763 } 764} 765 766/* Advance to the next nonzero bit of an intersecting pair of 767 bitmaps. We will have already advanced past the just iterated bit. 768 Return true if there is a bit to iterate. */ 769 770static inline bool 771bmp_iter_and (bitmap_iterator *bi, unsigned *bit_no) 772{ 773 /* If our current word is nonzero, it contains the bit we want. */ 774 if (bi->bits) 775 { 776 next_bit: 777 bmp_iter_next_bit (bi, bit_no); 778 return true; 779 } 780 781 /* Round up to the word boundary. We might have just iterated past 782 the end of the last word, hence the -1. It is not possible for 783 bit_no to point at the beginning of the now last word. */ 784 *bit_no = ((*bit_no + BITMAP_WORD_BITS - 1) 785 / BITMAP_WORD_BITS * BITMAP_WORD_BITS); 786 bi->word_no++; 787 788 while (1) 789 { 790 /* Find the next nonzero word in this elt. */ 791 while (bi->word_no != BITMAP_ELEMENT_WORDS) 792 { 793 bi->bits = bi->elt1->bits[bi->word_no] & bi->elt2->bits[bi->word_no]; 794 if (bi->bits) 795 goto next_bit; 796 *bit_no += BITMAP_WORD_BITS; 797 bi->word_no++; 798 } 799 800 /* Advance to the next identical element. */ 801 do 802 { 803 /* Make sure we didn't remove the element while iterating. */ 804 gcc_checking_assert (bi->elt1->indx != -1U); 805 806 /* Advance elt1 while it is less than elt2. We always want 807 to advance one elt. */ 808 do 809 { 810 bi->elt1 = bi->elt1->next; 811 if (!bi->elt1) 812 return false; 813 } 814 while (bi->elt1->indx < bi->elt2->indx); 815 816 /* Make sure we didn't remove the element while iterating. */ 817 gcc_checking_assert (bi->elt2->indx != -1U); 818 819 /* Advance elt2 to be no less than elt1. This might not 820 advance. */ 821 while (bi->elt2->indx < bi->elt1->indx) 822 { 823 bi->elt2 = bi->elt2->next; 824 if (!bi->elt2) 825 return false; 826 } 827 } 828 while (bi->elt1->indx != bi->elt2->indx); 829 830 *bit_no = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS; 831 bi->word_no = 0; 832 } 833} 834 835/* Advance to the next nonzero bit in the intersection of 836 complemented bitmaps. We will have already advanced past the just 837 iterated bit. */ 838 839static inline bool 840bmp_iter_and_compl (bitmap_iterator *bi, unsigned *bit_no) 841{ 842 /* If our current word is nonzero, it contains the bit we want. */ 843 if (bi->bits) 844 { 845 next_bit: 846 bmp_iter_next_bit (bi, bit_no); 847 return true; 848 } 849 850 /* Round up to the word boundary. We might have just iterated past 851 the end of the last word, hence the -1. It is not possible for 852 bit_no to point at the beginning of the now last word. */ 853 *bit_no = ((*bit_no + BITMAP_WORD_BITS - 1) 854 / BITMAP_WORD_BITS * BITMAP_WORD_BITS); 855 bi->word_no++; 856 857 while (1) 858 { 859 /* Find the next nonzero word in this elt. */ 860 while (bi->word_no != BITMAP_ELEMENT_WORDS) 861 { 862 bi->bits = bi->elt1->bits[bi->word_no]; 863 if (bi->elt2 && bi->elt2->indx == bi->elt1->indx) 864 bi->bits &= ~bi->elt2->bits[bi->word_no]; 865 if (bi->bits) 866 goto next_bit; 867 *bit_no += BITMAP_WORD_BITS; 868 bi->word_no++; 869 } 870 871 /* Make sure we didn't remove the element while iterating. */ 872 gcc_checking_assert (bi->elt1->indx != -1U); 873 874 /* Advance to the next element of elt1. */ 875 bi->elt1 = bi->elt1->next; 876 if (!bi->elt1) 877 return false; 878 879 /* Make sure we didn't remove the element while iterating. */ 880 gcc_checking_assert (! bi->elt2 || bi->elt2->indx != -1U); 881 882 /* Advance elt2 until it is no less than elt1. */ 883 while (bi->elt2 && bi->elt2->indx < bi->elt1->indx) 884 bi->elt2 = bi->elt2->next; 885 886 *bit_no = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS; 887 bi->word_no = 0; 888 } 889} 890 891/* If you are modifying a bitmap you are currently iterating over you 892 have to ensure to 893 - never remove the current bit; 894 - if you set or clear a bit before the current bit this operation 895 will not affect the set of bits you are visiting during the iteration; 896 - if you set or clear a bit after the current bit it is unspecified 897 whether that affects the set of bits you are visiting during the 898 iteration. 899 If you want to remove the current bit you can delay this to the next 900 iteration (and after the iteration in case the last iteration is 901 affected). */ 902 903/* Loop over all bits set in BITMAP, starting with MIN and setting 904 BITNUM to the bit number. ITER is a bitmap iterator. BITNUM 905 should be treated as a read-only variable as it contains loop 906 state. */ 907 908#ifndef EXECUTE_IF_SET_IN_BITMAP 909/* See sbitmap.h for the other definition of EXECUTE_IF_SET_IN_BITMAP. */ 910#define EXECUTE_IF_SET_IN_BITMAP(BITMAP, MIN, BITNUM, ITER) \ 911 for (bmp_iter_set_init (&(ITER), (BITMAP), (MIN), &(BITNUM)); \ 912 bmp_iter_set (&(ITER), &(BITNUM)); \ 913 bmp_iter_next (&(ITER), &(BITNUM))) 914#endif 915 916/* Loop over all the bits set in BITMAP1 & BITMAP2, starting with MIN 917 and setting BITNUM to the bit number. ITER is a bitmap iterator. 918 BITNUM should be treated as a read-only variable as it contains 919 loop state. */ 920 921#define EXECUTE_IF_AND_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, ITER) \ 922 for (bmp_iter_and_init (&(ITER), (BITMAP1), (BITMAP2), (MIN), \ 923 &(BITNUM)); \ 924 bmp_iter_and (&(ITER), &(BITNUM)); \ 925 bmp_iter_next (&(ITER), &(BITNUM))) 926 927/* Loop over all the bits set in BITMAP1 & ~BITMAP2, starting with MIN 928 and setting BITNUM to the bit number. ITER is a bitmap iterator. 929 BITNUM should be treated as a read-only variable as it contains 930 loop state. */ 931 932#define EXECUTE_IF_AND_COMPL_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, ITER) \ 933 for (bmp_iter_and_compl_init (&(ITER), (BITMAP1), (BITMAP2), (MIN), \ 934 &(BITNUM)); \ 935 bmp_iter_and_compl (&(ITER), &(BITNUM)); \ 936 bmp_iter_next (&(ITER), &(BITNUM))) 937 938/* A class that ties the lifetime of a bitmap to its scope. */ 939class auto_bitmap 940{ 941 public: 942 auto_bitmap () { bitmap_initialize (&m_bits, &bitmap_default_obstack); } 943 explicit auto_bitmap (bitmap_obstack *o) { bitmap_initialize (&m_bits, o); } 944 ~auto_bitmap () { bitmap_clear (&m_bits); } 945 // Allow calling bitmap functions on our bitmap. 946 operator bitmap () { return &m_bits; } 947 948 private: 949 // Prevent making a copy that references our bitmap. 950 auto_bitmap (const auto_bitmap &); 951 auto_bitmap &operator = (const auto_bitmap &); 952#if __cplusplus >= 201103L 953 auto_bitmap (auto_bitmap &&); 954 auto_bitmap &operator = (auto_bitmap &&); 955#endif 956 957 bitmap_head m_bits; 958}; 959 960/* Base class for bitmap_view; see there for details. */ 961template<typename T, typename Traits = array_traits<T> > 962class base_bitmap_view 963{ 964public: 965 typedef typename Traits::element_type array_element_type; 966 967 base_bitmap_view (const T &, bitmap_element *); 968 operator const_bitmap () const { return &m_head; } 969 970private: 971 base_bitmap_view (const base_bitmap_view &); 972 973 bitmap_head m_head; 974}; 975 976/* Provides a read-only bitmap view of a single integer bitmask or a 977 constant-sized array of integer bitmasks, or of a wrapper around such 978 bitmasks. */ 979template<typename T, typename Traits> 980class bitmap_view<T, Traits, true> : public base_bitmap_view<T, Traits> 981{ 982public: 983 bitmap_view (const T &array) 984 : base_bitmap_view<T, Traits> (array, m_bitmap_elements) {} 985 986private: 987 /* How many bitmap_elements we need to hold a full T. */ 988 static const size_t num_bitmap_elements 989 = CEIL (CHAR_BIT 990 * sizeof (typename Traits::element_type) 991 * Traits::constant_size, 992 BITMAP_ELEMENT_ALL_BITS); 993 bitmap_element m_bitmap_elements[num_bitmap_elements]; 994}; 995 996/* Initialize the view for array ARRAY, using the array of bitmap 997 elements in BITMAP_ELEMENTS (which is known to contain enough 998 entries). */ 999template<typename T, typename Traits> 1000base_bitmap_view<T, Traits>::base_bitmap_view (const T &array, 1001 bitmap_element *bitmap_elements) 1002{ 1003 m_head.obstack = NULL; 1004 1005 /* The code currently assumes that each element of ARRAY corresponds 1006 to exactly one bitmap_element. */ 1007 const size_t array_element_bits = CHAR_BIT * sizeof (array_element_type); 1008 STATIC_ASSERT (BITMAP_ELEMENT_ALL_BITS % array_element_bits == 0); 1009 size_t array_step = BITMAP_ELEMENT_ALL_BITS / array_element_bits; 1010 size_t array_size = Traits::size (array); 1011 1012 /* Process each potential bitmap_element in turn. The loop is written 1013 this way rather than per array element because usually there are 1014 only a small number of array elements per bitmap element (typically 1015 two or four). The inner loops should therefore unroll completely. */ 1016 const array_element_type *array_elements = Traits::base (array); 1017 unsigned int indx = 0; 1018 for (size_t array_base = 0; 1019 array_base < array_size; 1020 array_base += array_step, indx += 1) 1021 { 1022 /* How many array elements are in this particular bitmap_element. */ 1023 unsigned int array_count 1024 = (STATIC_CONSTANT_P (array_size % array_step == 0) 1025 ? array_step : MIN (array_step, array_size - array_base)); 1026 1027 /* See whether we need this bitmap element. */ 1028 array_element_type ior = array_elements[array_base]; 1029 for (size_t i = 1; i < array_count; ++i) 1030 ior |= array_elements[array_base + i]; 1031 if (ior == 0) 1032 continue; 1033 1034 /* Grab the next bitmap element and chain it. */ 1035 bitmap_element *bitmap_element = bitmap_elements++; 1036 if (m_head.current) 1037 m_head.current->next = bitmap_element; 1038 else 1039 m_head.first = bitmap_element; 1040 bitmap_element->prev = m_head.current; 1041 bitmap_element->next = NULL; 1042 bitmap_element->indx = indx; 1043 m_head.current = bitmap_element; 1044 m_head.indx = indx; 1045 1046 /* Fill in the bits of the bitmap element. */ 1047 if (array_element_bits < BITMAP_WORD_BITS) 1048 { 1049 /* Multiple array elements fit in one element of 1050 bitmap_element->bits. */ 1051 size_t array_i = array_base; 1052 for (unsigned int word_i = 0; word_i < BITMAP_ELEMENT_WORDS; 1053 ++word_i) 1054 { 1055 BITMAP_WORD word = 0; 1056 for (unsigned int shift = 0; 1057 shift < BITMAP_WORD_BITS && array_i < array_size; 1058 shift += array_element_bits) 1059 word |= array_elements[array_i++] << shift; 1060 bitmap_element->bits[word_i] = word; 1061 } 1062 } 1063 else 1064 { 1065 /* Array elements are the same size as elements of 1066 bitmap_element->bits, or are an exact multiple of that size. */ 1067 unsigned int word_i = 0; 1068 for (unsigned int i = 0; i < array_count; ++i) 1069 for (unsigned int shift = 0; shift < array_element_bits; 1070 shift += BITMAP_WORD_BITS) 1071 bitmap_element->bits[word_i++] 1072 = array_elements[array_base + i] >> shift; 1073 while (word_i < BITMAP_ELEMENT_WORDS) 1074 bitmap_element->bits[word_i++] = 0; 1075 } 1076 } 1077} 1078 1079#endif /* GCC_BITMAP_H */ 1080