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