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