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