1 /* Functions to support general ended bitmaps. 2 Copyright (C) 1997-2018 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 #include "config.h" 21 #include "system.h" 22 #include "coretypes.h" 23 #include "bitmap.h" 24 #include "selftest.h" 25 26 /* Memory allocation statistics purpose instance. */ 27 mem_alloc_description<bitmap_usage> bitmap_mem_desc; 28 29 /* Register new bitmap. */ 30 void 31 bitmap_register (bitmap b MEM_STAT_DECL) 32 { 33 bitmap_mem_desc.register_descriptor (b, BITMAP_ORIGIN, false 34 FINAL_PASS_MEM_STAT); 35 } 36 37 /* Account the overhead. */ 38 static void 39 register_overhead (bitmap b, size_t amount) 40 { 41 if (bitmap_mem_desc.contains_descriptor_for_instance (b)) 42 bitmap_mem_desc.register_instance_overhead (amount, b); 43 } 44 45 /* Global data */ 46 bitmap_element bitmap_zero_bits; /* An element of all zero bits. */ 47 bitmap_obstack bitmap_default_obstack; /* The default bitmap obstack. */ 48 static int bitmap_default_obstack_depth; 49 static GTY((deletable)) bitmap_element *bitmap_ggc_free; /* Freelist of 50 GC'd elements. */ 51 52 static void bitmap_elem_to_freelist (bitmap, bitmap_element *); 53 static void bitmap_element_free (bitmap, bitmap_element *); 54 static bitmap_element *bitmap_element_allocate (bitmap); 55 static int bitmap_element_zerop (const bitmap_element *); 56 static void bitmap_element_link (bitmap, bitmap_element *); 57 static bitmap_element *bitmap_elt_insert_after (bitmap, bitmap_element *, unsigned int); 58 static void bitmap_elt_clear_from (bitmap, bitmap_element *); 59 static bitmap_element *bitmap_find_bit (bitmap, unsigned int); 60 61 62 /* Add ELEM to the appropriate freelist. */ 63 static inline void 64 bitmap_elem_to_freelist (bitmap head, bitmap_element *elt) 65 { 66 bitmap_obstack *bit_obstack = head->obstack; 67 68 elt->next = NULL; 69 elt->indx = -1; 70 if (bit_obstack) 71 { 72 elt->prev = bit_obstack->elements; 73 bit_obstack->elements = elt; 74 } 75 else 76 { 77 elt->prev = bitmap_ggc_free; 78 bitmap_ggc_free = elt; 79 } 80 } 81 82 /* Free a bitmap element. Since these are allocated off the 83 bitmap_obstack, "free" actually means "put onto the freelist". */ 84 85 static inline void 86 bitmap_element_free (bitmap head, bitmap_element *elt) 87 { 88 bitmap_element *next = elt->next; 89 bitmap_element *prev = elt->prev; 90 91 if (prev) 92 prev->next = next; 93 94 if (next) 95 next->prev = prev; 96 97 if (head->first == elt) 98 head->first = next; 99 100 /* Since the first thing we try is to insert before current, 101 make current the next entry in preference to the previous. */ 102 if (head->current == elt) 103 { 104 head->current = next != 0 ? next : prev; 105 if (head->current) 106 head->indx = head->current->indx; 107 else 108 head->indx = 0; 109 } 110 111 if (GATHER_STATISTICS) 112 register_overhead (head, -((int)sizeof (bitmap_element))); 113 114 bitmap_elem_to_freelist (head, elt); 115 } 116 117 /* Allocate a bitmap element. The bits are cleared, but nothing else is. */ 118 119 static inline bitmap_element * 120 bitmap_element_allocate (bitmap head) 121 { 122 bitmap_element *element; 123 bitmap_obstack *bit_obstack = head->obstack; 124 125 if (bit_obstack) 126 { 127 element = bit_obstack->elements; 128 129 if (element) 130 /* Use up the inner list first before looking at the next 131 element of the outer list. */ 132 if (element->next) 133 { 134 bit_obstack->elements = element->next; 135 bit_obstack->elements->prev = element->prev; 136 } 137 else 138 /* Inner list was just a singleton. */ 139 bit_obstack->elements = element->prev; 140 else 141 element = XOBNEW (&bit_obstack->obstack, bitmap_element); 142 } 143 else 144 { 145 element = bitmap_ggc_free; 146 if (element) 147 /* Use up the inner list first before looking at the next 148 element of the outer list. */ 149 if (element->next) 150 { 151 bitmap_ggc_free = element->next; 152 bitmap_ggc_free->prev = element->prev; 153 } 154 else 155 /* Inner list was just a singleton. */ 156 bitmap_ggc_free = element->prev; 157 else 158 element = ggc_alloc<bitmap_element> (); 159 } 160 161 if (GATHER_STATISTICS) 162 register_overhead (head, sizeof (bitmap_element)); 163 164 memset (element->bits, 0, sizeof (element->bits)); 165 166 return element; 167 } 168 169 /* Remove ELT and all following elements from bitmap HEAD. */ 170 171 void 172 bitmap_elt_clear_from (bitmap head, bitmap_element *elt) 173 { 174 bitmap_element *prev; 175 bitmap_obstack *bit_obstack = head->obstack; 176 177 if (!elt) return; 178 179 if (GATHER_STATISTICS) 180 { 181 int n = 0; 182 for (prev = elt; prev; prev = prev->next) 183 n++; 184 register_overhead (head, -sizeof (bitmap_element) * n); 185 } 186 187 prev = elt->prev; 188 if (prev) 189 { 190 prev->next = NULL; 191 if (head->current->indx > prev->indx) 192 { 193 head->current = prev; 194 head->indx = prev->indx; 195 } 196 } 197 else 198 { 199 head->first = NULL; 200 head->current = NULL; 201 head->indx = 0; 202 } 203 204 /* Put the entire list onto the free list in one operation. */ 205 if (bit_obstack) 206 { 207 elt->prev = bit_obstack->elements; 208 bit_obstack->elements = elt; 209 } 210 else 211 { 212 elt->prev = bitmap_ggc_free; 213 bitmap_ggc_free = elt; 214 } 215 } 216 217 /* Clear a bitmap by freeing the linked list. */ 218 219 void 220 bitmap_clear (bitmap head) 221 { 222 if (head->first) 223 bitmap_elt_clear_from (head, head->first); 224 } 225 226 /* Initialize a bitmap obstack. If BIT_OBSTACK is NULL, initialize 227 the default bitmap obstack. */ 228 229 void 230 bitmap_obstack_initialize (bitmap_obstack *bit_obstack) 231 { 232 if (!bit_obstack) 233 { 234 if (bitmap_default_obstack_depth++) 235 return; 236 bit_obstack = &bitmap_default_obstack; 237 } 238 239 #if !defined(__GNUC__) || (__GNUC__ < 2) 240 #define __alignof__(type) 0 241 #endif 242 243 bit_obstack->elements = NULL; 244 bit_obstack->heads = NULL; 245 obstack_specify_allocation (&bit_obstack->obstack, OBSTACK_CHUNK_SIZE, 246 __alignof__ (bitmap_element), 247 obstack_chunk_alloc, 248 obstack_chunk_free); 249 } 250 251 /* Release the memory from a bitmap obstack. If BIT_OBSTACK is NULL, 252 release the default bitmap obstack. */ 253 254 void 255 bitmap_obstack_release (bitmap_obstack *bit_obstack) 256 { 257 if (!bit_obstack) 258 { 259 if (--bitmap_default_obstack_depth) 260 { 261 gcc_assert (bitmap_default_obstack_depth > 0); 262 return; 263 } 264 bit_obstack = &bitmap_default_obstack; 265 } 266 267 bit_obstack->elements = NULL; 268 bit_obstack->heads = NULL; 269 obstack_free (&bit_obstack->obstack, NULL); 270 } 271 272 /* Create a new bitmap on an obstack. If BIT_OBSTACK is NULL, create 273 it on the default bitmap obstack. */ 274 275 bitmap 276 bitmap_alloc (bitmap_obstack *bit_obstack MEM_STAT_DECL) 277 { 278 bitmap map; 279 280 if (!bit_obstack) 281 bit_obstack = &bitmap_default_obstack; 282 map = bit_obstack->heads; 283 if (map) 284 bit_obstack->heads = (struct bitmap_head *) map->first; 285 else 286 map = XOBNEW (&bit_obstack->obstack, bitmap_head); 287 bitmap_initialize (map, bit_obstack PASS_MEM_STAT); 288 289 if (GATHER_STATISTICS) 290 register_overhead (map, sizeof (bitmap_head)); 291 292 return map; 293 } 294 295 /* Create a new GCd bitmap. */ 296 297 bitmap 298 bitmap_gc_alloc (ALONE_MEM_STAT_DECL) 299 { 300 bitmap map; 301 302 map = ggc_alloc<bitmap_head> (); 303 bitmap_initialize (map, NULL PASS_MEM_STAT); 304 305 if (GATHER_STATISTICS) 306 register_overhead (map, sizeof (bitmap_head)); 307 308 return map; 309 } 310 311 /* Release an obstack allocated bitmap. */ 312 313 void 314 bitmap_obstack_free (bitmap map) 315 { 316 if (map) 317 { 318 bitmap_clear (map); 319 map->first = (bitmap_element *) map->obstack->heads; 320 321 if (GATHER_STATISTICS) 322 register_overhead (map, -((int)sizeof (bitmap_head))); 323 324 map->obstack->heads = map; 325 } 326 } 327 328 329 /* Return nonzero if all bits in an element are zero. */ 330 331 static inline int 332 bitmap_element_zerop (const bitmap_element *element) 333 { 334 #if BITMAP_ELEMENT_WORDS == 2 335 return (element->bits[0] | element->bits[1]) == 0; 336 #else 337 unsigned i; 338 339 for (i = 0; i < BITMAP_ELEMENT_WORDS; i++) 340 if (element->bits[i] != 0) 341 return 0; 342 343 return 1; 344 #endif 345 } 346 347 /* Link the bitmap element into the current bitmap linked list. */ 348 349 static inline void 350 bitmap_element_link (bitmap head, bitmap_element *element) 351 { 352 unsigned int indx = element->indx; 353 bitmap_element *ptr; 354 355 /* If this is the first and only element, set it in. */ 356 if (head->first == 0) 357 { 358 element->next = element->prev = 0; 359 head->first = element; 360 } 361 362 /* If this index is less than that of the current element, it goes someplace 363 before the current element. */ 364 else if (indx < head->indx) 365 { 366 for (ptr = head->current; 367 ptr->prev != 0 && ptr->prev->indx > indx; 368 ptr = ptr->prev) 369 ; 370 371 if (ptr->prev) 372 ptr->prev->next = element; 373 else 374 head->first = element; 375 376 element->prev = ptr->prev; 377 element->next = ptr; 378 ptr->prev = element; 379 } 380 381 /* Otherwise, it must go someplace after the current element. */ 382 else 383 { 384 for (ptr = head->current; 385 ptr->next != 0 && ptr->next->indx < indx; 386 ptr = ptr->next) 387 ; 388 389 if (ptr->next) 390 ptr->next->prev = element; 391 392 element->next = ptr->next; 393 element->prev = ptr; 394 ptr->next = element; 395 } 396 397 /* Set up so this is the first element searched. */ 398 head->current = element; 399 head->indx = indx; 400 } 401 402 /* Insert a new uninitialized element into bitmap HEAD after element 403 ELT. If ELT is NULL, insert the element at the start. Return the 404 new element. */ 405 406 static bitmap_element * 407 bitmap_elt_insert_after (bitmap head, bitmap_element *elt, unsigned int indx) 408 { 409 bitmap_element *node = bitmap_element_allocate (head); 410 node->indx = indx; 411 412 if (!elt) 413 { 414 if (!head->current) 415 { 416 head->current = node; 417 head->indx = indx; 418 } 419 node->next = head->first; 420 if (node->next) 421 node->next->prev = node; 422 head->first = node; 423 node->prev = NULL; 424 } 425 else 426 { 427 gcc_checking_assert (head->current); 428 node->next = elt->next; 429 if (node->next) 430 node->next->prev = node; 431 elt->next = node; 432 node->prev = elt; 433 } 434 return node; 435 } 436 437 /* Copy a bitmap to another bitmap. */ 438 439 void 440 bitmap_copy (bitmap to, const_bitmap from) 441 { 442 const bitmap_element *from_ptr; 443 bitmap_element *to_ptr = 0; 444 445 bitmap_clear (to); 446 447 /* Copy elements in forward direction one at a time. */ 448 for (from_ptr = from->first; from_ptr; from_ptr = from_ptr->next) 449 { 450 bitmap_element *to_elt = bitmap_element_allocate (to); 451 452 to_elt->indx = from_ptr->indx; 453 memcpy (to_elt->bits, from_ptr->bits, sizeof (to_elt->bits)); 454 455 /* Here we have a special case of bitmap_element_link, for the case 456 where we know the links are being entered in sequence. */ 457 if (to_ptr == 0) 458 { 459 to->first = to->current = to_elt; 460 to->indx = from_ptr->indx; 461 to_elt->next = to_elt->prev = 0; 462 } 463 else 464 { 465 to_elt->prev = to_ptr; 466 to_elt->next = 0; 467 to_ptr->next = to_elt; 468 } 469 470 to_ptr = to_elt; 471 } 472 } 473 474 /* Move a bitmap to another bitmap. */ 475 476 void 477 bitmap_move (bitmap to, bitmap from) 478 { 479 gcc_assert (to->obstack == from->obstack); 480 481 bitmap_clear (to); 482 483 *to = *from; 484 485 if (GATHER_STATISTICS) 486 { 487 size_t sz = 0; 488 for (bitmap_element *e = to->first; e; e = e->next) 489 sz += sizeof (bitmap_element); 490 register_overhead (to, sz); 491 register_overhead (from, -sz); 492 } 493 } 494 495 /* Find a bitmap element that would hold a bitmap's bit. 496 Update the `current' field even if we can't find an element that 497 would hold the bitmap's bit to make eventual allocation 498 faster. */ 499 500 static inline bitmap_element * 501 bitmap_find_bit (bitmap head, unsigned int bit) 502 { 503 bitmap_element *element; 504 unsigned int indx = bit / BITMAP_ELEMENT_ALL_BITS; 505 506 if (head->current == NULL 507 || head->indx == indx) 508 return head->current; 509 if (head->current == head->first 510 && head->first->next == NULL) 511 return NULL; 512 513 /* Usage can be NULL due to allocated bitmaps for which we do not 514 call initialize function. */ 515 bitmap_usage *usage = NULL; 516 if (GATHER_STATISTICS) 517 usage = bitmap_mem_desc.get_descriptor_for_instance (head); 518 519 /* This bitmap has more than one element, and we're going to look 520 through the elements list. Count that as a search. */ 521 if (GATHER_STATISTICS && usage) 522 usage->m_nsearches++; 523 524 if (head->indx < indx) 525 /* INDX is beyond head->indx. Search from head->current 526 forward. */ 527 for (element = head->current; 528 element->next != 0 && element->indx < indx; 529 element = element->next) 530 { 531 if (GATHER_STATISTICS && usage) 532 usage->m_search_iter++; 533 } 534 535 else if (head->indx / 2 < indx) 536 /* INDX is less than head->indx and closer to head->indx than to 537 0. Search from head->current backward. */ 538 for (element = head->current; 539 element->prev != 0 && element->indx > indx; 540 element = element->prev) 541 { 542 if (GATHER_STATISTICS && usage) 543 usage->m_search_iter++; 544 } 545 546 else 547 /* INDX is less than head->indx and closer to 0 than to 548 head->indx. Search from head->first forward. */ 549 for (element = head->first; 550 element->next != 0 && element->indx < indx; 551 element = element->next) 552 if (GATHER_STATISTICS && usage) 553 { 554 usage->m_search_iter++; 555 } 556 557 /* `element' is the nearest to the one we want. If it's not the one we 558 want, the one we want doesn't exist. */ 559 head->current = element; 560 head->indx = element->indx; 561 if (element->indx != indx) 562 element = 0; 563 564 return element; 565 } 566 567 /* Clear a single bit in a bitmap. Return true if the bit changed. */ 568 569 bool 570 bitmap_clear_bit (bitmap head, int bit) 571 { 572 bitmap_element *const ptr = bitmap_find_bit (head, bit); 573 574 if (ptr != 0) 575 { 576 unsigned bit_num = bit % BITMAP_WORD_BITS; 577 unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS; 578 BITMAP_WORD bit_val = ((BITMAP_WORD) 1) << bit_num; 579 bool res = (ptr->bits[word_num] & bit_val) != 0; 580 if (res) 581 { 582 ptr->bits[word_num] &= ~bit_val; 583 /* If we cleared the entire word, free up the element. */ 584 if (!ptr->bits[word_num] 585 && bitmap_element_zerop (ptr)) 586 bitmap_element_free (head, ptr); 587 } 588 589 return res; 590 } 591 592 return false; 593 } 594 595 /* Set a single bit in a bitmap. Return true if the bit changed. */ 596 597 bool 598 bitmap_set_bit (bitmap head, int bit) 599 { 600 bitmap_element *ptr = bitmap_find_bit (head, bit); 601 unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS; 602 unsigned bit_num = bit % BITMAP_WORD_BITS; 603 BITMAP_WORD bit_val = ((BITMAP_WORD) 1) << bit_num; 604 605 if (ptr == 0) 606 { 607 ptr = bitmap_element_allocate (head); 608 ptr->indx = bit / BITMAP_ELEMENT_ALL_BITS; 609 ptr->bits[word_num] = bit_val; 610 bitmap_element_link (head, ptr); 611 return true; 612 } 613 else 614 { 615 bool res = (ptr->bits[word_num] & bit_val) == 0; 616 if (res) 617 ptr->bits[word_num] |= bit_val; 618 return res; 619 } 620 } 621 622 /* Return whether a bit is set within a bitmap. */ 623 624 int 625 bitmap_bit_p (bitmap head, int bit) 626 { 627 bitmap_element *ptr; 628 unsigned bit_num; 629 unsigned word_num; 630 631 ptr = bitmap_find_bit (head, bit); 632 if (ptr == 0) 633 return 0; 634 635 bit_num = bit % BITMAP_WORD_BITS; 636 word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS; 637 638 return (ptr->bits[word_num] >> bit_num) & 1; 639 } 640 641 #if GCC_VERSION < 3400 642 /* Table of number of set bits in a character, indexed by value of char. */ 643 static const unsigned char popcount_table[] = 644 { 645 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5, 646 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6, 647 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6, 648 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7, 649 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6, 650 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7, 651 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7, 652 3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8, 653 }; 654 655 static unsigned long 656 bitmap_popcount (BITMAP_WORD a) 657 { 658 unsigned long ret = 0; 659 unsigned i; 660 661 /* Just do this the table way for now */ 662 for (i = 0; i < BITMAP_WORD_BITS; i+= 8) 663 ret += popcount_table[(a >> i) & 0xff]; 664 return ret; 665 } 666 #endif 667 668 /* Count and return the number of bits set in the bitmap word BITS. */ 669 static unsigned long 670 bitmap_count_bits_in_word (const BITMAP_WORD *bits) 671 { 672 unsigned long count = 0; 673 674 for (unsigned ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++) 675 { 676 #if GCC_VERSION >= 3400 677 /* Note that popcountl matches BITMAP_WORD in type, so the actual size 678 of BITMAP_WORD is not material. */ 679 count += __builtin_popcountl (bits[ix]); 680 #else 681 count += bitmap_popcount (bits[ix]); 682 #endif 683 } 684 return count; 685 } 686 687 /* Count the number of bits set in the bitmap, and return it. */ 688 689 unsigned long 690 bitmap_count_bits (const_bitmap a) 691 { 692 unsigned long count = 0; 693 const bitmap_element *elt; 694 695 for (elt = a->first; elt; elt = elt->next) 696 count += bitmap_count_bits_in_word (elt->bits); 697 698 return count; 699 } 700 701 /* Count the number of unique bits set in A and B and return it. */ 702 703 unsigned long 704 bitmap_count_unique_bits (const_bitmap a, const_bitmap b) 705 { 706 unsigned long count = 0; 707 const bitmap_element *elt_a, *elt_b; 708 709 for (elt_a = a->first, elt_b = b->first; elt_a && elt_b; ) 710 { 711 /* If we're at different indices, then count all the bits 712 in the lower element. If we're at the same index, then 713 count the bits in the IOR of the two elements. */ 714 if (elt_a->indx < elt_b->indx) 715 { 716 count += bitmap_count_bits_in_word (elt_a->bits); 717 elt_a = elt_a->next; 718 } 719 else if (elt_b->indx < elt_a->indx) 720 { 721 count += bitmap_count_bits_in_word (elt_b->bits); 722 elt_b = elt_b->next; 723 } 724 else 725 { 726 BITMAP_WORD bits[BITMAP_ELEMENT_WORDS]; 727 for (unsigned ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++) 728 bits[ix] = elt_a->bits[ix] | elt_b->bits[ix]; 729 count += bitmap_count_bits_in_word (bits); 730 elt_a = elt_a->next; 731 elt_b = elt_b->next; 732 } 733 } 734 return count; 735 } 736 737 /* Return true if the bitmap has a single bit set. Otherwise return 738 false. */ 739 740 bool 741 bitmap_single_bit_set_p (const_bitmap a) 742 { 743 unsigned long count = 0; 744 const bitmap_element *elt; 745 unsigned ix; 746 747 if (bitmap_empty_p (a)) 748 return false; 749 750 elt = a->first; 751 /* As there are no completely empty bitmap elements, a second one 752 means we have more than one bit set. */ 753 if (elt->next != NULL) 754 return false; 755 756 for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++) 757 { 758 #if GCC_VERSION >= 3400 759 /* Note that popcountl matches BITMAP_WORD in type, so the actual size 760 of BITMAP_WORD is not material. */ 761 count += __builtin_popcountl (elt->bits[ix]); 762 #else 763 count += bitmap_popcount (elt->bits[ix]); 764 #endif 765 if (count > 1) 766 return false; 767 } 768 769 return count == 1; 770 } 771 772 773 /* Return the bit number of the first set bit in the bitmap. The 774 bitmap must be non-empty. */ 775 776 unsigned 777 bitmap_first_set_bit (const_bitmap a) 778 { 779 const bitmap_element *elt = a->first; 780 unsigned bit_no; 781 BITMAP_WORD word; 782 unsigned ix; 783 784 gcc_checking_assert (elt); 785 bit_no = elt->indx * BITMAP_ELEMENT_ALL_BITS; 786 for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++) 787 { 788 word = elt->bits[ix]; 789 if (word) 790 goto found_bit; 791 } 792 gcc_unreachable (); 793 found_bit: 794 bit_no += ix * BITMAP_WORD_BITS; 795 796 #if GCC_VERSION >= 3004 797 gcc_assert (sizeof (long) == sizeof (word)); 798 bit_no += __builtin_ctzl (word); 799 #else 800 /* Binary search for the first set bit. */ 801 #if BITMAP_WORD_BITS > 64 802 #error "Fill out the table." 803 #endif 804 #if BITMAP_WORD_BITS > 32 805 if (!(word & 0xffffffff)) 806 word >>= 32, bit_no += 32; 807 #endif 808 if (!(word & 0xffff)) 809 word >>= 16, bit_no += 16; 810 if (!(word & 0xff)) 811 word >>= 8, bit_no += 8; 812 if (!(word & 0xf)) 813 word >>= 4, bit_no += 4; 814 if (!(word & 0x3)) 815 word >>= 2, bit_no += 2; 816 if (!(word & 0x1)) 817 word >>= 1, bit_no += 1; 818 819 gcc_checking_assert (word & 1); 820 #endif 821 return bit_no; 822 } 823 824 /* Return the bit number of the first set bit in the bitmap. The 825 bitmap must be non-empty. */ 826 827 unsigned 828 bitmap_last_set_bit (const_bitmap a) 829 { 830 const bitmap_element *elt = a->current ? a->current : a->first; 831 unsigned bit_no; 832 BITMAP_WORD word; 833 int ix; 834 835 gcc_checking_assert (elt); 836 while (elt->next) 837 elt = elt->next; 838 bit_no = elt->indx * BITMAP_ELEMENT_ALL_BITS; 839 for (ix = BITMAP_ELEMENT_WORDS - 1; ix >= 0; ix--) 840 { 841 word = elt->bits[ix]; 842 if (word) 843 goto found_bit; 844 } 845 gcc_unreachable (); 846 found_bit: 847 bit_no += ix * BITMAP_WORD_BITS; 848 #if GCC_VERSION >= 3004 849 gcc_assert (sizeof (long) == sizeof (word)); 850 bit_no += BITMAP_WORD_BITS - __builtin_clzl (word) - 1; 851 #else 852 /* Hopefully this is a twos-complement host... */ 853 BITMAP_WORD x = word; 854 x |= (x >> 1); 855 x |= (x >> 2); 856 x |= (x >> 4); 857 x |= (x >> 8); 858 x |= (x >> 16); 859 #if BITMAP_WORD_BITS > 32 860 x |= (x >> 32); 861 #endif 862 bit_no += bitmap_popcount (x) - 1; 863 #endif 864 865 return bit_no; 866 } 867 868 869 /* DST = A & B. */ 870 871 void 872 bitmap_and (bitmap dst, const_bitmap a, const_bitmap b) 873 { 874 bitmap_element *dst_elt = dst->first; 875 const bitmap_element *a_elt = a->first; 876 const bitmap_element *b_elt = b->first; 877 bitmap_element *dst_prev = NULL; 878 879 gcc_assert (dst != a && dst != b); 880 881 if (a == b) 882 { 883 bitmap_copy (dst, a); 884 return; 885 } 886 887 while (a_elt && b_elt) 888 { 889 if (a_elt->indx < b_elt->indx) 890 a_elt = a_elt->next; 891 else if (b_elt->indx < a_elt->indx) 892 b_elt = b_elt->next; 893 else 894 { 895 /* Matching elts, generate A & B. */ 896 unsigned ix; 897 BITMAP_WORD ior = 0; 898 899 if (!dst_elt) 900 dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx); 901 else 902 dst_elt->indx = a_elt->indx; 903 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) 904 { 905 BITMAP_WORD r = a_elt->bits[ix] & b_elt->bits[ix]; 906 907 dst_elt->bits[ix] = r; 908 ior |= r; 909 } 910 if (ior) 911 { 912 dst_prev = dst_elt; 913 dst_elt = dst_elt->next; 914 } 915 a_elt = a_elt->next; 916 b_elt = b_elt->next; 917 } 918 } 919 /* Ensure that dst->current is valid. */ 920 dst->current = dst->first; 921 bitmap_elt_clear_from (dst, dst_elt); 922 gcc_checking_assert (!dst->current == !dst->first); 923 if (dst->current) 924 dst->indx = dst->current->indx; 925 } 926 927 /* A &= B. Return true if A changed. */ 928 929 bool 930 bitmap_and_into (bitmap a, const_bitmap b) 931 { 932 bitmap_element *a_elt = a->first; 933 const bitmap_element *b_elt = b->first; 934 bitmap_element *next; 935 bool changed = false; 936 937 if (a == b) 938 return false; 939 940 while (a_elt && b_elt) 941 { 942 if (a_elt->indx < b_elt->indx) 943 { 944 next = a_elt->next; 945 bitmap_element_free (a, a_elt); 946 a_elt = next; 947 changed = true; 948 } 949 else if (b_elt->indx < a_elt->indx) 950 b_elt = b_elt->next; 951 else 952 { 953 /* Matching elts, generate A &= B. */ 954 unsigned ix; 955 BITMAP_WORD ior = 0; 956 957 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) 958 { 959 BITMAP_WORD r = a_elt->bits[ix] & b_elt->bits[ix]; 960 if (a_elt->bits[ix] != r) 961 changed = true; 962 a_elt->bits[ix] = r; 963 ior |= r; 964 } 965 next = a_elt->next; 966 if (!ior) 967 bitmap_element_free (a, a_elt); 968 a_elt = next; 969 b_elt = b_elt->next; 970 } 971 } 972 973 if (a_elt) 974 { 975 changed = true; 976 bitmap_elt_clear_from (a, a_elt); 977 } 978 979 gcc_checking_assert (!a->current == !a->first 980 && (!a->current || a->indx == a->current->indx)); 981 982 return changed; 983 } 984 985 986 /* Insert an element equal to SRC_ELT after DST_PREV, overwriting DST_ELT 987 if non-NULL. CHANGED is true if the destination bitmap had already been 988 changed; the new value of CHANGED is returned. */ 989 990 static inline bool 991 bitmap_elt_copy (bitmap dst, bitmap_element *dst_elt, bitmap_element *dst_prev, 992 const bitmap_element *src_elt, bool changed) 993 { 994 if (!changed && dst_elt && dst_elt->indx == src_elt->indx) 995 { 996 unsigned ix; 997 998 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) 999 if (src_elt->bits[ix] != dst_elt->bits[ix]) 1000 { 1001 dst_elt->bits[ix] = src_elt->bits[ix]; 1002 changed = true; 1003 } 1004 } 1005 else 1006 { 1007 changed = true; 1008 if (!dst_elt) 1009 dst_elt = bitmap_elt_insert_after (dst, dst_prev, src_elt->indx); 1010 else 1011 dst_elt->indx = src_elt->indx; 1012 memcpy (dst_elt->bits, src_elt->bits, sizeof (dst_elt->bits)); 1013 } 1014 return changed; 1015 } 1016 1017 1018 1019 /* DST = A & ~B */ 1020 1021 bool 1022 bitmap_and_compl (bitmap dst, const_bitmap a, const_bitmap b) 1023 { 1024 bitmap_element *dst_elt = dst->first; 1025 const bitmap_element *a_elt = a->first; 1026 const bitmap_element *b_elt = b->first; 1027 bitmap_element *dst_prev = NULL; 1028 bitmap_element **dst_prev_pnext = &dst->first; 1029 bool changed = false; 1030 1031 gcc_assert (dst != a && dst != b); 1032 1033 if (a == b) 1034 { 1035 changed = !bitmap_empty_p (dst); 1036 bitmap_clear (dst); 1037 return changed; 1038 } 1039 1040 while (a_elt) 1041 { 1042 while (b_elt && b_elt->indx < a_elt->indx) 1043 b_elt = b_elt->next; 1044 1045 if (!b_elt || b_elt->indx > a_elt->indx) 1046 { 1047 changed = bitmap_elt_copy (dst, dst_elt, dst_prev, a_elt, changed); 1048 dst_prev = *dst_prev_pnext; 1049 dst_prev_pnext = &dst_prev->next; 1050 dst_elt = *dst_prev_pnext; 1051 a_elt = a_elt->next; 1052 } 1053 1054 else 1055 { 1056 /* Matching elts, generate A & ~B. */ 1057 unsigned ix; 1058 BITMAP_WORD ior = 0; 1059 1060 if (!changed && dst_elt && dst_elt->indx == a_elt->indx) 1061 { 1062 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) 1063 { 1064 BITMAP_WORD r = a_elt->bits[ix] & ~b_elt->bits[ix]; 1065 1066 if (dst_elt->bits[ix] != r) 1067 { 1068 changed = true; 1069 dst_elt->bits[ix] = r; 1070 } 1071 ior |= r; 1072 } 1073 } 1074 else 1075 { 1076 bool new_element; 1077 if (!dst_elt || dst_elt->indx > a_elt->indx) 1078 { 1079 dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx); 1080 new_element = true; 1081 } 1082 else 1083 { 1084 dst_elt->indx = a_elt->indx; 1085 new_element = false; 1086 } 1087 1088 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) 1089 { 1090 BITMAP_WORD r = a_elt->bits[ix] & ~b_elt->bits[ix]; 1091 1092 dst_elt->bits[ix] = r; 1093 ior |= r; 1094 } 1095 1096 if (ior) 1097 changed = true; 1098 else 1099 { 1100 changed |= !new_element; 1101 bitmap_element_free (dst, dst_elt); 1102 dst_elt = *dst_prev_pnext; 1103 } 1104 } 1105 1106 if (ior) 1107 { 1108 dst_prev = *dst_prev_pnext; 1109 dst_prev_pnext = &dst_prev->next; 1110 dst_elt = *dst_prev_pnext; 1111 } 1112 a_elt = a_elt->next; 1113 b_elt = b_elt->next; 1114 } 1115 } 1116 1117 /* Ensure that dst->current is valid. */ 1118 dst->current = dst->first; 1119 1120 if (dst_elt) 1121 { 1122 changed = true; 1123 bitmap_elt_clear_from (dst, dst_elt); 1124 } 1125 gcc_checking_assert (!dst->current == !dst->first); 1126 if (dst->current) 1127 dst->indx = dst->current->indx; 1128 1129 return changed; 1130 } 1131 1132 /* A &= ~B. Returns true if A changes */ 1133 1134 bool 1135 bitmap_and_compl_into (bitmap a, const_bitmap b) 1136 { 1137 bitmap_element *a_elt = a->first; 1138 const bitmap_element *b_elt = b->first; 1139 bitmap_element *next; 1140 BITMAP_WORD changed = 0; 1141 1142 if (a == b) 1143 { 1144 if (bitmap_empty_p (a)) 1145 return false; 1146 else 1147 { 1148 bitmap_clear (a); 1149 return true; 1150 } 1151 } 1152 1153 while (a_elt && b_elt) 1154 { 1155 if (a_elt->indx < b_elt->indx) 1156 a_elt = a_elt->next; 1157 else if (b_elt->indx < a_elt->indx) 1158 b_elt = b_elt->next; 1159 else 1160 { 1161 /* Matching elts, generate A &= ~B. */ 1162 unsigned ix; 1163 BITMAP_WORD ior = 0; 1164 1165 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) 1166 { 1167 BITMAP_WORD cleared = a_elt->bits[ix] & b_elt->bits[ix]; 1168 BITMAP_WORD r = a_elt->bits[ix] ^ cleared; 1169 1170 a_elt->bits[ix] = r; 1171 changed |= cleared; 1172 ior |= r; 1173 } 1174 next = a_elt->next; 1175 if (!ior) 1176 bitmap_element_free (a, a_elt); 1177 a_elt = next; 1178 b_elt = b_elt->next; 1179 } 1180 } 1181 gcc_checking_assert (!a->current == !a->first 1182 && (!a->current || a->indx == a->current->indx)); 1183 return changed != 0; 1184 } 1185 1186 /* Set COUNT bits from START in HEAD. */ 1187 void 1188 bitmap_set_range (bitmap head, unsigned int start, unsigned int count) 1189 { 1190 unsigned int first_index, end_bit_plus1, last_index; 1191 bitmap_element *elt, *elt_prev; 1192 unsigned int i; 1193 1194 if (!count) 1195 return; 1196 1197 if (count == 1) 1198 { 1199 bitmap_set_bit (head, start); 1200 return; 1201 } 1202 1203 first_index = start / BITMAP_ELEMENT_ALL_BITS; 1204 end_bit_plus1 = start + count; 1205 last_index = (end_bit_plus1 - 1) / BITMAP_ELEMENT_ALL_BITS; 1206 elt = bitmap_find_bit (head, start); 1207 1208 /* If bitmap_find_bit returns zero, the current is the closest block 1209 to the result. Otherwise, just use bitmap_element_allocate to 1210 ensure ELT is set; in the loop below, ELT == NULL means "insert 1211 at the end of the bitmap". */ 1212 if (!elt) 1213 { 1214 elt = bitmap_element_allocate (head); 1215 elt->indx = first_index; 1216 bitmap_element_link (head, elt); 1217 } 1218 1219 gcc_checking_assert (elt->indx == first_index); 1220 elt_prev = elt->prev; 1221 for (i = first_index; i <= last_index; i++) 1222 { 1223 unsigned elt_start_bit = i * BITMAP_ELEMENT_ALL_BITS; 1224 unsigned elt_end_bit_plus1 = elt_start_bit + BITMAP_ELEMENT_ALL_BITS; 1225 1226 unsigned int first_word_to_mod; 1227 BITMAP_WORD first_mask; 1228 unsigned int last_word_to_mod; 1229 BITMAP_WORD last_mask; 1230 unsigned int ix; 1231 1232 if (!elt || elt->indx != i) 1233 elt = bitmap_elt_insert_after (head, elt_prev, i); 1234 1235 if (elt_start_bit <= start) 1236 { 1237 /* The first bit to turn on is somewhere inside this 1238 elt. */ 1239 first_word_to_mod = (start - elt_start_bit) / BITMAP_WORD_BITS; 1240 1241 /* This mask should have 1s in all bits >= start position. */ 1242 first_mask = 1243 (((BITMAP_WORD) 1) << ((start % BITMAP_WORD_BITS))) - 1; 1244 first_mask = ~first_mask; 1245 } 1246 else 1247 { 1248 /* The first bit to turn on is below this start of this elt. */ 1249 first_word_to_mod = 0; 1250 first_mask = ~(BITMAP_WORD) 0; 1251 } 1252 1253 if (elt_end_bit_plus1 <= end_bit_plus1) 1254 { 1255 /* The last bit to turn on is beyond this elt. */ 1256 last_word_to_mod = BITMAP_ELEMENT_WORDS - 1; 1257 last_mask = ~(BITMAP_WORD) 0; 1258 } 1259 else 1260 { 1261 /* The last bit to turn on is inside to this elt. */ 1262 last_word_to_mod = 1263 (end_bit_plus1 - elt_start_bit) / BITMAP_WORD_BITS; 1264 1265 /* The last mask should have 1s below the end bit. */ 1266 last_mask = 1267 (((BITMAP_WORD) 1) << ((end_bit_plus1 % BITMAP_WORD_BITS))) - 1; 1268 } 1269 1270 if (first_word_to_mod == last_word_to_mod) 1271 { 1272 BITMAP_WORD mask = first_mask & last_mask; 1273 elt->bits[first_word_to_mod] |= mask; 1274 } 1275 else 1276 { 1277 elt->bits[first_word_to_mod] |= first_mask; 1278 if (BITMAP_ELEMENT_WORDS > 2) 1279 for (ix = first_word_to_mod + 1; ix < last_word_to_mod; ix++) 1280 elt->bits[ix] = ~(BITMAP_WORD) 0; 1281 elt->bits[last_word_to_mod] |= last_mask; 1282 } 1283 1284 elt_prev = elt; 1285 elt = elt->next; 1286 } 1287 1288 head->current = elt ? elt : elt_prev; 1289 head->indx = head->current->indx; 1290 } 1291 1292 /* Clear COUNT bits from START in HEAD. */ 1293 void 1294 bitmap_clear_range (bitmap head, unsigned int start, unsigned int count) 1295 { 1296 unsigned int first_index, end_bit_plus1, last_index; 1297 bitmap_element *elt; 1298 1299 if (!count) 1300 return; 1301 1302 if (count == 1) 1303 { 1304 bitmap_clear_bit (head, start); 1305 return; 1306 } 1307 1308 first_index = start / BITMAP_ELEMENT_ALL_BITS; 1309 end_bit_plus1 = start + count; 1310 last_index = (end_bit_plus1 - 1) / BITMAP_ELEMENT_ALL_BITS; 1311 elt = bitmap_find_bit (head, start); 1312 1313 /* If bitmap_find_bit returns zero, the current is the closest block 1314 to the result. If the current is less than first index, find the 1315 next one. Otherwise, just set elt to be current. */ 1316 if (!elt) 1317 { 1318 if (head->current) 1319 { 1320 if (head->indx < first_index) 1321 { 1322 elt = head->current->next; 1323 if (!elt) 1324 return; 1325 } 1326 else 1327 elt = head->current; 1328 } 1329 else 1330 return; 1331 } 1332 1333 while (elt && (elt->indx <= last_index)) 1334 { 1335 bitmap_element * next_elt = elt->next; 1336 unsigned elt_start_bit = (elt->indx) * BITMAP_ELEMENT_ALL_BITS; 1337 unsigned elt_end_bit_plus1 = elt_start_bit + BITMAP_ELEMENT_ALL_BITS; 1338 1339 1340 if (elt_start_bit >= start && elt_end_bit_plus1 <= end_bit_plus1) 1341 /* Get rid of the entire elt and go to the next one. */ 1342 bitmap_element_free (head, elt); 1343 else 1344 { 1345 /* Going to have to knock out some bits in this elt. */ 1346 unsigned int first_word_to_mod; 1347 BITMAP_WORD first_mask; 1348 unsigned int last_word_to_mod; 1349 BITMAP_WORD last_mask; 1350 unsigned int i; 1351 bool clear = true; 1352 1353 if (elt_start_bit <= start) 1354 { 1355 /* The first bit to turn off is somewhere inside this 1356 elt. */ 1357 first_word_to_mod = (start - elt_start_bit) / BITMAP_WORD_BITS; 1358 1359 /* This mask should have 1s in all bits >= start position. */ 1360 first_mask = 1361 (((BITMAP_WORD) 1) << ((start % BITMAP_WORD_BITS))) - 1; 1362 first_mask = ~first_mask; 1363 } 1364 else 1365 { 1366 /* The first bit to turn off is below this start of this elt. */ 1367 first_word_to_mod = 0; 1368 first_mask = 0; 1369 first_mask = ~first_mask; 1370 } 1371 1372 if (elt_end_bit_plus1 <= end_bit_plus1) 1373 { 1374 /* The last bit to turn off is beyond this elt. */ 1375 last_word_to_mod = BITMAP_ELEMENT_WORDS - 1; 1376 last_mask = 0; 1377 last_mask = ~last_mask; 1378 } 1379 else 1380 { 1381 /* The last bit to turn off is inside to this elt. */ 1382 last_word_to_mod = 1383 (end_bit_plus1 - elt_start_bit) / BITMAP_WORD_BITS; 1384 1385 /* The last mask should have 1s below the end bit. */ 1386 last_mask = 1387 (((BITMAP_WORD) 1) << (((end_bit_plus1) % BITMAP_WORD_BITS))) - 1; 1388 } 1389 1390 1391 if (first_word_to_mod == last_word_to_mod) 1392 { 1393 BITMAP_WORD mask = first_mask & last_mask; 1394 elt->bits[first_word_to_mod] &= ~mask; 1395 } 1396 else 1397 { 1398 elt->bits[first_word_to_mod] &= ~first_mask; 1399 if (BITMAP_ELEMENT_WORDS > 2) 1400 for (i = first_word_to_mod + 1; i < last_word_to_mod; i++) 1401 elt->bits[i] = 0; 1402 elt->bits[last_word_to_mod] &= ~last_mask; 1403 } 1404 for (i = 0; i < BITMAP_ELEMENT_WORDS; i++) 1405 if (elt->bits[i]) 1406 { 1407 clear = false; 1408 break; 1409 } 1410 /* Check to see if there are any bits left. */ 1411 if (clear) 1412 bitmap_element_free (head, elt); 1413 } 1414 elt = next_elt; 1415 } 1416 1417 if (elt) 1418 { 1419 head->current = elt; 1420 head->indx = head->current->indx; 1421 } 1422 } 1423 1424 /* A = ~A & B. */ 1425 1426 void 1427 bitmap_compl_and_into (bitmap a, const_bitmap b) 1428 { 1429 bitmap_element *a_elt = a->first; 1430 const bitmap_element *b_elt = b->first; 1431 bitmap_element *a_prev = NULL; 1432 bitmap_element *next; 1433 1434 gcc_assert (a != b); 1435 1436 if (bitmap_empty_p (a)) 1437 { 1438 bitmap_copy (a, b); 1439 return; 1440 } 1441 if (bitmap_empty_p (b)) 1442 { 1443 bitmap_clear (a); 1444 return; 1445 } 1446 1447 while (a_elt || b_elt) 1448 { 1449 if (!b_elt || (a_elt && a_elt->indx < b_elt->indx)) 1450 { 1451 /* A is before B. Remove A */ 1452 next = a_elt->next; 1453 a_prev = a_elt->prev; 1454 bitmap_element_free (a, a_elt); 1455 a_elt = next; 1456 } 1457 else if (!a_elt || b_elt->indx < a_elt->indx) 1458 { 1459 /* B is before A. Copy B. */ 1460 next = bitmap_elt_insert_after (a, a_prev, b_elt->indx); 1461 memcpy (next->bits, b_elt->bits, sizeof (next->bits)); 1462 a_prev = next; 1463 b_elt = b_elt->next; 1464 } 1465 else 1466 { 1467 /* Matching elts, generate A = ~A & B. */ 1468 unsigned ix; 1469 BITMAP_WORD ior = 0; 1470 1471 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) 1472 { 1473 BITMAP_WORD cleared = a_elt->bits[ix] & b_elt->bits[ix]; 1474 BITMAP_WORD r = b_elt->bits[ix] ^ cleared; 1475 1476 a_elt->bits[ix] = r; 1477 ior |= r; 1478 } 1479 next = a_elt->next; 1480 if (!ior) 1481 bitmap_element_free (a, a_elt); 1482 else 1483 a_prev = a_elt; 1484 a_elt = next; 1485 b_elt = b_elt->next; 1486 } 1487 } 1488 gcc_checking_assert (!a->current == !a->first 1489 && (!a->current || a->indx == a->current->indx)); 1490 return; 1491 } 1492 1493 1494 /* Insert an element corresponding to A_ELT | B_ELT after DST_PREV, 1495 overwriting DST_ELT if non-NULL. CHANGED is true if the destination bitmap 1496 had already been changed; the new value of CHANGED is returned. */ 1497 1498 static inline bool 1499 bitmap_elt_ior (bitmap dst, bitmap_element *dst_elt, bitmap_element *dst_prev, 1500 const bitmap_element *a_elt, const bitmap_element *b_elt, 1501 bool changed) 1502 { 1503 gcc_assert (a_elt || b_elt); 1504 1505 if (a_elt && b_elt && a_elt->indx == b_elt->indx) 1506 { 1507 /* Matching elts, generate A | B. */ 1508 unsigned ix; 1509 1510 if (!changed && dst_elt && dst_elt->indx == a_elt->indx) 1511 { 1512 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) 1513 { 1514 BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix]; 1515 if (r != dst_elt->bits[ix]) 1516 { 1517 dst_elt->bits[ix] = r; 1518 changed = true; 1519 } 1520 } 1521 } 1522 else 1523 { 1524 changed = true; 1525 if (!dst_elt) 1526 dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx); 1527 else 1528 dst_elt->indx = a_elt->indx; 1529 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) 1530 { 1531 BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix]; 1532 dst_elt->bits[ix] = r; 1533 } 1534 } 1535 } 1536 else 1537 { 1538 /* Copy a single element. */ 1539 const bitmap_element *src; 1540 1541 if (!b_elt || (a_elt && a_elt->indx < b_elt->indx)) 1542 src = a_elt; 1543 else 1544 src = b_elt; 1545 1546 gcc_checking_assert (src); 1547 changed = bitmap_elt_copy (dst, dst_elt, dst_prev, src, changed); 1548 } 1549 return changed; 1550 } 1551 1552 1553 /* DST = A | B. Return true if DST changes. */ 1554 1555 bool 1556 bitmap_ior (bitmap dst, const_bitmap a, const_bitmap b) 1557 { 1558 bitmap_element *dst_elt = dst->first; 1559 const bitmap_element *a_elt = a->first; 1560 const bitmap_element *b_elt = b->first; 1561 bitmap_element *dst_prev = NULL; 1562 bitmap_element **dst_prev_pnext = &dst->first; 1563 bool changed = false; 1564 1565 gcc_assert (dst != a && dst != b); 1566 1567 while (a_elt || b_elt) 1568 { 1569 changed = bitmap_elt_ior (dst, dst_elt, dst_prev, a_elt, b_elt, changed); 1570 1571 if (a_elt && b_elt && a_elt->indx == b_elt->indx) 1572 { 1573 a_elt = a_elt->next; 1574 b_elt = b_elt->next; 1575 } 1576 else 1577 { 1578 if (a_elt && (!b_elt || a_elt->indx <= b_elt->indx)) 1579 a_elt = a_elt->next; 1580 else if (b_elt && (!a_elt || b_elt->indx <= a_elt->indx)) 1581 b_elt = b_elt->next; 1582 } 1583 1584 dst_prev = *dst_prev_pnext; 1585 dst_prev_pnext = &dst_prev->next; 1586 dst_elt = *dst_prev_pnext; 1587 } 1588 1589 if (dst_elt) 1590 { 1591 changed = true; 1592 /* Ensure that dst->current is valid. */ 1593 dst->current = dst->first; 1594 bitmap_elt_clear_from (dst, dst_elt); 1595 } 1596 gcc_checking_assert (!dst->current == !dst->first); 1597 if (dst->current) 1598 dst->indx = dst->current->indx; 1599 return changed; 1600 } 1601 1602 /* A |= B. Return true if A changes. */ 1603 1604 bool 1605 bitmap_ior_into (bitmap a, const_bitmap b) 1606 { 1607 bitmap_element *a_elt = a->first; 1608 const bitmap_element *b_elt = b->first; 1609 bitmap_element *a_prev = NULL; 1610 bitmap_element **a_prev_pnext = &a->first; 1611 bool changed = false; 1612 1613 if (a == b) 1614 return false; 1615 1616 while (b_elt) 1617 { 1618 /* If A lags behind B, just advance it. */ 1619 if (!a_elt || a_elt->indx == b_elt->indx) 1620 { 1621 changed = bitmap_elt_ior (a, a_elt, a_prev, a_elt, b_elt, changed); 1622 b_elt = b_elt->next; 1623 } 1624 else if (a_elt->indx > b_elt->indx) 1625 { 1626 changed = bitmap_elt_copy (a, NULL, a_prev, b_elt, changed); 1627 b_elt = b_elt->next; 1628 } 1629 1630 a_prev = *a_prev_pnext; 1631 a_prev_pnext = &a_prev->next; 1632 a_elt = *a_prev_pnext; 1633 } 1634 1635 gcc_checking_assert (!a->current == !a->first); 1636 if (a->current) 1637 a->indx = a->current->indx; 1638 return changed; 1639 } 1640 1641 /* DST = A ^ B */ 1642 1643 void 1644 bitmap_xor (bitmap dst, const_bitmap a, const_bitmap b) 1645 { 1646 bitmap_element *dst_elt = dst->first; 1647 const bitmap_element *a_elt = a->first; 1648 const bitmap_element *b_elt = b->first; 1649 bitmap_element *dst_prev = NULL; 1650 1651 gcc_assert (dst != a && dst != b); 1652 if (a == b) 1653 { 1654 bitmap_clear (dst); 1655 return; 1656 } 1657 1658 while (a_elt || b_elt) 1659 { 1660 if (a_elt && b_elt && a_elt->indx == b_elt->indx) 1661 { 1662 /* Matching elts, generate A ^ B. */ 1663 unsigned ix; 1664 BITMAP_WORD ior = 0; 1665 1666 if (!dst_elt) 1667 dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx); 1668 else 1669 dst_elt->indx = a_elt->indx; 1670 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) 1671 { 1672 BITMAP_WORD r = a_elt->bits[ix] ^ b_elt->bits[ix]; 1673 1674 ior |= r; 1675 dst_elt->bits[ix] = r; 1676 } 1677 a_elt = a_elt->next; 1678 b_elt = b_elt->next; 1679 if (ior) 1680 { 1681 dst_prev = dst_elt; 1682 dst_elt = dst_elt->next; 1683 } 1684 } 1685 else 1686 { 1687 /* Copy a single element. */ 1688 const bitmap_element *src; 1689 1690 if (!b_elt || (a_elt && a_elt->indx < b_elt->indx)) 1691 { 1692 src = a_elt; 1693 a_elt = a_elt->next; 1694 } 1695 else 1696 { 1697 src = b_elt; 1698 b_elt = b_elt->next; 1699 } 1700 1701 if (!dst_elt) 1702 dst_elt = bitmap_elt_insert_after (dst, dst_prev, src->indx); 1703 else 1704 dst_elt->indx = src->indx; 1705 memcpy (dst_elt->bits, src->bits, sizeof (dst_elt->bits)); 1706 dst_prev = dst_elt; 1707 dst_elt = dst_elt->next; 1708 } 1709 } 1710 /* Ensure that dst->current is valid. */ 1711 dst->current = dst->first; 1712 bitmap_elt_clear_from (dst, dst_elt); 1713 gcc_checking_assert (!dst->current == !dst->first); 1714 if (dst->current) 1715 dst->indx = dst->current->indx; 1716 } 1717 1718 /* A ^= B */ 1719 1720 void 1721 bitmap_xor_into (bitmap a, const_bitmap b) 1722 { 1723 bitmap_element *a_elt = a->first; 1724 const bitmap_element *b_elt = b->first; 1725 bitmap_element *a_prev = NULL; 1726 1727 if (a == b) 1728 { 1729 bitmap_clear (a); 1730 return; 1731 } 1732 1733 while (b_elt) 1734 { 1735 if (!a_elt || b_elt->indx < a_elt->indx) 1736 { 1737 /* Copy b_elt. */ 1738 bitmap_element *dst = bitmap_elt_insert_after (a, a_prev, b_elt->indx); 1739 memcpy (dst->bits, b_elt->bits, sizeof (dst->bits)); 1740 a_prev = dst; 1741 b_elt = b_elt->next; 1742 } 1743 else if (a_elt->indx < b_elt->indx) 1744 { 1745 a_prev = a_elt; 1746 a_elt = a_elt->next; 1747 } 1748 else 1749 { 1750 /* Matching elts, generate A ^= B. */ 1751 unsigned ix; 1752 BITMAP_WORD ior = 0; 1753 bitmap_element *next = a_elt->next; 1754 1755 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) 1756 { 1757 BITMAP_WORD r = a_elt->bits[ix] ^ b_elt->bits[ix]; 1758 1759 ior |= r; 1760 a_elt->bits[ix] = r; 1761 } 1762 b_elt = b_elt->next; 1763 if (ior) 1764 a_prev = a_elt; 1765 else 1766 bitmap_element_free (a, a_elt); 1767 a_elt = next; 1768 } 1769 } 1770 gcc_checking_assert (!a->current == !a->first); 1771 if (a->current) 1772 a->indx = a->current->indx; 1773 } 1774 1775 /* Return true if two bitmaps are identical. 1776 We do not bother with a check for pointer equality, as that never 1777 occurs in practice. */ 1778 1779 bool 1780 bitmap_equal_p (const_bitmap a, const_bitmap b) 1781 { 1782 const bitmap_element *a_elt; 1783 const bitmap_element *b_elt; 1784 unsigned ix; 1785 1786 for (a_elt = a->first, b_elt = b->first; 1787 a_elt && b_elt; 1788 a_elt = a_elt->next, b_elt = b_elt->next) 1789 { 1790 if (a_elt->indx != b_elt->indx) 1791 return false; 1792 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) 1793 if (a_elt->bits[ix] != b_elt->bits[ix]) 1794 return false; 1795 } 1796 return !a_elt && !b_elt; 1797 } 1798 1799 /* Return true if A AND B is not empty. */ 1800 1801 bool 1802 bitmap_intersect_p (const_bitmap a, const_bitmap b) 1803 { 1804 const bitmap_element *a_elt; 1805 const bitmap_element *b_elt; 1806 unsigned ix; 1807 1808 for (a_elt = a->first, b_elt = b->first; 1809 a_elt && b_elt;) 1810 { 1811 if (a_elt->indx < b_elt->indx) 1812 a_elt = a_elt->next; 1813 else if (b_elt->indx < a_elt->indx) 1814 b_elt = b_elt->next; 1815 else 1816 { 1817 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) 1818 if (a_elt->bits[ix] & b_elt->bits[ix]) 1819 return true; 1820 a_elt = a_elt->next; 1821 b_elt = b_elt->next; 1822 } 1823 } 1824 return false; 1825 } 1826 1827 /* Return true if A AND NOT B is not empty. */ 1828 1829 bool 1830 bitmap_intersect_compl_p (const_bitmap a, const_bitmap b) 1831 { 1832 const bitmap_element *a_elt; 1833 const bitmap_element *b_elt; 1834 unsigned ix; 1835 for (a_elt = a->first, b_elt = b->first; 1836 a_elt && b_elt;) 1837 { 1838 if (a_elt->indx < b_elt->indx) 1839 return true; 1840 else if (b_elt->indx < a_elt->indx) 1841 b_elt = b_elt->next; 1842 else 1843 { 1844 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) 1845 if (a_elt->bits[ix] & ~b_elt->bits[ix]) 1846 return true; 1847 a_elt = a_elt->next; 1848 b_elt = b_elt->next; 1849 } 1850 } 1851 return a_elt != NULL; 1852 } 1853 1854 1855 /* DST = A | (FROM1 & ~FROM2). Return true if DST changes. */ 1856 1857 bool 1858 bitmap_ior_and_compl (bitmap dst, const_bitmap a, const_bitmap b, const_bitmap kill) 1859 { 1860 bool changed = false; 1861 1862 bitmap_element *dst_elt = dst->first; 1863 const bitmap_element *a_elt = a->first; 1864 const bitmap_element *b_elt = b->first; 1865 const bitmap_element *kill_elt = kill->first; 1866 bitmap_element *dst_prev = NULL; 1867 bitmap_element **dst_prev_pnext = &dst->first; 1868 1869 gcc_assert (dst != a && dst != b && dst != kill); 1870 1871 /* Special cases. We don't bother checking for bitmap_equal_p (b, kill). */ 1872 if (b == kill || bitmap_empty_p (b)) 1873 { 1874 changed = !bitmap_equal_p (dst, a); 1875 if (changed) 1876 bitmap_copy (dst, a); 1877 return changed; 1878 } 1879 if (bitmap_empty_p (kill)) 1880 return bitmap_ior (dst, a, b); 1881 if (bitmap_empty_p (a)) 1882 return bitmap_and_compl (dst, b, kill); 1883 1884 while (a_elt || b_elt) 1885 { 1886 bool new_element = false; 1887 1888 if (b_elt) 1889 while (kill_elt && kill_elt->indx < b_elt->indx) 1890 kill_elt = kill_elt->next; 1891 1892 if (b_elt && kill_elt && kill_elt->indx == b_elt->indx 1893 && (!a_elt || a_elt->indx >= b_elt->indx)) 1894 { 1895 bitmap_element tmp_elt; 1896 unsigned ix; 1897 1898 BITMAP_WORD ior = 0; 1899 tmp_elt.indx = b_elt->indx; 1900 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) 1901 { 1902 BITMAP_WORD r = b_elt->bits[ix] & ~kill_elt->bits[ix]; 1903 ior |= r; 1904 tmp_elt.bits[ix] = r; 1905 } 1906 1907 if (ior) 1908 { 1909 changed = bitmap_elt_ior (dst, dst_elt, dst_prev, 1910 a_elt, &tmp_elt, changed); 1911 new_element = true; 1912 if (a_elt && a_elt->indx == b_elt->indx) 1913 a_elt = a_elt->next; 1914 } 1915 1916 b_elt = b_elt->next; 1917 kill_elt = kill_elt->next; 1918 } 1919 else 1920 { 1921 changed = bitmap_elt_ior (dst, dst_elt, dst_prev, 1922 a_elt, b_elt, changed); 1923 new_element = true; 1924 1925 if (a_elt && b_elt && a_elt->indx == b_elt->indx) 1926 { 1927 a_elt = a_elt->next; 1928 b_elt = b_elt->next; 1929 } 1930 else 1931 { 1932 if (a_elt && (!b_elt || a_elt->indx <= b_elt->indx)) 1933 a_elt = a_elt->next; 1934 else if (b_elt && (!a_elt || b_elt->indx <= a_elt->indx)) 1935 b_elt = b_elt->next; 1936 } 1937 } 1938 1939 if (new_element) 1940 { 1941 dst_prev = *dst_prev_pnext; 1942 dst_prev_pnext = &dst_prev->next; 1943 dst_elt = *dst_prev_pnext; 1944 } 1945 } 1946 1947 if (dst_elt) 1948 { 1949 changed = true; 1950 /* Ensure that dst->current is valid. */ 1951 dst->current = dst->first; 1952 bitmap_elt_clear_from (dst, dst_elt); 1953 } 1954 gcc_checking_assert (!dst->current == !dst->first); 1955 if (dst->current) 1956 dst->indx = dst->current->indx; 1957 1958 return changed; 1959 } 1960 1961 /* A |= (FROM1 & ~FROM2). Return true if A changes. */ 1962 1963 bool 1964 bitmap_ior_and_compl_into (bitmap a, const_bitmap from1, const_bitmap from2) 1965 { 1966 bitmap_head tmp; 1967 bool changed; 1968 1969 bitmap_initialize (&tmp, &bitmap_default_obstack); 1970 bitmap_and_compl (&tmp, from1, from2); 1971 changed = bitmap_ior_into (a, &tmp); 1972 bitmap_clear (&tmp); 1973 1974 return changed; 1975 } 1976 1977 /* A |= (B & C). Return true if A changes. */ 1978 1979 bool 1980 bitmap_ior_and_into (bitmap a, const_bitmap b, const_bitmap c) 1981 { 1982 bitmap_element *a_elt = a->first; 1983 const bitmap_element *b_elt = b->first; 1984 const bitmap_element *c_elt = c->first; 1985 bitmap_element and_elt; 1986 bitmap_element *a_prev = NULL; 1987 bitmap_element **a_prev_pnext = &a->first; 1988 bool changed = false; 1989 unsigned ix; 1990 1991 if (b == c) 1992 return bitmap_ior_into (a, b); 1993 if (bitmap_empty_p (b) || bitmap_empty_p (c)) 1994 return false; 1995 1996 and_elt.indx = -1; 1997 while (b_elt && c_elt) 1998 { 1999 BITMAP_WORD overall; 2000 2001 /* Find a common item of B and C. */ 2002 while (b_elt->indx != c_elt->indx) 2003 { 2004 if (b_elt->indx < c_elt->indx) 2005 { 2006 b_elt = b_elt->next; 2007 if (!b_elt) 2008 goto done; 2009 } 2010 else 2011 { 2012 c_elt = c_elt->next; 2013 if (!c_elt) 2014 goto done; 2015 } 2016 } 2017 2018 overall = 0; 2019 and_elt.indx = b_elt->indx; 2020 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) 2021 { 2022 and_elt.bits[ix] = b_elt->bits[ix] & c_elt->bits[ix]; 2023 overall |= and_elt.bits[ix]; 2024 } 2025 2026 b_elt = b_elt->next; 2027 c_elt = c_elt->next; 2028 if (!overall) 2029 continue; 2030 2031 /* Now find a place to insert AND_ELT. */ 2032 do 2033 { 2034 ix = a_elt ? a_elt->indx : and_elt.indx; 2035 if (ix == and_elt.indx) 2036 changed = bitmap_elt_ior (a, a_elt, a_prev, a_elt, &and_elt, changed); 2037 else if (ix > and_elt.indx) 2038 changed = bitmap_elt_copy (a, NULL, a_prev, &and_elt, changed); 2039 2040 a_prev = *a_prev_pnext; 2041 a_prev_pnext = &a_prev->next; 2042 a_elt = *a_prev_pnext; 2043 2044 /* If A lagged behind B/C, we advanced it so loop once more. */ 2045 } 2046 while (ix < and_elt.indx); 2047 } 2048 2049 done: 2050 gcc_checking_assert (!a->current == !a->first); 2051 if (a->current) 2052 a->indx = a->current->indx; 2053 return changed; 2054 } 2055 2056 /* Compute hash of bitmap (for purposes of hashing). */ 2057 hashval_t 2058 bitmap_hash (const_bitmap head) 2059 { 2060 const bitmap_element *ptr; 2061 BITMAP_WORD hash = 0; 2062 int ix; 2063 2064 for (ptr = head->first; ptr; ptr = ptr->next) 2065 { 2066 hash ^= ptr->indx; 2067 for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++) 2068 hash ^= ptr->bits[ix]; 2069 } 2070 return (hashval_t)hash; 2071 } 2072 2073 2074 /* Debugging function to print out the contents of a bitmap. */ 2075 2076 DEBUG_FUNCTION void 2077 debug_bitmap_file (FILE *file, const_bitmap head) 2078 { 2079 const bitmap_element *ptr; 2080 2081 fprintf (file, "\nfirst = " HOST_PTR_PRINTF 2082 " current = " HOST_PTR_PRINTF " indx = %u\n", 2083 (void *) head->first, (void *) head->current, head->indx); 2084 2085 for (ptr = head->first; ptr; ptr = ptr->next) 2086 { 2087 unsigned int i, j, col = 26; 2088 2089 fprintf (file, "\t" HOST_PTR_PRINTF " next = " HOST_PTR_PRINTF 2090 " prev = " HOST_PTR_PRINTF " indx = %u\n\t\tbits = {", 2091 (const void*) ptr, (const void*) ptr->next, 2092 (const void*) ptr->prev, ptr->indx); 2093 2094 for (i = 0; i < BITMAP_ELEMENT_WORDS; i++) 2095 for (j = 0; j < BITMAP_WORD_BITS; j++) 2096 if ((ptr->bits[i] >> j) & 1) 2097 { 2098 if (col > 70) 2099 { 2100 fprintf (file, "\n\t\t\t"); 2101 col = 24; 2102 } 2103 2104 fprintf (file, " %u", (ptr->indx * BITMAP_ELEMENT_ALL_BITS 2105 + i * BITMAP_WORD_BITS + j)); 2106 col += 4; 2107 } 2108 2109 fprintf (file, " }\n"); 2110 } 2111 } 2112 2113 /* Function to be called from the debugger to print the contents 2114 of a bitmap. */ 2115 2116 DEBUG_FUNCTION void 2117 debug_bitmap (const_bitmap head) 2118 { 2119 debug_bitmap_file (stderr, head); 2120 } 2121 2122 /* Function to print out the contents of a bitmap. Unlike debug_bitmap_file, 2123 it does not print anything but the bits. */ 2124 2125 DEBUG_FUNCTION void 2126 bitmap_print (FILE *file, const_bitmap head, const char *prefix, 2127 const char *suffix) 2128 { 2129 const char *comma = ""; 2130 unsigned i; 2131 bitmap_iterator bi; 2132 2133 fputs (prefix, file); 2134 EXECUTE_IF_SET_IN_BITMAP (head, 0, i, bi) 2135 { 2136 fprintf (file, "%s%d", comma, i); 2137 comma = ", "; 2138 } 2139 fputs (suffix, file); 2140 } 2141 2142 /* Output per-bitmap memory usage statistics. */ 2143 void 2144 dump_bitmap_statistics (void) 2145 { 2146 if (!GATHER_STATISTICS) 2147 return; 2148 2149 bitmap_mem_desc.dump (BITMAP_ORIGIN); 2150 } 2151 2152 DEBUG_FUNCTION void 2153 debug (const bitmap_head &ref) 2154 { 2155 dump_bitmap (stderr, &ref); 2156 } 2157 2158 DEBUG_FUNCTION void 2159 debug (const bitmap_head *ptr) 2160 { 2161 if (ptr) 2162 debug (*ptr); 2163 else 2164 fprintf (stderr, "<nil>\n"); 2165 } 2166 2167 #if CHECKING_P 2168 2169 namespace selftest { 2170 2171 /* Selftests for bitmaps. */ 2172 2173 /* Freshly-created bitmaps ought to be empty. */ 2174 2175 static void 2176 test_gc_alloc () 2177 { 2178 bitmap b = bitmap_gc_alloc (); 2179 ASSERT_TRUE (bitmap_empty_p (b)); 2180 } 2181 2182 /* Verify bitmap_set_range. */ 2183 2184 static void 2185 test_set_range () 2186 { 2187 bitmap b = bitmap_gc_alloc (); 2188 ASSERT_TRUE (bitmap_empty_p (b)); 2189 2190 bitmap_set_range (b, 7, 5); 2191 ASSERT_FALSE (bitmap_empty_p (b)); 2192 ASSERT_EQ (5, bitmap_count_bits (b)); 2193 2194 /* Verify bitmap_bit_p at the boundaries. */ 2195 ASSERT_FALSE (bitmap_bit_p (b, 6)); 2196 ASSERT_TRUE (bitmap_bit_p (b, 7)); 2197 ASSERT_TRUE (bitmap_bit_p (b, 11)); 2198 ASSERT_FALSE (bitmap_bit_p (b, 12)); 2199 } 2200 2201 /* Verify splitting a range into two pieces using bitmap_clear_bit. */ 2202 2203 static void 2204 test_clear_bit_in_middle () 2205 { 2206 bitmap b = bitmap_gc_alloc (); 2207 2208 /* Set b to [100..200]. */ 2209 bitmap_set_range (b, 100, 100); 2210 ASSERT_EQ (100, bitmap_count_bits (b)); 2211 2212 /* Clear a bit in the middle. */ 2213 bool changed = bitmap_clear_bit (b, 150); 2214 ASSERT_TRUE (changed); 2215 ASSERT_EQ (99, bitmap_count_bits (b)); 2216 ASSERT_TRUE (bitmap_bit_p (b, 149)); 2217 ASSERT_FALSE (bitmap_bit_p (b, 150)); 2218 ASSERT_TRUE (bitmap_bit_p (b, 151)); 2219 } 2220 2221 /* Verify bitmap_copy. */ 2222 2223 static void 2224 test_copying () 2225 { 2226 bitmap src = bitmap_gc_alloc (); 2227 bitmap_set_range (src, 40, 10); 2228 2229 bitmap dst = bitmap_gc_alloc (); 2230 ASSERT_FALSE (bitmap_equal_p (src, dst)); 2231 bitmap_copy (dst, src); 2232 ASSERT_TRUE (bitmap_equal_p (src, dst)); 2233 2234 /* Verify that we can make them unequal again... */ 2235 bitmap_set_range (src, 70, 5); 2236 ASSERT_FALSE (bitmap_equal_p (src, dst)); 2237 2238 /* ...and that changing src after the copy didn't affect 2239 the other: */ 2240 ASSERT_FALSE (bitmap_bit_p (dst, 70)); 2241 } 2242 2243 /* Verify bitmap_single_bit_set_p. */ 2244 2245 static void 2246 test_bitmap_single_bit_set_p () 2247 { 2248 bitmap b = bitmap_gc_alloc (); 2249 2250 ASSERT_FALSE (bitmap_single_bit_set_p (b)); 2251 2252 bitmap_set_range (b, 42, 1); 2253 ASSERT_TRUE (bitmap_single_bit_set_p (b)); 2254 ASSERT_EQ (42, bitmap_first_set_bit (b)); 2255 2256 bitmap_set_range (b, 1066, 1); 2257 ASSERT_FALSE (bitmap_single_bit_set_p (b)); 2258 ASSERT_EQ (42, bitmap_first_set_bit (b)); 2259 2260 bitmap_clear_range (b, 0, 100); 2261 ASSERT_TRUE (bitmap_single_bit_set_p (b)); 2262 ASSERT_EQ (1066, bitmap_first_set_bit (b)); 2263 } 2264 2265 /* Run all of the selftests within this file. */ 2266 2267 void 2268 bitmap_c_tests () 2269 { 2270 test_gc_alloc (); 2271 test_set_range (); 2272 test_clear_bit_in_middle (); 2273 test_copying (); 2274 test_bitmap_single_bit_set_p (); 2275 } 2276 2277 } // namespace selftest 2278 #endif /* CHECKING_P */ 2279 2280 #include "gt-bitmap.h" 2281