1/* Functions to support general ended bitmaps. 2 Copyright (C) 1997-2015 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. 24 25 This sparse set representation is suitable for sparse sets with an 26 unknown (a priori) universe. The set is represented as a double-linked 27 list of container nodes (struct bitmap_element). Each node consists 28 of an index for the first member that could be held in the container, 29 a small array of integers that represent the members in the container, 30 and pointers to the next and previous element in the linked list. The 31 elements in the list are sorted in ascending order, i.e. the head of 32 the list holds the element with the smallest member of the set. 33 34 For a given member I in the set: 35 - the element for I will have index is I / (bits per element) 36 - the position for I within element is I % (bits per element) 37 38 This representation is very space-efficient for large sparse sets, and 39 the size of the set can be changed dynamically without much overhead. 40 An important parameter is the number of bits per element. In this 41 implementation, there are 128 bits per element. This results in a 42 high storage overhead *per element*, but a small overall overhead if 43 the set is very sparse. 44 45 The downside is that many operations are relatively slow because the 46 linked list has to be traversed to test membership (i.e. member_p/ 47 add_member/remove_member). To improve the performance of this set 48 representation, the last accessed element and its index are cached. 49 For membership tests on members close to recently accessed members, 50 the cached last element improves membership test to a constant-time 51 operation. 52 53 The following operations can always be performed in O(1) time: 54 55 * clear : bitmap_clear 56 * choose_one : (not implemented, but could be 57 implemented in constant time) 58 59 The following operations can be performed in O(E) time worst-case (with 60 E the number of elements in the linked list), but in O(1) time with a 61 suitable access patterns: 62 63 * member_p : bitmap_bit_p 64 * add_member : bitmap_set_bit 65 * remove_member : bitmap_clear_bit 66 67 The following operations can be performed in O(E) time: 68 69 * cardinality : bitmap_count_bits 70 * set_size : bitmap_last_set_bit (but this could 71 in constant time with a pointer to 72 the last element in the chain) 73 74 Additionally, the linked-list sparse set representation supports 75 enumeration of the members in O(E) time: 76 77 * forall : EXECUTE_IF_SET_IN_BITMAP 78 * set_copy : bitmap_copy 79 * set_intersection : bitmap_intersect_p / 80 bitmap_and / bitmap_and_into / 81 EXECUTE_IF_AND_IN_BITMAP 82 * set_union : bitmap_ior / bitmap_ior_into 83 * set_difference : bitmap_intersect_compl_p / 84 bitmap_and_comp / bitmap_and_comp_into / 85 EXECUTE_IF_AND_COMPL_IN_BITMAP 86 * set_disjuction : bitmap_xor_comp / bitmap_xor_comp_into 87 * set_compare : bitmap_equal_p 88 89 Some operations on 3 sets that occur frequently in in data flow problems 90 are also implemented: 91 92 * A | (B & C) : bitmap_ior_and_into 93 * A | (B & ~C) : bitmap_ior_and_compl / 94 bitmap_ior_and_compl_into 95 96 The storage requirements for linked-list sparse sets are O(E), with E->N 97 in the worst case (a sparse set with large distances between the values 98 of the set members). 99 100 The linked-list set representation works well for problems involving very 101 sparse sets. The canonical example in GCC is, of course, the "set of 102 sets" for some CFG-based data flow problems (liveness analysis, dominance 103 frontiers, etc.). 104 105 This representation also works well for data flow problems where the size 106 of the set may grow dynamically, but care must be taken that the member_p, 107 add_member, and remove_member operations occur with a suitable access 108 pattern. 109 110 For random-access sets with a known, relatively small universe size, the 111 SparseSet or simple bitmap representations may be more efficient than a 112 linked-list set. For random-access sets of unknown universe, a hash table 113 or a balanced binary tree representation is likely to be a more suitable 114 choice. 115 116 Traversing linked lists is usually cache-unfriendly, even with the last 117 accessed element cached. 118 119 Cache performance can be improved by keeping the elements in the set 120 grouped together in memory, using a dedicated obstack for a set (or group 121 of related sets). Elements allocated on obstacks are released to a 122 free-list and taken off the free list. If multiple sets are allocated on 123 the same obstack, elements freed from one set may be re-used for one of 124 the other sets. This usually helps avoid cache misses. 125 126 A single free-list is used for all sets allocated in GGC space. This is 127 bad for persistent sets, so persistent sets should be allocated on an 128 obstack whenever possible. */ 129 130#include "hashtab.h" 131#include "statistics.h" 132#include "obstack.h" 133 134/* Fundamental storage type for bitmap. */ 135 136typedef unsigned long BITMAP_WORD; 137/* BITMAP_WORD_BITS needs to be unsigned, but cannot contain casts as 138 it is used in preprocessor directives -- hence the 1u. */ 139#define BITMAP_WORD_BITS (CHAR_BIT * SIZEOF_LONG * 1u) 140 141/* Number of words to use for each element in the linked list. */ 142 143#ifndef BITMAP_ELEMENT_WORDS 144#define BITMAP_ELEMENT_WORDS ((128 + BITMAP_WORD_BITS - 1) / BITMAP_WORD_BITS) 145#endif 146 147/* Number of bits in each actual element of a bitmap. */ 148 149#define BITMAP_ELEMENT_ALL_BITS (BITMAP_ELEMENT_WORDS * BITMAP_WORD_BITS) 150 151/* Obstack for allocating bitmaps and elements from. */ 152struct GTY (()) bitmap_obstack { 153 struct bitmap_element *elements; 154 struct bitmap_head *heads; 155 struct obstack GTY ((skip)) obstack; 156}; 157 158/* Bitmap set element. We use a linked list to hold only the bits that 159 are set. This allows for use to grow the bitset dynamically without 160 having to realloc and copy a giant bit array. 161 162 The free list is implemented as a list of lists. There is one 163 outer list connected together by prev fields. Each element of that 164 outer is an inner list (that may consist only of the outer list 165 element) that are connected by the next fields. The prev pointer 166 is undefined for interior elements. This allows 167 bitmap_elt_clear_from to be implemented in unit time rather than 168 linear in the number of elements to be freed. */ 169 170struct GTY((chain_next ("%h.next"), chain_prev ("%h.prev"))) bitmap_element { 171 struct bitmap_element *next; /* Next element. */ 172 struct bitmap_element *prev; /* Previous element. */ 173 unsigned int indx; /* regno/BITMAP_ELEMENT_ALL_BITS. */ 174 BITMAP_WORD bits[BITMAP_ELEMENT_WORDS]; /* Bits that are set. */ 175}; 176 177/* Head of bitmap linked list. The 'current' member points to something 178 already pointed to by the chain started by first, so GTY((skip)) it. */ 179 180struct GTY(()) bitmap_head { 181 unsigned int indx; /* Index of last element looked at. */ 182 unsigned int descriptor_id; /* Unique identifier for the allocation 183 site of this bitmap, for detailed 184 statistics gathering. */ 185 bitmap_element *first; /* First element in linked list. */ 186 bitmap_element * GTY((skip(""))) current; /* Last element looked at. */ 187 bitmap_obstack *obstack; /* Obstack to allocate elements from. 188 If NULL, then use GGC allocation. */ 189}; 190 191/* Global data */ 192extern bitmap_element bitmap_zero_bits; /* Zero bitmap element */ 193extern bitmap_obstack bitmap_default_obstack; /* Default bitmap obstack */ 194 195/* Clear a bitmap by freeing up the linked list. */ 196extern void bitmap_clear (bitmap); 197 198/* Copy a bitmap to another bitmap. */ 199extern void bitmap_copy (bitmap, const_bitmap); 200 201/* True if two bitmaps are identical. */ 202extern bool bitmap_equal_p (const_bitmap, const_bitmap); 203 204/* True if the bitmaps intersect (their AND is non-empty). */ 205extern bool bitmap_intersect_p (const_bitmap, const_bitmap); 206 207/* True if the complement of the second intersects the first (their 208 AND_COMPL is non-empty). */ 209extern bool bitmap_intersect_compl_p (const_bitmap, const_bitmap); 210 211/* True if MAP is an empty bitmap. */ 212inline bool bitmap_empty_p (const_bitmap map) 213{ 214 return !map->first; 215} 216 217/* True if the bitmap has only a single bit set. */ 218extern bool bitmap_single_bit_set_p (const_bitmap); 219 220/* Count the number of bits set in the bitmap. */ 221extern unsigned long bitmap_count_bits (const_bitmap); 222 223/* Boolean operations on bitmaps. The _into variants are two operand 224 versions that modify the first source operand. The other variants 225 are three operand versions that to not destroy the source bitmaps. 226 The operations supported are &, & ~, |, ^. */ 227extern void bitmap_and (bitmap, const_bitmap, const_bitmap); 228extern bool bitmap_and_into (bitmap, const_bitmap); 229extern bool bitmap_and_compl (bitmap, const_bitmap, const_bitmap); 230extern bool bitmap_and_compl_into (bitmap, const_bitmap); 231#define bitmap_compl_and(DST, A, B) bitmap_and_compl (DST, B, A) 232extern void bitmap_compl_and_into (bitmap, const_bitmap); 233extern void bitmap_clear_range (bitmap, unsigned int, unsigned int); 234extern void bitmap_set_range (bitmap, unsigned int, unsigned int); 235extern bool bitmap_ior (bitmap, const_bitmap, const_bitmap); 236extern bool bitmap_ior_into (bitmap, const_bitmap); 237extern void bitmap_xor (bitmap, const_bitmap, const_bitmap); 238extern void bitmap_xor_into (bitmap, const_bitmap); 239 240/* DST = A | (B & C). Return true if DST changes. */ 241extern bool bitmap_ior_and_into (bitmap DST, const_bitmap B, const_bitmap C); 242/* DST = A | (B & ~C). Return true if DST changes. */ 243extern bool bitmap_ior_and_compl (bitmap DST, const_bitmap A, 244 const_bitmap B, const_bitmap C); 245/* A |= (B & ~C). Return true if A changes. */ 246extern bool bitmap_ior_and_compl_into (bitmap A, 247 const_bitmap B, const_bitmap C); 248 249/* Clear a single bit in a bitmap. Return true if the bit changed. */ 250extern bool bitmap_clear_bit (bitmap, int); 251 252/* Set a single bit in a bitmap. Return true if the bit changed. */ 253extern bool bitmap_set_bit (bitmap, int); 254 255/* Return true if a register is set in a register set. */ 256extern int bitmap_bit_p (bitmap, int); 257 258/* Debug functions to print a bitmap linked list. */ 259extern void debug_bitmap (const_bitmap); 260extern void debug_bitmap_file (FILE *, const_bitmap); 261 262/* Print a bitmap. */ 263extern void bitmap_print (FILE *, const_bitmap, const char *, const char *); 264 265/* Initialize and release a bitmap obstack. */ 266extern void bitmap_obstack_initialize (bitmap_obstack *); 267extern void bitmap_obstack_release (bitmap_obstack *); 268extern void bitmap_register (bitmap MEM_STAT_DECL); 269extern void dump_bitmap_statistics (void); 270 271/* Initialize a bitmap header. OBSTACK indicates the bitmap obstack 272 to allocate from, NULL for GC'd bitmap. */ 273 274static inline void 275bitmap_initialize_stat (bitmap head, bitmap_obstack *obstack MEM_STAT_DECL) 276{ 277 head->first = head->current = NULL; 278 head->obstack = obstack; 279 if (GATHER_STATISTICS) 280 bitmap_register (head PASS_MEM_STAT); 281} 282#define bitmap_initialize(h,o) bitmap_initialize_stat (h,o MEM_STAT_INFO) 283 284/* Allocate and free bitmaps from obstack, malloc and gc'd memory. */ 285extern bitmap bitmap_obstack_alloc_stat (bitmap_obstack *obstack MEM_STAT_DECL); 286#define bitmap_obstack_alloc(t) bitmap_obstack_alloc_stat (t MEM_STAT_INFO) 287extern bitmap bitmap_gc_alloc_stat (ALONE_MEM_STAT_DECL); 288#define bitmap_gc_alloc() bitmap_gc_alloc_stat (ALONE_MEM_STAT_INFO) 289extern void bitmap_obstack_free (bitmap); 290 291/* A few compatibility/functions macros for compatibility with sbitmaps */ 292inline void dump_bitmap (FILE *file, const_bitmap map) 293{ 294 bitmap_print (file, map, "", "\n"); 295} 296extern void debug (const bitmap_head &ref); 297extern void debug (const bitmap_head *ptr); 298 299extern unsigned bitmap_first_set_bit (const_bitmap); 300extern unsigned bitmap_last_set_bit (const_bitmap); 301 302/* Compute bitmap hash (for purposes of hashing etc.) */ 303extern hashval_t bitmap_hash (const_bitmap); 304 305/* Allocate a bitmap from a bit obstack. */ 306#define BITMAP_ALLOC(OBSTACK) bitmap_obstack_alloc (OBSTACK) 307 308/* Allocate a gc'd bitmap. */ 309#define BITMAP_GGC_ALLOC() bitmap_gc_alloc () 310 311/* Do any cleanup needed on a bitmap when it is no longer used. */ 312#define BITMAP_FREE(BITMAP) \ 313 ((void) (bitmap_obstack_free ((bitmap) BITMAP), (BITMAP) = (bitmap) NULL)) 314 315/* Iterator for bitmaps. */ 316 317struct bitmap_iterator 318{ 319 /* Pointer to the current bitmap element. */ 320 bitmap_element *elt1; 321 322 /* Pointer to 2nd bitmap element when two are involved. */ 323 bitmap_element *elt2; 324 325 /* Word within the current element. */ 326 unsigned word_no; 327 328 /* Contents of the actually processed word. When finding next bit 329 it is shifted right, so that the actual bit is always the least 330 significant bit of ACTUAL. */ 331 BITMAP_WORD bits; 332}; 333 334/* Initialize a single bitmap iterator. START_BIT is the first bit to 335 iterate from. */ 336 337static inline void 338bmp_iter_set_init (bitmap_iterator *bi, const_bitmap map, 339 unsigned start_bit, unsigned *bit_no) 340{ 341 bi->elt1 = map->first; 342 bi->elt2 = NULL; 343 344 /* Advance elt1 until it is not before the block containing start_bit. */ 345 while (1) 346 { 347 if (!bi->elt1) 348 { 349 bi->elt1 = &bitmap_zero_bits; 350 break; 351 } 352 353 if (bi->elt1->indx >= start_bit / BITMAP_ELEMENT_ALL_BITS) 354 break; 355 bi->elt1 = bi->elt1->next; 356 } 357 358 /* We might have gone past the start bit, so reinitialize it. */ 359 if (bi->elt1->indx != start_bit / BITMAP_ELEMENT_ALL_BITS) 360 start_bit = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS; 361 362 /* Initialize for what is now start_bit. */ 363 bi->word_no = start_bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS; 364 bi->bits = bi->elt1->bits[bi->word_no]; 365 bi->bits >>= start_bit % BITMAP_WORD_BITS; 366 367 /* If this word is zero, we must make sure we're not pointing at the 368 first bit, otherwise our incrementing to the next word boundary 369 will fail. It won't matter if this increment moves us into the 370 next word. */ 371 start_bit += !bi->bits; 372 373 *bit_no = start_bit; 374} 375 376/* Initialize an iterator to iterate over the intersection of two 377 bitmaps. START_BIT is the bit to commence from. */ 378 379static inline void 380bmp_iter_and_init (bitmap_iterator *bi, const_bitmap map1, const_bitmap map2, 381 unsigned start_bit, unsigned *bit_no) 382{ 383 bi->elt1 = map1->first; 384 bi->elt2 = map2->first; 385 386 /* Advance elt1 until it is not before the block containing 387 start_bit. */ 388 while (1) 389 { 390 if (!bi->elt1) 391 { 392 bi->elt2 = NULL; 393 break; 394 } 395 396 if (bi->elt1->indx >= start_bit / BITMAP_ELEMENT_ALL_BITS) 397 break; 398 bi->elt1 = bi->elt1->next; 399 } 400 401 /* Advance elt2 until it is not before elt1. */ 402 while (1) 403 { 404 if (!bi->elt2) 405 { 406 bi->elt1 = bi->elt2 = &bitmap_zero_bits; 407 break; 408 } 409 410 if (bi->elt2->indx >= bi->elt1->indx) 411 break; 412 bi->elt2 = bi->elt2->next; 413 } 414 415 /* If we're at the same index, then we have some intersecting bits. */ 416 if (bi->elt1->indx == bi->elt2->indx) 417 { 418 /* We might have advanced beyond the start_bit, so reinitialize 419 for that. */ 420 if (bi->elt1->indx != start_bit / BITMAP_ELEMENT_ALL_BITS) 421 start_bit = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS; 422 423 bi->word_no = start_bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS; 424 bi->bits = bi->elt1->bits[bi->word_no] & bi->elt2->bits[bi->word_no]; 425 bi->bits >>= start_bit % BITMAP_WORD_BITS; 426 } 427 else 428 { 429 /* Otherwise we must immediately advance elt1, so initialize for 430 that. */ 431 bi->word_no = BITMAP_ELEMENT_WORDS - 1; 432 bi->bits = 0; 433 } 434 435 /* If this word is zero, we must make sure we're not pointing at the 436 first bit, otherwise our incrementing to the next word boundary 437 will fail. It won't matter if this increment moves us into the 438 next word. */ 439 start_bit += !bi->bits; 440 441 *bit_no = start_bit; 442} 443 444/* Initialize an iterator to iterate over the bits in MAP1 & ~MAP2. 445 */ 446 447static inline void 448bmp_iter_and_compl_init (bitmap_iterator *bi, 449 const_bitmap map1, const_bitmap map2, 450 unsigned start_bit, unsigned *bit_no) 451{ 452 bi->elt1 = map1->first; 453 bi->elt2 = map2->first; 454 455 /* Advance elt1 until it is not before the block containing start_bit. */ 456 while (1) 457 { 458 if (!bi->elt1) 459 { 460 bi->elt1 = &bitmap_zero_bits; 461 break; 462 } 463 464 if (bi->elt1->indx >= start_bit / BITMAP_ELEMENT_ALL_BITS) 465 break; 466 bi->elt1 = bi->elt1->next; 467 } 468 469 /* Advance elt2 until it is not before elt1. */ 470 while (bi->elt2 && bi->elt2->indx < bi->elt1->indx) 471 bi->elt2 = bi->elt2->next; 472 473 /* We might have advanced beyond the start_bit, so reinitialize for 474 that. */ 475 if (bi->elt1->indx != start_bit / BITMAP_ELEMENT_ALL_BITS) 476 start_bit = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS; 477 478 bi->word_no = start_bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS; 479 bi->bits = bi->elt1->bits[bi->word_no]; 480 if (bi->elt2 && bi->elt1->indx == bi->elt2->indx) 481 bi->bits &= ~bi->elt2->bits[bi->word_no]; 482 bi->bits >>= start_bit % BITMAP_WORD_BITS; 483 484 /* If this word is zero, we must make sure we're not pointing at the 485 first bit, otherwise our incrementing to the next word boundary 486 will fail. It won't matter if this increment moves us into the 487 next word. */ 488 start_bit += !bi->bits; 489 490 *bit_no = start_bit; 491} 492 493/* Advance to the next bit in BI. We don't advance to the next 494 nonzero bit yet. */ 495 496static inline void 497bmp_iter_next (bitmap_iterator *bi, unsigned *bit_no) 498{ 499 bi->bits >>= 1; 500 *bit_no += 1; 501} 502 503/* Advance to first set bit in BI. */ 504 505static inline void 506bmp_iter_next_bit (bitmap_iterator * bi, unsigned *bit_no) 507{ 508#if (GCC_VERSION >= 3004) 509 { 510 unsigned int n = __builtin_ctzl (bi->bits); 511 gcc_assert (sizeof (unsigned long) == sizeof (BITMAP_WORD)); 512 bi->bits >>= n; 513 *bit_no += n; 514 } 515#else 516 while (!(bi->bits & 1)) 517 { 518 bi->bits >>= 1; 519 *bit_no += 1; 520 } 521#endif 522} 523 524/* Advance to the next nonzero bit of a single bitmap, we will have 525 already advanced past the just iterated bit. Return true if there 526 is a bit to iterate. */ 527 528static inline bool 529bmp_iter_set (bitmap_iterator *bi, unsigned *bit_no) 530{ 531 /* If our current word is nonzero, it contains the bit we want. */ 532 if (bi->bits) 533 { 534 next_bit: 535 bmp_iter_next_bit (bi, bit_no); 536 return true; 537 } 538 539 /* Round up to the word boundary. We might have just iterated past 540 the end of the last word, hence the -1. It is not possible for 541 bit_no to point at the beginning of the now last word. */ 542 *bit_no = ((*bit_no + BITMAP_WORD_BITS - 1) 543 / BITMAP_WORD_BITS * BITMAP_WORD_BITS); 544 bi->word_no++; 545 546 while (1) 547 { 548 /* Find the next nonzero word in this elt. */ 549 while (bi->word_no != BITMAP_ELEMENT_WORDS) 550 { 551 bi->bits = bi->elt1->bits[bi->word_no]; 552 if (bi->bits) 553 goto next_bit; 554 *bit_no += BITMAP_WORD_BITS; 555 bi->word_no++; 556 } 557 558 /* Advance to the next element. */ 559 bi->elt1 = bi->elt1->next; 560 if (!bi->elt1) 561 return false; 562 *bit_no = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS; 563 bi->word_no = 0; 564 } 565} 566 567/* Advance to the next nonzero bit of an intersecting pair of 568 bitmaps. We will have already advanced past the just iterated bit. 569 Return true if there is a bit to iterate. */ 570 571static inline bool 572bmp_iter_and (bitmap_iterator *bi, unsigned *bit_no) 573{ 574 /* If our current word is nonzero, it contains the bit we want. */ 575 if (bi->bits) 576 { 577 next_bit: 578 bmp_iter_next_bit (bi, bit_no); 579 return true; 580 } 581 582 /* Round up to the word boundary. We might have just iterated past 583 the end of the last word, hence the -1. It is not possible for 584 bit_no to point at the beginning of the now last word. */ 585 *bit_no = ((*bit_no + BITMAP_WORD_BITS - 1) 586 / BITMAP_WORD_BITS * BITMAP_WORD_BITS); 587 bi->word_no++; 588 589 while (1) 590 { 591 /* Find the next nonzero word in this elt. */ 592 while (bi->word_no != BITMAP_ELEMENT_WORDS) 593 { 594 bi->bits = bi->elt1->bits[bi->word_no] & bi->elt2->bits[bi->word_no]; 595 if (bi->bits) 596 goto next_bit; 597 *bit_no += BITMAP_WORD_BITS; 598 bi->word_no++; 599 } 600 601 /* Advance to the next identical element. */ 602 do 603 { 604 /* Advance elt1 while it is less than elt2. We always want 605 to advance one elt. */ 606 do 607 { 608 bi->elt1 = bi->elt1->next; 609 if (!bi->elt1) 610 return false; 611 } 612 while (bi->elt1->indx < bi->elt2->indx); 613 614 /* Advance elt2 to be no less than elt1. This might not 615 advance. */ 616 while (bi->elt2->indx < bi->elt1->indx) 617 { 618 bi->elt2 = bi->elt2->next; 619 if (!bi->elt2) 620 return false; 621 } 622 } 623 while (bi->elt1->indx != bi->elt2->indx); 624 625 *bit_no = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS; 626 bi->word_no = 0; 627 } 628} 629 630/* Advance to the next nonzero bit in the intersection of 631 complemented bitmaps. We will have already advanced past the just 632 iterated bit. */ 633 634static inline bool 635bmp_iter_and_compl (bitmap_iterator *bi, unsigned *bit_no) 636{ 637 /* If our current word is nonzero, it contains the bit we want. */ 638 if (bi->bits) 639 { 640 next_bit: 641 bmp_iter_next_bit (bi, bit_no); 642 return true; 643 } 644 645 /* Round up to the word boundary. We might have just iterated past 646 the end of the last word, hence the -1. It is not possible for 647 bit_no to point at the beginning of the now last word. */ 648 *bit_no = ((*bit_no + BITMAP_WORD_BITS - 1) 649 / BITMAP_WORD_BITS * BITMAP_WORD_BITS); 650 bi->word_no++; 651 652 while (1) 653 { 654 /* Find the next nonzero word in this elt. */ 655 while (bi->word_no != BITMAP_ELEMENT_WORDS) 656 { 657 bi->bits = bi->elt1->bits[bi->word_no]; 658 if (bi->elt2 && bi->elt2->indx == bi->elt1->indx) 659 bi->bits &= ~bi->elt2->bits[bi->word_no]; 660 if (bi->bits) 661 goto next_bit; 662 *bit_no += BITMAP_WORD_BITS; 663 bi->word_no++; 664 } 665 666 /* Advance to the next element of elt1. */ 667 bi->elt1 = bi->elt1->next; 668 if (!bi->elt1) 669 return false; 670 671 /* Advance elt2 until it is no less than elt1. */ 672 while (bi->elt2 && bi->elt2->indx < bi->elt1->indx) 673 bi->elt2 = bi->elt2->next; 674 675 *bit_no = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS; 676 bi->word_no = 0; 677 } 678} 679 680/* Loop over all bits set in BITMAP, starting with MIN and setting 681 BITNUM to the bit number. ITER is a bitmap iterator. BITNUM 682 should be treated as a read-only variable as it contains loop 683 state. */ 684 685#ifndef EXECUTE_IF_SET_IN_BITMAP 686/* See sbitmap.h for the other definition of EXECUTE_IF_SET_IN_BITMAP. */ 687#define EXECUTE_IF_SET_IN_BITMAP(BITMAP, MIN, BITNUM, ITER) \ 688 for (bmp_iter_set_init (&(ITER), (BITMAP), (MIN), &(BITNUM)); \ 689 bmp_iter_set (&(ITER), &(BITNUM)); \ 690 bmp_iter_next (&(ITER), &(BITNUM))) 691#endif 692 693/* Loop over all the bits set in BITMAP1 & BITMAP2, starting with MIN 694 and setting BITNUM to the bit number. ITER is a bitmap iterator. 695 BITNUM should be treated as a read-only variable as it contains 696 loop state. */ 697 698#define EXECUTE_IF_AND_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, ITER) \ 699 for (bmp_iter_and_init (&(ITER), (BITMAP1), (BITMAP2), (MIN), \ 700 &(BITNUM)); \ 701 bmp_iter_and (&(ITER), &(BITNUM)); \ 702 bmp_iter_next (&(ITER), &(BITNUM))) 703 704/* Loop over all the bits set in BITMAP1 & ~BITMAP2, starting with MIN 705 and setting BITNUM to the bit number. ITER is a bitmap iterator. 706 BITNUM should be treated as a read-only variable as it contains 707 loop state. */ 708 709#define EXECUTE_IF_AND_COMPL_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, ITER) \ 710 for (bmp_iter_and_compl_init (&(ITER), (BITMAP1), (BITMAP2), (MIN), \ 711 &(BITNUM)); \ 712 bmp_iter_and_compl (&(ITER), &(BITNUM)); \ 713 bmp_iter_next (&(ITER), &(BITNUM))) 714 715#endif /* GCC_BITMAP_H */ 716