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