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