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